From 2b8a9a484fbc91b7b0d21890e33b28a0b48e3a10 Mon Sep 17 00:00:00 2001 From: Austin Clements Date: Tue, 19 Jul 2022 17:31:52 -0400 Subject: runtime: generate the lock ranking from a DAG description Currently, the runtime lock rank graph is maintained manually in a large set of arrays that give the partial order and a manual topological sort of this partial order. Any changes to the rank graph are difficult to reason about and hard to review, as well as likely to cause merge conflicts. Furthermore, because the partial order is manually maintained, it's not actually transitively closed (though it's close), meaning there are many cases where rank a can be acquired before b and b before c, but a cannot be acquired before c. While this isn't technically wrong, it's very strange in the context of lock ordering. Replace all of this with a much more compact, readable, and maintainable description of the rank graph written in the internal/dag graph language. We statically generate the runtime structures from this description, which has the advantage that the parser doesn't have to run during runtime initialization and the structures can live in static data where they can be accessed from any point during runtime init. The current description was automatically generated from the existing partial order, combined with a transitive reduction. This ensures it's correct, but it could use some manual messaging to call out the logical layers and add some structure. We do lose the ad hoc string names of the lock ranks in this translation, which could mostly be derived from the rank constant names, but not always. I may bring those back but in a more uniform way. We no longer need the tests in lockrank_test.go because they were checking that we manually maintained the structures correctly. Fixes #53789. Change-Id: I54451d561b22e61150aff7e9b8602ba9737e1b9b Reviewed-on: https://go-review.googlesource.com/c/go/+/418715 Run-TryBot: Austin Clements Reviewed-by: Michael Pratt TryBot-Result: Gopher Robot --- src/runtime/mklockrank.go | 240 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 240 insertions(+) create mode 100644 src/runtime/mklockrank.go (limited to 'src/runtime/mklockrank.go') diff --git a/src/runtime/mklockrank.go b/src/runtime/mklockrank.go new file mode 100644 index 0000000000..9cb51bedca --- /dev/null +++ b/src/runtime/mklockrank.go @@ -0,0 +1,240 @@ +// Copyright 2022 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +//go:build ignore + +// mklockrank records the static rank graph of the locks in the +// runtime and generates the rank checking structures in lockrank.go. +package main + +import ( + "bytes" + "flag" + "fmt" + "go/format" + "internal/dag" + "io" + "log" + "os" + "strings" +) + +// ranks describes the lock rank graph. See "go doc internal/dag" for +// the syntax. +// +// "a < b" means a must be acquired before b if both are held +// (or, if b is held, a cannot be acquired). +// +// "NONE < a" means no locks may be held when a is acquired. +// +// If a lock is not given a rank, then it is assumed to be a leaf +// lock, which means no other lock can be acquired while it is held. +// Therefore, leaf locks do not need to be given an explicit rank. +// +// TODO: It's often hard to correlate rank names to locks. Change +// these to be more consistent with the locks they label. +const ranks = ` +NONE < sysmon, sweepWaiters, assistQueue, cpuprof, sweep, pollDesc, deadlock, itab, notifyList, root, rwmutexW, defer; +sysmon < scavenge, forcegc; +assistQueue, cpuprof, forcegc, pollDesc, scavenge, sweep, sweepWaiters < sched; +sched < allg, allp; +allp < timers; +itab < reflectOffs; +scavenge, sweep < hchan; +scavenge < traceBuf; +allg, hchan, reflectOffs, timers, traceBuf < fin; +traceBuf < traceStrings; +allg, hchan, notifyList, reflectOffs, timers, traceStrings < mspanSpecial, profInsert, profBlock, profMemActive, gcBitsArenas, spanSetSpine, mheapSpecial; +profMemActive < profMemFuture; +hchan, root, sched, traceStrings < trace; +fin, notifyList, trace < traceStackTab; +timers < netpollInit; +rwmutexW, sysmon < rwmutexR; +gcBitsArenas, netpollInit, profBlock, profInsert, profMemFuture, spanSetSpine, traceStackTab < gscan; +gscan, rwmutexR < stackpool; +gscan < stackLarge; + +# 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 use this hchanLeaf rank in syncadjustsudogs(), +# rather than hchan. By using this special rank, we don't allow any further +# locks to be acquired other than more hchan locks. +gscan < hchanLeaf; + +hchan, notifyList < sudog; +defer, gscan, mspanSpecial, sudog < wbufSpans; +stackLarge, stackpool, wbufSpans < mheap; +mheap, mheapSpecial < globalAlloc; + +# panic is handled specially. It is implicitly below all other locks. +deadlock < panic; +` + +// cyclicRanks lists lock ranks that allow multiple locks of the same +// rank to be acquired simultaneously. The runtime enforces ordering +// within these ranks using a separate mechanism. +var cyclicRanks = map[string]bool{ + // Multiple timers are locked simultaneously in destroy(). + "timers": true, + // Multiple hchans are acquired in hchan.sortkey() order in + // select. + "hchan": true, + // Multiple hchanLeafs are acquired in hchan.sortkey() order in + // syncadjustsudogs(). + "hchanLeaf": true, +} + +func main() { + flagO := flag.String("o", "", "write to `file` instead of stdout") + flagDot := flag.Bool("dot", false, "emit graphviz output instead of Go") + flag.Parse() + if flag.NArg() != 0 { + fmt.Fprintf(os.Stderr, "too many arguments") + os.Exit(2) + } + + g, err := dag.Parse(ranks) + if err != nil { + log.Fatal(err) + } + + var out []byte + if *flagDot { + var b bytes.Buffer + g.TransitiveReduction() + // Add cyclic edges for visualization. + for k := range cyclicRanks { + g.AddEdge(k, k) + } + // Reverse the graph. It's much easier to read this as + // a "<" partial order than a ">" partial order. This + // ways, locks are acquired from the top going down + // and time moves forward over the edges instead of + // backward. + g.Transpose() + generateDot(&b, g) + out = b.Bytes() + } else { + var b bytes.Buffer + generateGo(&b, g) + out, err = format.Source(b.Bytes()) + if err != nil { + log.Fatal(err) + } + } + + if *flagO != "" { + err = os.WriteFile(*flagO, out, 0666) + } else { + _, err = os.Stdout.Write(out) + } + if err != nil { + log.Fatal(err) + } +} + +func generateGo(w io.Writer, g *dag.Graph) { + fmt.Fprintf(w, `// Code generated by mklockrank.go; DO NOT EDIT. + +package runtime + +type lockRank int + +`) + + // Create numeric ranks. + topo := g.Topo() + for i, j := 0, len(topo)-1; i < j; i, j = i+1, j-1 { + topo[i], topo[j] = topo[j], topo[i] + } + fmt.Fprintf(w, ` +// Constants representing the ranks of all non-leaf runtime locks, in rank order. +// Locks with lower rank must be taken before locks with higher rank, +// in addition to satisfying the partial order in lockPartialOrder. +// A few ranks allow self-cycles, which are specified in lockPartialOrder. +const ( + lockRankUnknown lockRank = iota + +`) + for _, rank := range topo { + fmt.Fprintf(w, "\t%s\n", cname(rank)) + } + fmt.Fprintf(w, `) + +// lockRankLeafRank is the rank of lock that does not have a declared rank, +// and hence is a leaf lock. +const lockRankLeafRank lockRank = 1000 +`) + + // Create string table. + fmt.Fprintf(w, ` +// lockNames gives the names associated with each of the above ranks. +var lockNames = []string{ +`) + for _, rank := range topo { + fmt.Fprintf(w, "\t%s: %q,\n", cname(rank), rank) + } + fmt.Fprintf(w, `} + +func (rank lockRank) String() string { + if rank == 0 { + return "UNKNOWN" + } + if rank == lockRankLeafRank { + return "LEAF" + } + if rank < 0 || int(rank) >= len(lockNames) { + return "BAD RANK" + } + return lockNames[rank] +} +`) + + // Create partial order structure. + fmt.Fprintf(w, ` +// lockPartialOrder is the transitive closure of the lock rank graph. +// An entry for rank X lists all of the ranks that can already be held +// when rank X is acquired. +// +// Lock ranks that allow self-cycles list themselves. +var lockPartialOrder [][]lockRank = [][]lockRank{ +`) + for _, rank := range topo { + list := []string{} + for _, before := range g.Edges(rank) { + list = append(list, cname(before)) + } + if cyclicRanks[rank] { + list = append(list, cname(rank)) + } + + fmt.Fprintf(w, "\t%s: {%s},\n", cname(rank), strings.Join(list, ", ")) + } + fmt.Fprintf(w, "}\n") +} + +// cname returns the Go const name for the given lock rank label. +func cname(label string) string { + return "lockRank" + strings.ToUpper(label[:1]) + label[1:] +} + +// generateDot emits a Graphviz dot representation of g to w. +func generateDot(w io.Writer, g *dag.Graph) { + fmt.Fprintf(w, "digraph g {\n") + + // Define all nodes. + for _, node := range g.Nodes { + fmt.Fprintf(w, "%q;\n", node) + } + + // Create edges. + for _, node := range g.Nodes { + for _, to := range g.Edges(node) { + fmt.Fprintf(w, "%q -> %q;\n", node, to) + } + } + + fmt.Fprintf(w, "}\n") +} -- cgit v1.2.1 From c5be4ed7df3b2ae8f9d0a5c85afa4cf49e22a56d Mon Sep 17 00:00:00 2001 From: Austin Clements Date: Wed, 20 Jul 2022 21:49:15 -0400 Subject: runtime: add missing trace lock edges We're missing lock edges to trace.lock that happen only rarely. Any trace event can potentially fill up a trace buffer and acquire trace.lock in order to flush the buffer, but this happens relatively rarely, so we simply haven't seen some of these lock edges that could happen. With this change, we promote "fin, notifyList < traceStackTab" to "fin, notifyList < trace" and now everything that emits trace events with a P enters the tracer lock ranks via "trace", rather than some things entering at "trace" and others at "traceStackTab". This was found by inspecting the rank graph for things that didn't make sense. Ideally we would add a mayAcquire annotation that any trace event can potentially acquire trace.lock, but there are actually cases that violate this ranking right now. This is #53979. The chance of a lock cycle is extremely low given the number of conditions that have to happen simultaneously. For #53789. Change-Id: Ic65947d27dee88d2daf639b21b2c9d37552f0ac0 Reviewed-on: https://go-review.googlesource.com/c/go/+/418716 Reviewed-by: Michael Pratt Run-TryBot: Austin Clements TryBot-Result: Gopher Robot --- src/runtime/mklockrank.go | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'src/runtime/mklockrank.go') diff --git a/src/runtime/mklockrank.go b/src/runtime/mklockrank.go index 9cb51bedca..110d57faf0 100644 --- a/src/runtime/mklockrank.go +++ b/src/runtime/mklockrank.go @@ -47,8 +47,8 @@ allg, hchan, reflectOffs, timers, traceBuf < fin; traceBuf < traceStrings; allg, hchan, notifyList, reflectOffs, timers, traceStrings < mspanSpecial, profInsert, profBlock, profMemActive, gcBitsArenas, spanSetSpine, mheapSpecial; profMemActive < profMemFuture; -hchan, root, sched, traceStrings < trace; -fin, notifyList, trace < traceStackTab; +hchan, root, sched, traceStrings, notifyList, fin < trace; +trace < traceStackTab; timers < netpollInit; rwmutexW, sysmon < rwmutexR; gcBitsArenas, netpollInit, profBlock, profInsert, profMemFuture, spanSetSpine, traceStackTab < gscan; -- cgit v1.2.1 From d29a0282e9b7340ba2ed3f506e66304e92580238 Mon Sep 17 00:00:00 2001 From: Austin Clements Date: Wed, 20 Jul 2022 15:06:31 -0400 Subject: runtime: add mayAcquire annotation for finlock We're missing lock edges to finlock that happen only rarely. Anything that calls mallocgc can potentially trigger sweeping, which can potentially queue a finalizer, which acquires finlock. While this can happen on any malloc, it happens relatively rarely, so we simply haven't seen some of the lock edges that could happen. Add a mayAcquire annotation to mallocgc to capture the possibility of acquiring finlock. With this change, we add "fin" to the set of "malloc" locks. Several of these edges were already there, but not quite all of them. This was found by inspecting the rank graph for things that didn't make sense. For #53789. Change-Id: Idc10ce6f250596b0c07ba07ac93f2198fb38c22b Reviewed-on: https://go-review.googlesource.com/c/go/+/418717 Run-TryBot: Austin Clements Reviewed-by: Michael Pratt TryBot-Result: Gopher Robot --- src/runtime/mklockrank.go | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'src/runtime/mklockrank.go') diff --git a/src/runtime/mklockrank.go b/src/runtime/mklockrank.go index 110d57faf0..d0b882415c 100644 --- a/src/runtime/mklockrank.go +++ b/src/runtime/mklockrank.go @@ -43,9 +43,8 @@ allp < timers; itab < reflectOffs; scavenge, sweep < hchan; scavenge < traceBuf; -allg, hchan, reflectOffs, timers, traceBuf < fin; traceBuf < traceStrings; -allg, hchan, notifyList, reflectOffs, timers, traceStrings < mspanSpecial, profInsert, profBlock, profMemActive, gcBitsArenas, spanSetSpine, mheapSpecial; +allg, hchan, notifyList, reflectOffs, timers, traceStrings < mspanSpecial, profInsert, profBlock, profMemActive, gcBitsArenas, spanSetSpine, mheapSpecial, fin; profMemActive < profMemFuture; hchan, root, sched, traceStrings, notifyList, fin < trace; trace < traceStackTab; -- cgit v1.2.1 From f42dc0de74f83d39e5ca1af72fc5334c73bd41f9 Mon Sep 17 00:00:00 2001 From: Austin Clements Date: Wed, 20 Jul 2022 16:17:51 -0400 Subject: runtime: make the lock rank DAG make more sense This groups, comments, and generally reorganizes the lock rank graph description by subsystem. It also introduces several pseudo-nodes that more cleanly describe the inherent layering of lock ranks by subsystem. I believe this doesn't actually change the graph, but haven't verified this. For #53789. Change-Id: I72f332f5a23b8217c7dc1b21411631ad48cee4b0 Reviewed-on: https://go-review.googlesource.com/c/go/+/418718 TryBot-Result: Gopher Robot Run-TryBot: Austin Clements Reviewed-by: Michael Pratt --- src/runtime/mklockrank.go | 165 +++++++++++++++++++++++++++++++++++++++------- 1 file changed, 141 insertions(+), 24 deletions(-) (limited to 'src/runtime/mklockrank.go') diff --git a/src/runtime/mklockrank.go b/src/runtime/mklockrank.go index d0b882415c..fc7c0223e4 100644 --- a/src/runtime/mklockrank.go +++ b/src/runtime/mklockrank.go @@ -32,42 +32,144 @@ import ( // lock, which means no other lock can be acquired while it is held. // Therefore, leaf locks do not need to be given an explicit rank. // +// Ranks in all caps are pseudo-nodes that help define order, but do +// not actually define a rank. +// // TODO: It's often hard to correlate rank names to locks. Change // these to be more consistent with the locks they label. const ranks = ` -NONE < sysmon, sweepWaiters, assistQueue, cpuprof, sweep, pollDesc, deadlock, itab, notifyList, root, rwmutexW, defer; -sysmon < scavenge, forcegc; -assistQueue, cpuprof, forcegc, pollDesc, scavenge, sweep, sweepWaiters < sched; +# Sysmon +NONE +< sysmon +< scavenge, forcegc; + +# Defer +NONE < defer; + +# GC +NONE < + sweepWaiters, + assistQueue, + sweep; + +# Scheduler, timers, netpoll +NONE < pollDesc, cpuprof; +assistQueue, + cpuprof, + forcegc, + pollDesc, # pollDesc can interact with timers, which can lock sched. + scavenge, + sweep, + sweepWaiters +< sched; sched < allg, allp; allp < timers; -itab < reflectOffs; +timers < netpollInit; + +# Channels scavenge, sweep < hchan; -scavenge < traceBuf; +NONE < notifyList; +hchan, notifyList < sudog; + +# RWMutex +NONE < rwmutexW; +rwmutexW, sysmon < rwmutexR; + +# Semaphores +NONE < root; + +# Itabs +NONE +< itab +< reflectOffs; + +# Tracing without a P uses a global trace buffer. +scavenge +# Above TRACEGLOBAL can emit a trace event without a P. +< TRACEGLOBAL +# Below TRACEGLOBAL manages the global tracing buffer. +# Note that traceBuf eventually chains to MALLOC, but we never get that far +# in the situation where there's no P. +< traceBuf; +# Starting/stopping tracing traces strings. traceBuf < traceStrings; -allg, hchan, notifyList, reflectOffs, timers, traceStrings < mspanSpecial, profInsert, profBlock, profMemActive, gcBitsArenas, spanSetSpine, mheapSpecial, fin; + +# Malloc +allg, + hchan, + notifyList, + reflectOffs, + timers, + traceStrings +# Above MALLOC are things that can allocate memory. +< MALLOC +# Below MALLOC is the malloc implementation. +< fin, + gcBitsArenas, + mheapSpecial, + mspanSpecial, + spanSetSpine, + MPROF; + +# Memory profiling +MPROF < profInsert, profBlock, profMemActive; profMemActive < profMemFuture; -hchan, root, sched, traceStrings, notifyList, fin < trace; -trace < traceStackTab; -timers < netpollInit; -rwmutexW, sysmon < rwmutexR; -gcBitsArenas, netpollInit, profBlock, profInsert, profMemFuture, spanSetSpine, traceStackTab < gscan; + +# Execution tracer events (with a P) +hchan, + root, + sched, + traceStrings, + notifyList, + fin +# Above TRACE is anything that can create a trace event +< TRACE +< trace +< traceStackTab; + +# Stack allocation and copying +gcBitsArenas, + netpollInit, + profBlock, + profInsert, + profMemFuture, + spanSetSpine, + traceStackTab +# Anything that can grow the stack can acquire STACKGROW. +# (Most higher layers imply STACKGROW, like MALLOC.) +< STACKGROW +# Below STACKGROW is the stack allocator/copying implementation. +< gscan; gscan, rwmutexR < stackpool; gscan < stackLarge; - -# 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 use this hchanLeaf rank in syncadjustsudogs(), -# rather than hchan. By using this special rank, we don't allow any further -# locks to be acquired other than more hchan locks. +# Generally, hchan must be acquired before gscan. But in one case, +# where we suspend a G and then shrink its stack, syncadjustsudogs +# can acquire hchan locks while holding gscan. To allow this case, +# we use hchanLeaf instead of hchan. gscan < hchanLeaf; -hchan, notifyList < sudog; -defer, gscan, mspanSpecial, sudog < wbufSpans; -stackLarge, stackpool, wbufSpans < mheap; +# Write barrier +defer, + gscan, + mspanSpecial, + sudog +# Anything that can have write barriers can acquire WB. +# Above WB, we can have write barriers. +< WB +# Below WB is the write barrier implementation. +< wbufSpans; + +# Span allocator +stackLarge, + stackpool, + wbufSpans +# Above mheap is anything that can call the span allocator. +< mheap; +# Below mheap is the span allocator implementation. mheap, mheapSpecial < globalAlloc; # panic is handled specially. It is implicitly below all other locks. +NONE < deadlock; deadlock < panic; ` @@ -158,7 +260,11 @@ const ( `) for _, rank := range topo { - fmt.Fprintf(w, "\t%s\n", cname(rank)) + if isPseudo(rank) { + fmt.Fprintf(w, "\t// %s\n", rank) + } else { + fmt.Fprintf(w, "\t%s\n", cname(rank)) + } } fmt.Fprintf(w, `) @@ -173,7 +279,9 @@ const lockRankLeafRank lockRank = 1000 var lockNames = []string{ `) for _, rank := range topo { - fmt.Fprintf(w, "\t%s: %q,\n", cname(rank), rank) + if !isPseudo(rank) { + fmt.Fprintf(w, "\t%s: %q,\n", cname(rank), rank) + } } fmt.Fprintf(w, `} @@ -201,9 +309,14 @@ func (rank lockRank) String() string { var lockPartialOrder [][]lockRank = [][]lockRank{ `) for _, rank := range topo { + if isPseudo(rank) { + continue + } list := []string{} for _, before := range g.Edges(rank) { - list = append(list, cname(before)) + if !isPseudo(before) { + list = append(list, cname(before)) + } } if cyclicRanks[rank] { list = append(list, cname(rank)) @@ -219,6 +332,10 @@ func cname(label string) string { return "lockRank" + strings.ToUpper(label[:1]) + label[1:] } +func isPseudo(label string) bool { + return strings.ToUpper(label) == label +} + // generateDot emits a Graphviz dot representation of g to w. func generateDot(w io.Writer, g *dag.Graph) { fmt.Fprintf(w, "digraph g {\n") -- cgit v1.2.1 From 44ff9bff0cd02642c37cce0223d25dc57230c8d2 Mon Sep 17 00:00:00 2001 From: Austin Clements Date: Wed, 20 Jul 2022 17:44:45 -0400 Subject: runtime: clean up panic and deadlock lock ranks I'm not entirely sure why these locks are currently ranked "deadlock < panic" since we drop panic before acquiring deadlock, and we actually want deadlock to be below panic because panic is implicitly below everything else and we want deadlock to be, too. My best guess is that we had this edge because we intentionally acquire deadlock twice to deadlock, and that causes the lock rank checking to panic on the second acquire. Fix this in a more sensible way by capturing that deadlock can be acquired in a self-cycle and flipping the rank to "panic < deadlock" to express that deadlock needs to be under all other locks, just like panic. For #53789. Change-Id: I8809e5d102ce473bd3ace0ba07bf2200ef60263f Reviewed-on: https://go-review.googlesource.com/c/go/+/418719 TryBot-Result: Gopher Robot Reviewed-by: Michael Pratt Run-TryBot: Austin Clements --- src/runtime/mklockrank.go | 8 ++++++-- 1 file changed, 6 insertions(+), 2 deletions(-) (limited to 'src/runtime/mklockrank.go') diff --git a/src/runtime/mklockrank.go b/src/runtime/mklockrank.go index fc7c0223e4..0d50d60a22 100644 --- a/src/runtime/mklockrank.go +++ b/src/runtime/mklockrank.go @@ -169,8 +169,10 @@ stackLarge, mheap, mheapSpecial < globalAlloc; # panic is handled specially. It is implicitly below all other locks. -NONE < deadlock; -deadlock < panic; +NONE < panic; +# deadlock is not acquired while holding panic, but it also needs to be +# below all other locks. +panic < deadlock; ` // cyclicRanks lists lock ranks that allow multiple locks of the same @@ -185,6 +187,8 @@ var cyclicRanks = map[string]bool{ // Multiple hchanLeafs are acquired in hchan.sortkey() order in // syncadjustsudogs(). "hchanLeaf": true, + // The point of the deadlock lock is to deadlock. + "deadlock": true, } func main() { -- cgit v1.2.1