libgo/go/runtime/mgcsweepbuf.go

   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 }