Alexey Samsonov | 603c4be | 2012-06-04 13:55:19 +0000 | [diff] [blame] | 1 | //===-- tsan_mutex.cc -----------------------------------------------------===// |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 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 | //===----------------------------------------------------------------------===// |
Alexey Samsonov | 0969bcf | 2012-06-18 08:44:30 +0000 | [diff] [blame] | 13 | #include "sanitizer_common/sanitizer_libc.h" |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 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. |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 28 | #if SANITIZER_DEBUG && !SANITIZER_GO |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 29 | const MutexType MutexTypeLeaf = (MutexType)-1; |
| 30 | static MutexType CanLockTab[MutexTypeCount][MutexTypeCount] = { |
Dmitry Vyukov | f4e4f93 | 2012-12-21 11:30:14 +0000 | [diff] [blame] | 31 | /*0 MutexTypeInvalid*/ {}, |
| 32 | /*1 MutexTypeTrace*/ {MutexTypeLeaf}, |
| 33 | /*2 MutexTypeThreads*/ {MutexTypeReport}, |
Stephen Hines | 6a211c5 | 2014-07-21 00:49:56 -0700 | [diff] [blame] | 34 | /*3 MutexTypeReport*/ {MutexTypeSyncVar, |
Dmitry Vyukov | 94d8b44 | 2013-04-30 12:00:40 +0000 | [diff] [blame] | 35 | MutexTypeMBlock, MutexTypeJavaMBlock}, |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 36 | /*4 MutexTypeSyncVar*/ {MutexTypeDDetector}, |
Stephen Hines | 6a211c5 | 2014-07-21 00:49:56 -0700 | [diff] [blame] | 37 | /*5 MutexTypeSyncTab*/ {}, // unused |
Dmitry Vyukov | f4e4f93 | 2012-12-21 11:30:14 +0000 | [diff] [blame] | 38 | /*6 MutexTypeSlab*/ {MutexTypeLeaf}, |
| 39 | /*7 MutexTypeAnnotations*/ {}, |
Stephen Hines | 6a211c5 | 2014-07-21 00:49:56 -0700 | [diff] [blame] | 40 | /*8 MutexTypeAtExit*/ {MutexTypeSyncVar}, |
Dmitry Vyukov | f4e4f93 | 2012-12-21 11:30:14 +0000 | [diff] [blame] | 41 | /*9 MutexTypeMBlock*/ {MutexTypeSyncVar}, |
| 42 | /*10 MutexTypeJavaMBlock*/ {MutexTypeSyncVar}, |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 43 | /*11 MutexTypeDDetector*/ {}, |
Pirama Arumuga Nainar | 799172d | 2016-03-03 15:50:30 -0800 | [diff] [blame^] | 44 | /*12 MutexTypeFired*/ {MutexTypeLeaf}, |
| 45 | /*13 MutexTypeRacy*/ {MutexTypeLeaf}, |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 46 | }; |
| 47 | |
| 48 | static bool CanLockAdj[MutexTypeCount][MutexTypeCount]; |
Dmitry Vyukov | d622379 | 2012-12-13 09:22:11 +0000 | [diff] [blame] | 49 | #endif |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 50 | |
| 51 | void InitializeMutex() { |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 52 | #if SANITIZER_DEBUG && !SANITIZER_GO |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 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++) { |
Alexey Samsonov | 2135d8a | 2012-09-13 11:54:41 +0000 | [diff] [blame] | 60 | MutexType z = CanLockTab[i][j]; |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 61 | if (z == MutexTypeInvalid) |
| 62 | continue; |
| 63 | if (z == MutexTypeLeaf) { |
| 64 | CHECK(!leaf[i]); |
| 65 | leaf[i] = true; |
| 66 | continue; |
| 67 | } |
Alexey Samsonov | 2135d8a | 2012-09-13 11:54:41 +0000 | [diff] [blame] | 68 | CHECK(!CanLockAdj[i][(int)z]); |
| 69 | CanLockAdj[i][(int)z] = true; |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 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 |
Alexey Samsonov | b1fe302 | 2012-11-02 12:17:51 +0000 | [diff] [blame] | 104 | Printf("Can lock graph:\n"); |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 105 | for (int i = 0; i < N; i++) { |
| 106 | for (int j = 0; j < N; j++) { |
Alexey Samsonov | b1fe302 | 2012-11-02 12:17:51 +0000 | [diff] [blame] | 107 | Printf("%d ", CanLockAdj[i][j]); |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 108 | } |
Alexey Samsonov | b1fe302 | 2012-11-02 12:17:51 +0000 | [diff] [blame] | 109 | Printf("\n"); |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 110 | } |
Alexey Samsonov | b1fe302 | 2012-11-02 12:17:51 +0000 | [diff] [blame] | 111 | Printf("Can lock graph closure:\n"); |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 112 | for (int i = 0; i < N; i++) { |
| 113 | for (int j = 0; j < N; j++) { |
Alexey Samsonov | b1fe302 | 2012-11-02 12:17:51 +0000 | [diff] [blame] | 114 | Printf("%d ", CanLockAdj2[i][j]); |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 115 | } |
Alexey Samsonov | b1fe302 | 2012-11-02 12:17:51 +0000 | [diff] [blame] | 116 | Printf("\n"); |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 117 | } |
| 118 | #endif |
| 119 | // Verify that the graph is acyclic. |
| 120 | for (int i = 0; i < N; i++) { |
| 121 | if (CanLockAdj2[i][i]) { |
Alexey Samsonov | b1fe302 | 2012-11-02 12:17:51 +0000 | [diff] [blame] | 122 | Printf("Mutex %d participates in a cycle\n", i); |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 123 | Die(); |
| 124 | } |
| 125 | } |
Dmitry Vyukov | d622379 | 2012-12-13 09:22:11 +0000 | [diff] [blame] | 126 | #endif |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 127 | } |
| 128 | |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 129 | InternalDeadlockDetector::InternalDeadlockDetector() { |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 130 | // Rely on zero initialization because some mutexes can be locked before ctor. |
| 131 | } |
| 132 | |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 133 | #if SANITIZER_DEBUG && !SANITIZER_GO |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 134 | void InternalDeadlockDetector::Lock(MutexType t) { |
Alexey Samsonov | b1fe302 | 2012-11-02 12:17:51 +0000 | [diff] [blame] | 135 | // Printf("LOCK %d @%zu\n", t, seq_ + 1); |
Dmitry Vyukov | ad9da37 | 2012-12-06 12:16:15 +0000 | [diff] [blame] | 136 | CHECK_GT(t, MutexTypeInvalid); |
| 137 | CHECK_LT(t, MutexTypeCount); |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 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; |
Alexey Samsonov | b1fe302 | 2012-11-02 12:17:51 +0000 | [diff] [blame] | 152 | // Printf(" last %d @%zu\n", max_idx, max_seq); |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 153 | if (!CanLockAdj[max_idx][t]) { |
Alexey Samsonov | b1fe302 | 2012-11-02 12:17:51 +0000 | [diff] [blame] | 154 | Printf("ThreadSanitizer: internal deadlock detected\n"); |
| 155 | Printf("ThreadSanitizer: can't lock %d while under %zu\n", |
Alexey Samsonov | e954101 | 2012-06-06 13:11:29 +0000 | [diff] [blame] | 156 | t, (uptr)max_idx); |
Dmitry Vyukov | ff35f1d | 2012-08-30 13:02:30 +0000 | [diff] [blame] | 157 | CHECK(0); |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 158 | } |
| 159 | } |
| 160 | |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 161 | void InternalDeadlockDetector::Unlock(MutexType t) { |
Alexey Samsonov | b1fe302 | 2012-11-02 12:17:51 +0000 | [diff] [blame] | 162 | // Printf("UNLO %d @%zu #%zu\n", t, seq_, locked_[t]); |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 163 | CHECK(locked_[t]); |
| 164 | locked_[t] = 0; |
| 165 | } |
Stephen Hines | 6a211c5 | 2014-07-21 00:49:56 -0700 | [diff] [blame] | 166 | |
| 167 | void InternalDeadlockDetector::CheckNoLocks() { |
| 168 | for (int i = 0; i != MutexTypeCount; i++) { |
| 169 | CHECK_EQ(locked_[i], 0); |
| 170 | } |
| 171 | } |
Dmitry Vyukov | d622379 | 2012-12-13 09:22:11 +0000 | [diff] [blame] | 172 | #endif |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 173 | |
Stephen Hines | 6a211c5 | 2014-07-21 00:49:56 -0700 | [diff] [blame] | 174 | void CheckNoLocks(ThreadState *thr) { |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 175 | #if SANITIZER_DEBUG && !SANITIZER_GO |
Stephen Hines | 6a211c5 | 2014-07-21 00:49:56 -0700 | [diff] [blame] | 176 | thr->internal_deadlock_detector.CheckNoLocks(); |
| 177 | #endif |
| 178 | } |
| 179 | |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 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 |
Alexey Samsonov | 0969bcf | 2012-06-18 08:44:30 +0000 | [diff] [blame] | 194 | internal_sched_yield(); |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 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); |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 213 | #if SANITIZER_DEBUG |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 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() { |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 227 | #if SANITIZER_DEBUG && !SANITIZER_GO |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 228 | cur_thread()->internal_deadlock_detector.Lock(type_); |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 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)) { |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 239 | #if TSAN_COLLECT_STATS && !SANITIZER_GO |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 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); |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 252 | #if SANITIZER_DEBUG && !SANITIZER_GO |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 253 | cur_thread()->internal_deadlock_detector.Unlock(type_); |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 254 | #endif |
| 255 | } |
| 256 | |
| 257 | void Mutex::ReadLock() { |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 258 | #if SANITIZER_DEBUG && !SANITIZER_GO |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 259 | cur_thread()->internal_deadlock_detector.Lock(type_); |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 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) { |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 267 | #if TSAN_COLLECT_STATS && !SANITIZER_GO |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 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); |
Stephen Hines | 86277eb | 2015-03-23 12:06:32 -0700 | [diff] [blame] | 280 | #if SANITIZER_DEBUG && !SANITIZER_GO |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 281 | cur_thread()->internal_deadlock_detector.Unlock(type_); |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 282 | #endif |
| 283 | } |
| 284 | |
Dmitry Vyukov | ff35f1d | 2012-08-30 13:02:30 +0000 | [diff] [blame] | 285 | void Mutex::CheckLocked() { |
| 286 | CHECK_NE(atomic_load(&state_, memory_order_relaxed), 0); |
| 287 | } |
| 288 | |
Kostya Serebryany | 7ac4148 | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 289 | } // namespace __tsan |