[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

1 files changed, 67 insertions, 0 deletions

diff --git a/src/time/sleep_test.go b/src/time/sleep_test.go
index e0172bf5e0..c48e704eb7 100644
--- a/src/time/sleep_test.go
+++ b/src/time/sleep_test.go
@@ -7,6 +7,7 @@ package time_test
 import (
 	"errors"
 	"fmt"
+	"math/rand"
 	"runtime"
 	"strings"
 	"sync"
@@ -561,6 +562,72 @@ func TestTimerModifiedEarlier(t *testing.T) {
 	}
 }
 
+// Test that rapidly moving timers earlier and later doesn't cause
+// some of the sleep times to be lost.
+// Issue 47762
+func TestAdjustTimers(t *testing.T) {
+	var rnd = rand.New(rand.NewSource(Now().UnixNano()))
+
+	timers := make([]*Timer, 100)
+	states := make([]int, len(timers))
+	indices := rnd.Perm(len(timers))
+
+	for len(indices) != 0 {
+		var ii = rnd.Intn(len(indices))
+		var i = indices[ii]
+
+		var timer = timers[i]
+		var state = states[i]
+		states[i]++
+
+		switch state {
+		case 0:
+			timers[i] = NewTimer(0)
+		case 1:
+			<-timer.C // Timer is now idle.
+
+		// Reset to various long durations, which we'll cancel.
+		case 2:
+			if timer.Reset(1 * Minute) {
+				panic("shouldn't be active (1)")
+			}
+		case 4:
+			if timer.Reset(3 * Minute) {
+				panic("shouldn't be active (3)")
+			}
+		case 6:
+			if timer.Reset(2 * Minute) {
+				panic("shouldn't be active (2)")
+			}
+
+		// Stop and drain a long-duration timer.
+		case 3, 5, 7:
+			if !timer.Stop() {
+				t.Logf("timer %d state %d Stop returned false", i, state)
+				<-timer.C
+			}
+
+		// Start a short-duration timer we expect to select without blocking.
+		case 8:
+			if timer.Reset(0) {
+				t.Fatal("timer.Reset returned true")
+			}
+		case 9:
+			now := Now()
+			<-timer.C
+			dur := Since(now)
+			if dur > 750*Millisecond {
+				t.Errorf("timer %d took %v to complete", i, dur)
+			}
+
+		// Timer is done. Swap with tail and remove.
+		case 10:
+			indices[ii] = indices[len(indices)-1]
+			indices = indices[:len(indices)-1]
+		}
+	}
+}
+
 // Benchmark timer latency when the thread that creates the timer is busy with
 // other work and the timers must be serviced by other threads.
 // https://golang.org/issue/38860