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
diff --git a/absl/synchronization/internal/graphcycles.cc b/absl/synchronization/internal/graphcycles.cc index 25b51ff..7079081 100644 --- a/absl/synchronization/internal/graphcycles.cc +++ b/absl/synchronization/internal/graphcycles.cc
@@ -27,6 +27,9 @@ // implies rank[x] < rank[y]. // (2) When a new edge (x->y) is inserted, do nothing if rank[x] < rank[y]. // (3) Otherwise: adjust ranks in the neighborhood of x and y. +// +// Unlike in the paper, ranks are spaced apart, which often lets step (3) move +// just x or just y (see "Rank allocation" below). #include "absl/base/internal/low_level_alloc.h" // IWYU pragma: keep // This file is a no-op if the required LowLevelAlloc support is missing. @@ -282,7 +285,9 @@ } struct Node { - int32_t rank; // rank number assigned by Pearce-Kelly algorithm + int64_t rank; // Unique rank (see "Rank allocation") + int32_t prev_slot; // Slot with the next lower rank, or -1 if none + int32_t next_slot; // Slot with the next higher rank, or -1 if none uint32_t version; // Current version number int32_t next_hash; // Next entry in hash table bool visited; // Temporary marker used by depth-first-search @@ -348,17 +353,53 @@ } // namespace +// Rank allocation +// +// Ranks are unique int64_t values. All slots, including free slots, are kept in +// a doubly linked list sorted by rank (Node::prev_slot and Node::next_slot, +// from Rep::lowest_slot to Rep::highest_slot). Free slots keep their rank and +// their place in the list, which are reused along with the slot. New slots get +// ranks kRankStride above the highest rank. +// +// When a new edge x->y violates the rank order, InsertEdge first tries to move +// just x below y, or just y above x (see TryMoveXBelowY()): either to the +// midpoint between two ranks that are adjacent in the list, or kRankStride +// beyond the lowest or highest rank. No other slot can have such a rank, so +// ranks stay unique. +// +// kRankStride leaves room for about 32 moves, one after another, into the gap +// between two adjacent new slots. When a gap has no room left, Respace() first +// spreads out the ranks around it. Ranks beyond the lowest and highest ones +// stay within [kMinRank, kMaxRank], which leaves room for about 2^30 moves at +// each end before all slots are respaced. +static constexpr int64_t kRankStride = int64_t{1} << 32; +static constexpr int64_t kMinRank = -(int64_t{1} << 62); +static constexpr int64_t kMaxRank = int64_t{1} << 62; +// Respace() spreads out ranks until they can be at least this far apart. +static constexpr uint64_t kMinRespacedGap = uint64_t{1} << 16; +// Maximum number of in-neighbors of x (or out-neighbors of y) that +// TryMoveXBelowY() (or TryMoveYAboveX()) will examine. +static constexpr int kMaxSingleNodeDegree = 16; + struct GraphCycles::Rep { Vec<Node*> nodes_; Vec<int32_t> free_nodes_; // Indices for unused entries in nodes_ PointerMap ptrmap_; + int32_t lowest_slot = -1; // Slot with the lowest rank, or -1 if none + int32_t highest_slot = -1; // Slot with the highest rank, or -1 if none + int64_t rank_stride = kRankStride; // See TestOnlySetRankStride() // Temporary state. Vec<int32_t> deltaf_; // Results of forward DFS Vec<int32_t> deltab_; // Results of backward DFS Vec<int32_t> list_; // All nodes to reprocess - Vec<int32_t> merged_; // Rank values to assign to list_ entries Vec<int32_t> stack_; // Emulates recursion stack for depth-first searches + // Used by Reorder(): the slots to reorder, sorted by their current ranks, and + // the rank, prev_slot and next_slot of each. + Vec<int32_t> sorted_slots; + Vec<int64_t> sorted_ranks; + Vec<int32_t> old_prev_slots; + Vec<int32_t> old_next_slots; Rep() : ptrmap_(&nodes_) {} }; @@ -368,6 +409,119 @@ return (n->version == NodeVersion(id)) ? n : nullptr; } +static Node* NodeAt(GraphCycles::Rep* r, int32_t slot) { + return r->nodes_[static_cast<uint32_t>(slot)]; +} + +// Makes next_slot follow prev_slot in the rank list. prev_slot == -1 makes +// next_slot the lowest slot, and next_slot == -1 makes prev_slot the highest. +static void Link(GraphCycles::Rep* r, int32_t prev_slot, int32_t next_slot) { + if (prev_slot == -1) { + r->lowest_slot = next_slot; + } else { + NodeAt(r, prev_slot)->next_slot = next_slot; + } + if (next_slot == -1) { + r->highest_slot = prev_slot; + } else { + NodeAt(r, next_slot)->prev_slot = prev_slot; + } +} + +// Removes slot from the rank list. +static void Unlink(GraphCycles::Rep* r, int32_t slot) { + Link(r, NodeAt(r, slot)->prev_slot, NodeAt(r, slot)->next_slot); +} + +// Returns upper - lower, for lower <= upper, without overflow. +static uint64_t RankDistance(int64_t lower, int64_t upper) { + return static_cast<uint64_t>(upper) - static_cast<uint64_t>(lower); +} + +// Gives the run of adjacent slots from first_slot to last_slot in the rank list +// evenly spaced ranks, keeping their order. First grows the run on both sides +// until its slots can be at least kMinRespacedGap apart between the ranks just +// outside it (kMinRank and kMaxRank beyond the ends of the list), or until it +// covers the whole list. The whole list is spaced across +// [kMinRank / 2, kMaxRank / 2], which leaves room beyond both of its ends. +static void Respace(GraphCycles::Rep* r, int32_t first_slot, + int32_t last_slot) { + uint64_t count = 1; + for (int32_t slot = first_slot; slot != last_slot; + slot = NodeAt(r, slot)->next_slot) { + count++; + } + int64_t lower; + int64_t upper; + while (true) { + const int32_t before_slot = NodeAt(r, first_slot)->prev_slot; + const int32_t after_slot = NodeAt(r, last_slot)->next_slot; + if (before_slot == -1 && after_slot == -1) { + lower = kMinRank / 2; + upper = kMaxRank / 2; + break; + } + lower = before_slot == -1 ? kMinRank : NodeAt(r, before_slot)->rank; + upper = after_slot == -1 ? kMaxRank : NodeAt(r, after_slot)->rank; + if (RankDistance(lower, upper) / (count + 1) >= kMinRespacedGap) break; + // Double the size of the run, as far as the ends of the list allow. + for (const uint64_t target = 2 * count; count < target;) { + const int32_t prev_slot = NodeAt(r, first_slot)->prev_slot; + const int32_t next_slot = NodeAt(r, last_slot)->next_slot; + if (prev_slot == -1 && next_slot == -1) break; + if (prev_slot != -1) { + first_slot = prev_slot; + count++; + } + if (next_slot != -1) { + last_slot = next_slot; + count++; + } + } + } + const uint64_t step = RankDistance(lower, upper) / (count + 1); + int64_t rank = lower; + for (int32_t slot = first_slot;; slot = NodeAt(r, slot)->next_slot) { + rank += static_cast<int64_t>(step); + NodeAt(r, slot)->rank = rank; + if (slot == last_slot) return; + } +} + +// Links slot, which is not in the rank list, between prev_slot and next_slot, +// which are adjacent in it (-1 beyond its ends), with a rank between theirs: +// rank_stride (kRankStride by default) beyond prev_slot or next_slot at the +// ends of the list, and halfway between them otherwise. If there is no room +// for such a rank, respaces ranks first. +static void LinkBetween(GraphCycles::Rep* r, int32_t slot, int32_t prev_slot, + int32_t next_slot) { + int64_t rank; + if (prev_slot == -1 && next_slot == -1) { + rank = 0; + } else if (prev_slot == -1) { + if (NodeAt(r, next_slot)->rank < kMinRank + r->rank_stride) { + Respace(r, r->lowest_slot, r->highest_slot); + } + rank = NodeAt(r, next_slot)->rank - r->rank_stride; + } else if (next_slot == -1) { + if (NodeAt(r, prev_slot)->rank > kMaxRank - r->rank_stride) { + Respace(r, r->lowest_slot, r->highest_slot); + } + rank = NodeAt(r, prev_slot)->rank + r->rank_stride; + } else { + const Node* prev_node = NodeAt(r, prev_slot); + const Node* next_node = NodeAt(r, next_slot); + if (RankDistance(prev_node->rank, next_node->rank) < 2) { + Respace(r, prev_slot, next_slot); + } + const uint64_t gap = RankDistance(prev_node->rank, next_node->rank); + rank = prev_node->rank + static_cast<int64_t>(gap / 2); + } + NodeAt(r, slot)->rank = rank; + Link(r, prev_slot, slot); + Link(r, slot, next_slot); +} + void GraphCycles::TestOnlyAddNodes(uint32_t n) { uint32_t old_size = rep_->nodes_.size(); rep_->nodes_.resize(n); @@ -376,6 +530,13 @@ } } +void GraphCycles::TestOnlySetRankStride(int64_t stride) { + // After Respace() of the whole list, there is room for a stride of 2^61 + // beyond each end. + ABSL_RAW_CHECK(stride >= 1 && stride <= kMaxRank / 2, "Bad rank stride"); + rep_->rank_stride = stride; +} + GraphCycles::GraphCycles() { InitArenaIfNecessary(); rep_ = new (base_internal::LowLevelAlloc::AllocWithArena(sizeof(Rep), arena)) @@ -396,7 +557,6 @@ bool GraphCycles::CheckInvariants() const { Rep* r = rep_; - NodeSet ranks; // Set of ranks seen so far. for (uint32_t x = 0; x < r->nodes_.size(); x++) { Node* nx = r->nodes_[x]; void* ptr = base_internal::UnhidePtr<void>(nx->masked_ptr); @@ -407,19 +567,44 @@ if (nx->visited) { ABSL_RAW_LOG(FATAL, "Did not clear visited marker on node %" PRIu32, x); } - if (!ranks.insert(nx->rank)) { - ABSL_RAW_LOG(FATAL, "Duplicate occurrence of rank %" PRId32, nx->rank); - } HASH_FOR_EACH(y, nx->out) { Node* ny = r->nodes_[static_cast<uint32_t>(y)]; if (nx->rank >= ny->rank) { ABSL_RAW_LOG(FATAL, "Edge %" PRIu32 " ->%" PRId32 - " has bad rank assignment %" PRId32 "->%" PRId32, + " has bad rank assignment %" PRId64 "->%" PRId64, x, y, nx->rank, ny->rank); } } } + // The rank list holds each slot once, in increasing rank order, so ranks are + // unique. + const uint32_t num_slots = r->nodes_.size(); + uint32_t num_listed = 0; + int32_t prev_slot = -1; + for (int32_t slot = r->lowest_slot; slot != -1; + slot = NodeAt(r, slot)->next_slot) { + if (NodeAt(r, slot)->prev_slot != prev_slot) { + ABSL_RAW_LOG(FATAL, + "Slot %" PRId32 " has prev_slot %" PRId32 + " instead of %" PRId32, + slot, NodeAt(r, slot)->prev_slot, prev_slot); + } + if (prev_slot != -1 && + NodeAt(r, prev_slot)->rank >= NodeAt(r, slot)->rank) { + ABSL_RAW_LOG( + FATAL, "Rank of slot %" PRId32 " is not above rank of slot %" PRId32, + slot, prev_slot); + } + if (++num_listed > num_slots) { + ABSL_RAW_LOG(FATAL, "Rank list has more entries than there are slots"); + } + prev_slot = slot; + } + if (prev_slot != r->highest_slot || num_listed != num_slots) { + ABSL_RAW_LOG(FATAL, "Rank list has %" PRIu32 " of %" PRIu32 " slots", + num_listed, num_slots); + } return true; } @@ -428,29 +613,29 @@ if (i != -1) { return MakeId(i, rep_->nodes_[static_cast<uint32_t>(i)]->version); } else if (rep_->free_nodes_.empty()) { + const int32_t slot = static_cast<int32_t>(rep_->nodes_.size()); Node* n = new (base_internal::LowLevelAlloc::AllocWithArena(sizeof(Node), arena)) Node; n->version = 1; // Avoid 0 since it is used by InvalidGraphId() n->visited = false; - n->rank = static_cast<int32_t>(rep_->nodes_.size()); n->masked_ptr = base_internal::HidePtr(ptr); n->nstack = 0; n->priority = 0; rep_->nodes_.push_back(n); - rep_->ptrmap_.Add(ptr, n->rank); - return MakeId(n->rank, n->version); + LinkBetween(rep_, slot, rep_->highest_slot, /*next_slot=*/-1); + rep_->ptrmap_.Add(ptr, slot); + return MakeId(slot, n->version); } else { - // Preserve preceding rank since the set of ranks in use must be - // a permutation of [0,rep_->nodes_.size()-1]. - int32_t r = rep_->free_nodes_.back(); + // The slot keeps its rank (see "Rank allocation"). + int32_t slot = rep_->free_nodes_.back(); rep_->free_nodes_.pop_back(); - Node* n = rep_->nodes_[static_cast<uint32_t>(r)]; + Node* n = rep_->nodes_[static_cast<uint32_t>(slot)]; n->masked_ptr = base_internal::HidePtr(ptr); n->nstack = 0; n->priority = 0; - rep_->ptrmap_.Add(ptr, r); - return MakeId(r, n->version); + rep_->ptrmap_.Add(ptr, slot); + return MakeId(slot, n->version); } } @@ -502,13 +687,65 @@ } } -static bool ForwardDFS(GraphCycles::Rep* r, int32_t n, int32_t upper_bound); -static void BackwardDFS(GraphCycles::Rep* r, int32_t n, int32_t lower_bound); +static bool ForwardDFS(GraphCycles::Rep* r, int32_t n, int64_t upper_bound); +static void BackwardDFS(GraphCycles::Rep* r, int32_t n, int64_t lower_bound); static void Reorder(GraphCycles::Rep* r); static void Sort(const Vec<Node*>&, Vec<int32_t>* delta); static void MoveToList(GraphCycles::Rep* r, Vec<int32_t>* src, Vec<int32_t>* dst); +// TryMoveXBelowY() and TryMoveYAboveX() are called by InsertEdge(x, y) when +// rank(x) > rank(y). They try to restore the rank order by moving only x below +// y, or only y above x, which is much cheaper than the Pearce-Kelly search and +// reorder. +// +// x can move below y if all of x's in-neighbors rank below y. This also shows +// that the new edge does not close a cycle: every node reachable from y ranks +// at or above y, so a path from y to x would have to enter x from such a node. +// Similarly, y can move above x if all of y's out-neighbors rank above x. +// +// Each returns false, changing nothing, if the move is not possible or if +// there are more than kMaxSingleNodeDegree neighbors to check. +static bool TryMoveXBelowY(GraphCycles::Rep* r, int32_t x, int32_t y) { + Node* nx = NodeAt(r, x); + Node* ny = NodeAt(r, y); + int degree = 0; + HASH_FOR_EACH(u, nx->in) { + if (++degree > kMaxSingleNodeDegree) return false; + if (NodeAt(r, u)->rank >= ny->rank) return false; + } + Unlink(r, x); + if (degree == 0) { + // Move x below all other nodes. + LinkBetween(r, x, /*prev_slot=*/-1, r->lowest_slot); + } else { + // Move x right below y. Its in-neighbors rank below y, so they rank no + // higher than the node right below y. + LinkBetween(r, x, ny->prev_slot, y); + } + return true; +} + +static bool TryMoveYAboveX(GraphCycles::Rep* r, int32_t x, int32_t y) { + Node* nx = NodeAt(r, x); + Node* ny = NodeAt(r, y); + int degree = 0; + HASH_FOR_EACH(w, ny->out) { + if (++degree > kMaxSingleNodeDegree) return false; + if (NodeAt(r, w)->rank <= nx->rank) return false; + } + Unlink(r, y); + if (degree == 0) { + // Move y above all other nodes. + LinkBetween(r, y, r->highest_slot, /*next_slot=*/-1); + } else { + // Move y right above x. Its out-neighbors rank above x, so they rank no + // lower than the node right above x. + LinkBetween(r, y, x, nx->next_slot); + } + return true; +} + bool GraphCycles::InsertEdge(GraphId idx, GraphId idy) { Rep* r = rep_; const int32_t x = NodeIndex(idx); @@ -530,6 +767,9 @@ return true; } + // Try moving just x or just y. + if (TryMoveXBelowY(r, x, y) || TryMoveYAboveX(r, x, y)) return true; + // Current rank assignments are incompatible with the new edge. Recompute. // We only need to consider nodes that fall in the range [ny->rank,nx->rank]. if (!ForwardDFS(r, y, nx->rank)) { @@ -548,7 +788,7 @@ return true; } -static bool ForwardDFS(GraphCycles::Rep* r, int32_t n, int32_t upper_bound) { +static bool ForwardDFS(GraphCycles::Rep* r, int32_t n, int64_t upper_bound) { // Avoid recursion since stack space might be limited. // We instead keep a stack of nodes to visit. r->deltaf_.clear(); @@ -576,7 +816,7 @@ return true; } -static void BackwardDFS(GraphCycles::Rep* r, int32_t n, int32_t lower_bound) { +static void BackwardDFS(GraphCycles::Rep* r, int32_t n, int64_t lower_bound) { r->deltab_.clear(); r->stack_.clear(); r->stack_.push_back(n); @@ -602,19 +842,48 @@ Sort(r->nodes_, &r->deltab_); Sort(r->nodes_, &r->deltaf_); + // The slots to reorder, sorted by their current ranks. In their new order + // (list_), they take over the same ranks and places in the rank list. + const uint32_t count = r->deltab_.size() + r->deltaf_.size(); + r->sorted_slots.resize(count); + std::merge(r->deltab_.begin(), r->deltab_.end(), r->deltaf_.begin(), + r->deltaf_.end(), r->sorted_slots.begin(), + [r](int32_t a, int32_t b) { + return NodeAt(r, a)->rank < NodeAt(r, b)->rank; + }); + // Adds contents of delta lists to list_ (backwards deltas first). r->list_.clear(); MoveToList(r, &r->deltab_, &r->list_); MoveToList(r, &r->deltaf_, &r->list_); - // Produce sorted list of all ranks that will be reassigned. - r->merged_.resize(r->deltab_.size() + r->deltaf_.size()); - std::merge(r->deltab_.begin(), r->deltab_.end(), r->deltaf_.begin(), - r->deltaf_.end(), r->merged_.begin()); + // Record the rank, prev_slot and next_slot of each place before changing + // them. + r->sorted_ranks.resize(count); + r->old_prev_slots.resize(count); + r->old_next_slots.resize(count); + for (uint32_t i = 0; i < count; i++) { + const Node* p = NodeAt(r, r->sorted_slots[i]); + r->sorted_ranks[i] = p->rank; + r->old_prev_slots[i] = p->prev_slot; + r->old_next_slots[i] = p->next_slot; + } - // Assign the ranks in order to the collected list. - for (uint32_t i = 0; i < r->list_.size(); i++) { - r->nodes_[static_cast<uint32_t>(r->list_[i])]->rank = r->merged_[i]; + // Assign the ranks and places in order to the collected list. A prev_slot + // (or next_slot) that is also being reordered must be the previous (or next) + // place in sorted_slots, so link to the slot that now takes that place + // instead. + for (uint32_t i = 0; i < count; i++) { + const int32_t slot = r->list_[i]; + NodeAt(r, slot)->rank = r->sorted_ranks[i]; + if (i > 0 && r->old_prev_slots[i] == r->sorted_slots[i - 1]) { + Link(r, r->list_[i - 1], slot); + } else { + Link(r, r->old_prev_slots[i], slot); + } + if (i + 1 == count || r->old_next_slots[i] != r->sorted_slots[i + 1]) { + Link(r, slot, r->old_next_slots[i]); + } } } @@ -633,10 +902,7 @@ static void MoveToList(GraphCycles::Rep* r, Vec<int32_t>* src, Vec<int32_t>* dst) { - for (auto& v : *src) { - int32_t w = v; - // Replace v entry with its rank - v = r->nodes_[static_cast<uint32_t>(w)]->rank; + for (int32_t w : *src) { // Prepare for future DFS calls r->nodes_[static_cast<uint32_t>(w)]->visited = false; dst->push_back(w);
diff --git a/absl/synchronization/internal/graphcycles.h b/absl/synchronization/internal/graphcycles.h index da06504..27eaa6c 100644 --- a/absl/synchronization/internal/graphcycles.h +++ b/absl/synchronization/internal/graphcycles.h
@@ -131,6 +131,12 @@ // very full. void TestOnlyAddNodes(uint32_t n); + // Test-only method to set how far apart the ranks of new nodes are, and how + // far below (above) all other nodes a node is moved. The default is 2^32. A + // stride of up to 2^61 makes the ranks beyond the lowest and highest ones run + // out after a few new nodes or moves. + void TestOnlySetRankStride(int64_t stride); + // ---------------------------------------------------- struct Rep; private:
diff --git a/absl/synchronization/internal/graphcycles_benchmark.cc b/absl/synchronization/internal/graphcycles_benchmark.cc index 9012801..9d11c38 100644 --- a/absl/synchronization/internal/graphcycles_benchmark.cc +++ b/absl/synchronization/internal/graphcycles_benchmark.cc
@@ -40,4 +40,65 @@ } BENCHMARK(BM_StressTest)->Range(2048, 1048576); +using absl::synchronization_internal::GraphCycles; +using absl::synchronization_internal::GraphId; + +// Returns a node for a new pointer value, next_ptr, and increments next_ptr. +GraphId NewNode(GraphCycles& g, uintptr_t& next_ptr) { + return g.GetId(reinterpret_cast<void*>(next_ptr++)); +} + +// Adds a chain of n new nodes after node. +void AddChain(GraphCycles& g, GraphId node, int n, uintptr_t& next_ptr) { + for (int i = 0; i < n; i++) { + const GraphId next = NewNode(g, next_ptr); + ABSL_RAW_CHECK(g.InsertEdge(node, next), ""); + node = next; + } +} + +// Inserts edges from new nodes to an old node that has a chain of +// state.range(0) descendants. New nodes rank above old ones, so each edge +// violates the rank order. Deadlock detection sees this pattern whenever a +// newly created Mutex is held while an older one is acquired. +void BM_NewNodeToOldNode(benchmark::State& state) { + const int num_descendants = static_cast<int>(state.range(0)); + constexpr int kNewNodes = 10000; + while (state.KeepRunningBatch(kNewNodes)) { + GraphCycles g; + uintptr_t next_ptr = 1; + const GraphId old_node = NewNode(g, next_ptr); + AddChain(g, old_node, num_descendants, next_ptr); + for (int i = 0; i < kNewNodes; i++) { + const GraphId new_node = NewNode(g, next_ptr); + ABSL_RAW_CHECK(g.InsertEdge(new_node, old_node), ""); + } + } +} +BENCHMARK(BM_NewNodeToOldNode)->Arg(256); + +// Inserts edges u -> new node -> y, where u -> y are old nodes and y has a +// chain of state.range(0) descendants. Each new node must move between u and y, +// so these moves all go into the same gap. Deadlock detection sees this +// pattern when newly created Mutexes are each acquired while one Mutex is held, +// and then held while another one is acquired. +void BM_NewNodesBetweenOldNodes(benchmark::State& state) { + const int num_descendants = static_cast<int>(state.range(0)); + constexpr int kNewNodes = 10000; + while (state.KeepRunningBatch(kNewNodes)) { + GraphCycles g; + uintptr_t next_ptr = 1; + const GraphId u = NewNode(g, next_ptr); + const GraphId y = NewNode(g, next_ptr); + ABSL_RAW_CHECK(g.InsertEdge(u, y), ""); + AddChain(g, y, num_descendants, next_ptr); + for (int i = 0; i < kNewNodes; i++) { + const GraphId new_node = NewNode(g, next_ptr); + ABSL_RAW_CHECK(g.InsertEdge(u, new_node), ""); + ABSL_RAW_CHECK(g.InsertEdge(new_node, y), ""); + } + } +} +BENCHMARK(BM_NewNodesBetweenOldNodes)->Arg(256); + } // namespace
diff --git a/absl/synchronization/internal/graphcycles_test.cc b/absl/synchronization/internal/graphcycles_test.cc index d4ba0f6..b1a6daf 100644 --- a/absl/synchronization/internal/graphcycles_test.cc +++ b/absl/synchronization/internal/graphcycles_test.cc
@@ -483,6 +483,167 @@ graph_cycles.RemoveNode(reinterpret_cast<void*>(buf)); } +// Returns ids for n new nodes. A new GraphCycles ranks nodes in creation order, +// so InsertEdge(ids[i], ids[j]) with i > j violates the rank order and makes +// InsertEdge reorder nodes. +static std::vector<GraphId> NewNodes(GraphCycles* g, size_t n) { + std::vector<GraphId> ids(n); + for (size_t i = 0; i < n; ++i) { + ids[i] = g->GetId(reinterpret_cast<void*>(static_cast<uintptr_t>(i + 1))); + } + return ids; +} + +// Each group of edges below violates the rank order in a different way. The +// comments say how InsertEdge is expected to restore the order. +TEST(GraphCycles, RankOrderRepairs) { + GraphCycles g; + std::vector<GraphId> n = NewNodes(&g, 16); + + // x has no in-neighbors: move x below all nodes. + ASSERT_TRUE(g.InsertEdge(n[1], n[0])); + + // x's in-neighbors rank below y: move x into the gap below y. + ASSERT_TRUE(g.InsertEdge(n[2], n[4])); + ASSERT_TRUE(g.InsertEdge(n[4], n[3])); + + // y has no out-neighbors: move y above all nodes. + ASSERT_TRUE(g.InsertEdge(n[6], n[7])); + ASSERT_TRUE(g.InsertEdge(n[7], n[5])); + + // y's out-neighbors rank above x: move y into the gap above x. + ASSERT_TRUE(g.InsertEdge(n[8], n[11])); + ASSERT_TRUE(g.InsertEdge(n[9], n[10])); + ASSERT_TRUE(g.InsertEdge(n[10], n[8])); + + // Neither x nor y can move alone: Pearce-Kelly reorder. + ASSERT_TRUE(g.InsertEdge(n[12], n[13])); + ASSERT_TRUE(g.InsertEdge(n[14], n[15])); + ASSERT_TRUE(g.InsertEdge(n[15], n[12])); + CheckInvariants(g); + + // Edges that would close a cycle are still rejected. + EXPECT_FALSE(g.InsertEdge(n[0], n[1])); + EXPECT_FALSE(g.InsertEdge(n[3], n[2])); + EXPECT_FALSE(g.InsertEdge(n[5], n[6])); + EXPECT_FALSE(g.InsertEdge(n[8], n[9])); + EXPECT_FALSE(g.InsertEdge(n[13], n[14])); + CheckInvariants(g); +} + +// InsertEdge(x, y) does not move x if x has too many in-neighbors to check, +// even if moving it would restore the rank order. Here y cannot move either, so +// InsertEdge falls back to the Pearce-Kelly reorder. +TEST(GraphCycles, TooManyNeighborsToMove) { + GraphCycles g; + std::vector<GraphId> n = NewNodes(&g, 41); + + // x is 40, which has 17 in-neighbors. y is 30, which cannot move above x + // because of its out-neighbor 31. + for (size_t i = 0; i <= 16; ++i) { + ASSERT_TRUE(g.InsertEdge(n[i], n[40])); + } + ASSERT_TRUE(g.InsertEdge(n[30], n[31])); + ASSERT_TRUE(g.InsertEdge(n[40], n[30])); + CheckInvariants(g); + + EXPECT_FALSE(g.InsertEdge(n[30], n[0])); + CheckInvariants(g); +} + +// Each move of a node right below the same node halves the gap below it. Check +// that InsertEdge keeps working when that gap runs out and the ranks around it +// are respaced. +TEST(GraphCycles, RespacesCrowdedGapBelow) { + GraphCycles g; + std::vector<GraphId> n = NewNodes(&g, 2000); + + // Each n[i] has in-neighbor 50, which ranks below 51, so each n[i] -> n[51] + // edge below moves n[i] right below 51. + for (size_t i = 100; i < 2000; ++i) { + ASSERT_TRUE(g.InsertEdge(n[50], n[i])); + ASSERT_TRUE(g.InsertEdge(n[i], n[51])); + if (i % 100 == 0) CheckInvariants(g); + } + CheckInvariants(g); + + EXPECT_FALSE(g.InsertEdge(n[51], n[50])); + EXPECT_FALSE(g.InsertEdge(n[51], n[100])); + EXPECT_FALSE(g.InsertEdge(n[1999], n[50])); + CheckInvariants(g); +} + +// Same, for moves of a node right above the same node. +TEST(GraphCycles, RespacesCrowdedGapAbove) { + GraphCycles g; + constexpr size_t kNumMoved = 1000; + std::vector<GraphId> n = NewNodes(&g, 2 * kNumMoved + 18); + + // x ranks above each n[i], i < kNumMoved, and has too many in-neighbors to + // move. n[i] has an out-neighbor that ranks above x, so each x -> n[i] edge + // below moves n[i] right above x. + const GraphId x = n[kNumMoved + 17]; + for (size_t j = 0; j <= 16; ++j) { + ASSERT_TRUE(g.InsertEdge(n[kNumMoved + j], x)); + } + for (size_t i = 0; i < kNumMoved; ++i) { + ASSERT_TRUE(g.InsertEdge(n[i], n[kNumMoved + 18 + i])); + ASSERT_TRUE(g.InsertEdge(x, n[i])); + if (i % 100 == 0) CheckInvariants(g); + } + CheckInvariants(g); + + EXPECT_FALSE(g.InsertEdge(n[0], x)); + EXPECT_FALSE(g.InsertEdge(n[kNumMoved + 18], x)); + EXPECT_FALSE(g.InsertEdge(n[kNumMoved - 1], n[kNumMoved])); + CheckInvariants(g); +} + +// With a rank stride this large, the ranks beyond the lowest and highest ones +// run out after a few new nodes, or a few moves of a node below or above all +// other nodes, and then all ranks are respaced. Check that the rank order stays +// valid. +TEST(GraphCycles, RanksRunOut) { + GraphCycles g; + g.TestOnlySetRankStride(int64_t{1} << 60); + std::vector<GraphId> n = NewNodes(&g, 50); + for (size_t i = 0; i < 9; ++i) { + ASSERT_TRUE(g.InsertEdge(n[i], n[i + 1])); + } + CheckInvariants(g); + const GraphId a = n[10]; + const GraphId b = n[11]; + + // a and b have no in-neighbors, so each InsertEdge call below moves one of + // them below all other nodes. + for (int i = 0; i < 1000; ++i) { + ASSERT_TRUE(g.InsertEdge(b, a)); + g.RemoveEdge(b, a); + ASSERT_TRUE(g.InsertEdge(a, b)); + g.RemoveEdge(a, b); + } + CheckInvariants(g); + + // Now a and b have too many in-neighbors to move, so each InsertEdge call + // below moves the other one above all other nodes. + for (size_t i = 12; i < 50; ++i) { + ASSERT_TRUE(g.InsertEdge(n[i], i % 2 == 0 ? a : b)); + } + for (int i = 0; i < 1000; ++i) { + ASSERT_TRUE(g.InsertEdge(b, a)); + g.RemoveEdge(b, a); + ASSERT_TRUE(g.InsertEdge(a, b)); + g.RemoveEdge(a, b); + } + CheckInvariants(g); + + EXPECT_TRUE(g.IsReachable(n[0], n[9])); + EXPECT_FALSE(g.InsertEdge(n[9], n[0])); + ASSERT_TRUE(g.InsertEdge(n[9], a)); + EXPECT_FALSE(g.InsertEdge(a, n[0])); + CheckInvariants(g); +} + } // namespace synchronization_internal ABSL_NAMESPACE_END } // namespace absl