tree ab1de59d49b6af65c43341483f7696f19545848a
parent d522178b54087d2c3855484c1899ce99ad278169
author Todd Lipcon <tlipcon@google.com> 1791943593 -0700
committer Copybara-Service <copybara-worker@google.com> 1791943715 -0700

Space out GraphCycles ranks so that InsertEdge can often move just one node

In debug builds, absl::Mutex deadlock detection records each lock-order edge
with GraphCycles::InsertEdge(held, acquired), under a global lock. GraphCycles
keeps node ranks in topological order: rank(x) < rank(y) for each edge x->y.
When a new edge breaks this order, InsertEdge uses the Pearce-Kelly algorithm
to detect a cycle or repair the ranks.

Before this change, ranks were a dense permutation of [0, N), and each new slot
got the next rank, above all existing nodes. So when a newly created mutex x is
held while an older mutex y is acquired, which is common, the edge x->y often
breaks the order. Pearce-Kelly then visits every descendant of y that ranks
below x (nearly all of them, since x is new), and sorts and renumbers them,
just to put one node in order. With no unused ranks between nodes, even moving
one node means renumbering everything in between.

This change leaves unused ranks between nodes, so that InsertEdge can often fix
the order by moving just x or just y:

- Ranks are now int64_t, and new slots get ranks 2^32 above the highest rank.
  All slots, including free slots, are kept in a doubly linked list sorted by
  rank. As before, a free slot keeps its rank (and now its place in the list),
  which is reused with the slot.
- If rank(x) > rank(y), InsertEdge(x, y) first tries to move x below y, which
  requires all in-neighbors of x to rank below y. x moves to the midpoint
  between y and the slot just below y, or 2^32 below the lowest rank if x has
  no in-neighbors. If x cannot move, InsertEdge tries the symmetric move of y
  above x, which requires all out-neighbors of y to rank above x. If neither
  move works, Pearce-Kelly runs as before.
- Ranks stay unique by construction: each new rank is strictly between the
  ranks of two adjacent slots in the list, or beyond the lowest or highest
  rank, so no other slot can have it. As before, the Pearce-Kelly reorder
  reassigns the ranks of the reordered nodes among them. It now also gives each
  one the list place that goes with its new rank.
- A move never hides a cycle: the condition for moving x also proves that y
  cannot reach x, since every node reachable from y ranks at or above y, but
  every in-neighbor of x ranks below y. The same holds for moving y, so all
  cycle detection still happens in the Pearce-Kelly path.

Why not simply give new nodes decreasing initial ranks (below all existing
nodes)? That makes new -> old edges immediately ordered, but it inverts the
order for old -> new edges, such as when a long-lived container mutex locks a
newly created child mutex, or when a chain of mutexes is acquired in creation
order. Every old -> new edge then triggers a Pearce-Kelly traversal and dense
renumbering, making sequential chain construction (BM_StressTest) quadratic:
O(N) per edge (114 us/node at N=2048 and 2.9 ms/node at N=32768, vs. under 0.5
us/node). Spacing ranks out and moving either endpoint handles both directions
in O(degree) time.

Limits and trade-offs:

- InsertEdge does not try to move x if x has more than 16 in-neighbors to
  check, or y if y has more than 16 out-neighbors. If neither can move, it
  falls back to Pearce-Kelly. This bounds the cost of each attempt.
- The 2^32 spacing leaves room for about 32 consecutive moves into the gap
  between two adjacent new slots. When the two ranks around a gap are less than
  2 apart, Respace() first spreads out a run of slots around the gap, keeping
  their order. Starting with the two slots around the gap, the run doubles in
  size until its slots can be evenly spaced at least 2^16 apart between the
  ranks just outside it (-2^62 and 2^62 beyond the ends of the list).
- Ranks beyond the lowest and highest ones stay within [-2^62, 2^62], which
  leaves room for about 2^30 moves (or new slots) at each end. When that runs
  out, all slots are respaced evenly across [-2^61, 2^61] in O(N) time, which
  leaves room for 2^29 more at each end.
- Slot indices are still int32_t, and the ranks have room for 2^31 slots, so
  there is no new limit on node count.
- Node grows by 16 bytes, for the 64-bit rank and two 32-bit list links (with
  alignment). It was already over 400 bytes, since it holds a 40-entry stack
  trace.

New tests cover each kind of move, the fallbacks to Pearce-Kelly, and both
kinds of respacing. A new test-only method, TestOnlySetRankStride(), lets a
test make the ranks beyond the lowest and highest ones run out after a few
moves, to exercise the respacing of all slots.

PiperOrigin-RevId: 999040867
Change-Id: I3353404e681c094b3cbd4978f384c0415200b2ec