]> Cypherpunks.ru repositories - gostls13.git/blob - src/runtime/mgcpacer.go
runtime: add a non-functional memory limit to the pacer
[gostls13.git] / src / runtime / mgcpacer.go
1 // Copyright 2021 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4
5 package runtime
6
7 import (
8         "internal/cpu"
9         "internal/goexperiment"
10         "runtime/internal/atomic"
11         "unsafe"
12 )
13
14 // go119MemoryLimitSupport is a feature flag for a number of changes
15 // related to the memory limit feature (#48409). Disabling this flag
16 // disables those features, as well as the memory limit mechanism,
17 // which becomes a no-op.
18 const go119MemoryLimitSupport = true
19
20 const (
21         // gcGoalUtilization is the goal CPU utilization for
22         // marking as a fraction of GOMAXPROCS.
23         //
24         // Increasing the goal utilization will shorten GC cycles as the GC
25         // has more resources behind it, lessening costs from the write barrier,
26         // but comes at the cost of increasing mutator latency.
27         gcGoalUtilization = gcBackgroundUtilization
28
29         // gcBackgroundUtilization is the fixed CPU utilization for background
30         // marking. It must be <= gcGoalUtilization. The difference between
31         // gcGoalUtilization and gcBackgroundUtilization will be made up by
32         // mark assists. The scheduler will aim to use within 50% of this
33         // goal.
34         //
35         // As a general rule, there's little reason to set gcBackgroundUtilization
36         // < gcGoalUtilization. One reason might be in mostly idle applications,
37         // where goroutines are unlikely to assist at all, so the actual
38         // utilization will be lower than the goal. But this is moot point
39         // because the idle mark workers already soak up idle CPU resources.
40         // These two values are still kept separate however because they are
41         // distinct conceptually, and in previous iterations of the pacer the
42         // distinction was more important.
43         gcBackgroundUtilization = 0.25
44
45         // gcCreditSlack is the amount of scan work credit that can
46         // accumulate locally before updating gcController.heapScanWork and,
47         // optionally, gcController.bgScanCredit. Lower values give a more
48         // accurate assist ratio and make it more likely that assists will
49         // successfully steal background credit. Higher values reduce memory
50         // contention.
51         gcCreditSlack = 2000
52
53         // gcAssistTimeSlack is the nanoseconds of mutator assist time that
54         // can accumulate on a P before updating gcController.assistTime.
55         gcAssistTimeSlack = 5000
56
57         // gcOverAssistWork determines how many extra units of scan work a GC
58         // assist does when an assist happens. This amortizes the cost of an
59         // assist by pre-paying for this many bytes of future allocations.
60         gcOverAssistWork = 64 << 10
61
62         // defaultHeapMinimum is the value of heapMinimum for GOGC==100.
63         defaultHeapMinimum = (goexperiment.HeapMinimum512KiBInt)*(512<<10) +
64                 (1-goexperiment.HeapMinimum512KiBInt)*(4<<20)
65
66         // scannableStackSizeSlack is the bytes of stack space allocated or freed
67         // that can accumulate on a P before updating gcController.stackSize.
68         scannableStackSizeSlack = 8 << 10
69 )
70
71 func init() {
72         if offset := unsafe.Offsetof(gcController.heapLive); offset%8 != 0 {
73                 println(offset)
74                 throw("gcController.heapLive not aligned to 8 bytes")
75         }
76 }
77
78 // gcController implements the GC pacing controller that determines
79 // when to trigger concurrent garbage collection and how much marking
80 // work to do in mutator assists and background marking.
81 //
82 // It calculates the ratio between the allocation rate (in terms of CPU
83 // time) and the GC scan throughput to determine the heap size at which to
84 // trigger a GC cycle such that no GC assists are required to finish on time.
85 // This algorithm thus optimizes GC CPU utilization to the dedicated background
86 // mark utilization of 25% of GOMAXPROCS by minimizing GC assists.
87 // GOMAXPROCS. The high-level design of this algorithm is documented
88 // at https://github.com/golang/proposal/blob/master/design/44167-gc-pacer-redesign.md.
89 // See https://golang.org/s/go15gcpacing for additional historical context.
90 var gcController gcControllerState
91
92 type gcControllerState struct {
93         // Initialized from GOGC. GOGC=off means no GC.
94         gcPercent atomic.Int32
95
96         _ uint32 // padding so following 64-bit values are 8-byte aligned
97
98         // memoryLimit is the soft memory limit in bytes.
99         //
100         // Initialized from GOMEMLIMIT. GOMEMLIMIT=off is equivalent to MaxInt64
101         // which means no soft memory limit in practice.
102         //
103         // This is an int64 instead of a uint64 to more easily maintain parity with
104         // the SetMemoryLimit API, which sets a maximum at MaxInt64. This value
105         // should never be negative.
106         memoryLimit atomic.Int64
107
108         // heapMinimum is the minimum heap size at which to trigger GC.
109         // For small heaps, this overrides the usual GOGC*live set rule.
110         //
111         // When there is a very small live set but a lot of allocation, simply
112         // collecting when the heap reaches GOGC*live results in many GC
113         // cycles and high total per-GC overhead. This minimum amortizes this
114         // per-GC overhead while keeping the heap reasonably small.
115         //
116         // During initialization this is set to 4MB*GOGC/100. In the case of
117         // GOGC==0, this will set heapMinimum to 0, resulting in constant
118         // collection even when the heap size is small, which is useful for
119         // debugging.
120         heapMinimum uint64
121
122         // trigger is the heap size that triggers marking.
123         //
124         // When heapLive ≥ trigger, the mark phase will start.
125         // This is also the heap size by which proportional sweeping
126         // must be complete.
127         //
128         // This is computed from consMark during mark termination for
129         // the next cycle's trigger.
130         //
131         // Protected by mheap_.lock or a STW.
132         trigger uint64
133
134         // consMark is the estimated per-CPU consMark ratio for the application.
135         //
136         // It represents the ratio between the application's allocation
137         // rate, as bytes allocated per CPU-time, and the GC's scan rate,
138         // as bytes scanned per CPU-time.
139         // The units of this ratio are (B / cpu-ns) / (B / cpu-ns).
140         //
141         // At a high level, this value is computed as the bytes of memory
142         // allocated (cons) per unit of scan work completed (mark) in a GC
143         // cycle, divided by the CPU time spent on each activity.
144         //
145         // Updated at the end of each GC cycle, in endCycle.
146         consMark float64
147
148         // consMarkController holds the state for the mark-cons ratio
149         // estimation over time.
150         //
151         // Its purpose is to smooth out noisiness in the computation of
152         // consMark; see consMark for details.
153         consMarkController piController
154
155         _ uint32 // Padding for atomics on 32-bit platforms.
156
157         // heapGoal is the goal heapLive for when next GC ends.
158         // Set to ^uint64(0) if disabled.
159         //
160         // Read and written atomically, unless the world is stopped.
161         heapGoal uint64
162
163         // lastHeapGoal is the value of heapGoal for the previous GC.
164         // Note that this is distinct from the last value heapGoal had,
165         // because it could change if e.g. gcPercent changes.
166         //
167         // Read and written with the world stopped or with mheap_.lock held.
168         lastHeapGoal uint64
169
170         // heapLive is the number of bytes considered live by the GC.
171         // That is: retained by the most recent GC plus allocated
172         // since then. heapLive ≤ memstats.heapAlloc, since heapAlloc includes
173         // unmarked objects that have not yet been swept (and hence goes up as we
174         // allocate and down as we sweep) while heapLive excludes these
175         // objects (and hence only goes up between GCs).
176         //
177         // This is updated atomically without locking. To reduce
178         // contention, this is updated only when obtaining a span from
179         // an mcentral and at this point it counts all of the
180         // unallocated slots in that span (which will be allocated
181         // before that mcache obtains another span from that
182         // mcentral). Hence, it slightly overestimates the "true" live
183         // heap size. It's better to overestimate than to
184         // underestimate because 1) this triggers the GC earlier than
185         // necessary rather than potentially too late and 2) this
186         // leads to a conservative GC rate rather than a GC rate that
187         // is potentially too low.
188         //
189         // Reads should likewise be atomic (or during STW).
190         //
191         // Whenever this is updated, call traceHeapAlloc() and
192         // this gcControllerState's revise() method.
193         heapLive uint64
194
195         // heapScan is the number of bytes of "scannable" heap. This
196         // is the live heap (as counted by heapLive), but omitting
197         // no-scan objects and no-scan tails of objects.
198         //
199         // This value is fixed at the start of a GC cycle, so during a
200         // GC cycle it is safe to read without atomics, and it represents
201         // the maximum scannable heap.
202         heapScan uint64
203
204         // lastHeapScan is the number of bytes of heap that were scanned
205         // last GC cycle. It is the same as heapMarked, but only
206         // includes the "scannable" parts of objects.
207         //
208         // Updated when the world is stopped.
209         lastHeapScan uint64
210
211         // stackScan is a snapshot of scannableStackSize taken at each GC
212         // STW pause and is used in pacing decisions.
213         //
214         // Updated only while the world is stopped.
215         stackScan uint64
216
217         // scannableStackSize is the amount of allocated goroutine stack space in
218         // use by goroutines.
219         //
220         // This number tracks allocated goroutine stack space rather than used
221         // goroutine stack space (i.e. what is actually scanned) because used
222         // goroutine stack space is much harder to measure cheaply. By using
223         // allocated space, we make an overestimate; this is OK, it's better
224         // to conservatively overcount than undercount.
225         //
226         // Read and updated atomically.
227         scannableStackSize uint64
228
229         // globalsScan is the total amount of global variable space
230         // that is scannable.
231         //
232         // Read and updated atomically.
233         globalsScan uint64
234
235         // heapMarked is the number of bytes marked by the previous
236         // GC. After mark termination, heapLive == heapMarked, but
237         // unlike heapLive, heapMarked does not change until the
238         // next mark termination.
239         heapMarked uint64
240
241         // heapScanWork is the total heap scan work performed this cycle.
242         // stackScanWork is the total stack scan work performed this cycle.
243         // globalsScanWork is the total globals scan work performed this cycle.
244         //
245         // These are updated atomically during the cycle. Updates occur in
246         // bounded batches, since they are both written and read
247         // throughout the cycle. At the end of the cycle, heapScanWork is how
248         // much of the retained heap is scannable.
249         //
250         // Currently these are measured in bytes. For most uses, this is an
251         // opaque unit of work, but for estimation the definition is important.
252         //
253         // Note that stackScanWork includes all allocated space, not just the
254         // size of the stack itself, mirroring stackSize.
255         heapScanWork    atomic.Int64
256         stackScanWork   atomic.Int64
257         globalsScanWork atomic.Int64
258
259         // bgScanCredit is the scan work credit accumulated by the
260         // concurrent background scan. This credit is accumulated by
261         // the background scan and stolen by mutator assists. This is
262         // updated atomically. Updates occur in bounded batches, since
263         // it is both written and read throughout the cycle.
264         bgScanCredit int64
265
266         // assistTime is the nanoseconds spent in mutator assists
267         // during this cycle. This is updated atomically, and must also
268         // be updated atomically even during a STW, because it is read
269         // by sysmon. Updates occur in bounded batches, since it is both
270         // written and read throughout the cycle.
271         assistTime atomic.Int64
272
273         // dedicatedMarkTime is the nanoseconds spent in dedicated
274         // mark workers during this cycle. This is updated atomically
275         // at the end of the concurrent mark phase.
276         dedicatedMarkTime int64
277
278         // fractionalMarkTime is the nanoseconds spent in the
279         // fractional mark worker during this cycle. This is updated
280         // atomically throughout the cycle and will be up-to-date if
281         // the fractional mark worker is not currently running.
282         fractionalMarkTime int64
283
284         // idleMarkTime is the nanoseconds spent in idle marking
285         // during this cycle. This is updated atomically throughout
286         // the cycle.
287         idleMarkTime int64
288
289         // markStartTime is the absolute start time in nanoseconds
290         // that assists and background mark workers started.
291         markStartTime int64
292
293         // dedicatedMarkWorkersNeeded is the number of dedicated mark
294         // workers that need to be started. This is computed at the
295         // beginning of each cycle and decremented atomically as
296         // dedicated mark workers get started.
297         dedicatedMarkWorkersNeeded int64
298
299         // idleMarkWorkers is two packed int32 values in a single uint64.
300         // These two values are always updated simultaneously.
301         //
302         // The bottom int32 is the current number of idle mark workers executing.
303         //
304         // The top int32 is the maximum number of idle mark workers allowed to
305         // execute concurrently. Normally, this number is just gomaxprocs. However,
306         // during periodic GC cycles it is set to 0 because the system is idle
307         // anyway; there's no need to go full blast on all of GOMAXPROCS.
308         //
309         // The maximum number of idle mark workers is used to prevent new workers
310         // from starting, but it is not a hard maximum. It is possible (but
311         // exceedingly rare) for the current number of idle mark workers to
312         // transiently exceed the maximum. This could happen if the maximum changes
313         // just after a GC ends, and an M with no P.
314         //
315         // Note that if we have no dedicated mark workers, we set this value to
316         // 1 in this case we only have fractional GC workers which aren't scheduled
317         // strictly enough to ensure GC progress. As a result, idle-priority mark
318         // workers are vital to GC progress in these situations.
319         //
320         // For example, consider a situation in which goroutines block on the GC
321         // (such as via runtime.GOMAXPROCS) and only fractional mark workers are
322         // scheduled (e.g. GOMAXPROCS=1). Without idle-priority mark workers, the
323         // last running M might skip scheduling a fractional mark worker if its
324         // utilization goal is met, such that once it goes to sleep (because there's
325         // nothing to do), there will be nothing else to spin up a new M for the
326         // fractional worker in the future, stalling GC progress and causing a
327         // deadlock. However, idle-priority workers will *always* run when there is
328         // nothing left to do, ensuring the GC makes progress.
329         //
330         // See github.com/golang/go/issues/44163 for more details.
331         idleMarkWorkers atomic.Uint64
332
333         // assistWorkPerByte is the ratio of scan work to allocated
334         // bytes that should be performed by mutator assists. This is
335         // computed at the beginning of each cycle and updated every
336         // time heapScan is updated.
337         assistWorkPerByte atomic.Float64
338
339         // assistBytesPerWork is 1/assistWorkPerByte.
340         //
341         // Note that because this is read and written independently
342         // from assistWorkPerByte users may notice a skew between
343         // the two values, and such a state should be safe.
344         assistBytesPerWork atomic.Float64
345
346         // fractionalUtilizationGoal is the fraction of wall clock
347         // time that should be spent in the fractional mark worker on
348         // each P that isn't running a dedicated worker.
349         //
350         // For example, if the utilization goal is 25% and there are
351         // no dedicated workers, this will be 0.25. If the goal is
352         // 25%, there is one dedicated worker, and GOMAXPROCS is 5,
353         // this will be 0.05 to make up the missing 5%.
354         //
355         // If this is zero, no fractional workers are needed.
356         fractionalUtilizationGoal float64
357
358         // test indicates that this is a test-only copy of gcControllerState.
359         test bool
360
361         _ cpu.CacheLinePad
362 }
363
364 func (c *gcControllerState) init(gcPercent int32, memoryLimit int64) {
365         c.heapMinimum = defaultHeapMinimum
366
367         c.consMarkController = piController{
368                 // Tuned first via the Ziegler-Nichols process in simulation,
369                 // then the integral time was manually tuned against real-world
370                 // applications to deal with noisiness in the measured cons/mark
371                 // ratio.
372                 kp: 0.9,
373                 ti: 4.0,
374
375                 // Set a high reset time in GC cycles.
376                 // This is inversely proportional to the rate at which we
377                 // accumulate error from clipping. By making this very high
378                 // we make the accumulation slow. In general, clipping is
379                 // OK in our situation, hence the choice.
380                 //
381                 // Tune this if we get unintended effects from clipping for
382                 // a long time.
383                 tt:  1000,
384                 min: -1000,
385                 max: 1000,
386         }
387
388         c.setGCPercent(gcPercent)
389         c.setMemoryLimit(memoryLimit)
390         c.commit()
391 }
392
393 // startCycle resets the GC controller's state and computes estimates
394 // for a new GC cycle. The caller must hold worldsema and the world
395 // must be stopped.
396 func (c *gcControllerState) startCycle(markStartTime int64, procs int, trigger gcTrigger) {
397         c.heapScanWork.Store(0)
398         c.stackScanWork.Store(0)
399         c.globalsScanWork.Store(0)
400         c.bgScanCredit = 0
401         c.assistTime.Store(0)
402         c.dedicatedMarkTime = 0
403         c.fractionalMarkTime = 0
404         c.idleMarkTime = 0
405         c.markStartTime = markStartTime
406         c.stackScan = atomic.Load64(&c.scannableStackSize)
407
408         // Ensure that the heap goal is at least a little larger than
409         // the current live heap size. This may not be the case if GC
410         // start is delayed or if the allocation that pushed gcController.heapLive
411         // over trigger is large or if the trigger is really close to
412         // GOGC. Assist is proportional to this distance, so enforce a
413         // minimum distance, even if it means going over the GOGC goal
414         // by a tiny bit.
415         if c.heapGoal < c.heapLive+64<<10 {
416                 c.heapGoal = c.heapLive + 64<<10
417         }
418
419         // Compute the background mark utilization goal. In general,
420         // this may not come out exactly. We round the number of
421         // dedicated workers so that the utilization is closest to
422         // 25%. For small GOMAXPROCS, this would introduce too much
423         // error, so we add fractional workers in that case.
424         totalUtilizationGoal := float64(procs) * gcBackgroundUtilization
425         c.dedicatedMarkWorkersNeeded = int64(totalUtilizationGoal + 0.5)
426         utilError := float64(c.dedicatedMarkWorkersNeeded)/totalUtilizationGoal - 1
427         const maxUtilError = 0.3
428         if utilError < -maxUtilError || utilError > maxUtilError {
429                 // Rounding put us more than 30% off our goal. With
430                 // gcBackgroundUtilization of 25%, this happens for
431                 // GOMAXPROCS<=3 or GOMAXPROCS=6. Enable fractional
432                 // workers to compensate.
433                 if float64(c.dedicatedMarkWorkersNeeded) > totalUtilizationGoal {
434                         // Too many dedicated workers.
435                         c.dedicatedMarkWorkersNeeded--
436                 }
437                 c.fractionalUtilizationGoal = (totalUtilizationGoal - float64(c.dedicatedMarkWorkersNeeded)) / float64(procs)
438         } else {
439                 c.fractionalUtilizationGoal = 0
440         }
441
442         // In STW mode, we just want dedicated workers.
443         if debug.gcstoptheworld > 0 {
444                 c.dedicatedMarkWorkersNeeded = int64(procs)
445                 c.fractionalUtilizationGoal = 0
446         }
447
448         // Clear per-P state
449         for _, p := range allp {
450                 p.gcAssistTime = 0
451                 p.gcFractionalMarkTime = 0
452         }
453
454         if trigger.kind == gcTriggerTime {
455                 // During a periodic GC cycle, reduce the number of idle mark workers
456                 // required. However, we need at least one dedicated mark worker or
457                 // idle GC worker to ensure GC progress in some scenarios (see comment
458                 // on maxIdleMarkWorkers).
459                 if c.dedicatedMarkWorkersNeeded > 0 {
460                         c.setMaxIdleMarkWorkers(0)
461                 } else {
462                         // TODO(mknyszek): The fundamental reason why we need this is because
463                         // we can't count on the fractional mark worker to get scheduled.
464                         // Fix that by ensuring it gets scheduled according to its quota even
465                         // if the rest of the application is idle.
466                         c.setMaxIdleMarkWorkers(1)
467                 }
468         } else {
469                 // N.B. gomaxprocs and dedicatedMarkWorkersNeeded is guaranteed not to
470                 // change during a GC cycle.
471                 c.setMaxIdleMarkWorkers(int32(procs) - int32(c.dedicatedMarkWorkersNeeded))
472         }
473
474         // Compute initial values for controls that are updated
475         // throughout the cycle.
476         c.revise()
477
478         if debug.gcpacertrace > 0 {
479                 assistRatio := c.assistWorkPerByte.Load()
480                 print("pacer: assist ratio=", assistRatio,
481                         " (scan ", gcController.heapScan>>20, " MB in ",
482                         work.initialHeapLive>>20, "->",
483                         c.heapGoal>>20, " MB)",
484                         " workers=", c.dedicatedMarkWorkersNeeded,
485                         "+", c.fractionalUtilizationGoal, "\n")
486         }
487 }
488
489 // revise updates the assist ratio during the GC cycle to account for
490 // improved estimates. This should be called whenever gcController.heapScan,
491 // gcController.heapLive, or gcController.heapGoal is updated. It is safe to
492 // call concurrently, but it may race with other calls to revise.
493 //
494 // The result of this race is that the two assist ratio values may not line
495 // up or may be stale. In practice this is OK because the assist ratio
496 // moves slowly throughout a GC cycle, and the assist ratio is a best-effort
497 // heuristic anyway. Furthermore, no part of the heuristic depends on
498 // the two assist ratio values being exact reciprocals of one another, since
499 // the two values are used to convert values from different sources.
500 //
501 // The worst case result of this raciness is that we may miss a larger shift
502 // in the ratio (say, if we decide to pace more aggressively against the
503 // hard heap goal) but even this "hard goal" is best-effort (see #40460).
504 // The dedicated GC should ensure we don't exceed the hard goal by too much
505 // in the rare case we do exceed it.
506 //
507 // It should only be called when gcBlackenEnabled != 0 (because this
508 // is when assists are enabled and the necessary statistics are
509 // available).
510 func (c *gcControllerState) revise() {
511         gcPercent := c.gcPercent.Load()
512         if gcPercent < 0 {
513                 // If GC is disabled but we're running a forced GC,
514                 // act like GOGC is huge for the below calculations.
515                 gcPercent = 100000
516         }
517         live := atomic.Load64(&c.heapLive)
518         scan := atomic.Load64(&c.heapScan)
519         work := c.heapScanWork.Load() + c.stackScanWork.Load() + c.globalsScanWork.Load()
520
521         // Assume we're under the soft goal. Pace GC to complete at
522         // heapGoal assuming the heap is in steady-state.
523         heapGoal := int64(atomic.Load64(&c.heapGoal))
524
525         // The expected scan work is computed as the amount of bytes scanned last
526         // GC cycle, plus our estimate of stacks and globals work for this cycle.
527         scanWorkExpected := int64(c.lastHeapScan + c.stackScan + c.globalsScan)
528
529         // maxScanWork is a worst-case estimate of the amount of scan work that
530         // needs to be performed in this GC cycle. Specifically, it represents
531         // the case where *all* scannable memory turns out to be live.
532         maxScanWork := int64(scan + c.stackScan + c.globalsScan)
533         if work > scanWorkExpected {
534                 // We've already done more scan work than expected. Because our expectation
535                 // is based on a steady-state scannable heap size, we assume this means our
536                 // heap is growing. Compute a new heap goal that takes our existing runway
537                 // computed for scanWorkExpected and extrapolates it to maxScanWork, the worst-case
538                 // scan work. This keeps our assist ratio stable if the heap continues to grow.
539                 //
540                 // The effect of this mechanism is that assists stay flat in the face of heap
541                 // growths. It's OK to use more memory this cycle to scan all the live heap,
542                 // because the next GC cycle is inevitably going to use *at least* that much
543                 // memory anyway.
544                 extHeapGoal := int64(float64(heapGoal-int64(c.trigger))/float64(scanWorkExpected)*float64(maxScanWork)) + int64(c.trigger)
545                 scanWorkExpected = maxScanWork
546
547                 // hardGoal is a hard limit on the amount that we're willing to push back the
548                 // heap goal, and that's twice the heap goal (i.e. if GOGC=100 and the heap and/or
549                 // stacks and/or globals grow to twice their size, this limits the current GC cycle's
550                 // growth to 4x the original live heap's size).
551                 //
552                 // This maintains the invariant that we use no more memory than the next GC cycle
553                 // will anyway.
554                 hardGoal := int64((1.0 + float64(gcPercent)/100.0) * float64(heapGoal))
555                 if extHeapGoal > hardGoal {
556                         extHeapGoal = hardGoal
557                 }
558                 heapGoal = extHeapGoal
559         }
560         if int64(live) > heapGoal {
561                 // We're already past our heap goal, even the extrapolated one.
562                 // Leave ourselves some extra runway, so in the worst case we
563                 // finish by that point.
564                 const maxOvershoot = 1.1
565                 heapGoal = int64(float64(heapGoal) * maxOvershoot)
566
567                 // Compute the upper bound on the scan work remaining.
568                 scanWorkExpected = maxScanWork
569         }
570
571         // Compute the remaining scan work estimate.
572         //
573         // Note that we currently count allocations during GC as both
574         // scannable heap (heapScan) and scan work completed
575         // (scanWork), so allocation will change this difference
576         // slowly in the soft regime and not at all in the hard
577         // regime.
578         scanWorkRemaining := scanWorkExpected - work
579         if scanWorkRemaining < 1000 {
580                 // We set a somewhat arbitrary lower bound on
581                 // remaining scan work since if we aim a little high,
582                 // we can miss by a little.
583                 //
584                 // We *do* need to enforce that this is at least 1,
585                 // since marking is racy and double-scanning objects
586                 // may legitimately make the remaining scan work
587                 // negative, even in the hard goal regime.
588                 scanWorkRemaining = 1000
589         }
590
591         // Compute the heap distance remaining.
592         heapRemaining := heapGoal - int64(live)
593         if heapRemaining <= 0 {
594                 // This shouldn't happen, but if it does, avoid
595                 // dividing by zero or setting the assist negative.
596                 heapRemaining = 1
597         }
598
599         // Compute the mutator assist ratio so by the time the mutator
600         // allocates the remaining heap bytes up to heapGoal, it will
601         // have done (or stolen) the remaining amount of scan work.
602         // Note that the assist ratio values are updated atomically
603         // but not together. This means there may be some degree of
604         // skew between the two values. This is generally OK as the
605         // values shift relatively slowly over the course of a GC
606         // cycle.
607         assistWorkPerByte := float64(scanWorkRemaining) / float64(heapRemaining)
608         assistBytesPerWork := float64(heapRemaining) / float64(scanWorkRemaining)
609         c.assistWorkPerByte.Store(assistWorkPerByte)
610         c.assistBytesPerWork.Store(assistBytesPerWork)
611 }
612
613 // endCycle computes the consMark estimate for the next cycle.
614 // userForced indicates whether the current GC cycle was forced
615 // by the application.
616 func (c *gcControllerState) endCycle(now int64, procs int, userForced bool) {
617         // Record last heap goal for the scavenger.
618         // We'll be updating the heap goal soon.
619         gcController.lastHeapGoal = gcController.heapGoal
620
621         // Compute the duration of time for which assists were turned on.
622         assistDuration := now - c.markStartTime
623
624         // Assume background mark hit its utilization goal.
625         utilization := gcBackgroundUtilization
626         // Add assist utilization; avoid divide by zero.
627         if assistDuration > 0 {
628                 utilization += float64(c.assistTime.Load()) / float64(assistDuration*int64(procs))
629         }
630
631         if c.heapLive <= c.trigger {
632                 // Shouldn't happen, but let's be very safe about this in case the
633                 // GC is somehow extremely short.
634                 //
635                 // In this case though, the only reasonable value for c.heapLive-c.trigger
636                 // would be 0, which isn't really all that useful, i.e. the GC was so short
637                 // that it didn't matter.
638                 //
639                 // Ignore this case and don't update anything.
640                 return
641         }
642         idleUtilization := 0.0
643         if assistDuration > 0 {
644                 idleUtilization = float64(c.idleMarkTime) / float64(assistDuration*int64(procs))
645         }
646         // Determine the cons/mark ratio.
647         //
648         // The units we want for the numerator and denominator are both B / cpu-ns.
649         // We get this by taking the bytes allocated or scanned, and divide by the amount of
650         // CPU time it took for those operations. For allocations, that CPU time is
651         //
652         //    assistDuration * procs * (1 - utilization)
653         //
654         // Where utilization includes just background GC workers and assists. It does *not*
655         // include idle GC work time, because in theory the mutator is free to take that at
656         // any point.
657         //
658         // For scanning, that CPU time is
659         //
660         //    assistDuration * procs * (utilization + idleUtilization)
661         //
662         // In this case, we *include* idle utilization, because that is additional CPU time that the
663         // the GC had available to it.
664         //
665         // In effect, idle GC time is sort of double-counted here, but it's very weird compared
666         // to other kinds of GC work, because of how fluid it is. Namely, because the mutator is
667         // *always* free to take it.
668         //
669         // So this calculation is really:
670         //     (heapLive-trigger) / (assistDuration * procs * (1-utilization)) /
671         //         (scanWork) / (assistDuration * procs * (utilization+idleUtilization)
672         //
673         // Note that because we only care about the ratio, assistDuration and procs cancel out.
674         scanWork := c.heapScanWork.Load() + c.stackScanWork.Load() + c.globalsScanWork.Load()
675         currentConsMark := (float64(c.heapLive-c.trigger) * (utilization + idleUtilization)) /
676                 (float64(scanWork) * (1 - utilization))
677
678         // Update cons/mark controller. The time period for this is 1 GC cycle.
679         //
680         // This use of a PI controller might seem strange. So, here's an explanation:
681         //
682         // currentConsMark represents the consMark we *should've* had to be perfectly
683         // on-target for this cycle. Given that we assume the next GC will be like this
684         // one in the steady-state, it stands to reason that we should just pick that
685         // as our next consMark. In practice, however, currentConsMark is too noisy:
686         // we're going to be wildly off-target in each GC cycle if we do that.
687         //
688         // What we do instead is make a long-term assumption: there is some steady-state
689         // consMark value, but it's obscured by noise. By constantly shooting for this
690         // noisy-but-perfect consMark value, the controller will bounce around a bit,
691         // but its average behavior, in aggregate, should be less noisy and closer to
692         // the true long-term consMark value, provided its tuned to be slightly overdamped.
693         var ok bool
694         oldConsMark := c.consMark
695         c.consMark, ok = c.consMarkController.next(c.consMark, currentConsMark, 1.0)
696         if !ok {
697                 // The error spiraled out of control. This is incredibly unlikely seeing
698                 // as this controller is essentially just a smoothing function, but it might
699                 // mean that something went very wrong with how currentConsMark was calculated.
700                 // Just reset consMark and keep going.
701                 c.consMark = 0
702         }
703
704         if debug.gcpacertrace > 0 {
705                 printlock()
706                 goal := gcGoalUtilization * 100
707                 print("pacer: ", int(utilization*100), "% CPU (", int(goal), " exp.) for ")
708                 print(c.heapScanWork.Load(), "+", c.stackScanWork.Load(), "+", c.globalsScanWork.Load(), " B work (", c.lastHeapScan+c.stackScan+c.globalsScan, " B exp.) ")
709                 print("in ", c.trigger, " B -> ", c.heapLive, " B (∆goal ", int64(c.heapLive)-int64(c.heapGoal), ", cons/mark ", oldConsMark, ")")
710                 if !ok {
711                         print("[controller reset]")
712                 }
713                 println()
714                 printunlock()
715         }
716 }
717
718 // enlistWorker encourages another dedicated mark worker to start on
719 // another P if there are spare worker slots. It is used by putfull
720 // when more work is made available.
721 //
722 //go:nowritebarrier
723 func (c *gcControllerState) enlistWorker() {
724         // If there are idle Ps, wake one so it will run an idle worker.
725         // NOTE: This is suspected of causing deadlocks. See golang.org/issue/19112.
726         //
727         //      if atomic.Load(&sched.npidle) != 0 && atomic.Load(&sched.nmspinning) == 0 {
728         //              wakep()
729         //              return
730         //      }
731
732         // There are no idle Ps. If we need more dedicated workers,
733         // try to preempt a running P so it will switch to a worker.
734         if c.dedicatedMarkWorkersNeeded <= 0 {
735                 return
736         }
737         // Pick a random other P to preempt.
738         if gomaxprocs <= 1 {
739                 return
740         }
741         gp := getg()
742         if gp == nil || gp.m == nil || gp.m.p == 0 {
743                 return
744         }
745         myID := gp.m.p.ptr().id
746         for tries := 0; tries < 5; tries++ {
747                 id := int32(fastrandn(uint32(gomaxprocs - 1)))
748                 if id >= myID {
749                         id++
750                 }
751                 p := allp[id]
752                 if p.status != _Prunning {
753                         continue
754                 }
755                 if preemptone(p) {
756                         return
757                 }
758         }
759 }
760
761 // findRunnableGCWorker returns a background mark worker for _p_ if it
762 // should be run. This must only be called when gcBlackenEnabled != 0.
763 func (c *gcControllerState) findRunnableGCWorker(_p_ *p, now int64) *g {
764         if gcBlackenEnabled == 0 {
765                 throw("gcControllerState.findRunnable: blackening not enabled")
766         }
767
768         // Since we have the current time, check if the GC CPU limiter
769         // hasn't had an update in a while. This check is necessary in
770         // case the limiter is on but hasn't been checked in a while and
771         // so may have left sufficient headroom to turn off again.
772         if gcCPULimiter.needUpdate(now) {
773                 gcCPULimiter.update(gcController.assistTime.Load(), now)
774         }
775
776         if !gcMarkWorkAvailable(_p_) {
777                 // No work to be done right now. This can happen at
778                 // the end of the mark phase when there are still
779                 // assists tapering off. Don't bother running a worker
780                 // now because it'll just return immediately.
781                 return nil
782         }
783
784         // Grab a worker before we commit to running below.
785         node := (*gcBgMarkWorkerNode)(gcBgMarkWorkerPool.pop())
786         if node == nil {
787                 // There is at least one worker per P, so normally there are
788                 // enough workers to run on all Ps, if necessary. However, once
789                 // a worker enters gcMarkDone it may park without rejoining the
790                 // pool, thus freeing a P with no corresponding worker.
791                 // gcMarkDone never depends on another worker doing work, so it
792                 // is safe to simply do nothing here.
793                 //
794                 // If gcMarkDone bails out without completing the mark phase,
795                 // it will always do so with queued global work. Thus, that P
796                 // will be immediately eligible to re-run the worker G it was
797                 // just using, ensuring work can complete.
798                 return nil
799         }
800
801         decIfPositive := func(ptr *int64) bool {
802                 for {
803                         v := atomic.Loadint64(ptr)
804                         if v <= 0 {
805                                 return false
806                         }
807
808                         if atomic.Casint64(ptr, v, v-1) {
809                                 return true
810                         }
811                 }
812         }
813
814         if decIfPositive(&c.dedicatedMarkWorkersNeeded) {
815                 // This P is now dedicated to marking until the end of
816                 // the concurrent mark phase.
817                 _p_.gcMarkWorkerMode = gcMarkWorkerDedicatedMode
818         } else if c.fractionalUtilizationGoal == 0 {
819                 // No need for fractional workers.
820                 gcBgMarkWorkerPool.push(&node.node)
821                 return nil
822         } else {
823                 // Is this P behind on the fractional utilization
824                 // goal?
825                 //
826                 // This should be kept in sync with pollFractionalWorkerExit.
827                 delta := now - c.markStartTime
828                 if delta > 0 && float64(_p_.gcFractionalMarkTime)/float64(delta) > c.fractionalUtilizationGoal {
829                         // Nope. No need to run a fractional worker.
830                         gcBgMarkWorkerPool.push(&node.node)
831                         return nil
832                 }
833                 // Run a fractional worker.
834                 _p_.gcMarkWorkerMode = gcMarkWorkerFractionalMode
835         }
836
837         // Run the background mark worker.
838         gp := node.gp.ptr()
839         casgstatus(gp, _Gwaiting, _Grunnable)
840         if trace.enabled {
841                 traceGoUnpark(gp, 0)
842         }
843         return gp
844 }
845
846 // resetLive sets up the controller state for the next mark phase after the end
847 // of the previous one. Must be called after endCycle and before commit, before
848 // the world is started.
849 //
850 // The world must be stopped.
851 func (c *gcControllerState) resetLive(bytesMarked uint64) {
852         c.heapMarked = bytesMarked
853         c.heapLive = bytesMarked
854         c.heapScan = uint64(c.heapScanWork.Load())
855         c.lastHeapScan = uint64(c.heapScanWork.Load())
856
857         // heapLive was updated, so emit a trace event.
858         if trace.enabled {
859                 traceHeapAlloc()
860         }
861 }
862
863 // markWorkerStop must be called whenever a mark worker stops executing.
864 //
865 // It updates mark work accounting in the controller by a duration of
866 // work in nanoseconds and other bookkeeping.
867 //
868 // Safe to execute at any time.
869 func (c *gcControllerState) markWorkerStop(mode gcMarkWorkerMode, duration int64) {
870         switch mode {
871         case gcMarkWorkerDedicatedMode:
872                 atomic.Xaddint64(&c.dedicatedMarkTime, duration)
873                 atomic.Xaddint64(&c.dedicatedMarkWorkersNeeded, 1)
874         case gcMarkWorkerFractionalMode:
875                 atomic.Xaddint64(&c.fractionalMarkTime, duration)
876         case gcMarkWorkerIdleMode:
877                 atomic.Xaddint64(&c.idleMarkTime, duration)
878                 c.removeIdleMarkWorker()
879         default:
880                 throw("markWorkerStop: unknown mark worker mode")
881         }
882 }
883
884 func (c *gcControllerState) update(dHeapLive, dHeapScan int64) {
885         if dHeapLive != 0 {
886                 atomic.Xadd64(&gcController.heapLive, dHeapLive)
887                 if trace.enabled {
888                         // gcController.heapLive changed.
889                         traceHeapAlloc()
890                 }
891         }
892         if gcBlackenEnabled == 0 {
893                 // Update heapScan when we're not in a current GC. It is fixed
894                 // at the beginning of a cycle.
895                 if dHeapScan != 0 {
896                         atomic.Xadd64(&gcController.heapScan, dHeapScan)
897                 }
898         } else {
899                 // gcController.heapLive changed.
900                 c.revise()
901         }
902 }
903
904 func (c *gcControllerState) addScannableStack(pp *p, amount int64) {
905         if pp == nil {
906                 atomic.Xadd64(&c.scannableStackSize, amount)
907                 return
908         }
909         pp.scannableStackSizeDelta += amount
910         if pp.scannableStackSizeDelta >= scannableStackSizeSlack || pp.scannableStackSizeDelta <= -scannableStackSizeSlack {
911                 atomic.Xadd64(&c.scannableStackSize, pp.scannableStackSizeDelta)
912                 pp.scannableStackSizeDelta = 0
913         }
914 }
915
916 func (c *gcControllerState) addGlobals(amount int64) {
917         atomic.Xadd64(&c.globalsScan, amount)
918 }
919
920 // commit recomputes all pacing parameters from scratch, namely
921 // absolute trigger, the heap goal, mark pacing, and sweep pacing.
922 //
923 // This can be called any time. If GC is the in the middle of a
924 // concurrent phase, it will adjust the pacing of that phase.
925 //
926 // This depends on gcPercent, gcController.heapMarked, and
927 // gcController.heapLive. These must be up to date.
928 //
929 // mheap_.lock must be held or the world must be stopped.
930 func (c *gcControllerState) commit() {
931         if !c.test {
932                 assertWorldStoppedOrLockHeld(&mheap_.lock)
933         }
934
935         // Compute the next GC goal, which is when the allocated heap
936         // has grown by GOGC/100 over where it started the last cycle,
937         // plus additional runway for non-heap sources of GC work.
938         goal := ^uint64(0)
939         if gcPercent := c.gcPercent.Load(); gcPercent >= 0 {
940                 goal = c.heapMarked + (c.heapMarked+atomic.Load64(&c.stackScan)+atomic.Load64(&c.globalsScan))*uint64(gcPercent)/100
941         }
942
943         // Don't trigger below the minimum heap size.
944         minTrigger := c.heapMinimum
945         if !isSweepDone() {
946                 // Concurrent sweep happens in the heap growth
947                 // from gcController.heapLive to trigger, so ensure
948                 // that concurrent sweep has some heap growth
949                 // in which to perform sweeping before we
950                 // start the next GC cycle.
951                 sweepMin := atomic.Load64(&c.heapLive) + sweepMinHeapDistance
952                 if sweepMin > minTrigger {
953                         minTrigger = sweepMin
954                 }
955         }
956
957         // If we let the trigger go too low, then if the application
958         // is allocating very rapidly we might end up in a situation
959         // where we're allocating black during a nearly always-on GC.
960         // The result of this is a growing heap and ultimately an
961         // increase in RSS. By capping us at a point >0, we're essentially
962         // saying that we're OK using more CPU during the GC to prevent
963         // this growth in RSS.
964         //
965         // The current constant was chosen empirically: given a sufficiently
966         // fast/scalable allocator with 48 Ps that could drive the trigger ratio
967         // to <0.05, this constant causes applications to retain the same peak
968         // RSS compared to not having this allocator.
969         if triggerBound := uint64(0.7*float64(goal-c.heapMarked)) + c.heapMarked; minTrigger < triggerBound {
970                 minTrigger = triggerBound
971         }
972
973         // For small heaps, set the max trigger point at 95% of the heap goal.
974         // This ensures we always have *some* headroom when the GC actually starts.
975         // For larger heaps, set the max trigger point at the goal, minus the
976         // minimum heap size.
977         // This choice follows from the fact that the minimum heap size is chosen
978         // to reflect the costs of a GC with no work to do. With a large heap but
979         // very little scan work to perform, this gives us exactly as much runway
980         // as we would need, in the worst case.
981         maxRunway := uint64(0.95 * float64(goal-c.heapMarked))
982         if largeHeapMaxRunway := goal - c.heapMinimum; goal > c.heapMinimum && maxRunway < largeHeapMaxRunway {
983                 maxRunway = largeHeapMaxRunway
984         }
985         maxTrigger := maxRunway + c.heapMarked
986         if maxTrigger < minTrigger {
987                 maxTrigger = minTrigger
988         }
989
990         // Compute the trigger by using our estimate of the cons/mark ratio.
991         //
992         // The idea is to take our expected scan work, and multiply it by
993         // the cons/mark ratio to determine how long it'll take to complete
994         // that scan work in terms of bytes allocated. This gives us our GC's
995         // runway.
996         //
997         // However, the cons/mark ratio is a ratio of rates per CPU-second, but
998         // here we care about the relative rates for some division of CPU
999         // resources among the mutator and the GC.
1000         //
1001         // To summarize, we have B / cpu-ns, and we want B / ns. We get that
1002         // by multiplying by our desired division of CPU resources. We choose
1003         // to express CPU resources as GOMAPROCS*fraction. Note that because
1004         // we're working with a ratio here, we can omit the number of CPU cores,
1005         // because they'll appear in the numerator and denominator and cancel out.
1006         // As a result, this is basically just "weighing" the cons/mark ratio by
1007         // our desired division of resources.
1008         //
1009         // Furthermore, by setting the trigger so that CPU resources are divided
1010         // this way, assuming that the cons/mark ratio is correct, we make that
1011         // division a reality.
1012         var trigger uint64
1013         runway := uint64((c.consMark * (1 - gcGoalUtilization) / (gcGoalUtilization)) * float64(c.lastHeapScan+c.stackScan+c.globalsScan))
1014         if runway > goal {
1015                 trigger = minTrigger
1016         } else {
1017                 trigger = goal - runway
1018         }
1019         if trigger < minTrigger {
1020                 trigger = minTrigger
1021         }
1022         if trigger > maxTrigger {
1023                 trigger = maxTrigger
1024         }
1025         if trigger > goal {
1026                 goal = trigger
1027         }
1028
1029         // Commit to the trigger and goal.
1030         c.trigger = trigger
1031         atomic.Store64(&c.heapGoal, goal)
1032         if trace.enabled {
1033                 traceHeapGoal()
1034         }
1035
1036         // Update mark pacing.
1037         if gcphase != _GCoff {
1038                 c.revise()
1039         }
1040 }
1041
1042 // effectiveGrowthRatio returns the current effective heap growth
1043 // ratio (GOGC/100) based on heapMarked from the previous GC and
1044 // heapGoal for the current GC.
1045 //
1046 // This may differ from gcPercent/100 because of various upper and
1047 // lower bounds on gcPercent. For example, if the heap is smaller than
1048 // heapMinimum, this can be higher than gcPercent/100.
1049 //
1050 // mheap_.lock must be held or the world must be stopped.
1051 func (c *gcControllerState) effectiveGrowthRatio() float64 {
1052         if !c.test {
1053                 assertWorldStoppedOrLockHeld(&mheap_.lock)
1054         }
1055
1056         egogc := float64(atomic.Load64(&c.heapGoal)-c.heapMarked) / float64(c.heapMarked)
1057         if egogc < 0 {
1058                 // Shouldn't happen, but just in case.
1059                 egogc = 0
1060         }
1061         return egogc
1062 }
1063
1064 // setGCPercent updates gcPercent. commit must be called after.
1065 // Returns the old value of gcPercent.
1066 //
1067 // The world must be stopped, or mheap_.lock must be held.
1068 func (c *gcControllerState) setGCPercent(in int32) int32 {
1069         if !c.test {
1070                 assertWorldStoppedOrLockHeld(&mheap_.lock)
1071         }
1072
1073         out := c.gcPercent.Load()
1074         if in < 0 {
1075                 in = -1
1076         }
1077         c.heapMinimum = defaultHeapMinimum * uint64(in) / 100
1078         c.gcPercent.Store(in)
1079
1080         return out
1081 }
1082
1083 //go:linkname setGCPercent runtime/debug.setGCPercent
1084 func setGCPercent(in int32) (out int32) {
1085         // Run on the system stack since we grab the heap lock.
1086         systemstack(func() {
1087                 lock(&mheap_.lock)
1088                 out = gcController.setGCPercent(in)
1089                 gcController.commit()
1090                 gcPaceSweeper(gcController.trigger)
1091                 gcPaceScavenger(gcController.heapGoal, gcController.lastHeapGoal)
1092                 unlock(&mheap_.lock)
1093         })
1094
1095         // If we just disabled GC, wait for any concurrent GC mark to
1096         // finish so we always return with no GC running.
1097         if in < 0 {
1098                 gcWaitOnMark(atomic.Load(&work.cycles))
1099         }
1100
1101         return out
1102 }
1103
1104 func readGOGC() int32 {
1105         p := gogetenv("GOGC")
1106         if p == "off" {
1107                 return -1
1108         }
1109         if n, ok := atoi32(p); ok {
1110                 return n
1111         }
1112         return 100
1113 }
1114
1115 // setMemoryLimit updates memoryLimit. commit must be called after
1116 // Returns the old value of memoryLimit.
1117 //
1118 // The world must be stopped, or mheap_.lock must be held.
1119 func (c *gcControllerState) setMemoryLimit(in int64) int64 {
1120         if !c.test {
1121                 assertWorldStoppedOrLockHeld(&mheap_.lock)
1122         }
1123
1124         out := c.memoryLimit.Load()
1125         if in >= 0 {
1126                 c.memoryLimit.Store(in)
1127         }
1128
1129         return out
1130 }
1131
1132 //go:linkname setMemoryLimit runtime/debug.setMemoryLimit
1133 func setMemoryLimit(in int64) (out int64) {
1134         // Run on the system stack since we grab the heap lock.
1135         systemstack(func() {
1136                 lock(&mheap_.lock)
1137                 out = gcController.setMemoryLimit(in)
1138                 if in < 0 || out == in {
1139                         // If we're just checking the value or not changing
1140                         // it, there's no point in doing the rest.
1141                         unlock(&mheap_.lock)
1142                         return
1143                 }
1144                 gcController.commit()
1145                 gcPaceSweeper(gcController.trigger)
1146                 gcPaceScavenger(gcController.heapGoal, gcController.lastHeapGoal)
1147                 unlock(&mheap_.lock)
1148         })
1149         return out
1150 }
1151
1152 func readGOMEMLIMIT() int64 {
1153         p := gogetenv("GOMEMLIMIT")
1154         if p == "" || p == "off" {
1155                 return maxInt64
1156         }
1157         n, ok := parseByteCount(p)
1158         if !ok {
1159                 print("GOMEMLIMIT=", p, "\n")
1160                 throw("malformed GOMEMLIMIT; see `go doc runtime/debug.SetMemoryLimit`")
1161         }
1162         return n
1163 }
1164
1165 type piController struct {
1166         kp float64 // Proportional constant.
1167         ti float64 // Integral time constant.
1168         tt float64 // Reset time.
1169
1170         min, max float64 // Output boundaries.
1171
1172         // PI controller state.
1173
1174         errIntegral float64 // Integral of the error from t=0 to now.
1175
1176         // Error flags.
1177         errOverflow   bool // Set if errIntegral ever overflowed.
1178         inputOverflow bool // Set if an operation with the input overflowed.
1179 }
1180
1181 // next provides a new sample to the controller.
1182 //
1183 // input is the sample, setpoint is the desired point, and period is how much
1184 // time (in whatever unit makes the most sense) has passed since the last sample.
1185 //
1186 // Returns a new value for the variable it's controlling, and whether the operation
1187 // completed successfully. One reason this might fail is if error has been growing
1188 // in an unbounded manner, to the point of overflow.
1189 //
1190 // In the specific case of an error overflow occurs, the errOverflow field will be
1191 // set and the rest of the controller's internal state will be fully reset.
1192 func (c *piController) next(input, setpoint, period float64) (float64, bool) {
1193         // Compute the raw output value.
1194         prop := c.kp * (setpoint - input)
1195         rawOutput := prop + c.errIntegral
1196
1197         // Clamp rawOutput into output.
1198         output := rawOutput
1199         if isInf(output) || isNaN(output) {
1200                 // The input had a large enough magnitude that either it was already
1201                 // overflowed, or some operation with it overflowed.
1202                 // Set a flag and reset. That's the safest thing to do.
1203                 c.reset()
1204                 c.inputOverflow = true
1205                 return c.min, false
1206         }
1207         if output < c.min {
1208                 output = c.min
1209         } else if output > c.max {
1210                 output = c.max
1211         }
1212
1213         // Update the controller's state.
1214         if c.ti != 0 && c.tt != 0 {
1215                 c.errIntegral += (c.kp*period/c.ti)*(setpoint-input) + (period/c.tt)*(output-rawOutput)
1216                 if isInf(c.errIntegral) || isNaN(c.errIntegral) {
1217                         // So much error has accumulated that we managed to overflow.
1218                         // The assumptions around the controller have likely broken down.
1219                         // Set a flag and reset. That's the safest thing to do.
1220                         c.reset()
1221                         c.errOverflow = true
1222                         return c.min, false
1223                 }
1224         }
1225         return output, true
1226 }
1227
1228 // reset resets the controller state, except for controller error flags.
1229 func (c *piController) reset() {
1230         c.errIntegral = 0
1231 }
1232
1233 // addIdleMarkWorker attempts to add a new idle mark worker.
1234 //
1235 // If this returns true, the caller must become an idle mark worker unless
1236 // there's no background mark worker goroutines in the pool. This case is
1237 // harmless because there are already background mark workers running.
1238 // If this returns false, the caller must NOT become an idle mark worker.
1239 //
1240 // nosplit because it may be called without a P.
1241 //go:nosplit
1242 func (c *gcControllerState) addIdleMarkWorker() bool {
1243         for {
1244                 old := c.idleMarkWorkers.Load()
1245                 n, max := int32(old&uint64(^uint32(0))), int32(old>>32)
1246                 if n >= max {
1247                         // See the comment on idleMarkWorkers for why
1248                         // n > max is tolerated.
1249                         return false
1250                 }
1251                 if n < 0 {
1252                         print("n=", n, " max=", max, "\n")
1253                         throw("negative idle mark workers")
1254                 }
1255                 new := uint64(uint32(n+1)) | (uint64(max) << 32)
1256                 if c.idleMarkWorkers.CompareAndSwap(old, new) {
1257                         return true
1258                 }
1259         }
1260 }
1261
1262 // needIdleMarkWorker is a hint as to whether another idle mark worker is needed.
1263 //
1264 // The caller must still call addIdleMarkWorker to become one. This is mainly
1265 // useful for a quick check before an expensive operation.
1266 //
1267 // nosplit because it may be called without a P.
1268 //go:nosplit
1269 func (c *gcControllerState) needIdleMarkWorker() bool {
1270         p := c.idleMarkWorkers.Load()
1271         n, max := int32(p&uint64(^uint32(0))), int32(p>>32)
1272         return n < max
1273 }
1274
1275 // removeIdleMarkWorker must be called when an new idle mark worker stops executing.
1276 func (c *gcControllerState) removeIdleMarkWorker() {
1277         for {
1278                 old := c.idleMarkWorkers.Load()
1279                 n, max := int32(old&uint64(^uint32(0))), int32(old>>32)
1280                 if n-1 < 0 {
1281                         print("n=", n, " max=", max, "\n")
1282                         throw("negative idle mark workers")
1283                 }
1284                 new := uint64(uint32(n-1)) | (uint64(max) << 32)
1285                 if c.idleMarkWorkers.CompareAndSwap(old, new) {
1286                         return
1287                 }
1288         }
1289 }
1290
1291 // setMaxIdleMarkWorkers sets the maximum number of idle mark workers allowed.
1292 //
1293 // This method is optimistic in that it does not wait for the number of
1294 // idle mark workers to reduce to max before returning; it assumes the workers
1295 // will deschedule themselves.
1296 func (c *gcControllerState) setMaxIdleMarkWorkers(max int32) {
1297         for {
1298                 old := c.idleMarkWorkers.Load()
1299                 n := int32(old & uint64(^uint32(0)))
1300                 if n < 0 {
1301                         print("n=", n, " max=", max, "\n")
1302                         throw("negative idle mark workers")
1303                 }
1304                 new := uint64(uint32(n)) | (uint64(max) << 32)
1305                 if c.idleMarkWorkers.CompareAndSwap(old, new) {
1306                         return
1307                 }
1308         }
1309 }