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