tsan: refactor deadlock detector

Introduce DDetector interface between the tool and the DD itself.
It will help to experiment with other DD implementation,
as well as reuse DD in other tools.



git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@202485 91177308-0d34-0410-b5e6-96231b3b80d8

11 files changed, 307 insertions, 93 deletions

diff --git a/lib/sanitizer_common/CMakeLists.txt b/lib/sanitizer_common/CMakeLists.txt
index c62776d31..8f30f2838 100644
--- a/lib/sanitizer_common/CMakeLists.txt
+++ b/lib/sanitizer_common/CMakeLists.txt
@@ -5,6 +5,7 @@ set(SANITIZER_SOURCES
   sanitizer_allocator.cc
   sanitizer_common.cc
   sanitizer_coverage.cc
+  sanitizer_deadlock_detector1.cc
   sanitizer_flags.cc
   sanitizer_libc.cc
   sanitizer_libignore.cc
@@ -52,6 +53,7 @@ set(SANITIZER_HEADERS
   sanitizer_common_interceptors_format.inc
   sanitizer_common_syscalls.inc
   sanitizer_deadlock_detector.h
+  sanitizer_deadlock_detector_interface.h
   sanitizer_flags.h
   sanitizer_internal_defs.h
   sanitizer_lfstack.h
diff --git a/lib/sanitizer_common/sanitizer_deadlock_detector1.cc b/lib/sanitizer_common/sanitizer_deadlock_detector1.cc
new file mode 100644
index 000000000..ba03e0d74
--- /dev/null
+++ b/lib/sanitizer_common/sanitizer_deadlock_detector1.cc
@@ -0,0 +1,141 @@
+//===-- sanitizer_deadlock_detector1.cc -----------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Deadlock detector implementation based on NxN adjacency bit matrix.
+//
+//===----------------------------------------------------------------------===//
+
+#include "sanitizer_deadlock_detector_interface.h"
+#include "sanitizer_deadlock_detector.h"
+#include "sanitizer_allocator_internal.h"
+#include "sanitizer_placement_new.h"
+#include "sanitizer_mutex.h"
+
+namespace __sanitizer {
+
+typedef TwoLevelBitVector<> DDBV;  // DeadlockDetector's bit vector.
+
+struct DDPhysicalThread {
+};
+
+struct DDLogicalThread {
+  u64 ctx;
+  DeadlockDetectorTLS<DDBV> dd;
+  DDReport rep;
+};
+
+struct DDetectorImpl : public DDetector {
+  SpinMutex mtx;
+  DeadlockDetector<DDBV> dd;
+
+  DDetectorImpl();
+
+  virtual DDPhysicalThread* CreatePhysicalThread();
+  virtual void DestroyPhysicalThread(DDPhysicalThread *pt);
+
+  virtual DDLogicalThread* CreateLogicalThread(u64 ctx);
+  virtual void DestroyLogicalThread(DDLogicalThread *lt);
+
+  virtual void MutexInit(DDMutex *m, u32 stk, u64 ctx);
+  virtual DDReport *MutexLock(DDPhysicalThread *pt, DDLogicalThread *lt,
+      DDMutex *m, bool writelock, bool trylock);
+  virtual DDReport *MutexUnlock(DDPhysicalThread *pt, DDLogicalThread *lt,
+      DDMutex *m, bool writelock);
+  virtual void MutexDestroy(DDPhysicalThread *pt, DDLogicalThread *lt,
+      DDMutex *m);
+
+  void MutexEnsureID(DDLogicalThread *lt, DDMutex *m);
+};
+
+DDetector *DDetector::Create() {
+  void *mem = MmapOrDie(sizeof(DDetectorImpl), "deadlock detector");
+  return new(mem) DDetectorImpl();
+}
+
+DDetectorImpl::DDetectorImpl() {
+  dd.clear();
+}
+
+DDPhysicalThread* DDetectorImpl::CreatePhysicalThread() {
+  return 0;
+}
+
+void DDetectorImpl::DestroyPhysicalThread(DDPhysicalThread *pt) {
+}
+
+DDLogicalThread* DDetectorImpl::CreateLogicalThread(u64 ctx) {
+  DDLogicalThread *lt = (DDLogicalThread*)InternalAlloc(sizeof(*lt));
+  lt->ctx = ctx;
+  lt->dd.clear();
+  return lt;
+}
+
+void DDetectorImpl::DestroyLogicalThread(DDLogicalThread *lt) {
+  lt->~DDLogicalThread();
+  InternalFree(lt);
+}
+
+void DDetectorImpl::MutexInit(DDMutex *m, u32 stk, u64 ctx) {
+  m->id = 0;
+  m->stk = stk;
+  m->ctx = ctx;
+}
+
+void DDetectorImpl::MutexEnsureID(DDLogicalThread *lt, DDMutex *m) {
+  if (!dd.nodeBelongsToCurrentEpoch(m->id))
+    m->id = dd.newNode(reinterpret_cast<uptr>(m));
+  dd.ensureCurrentEpoch(&lt->dd);
+}
+
+DDReport *DDetectorImpl::MutexLock(DDPhysicalThread *pt, DDLogicalThread *lt,
+    DDMutex *m, bool writelock, bool trylock) {
+  SpinMutexLock lk(&mtx);
+  MutexEnsureID(lt, m);
+  CHECK(!dd.isHeld(&lt->dd, m->id));
+  // Printf("T%d MutexLock:   %zx\n", thr->tid, s->deadlock_detector_id);
+  bool has_deadlock = trylock
+      ? dd.onTryLock(&lt->dd, m->id)
+       : dd.onLock(&lt->dd, m->id);
+  DDReport *rep = 0;
+  if (has_deadlock) {
+    uptr path[10];
+    uptr len = dd.findPathToHeldLock(&lt->dd, m->id,
+                                          path, ARRAY_SIZE(path));
+    CHECK_GT(len, 0U);  // Hm.. cycle of 10 locks? I'd like to see that.
+    rep = &lt->rep;
+    rep->n = len;
+    for (uptr i = 0; i < len; i++) {
+      DDMutex *m0 = (DDMutex*)dd.getData(path[i]);
+      DDMutex *m1 = (DDMutex*)dd.getData(path[i < len - 1 ? i + 1 : 0]);
+      rep->loop[i].thr_ctx = 0;  // don't know
+      rep->loop[i].mtx_ctx0 = m0->ctx;
+      rep->loop[i].mtx_ctx1 = m1->ctx;
+      rep->loop[i].stk = m0->stk;
+    }
+  }
+  return rep;
+}
+
+DDReport *DDetectorImpl::MutexUnlock(DDPhysicalThread *pt, DDLogicalThread *lt,
+    DDMutex *m, bool writelock) {
+  // Printf("T%d MutexUnlock: %zx; recursion %d\n", thr->tid,
+  //        s->deadlock_detector_id, s->recursion);
+  dd.onUnlock(&lt->dd, m->id);
+  return 0;
+}
+
+void DDetectorImpl::MutexDestroy(DDPhysicalThread *pt, DDLogicalThread *lt,
+    DDMutex *m) {
+  SpinMutexLock lk(&mtx);
+  if (dd.nodeBelongsToCurrentEpoch(m->id))
+    dd.removeNode(m->id);
+  m->id = 0;
+}
+
+}  // namespace __sanitizer
diff --git a/lib/sanitizer_common/sanitizer_deadlock_detector_interface.h b/lib/sanitizer_common/sanitizer_deadlock_detector_interface.h
new file mode 100644
index 000000000..9c585c30f
--- /dev/null
+++ b/lib/sanitizer_common/sanitizer_deadlock_detector_interface.h
@@ -0,0 +1,66 @@
+//===-- sanitizer_deadlock_detector_interface.h -----------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of Sanitizer runtime.
+// Abstract deadlock detector interface.
+// FIXME: this is work in progress, nothing really works yet.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef SANITIZER_DEADLOCK_DETECTOR_INTERFACE_H
+#define SANITIZER_DEADLOCK_DETECTOR_INTERFACE_H
+
+#include "sanitizer_internal_defs.h"
+
+namespace __sanitizer {
+
+// dd - deadlock detector.
+// lt - logical (user) thread.
+// pt - physical (OS) thread.
+
+struct DDMutex {
+  uptr id;
+  u32  stk;  // creation (or any other) stack that indentifies the mutex
+  u64  ctx;  // user context
+};
+
+struct DDReport {
+  int n;  // number of entries in loop
+  struct {
+    u64 thr_ctx;   // user thread context
+    u64 mtx_ctx0;  // user mutex context, start of the edge
+    u64 mtx_ctx1;  // user mutex context, end of the edge
+    u32 stk;       // stack id for the edge
+  } loop[16];
+};
+
+struct DDPhysicalThread;
+struct DDLogicalThread;
+
+struct DDetector {
+  static DDetector *Create();
+
+  virtual DDPhysicalThread* CreatePhysicalThread() { return 0; }
+  virtual void DestroyPhysicalThread(DDPhysicalThread *pt) {}
+
+  virtual DDLogicalThread* CreateLogicalThread(u64 ctx) { return 0; }
+  virtual void DestroyLogicalThread(DDLogicalThread *lt) {}
+
+  virtual void MutexInit(DDMutex *m, u32 stk, u64 ctx) {}
+  virtual DDReport *MutexLock(DDPhysicalThread *pt, DDLogicalThread *lt,
+      DDMutex *m, bool writelock, bool trylock) { return 0; }
+  virtual DDReport *MutexUnlock(DDPhysicalThread *pt, DDLogicalThread *lt,
+      DDMutex *m, bool writelock) { return 0; }
+  virtual void MutexDestroy(DDPhysicalThread *pt, DDLogicalThread *lt,
+      DDMutex *m) {}
+};
+
+} // namespace __sanitizer
+
+#endif // SANITIZER_DEADLOCK_DETECTOR_INTERFACE_H
diff --git a/lib/tsan/go/buildgo.sh b/lib/tsan/go/buildgo.sh
index 95b2ac114..71191a321 100755
--- a/lib/tsan/go/buildgo.sh
+++ b/lib/tsan/go/buildgo.sh
@@ -17,6 +17,7 @@ SRCS="
 	../rtl/tsan_sync.cc
 	../../sanitizer_common/sanitizer_allocator.cc
 	../../sanitizer_common/sanitizer_common.cc
+	../../sanitizer_common/sanitizer_deadlock_detector1.cc
 	../../sanitizer_common/sanitizer_flags.cc
 	../../sanitizer_common/sanitizer_libc.cc
 	../../sanitizer_common/sanitizer_printf.cc
diff --git a/lib/tsan/rtl/tsan_rtl.cc b/lib/tsan/rtl/tsan_rtl.cc
index 5dd45fc65..b4bf10c2b 100644
--- a/lib/tsan/rtl/tsan_rtl.cc
+++ b/lib/tsan/rtl/tsan_rtl.cc
@@ -82,9 +82,7 @@ Context::Context()
       CreateThreadContext, kMaxTid, kThreadQuarantineSize))
   , racy_stacks(MBlockRacyStacks)
   , racy_addresses(MBlockRacyAddresses)
-  , fired_suppressions(8)
-  , dd_mtx(MutexTypeDDetector, StatMtxDeadlockDetector) {
-  dd.clear();
+  , fired_suppressions(8) {
 }
 
 // The objects are allocated in TLS, so one may rely on zero-initialization.
@@ -252,6 +250,8 @@ void Initialize(ThreadState *thr) {
   Symbolizer::Get()->AddHooks(EnterSymbolizer, ExitSymbolizer);
 #endif
   internal_start_thread(&BackgroundThread, 0);
+  if (flags()->detect_deadlocks)
+    ctx->dd = DDetector::Create();
 
   if (ctx->flags.verbosity)
     Printf("***** Running under ThreadSanitizer v2 (pid %d) *****\n",
diff --git a/lib/tsan/rtl/tsan_rtl.h b/lib/tsan/rtl/tsan_rtl.h
index 069838b5d..bba54936a 100644
--- a/lib/tsan/rtl/tsan_rtl.h
+++ b/lib/tsan/rtl/tsan_rtl.h
@@ -30,7 +30,7 @@
 #include "sanitizer_common/sanitizer_allocator_internal.h"
 #include "sanitizer_common/sanitizer_asm.h"
 #include "sanitizer_common/sanitizer_common.h"
-#include "sanitizer_common/sanitizer_deadlock_detector.h"
+#include "sanitizer_common/sanitizer_deadlock_detector_interface.h"
 #include "sanitizer_common/sanitizer_libignore.h"
 #include "sanitizer_common/sanitizer_suppressions.h"
 #include "sanitizer_common/sanitizer_thread_registry.h"
@@ -390,8 +390,6 @@ class Shadow : public FastState {
 
 struct SignalContext;
 
-typedef TwoLevelBitVector<> DDBV;  // DeadlockDetector's bit vector.
-
 struct JmpBuf {
   uptr sp;
   uptr mangled_sp;
@@ -453,7 +451,8 @@ struct ThreadState {
   ThreadContext *tctx;
 
   InternalDeadlockDetector internal_deadlock_detector;
-  __sanitizer::DeadlockDetectorTLS<DDBV> deadlock_detector_tls;
+  DDPhysicalThread *dd_pt;
+  DDLogicalThread *dd_lt;
 
   bool in_signal_handler;
   SignalContext *signal_ctx;
@@ -548,9 +547,7 @@ struct Context {
   Vector<RacyAddress> racy_addresses;
   // Number of fired suppressions may be large enough.
   InternalMmapVector<FiredSuppression> fired_suppressions;
-
-  __sanitizer::DeadlockDetector<DDBV> dd;
-  Mutex dd_mtx;
+  DDetector *dd;
 
   Flags flags;
 
@@ -583,6 +580,7 @@ class ScopedReport {
                        const MutexSet *mset);
   void AddThread(const ThreadContext *tctx);
   void AddMutex(const SyncVar *s);
+  u64 AddMutex(u64 id);
   void AddLocation(uptr addr, uptr size);
   void AddSleep(u32 stack_id);
   void SetCount(int count);
@@ -596,7 +594,7 @@ class ScopedReport {
   // at best it will cause deadlocks on internal mutexes.
   ScopedIgnoreInterceptors ignore_interceptors_;
 
-  void AddMutex(u64 id);
+  void AddDeadMutex(u64 id);
 
   ScopedReport(const ScopedReport&);
   void operator = (const ScopedReport&);
diff --git a/lib/tsan/rtl/tsan_rtl_mutex.cc b/lib/tsan/rtl/tsan_rtl_mutex.cc
index c33328126..fbbd5ee46 100644
--- a/lib/tsan/rtl/tsan_rtl_mutex.cc
+++ b/lib/tsan/rtl/tsan_rtl_mutex.cc
@@ -11,7 +11,7 @@
 //
 //===----------------------------------------------------------------------===//
 
-#include <sanitizer_common/sanitizer_deadlock_detector.h>
+#include <sanitizer_common/sanitizer_deadlock_detector_interface.h>
 
 #include "tsan_rtl.h"
 #include "tsan_flags.h"
@@ -22,50 +22,7 @@
 
 namespace __tsan {
 
-static void EnsureDeadlockDetectorID(Context *ctx, ThreadState *thr,
-                                     SyncVar *s) {
-  if (!ctx->dd.nodeBelongsToCurrentEpoch(s->deadlock_detector_id))
-    s->deadlock_detector_id = ctx->dd.newNode(reinterpret_cast<uptr>(s));
-  ctx->dd.ensureCurrentEpoch(&thr->deadlock_detector_tls);
-}
-
-static void DDUnlock(Context *ctx, ThreadState *thr, SyncVar *s) {
-  if (!common_flags()->detect_deadlocks) return;
-  if (s->recursion != 0) return;
-  // Printf("T%d MutexUnlock: %zx; recursion %d\n", thr->tid,
-  //        s->deadlock_detector_id, s->recursion);
-  ctx->dd.onUnlock(&thr->deadlock_detector_tls, s->deadlock_detector_id);
-}
-
-static void DDLock(Context *ctx, ThreadState *thr, SyncVar *s, uptr pc,
-                   bool try_lock) {
-  if (!common_flags()->detect_deadlocks) return;
-  if (s->recursion > 1) return;
-  Lock lk(&ctx->dd_mtx);
-  EnsureDeadlockDetectorID(ctx, thr, s);
-  CHECK(!ctx->dd.isHeld(&thr->deadlock_detector_tls, s->deadlock_detector_id));
-  // Printf("T%d MutexLock:   %zx\n", thr->tid, s->deadlock_detector_id);
-  bool has_deadlock = try_lock
-      ? ctx->dd.onTryLock(&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 = 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<SyncVar*>(ctx->dd.getData(path[i])));
-    StackTrace trace;
-    trace.ObtainCurrent(thr, pc);
-    rep.AddStack(&trace);
-    OutputReport(CTX(), rep);
-  }
-}
+void ReportDeadlockReport(ThreadState *thr, uptr pc, DDReport *r);
 
 void MutexCreate(ThreadState *thr, uptr pc, uptr addr,
                  bool rw, bool recursive, bool linker_init) {
@@ -98,12 +55,8 @@ void MutexDestroy(ThreadState *thr, uptr pc, uptr addr) {
   SyncVar *s = ctx->synctab.GetAndRemove(thr, pc, addr);
   if (s == 0)
     return;
-  if (common_flags()->detect_deadlocks) {
-    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 (flags()->detect_deadlocks)
+    ctx->dd->MutexDestroy(thr->dd_pt, thr->dd_lt, &s->dd);
   if (IsAppMem(addr)) {
     CHECK(!thr->is_freeing);
     thr->is_freeing = true;
@@ -158,8 +111,12 @@ void MutexLock(ThreadState *thr, uptr pc, uptr addr, int rec, bool try_lock) {
   }
   s->recursion += rec;
   thr->mset.Add(s->GetId(), true, thr->fast_state.epoch());
-  DDLock(ctx, thr, s, pc, try_lock);
+  DDReport *dd_rep = 0;
+  if (flags()->detect_deadlocks && s->recursion == 1)
+    dd_rep = ctx->dd->MutexLock(thr->dd_pt, thr->dd_lt, &s->dd, true, try_lock);
   s->mtx.Unlock();
+  if (dd_rep)
+    ReportDeadlockReport(thr, pc, dd_rep);
 }
 
 int MutexUnlock(ThreadState *thr, uptr pc, uptr addr, bool all) {
@@ -196,17 +153,22 @@ int MutexUnlock(ThreadState *thr, uptr pc, uptr addr, bool all) {
     }
   }
   thr->mset.Del(s->GetId(), true);
-  DDUnlock(ctx, thr, s);
+  DDReport *dd_rep = 0;
+  if (flags()->detect_deadlocks && s->recursion == 0)
+    dd_rep = ctx->dd->MutexUnlock(thr->dd_pt, thr->dd_lt, &s->dd, true);
   s->mtx.Unlock();
+  if (dd_rep)
+    ReportDeadlockReport(thr, pc, dd_rep);
   return rec;
 }
 
-void MutexReadLock(ThreadState *thr, uptr pc, uptr addr, bool try_lock) {
+void MutexReadLock(ThreadState *thr, uptr pc, uptr addr, bool trylock) {
+  Context *ctx = CTX();
   DPrintf("#%d: MutexReadLock %zx\n", thr->tid, addr);
   StatInc(thr, StatMutexReadLock);
   if (IsAppMem(addr))
     MemoryReadAtomic(thr, pc, addr, kSizeLog1);
-  SyncVar *s = CTX()->synctab.GetOrCreateAndLock(thr, pc, addr, false);
+  SyncVar *s = ctx->synctab.GetOrCreateAndLock(thr, pc, addr, false);
   thr->fast_state.IncrementEpoch();
   TraceAddEvent(thr, thr->fast_state, EventTypeRLock, s->GetId());
   if (s->owner_tid != SyncVar::kInvalidTid) {
@@ -217,16 +179,21 @@ void MutexReadLock(ThreadState *thr, uptr pc, uptr addr, bool try_lock) {
   AcquireImpl(thr, pc, &s->clock);
   s->last_lock = thr->fast_state.raw();
   thr->mset.Add(s->GetId(), false, thr->fast_state.epoch());
-  DDLock(CTX(), thr, s, pc, try_lock);
+  DDReport *dd_rep = 0;
+  if (flags()->detect_deadlocks && s->recursion == 0)
+    dd_rep = ctx->dd->MutexLock(thr->dd_pt, thr->dd_lt, &s->dd, false, trylock);
   s->mtx.ReadUnlock();
+  if (dd_rep)
+    ReportDeadlockReport(thr, pc, dd_rep);
 }
 
 void MutexReadUnlock(ThreadState *thr, uptr pc, uptr addr) {
+  Context *ctx = CTX();
   DPrintf("#%d: MutexReadUnlock %zx\n", thr->tid, addr);
   StatInc(thr, StatMutexReadUnlock);
   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, EventTypeRUnlock, s->GetId());
   if (s->owner_tid != SyncVar::kInvalidTid) {
@@ -235,16 +202,21 @@ void MutexReadUnlock(ThreadState *thr, uptr pc, uptr addr) {
     PrintCurrentStack(thr, pc);
   }
   ReleaseImpl(thr, pc, &s->read_clock);
-  DDUnlock(CTX(), thr, s);
+  DDReport *dd_rep = 0;
+  if (flags()->detect_deadlocks && s->recursion == 0)
+    dd_rep = ctx->dd->MutexUnlock(thr->dd_pt, thr->dd_lt, &s->dd, false);
   s->mtx.Unlock();
   thr->mset.Del(s->GetId(), false);
+  if (dd_rep)
+    ReportDeadlockReport(thr, pc, dd_rep);
 }
 
 void MutexReadOrWriteUnlock(ThreadState *thr, uptr pc, uptr addr) {
+  Context *ctx = CTX();
   DPrintf("#%d: MutexReadOrWriteUnlock %zx\n", thr->tid, addr);
   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);
   bool write = true;
   if (s->owner_tid == SyncVar::kInvalidTid) {
     // Seems to be read unlock.
@@ -273,8 +245,12 @@ void MutexReadOrWriteUnlock(ThreadState *thr, uptr pc, uptr addr) {
     PrintCurrentStack(thr, pc);
   }
   thr->mset.Del(s->GetId(), write);
-  DDUnlock(CTX(), thr, s);
+  DDReport *dd_rep = 0;
+  if (flags()->detect_deadlocks && s->recursion == 0)
+    dd_rep = ctx->dd->MutexUnlock(thr->dd_pt, thr->dd_lt, &s->dd, write);
   s->mtx.Unlock();
+  if (dd_rep)
+    ReportDeadlockReport(thr, pc, dd_rep);
 }
 
 void MutexRepair(ThreadState *thr, uptr pc, uptr addr) {
@@ -394,4 +370,16 @@ void AcquireReleaseImpl(ThreadState *thr, uptr pc, SyncClock *c) {
   StatInc(thr, StatSyncRelease);
 }
 
+void ReportDeadlockReport(ThreadState *thr, uptr pc, DDReport *r) {
+  Context *ctx = CTX();
+  ThreadRegistryLock l(ctx->thread_registry);
+  ScopedReport rep(ReportTypeDeadlock);
+  for (int i = 0; i < r->n; i++)
+    rep.AddMutex(r->loop[i].mtx_ctx0);
+  StackTrace trace;
+  trace.ObtainCurrent(thr, pc);
+  rep.AddStack(&trace);
+  OutputReport(ctx, rep);
+}
+
 }  // namespace __tsan
diff --git a/lib/tsan/rtl/tsan_rtl_report.cc b/lib/tsan/rtl/tsan_rtl_report.cc
index a892f4297..795317358 100644
--- a/lib/tsan/rtl/tsan_rtl_report.cc
+++ b/lib/tsan/rtl/tsan_rtl_report.cc
@@ -181,23 +181,9 @@ void ScopedReport::AddMemoryAccess(uptr addr, Shadow s,
   mop->stack = SymbolizeStack(*stack);
   for (uptr i = 0; i < mset->Size(); i++) {
     MutexSet::Desc d = mset->Get(i);
-    u64 uid = 0;
-    uptr addr = SyncVar::SplitId(d.id, &uid);
-    SyncVar *s = ctx_->synctab.GetIfExistsAndLock(addr, false);
-    // Check that the mutex is still alive.
-    // Another mutex can be created at the same address,
-    // so check uid as well.
-    if (s && s->CheckId(uid)) {
-      ReportMopMutex mtx = {s->uid, d.write};
-      mop->mset.PushBack(mtx);
-      AddMutex(s);
-    } else {
-      ReportMopMutex mtx = {d.id, d.write};
-      mop->mset.PushBack(mtx);
-      AddMutex(d.id);
-    }
-    if (s)
-      s->mtx.ReadUnlock();
+    u64 mid = this->AddMutex(d.id);
+    ReportMopMutex mtx = {mid, d.write};
+    mop->mset.PushBack(mtx);
   }
 }
 
@@ -286,7 +272,26 @@ void ScopedReport::AddMutex(const SyncVar *s) {
 #endif
 }
 
-void ScopedReport::AddMutex(u64 id) {
+u64 ScopedReport::AddMutex(u64 id) {
+  u64 uid = 0;
+  u64 mid = id;
+  uptr addr = SyncVar::SplitId(id, &uid);
+  SyncVar *s = ctx_->synctab.GetIfExistsAndLock(addr, false);
+  // Check that the mutex is still alive.
+  // Another mutex can be created at the same address,
+  // so check uid as well.
+  if (s && s->CheckId(uid)) {
+    mid = s->uid;
+    AddMutex(s);
+  } else {
+    AddDeadMutex(id);
+  }
+  if (s)
+    s->mtx.ReadUnlock();
+  return mid;
+}
+
+void ScopedReport::AddDeadMutex(u64 id) {
   for (uptr i = 0; i < rep_->mutexes.Size(); i++) {
     if (rep_->mutexes[i]->id == id)
       return;
diff --git a/lib/tsan/rtl/tsan_rtl_thread.cc b/lib/tsan/rtl/tsan_rtl_thread.cc
index f41ed50dd..abf68ca3b 100644
--- a/lib/tsan/rtl/tsan_rtl_thread.cc
+++ b/lib/tsan/rtl/tsan_rtl_thread.cc
@@ -83,13 +83,14 @@ struct OnStartedArgs {
 };
 
 void ThreadContext::OnStarted(void *arg) {
+  Context *ctx = CTX();
   OnStartedArgs *args = static_cast<OnStartedArgs*>(arg);
   thr = args->thr;
   // RoundUp so that one trace part does not contain events
   // from different threads.
   epoch0 = RoundUp(epoch1 + 1, kTracePartSize);
   epoch1 = (u64)-1;
-  new(thr) ThreadState(CTX(), tid, unique_id,
+  new(thr) ThreadState(ctx, tid, unique_id,
       epoch0, args->stk_addr, args->stk_size, args->tls_addr, args->tls_size);
 #ifndef TSAN_GO
   thr->shadow_stack = &ThreadTrace(thr->tid)->shadow_stack[0];
@@ -106,6 +107,10 @@ void ThreadContext::OnStarted(void *arg) {
 #ifndef TSAN_GO
   AllocatorThreadStart(thr);
 #endif
+  if (flags()->detect_deadlocks) {
+    thr->dd_pt = ctx->dd->CreatePhysicalThread();
+    thr->dd_lt = ctx->dd->CreateLogicalThread(unique_id);
+  }
   thr->fast_synch_epoch = epoch0;
   AcquireImpl(thr, 0, &sync);
   thr->fast_state.SetHistorySize(flags()->history_size);
@@ -122,6 +127,7 @@ void ThreadContext::OnStarted(void *arg) {
 }
 
 void ThreadContext::OnFinished() {
+  Context *ctx = CTX();
   if (!detached) {
     thr->fast_state.IncrementEpoch();
     // Can't increment epoch w/o writing to the trace as well.
@@ -130,11 +136,15 @@ void ThreadContext::OnFinished() {
   }
   epoch1 = thr->fast_state.epoch();
 
+  if (flags()->detect_deadlocks) {
+    ctx->dd->DestroyPhysicalThread(thr->dd_pt);
+    ctx->dd->DestroyLogicalThread(thr->dd_lt);
+  }
 #ifndef TSAN_GO
   AllocatorThreadFinish(thr);
 #endif
   thr->~ThreadState();
-  StatAggregate(CTX()->stat, thr->stat);
+  StatAggregate(ctx->stat, thr->stat);
   thr = 0;
 }
 
diff --git a/lib/tsan/rtl/tsan_sync.cc b/lib/tsan/rtl/tsan_sync.cc
index 6def3c124..1fe72c819 100644
--- a/lib/tsan/rtl/tsan_sync.cc
+++ b/lib/tsan/rtl/tsan_sync.cc
@@ -58,14 +58,16 @@ SyncVar* SyncTab::GetIfExistsAndLock(uptr addr, bool write_lock) {
 }
 
 SyncVar* SyncTab::Create(ThreadState *thr, uptr pc, uptr addr) {
+  Context *ctx = CTX();
   StatInc(thr, StatSyncCreated);
   void *mem = internal_alloc(MBlockSync, sizeof(SyncVar));
   const u64 uid = atomic_fetch_add(&uid_gen_, 1, memory_order_relaxed);
   SyncVar *res = new(mem) SyncVar(addr, uid);
-  res->deadlock_detector_id = 0;
 #ifndef TSAN_GO
   res->creation_stack_id = CurrentStackId(thr, pc);
 #endif
+  if (flags()->detect_deadlocks)
+    ctx->dd->MutexInit(&res->dd, res->creation_stack_id, res->GetId());
   return res;
 }
 
diff --git a/lib/tsan/rtl/tsan_sync.h b/lib/tsan/rtl/tsan_sync.h
index 2a90d2d44..707d82394 100644
--- a/lib/tsan/rtl/tsan_sync.h
+++ b/lib/tsan/rtl/tsan_sync.h
@@ -15,6 +15,7 @@
 
 #include "sanitizer_common/sanitizer_atomic.h"
 #include "sanitizer_common/sanitizer_common.h"
+#include "sanitizer_common/sanitizer_deadlock_detector_interface.h"
 #include "tsan_clock.h"
 #include "tsan_defs.h"
 #include "tsan_mutex.h"
@@ -61,7 +62,6 @@ struct SyncVar {
   SyncClock read_clock;  // Used for rw mutexes only.
   u32 creation_stack_id;
   int owner_tid;  // Set only by exclusive owners.
-  uptr deadlock_detector_id;
   u64 last_lock;
   int recursion;
   bool is_rw;
@@ -69,6 +69,7 @@ struct SyncVar {
   bool is_broken;
   bool is_linker_init;
   SyncVar *next;  // In SyncTab hashtable.
+  DDMutex dd;
 
   uptr GetMemoryConsumption();
   u64 GetId() const {