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.
8 "runtime/internal/atomic"
14 _Debugwbufs = false // if true check wbufs consistency
15 _WorkbufSize = 2048 // in bytes; larger values result in less contention
18 // Garbage collector work pool abstraction.
20 // This implements a producer/consumer model for pointers to grey
21 // objects. A grey object is one that is marked and on a work
22 // queue. A black object is marked and not on a work queue.
24 // Write barriers, root discovery, stack scanning, and object scanning
25 // produce pointers to grey objects. Scanning consumes pointers to
26 // grey objects, thus blackening them, and then scans them,
27 // potentially producing new pointers to grey objects.
29 // A wbufptr holds a workbuf*, but protects it from write barriers.
30 // workbufs never live on the heap, so write barriers are unnecessary.
31 // Write barriers on workbuf pointers may also be dangerous in the GC.
34 func wbufptrOf(w *workbuf) wbufptr {
35 return wbufptr(unsafe.Pointer(w))
38 func (wp wbufptr) ptr() *workbuf {
39 return (*workbuf)(unsafe.Pointer(wp))
42 // A gcWork provides the interface to produce and consume work for the
45 // A gcWork can be used on the stack as follows:
49 // .. call gcw.put() to produce and gcw.get() to consume ..
53 // Or from the per-P gcWork cache:
55 // (preemption must be disabled)
56 // gcw := &getg().m.p.ptr().gcw
57 // .. call gcw.put() to produce and gcw.get() to consume ..
58 // if gcBlackenPromptly {
62 // It's important that any use of gcWork during the mark phase prevent
63 // the garbage collector from transitioning to mark termination since
64 // gcWork may locally hold GC work buffers. This can be done by
65 // disabling preemption (systemstack or acquirem).
67 // wbuf1 and wbuf2 are the primary and secondary work buffers.
69 // This can be thought of as a stack of both work buffers'
70 // pointers concatenated. When we pop the last pointer, we
71 // shift the stack up by one work buffer by bringing in a new
72 // full buffer and discarding an empty one. When we fill both
73 // buffers, we shift the stack down by one work buffer by
74 // bringing in a new empty buffer and discarding a full one.
75 // This way we have one buffer's worth of hysteresis, which
76 // amortizes the cost of getting or putting a work buffer over
77 // at least one buffer of work and reduces contention on the
80 // wbuf1 is always the buffer we're currently pushing to and
81 // popping from and wbuf2 is the buffer that will be discarded
84 // Invariant: Both wbuf1 and wbuf2 are nil or neither are.
87 // Bytes marked (blackened) on this gcWork. This is aggregated
88 // into work.bytesMarked by dispose.
91 // Scan work performed on this gcWork. This is aggregated into
92 // gcController by dispose and may also be flushed by callers.
96 func (w *gcWork) init() {
97 w.wbuf1 = wbufptrOf(getempty(101))
98 wbuf2 := trygetfull(102)
100 wbuf2 = getempty(103)
102 w.wbuf2 = wbufptrOf(wbuf2)
105 // put enqueues a pointer for the garbage collector to trace.
106 // obj must point to the beginning of a heap object.
108 func (ww *gcWork) put(obj uintptr) {
109 w := (*gcWork)(noescape(unsafe.Pointer(ww))) // TODO: remove when escape analysis is fixed
111 wbuf := w.wbuf1.ptr()
115 // wbuf is empty at this point.
116 } else if wbuf.nobj == len(wbuf.obj) {
117 w.wbuf1, w.wbuf2 = w.wbuf2, w.wbuf1
119 if wbuf.nobj == len(wbuf.obj) {
122 w.wbuf1 = wbufptrOf(wbuf)
126 wbuf.obj[wbuf.nobj] = obj
130 // tryGet dequeues a pointer for the garbage collector to trace.
132 // If there are no pointers remaining in this gcWork or in the global
133 // queue, tryGet returns 0. Note that there may still be pointers in
134 // other gcWork instances or other caches.
136 func (ww *gcWork) tryGet() uintptr {
137 w := (*gcWork)(noescape(unsafe.Pointer(ww))) // TODO: remove when escape analysis is fixed
139 wbuf := w.wbuf1.ptr()
143 // wbuf is empty at this point.
146 w.wbuf1, w.wbuf2 = w.wbuf2, w.wbuf1
150 wbuf = trygetfull(167)
155 w.wbuf1 = wbufptrOf(wbuf)
160 return wbuf.obj[wbuf.nobj]
163 // get dequeues a pointer for the garbage collector to trace, blocking
164 // if necessary to ensure all pointers from all queues and caches have
165 // been retrieved. get returns 0 if there are no pointers remaining.
167 func (ww *gcWork) get() uintptr {
168 w := (*gcWork)(noescape(unsafe.Pointer(ww))) // TODO: remove when escape analysis is fixed
170 wbuf := w.wbuf1.ptr()
174 // wbuf is empty at this point.
177 w.wbuf1, w.wbuf2 = w.wbuf2, w.wbuf1
186 w.wbuf1 = wbufptrOf(wbuf)
190 // TODO: This might be a good place to add prefetch code
193 return wbuf.obj[wbuf.nobj]
196 // dispose returns any cached pointers to the global queue.
197 // The buffers are being put on the full queue so that the
198 // write barriers will not simply reacquire them before the
199 // GC can inspect them. This helps reduce the mutator's
200 // ability to hide pointers during the concurrent mark phase.
203 func (w *gcWork) dispose() {
204 if wbuf := w.wbuf1.ptr(); wbuf != nil {
220 if w.bytesMarked != 0 {
221 // dispose happens relatively infrequently. If this
222 // atomic becomes a problem, we should first try to
223 // dispose less and if necessary aggregate in a per-P
225 atomic.Xadd64(&work.bytesMarked, int64(w.bytesMarked))
229 atomic.Xaddint64(&gcController.scanWork, w.scanWork)
234 // balance moves some work that's cached in this gcWork back on the
237 func (w *gcWork) balance() {
241 if wbuf := w.wbuf2.ptr(); wbuf.nobj != 0 {
243 w.wbuf2 = wbufptrOf(getempty(247))
244 } else if wbuf := w.wbuf1.ptr(); wbuf.nobj > 4 {
245 w.wbuf1 = wbufptrOf(handoff(wbuf))
249 // empty returns true if w has no mark work available.
251 func (w *gcWork) empty() bool {
252 return w.wbuf1 == 0 || (w.wbuf1.ptr().nobj == 0 && w.wbuf2.ptr().nobj == 0)
255 // Internally, the GC work pool is kept in arrays in work buffers.
256 // The gcWork interface caches a work buffer until full (or empty) to
257 // avoid contending on the global work buffer lists.
259 type workbufhdr struct {
260 node lfnode // must be first
262 inuse bool // This workbuf is in use by some gorotuine and is not on the work.empty/full queues.
263 log [4]int // line numbers forming a history of ownership changes to workbuf
266 type workbuf struct {
268 // account for the above fields
269 obj [(_WorkbufSize - unsafe.Sizeof(workbufhdr{})) / sys.PtrSize]uintptr
272 // workbuf factory routines. These funcs are used to manage the
274 // If the GC asks for some work these are the only routines that
275 // make wbufs available to the GC.
276 // Each of the gets and puts also take an distinct integer that is used
277 // to record a brief history of changes to ownership of the workbuf.
278 // The convention is to use a unique line number but any encoding
279 // is permissible. For example if you want to pass in 2 bits of information
280 // you could simple add lineno1*100000+lineno2.
282 // logget records the past few values of entry to aid in debugging.
283 // logget checks the buffer b is not currently in use.
284 func (b *workbuf) logget(entry int) {
289 println("runtime: logget fails log entry=", entry,
290 "b.log[0]=", b.log[0], "b.log[1]=", b.log[1],
291 "b.log[2]=", b.log[2], "b.log[3]=", b.log[3])
292 throw("logget: get not legal")
295 copy(b.log[1:], b.log[:])
299 // logput records the past few values of entry to aid in debugging.
300 // logput checks the buffer b is currently in use.
301 func (b *workbuf) logput(entry int) {
306 println("runtime: logput fails log entry=", entry,
307 "b.log[0]=", b.log[0], "b.log[1]=", b.log[1],
308 "b.log[2]=", b.log[2], "b.log[3]=", b.log[3])
309 throw("logput: put not legal")
312 copy(b.log[1:], b.log[:])
316 func (b *workbuf) checknonempty() {
318 println("runtime: nonempty check fails",
319 "b.log[0]=", b.log[0], "b.log[1]=", b.log[1],
320 "b.log[2]=", b.log[2], "b.log[3]=", b.log[3])
321 throw("workbuf is empty")
325 func (b *workbuf) checkempty() {
327 println("runtime: empty check fails",
328 "b.log[0]=", b.log[0], "b.log[1]=", b.log[1],
329 "b.log[2]=", b.log[2], "b.log[3]=", b.log[3])
330 throw("workbuf is not empty")
334 // getempty pops an empty work buffer off the work.empty list,
335 // allocating new buffers if none are available.
336 // entry is used to record a brief history of ownership.
338 func getempty(entry int) *workbuf {
341 b = (*workbuf)(lfstackpop(&work.empty))
347 b = (*workbuf)(persistentalloc(unsafe.Sizeof(*b), sys.CacheLineSize, &memstats.gc_sys))
353 // putempty puts a workbuf onto the work.empty list.
354 // Upon entry this go routine owns b. The lfstackpush relinquishes ownership.
356 func putempty(b *workbuf, entry int) {
359 lfstackpush(&work.empty, &b.node)
362 // putfull puts the workbuf on the work.full list for the GC.
363 // putfull accepts partially full buffers so the GC can avoid competing
364 // with the mutators for ownership of partially full buffers.
366 func putfull(b *workbuf, entry int) {
369 lfstackpush(&work.full, &b.node)
371 // We just made more work available. Let the GC controller
372 // know so it can encourage more workers to run.
373 if gcphase == _GCmark {
374 gcController.enlistWorker()
378 // trygetfull tries to get a full or partially empty workbuffer.
379 // If one is not immediately available return nil
381 func trygetfull(entry int) *workbuf {
382 b := (*workbuf)(lfstackpop(&work.full))
391 // Get a full work buffer off the work.full list.
392 // If nothing is available wait until all the other gc helpers have
393 // finished and then return nil.
394 // getfull acts as a barrier for work.nproc helpers. As long as one
395 // gchelper is actively marking objects it
396 // may create a workbuffer that the other helpers can work on.
397 // The for loop either exits when a work buffer is found
398 // or when _all_ of the work.nproc GC helpers are in the loop
399 // looking for work and thus not capable of creating new work.
400 // This is in fact the termination condition for the STW mark
403 func getfull(entry int) *workbuf {
404 b := (*workbuf)(lfstackpop(&work.full))
411 incnwait := atomic.Xadd(&work.nwait, +1)
412 if incnwait > work.nproc {
413 println("runtime: work.nwait=", incnwait, "work.nproc=", work.nproc)
414 throw("work.nwait > work.nproc")
418 decnwait := atomic.Xadd(&work.nwait, -1)
419 if decnwait == work.nproc {
420 println("runtime: work.nwait=", decnwait, "work.nproc=", work.nproc)
421 throw("work.nwait > work.nproc")
423 b = (*workbuf)(lfstackpop(&work.full))
429 incnwait := atomic.Xadd(&work.nwait, +1)
430 if incnwait > work.nproc {
431 println("runtime: work.nwait=", incnwait, "work.nproc=", work.nproc)
432 throw("work.nwait > work.nproc")
435 if work.nwait == work.nproc && work.markrootNext >= work.markrootJobs {
440 _g_.m.gcstats.nprocyield++
443 _g_.m.gcstats.nosyield++
446 _g_.m.gcstats.nsleep++
453 func handoff(b *workbuf) *workbuf {
454 // Make new buffer with half of b's pointers.
459 memmove(unsafe.Pointer(&b1.obj[0]), unsafe.Pointer(&b.obj[b.nobj]), uintptr(n)*unsafe.Sizeof(b1.obj[0]))
461 _g_.m.gcstats.nhandoff++
462 _g_.m.gcstats.nhandoffcnt += uint64(n)
464 // Put b on full list - let first half of b get stolen.