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  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  	// Scan work performed on this gcWork. This is aggregated into
    81  	// gcController by dispose and may also be flushed by callers.
    82  	scanWork int64
    83  
    84  	// flushedWork indicates that a non-empty work buffer was
    85  	// flushed to the global work list since the last gcMarkDone
    86  	// termination check. Specifically, this indicates that this
    87  	// gcWork may have communicated work to another gcWork.
    88  	flushedWork bool
    89  }
    90  
    91  // Most of the methods of gcWork are go:nowritebarrierrec because the
    92  // write barrier itself can invoke gcWork methods but the methods are
    93  // not generally re-entrant. Hence, if a gcWork method invoked the
    94  // write barrier while the gcWork was in an inconsistent state, and
    95  // the write barrier in turn invoked a gcWork method, it could
    96  // permanently corrupt the gcWork.
    97  
    98  func (w *gcWork) init() {
    99  	w.wbuf1 = getempty()
   100  	wbuf2 := trygetfull()
   101  	if wbuf2 == nil {
   102  		wbuf2 = getempty()
   103  	}
   104  	w.wbuf2 = wbuf2
   105  }
   106  
   107  // put enqueues a pointer for the garbage collector to trace.
   108  // obj must point to the beginning of a heap object or an oblet.
   109  //go:nowritebarrierrec
   110  func (w *gcWork) put(obj uintptr) {
   111  	flushed := false
   112  	wbuf := w.wbuf1
   113  	// Record that this may acquire the wbufSpans or heap lock to
   114  	// allocate a workbuf.
   115  	lockWithRankMayAcquire(&work.wbufSpans.lock, lockRankWbufSpans)
   116  	lockWithRankMayAcquire(&mheap_.lock, lockRankMheap)
   117  	if wbuf == nil {
   118  		w.init()
   119  		wbuf = w.wbuf1
   120  		// wbuf is empty at this point.
   121  	} else if wbuf.nobj == len(wbuf.obj) {
   122  		w.wbuf1, w.wbuf2 = w.wbuf2, w.wbuf1
   123  		wbuf = w.wbuf1
   124  		if wbuf.nobj == len(wbuf.obj) {
   125  			putfull(wbuf)
   126  			w.flushedWork = true
   127  			wbuf = getempty()
   128  			w.wbuf1 = wbuf
   129  			flushed = true
   130  		}
   131  	}
   132  
   133  	wbuf.obj[wbuf.nobj] = obj
   134  	wbuf.nobj++
   135  
   136  	// If we put a buffer on full, let the GC controller know so
   137  	// it can encourage more workers to run. We delay this until
   138  	// the end of put so that w is in a consistent state, since
   139  	// enlistWorker may itself manipulate w.
   140  	if flushed && gcphase == _GCmark {
   141  		gcController.enlistWorker()
   142  	}
   143  }
   144  
   145  // putFast does a put and reports whether it can be done quickly
   146  // otherwise it returns false and the caller needs to call put.
   147  //go:nowritebarrierrec
   148  func (w *gcWork) putFast(obj uintptr) bool {
   149  	wbuf := w.wbuf1
   150  	if wbuf == nil {
   151  		return false
   152  	} else if wbuf.nobj == len(wbuf.obj) {
   153  		return false
   154  	}
   155  
   156  	wbuf.obj[wbuf.nobj] = obj
   157  	wbuf.nobj++
   158  	return true
   159  }
   160  
   161  // putBatch performs a put on every pointer in obj. See put for
   162  // constraints on these pointers.
   163  //
   164  //go:nowritebarrierrec
   165  func (w *gcWork) putBatch(obj []uintptr) {
   166  	if len(obj) == 0 {
   167  		return
   168  	}
   169  
   170  	flushed := false
   171  	wbuf := w.wbuf1
   172  	if wbuf == nil {
   173  		w.init()
   174  		wbuf = w.wbuf1
   175  	}
   176  
   177  	for len(obj) > 0 {
   178  		for wbuf.nobj == len(wbuf.obj) {
   179  			putfull(wbuf)
   180  			w.flushedWork = true
   181  			w.wbuf1, w.wbuf2 = w.wbuf2, getempty()
   182  			wbuf = w.wbuf1
   183  			flushed = true
   184  		}
   185  		n := copy(wbuf.obj[wbuf.nobj:], obj)
   186  		wbuf.nobj += n
   187  		obj = obj[n:]
   188  	}
   189  
   190  	if flushed && gcphase == _GCmark {
   191  		gcController.enlistWorker()
   192  	}
   193  }
   194  
   195  // tryGet dequeues a pointer for the garbage collector to trace.
   196  //
   197  // If there are no pointers remaining in this gcWork or in the global
   198  // queue, tryGet returns 0.  Note that there may still be pointers in
   199  // other gcWork instances or other caches.
   200  //go:nowritebarrierrec
   201  func (w *gcWork) tryGet() uintptr {
   202  	wbuf := w.wbuf1
   203  	if wbuf == nil {
   204  		w.init()
   205  		wbuf = w.wbuf1
   206  		// wbuf is empty at this point.
   207  	}
   208  	if wbuf.nobj == 0 {
   209  		w.wbuf1, w.wbuf2 = w.wbuf2, w.wbuf1
   210  		wbuf = w.wbuf1
   211  		if wbuf.nobj == 0 {
   212  			owbuf := wbuf
   213  			wbuf = trygetfull()
   214  			if wbuf == nil {
   215  				return 0
   216  			}
   217  			putempty(owbuf)
   218  			w.wbuf1 = wbuf
   219  		}
   220  	}
   221  
   222  	wbuf.nobj--
   223  	return wbuf.obj[wbuf.nobj]
   224  }
   225  
   226  // tryGetFast dequeues a pointer for the garbage collector to trace
   227  // if one is readily available. Otherwise it returns 0 and
   228  // the caller is expected to call tryGet().
   229  //go:nowritebarrierrec
   230  func (w *gcWork) tryGetFast() uintptr {
   231  	wbuf := w.wbuf1
   232  	if wbuf == nil {
   233  		return 0
   234  	}
   235  	if 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.scanWork != 0 {
   278  		atomic.Xaddint64(&gcController.scanWork, w.scanWork)
   279  		w.scanWork = 0
   280  	}
   281  }
   282  
   283  // balance moves some work that's cached in this gcWork back on the
   284  // global queue.
   285  //go:nowritebarrierrec
   286  func (w *gcWork) balance() {
   287  	if w.wbuf1 == nil {
   288  		return
   289  	}
   290  	if wbuf := w.wbuf2; wbuf.nobj != 0 {
   291  		putfull(wbuf)
   292  		w.flushedWork = true
   293  		w.wbuf2 = getempty()
   294  	} else if wbuf := w.wbuf1; wbuf.nobj > 4 {
   295  		w.wbuf1 = handoff(wbuf)
   296  		w.flushedWork = true // handoff did putfull
   297  	} else {
   298  		return
   299  	}
   300  	// We flushed a buffer to the full list, so wake a worker.
   301  	if gcphase == _GCmark {
   302  		gcController.enlistWorker()
   303  	}
   304  }
   305  
   306  // empty reports whether w has no mark work available.
   307  //go:nowritebarrierrec
   308  func (w *gcWork) empty() bool {
   309  	return w.wbuf1 == nil || (w.wbuf1.nobj == 0 && w.wbuf2.nobj == 0)
   310  }
   311  
   312  // Internally, the GC work pool is kept in arrays in work buffers.
   313  // The gcWork interface caches a work buffer until full (or empty) to
   314  // avoid contending on the global work buffer lists.
   315  
   316  type workbufhdr struct {
   317  	node lfnode // must be first
   318  	nobj int
   319  }
   320  
   321  //go:notinheap
   322  type workbuf struct {
   323  	workbufhdr
   324  	// account for the above fields
   325  	obj [(_WorkbufSize - unsafe.Sizeof(workbufhdr{})) / sys.PtrSize]uintptr
   326  }
   327  
   328  // workbuf factory routines. These funcs are used to manage the
   329  // workbufs.
   330  // If the GC asks for some work these are the only routines that
   331  // make wbufs available to the GC.
   332  
   333  func (b *workbuf) checknonempty() {
   334  	if b.nobj == 0 {
   335  		throw("workbuf is empty")
   336  	}
   337  }
   338  
   339  func (b *workbuf) checkempty() {
   340  	if b.nobj != 0 {
   341  		throw("workbuf is not empty")
   342  	}
   343  }
   344  
   345  // getempty pops an empty work buffer off the work.empty list,
   346  // allocating new buffers if none are available.
   347  //go:nowritebarrier
   348  func getempty() *workbuf {
   349  	var b *workbuf
   350  	if work.empty != 0 {
   351  		b = (*workbuf)(work.empty.pop())
   352  		if b != nil {
   353  			b.checkempty()
   354  		}
   355  	}
   356  	// Record that this may acquire the wbufSpans or heap lock to
   357  	// allocate a workbuf.
   358  	lockWithRankMayAcquire(&work.wbufSpans.lock, lockRankWbufSpans)
   359  	lockWithRankMayAcquire(&mheap_.lock, lockRankMheap)
   360  	if b == nil {
   361  		// Allocate more workbufs.
   362  		var s *mspan
   363  		if work.wbufSpans.free.first != nil {
   364  			lock(&work.wbufSpans.lock)
   365  			s = work.wbufSpans.free.first
   366  			if s != nil {
   367  				work.wbufSpans.free.remove(s)
   368  				work.wbufSpans.busy.insert(s)
   369  			}
   370  			unlock(&work.wbufSpans.lock)
   371  		}
   372  		if s == nil {
   373  			systemstack(func() {
   374  				s = mheap_.allocManual(workbufAlloc/pageSize, spanAllocWorkBuf)
   375  			})
   376  			if s == nil {
   377  				throw("out of memory")
   378  			}
   379  			// Record the new span in the busy list.
   380  			lock(&work.wbufSpans.lock)
   381  			work.wbufSpans.busy.insert(s)
   382  			unlock(&work.wbufSpans.lock)
   383  		}
   384  		// Slice up the span into new workbufs. Return one and
   385  		// put the rest on the empty list.
   386  		for i := uintptr(0); i+_WorkbufSize <= workbufAlloc; i += _WorkbufSize {
   387  			newb := (*workbuf)(unsafe.Pointer(s.base() + i))
   388  			newb.nobj = 0
   389  			lfnodeValidate(&newb.node)
   390  			if i == 0 {
   391  				b = newb
   392  			} else {
   393  				putempty(newb)
   394  			}
   395  		}
   396  	}
   397  	return b
   398  }
   399  
   400  // putempty puts a workbuf onto the work.empty list.
   401  // Upon entry this goroutine owns b. The lfstack.push relinquishes ownership.
   402  //go:nowritebarrier
   403  func putempty(b *workbuf) {
   404  	b.checkempty()
   405  	work.empty.push(&b.node)
   406  }
   407  
   408  // putfull puts the workbuf on the work.full list for the GC.
   409  // putfull accepts partially full buffers so the GC can avoid competing
   410  // with the mutators for ownership of partially full buffers.
   411  //go:nowritebarrier
   412  func putfull(b *workbuf) {
   413  	b.checknonempty()
   414  	work.full.push(&b.node)
   415  }
   416  
   417  // trygetfull tries to get a full or partially empty workbuffer.
   418  // If one is not immediately available return nil
   419  //go:nowritebarrier
   420  func trygetfull() *workbuf {
   421  	b := (*workbuf)(work.full.pop())
   422  	if b != nil {
   423  		b.checknonempty()
   424  		return b
   425  	}
   426  	return b
   427  }
   428  
   429  //go:nowritebarrier
   430  func handoff(b *workbuf) *workbuf {
   431  	// Make new buffer with half of b's pointers.
   432  	b1 := getempty()
   433  	n := b.nobj / 2
   434  	b.nobj -= n
   435  	b1.nobj = n
   436  	memmove(unsafe.Pointer(&b1.obj[0]), unsafe.Pointer(&b.obj[b.nobj]), uintptr(n)*unsafe.Sizeof(b1.obj[0]))
   437  
   438  	// Put b on full list - let first half of b get stolen.
   439  	putfull(b)
   440  	return b1
   441  }
   442  
   443  // prepareFreeWorkbufs moves busy workbuf spans to free list so they
   444  // can be freed to the heap. This must only be called when all
   445  // workbufs are on the empty list.
   446  func prepareFreeWorkbufs() {
   447  	lock(&work.wbufSpans.lock)
   448  	if work.full != 0 {
   449  		throw("cannot free workbufs when work.full != 0")
   450  	}
   451  	// Since all workbufs are on the empty list, we don't care
   452  	// which ones are in which spans. We can wipe the entire empty
   453  	// list and move all workbuf spans to the free list.
   454  	work.empty = 0
   455  	work.wbufSpans.free.takeAll(&work.wbufSpans.busy)
   456  	unlock(&work.wbufSpans.lock)
   457  }
   458  
   459  // freeSomeWbufs frees some workbufs back to the heap and returns
   460  // true if it should be called again to free more.
   461  func freeSomeWbufs(preemptible bool) bool {
   462  	const batchSize = 64 // ~1–2 µs per span.
   463  	lock(&work.wbufSpans.lock)
   464  	if gcphase != _GCoff || work.wbufSpans.free.isEmpty() {
   465  		unlock(&work.wbufSpans.lock)
   466  		return false
   467  	}
   468  	systemstack(func() {
   469  		gp := getg().m.curg
   470  		for i := 0; i < batchSize && !(preemptible && gp.preempt); i++ {
   471  			span := work.wbufSpans.free.first
   472  			if span == nil {
   473  				break
   474  			}
   475  			work.wbufSpans.free.remove(span)
   476  			mheap_.freeManual(span, spanAllocWorkBuf)
   477  		}
   478  	})
   479  	more := !work.wbufSpans.free.isEmpty()
   480  	unlock(&work.wbufSpans.lock)
   481  	return more
   482  }
   483
View as plain text