From de60b3af716f062752e1dee410de1064438a20af Mon Sep 17 00:00:00 2001 From: Kostya Serebryany Date: Fri, 21 Feb 2014 15:07:18 +0000 Subject: [tsan] add coarse-grained lock around the DeadlockDetector. We can do better than that, but that's a start. git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@201861 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/tsan/rtl/tsan_mutex.h | 1 + lib/tsan/rtl/tsan_rtl.cc | 4 ++- lib/tsan/rtl/tsan_rtl.h | 3 ++ lib/tsan/rtl/tsan_rtl_mutex.cc | 34 ++++++++++-------- lib/tsan/rtl/tsan_stat.cc | 1 + lib/tsan/rtl/tsan_stat.h | 1 + test/tsan/deadlock_detector_stress_test.cc | 55 +++++++++++++++++++++++++----- 7 files changed, 74 insertions(+), 25 deletions(-) diff --git a/lib/tsan/rtl/tsan_mutex.h b/lib/tsan/rtl/tsan_mutex.h index 4e47d7a31..0cb0e5be4 100644 --- a/lib/tsan/rtl/tsan_mutex.h +++ b/lib/tsan/rtl/tsan_mutex.h @@ -31,6 +31,7 @@ enum MutexType { MutexTypeAtExit, MutexTypeMBlock, MutexTypeJavaMBlock, + MutexTypeDeadlockDetector, // This must be the last. MutexTypeCount diff --git a/lib/tsan/rtl/tsan_rtl.cc b/lib/tsan/rtl/tsan_rtl.cc index b0c2ee35f..408423db2 100644 --- a/lib/tsan/rtl/tsan_rtl.cc +++ b/lib/tsan/rtl/tsan_rtl.cc @@ -82,7 +82,9 @@ Context::Context() CreateThreadContext, kMaxTid, kThreadQuarantineSize)) , racy_stacks(MBlockRacyStacks) , racy_addresses(MBlockRacyAddresses) - , fired_suppressions(8) { + , fired_suppressions(8) + , dd_mtx(MutexTypeDeadlockDetector, StatMtxDeadlockDetector) { + dd.clear(); } // The objects are allocated in TLS, so one may rely on zero-initialization. diff --git a/lib/tsan/rtl/tsan_rtl.h b/lib/tsan/rtl/tsan_rtl.h index dc7ea0c26..b7090f918 100644 --- a/lib/tsan/rtl/tsan_rtl.h +++ b/lib/tsan/rtl/tsan_rtl.h @@ -549,6 +549,9 @@ struct Context { // Number of fired suppressions may be large enough. InternalMmapVector fired_suppressions; + __sanitizer::DeadlockDetector dd; + Mutex dd_mtx; + Flags flags; u64 stat[StatCnt]; diff --git a/lib/tsan/rtl/tsan_rtl_mutex.cc b/lib/tsan/rtl/tsan_rtl_mutex.cc index 364f4b57c..74aec4e6a 100644 --- a/lib/tsan/rtl/tsan_rtl_mutex.cc +++ b/lib/tsan/rtl/tsan_rtl_mutex.cc @@ -22,11 +22,10 @@ namespace __tsan { -static __sanitizer::DeadlockDetector g_dd; -static void EnsureDeadlockDetectorID(ThreadState *thr, SyncVar *s) { - if (!g_dd.nodeBelongsToCurrentEpoch(s->deadlock_detector_id)) - s->deadlock_detector_id = g_dd.newNode(reinterpret_cast(s)); +static void EnsureDeadlockDetectorID(Context *ctx, SyncVar *s) { + if (!ctx->dd.nodeBelongsToCurrentEpoch(s->deadlock_detector_id)) + s->deadlock_detector_id = ctx->dd.newNode(reinterpret_cast(s)); } void MutexCreate(ThreadState *thr, uptr pc, uptr addr, @@ -61,8 +60,9 @@ void MutexDestroy(ThreadState *thr, uptr pc, uptr addr) { if (s == 0) return; if (common_flags()->detect_deadlocks) { - if (g_dd.nodeBelongsToCurrentEpoch(s->deadlock_detector_id)) - g_dd.removeNode(s->deadlock_detector_id); + Lock lk(&ctx->dd_mtx); + if (ctx->dd.nodeBelongsToCurrentEpoch(s->deadlock_detector_id)) + ctx->dd.removeNode(s->deadlock_detector_id); s->deadlock_detector_id = 0; } if (IsAppMem(addr)) { @@ -92,11 +92,12 @@ void MutexDestroy(ThreadState *thr, uptr pc, uptr addr) { } void MutexLock(ThreadState *thr, uptr pc, uptr addr, int rec) { + Context *ctx = CTX(); DPrintf("#%d: MutexLock %zx rec=%d\n", thr->tid, addr, rec); CHECK_GT(rec, 0); if (IsAppMem(addr)) MemoryReadAtomic(thr, pc, addr, kSizeLog1); - SyncVar *s = CTX()->synctab.GetOrCreateAndLock(thr, pc, addr, true); + SyncVar *s = ctx->synctab.GetOrCreateAndLock(thr, pc, addr, true); thr->fast_state.IncrementEpoch(); TraceAddEvent(thr, thr->fast_state, EventTypeLock, s->GetId()); if (s->owner_tid == SyncVar::kInvalidTid) { @@ -119,24 +120,25 @@ void MutexLock(ThreadState *thr, uptr pc, uptr addr, int rec) { s->recursion += rec; thr->mset.Add(s->GetId(), true, thr->fast_state.epoch()); if (common_flags()->detect_deadlocks) { - EnsureDeadlockDetectorID(thr, s); - if (g_dd.isHeld(&thr->deadlock_detector_tls, s->deadlock_detector_id)) { + Lock lk(&ctx->dd_mtx); + EnsureDeadlockDetectorID(ctx, s); + if (ctx->dd.isHeld(&thr->deadlock_detector_tls, s->deadlock_detector_id)) { // FIXME: add tests, handle the real recursive locks. Printf("ThreadSanitizer: reursive-lock\n"); } // Printf("MutexLock: %zx\n", s->deadlock_detector_id); bool has_deadlock = - g_dd.onLock(&thr->deadlock_detector_tls, s->deadlock_detector_id); + ctx->dd.onLock(&thr->deadlock_detector_tls, s->deadlock_detector_id); if (has_deadlock) { uptr path[10]; - uptr len = g_dd.findPathToHeldLock(&thr->deadlock_detector_tls, + uptr len = ctx->dd.findPathToHeldLock(&thr->deadlock_detector_tls, s->deadlock_detector_id, path, ARRAY_SIZE(path)); CHECK_GT(len, 0U); // Hm.. cycle of 10 locks? I'd like to see that. ThreadRegistryLock l(CTX()->thread_registry); ScopedReport rep(ReportTypeDeadlock); for (uptr i = 0; i < len; i++) - rep.AddMutex(reinterpret_cast(g_dd.getData(path[i]))); + rep.AddMutex(reinterpret_cast(ctx->dd.getData(path[i]))); StackTrace trace; trace.ObtainCurrent(thr, pc); rep.AddStack(&trace); @@ -147,10 +149,11 @@ void MutexLock(ThreadState *thr, uptr pc, uptr addr, int rec) { } int MutexUnlock(ThreadState *thr, uptr pc, uptr addr, bool all) { + Context *ctx = CTX(); DPrintf("#%d: MutexUnlock %zx all=%d\n", thr->tid, addr, all); if (IsAppMem(addr)) MemoryReadAtomic(thr, pc, addr, kSizeLog1); - SyncVar *s = CTX()->synctab.GetOrCreateAndLock(thr, pc, addr, true); + SyncVar *s = ctx->synctab.GetOrCreateAndLock(thr, pc, addr, true); thr->fast_state.IncrementEpoch(); TraceAddEvent(thr, thr->fast_state, EventTypeUnlock, s->GetId()); int rec = 0; @@ -180,9 +183,10 @@ int MutexUnlock(ThreadState *thr, uptr pc, uptr addr, bool all) { } thr->mset.Del(s->GetId(), true); if (common_flags()->detect_deadlocks) { - EnsureDeadlockDetectorID(thr, s); + Lock lk(&ctx->dd_mtx); + EnsureDeadlockDetectorID(ctx, s); // Printf("MutexUnlock: %zx\n", s->deadlock_detector_id); - g_dd.onUnlock(&thr->deadlock_detector_tls, + ctx->dd.onUnlock(&thr->deadlock_detector_tls, s->deadlock_detector_id); } s->mtx.Unlock(); diff --git a/lib/tsan/rtl/tsan_stat.cc b/lib/tsan/rtl/tsan_stat.cc index 4da75589d..010a2317f 100644 --- a/lib/tsan/rtl/tsan_stat.cc +++ b/lib/tsan/rtl/tsan_stat.cc @@ -145,6 +145,7 @@ void StatOutput(u64 *stat) { name[StatMtxAnnotations] = " Annotations "; name[StatMtxMBlock] = " MBlock "; name[StatMtxJavaMBlock] = " JavaMBlock "; + name[StatMtxDeadlockDetector] = " DeadlockDetector "; name[StatMtxFD] = " FD "; Printf("Statistics:\n"); diff --git a/lib/tsan/rtl/tsan_stat.h b/lib/tsan/rtl/tsan_stat.h index 789c4c725..6453bda5f 100644 --- a/lib/tsan/rtl/tsan_stat.h +++ b/lib/tsan/rtl/tsan_stat.h @@ -143,6 +143,7 @@ enum StatType { StatMtxAtExit, StatMtxMBlock, StatMtxJavaMBlock, + StatMtxDeadlockDetector, StatMtxFD, // This must be the last. diff --git a/test/tsan/deadlock_detector_stress_test.cc b/test/tsan/deadlock_detector_stress_test.cc index 535ced7c6..74dafe84b 100644 --- a/test/tsan/deadlock_detector_stress_test.cc +++ b/test/tsan/deadlock_detector_stress_test.cc @@ -44,8 +44,8 @@ class LockTest { // CHECK: Starting Test1 fprintf(stderr, "Expecting lock inversion: %p %p\n", A(0), A(1)); // CHECK: Expecting lock inversion: [[A1:0x[a-f0-9]*]] [[A2:0x[a-f0-9]*]] - L(0); L(1); U(0); U(1); - L(1); L(0); U(0); U(1); + Lock_0_1(); + Lock_1_0(); // CHECK: WARNING: ThreadSanitizer: lock-order-inversion (potential deadlock) // CHECK: path: [[M1:M[0-9]+]] => [[M2:M[0-9]+]] => [[M1]] // CHECK: Mutex [[M1]] ([[A1]]) created at: @@ -59,9 +59,9 @@ class LockTest { // CHECK: Starting Test2 fprintf(stderr, "Expecting lock inversion: %p %p %p\n", A(0), A(1), A(2)); // CHECK: Expecting lock inversion: [[A1:0x[a-f0-9]*]] [[A2:0x[a-f0-9]*]] [[A3:0x[a-f0-9]*]] - L(0); L(1); U(0); U(1); - L(1); L(2); U(1); U(2); - L(2); L(0); U(0); U(2); + Lock2(0, 1); + Lock2(1, 2); + Lock2(2, 0); // CHECK: WARNING: ThreadSanitizer: lock-order-inversion (potential deadlock) // CHECK: path: [[M1:M[0-9]+]] => [[M2:M[0-9]+]] => [[M3:M[0-9]+]] => [[M1]] // CHECK: Mutex [[M1]] ([[A1]]) created at: @@ -76,11 +76,11 @@ class LockTest { void Test3() { fprintf(stderr, "Starting Test3\n"); // CHECK: Starting Test3 - L(0); L(1); U(0); U(1); + Lock_0_1(); L(2); CreateAndDestroyManyLocks(); U(2); - L(1); L(0); U(0); U(1); + Lock_1_0(); // CHECK: WARNING: ThreadSanitizer: lock-order-inversion (potential deadlock) // CHECK-NOT: WARNING: ThreadSanitizer: } @@ -90,15 +90,27 @@ class LockTest { void Test4() { fprintf(stderr, "Starting Test4\n"); // CHECK: Starting Test4 - L(0); L(1); U(0); U(1); + Lock_0_1(); L(2); CreateLockUnlockAndDestroyManyLocks(); U(2); - L(1); L(0); U(0); U(1); + Lock_1_0(); + // CHECK-NOT: WARNING: ThreadSanitizer: + } + + void Test5() { + fprintf(stderr, "Starting Test5\n"); + // CHECK: Starting Test5 + RunThreads(&LockTest::Lock_0_1, &LockTest::Lock_1_0); + // CHECK: WARNING: ThreadSanitizer: lock-order-inversion // CHECK-NOT: WARNING: ThreadSanitizer: } private: + void Lock2(size_t l1, size_t l2) { L(l1); L(l2); U(l2); U(l1); } + void Lock_0_1() { Lock2(0, 1); } + void Lock_1_0() { Lock2(1, 0); } + void CreateAndDestroyManyLocks() { PaddedLock create_many_locks_but_never_acquire[kDeadlockGraphSize]; } @@ -109,6 +121,30 @@ class LockTest { many_locks[i].unlock(); } } + + // LockTest Member function callback. + struct CB { + void (LockTest::*f)(); + LockTest *lt; + }; + + // Thread function with CB. + static void *Thread(void *param) { + CB *cb = (CB*)param; + (cb->lt->*cb->f)(); + return NULL; + } + + void RunThreads(void (LockTest::*f1)(), void (LockTest::*f2)()) { + const int kNumThreads = 2; + pthread_t t[kNumThreads]; + CB cb[2] = {{f1, this}, {f2, this}}; + for (int i = 0; i < kNumThreads; i++) + pthread_create(&t[i], 0, Thread, &cb[i]); + for (int i = 0; i < kNumThreads; i++) + pthread_join(t[i], 0); + } + static const size_t kDeadlockGraphSize = 4096; size_t n_; PaddedLock *locks_; @@ -119,6 +155,7 @@ int main() { { LockTest t(5); t.Test2(); } { LockTest t(5); t.Test3(); } { LockTest t(5); t.Test4(); } + { LockTest t(5); t.Test5(); } fprintf(stderr, "DONE\n"); // CHECK: DONE } -- cgit v1.2.3