...
Run Format

Source file src/runtime/mgcwork.go

     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	
    17	// Garbage collector work pool abstraction.
    18	//
    19	// This implements a producer/consumer model for pointers to grey
    20	// objects. A grey object is one that is marked and on a work
    21	// queue. A black object is marked and not on a work queue.
    22	//
    23	// Write barriers, root discovery, stack scanning, and object scanning
    24	// produce pointers to grey objects. Scanning consumes pointers to
    25	// grey objects, thus blackening them, and then scans them,
    26	// potentially producing new pointers to grey objects.
    27	
    28	// A wbufptr holds a workbuf*, but protects it from write barriers.
    29	// workbufs never live on the heap, so write barriers are unnecessary.
    30	// Write barriers on workbuf pointers may also be dangerous in the GC.
    31	//
    32	// TODO: Since workbuf is now go:notinheap, this isn't necessary.
    33	type wbufptr uintptr
    34	
    35	func wbufptrOf(w *workbuf) wbufptr {
    36		return wbufptr(unsafe.Pointer(w))
    37	}
    38	
    39	func (wp wbufptr) ptr() *workbuf {
    40		return (*workbuf)(unsafe.Pointer(wp))
    41	}
    42	
    43	// A gcWork provides the interface to produce and consume work for the
    44	// garbage collector.
    45	//
    46	// A gcWork can be used on the stack as follows:
    47	//
    48	//     (preemption must be disabled)
    49	//     gcw := &getg().m.p.ptr().gcw
    50	//     .. call gcw.put() to produce and gcw.get() to consume ..
    51	//     if gcBlackenPromptly {
    52	//         gcw.dispose()
    53	//     }
    54	//
    55	// It's important that any use of gcWork during the mark phase prevent
    56	// the garbage collector from transitioning to mark termination since
    57	// gcWork may locally hold GC work buffers. This can be done by
    58	// disabling preemption (systemstack or acquirem).
    59	type gcWork struct {
    60		// wbuf1 and wbuf2 are the primary and secondary work buffers.
    61		//
    62		// This can be thought of as a stack of both work buffers'
    63		// pointers concatenated. When we pop the last pointer, we
    64		// shift the stack up by one work buffer by bringing in a new
    65		// full buffer and discarding an empty one. When we fill both
    66		// buffers, we shift the stack down by one work buffer by
    67		// bringing in a new empty buffer and discarding a full one.
    68		// This way we have one buffer's worth of hysteresis, which
    69		// amortizes the cost of getting or putting a work buffer over
    70		// at least one buffer of work and reduces contention on the
    71		// global work lists.
    72		//
    73		// wbuf1 is always the buffer we're currently pushing to and
    74		// popping from and wbuf2 is the buffer that will be discarded
    75		// next.
    76		//
    77		// Invariant: Both wbuf1 and wbuf2 are nil or neither are.
    78		wbuf1, wbuf2 wbufptr
    79	
    80		// Bytes marked (blackened) on this gcWork. This is aggregated
    81		// into work.bytesMarked by dispose.
    82		bytesMarked uint64
    83	
    84		// Scan work performed on this gcWork. This is aggregated into
    85		// gcController by dispose and may also be flushed by callers.
    86		scanWork int64
    87	}
    88	
    89	func (w *gcWork) init() {
    90		w.wbuf1 = wbufptrOf(getempty())
    91		wbuf2 := trygetfull()
    92		if wbuf2 == nil {
    93			wbuf2 = getempty()
    94		}
    95		w.wbuf2 = wbufptrOf(wbuf2)
    96	}
    97	
    98	// put enqueues a pointer for the garbage collector to trace.
    99	// obj must point to the beginning of a heap object or an oblet.
   100	//go:nowritebarrier
   101	func (w *gcWork) put(obj uintptr) {
   102		flushed := false
   103		wbuf := w.wbuf1.ptr()
   104		if wbuf == nil {
   105			w.init()
   106			wbuf = w.wbuf1.ptr()
   107			// wbuf is empty at this point.
   108		} else if wbuf.nobj == len(wbuf.obj) {
   109			w.wbuf1, w.wbuf2 = w.wbuf2, w.wbuf1
   110			wbuf = w.wbuf1.ptr()
   111			if wbuf.nobj == len(wbuf.obj) {
   112				putfull(wbuf)
   113				wbuf = getempty()
   114				w.wbuf1 = wbufptrOf(wbuf)
   115				flushed = true
   116			}
   117		}
   118	
   119		wbuf.obj[wbuf.nobj] = obj
   120		wbuf.nobj++
   121	
   122		// If we put a buffer on full, let the GC controller know so
   123		// it can encourage more workers to run. We delay this until
   124		// the end of put so that w is in a consistent state, since
   125		// enlistWorker may itself manipulate w.
   126		if flushed && gcphase == _GCmark {
   127			gcController.enlistWorker()
   128		}
   129	}
   130	
   131	// putFast does a put and returns true if it can be done quickly
   132	// otherwise it returns false and the caller needs to call put.
   133	//go:nowritebarrier
   134	func (w *gcWork) putFast(obj uintptr) bool {
   135		wbuf := w.wbuf1.ptr()
   136		if wbuf == nil {
   137			return false
   138		} else if wbuf.nobj == len(wbuf.obj) {
   139			return false
   140		}
   141	
   142		wbuf.obj[wbuf.nobj] = obj
   143		wbuf.nobj++
   144		return true
   145	}
   146	
   147	// tryGet dequeues a pointer for the garbage collector to trace.
   148	//
   149	// If there are no pointers remaining in this gcWork or in the global
   150	// queue, tryGet returns 0.  Note that there may still be pointers in
   151	// other gcWork instances or other caches.
   152	//go:nowritebarrier
   153	func (w *gcWork) tryGet() uintptr {
   154		wbuf := w.wbuf1.ptr()
   155		if wbuf == nil {
   156			w.init()
   157			wbuf = w.wbuf1.ptr()
   158			// wbuf is empty at this point.
   159		}
   160		if wbuf.nobj == 0 {
   161			w.wbuf1, w.wbuf2 = w.wbuf2, w.wbuf1
   162			wbuf = w.wbuf1.ptr()
   163			if wbuf.nobj == 0 {
   164				owbuf := wbuf
   165				wbuf = trygetfull()
   166				if wbuf == nil {
   167					return 0
   168				}
   169				putempty(owbuf)
   170				w.wbuf1 = wbufptrOf(wbuf)
   171			}
   172		}
   173	
   174		wbuf.nobj--
   175		return wbuf.obj[wbuf.nobj]
   176	}
   177	
   178	// tryGetFast dequeues a pointer for the garbage collector to trace
   179	// if one is readily available. Otherwise it returns 0 and
   180	// the caller is expected to call tryGet().
   181	//go:nowritebarrier
   182	func (w *gcWork) tryGetFast() uintptr {
   183		wbuf := w.wbuf1.ptr()
   184		if wbuf == nil {
   185			return 0
   186		}
   187		if wbuf.nobj == 0 {
   188			return 0
   189		}
   190	
   191		wbuf.nobj--
   192		return wbuf.obj[wbuf.nobj]
   193	}
   194	
   195	// get dequeues a pointer for the garbage collector to trace, blocking
   196	// if necessary to ensure all pointers from all queues and caches have
   197	// been retrieved.  get returns 0 if there are no pointers remaining.
   198	//go:nowritebarrier
   199	func (w *gcWork) get() uintptr {
   200		wbuf := w.wbuf1.ptr()
   201		if wbuf == nil {
   202			w.init()
   203			wbuf = w.wbuf1.ptr()
   204			// wbuf is empty at this point.
   205		}
   206		if wbuf.nobj == 0 {
   207			w.wbuf1, w.wbuf2 = w.wbuf2, w.wbuf1
   208			wbuf = w.wbuf1.ptr()
   209			if wbuf.nobj == 0 {
   210				owbuf := wbuf
   211				wbuf = getfull()
   212				if wbuf == nil {
   213					return 0
   214				}
   215				putempty(owbuf)
   216				w.wbuf1 = wbufptrOf(wbuf)
   217			}
   218		}
   219	
   220		// TODO: This might be a good place to add prefetch code
   221	
   222		wbuf.nobj--
   223		return wbuf.obj[wbuf.nobj]
   224	}
   225	
   226	// dispose returns any cached pointers to the global queue.
   227	// The buffers are being put on the full queue so that the
   228	// write barriers will not simply reacquire them before the
   229	// GC can inspect them. This helps reduce the mutator's
   230	// ability to hide pointers during the concurrent mark phase.
   231	//
   232	//go:nowritebarrier
   233	func (w *gcWork) dispose() {
   234		if wbuf := w.wbuf1.ptr(); wbuf != nil {
   235			if wbuf.nobj == 0 {
   236				putempty(wbuf)
   237			} else {
   238				putfull(wbuf)
   239			}
   240			w.wbuf1 = 0
   241	
   242			wbuf = w.wbuf2.ptr()
   243			if wbuf.nobj == 0 {
   244				putempty(wbuf)
   245			} else {
   246				putfull(wbuf)
   247			}
   248			w.wbuf2 = 0
   249		}
   250		if w.bytesMarked != 0 {
   251			// dispose happens relatively infrequently. If this
   252			// atomic becomes a problem, we should first try to
   253			// dispose less and if necessary aggregate in a per-P
   254			// counter.
   255			atomic.Xadd64(&work.bytesMarked, int64(w.bytesMarked))
   256			w.bytesMarked = 0
   257		}
   258		if w.scanWork != 0 {
   259			atomic.Xaddint64(&gcController.scanWork, w.scanWork)
   260			w.scanWork = 0
   261		}
   262	}
   263	
   264	// balance moves some work that's cached in this gcWork back on the
   265	// global queue.
   266	//go:nowritebarrier
   267	func (w *gcWork) balance() {
   268		if w.wbuf1 == 0 {
   269			return
   270		}
   271		if wbuf := w.wbuf2.ptr(); wbuf.nobj != 0 {
   272			putfull(wbuf)
   273			w.wbuf2 = wbufptrOf(getempty())
   274		} else if wbuf := w.wbuf1.ptr(); wbuf.nobj > 4 {
   275			w.wbuf1 = wbufptrOf(handoff(wbuf))
   276		} else {
   277			return
   278		}
   279		// We flushed a buffer to the full list, so wake a worker.
   280		if gcphase == _GCmark {
   281			gcController.enlistWorker()
   282		}
   283	}
   284	
   285	// empty returns true if w has no mark work available.
   286	//go:nowritebarrier
   287	func (w *gcWork) empty() bool {
   288		return w.wbuf1 == 0 || (w.wbuf1.ptr().nobj == 0 && w.wbuf2.ptr().nobj == 0)
   289	}
   290	
   291	// Internally, the GC work pool is kept in arrays in work buffers.
   292	// The gcWork interface caches a work buffer until full (or empty) to
   293	// avoid contending on the global work buffer lists.
   294	
   295	type workbufhdr struct {
   296		node lfnode // must be first
   297		nobj int
   298	}
   299	
   300	//go:notinheap
   301	type workbuf struct {
   302		workbufhdr
   303		// account for the above fields
   304		obj [(_WorkbufSize - unsafe.Sizeof(workbufhdr{})) / sys.PtrSize]uintptr
   305	}
   306	
   307	// workbuf factory routines. These funcs are used to manage the
   308	// workbufs.
   309	// If the GC asks for some work these are the only routines that
   310	// make wbufs available to the GC.
   311	
   312	func (b *workbuf) checknonempty() {
   313		if b.nobj == 0 {
   314			throw("workbuf is empty")
   315		}
   316	}
   317	
   318	func (b *workbuf) checkempty() {
   319		if b.nobj != 0 {
   320			throw("workbuf is not empty")
   321		}
   322	}
   323	
   324	// getempty pops an empty work buffer off the work.empty list,
   325	// allocating new buffers if none are available.
   326	//go:nowritebarrier
   327	func getempty() *workbuf {
   328		var b *workbuf
   329		if work.empty != 0 {
   330			b = (*workbuf)(lfstackpop(&work.empty))
   331			if b != nil {
   332				b.checkempty()
   333			}
   334		}
   335		if b == nil {
   336			b = (*workbuf)(persistentalloc(unsafe.Sizeof(*b), sys.CacheLineSize, &memstats.gc_sys))
   337		}
   338		return b
   339	}
   340	
   341	// putempty puts a workbuf onto the work.empty list.
   342	// Upon entry this go routine owns b. The lfstackpush relinquishes ownership.
   343	//go:nowritebarrier
   344	func putempty(b *workbuf) {
   345		b.checkempty()
   346		lfstackpush(&work.empty, &b.node)
   347	}
   348	
   349	// putfull puts the workbuf on the work.full list for the GC.
   350	// putfull accepts partially full buffers so the GC can avoid competing
   351	// with the mutators for ownership of partially full buffers.
   352	//go:nowritebarrier
   353	func putfull(b *workbuf) {
   354		b.checknonempty()
   355		lfstackpush(&work.full, &b.node)
   356	}
   357	
   358	// trygetfull tries to get a full or partially empty workbuffer.
   359	// If one is not immediately available return nil
   360	//go:nowritebarrier
   361	func trygetfull() *workbuf {
   362		b := (*workbuf)(lfstackpop(&work.full))
   363		if b != nil {
   364			b.checknonempty()
   365			return b
   366		}
   367		return b
   368	}
   369	
   370	// Get a full work buffer off the work.full list.
   371	// If nothing is available wait until all the other gc helpers have
   372	// finished and then return nil.
   373	// getfull acts as a barrier for work.nproc helpers. As long as one
   374	// gchelper is actively marking objects it
   375	// may create a workbuffer that the other helpers can work on.
   376	// The for loop either exits when a work buffer is found
   377	// or when _all_ of the work.nproc GC helpers are in the loop
   378	// looking for work and thus not capable of creating new work.
   379	// This is in fact the termination condition for the STW mark
   380	// phase.
   381	//go:nowritebarrier
   382	func getfull() *workbuf {
   383		b := (*workbuf)(lfstackpop(&work.full))
   384		if b != nil {
   385			b.checknonempty()
   386			return b
   387		}
   388	
   389		incnwait := atomic.Xadd(&work.nwait, +1)
   390		if incnwait > work.nproc {
   391			println("runtime: work.nwait=", incnwait, "work.nproc=", work.nproc)
   392			throw("work.nwait > work.nproc")
   393		}
   394		for i := 0; ; i++ {
   395			if work.full != 0 {
   396				decnwait := atomic.Xadd(&work.nwait, -1)
   397				if decnwait == work.nproc {
   398					println("runtime: work.nwait=", decnwait, "work.nproc=", work.nproc)
   399					throw("work.nwait > work.nproc")
   400				}
   401				b = (*workbuf)(lfstackpop(&work.full))
   402				if b != nil {
   403					b.checknonempty()
   404					return b
   405				}
   406				incnwait := atomic.Xadd(&work.nwait, +1)
   407				if incnwait > work.nproc {
   408					println("runtime: work.nwait=", incnwait, "work.nproc=", work.nproc)
   409					throw("work.nwait > work.nproc")
   410				}
   411			}
   412			if work.nwait == work.nproc && work.markrootNext >= work.markrootJobs {
   413				return nil
   414			}
   415			_g_ := getg()
   416			if i < 10 {
   417				_g_.m.gcstats.nprocyield++
   418				procyield(20)
   419			} else if i < 20 {
   420				_g_.m.gcstats.nosyield++
   421				osyield()
   422			} else {
   423				_g_.m.gcstats.nsleep++
   424				usleep(100)
   425			}
   426		}
   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		_g_ := getg()
   438		_g_.m.gcstats.nhandoff++
   439		_g_.m.gcstats.nhandoffcnt += uint64(n)
   440	
   441		// Put b on full list - let first half of b get stolen.
   442		putfull(b)
   443		return b1
   444	}
   445	

View as plain text