libsanitizer/tsan/tsan_mutex.cc

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