Fix deadlock detection after ForgetDeadlockInfo() on a held Mutex In debug builds, the Mutex deadlock detector records each lock order edge (A is held while B is acquired) in a global graph keyed by Mutex address. ForgetDeadlockInfo() erases everything recorded about one Mutex by removing its graph node. The header says to call it when the lock ordering of a Mutex changes. ~Mutex() also calls it in debug builds, so that a new Mutex at a reused address does not inherit the old one's history. Each thread keeps a list of the locks it holds, so that it can add an edge from each of them when it acquires another lock. This list identified a held lock by the graph id that was looked up when the lock was acquired, and ForgetDeadlockInfo() makes that id stale. So, before this change, if any thread called ForgetDeadlockInfo() on a Mutex while some thread held it: - The hold was ignored for lock ordering until it was released. - unlock() looked up the entry by a newly assigned id, so it never removed the entry. After 40 leaked entries the list was full, and the detector silently stopped checking that thread. For example, if a thread held a Mutex 50 times, and each time another thread forgot it, a later a -> b, b -> a inversion on the first thread was not reported. - AssertNotHeld() compared a new id with the stale one, so it passed although the thread held the Mutex. These effects were accidental. This change identifies held locks by Mutex* instead. ForgetDeadlockInfo() still removes the Mutex's graph node, and now: - If the calling thread holds the Mutex, that hold is still ignored for lock ordering until it is released. A new per-entry flag marks such holds. - Holds by other threads keep counting. When such a thread next acquires another lock, the detector looks up the Mutex's new graph id and records the edge. This includes the later hold of a thread that was blocked in lock(), or waiting in CondVar::Wait(), when the Mutex was forgotten. - unlock() always removes the entry, so the thread keeps being checked. - ~Mutex() also removes any entry for the Mutex on the calling thread, since a Mutex destroyed while locked is never unlocked. Previously, destroying 40 locked Mutexes on a thread (as in Mutex.LockedMutexDestructionBug) filled the list and disabled deadlock detection on that thread for the rest of the process. - AssertNotHeld() fails for any Mutex that the thread holds, even after ForgetDeadlockInfo(). These rules do not depend on when a graph id was looked up. This lets a follow-up change look up graph ids only for nested locking, without changing behavior. As a side effect, unlock() and AssertNotHeld() no longer look up a graph id, so they no longer take deadlock_graph_mu or create graph nodes. (Before, unlock() even created a new node for a forgotten Mutex.) So a lock()/unlock() pair now takes deadlock_graph_mu once instead of twice. ~Mutex() still takes it once. Code that calls ForgetDeadlockInfo() on a Mutex that other threads hold may now get deadlock reports. First, those holds now count. Second, threads that used to stop being checked after 40 leaked entries keep being checked, which can also surface real inversions that involve other Mutexes. This mainly affects code that calls ForgetDeadlockInfo() right before every lock, to turn off deadlock detection for one Mutex. PiperOrigin-RevId: 1002421692
diff --git a/absl/synchronization/mutex.cc b/absl/synchronization/mutex.cc index d6e2aac..7d5aba7 100644 --- a/absl/synchronization/mutex.cc +++ b/absl/synchronization/mutex.cc
@@ -538,6 +538,9 @@ struct { Mutex* mu; // lock acquired int32_t count; // times acquired + // True iff this thread called mu->ForgetDeadlockInfo() while holding mu. + // The entry is then ignored for lock ordering until it is released. + bool forgotten; GraphId id; // deadlock_graph id of acquired lock } locks[40]; // If a thread overfills the array during deadlock detection, we @@ -559,6 +562,14 @@ return ret; } +static void RemoveHeldLockEntry(SynchLocksHeld* held_locks, int i) { + const int last = --held_locks->n; + held_locks->locks[i] = held_locks->locks[last]; + held_locks->locks[last].id = InvalidGraphId(); + held_locks->locks[last].mu = + nullptr; // clear mu to please the leak detector. +} + // Return the PerThreadSynch-struct for this thread. static PerThreadSynch* Synch_GetPerThread() { ThreadIdentity* identity = GetOrCreateCurrentThreadIdentity(); @@ -757,6 +768,20 @@ defined(ABSL_BUILD_DLL) void Mutex::Dtor() { if (kDebugMode) { + // If this thread is destroying a locked Mutex, remove any held-lock + // entries for it so their slots are not leaked. + ThreadIdentity* identity = CurrentThreadIdentityIfPresent(); + if (identity != nullptr && + identity->per_thread_synch.all_locks != nullptr) { + SynchLocksHeld* held_locks = identity->per_thread_synch.all_locks; + for (int i = 0; i < held_locks->n;) { + if (held_locks->locks[i].mu == this) { + RemoveHeldLockEntry(held_locks, i); + } else { + i++; + } + } + } this->ForgetDeadlockInfo(); } ABSL_TSAN_MUTEX_DESTROY(this, __tsan_mutex_not_static); @@ -1237,22 +1262,35 @@ return id; } +// 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. +static int FindHeldLock(const SynchLocksHeld* held_locks, const Mutex* mu) { + int forgotten_index = -1; + for (int i = 0; i != held_locks->n; i++) { + if (held_locks->locks[i].mu == mu) { + if (!held_locks->locks[i].forgotten) return i; + if (forgotten_index == -1) forgotten_index = i; + } + } + return forgotten_index; +} + // Record a lock acquisition. This is used in debug mode for deadlock // detection. The held_locks pointer points to the relevant data // structure for each case. static void LockEnter(Mutex* mu, GraphId id, SynchLocksHeld* held_locks) { int n = held_locks->n; - int i = 0; - while (i != n && held_locks->locks[i].id != id) { - i++; - } - if (i == n) { + int i = FindHeldLock(held_locks, mu); + // A forgotten hold stays ignored, so a new hold of mu gets its own entry. + if (i == -1 || held_locks->locks[i].forgotten) { if (n == static_cast<int>(std::size(held_locks->locks))) { held_locks->overflow = true; // lost some data } else { // we have room for lock - held_locks->locks[i].mu = mu; - held_locks->locks[i].count = 1; - held_locks->locks[i].id = id; + held_locks->locks[n].mu = mu; + held_locks->locks[n].count = 1; + held_locks->locks[n].forgotten = false; + held_locks->locks[n].id = id; held_locks->n = n + 1; } } else { @@ -1261,38 +1299,27 @@ } // Record a lock release. Each call to LockEnter(mu, id, x) should be -// eventually followed by a call to LockLeave(mu, id, x) by the same thread. +// eventually followed by a call to LockLeave(mu, x) by the same thread. // It does not process the event if is not needed when deadlock detection is // disabled. -static void LockLeave(Mutex* mu, GraphId id, SynchLocksHeld* held_locks) { - int n = held_locks->n; - int i = 0; - while (i != n && held_locks->locks[i].id != id) { - i++; - } - if (i == n) { - if (!held_locks->overflow) { - // The deadlock id may have been reassigned after ForgetDeadlockInfo, - // but in that case mu should still be present. - i = 0; - while (i != n && held_locks->locks[i].mu != mu) { - i++; - } - if (i == n) { // mu missing means releasing unheld lock - SynchEvent* mu_events = GetSynchEvent(mu); - ABSL_RAW_LOG(FATAL, - "thread releasing lock it does not hold: %p %s; " - , - static_cast<void*>(mu), - mu_events == nullptr ? "" : mu_events->name); - } +static void LockLeave(Mutex* mu, SynchLocksHeld* held_locks) { + // If mu was forgotten while held, this releases the forgotten entry. + int i = FindHeldLock(held_locks, mu); + if (i == -1) { + // The thread does not hold mu, unless held_locks was full when mu was + // acquired. + if (held_locks->overflow) { + return; } - } else if (held_locks->locks[i].count == 1) { - held_locks->n = n - 1; - held_locks->locks[i] = held_locks->locks[n - 1]; - held_locks->locks[n - 1].id = InvalidGraphId(); - held_locks->locks[n - 1].mu = - nullptr; // clear mu to please the leak detector. + SynchEvent* mu_events = GetSynchEvent(mu); + ABSL_RAW_LOG(FATAL, + "thread releasing lock it does not hold: %p %s; " + , + static_cast<void*>(mu), + mu_events == nullptr ? "" : mu_events->name); + } + if (held_locks->locks[i].count == 1) { + RemoveHeldLockEntry(held_locks, i); } else { assert(held_locks->locks[i].count > 0); held_locks->locks[i].count--; @@ -1324,7 +1351,7 @@ if (kDebugMode) { if (synch_deadlock_detection.load(std::memory_order_acquire) != OnDeadlockCycle::kIgnore) { - LockLeave(mu, GetGraphId(mu), Synch_GetAllLocks()); + LockLeave(mu, Synch_GetAllLocks()); } } } @@ -1384,6 +1411,29 @@ } } // 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 new ids for the entries in held_locks that are not marked forgotten +// and whose ids are no longer current, because another thread called +// ForgetDeadlockInfo() on that Mutex after this thread acquired it. +static void UpdateHeldLockIds(SynchLocksHeld* held_locks) + ABSL_EXCLUSIVE_LOCKS_REQUIRED(deadlock_graph_mu) { + for (int i = 0; i != held_locks->n; i++) { + if (held_locks->locks[i].forgotten) continue; + const GraphId id = held_locks->locks[i].id; + if (id == InvalidGraphId() || deadlock_graph->Ptr(id) == nullptr) { + held_locks->locks[i].id = GetGraphIdLocked(held_locks->locks[i].mu); + } + } +} + // Called in debug mode when a thread is about to acquire a lock in a way that // may block. static GraphId DeadlockCheck(Mutex* mu) { @@ -1397,7 +1447,7 @@ absl::base_internal::SpinLockHolder lock(deadlock_graph_mu); const GraphId mu_id = GetGraphIdLocked(mu); - if (all_locks->n == 0) { + if (!HoldsUnforgottenLock(all_locks)) { // There are no other locks held. Return now so that we don't need to // call GetSynchEvent(). This way we do not record the stack trace // for this Mutex. It's ok, since if this Mutex is involved in a deadlock, @@ -1405,6 +1455,8 @@ return mu_id; } + UpdateHeldLockIds(all_locks); + // We prefer to keep stack traces that show a thread holding and acquiring // 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 @@ -1413,6 +1465,7 @@ // For each other mutex already held by this thread: for (int i = 0; i != all_locks->n; i++) { + if (all_locks->locks[i].forgotten) continue; const GraphId other_node_id = all_locks->locks[i].id; const Mutex* other = static_cast<const Mutex*>(deadlock_graph->Ptr(other_node_id)); @@ -1433,6 +1486,7 @@ CurrentStackString(b->buf, sizeof (b->buf), symbolize)); size_t len = 0; for (int j = 0; j != all_locks->n; j++) { + if (all_locks->locks[j].forgotten) continue; void* pr = deadlock_graph->Ptr(all_locks->locks[j].id); if (pr != nullptr) { snprintf(b->buf + len, sizeof(b->buf) - len, " %p", pr); @@ -1490,6 +1544,19 @@ void Mutex::ForgetDeadlockInfo() { if (kDebugMode && synch_deadlock_detection.load(std::memory_order_acquire) != OnDeadlockCycle::kIgnore) { + // If this thread holds this Mutex, ignore that hold from now on (see + // SynchLocksHeld::forgotten). Holds by other threads keep counting: + // RemoveNode() makes their ids stale, and DeadlockCheck() looks up the + // new id when they are next needed. + ThreadIdentity* identity = CurrentThreadIdentityIfPresent(); + if (identity != nullptr && + identity->per_thread_synch.all_locks != nullptr) { + SynchLocksHeld* held_locks = identity->per_thread_synch.all_locks; + int i = FindHeldLock(held_locks, this); + if (i != -1) { + held_locks->locks[i].forgotten = true; + } + } deadlock_graph_mu.lock(); if (deadlock_graph != nullptr) { deadlock_graph->RemoveNode(this); @@ -1505,10 +1572,9 @@ (mu_.load(std::memory_order_relaxed) & (kMuWriter | kMuReader)) != 0 && synch_deadlock_detection.load(std::memory_order_acquire) != OnDeadlockCycle::kIgnore) { - GraphId id = GetGraphId(const_cast<Mutex*>(this)); SynchLocksHeld* locks = Synch_GetAllLocks(); for (int i = 0; i != locks->n; i++) { - if (locks->locks[i].id == id) { + if (locks->locks[i].mu == this) { SynchEvent* mu_events = GetSynchEvent(this); ABSL_RAW_LOG(FATAL, "thread should not hold mutex %p %s", static_cast<const void*>(this),
diff --git a/absl/synchronization/mutex_test.cc b/absl/synchronization/mutex_test.cc index a96bcff..e945d5e 100644 --- a/absl/synchronization/mutex_test.cc +++ b/absl/synchronization/mutex_test.cc
@@ -1357,6 +1357,268 @@ c.unlock(); } +// The tests below check what the deadlock detector reports, so they need it to +// be compiled in. Under TSAN, the lock cycles they create would also trigger +// TSAN's own reports. +#if !defined(NDEBUG) && !defined(ABSL_HAVE_THREAD_SANITIZER) +// ForgetDeadlockInfo(), which ~Mutex() also calls, must remove the lock order +// recorded for the Mutex, including by other threads. +TEST(Mutex, ForgetDeadlockInfoForgetsLockOrder) +ABSL_NO_THREAD_SAFETY_ANALYSIS { + absl::SetMutexDeadlockDetectionMode(absl::OnDeadlockCycle::kAbort); + absl::Mutex a; + absl::Mutex b; + std::thread other([&]() ABSL_NO_THREAD_SAFETY_ANALYSIS { + a.lock(); + b.lock(); // Records a -> b. + b.unlock(); + a.unlock(); + }); + other.join(); + a.ForgetDeadlockInfo(); + // With a -> b forgotten, acquiring a while holding b is not a cycle. + b.lock(); + a.lock(); + a.unlock(); + b.unlock(); +} + +TEST(Mutex, ForgetDeadlockInfoWhileHeldDoesNotMaskOtherHeldLocks) +ABSL_NO_THREAD_SAFETY_ANALYSIS { + EXPECT_DEATH_IF_SUPPORTED( + { + ScopedDisableBazelTestWarnings disable_bazel_test_warnings; + absl::SetMutexDeadlockDetectionMode(absl::OnDeadlockCycle::kAbort); + absl::Mutex a; + absl::Mutex b; + absl::Mutex c; + // Record c -> a. + c.lock(); + a.lock(); + a.unlock(); + c.unlock(); + // Forgetting b while holding a and b must ignore only the hold of b. + a.lock(); + ASSERT_TRUE(b.try_lock_shared()); + b.ForgetDeadlockInfo(); + b.unlock_shared(); + // Acquiring c while holding a closes the cycle. + c.lock(); + }, + "dying due to potential deadlock"); +} + +// Forgetting a Mutex while another thread is blocked acquiring it must not +// hide the lock order of that thread's hold once it acquires the Mutex. +TEST(Mutex, ForgetDeadlockInfoWhileWaiterBlockedDoesNotMaskSubsequentHold) +ABSL_NO_THREAD_SAFETY_ANALYSIS { + for (bool waiter_holds_other_lock : {false, true}) { + EXPECT_DEATH_IF_SUPPORTED( + { + ScopedDisableBazelTestWarnings disable_bazel_test_warnings; + absl::SetMutexDeadlockDetectionMode(absl::OnDeadlockCycle::kAbort); + absl::Mutex other; + absl::Mutex a; + absl::Mutex b; + std::atomic<bool> about_to_lock{false}; + { + a.lock_shared(); + absl::synchronization_internal::ThreadPool pool(1); + pool.Schedule([&]() ABSL_NO_THREAD_SAFETY_ANALYSIS { + // If the waiter holds another lock, the deadlock check looks up + // the deadlock graph node of a before the waiter blocks. + if (waiter_holds_other_lock) other.lock(); + about_to_lock.store(true, std::memory_order_release); + a.lock(); // Blocks until a.unlock_shared() below. + b.lock(); // Records a -> b. + b.unlock(); + a.unlock(); + if (waiter_holds_other_lock) other.unlock(); + }); + while (!about_to_lock.load(std::memory_order_acquire)) { + absl::SleepFor(absl::Milliseconds(1)); + } + absl::SleepFor(absl::Milliseconds(20)); // Let the waiter block. + a.ForgetDeadlockInfo(); + a.unlock_shared(); + } + // Acquiring a while holding b closes the cycle. + b.lock(); + a.lock(); + }, + "dying due to potential deadlock"); + } +} + +// A hold by another thread keeps counting for lock ordering after +// ForgetDeadlockInfo(), even if that thread already used it to record lock +// order before the Mutex was forgotten. +TEST(Mutex, ForgetDeadlockInfoDoesNotMaskOtherThreadsHold) +ABSL_NO_THREAD_SAFETY_ANALYSIS { + EXPECT_DEATH_IF_SUPPORTED( + { + ScopedDisableBazelTestWarnings disable_bazel_test_warnings; + absl::SetMutexDeadlockDetectionMode(absl::OnDeadlockCycle::kAbort); + absl::Mutex a; + absl::Mutex b; + absl::Mutex c; + std::atomic<bool> recorded{false}; + std::atomic<bool> forgotten{false}; + std::thread holder([&]() ABSL_NO_THREAD_SAFETY_ANALYSIS { + a.lock(); + b.lock(); // Records a -> b. + b.unlock(); + recorded.store(true, std::memory_order_release); + while (!forgotten.load(std::memory_order_acquire)) { + absl::SleepFor(absl::Milliseconds(1)); + } + c.lock(); // Records a -> c, although a was forgotten. + c.unlock(); + a.unlock(); + }); + while (!recorded.load(std::memory_order_acquire)) { + absl::SleepFor(absl::Milliseconds(1)); + } + a.ForgetDeadlockInfo(); + forgotten.store(true, std::memory_order_release); + holder.join(); + // Acquiring a while holding c closes the cycle. + c.lock(); + a.lock(); + }, + "dying due to potential deadlock"); +} + +// Same, for a thread that waits on a CondVar: it is still considered to hold +// the Mutex while it waits. +TEST(Mutex, ForgetDeadlockInfoDuringCondVarWaitDoesNotMaskReacquiredHold) +ABSL_NO_THREAD_SAFETY_ANALYSIS { + EXPECT_DEATH_IF_SUPPORTED( + { + ScopedDisableBazelTestWarnings disable_bazel_test_warnings; + absl::SetMutexDeadlockDetectionMode(absl::OnDeadlockCycle::kAbort); + absl::Mutex a; + absl::Mutex b; + absl::CondVar cv; + bool ready = false; + std::atomic<bool> waiting{false}; + { + absl::synchronization_internal::ThreadPool pool(1); + pool.Schedule([&]() ABSL_NO_THREAD_SAFETY_ANALYSIS { + a.lock(); + waiting.store(true, std::memory_order_release); + while (!ready) { + cv.Wait(&a); + } + b.lock(); // Records a -> b. + b.unlock(); + a.unlock(); + }); + while (!waiting.load(std::memory_order_acquire)) { + absl::SleepFor(absl::Milliseconds(1)); + } + absl::SleepFor(absl::Milliseconds(20)); // Let the waiter wait. + a.ForgetDeadlockInfo(); + a.lock(); + ready = true; + cv.Signal(); + a.unlock(); + } + // Acquiring a while holding b closes the cycle. + b.lock(); + a.lock(); + }, + "dying due to potential deadlock"); +} + +TEST(Mutex, ForgetDeadlockInfoWhileHoldingManyLocks) +ABSL_NO_THREAD_SAFETY_ANALYSIS { + absl::SetMutexDeadlockDetectionMode(absl::OnDeadlockCycle::kAbort); + // Use a new thread: the list of held locks overflows and sets the thread's + // overflow flag. + std::thread thread([]() ABSL_NO_THREAD_SAFETY_ANALYSIS { + // More locks than the deadlock detector can track per thread. + constexpr int kNumLocks = 42; + absl::Mutex mutexes[kNumLocks]; + mutexes[0].lock(); + mutexes[0].ForgetDeadlockInfo(); + for (int i = 1; i < kNumLocks; ++i) { + mutexes[i].lock(); + } + for (int i = kNumLocks - 1; i >= 0; --i) { + mutexes[i].unlock(); + } + }); + thread.join(); + + // Repeatedly forgetting a held lock and unlocking it, or destroying a locked + // Mutex, must not leak slots in the thread's held-locks array. + EXPECT_DEATH_IF_SUPPORTED( + { + ScopedDisableBazelTestWarnings disable_bazel_test_warnings; + absl::SetMutexDeadlockDetectionMode(absl::OnDeadlockCycle::kAbort); + absl::Mutex m; + for (int i = 0; i < 50; ++i) { + m.lock(); + m.ForgetDeadlockInfo(); + m.unlock(); + } + auto destroyed_locked = std::make_unique<absl::Mutex[]>(50); + for (size_t i = 0; i < 50; ++i) { + destroyed_locked[i].lock(); + } + destroyed_locked.reset(); + absl::Mutex a; + absl::Mutex b; + a.lock(); + b.lock(); + b.unlock(); + a.unlock(); + b.lock(); + a.lock(); + }, + "dying due to potential deadlock"); +} + +TEST(Mutex, AssertNotHeld) ABSL_NO_THREAD_SAFETY_ANALYSIS { + absl::SetMutexDeadlockDetectionMode(absl::OnDeadlockCycle::kAbort); + absl::Mutex mu; + mu.AssertNotHeld(); + + // A hold by another thread does not count. + std::atomic<bool> held{false}; + std::atomic<bool> release{false}; + std::thread holder([&]() ABSL_NO_THREAD_SAFETY_ANALYSIS { + mu.lock(); + held.store(true, std::memory_order_release); + while (!release.load(std::memory_order_acquire)) { + absl::SleepFor(absl::Milliseconds(1)); + } + mu.unlock(); + }); + while (!held.load(std::memory_order_acquire)) { + absl::SleepFor(absl::Milliseconds(1)); + } + mu.AssertNotHeld(); + release.store(true, std::memory_order_release); + holder.join(); + + EXPECT_DEATH_IF_SUPPORTED( + { + mu.lock(); + mu.AssertNotHeld(); + }, + "thread should not hold mutex"); + EXPECT_DEATH_IF_SUPPORTED( + { + mu.lock(); + mu.ForgetDeadlockInfo(); + mu.AssertNotHeld(); + }, + "thread should not hold mutex"); +} +#endif // !defined(NDEBUG) && !defined(ABSL_HAVE_THREAD_SANITIZER) + // -------------------------------------------------------- // Test for timeouts/deadlines on condition waits that are specified using // absl::Duration and absl::Time. For each waiting function we test with