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 < netpollInit;
  68
  69 # Channels
  70 scavenge, sweep < hchan;
  71 NONE < notifyList;
  72 hchan, notifyList < sudog;
  73
  74 # RWMutex
  75 NONE < rwmutexW;
  76 rwmutexW, sysmon < rwmutexR;
  77
  78 # Semaphores
  79 NONE < root;
  80
  81 # Itabs
  82 NONE
  83 < itab
  84 < reflectOffs;
  85
  86 # Tracing without a P uses a global trace buffer.
  87 scavenge
  88 # Above TRACEGLOBAL can emit a trace event without a P.
  89 < TRACEGLOBAL
  90 # Below TRACEGLOBAL manages the global tracing buffer.
  91 # Note that traceBuf eventually chains to MALLOC, but we never get that far
  92 # in the situation where there's no P.
  93 < traceBuf;
  94 # Starting/stopping tracing traces strings.
  95 traceBuf < traceStrings;
  96
  97 # Malloc
  98 allg,
  99   hchan,
 100   notifyList,
 101   reflectOffs,
 102   timers,
 103   traceStrings
 104 # Above MALLOC are things that can allocate memory.
 105 < MALLOC
 106 # Below MALLOC is the malloc implementation.
 107 < fin,
 108   gcBitsArenas,
 109   mheapSpecial,
 110   mspanSpecial,
 111   spanSetSpine,
 112   MPROF;
 113
 114 # Memory profiling
 115 MPROF < profInsert, profBlock, profMemActive;
 116 profMemActive < profMemFuture;
 117
 118 # Execution tracer events (with a P)
 119 hchan,
 120   root,
 121   sched,
 122   traceStrings,
 123   notifyList,
 124   fin
 125 # Above TRACE is anything that can create a trace event
 126 < TRACE
 127 < trace
 128 < traceStackTab;
 129
 130 # Stack allocation and copying
 131 gcBitsArenas,
 132   netpollInit,
 133   profBlock,
 134   profInsert,
 135   profMemFuture,
 136   spanSetSpine,
 137   traceStackTab
 138 # Anything that can grow the stack can acquire STACKGROW.
 139 # (Most higher layers imply STACKGROW, like MALLOC.)
 140 < STACKGROW
 141 # Below STACKGROW is the stack allocator/copying implementation.
 142 < gscan;
 143 gscan, rwmutexR < stackpool;
 144 gscan < stackLarge;
 145 # Generally, hchan must be acquired before gscan. But in one case,
 146 # where we suspend a G and then shrink its stack, syncadjustsudogs
 147 # can acquire hchan locks while holding gscan. To allow this case,
 148 # we use hchanLeaf instead of hchan.
 149 gscan < hchanLeaf;
 150
 151 # Write barrier
 152 defer,
 153   gscan,
 154   mspanSpecial,
 155   sudog
 156 # Anything that can have write barriers can acquire WB.
 157 # Above WB, we can have write barriers.
 158 < WB
 159 # Below WB is the write barrier implementation.
 160 < wbufSpans;
 161
 162 # Span allocator
 163 stackLarge,
 164   stackpool,
 165   wbufSpans
 166 # Above mheap is anything that can call the span allocator.
 167 < mheap;
 168 # Below mheap is the span allocator implementation.
 169 mheap, mheapSpecial < globalAlloc;
 170
 171 # panic is handled specially. It is implicitly below all other locks.
 172 NONE < deadlock;
 173 deadlock < panic;
 174 `
 175
 176 // cyclicRanks lists lock ranks that allow multiple locks of the same
 177 // rank to be acquired simultaneously. The runtime enforces ordering
 178 // within these ranks using a separate mechanism.
 179 var cyclicRanks = map[string]bool{
 180         // Multiple timers are locked simultaneously in destroy().
 181         "timers": true,
 182         // Multiple hchans are acquired in hchan.sortkey() order in
 183         // select.
 184         "hchan": true,
 185         // Multiple hchanLeafs are acquired in hchan.sortkey() order in
 186         // syncadjustsudogs().
 187         "hchanLeaf": true,
 188 }
 189
 190 func main() {
 191         flagO := flag.String("o", "", "write to `file` instead of stdout")
 192         flagDot := flag.Bool("dot", false, "emit graphviz output instead of Go")
 193         flag.Parse()
 194         if flag.NArg() != 0 {
 195                 fmt.Fprintf(os.Stderr, "too many arguments")
 196                 os.Exit(2)
 197         }
 198
 199         g, err := dag.Parse(ranks)
 200         if err != nil {
 201                 log.Fatal(err)
 202         }
 203
 204         var out []byte
 205         if *flagDot {
 206                 var b bytes.Buffer
 207                 g.TransitiveReduction()
 208                 // Add cyclic edges for visualization.
 209                 for k := range cyclicRanks {
 210                         g.AddEdge(k, k)
 211                 }
 212                 // Reverse the graph. It's much easier to read this as
 213                 // a "<" partial order than a ">" partial order. This
 214                 // ways, locks are acquired from the top going down
 215                 // and time moves forward over the edges instead of
 216                 // backward.
 217                 g.Transpose()
 218                 generateDot(&b, g)
 219                 out = b.Bytes()
 220         } else {
 221                 var b bytes.Buffer
 222                 generateGo(&b, g)
 223                 out, err = format.Source(b.Bytes())
 224                 if err != nil {
 225                         log.Fatal(err)
 226                 }
 227         }
 228
 229         if *flagO != "" {
 230                 err = os.WriteFile(*flagO, out, 0666)
 231         } else {
 232                 _, err = os.Stdout.Write(out)
 233         }
 234         if err != nil {
 235                 log.Fatal(err)
 236         }
 237 }
 238
 239 func generateGo(w io.Writer, g *dag.Graph) {
 240         fmt.Fprintf(w, `// Code generated by mklockrank.go; DO NOT EDIT.
 241
 242 package runtime
 243
 244 type lockRank int
 245
 246 `)
 247
 248         // Create numeric ranks.
 249         topo := g.Topo()
 250         for i, j := 0, len(topo)-1; i < j; i, j = i+1, j-1 {
 251                 topo[i], topo[j] = topo[j], topo[i]
 252         }
 253         fmt.Fprintf(w, `
 254 // Constants representing the ranks of all non-leaf runtime locks, in rank order.
 255 // Locks with lower rank must be taken before locks with higher rank,
 256 // in addition to satisfying the partial order in lockPartialOrder.
 257 // A few ranks allow self-cycles, which are specified in lockPartialOrder.
 258 const (
 259         lockRankUnknown lockRank = iota
 260
 261 `)
 262         for _, rank := range topo {
 263                 if isPseudo(rank) {
 264                         fmt.Fprintf(w, "\t// %s\n", rank)
 265                 } else {
 266                         fmt.Fprintf(w, "\t%s\n", cname(rank))
 267                 }
 268         }
 269         fmt.Fprintf(w, `)
 270
 271 // lockRankLeafRank is the rank of lock that does not have a declared rank,
 272 // and hence is a leaf lock.
 273 const lockRankLeafRank lockRank = 1000
 274 `)
 275
 276         // Create string table.
 277         fmt.Fprintf(w, `
 278 // lockNames gives the names associated with each of the above ranks.
 279 var lockNames = []string{
 280 `)
 281         for _, rank := range topo {
 282                 if !isPseudo(rank) {
 283                         fmt.Fprintf(w, "\t%s: %q,\n", cname(rank), rank)
 284                 }
 285         }
 286         fmt.Fprintf(w, `}
 287
 288 func (rank lockRank) String() string {
 289         if rank == 0 {
 290                 return "UNKNOWN"
 291         }
 292         if rank == lockRankLeafRank {
 293                 return "LEAF"
 294         }
 295         if rank < 0 || int(rank) >= len(lockNames) {
 296                 return "BAD RANK"
 297         }
 298         return lockNames[rank]
 299 }
 300 `)
 301
 302         // Create partial order structure.
 303         fmt.Fprintf(w, `
 304 // lockPartialOrder is the transitive closure of the lock rank graph.
 305 // An entry for rank X lists all of the ranks that can already be held
 306 // when rank X is acquired.
 307 //
 308 // Lock ranks that allow self-cycles list themselves.
 309 var lockPartialOrder [][]lockRank = [][]lockRank{
 310 `)
 311         for _, rank := range topo {
 312                 if isPseudo(rank) {
 313                         continue
 314                 }
 315                 list := []string{}
 316                 for _, before := range g.Edges(rank) {
 317                         if !isPseudo(before) {
 318                                 list = append(list, cname(before))
 319                         }
 320                 }
 321                 if cyclicRanks[rank] {
 322                         list = append(list, cname(rank))
 323                 }
 324
 325                 fmt.Fprintf(w, "\t%s: {%s},\n", cname(rank), strings.Join(list, ", "))
 326         }
 327         fmt.Fprintf(w, "}\n")
 328 }
 329
 330 // cname returns the Go const name for the given lock rank label.
 331 func cname(label string) string {
 332         return "lockRank" + strings.ToUpper(label[:1]) + label[1:]
 333 }
 334
 335 func isPseudo(label string) bool {
 336         return strings.ToUpper(label) == label
 337 }
 338
 339 // generateDot emits a Graphviz dot representation of g to w.
 340 func generateDot(w io.Writer, g *dag.Graph) {
 341         fmt.Fprintf(w, "digraph g {\n")
 342
 343         // Define all nodes.
 344         for _, node := range g.Nodes {
 345                 fmt.Fprintf(w, "%q;\n", node)
 346         }
 347
 348         // Create edges.
 349         for _, node := range g.Nodes {
 350                 for _, to := range g.Edges(node) {
 351                         fmt.Fprintf(w, "%q -> %q;\n", node, to)
 352                 }
 353         }
 354
 355         fmt.Fprintf(w, "}\n")
 356 }