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 // TODO: It's often hard to correlate rank names to locks. Change
  36 // these to be more consistent with the locks they label.
  37 const ranks = `
  38 NONE < sysmon, sweepWaiters, assistQueue, cpuprof, sweep, pollDesc, deadlock, itab, notifyList, root, rwmutexW, defer;
  39 sysmon < scavenge, forcegc;
  40 assistQueue, cpuprof, forcegc, pollDesc, scavenge, sweep, sweepWaiters < sched;
  41 sched < allg, allp;
  42 allp < timers;
  43 itab < reflectOffs;
  44 scavenge, sweep < hchan;
  45 scavenge < traceBuf;
  46 allg, hchan, reflectOffs, timers, traceBuf < fin;
  47 traceBuf < traceStrings;
  48 allg, hchan, notifyList, reflectOffs, timers, traceStrings < mspanSpecial, profInsert, profBlock, profMemActive, gcBitsArenas, spanSetSpine, mheapSpecial;
  49 profMemActive < profMemFuture;
  50 hchan, root, sched, traceStrings, notifyList, fin < trace;
  51 trace < traceStackTab;
  52 timers < netpollInit;
  53 rwmutexW, sysmon < rwmutexR;
  54 gcBitsArenas, netpollInit, profBlock, profInsert, profMemFuture, spanSetSpine, traceStackTab < gscan;
  55 gscan, rwmutexR < stackpool;
  56 gscan < stackLarge;
  57
  58 # Generally, hchan must be acquired before gscan. But in one specific
  59 # case (in syncadjustsudogs from markroot after the g has been suspended
  60 # by suspendG), we allow gscan to be acquired, and then an hchan lock. To
  61 # allow this case, we use this hchanLeaf rank in syncadjustsudogs(),
  62 # rather than hchan. By using this special rank, we don't allow any further
  63 # locks to be acquired other than more hchan locks.
  64 gscan < hchanLeaf;
  65
  66 hchan, notifyList < sudog;
  67 defer, gscan, mspanSpecial, sudog < wbufSpans;
  68 stackLarge, stackpool, wbufSpans < mheap;
  69 mheap, mheapSpecial < globalAlloc;
  70
  71 # panic is handled specially. It is implicitly below all other locks.
  72 deadlock < panic;
  73 `
  74
  75 // cyclicRanks lists lock ranks that allow multiple locks of the same
  76 // rank to be acquired simultaneously. The runtime enforces ordering
  77 // within these ranks using a separate mechanism.
  78 var cyclicRanks = map[string]bool{
  79         // Multiple timers are locked simultaneously in destroy().
  80         "timers": true,
  81         // Multiple hchans are acquired in hchan.sortkey() order in
  82         // select.
  83         "hchan": true,
  84         // Multiple hchanLeafs are acquired in hchan.sortkey() order in
  85         // syncadjustsudogs().
  86         "hchanLeaf": true,
  87 }
  88
  89 func main() {
  90         flagO := flag.String("o", "", "write to `file` instead of stdout")
  91         flagDot := flag.Bool("dot", false, "emit graphviz output instead of Go")
  92         flag.Parse()
  93         if flag.NArg() != 0 {
  94                 fmt.Fprintf(os.Stderr, "too many arguments")
  95                 os.Exit(2)
  96         }
  97
  98         g, err := dag.Parse(ranks)
  99         if err != nil {
 100                 log.Fatal(err)
 101         }
 102
 103         var out []byte
 104         if *flagDot {
 105                 var b bytes.Buffer
 106                 g.TransitiveReduction()
 107                 // Add cyclic edges for visualization.
 108                 for k := range cyclicRanks {
 109                         g.AddEdge(k, k)
 110                 }
 111                 // Reverse the graph. It's much easier to read this as
 112                 // a "<" partial order than a ">" partial order. This
 113                 // ways, locks are acquired from the top going down
 114                 // and time moves forward over the edges instead of
 115                 // backward.
 116                 g.Transpose()
 117                 generateDot(&b, g)
 118                 out = b.Bytes()
 119         } else {
 120                 var b bytes.Buffer
 121                 generateGo(&b, g)
 122                 out, err = format.Source(b.Bytes())
 123                 if err != nil {
 124                         log.Fatal(err)
 125                 }
 126         }
 127
 128         if *flagO != "" {
 129                 err = os.WriteFile(*flagO, out, 0666)
 130         } else {
 131                 _, err = os.Stdout.Write(out)
 132         }
 133         if err != nil {
 134                 log.Fatal(err)
 135         }
 136 }
 137
 138 func generateGo(w io.Writer, g *dag.Graph) {
 139         fmt.Fprintf(w, `// Code generated by mklockrank.go; DO NOT EDIT.
 140
 141 package runtime
 142
 143 type lockRank int
 144
 145 `)
 146
 147         // Create numeric ranks.
 148         topo := g.Topo()
 149         for i, j := 0, len(topo)-1; i < j; i, j = i+1, j-1 {
 150                 topo[i], topo[j] = topo[j], topo[i]
 151         }
 152         fmt.Fprintf(w, `
 153 // Constants representing the ranks of all non-leaf runtime locks, in rank order.
 154 // Locks with lower rank must be taken before locks with higher rank,
 155 // in addition to satisfying the partial order in lockPartialOrder.
 156 // A few ranks allow self-cycles, which are specified in lockPartialOrder.
 157 const (
 158         lockRankUnknown lockRank = iota
 159
 160 `)
 161         for _, rank := range topo {
 162                 fmt.Fprintf(w, "\t%s\n", cname(rank))
 163         }
 164         fmt.Fprintf(w, `)
 165
 166 // lockRankLeafRank is the rank of lock that does not have a declared rank,
 167 // and hence is a leaf lock.
 168 const lockRankLeafRank lockRank = 1000
 169 `)
 170
 171         // Create string table.
 172         fmt.Fprintf(w, `
 173 // lockNames gives the names associated with each of the above ranks.
 174 var lockNames = []string{
 175 `)
 176         for _, rank := range topo {
 177                 fmt.Fprintf(w, "\t%s: %q,\n", cname(rank), rank)
 178         }
 179         fmt.Fprintf(w, `}
 180
 181 func (rank lockRank) String() string {
 182         if rank == 0 {
 183                 return "UNKNOWN"
 184         }
 185         if rank == lockRankLeafRank {
 186                 return "LEAF"
 187         }
 188         if rank < 0 || int(rank) >= len(lockNames) {
 189                 return "BAD RANK"
 190         }
 191         return lockNames[rank]
 192 }
 193 `)
 194
 195         // Create partial order structure.
 196         fmt.Fprintf(w, `
 197 // lockPartialOrder is the transitive closure of the lock rank graph.
 198 // An entry for rank X lists all of the ranks that can already be held
 199 // when rank X is acquired.
 200 //
 201 // Lock ranks that allow self-cycles list themselves.
 202 var lockPartialOrder [][]lockRank = [][]lockRank{
 203 `)
 204         for _, rank := range topo {
 205                 list := []string{}
 206                 for _, before := range g.Edges(rank) {
 207                         list = append(list, cname(before))
 208                 }
 209                 if cyclicRanks[rank] {
 210                         list = append(list, cname(rank))
 211                 }
 212
 213                 fmt.Fprintf(w, "\t%s: {%s},\n", cname(rank), strings.Join(list, ", "))
 214         }
 215         fmt.Fprintf(w, "}\n")
 216 }
 217
 218 // cname returns the Go const name for the given lock rank label.
 219 func cname(label string) string {
 220         return "lockRank" + strings.ToUpper(label[:1]) + label[1:]
 221 }
 222
 223 // generateDot emits a Graphviz dot representation of g to w.
 224 func generateDot(w io.Writer, g *dag.Graph) {
 225         fmt.Fprintf(w, "digraph g {\n")
 226
 227         // Define all nodes.
 228         for _, node := range g.Nodes {
 229                 fmt.Fprintf(w, "%q;\n", node)
 230         }
 231
 232         // Create edges.
 233         for _, node := range g.Nodes {
 234                 for _, to := range g.Edges(node) {
 235                         fmt.Fprintf(w, "%q -> %q;\n", node, to)
 236                 }
 237         }
 238
 239         fmt.Fprintf(w, "}\n")
 240 }