mgcsweepbuf.go

Documentation: runtime

     1  // Copyright 2016 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  	"runtime/internal/atomic"
     9  	"runtime/internal/sys"
    10  	"unsafe"
    11  )
    12  
    13  // A gcSweepBuf is a set of *mspans.
    14  //
    15  // gcSweepBuf is safe for concurrent push operations *or* concurrent
    16  // pop operations, but not both simultaneously.
    17  type gcSweepBuf struct {
    18  	// A gcSweepBuf 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 gcSweepBuf, 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. We never release
    30  	// this memory because there could be concurrent lock-free
    31  	// access and we're likely to reuse it anyway. (In principle,
    32  	// we could do this during STW.)
    33  
    34  	spineLock mutex
    35  	spine     unsafe.Pointer // *[N]*gcSweepBlock, accessed atomically
    36  	spineLen  uintptr        // Spine array length, accessed atomically
    37  	spineCap  uintptr        // Spine array cap, accessed under lock
    38  
    39  	// index is the first unused slot in the logical concatenation
    40  	// of all blocks. It is accessed atomically.
    41  	index uint32
    42  }
    43  
    44  const (
    45  	gcSweepBlockEntries    = 512 // 4KB on 64-bit
    46  	gcSweepBufInitSpineCap = 256 // Enough for 1GB heap on 64-bit
    47  )
    48  
    49  type gcSweepBlock struct {
    50  	spans [gcSweepBlockEntries]*mspan
    51  }
    52  
    53  // push adds span s to buffer b. push is safe to call concurrently
    54  // with other push operations, but NOT to call concurrently with pop.
    55  func (b *gcSweepBuf) push(s *mspan) {
    56  	// Obtain our slot.
    57  	cursor := uintptr(atomic.Xadd(&b.index, +1) - 1)
    58  	top, bottom := cursor/gcSweepBlockEntries, cursor%gcSweepBlockEntries
    59  
    60  	// Do we need to add a block?
    61  	spineLen := atomic.Loaduintptr(&b.spineLen)
    62  	var block *gcSweepBlock
    63  retry:
    64  	if top < spineLen {
    65  		spine := atomic.Loadp(unsafe.Pointer(&b.spine))
    66  		blockp := add(spine, sys.PtrSize*top)
    67  		block = (*gcSweepBlock)(atomic.Loadp(blockp))
    68  	} else {
    69  		// Add a new block to the spine, potentially growing
    70  		// the spine.
    71  		lock(&b.spineLock)
    72  		// spineLen cannot change until we release the lock,
    73  		// but may have changed while we were waiting.
    74  		spineLen = atomic.Loaduintptr(&b.spineLen)
    75  		if top < spineLen {
    76  			unlock(&b.spineLock)
    77  			goto retry
    78  		}
    79  
    80  		if spineLen == b.spineCap {
    81  			// Grow the spine.
    82  			newCap := b.spineCap * 2
    83  			if newCap == 0 {
    84  				newCap = gcSweepBufInitSpineCap
    85  			}
    86  			newSpine := persistentalloc(newCap*sys.PtrSize, sys.CacheLineSize, &memstats.gc_sys)
    87  			if b.spineCap != 0 {
    88  				// Blocks are allocated off-heap, so
    89  				// no write barriers.
    90  				memmove(newSpine, b.spine, b.spineCap*sys.PtrSize)
    91  			}
    92  			// Spine is allocated off-heap, so no write barrier.
    93  			atomic.StorepNoWB(unsafe.Pointer(&b.spine), newSpine)
    94  			b.spineCap = newCap
    95  			// We can't immediately free the old spine
    96  			// since a concurrent push with a lower index
    97  			// could still be reading from it. We let it
    98  			// leak because even a 1TB heap would waste
    99  			// less than 2MB of memory on old spines. If
   100  			// this is a problem, we could free old spines
   101  			// during STW.
   102  		}
   103  
   104  		// Allocate a new block and add it to the spine.
   105  		block = (*gcSweepBlock)(persistentalloc(unsafe.Sizeof(gcSweepBlock{}), sys.CacheLineSize, &memstats.gc_sys))
   106  		blockp := add(b.spine, sys.PtrSize*top)
   107  		// Blocks are allocated off-heap, so no write barrier.
   108  		atomic.StorepNoWB(blockp, unsafe.Pointer(block))
   109  		atomic.Storeuintptr(&b.spineLen, spineLen+1)
   110  		unlock(&b.spineLock)
   111  	}
   112  
   113  	// We have a block. Insert the span.
   114  	block.spans[bottom] = s
   115  }
   116  
   117  // pop removes and returns a span from buffer b, or nil if b is empty.
   118  // pop is safe to call concurrently with other pop operations, but NOT
   119  // to call concurrently with push.
   120  func (b *gcSweepBuf) pop() *mspan {
   121  	cursor := atomic.Xadd(&b.index, -1)
   122  	if int32(cursor) < 0 {
   123  		atomic.Xadd(&b.index, +1)
   124  		return nil
   125  	}
   126  
   127  	// There are no concurrent spine or block modifications during
   128  	// pop, so we can omit the atomics.
   129  	top, bottom := cursor/gcSweepBlockEntries, cursor%gcSweepBlockEntries
   130  	blockp := (**gcSweepBlock)(add(b.spine, sys.PtrSize*uintptr(top)))
   131  	block := *blockp
   132  	s := block.spans[bottom]
   133  	// Clear the pointer for block(i).
   134  	block.spans[bottom] = nil
   135  	return s
   136  }
   137  
   138  // numBlocks returns the number of blocks in buffer b. numBlocks is
   139  // safe to call concurrently with any other operation. Spans that have
   140  // been pushed prior to the call to numBlocks are guaranteed to appear
   141  // in some block in the range [0, numBlocks()), assuming there are no
   142  // intervening pops. Spans that are pushed after the call may also
   143  // appear in these blocks.
   144  func (b *gcSweepBuf) numBlocks() int {
   145  	return int((atomic.Load(&b.index) + gcSweepBlockEntries - 1) / gcSweepBlockEntries)
   146  }
   147  
   148  // block returns the spans in the i'th block of buffer b. block is
   149  // safe to call concurrently with push.
   150  func (b *gcSweepBuf) block(i int) []*mspan {
   151  	// Perform bounds check before loading spine address since
   152  	// push ensures the allocated length is at least spineLen.
   153  	if i < 0 || uintptr(i) >= atomic.Loaduintptr(&b.spineLen) {
   154  		throw("block index out of range")
   155  	}
   156  
   157  	// Get block i.
   158  	spine := atomic.Loadp(unsafe.Pointer(&b.spine))
   159  	blockp := add(spine, sys.PtrSize*uintptr(i))
   160  	block := (*gcSweepBlock)(atomic.Loadp(blockp))
   161  
   162  	// Slice the block if necessary.
   163  	cursor := uintptr(atomic.Load(&b.index))
   164  	top, bottom := cursor/gcSweepBlockEntries, cursor%gcSweepBlockEntries
   165  	var spans []*mspan
   166  	if uintptr(i) < top {
   167  		spans = block.spans[:]
   168  	} else {
   169  		spans = block.spans[:bottom]
   170  	}
   171  
   172  	// push may have reserved a slot but not filled it yet, so
   173  	// trim away unused entries.
   174  	for len(spans) > 0 && spans[len(spans)-1] == nil {
   175  		spans = spans[:len(spans)-1]
   176  	}
   177  	return spans
   178  }
   179
View as plain text