summaryrefslogtreecommitdiffstats
path: root/src/sync/pool.go
diff options
context:
space:
mode:
Diffstat (limited to 'src/sync/pool.go')
-rw-r--r--src/sync/pool.go297
1 files changed, 297 insertions, 0 deletions
diff --git a/src/sync/pool.go b/src/sync/pool.go
new file mode 100644
index 0000000..cf01e2e
--- /dev/null
+++ b/src/sync/pool.go
@@ -0,0 +1,297 @@
+// Copyright 2013 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 sync
+
+import (
+ "internal/race"
+ "runtime"
+ "sync/atomic"
+ "unsafe"
+)
+
+// A Pool is a set of temporary objects that may be individually saved and
+// retrieved.
+//
+// Any item stored in the Pool may be removed automatically at any time without
+// notification. If the Pool holds the only reference when this happens, the
+// item might be deallocated.
+//
+// A Pool is safe for use by multiple goroutines simultaneously.
+//
+// Pool's purpose is to cache allocated but unused items for later reuse,
+// relieving pressure on the garbage collector. That is, it makes it easy to
+// build efficient, thread-safe free lists. However, it is not suitable for all
+// free lists.
+//
+// An appropriate use of a Pool is to manage a group of temporary items
+// silently shared among and potentially reused by concurrent independent
+// clients of a package. Pool provides a way to amortize allocation overhead
+// across many clients.
+//
+// An example of good use of a Pool is in the fmt package, which maintains a
+// dynamically-sized store of temporary output buffers. The store scales under
+// load (when many goroutines are actively printing) and shrinks when
+// quiescent.
+//
+// On the other hand, a free list maintained as part of a short-lived object is
+// not a suitable use for a Pool, since the overhead does not amortize well in
+// that scenario. It is more efficient to have such objects implement their own
+// free list.
+//
+// A Pool must not be copied after first use.
+//
+// In the terminology of the Go memory model, a call to Put(x) “synchronizes before”
+// a call to Get returning that same value x.
+// Similarly, a call to New returning x “synchronizes before”
+// a call to Get returning that same value x.
+type Pool struct {
+ noCopy noCopy
+
+ local unsafe.Pointer // local fixed-size per-P pool, actual type is [P]poolLocal
+ localSize uintptr // size of the local array
+
+ victim unsafe.Pointer // local from previous cycle
+ victimSize uintptr // size of victims array
+
+ // New optionally specifies a function to generate
+ // a value when Get would otherwise return nil.
+ // It may not be changed concurrently with calls to Get.
+ New func() any
+}
+
+// Local per-P Pool appendix.
+type poolLocalInternal struct {
+ private any // Can be used only by the respective P.
+ shared poolChain // Local P can pushHead/popHead; any P can popTail.
+}
+
+type poolLocal struct {
+ poolLocalInternal
+
+ // Prevents false sharing on widespread platforms with
+ // 128 mod (cache line size) = 0 .
+ pad [128 - unsafe.Sizeof(poolLocalInternal{})%128]byte
+}
+
+// from runtime
+func fastrandn(n uint32) uint32
+
+var poolRaceHash [128]uint64
+
+// poolRaceAddr returns an address to use as the synchronization point
+// for race detector logic. We don't use the actual pointer stored in x
+// directly, for fear of conflicting with other synchronization on that address.
+// Instead, we hash the pointer to get an index into poolRaceHash.
+// See discussion on golang.org/cl/31589.
+func poolRaceAddr(x any) unsafe.Pointer {
+ ptr := uintptr((*[2]unsafe.Pointer)(unsafe.Pointer(&x))[1])
+ h := uint32((uint64(uint32(ptr)) * 0x85ebca6b) >> 16)
+ return unsafe.Pointer(&poolRaceHash[h%uint32(len(poolRaceHash))])
+}
+
+// Put adds x to the pool.
+func (p *Pool) Put(x any) {
+ if x == nil {
+ return
+ }
+ if race.Enabled {
+ if fastrandn(4) == 0 {
+ // Randomly drop x on floor.
+ return
+ }
+ race.ReleaseMerge(poolRaceAddr(x))
+ race.Disable()
+ }
+ l, _ := p.pin()
+ if l.private == nil {
+ l.private = x
+ } else {
+ l.shared.pushHead(x)
+ }
+ runtime_procUnpin()
+ if race.Enabled {
+ race.Enable()
+ }
+}
+
+// Get selects an arbitrary item from the Pool, removes it from the
+// Pool, and returns it to the caller.
+// Get may choose to ignore the pool and treat it as empty.
+// Callers should not assume any relation between values passed to Put and
+// the values returned by Get.
+//
+// If Get would otherwise return nil and p.New is non-nil, Get returns
+// the result of calling p.New.
+func (p *Pool) Get() any {
+ if race.Enabled {
+ race.Disable()
+ }
+ l, pid := p.pin()
+ x := l.private
+ l.private = nil
+ if x == nil {
+ // Try to pop the head of the local shard. We prefer
+ // the head over the tail for temporal locality of
+ // reuse.
+ x, _ = l.shared.popHead()
+ if x == nil {
+ x = p.getSlow(pid)
+ }
+ }
+ runtime_procUnpin()
+ if race.Enabled {
+ race.Enable()
+ if x != nil {
+ race.Acquire(poolRaceAddr(x))
+ }
+ }
+ if x == nil && p.New != nil {
+ x = p.New()
+ }
+ return x
+}
+
+func (p *Pool) getSlow(pid int) any {
+ // See the comment in pin regarding ordering of the loads.
+ size := runtime_LoadAcquintptr(&p.localSize) // load-acquire
+ locals := p.local // load-consume
+ // Try to steal one element from other procs.
+ for i := 0; i < int(size); i++ {
+ l := indexLocal(locals, (pid+i+1)%int(size))
+ if x, _ := l.shared.popTail(); x != nil {
+ return x
+ }
+ }
+
+ // Try the victim cache. We do this after attempting to steal
+ // from all primary caches because we want objects in the
+ // victim cache to age out if at all possible.
+ size = atomic.LoadUintptr(&p.victimSize)
+ if uintptr(pid) >= size {
+ return nil
+ }
+ locals = p.victim
+ l := indexLocal(locals, pid)
+ if x := l.private; x != nil {
+ l.private = nil
+ return x
+ }
+ for i := 0; i < int(size); i++ {
+ l := indexLocal(locals, (pid+i)%int(size))
+ if x, _ := l.shared.popTail(); x != nil {
+ return x
+ }
+ }
+
+ // Mark the victim cache as empty for future gets don't bother
+ // with it.
+ atomic.StoreUintptr(&p.victimSize, 0)
+
+ return nil
+}
+
+// pin pins the current goroutine to P, disables preemption and
+// returns poolLocal pool for the P and the P's id.
+// Caller must call runtime_procUnpin() when done with the pool.
+func (p *Pool) pin() (*poolLocal, int) {
+ pid := runtime_procPin()
+ // In pinSlow we store to local and then to localSize, here we load in opposite order.
+ // Since we've disabled preemption, GC cannot happen in between.
+ // Thus here we must observe local at least as large localSize.
+ // We can observe a newer/larger local, it is fine (we must observe its zero-initialized-ness).
+ s := runtime_LoadAcquintptr(&p.localSize) // load-acquire
+ l := p.local // load-consume
+ if uintptr(pid) < s {
+ return indexLocal(l, pid), pid
+ }
+ return p.pinSlow()
+}
+
+func (p *Pool) pinSlow() (*poolLocal, int) {
+ // Retry under the mutex.
+ // Can not lock the mutex while pinned.
+ runtime_procUnpin()
+ allPoolsMu.Lock()
+ defer allPoolsMu.Unlock()
+ pid := runtime_procPin()
+ // poolCleanup won't be called while we are pinned.
+ s := p.localSize
+ l := p.local
+ if uintptr(pid) < s {
+ return indexLocal(l, pid), pid
+ }
+ if p.local == nil {
+ allPools = append(allPools, p)
+ }
+ // If GOMAXPROCS changes between GCs, we re-allocate the array and lose the old one.
+ size := runtime.GOMAXPROCS(0)
+ local := make([]poolLocal, size)
+ atomic.StorePointer(&p.local, unsafe.Pointer(&local[0])) // store-release
+ runtime_StoreReluintptr(&p.localSize, uintptr(size)) // store-release
+ return &local[pid], pid
+}
+
+func poolCleanup() {
+ // This function is called with the world stopped, at the beginning of a garbage collection.
+ // It must not allocate and probably should not call any runtime functions.
+
+ // Because the world is stopped, no pool user can be in a
+ // pinned section (in effect, this has all Ps pinned).
+
+ // Drop victim caches from all pools.
+ for _, p := range oldPools {
+ p.victim = nil
+ p.victimSize = 0
+ }
+
+ // Move primary cache to victim cache.
+ for _, p := range allPools {
+ p.victim = p.local
+ p.victimSize = p.localSize
+ p.local = nil
+ p.localSize = 0
+ }
+
+ // The pools with non-empty primary caches now have non-empty
+ // victim caches and no pools have primary caches.
+ oldPools, allPools = allPools, nil
+}
+
+var (
+ allPoolsMu Mutex
+
+ // allPools is the set of pools that have non-empty primary
+ // caches. Protected by either 1) allPoolsMu and pinning or 2)
+ // STW.
+ allPools []*Pool
+
+ // oldPools is the set of pools that may have non-empty victim
+ // caches. Protected by STW.
+ oldPools []*Pool
+)
+
+func init() {
+ runtime_registerPoolCleanup(poolCleanup)
+}
+
+func indexLocal(l unsafe.Pointer, i int) *poolLocal {
+ lp := unsafe.Pointer(uintptr(l) + uintptr(i)*unsafe.Sizeof(poolLocal{}))
+ return (*poolLocal)(lp)
+}
+
+// Implemented in runtime.
+func runtime_registerPoolCleanup(cleanup func())
+func runtime_procPin() int
+func runtime_procUnpin()
+
+// The below are implemented in runtime/internal/atomic and the
+// compiler also knows to intrinsify the symbol we linkname into this
+// package.
+
+//go:linkname runtime_LoadAcquintptr runtime/internal/atomic.LoadAcquintptr
+func runtime_LoadAcquintptr(ptr *uintptr) uintptr
+
+//go:linkname runtime_StoreReluintptr runtime/internal/atomic.StoreReluintptr
+func runtime_StoreReluintptr(ptr *uintptr, val uintptr) uintptr