| // Copyright 2009 The Go Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style |
| // license that can be found in the LICENSE file. |
| |
| // Central free lists. |
| // |
| // See malloc.go for an overview. |
| // |
| // The MCentral doesn't actually contain the list of free objects; the MSpan does. |
| // Each MCentral is two lists of MSpans: those with free objects (c->nonempty) |
| // and those that are completely allocated (c->empty). |
| |
| package runtime |
| |
| import "runtime/internal/atomic" |
| |
| // Central list of free objects of a given size. |
| type mcentral struct { |
| lock mutex |
| sizeclass int32 |
| nonempty mSpanList // list of spans with a free object, ie a nonempty free list |
| empty mSpanList // list of spans with no free objects (or cached in an mcache) |
| } |
| |
| // Initialize a single central free list. |
| func (c *mcentral) init(sizeclass int32) { |
| c.sizeclass = sizeclass |
| c.nonempty.init() |
| c.empty.init() |
| } |
| |
| // Allocate a span to use in an MCache. |
| func (c *mcentral) cacheSpan() *mspan { |
| // Deduct credit for this span allocation and sweep if necessary. |
| spanBytes := uintptr(class_to_allocnpages[c.sizeclass]) * _PageSize |
| deductSweepCredit(spanBytes, 0) |
| |
| lock(&c.lock) |
| sg := mheap_.sweepgen |
| retry: |
| var s *mspan |
| for s = c.nonempty.first; s != nil; s = s.next { |
| if s.sweepgen == sg-2 && atomic.Cas(&s.sweepgen, sg-2, sg-1) { |
| c.nonempty.remove(s) |
| c.empty.insertBack(s) |
| unlock(&c.lock) |
| s.sweep(true) |
| goto havespan |
| } |
| if s.sweepgen == sg-1 { |
| // the span is being swept by background sweeper, skip |
| continue |
| } |
| // we have a nonempty span that does not require sweeping, allocate from it |
| c.nonempty.remove(s) |
| c.empty.insertBack(s) |
| unlock(&c.lock) |
| goto havespan |
| } |
| |
| for s = c.empty.first; s != nil; s = s.next { |
| if s.sweepgen == sg-2 && atomic.Cas(&s.sweepgen, sg-2, sg-1) { |
| // we have an empty span that requires sweeping, |
| // sweep it and see if we can free some space in it |
| c.empty.remove(s) |
| // swept spans are at the end of the list |
| c.empty.insertBack(s) |
| unlock(&c.lock) |
| s.sweep(true) |
| freeIndex := s.nextFreeIndex() |
| if freeIndex != s.nelems { |
| s.freeindex = freeIndex |
| goto havespan |
| } |
| lock(&c.lock) |
| // the span is still empty after sweep |
| // it is already in the empty list, so just retry |
| goto retry |
| } |
| if s.sweepgen == sg-1 { |
| // the span is being swept by background sweeper, skip |
| continue |
| } |
| // already swept empty span, |
| // all subsequent ones must also be either swept or in process of sweeping |
| break |
| } |
| unlock(&c.lock) |
| |
| // Replenish central list if empty. |
| s = c.grow() |
| if s == nil { |
| return nil |
| } |
| lock(&c.lock) |
| c.empty.insertBack(s) |
| unlock(&c.lock) |
| |
| // At this point s is a non-empty span, queued at the end of the empty list, |
| // c is unlocked. |
| havespan: |
| cap := int32((s.npages << _PageShift) / s.elemsize) |
| n := cap - int32(s.allocCount) |
| if n == 0 || s.freeindex == s.nelems || uintptr(s.allocCount) == s.nelems { |
| throw("span has no free objects") |
| } |
| usedBytes := uintptr(s.allocCount) * s.elemsize |
| if usedBytes > 0 { |
| reimburseSweepCredit(usedBytes) |
| } |
| atomic.Xadd64(&memstats.heap_live, int64(spanBytes)-int64(usedBytes)) |
| if trace.enabled { |
| // heap_live changed. |
| traceHeapAlloc() |
| } |
| if gcBlackenEnabled != 0 { |
| // heap_live changed. |
| gcController.revise() |
| } |
| s.incache = true |
| freeByteBase := s.freeindex &^ (64 - 1) |
| whichByte := freeByteBase / 8 |
| // Init alloc bits cache. |
| s.refillAllocCache(whichByte) |
| |
| // Adjust the allocCache so that s.freeindex corresponds to the low bit in |
| // s.allocCache. |
| s.allocCache >>= s.freeindex % 64 |
| |
| return s |
| } |
| |
| // Return span from an MCache. |
| func (c *mcentral) uncacheSpan(s *mspan) { |
| lock(&c.lock) |
| |
| s.incache = false |
| |
| if s.allocCount == 0 { |
| throw("uncaching span but s.allocCount == 0") |
| } |
| |
| cap := int32((s.npages << _PageShift) / s.elemsize) |
| n := cap - int32(s.allocCount) |
| if n > 0 { |
| c.empty.remove(s) |
| c.nonempty.insert(s) |
| // mCentral_CacheSpan conservatively counted |
| // unallocated slots in heap_live. Undo this. |
| atomic.Xadd64(&memstats.heap_live, -int64(n)*int64(s.elemsize)) |
| } |
| unlock(&c.lock) |
| } |
| |
| // freeSpan updates c and s after sweeping s. |
| // It sets s's sweepgen to the latest generation, |
| // and, based on the number of free objects in s, |
| // moves s to the appropriate list of c or returns it |
| // to the heap. |
| // freeSpan returns true if s was returned to the heap. |
| // If preserve=true, it does not move s (the caller |
| // must take care of it). |
| func (c *mcentral) freeSpan(s *mspan, preserve bool, wasempty bool) bool { |
| if s.incache { |
| throw("freeSpan given cached span") |
| } |
| s.needzero = 1 |
| |
| if preserve { |
| // preserve is set only when called from MCentral_CacheSpan above, |
| // the span must be in the empty list. |
| if !s.inList() { |
| throw("can't preserve unlinked span") |
| } |
| atomic.Store(&s.sweepgen, mheap_.sweepgen) |
| return false |
| } |
| |
| lock(&c.lock) |
| |
| // Move to nonempty if necessary. |
| if wasempty { |
| c.empty.remove(s) |
| c.nonempty.insert(s) |
| } |
| |
| // delay updating sweepgen until here. This is the signal that |
| // the span may be used in an MCache, so it must come after the |
| // linked list operations above (actually, just after the |
| // lock of c above.) |
| atomic.Store(&s.sweepgen, mheap_.sweepgen) |
| |
| if s.allocCount != 0 { |
| unlock(&c.lock) |
| return false |
| } |
| |
| c.nonempty.remove(s) |
| unlock(&c.lock) |
| mheap_.freeSpan(s, 0) |
| return true |
| } |
| |
| // grow allocates a new empty span from the heap and initializes it for c's size class. |
| func (c *mcentral) grow() *mspan { |
| npages := uintptr(class_to_allocnpages[c.sizeclass]) |
| size := uintptr(class_to_size[c.sizeclass]) |
| n := (npages << _PageShift) / size |
| |
| s := mheap_.alloc(npages, c.sizeclass, false, true) |
| if s == nil { |
| return nil |
| } |
| |
| p := s.base() |
| s.limit = p + size*n |
| |
| heapBitsForSpan(s.base()).initSpan(s) |
| return s |
| } |