runtime: incorporate Gscan acquire/release into lock ranking order

I added routines that can acquire/release a particular rank without
acquiring/releasing an associated lock. I added lockRankGscan as a rank
for acquiring/releasing the Gscan bit.

castogscanstatus() and casGtoPreemptScan() are acquires of the Gscan
bit. casfrom_Gscanstatus() is a release of the Gscan bit. casgstatus()
is like an acquire and release of the Gscan bit, since it will wait if
Gscan bit is currently set.

We have a cycle between hchan and Gscan. The acquisition of Gscan and
then hchan only happens in syncadjustsudogs() when the G is suspended,
so the main normal ordering (get hchan, then get Gscan) can't be
happening. So, I added a new rank lockRankHchanLeaf that is used when
acquiring hchan locks in syncadjustsudogs. This ranking is set so no
other locks can be acquired except other hchan locks.

Fixes #38922

Change-Id: I58ce526a74ba856cb42078f7b9901f2832e1d45c
Reviewed-on: https://go-review.googlesource.com/c/go/+/228417
Run-TryBot: Dan Scales <danscales@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Austin Clements <austin@google.com>

8 files changed, 129 insertions, 41 deletions

diff --git a/src/runtime/lock_futex.go b/src/runtime/lock_futex.go
index b0395d6a69..29b7be0d8f 100644
--- a/src/runtime/lock_futex.go
+++ b/src/runtime/lock_futex.go
@@ -108,7 +108,7 @@ func lock2(l *mutex) {
 }
 
 func unlock(l *mutex) {
-	lockRankRelease(l)
+	unlockWithRank(l)
 }
 
 func unlock2(l *mutex) {
diff --git a/src/runtime/lock_js.go b/src/runtime/lock_js.go
index 7a720f4790..429ce63923 100644
--- a/src/runtime/lock_js.go
+++ b/src/runtime/lock_js.go
@@ -44,7 +44,7 @@ func lock2(l *mutex) {
 }
 
 func unlock(l *mutex) {
-	lockRankRelease(l)
+	unlockWithRank(l)
 }
 
 func unlock2(l *mutex) {
diff --git a/src/runtime/lock_sema.go b/src/runtime/lock_sema.go
index d79520da07..bf2584ac92 100644
--- a/src/runtime/lock_sema.go
+++ b/src/runtime/lock_sema.go
@@ -94,7 +94,7 @@ Loop:
 }
 
 func unlock(l *mutex) {
-	lockRankRelease(l)
+	unlockWithRank(l)
 }
 
 //go:nowritebarrier
diff --git a/src/runtime/lockrank.go b/src/runtime/lockrank.go
index 5174adc8bf..899c4e2e85 100644
--- a/src/runtime/lockrank.go
+++ b/src/runtime/lockrank.go
@@ -69,6 +69,7 @@ const (
 	lockRankMcentral // For !go115NewMCentralImpl
 	lockRankSpine    // For !go115NewMCentralImpl
 	lockRankSpanSetSpine
+	lockRankGscan
 	lockRankStackpool
 	lockRankStackLarge
 	lockRankDefer
@@ -84,6 +85,14 @@ const (
 
 	// Other leaf locks
 	lockRankGFree
+	// Generally, hchan must be acquired before gscan. But in one specific
+	// case (in syncadjustsudogs from markroot after the g has been suspended
+	// by suspendG), we allow gscan to be acquired, and then an hchan lock. To
+	// allow this case, we get this lockRankHchanLeaf rank in
+	// syncadjustsudogs(), rather than lockRankHchan. By using this special
+	// rank, we don't allow any further locks to be acquired other than more
+	// hchan locks.
+	lockRankHchanLeaf
 
 	// Leaf locks with no dependencies, so these constants are not actually used anywhere.
 	// There are other architecture-dependent leaf locks as well.
@@ -141,6 +150,7 @@ var lockNames = []string{
 	lockRankMcentral:     "mcentral",
 	lockRankSpine:        "spine",
 	lockRankSpanSetSpine: "spanSetSpine",
+	lockRankGscan:        "gscan",
 	lockRankStackpool:    "stackpool",
 	lockRankStackLarge:   "stackLarge",
 	lockRankDefer:        "defer",
@@ -152,7 +162,8 @@ var lockNames = []string{
 
 	lockRankGlobalAlloc: "globalAlloc.mutex",
 
-	lockRankGFree: "gFree",
+	lockRankGFree:     "gFree",
+	lockRankHchanLeaf: "hchanLeaf",
 
 	lockRankNewmHandoff:   "newmHandoff.lock",
 	lockRankDebugPtrmask:  "debugPtrmask.lock",
@@ -217,16 +228,18 @@ var lockPartialOrder [][]lockRank = [][]lockRank{
 	lockRankMcentral:     {lockRankScavenge, lockRankForcegc, lockRankAssistQueue, lockRankCpuprof, lockRankSweep, lockRankSched, lockRankAllg, lockRankAllp, lockRankTimers, lockRankItab, lockRankReflectOffs, lockRankNotifyList, lockRankTraceBuf, lockRankTraceStrings, lockRankHchan},
 	lockRankSpine:        {lockRankScavenge, lockRankAssistQueue, lockRankCpuprof, lockRankSched, lockRankAllg, lockRankTimers, lockRankItab, lockRankReflectOffs, lockRankNotifyList, lockRankTraceBuf, lockRankTraceStrings, lockRankHchan},
 	lockRankSpanSetSpine: {lockRankScavenge, lockRankForcegc, lockRankAssistQueue, lockRankCpuprof, lockRankSweep, lockRankSched, lockRankAllg, lockRankAllp, lockRankTimers, lockRankItab, lockRankReflectOffs, lockRankNotifyList, lockRankTraceBuf, lockRankTraceStrings, lockRankHchan},
-	lockRankStackpool:    {lockRankScavenge, lockRankSweepWaiters, lockRankAssistQueue, lockRankCpuprof, lockRankSweep, lockRankSched, lockRankPollDesc, lockRankTimers, lockRankItab, lockRankReflectOffs, lockRankHchan, lockRankFin, lockRankNotifyList, lockRankTraceBuf, lockRankTraceStrings, lockRankProf, lockRankGcBitsArenas, lockRankRoot, lockRankTrace, lockRankTraceStackTab, lockRankNetpollInit, lockRankRwmutexR, lockRankMcentral, lockRankSpine, lockRankSpanSetSpine},
-	lockRankStackLarge:   {lockRankAssistQueue, lockRankSched, lockRankItab, lockRankHchan, lockRankProf, lockRankGcBitsArenas, lockRankRoot, lockRankMcentral, lockRankSpanSetSpine},
+	lockRankGscan:        {lockRankScavenge, lockRankForcegc, lockRankSweepWaiters, lockRankAssistQueue, lockRankCpuprof, lockRankSweep, lockRankSched, lockRankTimers, lockRankItab, lockRankReflectOffs, lockRankHchan, lockRankFin, lockRankTraceBuf, lockRankTraceStrings, lockRankRoot, lockRankNotifyList, lockRankProf, lockRankGcBitsArenas, lockRankTrace, lockRankTraceStackTab, lockRankNetpollInit, lockRankMcentral, lockRankSpine, lockRankSpanSetSpine},
+	lockRankStackpool:    {lockRankScavenge, lockRankSweepWaiters, lockRankAssistQueue, lockRankCpuprof, lockRankSweep, lockRankSched, lockRankPollDesc, lockRankTimers, lockRankItab, lockRankReflectOffs, lockRankHchan, lockRankFin, lockRankNotifyList, lockRankTraceBuf, lockRankTraceStrings, lockRankProf, lockRankGcBitsArenas, lockRankRoot, lockRankTrace, lockRankTraceStackTab, lockRankNetpollInit, lockRankRwmutexR, lockRankMcentral, lockRankSpine, lockRankSpanSetSpine, lockRankGscan},
+	lockRankStackLarge:   {lockRankAssistQueue, lockRankSched, lockRankItab, lockRankHchan, lockRankProf, lockRankGcBitsArenas, lockRankRoot, lockRankMcentral, lockRankSpanSetSpine, lockRankGscan},
 	lockRankDefer:        {},
 	lockRankSudog:        {lockRankNotifyList, lockRankHchan},
-	lockRankWbufSpans:    {lockRankScavenge, lockRankSweepWaiters, lockRankAssistQueue, lockRankSweep, lockRankSched, lockRankAllg, lockRankPollDesc, lockRankTimers, lockRankItab, lockRankReflectOffs, lockRankHchan, lockRankNotifyList, lockRankTraceStrings, lockRankMspanSpecial, lockRankProf, lockRankRoot, lockRankDefer, lockRankSudog},
-	lockRankMheap:        {lockRankScavenge, lockRankSweepWaiters, lockRankAssistQueue, lockRankCpuprof, lockRankSweep, lockRankSched, lockRankAllg, lockRankAllp, lockRankPollDesc, lockRankTimers, lockRankItab, lockRankReflectOffs, lockRankNotifyList, lockRankTraceBuf, lockRankTraceStrings, lockRankHchan, lockRankMspanSpecial, lockRankProf, lockRankGcBitsArenas, lockRankRoot, lockRankMcentral, lockRankStackpool, lockRankStackLarge, lockRankDefer, lockRankSudog, lockRankWbufSpans, lockRankSpanSetSpine},
+	lockRankWbufSpans:    {lockRankScavenge, lockRankSweepWaiters, lockRankAssistQueue, lockRankSweep, lockRankSched, lockRankAllg, lockRankPollDesc, lockRankTimers, lockRankItab, lockRankReflectOffs, lockRankHchan, lockRankNotifyList, lockRankTraceStrings, lockRankMspanSpecial, lockRankProf, lockRankRoot, lockRankGscan, lockRankDefer, lockRankSudog},
+	lockRankMheap:        {lockRankScavenge, lockRankSweepWaiters, lockRankAssistQueue, lockRankCpuprof, lockRankSweep, lockRankSched, lockRankAllg, lockRankAllp, lockRankPollDesc, lockRankTimers, lockRankItab, lockRankReflectOffs, lockRankNotifyList, lockRankTraceBuf, lockRankTraceStrings, lockRankHchan, lockRankMspanSpecial, lockRankProf, lockRankGcBitsArenas, lockRankRoot, lockRankMcentral, lockRankGscan, lockRankStackpool, lockRankStackLarge, lockRankDefer, lockRankSudog, lockRankWbufSpans, lockRankSpanSetSpine},
 	lockRankMheapSpecial: {lockRankScavenge, lockRankAssistQueue, lockRankCpuprof, lockRankSweep, lockRankSched, lockRankAllg, lockRankAllp, lockRankTimers, lockRankItab, lockRankReflectOffs, lockRankNotifyList, lockRankTraceBuf, lockRankTraceStrings, lockRankHchan},
 	lockRankGlobalAlloc:  {lockRankProf, lockRankSpine, lockRankSpanSetSpine, lockRankMheap, lockRankMheapSpecial},
 
-	lockRankGFree: {lockRankSched},
+	lockRankGFree:     {lockRankSched},
+	lockRankHchanLeaf: {lockRankGscan, lockRankHchanLeaf},
 
 	lockRankNewmHandoff:   {},
 	lockRankDebugPtrmask:  {},
diff --git a/src/runtime/lockrank_off.go b/src/runtime/lockrank_off.go
index fcfcff57a3..891589c0f2 100644
--- a/src/runtime/lockrank_off.go
+++ b/src/runtime/lockrank_off.go
@@ -14,12 +14,18 @@ func getLockRank(l *mutex) lockRank {
 	return 0
 }
 
-func lockRankRelease(l *mutex) {
+func lockWithRank(l *mutex, rank lockRank) {
+	lock2(l)
+}
+
+func acquireLockRank(rank lockRank) {
+}
+
+func unlockWithRank(l *mutex) {
 	unlock2(l)
 }
 
-func lockWithRank(l *mutex, rank lockRank) {
-	lock2(l)
+func releaseLockRank(rank lockRank) {
 }
 
 func lockWithRankMayAcquire(l *mutex, rank lockRank) {
diff --git a/src/runtime/lockrank_on.go b/src/runtime/lockrank_on.go
index fc72a06f6f..cf4151ff46 100644
--- a/src/runtime/lockrank_on.go
+++ b/src/runtime/lockrank_on.go
@@ -46,10 +46,17 @@ func getLockRank(l *mutex) lockRank {
 // when acquiring a non-static lock.
 //go:nosplit
 func lockWithRank(l *mutex, rank lockRank) {
-	if l == &debuglock {
-		// debuglock is only used for println/printlock(). Don't do lock rank
-		// recording for it, since print/println are used when printing
-		// out a lock ordering problem below.
+	if l == &debuglock || l == &paniclk {
+		// debuglock is only used for println/printlock(). Don't do lock
+		// rank recording for it, since print/println are used when
+		// printing out a lock ordering problem below.
+		//
+		// paniclk has an ordering problem, since it can be acquired
+		// during a panic with any other locks held (especially if the
+		// panic is because of a directed segv), and yet also allg is
+		// acquired after paniclk in tracebackothers()). This is a genuine
+		// problem, so for now we don't do lock rank recording for paniclk
+		// either.
 		lock2(l)
 		return
 	}
@@ -75,26 +82,49 @@ func lockWithRank(l *mutex, rank lockRank) {
 	})
 }
 
+// acquireLockRank acquires a rank which is not associated with a mutex lock
+//go:nosplit
+func acquireLockRank(rank lockRank) {
+	gp := getg()
+	// Log the new class.
+	systemstack(func() {
+		i := gp.m.locksHeldLen
+		if i >= len(gp.m.locksHeld) {
+			throw("too many locks held concurrently for rank checking")
+		}
+		gp.m.locksHeld[i].rank = rank
+		gp.m.locksHeld[i].lockAddr = 0
+		gp.m.locksHeldLen++
+
+		// i is the index of the lock being acquired
+		if i > 0 {
+			checkRanks(gp, gp.m.locksHeld[i-1].rank, rank)
+		}
+	})
+}
+
+// checkRanks checks if goroutine g, which has mostly recently acquired a lock
+// with rank 'prevRank', can now acquire a lock with rank 'rank'.
 func checkRanks(gp *g, prevRank, rank lockRank) {
 	rankOK := false
-	// If rank < prevRank, then we definitely have a rank error
-	if prevRank <= rank {
-		if rank == lockRankLeafRank {
-			// If new lock is a leaf lock, then the preceding lock can
-			// be anything except another leaf lock.
-			rankOK = prevRank < lockRankLeafRank
-		} else {
-			// We've already verified the total lock ranking, but we
-			// also enforce the partial ordering specified by
-			// lockPartialOrder as well. Two locks with the same rank
-			// can only be acquired at the same time if explicitly
-			// listed in the lockPartialOrder table.
-			list := lockPartialOrder[rank]
-			for _, entry := range list {
-				if entry == prevRank {
-					rankOK = true
-					break
-				}
+	if rank < prevRank {
+		// If rank < prevRank, then we definitely have a rank error
+		rankOK = false
+	} else if rank == lockRankLeafRank {
+		// If new lock is a leaf lock, then the preceding lock can
+		// be anything except another leaf lock.
+		rankOK = prevRank < lockRankLeafRank
+	} else {
+		// We've now verified the total lock ranking, but we
+		// also enforce the partial ordering specified by
+		// lockPartialOrder as well. Two locks with the same rank
+		// can only be acquired at the same time if explicitly
+		// listed in the lockPartialOrder table.
+		list := lockPartialOrder[rank]
+		for _, entry := range list {
+			if entry == prevRank {
+				rankOK = true
+				break
 			}
 		}
 	}
@@ -109,11 +139,9 @@ func checkRanks(gp *g, prevRank, rank lockRank) {
 }
 
 //go:nosplit
-func lockRankRelease(l *mutex) {
-	if l == &debuglock {
-		// debuglock is only used for print/println. Don't do lock rank
-		// recording for it, since print/println are used when printing
-		// out a lock ordering problem below.
+func unlockWithRank(l *mutex) {
+	if l == &debuglock || l == &paniclk {
+		// See comment at beginning of lockWithRank.
 		unlock2(l)
 		return
 	}
@@ -125,6 +153,7 @@ func lockRankRelease(l *mutex) {
 				found = true
 				copy(gp.m.locksHeld[i:gp.m.locksHeldLen-1], gp.m.locksHeld[i+1:gp.m.locksHeldLen])
 				gp.m.locksHeldLen--
+				break
 			}
 		}
 		if !found {
@@ -135,6 +164,27 @@ func lockRankRelease(l *mutex) {
 	})
 }
 
+// releaseLockRank releases a rank which is not associated with a mutex lock
+//go:nosplit
+func releaseLockRank(rank lockRank) {
+	gp := getg()
+	systemstack(func() {
+		found := false
+		for i := gp.m.locksHeldLen - 1; i >= 0; i-- {
+			if gp.m.locksHeld[i].rank == rank && gp.m.locksHeld[i].lockAddr == 0 {
+				found = true
+				copy(gp.m.locksHeld[i:gp.m.locksHeldLen-1], gp.m.locksHeld[i+1:gp.m.locksHeldLen])
+				gp.m.locksHeldLen--
+				break
+			}
+		}
+		if !found {
+			println(gp.m.procid, ":", rank.String(), rank)
+			throw("lockRank release without matching lockRank acquire")
+		}
+	})
+}
+
 //go:nosplit
 func lockWithRankMayAcquire(l *mutex, rank lockRank) {
 	gp := getg()
diff --git a/src/runtime/proc.go b/src/runtime/proc.go
index fe7da0bc87..ca99870224 100644
--- a/src/runtime/proc.go
+++ b/src/runtime/proc.go
@@ -760,6 +760,7 @@ func casfrom_Gscanstatus(gp *g, oldval, newval uint32) {
 		dumpgstatus(gp)
 		throw("casfrom_Gscanstatus: gp->status is not in scan state")
 	}
+	releaseLockRank(lockRankGscan)
 }
 
 // This will return false if the gp is not in the expected status and the cas fails.
@@ -771,7 +772,12 @@ func castogscanstatus(gp *g, oldval, newval uint32) bool {
 		_Gwaiting,
 		_Gsyscall:
 		if newval == oldval|_Gscan {
-			return atomic.Cas(&gp.atomicstatus, oldval, newval)
+			r := atomic.Cas(&gp.atomicstatus, oldval, newval)
+			if r {
+				acquireLockRank(lockRankGscan)
+			}
+			return r
+
 		}
 	}
 	print("runtime: castogscanstatus oldval=", hex(oldval), " newval=", hex(newval), "\n")
@@ -792,6 +798,9 @@ func casgstatus(gp *g, oldval, newval uint32) {
 		})
 	}
 
+	acquireLockRank(lockRankGscan)
+	releaseLockRank(lockRankGscan)
+
 	// See https://golang.org/cl/21503 for justification of the yield delay.
 	const yieldDelay = 5 * 1000
 	var nextYield int64
@@ -842,6 +851,7 @@ func casGToPreemptScan(gp *g, old, new uint32) {
 	if old != _Grunning || new != _Gscan|_Gpreempted {
 		throw("bad g transition")
 	}
+	acquireLockRank(lockRankGscan)
 	for !atomic.Cas(&gp.atomicstatus, _Grunning, _Gscan|_Gpreempted) {
 	}
 }
diff --git a/src/runtime/stack.go b/src/runtime/stack.go
index 6e1f07bf73..52e54171cb 100644
--- a/src/runtime/stack.go
+++ b/src/runtime/stack.go
@@ -794,7 +794,16 @@ func syncadjustsudogs(gp *g, used uintptr, adjinfo *adjustinfo) uintptr {
 	var lastc *hchan
 	for sg := gp.waiting; sg != nil; sg = sg.waitlink {
 		if sg.c != lastc {
-			lock(&sg.c.lock)
+			// There is a ranking cycle here between gscan bit and
+			// hchan locks. Normally, we only allow acquiring hchan
+			// locks and then getting a gscan bit. In this case, we
+			// already have the gscan bit. We allow acquiring hchan
+			// locks here as a special case, since a deadlock can't
+			// happen because the G involved must already be
+			// suspended. So, we get a special hchan lock rank here
+			// that is lower than gscan, but doesn't allow acquiring
+			// any other locks other than hchan.
+			lockWithRank(&sg.c.lock, lockRankHchanLeaf)
 		}
 		lastc = sg.c
 	}