libgo/go/sync/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         "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 type Pool struct {
  45         noCopy noCopy
  46
  47         local     unsafe.Pointer // local fixed-size per-P pool, actual type is [P]poolLocal
  48         localSize uintptr        // size of the local array
  49
  50         // New optionally specifies a function to generate
  51         // a value when Get would otherwise return nil.
  52         // It may not be changed concurrently with calls to Get.
  53         New func() interface{}
  54 }
  55
  56 // Local per-P Pool appendix.
  57 type poolLocalInternal struct {
  58         private interface{}   // Can be used only by the respective P.
  59         shared  []interface{} // Can be used by any P.
  60         Mutex                 // Protects shared.
  61 }
  62
  63 type poolLocal struct {
  64         poolLocalInternal
  65
  66         // Prevents false sharing on widespread platforms with
  67         // 128 mod (cache line size) = 0 .
  68         pad [128 - unsafe.Sizeof(poolLocalInternal{})%128]byte
  69 }
  70
  71 // from runtime
  72 func fastrand() uint32
  73
  74 var poolRaceHash [128]uint64
  75
  76 // poolRaceAddr returns an address to use as the synchronization point
  77 // for race detector logic. We don't use the actual pointer stored in x
  78 // directly, for fear of conflicting with other synchronization on that address.
  79 // Instead, we hash the pointer to get an index into poolRaceHash.
  80 // See discussion on golang.org/cl/31589.
  81 func poolRaceAddr(x interface{}) unsafe.Pointer {
  82         ptr := uintptr((*[2]unsafe.Pointer)(unsafe.Pointer(&x))[1])
  83         h := uint32((uint64(uint32(ptr)) * 0x85ebca6b) >> 16)
  84         return unsafe.Pointer(&poolRaceHash[h%uint32(len(poolRaceHash))])
  85 }
  86
  87 // Put adds x to the pool.
  88 func (p *Pool) Put(x interface{}) {
  89         if x == nil {
  90                 return
  91         }
  92         if race.Enabled {
  93                 if fastrand()%4 == 0 {
  94                         // Randomly drop x on floor.
  95                         return
  96                 }
  97                 race.ReleaseMerge(poolRaceAddr(x))
  98                 race.Disable()
  99         }
 100         l := p.pin()
 101         if l.private == nil {
 102                 l.private = x
 103                 x = nil
 104         }
 105         runtime_procUnpin()
 106         if x != nil {
 107                 l.Lock()
 108                 l.shared = append(l.shared, x)
 109                 l.Unlock()
 110         }
 111         if race.Enabled {
 112                 race.Enable()
 113         }
 114 }
 115
 116 // Get selects an arbitrary item from the Pool, removes it from the
 117 // Pool, and returns it to the caller.
 118 // Get may choose to ignore the pool and treat it as empty.
 119 // Callers should not assume any relation between values passed to Put and
 120 // the values returned by Get.
 121 //
 122 // If Get would otherwise return nil and p.New is non-nil, Get returns
 123 // the result of calling p.New.
 124 func (p *Pool) Get() interface{} {
 125         if race.Enabled {
 126                 race.Disable()
 127         }
 128         l := p.pin()
 129         x := l.private
 130         l.private = nil
 131         runtime_procUnpin()
 132         if x == nil {
 133                 l.Lock()
 134                 last := len(l.shared) - 1
 135                 if last >= 0 {
 136                         x = l.shared[last]
 137                         l.shared = l.shared[:last]
 138                 }
 139                 l.Unlock()
 140                 if x == nil {
 141                         x = p.getSlow()
 142                 }
 143         }
 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() (x interface{}) {
 157         // See the comment in pin regarding ordering of the loads.
 158         size := atomic.LoadUintptr(&p.localSize) // load-acquire
 159         local := p.local                         // load-consume
 160         // Try to steal one element from other procs.
 161         pid := runtime_procPin()
 162         runtime_procUnpin()
 163         for i := 0; i < int(size); i++ {
 164                 l := indexLocal(local, (pid+i+1)%int(size))
 165                 l.Lock()
 166                 last := len(l.shared) - 1
 167                 if last >= 0 {
 168                         x = l.shared[last]
 169                         l.shared = l.shared[:last]
 170                         l.Unlock()
 171                         break
 172                 }
 173                 l.Unlock()
 174         }
 175         return x
 176 }
 177
 178 // pin pins the current goroutine to P, disables preemption and returns poolLocal pool for the P.
 179 // Caller must call runtime_procUnpin() when done with the pool.
 180 func (p *Pool) pin() *poolLocal {
 181         pid := runtime_procPin()
 182         // In pinSlow we store to localSize and then to local, here we load in opposite order.
 183         // Since we've disabled preemption, GC cannot happen in between.
 184         // Thus here we must observe local at least as large localSize.
 185         // We can observe a newer/larger local, it is fine (we must observe its zero-initialized-ness).
 186         s := atomic.LoadUintptr(&p.localSize) // load-acquire
 187         l := p.local                          // load-consume
 188         if uintptr(pid) < s {
 189                 return indexLocal(l, pid)
 190         }
 191         return p.pinSlow()
 192 }
 193
 194 func (p *Pool) pinSlow() *poolLocal {
 195         // Retry under the mutex.
 196         // Can not lock the mutex while pinned.
 197         runtime_procUnpin()
 198         allPoolsMu.Lock()
 199         defer allPoolsMu.Unlock()
 200         pid := runtime_procPin()
 201         // poolCleanup won't be called while we are pinned.
 202         s := p.localSize
 203         l := p.local
 204         if uintptr(pid) < s {
 205                 return indexLocal(l, pid)
 206         }
 207         if p.local == nil {
 208                 allPools = append(allPools, p)
 209         }
 210         // If GOMAXPROCS changes between GCs, we re-allocate the array and lose the old one.
 211         size := runtime.GOMAXPROCS(0)
 212         local := make([]poolLocal, size)
 213         atomic.StorePointer(&p.local, unsafe.Pointer(&local[0])) // store-release
 214         atomic.StoreUintptr(&p.localSize, uintptr(size))         // store-release
 215         return &local[pid]
 216 }
 217
 218 func poolCleanup() {
 219         // This function is called with the world stopped, at the beginning of a garbage collection.
 220         // It must not allocate and probably should not call any runtime functions.
 221         // Defensively zero out everything, 2 reasons:
 222         // 1. To prevent false retention of whole Pools.
 223         // 2. If GC happens while a goroutine works with l.shared in Put/Get,
 224         //    it will retain whole Pool. So next cycle memory consumption would be doubled.
 225         for i, p := range allPools {
 226                 allPools[i] = nil
 227                 for i := 0; i < int(p.localSize); i++ {
 228                         l := indexLocal(p.local, i)
 229                         l.private = nil
 230                         for j := range l.shared {
 231                                 l.shared[j] = nil
 232                         }
 233                         l.shared = nil
 234                 }
 235                 p.local = nil
 236                 p.localSize = 0
 237         }
 238         allPools = []*Pool{}
 239 }
 240
 241 var (
 242         allPoolsMu Mutex
 243         allPools   []*Pool
 244 )
 245
 246 func init() {
 247         runtime_registerPoolCleanup(poolCleanup)
 248 }
 249
 250 func indexLocal(l unsafe.Pointer, i int) *poolLocal {
 251         lp := unsafe.Pointer(uintptr(l) + uintptr(i)*unsafe.Sizeof(poolLocal{}))
 252         return (*poolLocal)(lp)
 253 }
 254
 255 // Implemented in runtime.
 256 func runtime_registerPoolCleanup(cleanup func())
 257 func runtime_procPin() int
 258 func runtime_procUnpin()