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, computeMaxProcs, updateMaxProcsG;
    45  
    46  # Defer
    47  NONE < defer;
    48  
    49  # GC
    50  NONE <
    51    sweepWaiters,
    52    assistQueue,
    53    strongFromWeakQueue,
    54    cleanupQueue,
    55    sweep;
    56  
    57  # Test only
    58  NONE < testR, testW;
    59  
    60  # vgetrandom
    61  NONE < vgetrandom;
    62  
    63  NONE < timerSend;
    64  
    65  # Scheduler, timers, netpoll
    66  NONE < allocmW, execW, cpuprof, pollCache, pollDesc, wakeableSleep;
    67  scavenge, sweep, testR, wakeableSleep, timerSend < hchan;
    68  assistQueue,
    69    cleanupQueue,
    70    computeMaxProcs,
    71    cpuprof,
    72    forcegc,
    73    updateMaxProcsG,
    74    hchan,
    75    pollDesc, # pollDesc can interact with timers, which can lock sched.
    76    scavenge,
    77    strongFromWeakQueue,
    78    sweep,
    79    sweepWaiters,
    80    testR,
    81    wakeableSleep
    82  # Above SCHED are things that can call into the scheduler.
    83  < SCHED
    84  # Below SCHED is the scheduler implementation.
    85  < allocmR,
    86    execR;
    87  allocmR, execR, hchan < sched;
    88  sched < allg, allp;
    89  
    90  # Channels
    91  NONE < notifyList;
    92  hchan, notifyList < sudog;
    93  
    94  hchan, pollDesc, wakeableSleep < timers;
    95  timers, timerSend < timer < netpollInit;
    96  
    97  # Semaphores
    98  NONE < root;
    99  
   100  # Itabs
   101  NONE
   102  < itab
   103  < reflectOffs;
   104  
   105  # Typelinks
   106  NONE
   107  < typelinks;
   108  
   109  # Synctest
   110  hchan,
   111    notifyList,
   112    reflectOffs,
   113    root,
   114    strongFromWeakQueue,
   115    sweepWaiters,
   116    timer,
   117    timers
   118  < synctest;
   119  
   120  # User arena state
   121  NONE < userArenaState;
   122  
   123  # Tracing without a P uses a global trace buffer.
   124  scavenge
   125  # Above TRACEGLOBAL can emit a trace event without a P.
   126  < TRACEGLOBAL
   127  # Below TRACEGLOBAL manages the global tracing buffer.
   128  # Note that traceBuf eventually chains to MALLOC, but we never get that far
   129  # in the situation where there's no P.
   130  < traceBuf;
   131  # Starting/stopping tracing traces strings.
   132  traceBuf < traceStrings;
   133  
   134  # Malloc
   135  allg,
   136    allocmR,
   137    allp, # procresize
   138    execR, # May grow stack
   139    execW, # May allocate after BeforeFork
   140    hchan,
   141    notifyList,
   142    reflectOffs,
   143    timer,
   144    traceStrings,
   145    typelinks,
   146    userArenaState,
   147    vgetrandom
   148  # Above MALLOC are things that can allocate memory.
   149  < MALLOC
   150  # Below MALLOC is the malloc implementation.
   151  < fin,
   152    spanSetSpine,
   153    mspanSpecial,
   154    traceTypeTab,
   155    MPROF;
   156  
   157  # Specials: we're allowed to allocate a special while holding
   158  # an mspanSpecial lock. Special record allocation can grow the stack,
   159  # so mheapSpecial must be above STACKGROW.
   160  mspanSpecial < mheapSpecial;
   161  
   162  # We can acquire gcBitsArenas for pinner bits, and
   163  # it's guarded by mspanSpecial.
   164  MALLOC, mspanSpecial < gcBitsArenas;
   165  
   166  # Memory profiling
   167  MPROF < profInsert, profBlock, profMemActive;
   168  profMemActive < profMemFuture;
   169  
   170  # Stack allocation and copying
   171  gcBitsArenas,
   172    mheapSpecial,
   173    netpollInit,
   174    profBlock,
   175    profInsert,
   176    profMemFuture,
   177    spanSetSpine,
   178    synctest,
   179    fin,
   180    root
   181  # Anything that can grow the stack can acquire STACKGROW.
   182  # (Most higher layers imply STACKGROW, like MALLOC.)
   183  < STACKGROW
   184  # Below STACKGROW is the stack allocator/copying implementation.
   185  < gscan;
   186  gscan < stackpool;
   187  gscan < stackLarge;
   188  # Generally, hchan must be acquired before gscan. But in one case,
   189  # where we suspend a G and then shrink its stack, syncadjustsudogs
   190  # can acquire hchan locks while holding gscan. To allow this case,
   191  # we use hchanLeaf instead of hchan.
   192  gscan < hchanLeaf;
   193  
   194  # Write barrier
   195  defer,
   196    gscan,
   197    mspanSpecial,
   198    pollCache,
   199    sudog,
   200    timer
   201  # Anything that can have write barriers can acquire WB.
   202  # Above WB, we can have write barriers.
   203  < WB
   204  # Below WB is the write barrier implementation.
   205  < wbufSpans;
   206  
   207  # xRegState allocator
   208  sched < xRegAlloc;
   209  
   210  # spanSPMCs allocator and list
   211  WB, sched < spanSPMCs;
   212  
   213  # Span allocator
   214  stackLarge,
   215    stackpool,
   216    wbufSpans
   217  # Above mheap is anything that can call the span allocator.
   218  < mheap;
   219  # Below mheap is the span allocator implementation.
   220  
   221  # Fixallocs
   222  mheap, mheapSpecial, xRegAlloc, spanSPMCs < globalAlloc;
   223  
   224  # Execution tracer events (with a P)
   225  hchan,
   226    mheap,
   227    root,
   228    sched,
   229    traceStrings,
   230    notifyList,
   231    fin
   232  # Above TRACE is anything that can create a trace event
   233  < TRACE
   234  < trace
   235  < traceStackTab;
   236  
   237  # panic is handled specially. It is implicitly below all other locks.
   238  NONE < panic;
   239  # deadlock is not acquired while holding panic, but it also needs to be
   240  # below all other locks.
   241  panic < deadlock;
   242  # raceFini is only held while exiting.
   243  panic < raceFini;
   244  
   245  # RWMutex internal read lock
   246  
   247  allocmR,
   248    allocmW
   249  < allocmRInternal;
   250  
   251  execR,
   252    execW
   253  < execRInternal;
   254  
   255  testR,
   256    testW
   257  < testRInternal;
   258  `
   259  
   260  // cyclicRanks lists lock ranks that allow multiple locks of the same
   261  // rank to be acquired simultaneously. The runtime enforces ordering
   262  // within these ranks using a separate mechanism.
   263  var cyclicRanks = map[string]bool{
   264  	// Multiple timers are locked simultaneously in destroy().
   265  	"timers": true,
   266  	// Multiple hchans are acquired in hchan.sortkey() order in
   267  	// select.
   268  	"hchan": true,
   269  	// Multiple hchanLeafs are acquired in hchan.sortkey() order in
   270  	// syncadjustsudogs().
   271  	"hchanLeaf": true,
   272  	// The point of the deadlock lock is to deadlock.
   273  	"deadlock": true,
   274  }
   275  
   276  func main() {
   277  	flagO := flag.String("o", "", "write to `file` instead of stdout")
   278  	flagDot := flag.Bool("dot", false, "emit graphviz output instead of Go")
   279  	flag.Parse()
   280  	if flag.NArg() != 0 {
   281  		fmt.Fprintf(os.Stderr, "too many arguments")
   282  		os.Exit(2)
   283  	}
   284  
   285  	g, err := dag.Parse(ranks)
   286  	if err != nil {
   287  		log.Fatal(err)
   288  	}
   289  
   290  	var out []byte
   291  	if *flagDot {
   292  		var b bytes.Buffer
   293  		g.TransitiveReduction()
   294  		// Add cyclic edges for visualization.
   295  		for k := range cyclicRanks {
   296  			g.AddEdge(k, k)
   297  		}
   298  		// Reverse the graph. It's much easier to read this as
   299  		// a "<" partial order than a ">" partial order. This
   300  		// ways, locks are acquired from the top going down
   301  		// and time moves forward over the edges instead of
   302  		// backward.
   303  		g.Transpose()
   304  		generateDot(&b, g)
   305  		out = b.Bytes()
   306  	} else {
   307  		var b bytes.Buffer
   308  		generateGo(&b, g)
   309  		out, err = format.Source(b.Bytes())
   310  		if err != nil {
   311  			log.Fatal(err)
   312  		}
   313  	}
   314  
   315  	if *flagO != "" {
   316  		err = os.WriteFile(*flagO, out, 0666)
   317  	} else {
   318  		_, err = os.Stdout.Write(out)
   319  	}
   320  	if err != nil {
   321  		log.Fatal(err)
   322  	}
   323  }
   324  
   325  func generateGo(w io.Writer, g *dag.Graph) {
   326  	fmt.Fprintf(w, `// Code generated by mklockrank.go; DO NOT EDIT.
   327  
   328  package runtime
   329  
   330  type lockRank int64
   331  
   332  `)
   333  
   334  	// Create numeric ranks.
   335  	topo := g.Topo()
   336  	for i, j := 0, len(topo)-1; i < j; i, j = i+1, j-1 {
   337  		topo[i], topo[j] = topo[j], topo[i]
   338  	}
   339  	fmt.Fprintf(w, `
   340  // Constants representing the ranks of all non-leaf runtime locks, in rank order.
   341  // Locks with lower rank must be taken before locks with higher rank,
   342  // in addition to satisfying the partial order in lockPartialOrder.
   343  // A few ranks allow self-cycles, which are specified in lockPartialOrder.
   344  const (
   345  	lockRankUnknown lockRank = iota
   346  
   347  `)
   348  	for _, rank := range topo {
   349  		if isPseudo(rank) {
   350  			fmt.Fprintf(w, "\t// %s\n", rank)
   351  		} else {
   352  			fmt.Fprintf(w, "\t%s\n", cname(rank))
   353  		}
   354  	}
   355  	fmt.Fprintf(w, `)
   356  
   357  // lockRankLeafRank is the rank of lock that does not have a declared rank,
   358  // and hence is a leaf lock.
   359  const lockRankLeafRank lockRank = 1000
   360  `)
   361  
   362  	// Create string table.
   363  	fmt.Fprintf(w, `
   364  // lockNames gives the names associated with each of the above ranks.
   365  var lockNames = []string{
   366  `)
   367  	for _, rank := range topo {
   368  		if !isPseudo(rank) {
   369  			fmt.Fprintf(w, "\t%s: %q,\n", cname(rank), rank)
   370  		}
   371  	}
   372  	fmt.Fprintf(w, `}
   373  
   374  func (rank lockRank) String() string {
   375  	if rank == 0 {
   376  		return "UNKNOWN"
   377  	}
   378  	if rank == lockRankLeafRank {
   379  		return "LEAF"
   380  	}
   381  	if rank < 0 || int(rank) >= len(lockNames) {
   382  		return "BAD RANK"
   383  	}
   384  	return lockNames[rank]
   385  }
   386  `)
   387  
   388  	// Create partial order structure.
   389  	fmt.Fprintf(w, `
   390  // lockPartialOrder is the transitive closure of the lock rank graph.
   391  // An entry for rank X lists all of the ranks that can already be held
   392  // when rank X is acquired.
   393  //
   394  // Lock ranks that allow self-cycles list themselves.
   395  var lockPartialOrder [][]lockRank = [][]lockRank{
   396  `)
   397  	for _, rank := range topo {
   398  		if isPseudo(rank) {
   399  			continue
   400  		}
   401  		list := []string{}
   402  		for _, before := range g.Edges(rank) {
   403  			if !isPseudo(before) {
   404  				list = append(list, cname(before))
   405  			}
   406  		}
   407  		if cyclicRanks[rank] {
   408  			list = append(list, cname(rank))
   409  		}
   410  
   411  		fmt.Fprintf(w, "\t%s: {%s},\n", cname(rank), strings.Join(list, ", "))
   412  	}
   413  	fmt.Fprintf(w, "}\n")
   414  }
   415  
   416  // cname returns the Go const name for the given lock rank label.
   417  func cname(label string) string {
   418  	return "lockRank" + strings.ToUpper(label[:1]) + label[1:]
   419  }
   420  
   421  func isPseudo(label string) bool {
   422  	return strings.ToUpper(label) == label
   423  }
   424  
   425  // generateDot emits a Graphviz dot representation of g to w.
   426  func generateDot(w io.Writer, g *dag.Graph) {
   427  	fmt.Fprintf(w, "digraph g {\n")
   428  
   429  	// Define all nodes.
   430  	for _, node := range g.Nodes {
   431  		fmt.Fprintf(w, "%q;\n", node)
   432  	}
   433  
   434  	// Create edges.
   435  	for _, node := range g.Nodes {
   436  		for _, to := range g.Edges(node) {
   437  			fmt.Fprintf(w, "%q -> %q;\n", node, to)
   438  		}
   439  	}
   440  
   441  	fmt.Fprintf(w, "}\n")
   442  }
   443
View as plain text