// 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 < wakeableSleep;
+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;
+
+# User arena state
+NONE < userArenaState;
+
+# 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,
+ userArenaState
+# Above MALLOC are things that can allocate memory.
+< MALLOC
+# Below MALLOC is the malloc implementation.
+< fin,
+ spanSetSpine,
+ mspanSpecial,
+ MPROF;
+
+# We can acquire gcBitsArenas for pinner bits, and
+# it's guarded by mspanSpecial.
+MALLOC, mspanSpecial < gcBitsArenas;
+
+# 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;
+
+# Stack allocation and copying
+gcBitsArenas,
+ netpollInit,
+ profBlock,
+ profInsert,
+ profMemFuture,
+ spanSetSpine,
+ fin,
+ root
+# 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.
+#
+# Specials: we're allowed to allocate a special while holding
+# an mspanSpecial lock, and they're part of the malloc implementation.
+# Pinner bits might be freed by the span allocator.
+mheap, mspanSpecial < mheapSpecial;
mheap, mheapSpecial < globalAlloc;
+# Execution tracer events (with a P)
+hchan,
+ mheap,
+ root,
+ sched,
+ traceStrings,
+ notifyList,
+ fin
+# Above TRACE is anything that can create a trace event
+< TRACE
+< trace
+< traceStackTab;
+
# panic is handled specially. It is implicitly below all other locks.
-deadlock < panic;
+NONE < panic;
+# deadlock is not acquired while holding panic, but it also needs to be
+# below all other locks.
+panic < deadlock;
+# raceFini is only held while exiting.
+panic < raceFini;
`
// cyclicRanks lists lock ranks that allow multiple locks of the same
// 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() {
`)
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, `)
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, `}
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))
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")