sanitizer_common: add deadlock detection to the Mutex2

[vitalybuka]

Summary

Move internal deadlock detector from tsan to sanitizer_common
so that we can switch tsan to the new mutex and remove tsan's mutex.

compiler-rt/lib/sanitizer_common/sanitizer_mutex.h

public:
 
   void Wait();
   void Post(u32 count = 1);
 
  private:
   atomic_uint32_t state_ = {0};
 };
 
+typedef int MutexType;
+
+enum {
+  // Used as sentinel and to catch unassigned types
+  // (should not be used as real Mutex type).
+  MutexInvalid = 0,
+  MutexThreadRegistry,
+  // Each tool own mutexes must start at this number.
+  MutexLastCommon,
+  // Type for legacy mutexes that are not checked for deadlocks.
+  MutexUnchecked = -1,
+  // Special marks that can be used in MutexMeta::can_lock table.
+  // The leaf mutexes can be locked under any other non-leaf mutex,
+  // but no other mutex can be locked while under a leaf mutex.
+  MutexLeaf = -1,
+  // Multiple mutexes of this type can be locked at the same time.
+  MutexMulti = -3,
+};
+
+// Go linker does not support THREADLOCAL variables,
+// so we can't use per-thread state.
+#define SANITIZER_CHECK_DEADLOCKS (SANITIZER_DEBUG && !SANITIZER_GO)
+
+#if SANITIZER_CHECK_DEADLOCKS
+struct MutexMeta {
+  MutexType type;
+  const char *name;
+  // The table fixes what mutexes can be locked under what mutexes.
+  // If the entry for MutexTypeFoo contains MutexTypeBar,
+  // then Bar mutex can be locked while under Foo mutex.
+  // Can also contain the special MutexLeaf/MutexMulti marks.
+  MutexType can_lock[10];
+};
+#endif
+
+class CheckedMutex {
+ public:
+  constexpr CheckedMutex(MutexType type)
+#if SANITIZER_CHECK_DEADLOCKS
+      : type_(type)
+#endif
+  {
+  }
+
+  ALWAYS_INLINE void Lock() {
+#if SANITIZER_CHECK_DEADLOCKS
+    LockImpl(GET_CALLER_PC());
+#endif
+  }
+
+  ALWAYS_INLINE void Unlock() {
+#if SANITIZER_CHECK_DEADLOCKS
+    UnlockImpl();
+#endif
+  }
+
+  // Checks that the current thread does not hold any mutexes
+  // (e.g. when returning from a runtime function to user code).
+  static void CheckNoLocks() {
+#if SANITIZER_CHECK_DEADLOCKS
+    CheckNoLocksImpl();
+#endif
+  }
+
+ private:
+#if SANITIZER_CHECK_DEADLOCKS
+  const MutexType type_;
+
+  void LockImpl(uptr pc);
+  void UnlockImpl();
+  static void CheckNoLocksImpl();
+#endif
+};
+
 // Reader-writer mutex.
-class MUTEX Mutex2 {
+class MUTEX Mutex2 : CheckedMutex {
  public:
-  constexpr Mutex2() {}
+  constexpr Mutex2(MutexType type = MutexUnchecked) : CheckedMutex(type) {}
 
   void Lock() ACQUIRE() {
+    CheckedMutex::Lock();
     u64 reset_mask = ~0ull;
     u64 state = atomic_load_relaxed(&state_);
     const uptr kMaxSpinIters = 1500;
     for (uptr spin_iters = 0;; spin_iters++) {
       u64 new_state;
       bool locked = (state & (kWriterLock | kReaderLockMask)) != 0;
       if (LIKELY(!locked)) {
         // The mutex is not read-/write-locked, try to lock.
for (uptr spin_iters = 0;; spin_iters++) {
       // or we just spun but set kWriterSpinWait.
       // Either way we need to reset kWriterSpinWait
       // next time we take the lock or block again.
       reset_mask = ~kWriterSpinWait;
     }
   }
 
   void Unlock() RELEASE() {
+    CheckedMutex::Unlock();
     bool wake_writer;
     u64 wake_readers;
     u64 new_state;
     u64 state = atomic_load_relaxed(&state_);
     do {
       DCHECK_NE(state & kWriterLock, 0);
       DCHECK_EQ(state & kReaderLockMask, 0);
       new_state = state & ~kWriterLock;
do {
                                                     memory_order_release)));
     if (UNLIKELY(wake_writer))
       writers_.Post();
     else if (UNLIKELY(wake_readers))
       readers_.Post(wake_readers);
   }
 
   void ReadLock() ACQUIRE_SHARED() {
+    CheckedMutex::Lock();
     bool locked;
     u64 new_state;
     u64 state = atomic_load_relaxed(&state_);
     do {
       locked =
           (state & kReaderLockMask) == 0 &&
           (state & (kWriterLock | kWriterSpinWait | kWaitingWriterMask)) != 0;
       if (LIKELY(!locked))
         new_state = state + kReaderLockInc;
       else
         new_state = state + kWaitingReaderInc;
     } while (UNLIKELY(!atomic_compare_exchange_weak(&state_, &state, new_state,
                                                     memory_order_acquire)));
     if (UNLIKELY(locked))
       readers_.Wait();
     DCHECK_EQ(atomic_load_relaxed(&state_) & kWriterLock, 0);
     DCHECK_NE(atomic_load_relaxed(&state_) & kReaderLockMask, 0);
   }
 
   void ReadUnlock() RELEASE_SHARED() {
+    CheckedMutex::Unlock();
     bool wake;
     u64 new_state;
     u64 state = atomic_load_relaxed(&state_);
     do {
       DCHECK_NE(state & kReaderLockMask, 0);
       DCHECK_EQ(state & (kWaitingReaderMask | kWriterLock), 0);
       new_state = state - kReaderLockInc;
       wake = (new_state & (kReaderLockMask | kWriterSpinWait)) == 0 &&

compiler-rt/lib/sanitizer_common/sanitizer_mutex.cpp

 }
 
 void Semaphore::Post(u32 count) {
   CHECK_NE(count, 0);
   atomic_fetch_add(&state_, count, memory_order_release);
   FutexWake(&state_, count);
 }
 
+#if SANITIZER_CHECK_DEADLOCKS
+// An empty mutex meta table, it effectively disables deadlock detection.
+// Each tool can override the table to define own mutex hierarchy and
+// enable deadlock detection.
+// The table defines a static mutex hierarchy (what mutexes can be locked
+// under what mutexes). This table is checked to be acyclic and then
+// actual mutex lock/unlock operations are checked to adhere to this hierarchy.
+const int kMutexTypeMax = 20;
+SANITIZER_WEAK_ATTRIBUTE MutexMeta mutex_meta[kMutexTypeMax] = {};
+SANITIZER_WEAK_ATTRIBUTE void PrintMutexPC(uptr pc) {}
+static StaticSpinMutex mutex_meta_mtx;
+static int mutex_count = -1;
+// Adjacency matrix of what mutexes can be locked under what mutexes.
+static bool mutex_can_lock[kMutexTypeMax][kMutexTypeMax];
+// Mutex types with MutexMulti mark.
+static bool mutex_multi[kMutexTypeMax];
+
+void DebugMutexInit() {
+  // Build adjacency matrix.
+  bool leaf[kMutexTypeMax];
+  internal_memset(&leaf, 0, sizeof(leaf));
+  int cnt[kMutexTypeMax] = {};
+  internal_memset(&cnt, 0, sizeof(cnt));
+  for (int t = 0;; t++) {
+    mutex_count = t;
+    CHECK_LE(mutex_count, kMutexTypeMax);
+    if (!mutex_meta[t].name)
+      break;
+    CHECK_EQ(t, mutex_meta[t].type);
+    for (uptr j = 0; j < ARRAY_SIZE(mutex_meta[t].can_lock); j++) {
+      MutexType z = mutex_meta[t].can_lock[j];
+      if (z == MutexInvalid)
+        break;
+      if (z == MutexLeaf) {
+        CHECK(!leaf[t]);
+        leaf[t] = true;
+        continue;
+      }
+      if (z == MutexMulti) {
+        mutex_multi[t] = true;
+        continue;
+      }
+      CHECK_LT(z, kMutexTypeMax);
+      CHECK(!mutex_can_lock[t][z]);
+      mutex_can_lock[t][z] = true;
+      cnt[t]++;
+    }
+  }
+  // Add leaf mutexes.
+  for (int t = 0; t < mutex_count; t++) {
+    if (!leaf[t])
+      continue;
+    CHECK_EQ(cnt[t], 0);
+    for (int z = 0; z < mutex_count; z++) {
+      if (z == MutexInvalid || t == z || leaf[z])
+        continue;
+      CHECK(!mutex_can_lock[z][t]);
+      mutex_can_lock[z][t] = true;
+    }
+  }
+  // Build the transitive closure and check that the graphs is acyclic.
+  // The table is too large for stack allocation.
+  u32 trans[kMutexTypeMax];
+  static_assert(sizeof(trans[0]) * 8 >= kMutexTypeMax,
+                "kMutexTypeMax does not fit into u32, switch to u64");
+  internal_memset(&trans, 0, sizeof(trans));
+  for (int i = 0; i < mutex_count; i++) {
+    for (int j = 0; j < mutex_count; j++)
+      if (mutex_can_lock[i][j])
+        trans[i] |= 1 << j;
+  }
+  for (int k = 0; k < mutex_count; k++) {
+    for (int i = 0; i < mutex_count; i++) {
+      if (trans[i] & (1 << k))
+        trans[i] |= trans[k];
+    }
+  }
+  for (int i = 0; i < mutex_count; i++) {
+    if (trans[i] & (1 << i)) {
+      Printf("Mutex %s participates in a cycle\n", mutex_meta[i].name);
+      Die();
+    }
+  }
+}
+
+struct InternalDeadlockDetector {
+  struct LockDesc {
+    u64 seq;
+    uptr pc;
+    int recursion;
+  };
+  int initialized;
+  u64 sequence;
+  LockDesc locked[kMutexTypeMax];
+
+  void Lock(MutexType type, uptr pc) {
+    if (!Initialize(type))
+      return;
+    CHECK_LT(type, mutex_count);
+    // Find the last locked mutex type.
+    // This is the type we will use for hierarchy checks.
+    u64 max_seq = 0;
+    MutexType max_idx = MutexInvalid;
+    for (int i = 0; i != mutex_count; i++) {
+      if (locked[i].seq == 0)
+        continue;
+      CHECK_NE(locked[i].seq, max_seq);
+      if (max_seq < locked[i].seq) {
+        max_seq = locked[i].seq;
+        max_idx = (MutexType)i;
+      }
+    }
+    if (max_idx == type && mutex_multi[type]) {
+      // Recursive lock of the same type.
+      CHECK_EQ(locked[type].seq, max_seq);
+      CHECK(locked[type].pc);
+      locked[type].recursion++;
+      return;
+    }
+    if (max_idx != MutexInvalid && !mutex_can_lock[max_idx][type]) {
+      Printf("%s: internal deadlock: can't lock %s under %s mutex\n",
+             SanitizerToolName, mutex_meta[type].name,
+             mutex_meta[max_idx].name);
+      PrintMutexPC(pc);
+      CHECK(0);
+    }
+    locked[type].seq = ++sequence;
+    locked[type].pc = pc;
+    locked[type].recursion = 1;
+  }
+
+  void Unlock(MutexType type) {
+    if (!Initialize(type))
+      return;
+    CHECK_LT(type, mutex_count);
+    CHECK(locked[type].seq);
+    CHECK_GT(locked[type].recursion, 0);
+    if (--locked[type].recursion)
+      return;
+    locked[type].seq = 0;
+    locked[type].pc = 0;
+  }
+
+  void CheckNoLocks() {
+    for (int i = 0; i < mutex_count; i++) CHECK_EQ(locked[i].recursion, 0);
+  }
+
+  bool Initialize(MutexType type) {
+    if (type == MutexUnchecked || type == MutexInvalid)
+      return false;
+    CHECK_GT(type, MutexInvalid);
+    if (initialized != 0)
+      return initialized > 0;
+    initialized = -1;
+    SpinMutexLock lock(&mutex_meta_mtx);
+    if (mutex_count < 0)
+      DebugMutexInit();
+    initialized = mutex_count ? 1 : -1;
+    return initialized > 0;
+  }
+};
+
+THREADLOCAL InternalDeadlockDetector deadlock_detector;
+
+void CheckedMutex::LockImpl(uptr pc) { deadlock_detector.Lock(type_, pc); }
+
+void CheckedMutex::UnlockImpl() { deadlock_detector.Unlock(type_); }
+
+void CheckedMutex::CheckNoLocksImpl() { deadlock_detector.CheckNoLocks(); }
+#endif
+
 }  // namespace __sanitizer