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.
7 // See malloc.h for an overview.
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).
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.
20 static bool MCentral_Grow(MCentral *c);
21 static void* MCentral_Alloc(MCentral *c);
22 static void MCentral_Free(MCentral *c, void *v);
24 // Initialize a single central free list.
26 runtime_MCentral_Init(MCentral *c, int32 sizeclass)
29 c->sizeclass = sizeclass;
30 runtime_MSpanList_Init(&c->nonempty);
31 runtime_MSpanList_Init(&c->empty);
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.
39 runtime_MCentral_AllocList(MCentral *c, int32 n, MLink **pfirst)
41 MLink *first, *last, *v;
45 // Replenish central list if empty.
46 if(runtime_MSpanList_IsEmpty(&c->nonempty)) {
47 if(!MCentral_Grow(c)) {
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);
58 for(i=1; i<n && (v = MCentral_Alloc(c)) != nil; i++) {
70 // Helper: allocate one object from the central free list.
72 MCentral_Alloc(MCentral *c)
77 if(runtime_MSpanList_IsEmpty(&c->nonempty))
82 s->freelist = v->next;
83 if(s->freelist == nil) {
84 runtime_MSpanList_Remove(s);
85 runtime_MSpanList_Insert(&c->empty, s);
90 // Free n objects back into the central free list.
91 // Return the number of objects allocated.
92 // The objects are linked together by their first words.
93 // On return, *pstart points at the first object and *pend at the last.
95 runtime_MCentral_FreeList(MCentral *c, int32 n, MLink *start)
99 // Assume next == nil marks end of list.
100 // n and end would be useful if we implemented
101 // the transfer cache optimization in the TODO above.
105 for(v=start; v; v=next) {
112 // Helper: free one object back into the central free list.
114 MCentral_Free(MCentral *c, void *v)
122 page = (uintptr)v >> PageShift;
123 s = runtime_MHeap_Lookup(&runtime_mheap, page);
124 if(s == nil || s->ref == 0)
125 runtime_throw("invalid free");
127 // Move to nonempty if necessary.
128 if(s->freelist == nil) {
129 runtime_MSpanList_Remove(s);
130 runtime_MSpanList_Insert(&c->nonempty, s);
133 // Add v back to s's free list.
135 p->next = s->freelist;
139 // If s is completely freed, return it to the heap.
141 size = runtime_class_to_size[c->sizeclass];
142 runtime_MSpanList_Remove(s);
143 // The second word of each freed block indicates
144 // whether it needs to be zeroed. The first word
145 // is the link pointer and must always be cleared.
146 for(p=s->freelist; p; p=next) {
148 if(size > (int32)sizeof(uintptr) && ((uintptr*)p)[1] != 0)
149 runtime_memclr((byte*)p, size);
154 c->nfree -= (s->npages << PageShift) / size;
156 runtime_MHeap_Free(&runtime_mheap, s, 0);
162 runtime_MGetSizeClassInfo(int32 sizeclass, int32 *sizep, int32 *npagesp, int32 *nobj)
167 npages = runtime_class_to_allocnpages[sizeclass];
168 size = runtime_class_to_size[sizeclass];
171 *nobj = (npages << PageShift) / (size + RefcountOverhead);
174 // Fetch a new span from the heap and
175 // carve into objects for the free list.
177 MCentral_Grow(MCentral *c)
179 int32 i, n, npages, size;
185 runtime_MGetSizeClassInfo(c->sizeclass, &size, &npages, &n);
186 s = runtime_MHeap_Alloc(&runtime_mheap, npages, c->sizeclass, 0);
188 // TODO(rsc): Log out of memory
193 // Carve span into sequence of blocks.
194 tailp = &s->freelist;
195 p = (byte*)(s->start << PageShift);
196 s->gcref = (uint32*)(p + size*n);
207 runtime_MSpanList_Insert(&c->nonempty, s);