Implement a flag -fext-numeric-literals that allows control of whether GNU
[official-gcc.git] / libgo / runtime / mcentral.c
blob670a647b9613f3683a544cb5b3f96f5fa383ea3c
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.
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).
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.
17 #include "runtime.h"
18 #include "arch.h"
19 #include "malloc.h"
21 static bool MCentral_Grow(MCentral *c);
22 static void* MCentral_Alloc(MCentral *c);
23 static void MCentral_Free(MCentral *c, void *v);
25 // Initialize a single central free list.
26 void
27 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.
38 int32
39 runtime_MCentral_AllocList(MCentral *c, int32 n, MLink **pfirst)
41 MLink *first, *last, *v;
42 int32 i;
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;
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;
62 last->next = nil;
63 c->nfree -= i;
65 runtime_unlock(c);
66 *pfirst = first;
67 return i;
70 // Helper: allocate one object from the central free list.
71 static void*
72 MCentral_Alloc(MCentral *c)
74 MSpan *s;
75 MLink *v;
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);
87 return v;
90 // Free n objects back into the central free list.
91 void
92 runtime_MCentral_FreeList(MCentral *c, int32 n, MLink *start)
94 MLink *v, *next;
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);
101 runtime_lock(c);
102 for(v=start; v; v=next) {
103 next = v->next;
104 MCentral_Free(c, v);
106 runtime_unlock(c);
109 // Helper: free one object back into the central free list.
110 static void
111 MCentral_Free(MCentral *c, void *v)
113 MSpan *s;
114 MLink *p;
115 int32 size;
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");
122 // Move to nonempty if necessary.
123 if(s->freelist == nil) {
124 runtime_MSpanList_Remove(s);
125 runtime_MSpanList_Insert(&c->nonempty, s);
128 // Add v back to s's free list.
129 p = v;
130 p->next = s->freelist;
131 s->freelist = p;
132 c->nfree++;
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);
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)
153 int32 size;
155 runtime_lock(c);
157 // Move to nonempty if necessary.
158 if(s->freelist == nil) {
159 runtime_MSpanList_Remove(s);
160 runtime_MSpanList_Insert(&c->nonempty, s);
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;
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);
184 void
185 runtime_MGetSizeClassInfo(int32 sizeclass, uintptr *sizep, int32 *npagesp, int32 *nobj)
187 int32 size;
188 int32 npages;
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;
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)
202 int32 i, n, npages;
203 uintptr size;
204 MLink **tailp, *v;
205 byte *p;
206 MSpan *s;
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;
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;
227 *tailp = nil;
228 runtime_markspan((byte*)(s->start<<PageShift), size, n, size*n < (s->npages<<PageShift));
230 runtime_lock(c);
231 c->nfree += n;
232 runtime_MSpanList_Insert(&c->nonempty, s);
233 return true;