1 // Copyright 2022 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 "runtime/internal/atomic" 8 9 // gcCPULimiter is a mechanism to limit GC CPU utilization in situations 10 // where it might become excessive and inhibit application progress (e.g. 11 // a death spiral). 12 // 13 // The core of the limiter is a leaky bucket mechanism that fills with GC 14 // CPU time and drains with mutator time. Because the bucket fills and 15 // drains with time directly (i.e. without any weighting), this effectively 16 // sets a very conservative limit of 50%. This limit could be enforced directly, 17 // however, but the purpose of the bucket is to accommodate spikes in GC CPU 18 // utilization without hurting throughput. 19 // 20 // Note that the bucket in the leaky bucket mechanism can never go negative, 21 // so the GC never gets credit for a lot of CPU time spent without the GC 22 // running. This is intentional, as an application that stays idle for, say, 23 // an entire day, could build up enough credit to fail to prevent a death 24 // spiral the following day. The bucket's capacity is the GC's only leeway. 25 // 26 // The capacity thus also sets the window the limiter considers. For example, 27 // if the capacity of the bucket is 1 cpu-second, then the limiter will not 28 // kick in until at least 1 full cpu-second in the last 2 cpu-second window 29 // is spent on GC CPU time. 30 var gcCPULimiter gcCPULimiterState 31 32 type gcCPULimiterState struct { 33 lock atomic.Uint32 34 35 enabled atomic.Bool 36 bucket struct { 37 // Invariants: 38 // - fill >= 0 39 // - capacity >= 0 40 // - fill <= capacity 41 fill, capacity uint64 42 } 43 // overflow is the cumulative amount of GC CPU time that we tried to fill the 44 // bucket with but exceeded its capacity. 45 overflow uint64 46 47 // gcEnabled is an internal copy of gcBlackenEnabled that determines 48 // whether the limiter tracks total assist time. 49 // 50 // gcBlackenEnabled isn't used directly so as to keep this structure 51 // unit-testable. 52 gcEnabled bool 53 54 // transitioning is true when the GC is in a STW and transitioning between 55 // the mark and sweep phases. 56 transitioning bool 57 58 _ uint32 // Align assistTimePool and lastUpdate on 32-bit platforms. 59 60 // assistTimePool is the accumulated assist time since the last update. 61 assistTimePool atomic.Int64 62 63 // idleMarkTimePool is the accumulated idle mark time since the last update. 64 idleMarkTimePool atomic.Int64 65 66 // idleTimePool is the accumulated time Ps spent on the idle list since the last update. 67 idleTimePool atomic.Int64 68 69 // lastUpdate is the nanotime timestamp of the last time update was called. 70 // 71 // Updated under lock, but may be read concurrently. 72 lastUpdate atomic.Int64 73 74 // lastEnabledCycle is the GC cycle that last had the limiter enabled. 75 lastEnabledCycle atomic.Uint32 76 77 // nprocs is an internal copy of gomaxprocs, used to determine total available 78 // CPU time. 79 // 80 // gomaxprocs isn't used directly so as to keep this structure unit-testable. 81 nprocs int32 82 83 // test indicates whether this instance of the struct was made for testing purposes. 84 test bool 85 } 86 87 // limiting returns true if the CPU limiter is currently enabled, meaning the Go GC 88 // should take action to limit CPU utilization. 89 // 90 // It is safe to call concurrently with other operations. 91 func (l *gcCPULimiterState) limiting() bool { 92 return l.enabled.Load() 93 } 94 95 // startGCTransition notifies the limiter of a GC transition. 96 // 97 // This call takes ownership of the limiter and disables all other means of 98 // updating the limiter. Release ownership by calling finishGCTransition. 99 // 100 // It is safe to call concurrently with other operations. 101 func (l *gcCPULimiterState) startGCTransition(enableGC bool, now int64) { 102 if !l.tryLock() { 103 // This must happen during a STW, so we can't fail to acquire the lock. 104 // If we did, something went wrong. Throw. 105 throw("failed to acquire lock to start a GC transition") 106 } 107 if l.gcEnabled == enableGC { 108 throw("transitioning GC to the same state as before?") 109 } 110 // Flush whatever was left between the last update and now. 111 l.updateLocked(now) 112 l.gcEnabled = enableGC 113 l.transitioning = true 114 // N.B. finishGCTransition releases the lock. 115 // 116 // We don't release here to increase the chance that if there's a failure 117 // to finish the transition, that we throw on failing to acquire the lock. 118 } 119 120 // finishGCTransition notifies the limiter that the GC transition is complete 121 // and releases ownership of it. It also accumulates STW time in the bucket. 122 // now must be the timestamp from the end of the STW pause. 123 func (l *gcCPULimiterState) finishGCTransition(now int64) { 124 if !l.transitioning { 125 throw("finishGCTransition called without starting one?") 126 } 127 // Count the full nprocs set of CPU time because the world is stopped 128 // between startGCTransition and finishGCTransition. Even though the GC 129 // isn't running on all CPUs, it is preventing user code from doing so, 130 // so it might as well be. 131 if lastUpdate := l.lastUpdate.Load(); now >= lastUpdate { 132 l.accumulate(0, (now-lastUpdate)*int64(l.nprocs)) 133 } 134 l.lastUpdate.Store(now) 135 l.transitioning = false 136 l.unlock() 137 } 138 139 // gcCPULimiterUpdatePeriod dictates the maximum amount of wall-clock time 140 // we can go before updating the limiter. 141 const gcCPULimiterUpdatePeriod = 10e6 // 10ms 142 143 // needUpdate returns true if the limiter's maximum update period has been 144 // exceeded, and so would benefit from an update. 145 func (l *gcCPULimiterState) needUpdate(now int64) bool { 146 return now-l.lastUpdate.Load() > gcCPULimiterUpdatePeriod 147 } 148 149 // addAssistTime notifies the limiter of additional assist time. It will be 150 // included in the next update. 151 func (l *gcCPULimiterState) addAssistTime(t int64) { 152 l.assistTimePool.Add(t) 153 } 154 155 // addIdleTime notifies the limiter of additional time a P spent on the idle list. It will be 156 // subtracted from the total CPU time in the next update. 157 func (l *gcCPULimiterState) addIdleTime(t int64) { 158 l.idleTimePool.Add(t) 159 } 160 161 // update updates the bucket given runtime-specific information. now is the 162 // current monotonic time in nanoseconds. 163 // 164 // This is safe to call concurrently with other operations, except *GCTransition. 165 func (l *gcCPULimiterState) update(now int64) { 166 if !l.tryLock() { 167 // We failed to acquire the lock, which means something else is currently 168 // updating. Just drop our update, the next one to update will include 169 // our total assist time. 170 return 171 } 172 if l.transitioning { 173 throw("update during transition") 174 } 175 l.updateLocked(now) 176 l.unlock() 177 } 178 179 // updatedLocked is the implementation of update. l.lock must be held. 180 func (l *gcCPULimiterState) updateLocked(now int64) { 181 lastUpdate := l.lastUpdate.Load() 182 if now < lastUpdate { 183 // Defensively avoid overflow. This isn't even the latest update anyway. 184 return 185 } 186 windowTotalTime := (now - lastUpdate) * int64(l.nprocs) 187 l.lastUpdate.Store(now) 188 189 // Drain the pool of assist time. 190 assistTime := l.assistTimePool.Load() 191 if assistTime != 0 { 192 l.assistTimePool.Add(-assistTime) 193 } 194 195 // Drain the pool of idle time. 196 idleTime := l.idleTimePool.Load() 197 if idleTime != 0 { 198 l.idleTimePool.Add(-idleTime) 199 } 200 201 if !l.test { 202 // Consume time from in-flight events. Make sure we're not preemptible so allp can't change. 203 // 204 // The reason we do this instead of just waiting for those events to finish and push updates 205 // is to ensure that all the time we're accounting for happened sometime between lastUpdate 206 // and now. This dramatically simplifies reasoning about the limiter because we're not at 207 // risk of extra time being accounted for in this window than actually happened in this window, 208 // leading to all sorts of weird transient behavior. 209 mp := acquirem() 210 for _, pp := range allp { 211 typ, duration := pp.limiterEvent.consume(now) 212 switch typ { 213 case limiterEventIdleMarkWork: 214 fallthrough 215 case limiterEventIdle: 216 idleTime += duration 217 case limiterEventMarkAssist: 218 fallthrough 219 case limiterEventScavengeAssist: 220 assistTime += duration 221 case limiterEventNone: 222 break 223 default: 224 throw("invalid limiter event type found") 225 } 226 } 227 releasem(mp) 228 } 229 230 // Compute total GC time. 231 windowGCTime := assistTime 232 if l.gcEnabled { 233 windowGCTime += int64(float64(windowTotalTime) * gcBackgroundUtilization) 234 } 235 236 // Subtract out all idle time from the total time. Do this after computing 237 // GC time, because the background utilization is dependent on the *real* 238 // total time, not the total time after idle time is subtracted. 239 // 240 // Idle time is counted as any time that a P is on the P idle list plus idle mark 241 // time. Idle mark workers soak up time that the application spends idle. 242 // 243 // On a heavily undersubscribed system, any additional idle time can skew GC CPU 244 // utilization, because the GC might be executing continuously and thrashing, 245 // yet the CPU utilization with respect to GOMAXPROCS will be quite low, so 246 // the limiter fails to turn on. By subtracting idle time, we're removing time that 247 // we know the application was idle giving a more accurate picture of whether 248 // the GC is thrashing. 249 // 250 // Note that this can cause the limiter to turn on even if it's not needed. For 251 // instance, on a system with 32 Ps but only 1 running goroutine, each GC will have 252 // 8 dedicated GC workers. Assuming the GC cycle is half mark phase and half sweep 253 // phase, then the GC CPU utilization over that cycle, with idle time removed, will 254 // be 8/(8+2) = 80%. Even though the limiter turns on, though, assist should be 255 // unnecessary, as the GC has way more CPU time to outpace the 1 goroutine that's 256 // running. 257 windowTotalTime -= idleTime 258 259 l.accumulate(windowTotalTime-windowGCTime, windowGCTime) 260 } 261 262 // accumulate adds time to the bucket and signals whether the limiter is enabled. 263 // 264 // This is an internal function that deals just with the bucket. Prefer update. 265 // l.lock must be held. 266 func (l *gcCPULimiterState) accumulate(mutatorTime, gcTime int64) { 267 headroom := l.bucket.capacity - l.bucket.fill 268 enabled := headroom == 0 269 270 // Let's be careful about three things here: 271 // 1. The addition and subtraction, for the invariants. 272 // 2. Overflow. 273 // 3. Excessive mutation of l.enabled, which is accessed 274 // by all assists, potentially more than once. 275 change := gcTime - mutatorTime 276 277 // Handle limiting case. 278 if change > 0 && headroom <= uint64(change) { 279 l.overflow += uint64(change) - headroom 280 l.bucket.fill = l.bucket.capacity 281 if !enabled { 282 l.enabled.Store(true) 283 l.lastEnabledCycle.Store(memstats.numgc + 1) 284 } 285 return 286 } 287 288 // Handle non-limiting cases. 289 if change < 0 && l.bucket.fill <= uint64(-change) { 290 // Bucket emptied. 291 l.bucket.fill = 0 292 } else { 293 // All other cases. 294 l.bucket.fill -= uint64(-change) 295 } 296 if change != 0 && enabled { 297 l.enabled.Store(false) 298 } 299 } 300 301 // tryLock attempts to lock l. Returns true on success. 302 func (l *gcCPULimiterState) tryLock() bool { 303 return l.lock.CompareAndSwap(0, 1) 304 } 305 306 // unlock releases the lock on l. Must be called if tryLock returns true. 307 func (l *gcCPULimiterState) unlock() { 308 old := l.lock.Swap(0) 309 if old != 1 { 310 throw("double unlock") 311 } 312 } 313 314 // capacityPerProc is the limiter's bucket capacity for each P in GOMAXPROCS. 315 const capacityPerProc = 1e9 // 1 second in nanoseconds 316 317 // resetCapacity updates the capacity based on GOMAXPROCS. Must not be called 318 // while the GC is enabled. 319 // 320 // It is safe to call concurrently with other operations. 321 func (l *gcCPULimiterState) resetCapacity(now int64, nprocs int32) { 322 if !l.tryLock() { 323 // This must happen during a STW, so we can't fail to acquire the lock. 324 // If we did, something went wrong. Throw. 325 throw("failed to acquire lock to reset capacity") 326 } 327 // Flush the rest of the time for this period. 328 l.updateLocked(now) 329 l.nprocs = nprocs 330 331 l.bucket.capacity = uint64(nprocs) * capacityPerProc 332 if l.bucket.fill > l.bucket.capacity { 333 l.bucket.fill = l.bucket.capacity 334 l.enabled.Store(true) 335 l.lastEnabledCycle.Store(memstats.numgc + 1) 336 } else if l.bucket.fill < l.bucket.capacity { 337 l.enabled.Store(false) 338 } 339 l.unlock() 340 } 341 342 // limiterEventType indicates the type of an event occuring on some P. 343 // 344 // These events represent the full set of events that the GC CPU limiter tracks 345 // to execute its function. 346 // 347 // This type may use no more than limiterEventBits bits of information. 348 type limiterEventType uint8 349 350 const ( 351 limiterEventNone limiterEventType = iota // None of the following events. 352 limiterEventIdleMarkWork // Refers to an idle mark worker (see gcMarkWorkerMode). 353 limiterEventMarkAssist // Refers to mark assist (see gcAssistAlloc). 354 limiterEventScavengeAssist // Refers to a scavenge assist (see allocSpan). 355 limiterEventIdle // Refers to time a P spent on the idle list. 356 357 limiterEventBits = 3 358 ) 359 360 // limiterEventTypeMask is a mask for the bits in p.limiterEventStart that represent 361 // the event type. The rest of the bits of that field represent a timestamp. 362 const ( 363 limiterEventTypeMask = uint64((1<<limiterEventBits)-1) << (64 - limiterEventBits) 364 limiterEventStampNone = limiterEventStamp(0) 365 ) 366 367 // limiterEventStamp is a nanotime timestamp packed with a limiterEventType. 368 type limiterEventStamp uint64 369 370 // makeLimiterEventStamp creates a new stamp from the event type and the current timestamp. 371 func makeLimiterEventStamp(typ limiterEventType, now int64) limiterEventStamp { 372 return limiterEventStamp(uint64(typ)<<(64-limiterEventBits) | (uint64(now) &^ limiterEventTypeMask)) 373 } 374 375 // duration computes the difference between now and the start time stored in the stamp. 376 // 377 // Returns 0 if the difference is negative, which may happen if now is stale or if the 378 // before and after timestamps cross a 2^(64-limiterEventBits) boundary. 379 func (s limiterEventStamp) duration(now int64) int64 { 380 // The top limiterEventBits bits of the timestamp are derived from the current time 381 // when computing a duration. 382 start := int64((uint64(now) & limiterEventTypeMask) | (uint64(s) &^ limiterEventTypeMask)) 383 if now < start { 384 return 0 385 } 386 return now - start 387 } 388 389 // type extracts the event type from the stamp. 390 func (s limiterEventStamp) typ() limiterEventType { 391 return limiterEventType(s >> (64 - limiterEventBits)) 392 } 393 394 // limiterEvent represents tracking state for an event tracked by the GC CPU limiter. 395 type limiterEvent struct { 396 stamp atomic.Uint64 // Stores a limiterEventStamp. 397 } 398 399 // start begins tracking a new limiter event of the current type. If an event 400 // is already in flight, then a new event cannot begin because the current time is 401 // already being attributed to that event. In this case, this function returns false. 402 // Otherwise, it returns true. 403 // 404 // The caller must be non-preemptible until at least stop is called or this function 405 // returns false. Because this is trying to measure "on-CPU" time of some event, getting 406 // scheduled away during it can mean that whatever we're measuring isn't a reflection 407 // of "on-CPU" time. The OS could deschedule us at any time, but we want to maintain as 408 // close of an approximation as we can. 409 func (e *limiterEvent) start(typ limiterEventType, now int64) bool { 410 if limiterEventStamp(e.stamp.Load()).typ() != limiterEventNone { 411 return false 412 } 413 e.stamp.Store(uint64(makeLimiterEventStamp(typ, now))) 414 return true 415 } 416 417 // consume acquires the partial event CPU time from any in-flight event. 418 // It achieves this by storing the current time as the new event time. 419 // 420 // Returns the type of the in-flight event, as well as how long it's currently been 421 // executing for. Returns limiterEventNone if no event is active. 422 func (e *limiterEvent) consume(now int64) (typ limiterEventType, duration int64) { 423 // Read the limiter event timestamp and update it to now. 424 for { 425 old := limiterEventStamp(e.stamp.Load()) 426 typ = old.typ() 427 if typ == limiterEventNone { 428 // There's no in-flight event, so just push that up. 429 return 430 } 431 duration = old.duration(now) 432 if duration == 0 { 433 // We might have a stale now value, or this crossed the 434 // 2^(64-limiterEventBits) boundary in the clock readings. 435 // Just ignore it. 436 return limiterEventNone, 0 437 } 438 new := makeLimiterEventStamp(typ, now) 439 if e.stamp.CompareAndSwap(uint64(old), uint64(new)) { 440 break 441 } 442 } 443 return 444 } 445 446 // stop stops the active limiter event. Throws if the 447 // 448 // The caller must be non-preemptible across the event. See start as to why. 449 func (e *limiterEvent) stop(typ limiterEventType, now int64) { 450 var stamp limiterEventStamp 451 for { 452 stamp = limiterEventStamp(e.stamp.Load()) 453 if stamp.typ() != typ { 454 print("runtime: want=", typ, " got=", stamp.typ(), "\n") 455 throw("limiterEvent.stop: found wrong event in p's limiter event slot") 456 } 457 if e.stamp.CompareAndSwap(uint64(stamp), uint64(limiterEventStampNone)) { 458 break 459 } 460 } 461 duration := stamp.duration(now) 462 if duration == 0 { 463 // It's possible that we're missing time because we crossed a 464 // 2^(64-limiterEventBits) boundary between the start and end. 465 // In this case, we're dropping that information. This is OK because 466 // at worst it'll cause a transient hiccup that will quickly resolve 467 // itself as all new timestamps begin on the other side of the boundary. 468 // Such a hiccup should be incredibly rare. 469 return 470 } 471 // Account for the event. 472 switch typ { 473 case limiterEventIdleMarkWork: 474 fallthrough 475 case limiterEventIdle: 476 gcCPULimiter.addIdleTime(duration) 477 case limiterEventMarkAssist: 478 fallthrough 479 case limiterEventScavengeAssist: 480 gcCPULimiter.addAssistTime(duration) 481 default: 482 throw("limiterEvent.stop: invalid limiter event type found") 483 } 484 } 485