runtime: don't skip checkTimers if we would clear deleted timers

The timers code used to have a problem: if code started and stopped a
lot of timers, as would happen with, for example, lots of calls to
context.WithTimeout, then it would steadily use memory holding timers
that had stopped but not been removed from the timer heap.
That problem was fixed by CL 214299, which would remove all deleted
timers whenever they got to be more than 1/4 of the total number of
timers on the heap.

The timers code had a different problem: if there were some idle P's,
the running P's would have lock contention trying to steal their timers.
That problem was fixed by CL 214185, which only acquired the timer lock
if the next timer was ready to run or there were some timers to adjust.

Unfortunately, CL 214185 partially undid 214299, in that we could now
accumulate an increasing number of deleted timers while there were no
timers ready to run. This CL restores the 214299 behavior, by checking
whether there are lots of deleted timers without acquiring the lock.

This is a performance issue to consider for the 1.14 release.

Change-Id: I13c980efdcc2a46eb84882750c39e3f7c5b2e7c3
Reviewed-on: https://go-review.googlesource.com/c/go/+/215722
Run-TryBot: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Austin Clements <austin@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>

1 files changed, 21 insertions, 11 deletions

diff --git a/src/runtime/time.go b/src/runtime/time.go
index 6c3c1a63c4..e8323ce0e6 100644
--- a/src/runtime/time.go
+++ b/src/runtime/time.go
@@ -292,6 +292,7 @@ func doaddtimer(pp *p, t *timer) bool {
 	if t == pp.timers[0] {
 		atomic.Store64(&pp.timer0When, uint64(t.when))
 	}
+	atomic.Xadd(&pp.numTimers, 1)
 	return ok
 }
 
@@ -370,6 +371,7 @@ func dodeltimer(pp *p, i int) bool {
 	if i == 0 {
 		updateTimer0When(pp)
 	}
+	atomic.Xadd(&pp.numTimers, -1)
 	return ok
 }
 
@@ -394,6 +396,7 @@ func dodeltimer0(pp *p) bool {
 		ok = siftdownTimer(pp.timers, 0)
 	}
 	updateTimer0When(pp)
+	atomic.Xadd(&pp.numTimers, -1)
 	return ok
 }
 
@@ -650,7 +653,7 @@ func adjusttimers(pp *p) {
 	}
 	if atomic.Load(&pp.adjustTimers) == 0 {
 		if verifyTimers {
-			verifyTimerHeap(pp.timers)
+			verifyTimerHeap(pp)
 		}
 		return
 	}
@@ -712,7 +715,7 @@ loop:
 	}
 
 	if verifyTimers {
-		verifyTimerHeap(pp.timers)
+		verifyTimerHeap(pp)
 	}
 }
 
@@ -954,21 +957,24 @@ nextTimer:
 		timers[i] = nil
 	}
 
-	timers = timers[:to]
-	if verifyTimers {
-		verifyTimerHeap(timers)
-	}
-	pp.timers = timers
 	atomic.Xadd(&pp.deletedTimers, -cdel)
+	atomic.Xadd(&pp.numTimers, -cdel)
 	atomic.Xadd(&pp.adjustTimers, -cearlier)
+
+	timers = timers[:to]
+	pp.timers = timers
 	updateTimer0When(pp)
+
+	if verifyTimers {
+		verifyTimerHeap(pp)
+	}
 }
 
 // verifyTimerHeap verifies that the timer heap is in a valid state.
 // This is only for debugging, and is only called if verifyTimers is true.
 // The caller must have locked the timers.
-func verifyTimerHeap(timers []*timer) {
-	for i, t := range timers {
+func verifyTimerHeap(pp *p) {
+	for i, t := range pp.timers {
 		if i == 0 {
 			// First timer has no parent.
 			continue
@@ -976,11 +982,15 @@ func verifyTimerHeap(timers []*timer) {
 
 		// The heap is 4-ary. See siftupTimer and siftdownTimer.
 		p := (i - 1) / 4
-		if t.when < timers[p].when {
-			print("bad timer heap at ", i, ": ", p, ": ", timers[p].when, ", ", i, ": ", t.when, "\n")
+		if t.when < pp.timers[p].when {
+			print("bad timer heap at ", i, ": ", p, ": ", pp.timers[p].when, ", ", i, ": ", t.when, "\n")
 			throw("bad timer heap")
 		}
 	}
+	if numTimers := int(atomic.Load(&pp.numTimers)); len(pp.timers) != numTimers {
+		println("timer heap len", len(pp.timers), "!= numTimers", numTimers)
+		throw("bad timer heap len")
+	}
 }
 
 // updateTimer0When sets the P's timer0When field.