Source file src/runtime/mgc.go

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

View as plain text