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.go 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).
15 import "runtime/internal/atomic"
17 // Central list of free objects of a given size.
20 type mcentral
struct {
23 nonempty mSpanList
// list of spans with a free object, ie a nonempty free list
24 empty mSpanList
// list of spans with no free objects (or cached in an mcache)
26 // nmalloc is the cumulative count of objects allocated from
27 // this mcentral, assuming all spans in mcaches are
28 // fully-allocated. Written atomically, read under STW.
32 // Initialize a single central free list.
33 func (c
*mcentral
) init(spc spanClass
) {
39 // Allocate a span to use in an MCache.
40 func (c
*mcentral
) cacheSpan() *mspan
{
41 // Deduct credit for this span allocation and sweep if necessary.
42 spanBytes
:= uintptr(class_to_allocnpages
[c
.spanclass
.sizeclass()]) * _PageSize
43 deductSweepCredit(spanBytes
, 0)
53 for s
= c
.nonempty
.first
; s
!= nil; s
= s
.next
{
54 if s
.sweepgen
== sg
-2 && atomic
.Cas(&s
.sweepgen
, sg
-2, sg
-1) {
61 if s
.sweepgen
== sg
-1 {
62 // the span is being swept by background sweeper, skip
65 // we have a nonempty span that does not require sweeping, allocate from it
72 for s
= c
.empty
.first
; s
!= nil; s
= s
.next
{
73 if s
.sweepgen
== sg
-2 && atomic
.Cas(&s
.sweepgen
, sg
-2, sg
-1) {
74 // we have an empty span that requires sweeping,
75 // sweep it and see if we can free some space in it
77 // swept spans are at the end of the list
81 freeIndex
:= s
.nextFreeIndex()
82 if freeIndex
!= s
.nelems
{
83 s
.freeindex
= freeIndex
87 // the span is still empty after sweep
88 // it is already in the empty list, so just retry
91 if s
.sweepgen
== sg
-1 {
92 // the span is being swept by background sweeper, skip
95 // already swept empty span,
96 // all subsequent ones must also be either swept or in process of sweeping
105 // Replenish central list if empty.
111 c
.empty
.insertBack(s
)
114 // At this point s is a non-empty span, queued at the end of the empty list,
117 if trace
.enabled
&& !traceDone
{
120 cap := int32((s
.npages
<< _PageShift
) / s
.elemsize
)
121 n
:= cap - int32(s
.allocCount
)
122 if n
== 0 || s
.freeindex
== s
.nelems ||
uintptr(s
.allocCount
) == s
.nelems
{
123 throw("span has no free objects")
125 // Assume all objects from this span will be allocated in the
126 // mcache. If it gets uncached, we'll adjust this.
127 atomic
.Xadd64(&c
.nmalloc
, int64(n
))
128 usedBytes
:= uintptr(s
.allocCount
) * s
.elemsize
129 atomic
.Xadd64(&memstats
.heap_live
, int64(spanBytes
)-int64(usedBytes
))
131 // heap_live changed.
134 if gcBlackenEnabled
!= 0 {
135 // heap_live changed.
136 gcController
.revise()
139 freeByteBase
:= s
.freeindex
&^ (64 - 1)
140 whichByte
:= freeByteBase
/ 8
141 // Init alloc bits cache.
142 s
.refillAllocCache(whichByte
)
144 // Adjust the allocCache so that s.freeindex corresponds to the low bit in
146 s
.allocCache
>>= s
.freeindex
% 64
151 // Return span from an MCache.
152 func (c
*mcentral
) uncacheSpan(s
*mspan
) {
157 if s
.allocCount
== 0 {
158 throw("uncaching span but s.allocCount == 0")
161 cap := int32((s
.npages
<< _PageShift
) / s
.elemsize
)
162 n
:= cap - int32(s
.allocCount
)
166 // mCentral_CacheSpan conservatively counted
167 // unallocated slots in heap_live. Undo this.
168 atomic
.Xadd64(&memstats
.heap_live
, -int64(n
)*int64(s
.elemsize
))
169 // cacheSpan updated alloc assuming all objects on s
170 // were going to be allocated. Adjust for any that
172 atomic
.Xadd64(&c
.nmalloc
, -int64(n
))
177 // freeSpan updates c and s after sweeping s.
178 // It sets s's sweepgen to the latest generation,
179 // and, based on the number of free objects in s,
180 // moves s to the appropriate list of c or returns it
182 // freeSpan returns true if s was returned to the heap.
183 // If preserve=true, it does not move s (the caller
184 // must take care of it).
185 func (c
*mcentral
) freeSpan(s
*mspan
, preserve
bool, wasempty
bool) bool {
187 throw("freeSpan given cached span")
192 // preserve is set only when called from MCentral_CacheSpan above,
193 // the span must be in the empty list.
195 throw("can't preserve unlinked span")
197 atomic
.Store(&s
.sweepgen
, mheap_
.sweepgen
)
203 // Move to nonempty if necessary.
209 // delay updating sweepgen until here. This is the signal that
210 // the span may be used in an MCache, so it must come after the
211 // linked list operations above (actually, just after the
213 atomic
.Store(&s
.sweepgen
, mheap_
.sweepgen
)
215 if s
.allocCount
!= 0 {
222 mheap_
.freeSpan(s
, 0)
226 // grow allocates a new empty span from the heap and initializes it for c's size class.
227 func (c
*mcentral
) grow() *mspan
{
228 npages
:= uintptr(class_to_allocnpages
[c
.spanclass
.sizeclass()])
229 size
:= uintptr(class_to_size
[c
.spanclass
.sizeclass()])
230 n
:= (npages
<< _PageShift
) / size
232 s
:= mheap_
.alloc(npages
, c
.spanclass
, false, true)
240 heapBitsForSpan(s
.base()).initSpan(s
)