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.
21 static bool MCentral_Grow(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)
28 c->sizeclass = sizeclass;
29 runtime_MSpanList_Init(&c->nonempty);
30 runtime_MSpanList_Init(&c->empty);
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.
38 runtime_MCentral_AllocList(MCentral *c, int32 n, MLink **pfirst)
45 // Replenish central list if empty.
46 if(runtime_MSpanList_IsEmpty(&c->nonempty)) {
47 if(!MCentral_Grow(c)) {
54 cap = (s->npages << PageShift) / s->elemsize;
59 // First one is guaranteed to work, because we just grew the list.
65 s->freelist = last->next;
71 if(s->freelist != nil || s->ref != (uint32)cap) {
72 runtime_throw("invalid freelist");
74 runtime_MSpanList_Remove(s);
75 runtime_MSpanList_Insert(&c->empty, s);
83 // Free n objects back into the central free list.
85 runtime_MCentral_FreeList(MCentral *c, int32 n, MLink *start)
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.
95 for(v=start; v; v=next) {
102 // Helper: free one object back into the central free list.
104 MCentral_Free(MCentral *c, void *v)
111 s = runtime_MHeap_Lookup(&runtime_mheap, v);
112 if(s == nil || s->ref == 0)
113 runtime_throw("invalid free");
115 // Move to nonempty if necessary.
116 if(s->freelist == nil) {
117 runtime_MSpanList_Remove(s);
118 runtime_MSpanList_Insert(&c->nonempty, s);
121 // Add v back to s's free list.
123 p->next = s->freelist;
127 // If s is completely freed, return it to the heap.
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
134 c->nfree -= (s->npages << PageShift) / size;
136 runtime_MHeap_Free(&runtime_mheap, s, 0);
141 // Free n objects from a span s back into the central free list c.
144 runtime_MCentral_FreeSpan(MCentral *c, MSpan *s, int32 n, MLink *start, MLink *end)
150 // Move to nonempty if necessary.
151 if(s->freelist == nil) {
152 runtime_MSpanList_Remove(s);
153 runtime_MSpanList_Insert(&c->nonempty, s);
156 // Add the objects back to s's free list.
157 end->next = s->freelist;
162 // If s is completely freed, return it to the heap.
164 size = runtime_class_to_size[c->sizeclass];
165 runtime_MSpanList_Remove(s);
166 *(uintptr*)(s->start<<PageShift) = 1; // needs zeroing
168 c->nfree -= (s->npages << PageShift) / size;
170 runtime_unmarkspan((byte*)(s->start<<PageShift), s->npages<<PageShift);
171 runtime_MHeap_Free(&runtime_mheap, s, 0);
178 runtime_MGetSizeClassInfo(int32 sizeclass, uintptr *sizep, int32 *npagesp, int32 *nobj)
183 npages = runtime_class_to_allocnpages[sizeclass];
184 size = runtime_class_to_size[sizeclass];
187 *nobj = (npages << PageShift) / size;
190 // Fetch a new span from the heap and
191 // carve into objects for the free list.
193 MCentral_Grow(MCentral *c)
202 runtime_MGetSizeClassInfo(c->sizeclass, &size, &npages, &n);
203 s = runtime_MHeap_Alloc(&runtime_mheap, npages, c->sizeclass, 0, 1);
205 // TODO(rsc): Log out of memory
210 // Carve span into sequence of blocks.
211 tailp = &s->freelist;
212 p = (byte*)(s->start << PageShift);
213 s->limit = p + size*n;
221 runtime_markspan((byte*)(s->start<<PageShift), size, n, size*n < (s->npages<<PageShift));
225 runtime_MSpanList_Insert(&c->nonempty, s);