Black Lives Matter. Support the Equal Justice Initiative.

Source file src/runtime/mgcwork.go

Documentation: runtime

     1  // Copyright 2009 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 runtime
     6  
     7  import (
     8  	"runtime/internal/atomic"
     9  	"runtime/internal/sys"
    10  	"unsafe"
    11  )
    12  
    13  const (
    14  	_WorkbufSize = 2048 // in bytes; larger values result in less contention
    15  
    16  	// workbufAlloc is the number of bytes to allocate at a time
    17  	// for new workbufs. This must be a multiple of pageSize and
    18  	// should be a multiple of _WorkbufSize.
    19  	//
    20  	// Larger values reduce workbuf allocation overhead. Smaller
    21  	// values reduce heap fragmentation.
    22  	workbufAlloc = 32 << 10
    23  )
    24  
    25  // throwOnGCWork causes any operations that add pointers to a gcWork
    26  // buffer to throw.
    27  //
    28  // TODO(austin): This is a temporary debugging measure for issue
    29  // #27993. To be removed before release.
    30  var throwOnGCWork bool
    31  
    32  func init() {
    33  	if workbufAlloc%pageSize != 0 || workbufAlloc%_WorkbufSize != 0 {
    34  		throw("bad workbufAlloc")
    35  	}
    36  }
    37  
    38  // Garbage collector work pool abstraction.
    39  //
    40  // This implements a producer/consumer model for pointers to grey
    41  // objects. A grey object is one that is marked and on a work
    42  // queue. A black object is marked and not on a work queue.
    43  //
    44  // Write barriers, root discovery, stack scanning, and object scanning
    45  // produce pointers to grey objects. Scanning consumes pointers to
    46  // grey objects, thus blackening them, and then scans them,
    47  // potentially producing new pointers to grey objects.
    48  
    49  // A gcWork provides the interface to produce and consume work for the
    50  // garbage collector.
    51  //
    52  // A gcWork can be used on the stack as follows:
    53  //
    54  //     (preemption must be disabled)
    55  //     gcw := &getg().m.p.ptr().gcw
    56  //     .. call gcw.put() to produce and gcw.tryGet() to consume ..
    57  //
    58  // It's important that any use of gcWork during the mark phase prevent
    59  // the garbage collector from transitioning to mark termination since
    60  // gcWork may locally hold GC work buffers. This can be done by
    61  // disabling preemption (systemstack or acquirem).
    62  type gcWork struct {
    63  	// wbuf1 and wbuf2 are the primary and secondary work buffers.
    64  	//
    65  	// This can be thought of as a stack of both work buffers'
    66  	// pointers concatenated. When we pop the last pointer, we
    67  	// shift the stack up by one work buffer by bringing in a new
    68  	// full buffer and discarding an empty one. When we fill both
    69  	// buffers, we shift the stack down by one work buffer by
    70  	// bringing in a new empty buffer and discarding a full one.
    71  	// This way we have one buffer's worth of hysteresis, which
    72  	// amortizes the cost of getting or putting a work buffer over
    73  	// at least one buffer of work and reduces contention on the
    74  	// global work lists.
    75  	//
    76  	// wbuf1 is always the buffer we're currently pushing to and
    77  	// popping from and wbuf2 is the buffer that will be discarded
    78  	// next.
    79  	//
    80  	// Invariant: Both wbuf1 and wbuf2 are nil or neither are.
    81  	wbuf1, wbuf2 *workbuf
    82  
    83  	// Bytes marked (blackened) on this gcWork. This is aggregated
    84  	// into work.bytesMarked by dispose.
    85  	bytesMarked uint64
    86  
    87  	// Scan work performed on this gcWork. This is aggregated into
    88  	// gcController by dispose and may also be flushed by callers.
    89  	scanWork int64
    90  
    91  	// flushedWork indicates that a non-empty work buffer was
    92  	// flushed to the global work list since the last gcMarkDone
    93  	// termination check. Specifically, this indicates that this
    94  	// gcWork may have communicated work to another gcWork.
    95  	flushedWork bool
    96  
    97  	// pauseGen causes put operations to spin while pauseGen ==
    98  	// gcWorkPauseGen if debugCachedWork is true.
    99  	pauseGen uint32
   100  
   101  	// putGen is the pauseGen of the last putGen.
   102  	putGen uint32
   103  
   104  	// pauseStack is the stack at which this P was paused if
   105  	// debugCachedWork is true.
   106  	pauseStack [16]uintptr
   107  }
   108  
   109  // Most of the methods of gcWork are go:nowritebarrierrec because the
   110  // write barrier itself can invoke gcWork methods but the methods are
   111  // not generally re-entrant. Hence, if a gcWork method invoked the
   112  // write barrier while the gcWork was in an inconsistent state, and
   113  // the write barrier in turn invoked a gcWork method, it could
   114  // permanently corrupt the gcWork.
   115  
   116  func (w *gcWork) init() {
   117  	w.wbuf1 = getempty()
   118  	wbuf2 := trygetfull()
   119  	if wbuf2 == nil {
   120  		wbuf2 = getempty()
   121  	}
   122  	w.wbuf2 = wbuf2
   123  }
   124  
   125  func (w *gcWork) checkPut(ptr uintptr, ptrs []uintptr) {
   126  	if debugCachedWork {
   127  		alreadyFailed := w.putGen == w.pauseGen
   128  		w.putGen = w.pauseGen
   129  		if !canPreemptM(getg().m) {
   130  			// If we were to spin, the runtime may
   131  			// deadlock. Since we can't be preempted, the
   132  			// spin could prevent gcMarkDone from
   133  			// finishing the ragged barrier, which is what
   134  			// releases us from the spin.
   135  			return
   136  		}
   137  		for atomic.Load(&gcWorkPauseGen) == w.pauseGen {
   138  		}
   139  		if throwOnGCWork {
   140  			printlock()
   141  			if alreadyFailed {
   142  				println("runtime: checkPut already failed at this generation")
   143  			}
   144  			println("runtime: late gcWork put")
   145  			if ptr != 0 {
   146  				gcDumpObject("ptr", ptr, ^uintptr(0))
   147  			}
   148  			for _, ptr := range ptrs {
   149  				gcDumpObject("ptrs", ptr, ^uintptr(0))
   150  			}
   151  			println("runtime: paused at")
   152  			for _, pc := range w.pauseStack {
   153  				if pc == 0 {
   154  					break
   155  				}
   156  				f := findfunc(pc)
   157  				if f.valid() {
   158  					// Obviously this doesn't
   159  					// relate to ancestor
   160  					// tracebacks, but this
   161  					// function prints what we
   162  					// want.
   163  					printAncestorTracebackFuncInfo(f, pc)
   164  				} else {
   165  					println("\tunknown PC ", hex(pc), "\n")
   166  				}
   167  			}
   168  			throw("throwOnGCWork")
   169  		}
   170  	}
   171  }
   172  
   173  // put enqueues a pointer for the garbage collector to trace.
   174  // obj must point to the beginning of a heap object or an oblet.
   175  //go:nowritebarrierrec
   176  func (w *gcWork) put(obj uintptr) {
   177  	w.checkPut(obj, nil)
   178  
   179  	flushed := false
   180  	wbuf := w.wbuf1
   181  	// Record that this may acquire the wbufSpans or heap lock to
   182  	// allocate a workbuf.
   183  	lockWithRankMayAcquire(&work.wbufSpans.lock, lockRankWbufSpans)
   184  	lockWithRankMayAcquire(&mheap_.lock, lockRankMheap)
   185  	if wbuf == nil {
   186  		w.init()
   187  		wbuf = w.wbuf1
   188  		// wbuf is empty at this point.
   189  	} else if wbuf.nobj == len(wbuf.obj) {
   190  		w.wbuf1, w.wbuf2 = w.wbuf2, w.wbuf1
   191  		wbuf = w.wbuf1
   192  		if wbuf.nobj == len(wbuf.obj) {
   193  			putfull(wbuf)
   194  			w.flushedWork = true
   195  			wbuf = getempty()
   196  			w.wbuf1 = wbuf
   197  			flushed = true
   198  		}
   199  	}
   200  
   201  	wbuf.obj[wbuf.nobj] = obj
   202  	wbuf.nobj++
   203  
   204  	// If we put a buffer on full, let the GC controller know so
   205  	// it can encourage more workers to run. We delay this until
   206  	// the end of put so that w is in a consistent state, since
   207  	// enlistWorker may itself manipulate w.
   208  	if flushed && gcphase == _GCmark {
   209  		gcController.enlistWorker()
   210  	}
   211  }
   212  
   213  // putFast does a put and reports whether it can be done quickly
   214  // otherwise it returns false and the caller needs to call put.
   215  //go:nowritebarrierrec
   216  func (w *gcWork) putFast(obj uintptr) bool {
   217  	w.checkPut(obj, nil)
   218  
   219  	wbuf := w.wbuf1
   220  	if wbuf == nil {
   221  		return false
   222  	} else if wbuf.nobj == len(wbuf.obj) {
   223  		return false
   224  	}
   225  
   226  	wbuf.obj[wbuf.nobj] = obj
   227  	wbuf.nobj++
   228  	return true
   229  }
   230  
   231  // putBatch performs a put on every pointer in obj. See put for
   232  // constraints on these pointers.
   233  //
   234  //go:nowritebarrierrec
   235  func (w *gcWork) putBatch(obj []uintptr) {
   236  	if len(obj) == 0 {
   237  		return
   238  	}
   239  
   240  	w.checkPut(0, obj)
   241  
   242  	flushed := false
   243  	wbuf := w.wbuf1
   244  	if wbuf == nil {
   245  		w.init()
   246  		wbuf = w.wbuf1
   247  	}
   248  
   249  	for len(obj) > 0 {
   250  		for wbuf.nobj == len(wbuf.obj) {
   251  			putfull(wbuf)
   252  			w.flushedWork = true
   253  			w.wbuf1, w.wbuf2 = w.wbuf2, getempty()
   254  			wbuf = w.wbuf1
   255  			flushed = true
   256  		}
   257  		n := copy(wbuf.obj[wbuf.nobj:], obj)
   258  		wbuf.nobj += n
   259  		obj = obj[n:]
   260  	}
   261  
   262  	if flushed && gcphase == _GCmark {
   263  		gcController.enlistWorker()
   264  	}
   265  }
   266  
   267  // tryGet dequeues a pointer for the garbage collector to trace.
   268  //
   269  // If there are no pointers remaining in this gcWork or in the global
   270  // queue, tryGet returns 0.  Note that there may still be pointers in
   271  // other gcWork instances or other caches.
   272  //go:nowritebarrierrec
   273  func (w *gcWork) tryGet() uintptr {
   274  	wbuf := w.wbuf1
   275  	if wbuf == nil {
   276  		w.init()
   277  		wbuf = w.wbuf1
   278  		// wbuf is empty at this point.
   279  	}
   280  	if wbuf.nobj == 0 {
   281  		w.wbuf1, w.wbuf2 = w.wbuf2, w.wbuf1
   282  		wbuf = w.wbuf1
   283  		if wbuf.nobj == 0 {
   284  			owbuf := wbuf
   285  			wbuf = trygetfull()
   286  			if wbuf == nil {
   287  				return 0
   288  			}
   289  			putempty(owbuf)
   290  			w.wbuf1 = wbuf
   291  		}
   292  	}
   293  
   294  	wbuf.nobj--
   295  	return wbuf.obj[wbuf.nobj]
   296  }
   297  
   298  // tryGetFast dequeues a pointer for the garbage collector to trace
   299  // if one is readily available. Otherwise it returns 0 and
   300  // the caller is expected to call tryGet().
   301  //go:nowritebarrierrec
   302  func (w *gcWork) tryGetFast() uintptr {
   303  	wbuf := w.wbuf1
   304  	if wbuf == nil {
   305  		return 0
   306  	}
   307  	if wbuf.nobj == 0 {
   308  		return 0
   309  	}
   310  
   311  	wbuf.nobj--
   312  	return wbuf.obj[wbuf.nobj]
   313  }
   314  
   315  // dispose returns any cached pointers to the global queue.
   316  // The buffers are being put on the full queue so that the
   317  // write barriers will not simply reacquire them before the
   318  // GC can inspect them. This helps reduce the mutator's
   319  // ability to hide pointers during the concurrent mark phase.
   320  //
   321  //go:nowritebarrierrec
   322  func (w *gcWork) dispose() {
   323  	if wbuf := w.wbuf1; wbuf != nil {
   324  		if wbuf.nobj == 0 {
   325  			putempty(wbuf)
   326  		} else {
   327  			putfull(wbuf)
   328  			w.flushedWork = true
   329  		}
   330  		w.wbuf1 = nil
   331  
   332  		wbuf = w.wbuf2
   333  		if wbuf.nobj == 0 {
   334  			putempty(wbuf)
   335  		} else {
   336  			putfull(wbuf)
   337  			w.flushedWork = true
   338  		}
   339  		w.wbuf2 = nil
   340  	}
   341  	if w.bytesMarked != 0 {
   342  		// dispose happens relatively infrequently. If this
   343  		// atomic becomes a problem, we should first try to
   344  		// dispose less and if necessary aggregate in a per-P
   345  		// counter.
   346  		atomic.Xadd64(&work.bytesMarked, int64(w.bytesMarked))
   347  		w.bytesMarked = 0
   348  	}
   349  	if w.scanWork != 0 {
   350  		atomic.Xaddint64(&gcController.scanWork, w.scanWork)
   351  		w.scanWork = 0
   352  	}
   353  }
   354  
   355  // balance moves some work that's cached in this gcWork back on the
   356  // global queue.
   357  //go:nowritebarrierrec
   358  func (w *gcWork) balance() {
   359  	if w.wbuf1 == nil {
   360  		return
   361  	}
   362  	if wbuf := w.wbuf2; wbuf.nobj != 0 {
   363  		w.checkPut(0, wbuf.obj[:wbuf.nobj])
   364  		putfull(wbuf)
   365  		w.flushedWork = true
   366  		w.wbuf2 = getempty()
   367  	} else if wbuf := w.wbuf1; wbuf.nobj > 4 {
   368  		w.checkPut(0, wbuf.obj[:wbuf.nobj])
   369  		w.wbuf1 = handoff(wbuf)
   370  		w.flushedWork = true // handoff did putfull
   371  	} else {
   372  		return
   373  	}
   374  	// We flushed a buffer to the full list, so wake a worker.
   375  	if gcphase == _GCmark {
   376  		gcController.enlistWorker()
   377  	}
   378  }
   379  
   380  // empty reports whether w has no mark work available.
   381  //go:nowritebarrierrec
   382  func (w *gcWork) empty() bool {
   383  	return w.wbuf1 == nil || (w.wbuf1.nobj == 0 && w.wbuf2.nobj == 0)
   384  }
   385  
   386  // Internally, the GC work pool is kept in arrays in work buffers.
   387  // The gcWork interface caches a work buffer until full (or empty) to
   388  // avoid contending on the global work buffer lists.
   389  
   390  type workbufhdr struct {
   391  	node lfnode // must be first
   392  	nobj int
   393  }
   394  
   395  //go:notinheap
   396  type workbuf struct {
   397  	workbufhdr
   398  	// account for the above fields
   399  	obj [(_WorkbufSize - unsafe.Sizeof(workbufhdr{})) / sys.PtrSize]uintptr
   400  }
   401  
   402  // workbuf factory routines. These funcs are used to manage the
   403  // workbufs.
   404  // If the GC asks for some work these are the only routines that
   405  // make wbufs available to the GC.
   406  
   407  func (b *workbuf) checknonempty() {
   408  	if b.nobj == 0 {
   409  		throw("workbuf is empty")
   410  	}
   411  }
   412  
   413  func (b *workbuf) checkempty() {
   414  	if b.nobj != 0 {
   415  		throw("workbuf is not empty")
   416  	}
   417  }
   418  
   419  // getempty pops an empty work buffer off the work.empty list,
   420  // allocating new buffers if none are available.
   421  //go:nowritebarrier
   422  func getempty() *workbuf {
   423  	var b *workbuf
   424  	if work.empty != 0 {
   425  		b = (*workbuf)(work.empty.pop())
   426  		if b != nil {
   427  			b.checkempty()
   428  		}
   429  	}
   430  	// Record that this may acquire the wbufSpans or heap lock to
   431  	// allocate a workbuf.
   432  	lockWithRankMayAcquire(&work.wbufSpans.lock, lockRankWbufSpans)
   433  	lockWithRankMayAcquire(&mheap_.lock, lockRankMheap)
   434  	if b == nil {
   435  		// Allocate more workbufs.
   436  		var s *mspan
   437  		if work.wbufSpans.free.first != nil {
   438  			lock(&work.wbufSpans.lock)
   439  			s = work.wbufSpans.free.first
   440  			if s != nil {
   441  				work.wbufSpans.free.remove(s)
   442  				work.wbufSpans.busy.insert(s)
   443  			}
   444  			unlock(&work.wbufSpans.lock)
   445  		}
   446  		if s == nil {
   447  			systemstack(func() {
   448  				s = mheap_.allocManual(workbufAlloc/pageSize, &memstats.gc_sys)
   449  			})
   450  			if s == nil {
   451  				throw("out of memory")
   452  			}
   453  			// Record the new span in the busy list.
   454  			lock(&work.wbufSpans.lock)
   455  			work.wbufSpans.busy.insert(s)
   456  			unlock(&work.wbufSpans.lock)
   457  		}
   458  		// Slice up the span into new workbufs. Return one and
   459  		// put the rest on the empty list.
   460  		for i := uintptr(0); i+_WorkbufSize <= workbufAlloc; i += _WorkbufSize {
   461  			newb := (*workbuf)(unsafe.Pointer(s.base() + i))
   462  			newb.nobj = 0
   463  			lfnodeValidate(&newb.node)
   464  			if i == 0 {
   465  				b = newb
   466  			} else {
   467  				putempty(newb)
   468  			}
   469  		}
   470  	}
   471  	return b
   472  }
   473  
   474  // putempty puts a workbuf onto the work.empty list.
   475  // Upon entry this go routine owns b. The lfstack.push relinquishes ownership.
   476  //go:nowritebarrier
   477  func putempty(b *workbuf) {
   478  	b.checkempty()
   479  	work.empty.push(&b.node)
   480  }
   481  
   482  // putfull puts the workbuf on the work.full list for the GC.
   483  // putfull accepts partially full buffers so the GC can avoid competing
   484  // with the mutators for ownership of partially full buffers.
   485  //go:nowritebarrier
   486  func putfull(b *workbuf) {
   487  	b.checknonempty()
   488  	work.full.push(&b.node)
   489  }
   490  
   491  // trygetfull tries to get a full or partially empty workbuffer.
   492  // If one is not immediately available return nil
   493  //go:nowritebarrier
   494  func trygetfull() *workbuf {
   495  	b := (*workbuf)(work.full.pop())
   496  	if b != nil {
   497  		b.checknonempty()
   498  		return b
   499  	}
   500  	return b
   501  }
   502  
   503  //go:nowritebarrier
   504  func handoff(b *workbuf) *workbuf {
   505  	// Make new buffer with half of b's pointers.
   506  	b1 := getempty()
   507  	n := b.nobj / 2
   508  	b.nobj -= n
   509  	b1.nobj = n
   510  	memmove(unsafe.Pointer(&b1.obj[0]), unsafe.Pointer(&b.obj[b.nobj]), uintptr(n)*unsafe.Sizeof(b1.obj[0]))
   511  
   512  	// Put b on full list - let first half of b get stolen.
   513  	putfull(b)
   514  	return b1
   515  }
   516  
   517  // prepareFreeWorkbufs moves busy workbuf spans to free list so they
   518  // can be freed to the heap. This must only be called when all
   519  // workbufs are on the empty list.
   520  func prepareFreeWorkbufs() {
   521  	lock(&work.wbufSpans.lock)
   522  	if work.full != 0 {
   523  		throw("cannot free workbufs when work.full != 0")
   524  	}
   525  	// Since all workbufs are on the empty list, we don't care
   526  	// which ones are in which spans. We can wipe the entire empty
   527  	// list and move all workbuf spans to the free list.
   528  	work.empty = 0
   529  	work.wbufSpans.free.takeAll(&work.wbufSpans.busy)
   530  	unlock(&work.wbufSpans.lock)
   531  }
   532  
   533  // freeSomeWbufs frees some workbufs back to the heap and returns
   534  // true if it should be called again to free more.
   535  func freeSomeWbufs(preemptible bool) bool {
   536  	const batchSize = 64 // ~1–2 µs per span.
   537  	lock(&work.wbufSpans.lock)
   538  	if gcphase != _GCoff || work.wbufSpans.free.isEmpty() {
   539  		unlock(&work.wbufSpans.lock)
   540  		return false
   541  	}
   542  	systemstack(func() {
   543  		gp := getg().m.curg
   544  		for i := 0; i < batchSize && !(preemptible && gp.preempt); i++ {
   545  			span := work.wbufSpans.free.first
   546  			if span == nil {
   547  				break
   548  			}
   549  			work.wbufSpans.free.remove(span)
   550  			mheap_.freeManual(span, &memstats.gc_sys)
   551  		}
   552  	})
   553  	more := !work.wbufSpans.free.isEmpty()
   554  	unlock(&work.wbufSpans.lock)
   555  	return more
   556  }
   557  

View as plain text