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