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