runtime: generate the lock ranking from a DAG description
Currently, the runtime lock rank graph is maintained manually in a
large set of arrays that give the partial order and a manual
topological sort of this partial order. Any changes to the rank graph
are difficult to reason about and hard to review, as well as likely to
cause merge conflicts. Furthermore, because the partial order is
manually maintained, it's not actually transitively closed (though
it's close), meaning there are many cases where rank a can be acquired
before b and b before c, but a cannot be acquired before c. While this
isn't technically wrong, it's very strange in the context of lock
ordering.
Replace all of this with a much more compact, readable, and
maintainable description of the rank graph written in the internal/dag
graph language. We statically generate the runtime structures from
this description, which has the advantage that the parser doesn't have
to run during runtime initialization and the structures can live in
static data where they can be accessed from any point during runtime
init.
The current description was automatically generated from the existing
partial order, combined with a transitive reduction. This ensures it's
correct, but it could use some manual messaging to call out the
logical layers and add some structure.
We do lose the ad hoc string names of the lock ranks in this
translation, which could mostly be derived from the rank constant
names, but not always. I may bring those back but in a more uniform
way.
We no longer need the tests in lockrank_test.go because they were
checking that we manually maintained the structures correctly.
Fixes #53789.
Change-Id: I54451d561b22e61150aff7e9b8602ba9737e1b9b
Reviewed-on: https://go-review.googlesource.com/c/go/+/418715
Run-TryBot: Austin Clements <austin@google.com>
Reviewed-by: Michael Pratt <mpratt@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>