libgo/runtime/mcentral.c

   1 // Copyright 2009 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 // Central free lists.
   6 //
   7 // See malloc.h for an overview.
   8 //
   9 // The MCentral doesn't actually contain the list of free objects; the MSpan does.
  10 // Each MCentral is two lists of MSpans: those with free objects (c->nonempty)
  11 // and those that are completely allocated (c->empty).
  12 //
  13 // TODO(rsc): tcmalloc uses a "transfer cache" to split the list
  14 // into sections of class_to_transfercount[sizeclass] objects
  15 // so that it is faster to move those lists between MCaches and MCentrals.
  16
  17 #include "runtime.h"
  18 #include "arch.h"
  19 #include "malloc.h"
  20
  21 static bool MCentral_Grow(MCentral *c);
  22 static void MCentral_Free(MCentral *c, void *v);
  23
  24 // Initialize a single central free list.
  25 void
  26 runtime_MCentral_Init(MCentral *c, int32 sizeclass)
  27 {
  28         c->sizeclass = sizeclass;
  29         runtime_MSpanList_Init(&c->nonempty);
  30         runtime_MSpanList_Init(&c->empty);
  31 }
  32
  33 // Allocate a list of objects from the central free list.
  34 // Return the number of objects allocated.
  35 // The objects are linked together by their first words.
  36 // On return, *pfirst points at the first object.
  37 int32
  38 runtime_MCentral_AllocList(MCentral *c, MLink **pfirst)
  39 {
  40         MSpan *s;
  41         int32 cap, n;
  42
  43         runtime_lock(c);
  44         // Replenish central list if empty.
  45         if(runtime_MSpanList_IsEmpty(&c->nonempty)) {
  46                 if(!MCentral_Grow(c)) {
  47                         runtime_unlock(c);
  48                         *pfirst = nil;
  49                         return 0;
  50                 }
  51         }
  52         s = c->nonempty.next;
  53         cap = (s->npages << PageShift) / s->elemsize;
  54         n = cap - s->ref;
  55         *pfirst = s->freelist;
  56         s->freelist = nil;
  57         s->ref += n;
  58         c->nfree -= n;
  59         runtime_MSpanList_Remove(s);
  60         runtime_MSpanList_Insert(&c->empty, s);
  61         runtime_unlock(c);
  62         return n;
  63 }
  64
  65 // Free the list of objects back into the central free list.
  66 void
  67 runtime_MCentral_FreeList(MCentral *c, MLink *start)
  68 {
  69         MLink *next;
  70
  71         runtime_lock(c);
  72         for(; start != nil; start = next) {
  73                 next = start->next;
  74                 MCentral_Free(c, start);
  75         }
  76         runtime_unlock(c);
  77 }
  78
  79 // Helper: free one object back into the central free list.
  80 static void
  81 MCentral_Free(MCentral *c, void *v)
  82 {
  83         MSpan *s;
  84         MLink *p;
  85         int32 size;
  86
  87         // Find span for v.
  88         s = runtime_MHeap_Lookup(&runtime_mheap, v);
  89         if(s == nil || s->ref == 0)
  90                 runtime_throw("invalid free");
  91
  92         // Move to nonempty if necessary.
  93         if(s->freelist == nil) {
  94                 runtime_MSpanList_Remove(s);
  95                 runtime_MSpanList_Insert(&c->nonempty, s);
  96         }
  97
  98         // Add v back to s's free list.
  99         p = v;
 100         p->next = s->freelist;
 101         s->freelist = p;
 102         c->nfree++;
 103
 104         // If s is completely freed, return it to the heap.
 105         if(--s->ref == 0) {
 106                 size = runtime_class_to_size[c->sizeclass];
 107                 runtime_MSpanList_Remove(s);
 108                 runtime_unmarkspan((byte*)(s->start<<PageShift), s->npages<<PageShift);
 109                 *(uintptr*)(s->start<<PageShift) = 1;  // needs zeroing
 110                 s->freelist = nil;
 111                 c->nfree -= (s->npages << PageShift) / size;
 112                 runtime_unlock(c);
 113                 runtime_MHeap_Free(&runtime_mheap, s, 0);
 114                 runtime_lock(c);
 115         }
 116 }
 117
 118 // Free n objects from a span s back into the central free list c.
 119 // Called from GC.
 120 void
 121 runtime_MCentral_FreeSpan(MCentral *c, MSpan *s, int32 n, MLink *start, MLink *end)
 122 {
 123         int32 size;
 124
 125         runtime_lock(c);
 126
 127         // Move to nonempty if necessary.
 128         if(s->freelist == nil) {
 129                 runtime_MSpanList_Remove(s);
 130                 runtime_MSpanList_Insert(&c->nonempty, s);
 131         }
 132
 133         // Add the objects back to s's free list.
 134         end->next = s->freelist;
 135         s->freelist = start;
 136         s->ref -= n;
 137         c->nfree += n;
 138
 139         // If s is completely freed, return it to the heap.
 140         if(s->ref == 0) {
 141                 size = runtime_class_to_size[c->sizeclass];
 142                 runtime_MSpanList_Remove(s);
 143                 *(uintptr*)(s->start<<PageShift) = 1;  // needs zeroing
 144                 s->freelist = nil;
 145                 c->nfree -= (s->npages << PageShift) / size;
 146                 runtime_unlock(c);
 147                 runtime_unmarkspan((byte*)(s->start<<PageShift), s->npages<<PageShift);
 148                 runtime_MHeap_Free(&runtime_mheap, s, 0);
 149         } else {
 150                 runtime_unlock(c);
 151         }
 152 }
 153
 154 void
 155 runtime_MGetSizeClassInfo(int32 sizeclass, uintptr *sizep, int32 *npagesp, int32 *nobj)
 156 {
 157         int32 size;
 158         int32 npages;
 159
 160         npages = runtime_class_to_allocnpages[sizeclass];
 161         size = runtime_class_to_size[sizeclass];
 162         *npagesp = npages;
 163         *sizep = size;
 164         *nobj = (npages << PageShift) / size;
 165 }
 166
 167 // Fetch a new span from the heap and
 168 // carve into objects for the free list.
 169 static bool
 170 MCentral_Grow(MCentral *c)
 171 {
 172         int32 i, n, npages;
 173         uintptr size;
 174         MLink **tailp, *v;
 175         byte *p;
 176         MSpan *s;
 177
 178         runtime_unlock(c);
 179         runtime_MGetSizeClassInfo(c->sizeclass, &size, &npages, &n);
 180         s = runtime_MHeap_Alloc(&runtime_mheap, npages, c->sizeclass, 0, 1);
 181         if(s == nil) {
 182                 // TODO(rsc): Log out of memory
 183                 runtime_lock(c);
 184                 return false;
 185         }
 186
 187         // Carve span into sequence of blocks.
 188         tailp = &s->freelist;
 189         p = (byte*)(s->start << PageShift);
 190         s->limit = p + size*n;
 191         for(i=0; i<n; i++) {
 192                 v = (MLink*)p;
 193                 *tailp = v;
 194                 tailp = &v->next;
 195                 p += size;
 196         }
 197         *tailp = nil;
 198         runtime_markspan((byte*)(s->start<<PageShift), size, n, size*n < (s->npages<<PageShift));
 199
 200         runtime_lock(c);
 201         c->nfree += n;
 202         runtime_MSpanList_Insert(&c->nonempty, s);
 203         return true;
 204 }