Source file src/runtime/mgclimit.go

     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 "internal/runtime/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  
    37  	// gcEnabled is an internal copy of gcBlackenEnabled that determines
    38  	// whether the limiter tracks total assist time.
    39  	//
    40  	// gcBlackenEnabled isn't used directly so as to keep this structure
    41  	// unit-testable.
    42  	gcEnabled bool
    43  
    44  	// transitioning is true when the GC is in a STW and transitioning between
    45  	// the mark and sweep phases.
    46  	transitioning bool
    47  
    48  	// test indicates whether this instance of the struct was made for testing purposes.
    49  	test bool
    50  
    51  	bucket struct {
    52  		// Invariants:
    53  		// - fill >= 0
    54  		// - capacity >= 0
    55  		// - fill <= capacity
    56  		fill, capacity uint64
    57  	}
    58  	// overflow is the cumulative amount of GC CPU time that we tried to fill the
    59  	// bucket with but exceeded its capacity.
    60  	overflow uint64
    61  
    62  	// assistTimePool is the accumulated assist time since the last update.
    63  	assistTimePool atomic.Int64
    64  
    65  	// idleMarkTimePool is the accumulated idle mark time since the last update.
    66  	idleMarkTimePool atomic.Int64
    67  
    68  	// idleTimePool is the accumulated time Ps spent on the idle list since the last update.
    69  	idleTimePool atomic.Int64
    70  
    71  	// lastUpdate is the nanotime timestamp of the last time update was called.
    72  	//
    73  	// Updated under lock, but may be read concurrently.
    74  	lastUpdate atomic.Int64
    75  
    76  	// lastEnabledCycle is the GC cycle that last had the limiter enabled.
    77  	lastEnabledCycle atomic.Uint32
    78  
    79  	// nprocs is an internal copy of gomaxprocs, used to determine total available
    80  	// CPU time.
    81  	//
    82  	// gomaxprocs isn't used directly so as to keep this structure unit-testable.
    83  	nprocs int32
    84  }
    85  
    86  // limiting returns true if the CPU limiter is currently enabled, meaning the Go GC
    87  // should take action to limit CPU utilization.
    88  //
    89  // It is safe to call concurrently with other operations.
    90  func (l *gcCPULimiterState) limiting() bool {
    91  	return l.enabled.Load()
    92  }
    93  
    94  // startGCTransition notifies the limiter of a GC transition.
    95  //
    96  // This call takes ownership of the limiter and disables all other means of
    97  // updating the limiter. Release ownership by calling finishGCTransition.
    98  //
    99  // It is safe to call concurrently with other operations.
   100  func (l *gcCPULimiterState) startGCTransition(enableGC bool, now int64) {
   101  	if !l.tryLock() {
   102  		// This must happen during a STW, so we can't fail to acquire the lock.
   103  		// If we did, something went wrong. Throw.
   104  		throw("failed to acquire lock to start a GC transition")
   105  	}
   106  	if l.gcEnabled == enableGC {
   107  		throw("transitioning GC to the same state as before?")
   108  	}
   109  	// Flush whatever was left between the last update and now.
   110  	l.updateLocked(now)
   111  	l.gcEnabled = enableGC
   112  	l.transitioning = true
   113  	// N.B. finishGCTransition releases the lock.
   114  	//
   115  	// We don't release here to increase the chance that if there's a failure
   116  	// to finish the transition, that we throw on failing to acquire the lock.
   117  }
   118  
   119  // finishGCTransition notifies the limiter that the GC transition is complete
   120  // and releases ownership of it. It also accumulates STW time in the bucket.
   121  // now must be the timestamp from the end of the STW pause.
   122  func (l *gcCPULimiterState) finishGCTransition(now int64) {
   123  	if !l.transitioning {
   124  		throw("finishGCTransition called without starting one?")
   125  	}
   126  	// Count the full nprocs set of CPU time because the world is stopped
   127  	// between startGCTransition and finishGCTransition. Even though the GC
   128  	// isn't running on all CPUs, it is preventing user code from doing so,
   129  	// so it might as well be.
   130  	if lastUpdate := l.lastUpdate.Load(); now >= lastUpdate {
   131  		l.accumulate(0, (now-lastUpdate)*int64(l.nprocs))
   132  	}
   133  	l.lastUpdate.Store(now)
   134  	l.transitioning = false
   135  	l.unlock()
   136  }
   137  
   138  // gcCPULimiterUpdatePeriod dictates the maximum amount of wall-clock time
   139  // we can go before updating the limiter.
   140  const gcCPULimiterUpdatePeriod = 10e6 // 10ms
   141  
   142  // needUpdate returns true if the limiter's maximum update period has been
   143  // exceeded, and so would benefit from an update.
   144  func (l *gcCPULimiterState) needUpdate(now int64) bool {
   145  	return now-l.lastUpdate.Load() > gcCPULimiterUpdatePeriod
   146  }
   147  
   148  // addAssistTime notifies the limiter of additional assist time. It will be
   149  // included in the next update.
   150  func (l *gcCPULimiterState) addAssistTime(t int64) {
   151  	l.assistTimePool.Add(t)
   152  }
   153  
   154  // addIdleTime notifies the limiter of additional time a P spent on the idle list. It will be
   155  // subtracted from the total CPU time in the next update.
   156  func (l *gcCPULimiterState) addIdleTime(t int64) {
   157  	l.idleTimePool.Add(t)
   158  }
   159  
   160  // update updates the bucket given runtime-specific information. now is the
   161  // current monotonic time in nanoseconds.
   162  //
   163  // This is safe to call concurrently with other operations, except *GCTransition.
   164  func (l *gcCPULimiterState) update(now int64) {
   165  	if !l.tryLock() {
   166  		// We failed to acquire the lock, which means something else is currently
   167  		// updating. Just drop our update, the next one to update will include
   168  		// our total assist time.
   169  		return
   170  	}
   171  	if l.transitioning {
   172  		throw("update during transition")
   173  	}
   174  	l.updateLocked(now)
   175  	l.unlock()
   176  }
   177  
   178  // updateLocked is the implementation of update. l.lock must be held.
   179  func (l *gcCPULimiterState) updateLocked(now int64) {
   180  	lastUpdate := l.lastUpdate.Load()
   181  	if now < lastUpdate {
   182  		// Defensively avoid overflow. This isn't even the latest update anyway.
   183  		return
   184  	}
   185  	windowTotalTime := (now - lastUpdate) * int64(l.nprocs)
   186  	l.lastUpdate.Store(now)
   187  
   188  	// Drain the pool of assist time.
   189  	assistTime := l.assistTimePool.Load()
   190  	if assistTime != 0 {
   191  		l.assistTimePool.Add(-assistTime)
   192  	}
   193  
   194  	// Drain the pool of idle time.
   195  	idleTime := l.idleTimePool.Load()
   196  	if idleTime != 0 {
   197  		l.idleTimePool.Add(-idleTime)
   198  	}
   199  
   200  	if !l.test {
   201  		// Consume time from in-flight events. Make sure we're not preemptible so allp can't change.
   202  		//
   203  		// The reason we do this instead of just waiting for those events to finish and push updates
   204  		// is to ensure that all the time we're accounting for happened sometime between lastUpdate
   205  		// and now. This dramatically simplifies reasoning about the limiter because we're not at
   206  		// risk of extra time being accounted for in this window than actually happened in this window,
   207  		// leading to all sorts of weird transient behavior.
   208  		mp := acquirem()
   209  		for _, pp := range allp {
   210  			typ, duration := pp.limiterEvent.consume(now)
   211  			switch typ {
   212  			case limiterEventIdleMarkWork:
   213  				fallthrough
   214  			case limiterEventIdle:
   215  				idleTime += duration
   216  				sched.idleTime.Add(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 occurring 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  		gcCPULimiter.addIdleTime(duration)
   475  	case limiterEventIdle:
   476  		gcCPULimiter.addIdleTime(duration)
   477  		sched.idleTime.Add(duration)
   478  	case limiterEventMarkAssist:
   479  		fallthrough
   480  	case limiterEventScavengeAssist:
   481  		gcCPULimiter.addAssistTime(duration)
   482  	default:
   483  		throw("limiterEvent.stop: invalid limiter event type found")
   484  	}
   485  }
   486  

View as plain text