Count graph nodes per address bucket so ForgetDeadlockInfo() can skip deadlock_graph_mu. In debug builds with deadlock detection enabled, ~Mutex() calls ForgetDeadlockInfo(), which takes the global deadlock_graph_mu spinlock to remove the Mutex's node from deadlock_graph. Only Mutexes involved in nested locking get a node, so for most destroyed Mutexes there is nothing to remove. Keep a count of deadlock_graph nodes for each hash bucket of Mutex addresses. ForgetDeadlockInfo() reads the count for the Mutex's bucket without the lock, and returns early if it is zero: - Counts change only under deadlock_graph_mu, when GetGraphIdLocked() creates a node and when ForgetDeadlockInfo() removes one. GraphCycles::GetId() can now report whether it created a node, and RemoveNode() returns whether the node existed. - If the Mutex has a node, the DeadlockCheck() call that created it either happens-before ForgetDeadlockInfo() or races with it. In the first case, ForgetDeadlockInfo() sees a nonzero count. In the second case, DeadlockCheck() could also create the node just after the removal, so the early return adds no new race. - Counts saturate at 255 and then never change, so a saturated bucket is never treated as empty again. Counts below 255 are exact. There are 2^18 buckets, with 8-bit counts packed four per 32-bit atomic word. 8-bit counts give 4x as many buckets as 32-bit counts in the same memory, so a larger fraction of buckets is empty. Packing keeps the array constant-initialized: an array of 2^18 one-byte atomics exceeds the compiler's constexpr evaluation step limit for ABSL_CONST_INIT. Cost: a 256 KiB zero-initialized static array, touched only in debug builds with deadlock detection enabled. PiperOrigin-RevId: 997581888
diff --git a/absl/synchronization/internal/graphcycles.cc b/absl/synchronization/internal/graphcycles.cc index 7079081..7b81bc2 100644 --- a/absl/synchronization/internal/graphcycles.cc +++ b/absl/synchronization/internal/graphcycles.cc
@@ -608,9 +608,10 @@ return true; } -GraphId GraphCycles::GetId(void* ptr) { +GraphId GraphCycles::GetId(void* ptr, bool* is_new) { int32_t i = rep_->ptrmap_.Find(ptr); if (i != -1) { + if (is_new != nullptr) *is_new = false; 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()); @@ -625,6 +626,7 @@ rep_->nodes_.push_back(n); LinkBetween(rep_, slot, rep_->highest_slot, /*next_slot=*/-1); rep_->ptrmap_.Add(ptr, slot); + if (is_new != nullptr) *is_new = true; return MakeId(slot, n->version); } else { // The slot keeps its rank (see "Rank allocation"). @@ -635,14 +637,15 @@ n->nstack = 0; n->priority = 0; rep_->ptrmap_.Add(ptr, slot); + if (is_new != nullptr) *is_new = true; return MakeId(slot, n->version); } } -void GraphCycles::RemoveNode(void* ptr) { +bool GraphCycles::RemoveNode(void* ptr) { int32_t i = rep_->ptrmap_.Remove(ptr); if (i == -1) { - return; + return false; } Node* x = rep_->nodes_[static_cast<uint32_t>(i)]; HASH_FOR_EACH(y, x->out) { @@ -660,6 +663,7 @@ x->version++; // Invalidates all copies of node. rep_->free_nodes_.push_back(i); } + return true; } void* GraphCycles::Ptr(GraphId id) {
diff --git a/absl/synchronization/internal/graphcycles.h b/absl/synchronization/internal/graphcycles.h index 27eaa6c..9202f18 100644 --- a/absl/synchronization/internal/graphcycles.h +++ b/absl/synchronization/internal/graphcycles.h
@@ -66,12 +66,13 @@ // Return the id to use for ptr, assigning one if necessary. // Subsequent calls with the same ptr value will return the same id - // until Remove(). - GraphId GetId(void* ptr); + // until Remove(). If is_new is non-null, *is_new is set to whether a new id + // was assigned. + GraphId GetId(void* ptr, bool* is_new = nullptr); - // Remove "ptr" from the graph. Its corresponding node and all - // edges to and from it are removed. - void RemoveNode(void* ptr); + // Remove "ptr" from the graph, if present. Its corresponding node and all + // edges to and from it are removed. Returns whether a node was removed. + bool RemoveNode(void* ptr); // Return the pointer associated with id, or nullptr if id is not // currently in the graph.
diff --git a/absl/synchronization/internal/graphcycles_test.cc b/absl/synchronization/internal/graphcycles_test.cc index b1a6daf..03c9bf0 100644 --- a/absl/synchronization/internal/graphcycles_test.cc +++ b/absl/synchronization/internal/graphcycles_test.cc
@@ -644,6 +644,24 @@ CheckInvariants(g); } +TEST(GraphCycles, GetIdIsNewAndRemoveNodeResult) { + GraphCycles g; + int a = 0; + bool is_new = false; + EXPECT_FALSE(g.RemoveNode(&a)); + + const GraphId id1 = g.GetId(&a, &is_new); + EXPECT_TRUE(is_new); + EXPECT_EQ(g.GetId(&a, &is_new), id1); + EXPECT_FALSE(is_new); + + EXPECT_TRUE(g.RemoveNode(&a)); + EXPECT_FALSE(g.RemoveNode(&a)); + + EXPECT_NE(g.GetId(&a, &is_new), id1); + EXPECT_TRUE(is_new); +} + } // namespace synchronization_internal ABSL_NAMESPACE_END } // namespace absl
diff --git a/absl/synchronization/mutex.cc b/absl/synchronization/mutex.cc index d5c1a3c..7efdb58 100644 --- a/absl/synchronization/mutex.cc +++ b/absl/synchronization/mutex.cc
@@ -1250,6 +1250,45 @@ return next; } +// Counts of deadlock_graph nodes per hash bucket of Mutex addresses, so that +// ForgetDeadlockInfo() can skip deadlock_graph_mu when the bucket of a Mutex +// is empty. Most Mutexes never get a node, since they are never held while +// another lock is acquired. Each word holds four 8-bit counts, which are +// modified only under deadlock_graph_mu but read without it. A count that +// reaches 255 stays there, so its bucket is never treated as empty again. +constexpr int kDeadlockNodeBucketBits = 18; +ABSL_CONST_INIT static std::atomic<uint32_t> + deadlock_node_bucket_counts[(size_t{1} << kDeadlockNodeBucketBits) / 4]; + +namespace { +struct DeadlockNodeBucket { + std::atomic<uint32_t>* word; + int shift; // Bit offset of the count within *word. + + explicit DeadlockNodeBucket(const Mutex* mu) { + const uint64_t h = + uint64_t{reinterpret_cast<uintptr_t>(mu)} * 0x9e3779b97f4a7c15ULL; + const size_t i = static_cast<size_t>(h >> (64 - kDeadlockNodeBucketBits)); + word = &deadlock_node_bucket_counts[i / 4]; + shift = static_cast<int>(i % 4) * 8; + } + + bool IsEmpty() const { + return ((word->load(std::memory_order_relaxed) >> shift) & 0xff) == 0; + } + + // Adds 1 to (if increment) or subtracts 1 from the count, unless it is + // saturated. + void Update(bool increment) const + ABSL_EXCLUSIVE_LOCKS_REQUIRED(deadlock_graph_mu) { + const uint32_t w = word->load(std::memory_order_relaxed); + if (((w >> shift) & 0xff) == 0xff) return; + const uint32_t one = uint32_t{1} << shift; + word->store(increment ? w + one : w - one, std::memory_order_relaxed); + } +}; +} // namespace + static GraphId GetGraphIdLocked(Mutex* mu) ABSL_EXCLUSIVE_LOCKS_REQUIRED(deadlock_graph_mu) { if (!deadlock_graph) { // (re)create the deadlock graph. @@ -1257,7 +1296,10 @@ new (base_internal::LowLevelAlloc::Alloc(sizeof(*deadlock_graph))) GraphCycles; } - return deadlock_graph->GetId(mu); + bool is_new = false; + const GraphId id = deadlock_graph->GetId(mu, &is_new); + if (is_new) DeadlockNodeBucket(mu).Update(/*increment=*/true); + return id; } // Returns the index of the entry for mu in held_locks, or -1 if there is none. @@ -1544,9 +1586,14 @@ held_locks->locks[i].forgotten = true; } } + // A node for this Mutex is created by a DeadlockCheck() call that + // happens-before this call, unless the two race (which would also race + // with the removal below), so then its bucket is not empty here. + const DeadlockNodeBucket bucket(this); + if (bucket.IsEmpty()) return; deadlock_graph_mu.lock(); - if (deadlock_graph != nullptr) { - deadlock_graph->RemoveNode(this); + if (deadlock_graph != nullptr && deadlock_graph->RemoveNode(this)) { + bucket.Update(/*increment=*/false); } deadlock_graph_mu.unlock(); }