Cache lock-order edges per thread so DeadlockCheck() can skip deadlock_graph_mu. In debug builds with deadlock detection enabled, a thread that acquires a Mutex while it holds another takes the global deadlock_graph_mu spinlock, to insert the lock-order edges from its held locks into deadlock_graph. Most of these acquisitions find every edge already in the graph, but with many threads they still contend on deadlock_graph_mu. Give each thread a 512-entry direct-mapped cache of the edges that it has found or inserted in deadlock_graph. If every edge from a held lock to the new lock has a valid cache entry, DeadlockCheck() takes the held locks' GraphIds from the cache and returns without deadlock_graph_mu. A hit skips only work that would leave deadlock_graph unchanged: - Edges leave deadlock_graph only when one of their nodes is removed, so an entry is valid while both of its nodes are still in the graph. The new GraphCycles::IsCurrent() checks this by comparing node versions, without deadlock_graph_mu. RemoveNode() bumps the version, so an entry for a destroyed or forgotten Mutex misses, even if a new Mutex reuses its address. The check is exact per node: removing a node does not invalidate entries for other nodes. - DeadlockCheck() replaces a lock's stored stack trace when the thread holds more locks than when that trace was taken. So that a hit never skips this, each entry records the lock depth at which it was cached, and serves only acquisitions at that depth or lower. Cost: 28 KiB per thread, zero-initialized on the thread's first nested lock acquisition, only in debug builds with deadlock detection enabled. PiperOrigin-RevId: 997581889
diff --git a/absl/synchronization/internal/graphcycles.cc b/absl/synchronization/internal/graphcycles.cc index 7079081..a3edaed 100644 --- a/absl/synchronization/internal/graphcycles.cc +++ b/absl/synchronization/internal/graphcycles.cc
@@ -37,6 +37,7 @@ #include <algorithm> #include <array> +#include <atomic> #include <cinttypes> #include <cstddef> #include <cstdint> @@ -288,7 +289,9 @@ 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 + // Current version number. Atomic so that IsCurrent() can read it without + // the external synchronization that other methods require. + std::atomic<uint32_t> version; int32_t next_hash; // Next entry in hash table bool visited; // Temporary marker used by depth-first-search uintptr_t masked_ptr; // User-supplied pointer @@ -406,7 +409,9 @@ static Node* FindNode(GraphCycles::Rep* rep, GraphId id) { Node* n = rep->nodes_[static_cast<uint32_t>(NodeIndex(id))]; - return (n->version == NodeVersion(id)) ? n : nullptr; + return n->version.load(std::memory_order_relaxed) == NodeVersion(id) + ? n + : nullptr; } static Node* NodeAt(GraphCycles::Rep* r, int32_t slot) { @@ -611,13 +616,15 @@ GraphId GraphCycles::GetId(void* ptr) { int32_t i = rep_->ptrmap_.Find(ptr); if (i != -1) { - return MakeId(i, rep_->nodes_[static_cast<uint32_t>(i)]->version); + return MakeId(i, rep_->nodes_[static_cast<uint32_t>(i)]->version.load( + std::memory_order_relaxed)); } 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() + // Avoid 0 since it is used by InvalidGraphId() + n->version.store(1, std::memory_order_relaxed); n->visited = false; n->masked_ptr = base_internal::HidePtr(ptr); n->nstack = 0; @@ -625,7 +632,7 @@ rep_->nodes_.push_back(n); LinkBetween(rep_, slot, rep_->highest_slot, /*next_slot=*/-1); rep_->ptrmap_.Add(ptr, slot); - return MakeId(slot, n->version); + return MakeId(slot, 1); } else { // The slot keeps its rank (see "Rank allocation"). int32_t slot = rep_->free_nodes_.back(); @@ -635,7 +642,7 @@ n->nstack = 0; n->priority = 0; rep_->ptrmap_.Add(ptr, slot); - return MakeId(slot, n->version); + return MakeId(slot, n->version.load(std::memory_order_relaxed)); } } @@ -654,10 +661,12 @@ x->in.clear(); x->out.clear(); x->masked_ptr = base_internal::HidePtr<void>(nullptr); - if (x->version == std::numeric_limits<uint32_t>::max()) { + const uint32_t version = x->version.load(std::memory_order_relaxed); + if (version == std::numeric_limits<uint32_t>::max()) { // Cannot use x any more } else { - x->version++; // Invalidates all copies of node. + // Invalidates all copies of node. + x->version.store(version + 1, std::memory_order_relaxed); rep_->free_nodes_.push_back(i); } } @@ -671,6 +680,15 @@ return FindNode(rep_, node) != nullptr; } +const void* GraphCycles::GetNodeHandle(GraphId node) { + return FindNode(rep_, node); +} + +bool GraphCycles::IsCurrent(const void* node_handle, GraphId node) { + return static_cast<const Node*>(node_handle) + ->version.load(std::memory_order_relaxed) == NodeVersion(node); +} + bool GraphCycles::HasEdge(GraphId x, GraphId y) const { Node* xn = FindNode(rep_, x); return xn && FindNode(rep_, y) && xn->out.contains(NodeIndex(y)); @@ -935,7 +953,8 @@ if (path_len < max_path_len) { path[path_len] = - MakeId(n, rep_->nodes_[static_cast<uint32_t>(n)]->version); + MakeId(n, rep_->nodes_[static_cast<uint32_t>(n)]->version.load( + std::memory_order_relaxed)); } path_len++; r->stack_.push_back(-1); // Will remove tentative path entry
diff --git a/absl/synchronization/internal/graphcycles.h b/absl/synchronization/internal/graphcycles.h index 27eaa6c..72b6e76 100644 --- a/absl/synchronization/internal/graphcycles.h +++ b/absl/synchronization/internal/graphcycles.h
@@ -88,6 +88,17 @@ // Return whether node exists in the graph. bool HasNode(GraphId node); + // Return an opaque handle to node for use with IsCurrent(), or nullptr if + // node is not in the graph. The handle remains usable for the lifetime of + // this GraphCycles. + const void* GetNodeHandle(GraphId node); + + // Return whether node, whose handle was returned by GetNodeHandle(node), is + // still in the graph. Unlike the other methods, this may be called without + // external serialization. Its result then reflects at least every + // RemoveNode() call that happens-before it. + static bool IsCurrent(const void* node_handle, GraphId node); + // Return whether there is an edge directly from source_node to dest_node. bool HasEdge(GraphId x, GraphId y) const;
diff --git a/absl/synchronization/internal/graphcycles_test.cc b/absl/synchronization/internal/graphcycles_test.cc index b1a6daf..26a81aa 100644 --- a/absl/synchronization/internal/graphcycles_test.cc +++ b/absl/synchronization/internal/graphcycles_test.cc
@@ -644,6 +644,26 @@ CheckInvariants(g); } +TEST(GraphCycles, NodeHandles) { + GraphCycles g; + int a = 0; + const GraphId id1 = g.GetId(&a); + const void* handle = g.GetNodeHandle(id1); + ASSERT_NE(handle, nullptr); + EXPECT_TRUE(GraphCycles::IsCurrent(handle, id1)); + + g.RemoveNode(&a); + EXPECT_FALSE(GraphCycles::IsCurrent(handle, id1)); + EXPECT_EQ(g.GetNodeHandle(id1), nullptr); + + // The next node reuses the removed node's slot, and so its handle. + const GraphId id2 = g.GetId(&a); + EXPECT_NE(id2, id1); + EXPECT_EQ(g.GetNodeHandle(id2), handle); + EXPECT_TRUE(GraphCycles::IsCurrent(handle, id2)); + EXPECT_FALSE(GraphCycles::IsCurrent(handle, id1)); +} + } // namespace synchronization_internal ABSL_NAMESPACE_END } // namespace absl
diff --git a/absl/synchronization/mutex.cc b/absl/synchronization/mutex.cc index d5c1a3c..f6f161a 100644 --- a/absl/synchronization/mutex.cc +++ b/absl/synchronization/mutex.cc
@@ -535,6 +535,7 @@ struct SynchLocksHeld { int n; // number of valid entries in locks[] bool overflow; // true iff we overflowed the array at some point + bool edge_cache_initialized; struct { Mutex* mu; // lock acquired int32_t count; // times acquired @@ -551,6 +552,24 @@ // continue, discarding information as needed. If no overflow has // taken place, we can provide more error checking, such as // detecting when a thread releases a lock it does not hold. + + // Direct-mapped cache of lock-order edges (from -> to) that this thread + // found or inserted in deadlock_graph, so that DeadlockCheck() can skip + // deadlock_graph_mu when all the edges it would insert are cached. An entry + // is valid while deadlock_graph still has both nodes (see + // GraphCycles::IsCurrent()). It covers acquisitions at lock depths up to + // priority, since a stack trace of at least that priority is recorded for + // `to`. + static constexpr size_t kEdgeCacheSize = 512; + struct CachedEdge { + uintptr_t from_masked; // base_internal::HidePtr(from) + uintptr_t to_masked; // base_internal::HidePtr(to) + GraphId from_id; + GraphId to_id; + const void* from_node; // GraphCycles::GetNodeHandle(from_id) + const void* to_node; // GraphCycles::GetNodeHandle(to_id) + int priority; + } edge_cache[kEdgeCacheSize]; }; // A sentinel value in lists that is not 0. @@ -563,6 +582,7 @@ base_internal::LowLevelAlloc::Alloc(sizeof(SynchLocksHeld))); ret->n = 0; ret->overflow = false; + ret->edge_cache_initialized = false; return ret; } @@ -1260,6 +1280,14 @@ return deadlock_graph->GetId(mu); } +// Returns the SynchLocksHeld::edge_cache slot for the edge from -> to. +static size_t EdgeCacheIndex(const Mutex* from, const Mutex* to) { + const uint64_t a = reinterpret_cast<uintptr_t>(from); + const uint64_t b = reinterpret_cast<uintptr_t>(to); + const uint64_t h = (a * 0x9e3779b97f4a7c15ULL) ^ (b * 0xbf58476d1ce4e5b9ULL); + return static_cast<size_t>((h >> 32) & (SynchLocksHeld::kEdgeCacheSize - 1)); +} + // Returns the index of the entry for mu in held_locks, or -1 if there is none. // Prefers the entry that is not marked forgotten (there is at most one), and // otherwise returns the first entry that is. @@ -1399,15 +1427,6 @@ } } // anonymous namespace -// Returns true iff held_locks has an entry that counts for lock ordering, that -// is, one that is not marked forgotten. -static bool HoldsUnforgottenLock(const SynchLocksHeld* held_locks) { - for (int i = 0; i != held_locks->n; i++) { - if (!held_locks->locks[i].forgotten) return true; - } - return false; -} - // Looks up ids for the entries in held_locks that are not marked forgotten and // do not have a current id, because this thread has not needed it yet, or // because another thread called ForgetDeadlockInfo() on that Mutex. @@ -1432,7 +1451,31 @@ SynchLocksHeld* all_locks = Synch_GetAllLocks(); - if (!HoldsUnforgottenLock(all_locks)) { + // Entries marked forgotten do not count for lock ordering. Check whether + // every edge from a held lock to mu is already in deadlock_graph, according + // to this thread's edge cache. + bool holds_lock = false; + bool all_cached = all_locks->edge_cache_initialized; + const int priority = all_locks->n + 1; + const uintptr_t mu_masked = base_internal::HidePtr(mu); + for (int i = 0; i != all_locks->n; i++) { + if (all_locks->locks[i].forgotten) continue; + holds_lock = true; + if (!all_cached) break; + const Mutex* other = all_locks->locks[i].mu; + const SynchLocksHeld::CachedEdge& c = + all_locks->edge_cache[EdgeCacheIndex(other, mu)]; + if (c.from_masked != base_internal::HidePtr(other) || + c.to_masked != mu_masked || c.priority < priority || + (all_locks->locks[i].id != InvalidGraphId() && + all_locks->locks[i].id != c.from_id) || + !GraphCycles::IsCurrent(c.from_node, c.from_id) || + !GraphCycles::IsCurrent(c.to_node, c.to_id)) { + all_cached = false; + break; + } + } + if (!holds_lock) { // There are no other locks held, so there are no edges to add. Return now // so that we don't need to take deadlock_graph_mu or call GetSynchEvent(). // This way we do not record the stack trace for this Mutex. It's ok, since @@ -1440,6 +1483,22 @@ // lock acquired by a thread. return; } + if (all_cached) { + // Record the ids of held locks, as the code below would. + for (int i = 0; i != all_locks->n; i++) { + if (!all_locks->locks[i].forgotten && + all_locks->locks[i].id == InvalidGraphId()) { + all_locks->locks[i].id = + all_locks->edge_cache[EdgeCacheIndex(all_locks->locks[i].mu, mu)] + .from_id; + } + } + return; + } + if (!all_locks->edge_cache_initialized) { + memset(all_locks->edge_cache, 0, sizeof(all_locks->edge_cache)); + all_locks->edge_cache_initialized = true; + } absl::base_internal::SpinLockHolder lock(deadlock_graph_mu); @@ -1453,7 +1512,7 @@ // as many locks as possible. This increases the chances that a given edge // in the acquires-before graph will be represented in the stack traces // recorded for the locks. - deadlock_graph->UpdateStackTrace(mu_id, all_locks->n + 1, GetStack); + deadlock_graph->UpdateStackTrace(mu_id, priority, GetStack); // For each other mutex already held by this thread: for (int i = 0; i != all_locks->n; i++) { @@ -1516,6 +1575,22 @@ } break; // report at most one potential deadlock per acquisition } + + // The edge is in deadlock_graph, and a stack trace of at least this + // priority is recorded for mu. Remember that in the edge cache. + const uintptr_t other_masked = base_internal::HidePtr(other); + SynchLocksHeld::CachedEdge& c = + all_locks->edge_cache[EdgeCacheIndex(other, mu)]; + const bool same_edge = c.from_masked == other_masked && + c.to_masked == mu_masked && + c.from_id == other_node_id && c.to_id == mu_id; + c = {other_masked, + mu_masked, + other_node_id, + mu_id, + deadlock_graph->GetNodeHandle(other_node_id), + deadlock_graph->GetNodeHandle(mu_id), + same_edge && c.priority > priority ? c.priority : priority}; } }
diff --git a/absl/synchronization/mutex_test.cc b/absl/synchronization/mutex_test.cc index 50b982e..d89bd89 100644 --- a/absl/synchronization/mutex_test.cc +++ b/absl/synchronization/mutex_test.cc
@@ -1403,6 +1403,50 @@ b.unlock(); } +TEST(Mutex, ForgetDeadlockInfoInvalidatesCachedEdge) +ABSL_NO_THREAD_SAFETY_ANALYSIS { + for (bool recreate_from : {false, true}) { + EXPECT_DEATH_IF_SUPPORTED( + { + ScopedDisableBazelTestWarnings disable_bazel_test_warnings; + absl::SetMutexDeadlockDetectionMode(absl::OnDeadlockCycle::kAbort); + alignas(absl::Mutex) unsigned char storage_a[sizeof(absl::Mutex)]; + alignas(absl::Mutex) unsigned char storage_b[sizeof(absl::Mutex)]; + absl::Mutex* a = new (storage_a) absl::Mutex; + absl::Mutex* b = new (storage_b) absl::Mutex; + + // Populate this thread's edge cache with a -> b. + a->lock(); + b->lock(); + b->unlock(); + a->unlock(); + + // Destroy and recreate one endpoint at the exact same address on + // another thread, then record the reverse edge b -> a. + std::thread other([&]() ABSL_NO_THREAD_SAFETY_ANALYSIS { + if (recreate_from) { + a->~Mutex(); + a = new (storage_a) absl::Mutex; + } else { + b->~Mutex(); + b = new (storage_b) absl::Mutex; + } + b->lock(); + a->lock(); + a->unlock(); + b->unlock(); + }); + other.join(); + + // Acquiring b while holding a on the original thread must not hit the + // stale a -> b cache entry; it must detect the b -> a -> b cycle. + a->lock(); + b->lock(); + }, + "dying due to potential deadlock"); + } +} + TEST(Mutex, ForgetDeadlockInfoWhileHeldDoesNotMaskOtherHeldLocks) ABSL_NO_THREAD_SAFETY_ANALYSIS { EXPECT_DEATH_IF_SUPPORTED(