diff options
author | Ian Lance Taylor <iant@golang.org> | 2021-08-20 16:55:04 -0700 |
---|---|---|
committer | Ian Lance Taylor <iant@golang.org> | 2021-09-15 23:27:54 +0000 |
commit | 552410fec2c662b8cc003c27b239d8b5bb11fcd7 (patch) | |
tree | d3e7fa678d35eebe4f477aca96a1ce073ce36319 /src/runtime | |
parent | 170a72e58bd128b421f4b3974fe2a37fd035efdf (diff) | |
download | go-552410fec2c662b8cc003c27b239d8b5bb11fcd7.tar.gz go-552410fec2c662b8cc003c27b239d8b5bb11fcd7.zip |
[release-branch.go1.16] runtime: in adjustTimers back up as far as necessary
When the adjustTimers function removed a timer it assumed it was
sufficient to continue the heap traversal at that position.
However, in some cases a timer will be moved to an earlier
position in the heap. If that timer is timerModifiedEarlier,
that can leave timerModifiedEarliest not correctly representing
the earlier such timer.
Fix the problem by restarting the heap traversal at the earliest
changed position.
For #47762
Fixes #47858
Change-Id: I152bbe62793ee40a680baf49967bcb89b1f94764
Reviewed-on: https://go-review.googlesource.com/c/go/+/343882
Trust: Ian Lance Taylor <iant@golang.org>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Michael Knyszek <mknyszek@google.com>
(cherry picked from commit 2da3375e9b4980e368a8641f54cc53c4af4d1a12)
Reviewed-on: https://go-review.googlesource.com/c/go/+/350000
Diffstat (limited to 'src/runtime')
-rw-r--r-- | src/runtime/time.go | 30 |
1 files changed, 20 insertions, 10 deletions
diff --git a/src/runtime/time.go b/src/runtime/time.go index 666b242316..517a493a70 100644 --- a/src/runtime/time.go +++ b/src/runtime/time.go @@ -366,9 +366,9 @@ func deltimer(t *timer) bool { // dodeltimer removes timer i from the current P's heap. // We are locked on the P when this is called. -// It reports whether it saw no problems due to races. +// It returns the smallest changed index in pp.timers. // The caller must have locked the timers for pp. -func dodeltimer(pp *p, i int) { +func dodeltimer(pp *p, i int) int { if t := pp.timers[i]; t.pp.ptr() != pp { throw("dodeltimer: wrong P") } else { @@ -380,16 +380,18 @@ func dodeltimer(pp *p, i int) { } pp.timers[last] = nil pp.timers = pp.timers[:last] + smallestChanged := i if i != last { // Moving to i may have moved the last timer to a new parent, // so sift up to preserve the heap guarantee. - siftupTimer(pp.timers, i) + smallestChanged = siftupTimer(pp.timers, i) siftdownTimer(pp.timers, i) } if i == 0 { updateTimer0When(pp) } atomic.Xadd(&pp.numTimers, -1) + return smallestChanged } // dodeltimer0 removes timer 0 from the current P's heap. @@ -674,13 +676,14 @@ func adjusttimers(pp *p, now int64) { switch s := atomic.Load(&t.status); s { case timerDeleted: if atomic.Cas(&t.status, s, timerRemoving) { - dodeltimer(pp, i) + changed := dodeltimer(pp, i) if !atomic.Cas(&t.status, timerRemoving, timerRemoved) { badTimer() } atomic.Xadd(&pp.deletedTimers, -1) - // Look at this heap position again. - i-- + // Go back to the earliest changed heap entry. + // "- 1" because the loop will add 1. + i = changed - 1 } case timerModifiedEarlier, timerModifiedLater: if atomic.Cas(&t.status, s, timerMoving) { @@ -690,10 +693,11 @@ func adjusttimers(pp *p, now int64) { // We don't add it back yet because the // heap manipulation could cause our // loop to skip some other timer. - dodeltimer(pp, i) + changed := dodeltimer(pp, i) moved = append(moved, t) - // Look at this heap position again. - i-- + // Go back to the earliest changed heap entry. + // "- 1" because the loop will add 1. + i = changed - 1 } case timerNoStatus, timerRunning, timerRemoving, timerRemoved, timerMoving: badTimer() @@ -1043,7 +1047,10 @@ func timeSleepUntil() (int64, *p) { // "panic holding locks" message. Instead, we panic while not // holding a lock. -func siftupTimer(t []*timer, i int) { +// siftupTimer puts the timer at position i in the right place +// in the heap by moving it up toward the top of the heap. +// It returns the smallest changed index. +func siftupTimer(t []*timer, i int) int { if i >= len(t) { badTimer() } @@ -1063,8 +1070,11 @@ func siftupTimer(t []*timer, i int) { if tmp != t[i] { t[i] = tmp } + return i } +// siftdownTimer puts the timer at position i in the right place +// in the heap by moving it down toward the bottom of the heap. func siftdownTimer(t []*timer, i int) { n := len(t) if i >= n { |