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 a list of 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, *pfirst points at the first object.
38 runtime_MCentral_AllocList(MCentral
*c
, MLink
**pfirst
)
45 sg
= runtime_mheap
.sweepgen
;
47 for(s
= c
->nonempty
.next
; s
!= &c
->nonempty
; s
= s
->next
) {
48 if(s
->sweepgen
== sg
-2 && runtime_cas(&s
->sweepgen
, sg
-2, sg
-1)) {
50 runtime_MSpan_Sweep(s
);
52 // the span could have been moved to heap, retry
55 if(s
->sweepgen
== sg
-1) {
56 // the span is being swept by background sweeper, skip
59 // we have a nonempty span that does not require sweeping, allocate from it
63 for(s
= c
->empty
.next
; s
!= &c
->empty
; s
= s
->next
) {
64 if(s
->sweepgen
== sg
-2 && runtime_cas(&s
->sweepgen
, sg
-2, sg
-1)) {
65 // we have an empty span that requires sweeping,
66 // sweep it and see if we can free some space in it
67 runtime_MSpanList_Remove(s
);
68 // swept spans are at the end of the list
69 runtime_MSpanList_InsertBack(&c
->empty
, s
);
71 runtime_MSpan_Sweep(s
);
73 // the span could be moved to nonempty or heap, retry
76 if(s
->sweepgen
== sg
-1) {
77 // the span is being swept by background sweeper, skip
80 // already swept empty span,
81 // all subsequent ones must also be either swept or in process of sweeping
85 // Replenish central list if empty.
86 if(!MCentral_Grow(c
)) {
94 cap
= (s
->npages
<< PageShift
) / s
->elemsize
;
96 *pfirst
= s
->freelist
;
100 runtime_MSpanList_Remove(s
);
101 runtime_MSpanList_InsertBack(&c
->empty
, s
);
106 // Free the list of objects back into the central free list.
108 runtime_MCentral_FreeList(MCentral
*c
, MLink
*start
)
113 for(; start
!= nil
; start
= next
) {
115 MCentral_Free(c
, start
);
120 // Helper: free one object back into the central free list.
122 MCentral_Free(MCentral
*c
, void *v
)
129 s
= runtime_MHeap_Lookup(&runtime_mheap
, v
);
130 if(s
== nil
|| s
->ref
== 0)
131 runtime_throw("invalid free");
133 // Move to nonempty if necessary.
134 if(s
->freelist
== nil
) {
135 runtime_MSpanList_Remove(s
);
136 runtime_MSpanList_Insert(&c
->nonempty
, s
);
139 // Add v back to s's free list.
141 p
->next
= s
->freelist
;
145 // If s is completely freed, return it to the heap.
147 size
= runtime_class_to_size
[c
->sizeclass
];
148 runtime_MSpanList_Remove(s
);
149 runtime_unmarkspan((byte
*)(s
->start
<<PageShift
), s
->npages
<<PageShift
);
152 c
->nfree
-= (s
->npages
<< PageShift
) / size
;
154 runtime_MHeap_Free(&runtime_mheap
, s
, 0);
159 // Free n objects from a span s back into the central free list c.
160 // Called during sweep.
161 // Returns true if the span was returned to heap.
163 runtime_MCentral_FreeSpan(MCentral
*c
, MSpan
*s
, int32 n
, MLink
*start
, MLink
*end
)
169 // Move to nonempty if necessary.
170 if(s
->freelist
== nil
) {
171 runtime_MSpanList_Remove(s
);
172 runtime_MSpanList_Insert(&c
->nonempty
, s
);
175 // Add the objects back to s's free list.
176 end
->next
= s
->freelist
;
186 // s is completely freed, return it to the heap.
187 size
= runtime_class_to_size
[c
->sizeclass
];
188 runtime_MSpanList_Remove(s
);
191 c
->nfree
-= (s
->npages
<< PageShift
) / size
;
193 runtime_unmarkspan((byte
*)(s
->start
<<PageShift
), s
->npages
<<PageShift
);
194 runtime_MHeap_Free(&runtime_mheap
, s
, 0);
199 runtime_MGetSizeClassInfo(int32 sizeclass
, uintptr
*sizep
, int32
*npagesp
, int32
*nobj
)
204 npages
= runtime_class_to_allocnpages
[sizeclass
];
205 size
= runtime_class_to_size
[sizeclass
];
208 *nobj
= (npages
<< PageShift
) / size
;
211 // Fetch a new span from the heap and
212 // carve into objects for the free list.
214 MCentral_Grow(MCentral
*c
)
223 runtime_MGetSizeClassInfo(c
->sizeclass
, &size
, &npages
, &n
);
224 s
= runtime_MHeap_Alloc(&runtime_mheap
, npages
, c
->sizeclass
, 0, 1);
226 // TODO(rsc): Log out of memory
231 // Carve span into sequence of blocks.
232 tailp
= &s
->freelist
;
233 p
= (byte
*)(s
->start
<< PageShift
);
234 s
->limit
= p
+ size
*n
;
242 runtime_markspan((byte
*)(s
->start
<<PageShift
), size
, n
, size
*n
< (s
->npages
<<PageShift
));
246 runtime_MSpanList_Insert(&c
->nonempty
, s
);