diff options
Diffstat (limited to 'src/runtime/mgclimit.go')
| -rw-r--r-- | src/runtime/mgclimit.go | 484 |
1 files changed, 484 insertions, 0 deletions
diff --git a/src/runtime/mgclimit.go b/src/runtime/mgclimit.go new file mode 100644 index 0000000..ef3cc08 --- /dev/null +++ b/src/runtime/mgclimit.go @@ -0,0 +1,484 @@ +// Copyright 2022 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package runtime + +import "runtime/internal/atomic" + +// gcCPULimiter is a mechanism to limit GC CPU utilization in situations +// where it might become excessive and inhibit application progress (e.g. +// a death spiral). +// +// The core of the limiter is a leaky bucket mechanism that fills with GC +// CPU time and drains with mutator time. Because the bucket fills and +// drains with time directly (i.e. without any weighting), this effectively +// sets a very conservative limit of 50%. This limit could be enforced directly, +// however, but the purpose of the bucket is to accommodate spikes in GC CPU +// utilization without hurting throughput. +// +// Note that the bucket in the leaky bucket mechanism can never go negative, +// so the GC never gets credit for a lot of CPU time spent without the GC +// running. This is intentional, as an application that stays idle for, say, +// an entire day, could build up enough credit to fail to prevent a death +// spiral the following day. The bucket's capacity is the GC's only leeway. +// +// The capacity thus also sets the window the limiter considers. For example, +// if the capacity of the bucket is 1 cpu-second, then the limiter will not +// kick in until at least 1 full cpu-second in the last 2 cpu-second window +// is spent on GC CPU time. +var gcCPULimiter gcCPULimiterState + +type gcCPULimiterState struct { + lock atomic.Uint32 + + enabled atomic.Bool + bucket struct { + // Invariants: + // - fill >= 0 + // - capacity >= 0 + // - fill <= capacity + fill, capacity uint64 + } + // overflow is the cumulative amount of GC CPU time that we tried to fill the + // bucket with but exceeded its capacity. + overflow uint64 + + // gcEnabled is an internal copy of gcBlackenEnabled that determines + // whether the limiter tracks total assist time. + // + // gcBlackenEnabled isn't used directly so as to keep this structure + // unit-testable. + gcEnabled bool + + // transitioning is true when the GC is in a STW and transitioning between + // the mark and sweep phases. + transitioning bool + + // assistTimePool is the accumulated assist time since the last update. + assistTimePool atomic.Int64 + + // idleMarkTimePool is the accumulated idle mark time since the last update. + idleMarkTimePool atomic.Int64 + + // idleTimePool is the accumulated time Ps spent on the idle list since the last update. + idleTimePool atomic.Int64 + + // lastUpdate is the nanotime timestamp of the last time update was called. + // + // Updated under lock, but may be read concurrently. + lastUpdate atomic.Int64 + + // lastEnabledCycle is the GC cycle that last had the limiter enabled. + lastEnabledCycle atomic.Uint32 + + // nprocs is an internal copy of gomaxprocs, used to determine total available + // CPU time. + // + // gomaxprocs isn't used directly so as to keep this structure unit-testable. + nprocs int32 + + // test indicates whether this instance of the struct was made for testing purposes. + test bool +} + +// limiting returns true if the CPU limiter is currently enabled, meaning the Go GC +// should take action to limit CPU utilization. +// +// It is safe to call concurrently with other operations. +func (l *gcCPULimiterState) limiting() bool { + return l.enabled.Load() +} + +// startGCTransition notifies the limiter of a GC transition. +// +// This call takes ownership of the limiter and disables all other means of +// updating the limiter. Release ownership by calling finishGCTransition. +// +// It is safe to call concurrently with other operations. +func (l *gcCPULimiterState) startGCTransition(enableGC bool, now int64) { + if !l.tryLock() { + // This must happen during a STW, so we can't fail to acquire the lock. + // If we did, something went wrong. Throw. + throw("failed to acquire lock to start a GC transition") + } + if l.gcEnabled == enableGC { + throw("transitioning GC to the same state as before?") + } + // Flush whatever was left between the last update and now. + l.updateLocked(now) + l.gcEnabled = enableGC + l.transitioning = true + // N.B. finishGCTransition releases the lock. + // + // We don't release here to increase the chance that if there's a failure + // to finish the transition, that we throw on failing to acquire the lock. +} + +// finishGCTransition notifies the limiter that the GC transition is complete +// and releases ownership of it. It also accumulates STW time in the bucket. +// now must be the timestamp from the end of the STW pause. +func (l *gcCPULimiterState) finishGCTransition(now int64) { + if !l.transitioning { + throw("finishGCTransition called without starting one?") + } + // Count the full nprocs set of CPU time because the world is stopped + // between startGCTransition and finishGCTransition. Even though the GC + // isn't running on all CPUs, it is preventing user code from doing so, + // so it might as well be. + if lastUpdate := l.lastUpdate.Load(); now >= lastUpdate { + l.accumulate(0, (now-lastUpdate)*int64(l.nprocs)) + } + l.lastUpdate.Store(now) + l.transitioning = false + l.unlock() +} + +// gcCPULimiterUpdatePeriod dictates the maximum amount of wall-clock time +// we can go before updating the limiter. +const gcCPULimiterUpdatePeriod = 10e6 // 10ms + +// needUpdate returns true if the limiter's maximum update period has been +// exceeded, and so would benefit from an update. +func (l *gcCPULimiterState) needUpdate(now int64) bool { + return now-l.lastUpdate.Load() > gcCPULimiterUpdatePeriod +} + +// addAssistTime notifies the limiter of additional assist time. It will be +// included in the next update. +func (l *gcCPULimiterState) addAssistTime(t int64) { + l.assistTimePool.Add(t) +} + +// addIdleTime notifies the limiter of additional time a P spent on the idle list. It will be +// subtracted from the total CPU time in the next update. +func (l *gcCPULimiterState) addIdleTime(t int64) { + l.idleTimePool.Add(t) +} + +// update updates the bucket given runtime-specific information. now is the +// current monotonic time in nanoseconds. +// +// This is safe to call concurrently with other operations, except *GCTransition. +func (l *gcCPULimiterState) update(now int64) { + if !l.tryLock() { + // We failed to acquire the lock, which means something else is currently + // updating. Just drop our update, the next one to update will include + // our total assist time. + return + } + if l.transitioning { + throw("update during transition") + } + l.updateLocked(now) + l.unlock() +} + +// updateLocked is the implementation of update. l.lock must be held. +func (l *gcCPULimiterState) updateLocked(now int64) { + lastUpdate := l.lastUpdate.Load() + if now < lastUpdate { + // Defensively avoid overflow. This isn't even the latest update anyway. + return + } + windowTotalTime := (now - lastUpdate) * int64(l.nprocs) + l.lastUpdate.Store(now) + + // Drain the pool of assist time. + assistTime := l.assistTimePool.Load() + if assistTime != 0 { + l.assistTimePool.Add(-assistTime) + } + + // Drain the pool of idle time. + idleTime := l.idleTimePool.Load() + if idleTime != 0 { + l.idleTimePool.Add(-idleTime) + } + + if !l.test { + // Consume time from in-flight events. Make sure we're not preemptible so allp can't change. + // + // The reason we do this instead of just waiting for those events to finish and push updates + // is to ensure that all the time we're accounting for happened sometime between lastUpdate + // and now. This dramatically simplifies reasoning about the limiter because we're not at + // risk of extra time being accounted for in this window than actually happened in this window, + // leading to all sorts of weird transient behavior. + mp := acquirem() + for _, pp := range allp { + typ, duration := pp.limiterEvent.consume(now) + switch typ { + case limiterEventIdleMarkWork: + fallthrough + case limiterEventIdle: + idleTime += duration + sched.idleTime.Add(duration) + case limiterEventMarkAssist: + fallthrough + case limiterEventScavengeAssist: + assistTime += duration + case limiterEventNone: + break + default: + throw("invalid limiter event type found") + } + } + releasem(mp) + } + + // Compute total GC time. + windowGCTime := assistTime + if l.gcEnabled { + windowGCTime += int64(float64(windowTotalTime) * gcBackgroundUtilization) + } + + // Subtract out all idle time from the total time. Do this after computing + // GC time, because the background utilization is dependent on the *real* + // total time, not the total time after idle time is subtracted. + // + // Idle time is counted as any time that a P is on the P idle list plus idle mark + // time. Idle mark workers soak up time that the application spends idle. + // + // On a heavily undersubscribed system, any additional idle time can skew GC CPU + // utilization, because the GC might be executing continuously and thrashing, + // yet the CPU utilization with respect to GOMAXPROCS will be quite low, so + // the limiter fails to turn on. By subtracting idle time, we're removing time that + // we know the application was idle giving a more accurate picture of whether + // the GC is thrashing. + // + // Note that this can cause the limiter to turn on even if it's not needed. For + // instance, on a system with 32 Ps but only 1 running goroutine, each GC will have + // 8 dedicated GC workers. Assuming the GC cycle is half mark phase and half sweep + // phase, then the GC CPU utilization over that cycle, with idle time removed, will + // be 8/(8+2) = 80%. Even though the limiter turns on, though, assist should be + // unnecessary, as the GC has way more CPU time to outpace the 1 goroutine that's + // running. + windowTotalTime -= idleTime + + l.accumulate(windowTotalTime-windowGCTime, windowGCTime) +} + +// accumulate adds time to the bucket and signals whether the limiter is enabled. +// +// This is an internal function that deals just with the bucket. Prefer update. +// l.lock must be held. +func (l *gcCPULimiterState) accumulate(mutatorTime, gcTime int64) { + headroom := l.bucket.capacity - l.bucket.fill + enabled := headroom == 0 + + // Let's be careful about three things here: + // 1. The addition and subtraction, for the invariants. + // 2. Overflow. + // 3. Excessive mutation of l.enabled, which is accessed + // by all assists, potentially more than once. + change := gcTime - mutatorTime + + // Handle limiting case. + if change > 0 && headroom <= uint64(change) { + l.overflow += uint64(change) - headroom + l.bucket.fill = l.bucket.capacity + if !enabled { + l.enabled.Store(true) + l.lastEnabledCycle.Store(memstats.numgc + 1) + } + return + } + + // Handle non-limiting cases. + if change < 0 && l.bucket.fill <= uint64(-change) { + // Bucket emptied. + l.bucket.fill = 0 + } else { + // All other cases. + l.bucket.fill -= uint64(-change) + } + if change != 0 && enabled { + l.enabled.Store(false) + } +} + +// tryLock attempts to lock l. Returns true on success. +func (l *gcCPULimiterState) tryLock() bool { + return l.lock.CompareAndSwap(0, 1) +} + +// unlock releases the lock on l. Must be called if tryLock returns true. +func (l *gcCPULimiterState) unlock() { + old := l.lock.Swap(0) + if old != 1 { + throw("double unlock") + } +} + +// capacityPerProc is the limiter's bucket capacity for each P in GOMAXPROCS. +const capacityPerProc = 1e9 // 1 second in nanoseconds + +// resetCapacity updates the capacity based on GOMAXPROCS. Must not be called +// while the GC is enabled. +// +// It is safe to call concurrently with other operations. +func (l *gcCPULimiterState) resetCapacity(now int64, nprocs int32) { + if !l.tryLock() { + // This must happen during a STW, so we can't fail to acquire the lock. + // If we did, something went wrong. Throw. + throw("failed to acquire lock to reset capacity") + } + // Flush the rest of the time for this period. + l.updateLocked(now) + l.nprocs = nprocs + + l.bucket.capacity = uint64(nprocs) * capacityPerProc + if l.bucket.fill > l.bucket.capacity { + l.bucket.fill = l.bucket.capacity + l.enabled.Store(true) + l.lastEnabledCycle.Store(memstats.numgc + 1) + } else if l.bucket.fill < l.bucket.capacity { + l.enabled.Store(false) + } + l.unlock() +} + +// limiterEventType indicates the type of an event occurring on some P. +// +// These events represent the full set of events that the GC CPU limiter tracks +// to execute its function. +// +// This type may use no more than limiterEventBits bits of information. +type limiterEventType uint8 + +const ( + limiterEventNone limiterEventType = iota // None of the following events. + limiterEventIdleMarkWork // Refers to an idle mark worker (see gcMarkWorkerMode). + limiterEventMarkAssist // Refers to mark assist (see gcAssistAlloc). + limiterEventScavengeAssist // Refers to a scavenge assist (see allocSpan). + limiterEventIdle // Refers to time a P spent on the idle list. + + limiterEventBits = 3 +) + +// limiterEventTypeMask is a mask for the bits in p.limiterEventStart that represent +// the event type. The rest of the bits of that field represent a timestamp. +const ( + limiterEventTypeMask = uint64((1<<limiterEventBits)-1) << (64 - limiterEventBits) + limiterEventStampNone = limiterEventStamp(0) +) + +// limiterEventStamp is a nanotime timestamp packed with a limiterEventType. +type limiterEventStamp uint64 + +// makeLimiterEventStamp creates a new stamp from the event type and the current timestamp. +func makeLimiterEventStamp(typ limiterEventType, now int64) limiterEventStamp { + return limiterEventStamp(uint64(typ)<<(64-limiterEventBits) | (uint64(now) &^ limiterEventTypeMask)) +} + +// duration computes the difference between now and the start time stored in the stamp. +// +// Returns 0 if the difference is negative, which may happen if now is stale or if the +// before and after timestamps cross a 2^(64-limiterEventBits) boundary. +func (s limiterEventStamp) duration(now int64) int64 { + // The top limiterEventBits bits of the timestamp are derived from the current time + // when computing a duration. + start := int64((uint64(now) & limiterEventTypeMask) | (uint64(s) &^ limiterEventTypeMask)) + if now < start { + return 0 + } + return now - start +} + +// type extracts the event type from the stamp. +func (s limiterEventStamp) typ() limiterEventType { + return limiterEventType(s >> (64 - limiterEventBits)) +} + +// limiterEvent represents tracking state for an event tracked by the GC CPU limiter. +type limiterEvent struct { + stamp atomic.Uint64 // Stores a limiterEventStamp. +} + +// start begins tracking a new limiter event of the current type. If an event +// is already in flight, then a new event cannot begin because the current time is +// already being attributed to that event. In this case, this function returns false. +// Otherwise, it returns true. +// +// The caller must be non-preemptible until at least stop is called or this function +// returns false. Because this is trying to measure "on-CPU" time of some event, getting +// scheduled away during it can mean that whatever we're measuring isn't a reflection +// of "on-CPU" time. The OS could deschedule us at any time, but we want to maintain as +// close of an approximation as we can. +func (e *limiterEvent) start(typ limiterEventType, now int64) bool { + if limiterEventStamp(e.stamp.Load()).typ() != limiterEventNone { + return false + } + e.stamp.Store(uint64(makeLimiterEventStamp(typ, now))) + return true +} + +// consume acquires the partial event CPU time from any in-flight event. +// It achieves this by storing the current time as the new event time. +// +// Returns the type of the in-flight event, as well as how long it's currently been +// executing for. Returns limiterEventNone if no event is active. +func (e *limiterEvent) consume(now int64) (typ limiterEventType, duration int64) { + // Read the limiter event timestamp and update it to now. + for { + old := limiterEventStamp(e.stamp.Load()) + typ = old.typ() + if typ == limiterEventNone { + // There's no in-flight event, so just push that up. + return + } + duration = old.duration(now) + if duration == 0 { + // We might have a stale now value, or this crossed the + // 2^(64-limiterEventBits) boundary in the clock readings. + // Just ignore it. + return limiterEventNone, 0 + } + new := makeLimiterEventStamp(typ, now) + if e.stamp.CompareAndSwap(uint64(old), uint64(new)) { + break + } + } + return +} + +// stop stops the active limiter event. Throws if the +// +// The caller must be non-preemptible across the event. See start as to why. +func (e *limiterEvent) stop(typ limiterEventType, now int64) { + var stamp limiterEventStamp + for { + stamp = limiterEventStamp(e.stamp.Load()) + if stamp.typ() != typ { + print("runtime: want=", typ, " got=", stamp.typ(), "\n") + throw("limiterEvent.stop: found wrong event in p's limiter event slot") + } + if e.stamp.CompareAndSwap(uint64(stamp), uint64(limiterEventStampNone)) { + break + } + } + duration := stamp.duration(now) + if duration == 0 { + // It's possible that we're missing time because we crossed a + // 2^(64-limiterEventBits) boundary between the start and end. + // In this case, we're dropping that information. This is OK because + // at worst it'll cause a transient hiccup that will quickly resolve + // itself as all new timestamps begin on the other side of the boundary. + // Such a hiccup should be incredibly rare. + return + } + // Account for the event. + switch typ { + case limiterEventIdleMarkWork: + gcCPULimiter.addIdleTime(duration) + case limiterEventIdle: + gcCPULimiter.addIdleTime(duration) + sched.idleTime.Add(duration) + case limiterEventMarkAssist: + fallthrough + case limiterEventScavengeAssist: + gcCPULimiter.addAssistTime(duration) + default: + throw("limiterEvent.stop: invalid limiter event type found") + } +} |