From 3c39b2ed116fa9edba6fde3be566310c7b76114c Mon Sep 17 00:00:00 2001 From: Russ Cox Date: Thu, 29 Feb 2024 16:52:58 -0500 Subject: [PATCH] runtime: avoid pp.timers.lock in updateTimerPMask The comment in updateTimerPMask is wrong. It says: // Looks like there are no timers, however another P // may be adding one at this very moment. // Take the lock to synchronize. This was my incorrect simplification of the original comment from CL 264477 when I was renaming all the things it mentioned: // Looks like there are no timers, however another P may transiently // decrement numTimers when handling a timerModified timer in // checkTimers. We must take timersLock to serialize with these changes. updateTimerPMask is being called by pidleput, so the P in question is not in use. And other P's cannot add to this P. As the original comment more precisely noted, the problem was that other P's might be calling timers.check, which updates ts.len occasionally while ts is locked, and one of those updates might "leak" an ephemeral len==0 even when the heap is not going to be empty when the P is finally unlocked. The lock/unlock in updateTimerPMask synchronizes to avoid that. But this defeats most of the purpose of using ts.len in the first place. Instead of requiring that synchronization, we can arrange that ts.len only ever shows a "publishable" length, meaning the len(ts.heap) we leave behind during ts.unlock. Having done that, updateTimerPMask can be inlined into pidleput. The big comment on updateTimerPMask explaining how timerpMask works is better placed as the doc comment for timerpMask itself, so move it there. Change-Id: I5442c9bb7f1473b5fd37c43165429d087012e73f Reviewed-on: https://go-review.googlesource.com/c/go/+/568336 Reviewed-by: Michael Pratt LUCI-TryBot-Result: Go LUCI Auto-Submit: Russ Cox --- src/runtime/proc.go | 4 +++- src/runtime/runtime2.go | 31 ++++++++++++++++++++++++ src/runtime/time.go | 52 +++++++---------------------------------- 3 files changed, 43 insertions(+), 44 deletions(-) diff --git a/src/runtime/proc.go b/src/runtime/proc.go index a49a282bb7..36e895b8f0 100644 --- a/src/runtime/proc.go +++ b/src/runtime/proc.go @@ -6446,7 +6446,9 @@ func pidleput(pp *p, now int64) int64 { if now == 0 { now = nanotime() } - updateTimerPMask(pp) // clear if there are no timers. + if pp.timers.len.Load() == 0 { + timerpMask.clear(pp.id) + } idlepMask.set(pp.id) pp.link = sched.pidle sched.pidle.set(pp) diff --git a/src/runtime/runtime2.go b/src/runtime/runtime2.go index 985c1ffab4..64a2cc7163 100644 --- a/src/runtime/runtime2.go +++ b/src/runtime/runtime2.go @@ -1156,13 +1156,17 @@ var ( forcegc forcegcstate sched schedt newprocs int32 +) +var ( // allpLock protects P-less reads and size changes of allp, idlepMask, // and timerpMask, and all writes to allp. allpLock mutex + // len(allp) == gomaxprocs; may change at safe points, otherwise // immutable. allp []*p + // Bitmask of Ps in _Pidle list, one bit per P. Reads and writes must // be atomic. Length may change at safe points. // @@ -1174,10 +1178,37 @@ var ( // // N.B., procresize takes ownership of all Ps in stopTheWorldWithSema. idlepMask pMask + // Bitmask of Ps that may have a timer, one bit per P. Reads and writes // must be atomic. Length may change at safe points. + // + // Ideally, the timer mask would be kept immediately consistent on any timer + // operations. Unfortunately, updating a shared global data structure in the + // timer hot path adds too much overhead in applications frequently switching + // between no timers and some timers. + // + // As a compromise, the timer mask is updated only on pidleget / pidleput. A + // running P (returned by pidleget) may add a timer at any time, so its mask + // must be set. An idle P (passed to pidleput) cannot add new timers while + // idle, so if it has no timers at that time, its mask may be cleared. + // + // Thus, we get the following effects on timer-stealing in findrunnable: + // + // - Idle Ps with no timers when they go idle are never checked in findrunnable + // (for work- or timer-stealing; this is the ideal case). + // - Running Ps must always be checked. + // - Idle Ps whose timers are stolen must continue to be checked until they run + // again, even after timer expiration. + // + // When the P starts running again, the mask should be set, as a timer may be + // added at any time. + // + // TODO(prattmic): Additional targeted updates may improve the above cases. + // e.g., updating the mask when stealing a timer. timerpMask pMask +) +var ( // Pool of GC parked background workers. Entries are type // *gcBgMarkWorkerNode. gcBgMarkWorkerPool lfstack diff --git a/src/runtime/time.go b/src/runtime/time.go index cae3a3db47..f31ca3aeb7 100644 --- a/src/runtime/time.go +++ b/src/runtime/time.go @@ -89,6 +89,15 @@ func (ts *timers) lock() { } func (ts *timers) unlock() { + // Update atomic copy of len(ts.heap). + // We only update at unlock so that the len is always + // the most recent unlocked length, not an ephemeral length. + // This matters if we lock ts, delete the only timer from the heap, + // add it back, and unlock. We want ts.len.Load to return 1 the + // entire time, never 0. This is important for pidleput deciding + // whether ts is empty. + ts.len.Store(uint32(len(ts.heap))) + unlock(&ts.mu) } @@ -318,7 +327,6 @@ func (ts *timers) addHeap(t *timer) { if t == ts.heap[0] { ts.updateMinWhen() } - ts.len.Store(uint32(len(ts.heap))) } // stop deletes the timer t. It may be on some other P, so we can't @@ -367,7 +375,6 @@ func (ts *timers) deleteMin() { ts.siftDown(0) } ts.updateMinWhen() - ts.len.Store(uint32(last)) if last == 0 { // If there are no timers, then clearly there are no timerNextWhen timers. ts.minNextWhen.Store(0) @@ -540,7 +547,6 @@ func (ts *timers) take(src *timers) { ts.lock() ts.move(src.heap) src.heap = nil - src.len.Store(0) src.zombies.Store(0) src.minWhen.Store(0) ts.unlock() @@ -860,46 +866,6 @@ func (ts *timers) unlockAndRun(t *timer, now int64, state uint32, mp *m) { } } -// updateTimerPMask clears pp's timer mask if it has no timers on its heap. -// -// Ideally, the timer mask would be kept immediately consistent on any timer -// operations. Unfortunately, updating a shared global data structure in the -// timer hot path adds too much overhead in applications frequently switching -// between no timers and some timers. -// -// As a compromise, the timer mask is updated only on pidleget / pidleput. A -// running P (returned by pidleget) may add a timer at any time, so its mask -// must be set. An idle P (passed to pidleput) cannot add new timers while -// idle, so if it has no timers at that time, its mask may be cleared. -// -// Thus, we get the following effects on timer-stealing in findrunnable: -// -// - Idle Ps with no timers when they go idle are never checked in findrunnable -// (for work- or timer-stealing; this is the ideal case). -// - Running Ps must always be checked. -// - Idle Ps whose timers are stolen must continue to be checked until they run -// again, even after timer expiration. -// -// When the P starts running again, the mask should be set, as a timer may be -// added at any time. -// -// TODO(prattmic): Additional targeted updates may improve the above cases. -// e.g., updating the mask when stealing a timer. -func updateTimerPMask(pp *p) { - if pp.timers.len.Load() > 0 { - return - } - - // Looks like there are no timers, however another P - // may be adding one at this very moment. - // Take the lock to synchronize. - pp.timers.lock() - if len(pp.timers.heap) == 0 { - timerpMask.clear(pp.id) - } - pp.timers.unlock() -} - // verifyTimerHeap verifies that the timers is in a valid state. // This is only for debugging, and is only called if verifyTimers is true. // The caller must have locked ts. -- 2.48.1