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.
5 // TODO(rsc): The code having to do with the heap bitmap needs very serious cleanup.
6 // It has gotten completely out of control.
8 // Garbage collector (GC).
10 // The GC runs concurrently with mutator threads, is type accurate (aka precise), allows multiple
11 // GC thread to run in parallel. It is a concurrent mark and sweep that uses a write barrier. It is
12 // non-generational and non-compacting. Allocation is done using size segregated per P allocation
13 // areas to minimize fragmentation while eliminating locks in the common case.
15 // The algorithm decomposes into several steps.
16 // This is a high level description of the algorithm being used. For an overview of GC a good
17 // place to start is Richard Jones' gchandbook.org.
19 // The algorithm's intellectual heritage includes Dijkstra's on-the-fly algorithm, see
20 // Edsger W. Dijkstra, Leslie Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens. 1978.
21 // On-the-fly garbage collection: an exercise in cooperation. Commun. ACM 21, 11 (November 1978),
23 // For journal quality proofs that these steps are complete, correct, and terminate see
24 // Hudson, R., and Moss, J.E.B. Copying Garbage Collection without stopping the world.
25 // Concurrency and Computation: Practice and Experience 15(3-5), 2003.
27 // 0. Set phase = GCscan from GCoff.
28 // 1. Wait for all P's to acknowledge phase change.
29 // At this point all goroutines have passed through a GC safepoint and
30 // know we are in the GCscan phase.
31 // 2. GC scans all goroutine stacks, mark and enqueues all encountered pointers
32 // (marking avoids most duplicate enqueuing but races may produce benign duplication).
33 // Preempted goroutines are scanned before P schedules next goroutine.
34 // 3. Set phase = GCmark.
35 // 4. Wait for all P's to acknowledge phase change.
36 // 5. Now write barrier marks and enqueues black, grey, or white to white pointers.
37 // Malloc still allocates white (non-marked) objects.
38 // 6. Meanwhile GC transitively walks the heap marking reachable objects.
39 // 7. When GC finishes marking heap, it preempts P's one-by-one and
40 // retakes partial wbufs (filled by write barrier or during a stack scan of the goroutine
41 // currently scheduled on the P).
42 // 8. Once the GC has exhausted all available marking work it sets phase = marktermination.
43 // 9. Wait for all P's to acknowledge phase change.
44 // 10. Malloc now allocates black objects, so number of unmarked reachable objects
45 // monotonically decreases.
46 // 11. GC preempts P's one-by-one taking partial wbufs and marks all unmarked yet
48 // 12. When GC completes a full cycle over P's and discovers no new grey
49 // objects, (which means all reachable objects are marked) set phase = GCoff.
50 // 13. Wait for all P's to acknowledge phase change.
51 // 14. Now malloc allocates white (but sweeps spans before use).
52 // Write barrier becomes nop.
53 // 15. GC does background sweeping, see description below.
54 // 16. When sufficient allocation has taken place replay the sequence starting at 0 above,
55 // see discussion of GC rate below.
58 // Phases are changed by setting the gcphase to the next phase and possibly calling ackgcphase.
59 // All phase action must be benign in the presence of a change.
60 // Starting with GCoff
62 // GSscan scans stacks and globals greying them and never marks an object black.
63 // Once all the P's are aware of the new phase they will scan gs on preemption.
64 // This means that the scanning of preempted gs can't start until all the Ps
66 // When a stack is scanned, this phase also installs stack barriers to
67 // track how much of the stack has been active.
68 // This transition enables write barriers because stack barriers
69 // assume that writes to higher frames will be tracked by write
70 // barriers. Technically this only needs write barriers for writes
71 // to stack slots, but we enable write barriers in general.
73 // In GCmark, work buffers are drained until there are no more
75 // No scanning of objects (making them black) can happen until all
76 // Ps have enabled the write barrier, but that already happened in
77 // the transition to GCscan.
78 // GCmark to GCmarktermination
79 // The only change here is that we start allocating black so the Ps must acknowledge
80 // the change before we begin the termination algorithm
81 // GCmarktermination to GSsweep
82 // Object currently on the freelist must be marked black for this to work.
83 // Are things on the free lists black or white? How does the sweep phase work?
87 // The sweep phase proceeds concurrently with normal program execution.
88 // The heap is swept span-by-span both lazily (when a goroutine needs another span)
89 // and concurrently in a background goroutine (this helps programs that are not CPU bound).
90 // At the end of STW mark termination all spans are marked as "needs sweeping".
92 // The background sweeper goroutine simply sweeps spans one-by-one.
94 // To avoid requesting more OS memory while there are unswept spans, when a
95 // goroutine needs another span, it first attempts to reclaim that much memory
96 // by sweeping. When a goroutine needs to allocate a new small-object span, it
97 // sweeps small-object spans for the same object size until it frees at least
98 // one object. When a goroutine needs to allocate large-object span from heap,
99 // it sweeps spans until it frees at least that many pages into heap. There is
100 // one case where this may not suffice: if a goroutine sweeps and frees two
101 // nonadjacent one-page spans to the heap, it will allocate a new two-page
102 // span, but there can still be other one-page unswept spans which could be
103 // combined into a two-page span.
105 // It's critical to ensure that no operations proceed on unswept spans (that would corrupt
106 // mark bits in GC bitmap). During GC all mcaches are flushed into the central cache,
107 // so they are empty. When a goroutine grabs a new span into mcache, it sweeps it.
108 // When a goroutine explicitly frees an object or sets a finalizer, it ensures that
109 // the span is swept (either by sweeping it, or by waiting for the concurrent sweep to finish).
110 // The finalizer goroutine is kicked off only when all spans are swept.
111 // When the next GC starts, it sweeps all not-yet-swept spans (if any).
114 // Next GC is after we've allocated an extra amount of memory proportional to
115 // the amount already in use. The proportion is controlled by GOGC environment variable
116 // (100 by default). If GOGC=100 and we're using 4M, we'll GC again when we get to 8M
117 // (this mark is tracked in next_gc variable). This keeps the GC cost in linear
118 // proportion to the allocation cost. Adjusting GOGC just changes the linear constant
119 // (and also the amount of extra memory used).
124 "runtime/internal/atomic"
125 "runtime/internal/sys"
131 _ConcurrentSweep = true
132 _FinBlockSize = 4 * 1024
134 // sweepMinHeapDistance is a lower bound on the heap distance
135 // (in bytes) reserved for concurrent sweeping between GC
136 // cycles. This will be scaled by gcpercent/100.
137 sweepMinHeapDistance = 1024 * 1024
140 // heapminimum is the minimum heap size at which to trigger GC.
141 // For small heaps, this overrides the usual GOGC*live set rule.
143 // When there is a very small live set but a lot of allocation, simply
144 // collecting when the heap reaches GOGC*live results in many GC
145 // cycles and high total per-GC overhead. This minimum amortizes this
146 // per-GC overhead while keeping the heap reasonably small.
148 // During initialization this is set to 4MB*GOGC/100. In the case of
149 // GOGC==0, this will set heapminimum to 0, resulting in constant
150 // collection even when the heap size is small, which is useful for
152 var heapminimum uint64 = defaultHeapMinimum
154 // defaultHeapMinimum is the value of heapminimum for GOGC==100.
155 const defaultHeapMinimum = 4 << 20
157 // Initialized from $GOGC. GOGC=off means no GC.
161 if unsafe.Sizeof(workbuf{}) != _WorkbufSize {
162 throw("size of Workbuf is suboptimal")
165 _ = setGCPercent(readgogc())
166 for datap := &firstmoduledata; datap != nil; datap = datap.next {
167 datap.gcdatamask = progToPointerMask((*byte)(unsafe.Pointer(datap.gcdata)), datap.edata-datap.data)
168 datap.gcbssmask = progToPointerMask((*byte)(unsafe.Pointer(datap.gcbss)), datap.ebss-datap.bss)
170 memstats.next_gc = heapminimum
172 work.markDoneSema = 1
175 func readgogc() int32 {
176 p := gogetenv("GOGC")
183 return int32(atoi(p))
186 // gcenable is called after the bulk of the runtime initialization,
187 // just before we're about to start letting user code run.
188 // It kicks off the background sweeper goroutine and enables GC.
190 c := make(chan int, 1)
193 memstats.enablegc = true // now that runtime is initialized, GC is okay
196 //go:linkname setGCPercent runtime/debug.setGCPercent
197 func setGCPercent(in int32) (out int32) {
204 heapminimum = defaultHeapMinimum * uint64(gcpercent) / 100
205 if gcController.triggerRatio > float64(gcpercent)/100 {
206 gcController.triggerRatio = float64(gcpercent) / 100
212 // Garbage collector phase.
213 // Indicates to write barrier and sychronization task to preform.
216 // The compiler knows about this variable.
217 // If you change it, you must change the compiler too.
218 var writeBarrier struct {
219 enabled bool // compiler emits a check of this before calling write barrier
220 needed bool // whether we need a write barrier for current GC phase
221 cgo bool // whether we need a write barrier for a cgo check
222 alignme uint64 // guarantee alignment so that compiler can use a 32 or 64-bit load
225 // gcBlackenEnabled is 1 if mutator assists and background mark
226 // workers are allowed to blacken objects. This must only be set when
227 // gcphase == _GCmark.
228 var gcBlackenEnabled uint32
230 // gcBlackenPromptly indicates that optimizations that may
231 // hide work from the global work queue should be disabled.
233 // If gcBlackenPromptly is true, per-P gcWork caches should
234 // be flushed immediately and new objects should be allocated black.
236 // There is a tension between allocating objects white and
237 // allocating them black. If white and the objects die before being
238 // marked they can be collected during this GC cycle. On the other
239 // hand allocating them black will reduce _GCmarktermination latency
240 // since more work is done in the mark phase. This tension is resolved
241 // by allocating white until the mark phase is approaching its end and
242 // then allocating black for the remainder of the mark phase.
243 var gcBlackenPromptly bool
246 _GCoff = iota // GC not running; sweeping in background, write barrier disabled
247 _GCmark // GC marking roots and workbufs, write barrier ENABLED
248 _GCmarktermination // GC mark termination: allocate black, P's help GC, write barrier ENABLED
252 func setGCPhase(x uint32) {
253 atomic.Store(&gcphase, x)
254 writeBarrier.needed = gcphase == _GCmark || gcphase == _GCmarktermination
255 writeBarrier.enabled = writeBarrier.needed || writeBarrier.cgo
258 // gcMarkWorkerMode represents the mode that a concurrent mark worker
259 // should operate in.
261 // Concurrent marking happens through four different mechanisms. One
262 // is mutator assists, which happen in response to allocations and are
263 // not scheduled. The other three are variations in the per-P mark
264 // workers and are distinguished by gcMarkWorkerMode.
265 type gcMarkWorkerMode int
268 // gcMarkWorkerDedicatedMode indicates that the P of a mark
269 // worker is dedicated to running that mark worker. The mark
270 // worker should run without preemption.
271 gcMarkWorkerDedicatedMode gcMarkWorkerMode = iota
273 // gcMarkWorkerFractionalMode indicates that a P is currently
274 // running the "fractional" mark worker. The fractional worker
275 // is necessary when GOMAXPROCS*gcGoalUtilization is not an
276 // integer. The fractional worker should run until it is
277 // preempted and will be scheduled to pick up the fractional
278 // part of GOMAXPROCS*gcGoalUtilization.
279 gcMarkWorkerFractionalMode
281 // gcMarkWorkerIdleMode indicates that a P is running the mark
282 // worker because it has nothing else to do. The idle worker
283 // should run until it is preempted and account its time
284 // against gcController.idleMarkTime.
288 // gcController implements the GC pacing controller that determines
289 // when to trigger concurrent garbage collection and how much marking
290 // work to do in mutator assists and background marking.
292 // It uses a feedback control algorithm to adjust the memstats.next_gc
293 // trigger based on the heap growth and GC CPU utilization each cycle.
294 // This algorithm optimizes for heap growth to match GOGC and for CPU
295 // utilization between assist and background marking to be 25% of
296 // GOMAXPROCS. The high-level design of this algorithm is documented
297 // at https://golang.org/s/go15gcpacing.
298 var gcController = gcControllerState{
299 // Initial trigger ratio guess.
300 triggerRatio: 7 / 8.0,
303 type gcControllerState struct {
304 // scanWork is the total scan work performed this cycle. This
305 // is updated atomically during the cycle. Updates occur in
306 // bounded batches, since it is both written and read
307 // throughout the cycle.
309 // Currently this is the bytes of heap scanned. For most uses,
310 // this is an opaque unit of work, but for estimation the
311 // definition is important.
314 // bgScanCredit is the scan work credit accumulated by the
315 // concurrent background scan. This credit is accumulated by
316 // the background scan and stolen by mutator assists. This is
317 // updated atomically. Updates occur in bounded batches, since
318 // it is both written and read throughout the cycle.
321 // assistTime is the nanoseconds spent in mutator assists
322 // during this cycle. This is updated atomically. Updates
323 // occur in bounded batches, since it is both written and read
324 // throughout the cycle.
327 // dedicatedMarkTime is the nanoseconds spent in dedicated
328 // mark workers during this cycle. This is updated atomically
329 // at the end of the concurrent mark phase.
330 dedicatedMarkTime int64
332 // fractionalMarkTime is the nanoseconds spent in the
333 // fractional mark worker during this cycle. This is updated
334 // atomically throughout the cycle and will be up-to-date if
335 // the fractional mark worker is not currently running.
336 fractionalMarkTime int64
338 // idleMarkTime is the nanoseconds spent in idle marking
339 // during this cycle. This is updated atomically throughout
343 // bgMarkStartTime is the absolute start time in nanoseconds
344 // that the background mark phase started.
345 bgMarkStartTime int64
347 // assistTime is the absolute start time in nanoseconds that
348 // mutator assists were enabled.
349 assistStartTime int64
351 // heapGoal is the goal memstats.heap_live for when this cycle
352 // ends. This is computed at the beginning of each cycle.
355 // dedicatedMarkWorkersNeeded is the number of dedicated mark
356 // workers that need to be started. This is computed at the
357 // beginning of each cycle and decremented atomically as
358 // dedicated mark workers get started.
359 dedicatedMarkWorkersNeeded int64
361 // assistWorkPerByte is the ratio of scan work to allocated
362 // bytes that should be performed by mutator assists. This is
363 // computed at the beginning of each cycle and updated every
364 // time heap_scan is updated.
365 assistWorkPerByte float64
367 // assistBytesPerWork is 1/assistWorkPerByte.
368 assistBytesPerWork float64
370 // fractionalUtilizationGoal is the fraction of wall clock
371 // time that should be spent in the fractional mark worker.
372 // For example, if the overall mark utilization goal is 25%
373 // and GOMAXPROCS is 6, one P will be a dedicated mark worker
374 // and this will be set to 0.5 so that 50% of the time some P
375 // is in a fractional mark worker. This is computed at the
376 // beginning of each cycle.
377 fractionalUtilizationGoal float64
379 // triggerRatio is the heap growth ratio at which the garbage
380 // collection cycle should start. E.g., if this is 0.6, then
381 // GC should start when the live heap has reached 1.6 times
382 // the heap size marked by the previous cycle. This is updated
383 // at the end of of each cycle.
386 _ [sys.CacheLineSize]byte
388 // fractionalMarkWorkersNeeded is the number of fractional
389 // mark workers that need to be started. This is either 0 or
390 // 1. This is potentially updated atomically at every
391 // scheduling point (hence it gets its own cache line).
392 fractionalMarkWorkersNeeded int64
394 _ [sys.CacheLineSize]byte
397 // startCycle resets the GC controller's state and computes estimates
398 // for a new GC cycle. The caller must hold worldsema.
399 func (c *gcControllerState) startCycle() {
403 c.dedicatedMarkTime = 0
404 c.fractionalMarkTime = 0
407 // If this is the first GC cycle or we're operating on a very
408 // small heap, fake heap_marked so it looks like next_gc is
409 // the appropriate growth from heap_marked, even though the
410 // real heap_marked may not have a meaningful value (on the
411 // first cycle) or may be much smaller (resulting in a large
413 if memstats.next_gc <= heapminimum {
414 memstats.heap_marked = uint64(float64(memstats.next_gc) / (1 + c.triggerRatio))
415 memstats.heap_reachable = memstats.heap_marked
418 // Compute the heap goal for this cycle
419 c.heapGoal = memstats.heap_reachable + memstats.heap_reachable*uint64(gcpercent)/100
421 // Ensure that the heap goal is at least a little larger than
422 // the current live heap size. This may not be the case if GC
423 // start is delayed or if the allocation that pushed heap_live
424 // over next_gc is large or if the trigger is really close to
425 // GOGC. Assist is proportional to this distance, so enforce a
426 // minimum distance, even if it means going over the GOGC goal
428 if c.heapGoal < memstats.heap_live+1024*1024 {
429 c.heapGoal = memstats.heap_live + 1024*1024
432 // Compute the total mark utilization goal and divide it among
433 // dedicated and fractional workers.
434 totalUtilizationGoal := float64(gomaxprocs) * gcGoalUtilization
435 c.dedicatedMarkWorkersNeeded = int64(totalUtilizationGoal)
436 c.fractionalUtilizationGoal = totalUtilizationGoal - float64(c.dedicatedMarkWorkersNeeded)
437 if c.fractionalUtilizationGoal > 0 {
438 c.fractionalMarkWorkersNeeded = 1
440 c.fractionalMarkWorkersNeeded = 0
444 for _, p := range &allp {
451 // Compute initial values for controls that are updated
452 // throughout the cycle.
455 if debug.gcpacertrace > 0 {
456 print("pacer: assist ratio=", c.assistWorkPerByte,
457 " (scan ", memstats.heap_scan>>20, " MB in ",
458 work.initialHeapLive>>20, "->",
459 c.heapGoal>>20, " MB)",
460 " workers=", c.dedicatedMarkWorkersNeeded,
461 "+", c.fractionalMarkWorkersNeeded, "\n")
465 // revise updates the assist ratio during the GC cycle to account for
466 // improved estimates. This should be called either under STW or
467 // whenever memstats.heap_scan or memstats.heap_live is updated (with
468 // mheap_.lock held).
470 // It should only be called when gcBlackenEnabled != 0 (because this
471 // is when assists are enabled and the necessary statistics are
473 func (c *gcControllerState) revise() {
474 // Compute the expected scan work remaining.
476 // Note that the scannable heap size is likely to increase
477 // during the GC cycle. This is why it's important to revise
478 // the assist ratio throughout the cycle: if the scannable
479 // heap size increases, the assist ratio based on the initial
480 // scannable heap size may target too little scan work.
482 // This particular estimate is a strict upper bound on the
483 // possible remaining scan work for the current heap.
484 // You might consider dividing this by 2 (or by
485 // (100+GOGC)/100) to counter this over-estimation, but
486 // benchmarks show that this has almost no effect on mean
487 // mutator utilization, heap size, or assist time and it
488 // introduces the danger of under-estimating and letting the
489 // mutator outpace the garbage collector.
490 scanWorkExpected := int64(memstats.heap_scan) - c.scanWork
491 if scanWorkExpected < 1000 {
492 // We set a somewhat arbitrary lower bound on
493 // remaining scan work since if we aim a little high,
494 // we can miss by a little.
496 // We *do* need to enforce that this is at least 1,
497 // since marking is racy and double-scanning objects
498 // may legitimately make the expected scan work
500 scanWorkExpected = 1000
503 // Compute the heap distance remaining.
504 heapDistance := int64(c.heapGoal) - int64(memstats.heap_live)
505 if heapDistance <= 0 {
506 // This shouldn't happen, but if it does, avoid
507 // dividing by zero or setting the assist negative.
511 // Compute the mutator assist ratio so by the time the mutator
512 // allocates the remaining heap bytes up to next_gc, it will
513 // have done (or stolen) the remaining amount of scan work.
514 c.assistWorkPerByte = float64(scanWorkExpected) / float64(heapDistance)
515 c.assistBytesPerWork = float64(heapDistance) / float64(scanWorkExpected)
518 // endCycle updates the GC controller state at the end of the
519 // concurrent part of the GC cycle.
520 func (c *gcControllerState) endCycle() {
521 h_t := c.triggerRatio // For debugging
523 // Proportional response gain for the trigger controller. Must
524 // be in [0, 1]. Lower values smooth out transient effects but
525 // take longer to respond to phase changes. Higher values
526 // react to phase changes quickly, but are more affected by
527 // transient changes. Values near 1 may be unstable.
528 const triggerGain = 0.5
530 // Compute next cycle trigger ratio. First, this computes the
531 // "error" for this cycle; that is, how far off the trigger
532 // was from what it should have been, accounting for both heap
533 // growth and GC CPU utilization. We compute the actual heap
534 // growth during this cycle and scale that by how far off from
535 // the goal CPU utilization we were (to estimate the heap
536 // growth if we had the desired CPU utilization). The
537 // difference between this estimate and the GOGC-based goal
538 // heap growth is the error.
540 // TODO(austin): next_gc is based on heap_reachable, not
541 // heap_marked, which means the actual growth ratio
542 // technically isn't comparable to the trigger ratio.
543 goalGrowthRatio := float64(gcpercent) / 100
544 actualGrowthRatio := float64(memstats.heap_live)/float64(memstats.heap_marked) - 1
545 assistDuration := nanotime() - c.assistStartTime
547 // Assume background mark hit its utilization goal.
548 utilization := gcGoalUtilization
549 // Add assist utilization; avoid divide by zero.
550 if assistDuration > 0 {
551 utilization += float64(c.assistTime) / float64(assistDuration*int64(gomaxprocs))
554 triggerError := goalGrowthRatio - c.triggerRatio - utilization/gcGoalUtilization*(actualGrowthRatio-c.triggerRatio)
556 // Finally, we adjust the trigger for next time by this error,
557 // damped by the proportional gain.
558 c.triggerRatio += triggerGain * triggerError
559 if c.triggerRatio < 0 {
560 // This can happen if the mutator is allocating very
561 // quickly or the GC is scanning very slowly.
563 } else if c.triggerRatio > goalGrowthRatio*0.95 {
564 // Ensure there's always a little margin so that the
565 // mutator assist ratio isn't infinity.
566 c.triggerRatio = goalGrowthRatio * 0.95
569 if debug.gcpacertrace > 0 {
570 // Print controller state in terms of the design
572 H_m_prev := memstats.heap_marked
573 H_T := memstats.next_gc
574 h_a := actualGrowthRatio
575 H_a := memstats.heap_live
576 h_g := goalGrowthRatio
577 H_g := int64(float64(H_m_prev) * (1 + h_g))
579 u_g := gcGoalUtilization
581 print("pacer: H_m_prev=", H_m_prev,
582 " h_t=", h_t, " H_T=", H_T,
583 " h_a=", h_a, " H_a=", H_a,
584 " h_g=", h_g, " H_g=", H_g,
585 " u_a=", u_a, " u_g=", u_g,
587 " goalΔ=", goalGrowthRatio-h_t,
588 " actualΔ=", h_a-h_t,
589 " u_a/u_g=", u_a/u_g,
594 // enlistWorker encourages another dedicated mark worker to start on
595 // another P if there are spare worker slots. It is used by putfull
596 // when more work is made available.
599 func (c *gcControllerState) enlistWorker() {
600 if c.dedicatedMarkWorkersNeeded <= 0 {
603 // Pick a random other P to preempt.
608 if gp == nil || gp.m == nil || gp.m.p == 0 {
611 myID := gp.m.p.ptr().id
612 for tries := 0; tries < 5; tries++ {
613 id := int32(fastrand1() % uint32(gomaxprocs-1))
618 if p.status != _Prunning {
627 // findRunnableGCWorker returns the background mark worker for _p_ if it
628 // should be run. This must only be called when gcBlackenEnabled != 0.
629 func (c *gcControllerState) findRunnableGCWorker(_p_ *p) *g {
630 if gcBlackenEnabled == 0 {
631 throw("gcControllerState.findRunnable: blackening not enabled")
633 if _p_.gcBgMarkWorker == 0 {
634 // The mark worker associated with this P is blocked
635 // performing a mark transition. We can't run it
636 // because it may be on some other run or wait queue.
640 if !gcMarkWorkAvailable(_p_) {
641 // No work to be done right now. This can happen at
642 // the end of the mark phase when there are still
643 // assists tapering off. Don't bother running a worker
644 // now because it'll just return immediately.
648 decIfPositive := func(ptr *int64) bool {
650 if atomic.Xaddint64(ptr, -1) >= 0 {
654 atomic.Xaddint64(ptr, +1)
659 if decIfPositive(&c.dedicatedMarkWorkersNeeded) {
660 // This P is now dedicated to marking until the end of
661 // the concurrent mark phase.
662 _p_.gcMarkWorkerMode = gcMarkWorkerDedicatedMode
663 // TODO(austin): This P isn't going to run anything
664 // else for a while, so kick everything out of its run
667 if !decIfPositive(&c.fractionalMarkWorkersNeeded) {
668 // No more workers are need right now.
672 // This P has picked the token for the fractional worker.
673 // Is the GC currently under or at the utilization goal?
674 // If so, do more work.
676 // We used to check whether doing one time slice of work
677 // would remain under the utilization goal, but that has the
678 // effect of delaying work until the mutator has run for
679 // enough time slices to pay for the work. During those time
680 // slices, write barriers are enabled, so the mutator is running slower.
681 // Now instead we do the work whenever we're under or at the
682 // utilization work and pay for it by letting the mutator run later.
683 // This doesn't change the overall utilization averages, but it
684 // front loads the GC work so that the GC finishes earlier and
685 // write barriers can be turned off sooner, effectively giving
686 // the mutator a faster machine.
688 // The old, slower behavior can be restored by setting
689 // gcForcePreemptNS = forcePreemptNS.
690 const gcForcePreemptNS = 0
692 // TODO(austin): We could fast path this and basically
693 // eliminate contention on c.fractionalMarkWorkersNeeded by
694 // precomputing the minimum time at which it's worth
695 // next scheduling the fractional worker. Then Ps
696 // don't have to fight in the window where we've
697 // passed that deadline and no one has started the
700 // TODO(austin): Shorter preemption interval for mark
701 // worker to improve fairness and give this
702 // finer-grained control over schedule?
703 now := nanotime() - gcController.bgMarkStartTime
704 then := now + gcForcePreemptNS
705 timeUsed := c.fractionalMarkTime + gcForcePreemptNS
706 if then > 0 && float64(timeUsed)/float64(then) > c.fractionalUtilizationGoal {
707 // Nope, we'd overshoot the utilization goal
708 atomic.Xaddint64(&c.fractionalMarkWorkersNeeded, +1)
711 _p_.gcMarkWorkerMode = gcMarkWorkerFractionalMode
714 // Run the background mark worker
715 gp := _p_.gcBgMarkWorker.ptr()
716 casgstatus(gp, _Gwaiting, _Grunnable)
723 // gcGoalUtilization is the goal CPU utilization for background
724 // marking as a fraction of GOMAXPROCS.
725 const gcGoalUtilization = 0.25
727 // gcCreditSlack is the amount of scan work credit that can can
728 // accumulate locally before updating gcController.scanWork and,
729 // optionally, gcController.bgScanCredit. Lower values give a more
730 // accurate assist ratio and make it more likely that assists will
731 // successfully steal background credit. Higher values reduce memory
733 const gcCreditSlack = 2000
735 // gcAssistTimeSlack is the nanoseconds of mutator assist time that
736 // can accumulate on a P before updating gcController.assistTime.
737 const gcAssistTimeSlack = 5000
739 // gcOverAssistBytes determines how many extra allocation bytes of
740 // assist credit a GC assist builds up when an assist happens. This
741 // amortizes the cost of an assist by pre-paying for this many bytes
742 // of future allocations.
743 const gcOverAssistBytes = 1 << 20
746 full uint64 // lock-free list of full blocks workbuf
747 empty uint64 // lock-free list of empty blocks workbuf
748 pad0 [sys.CacheLineSize]uint8 // prevents false-sharing between full/empty and nproc/nwait
750 markrootNext uint32 // next markroot job
751 markrootJobs uint32 // number of markroot jobs
759 // Number of roots of various root types. Set by gcMarkRootPrepare.
760 nDataRoots, nBSSRoots, nSpanRoots, nStackRoots int
762 // finalizersDone indicates that finalizers and objects with
763 // finalizers have been scanned by markroot. During concurrent
764 // GC, this happens during the concurrent scan phase. During
765 // STW GC, this happens during mark termination.
768 // Each type of GC state transition is protected by a lock.
769 // Since multiple threads can simultaneously detect the state
770 // transition condition, any thread that detects a transition
771 // condition must acquire the appropriate transition lock,
772 // re-check the transition condition and return if it no
773 // longer holds or perform the transition if it does.
774 // Likewise, any transition must invalidate the transition
775 // condition before releasing the lock. This ensures that each
776 // transition is performed by exactly one thread and threads
777 // that need the transition to happen block until it has
780 // startSema protects the transition from "off" to mark or
783 // markDoneSema protects transitions from mark 1 to mark 2 and
784 // from mark 2 to mark termination.
787 bgMarkReady note // signal background mark worker has started
788 bgMarkDone uint32 // cas to 1 when at a background mark completion point
789 // Background mark completion signaling
791 // mode is the concurrency mode of the current GC cycle.
794 // Copy of mheap.allspans for marker or sweeper.
797 // totaltime is the CPU nanoseconds spent in GC since the
798 // program started if debug.gctrace > 0.
801 // bytesMarked is the number of bytes marked this cycle. This
802 // includes bytes blackened in scanned objects, noscan objects
803 // that go straight to black, and permagrey objects scanned by
804 // markroot during the concurrent scan phase. This is updated
805 // atomically during the cycle. Updates may be batched
806 // arbitrarily, since the value is only read at the end of the
809 // Because of benign races during marking, this number may not
810 // be the exact number of marked bytes, but it should be very
814 // initialHeapLive is the value of memstats.heap_live at the
815 // beginning of this GC cycle.
816 initialHeapLive uint64
818 // assistQueue is a queue of assists that are blocked because
819 // there was neither enough credit to steal or enough work to
826 // Timing/utilization stats for this cycle.
827 stwprocs, maxprocs int32
828 tSweepTerm, tMark, tMarkTerm, tEnd int64 // nanotime() of phase start
830 pauseNS int64 // total STW time this cycle
831 pauseStart int64 // nanotime() of last STW
833 // debug.gctrace heap sizes for this cycle.
834 heap0, heap1, heap2, heapGoal uint64
837 // GC runs a garbage collection and blocks the caller until the
838 // garbage collection is complete. It may also block the entire
841 gcStart(gcForceBlockMode, false)
844 // gcMode indicates how concurrent a GC cycle should be.
848 gcBackgroundMode gcMode = iota // concurrent GC and sweep
849 gcForceMode // stop-the-world GC now, concurrent sweep
850 gcForceBlockMode // stop-the-world GC now and STW sweep
853 // gcShouldStart returns true if the exit condition for the _GCoff
854 // phase has been met. The exit condition should be tested when
857 // If forceTrigger is true, it ignores the current heap size, but
858 // checks all other conditions. In general this should be false.
859 func gcShouldStart(forceTrigger bool) bool {
860 return gcphase == _GCoff && (forceTrigger || memstats.heap_live >= memstats.next_gc) && memstats.enablegc && panicking == 0 && gcpercent >= 0
863 // gcStart transitions the GC from _GCoff to _GCmark (if mode ==
864 // gcBackgroundMode) or _GCmarktermination (if mode !=
865 // gcBackgroundMode) by performing sweep termination and GC
868 // This may return without performing this transition in some cases,
869 // such as when called on a system stack or with locks held.
870 func gcStart(mode gcMode, forceTrigger bool) {
871 // Since this is called from malloc and malloc is called in
872 // the guts of a number of libraries that might be holding
873 // locks, don't attempt to start GC in non-preemptible or
874 // potentially unstable situations.
876 if gp := getg(); gp == mp.g0 || mp.locks > 1 || mp.preemptoff != "" {
883 // Pick up the remaining unswept/not being swept spans concurrently
885 // This shouldn't happen if we're being invoked in background
886 // mode since proportional sweep should have just finished
887 // sweeping everything, but rounding errors, etc, may leave a
888 // few spans unswept. In forced mode, this is necessary since
889 // GC can be forced at any point in the sweeping cycle.
891 // We check the transition condition continuously here in case
892 // this G gets delayed in to the next GC cycle.
893 for (mode != gcBackgroundMode || gcShouldStart(forceTrigger)) && gosweepone() != ^uintptr(0) {
897 // Perform GC initialization and the sweep termination
900 // If this is a forced GC, don't acquire the transition lock
901 // or re-check the transition condition because we
902 // specifically *don't* want to share the transition with
904 useStartSema := mode == gcBackgroundMode
906 semacquire(&work.startSema, false)
907 // Re-check transition condition under transition lock.
908 if !gcShouldStart(forceTrigger) {
909 semrelease(&work.startSema)
914 // In gcstoptheworld debug mode, upgrade the mode accordingly.
915 // We do this after re-checking the transition condition so
916 // that multiple goroutines that detect the heap trigger don't
917 // start multiple STW GCs.
918 if mode == gcBackgroundMode {
919 if debug.gcstoptheworld == 1 {
921 } else if debug.gcstoptheworld == 2 {
922 mode = gcForceBlockMode
926 // Ok, we're doing it! Stop everybody else
927 semacquire(&worldsema, false)
933 if mode == gcBackgroundMode {
934 gcBgMarkStartWorkers()
937 work.stwprocs, work.maxprocs = gcprocs(), gomaxprocs
938 work.tSweepTerm = now
939 work.heap0 = memstats.heap_live
943 work.pauseStart = now
944 systemstack(stopTheWorldWithSema)
945 // Finish sweep before we start concurrent scan.
949 // clearpools before we start the GC. If we wait they memory will not be
950 // reclaimed until the next GC cycle.
955 work.finalizersDone = false
957 if mode == gcBackgroundMode { // Do as much work concurrently as possible
958 gcController.startCycle()
959 work.heapGoal = gcController.heapGoal
961 // Enter concurrent mark phase and enable
964 // Because the world is stopped, all Ps will
965 // observe that write barriers are enabled by
966 // the time we start the world and begin
969 // It's necessary to enable write barriers
970 // during the scan phase for several reasons:
972 // They must be enabled for writes to higher
973 // stack frames before we scan stacks and
974 // install stack barriers because this is how
975 // we track writes to inactive stack frames.
976 // (Alternatively, we could not install stack
977 // barriers over frame boundaries with
980 // They must be enabled before assists are
981 // enabled because they must be enabled before
982 // any non-leaf heap objects are marked. Since
983 // allocations are blocked until assists can
984 // happen, we want enable assists as early as
988 // markrootSpans uses work.spans, so make sure
992 gcBgMarkPrepare() // Must happen before assist enable.
995 // At this point all Ps have enabled the write
996 // barrier, thus maintaining the no white to
997 // black invariant. Enable mutator assists to
998 // put back-pressure on fast allocating
1000 atomic.Store(&gcBlackenEnabled, 1)
1002 // Assists and workers can start the moment we start
1004 gcController.assistStartTime = now
1005 gcController.bgMarkStartTime = now
1008 systemstack(startTheWorldWithSema)
1010 work.pauseNS += now - work.pauseStart
1014 work.tMark, work.tMarkTerm = t, t
1015 work.heapGoal = work.heap0
1017 // Perform mark termination. This will restart the world.
1022 semrelease(&work.startSema)
1026 // gcMarkDone transitions the GC from mark 1 to mark 2 and from mark 2
1027 // to mark termination.
1029 // This should be called when all mark work has been drained. In mark
1030 // 1, this includes all root marking jobs, global work buffers, and
1031 // active work buffers in assists and background workers; however,
1032 // work may still be cached in per-P work buffers. In mark 2, per-P
1033 // caches are disabled.
1035 // The calling context must be preemptible.
1037 // Note that it is explicitly okay to have write barriers in this
1038 // function because completion of concurrent mark is best-effort
1039 // anyway. Any work created by write barriers here will be cleaned up
1040 // by mark termination.
1043 semacquire(&work.markDoneSema, false)
1045 // Re-check transition condition under transition lock.
1046 if !(gcphase == _GCmark && work.nwait == work.nproc && !gcMarkWorkAvailable(nil)) {
1047 semrelease(&work.markDoneSema)
1051 // Disallow starting new workers so that any remaining workers
1052 // in the current mark phase will drain out.
1054 // TODO(austin): Should dedicated workers keep an eye on this
1055 // and exit gcDrain promptly?
1056 atomic.Xaddint64(&gcController.dedicatedMarkWorkersNeeded, -0xffffffff)
1057 atomic.Xaddint64(&gcController.fractionalMarkWorkersNeeded, -0xffffffff)
1059 if !gcBlackenPromptly {
1060 // Transition from mark 1 to mark 2.
1062 // The global work list is empty, but there can still be work
1063 // sitting in the per-P work caches and there can be more
1064 // objects reachable from global roots since they don't have write
1065 // barriers. Rescan some roots and flush work caches.
1069 // Disallow caching workbufs and indicate that we're in mark 2.
1070 gcBlackenPromptly = true
1072 // Prevent completion of mark 2 until we've flushed
1074 atomic.Xadd(&work.nwait, -1)
1076 // Rescan global data and BSS. There may still work
1077 // workers running at this point, so bump "jobs" down
1078 // before "next" so they won't try running root jobs
1079 // until we set next.
1080 atomic.Store(&work.markrootJobs, uint32(fixedRootCount+work.nDataRoots+work.nBSSRoots))
1081 atomic.Store(&work.markrootNext, fixedRootCount)
1083 // GC is set up for mark 2. Let Gs blocked on the
1084 // transition lock go while we flush caches.
1085 semrelease(&work.markDoneSema)
1087 systemstack(func() {
1088 // Flush all currently cached workbufs and
1089 // ensure all Ps see gcBlackenPromptly. This
1090 // also blocks until any remaining mark 1
1091 // workers have exited their loop so we can
1092 // start new mark 2 workers that will observe
1093 // the new root marking jobs.
1094 forEachP(func(_p_ *p) {
1099 // Now we can start up mark 2 workers.
1100 atomic.Xaddint64(&gcController.dedicatedMarkWorkersNeeded, 0xffffffff)
1101 atomic.Xaddint64(&gcController.fractionalMarkWorkersNeeded, 0xffffffff)
1103 incnwait := atomic.Xadd(&work.nwait, +1)
1104 if incnwait == work.nproc && !gcMarkWorkAvailable(nil) {
1105 // This loop will make progress because
1106 // gcBlackenPromptly is now true, so it won't
1107 // take this same "if" branch.
1111 // Transition to mark termination.
1113 work.tMarkTerm = now
1114 work.pauseStart = now
1115 getg().m.preemptoff = "gcing"
1116 systemstack(stopTheWorldWithSema)
1117 // The gcphase is _GCmark, it will transition to _GCmarktermination
1118 // below. The important thing is that the wb remains active until
1119 // all marking is complete. This includes writes made by the GC.
1121 // markroot is done now, so record that objects with
1122 // finalizers have been scanned.
1123 work.finalizersDone = true
1125 // Disable assists and background workers. We must do
1126 // this before waking blocked assists.
1127 atomic.Store(&gcBlackenEnabled, 0)
1129 // Flush the gcWork caches. This must be done before
1130 // endCycle since endCycle depends on statistics kept
1134 // Wake all blocked assists. These will run when we
1135 // start the world again.
1138 // Likewise, release the transition lock. Blocked
1139 // workers and assists will run when we start the
1141 semrelease(&work.markDoneSema)
1143 gcController.endCycle()
1145 // Perform mark termination. This will restart the world.
1150 func gcMarkTermination() {
1151 // World is stopped.
1152 // Start marktermination which includes enabling the write barrier.
1153 atomic.Store(&gcBlackenEnabled, 0)
1154 gcBlackenPromptly = false
1155 setGCPhase(_GCmarktermination)
1157 work.heap1 = memstats.heap_live
1158 startTime := nanotime()
1161 mp.preemptoff = "gcing"
1165 casgstatus(gp, _Grunning, _Gwaiting)
1166 gp.waitreason = "garbage collection"
1168 // Run gc on the g0 stack. We do this so that the g stack
1169 // we're currently running on will no longer change. Cuts
1170 // the root set down a bit (g0 stacks are not scanned, and
1171 // we don't need to scan gc's internal state). We also
1172 // need to switch to g0 so we can shrink the stack.
1173 systemstack(func() {
1175 // Must return immediately.
1176 // The outer function's stack may have moved
1177 // during gcMark (it shrinks stacks, including the
1178 // outer function's stack), so we must not refer
1179 // to any of its variables. Return back to the
1180 // non-system stack to pick up the new addresses
1181 // before continuing.
1184 systemstack(func() {
1185 work.heap2 = work.bytesMarked
1186 if debug.gccheckmark > 0 {
1187 // Run a full stop-the-world mark using checkmark bits,
1188 // to check that we didn't forget to mark anything during
1189 // the concurrent mark process.
1196 // marking is complete so we can turn the write barrier off
1200 if debug.gctrace > 1 {
1201 startTime = nanotime()
1202 // The g stacks have been scanned so
1203 // they have gcscanvalid==true and gcworkdone==true.
1204 // Reset these so that all stacks will be rescanned.
1208 // Still in STW but gcphase is _GCoff, reset to _GCmarktermination
1209 // At this point all objects will be found during the gcMark which
1210 // does a complete STW mark and object scan.
1211 setGCPhase(_GCmarktermination)
1213 setGCPhase(_GCoff) // marking is done, turn off wb.
1219 casgstatus(gp, _Gwaiting, _Grunning)
1228 if gcphase != _GCoff {
1229 throw("gc done but gcphase != _GCoff")
1232 // Update timing memstats
1233 now, unixNow := nanotime(), unixnanotime()
1234 work.pauseNS += now - work.pauseStart
1236 atomic.Store64(&memstats.last_gc, uint64(unixNow)) // must be Unix time to make sense to user
1237 memstats.pause_ns[memstats.numgc%uint32(len(memstats.pause_ns))] = uint64(work.pauseNS)
1238 memstats.pause_end[memstats.numgc%uint32(len(memstats.pause_end))] = uint64(unixNow)
1239 memstats.pause_total_ns += uint64(work.pauseNS)
1241 // Update work.totaltime.
1242 sweepTermCpu := int64(work.stwprocs) * (work.tMark - work.tSweepTerm)
1243 // We report idle marking time below, but omit it from the
1244 // overall utilization here since it's "free".
1245 markCpu := gcController.assistTime + gcController.dedicatedMarkTime + gcController.fractionalMarkTime
1246 markTermCpu := int64(work.stwprocs) * (work.tEnd - work.tMarkTerm)
1247 cycleCpu := sweepTermCpu + markCpu + markTermCpu
1248 work.totaltime += cycleCpu
1250 // Compute overall GC CPU utilization.
1251 totalCpu := sched.totaltime + (now-sched.procresizetime)*int64(gomaxprocs)
1252 memstats.gc_cpu_fraction = float64(work.totaltime) / float64(totalCpu)
1256 // Reset sweep state.
1258 sweep.npausesweep = 0
1260 systemstack(startTheWorldWithSema)
1262 // Free stack spans. This must be done between GC cycles.
1263 systemstack(freeStackSpans)
1265 // Print gctrace before dropping worldsema. As soon as we drop
1266 // worldsema another cycle could start and smash the stats
1267 // we're trying to print.
1268 if debug.gctrace > 0 {
1269 util := int(memstats.gc_cpu_fraction * 100)
1273 print("gc ", memstats.numgc,
1274 " @", string(itoaDiv(sbuf[:], uint64(work.tSweepTerm-runtimeInitTime)/1e6, 3)), "s ",
1276 prev := work.tSweepTerm
1277 for i, ns := range []int64{work.tMark, work.tMarkTerm, work.tEnd} {
1281 print(string(fmtNSAsMS(sbuf[:], uint64(ns-prev))))
1284 print(" ms clock, ")
1285 for i, ns := range []int64{sweepTermCpu, gcController.assistTime, gcController.dedicatedMarkTime + gcController.fractionalMarkTime, gcController.idleMarkTime, markTermCpu} {
1286 if i == 2 || i == 3 {
1287 // Separate mark time components with /.
1292 print(string(fmtNSAsMS(sbuf[:], uint64(ns))))
1295 work.heap0>>20, "->", work.heap1>>20, "->", work.heap2>>20, " MB, ",
1296 work.heapGoal>>20, " MB goal, ",
1297 work.maxprocs, " P")
1298 if work.mode != gcBackgroundMode {
1305 semrelease(&worldsema)
1306 // Careful: another GC cycle may start now.
1311 // now that gc is done, kick off finalizer thread if needed
1312 if !concurrentSweep {
1313 // give the queued finalizers, if any, a chance to run
1318 // gcBgMarkStartWorkers prepares background mark worker goroutines.
1319 // These goroutines will not run until the mark phase, but they must
1320 // be started while the work is not stopped and from a regular G
1321 // stack. The caller must hold worldsema.
1322 func gcBgMarkStartWorkers() {
1323 // Background marking is performed by per-P G's. Ensure that
1324 // each P has a background GC G.
1325 for _, p := range &allp {
1326 if p == nil || p.status == _Pdead {
1329 if p.gcBgMarkWorker == 0 {
1330 go gcBgMarkWorker(p)
1331 notetsleepg(&work.bgMarkReady, -1)
1332 noteclear(&work.bgMarkReady)
1337 // gcBgMarkPrepare sets up state for background marking.
1338 // Mutator assists must not yet be enabled.
1339 func gcBgMarkPrepare() {
1340 // Background marking will stop when the work queues are empty
1341 // and there are no more workers (note that, since this is
1342 // concurrent, this may be a transient state, but mark
1343 // termination will clean it up). Between background workers
1344 // and assists, we don't really know how many workers there
1345 // will be, so we pretend to have an arbitrarily large number
1346 // of workers, almost all of which are "waiting". While a
1347 // worker is working it decrements nwait. If nproc == nwait,
1348 // there are no workers.
1349 work.nproc = ^uint32(0)
1350 work.nwait = ^uint32(0)
1353 func gcBgMarkWorker(_p_ *p) {
1354 type parkInfo struct {
1355 m *m // Release this m on park.
1356 attach *p // If non-nil, attach to this p on park.
1363 // Inform gcBgMarkStartWorkers that this worker is ready.
1364 // After this point, the background mark worker is scheduled
1365 // cooperatively by gcController.findRunnable. Hence, it must
1366 // never be preempted, as this would put it into _Grunnable
1367 // and put it on a run queue. Instead, when the preempt flag
1368 // is set, this puts itself into _Gwaiting to be woken up by
1369 // gcController.findRunnable at the appropriate time.
1370 notewakeup(&work.bgMarkReady)
1373 // Go to sleep until woken by gcContoller.findRunnable.
1374 // We can't releasem yet since even the call to gopark
1375 // may be preempted.
1376 gopark(func(g *g, parkp unsafe.Pointer) bool {
1377 park := (*parkInfo)(parkp)
1379 // The worker G is no longer running, so it's
1380 // now safe to allow preemption.
1383 // If the worker isn't attached to its P,
1384 // attach now. During initialization and after
1385 // a phase change, the worker may have been
1386 // running on a different P. As soon as we
1387 // attach, the owner P may schedule the
1388 // worker, so this must be done after the G is
1390 if park.attach != nil {
1393 // cas the worker because we may be
1394 // racing with a new worker starting
1396 if !p.gcBgMarkWorker.cas(0, guintptr(unsafe.Pointer(g))) {
1397 // The P got a new worker.
1398 // Exit this worker.
1403 }, noescape(unsafe.Pointer(&park)), "GC worker (idle)", traceEvGoBlock, 0)
1405 // Loop until the P dies and disassociates this
1406 // worker (the P may later be reused, in which case
1407 // it will get a new worker) or we failed to associate.
1408 if _p_.gcBgMarkWorker.ptr() != gp {
1412 // Disable preemption so we can use the gcw. If the
1413 // scheduler wants to preempt us, we'll stop draining,
1414 // dispose the gcw, and then preempt.
1417 if gcBlackenEnabled == 0 {
1418 throw("gcBgMarkWorker: blackening not enabled")
1421 startTime := nanotime()
1423 decnwait := atomic.Xadd(&work.nwait, -1)
1424 if decnwait == work.nproc {
1425 println("runtime: work.nwait=", decnwait, "work.nproc=", work.nproc)
1426 throw("work.nwait was > work.nproc")
1429 switch _p_.gcMarkWorkerMode {
1431 throw("gcBgMarkWorker: unexpected gcMarkWorkerMode")
1432 case gcMarkWorkerDedicatedMode:
1433 gcDrain(&_p_.gcw, gcDrainNoBlock|gcDrainFlushBgCredit)
1434 case gcMarkWorkerFractionalMode, gcMarkWorkerIdleMode:
1435 gcDrain(&_p_.gcw, gcDrainUntilPreempt|gcDrainFlushBgCredit)
1438 // If we are nearing the end of mark, dispose
1439 // of the cache promptly. We must do this
1440 // before signaling that we're no longer
1441 // working so that other workers can't observe
1442 // no workers and no work while we have this
1443 // cached, and before we compute done.
1444 if gcBlackenPromptly {
1448 // Account for time.
1449 duration := nanotime() - startTime
1450 switch _p_.gcMarkWorkerMode {
1451 case gcMarkWorkerDedicatedMode:
1452 atomic.Xaddint64(&gcController.dedicatedMarkTime, duration)
1453 atomic.Xaddint64(&gcController.dedicatedMarkWorkersNeeded, 1)
1454 case gcMarkWorkerFractionalMode:
1455 atomic.Xaddint64(&gcController.fractionalMarkTime, duration)
1456 atomic.Xaddint64(&gcController.fractionalMarkWorkersNeeded, 1)
1457 case gcMarkWorkerIdleMode:
1458 atomic.Xaddint64(&gcController.idleMarkTime, duration)
1461 // Was this the last worker and did we run out
1463 incnwait := atomic.Xadd(&work.nwait, +1)
1464 if incnwait > work.nproc {
1465 println("runtime: p.gcMarkWorkerMode=", _p_.gcMarkWorkerMode,
1466 "work.nwait=", incnwait, "work.nproc=", work.nproc)
1467 throw("work.nwait > work.nproc")
1470 // If this worker reached a background mark completion
1471 // point, signal the main GC goroutine.
1472 if incnwait == work.nproc && !gcMarkWorkAvailable(nil) {
1473 // Make this G preemptible and disassociate it
1474 // as the worker for this P so
1475 // findRunnableGCWorker doesn't try to
1477 _p_.gcBgMarkWorker.set(nil)
1482 // Disable preemption and prepare to reattach
1485 // We may be running on a different P at this
1486 // point, so we can't reattach until this G is
1494 // gcMarkWorkAvailable returns true if executing a mark worker
1495 // on p is potentially useful. p may be nil, in which case it only
1496 // checks the global sources of work.
1497 func gcMarkWorkAvailable(p *p) bool {
1498 if p != nil && !p.gcw.empty() {
1501 if atomic.Load64(&work.full) != 0 {
1502 return true // global work available
1504 if work.markrootNext < work.markrootJobs {
1505 return true // root scan work available
1510 // gcFlushGCWork disposes the gcWork caches of all Ps. The world must
1513 func gcFlushGCWork() {
1514 // Gather all cached GC work. All other Ps are stopped, so
1515 // it's safe to manipulate their GC work caches.
1516 for i := 0; i < int(gomaxprocs); i++ {
1517 allp[i].gcw.dispose()
1521 // gcMark runs the mark (or, for concurrent GC, mark termination)
1522 // STW is in effect at this point.
1523 //TODO go:nowritebarrier
1524 func gcMark(start_time int64) {
1525 if debug.allocfreetrace > 0 {
1529 if gcphase != _GCmarktermination {
1530 throw("in gcMark expecting to see gcphase as _GCmarktermination")
1532 work.tstart = start_time
1534 gcCopySpans() // TODO(rlh): should this be hoisted and done only once? Right now it is done for normal marking and also for checkmarking.
1536 // Make sure the per-P gcWork caches are empty. During mark
1537 // termination, these caches can still be used temporarily,
1538 // but must be disposed to the global lists immediately.
1541 // Queue root marking jobs.
1546 work.nproc = uint32(gcprocs())
1553 noteclear(&work.alldone)
1554 helpgc(int32(work.nproc))
1559 gcw := &getg().m.p.ptr().gcw
1560 gcDrain(gcw, gcDrainBlock)
1565 throw("work.full != 0")
1569 notesleep(&work.alldone)
1572 // markroot is done now, so record that objects with
1573 // finalizers have been scanned.
1574 work.finalizersDone = true
1576 for i := 0; i < int(gomaxprocs); i++ {
1577 if !allp[i].gcw.empty() {
1578 throw("P has cached GC work at end of mark termination")
1588 // Compute the reachable heap size at the beginning of the
1589 // cycle. This is approximately the marked heap size at the
1590 // end (which we know) minus the amount of marked heap that
1591 // was allocated after marking began (which we don't know, but
1592 // is approximately the amount of heap that was allocated
1593 // since marking began).
1594 allocatedDuringCycle := memstats.heap_live - work.initialHeapLive
1595 if memstats.heap_live < work.initialHeapLive {
1596 // This can happen if mCentral_UncacheSpan tightens
1597 // the heap_live approximation.
1598 allocatedDuringCycle = 0
1600 if work.bytesMarked >= allocatedDuringCycle {
1601 memstats.heap_reachable = work.bytesMarked - allocatedDuringCycle
1603 // This can happen if most of the allocation during
1604 // the cycle never became reachable from the heap.
1605 // Just set the reachable heap approximation to 0 and
1606 // let the heapminimum kick in below.
1607 memstats.heap_reachable = 0
1610 // Trigger the next GC cycle when the allocated heap has grown
1611 // by triggerRatio over the reachable heap size. Assume that
1612 // we're in steady state, so the reachable heap size is the
1613 // same now as it was at the beginning of the GC cycle.
1614 memstats.next_gc = uint64(float64(memstats.heap_reachable) * (1 + gcController.triggerRatio))
1615 if memstats.next_gc < heapminimum {
1616 memstats.next_gc = heapminimum
1618 if int64(memstats.next_gc) < 0 {
1619 print("next_gc=", memstats.next_gc, " bytesMarked=", work.bytesMarked, " heap_live=", memstats.heap_live, " initialHeapLive=", work.initialHeapLive, "\n")
1620 throw("next_gc underflow")
1623 // Update other GC heap size stats. This must happen after
1624 // cachestats (which flushes local statistics to these) and
1625 // flushallmcaches (which modifies heap_live).
1626 memstats.heap_live = work.bytesMarked
1627 memstats.heap_marked = work.bytesMarked
1628 memstats.heap_scan = uint64(gcController.scanWork)
1630 minNextGC := memstats.heap_live + sweepMinHeapDistance*uint64(gcpercent)/100
1631 if memstats.next_gc < minNextGC {
1632 // The allocated heap is already past the trigger.
1633 // This can happen if the triggerRatio is very low and
1634 // the reachable heap estimate is less than the live
1637 // Concurrent sweep happens in the heap growth from
1638 // heap_live to next_gc, so bump next_gc up to ensure
1639 // that concurrent sweep has some heap growth in which
1640 // to perform sweeping before we start the next GC
1642 memstats.next_gc = minNextGC
1651 func gcSweep(mode gcMode) {
1652 if gcphase != _GCoff {
1653 throw("gcSweep being done but phase is not GCoff")
1658 mheap_.sweepgen += 2
1659 mheap_.sweepdone = 0
1661 unlock(&mheap_.lock)
1663 if !_ConcurrentSweep || mode == gcForceBlockMode {
1664 // Special case synchronous sweep.
1665 // Record that no proportional sweeping has to happen.
1667 mheap_.sweepPagesPerByte = 0
1668 mheap_.pagesSwept = 0
1669 unlock(&mheap_.lock)
1670 // Sweep all spans eagerly.
1671 for sweepone() != ^uintptr(0) {
1674 // Do an additional mProf_GC, because all 'free' events are now real as well.
1680 // Concurrent sweep needs to sweep all of the in-use pages by
1681 // the time the allocated heap reaches the GC trigger. Compute
1682 // the ratio of in-use pages to sweep per byte allocated.
1683 heapDistance := int64(memstats.next_gc) - int64(memstats.heap_live)
1684 // Add a little margin so rounding errors and concurrent
1685 // sweep are less likely to leave pages unswept when GC starts.
1686 heapDistance -= 1024 * 1024
1687 if heapDistance < _PageSize {
1688 // Avoid setting the sweep ratio extremely high
1689 heapDistance = _PageSize
1692 mheap_.sweepPagesPerByte = float64(mheap_.pagesInUse) / float64(heapDistance)
1693 mheap_.pagesSwept = 0
1694 mheap_.spanBytesAlloc = 0
1695 unlock(&mheap_.lock)
1697 // Background sweep.
1700 sweep.parked = false
1707 func gcCopySpans() {
1708 // Cache runtime.mheap_.allspans in work.spans to avoid conflicts with
1709 // resizing/freeing allspans.
1710 // New spans can be created while GC progresses, but they are not garbage for
1712 // - new stack spans can be created even while the world is stopped.
1713 // - new malloc spans can be created during the concurrent sweep
1714 // Even if this is stop-the-world, a concurrent exitsyscall can allocate a stack from heap.
1716 // Free the old cached mark array if necessary.
1717 if work.spans != nil && &work.spans[0] != &h_allspans[0] {
1718 sysFree(unsafe.Pointer(&work.spans[0]), uintptr(len(work.spans))*unsafe.Sizeof(work.spans[0]), &memstats.other_sys)
1720 // Cache the current array for sweeping.
1721 mheap_.gcspans = mheap_.allspans
1722 work.spans = h_allspans
1723 unlock(&mheap_.lock)
1726 // gcResetMarkState resets global state prior to marking (concurrent
1727 // or STW) and resets the stack scan state of all Gs. Any Gs created
1728 // after this will also be in the reset state.
1729 func gcResetMarkState() {
1730 // This may be called during a concurrent phase, so make sure
1731 // allgs doesn't change.
1733 for _, gp := range allgs {
1734 gp.gcscandone = false // set to true in gcphasework
1735 gp.gcscanvalid = false // stack has not been scanned
1736 gp.gcAssistBytes = 0
1740 work.bytesMarked = 0
1741 work.initialHeapLive = memstats.heap_live
1744 // Hooks for other packages
1746 var poolcleanup func()
1748 //go:linkname sync_runtime_registerPoolCleanup sync.runtime_registerPoolCleanup
1749 func sync_runtime_registerPoolCleanup(f func()) {
1755 if poolcleanup != nil {
1759 // Clear central sudog cache.
1760 // Leave per-P caches alone, they have strictly bounded size.
1761 // Disconnect cached list before dropping it on the floor,
1762 // so that a dangling ref to one entry does not pin all of them.
1763 lock(&sched.sudoglock)
1764 var sg, sgnext *sudog
1765 for sg = sched.sudogcache; sg != nil; sg = sgnext {
1769 sched.sudogcache = nil
1770 unlock(&sched.sudoglock)
1772 // Clear central defer pools.
1773 // Leave per-P pools alone, they have strictly bounded size.
1774 lock(&sched.deferlock)
1775 for i := range sched.deferpool {
1776 // disconnect cached list before dropping it on the floor,
1777 // so that a dangling ref to one entry does not pin all of them.
1778 var d, dlink *_defer
1779 for d = sched.deferpool[i]; d != nil; d = dlink {
1783 sched.deferpool[i] = nil
1785 unlock(&sched.deferlock)
1800 // Parallel mark over GC roots and heap
1801 if gcphase == _GCmarktermination {
1802 gcw := &_g_.m.p.ptr().gcw
1803 gcDrain(gcw, gcDrainBlock) // blocks in getfull
1811 nproc := work.nproc // work.nproc can change right after we increment work.ndone
1812 if atomic.Xadd(&work.ndone, +1) == nproc-1 {
1813 notewakeup(&work.alldone)
1818 func gchelperstart() {
1821 if _g_.m.helpgc < 0 || _g_.m.helpgc >= _MaxGcproc {
1822 throw("gchelperstart: bad m->helpgc")
1824 if _g_ != _g_.m.g0 {
1825 throw("gchelper not running on g0 stack")
1829 // itoaDiv formats val/(10**dec) into buf.
1830 func itoaDiv(buf []byte, val uint64, dec int) []byte {
1833 for val >= 10 || i >= idec {
1834 buf[i] = byte(val%10 + '0')
1842 buf[i] = byte(val + '0')
1846 // fmtNSAsMS nicely formats ns nanoseconds as milliseconds.
1847 func fmtNSAsMS(buf []byte, ns uint64) []byte {
1849 // Format as whole milliseconds.
1850 return itoaDiv(buf, ns/1e6, 0)
1852 // Format two digits of precision, with at most three decimal places.
1863 return itoaDiv(buf, x, dec)