• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 };
47 
48 static bool CanLockAdj[MutexTypeCount][MutexTypeCount];
49 #endif
50 
InitializeMutex()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;
56   int cnt[N] = {};
57   bool leaf[N] = {};
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)
62         continue;
63       if (z == MutexTypeLeaf) {
64         CHECK(!leaf[i]);
65         leaf[i] = true;
66         continue;
67       }
68       CHECK(!CanLockAdj[i][(int)z]);
69       CanLockAdj[i][(int)z] = true;
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
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]);
108     }
109     Printf("\n");
110   }
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]);
115     }
116     Printf("\n");
117   }
118 #endif
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);
123       Die();
124     }
125   }
126 #endif
127 }
128 
InternalDeadlockDetector()129 InternalDeadlockDetector::InternalDeadlockDetector() {
130   // Rely on zero initialization because some mutexes can be locked before ctor.
131 }
132 
133 #if SANITIZER_DEBUG && !SANITIZER_GO
Lock(MutexType t)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);
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;
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",
156                t, (uptr)max_idx);
157     CHECK(0);
158   }
159 }
160 
Unlock(MutexType t)161 void InternalDeadlockDetector::Unlock(MutexType t) {
162   // Printf("UNLO %d @%zu #%zu\n", t, seq_, locked_[t]);
163   CHECK(locked_[t]);
164   locked_[t] = 0;
165 }
166 
CheckNoLocks()167 void InternalDeadlockDetector::CheckNoLocks() {
168   for (int i = 0; i != MutexTypeCount; i++) {
169     CHECK_EQ(locked_[i], 0);
170   }
171 }
172 #endif
173 
CheckNoLocks(ThreadState * thr)174 void CheckNoLocks(ThreadState *thr) {
175 #if SANITIZER_DEBUG && !SANITIZER_GO
176   thr->internal_deadlock_detector.CheckNoLocks();
177 #endif
178 }
179 
180 const uptr kUnlocked = 0;
181 const uptr kWriteLock = 1;
182 const uptr kReadLock = 2;
183 
184 class Backoff {
185  public:
Backoff()186   Backoff()
187     : iter_() {
188   }
189 
Do()190   bool Do() {
191     if (iter_++ < kActiveSpinIters)
192       proc_yield(kActiveSpinCnt);
193     else
194       internal_sched_yield();
195     return true;
196   }
197 
Contention() const198   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 
Mutex(MutexType type,StatType stat_type)210 Mutex::Mutex(MutexType type, StatType stat_type) {
211   CHECK_GT(type, MutexTypeInvalid);
212   CHECK_LT(type, MutexTypeCount);
213 #if SANITIZER_DEBUG
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 
~Mutex()222 Mutex::~Mutex() {
223   CHECK_EQ(atomic_load(&state_, memory_order_relaxed), kUnlocked);
224 }
225 
Lock()226 void Mutex::Lock() {
227 #if SANITIZER_DEBUG && !SANITIZER_GO
228   cur_thread()->internal_deadlock_detector.Lock(type_);
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)) {
239 #if TSAN_COLLECT_STATS && !SANITIZER_GO
240         StatInc(cur_thread(), stat_type_, backoff.Contention());
241 #endif
242         return;
243       }
244     }
245   }
246 }
247 
Unlock()248 void Mutex::Unlock() {
249   uptr prev = atomic_fetch_sub(&state_, kWriteLock, memory_order_release);
250   (void)prev;
251   DCHECK_NE(prev & kWriteLock, 0);
252 #if SANITIZER_DEBUG && !SANITIZER_GO
253   cur_thread()->internal_deadlock_detector.Unlock(type_);
254 #endif
255 }
256 
ReadLock()257 void Mutex::ReadLock() {
258 #if SANITIZER_DEBUG && !SANITIZER_GO
259   cur_thread()->internal_deadlock_detector.Lock(type_);
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) {
267 #if TSAN_COLLECT_STATS && !SANITIZER_GO
268       StatInc(cur_thread(), stat_type_, backoff.Contention());
269 #endif
270       return;
271     }
272   }
273 }
274 
ReadUnlock()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);
280 #if SANITIZER_DEBUG && !SANITIZER_GO
281   cur_thread()->internal_deadlock_detector.Unlock(type_);
282 #endif
283 }
284 
CheckLocked()285 void Mutex::CheckLocked() {
286   CHECK_NE(atomic_load(&state_, memory_order_relaxed), 0);
287 }
288 
289 }  // namespace __tsan
290