447 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file is a part of ThreadSanitizer/AddressSanitizer runtime.10//11//===----------------------------------------------------------------------===//12 13#ifndef SANITIZER_MUTEX_H14#define SANITIZER_MUTEX_H15 16#include "sanitizer_atomic.h"17#include "sanitizer_internal_defs.h"18#include "sanitizer_libc.h"19#include "sanitizer_thread_safety.h"20 21namespace __sanitizer {22 23class 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 53class 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 object65// (destruction-safety).66class 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 79typedef int MutexType;80 81enum {82 // Used as sentinel and to catch unassigned types83 // (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 support101// THREADLOCAL variables they are not usable early on during process init when102// `__sanitizer::Mutex` is used.103#define SANITIZER_CHECK_DEADLOCKS \104 (SANITIZER_DEBUG && !SANITIZER_GO && SANITIZER_SUPPORTS_THREADLOCAL && !SANITIZER_APPLE)105 106#if SANITIZER_CHECK_DEADLOCKS107struct 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#endif117 118class CheckedMutex {119 public:120 explicit constexpr CheckedMutex(MutexType type)121#if SANITIZER_CHECK_DEADLOCKS122 : type_(type)123#endif124 {125 }126 127 ALWAYS_INLINE void Lock() {128#if SANITIZER_CHECK_DEADLOCKS129 LockImpl(GET_CALLER_PC());130#endif131 }132 133 ALWAYS_INLINE void Unlock() {134#if SANITIZER_CHECK_DEADLOCKS135 UnlockImpl();136#endif137 }138 139 // Checks that the current thread does not hold any mutexes140 // (e.g. when returning from a runtime function to user code).141 static void CheckNoLocks() {142#if SANITIZER_CHECK_DEADLOCKS143 CheckNoLocksImpl();144#endif145 }146 147 private:148#if SANITIZER_CHECK_DEADLOCKS149 const MutexType type_;150 151 void LockImpl(uptr pc);152 void UnlockImpl();153 static void CheckNoLocksImpl();154#endif155};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.161class 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 unlocking182 // 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 kWriterSpinWait204 // 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) != 0241 ? 0242 : ((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 unlocking266 // 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 thread311 // is the thread which owns the mutex. This behavior, while more strictly312 // correct, causes problems in cases like StopTheWorld, where a parent thread313 // owns the mutex but a child checks that it is locked. Rather than314 // maintaining complex state to work around those situations, the check only315 // 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-locked334 // - number of waiting readers,335 // if not zero, the mutex is write-locked336 // - number of waiting writers,337 // if non zero, the mutex is read- or write-locked338 // And 2 flags:339 // - writer lock340 // if set, the mutex is write-locked341 // - a writer is awake and spin-waiting342 // the flag is used to prevent thundering herd problem343 // (new writers are not woken if this flag is set)344 // - a reader is awake and spin-waiting345 //346 // Both writers and readers use active spinning before blocking.347 // But readers are more aggressive and always take the mutex348 // if there are any other readers.349 // After wake up both writers and readers compete to lock the350 // mutex again. This is needed to allow repeated locks even in presence351 // 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 376void FutexWait(atomic_uint32_t *p, u32 cmp);377void FutexWake(atomic_uint32_t *p, u32 count);378 379template <typename MutexType>380class 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 395template <typename MutexType>396class 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 412template <typename MutexType>413class 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 else421 mu_->ReadLock();422 }423 424 ALWAYS_INLINE ~GenericScopedRWLock() SANITIZER_RELEASE() {425 if (write_)426 mu_->Unlock();427 else428 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 439typedef GenericScopedLock<StaticSpinMutex> SpinMutexLock;440typedef GenericScopedLock<Mutex> Lock;441typedef GenericScopedReadLock<Mutex> ReadLock;442typedef GenericScopedRWLock<Mutex> RWLock;443 444} // namespace __sanitizer445 446#endif // SANITIZER_MUTEX_H447