src/runtime/mklockrank.go

   1 // Copyright 2022 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 //go:build ignore
   6
   7 // mklockrank records the static rank graph of the locks in the
   8 // runtime and generates the rank checking structures in lockrank.go.
   9 package main
  10
  11 import (
  12         "bytes"
  13         "flag"
  14         "fmt"
  15         "go/format"
  16         "internal/dag"
  17         "io"
  18         "log"
  19         "os"
  20         "strings"
  21 )
  22
  23 // ranks describes the lock rank graph. See "go doc internal/dag" for
  24 // the syntax.
  25 //
  26 // "a < b" means a must be acquired before b if both are held
  27 // (or, if b is held, a cannot be acquired).
  28 //
  29 // "NONE < a" means no locks may be held when a is acquired.
  30 //
  31 // If a lock is not given a rank, then it is assumed to be a leaf
  32 // lock, which means no other lock can be acquired while it is held.
  33 // Therefore, leaf locks do not need to be given an explicit rank.
  34 //
  35 // Ranks in all caps are pseudo-nodes that help define order, but do
  36 // not actually define a rank.
  37 //
  38 // TODO: It's often hard to correlate rank names to locks. Change
  39 // these to be more consistent with the locks they label.
  40 const ranks = `
  41 # Sysmon
  42 NONE
  43 < sysmon
  44 < scavenge, forcegc;
  45
  46 # Defer
  47 NONE < defer;
  48
  49 # GC
  50 NONE <
  51   sweepWaiters,
  52   assistQueue,
  53   sweep;
  54
  55 # Scheduler, timers, netpoll
  56 NONE < pollDesc, cpuprof;
  57 assistQueue,
  58   cpuprof,
  59   forcegc,
  60   pollDesc, # pollDesc can interact with timers, which can lock sched.
  61   scavenge,
  62   sweep,
  63   sweepWaiters
  64 < sched;
  65 sched < allg, allp;
  66 allp < timers;
  67 timers < wakeableSleep;
  68 timers < netpollInit;
  69
  70 # Channels
  71 scavenge, sweep < hchan;
  72 NONE < notifyList;
  73 hchan, notifyList < sudog;
  74
  75 # RWMutex
  76 NONE < rwmutexW;
  77 rwmutexW, sysmon < rwmutexR;
  78
  79 # Semaphores
  80 NONE < root;
  81
  82 # Itabs
  83 NONE
  84 < itab
  85 < reflectOffs;
  86
  87 # User arena state
  88 NONE < userArenaState;
  89
  90 # Tracing without a P uses a global trace buffer.
  91 scavenge
  92 # Above TRACEGLOBAL can emit a trace event without a P.
  93 < TRACEGLOBAL
  94 # Below TRACEGLOBAL manages the global tracing buffer.
  95 # Note that traceBuf eventually chains to MALLOC, but we never get that far
  96 # in the situation where there's no P.
  97 < traceBuf;
  98 # Starting/stopping tracing traces strings.
  99 traceBuf < traceStrings;
 100
 101 # Malloc
 102 allg,
 103   hchan,
 104   notifyList,
 105   reflectOffs,
 106   timers,
 107   traceStrings,
 108   userArenaState
 109 # Above MALLOC are things that can allocate memory.
 110 < MALLOC
 111 # Below MALLOC is the malloc implementation.
 112 < fin,
 113   spanSetSpine,
 114   mspanSpecial,
 115   MPROF;
 116
 117 # We can acquire gcBitsArenas for pinner bits, and
 118 # it's guarded by mspanSpecial.
 119 MALLOC, mspanSpecial < gcBitsArenas;
 120
 121 # Memory profiling
 122 MPROF < profInsert, profBlock, profMemActive;
 123 profMemActive < profMemFuture;
 124
 125 # Stack allocation and copying
 126 gcBitsArenas,
 127   netpollInit,
 128   profBlock,
 129   profInsert,
 130   profMemFuture,
 131   spanSetSpine,
 132   fin,
 133   root
 134 # Anything that can grow the stack can acquire STACKGROW.
 135 # (Most higher layers imply STACKGROW, like MALLOC.)
 136 < STACKGROW
 137 # Below STACKGROW is the stack allocator/copying implementation.
 138 < gscan;
 139 gscan, rwmutexR < stackpool;
 140 gscan < stackLarge;
 141 # Generally, hchan must be acquired before gscan. But in one case,
 142 # where we suspend a G and then shrink its stack, syncadjustsudogs
 143 # can acquire hchan locks while holding gscan. To allow this case,
 144 # we use hchanLeaf instead of hchan.
 145 gscan < hchanLeaf;
 146
 147 # Write barrier
 148 defer,
 149   gscan,
 150   mspanSpecial,
 151   sudog
 152 # Anything that can have write barriers can acquire WB.
 153 # Above WB, we can have write barriers.
 154 < WB
 155 # Below WB is the write barrier implementation.
 156 < wbufSpans;
 157
 158 # Span allocator
 159 stackLarge,
 160   stackpool,
 161   wbufSpans
 162 # Above mheap is anything that can call the span allocator.
 163 < mheap;
 164 # Below mheap is the span allocator implementation.
 165 #
 166 # Specials: we're allowed to allocate a special while holding
 167 # an mspanSpecial lock, and they're part of the malloc implementation.
 168 # Pinner bits might be freed by the span allocator.
 169 mheap, mspanSpecial < mheapSpecial;
 170 mheap, mheapSpecial < globalAlloc;
 171
 172 # Execution tracer events (with a P)
 173 hchan,
 174   mheap,
 175   root,
 176   sched,
 177   traceStrings,
 178   notifyList,
 179   fin
 180 # Above TRACE is anything that can create a trace event
 181 < TRACE
 182 < trace
 183 < traceStackTab;
 184
 185 # panic is handled specially. It is implicitly below all other locks.
 186 NONE < panic;
 187 # deadlock is not acquired while holding panic, but it also needs to be
 188 # below all other locks.
 189 panic < deadlock;
 190 # raceFini is only held while exiting.
 191 panic < raceFini;
 192 `
 193
 194 // cyclicRanks lists lock ranks that allow multiple locks of the same
 195 // rank to be acquired simultaneously. The runtime enforces ordering
 196 // within these ranks using a separate mechanism.
 197 var cyclicRanks = map[string]bool{
 198         // Multiple timers are locked simultaneously in destroy().
 199         "timers": true,
 200         // Multiple hchans are acquired in hchan.sortkey() order in
 201         // select.
 202         "hchan": true,
 203         // Multiple hchanLeafs are acquired in hchan.sortkey() order in
 204         // syncadjustsudogs().
 205         "hchanLeaf": true,
 206         // The point of the deadlock lock is to deadlock.
 207         "deadlock": true,
 208 }
 209
 210 func main() {
 211         flagO := flag.String("o", "", "write to `file` instead of stdout")
 212         flagDot := flag.Bool("dot", false, "emit graphviz output instead of Go")
 213         flag.Parse()
 214         if flag.NArg() != 0 {
 215                 fmt.Fprintf(os.Stderr, "too many arguments")
 216                 os.Exit(2)
 217         }
 218
 219         g, err := dag.Parse(ranks)
 220         if err != nil {
 221                 log.Fatal(err)
 222         }
 223
 224         var out []byte
 225         if *flagDot {
 226                 var b bytes.Buffer
 227                 g.TransitiveReduction()
 228                 // Add cyclic edges for visualization.
 229                 for k := range cyclicRanks {
 230                         g.AddEdge(k, k)
 231                 }
 232                 // Reverse the graph. It's much easier to read this as
 233                 // a "<" partial order than a ">" partial order. This
 234                 // ways, locks are acquired from the top going down
 235                 // and time moves forward over the edges instead of
 236                 // backward.
 237                 g.Transpose()
 238                 generateDot(&b, g)
 239                 out = b.Bytes()
 240         } else {
 241                 var b bytes.Buffer
 242                 generateGo(&b, g)
 243                 out, err = format.Source(b.Bytes())
 244                 if err != nil {
 245                         log.Fatal(err)
 246                 }
 247         }
 248
 249         if *flagO != "" {
 250                 err = os.WriteFile(*flagO, out, 0666)
 251         } else {
 252                 _, err = os.Stdout.Write(out)
 253         }
 254         if err != nil {
 255                 log.Fatal(err)
 256         }
 257 }
 258
 259 func generateGo(w io.Writer, g *dag.Graph) {
 260         fmt.Fprintf(w, `// Code generated by mklockrank.go; DO NOT EDIT.
 261
 262 package runtime
 263
 264 type lockRank int
 265
 266 `)
 267
 268         // Create numeric ranks.
 269         topo := g.Topo()
 270         for i, j := 0, len(topo)-1; i < j; i, j = i+1, j-1 {
 271                 topo[i], topo[j] = topo[j], topo[i]
 272         }
 273         fmt.Fprintf(w, `
 274 // Constants representing the ranks of all non-leaf runtime locks, in rank order.
 275 // Locks with lower rank must be taken before locks with higher rank,
 276 // in addition to satisfying the partial order in lockPartialOrder.
 277 // A few ranks allow self-cycles, which are specified in lockPartialOrder.
 278 const (
 279         lockRankUnknown lockRank = iota
 280
 281 `)
 282         for _, rank := range topo {
 283                 if isPseudo(rank) {
 284                         fmt.Fprintf(w, "\t// %s\n", rank)
 285                 } else {
 286                         fmt.Fprintf(w, "\t%s\n", cname(rank))
 287                 }
 288         }
 289         fmt.Fprintf(w, `)
 290
 291 // lockRankLeafRank is the rank of lock that does not have a declared rank,
 292 // and hence is a leaf lock.
 293 const lockRankLeafRank lockRank = 1000
 294 `)
 295
 296         // Create string table.
 297         fmt.Fprintf(w, `
 298 // lockNames gives the names associated with each of the above ranks.
 299 var lockNames = []string{
 300 `)
 301         for _, rank := range topo {
 302                 if !isPseudo(rank) {
 303                         fmt.Fprintf(w, "\t%s: %q,\n", cname(rank), rank)
 304                 }
 305         }
 306         fmt.Fprintf(w, `}
 307
 308 func (rank lockRank) String() string {
 309         if rank == 0 {
 310                 return "UNKNOWN"
 311         }
 312         if rank == lockRankLeafRank {
 313                 return "LEAF"
 314         }
 315         if rank < 0 || int(rank) >= len(lockNames) {
 316                 return "BAD RANK"
 317         }
 318         return lockNames[rank]
 319 }
 320 `)
 321
 322         // Create partial order structure.
 323         fmt.Fprintf(w, `
 324 // lockPartialOrder is the transitive closure of the lock rank graph.
 325 // An entry for rank X lists all of the ranks that can already be held
 326 // when rank X is acquired.
 327 //
 328 // Lock ranks that allow self-cycles list themselves.
 329 var lockPartialOrder [][]lockRank = [][]lockRank{
 330 `)
 331         for _, rank := range topo {
 332                 if isPseudo(rank) {
 333                         continue
 334                 }
 335                 list := []string{}
 336                 for _, before := range g.Edges(rank) {
 337                         if !isPseudo(before) {
 338                                 list = append(list, cname(before))
 339                         }
 340                 }
 341                 if cyclicRanks[rank] {
 342                         list = append(list, cname(rank))
 343                 }
 344
 345                 fmt.Fprintf(w, "\t%s: {%s},\n", cname(rank), strings.Join(list, ", "))
 346         }
 347         fmt.Fprintf(w, "}\n")
 348 }
 349
 350 // cname returns the Go const name for the given lock rank label.
 351 func cname(label string) string {
 352         return "lockRank" + strings.ToUpper(label[:1]) + label[1:]
 353 }
 354
 355 func isPseudo(label string) bool {
 356         return strings.ToUpper(label) == label
 357 }
 358
 359 // generateDot emits a Graphviz dot representation of g to w.
 360 func generateDot(w io.Writer, g *dag.Graph) {
 361         fmt.Fprintf(w, "digraph g {\n")
 362
 363         // Define all nodes.
 364         for _, node := range g.Nodes {
 365                 fmt.Fprintf(w, "%q;\n", node)
 366         }
 367
 368         // Create edges.
 369         for _, node := range g.Nodes {
 370                 for _, to := range g.Edges(node) {
 371                         fmt.Fprintf(w, "%q -> %q;\n", node, to)
 372                 }
 373         }
 374
 375         fmt.Fprintf(w, "}\n")
 376 }