1 //===-- sanitizer_mutex.h ---------------------------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file is a part of ThreadSanitizer/AddressSanitizer runtime.
10 //
11 //===----------------------------------------------------------------------===//
12
13 #ifndef SANITIZER_MUTEX_H
14 #define SANITIZER_MUTEX_H
15
16 #include "sanitizer_atomic.h"
17 #include "sanitizer_internal_defs.h"
18 #include "sanitizer_libc.h"
19 #include "sanitizer_thread_safety.h"
20
21 namespace __sanitizer {
22
23 class SANITIZER_MUTEX StaticSpinMutex {
24 public:
25 void Init() {
26 atomic_store(&state_, 0, memory_order_relaxed);
27 }
28
29 void Lock() SANITIZER_ACQUIRE() {
30 if (LIKELY(TryLock()))
31 return;
32 LockSlow();
33 }
34
35 bool TryLock() SANITIZER_TRY_ACQUIRE(true) {
36 return atomic_exchange(&state_, 1, memory_order_acquire) == 0;
37 }
38
39 void Unlock() SANITIZER_RELEASE() {
40 atomic_store(&state_, 0, memory_order_release);
41 }
42
43 void CheckLocked() const SANITIZER_CHECK_LOCKED() {
44 CHECK_EQ(atomic_load(&state_, memory_order_relaxed), 1);
45 }
46
47 private:
48 atomic_uint8_t state_;
49
50 void LockSlow();
51 };
52
53 class SANITIZER_MUTEX SpinMutex : public StaticSpinMutex {
54 public:
55 SpinMutex() {
56 Init();
57 }
58
59 SpinMutex(const SpinMutex &) = delete;
60 void operator=(const SpinMutex &) = delete;
61 };
62
63 // Semaphore provides an OS-dependent way to park/unpark threads.
64 // The last thread returned from Wait can destroy the object
65 // (destruction-safety).
66 class Semaphore {
67 public:
68 constexpr Semaphore() {}
69 Semaphore(const Semaphore &) = delete;
70 void operator=(const Semaphore &) = delete;
71
72 void Wait();
73 void Post(u32 count = 1);
74
75 private:
76 atomic_uint32_t state_ = {0};
77 };
78
79 typedef int MutexType;
80
81 enum {
82 // Used as sentinel and to catch unassigned types
83 // (should not be used as real Mutex type).
84 MutexInvalid = 0,
85 MutexThreadRegistry,
86 // Each tool own mutexes must start at this number.
87 MutexLastCommon,
88 // Type for legacy mutexes that are not checked for deadlocks.
89 MutexUnchecked = -1,
90 // Special marks that can be used in MutexMeta::can_lock table.
91 // The leaf mutexes can be locked under any other non-leaf mutex,
92 // but no other mutex can be locked while under a leaf mutex.
93 MutexLeaf = -1,
94 // Multiple mutexes of this type can be locked at the same time.
95 MutexMulti = -3,
96 };
97
98 // Go linker does not support THREADLOCAL variables,
99 // so we can't use per-thread state.
100 // Disable checked locks on Darwin. Although Darwin platforms support
101 // THREADLOCAL variables they are not usable early on during process init when
102 // `__sanitizer::Mutex` is used.
103 #define SANITIZER_CHECK_DEADLOCKS \
104 (SANITIZER_DEBUG && !SANITIZER_GO && SANITIZER_SUPPORTS_THREADLOCAL && !SANITIZER_APPLE)
105
106 #if SANITIZER_CHECK_DEADLOCKS
107 struct MutexMeta {
108 MutexType type;
109 const char *name;
110 // The table fixes what mutexes can be locked under what mutexes.
111 // If the entry for MutexTypeFoo contains MutexTypeBar,
112 // then Bar mutex can be locked while under Foo mutex.
113 // Can also contain the special MutexLeaf/MutexMulti marks.
114 MutexType can_lock[10];
115 };
116 #endif
117
118 class CheckedMutex {
119 public:
120 explicit constexpr CheckedMutex(MutexType type)
121 #if SANITIZER_CHECK_DEADLOCKS
122 : type_(type)
123 #endif
124 {
125 }
126
127 ALWAYS_INLINE void Lock() {
128 #if SANITIZER_CHECK_DEADLOCKS
129 LockImpl(GET_CALLER_PC());
130 #endif
131 }
132
133 ALWAYS_INLINE void Unlock() {
134 #if SANITIZER_CHECK_DEADLOCKS
135 UnlockImpl();
136 #endif
137 }
138
139 // Checks that the current thread does not hold any mutexes
140 // (e.g. when returning from a runtime function to user code).
141 static void CheckNoLocks() {
142 #if SANITIZER_CHECK_DEADLOCKS
143 CheckNoLocksImpl();
144 #endif
145 }
146
147 private:
148 #if SANITIZER_CHECK_DEADLOCKS
149 const MutexType type_;
150
151 void LockImpl(uptr pc);
152 void UnlockImpl();
153 static void CheckNoLocksImpl();
154 #endif
155 };
156
157 // Reader-writer mutex.
158 // Derive from CheckedMutex for the purposes of EBO.
159 // We could make it a field marked with [[no_unique_address]],
160 // but this attribute is not supported by some older compilers.
161 class SANITIZER_MUTEX Mutex : CheckedMutex {
162 public:
163 explicit constexpr Mutex(MutexType type = MutexUnchecked)
164 : CheckedMutex(type) {}
165
166 void Lock() SANITIZER_ACQUIRE() {
167 CheckedMutex::Lock();
168 u64 reset_mask = ~0ull;
169 u64 state = atomic_load_relaxed(&state_);
170 for (uptr spin_iters = 0;; spin_iters++) {
171 u64 new_state;
172 bool locked = (state & (kWriterLock | kReaderLockMask)) != 0;
173 if (LIKELY(!locked)) {
174 // The mutex is not read-/write-locked, try to lock.
175 new_state = (state | kWriterLock) & reset_mask;
176 } else if (spin_iters > kMaxSpinIters) {
177 // We've spun enough, increment waiting writers count and block.
178 // The counter will be decremented by whoever wakes us.
179 new_state = (state + kWaitingWriterInc) & reset_mask;
180 } else if ((state & kWriterSpinWait) == 0) {
181 // Active spinning, but denote our presence so that unlocking
182 // thread does not wake up other threads.
183 new_state = state | kWriterSpinWait;
184 } else {
185 // Active spinning.
186 state = atomic_load(&state_, memory_order_relaxed);
187 continue;
188 }
189 if (UNLIKELY(!atomic_compare_exchange_weak(&state_, &state, new_state,
190 memory_order_acquire)))
191 continue;
192 if (LIKELY(!locked))
193 return; // We've locked the mutex.
194 if (spin_iters > kMaxSpinIters) {
195 // We've incremented waiting writers, so now block.
196 writers_.Wait();
197 spin_iters = 0;
198 } else {
199 // We've set kWriterSpinWait, but we are still in active spinning.
200 }
201 // We either blocked and were unblocked,
202 // or we just spun but set kWriterSpinWait.
203 // Either way we need to reset kWriterSpinWait
204 // next time we take the lock or block again.
205 reset_mask = ~kWriterSpinWait;
206 state = atomic_load(&state_, memory_order_relaxed);
207 DCHECK_NE(state & kWriterSpinWait, 0);
208 }
209 }
210
211 bool TryLock() SANITIZER_TRY_ACQUIRE(true) {
212 u64 state = atomic_load_relaxed(&state_);
213 for (;;) {
214 if (UNLIKELY(state & (kWriterLock | kReaderLockMask)))
215 return false;
216 // The mutex is not read-/write-locked, try to lock.
217 if (LIKELY(atomic_compare_exchange_weak(
218 &state_, &state, state | kWriterLock, memory_order_acquire))) {
219 CheckedMutex::Lock();
220 return true;
221 }
222 }
223 }
224
225 void Unlock() SANITIZER_RELEASE() {
226 CheckedMutex::Unlock();
227 bool wake_writer;
228 u64 wake_readers;
229 u64 new_state;
230 u64 state = atomic_load_relaxed(&state_);
231 do {
232 DCHECK_NE(state & kWriterLock, 0);
233 DCHECK_EQ(state & kReaderLockMask, 0);
234 new_state = state & ~kWriterLock;
235 wake_writer = (state & (kWriterSpinWait | kReaderSpinWait)) == 0 &&
236 (state & kWaitingWriterMask) != 0;
237 if (wake_writer)
238 new_state = (new_state - kWaitingWriterInc) | kWriterSpinWait;
239 wake_readers =
240 wake_writer || (state & kWriterSpinWait) != 0
241 ? 0
242 : ((state & kWaitingReaderMask) >> kWaitingReaderShift);
243 if (wake_readers)
244 new_state = (new_state & ~kWaitingReaderMask) | kReaderSpinWait;
245 } while (UNLIKELY(!atomic_compare_exchange_weak(&state_, &state, new_state,
246 memory_order_release)));
247 if (UNLIKELY(wake_writer))
248 writers_.Post();
249 else if (UNLIKELY(wake_readers))
250 readers_.Post(wake_readers);
251 }
252
253 void ReadLock() SANITIZER_ACQUIRE_SHARED() {
254 CheckedMutex::Lock();
255 u64 reset_mask = ~0ull;
256 u64 state = atomic_load_relaxed(&state_);
257 for (uptr spin_iters = 0;; spin_iters++) {
258 bool locked = (state & kWriterLock) != 0;
259 u64 new_state;
260 if (LIKELY(!locked)) {
261 new_state = (state + kReaderLockInc) & reset_mask;
262 } else if (spin_iters > kMaxSpinIters) {
263 new_state = (state + kWaitingReaderInc) & reset_mask;
264 } else if ((state & kReaderSpinWait) == 0) {
265 // Active spinning, but denote our presence so that unlocking
266 // thread does not wake up other threads.
267 new_state = state | kReaderSpinWait;
268 } else {
269 // Active spinning.
270 state = atomic_load(&state_, memory_order_relaxed);
271 continue;
272 }
273 if (UNLIKELY(!atomic_compare_exchange_weak(&state_, &state, new_state,
274 memory_order_acquire)))
275 continue;
276 if (LIKELY(!locked))
277 return; // We've locked the mutex.
278 if (spin_iters > kMaxSpinIters) {
279 // We've incremented waiting readers, so now block.
280 readers_.Wait();
281 spin_iters = 0;
282 } else {
283 // We've set kReaderSpinWait, but we are still in active spinning.
284 }
285 reset_mask = ~kReaderSpinWait;
286 state = atomic_load(&state_, memory_order_relaxed);
287 }
288 }
289
290 void ReadUnlock() SANITIZER_RELEASE_SHARED() {
291 CheckedMutex::Unlock();
292 bool wake;
293 u64 new_state;
294 u64 state = atomic_load_relaxed(&state_);
295 do {
296 DCHECK_NE(state & kReaderLockMask, 0);
297 DCHECK_EQ(state & kWriterLock, 0);
298 new_state = state - kReaderLockInc;
299 wake = (new_state &
300 (kReaderLockMask | kWriterSpinWait | kReaderSpinWait)) == 0 &&
301 (new_state & kWaitingWriterMask) != 0;
302 if (wake)
303 new_state = (new_state - kWaitingWriterInc) | kWriterSpinWait;
304 } while (UNLIKELY(!atomic_compare_exchange_weak(&state_, &state, new_state,
305 memory_order_release)));
306 if (UNLIKELY(wake))
307 writers_.Post();
308 }
309
310 // This function does not guarantee an explicit check that the calling thread
311 // is the thread which owns the mutex. This behavior, while more strictly
312 // correct, causes problems in cases like StopTheWorld, where a parent thread
313 // owns the mutex but a child checks that it is locked. Rather than
314 // maintaining complex state to work around those situations, the check only
315 // checks that the mutex is owned.
316 void CheckWriteLocked() const SANITIZER_CHECK_LOCKED() {
317 CHECK(atomic_load(&state_, memory_order_relaxed) & kWriterLock);
318 }
319
320 void CheckLocked() const SANITIZER_CHECK_LOCKED() { CheckWriteLocked(); }
321
322 void CheckReadLocked() const SANITIZER_CHECK_LOCKED() {
323 CHECK(atomic_load(&state_, memory_order_relaxed) & kReaderLockMask);
324 }
325
326 private:
327 atomic_uint64_t state_ = {0};
328 Semaphore writers_;
329 Semaphore readers_;
330
331 // The state has 3 counters:
332 // - number of readers holding the lock,
333 // if non zero, the mutex is read-locked
334 // - number of waiting readers,
335 // if not zero, the mutex is write-locked
336 // - number of waiting writers,
337 // if non zero, the mutex is read- or write-locked
338 // And 2 flags:
339 // - writer lock
340 // if set, the mutex is write-locked
341 // - a writer is awake and spin-waiting
342 // the flag is used to prevent thundering herd problem
343 // (new writers are not woken if this flag is set)
344 // - a reader is awake and spin-waiting
345 //
346 // Both writers and readers use active spinning before blocking.
347 // But readers are more aggressive and always take the mutex
348 // if there are any other readers.
349 // After wake up both writers and readers compete to lock the
350 // mutex again. This is needed to allow repeated locks even in presence
351 // of other blocked threads.
352 static constexpr u64 kCounterWidth = 20;
353 static constexpr u64 kReaderLockShift = 0;
354 static constexpr u64 kReaderLockInc = 1ull << kReaderLockShift;
355 static constexpr u64 kReaderLockMask = ((1ull << kCounterWidth) - 1)
356 << kReaderLockShift;
357 static constexpr u64 kWaitingReaderShift = kCounterWidth;
358 static constexpr u64 kWaitingReaderInc = 1ull << kWaitingReaderShift;
359 static constexpr u64 kWaitingReaderMask = ((1ull << kCounterWidth) - 1)
360 << kWaitingReaderShift;
361 static constexpr u64 kWaitingWriterShift = 2 * kCounterWidth;
362 static constexpr u64 kWaitingWriterInc = 1ull << kWaitingWriterShift;
363 static constexpr u64 kWaitingWriterMask = ((1ull << kCounterWidth) - 1)
364 << kWaitingWriterShift;
365 static constexpr u64 kWriterLock = 1ull << (3 * kCounterWidth);
366 static constexpr u64 kWriterSpinWait = 1ull << (3 * kCounterWidth + 1);
367 static constexpr u64 kReaderSpinWait = 1ull << (3 * kCounterWidth + 2);
368
369 static constexpr uptr kMaxSpinIters = 1500;
370
371 Mutex(LinkerInitialized) = delete;
372 Mutex(const Mutex &) = delete;
373 void operator=(const Mutex &) = delete;
374 };
375
376 void FutexWait(atomic_uint32_t *p, u32 cmp);
377 void FutexWake(atomic_uint32_t *p, u32 count);
378
379 template <typename MutexType>
380 class SANITIZER_SCOPED_LOCK GenericScopedLock {
381 public:
382 explicit GenericScopedLock(MutexType *mu) SANITIZER_ACQUIRE(mu) : mu_(mu) {
383 mu_->Lock();
384 }
385
386 ~GenericScopedLock() SANITIZER_RELEASE() { mu_->Unlock(); }
387
388 private:
389 MutexType *mu_;
390
391 GenericScopedLock(const GenericScopedLock &) = delete;
392 void operator=(const GenericScopedLock &) = delete;
393 };
394
395 template <typename MutexType>
396 class SANITIZER_SCOPED_LOCK GenericScopedReadLock {
397 public:
398 explicit GenericScopedReadLock(MutexType *mu) SANITIZER_ACQUIRE(mu)
399 : mu_(mu) {
400 mu_->ReadLock();
401 }
402
403 ~GenericScopedReadLock() SANITIZER_RELEASE() { mu_->ReadUnlock(); }
404
405 private:
406 MutexType *mu_;
407
408 GenericScopedReadLock(const GenericScopedReadLock &) = delete;
409 void operator=(const GenericScopedReadLock &) = delete;
410 };
411
412 template <typename MutexType>
413 class SANITIZER_SCOPED_LOCK GenericScopedRWLock {
414 public:
415 ALWAYS_INLINE explicit GenericScopedRWLock(MutexType *mu, bool write)
416 SANITIZER_ACQUIRE(mu)
417 : mu_(mu), write_(write) {
418 if (write_)
419 mu_->Lock();
420 else
421 mu_->ReadLock();
422 }
423
424 ALWAYS_INLINE ~GenericScopedRWLock() SANITIZER_RELEASE() {
425 if (write_)
426 mu_->Unlock();
427 else
428 mu_->ReadUnlock();
429 }
430
431 private:
432 MutexType *mu_;
433 bool write_;
434
435 GenericScopedRWLock(const GenericScopedRWLock &) = delete;
436 void operator=(const GenericScopedRWLock &) = delete;
437 };
438
439 typedef GenericScopedLock<StaticSpinMutex> SpinMutexLock;
440 typedef GenericScopedLock<Mutex> Lock;
441 typedef GenericScopedReadLock<Mutex> ReadLock;
442 typedef GenericScopedRWLock<Mutex> RWLock;
443
444 } // namespace __sanitizer
445
446 #endif // SANITIZER_MUTEX_H