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_Alloc(MCentral *c);
  23 static void MCentral_Free(MCentral *c, void *v);
  24
  25 // Initialize a single central free list.
  26 void
  27 runtime_MCentral_Init(MCentral *c, int32 sizeclass)
  28 {
  29         c->sizeclass = sizeclass;
  30         runtime_MSpanList_Init(&c->nonempty);
  31         runtime_MSpanList_Init(&c->empty);
  32 }
  33
  34 // Allocate up to n objects from the central free list.
  35 // Return the number of objects allocated.
  36 // The objects are linked together by their first words.
  37 // On return, *pstart points at the first object and *pend at the last.
  38 int32
  39 runtime_MCentral_AllocList(MCentral *c, int32 n, MLink **pfirst)
  40 {
  41         MLink *first, *last, *v;
  42         int32 i;
  43
  44         runtime_lock(c);
  45         // Replenish central list if empty.
  46         if(runtime_MSpanList_IsEmpty(&c->nonempty)) {
  47                 if(!MCentral_Grow(c)) {
  48                         runtime_unlock(c);
  49                         *pfirst = nil;
  50                         return 0;
  51                 }
  52         }
  53
  54         // Copy from list, up to n.
  55         // First one is guaranteed to work, because we just grew the list.
  56         first = MCentral_Alloc(c);
  57         last = first;
  58         for(i=1; i<n && (v = MCentral_Alloc(c)) != nil; i++) {
  59                 last->next = v;
  60                 last = v;
  61         }
  62         last->next = nil;
  63         c->nfree -= i;
  64
  65         runtime_unlock(c);
  66         *pfirst = first;
  67         return i;
  68 }
  69
  70 // Helper: allocate one object from the central free list.
  71 static void*
  72 MCentral_Alloc(MCentral *c)
  73 {
  74         MSpan *s;
  75         MLink *v;
  76
  77         if(runtime_MSpanList_IsEmpty(&c->nonempty))
  78                 return nil;
  79         s = c->nonempty.next;
  80         s->ref++;
  81         v = s->freelist;
  82         s->freelist = v->next;
  83         if(s->freelist == nil) {
  84                 runtime_MSpanList_Remove(s);
  85                 runtime_MSpanList_Insert(&c->empty, s);
  86         }
  87         return v;
  88 }
  89
  90 // Free n objects back into the central free list.
  91 void
  92 runtime_MCentral_FreeList(MCentral *c, int32 n, MLink *start)
  93 {
  94         MLink *v, *next;
  95
  96         // Assume next == nil marks end of list.
  97         // n and end would be useful if we implemented
  98         // the transfer cache optimization in the TODO above.
  99         USED(n);
 100
 101         runtime_lock(c);
 102         for(v=start; v; v=next) {
 103                 next = v->next;
 104                 MCentral_Free(c, v);
 105         }
 106         runtime_unlock(c);
 107 }
 108
 109 // Helper: free one object back into the central free list.
 110 static void
 111 MCentral_Free(MCentral *c, void *v)
 112 {
 113         MSpan *s;
 114         MLink *p;
 115         int32 size;
 116
 117         // Find span for v.
 118         s = runtime_MHeap_Lookup(&runtime_mheap, v);
 119         if(s == nil || s->ref == 0)
 120                 runtime_throw("invalid free");
 121
 122         // Move to nonempty if necessary.
 123         if(s->freelist == nil) {
 124                 runtime_MSpanList_Remove(s);
 125                 runtime_MSpanList_Insert(&c->nonempty, s);
 126         }
 127
 128         // Add v back to s's free list.
 129         p = v;
 130         p->next = s->freelist;
 131         s->freelist = p;
 132         c->nfree++;
 133
 134         // If s is completely freed, return it to the heap.
 135         if(--s->ref == 0) {
 136                 size = runtime_class_to_size[c->sizeclass];
 137                 runtime_MSpanList_Remove(s);
 138                 runtime_unmarkspan((byte*)(s->start<<PageShift), s->npages<<PageShift);
 139                 *(uintptr*)(s->start<<PageShift) = 1;  // needs zeroing
 140                 s->freelist = nil;
 141                 c->nfree -= (s->npages << PageShift) / size;
 142                 runtime_unlock(c);
 143                 runtime_MHeap_Free(&runtime_mheap, s, 0);
 144                 runtime_lock(c);
 145         }
 146 }
 147
 148 // Free n objects from a span s back into the central free list c.
 149 // Called from GC.
 150 void
 151 runtime_MCentral_FreeSpan(MCentral *c, MSpan *s, int32 n, MLink *start, MLink *end)
 152 {
 153         int32 size;
 154
 155         runtime_lock(c);
 156
 157         // Move to nonempty if necessary.
 158         if(s->freelist == nil) {
 159                 runtime_MSpanList_Remove(s);
 160                 runtime_MSpanList_Insert(&c->nonempty, s);
 161         }
 162
 163         // Add the objects back to s's free list.
 164         end->next = s->freelist;
 165         s->freelist = start;
 166         s->ref -= n;
 167         c->nfree += n;
 168
 169         // If s is completely freed, return it to the heap.
 170         if(s->ref == 0) {
 171                 size = runtime_class_to_size[c->sizeclass];
 172                 runtime_MSpanList_Remove(s);
 173                 *(uintptr*)(s->start<<PageShift) = 1;  // needs zeroing
 174                 s->freelist = nil;
 175                 c->nfree -= (s->npages << PageShift) / size;
 176                 runtime_unlock(c);
 177                 runtime_unmarkspan((byte*)(s->start<<PageShift), s->npages<<PageShift);
 178                 runtime_MHeap_Free(&runtime_mheap, s, 0);
 179         } else {
 180                 runtime_unlock(c);
 181         }
 182 }
 183
 184 void
 185 runtime_MGetSizeClassInfo(int32 sizeclass, uintptr *sizep, int32 *npagesp, int32 *nobj)
 186 {
 187         int32 size;
 188         int32 npages;
 189
 190         npages = runtime_class_to_allocnpages[sizeclass];
 191         size = runtime_class_to_size[sizeclass];
 192         *npagesp = npages;
 193         *sizep = size;
 194         *nobj = (npages << PageShift) / size;
 195 }
 196
 197 // Fetch a new span from the heap and
 198 // carve into objects for the free list.
 199 static bool
 200 MCentral_Grow(MCentral *c)
 201 {
 202         int32 i, n, npages;
 203         uintptr size;
 204         MLink **tailp, *v;
 205         byte *p;
 206         MSpan *s;
 207
 208         runtime_unlock(c);
 209         runtime_MGetSizeClassInfo(c->sizeclass, &size, &npages, &n);
 210         s = runtime_MHeap_Alloc(&runtime_mheap, npages, c->sizeclass, 0, 1);
 211         if(s == nil) {
 212                 // TODO(rsc): Log out of memory
 213                 runtime_lock(c);
 214                 return false;
 215         }
 216
 217         // Carve span into sequence of blocks.
 218         tailp = &s->freelist;
 219         p = (byte*)(s->start << PageShift);
 220         s->limit = p + size*n;
 221         for(i=0; i<n; i++) {
 222                 v = (MLink*)p;
 223                 *tailp = v;
 224                 tailp = &v->next;
 225                 p += size;
 226         }
 227         *tailp = nil;
 228         runtime_markspan((byte*)(s->start<<PageShift), size, n, size*n < (s->npages<<PageShift));
 229
 230         runtime_lock(c);
 231         c->nfree += n;
 232         runtime_MSpanList_Insert(&c->nonempty, s);
 233         return true;
 234 }