sanitizer_common: add deadlock detection to the Mutex2

[dvyukov]

Summary

Copy internal deadlock detector from tsan to sanitizer_common
(with some cosmetic changes).
Tsan version will be deleted in subsequent changes.
This allows us to switch tsan to the sanitizer_common mutex
and remove tsan's mutex.

[dvyukov]

re-upload in the hope that arc will auto-set dependent reviews

[dvyukov]

reupload

[melver]

compiler-rt/lib/sanitizer_common/sanitizer_mutex.cpp

58

should this be 'static constexpr' ?

[vitalybuka]

Summary says: "Move internal deadlock", but the patch only adds new code

[dvyukov]

s/const/static constexpr/ and update commit description

[dvyukov]

PTAL

[dvyukov]

In D106546#2896967, @vitalybuka wrote:

Summary says: "Move internal deadlock", but the patch only adds new code

Updated commit description

[vitalybuka]

compiler-rt/lib/sanitizer_common/sanitizer_mutex.cpp

76

if mutex_count == kMutexTypeMax
if (!mutex_meta[t].name) will overflow?

Why it can't just?
for (int t = 0; t < kMutexTypeMax; t++) {

[dvyukov]

fixed CHECK_LE(mutex_count, kMutexTypeMax);

[dvyukov]

compiler-rt/lib/sanitizer_common/sanitizer_mutex.cpp

76

I guess that needed to be CHECK_LT.
The original reason for this code is that I declared:

SANITIZER_WEAK_ATTRIBUTE MutexMeta mutex_meta[] = {{}};

(array with 1 element)
but this made compilers generate some wild code because they assumed the array is const size and has 1 element. But in reality its overriden in tsan with a different size. Compilers didn't understand the intention behind the WEAK part.

Now with mutex_meta[kMutexTypeMax] we can do this.
Done. PTAL

[melver]

compiler-rt/lib/sanitizer_common/sanitizer_mutex.cpp

59

Given this is just the dummy, could this be mutex_meta[1] ? I think in the case that this is not overridden, the DebugMutexInit loop will just immediately see !mutex_meta[0].name, right?

76

We might still overflow with the improved loop if the overridden version has <kMutexTypeMax elements and no terminator (unless I misunderstand how weak linking works for arrays). I think the previous version was correct, because it is impossible to know what the size of the override array is.

Do we now still have a CHECK-fail if the last element was not the terminating element? Because otherwise somebody might keep adding entries and they will just be ignored.

Non-dummy arrays of mutex_meta should therefore actually be able to have up to kMutexTypeMax+1 elements to be checked, where the last one should always be the terminator.

[melver]

compiler-rt/lib/sanitizer_common/sanitizer_mutex.cpp

59

Never mind, I just saw your comment about miscompilation.

[dvyukov]

compiler-rt/lib/sanitizer_common/sanitizer_mutex.cpp

76

What about adding CHECK_LT(mutex_count, kMutexTypeMax) after the loop? It will catch "too many" types.

[melver]

compiler-rt/lib/sanitizer_common/sanitizer_mutex.cpp

76

An override array can have up to kMutexTypeMax+1 elements with +1 being the terminator. Otherwise kMutexTypeMax is not the max, and the other arrays are wasting space.

I think to fix:

• iterate kMutexTypeMax+1 elements.
• add CHECK_LE(mutex_count, kMutexTypeMax) after loop.

The dummy mutex_meta might need a size-change to kMutexTypeMax+1 in case the compiler decides to be clever again.

[melver]

compiler-rt/lib/sanitizer_common/sanitizer_mutex.cpp

76

... and there needs to be a CHECK after if (!mutex_meta[t].name)

mutex_count = t;
if (!mutex_meta[t].name)
  break;
CHECK(t < kMutexTypeMax); // Indicates array is not properly terminated.

[vitalybuka]

In D106546#2896998, @dvyukov wrote:

In D106546#2896967, @vitalybuka wrote:

Summary says: "Move internal deadlock", but the patch only adds new code

Updated commit description

Oh, it's actual copying, but it looks very different from TSAN version.

compiler-rt/lib/sanitizer_common/sanitizer_mutex.cpp

51

Why this detector operates on types and not individual mutexes?
Is this enough? I guess we can have deadlock on two different mutexes of the same type?

152

mutex_count -> mutex_type_count ?

210

static THREADLOCAL

compiler-rt/lib/sanitizer_common/sanitizer_mutex.h

79

enum class (maybe)

[dvyukov]

compiler-rt/lib/sanitizer_common/sanitizer_mutex.cpp

76

and the other arrays are wasting space

This is a very slow debug mode. Execution speed effect is worse then spending few bytes of memory. And we are wasting half of the array right now, what tsan uses is half of kMutexTypeMax. And other sanitizer waste all of it. Not just one and not just if we are not careful with checks here. They are always wasting all of it.

[dvyukov]

added static
s/mutex_count/mutex_type_count/
CHECK for mutex_meta array overflow

[dvyukov]

PTAL

compiler-rt/lib/sanitizer_common/sanitizer_mutex.cpp

51

We don't lock more than 1 of the same type.
There will be 1 exception in the new tsan, but it's very local and I don't see how we can reasonably handle it. We would need to allocate per-mutex data (there can be millions of them), build runtime graph, traverse it, somehow protect from concurrent accesses in a scalable way, etc. That's tons of code complexity and memory/performance overheads. And for all types but one we still want to prohibit any recursion on mutexes of the same type.

compiler-rt/lib/sanitizer_common/sanitizer_mutex.h

79

The same reason we can't use enum call in tsan applies here. It's not possible to "extend" enum classes, and we need to be able to extend it in each sanitizer.

[vitalybuka]

compiler-rt/lib/sanitizer_common/sanitizer_mutex.cpp

51

That's fine, but maybe add comment explaining that. It's not obvious without digging into details.

[dvyukov]

add comment explaining why deadlock detector operates on mutex types

[dvyukov]

compiler-rt/lib/sanitizer_common/sanitizer_mutex.cpp

51

Done

[dvyukov]

PTAL

[pgousseau]

compiler-rt/lib/sanitizer_common/sanitizer_mutex.cpp

76

Hi Dmitry, the statement "int cnt[kMutexTypeMax] = {};" seems to be causing some unit test to fail to in some configurations ? Can we maybe remove the empty initializer list?
Thanks!
Pierre
cf:

$ cmake -G Ninja "../llvm" -DLLVM_ENABLE_PROJECTS="clang;compiler-rt;" -DLLVM_TARGETS_TO_BUILD="X86" -DCMAKE_BUILD_TYPE=Release -DCOMPILER_RT_DEBUG=ON -DCMAKE_C_COMPILER=clang-10 -DCMAKE_CXX_COMPILER=clang++-10

$ ninja -j12 check-sanitizer
[6/22] Generating Sanitizer-x86_64-Test-Nolibc
FAILED: projects/compiler-rt/lib/sanitizer_common/tests/Sanitizer-x86_64-Test-Nolibc
cd /home/pierre/llvm-project/build/projects/compiler-rt/lib/sanitizer_common/tests && /home/pierre/llvm-project/build/./bin/clang sanitizer_nolibc_test_main.x86_64.o -Wl,-whole-archive libRTSanitizerCommon.test.nolibc.x86_64.a -Wl,-no-whole-archive -o /home/pierre/llvm-project/build/projects/compiler-rt/lib/sanitizer_common/tests/./Sanitizer-x86_64-Test-Nolibc -static -nostdlib -m64 -m64
libRTSanitizerCommon.test.nolibc.x86_64.a(sanitizer_mutex.cpp.o): In function `__sanitizer::DebugMutexInit()':
/home/pierre/llvm-project/compiler-rt/lib/sanitizer_common/sanitizer_mutex.cpp:76: undefined reference to `memset'
clang-14: error: linker command failed with exit code 1 (use -v to see invocation)
[13/22] Running lint check for sanitizer sources...
ninja: build stopped: subcommand failed.

[dvyukov]

compiler-rt/lib/sanitizer_common/sanitizer_mutex.cpp

76

I've sent https://reviews.llvm.org/D106978
thanks for reporting

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 {
  public:
-  constexpr Mutex2() {}
+  constexpr Mutex2(MutexType type = MutexUnchecked) : checked_(type) {}
 
   void Lock() ACQUIRE() {
+    checked_.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() {
+    checked_.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() {
+    checked_.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() {
+    checked_.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 &&
public:
 
   void CheckLocked() const CHECK_LOCKED() { CheckWriteLocked(); }
 
   void CheckReadLocked() const CHECK_LOCKED() {
     CHECK(atomic_load(&state_, memory_order_relaxed) & kReaderLockMask);
   }
 
  private:
+  [[no_unique_address]] CheckedMutex checked_;
   atomic_uint64_t state_ = {0};
   Semaphore writers_;
   Semaphore readers_;
 
   // The state has 3 counters:
   //  - number of readers holding the lock,
   //    if non zero, the mutex is read-locked
   //  - number of waiting readers,

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 type hierarchy (what mutex types can be locked
+// under what mutex types). This table is checked to be acyclic and then
+// actual mutex lock/unlock operations are checked to adhere to this hierarchy.
+// The checking happens on mutex types rather than on individual mutex instances
+// because doing it on mutex instances will both significantly complicate
+// the implementation, worsen performance and memory overhead and is mostly
+// unnecessary (we almost never lock multiple mutexes of the same type recursively).
+static constexpr 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_type_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 < kMutexTypeMax; t++) {
+    mutex_type_count = t;
+    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]++;
+    }
+  }
+  // Indicates the array is not properly terminated.
+  CHECK_LT(mutex_type_count, kMutexTypeMax);
+  // Add leaf mutexes.
+  for (int t = 0; t < mutex_type_count; t++) {
+    if (!leaf[t])
+      continue;
+    CHECK_EQ(cnt[t], 0);
+    for (int z = 0; z < mutex_type_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.
+  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_type_count; i++) {
+    for (int j = 0; j < mutex_type_count; j++)
+      if (mutex_can_lock[i][j])
+        trans[i] |= 1 << j;
+  }
+  for (int k = 0; k < mutex_type_count; k++) {
+    for (int i = 0; i < mutex_type_count; i++) {
+      if (trans[i] & (1 << k))
+        trans[i] |= trans[k];
+    }
+  }
+  for (int i = 0; i < mutex_type_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_type_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_type_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_type_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_type_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_type_count < 0)
+      DebugMutexInit();
+    initialized = mutex_type_count ? 1 : -1;
+    return initialized > 0;
+  }
+};
+
+static 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