Source file src/runtime/mspanset.go

     1  // Copyright 2020 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.
     4  
     5  package runtime
     6  
     7  import (
     8  	"internal/cpu"
     9  	"internal/goarch"
    10  	"internal/runtime/atomic"
    11  	"unsafe"
    12  )
    13  
    14  // A spanSet is a set of *mspans.
    15  //
    16  // spanSet is safe for concurrent push and pop operations.
    17  type spanSet struct {
    18  	// A spanSet is a two-level data structure consisting of a
    19  	// growable spine that points to fixed-sized blocks. The spine
    20  	// can be accessed without locks, but adding a block or
    21  	// growing it requires taking the spine lock.
    22  	//
    23  	// Because each mspan covers at least 8K of heap and takes at
    24  	// most 8 bytes in the spanSet, the growth of the spine is
    25  	// quite limited.
    26  	//
    27  	// The spine and all blocks are allocated off-heap, which
    28  	// allows this to be used in the memory manager and avoids the
    29  	// need for write barriers on all of these. spanSetBlocks are
    30  	// managed in a pool, though never freed back to the operating
    31  	// system. We never release spine memory because there could be
    32  	// concurrent lock-free access and we're likely to reuse it
    33  	// anyway. (In principle, we could do this during STW.)
    34  
    35  	spineLock mutex
    36  	spine     atomicSpanSetSpinePointer // *[N]atomic.Pointer[spanSetBlock]
    37  	spineLen  atomic.Uintptr            // Spine array length
    38  	spineCap  uintptr                   // Spine array cap, accessed under spineLock
    39  
    40  	// index is the head and tail of the spanSet in a single field.
    41  	// The head and the tail both represent an index into the logical
    42  	// concatenation of all blocks, with the head always behind or
    43  	// equal to the tail (indicating an empty set). This field is
    44  	// always accessed atomically.
    45  	//
    46  	// The head and the tail are only 32 bits wide, which means we
    47  	// can only support up to 2^32 pushes before a reset. If every
    48  	// span in the heap were stored in this set, and each span were
    49  	// the minimum size (1 runtime page, 8 KiB), then roughly the
    50  	// smallest heap which would be unrepresentable is 32 TiB in size.
    51  	index atomicHeadTailIndex
    52  }
    53  
    54  const (
    55  	spanSetBlockEntries = 512 // 4KB on 64-bit
    56  	spanSetInitSpineCap = 256 // Enough for 1GB heap on 64-bit
    57  )
    58  
    59  type spanSetBlock struct {
    60  	// Free spanSetBlocks are managed via a lock-free stack.
    61  	lfnode
    62  
    63  	// popped is the number of pop operations that have occurred on
    64  	// this block. This number is used to help determine when a block
    65  	// may be safely recycled.
    66  	popped atomic.Uint32
    67  
    68  	// spans is the set of spans in this block.
    69  	spans [spanSetBlockEntries]atomicMSpanPointer
    70  }
    71  
    72  // push adds span s to buffer b. push is safe to call concurrently
    73  // with other push and pop operations.
    74  func (b *spanSet) push(s *mspan) {
    75  	// Obtain our slot.
    76  	cursor := uintptr(b.index.incTail().tail() - 1)
    77  	top, bottom := cursor/spanSetBlockEntries, cursor%spanSetBlockEntries
    78  
    79  	// Do we need to add a block?
    80  	spineLen := b.spineLen.Load()
    81  	var block *spanSetBlock
    82  retry:
    83  	if top < spineLen {
    84  		block = b.spine.Load().lookup(top).Load()
    85  	} else {
    86  		// Add a new block to the spine, potentially growing
    87  		// the spine.
    88  		lock(&b.spineLock)
    89  		// spineLen cannot change until we release the lock,
    90  		// but may have changed while we were waiting.
    91  		spineLen = b.spineLen.Load()
    92  		if top < spineLen {
    93  			unlock(&b.spineLock)
    94  			goto retry
    95  		}
    96  
    97  		spine := b.spine.Load()
    98  		if spineLen == b.spineCap {
    99  			// Grow the spine.
   100  			newCap := b.spineCap * 2
   101  			if newCap == 0 {
   102  				newCap = spanSetInitSpineCap
   103  			}
   104  			newSpine := persistentalloc(newCap*goarch.PtrSize, cpu.CacheLineSize, &memstats.gcMiscSys)
   105  			if b.spineCap != 0 {
   106  				// Blocks are allocated off-heap, so
   107  				// no write barriers.
   108  				memmove(newSpine, spine.p, b.spineCap*goarch.PtrSize)
   109  			}
   110  			spine = spanSetSpinePointer{newSpine}
   111  
   112  			// Spine is allocated off-heap, so no write barrier.
   113  			b.spine.StoreNoWB(spine)
   114  			b.spineCap = newCap
   115  			// We can't immediately free the old spine
   116  			// since a concurrent push with a lower index
   117  			// could still be reading from it. We let it
   118  			// leak because even a 1TB heap would waste
   119  			// less than 2MB of memory on old spines. If
   120  			// this is a problem, we could free old spines
   121  			// during STW.
   122  		}
   123  
   124  		// Allocate a new block from the pool.
   125  		block = spanSetBlockPool.alloc()
   126  
   127  		// Add it to the spine.
   128  		// Blocks are allocated off-heap, so no write barrier.
   129  		spine.lookup(top).StoreNoWB(block)
   130  		b.spineLen.Store(spineLen + 1)
   131  		unlock(&b.spineLock)
   132  	}
   133  
   134  	// We have a block. Insert the span atomically, since there may be
   135  	// concurrent readers via the block API.
   136  	block.spans[bottom].StoreNoWB(s)
   137  }
   138  
   139  // pop removes and returns a span from buffer b, or nil if b is empty.
   140  // pop is safe to call concurrently with other pop and push operations.
   141  func (b *spanSet) pop() *mspan {
   142  	var head, tail uint32
   143  claimLoop:
   144  	for {
   145  		headtail := b.index.load()
   146  		head, tail = headtail.split()
   147  		if head >= tail {
   148  			// The buf is empty, as far as we can tell.
   149  			return nil
   150  		}
   151  		// Check if the head position we want to claim is actually
   152  		// backed by a block.
   153  		spineLen := b.spineLen.Load()
   154  		if spineLen <= uintptr(head)/spanSetBlockEntries {
   155  			// We're racing with a spine growth and the allocation of
   156  			// a new block (and maybe a new spine!), and trying to grab
   157  			// the span at the index which is currently being pushed.
   158  			// Instead of spinning, let's just notify the caller that
   159  			// there's nothing currently here. Spinning on this is
   160  			// almost definitely not worth it.
   161  			return nil
   162  		}
   163  		// Try to claim the current head by CASing in an updated head.
   164  		// This may fail transiently due to a push which modifies the
   165  		// tail, so keep trying while the head isn't changing.
   166  		want := head
   167  		for want == head {
   168  			if b.index.cas(headtail, makeHeadTailIndex(want+1, tail)) {
   169  				break claimLoop
   170  			}
   171  			headtail = b.index.load()
   172  			head, tail = headtail.split()
   173  		}
   174  		// We failed to claim the spot we were after and the head changed,
   175  		// meaning a popper got ahead of us. Try again from the top because
   176  		// the buf may not be empty.
   177  	}
   178  	top, bottom := head/spanSetBlockEntries, head%spanSetBlockEntries
   179  
   180  	// We may be reading a stale spine pointer, but because the length
   181  	// grows monotonically and we've already verified it, we'll definitely
   182  	// be reading from a valid block.
   183  	blockp := b.spine.Load().lookup(uintptr(top))
   184  
   185  	// Given that the spine length is correct, we know we will never
   186  	// see a nil block here, since the length is always updated after
   187  	// the block is set.
   188  	block := blockp.Load()
   189  	s := block.spans[bottom].Load()
   190  	for s == nil {
   191  		// We raced with the span actually being set, but given that we
   192  		// know a block for this span exists, the race window here is
   193  		// extremely small. Try again.
   194  		s = block.spans[bottom].Load()
   195  	}
   196  	// Clear the pointer. This isn't strictly necessary, but defensively
   197  	// avoids accidentally re-using blocks which could lead to memory
   198  	// corruption. This way, we'll get a nil pointer access instead.
   199  	block.spans[bottom].StoreNoWB(nil)
   200  
   201  	// Increase the popped count. If we are the last possible popper
   202  	// in the block (note that bottom need not equal spanSetBlockEntries-1
   203  	// due to races) then it's our responsibility to free the block.
   204  	//
   205  	// If we increment popped to spanSetBlockEntries, we can be sure that
   206  	// we're the last popper for this block, and it's thus safe to free it.
   207  	// Every other popper must have crossed this barrier (and thus finished
   208  	// popping its corresponding mspan) by the time we get here. Because
   209  	// we're the last popper, we also don't have to worry about concurrent
   210  	// pushers (there can't be any). Note that we may not be the popper
   211  	// which claimed the last slot in the block, we're just the last one
   212  	// to finish popping.
   213  	if block.popped.Add(1) == spanSetBlockEntries {
   214  		// Clear the block's pointer.
   215  		blockp.StoreNoWB(nil)
   216  
   217  		// Return the block to the block pool.
   218  		spanSetBlockPool.free(block)
   219  	}
   220  	return s
   221  }
   222  
   223  // reset resets a spanSet which is empty. It will also clean up
   224  // any left over blocks.
   225  //
   226  // Throws if the buf is not empty.
   227  //
   228  // reset may not be called concurrently with any other operations
   229  // on the span set.
   230  func (b *spanSet) reset() {
   231  	head, tail := b.index.load().split()
   232  	if head < tail {
   233  		print("head = ", head, ", tail = ", tail, "\n")
   234  		throw("attempt to clear non-empty span set")
   235  	}
   236  	top := head / spanSetBlockEntries
   237  	if uintptr(top) < b.spineLen.Load() {
   238  		// If the head catches up to the tail and the set is empty,
   239  		// we may not clean up the block containing the head and tail
   240  		// since it may be pushed into again. In order to avoid leaking
   241  		// memory since we're going to reset the head and tail, clean
   242  		// up such a block now, if it exists.
   243  		blockp := b.spine.Load().lookup(uintptr(top))
   244  		block := blockp.Load()
   245  		if block != nil {
   246  			// Check the popped value.
   247  			if block.popped.Load() == 0 {
   248  				// popped should never be zero because that means we have
   249  				// pushed at least one value but not yet popped if this
   250  				// block pointer is not nil.
   251  				throw("span set block with unpopped elements found in reset")
   252  			}
   253  			if block.popped.Load() == spanSetBlockEntries {
   254  				// popped should also never be equal to spanSetBlockEntries
   255  				// because the last popper should have made the block pointer
   256  				// in this slot nil.
   257  				throw("fully empty unfreed span set block found in reset")
   258  			}
   259  
   260  			// Clear the pointer to the block.
   261  			blockp.StoreNoWB(nil)
   262  
   263  			// Return the block to the block pool.
   264  			spanSetBlockPool.free(block)
   265  		}
   266  	}
   267  	b.index.reset()
   268  	b.spineLen.Store(0)
   269  }
   270  
   271  // atomicSpanSetSpinePointer is an atomically-accessed spanSetSpinePointer.
   272  //
   273  // It has the same semantics as atomic.UnsafePointer.
   274  type atomicSpanSetSpinePointer struct {
   275  	a atomic.UnsafePointer
   276  }
   277  
   278  // Loads the spanSetSpinePointer and returns it.
   279  //
   280  // It has the same semantics as atomic.UnsafePointer.
   281  func (s *atomicSpanSetSpinePointer) Load() spanSetSpinePointer {
   282  	return spanSetSpinePointer{s.a.Load()}
   283  }
   284  
   285  // Stores the spanSetSpinePointer.
   286  //
   287  // It has the same semantics as [atomic.UnsafePointer].
   288  func (s *atomicSpanSetSpinePointer) StoreNoWB(p spanSetSpinePointer) {
   289  	s.a.StoreNoWB(p.p)
   290  }
   291  
   292  // spanSetSpinePointer represents a pointer to a contiguous block of atomic.Pointer[spanSetBlock].
   293  type spanSetSpinePointer struct {
   294  	p unsafe.Pointer
   295  }
   296  
   297  // lookup returns &s[idx].
   298  func (s spanSetSpinePointer) lookup(idx uintptr) *atomic.Pointer[spanSetBlock] {
   299  	return (*atomic.Pointer[spanSetBlock])(add(s.p, goarch.PtrSize*idx))
   300  }
   301  
   302  // spanSetBlockPool is a global pool of spanSetBlocks.
   303  var spanSetBlockPool spanSetBlockAlloc
   304  
   305  // spanSetBlockAlloc represents a concurrent pool of spanSetBlocks.
   306  type spanSetBlockAlloc struct {
   307  	stack lfstack
   308  }
   309  
   310  // alloc tries to grab a spanSetBlock out of the pool, and if it fails
   311  // persistentallocs a new one and returns it.
   312  func (p *spanSetBlockAlloc) alloc() *spanSetBlock {
   313  	if s := (*spanSetBlock)(p.stack.pop()); s != nil {
   314  		return s
   315  	}
   316  	return (*spanSetBlock)(persistentalloc(unsafe.Sizeof(spanSetBlock{}), cpu.CacheLineSize, &memstats.gcMiscSys))
   317  }
   318  
   319  // free returns a spanSetBlock back to the pool.
   320  func (p *spanSetBlockAlloc) free(block *spanSetBlock) {
   321  	block.popped.Store(0)
   322  	p.stack.push(&block.lfnode)
   323  }
   324  
   325  // headTailIndex represents a combined 32-bit head and 32-bit tail
   326  // of a queue into a single 64-bit value.
   327  type headTailIndex uint64
   328  
   329  // makeHeadTailIndex creates a headTailIndex value from a separate
   330  // head and tail.
   331  func makeHeadTailIndex(head, tail uint32) headTailIndex {
   332  	return headTailIndex(uint64(head)<<32 | uint64(tail))
   333  }
   334  
   335  // head returns the head of a headTailIndex value.
   336  func (h headTailIndex) head() uint32 {
   337  	return uint32(h >> 32)
   338  }
   339  
   340  // tail returns the tail of a headTailIndex value.
   341  func (h headTailIndex) tail() uint32 {
   342  	return uint32(h)
   343  }
   344  
   345  // split splits the headTailIndex value into its parts.
   346  func (h headTailIndex) split() (head uint32, tail uint32) {
   347  	return h.head(), h.tail()
   348  }
   349  
   350  // atomicHeadTailIndex is an atomically-accessed headTailIndex.
   351  type atomicHeadTailIndex struct {
   352  	u atomic.Uint64
   353  }
   354  
   355  // load atomically reads a headTailIndex value.
   356  func (h *atomicHeadTailIndex) load() headTailIndex {
   357  	return headTailIndex(h.u.Load())
   358  }
   359  
   360  // cas atomically compares-and-swaps a headTailIndex value.
   361  func (h *atomicHeadTailIndex) cas(old, new headTailIndex) bool {
   362  	return h.u.CompareAndSwap(uint64(old), uint64(new))
   363  }
   364  
   365  // incHead atomically increments the head of a headTailIndex.
   366  func (h *atomicHeadTailIndex) incHead() headTailIndex {
   367  	return headTailIndex(h.u.Add(1 << 32))
   368  }
   369  
   370  // decHead atomically decrements the head of a headTailIndex.
   371  func (h *atomicHeadTailIndex) decHead() headTailIndex {
   372  	return headTailIndex(h.u.Add(-(1 << 32)))
   373  }
   374  
   375  // incTail atomically increments the tail of a headTailIndex.
   376  func (h *atomicHeadTailIndex) incTail() headTailIndex {
   377  	ht := headTailIndex(h.u.Add(1))
   378  	// Check for overflow.
   379  	if ht.tail() == 0 {
   380  		print("runtime: head = ", ht.head(), ", tail = ", ht.tail(), "\n")
   381  		throw("headTailIndex overflow")
   382  	}
   383  	return ht
   384  }
   385  
   386  // reset clears the headTailIndex to (0, 0).
   387  func (h *atomicHeadTailIndex) reset() {
   388  	h.u.Store(0)
   389  }
   390  
   391  // atomicMSpanPointer is an atomic.Pointer[mspan]. Can't use generics because it's NotInHeap.
   392  type atomicMSpanPointer struct {
   393  	p atomic.UnsafePointer
   394  }
   395  
   396  // Load returns the *mspan.
   397  func (p *atomicMSpanPointer) Load() *mspan {
   398  	return (*mspan)(p.p.Load())
   399  }
   400  
   401  // Store stores an *mspan.
   402  func (p *atomicMSpanPointer) StoreNoWB(s *mspan) {
   403  	p.p.StoreNoWB(unsafe.Pointer(s))
   404  }
   405  

View as plain text