blob: cf01e2e1891a10d3feabf547c8721fb3d6ab3bec [file] [log] [blame]
Brad Fitzpatrick8c6ef062013-12-18 11:08:34 -08001// 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
5package sync
6
Dmitriy Vyukovf8e00572014-01-24 22:29:53 +04007import (
Dmitry Vyukov7b767f42015-09-23 10:03:54 +02008 "internal/race"
Dmitriy Vyukovf8e00572014-01-24 22:29:53 +04009 "runtime"
10 "sync/atomic"
11 "unsafe"
12)
13
Rob Pikea8787cd2014-04-10 05:45:18 +100014// A Pool is a set of temporary objects that may be individually saved and
15// retrieved.
Brad Fitzpatrick8c6ef062013-12-18 11:08:34 -080016//
Rob Pikea8787cd2014-04-10 05:45:18 +100017// 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.
Brad Fitzpatrick8c6ef062013-12-18 11:08:34 -080020//
21// A Pool is safe for use by multiple goroutines simultaneously.
22//
Rob Pikea8787cd2014-04-10 05:45:18 +100023// 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.
Rob Pikedc8572c2013-12-20 11:15:50 -080027//
Rob Pikea8787cd2014-04-10 05:45:18 +100028// 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//
Aliaksandr Valialkinc81a3532016-04-15 00:33:28 +030043// A Pool must not be copied after first use.
Russ Coxa71ca3d2022-01-26 16:53:50 -050044//
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.
Brad Fitzpatrick8c6ef062013-12-18 11:08:34 -080049type Pool struct {
Aliaksandr Valialkinc81a3532016-04-15 00:33:28 +030050 noCopy noCopy
51
Dmitriy Vyukov8fc6ed42014-04-14 21:13:32 +040052 local unsafe.Pointer // local fixed-size per-P pool, actual type is [P]poolLocal
53 localSize uintptr // size of the local array
Brad Fitzpatrick8c6ef062013-12-18 11:08:34 -080054
Austin Clements2dcbf8b2019-03-02 15:16:29 -050055 victim unsafe.Pointer // local from previous cycle
56 victimSize uintptr // size of victims array
57
Brad Fitzpatrick8c6ef062013-12-18 11:08:34 -080058 // 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.
Russ Cox2580d0e2021-12-01 12:15:45 -050061 New func() any
Brad Fitzpatrick8c6ef062013-12-18 11:08:34 -080062}
63
Dmitriy Vyukovf8e00572014-01-24 22:29:53 +040064// Local per-P Pool appendix.
Aliaksandr Valialkin8aa31d52017-04-18 13:12:58 +030065type poolLocalInternal struct {
Russ Cox2580d0e2021-12-01 12:15:45 -050066 private any // Can be used only by the respective P.
67 shared poolChain // Local P can pushHead/popHead; any P can popTail.
Aliaksandr Valialkin8aa31d52017-04-18 13:12:58 +030068}
69
70type 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
Dmitriy Vyukovf8e00572014-01-24 22:29:53 +040076}
Brad Fitzpatrick8c6ef062013-12-18 11:08:34 -080077
Russ Coxba048f72016-10-20 20:26:31 -040078// from runtime
Meng Zhuoecb2f232021-09-30 22:46:09 +080079func fastrandn(n uint32) uint32
Russ Coxba048f72016-10-20 20:26:31 -040080
81var 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.
Russ Cox2580d0e2021-12-01 12:15:45 -050088func poolRaceAddr(x any) unsafe.Pointer {
Russ Coxba048f72016-10-20 20:26:31 -040089 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
Brad Fitzpatrick8c6ef062013-12-18 11:08:34 -080094// Put adds x to the pool.
Russ Cox2580d0e2021-12-01 12:15:45 -050095func (p *Pool) Put(x any) {
Brad Fitzpatrick8c6ef062013-12-18 11:08:34 -080096 if x == nil {
97 return
98 }
Russ Coxba048f72016-10-20 20:26:31 -040099 if race.Enabled {
Meng Zhuoecb2f232021-09-30 22:46:09 +0800100 if fastrandn(4) == 0 {
Russ Coxba048f72016-10-20 20:26:31 -0400101 // Randomly drop x on floor.
102 return
103 }
104 race.ReleaseMerge(poolRaceAddr(x))
105 race.Disable()
106 }
Austin Clementsd5fd2dd2019-03-01 15:33:33 -0500107 l, _ := p.pin()
Dmitriy Vyukov8fc6ed42014-04-14 21:13:32 +0400108 if l.private == nil {
109 l.private = x
Jason7602507a44d2021-11-01 23:27:45 +0800110 } else {
Austin Clementsd5fd2dd2019-03-01 15:33:33 -0500111 l.shared.pushHead(x)
Brad Fitzpatrick8c6ef062013-12-18 11:08:34 -0800112 }
Austin Clementsd5fd2dd2019-03-01 15:33:33 -0500113 runtime_procUnpin()
Russ Coxba048f72016-10-20 20:26:31 -0400114 if race.Enabled {
115 race.Enable()
116 }
Brad Fitzpatrick8c6ef062013-12-18 11:08:34 -0800117}
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.
Russ Cox2580d0e2021-12-01 12:15:45 -0500127func (p *Pool) Get() any {
Dmitry Vyukov7b767f42015-09-23 10:03:54 +0200128 if race.Enabled {
Russ Coxba048f72016-10-20 20:26:31 -0400129 race.Disable()
Dmitriy Vyukovce8045f2014-01-25 20:11:16 +0400130 }
Austin Clementsd5fd2dd2019-03-01 15:33:33 -0500131 l, pid := p.pin()
Dmitriy Vyukov8fc6ed42014-04-14 21:13:32 +0400132 x := l.private
133 l.private = nil
Russ Coxba048f72016-10-20 20:26:31 -0400134 if x == nil {
Austin Clementsd5fd2dd2019-03-01 15:33:33 -0500135 // 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()
Russ Coxba048f72016-10-20 20:26:31 -0400139 if x == nil {
Austin Clementsd5fd2dd2019-03-01 15:33:33 -0500140 x = p.getSlow(pid)
Russ Coxba048f72016-10-20 20:26:31 -0400141 }
Dmitriy Vyukov8fc6ed42014-04-14 21:13:32 +0400142 }
Austin Clementsd5fd2dd2019-03-01 15:33:33 -0500143 runtime_procUnpin()
Russ Coxba048f72016-10-20 20:26:31 -0400144 if race.Enabled {
145 race.Enable()
146 if x != nil {
147 race.Acquire(poolRaceAddr(x))
148 }
Dmitriy Vyukov8fc6ed42014-04-14 21:13:32 +0400149 }
Russ Coxba048f72016-10-20 20:26:31 -0400150 if x == nil && p.New != nil {
151 x = p.New()
Brad Fitzpatrick8c6ef062013-12-18 11:08:34 -0800152 }
Russ Coxba048f72016-10-20 20:26:31 -0400153 return x
Dmitriy Vyukovf8e00572014-01-24 22:29:53 +0400154}
155
Russ Cox2580d0e2021-12-01 12:15:45 -0500156func (p *Pool) getSlow(pid int) any {
Dmitriy Vyukov8fc6ed42014-04-14 21:13:32 +0400157 // See the comment in pin regarding ordering of the loads.
Austin Clementsc305e492020-10-26 14:32:13 -0400158 size := runtime_LoadAcquintptr(&p.localSize) // load-acquire
Bryan C. Mills0d1280c2021-04-26 18:32:28 +0000159 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
Dmitriy Vyukov8fc6ed42014-04-14 21:13:32 +0400165 }
Dmitriy Vyukov8fc6ed42014-04-14 21:13:32 +0400166 }
Austin Clements2dcbf8b2019-03-02 15:16:29 -0500167
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.
Austin Clementsc305e492020-10-26 14:32:13 -0400171 size = atomic.LoadUintptr(&p.victimSize)
Austin Clements2dcbf8b2019-03-02 15:16:29 -0500172 if uintptr(pid) >= size {
173 return nil
174 }
Bryan C. Mills0d1280c2021-04-26 18:32:28 +0000175 locals = p.victim
Austin Clements2dcbf8b2019-03-02 15:16:29 -0500176 l := indexLocal(locals, pid)
177 if x := l.private; x != nil {
178 l.private = nil
179 return x
180 }
Bryan C. Mills0d1280c2021-04-26 18:32:28 +0000181 for i := 0; i < int(size); i++ {
Austin Clements2dcbf8b2019-03-02 15:16:29 -0500182 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
Austin Clementsd5fd2dd2019-03-01 15:33:33 -0500192 return nil
Brad Fitzpatrick8c6ef062013-12-18 11:08:34 -0800193}
Dmitriy Vyukovf8e00572014-01-24 22:29:53 +0400194
Austin Clementsd5fd2dd2019-03-01 15:33:33 -0500195// pin pins the current goroutine to P, disables preemption and
196// returns poolLocal pool for the P and the P's id.
Dmitriy Vyukovf8e00572014-01-24 22:29:53 +0400197// Caller must call runtime_procUnpin() when done with the pool.
Austin Clementsd5fd2dd2019-03-01 15:33:33 -0500198func (p *Pool) pin() (*poolLocal, int) {
Dmitriy Vyukovf8e00572014-01-24 22:29:53 +0400199 pid := runtime_procPin()
Kai Dong5ccaf2c2019-04-19 03:23:23 +0000200 // In pinSlow we store to local and then to localSize, here we load in opposite order.
Josh Bleecher Snydere43c74a2016-01-27 12:49:13 -0800201 // Since we've disabled preemption, GC cannot happen in between.
Dmitriy Vyukovf8e00572014-01-24 22:29:53 +0400202 // 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).
Austin Clementsc305e492020-10-26 14:32:13 -0400204 s := runtime_LoadAcquintptr(&p.localSize) // load-acquire
205 l := p.local // load-consume
Dmitriy Vyukovf8e00572014-01-24 22:29:53 +0400206 if uintptr(pid) < s {
Austin Clementsd5fd2dd2019-03-01 15:33:33 -0500207 return indexLocal(l, pid), pid
Dmitriy Vyukovf8e00572014-01-24 22:29:53 +0400208 }
209 return p.pinSlow()
210}
211
Austin Clementsd5fd2dd2019-03-01 15:33:33 -0500212func (p *Pool) pinSlow() (*poolLocal, int) {
Dmitriy Vyukovf8e00572014-01-24 22:29:53 +0400213 // Retry under the mutex.
Dmitriy Vyukov8fc6ed42014-04-14 21:13:32 +0400214 // Can not lock the mutex while pinned.
Dmitriy Vyukovf8e00572014-01-24 22:29:53 +0400215 runtime_procUnpin()
Dmitriy Vyukov8fc6ed42014-04-14 21:13:32 +0400216 allPoolsMu.Lock()
217 defer allPoolsMu.Unlock()
Dmitriy Vyukovf8e00572014-01-24 22:29:53 +0400218 pid := runtime_procPin()
Dmitriy Vyukov8fc6ed42014-04-14 21:13:32 +0400219 // poolCleanup won't be called while we are pinned.
Dmitriy Vyukovf8e00572014-01-24 22:29:53 +0400220 s := p.localSize
221 l := p.local
222 if uintptr(pid) < s {
Austin Clementsd5fd2dd2019-03-01 15:33:33 -0500223 return indexLocal(l, pid), pid
Dmitriy Vyukovf8e00572014-01-24 22:29:53 +0400224 }
225 if p.local == nil {
Dmitriy Vyukov8fc6ed42014-04-14 21:13:32 +0400226 allPools = append(allPools, p)
Dmitriy Vyukovf8e00572014-01-24 22:29:53 +0400227 }
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)
Bryan C. Mills0d1280c2021-04-26 18:32:28 +0000231 atomic.StorePointer(&p.local, unsafe.Pointer(&local[0])) // store-release
232 runtime_StoreReluintptr(&p.localSize, uintptr(size)) // store-release
Austin Clementsd5fd2dd2019-03-01 15:33:33 -0500233 return &local[pid], pid
Dmitriy Vyukovf8e00572014-01-24 22:29:53 +0400234}
235
Dmitriy Vyukov8fc6ed42014-04-14 21:13:32 +0400236func 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.
Austin Clementsd5fd2dd2019-03-01 15:33:33 -0500239
240 // Because the world is stopped, no pool user can be in a
241 // pinned section (in effect, this has all Ps pinned).
Austin Clements2dcbf8b2019-03-02 15:16:29 -0500242
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
Dmitriy Vyukovaf3868f2014-10-22 20:23:49 +0400253 p.local = nil
254 p.localSize = 0
Dmitriy Vyukov8fc6ed42014-04-14 21:13:32 +0400255 }
Austin Clements2dcbf8b2019-03-02 15:16:29 -0500256
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
Dmitriy Vyukov8fc6ed42014-04-14 21:13:32 +0400260}
261
262var (
263 allPoolsMu Mutex
Austin Clements2dcbf8b2019-03-02 15:16:29 -0500264
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
Dmitriy Vyukov8fc6ed42014-04-14 21:13:32 +0400273)
274
275func init() {
276 runtime_registerPoolCleanup(poolCleanup)
277}
278
279func indexLocal(l unsafe.Pointer, i int) *poolLocal {
Aliaksandr Valialkinaf5c9512017-04-17 15:09:10 +0300280 lp := unsafe.Pointer(uintptr(l) + uintptr(i)*unsafe.Sizeof(poolLocal{}))
281 return (*poolLocal)(lp)
Dmitriy Vyukovf8e00572014-01-24 22:29:53 +0400282}
283
284// Implemented in runtime.
Dmitriy Vyukov8fc6ed42014-04-14 21:13:32 +0400285func runtime_registerPoolCleanup(cleanup func())
Dmitriy Vyukovf8e00572014-01-24 22:29:53 +0400286func runtime_procPin() int
287func runtime_procUnpin()
Austin Clementsc305e492020-10-26 14:32:13 -0400288
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
294func runtime_LoadAcquintptr(ptr *uintptr) uintptr
295
296//go:linkname runtime_StoreReluintptr runtime/internal/atomic.StoreReluintptr
297func runtime_StoreReluintptr(ptr *uintptr, val uintptr) uintptr