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