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 291
