pool.go

     1  // Copyright 2013 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 sync
     6  
     7  import (
     8  	"internal/race"
     9  	rtatomic "internal/runtime/atomic"
    10  	"runtime"
    11  	"sync/atomic"
    12  	"unsafe"
    13  )
    14  
    15  // A Pool is a set of temporary objects that may be individually saved and
    16  // retrieved.
    17  //
    18  // Any item stored in the Pool may be removed automatically at any time without
    19  // notification. If the Pool holds the only reference when this happens, the
    20  // item might be deallocated.
    21  //
    22  // A Pool is safe for use by multiple goroutines simultaneously.
    23  //
    24  // Pool's purpose is to cache allocated but unused items for later reuse,
    25  // relieving pressure on the garbage collector. That is, it makes it easy to
    26  // build efficient, thread-safe free lists. However, it is not suitable for all
    27  // free lists.
    28  //
    29  // An appropriate use of a Pool is to manage a group of temporary items
    30  // silently shared among and potentially reused by concurrent independent
    31  // clients of a package. Pool provides a way to amortize allocation overhead
    32  // across many clients.
    33  //
    34  // An example of good use of a Pool is in the fmt package, which maintains a
    35  // dynamically-sized store of temporary output buffers. The store scales under
    36  // load (when many goroutines are actively printing) and shrinks when
    37  // quiescent.
    38  //
    39  // On the other hand, a free list maintained as part of a short-lived object is
    40  // not a suitable use for a Pool, since the overhead does not amortize well in
    41  // that scenario. It is more efficient to have such objects implement their own
    42  // free list.
    43  //
    44  // A Pool must not be copied after first use.
    45  //
    46  // In the terminology of [the Go memory model], a call to Put(x) “synchronizes before”
    47  // a call to [Pool.Get] returning that same value x.
    48  // Similarly, a call to New returning x “synchronizes before”
    49  // a call to Get returning that same value x.
    50  //
    51  // [the Go memory model]: https://go.dev/ref/mem
    52  type Pool struct {
    53  	noCopy noCopy
    54  
    55  	local     unsafe.Pointer // local fixed-size per-P pool, actual type is [P]poolLocal
    56  	localSize uintptr        // size of the local array
    57  
    58  	victim     unsafe.Pointer // local from previous cycle
    59  	victimSize uintptr        // size of victims array
    60  
    61  	// New optionally specifies a function to generate
    62  	// a value when Get would otherwise return nil.
    63  	// It may not be changed concurrently with calls to Get.
    64  	New func() any
    65  }
    66  
    67  // Local per-P Pool appendix.
    68  type poolLocalInternal struct {
    69  	private any       // Can be used only by the respective P.
    70  	shared  poolChain // Local P can pushHead/popHead; any P can popTail.
    71  }
    72  
    73  type poolLocal struct {
    74  	poolLocalInternal
    75  
    76  	// Prevents false sharing on widespread platforms with
    77  	// 128 mod (cache line size) = 0 .
    78  	pad [128 - unsafe.Sizeof(poolLocalInternal{})%128]byte
    79  }
    80  
    81  // from runtime
    82  //
    83  //go:linkname runtime_randn runtime.randn
    84  func runtime_randn(n uint32) uint32
    85  
    86  var poolRaceHash [128]uint64
    87  
    88  // poolRaceAddr returns an address to use as the synchronization point
    89  // for race detector logic. We don't use the actual pointer stored in x
    90  // directly, for fear of conflicting with other synchronization on that address.
    91  // Instead, we hash the pointer to get an index into poolRaceHash.
    92  // See discussion on golang.org/cl/31589.
    93  func poolRaceAddr(x any) unsafe.Pointer {
    94  	ptr := uintptr((*[2]unsafe.Pointer)(unsafe.Pointer(&x))[1])
    95  	h := uint32((uint64(uint32(ptr)) * 0x85ebca6b) >> 16)
    96  	return unsafe.Pointer(&poolRaceHash[h%uint32(len(poolRaceHash))])
    97  }
    98  
    99  // Put adds x to the pool.
   100  func (p *Pool) Put(x any) {
   101  	if x == nil {
   102  		return
   103  	}
   104  	if race.Enabled {
   105  		if runtime_randn(4) == 0 {
   106  			// Randomly drop x on floor.
   107  			return
   108  		}
   109  		race.ReleaseMerge(poolRaceAddr(x))
   110  		race.Disable()
   111  	}
   112  	l, _ := p.pin()
   113  	if l.private == nil {
   114  		l.private = x
   115  	} else {
   116  		l.shared.pushHead(x)
   117  	}
   118  	runtime_procUnpin()
   119  	if race.Enabled {
   120  		race.Enable()
   121  	}
   122  }
   123  
   124  // Get selects an arbitrary item from the [Pool], removes it from the
   125  // Pool, and returns it to the caller.
   126  // Get may choose to ignore the pool and treat it as empty.
   127  // Callers should not assume any relation between values passed to [Pool.Put] and
   128  // the values returned by Get.
   129  //
   130  // If Get would otherwise return nil and p.New is non-nil, Get returns
   131  // the result of calling p.New.
   132  func (p *Pool) Get() any {
   133  	if race.Enabled {
   134  		race.Disable()
   135  	}
   136  	l, pid := p.pin()
   137  	x := l.private
   138  	l.private = nil
   139  	if x == nil {
   140  		// Try to pop the head of the local shard. We prefer
   141  		// the head over the tail for temporal locality of
   142  		// reuse.
   143  		x, _ = l.shared.popHead()
   144  		if x == nil {
   145  			x = p.getSlow(pid)
   146  		}
   147  	}
   148  	runtime_procUnpin()
   149  	if race.Enabled {
   150  		race.Enable()
   151  		if x != nil {
   152  			race.Acquire(poolRaceAddr(x))
   153  		}
   154  	}
   155  	if x == nil && p.New != nil {
   156  		x = p.New()
   157  	}
   158  	return x
   159  }
   160  
   161  func (p *Pool) getSlow(pid int) any {
   162  	// See the comment in pin regarding ordering of the loads.
   163  	size := rtatomic.LoadAcquintptr(&p.localSize) // load-acquire
   164  	locals := p.local                             // load-consume
   165  	// Try to steal one element from other procs.
   166  	for i := 0; i < int(size); i++ {
   167  		l := indexLocal(locals, (pid+i+1)%int(size))
   168  		if x, _ := l.shared.popTail(); x != nil {
   169  			return x
   170  		}
   171  	}
   172  
   173  	// Try the victim cache. We do this after attempting to steal
   174  	// from all primary caches because we want objects in the
   175  	// victim cache to age out if at all possible.
   176  	size = atomic.LoadUintptr(&p.victimSize)
   177  	if uintptr(pid) >= size {
   178  		return nil
   179  	}
   180  	locals = p.victim
   181  	l := indexLocal(locals, pid)
   182  	if x := l.private; x != nil {
   183  		l.private = nil
   184  		return x
   185  	}
   186  	for i := 0; i < int(size); i++ {
   187  		l := indexLocal(locals, (pid+i)%int(size))
   188  		if x, _ := l.shared.popTail(); x != nil {
   189  			return x
   190  		}
   191  	}
   192  
   193  	// Mark the victim cache as empty for future gets don't bother
   194  	// with it.
   195  	atomic.StoreUintptr(&p.victimSize, 0)
   196  
   197  	return nil
   198  }
   199  
   200  // pin pins the current goroutine to P, disables preemption and
   201  // returns poolLocal pool for the P and the P's id.
   202  // Caller must call runtime_procUnpin() when done with the pool.
   203  func (p *Pool) pin() (*poolLocal, int) {
   204  	// Check whether p is nil to get a panic.
   205  	// Otherwise the nil dereference happens while the m is pinned,
   206  	// causing a fatal error rather than a panic.
   207  	if p == nil {
   208  		panic("nil Pool")
   209  	}
   210  
   211  	pid := runtime_procPin()
   212  	// In pinSlow we store to local and then to localSize, here we load in opposite order.
   213  	// Since we've disabled preemption, GC cannot happen in between.
   214  	// Thus here we must observe local at least as large localSize.
   215  	// We can observe a newer/larger local, it is fine (we must observe its zero-initialized-ness).
   216  	s := rtatomic.LoadAcquintptr(&p.localSize) // load-acquire
   217  	l := p.local                               // load-consume
   218  	if uintptr(pid) < s {
   219  		return indexLocal(l, pid), pid
   220  	}
   221  	return p.pinSlow()
   222  }
   223  
   224  func (p *Pool) pinSlow() (*poolLocal, int) {
   225  	// Retry under the mutex.
   226  	// Can not lock the mutex while pinned.
   227  	runtime_procUnpin()
   228  	allPoolsMu.Lock()
   229  	defer allPoolsMu.Unlock()
   230  	pid := runtime_procPin()
   231  	// poolCleanup won't be called while we are pinned.
   232  	s := p.localSize
   233  	l := p.local
   234  	if uintptr(pid) < s {
   235  		return indexLocal(l, pid), pid
   236  	}
   237  	if p.local == nil {
   238  		allPools = append(allPools, p)
   239  	}
   240  	// If GOMAXPROCS changes between GCs, we re-allocate the array and lose the old one.
   241  	size := runtime.GOMAXPROCS(0)
   242  	local := make([]poolLocal, size)
   243  	atomic.StorePointer(&p.local, unsafe.Pointer(&local[0])) // store-release
   244  	rtatomic.StoreReluintptr(&p.localSize, uintptr(size))    // store-release
   245  	return &local[pid], pid
   246  }
   247  
   248  // poolCleanup should be an internal detail,
   249  // but widely used packages access it using linkname.
   250  // Notable members of the hall of shame include:
   251  //   - github.com/bytedance/gopkg
   252  //   - github.com/songzhibin97/gkit
   253  //
   254  // Do not remove or change the type signature.
   255  // See go.dev/issue/67401.
   256  //
   257  //go:linkname poolCleanup
   258  func poolCleanup() {
   259  	// This function is called with the world stopped, at the beginning of a garbage collection.
   260  	// It must not allocate and probably should not call any runtime functions.
   261  
   262  	// Because the world is stopped, no pool user can be in a
   263  	// pinned section (in effect, this has all Ps pinned).
   264  
   265  	// Drop victim caches from all pools.
   266  	for _, p := range oldPools {
   267  		p.victim = nil
   268  		p.victimSize = 0
   269  	}
   270  
   271  	// Move primary cache to victim cache.
   272  	for _, p := range allPools {
   273  		p.victim = p.local
   274  		p.victimSize = p.localSize
   275  		p.local = nil
   276  		p.localSize = 0
   277  	}
   278  
   279  	// The pools with non-empty primary caches now have non-empty
   280  	// victim caches and no pools have primary caches.
   281  	oldPools, allPools = allPools, nil
   282  }
   283  
   284  var (
   285  	allPoolsMu Mutex
   286  
   287  	// allPools is the set of pools that have non-empty primary
   288  	// caches. Protected by either 1) allPoolsMu and pinning or 2)
   289  	// STW.
   290  	allPools []*Pool
   291  
   292  	// oldPools is the set of pools that may have non-empty victim
   293  	// caches. Protected by STW.
   294  	oldPools []*Pool
   295  )
   296  
   297  func init() {
   298  	runtime_registerPoolCleanup(poolCleanup)
   299  }
   300  
   301  func indexLocal(l unsafe.Pointer, i int) *poolLocal {
   302  	lp := unsafe.Pointer(uintptr(l) + uintptr(i)*unsafe.Sizeof(poolLocal{}))
   303  	return (*poolLocal)(lp)
   304  }
   305  
   306  // Implemented in runtime.
   307  func runtime_registerPoolCleanup(cleanup func())
   308  func runtime_procPin() int
   309  func runtime_procUnpin()
   310
View as plain text