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 // Garbage collector (GC). 6 // 7 // The GC runs concurrently with mutator threads, is type accurate (aka precise), allows multiple 8 // GC thread to run in parallel. It is a concurrent mark and sweep that uses a write barrier. It is 9 // non-generational and non-compacting. Allocation is done using size segregated per P allocation 10 // areas to minimize fragmentation while eliminating locks in the common case. 11 // 12 // The algorithm decomposes into several steps. 13 // This is a high level description of the algorithm being used. For an overview of GC a good 14 // place to start is Richard Jones' gchandbook.org. 15 // 16 // The algorithm's intellectual heritage includes Dijkstra's on-the-fly algorithm, see 17 // Edsger W. Dijkstra, Leslie Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens. 1978. 18 // On-the-fly garbage collection: an exercise in cooperation. Commun. ACM 21, 11 (November 1978), 19 // 966-975. 20 // For journal quality proofs that these steps are complete, correct, and terminate see 21 // Hudson, R., and Moss, J.E.B. Copying Garbage Collection without stopping the world. 22 // Concurrency and Computation: Practice and Experience 15(3-5), 2003. 23 // 24 // 1. GC performs sweep termination. 25 // 26 // a. Stop the world. This causes all Ps to reach a GC safe-point. 27 // 28 // b. Sweep any unswept spans. There will only be unswept spans if 29 // this GC cycle was forced before the expected time. 30 // 31 // 2. GC performs the "mark 1" sub-phase. In this sub-phase, Ps are 32 // allowed to locally cache parts of the work queue. 33 // 34 // a. Prepare for the mark phase by setting gcphase to _GCmark 35 // (from _GCoff), enabling the write barrier, enabling mutator 36 // assists, and enqueueing root mark jobs. No objects may be 37 // scanned until all Ps have enabled the write barrier, which is 38 // accomplished using STW. 39 // 40 // b. Start the world. From this point, GC work is done by mark 41 // workers started by the scheduler and by assists performed as 42 // part of allocation. The write barrier shades both the 43 // overwritten pointer and the new pointer value for any pointer 44 // writes (see mbarrier.go for details). Newly allocated objects 45 // are immediately marked black. 46 // 47 // c. GC performs root marking jobs. This includes scanning all 48 // stacks, shading all globals, and shading any heap pointers in 49 // off-heap runtime data structures. Scanning a stack stops a 50 // goroutine, shades any pointers found on its stack, and then 51 // resumes the goroutine. 52 // 53 // d. GC drains the work queue of grey objects, scanning each grey 54 // object to black and shading all pointers found in the object 55 // (which in turn may add those pointers to the work queue). 56 // 57 // 3. Once the global work queue is empty (but local work queue caches 58 // may still contain work), GC performs the "mark 2" sub-phase. 59 // 60 // a. GC stops all workers, disables local work queue caches, 61 // flushes each P's local work queue cache to the global work queue 62 // cache, and reenables workers. 63 // 64 // b. GC again drains the work queue, as in 2d above. 65 // 66 // 4. Once the work queue is empty, GC performs mark termination. 67 // 68 // a. Stop the world. 69 // 70 // b. Set gcphase to _GCmarktermination, and disable workers and 71 // assists. 72 // 73 // c. Drain any remaining work from the work queue (typically there 74 // will be none). 75 // 76 // d. Perform other housekeeping like flushing mcaches. 77 // 78 // 5. GC performs the sweep phase. 79 // 80 // a. Prepare for the sweep phase by setting gcphase to _GCoff, 81 // setting up sweep state and disabling the write barrier. 82 // 83 // b. Start the world. From this point on, newly allocated objects 84 // are white, and allocating sweeps spans before use if necessary. 85 // 86 // c. GC does concurrent sweeping in the background and in response 87 // to allocation. See description below. 88 // 89 // 6. When sufficient allocation has taken place, replay the sequence 90 // starting with 1 above. See discussion of GC rate below. 91 92 // Concurrent sweep. 93 // 94 // The sweep phase proceeds concurrently with normal program execution. 95 // The heap is swept span-by-span both lazily (when a goroutine needs another span) 96 // and concurrently in a background goroutine (this helps programs that are not CPU bound). 97 // At the end of STW mark termination all spans are marked as "needs sweeping". 98 // 99 // The background sweeper goroutine simply sweeps spans one-by-one. 100 // 101 // To avoid requesting more OS memory while there are unswept spans, when a 102 // goroutine needs another span, it first attempts to reclaim that much memory 103 // by sweeping. When a goroutine needs to allocate a new small-object span, it 104 // sweeps small-object spans for the same object size until it frees at least 105 // one object. When a goroutine needs to allocate large-object span from heap, 106 // it sweeps spans until it frees at least that many pages into heap. There is 107 // one case where this may not suffice: if a goroutine sweeps and frees two 108 // nonadjacent one-page spans to the heap, it will allocate a new two-page 109 // span, but there can still be other one-page unswept spans which could be 110 // combined into a two-page span. 111 // 112 // It's critical to ensure that no operations proceed on unswept spans (that would corrupt 113 // mark bits in GC bitmap). During GC all mcaches are flushed into the central cache, 114 // so they are empty. When a goroutine grabs a new span into mcache, it sweeps it. 115 // When a goroutine explicitly frees an object or sets a finalizer, it ensures that 116 // the span is swept (either by sweeping it, or by waiting for the concurrent sweep to finish). 117 // The finalizer goroutine is kicked off only when all spans are swept. 118 // When the next GC starts, it sweeps all not-yet-swept spans (if any). 119 120 // GC rate. 121 // Next GC is after we've allocated an extra amount of memory proportional to 122 // the amount already in use. The proportion is controlled by GOGC environment variable 123 // (100 by default). If GOGC=100 and we're using 4M, we'll GC again when we get to 8M 124 // (this mark is tracked in next_gc variable). This keeps the GC cost in linear 125 // proportion to the allocation cost. Adjusting GOGC just changes the linear constant 126 // (and also the amount of extra memory used). 127 128 // Oblets 129 // 130 // In order to prevent long pauses while scanning large objects and to 131 // improve parallelism, the garbage collector breaks up scan jobs for 132 // objects larger than maxObletBytes into "oblets" of at most 133 // maxObletBytes. When scanning encounters the beginning of a large 134 // object, it scans only the first oblet and enqueues the remaining 135 // oblets as new scan jobs. 136 137 package runtime 138 139 import ( 140 "runtime/internal/atomic" 141 "runtime/internal/sys" 142 "unsafe" 143 ) 144 145 const ( 146 _DebugGC = 0 147 _ConcurrentSweep = true 148 _FinBlockSize = 4 * 1024 149 150 // sweepMinHeapDistance is a lower bound on the heap distance 151 // (in bytes) reserved for concurrent sweeping between GC 152 // cycles. This will be scaled by gcpercent/100. 153 sweepMinHeapDistance = 1024 * 1024 154 ) 155 156 // heapminimum is the minimum heap size at which to trigger GC. 157 // For small heaps, this overrides the usual GOGC*live set rule. 158 // 159 // When there is a very small live set but a lot of allocation, simply 160 // collecting when the heap reaches GOGC*live results in many GC 161 // cycles and high total per-GC overhead. This minimum amortizes this 162 // per-GC overhead while keeping the heap reasonably small. 163 // 164 // During initialization this is set to 4MB*GOGC/100. In the case of 165 // GOGC==0, this will set heapminimum to 0, resulting in constant 166 // collection even when the heap size is small, which is useful for 167 // debugging. 168 var heapminimum uint64 = defaultHeapMinimum 169 170 // defaultHeapMinimum is the value of heapminimum for GOGC==100. 171 const defaultHeapMinimum = 4 << 20 172 173 // Initialized from $GOGC. GOGC=off means no GC. 174 var gcpercent int32 175 176 func gcinit() { 177 if unsafe.Sizeof(workbuf{}) != _WorkbufSize { 178 throw("size of Workbuf is suboptimal") 179 } 180 181 // No sweep on the first cycle. 182 mheap_.sweepdone = 1 183 184 // Set a reasonable initial GC trigger. 185 memstats.triggerRatio = 7 / 8.0 186 187 // Fake a heap_marked value so it looks like a trigger at 188 // heapminimum is the appropriate growth from heap_marked. 189 // This will go into computing the initial GC goal. 190 memstats.heap_marked = uint64(float64(heapminimum) / (1 + memstats.triggerRatio)) 191 192 // Set gcpercent from the environment. This will also compute 193 // and set the GC trigger and goal. 194 _ = setGCPercent(readgogc()) 195 196 work.startSema = 1 197 work.markDoneSema = 1 198 } 199 200 func readgogc() int32 { 201 p := gogetenv("GOGC") 202 if p == "off" { 203 return -1 204 } 205 if n, ok := atoi32(p); ok { 206 return n 207 } 208 return 100 209 } 210 211 // gcenable is called after the bulk of the runtime initialization, 212 // just before we're about to start letting user code run. 213 // It kicks off the background sweeper goroutine and enables GC. 214 func gcenable() { 215 c := make(chan int, 1) 216 go bgsweep(c) 217 <-c 218 memstats.enablegc = true // now that runtime is initialized, GC is okay 219 } 220 221 //go:linkname setGCPercent runtime/debug.setGCPercent 222 func setGCPercent(in int32) (out int32) { 223 lock(&mheap_.lock) 224 out = gcpercent 225 if in < 0 { 226 in = -1 227 } 228 gcpercent = in 229 heapminimum = defaultHeapMinimum * uint64(gcpercent) / 100 230 // Update pacing in response to gcpercent change. 231 gcSetTriggerRatio(memstats.triggerRatio) 232 unlock(&mheap_.lock) 233 234 // If we just disabled GC, wait for any concurrent GC mark to 235 // finish so we always return with no GC running. 236 if in < 0 { 237 gcWaitOnMark(atomic.Load(&work.cycles)) 238 } 239 240 return out 241 } 242 243 // Garbage collector phase. 244 // Indicates to write barrier and synchronization task to perform. 245 var gcphase uint32 246 247 // The compiler knows about this variable. 248 // If you change it, you must change builtin/runtime.go, too. 249 // If you change the first four bytes, you must also change the write 250 // barrier insertion code. 251 var writeBarrier struct { 252 enabled bool // compiler emits a check of this before calling write barrier 253 pad [3]byte // compiler uses 32-bit load for "enabled" field 254 needed bool // whether we need a write barrier for current GC phase 255 cgo bool // whether we need a write barrier for a cgo check 256 alignme uint64 // guarantee alignment so that compiler can use a 32 or 64-bit load 257 } 258 259 // gcBlackenEnabled is 1 if mutator assists and background mark 260 // workers are allowed to blacken objects. This must only be set when 261 // gcphase == _GCmark. 262 var gcBlackenEnabled uint32 263 264 // gcBlackenPromptly indicates that optimizations that may 265 // hide work from the global work queue should be disabled. 266 // 267 // If gcBlackenPromptly is true, per-P gcWork caches should 268 // be flushed immediately and new objects should be allocated black. 269 // 270 // There is a tension between allocating objects white and 271 // allocating them black. If white and the objects die before being 272 // marked they can be collected during this GC cycle. On the other 273 // hand allocating them black will reduce _GCmarktermination latency 274 // since more work is done in the mark phase. This tension is resolved 275 // by allocating white until the mark phase is approaching its end and 276 // then allocating black for the remainder of the mark phase. 277 var gcBlackenPromptly bool 278 279 const ( 280 _GCoff = iota // GC not running; sweeping in background, write barrier disabled 281 _GCmark // GC marking roots and workbufs: allocate black, write barrier ENABLED 282 _GCmarktermination // GC mark termination: allocate black, P's help GC, write barrier ENABLED 283 ) 284 285 //go:nosplit 286 func setGCPhase(x uint32) { 287 atomic.Store(&gcphase, x) 288 writeBarrier.needed = gcphase == _GCmark || gcphase == _GCmarktermination 289 writeBarrier.enabled = writeBarrier.needed || writeBarrier.cgo 290 } 291 292 // gcMarkWorkerMode represents the mode that a concurrent mark worker 293 // should operate in. 294 // 295 // Concurrent marking happens through four different mechanisms. One 296 // is mutator assists, which happen in response to allocations and are 297 // not scheduled. The other three are variations in the per-P mark 298 // workers and are distinguished by gcMarkWorkerMode. 299 type gcMarkWorkerMode int 300 301 const ( 302 // gcMarkWorkerDedicatedMode indicates that the P of a mark 303 // worker is dedicated to running that mark worker. The mark 304 // worker should run without preemption. 305 gcMarkWorkerDedicatedMode gcMarkWorkerMode = iota 306 307 // gcMarkWorkerFractionalMode indicates that a P is currently 308 // running the "fractional" mark worker. The fractional worker 309 // is necessary when GOMAXPROCS*gcBackgroundUtilization is not 310 // an integer. The fractional worker should run until it is 311 // preempted and will be scheduled to pick up the fractional 312 // part of GOMAXPROCS*gcBackgroundUtilization. 313 gcMarkWorkerFractionalMode 314 315 // gcMarkWorkerIdleMode indicates that a P is running the mark 316 // worker because it has nothing else to do. The idle worker 317 // should run until it is preempted and account its time 318 // against gcController.idleMarkTime. 319 gcMarkWorkerIdleMode 320 ) 321 322 // gcMarkWorkerModeStrings are the strings labels of gcMarkWorkerModes 323 // to use in execution traces. 324 var gcMarkWorkerModeStrings = [...]string{ 325 "GC (dedicated)", 326 "GC (fractional)", 327 "GC (idle)", 328 } 329 330 // gcController implements the GC pacing controller that determines 331 // when to trigger concurrent garbage collection and how much marking 332 // work to do in mutator assists and background marking. 333 // 334 // It uses a feedback control algorithm to adjust the memstats.gc_trigger 335 // trigger based on the heap growth and GC CPU utilization each cycle. 336 // This algorithm optimizes for heap growth to match GOGC and for CPU 337 // utilization between assist and background marking to be 25% of 338 // GOMAXPROCS. The high-level design of this algorithm is documented 339 // at https://golang.org/s/go15gcpacing. 340 // 341 // All fields of gcController are used only during a single mark 342 // cycle. 343 var gcController gcControllerState 344 345 type gcControllerState struct { 346 // scanWork is the total scan work performed this cycle. This 347 // is updated atomically during the cycle. Updates occur in 348 // bounded batches, since it is both written and read 349 // throughout the cycle. At the end of the cycle, this is how 350 // much of the retained heap is scannable. 351 // 352 // Currently this is the bytes of heap scanned. For most uses, 353 // this is an opaque unit of work, but for estimation the 354 // definition is important. 355 scanWork int64 356 357 // bgScanCredit is the scan work credit accumulated by the 358 // concurrent background scan. This credit is accumulated by 359 // the background scan and stolen by mutator assists. This is 360 // updated atomically. Updates occur in bounded batches, since 361 // it is both written and read throughout the cycle. 362 bgScanCredit int64 363 364 // assistTime is the nanoseconds spent in mutator assists 365 // during this cycle. This is updated atomically. Updates 366 // occur in bounded batches, since it is both written and read 367 // throughout the cycle. 368 assistTime int64 369 370 // dedicatedMarkTime is the nanoseconds spent in dedicated 371 // mark workers during this cycle. This is updated atomically 372 // at the end of the concurrent mark phase. 373 dedicatedMarkTime int64 374 375 // fractionalMarkTime is the nanoseconds spent in the 376 // fractional mark worker during this cycle. This is updated 377 // atomically throughout the cycle and will be up-to-date if 378 // the fractional mark worker is not currently running. 379 fractionalMarkTime int64 380 381 // idleMarkTime is the nanoseconds spent in idle marking 382 // during this cycle. This is updated atomically throughout 383 // the cycle. 384 idleMarkTime int64 385 386 // markStartTime is the absolute start time in nanoseconds 387 // that assists and background mark workers started. 388 markStartTime int64 389 390 // dedicatedMarkWorkersNeeded is the number of dedicated mark 391 // workers that need to be started. This is computed at the 392 // beginning of each cycle and decremented atomically as 393 // dedicated mark workers get started. 394 dedicatedMarkWorkersNeeded int64 395 396 // assistWorkPerByte is the ratio of scan work to allocated 397 // bytes that should be performed by mutator assists. This is 398 // computed at the beginning of each cycle and updated every 399 // time heap_scan is updated. 400 assistWorkPerByte float64 401 402 // assistBytesPerWork is 1/assistWorkPerByte. 403 assistBytesPerWork float64 404 405 // fractionalUtilizationGoal is the fraction of wall clock 406 // time that should be spent in the fractional mark worker on 407 // each P that isn't running a dedicated worker. 408 // 409 // For example, if the utilization goal is 25% and there are 410 // no dedicated workers, this will be 0.25. If there goal is 411 // 25%, there is one dedicated worker, and GOMAXPROCS is 5, 412 // this will be 0.05 to make up the missing 5%. 413 // 414 // If this is zero, no fractional workers are needed. 415 fractionalUtilizationGoal float64 416 417 _ [sys.CacheLineSize]byte 418 } 419 420 // startCycle resets the GC controller's state and computes estimates 421 // for a new GC cycle. The caller must hold worldsema. 422 func (c *gcControllerState) startCycle() { 423 c.scanWork = 0 424 c.bgScanCredit = 0 425 c.assistTime = 0 426 c.dedicatedMarkTime = 0 427 c.fractionalMarkTime = 0 428 c.idleMarkTime = 0 429 430 // If this is the first GC cycle or we're operating on a very 431 // small heap, fake heap_marked so it looks like gc_trigger is 432 // the appropriate growth from heap_marked, even though the 433 // real heap_marked may not have a meaningful value (on the 434 // first cycle) or may be much smaller (resulting in a large 435 // error response). 436 if memstats.gc_trigger <= heapminimum { 437 memstats.heap_marked = uint64(float64(memstats.gc_trigger) / (1 + memstats.triggerRatio)) 438 } 439 440 // Re-compute the heap goal for this cycle in case something 441 // changed. This is the same calculation we use elsewhere. 442 memstats.next_gc = memstats.heap_marked + memstats.heap_marked*uint64(gcpercent)/100 443 if gcpercent < 0 { 444 memstats.next_gc = ^uint64(0) 445 } 446 447 // Ensure that the heap goal is at least a little larger than 448 // the current live heap size. This may not be the case if GC 449 // start is delayed or if the allocation that pushed heap_live 450 // over gc_trigger is large or if the trigger is really close to 451 // GOGC. Assist is proportional to this distance, so enforce a 452 // minimum distance, even if it means going over the GOGC goal 453 // by a tiny bit. 454 if memstats.next_gc < memstats.heap_live+1024*1024 { 455 memstats.next_gc = memstats.heap_live + 1024*1024 456 } 457 458 // Compute the background mark utilization goal. In general, 459 // this may not come out exactly. We round the number of 460 // dedicated workers so that the utilization is closest to 461 // 25%. For small GOMAXPROCS, this would introduce too much 462 // error, so we add fractional workers in that case. 463 totalUtilizationGoal := float64(gomaxprocs) * gcBackgroundUtilization 464 c.dedicatedMarkWorkersNeeded = int64(totalUtilizationGoal + 0.5) 465 utilError := float64(c.dedicatedMarkWorkersNeeded)/totalUtilizationGoal - 1 466 const maxUtilError = 0.3 467 if utilError < -maxUtilError || utilError > maxUtilError { 468 // Rounding put us more than 30% off our goal. With 469 // gcBackgroundUtilization of 25%, this happens for 470 // GOMAXPROCS<=3 or GOMAXPROCS=6. Enable fractional 471 // workers to compensate. 472 if float64(c.dedicatedMarkWorkersNeeded) > totalUtilizationGoal { 473 // Too many dedicated workers. 474 c.dedicatedMarkWorkersNeeded-- 475 } 476 c.fractionalUtilizationGoal = (totalUtilizationGoal - float64(c.dedicatedMarkWorkersNeeded)) / float64(gomaxprocs) 477 } else { 478 c.fractionalUtilizationGoal = 0 479 } 480 481 // Clear per-P state 482 for _, p := range allp { 483 p.gcAssistTime = 0 484 p.gcFractionalMarkTime = 0 485 } 486 487 // Compute initial values for controls that are updated 488 // throughout the cycle. 489 c.revise() 490 491 if debug.gcpacertrace > 0 { 492 print("pacer: assist ratio=", c.assistWorkPerByte, 493 " (scan ", memstats.heap_scan>>20, " MB in ", 494 work.initialHeapLive>>20, "->", 495 memstats.next_gc>>20, " MB)", 496 " workers=", c.dedicatedMarkWorkersNeeded, 497 "+", c.fractionalUtilizationGoal, "\n") 498 } 499 } 500 501 // revise updates the assist ratio during the GC cycle to account for 502 // improved estimates. This should be called either under STW or 503 // whenever memstats.heap_scan, memstats.heap_live, or 504 // memstats.next_gc is updated (with mheap_.lock held). 505 // 506 // It should only be called when gcBlackenEnabled != 0 (because this 507 // is when assists are enabled and the necessary statistics are 508 // available). 509 func (c *gcControllerState) revise() { 510 gcpercent := gcpercent 511 if gcpercent < 0 { 512 // If GC is disabled but we're running a forced GC, 513 // act like GOGC is huge for the below calculations. 514 gcpercent = 100000 515 } 516 live := atomic.Load64(&memstats.heap_live) 517 518 var heapGoal, scanWorkExpected int64 519 if live <= memstats.next_gc { 520 // We're under the soft goal. Pace GC to complete at 521 // next_gc assuming the heap is in steady-state. 522 heapGoal = int64(memstats.next_gc) 523 524 // Compute the expected scan work remaining. 525 // 526 // This is estimated based on the expected 527 // steady-state scannable heap. For example, with 528 // GOGC=100, only half of the scannable heap is 529 // expected to be live, so that's what we target. 530 // 531 // (This is a float calculation to avoid overflowing on 532 // 100*heap_scan.) 533 scanWorkExpected = int64(float64(memstats.heap_scan) * 100 / float64(100+gcpercent)) 534 } else { 535 // We're past the soft goal. Pace GC so that in the 536 // worst case it will complete by the hard goal. 537 const maxOvershoot = 1.1 538 heapGoal = int64(float64(memstats.next_gc) * maxOvershoot) 539 540 // Compute the upper bound on the scan work remaining. 541 scanWorkExpected = int64(memstats.heap_scan) 542 } 543 544 // Compute the remaining scan work estimate. 545 // 546 // Note that we currently count allocations during GC as both 547 // scannable heap (heap_scan) and scan work completed 548 // (scanWork), so allocation will change this difference will 549 // slowly in the soft regime and not at all in the hard 550 // regime. 551 scanWorkRemaining := scanWorkExpected - c.scanWork 552 if scanWorkRemaining < 1000 { 553 // We set a somewhat arbitrary lower bound on 554 // remaining scan work since if we aim a little high, 555 // we can miss by a little. 556 // 557 // We *do* need to enforce that this is at least 1, 558 // since marking is racy and double-scanning objects 559 // may legitimately make the remaining scan work 560 // negative, even in the hard goal regime. 561 scanWorkRemaining = 1000 562 } 563 564 // Compute the heap distance remaining. 565 heapRemaining := heapGoal - int64(live) 566 if heapRemaining <= 0 { 567 // This shouldn't happen, but if it does, avoid 568 // dividing by zero or setting the assist negative. 569 heapRemaining = 1 570 } 571 572 // Compute the mutator assist ratio so by the time the mutator 573 // allocates the remaining heap bytes up to next_gc, it will 574 // have done (or stolen) the remaining amount of scan work. 575 c.assistWorkPerByte = float64(scanWorkRemaining) / float64(heapRemaining) 576 c.assistBytesPerWork = float64(heapRemaining) / float64(scanWorkRemaining) 577 } 578 579 // endCycle computes the trigger ratio for the next cycle. 580 func (c *gcControllerState) endCycle() float64 { 581 if work.userForced { 582 // Forced GC means this cycle didn't start at the 583 // trigger, so where it finished isn't good 584 // information about how to adjust the trigger. 585 // Just leave it where it is. 586 return memstats.triggerRatio 587 } 588 589 // Proportional response gain for the trigger controller. Must 590 // be in [0, 1]. Lower values smooth out transient effects but 591 // take longer to respond to phase changes. Higher values 592 // react to phase changes quickly, but are more affected by 593 // transient changes. Values near 1 may be unstable. 594 const triggerGain = 0.5 595 596 // Compute next cycle trigger ratio. First, this computes the 597 // "error" for this cycle; that is, how far off the trigger 598 // was from what it should have been, accounting for both heap 599 // growth and GC CPU utilization. We compute the actual heap 600 // growth during this cycle and scale that by how far off from 601 // the goal CPU utilization we were (to estimate the heap 602 // growth if we had the desired CPU utilization). The 603 // difference between this estimate and the GOGC-based goal 604 // heap growth is the error. 605 goalGrowthRatio := float64(gcpercent) / 100 606 actualGrowthRatio := float64(memstats.heap_live)/float64(memstats.heap_marked) - 1 607 assistDuration := nanotime() - c.markStartTime 608 609 // Assume background mark hit its utilization goal. 610 utilization := gcBackgroundUtilization 611 // Add assist utilization; avoid divide by zero. 612 if assistDuration > 0 { 613 utilization += float64(c.assistTime) / float64(assistDuration*int64(gomaxprocs)) 614 } 615 616 triggerError := goalGrowthRatio - memstats.triggerRatio - utilization/gcGoalUtilization*(actualGrowthRatio-memstats.triggerRatio) 617 618 // Finally, we adjust the trigger for next time by this error, 619 // damped by the proportional gain. 620 triggerRatio := memstats.triggerRatio + triggerGain*triggerError 621 622 if debug.gcpacertrace > 0 { 623 // Print controller state in terms of the design 624 // document. 625 H_m_prev := memstats.heap_marked 626 h_t := memstats.triggerRatio 627 H_T := memstats.gc_trigger 628 h_a := actualGrowthRatio 629 H_a := memstats.heap_live 630 h_g := goalGrowthRatio 631 H_g := int64(float64(H_m_prev) * (1 + h_g)) 632 u_a := utilization 633 u_g := gcGoalUtilization 634 W_a := c.scanWork 635 print("pacer: H_m_prev=", H_m_prev, 636 " h_t=", h_t, " H_T=", H_T, 637 " h_a=", h_a, " H_a=", H_a, 638 " h_g=", h_g, " H_g=", H_g, 639 " u_a=", u_a, " u_g=", u_g, 640 " W_a=", W_a, 641 " goalΔ=", goalGrowthRatio-h_t, 642 " actualΔ=", h_a-h_t, 643 " u_a/u_g=", u_a/u_g, 644 "\n") 645 } 646 647 return triggerRatio 648 } 649 650 // enlistWorker encourages another dedicated mark worker to start on 651 // another P if there are spare worker slots. It is used by putfull 652 // when more work is made available. 653 // 654 //go:nowritebarrier 655 func (c *gcControllerState) enlistWorker() { 656 // If there are idle Ps, wake one so it will run an idle worker. 657 // NOTE: This is suspected of causing deadlocks. See golang.org/issue/19112. 658 // 659 // if atomic.Load(&sched.npidle) != 0 && atomic.Load(&sched.nmspinning) == 0 { 660 // wakep() 661 // return 662 // } 663 664 // There are no idle Ps. If we need more dedicated workers, 665 // try to preempt a running P so it will switch to a worker. 666 if c.dedicatedMarkWorkersNeeded <= 0 { 667 return 668 } 669 // Pick a random other P to preempt. 670 if gomaxprocs <= 1 { 671 return 672 } 673 gp := getg() 674 if gp == nil || gp.m == nil || gp.m.p == 0 { 675 return 676 } 677 myID := gp.m.p.ptr().id 678 for tries := 0; tries < 5; tries++ { 679 id := int32(fastrandn(uint32(gomaxprocs - 1))) 680 if id >= myID { 681 id++ 682 } 683 p := allp[id] 684 if p.status != _Prunning { 685 continue 686 } 687 if preemptone(p) { 688 return 689 } 690 } 691 } 692 693 // findRunnableGCWorker returns the background mark worker for _p_ if it 694 // should be run. This must only be called when gcBlackenEnabled != 0. 695 func (c *gcControllerState) findRunnableGCWorker(_p_ *p) *g { 696 if gcBlackenEnabled == 0 { 697 throw("gcControllerState.findRunnable: blackening not enabled") 698 } 699 if _p_.gcBgMarkWorker == 0 { 700 // The mark worker associated with this P is blocked 701 // performing a mark transition. We can't run it 702 // because it may be on some other run or wait queue. 703 return nil 704 } 705 706 if !gcMarkWorkAvailable(_p_) { 707 // No work to be done right now. This can happen at 708 // the end of the mark phase when there are still 709 // assists tapering off. Don't bother running a worker 710 // now because it'll just return immediately. 711 return nil 712 } 713 714 decIfPositive := func(ptr *int64) bool { 715 if *ptr > 0 { 716 if atomic.Xaddint64(ptr, -1) >= 0 { 717 return true 718 } 719 // We lost a race 720 atomic.Xaddint64(ptr, +1) 721 } 722 return false 723 } 724 725 if decIfPositive(&c.dedicatedMarkWorkersNeeded) { 726 // This P is now dedicated to marking until the end of 727 // the concurrent mark phase. 728 _p_.gcMarkWorkerMode = gcMarkWorkerDedicatedMode 729 } else if c.fractionalUtilizationGoal == 0 { 730 // No need for fractional workers. 731 return nil 732 } else { 733 // Is this P behind on the fractional utilization 734 // goal? 735 // 736 // This should be kept in sync with pollFractionalWorkerExit. 737 delta := nanotime() - gcController.markStartTime 738 if delta > 0 && float64(_p_.gcFractionalMarkTime)/float64(delta) > c.fractionalUtilizationGoal { 739 // Nope. No need to run a fractional worker. 740 return nil 741 } 742 // Run a fractional worker. 743 _p_.gcMarkWorkerMode = gcMarkWorkerFractionalMode 744 } 745 746 // Run the background mark worker 747 gp := _p_.gcBgMarkWorker.ptr() 748 casgstatus(gp, _Gwaiting, _Grunnable) 749 if trace.enabled { 750 traceGoUnpark(gp, 0) 751 } 752 return gp 753 } 754 755 // pollFractionalWorkerExit returns true if a fractional mark worker 756 // should self-preempt. It assumes it is called from the fractional 757 // worker. 758 func pollFractionalWorkerExit() bool { 759 // This should be kept in sync with the fractional worker 760 // scheduler logic in findRunnableGCWorker. 761 now := nanotime() 762 delta := now - gcController.markStartTime 763 if delta <= 0 { 764 return true 765 } 766 p := getg().m.p.ptr() 767 selfTime := p.gcFractionalMarkTime + (now - p.gcMarkWorkerStartTime) 768 // Add some slack to the utilization goal so that the 769 // fractional worker isn't behind again the instant it exits. 770 return float64(selfTime)/float64(delta) > 1.2*gcController.fractionalUtilizationGoal 771 } 772 773 // gcSetTriggerRatio sets the trigger ratio and updates everything 774 // derived from it: the absolute trigger, the heap goal, mark pacing, 775 // and sweep pacing. 776 // 777 // This can be called any time. If GC is the in the middle of a 778 // concurrent phase, it will adjust the pacing of that phase. 779 // 780 // This depends on gcpercent, memstats.heap_marked, and 781 // memstats.heap_live. These must be up to date. 782 // 783 // mheap_.lock must be held or the world must be stopped. 784 func gcSetTriggerRatio(triggerRatio float64) { 785 // Set the trigger ratio, capped to reasonable bounds. 786 if triggerRatio < 0 { 787 // This can happen if the mutator is allocating very 788 // quickly or the GC is scanning very slowly. 789 triggerRatio = 0 790 } else if gcpercent >= 0 { 791 // Ensure there's always a little margin so that the 792 // mutator assist ratio isn't infinity. 793 maxTriggerRatio := 0.95 * float64(gcpercent) / 100 794 if triggerRatio > maxTriggerRatio { 795 triggerRatio = maxTriggerRatio 796 } 797 } 798 memstats.triggerRatio = triggerRatio 799 800 // Compute the absolute GC trigger from the trigger ratio. 801 // 802 // We trigger the next GC cycle when the allocated heap has 803 // grown by the trigger ratio over the marked heap size. 804 trigger := ^uint64(0) 805 if gcpercent >= 0 { 806 trigger = uint64(float64(memstats.heap_marked) * (1 + triggerRatio)) 807 // Don't trigger below the minimum heap size. 808 minTrigger := heapminimum 809 if !gosweepdone() { 810 // Concurrent sweep happens in the heap growth 811 // from heap_live to gc_trigger, so ensure 812 // that concurrent sweep has some heap growth 813 // in which to perform sweeping before we 814 // start the next GC cycle. 815 sweepMin := atomic.Load64(&memstats.heap_live) + sweepMinHeapDistance*uint64(gcpercent)/100 816 if sweepMin > minTrigger { 817 minTrigger = sweepMin 818 } 819 } 820 if trigger < minTrigger { 821 trigger = minTrigger 822 } 823 if int64(trigger) < 0 { 824 print("runtime: next_gc=", memstats.next_gc, " heap_marked=", memstats.heap_marked, " heap_live=", memstats.heap_live, " initialHeapLive=", work.initialHeapLive, "triggerRatio=", triggerRatio, " minTrigger=", minTrigger, "\n") 825 throw("gc_trigger underflow") 826 } 827 } 828 memstats.gc_trigger = trigger 829 830 // Compute the next GC goal, which is when the allocated heap 831 // has grown by GOGC/100 over the heap marked by the last 832 // cycle. 833 goal := ^uint64(0) 834 if gcpercent >= 0 { 835 goal = memstats.heap_marked + memstats.heap_marked*uint64(gcpercent)/100 836 if goal < trigger { 837 // The trigger ratio is always less than GOGC/100, but 838 // other bounds on the trigger may have raised it. 839 // Push up the goal, too. 840 goal = trigger 841 } 842 } 843 memstats.next_gc = goal 844 if trace.enabled { 845 traceNextGC() 846 } 847 848 // Update mark pacing. 849 if gcphase != _GCoff { 850 gcController.revise() 851 } 852 853 // Update sweep pacing. 854 if gosweepdone() { 855 mheap_.sweepPagesPerByte = 0 856 } else { 857 // Concurrent sweep needs to sweep all of the in-use 858 // pages by the time the allocated heap reaches the GC 859 // trigger. Compute the ratio of in-use pages to sweep 860 // per byte allocated, accounting for the fact that 861 // some might already be swept. 862 heapLiveBasis := atomic.Load64(&memstats.heap_live) 863 heapDistance := int64(trigger) - int64(heapLiveBasis) 864 // Add a little margin so rounding errors and 865 // concurrent sweep are less likely to leave pages 866 // unswept when GC starts. 867 heapDistance -= 1024 * 1024 868 if heapDistance < _PageSize { 869 // Avoid setting the sweep ratio extremely high 870 heapDistance = _PageSize 871 } 872 pagesSwept := atomic.Load64(&mheap_.pagesSwept) 873 sweepDistancePages := int64(mheap_.pagesInUse) - int64(pagesSwept) 874 if sweepDistancePages <= 0 { 875 mheap_.sweepPagesPerByte = 0 876 } else { 877 mheap_.sweepPagesPerByte = float64(sweepDistancePages) / float64(heapDistance) 878 mheap_.sweepHeapLiveBasis = heapLiveBasis 879 // Write pagesSweptBasis last, since this 880 // signals concurrent sweeps to recompute 881 // their debt. 882 atomic.Store64(&mheap_.pagesSweptBasis, pagesSwept) 883 } 884 } 885 } 886 887 // gcGoalUtilization is the goal CPU utilization for 888 // marking as a fraction of GOMAXPROCS. 889 const gcGoalUtilization = 0.30 890 891 // gcBackgroundUtilization is the fixed CPU utilization for background 892 // marking. It must be <= gcGoalUtilization. The difference between 893 // gcGoalUtilization and gcBackgroundUtilization will be made up by 894 // mark assists. The scheduler will aim to use within 50% of this 895 // goal. 896 // 897 // Setting this to < gcGoalUtilization avoids saturating the trigger 898 // feedback controller when there are no assists, which allows it to 899 // better control CPU and heap growth. However, the larger the gap, 900 // the more mutator assists are expected to happen, which impact 901 // mutator latency. 902 const gcBackgroundUtilization = 0.25 903 904 // gcCreditSlack is the amount of scan work credit that can can 905 // accumulate locally before updating gcController.scanWork and, 906 // optionally, gcController.bgScanCredit. Lower values give a more 907 // accurate assist ratio and make it more likely that assists will 908 // successfully steal background credit. Higher values reduce memory 909 // contention. 910 const gcCreditSlack = 2000 911 912 // gcAssistTimeSlack is the nanoseconds of mutator assist time that 913 // can accumulate on a P before updating gcController.assistTime. 914 const gcAssistTimeSlack = 5000 915 916 // gcOverAssistWork determines how many extra units of scan work a GC 917 // assist does when an assist happens. This amortizes the cost of an 918 // assist by pre-paying for this many bytes of future allocations. 919 const gcOverAssistWork = 64 << 10 920 921 var work struct { 922 full lfstack // lock-free list of full blocks workbuf 923 empty lfstack // lock-free list of empty blocks workbuf 924 pad0 [sys.CacheLineSize]uint8 // prevents false-sharing between full/empty and nproc/nwait 925 926 wbufSpans struct { 927 lock mutex 928 // free is a list of spans dedicated to workbufs, but 929 // that don't currently contain any workbufs. 930 free mSpanList 931 // busy is a list of all spans containing workbufs on 932 // one of the workbuf lists. 933 busy mSpanList 934 } 935 936 // Restore 64-bit alignment on 32-bit. 937 _ uint32 938 939 // bytesMarked is the number of bytes marked this cycle. This 940 // includes bytes blackened in scanned objects, noscan objects 941 // that go straight to black, and permagrey objects scanned by 942 // markroot during the concurrent scan phase. This is updated 943 // atomically during the cycle. Updates may be batched 944 // arbitrarily, since the value is only read at the end of the 945 // cycle. 946 // 947 // Because of benign races during marking, this number may not 948 // be the exact number of marked bytes, but it should be very 949 // close. 950 // 951 // Put this field here because it needs 64-bit atomic access 952 // (and thus 8-byte alignment even on 32-bit architectures). 953 bytesMarked uint64 954 955 markrootNext uint32 // next markroot job 956 markrootJobs uint32 // number of markroot jobs 957 958 nproc uint32 959 tstart int64 960 nwait uint32 961 ndone uint32 962 alldone note 963 964 // helperDrainBlock indicates that GC mark termination helpers 965 // should pass gcDrainBlock to gcDrain to block in the 966 // getfull() barrier. Otherwise, they should pass gcDrainNoBlock. 967 // 968 // TODO: This is a temporary fallback to work around races 969 // that cause early mark termination. 970 helperDrainBlock bool 971 972 // Number of roots of various root types. Set by gcMarkRootPrepare. 973 nFlushCacheRoots int 974 nDataRoots, nBSSRoots, nSpanRoots, nStackRoots int 975 976 // markrootDone indicates that roots have been marked at least 977 // once during the current GC cycle. This is checked by root 978 // marking operations that have to happen only during the 979 // first root marking pass, whether that's during the 980 // concurrent mark phase in current GC or mark termination in 981 // STW GC. 982 markrootDone bool 983 984 // Each type of GC state transition is protected by a lock. 985 // Since multiple threads can simultaneously detect the state 986 // transition condition, any thread that detects a transition 987 // condition must acquire the appropriate transition lock, 988 // re-check the transition condition and return if it no 989 // longer holds or perform the transition if it does. 990 // Likewise, any transition must invalidate the transition 991 // condition before releasing the lock. This ensures that each 992 // transition is performed by exactly one thread and threads 993 // that need the transition to happen block until it has 994 // happened. 995 // 996 // startSema protects the transition from "off" to mark or 997 // mark termination. 998 startSema uint32 999 // markDoneSema protects transitions from mark 1 to mark 2 and 1000 // from mark 2 to mark termination. 1001 markDoneSema uint32 1002 1003 bgMarkReady note // signal background mark worker has started 1004 bgMarkDone uint32 // cas to 1 when at a background mark completion point 1005 // Background mark completion signaling 1006 1007 // mode is the concurrency mode of the current GC cycle. 1008 mode gcMode 1009 1010 // userForced indicates the current GC cycle was forced by an 1011 // explicit user call. 1012 userForced bool 1013 1014 // totaltime is the CPU nanoseconds spent in GC since the 1015 // program started if debug.gctrace > 0. 1016 totaltime int64 1017 1018 // initialHeapLive is the value of memstats.heap_live at the 1019 // beginning of this GC cycle. 1020 initialHeapLive uint64 1021 1022 // assistQueue is a queue of assists that are blocked because 1023 // there was neither enough credit to steal or enough work to 1024 // do. 1025 assistQueue struct { 1026 lock mutex 1027 head, tail guintptr 1028 } 1029 1030 // sweepWaiters is a list of blocked goroutines to wake when 1031 // we transition from mark termination to sweep. 1032 sweepWaiters struct { 1033 lock mutex 1034 head guintptr 1035 } 1036 1037 // cycles is the number of completed GC cycles, where a GC 1038 // cycle is sweep termination, mark, mark termination, and 1039 // sweep. This differs from memstats.numgc, which is 1040 // incremented at mark termination. 1041 cycles uint32 1042 1043 // Timing/utilization stats for this cycle. 1044 stwprocs, maxprocs int32 1045 tSweepTerm, tMark, tMarkTerm, tEnd int64 // nanotime() of phase start 1046 1047 pauseNS int64 // total STW time this cycle 1048 pauseStart int64 // nanotime() of last STW 1049 1050 // debug.gctrace heap sizes for this cycle. 1051 heap0, heap1, heap2, heapGoal uint64 1052 } 1053 1054 // GC runs a garbage collection and blocks the caller until the 1055 // garbage collection is complete. It may also block the entire 1056 // program. 1057 func GC() { 1058 // We consider a cycle to be: sweep termination, mark, mark 1059 // termination, and sweep. This function shouldn't return 1060 // until a full cycle has been completed, from beginning to 1061 // end. Hence, we always want to finish up the current cycle 1062 // and start a new one. That means: 1063 // 1064 // 1. In sweep termination, mark, or mark termination of cycle 1065 // N, wait until mark termination N completes and transitions 1066 // to sweep N. 1067 // 1068 // 2. In sweep N, help with sweep N. 1069 // 1070 // At this point we can begin a full cycle N+1. 1071 // 1072 // 3. Trigger cycle N+1 by starting sweep termination N+1. 1073 // 1074 // 4. Wait for mark termination N+1 to complete. 1075 // 1076 // 5. Help with sweep N+1 until it's done. 1077 // 1078 // This all has to be written to deal with the fact that the 1079 // GC may move ahead on its own. For example, when we block 1080 // until mark termination N, we may wake up in cycle N+2. 1081 1082 // Wait until the current sweep termination, mark, and mark 1083 // termination complete. 1084 n := atomic.Load(&work.cycles) 1085 gcWaitOnMark(n) 1086 1087 // We're now in sweep N or later. Trigger GC cycle N+1, which 1088 // will first finish sweep N if necessary and then enter sweep 1089 // termination N+1. 1090 gcStart(gcBackgroundMode, gcTrigger{kind: gcTriggerCycle, n: n + 1}) 1091 1092 // Wait for mark termination N+1 to complete. 1093 gcWaitOnMark(n + 1) 1094 1095 // Finish sweep N+1 before returning. We do this both to 1096 // complete the cycle and because runtime.GC() is often used 1097 // as part of tests and benchmarks to get the system into a 1098 // relatively stable and isolated state. 1099 for atomic.Load(&work.cycles) == n+1 && gosweepone() != ^uintptr(0) { 1100 sweep.nbgsweep++ 1101 Gosched() 1102 } 1103 1104 // Callers may assume that the heap profile reflects the 1105 // just-completed cycle when this returns (historically this 1106 // happened because this was a STW GC), but right now the 1107 // profile still reflects mark termination N, not N+1. 1108 // 1109 // As soon as all of the sweep frees from cycle N+1 are done, 1110 // we can go ahead and publish the heap profile. 1111 // 1112 // First, wait for sweeping to finish. (We know there are no 1113 // more spans on the sweep queue, but we may be concurrently 1114 // sweeping spans, so we have to wait.) 1115 for atomic.Load(&work.cycles) == n+1 && atomic.Load(&mheap_.sweepers) != 0 { 1116 Gosched() 1117 } 1118 1119 // Now we're really done with sweeping, so we can publish the 1120 // stable heap profile. Only do this if we haven't already hit 1121 // another mark termination. 1122 mp := acquirem() 1123 cycle := atomic.Load(&work.cycles) 1124 if cycle == n+1 || (gcphase == _GCmark && cycle == n+2) { 1125 mProf_PostSweep() 1126 } 1127 releasem(mp) 1128 } 1129 1130 // gcWaitOnMark blocks until GC finishes the Nth mark phase. If GC has 1131 // already completed this mark phase, it returns immediately. 1132 func gcWaitOnMark(n uint32) { 1133 for { 1134 // Disable phase transitions. 1135 lock(&work.sweepWaiters.lock) 1136 nMarks := atomic.Load(&work.cycles) 1137 if gcphase != _GCmark { 1138 // We've already completed this cycle's mark. 1139 nMarks++ 1140 } 1141 if nMarks > n { 1142 // We're done. 1143 unlock(&work.sweepWaiters.lock) 1144 return 1145 } 1146 1147 // Wait until sweep termination, mark, and mark 1148 // termination of cycle N complete. 1149 gp := getg() 1150 gp.schedlink = work.sweepWaiters.head 1151 work.sweepWaiters.head.set(gp) 1152 goparkunlock(&work.sweepWaiters.lock, waitReasonWaitForGCCycle, traceEvGoBlock, 1) 1153 } 1154 } 1155 1156 // gcMode indicates how concurrent a GC cycle should be. 1157 type gcMode int 1158 1159 const ( 1160 gcBackgroundMode gcMode = iota // concurrent GC and sweep 1161 gcForceMode // stop-the-world GC now, concurrent sweep 1162 gcForceBlockMode // stop-the-world GC now and STW sweep (forced by user) 1163 ) 1164 1165 // A gcTrigger is a predicate for starting a GC cycle. Specifically, 1166 // it is an exit condition for the _GCoff phase. 1167 type gcTrigger struct { 1168 kind gcTriggerKind 1169 now int64 // gcTriggerTime: current time 1170 n uint32 // gcTriggerCycle: cycle number to start 1171 } 1172 1173 type gcTriggerKind int 1174 1175 const ( 1176 // gcTriggerAlways indicates that a cycle should be started 1177 // unconditionally, even if GOGC is off or we're in a cycle 1178 // right now. This cannot be consolidated with other cycles. 1179 gcTriggerAlways gcTriggerKind = iota 1180 1181 // gcTriggerHeap indicates that a cycle should be started when 1182 // the heap size reaches the trigger heap size computed by the 1183 // controller. 1184 gcTriggerHeap 1185 1186 // gcTriggerTime indicates that a cycle should be started when 1187 // it's been more than forcegcperiod nanoseconds since the 1188 // previous GC cycle. 1189 gcTriggerTime 1190 1191 // gcTriggerCycle indicates that a cycle should be started if 1192 // we have not yet started cycle number gcTrigger.n (relative 1193 // to work.cycles). 1194 gcTriggerCycle 1195 ) 1196 1197 // test returns true if the trigger condition is satisfied, meaning 1198 // that the exit condition for the _GCoff phase has been met. The exit 1199 // condition should be tested when allocating. 1200 func (t gcTrigger) test() bool { 1201 if !memstats.enablegc || panicking != 0 { 1202 return false 1203 } 1204 if t.kind == gcTriggerAlways { 1205 return true 1206 } 1207 if gcphase != _GCoff { 1208 return false 1209 } 1210 switch t.kind { 1211 case gcTriggerHeap: 1212 // Non-atomic access to heap_live for performance. If 1213 // we are going to trigger on this, this thread just 1214 // atomically wrote heap_live anyway and we'll see our 1215 // own write. 1216 return memstats.heap_live >= memstats.gc_trigger 1217 case gcTriggerTime: 1218 if gcpercent < 0 { 1219 return false 1220 } 1221 lastgc := int64(atomic.Load64(&memstats.last_gc_nanotime)) 1222 return lastgc != 0 && t.now-lastgc > forcegcperiod 1223 case gcTriggerCycle: 1224 // t.n > work.cycles, but accounting for wraparound. 1225 return int32(t.n-work.cycles) > 0 1226 } 1227 return true 1228 } 1229 1230 // gcStart transitions the GC from _GCoff to _GCmark (if 1231 // !mode.stwMark) or _GCmarktermination (if mode.stwMark) by 1232 // performing sweep termination and GC initialization. 1233 // 1234 // This may return without performing this transition in some cases, 1235 // such as when called on a system stack or with locks held. 1236 func gcStart(mode gcMode, trigger gcTrigger) { 1237 // Since this is called from malloc and malloc is called in 1238 // the guts of a number of libraries that might be holding 1239 // locks, don't attempt to start GC in non-preemptible or 1240 // potentially unstable situations. 1241 mp := acquirem() 1242 if gp := getg(); gp == mp.g0 || mp.locks > 1 || mp.preemptoff != "" { 1243 releasem(mp) 1244 return 1245 } 1246 releasem(mp) 1247 mp = nil 1248 1249 // Pick up the remaining unswept/not being swept spans concurrently 1250 // 1251 // This shouldn't happen if we're being invoked in background 1252 // mode since proportional sweep should have just finished 1253 // sweeping everything, but rounding errors, etc, may leave a 1254 // few spans unswept. In forced mode, this is necessary since 1255 // GC can be forced at any point in the sweeping cycle. 1256 // 1257 // We check the transition condition continuously here in case 1258 // this G gets delayed in to the next GC cycle. 1259 for trigger.test() && gosweepone() != ^uintptr(0) { 1260 sweep.nbgsweep++ 1261 } 1262 1263 // Perform GC initialization and the sweep termination 1264 // transition. 1265 semacquire(&work.startSema) 1266 // Re-check transition condition under transition lock. 1267 if !trigger.test() { 1268 semrelease(&work.startSema) 1269 return 1270 } 1271 1272 // For stats, check if this GC was forced by the user. 1273 work.userForced = trigger.kind == gcTriggerAlways || trigger.kind == gcTriggerCycle 1274 1275 // In gcstoptheworld debug mode, upgrade the mode accordingly. 1276 // We do this after re-checking the transition condition so 1277 // that multiple goroutines that detect the heap trigger don't 1278 // start multiple STW GCs. 1279 if mode == gcBackgroundMode { 1280 if debug.gcstoptheworld == 1 { 1281 mode = gcForceMode 1282 } else if debug.gcstoptheworld == 2 { 1283 mode = gcForceBlockMode 1284 } 1285 } 1286 1287 // Ok, we're doing it! Stop everybody else 1288 semacquire(&worldsema) 1289 1290 if trace.enabled { 1291 traceGCStart() 1292 } 1293 1294 if mode == gcBackgroundMode { 1295 gcBgMarkStartWorkers() 1296 } 1297 1298 gcResetMarkState() 1299 1300 work.stwprocs, work.maxprocs = gomaxprocs, gomaxprocs 1301 if work.stwprocs > ncpu { 1302 // This is used to compute CPU time of the STW phases, 1303 // so it can't be more than ncpu, even if GOMAXPROCS is. 1304 work.stwprocs = ncpu 1305 } 1306 work.heap0 = atomic.Load64(&memstats.heap_live) 1307 work.pauseNS = 0 1308 work.mode = mode 1309 1310 now := nanotime() 1311 work.tSweepTerm = now 1312 work.pauseStart = now 1313 if trace.enabled { 1314 traceGCSTWStart(1) 1315 } 1316 systemstack(stopTheWorldWithSema) 1317 // Finish sweep before we start concurrent scan. 1318 systemstack(func() { 1319 finishsweep_m() 1320 }) 1321 // clearpools before we start the GC. If we wait they memory will not be 1322 // reclaimed until the next GC cycle. 1323 clearpools() 1324 1325 work.cycles++ 1326 if mode == gcBackgroundMode { // Do as much work concurrently as possible 1327 gcController.startCycle() 1328 work.heapGoal = memstats.next_gc 1329 1330 // Enter concurrent mark phase and enable 1331 // write barriers. 1332 // 1333 // Because the world is stopped, all Ps will 1334 // observe that write barriers are enabled by 1335 // the time we start the world and begin 1336 // scanning. 1337 // 1338 // Write barriers must be enabled before assists are 1339 // enabled because they must be enabled before 1340 // any non-leaf heap objects are marked. Since 1341 // allocations are blocked until assists can 1342 // happen, we want enable assists as early as 1343 // possible. 1344 setGCPhase(_GCmark) 1345 1346 gcBgMarkPrepare() // Must happen before assist enable. 1347 gcMarkRootPrepare() 1348 1349 // Mark all active tinyalloc blocks. Since we're 1350 // allocating from these, they need to be black like 1351 // other allocations. The alternative is to blacken 1352 // the tiny block on every allocation from it, which 1353 // would slow down the tiny allocator. 1354 gcMarkTinyAllocs() 1355 1356 // At this point all Ps have enabled the write 1357 // barrier, thus maintaining the no white to 1358 // black invariant. Enable mutator assists to 1359 // put back-pressure on fast allocating 1360 // mutators. 1361 atomic.Store(&gcBlackenEnabled, 1) 1362 1363 // Assists and workers can start the moment we start 1364 // the world. 1365 gcController.markStartTime = now 1366 1367 // Concurrent mark. 1368 systemstack(func() { 1369 now = startTheWorldWithSema(trace.enabled) 1370 }) 1371 work.pauseNS += now - work.pauseStart 1372 work.tMark = now 1373 } else { 1374 if trace.enabled { 1375 // Switch to mark termination STW. 1376 traceGCSTWDone() 1377 traceGCSTWStart(0) 1378 } 1379 t := nanotime() 1380 work.tMark, work.tMarkTerm = t, t 1381 work.heapGoal = work.heap0 1382 1383 // Perform mark termination. This will restart the world. 1384 gcMarkTermination(memstats.triggerRatio) 1385 } 1386 1387 semrelease(&work.startSema) 1388 } 1389 1390 // gcMarkDone transitions the GC from mark 1 to mark 2 and from mark 2 1391 // to mark termination. 1392 // 1393 // This should be called when all mark work has been drained. In mark 1394 // 1, this includes all root marking jobs, global work buffers, and 1395 // active work buffers in assists and background workers; however, 1396 // work may still be cached in per-P work buffers. In mark 2, per-P 1397 // caches are disabled. 1398 // 1399 // The calling context must be preemptible. 1400 // 1401 // Note that it is explicitly okay to have write barriers in this 1402 // function because completion of concurrent mark is best-effort 1403 // anyway. Any work created by write barriers here will be cleaned up 1404 // by mark termination. 1405 func gcMarkDone() { 1406 top: 1407 semacquire(&work.markDoneSema) 1408 1409 // Re-check transition condition under transition lock. 1410 if !(gcphase == _GCmark && work.nwait == work.nproc && !gcMarkWorkAvailable(nil)) { 1411 semrelease(&work.markDoneSema) 1412 return 1413 } 1414 1415 // Disallow starting new workers so that any remaining workers 1416 // in the current mark phase will drain out. 1417 // 1418 // TODO(austin): Should dedicated workers keep an eye on this 1419 // and exit gcDrain promptly? 1420 atomic.Xaddint64(&gcController.dedicatedMarkWorkersNeeded, -0xffffffff) 1421 prevFractionalGoal := gcController.fractionalUtilizationGoal 1422 gcController.fractionalUtilizationGoal = 0 1423 1424 if !gcBlackenPromptly { 1425 // Transition from mark 1 to mark 2. 1426 // 1427 // The global work list is empty, but there can still be work 1428 // sitting in the per-P work caches. 1429 // Flush and disable work caches. 1430 1431 // Disallow caching workbufs and indicate that we're in mark 2. 1432 gcBlackenPromptly = true 1433 1434 // Prevent completion of mark 2 until we've flushed 1435 // cached workbufs. 1436 atomic.Xadd(&work.nwait, -1) 1437 1438 // GC is set up for mark 2. Let Gs blocked on the 1439 // transition lock go while we flush caches. 1440 semrelease(&work.markDoneSema) 1441 1442 systemstack(func() { 1443 // Flush all currently cached workbufs and 1444 // ensure all Ps see gcBlackenPromptly. This 1445 // also blocks until any remaining mark 1 1446 // workers have exited their loop so we can 1447 // start new mark 2 workers. 1448 forEachP(func(_p_ *p) { 1449 wbBufFlush1(_p_) 1450 _p_.gcw.dispose() 1451 }) 1452 }) 1453 1454 // Check that roots are marked. We should be able to 1455 // do this before the forEachP, but based on issue 1456 // #16083 there may be a (harmless) race where we can 1457 // enter mark 2 while some workers are still scanning 1458 // stacks. The forEachP ensures these scans are done. 1459 // 1460 // TODO(austin): Figure out the race and fix this 1461 // properly. 1462 gcMarkRootCheck() 1463 1464 // Now we can start up mark 2 workers. 1465 atomic.Xaddint64(&gcController.dedicatedMarkWorkersNeeded, 0xffffffff) 1466 gcController.fractionalUtilizationGoal = prevFractionalGoal 1467 1468 incnwait := atomic.Xadd(&work.nwait, +1) 1469 if incnwait == work.nproc && !gcMarkWorkAvailable(nil) { 1470 // This loop will make progress because 1471 // gcBlackenPromptly is now true, so it won't 1472 // take this same "if" branch. 1473 goto top 1474 } 1475 } else { 1476 // Transition to mark termination. 1477 now := nanotime() 1478 work.tMarkTerm = now 1479 work.pauseStart = now 1480 getg().m.preemptoff = "gcing" 1481 if trace.enabled { 1482 traceGCSTWStart(0) 1483 } 1484 systemstack(stopTheWorldWithSema) 1485 // The gcphase is _GCmark, it will transition to _GCmarktermination 1486 // below. The important thing is that the wb remains active until 1487 // all marking is complete. This includes writes made by the GC. 1488 1489 // Record that one root marking pass has completed. 1490 work.markrootDone = true 1491 1492 // Disable assists and background workers. We must do 1493 // this before waking blocked assists. 1494 atomic.Store(&gcBlackenEnabled, 0) 1495 1496 // Wake all blocked assists. These will run when we 1497 // start the world again. 1498 gcWakeAllAssists() 1499 1500 // Likewise, release the transition lock. Blocked 1501 // workers and assists will run when we start the 1502 // world again. 1503 semrelease(&work.markDoneSema) 1504 1505 // endCycle depends on all gcWork cache stats being 1506 // flushed. This is ensured by mark 2. 1507 nextTriggerRatio := gcController.endCycle() 1508 1509 // Perform mark termination. This will restart the world. 1510 gcMarkTermination(nextTriggerRatio) 1511 } 1512 } 1513 1514 func gcMarkTermination(nextTriggerRatio float64) { 1515 // World is stopped. 1516 // Start marktermination which includes enabling the write barrier. 1517 atomic.Store(&gcBlackenEnabled, 0) 1518 gcBlackenPromptly = false 1519 setGCPhase(_GCmarktermination) 1520 1521 work.heap1 = memstats.heap_live 1522 startTime := nanotime() 1523 1524 mp := acquirem() 1525 mp.preemptoff = "gcing" 1526 _g_ := getg() 1527 _g_.m.traceback = 2 1528 gp := _g_.m.curg 1529 casgstatus(gp, _Grunning, _Gwaiting) 1530 gp.waitreason = waitReasonGarbageCollection 1531 1532 // Run gc on the g0 stack. We do this so that the g stack 1533 // we're currently running on will no longer change. Cuts 1534 // the root set down a bit (g0 stacks are not scanned, and 1535 // we don't need to scan gc's internal state). We also 1536 // need to switch to g0 so we can shrink the stack. 1537 systemstack(func() { 1538 gcMark(startTime) 1539 // Must return immediately. 1540 // The outer function's stack may have moved 1541 // during gcMark (it shrinks stacks, including the 1542 // outer function's stack), so we must not refer 1543 // to any of its variables. Return back to the 1544 // non-system stack to pick up the new addresses 1545 // before continuing. 1546 }) 1547 1548 systemstack(func() { 1549 work.heap2 = work.bytesMarked 1550 if debug.gccheckmark > 0 { 1551 // Run a full stop-the-world mark using checkmark bits, 1552 // to check that we didn't forget to mark anything during 1553 // the concurrent mark process. 1554 gcResetMarkState() 1555 initCheckmarks() 1556 gcMark(startTime) 1557 clearCheckmarks() 1558 } 1559 1560 // marking is complete so we can turn the write barrier off 1561 setGCPhase(_GCoff) 1562 gcSweep(work.mode) 1563 1564 if debug.gctrace > 1 { 1565 startTime = nanotime() 1566 // The g stacks have been scanned so 1567 // they have gcscanvalid==true and gcworkdone==true. 1568 // Reset these so that all stacks will be rescanned. 1569 gcResetMarkState() 1570 finishsweep_m() 1571 1572 // Still in STW but gcphase is _GCoff, reset to _GCmarktermination 1573 // At this point all objects will be found during the gcMark which 1574 // does a complete STW mark and object scan. 1575 setGCPhase(_GCmarktermination) 1576 gcMark(startTime) 1577 setGCPhase(_GCoff) // marking is done, turn off wb. 1578 gcSweep(work.mode) 1579 } 1580 }) 1581 1582 _g_.m.traceback = 0 1583 casgstatus(gp, _Gwaiting, _Grunning) 1584 1585 if trace.enabled { 1586 traceGCDone() 1587 } 1588 1589 // all done 1590 mp.preemptoff = "" 1591 1592 if gcphase != _GCoff { 1593 throw("gc done but gcphase != _GCoff") 1594 } 1595 1596 // Update GC trigger and pacing for the next cycle. 1597 gcSetTriggerRatio(nextTriggerRatio) 1598 1599 // Update timing memstats 1600 now := nanotime() 1601 sec, nsec, _ := time_now() 1602 unixNow := sec*1e9 + int64(nsec) 1603 work.pauseNS += now - work.pauseStart 1604 work.tEnd = now 1605 atomic.Store64(&memstats.last_gc_unix, uint64(unixNow)) // must be Unix time to make sense to user 1606 atomic.Store64(&memstats.last_gc_nanotime, uint64(now)) // monotonic time for us 1607 memstats.pause_ns[memstats.numgc%uint32(len(memstats.pause_ns))] = uint64(work.pauseNS) 1608 memstats.pause_end[memstats.numgc%uint32(len(memstats.pause_end))] = uint64(unixNow) 1609 memstats.pause_total_ns += uint64(work.pauseNS) 1610 1611 // Update work.totaltime. 1612 sweepTermCpu := int64(work.stwprocs) * (work.tMark - work.tSweepTerm) 1613 // We report idle marking time below, but omit it from the 1614 // overall utilization here since it's "free". 1615 markCpu := gcController.assistTime + gcController.dedicatedMarkTime + gcController.fractionalMarkTime 1616 markTermCpu := int64(work.stwprocs) * (work.tEnd - work.tMarkTerm) 1617 cycleCpu := sweepTermCpu + markCpu + markTermCpu 1618 work.totaltime += cycleCpu 1619 1620 // Compute overall GC CPU utilization. 1621 totalCpu := sched.totaltime + (now-sched.procresizetime)*int64(gomaxprocs) 1622 memstats.gc_cpu_fraction = float64(work.totaltime) / float64(totalCpu) 1623 1624 // Reset sweep state. 1625 sweep.nbgsweep = 0 1626 sweep.npausesweep = 0 1627 1628 if work.userForced { 1629 memstats.numforcedgc++ 1630 } 1631 1632 // Bump GC cycle count and wake goroutines waiting on sweep. 1633 lock(&work.sweepWaiters.lock) 1634 memstats.numgc++ 1635 injectglist(work.sweepWaiters.head.ptr()) 1636 work.sweepWaiters.head = 0 1637 unlock(&work.sweepWaiters.lock) 1638 1639 // Finish the current heap profiling cycle and start a new 1640 // heap profiling cycle. We do this before starting the world 1641 // so events don't leak into the wrong cycle. 1642 mProf_NextCycle() 1643 1644 systemstack(func() { startTheWorldWithSema(true) }) 1645 1646 // Flush the heap profile so we can start a new cycle next GC. 1647 // This is relatively expensive, so we don't do it with the 1648 // world stopped. 1649 mProf_Flush() 1650 1651 // Prepare workbufs for freeing by the sweeper. We do this 1652 // asynchronously because it can take non-trivial time. 1653 prepareFreeWorkbufs() 1654 1655 // Free stack spans. This must be done between GC cycles. 1656 systemstack(freeStackSpans) 1657 1658 // Print gctrace before dropping worldsema. As soon as we drop 1659 // worldsema another cycle could start and smash the stats 1660 // we're trying to print. 1661 if debug.gctrace > 0 { 1662 util := int(memstats.gc_cpu_fraction * 100) 1663 1664 var sbuf [24]byte 1665 printlock() 1666 print("gc ", memstats.numgc, 1667 " @", string(itoaDiv(sbuf[:], uint64(work.tSweepTerm-runtimeInitTime)/1e6, 3)), "s ", 1668 util, "%: ") 1669 prev := work.tSweepTerm 1670 for i, ns := range []int64{work.tMark, work.tMarkTerm, work.tEnd} { 1671 if i != 0 { 1672 print("+") 1673 } 1674 print(string(fmtNSAsMS(sbuf[:], uint64(ns-prev)))) 1675 prev = ns 1676 } 1677 print(" ms clock, ") 1678 for i, ns := range []int64{sweepTermCpu, gcController.assistTime, gcController.dedicatedMarkTime + gcController.fractionalMarkTime, gcController.idleMarkTime, markTermCpu} { 1679 if i == 2 || i == 3 { 1680 // Separate mark time components with /. 1681 print("/") 1682 } else if i != 0 { 1683 print("+") 1684 } 1685 print(string(fmtNSAsMS(sbuf[:], uint64(ns)))) 1686 } 1687 print(" ms cpu, ", 1688 work.heap0>>20, "->", work.heap1>>20, "->", work.heap2>>20, " MB, ", 1689 work.heapGoal>>20, " MB goal, ", 1690 work.maxprocs, " P") 1691 if work.userForced { 1692 print(" (forced)") 1693 } 1694 print("\n") 1695 printunlock() 1696 } 1697 1698 semrelease(&worldsema) 1699 // Careful: another GC cycle may start now. 1700 1701 releasem(mp) 1702 mp = nil 1703 1704 // now that gc is done, kick off finalizer thread if needed 1705 if !concurrentSweep { 1706 // give the queued finalizers, if any, a chance to run 1707 Gosched() 1708 } 1709 } 1710 1711 // gcBgMarkStartWorkers prepares background mark worker goroutines. 1712 // These goroutines will not run until the mark phase, but they must 1713 // be started while the work is not stopped and from a regular G 1714 // stack. The caller must hold worldsema. 1715 func gcBgMarkStartWorkers() { 1716 // Background marking is performed by per-P G's. Ensure that 1717 // each P has a background GC G. 1718 for _, p := range allp { 1719 if p.gcBgMarkWorker == 0 { 1720 go gcBgMarkWorker(p) 1721 notetsleepg(&work.bgMarkReady, -1) 1722 noteclear(&work.bgMarkReady) 1723 } 1724 } 1725 } 1726 1727 // gcBgMarkPrepare sets up state for background marking. 1728 // Mutator assists must not yet be enabled. 1729 func gcBgMarkPrepare() { 1730 // Background marking will stop when the work queues are empty 1731 // and there are no more workers (note that, since this is 1732 // concurrent, this may be a transient state, but mark 1733 // termination will clean it up). Between background workers 1734 // and assists, we don't really know how many workers there 1735 // will be, so we pretend to have an arbitrarily large number 1736 // of workers, almost all of which are "waiting". While a 1737 // worker is working it decrements nwait. If nproc == nwait, 1738 // there are no workers. 1739 work.nproc = ^uint32(0) 1740 work.nwait = ^uint32(0) 1741 } 1742 1743 func gcBgMarkWorker(_p_ *p) { 1744 gp := getg() 1745 1746 type parkInfo struct { 1747 m muintptr // Release this m on park. 1748 attach puintptr // If non-nil, attach to this p on park. 1749 } 1750 // We pass park to a gopark unlock function, so it can't be on 1751 // the stack (see gopark). Prevent deadlock from recursively 1752 // starting GC by disabling preemption. 1753 gp.m.preemptoff = "GC worker init" 1754 park := new(parkInfo) 1755 gp.m.preemptoff = "" 1756 1757 park.m.set(acquirem()) 1758 park.attach.set(_p_) 1759 // Inform gcBgMarkStartWorkers that this worker is ready. 1760 // After this point, the background mark worker is scheduled 1761 // cooperatively by gcController.findRunnable. Hence, it must 1762 // never be preempted, as this would put it into _Grunnable 1763 // and put it on a run queue. Instead, when the preempt flag 1764 // is set, this puts itself into _Gwaiting to be woken up by 1765 // gcController.findRunnable at the appropriate time. 1766 notewakeup(&work.bgMarkReady) 1767 1768 for { 1769 // Go to sleep until woken by gcController.findRunnable. 1770 // We can't releasem yet since even the call to gopark 1771 // may be preempted. 1772 gopark(func(g *g, parkp unsafe.Pointer) bool { 1773 park := (*parkInfo)(parkp) 1774 1775 // The worker G is no longer running, so it's 1776 // now safe to allow preemption. 1777 releasem(park.m.ptr()) 1778 1779 // If the worker isn't attached to its P, 1780 // attach now. During initialization and after 1781 // a phase change, the worker may have been 1782 // running on a different P. As soon as we 1783 // attach, the owner P may schedule the 1784 // worker, so this must be done after the G is 1785 // stopped. 1786 if park.attach != 0 { 1787 p := park.attach.ptr() 1788 park.attach.set(nil) 1789 // cas the worker because we may be 1790 // racing with a new worker starting 1791 // on this P. 1792 if !p.gcBgMarkWorker.cas(0, guintptr(unsafe.Pointer(g))) { 1793 // The P got a new worker. 1794 // Exit this worker. 1795 return false 1796 } 1797 } 1798 return true 1799 }, unsafe.Pointer(park), waitReasonGCWorkerIdle, traceEvGoBlock, 0) 1800 1801 // Loop until the P dies and disassociates this 1802 // worker (the P may later be reused, in which case 1803 // it will get a new worker) or we failed to associate. 1804 if _p_.gcBgMarkWorker.ptr() != gp { 1805 break 1806 } 1807 1808 // Disable preemption so we can use the gcw. If the 1809 // scheduler wants to preempt us, we'll stop draining, 1810 // dispose the gcw, and then preempt. 1811 park.m.set(acquirem()) 1812 1813 if gcBlackenEnabled == 0 { 1814 throw("gcBgMarkWorker: blackening not enabled") 1815 } 1816 1817 startTime := nanotime() 1818 _p_.gcMarkWorkerStartTime = startTime 1819 1820 decnwait := atomic.Xadd(&work.nwait, -1) 1821 if decnwait == work.nproc { 1822 println("runtime: work.nwait=", decnwait, "work.nproc=", work.nproc) 1823 throw("work.nwait was > work.nproc") 1824 } 1825 1826 systemstack(func() { 1827 // Mark our goroutine preemptible so its stack 1828 // can be scanned. This lets two mark workers 1829 // scan each other (otherwise, they would 1830 // deadlock). We must not modify anything on 1831 // the G stack. However, stack shrinking is 1832 // disabled for mark workers, so it is safe to 1833 // read from the G stack. 1834 casgstatus(gp, _Grunning, _Gwaiting) 1835 switch _p_.gcMarkWorkerMode { 1836 default: 1837 throw("gcBgMarkWorker: unexpected gcMarkWorkerMode") 1838 case gcMarkWorkerDedicatedMode: 1839 gcDrain(&_p_.gcw, gcDrainUntilPreempt|gcDrainFlushBgCredit) 1840 if gp.preempt { 1841 // We were preempted. This is 1842 // a useful signal to kick 1843 // everything out of the run 1844 // queue so it can run 1845 // somewhere else. 1846 lock(&sched.lock) 1847 for { 1848 gp, _ := runqget(_p_) 1849 if gp == nil { 1850 break 1851 } 1852 globrunqput(gp) 1853 } 1854 unlock(&sched.lock) 1855 } 1856 // Go back to draining, this time 1857 // without preemption. 1858 gcDrain(&_p_.gcw, gcDrainNoBlock|gcDrainFlushBgCredit) 1859 case gcMarkWorkerFractionalMode: 1860 gcDrain(&_p_.gcw, gcDrainFractional|gcDrainUntilPreempt|gcDrainFlushBgCredit) 1861 case gcMarkWorkerIdleMode: 1862 gcDrain(&_p_.gcw, gcDrainIdle|gcDrainUntilPreempt|gcDrainFlushBgCredit) 1863 } 1864 casgstatus(gp, _Gwaiting, _Grunning) 1865 }) 1866 1867 // If we are nearing the end of mark, dispose 1868 // of the cache promptly. We must do this 1869 // before signaling that we're no longer 1870 // working so that other workers can't observe 1871 // no workers and no work while we have this 1872 // cached, and before we compute done. 1873 if gcBlackenPromptly { 1874 _p_.gcw.dispose() 1875 } 1876 1877 // Account for time. 1878 duration := nanotime() - startTime 1879 switch _p_.gcMarkWorkerMode { 1880 case gcMarkWorkerDedicatedMode: 1881 atomic.Xaddint64(&gcController.dedicatedMarkTime, duration) 1882 atomic.Xaddint64(&gcController.dedicatedMarkWorkersNeeded, 1) 1883 case gcMarkWorkerFractionalMode: 1884 atomic.Xaddint64(&gcController.fractionalMarkTime, duration) 1885 atomic.Xaddint64(&_p_.gcFractionalMarkTime, duration) 1886 case gcMarkWorkerIdleMode: 1887 atomic.Xaddint64(&gcController.idleMarkTime, duration) 1888 } 1889 1890 // Was this the last worker and did we run out 1891 // of work? 1892 incnwait := atomic.Xadd(&work.nwait, +1) 1893 if incnwait > work.nproc { 1894 println("runtime: p.gcMarkWorkerMode=", _p_.gcMarkWorkerMode, 1895 "work.nwait=", incnwait, "work.nproc=", work.nproc) 1896 throw("work.nwait > work.nproc") 1897 } 1898 1899 // If this worker reached a background mark completion 1900 // point, signal the main GC goroutine. 1901 if incnwait == work.nproc && !gcMarkWorkAvailable(nil) { 1902 // Make this G preemptible and disassociate it 1903 // as the worker for this P so 1904 // findRunnableGCWorker doesn't try to 1905 // schedule it. 1906 _p_.gcBgMarkWorker.set(nil) 1907 releasem(park.m.ptr()) 1908 1909 gcMarkDone() 1910 1911 // Disable preemption and prepare to reattach 1912 // to the P. 1913 // 1914 // We may be running on a different P at this 1915 // point, so we can't reattach until this G is 1916 // parked. 1917 park.m.set(acquirem()) 1918 park.attach.set(_p_) 1919 } 1920 } 1921 } 1922 1923 // gcMarkWorkAvailable returns true if executing a mark worker 1924 // on p is potentially useful. p may be nil, in which case it only 1925 // checks the global sources of work. 1926 func gcMarkWorkAvailable(p *p) bool { 1927 if p != nil && !p.gcw.empty() { 1928 return true 1929 } 1930 if !work.full.empty() { 1931 return true // global work available 1932 } 1933 if work.markrootNext < work.markrootJobs { 1934 return true // root scan work available 1935 } 1936 return false 1937 } 1938 1939 // gcMark runs the mark (or, for concurrent GC, mark termination) 1940 // All gcWork caches must be empty. 1941 // STW is in effect at this point. 1942 //TODO go:nowritebarrier 1943 func gcMark(start_time int64) { 1944 if debug.allocfreetrace > 0 { 1945 tracegc() 1946 } 1947 1948 if gcphase != _GCmarktermination { 1949 throw("in gcMark expecting to see gcphase as _GCmarktermination") 1950 } 1951 work.tstart = start_time 1952 1953 // Queue root marking jobs. 1954 gcMarkRootPrepare() 1955 1956 work.nwait = 0 1957 work.ndone = 0 1958 work.nproc = uint32(gcprocs()) 1959 1960 if work.full == 0 && work.nDataRoots+work.nBSSRoots+work.nSpanRoots+work.nStackRoots == 0 { 1961 // There's no work on the work queue and no root jobs 1962 // that can produce work, so don't bother entering the 1963 // getfull() barrier. 1964 // 1965 // This will be the situation the vast majority of the 1966 // time after concurrent mark. However, we still need 1967 // a fallback for STW GC and because there are some 1968 // known races that occasionally leave work around for 1969 // mark termination. 1970 // 1971 // We're still hedging our bets here: if we do 1972 // accidentally produce some work, we'll still process 1973 // it, just not necessarily in parallel. 1974 // 1975 // TODO(austin): Fix the races and and remove 1976 // work draining from mark termination so we don't 1977 // need the fallback path. 1978 work.helperDrainBlock = false 1979 } else { 1980 work.helperDrainBlock = true 1981 } 1982 1983 if work.nproc > 1 { 1984 noteclear(&work.alldone) 1985 helpgc(int32(work.nproc)) 1986 } 1987 1988 gchelperstart() 1989 1990 gcw := &getg().m.p.ptr().gcw 1991 if work.helperDrainBlock { 1992 gcDrain(gcw, gcDrainBlock) 1993 } else { 1994 gcDrain(gcw, gcDrainNoBlock) 1995 } 1996 gcw.dispose() 1997 1998 if debug.gccheckmark > 0 { 1999 // This is expensive when there's a large number of 2000 // Gs, so only do it if checkmark is also enabled. 2001 gcMarkRootCheck() 2002 } 2003 if work.full != 0 { 2004 throw("work.full != 0") 2005 } 2006 2007 if work.nproc > 1 { 2008 notesleep(&work.alldone) 2009 } 2010 2011 // Record that at least one root marking pass has completed. 2012 work.markrootDone = true 2013 2014 // Double-check that all gcWork caches are empty. This should 2015 // be ensured by mark 2 before we enter mark termination. 2016 for _, p := range allp { 2017 gcw := &p.gcw 2018 if !gcw.empty() { 2019 throw("P has cached GC work at end of mark termination") 2020 } 2021 if gcw.scanWork != 0 || gcw.bytesMarked != 0 { 2022 throw("P has unflushed stats at end of mark termination") 2023 } 2024 } 2025 2026 cachestats() 2027 2028 // Update the marked heap stat. 2029 memstats.heap_marked = work.bytesMarked 2030 2031 // Update other GC heap size stats. This must happen after 2032 // cachestats (which flushes local statistics to these) and 2033 // flushallmcaches (which modifies heap_live). 2034 memstats.heap_live = work.bytesMarked 2035 memstats.heap_scan = uint64(gcController.scanWork) 2036 2037 if trace.enabled { 2038 traceHeapAlloc() 2039 } 2040 } 2041 2042 func gcSweep(mode gcMode) { 2043 if gcphase != _GCoff { 2044 throw("gcSweep being done but phase is not GCoff") 2045 } 2046 2047 lock(&mheap_.lock) 2048 mheap_.sweepgen += 2 2049 mheap_.sweepdone = 0 2050 if mheap_.sweepSpans[mheap_.sweepgen/2%2].index != 0 { 2051 // We should have drained this list during the last 2052 // sweep phase. We certainly need to start this phase 2053 // with an empty swept list. 2054 throw("non-empty swept list") 2055 } 2056 mheap_.pagesSwept = 0 2057 unlock(&mheap_.lock) 2058 2059 if !_ConcurrentSweep || mode == gcForceBlockMode { 2060 // Special case synchronous sweep. 2061 // Record that no proportional sweeping has to happen. 2062 lock(&mheap_.lock) 2063 mheap_.sweepPagesPerByte = 0 2064 unlock(&mheap_.lock) 2065 // Sweep all spans eagerly. 2066 for sweepone() != ^uintptr(0) { 2067 sweep.npausesweep++ 2068 } 2069 // Free workbufs eagerly. 2070 prepareFreeWorkbufs() 2071 for freeSomeWbufs(false) { 2072 } 2073 // All "free" events for this mark/sweep cycle have 2074 // now happened, so we can make this profile cycle 2075 // available immediately. 2076 mProf_NextCycle() 2077 mProf_Flush() 2078 return 2079 } 2080 2081 // Background sweep. 2082 lock(&sweep.lock) 2083 if sweep.parked { 2084 sweep.parked = false 2085 ready(sweep.g, 0, true) 2086 } 2087 unlock(&sweep.lock) 2088 } 2089 2090 // gcResetMarkState resets global state prior to marking (concurrent 2091 // or STW) and resets the stack scan state of all Gs. 2092 // 2093 // This is safe to do without the world stopped because any Gs created 2094 // during or after this will start out in the reset state. 2095 func gcResetMarkState() { 2096 // This may be called during a concurrent phase, so make sure 2097 // allgs doesn't change. 2098 lock(&allglock) 2099 for _, gp := range allgs { 2100 gp.gcscandone = false // set to true in gcphasework 2101 gp.gcscanvalid = false // stack has not been scanned 2102 gp.gcAssistBytes = 0 2103 } 2104 unlock(&allglock) 2105 2106 work.bytesMarked = 0 2107 work.initialHeapLive = atomic.Load64(&memstats.heap_live) 2108 work.markrootDone = false 2109 } 2110 2111 // Hooks for other packages 2112 2113 var poolcleanup func() 2114 2115 //go:linkname sync_runtime_registerPoolCleanup sync.runtime_registerPoolCleanup 2116 func sync_runtime_registerPoolCleanup(f func()) { 2117 poolcleanup = f 2118 } 2119 2120 func clearpools() { 2121 // clear sync.Pools 2122 if poolcleanup != nil { 2123 poolcleanup() 2124 } 2125 2126 // Clear central sudog cache. 2127 // Leave per-P caches alone, they have strictly bounded size. 2128 // Disconnect cached list before dropping it on the floor, 2129 // so that a dangling ref to one entry does not pin all of them. 2130 lock(&sched.sudoglock) 2131 var sg, sgnext *sudog 2132 for sg = sched.sudogcache; sg != nil; sg = sgnext { 2133 sgnext = sg.next 2134 sg.next = nil 2135 } 2136 sched.sudogcache = nil 2137 unlock(&sched.sudoglock) 2138 2139 // Clear central defer pools. 2140 // Leave per-P pools alone, they have strictly bounded size. 2141 lock(&sched.deferlock) 2142 for i := range sched.deferpool { 2143 // disconnect cached list before dropping it on the floor, 2144 // so that a dangling ref to one entry does not pin all of them. 2145 var d, dlink *_defer 2146 for d = sched.deferpool[i]; d != nil; d = dlink { 2147 dlink = d.link 2148 d.link = nil 2149 } 2150 sched.deferpool[i] = nil 2151 } 2152 unlock(&sched.deferlock) 2153 } 2154 2155 // gchelper runs mark termination tasks on Ps other than the P 2156 // coordinating mark termination. 2157 // 2158 // The caller is responsible for ensuring that this has a P to run on, 2159 // even though it's running during STW. Because of this, it's allowed 2160 // to have write barriers. 2161 // 2162 //go:yeswritebarrierrec 2163 func gchelper() { 2164 _g_ := getg() 2165 _g_.m.traceback = 2 2166 gchelperstart() 2167 2168 // Parallel mark over GC roots and heap 2169 if gcphase == _GCmarktermination { 2170 gcw := &_g_.m.p.ptr().gcw 2171 if work.helperDrainBlock { 2172 gcDrain(gcw, gcDrainBlock) // blocks in getfull 2173 } else { 2174 gcDrain(gcw, gcDrainNoBlock) 2175 } 2176 gcw.dispose() 2177 } 2178 2179 nproc := atomic.Load(&work.nproc) // work.nproc can change right after we increment work.ndone 2180 if atomic.Xadd(&work.ndone, +1) == nproc-1 { 2181 notewakeup(&work.alldone) 2182 } 2183 _g_.m.traceback = 0 2184 } 2185 2186 func gchelperstart() { 2187 _g_ := getg() 2188 2189 if _g_.m.helpgc < 0 || _g_.m.helpgc >= _MaxGcproc { 2190 throw("gchelperstart: bad m->helpgc") 2191 } 2192 if _g_ != _g_.m.g0 { 2193 throw("gchelper not running on g0 stack") 2194 } 2195 } 2196 2197 // Timing 2198 2199 // itoaDiv formats val/(10**dec) into buf. 2200 func itoaDiv(buf []byte, val uint64, dec int) []byte { 2201 i := len(buf) - 1 2202 idec := i - dec 2203 for val >= 10 || i >= idec { 2204 buf[i] = byte(val%10 + '0') 2205 i-- 2206 if i == idec { 2207 buf[i] = '.' 2208 i-- 2209 } 2210 val /= 10 2211 } 2212 buf[i] = byte(val + '0') 2213 return buf[i:] 2214 } 2215 2216 // fmtNSAsMS nicely formats ns nanoseconds as milliseconds. 2217 func fmtNSAsMS(buf []byte, ns uint64) []byte { 2218 if ns >= 10e6 { 2219 // Format as whole milliseconds. 2220 return itoaDiv(buf, ns/1e6, 0) 2221 } 2222 // Format two digits of precision, with at most three decimal places. 2223 x := ns / 1e3 2224 if x == 0 { 2225 buf[0] = '0' 2226 return buf[:1] 2227 } 2228 dec := 3 2229 for x >= 100 { 2230 x /= 10 2231 dec-- 2232 } 2233 return itoaDiv(buf, x, dec) 2234 } 2235