contrib/compiler-rt/lib/tsan/rtl/tsan_mutex.cc

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