1 //===-- tsan_mutex.cc -----------------------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file is a part of ThreadSanitizer (TSan), a race detector.
12 //===----------------------------------------------------------------------===//
13 #include "sanitizer_common/sanitizer_libc.h"
14 #include "tsan_mutex.h"
15 #include "tsan_platform.h"
20 // Simple reader-writer spin-mutex. Optimized for not-so-contended case.
21 // Readers have preference, can possibly starvate writers.
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},
48 static bool CanLockAdj[MutexTypeCount][MutexTypeCount];
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;
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)
63 if (z == MutexTypeLeaf) {
68 CHECK(!CanLockAdj[i][(int)z]);
69 CanLockAdj[i][(int)z] = true;
73 for (int i = 0; i < N; i++) {
74 CHECK(!leaf[i] || cnt[i] == 0);
77 for (int i = 0; i < N; i++) {
80 for (int j = 0; j < N; j++) {
81 if (i == j || leaf[j] || j == MutexTypeInvalid)
83 CHECK(!CanLockAdj[j][i]);
84 CanLockAdj[j][i] = true;
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];
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;
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]);
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]);
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);
129 InternalDeadlockDetector::InternalDeadlockDetector() {
130 // Rely on zero initialization because some mutexes can be locked before ctor.
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);
139 u64 max_idx = MutexTypeInvalid;
140 for (int i = 0; i != MutexTypeCount; i++) {
143 CHECK_NE(locked_[i], max_seq);
144 if (max_seq < locked_[i]) {
145 max_seq = locked_[i];
150 if (max_idx == MutexTypeInvalid)
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",
161 void InternalDeadlockDetector::Unlock(MutexType t) {
162 // Printf("UNLO %d @%zu #%zu\n", t, seq_, locked_[t]);
167 void InternalDeadlockDetector::CheckNoLocks() {
168 for (int i = 0; i != MutexTypeCount; i++) {
169 CHECK_EQ(locked_[i], 0);
174 void CheckNoLocks(ThreadState *thr) {
175 #if SANITIZER_DEBUG && !SANITIZER_GO
176 thr->internal_deadlock_detector.CheckNoLocks();
180 const uptr kUnlocked = 0;
181 const uptr kWriteLock = 1;
182 const uptr kReadLock = 2;
191 if (iter_++ < kActiveSpinIters)
192 proc_yield(kActiveSpinCnt);
194 internal_sched_yield();
198 u64 Contention() const {
199 u64 active = iter_ % kActiveSpinIters;
200 u64 passive = iter_ - active;
201 return active + 10 * passive;
206 static const int kActiveSpinIters = 10;
207 static const int kActiveSpinCnt = 20;
210 Mutex::Mutex(MutexType type, StatType stat_type) {
211 CHECK_GT(type, MutexTypeInvalid);
212 CHECK_LT(type, MutexTypeCount);
216 #if TSAN_COLLECT_STATS
217 stat_type_ = stat_type;
219 atomic_store(&state_, kUnlocked, memory_order_relaxed);
223 CHECK_EQ(atomic_load(&state_, memory_order_relaxed), kUnlocked);
227 #if SANITIZER_DEBUG && !SANITIZER_GO
228 cur_thread()->internal_deadlock_detector.Lock(type_);
230 uptr cmp = kUnlocked;
231 if (atomic_compare_exchange_strong(&state_, &cmp, kWriteLock,
232 memory_order_acquire))
234 for (Backoff backoff; backoff.Do();) {
235 if (atomic_load(&state_, memory_order_relaxed) == 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());
248 void Mutex::Unlock() {
249 uptr prev = atomic_fetch_sub(&state_, kWriteLock, memory_order_release);
251 DCHECK_NE(prev & kWriteLock, 0);
252 #if SANITIZER_DEBUG && !SANITIZER_GO
253 cur_thread()->internal_deadlock_detector.Unlock(type_);
257 void Mutex::ReadLock() {
258 #if SANITIZER_DEBUG && !SANITIZER_GO
259 cur_thread()->internal_deadlock_detector.Lock(type_);
261 uptr prev = atomic_fetch_add(&state_, kReadLock, memory_order_acquire);
262 if ((prev & kWriteLock) == 0)
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());
275 void Mutex::ReadUnlock() {
276 uptr prev = atomic_fetch_sub(&state_, kReadLock, memory_order_release);
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_);
285 void Mutex::CheckLocked() {
286 CHECK_NE(atomic_load(&state_, memory_order_relaxed), 0);
289 } // namespace __tsan