| // Copyright 2020 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. |
| |
| package runtime |
| |
| import ( |
| "internal/cpu" |
| "internal/goarch" |
| "runtime/internal/atomic" |
| "unsafe" |
| ) |
| |
| // A spanSet is a set of *mspans. |
| // |
| // spanSet is safe for concurrent push and pop operations. |
| type spanSet struct { |
| // A spanSet is a two-level data structure consisting of a |
| // growable spine that points to fixed-sized blocks. The spine |
| // can be accessed without locks, but adding a block or |
| // growing it requires taking the spine lock. |
| // |
| // Because each mspan covers at least 8K of heap and takes at |
| // most 8 bytes in the spanSet, the growth of the spine is |
| // quite limited. |
| // |
| // The spine and all blocks are allocated off-heap, which |
| // allows this to be used in the memory manager and avoids the |
| // need for write barriers on all of these. spanSetBlocks are |
| // managed in a pool, though never freed back to the operating |
| // system. We never release spine memory because there could be |
| // concurrent lock-free access and we're likely to reuse it |
| // anyway. (In principle, we could do this during STW.) |
| |
| spineLock mutex |
| spine atomicSpanSetSpinePointer // *[N]atomic.Pointer[spanSetBlock] |
| spineLen atomic.Uintptr // Spine array length |
| spineCap uintptr // Spine array cap, accessed under spineLock |
| |
| // index is the head and tail of the spanSet in a single field. |
| // The head and the tail both represent an index into the logical |
| // concatenation of all blocks, with the head always behind or |
| // equal to the tail (indicating an empty set). This field is |
| // always accessed atomically. |
| // |
| // The head and the tail are only 32 bits wide, which means we |
| // can only support up to 2^32 pushes before a reset. If every |
| // span in the heap were stored in this set, and each span were |
| // the minimum size (1 runtime page, 8 KiB), then roughly the |
| // smallest heap which would be unrepresentable is 32 TiB in size. |
| index atomicHeadTailIndex |
| } |
| |
| const ( |
| spanSetBlockEntries = 512 // 4KB on 64-bit |
| spanSetInitSpineCap = 256 // Enough for 1GB heap on 64-bit |
| ) |
| |
| type spanSetBlock struct { |
| // Free spanSetBlocks are managed via a lock-free stack. |
| lfnode |
| |
| // popped is the number of pop operations that have occurred on |
| // this block. This number is used to help determine when a block |
| // may be safely recycled. |
| popped atomic.Uint32 |
| |
| // spans is the set of spans in this block. |
| spans [spanSetBlockEntries]atomicMSpanPointer |
| } |
| |
| // push adds span s to buffer b. push is safe to call concurrently |
| // with other push and pop operations. |
| func (b *spanSet) push(s *mspan) { |
| // Obtain our slot. |
| cursor := uintptr(b.index.incTail().tail() - 1) |
| top, bottom := cursor/spanSetBlockEntries, cursor%spanSetBlockEntries |
| |
| // Do we need to add a block? |
| spineLen := b.spineLen.Load() |
| var block *spanSetBlock |
| retry: |
| if top < spineLen { |
| block = b.spine.Load().lookup(top).Load() |
| } else { |
| // Add a new block to the spine, potentially growing |
| // the spine. |
| lock(&b.spineLock) |
| // spineLen cannot change until we release the lock, |
| // but may have changed while we were waiting. |
| spineLen = b.spineLen.Load() |
| if top < spineLen { |
| unlock(&b.spineLock) |
| goto retry |
| } |
| |
| spine := b.spine.Load() |
| if spineLen == b.spineCap { |
| // Grow the spine. |
| newCap := b.spineCap * 2 |
| if newCap == 0 { |
| newCap = spanSetInitSpineCap |
| } |
| newSpine := persistentalloc(newCap*goarch.PtrSize, cpu.CacheLineSize, &memstats.gcMiscSys) |
| if b.spineCap != 0 { |
| // Blocks are allocated off-heap, so |
| // no write barriers. |
| memmove(newSpine, spine.p, b.spineCap*goarch.PtrSize) |
| } |
| spine = spanSetSpinePointer{newSpine} |
| |
| // Spine is allocated off-heap, so no write barrier. |
| b.spine.StoreNoWB(spine) |
| b.spineCap = newCap |
| // We can't immediately free the old spine |
| // since a concurrent push with a lower index |
| // could still be reading from it. We let it |
| // leak because even a 1TB heap would waste |
| // less than 2MB of memory on old spines. If |
| // this is a problem, we could free old spines |
| // during STW. |
| } |
| |
| // Allocate a new block from the pool. |
| block = spanSetBlockPool.alloc() |
| |
| // Add it to the spine. |
| // Blocks are allocated off-heap, so no write barrier. |
| spine.lookup(top).StoreNoWB(block) |
| b.spineLen.Store(spineLen + 1) |
| unlock(&b.spineLock) |
| } |
| |
| // We have a block. Insert the span atomically, since there may be |
| // concurrent readers via the block API. |
| block.spans[bottom].StoreNoWB(s) |
| } |
| |
| // pop removes and returns a span from buffer b, or nil if b is empty. |
| // pop is safe to call concurrently with other pop and push operations. |
| func (b *spanSet) pop() *mspan { |
| var head, tail uint32 |
| claimLoop: |
| for { |
| headtail := b.index.load() |
| head, tail = headtail.split() |
| if head >= tail { |
| // The buf is empty, as far as we can tell. |
| return nil |
| } |
| // Check if the head position we want to claim is actually |
| // backed by a block. |
| spineLen := b.spineLen.Load() |
| if spineLen <= uintptr(head)/spanSetBlockEntries { |
| // We're racing with a spine growth and the allocation of |
| // a new block (and maybe a new spine!), and trying to grab |
| // the span at the index which is currently being pushed. |
| // Instead of spinning, let's just notify the caller that |
| // there's nothing currently here. Spinning on this is |
| // almost definitely not worth it. |
| return nil |
| } |
| // Try to claim the current head by CASing in an updated head. |
| // This may fail transiently due to a push which modifies the |
| // tail, so keep trying while the head isn't changing. |
| want := head |
| for want == head { |
| if b.index.cas(headtail, makeHeadTailIndex(want+1, tail)) { |
| break claimLoop |
| } |
| headtail = b.index.load() |
| head, tail = headtail.split() |
| } |
| // We failed to claim the spot we were after and the head changed, |
| // meaning a popper got ahead of us. Try again from the top because |
| // the buf may not be empty. |
| } |
| top, bottom := head/spanSetBlockEntries, head%spanSetBlockEntries |
| |
| // We may be reading a stale spine pointer, but because the length |
| // grows monotonically and we've already verified it, we'll definitely |
| // be reading from a valid block. |
| blockp := b.spine.Load().lookup(uintptr(top)) |
| |
| // Given that the spine length is correct, we know we will never |
| // see a nil block here, since the length is always updated after |
| // the block is set. |
| block := blockp.Load() |
| s := block.spans[bottom].Load() |
| for s == nil { |
| // We raced with the span actually being set, but given that we |
| // know a block for this span exists, the race window here is |
| // extremely small. Try again. |
| s = block.spans[bottom].Load() |
| } |
| // Clear the pointer. This isn't strictly necessary, but defensively |
| // avoids accidentally re-using blocks which could lead to memory |
| // corruption. This way, we'll get a nil pointer access instead. |
| block.spans[bottom].StoreNoWB(nil) |
| |
| // Increase the popped count. If we are the last possible popper |
| // in the block (note that bottom need not equal spanSetBlockEntries-1 |
| // due to races) then it's our responsibility to free the block. |
| // |
| // If we increment popped to spanSetBlockEntries, we can be sure that |
| // we're the last popper for this block, and it's thus safe to free it. |
| // Every other popper must have crossed this barrier (and thus finished |
| // popping its corresponding mspan) by the time we get here. Because |
| // we're the last popper, we also don't have to worry about concurrent |
| // pushers (there can't be any). Note that we may not be the popper |
| // which claimed the last slot in the block, we're just the last one |
| // to finish popping. |
| if block.popped.Add(1) == spanSetBlockEntries { |
| // Clear the block's pointer. |
| blockp.StoreNoWB(nil) |
| |
| // Return the block to the block pool. |
| spanSetBlockPool.free(block) |
| } |
| return s |
| } |
| |
| // reset resets a spanSet which is empty. It will also clean up |
| // any left over blocks. |
| // |
| // Throws if the buf is not empty. |
| // |
| // reset may not be called concurrently with any other operations |
| // on the span set. |
| func (b *spanSet) reset() { |
| head, tail := b.index.load().split() |
| if head < tail { |
| print("head = ", head, ", tail = ", tail, "\n") |
| throw("attempt to clear non-empty span set") |
| } |
| top := head / spanSetBlockEntries |
| if uintptr(top) < b.spineLen.Load() { |
| // If the head catches up to the tail and the set is empty, |
| // we may not clean up the block containing the head and tail |
| // since it may be pushed into again. In order to avoid leaking |
| // memory since we're going to reset the head and tail, clean |
| // up such a block now, if it exists. |
| blockp := b.spine.Load().lookup(uintptr(top)) |
| block := blockp.Load() |
| if block != nil { |
| // Check the popped value. |
| if block.popped.Load() == 0 { |
| // popped should never be zero because that means we have |
| // pushed at least one value but not yet popped if this |
| // block pointer is not nil. |
| throw("span set block with unpopped elements found in reset") |
| } |
| if block.popped.Load() == spanSetBlockEntries { |
| // popped should also never be equal to spanSetBlockEntries |
| // because the last popper should have made the block pointer |
| // in this slot nil. |
| throw("fully empty unfreed span set block found in reset") |
| } |
| |
| // Clear the pointer to the block. |
| blockp.StoreNoWB(nil) |
| |
| // Return the block to the block pool. |
| spanSetBlockPool.free(block) |
| } |
| } |
| b.index.reset() |
| b.spineLen.Store(0) |
| } |
| |
| // atomicSpanSetSpinePointer is an atomically-accessed spanSetSpinePointer. |
| // |
| // It has the same semantics as atomic.UnsafePointer. |
| type atomicSpanSetSpinePointer struct { |
| a atomic.UnsafePointer |
| } |
| |
| // Loads the spanSetSpinePointer and returns it. |
| // |
| // It has the same semantics as atomic.UnsafePointer. |
| func (s *atomicSpanSetSpinePointer) Load() spanSetSpinePointer { |
| return spanSetSpinePointer{s.a.Load()} |
| } |
| |
| // Stores the spanSetSpinePointer. |
| // |
| // It has the same semantics as atomic.UnsafePointer. |
| func (s *atomicSpanSetSpinePointer) StoreNoWB(p spanSetSpinePointer) { |
| s.a.StoreNoWB(p.p) |
| } |
| |
| // spanSetSpinePointer represents a pointer to a contiguous block of atomic.Pointer[spanSetBlock]. |
| type spanSetSpinePointer struct { |
| p unsafe.Pointer |
| } |
| |
| // lookup returns &s[idx]. |
| func (s spanSetSpinePointer) lookup(idx uintptr) *atomic.Pointer[spanSetBlock] { |
| return (*atomic.Pointer[spanSetBlock])(add(unsafe.Pointer(s.p), goarch.PtrSize*idx)) |
| } |
| |
| // spanSetBlockPool is a global pool of spanSetBlocks. |
| var spanSetBlockPool spanSetBlockAlloc |
| |
| // spanSetBlockAlloc represents a concurrent pool of spanSetBlocks. |
| type spanSetBlockAlloc struct { |
| stack lfstack |
| } |
| |
| // alloc tries to grab a spanSetBlock out of the pool, and if it fails |
| // persistentallocs a new one and returns it. |
| func (p *spanSetBlockAlloc) alloc() *spanSetBlock { |
| if s := (*spanSetBlock)(p.stack.pop()); s != nil { |
| return s |
| } |
| return (*spanSetBlock)(persistentalloc(unsafe.Sizeof(spanSetBlock{}), cpu.CacheLineSize, &memstats.gcMiscSys)) |
| } |
| |
| // free returns a spanSetBlock back to the pool. |
| func (p *spanSetBlockAlloc) free(block *spanSetBlock) { |
| block.popped.Store(0) |
| p.stack.push(&block.lfnode) |
| } |
| |
| // headTailIndex represents a combined 32-bit head and 32-bit tail |
| // of a queue into a single 64-bit value. |
| type headTailIndex uint64 |
| |
| // makeHeadTailIndex creates a headTailIndex value from a separate |
| // head and tail. |
| func makeHeadTailIndex(head, tail uint32) headTailIndex { |
| return headTailIndex(uint64(head)<<32 | uint64(tail)) |
| } |
| |
| // head returns the head of a headTailIndex value. |
| func (h headTailIndex) head() uint32 { |
| return uint32(h >> 32) |
| } |
| |
| // tail returns the tail of a headTailIndex value. |
| func (h headTailIndex) tail() uint32 { |
| return uint32(h) |
| } |
| |
| // split splits the headTailIndex value into its parts. |
| func (h headTailIndex) split() (head uint32, tail uint32) { |
| return h.head(), h.tail() |
| } |
| |
| // atomicHeadTailIndex is an atomically-accessed headTailIndex. |
| type atomicHeadTailIndex struct { |
| u atomic.Uint64 |
| } |
| |
| // load atomically reads a headTailIndex value. |
| func (h *atomicHeadTailIndex) load() headTailIndex { |
| return headTailIndex(h.u.Load()) |
| } |
| |
| // cas atomically compares-and-swaps a headTailIndex value. |
| func (h *atomicHeadTailIndex) cas(old, new headTailIndex) bool { |
| return h.u.CompareAndSwap(uint64(old), uint64(new)) |
| } |
| |
| // incHead atomically increments the head of a headTailIndex. |
| func (h *atomicHeadTailIndex) incHead() headTailIndex { |
| return headTailIndex(h.u.Add(1 << 32)) |
| } |
| |
| // decHead atomically decrements the head of a headTailIndex. |
| func (h *atomicHeadTailIndex) decHead() headTailIndex { |
| return headTailIndex(h.u.Add(-(1 << 32))) |
| } |
| |
| // incTail atomically increments the tail of a headTailIndex. |
| func (h *atomicHeadTailIndex) incTail() headTailIndex { |
| ht := headTailIndex(h.u.Add(1)) |
| // Check for overflow. |
| if ht.tail() == 0 { |
| print("runtime: head = ", ht.head(), ", tail = ", ht.tail(), "\n") |
| throw("headTailIndex overflow") |
| } |
| return ht |
| } |
| |
| // reset clears the headTailIndex to (0, 0). |
| func (h *atomicHeadTailIndex) reset() { |
| h.u.Store(0) |
| } |
| |
| // atomicMSpanPointer is an atomic.Pointer[mspan]. Can't use generics because it's NotInHeap. |
| type atomicMSpanPointer struct { |
| p atomic.UnsafePointer |
| } |
| |
| // Load returns the *mspan. |
| func (p *atomicMSpanPointer) Load() *mspan { |
| return (*mspan)(p.p.Load()) |
| } |
| |
| // Store stores an *mspan. |
| func (p *atomicMSpanPointer) StoreNoWB(s *mspan) { |
| p.p.StoreNoWB(unsafe.Pointer(s)) |
| } |