...
Run Format

Source file src/sync/pool.go

Documentation: sync

     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()
   259  

View as plain text