runtime: move scheduling decisions by schedule into findrunnable

This change moves several scheduling decisions made by schedule into
findrunnable. The main motivation behind this change is the fact that
stopped Ms can't become dedicated or fractional GC workers. The main
reason for this is that when a stopped M wakes up, it stays in
findrunnable until it finds work, which means it will never consider GC
work. On that note, it'll also never consider becoming the trace reader,
either.

Another way of looking at it is that this change tries to make
findrunnable aware of more sources of work than it was before. With this
change, any M in findrunnable should be capable of becoming a GC worker,
resolving #44313. While we're here, let's also make more sources of
work, such as the trace reader, visible to handoffp, which should really
be checking all sources of work. With that, we also now correctly handle
the case where StopTrace is called from the last live M that is also
locked (#39004). stoplockedm calls handoffp to start a new M and handle
the work it cannot, and once we include the trace reader in that, we
ensure that the trace reader gets scheduled.

This change attempts to preserve the exact same ordering of work
checking to reduce its impact.

One consequence of this change is that upon entering schedule, some
sources of work won't be checked twice (i.e. the local and global
runqs, and timers) as they do now, which in some sense gives them a
lower priority than they had before.

Fixes #39004.
Fixes #44313.

Change-Id: I5d8b7f63839db8d9a3e47cdda604baac1fe615ce
Reviewed-on: https://go-review.googlesource.com/c/go/+/393880
Reviewed-by: Michael Pratt <mpratt@google.com>
Run-TryBot: Michael Knyszek <mknyszek@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>

2 files changed, 64 insertions, 62 deletions

diff --git a/src/runtime/proc.go b/src/runtime/proc.go
index 4aeb66c92d..485bd65a9e 100644
--- a/src/runtime/proc.go
+++ b/src/runtime/proc.go
@@ -2351,6 +2351,11 @@ func handoffp(_p_ *p) {
 		startm(_p_, false)
 		return
 	}
+	// if there's trace work to do, start it straight away
+	if (trace.enabled || trace.shutdown) && traceReaderAvailable() {
+		startm(_p_, false)
+		return
+	}
 	// if it has GC work, start it straight away
 	if gcBlackenEnabled != 0 && gcMarkWorkAvailable(_p_) {
 		startm(_p_, false)
@@ -2535,7 +2540,9 @@ func execute(gp *g, inheritTime bool) {
 
 // Finds a runnable goroutine to execute.
 // Tries to steal from other P's, get g from local or global queue, poll network.
-func findrunnable() (gp *g, inheritTime bool) {
+// tryWakeP indicates that the returned goroutine is not normal (GC worker, trace
+// reader) so the caller should try to wake a P.
+func findRunnable() (gp *g, inheritTime, tryWakeP bool) {
 	_g_ := getg()
 
 	// The conditions here and in handoffp must agree: if
@@ -2552,8 +2559,43 @@ top:
 		runSafePointFn()
 	}
 
+	// now and pollUntil are saved for work stealing later,
+	// which may steal timers. It's important that between now
+	// and then, nothing blocks, so these numbers remain mostly
+	// relevant.
 	now, pollUntil, _ := checkTimers(_p_, 0)
 
+	// Try to schedule the trace reader.
+	if trace.enabled || trace.shutdown {
+		gp = traceReader()
+		if gp != nil {
+			casgstatus(gp, _Gwaiting, _Grunnable)
+			traceGoUnpark(gp, 0)
+			return gp, false, true
+		}
+	}
+
+	// Try to schedule a GC worker.
+	if gcBlackenEnabled != 0 {
+		gp = gcController.findRunnableGCWorker(_p_)
+		if gp != nil {
+			return gp, false, true
+		}
+	}
+
+	// Check the global runnable queue once in a while to ensure fairness.
+	// Otherwise two goroutines can completely occupy the local runqueue
+	// by constantly respawning each other.
+	if _p_.schedtick%61 == 0 && sched.runqsize > 0 {
+		lock(&sched.lock)
+		gp = globrunqget(_p_, 1)
+		unlock(&sched.lock)
+		if gp != nil {
+			return gp, false, false
+		}
+	}
+
+	// Wake up the finalizer G.
 	if fingwait && fingwake {
 		if gp := wakefing(); gp != nil {
 			ready(gp, 0, true)
@@ -2565,7 +2607,7 @@ top:
 
 	// local runq
 	if gp, inheritTime := runqget(_p_); gp != nil {
-		return gp, inheritTime
+		return gp, inheritTime, false
 	}
 
 	// global runq
@@ -2574,7 +2616,7 @@ top:
 		gp := globrunqget(_p_, 0)
 		unlock(&sched.lock)
 		if gp != nil {
-			return gp, false
+			return gp, false, false
 		}
 	}
 
@@ -2593,7 +2635,7 @@ top:
 			if trace.enabled {
 				traceGoUnpark(gp, 0)
 			}
-			return gp, false
+			return gp, false, false
 		}
 	}
 
@@ -2613,7 +2655,7 @@ top:
 		now = tnow
 		if gp != nil {
 			// Successfully stole.
-			return gp, inheritTime
+			return gp, inheritTime, false
 		}
 		if newWork {
 			// There may be new timer or GC work; restart to
@@ -2639,7 +2681,7 @@ top:
 			if trace.enabled {
 				traceGoUnpark(gp, 0)
 			}
-			return gp, false
+			return gp, false, false
 		}
 		gcController.removeIdleMarkWorker()
 	}
@@ -2654,7 +2696,7 @@ top:
 		if trace.enabled {
 			traceGoUnpark(gp, 0)
 		}
-		return gp, false
+		return gp, false, false
 	}
 	if otherReady {
 		goto top
@@ -2679,7 +2721,7 @@ top:
 	if sched.runqsize != 0 {
 		gp := globrunqget(_p_, 0)
 		unlock(&sched.lock)
-		return gp, false
+		return gp, false, false
 	}
 	if releasep() != _p_ {
 		throw("findrunnable: wrong p")
@@ -2742,7 +2784,7 @@ top:
 			if trace.enabled {
 				traceGoUnpark(gp, 0)
 			}
-			return gp, false
+			return gp, false, false
 		}
 
 		// Finally, check for timer creation or expiry concurrently with
@@ -2800,7 +2842,7 @@ top:
 				if trace.enabled {
 					traceGoUnpark(gp, 0)
 				}
-				return gp, false
+				return gp, false, false
 			}
 			if wasSpinning {
 				_g_.m.spinning = true
@@ -3147,62 +3189,14 @@ top:
 	pp := _g_.m.p.ptr()
 	pp.preempt = false
 
-	if sched.gcwaiting != 0 {
-		gcstopm()
-		goto top
-	}
-	if pp.runSafePointFn != 0 {
-		runSafePointFn()
-	}
-
-	// Sanity check: if we are spinning, the run queue should be empty.
+	// Safety check: if we are spinning, the run queue should be empty.
 	// Check this before calling checkTimers, as that might call
 	// goready to put a ready goroutine on the local run queue.
 	if _g_.m.spinning && (pp.runnext != 0 || pp.runqhead != pp.runqtail) {
 		throw("schedule: spinning with local work")
 	}
 
-	checkTimers(pp, 0)
-
-	var gp *g
-	var inheritTime bool
-
-	// Normal goroutines will check for need to wakeP in ready,
-	// but GCworkers and tracereaders will not, so the check must
-	// be done here instead.
-	tryWakeP := false
-	if trace.enabled || trace.shutdown {
-		gp = traceReader()
-		if gp != nil {
-			casgstatus(gp, _Gwaiting, _Grunnable)
-			traceGoUnpark(gp, 0)
-			tryWakeP = true
-		}
-	}
-	if gp == nil && gcBlackenEnabled != 0 {
-		gp = gcController.findRunnableGCWorker(_g_.m.p.ptr())
-		if gp != nil {
-			tryWakeP = true
-		}
-	}
-	if gp == nil {
-		// Check the global runnable queue once in a while to ensure fairness.
-		// Otherwise two goroutines can completely occupy the local runqueue
-		// by constantly respawning each other.
-		if _g_.m.p.ptr().schedtick%61 == 0 && sched.runqsize > 0 {
-			lock(&sched.lock)
-			gp = globrunqget(_g_.m.p.ptr(), 1)
-			unlock(&sched.lock)
-		}
-	}
-	if gp == nil {
-		gp, inheritTime = runqget(_g_.m.p.ptr())
-		// We can see gp != nil here even if the M is spinning,
-		// if checkTimers added a local goroutine via goready.
-	}
-	if gp == nil {
-		gp, inheritTime = findrunnable() // blocks until work is available
-	}
+	gp, inheritTime, tryWakeP := findRunnable() // blocks until work is available
 
 	// This thread is going to run a goroutine and is not spinning anymore,
 	// so if it was marked as spinning we need to reset it now and potentially
diff --git a/src/runtime/trace.go b/src/runtime/trace.go
index 8f60de2b05..b50e1b2ce0 100644
--- a/src/runtime/trace.go
+++ b/src/runtime/trace.go
@@ -461,12 +461,13 @@ func ReadTrace() []byte {
 }
 
 // traceReader returns the trace reader that should be woken up, if any.
+// Callers should first check that trace.enabled or trace.shutdown is set.
 func traceReader() *g {
-	if trace.reader == 0 || (trace.fullHead == 0 && !trace.shutdown) {
+	if !traceReaderAvailable() {
 		return nil
 	}
 	lock(&trace.lock)
-	if trace.reader == 0 || (trace.fullHead == 0 && !trace.shutdown) {
+	if !traceReaderAvailable() {
 		unlock(&trace.lock)
 		return nil
 	}
@@ -476,6 +477,13 @@ func traceReader() *g {
 	return gp
 }
 
+// traceReaderAvailable returns true if the trace reader is not currently
+// scheduled and should be. Callers should first check that trace.enabled
+// or trace.shutdown is set.
+func traceReaderAvailable() bool {
+	return trace.reader != 0 && (trace.fullHead != 0 || trace.shutdown)
+}
+
 // traceProcFree frees trace buffer associated with pp.
 func traceProcFree(pp *p) {
 	buf := pp.tracebuf