libsanitizer/tsan/tsan_mutex.cpp

   1 //===-- tsan_mutex.cpp ----------------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file is a part of ThreadSanitizer (TSan), a race detector.
  10 //
  11 //===----------------------------------------------------------------------===//
  12 #include "sanitizer_common/sanitizer_libc.h"
  13 #include "tsan_mutex.h"
  14 #include "tsan_platform.h"
  15 #include "tsan_rtl.h"
  16
  17 namespace __tsan {
  18
  19 // Simple reader-writer spin-mutex. Optimized for not-so-contended case.
  20 // Readers have preference, can possibly starvate writers.
  21
  22 // The table fixes what mutexes can be locked under what mutexes.
  23 // E.g. if the row for MutexTypeThreads contains MutexTypeReport,
  24 // then Report mutex can be locked while under Threads mutex.
  25 // The leaf mutexes can be locked under any other mutexes.
  26 // Recursive locking is not supported.
  27 #if SANITIZER_DEBUG && !SANITIZER_GO
  28 const MutexType MutexTypeLeaf = (MutexType)-1;
  29 static MutexType CanLockTab[MutexTypeCount][MutexTypeCount] = {
  30   /*0  MutexTypeInvalid*/     {},
  31   /*1  MutexTypeTrace*/       {MutexTypeLeaf},
  32   /*2  MutexTypeThreads*/     {MutexTypeReport},
  33   /*3  MutexTypeReport*/      {MutexTypeSyncVar,
  34                                MutexTypeMBlock, MutexTypeJavaMBlock},
  35   /*4  MutexTypeSyncVar*/     {MutexTypeDDetector},
  36   /*5  MutexTypeSyncTab*/     {},  // unused
  37   /*6  MutexTypeSlab*/        {MutexTypeLeaf},
  38   /*7  MutexTypeAnnotations*/ {},
  39   /*8  MutexTypeAtExit*/      {MutexTypeSyncVar},
  40   /*9  MutexTypeMBlock*/      {MutexTypeSyncVar},
  41   /*10 MutexTypeJavaMBlock*/  {MutexTypeSyncVar},
  42   /*11 MutexTypeDDetector*/   {},
  43   /*12 MutexTypeFired*/       {MutexTypeLeaf},
  44   /*13 MutexTypeRacy*/        {MutexTypeLeaf},
  45   /*14 MutexTypeGlobalProc*/  {},
  46 };
  47
  48 static bool CanLockAdj[MutexTypeCount][MutexTypeCount];
  49 #endif
  50
  51 void InitializeMutex() {
  52 #if SANITIZER_DEBUG && !SANITIZER_GO
  53   // Build the "can lock" adjacency matrix.
  54   // If [i][j]==true, then one can lock mutex j while under mutex i.
  55   const int N = MutexTypeCount;
  56   int cnt[N] = {};
  57   bool leaf[N] = {};
  58   for (int i = 1; i < N; i++) {
  59     for (int j = 0; j < N; j++) {
  60       MutexType z = CanLockTab[i][j];
  61       if (z == MutexTypeInvalid)
  62         continue;
  63       if (z == MutexTypeLeaf) {
  64         CHECK(!leaf[i]);
  65         leaf[i] = true;
  66         continue;
  67       }
  68       CHECK(!CanLockAdj[i][(int)z]);
  69       CanLockAdj[i][(int)z] = true;
  70       cnt[i]++;
  71     }
  72   }
  73   for (int i = 0; i < N; i++) {
  74     CHECK(!leaf[i] || cnt[i] == 0);
  75   }
  76   // Add leaf mutexes.
  77   for (int i = 0; i < N; i++) {
  78     if (!leaf[i])
  79       continue;
  80     for (int j = 0; j < N; j++) {
  81       if (i == j || leaf[j] || j == MutexTypeInvalid)
  82         continue;
  83       CHECK(!CanLockAdj[j][i]);
  84       CanLockAdj[j][i] = true;
  85     }
  86   }
  87   // Build the transitive closure.
  88   bool CanLockAdj2[MutexTypeCount][MutexTypeCount];
  89   for (int i = 0; i < N; i++) {
  90     for (int j = 0; j < N; j++) {
  91       CanLockAdj2[i][j] = CanLockAdj[i][j];
  92     }
  93   }
  94   for (int k = 0; k < N; k++) {
  95     for (int i = 0; i < N; i++) {
  96       for (int j = 0; j < N; j++) {
  97         if (CanLockAdj2[i][k] && CanLockAdj2[k][j]) {
  98           CanLockAdj2[i][j] = true;
  99         }
 100       }
 101     }
 102   }
 103 #if 0
 104   Printf("Can lock graph:\n");
 105   for (int i = 0; i < N; i++) {
 106     for (int j = 0; j < N; j++) {
 107       Printf("%d ", CanLockAdj[i][j]);
 108     }
 109     Printf("\n");
 110   }
 111   Printf("Can lock graph closure:\n");
 112   for (int i = 0; i < N; i++) {
 113     for (int j = 0; j < N; j++) {
 114       Printf("%d ", CanLockAdj2[i][j]);
 115     }
 116     Printf("\n");
 117   }
 118 #endif
 119   // Verify that the graph is acyclic.
 120   for (int i = 0; i < N; i++) {
 121     if (CanLockAdj2[i][i]) {
 122       Printf("Mutex %d participates in a cycle\n", i);
 123       Die();
 124     }
 125   }
 126 #endif
 127 }
 128
 129 InternalDeadlockDetector::InternalDeadlockDetector() {
 130   // Rely on zero initialization because some mutexes can be locked before ctor.
 131 }
 132
 133 #if SANITIZER_DEBUG && !SANITIZER_GO
 134 void InternalDeadlockDetector::Lock(MutexType t) {
 135   // Printf("LOCK %d @%zu\n", t, seq_ + 1);
 136   CHECK_GT(t, MutexTypeInvalid);
 137   CHECK_LT(t, MutexTypeCount);
 138   u64 max_seq = 0;
 139   u64 max_idx = MutexTypeInvalid;
 140   for (int i = 0; i != MutexTypeCount; i++) {
 141     if (locked_[i] == 0)
 142       continue;
 143     CHECK_NE(locked_[i], max_seq);
 144     if (max_seq < locked_[i]) {
 145       max_seq = locked_[i];
 146       max_idx = i;
 147     }
 148   }
 149   locked_[t] = ++seq_;
 150   if (max_idx == MutexTypeInvalid)
 151     return;
 152   // Printf("  last %d @%zu\n", max_idx, max_seq);
 153   if (!CanLockAdj[max_idx][t]) {
 154     Printf("ThreadSanitizer: internal deadlock detected\n");
 155     Printf("ThreadSanitizer: can't lock %d while under %zu\n",
 156                t, (uptr)max_idx);
 157     CHECK(0);
 158   }
 159 }
 160
 161 void InternalDeadlockDetector::Unlock(MutexType t) {
 162   // Printf("UNLO %d @%zu #%zu\n", t, seq_, locked_[t]);
 163   CHECK(locked_[t]);
 164   locked_[t] = 0;
 165 }
 166
 167 void InternalDeadlockDetector::CheckNoLocks() {
 168   for (int i = 0; i != MutexTypeCount; i++) {
 169     CHECK_EQ(locked_[i], 0);
 170   }
 171 }
 172 #endif
 173
 174 void CheckNoLocks(ThreadState *thr) {
 175 #if SANITIZER_DEBUG && !SANITIZER_GO
 176   thr->internal_deadlock_detector.CheckNoLocks();
 177 #endif
 178 }
 179
 180 const uptr kUnlocked = 0;
 181 const uptr kWriteLock = 1;
 182 const uptr kReadLock = 2;
 183
 184 class Backoff {
 185  public:
 186   Backoff()
 187     : iter_() {
 188   }
 189
 190   bool Do() {
 191     if (iter_++ < kActiveSpinIters)
 192       proc_yield(kActiveSpinCnt);
 193     else
 194       internal_sched_yield();
 195     return true;
 196   }
 197
 198   u64 Contention() const {
 199     u64 active = iter_ % kActiveSpinIters;
 200     u64 passive = iter_ - active;
 201     return active + 10 * passive;
 202   }
 203
 204  private:
 205   int iter_;
 206   static const int kActiveSpinIters = 10;
 207   static const int kActiveSpinCnt = 20;
 208 };
 209
 210 Mutex::Mutex(MutexType type, StatType stat_type) {
 211   CHECK_GT(type, MutexTypeInvalid);
 212   CHECK_LT(type, MutexTypeCount);
 213 #if SANITIZER_DEBUG
 214   type_ = type;
 215 #endif
 216 #if TSAN_COLLECT_STATS
 217   stat_type_ = stat_type;
 218 #endif
 219   atomic_store(&state_, kUnlocked, memory_order_relaxed);
 220 }
 221
 222 Mutex::~Mutex() {
 223   CHECK_EQ(atomic_load(&state_, memory_order_relaxed), kUnlocked);
 224 }
 225
 226 void Mutex::Lock() {
 227 #if SANITIZER_DEBUG && !SANITIZER_GO
 228   cur_thread()->internal_deadlock_detector.Lock(type_);
 229 #endif
 230   uptr cmp = kUnlocked;
 231   if (atomic_compare_exchange_strong(&state_, &cmp, kWriteLock,
 232                                      memory_order_acquire))
 233     return;
 234   for (Backoff backoff; backoff.Do();) {
 235     if (atomic_load(&state_, memory_order_relaxed) == kUnlocked) {
 236       cmp = kUnlocked;
 237       if (atomic_compare_exchange_weak(&state_, &cmp, kWriteLock,
 238                                        memory_order_acquire)) {
 239 #if TSAN_COLLECT_STATS && !SANITIZER_GO
 240         StatInc(cur_thread(), stat_type_, backoff.Contention());
 241 #endif
 242         return;
 243       }
 244     }
 245   }
 246 }
 247
 248 void Mutex::Unlock() {
 249   uptr prev = atomic_fetch_sub(&state_, kWriteLock, memory_order_release);
 250   (void)prev;
 251   DCHECK_NE(prev & kWriteLock, 0);
 252 #if SANITIZER_DEBUG && !SANITIZER_GO
 253   cur_thread()->internal_deadlock_detector.Unlock(type_);
 254 #endif
 255 }
 256
 257 void Mutex::ReadLock() {
 258 #if SANITIZER_DEBUG && !SANITIZER_GO
 259   cur_thread()->internal_deadlock_detector.Lock(type_);
 260 #endif
 261   uptr prev = atomic_fetch_add(&state_, kReadLock, memory_order_acquire);
 262   if ((prev & kWriteLock) == 0)
 263     return;
 264   for (Backoff backoff; backoff.Do();) {
 265     prev = atomic_load(&state_, memory_order_acquire);
 266     if ((prev & kWriteLock) == 0) {
 267 #if TSAN_COLLECT_STATS && !SANITIZER_GO
 268       StatInc(cur_thread(), stat_type_, backoff.Contention());
 269 #endif
 270       return;
 271     }
 272   }
 273 }
 274
 275 void Mutex::ReadUnlock() {
 276   uptr prev = atomic_fetch_sub(&state_, kReadLock, memory_order_release);
 277   (void)prev;
 278   DCHECK_EQ(prev & kWriteLock, 0);
 279   DCHECK_GT(prev & ~kWriteLock, 0);
 280 #if SANITIZER_DEBUG && !SANITIZER_GO
 281   cur_thread()->internal_deadlock_detector.Unlock(type_);
 282 #endif
 283 }
 284
 285 void Mutex::CheckLocked() {
 286   CHECK_NE(atomic_load(&state_, memory_order_relaxed), 0);
 287 }
 288
 289 }  // namespace __tsan