blob: 1c177d8e7cca3aa3948cd984a22035fbc544f098 [file] [log] [blame]
//===-- sanitizer_mutex.cpp -----------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file is shared between AddressSanitizer and ThreadSanitizer
// run-time libraries.
//===----------------------------------------------------------------------===//
#include "sanitizer_mutex.h"
#include "sanitizer_common.h"
namespace __sanitizer {
void StaticSpinMutex::LockSlow() {
for (int i = 0;; i++) {
if (i < 100)
proc_yield(1);
else
internal_sched_yield();
if (atomic_load(&state_, memory_order_relaxed) == 0 &&
atomic_exchange(&state_, 1, memory_order_acquire) == 0)
return;
}
}
void Semaphore::Wait() {
u32 count = atomic_load(&state_, memory_order_relaxed);
for (;;) {
if (count == 0) {
FutexWait(&state_, 0);
count = atomic_load(&state_, memory_order_relaxed);
continue;
}
if (atomic_compare_exchange_weak(&state_, &count, count - 1,
memory_order_acquire))
break;
}
}
void Semaphore::Post(u32 count) {
CHECK_NE(count, 0);
atomic_fetch_add(&state_, count, memory_order_release);
FutexWake(&state_, count);
}
#if SANITIZER_CHECK_DEADLOCKS
// An empty mutex meta table, it effectively disables deadlock detection.
// Each tool can override the table to define own mutex hierarchy and
// enable deadlock detection.
// The table defines a static mutex type hierarchy (what mutex types can be locked
// under what mutex types). This table is checked to be acyclic and then
// actual mutex lock/unlock operations are checked to adhere to this hierarchy.
// The checking happens on mutex types rather than on individual mutex instances
// because doing it on mutex instances will both significantly complicate
// the implementation, worsen performance and memory overhead and is mostly
// unnecessary (we almost never lock multiple mutexes of the same type recursively).
static constexpr int kMutexTypeMax = 20;
SANITIZER_WEAK_ATTRIBUTE MutexMeta mutex_meta[kMutexTypeMax] = {};
SANITIZER_WEAK_ATTRIBUTE void PrintMutexPC(uptr pc) {}
static StaticSpinMutex mutex_meta_mtx;
static int mutex_type_count = -1;
// Adjacency matrix of what mutexes can be locked under what mutexes.
static bool mutex_can_lock[kMutexTypeMax][kMutexTypeMax];
// Mutex types with MutexMulti mark.
static bool mutex_multi[kMutexTypeMax];
void DebugMutexInit() {
// Build adjacency matrix.
bool leaf[kMutexTypeMax];
internal_memset(&leaf, 0, sizeof(leaf));
int cnt[kMutexTypeMax];
internal_memset(&cnt, 0, sizeof(cnt));
for (int t = 0; t < kMutexTypeMax; t++) {
mutex_type_count = t;
if (!mutex_meta[t].name)
break;
CHECK_EQ(t, mutex_meta[t].type);
for (uptr j = 0; j < ARRAY_SIZE(mutex_meta[t].can_lock); j++) {
MutexType z = mutex_meta[t].can_lock[j];
if (z == MutexInvalid)
break;
if (z == MutexLeaf) {
CHECK(!leaf[t]);
leaf[t] = true;
continue;
}
if (z == MutexMulti) {
mutex_multi[t] = true;
continue;
}
CHECK_LT(z, kMutexTypeMax);
CHECK(!mutex_can_lock[t][z]);
mutex_can_lock[t][z] = true;
cnt[t]++;
}
}
// Indicates the array is not properly terminated.
CHECK_LT(mutex_type_count, kMutexTypeMax);
// Add leaf mutexes.
for (int t = 0; t < mutex_type_count; t++) {
if (!leaf[t])
continue;
CHECK_EQ(cnt[t], 0);
for (int z = 0; z < mutex_type_count; z++) {
if (z == MutexInvalid || t == z || leaf[z])
continue;
CHECK(!mutex_can_lock[z][t]);
mutex_can_lock[z][t] = true;
}
}
// Build the transitive closure and check that the graphs is acyclic.
u32 trans[kMutexTypeMax];
static_assert(sizeof(trans[0]) * 8 >= kMutexTypeMax,
"kMutexTypeMax does not fit into u32, switch to u64");
internal_memset(&trans, 0, sizeof(trans));
for (int i = 0; i < mutex_type_count; i++) {
for (int j = 0; j < mutex_type_count; j++)
if (mutex_can_lock[i][j])
trans[i] |= 1 << j;
}
for (int k = 0; k < mutex_type_count; k++) {
for (int i = 0; i < mutex_type_count; i++) {
if (trans[i] & (1 << k))
trans[i] |= trans[k];
}
}
for (int i = 0; i < mutex_type_count; i++) {
if (trans[i] & (1 << i)) {
Printf("Mutex %s participates in a cycle\n", mutex_meta[i].name);
Die();
}
}
}
struct InternalDeadlockDetector {
struct LockDesc {
u64 seq;
uptr pc;
int recursion;
};
int initialized;
u64 sequence;
LockDesc locked[kMutexTypeMax];
void Lock(MutexType type, uptr pc) {
if (!Initialize(type))
return;
CHECK_LT(type, mutex_type_count);
// Find the last locked mutex type.
// This is the type we will use for hierarchy checks.
u64 max_seq = 0;
MutexType max_idx = MutexInvalid;
for (int i = 0; i != mutex_type_count; i++) {
if (locked[i].seq == 0)
continue;
CHECK_NE(locked[i].seq, max_seq);
if (max_seq < locked[i].seq) {
max_seq = locked[i].seq;
max_idx = (MutexType)i;
}
}
if (max_idx == type && mutex_multi[type]) {
// Recursive lock of the same type.
CHECK_EQ(locked[type].seq, max_seq);
CHECK(locked[type].pc);
locked[type].recursion++;
return;
}
if (max_idx != MutexInvalid && !mutex_can_lock[max_idx][type]) {
Printf("%s: internal deadlock: can't lock %s under %s mutex\n", SanitizerToolName,
mutex_meta[type].name, mutex_meta[max_idx].name);
PrintMutexPC(pc);
CHECK(0);
}
locked[type].seq = ++sequence;
locked[type].pc = pc;
locked[type].recursion = 1;
}
void Unlock(MutexType type) {
if (!Initialize(type))
return;
CHECK_LT(type, mutex_type_count);
CHECK(locked[type].seq);
CHECK_GT(locked[type].recursion, 0);
if (--locked[type].recursion)
return;
locked[type].seq = 0;
locked[type].pc = 0;
}
void CheckNoLocks() {
for (int i = 0; i < mutex_type_count; i++) CHECK_EQ(locked[i].recursion, 0);
}
bool Initialize(MutexType type) {
if (type == MutexUnchecked || type == MutexInvalid)
return false;
CHECK_GT(type, MutexInvalid);
if (initialized != 0)
return initialized > 0;
initialized = -1;
SpinMutexLock lock(&mutex_meta_mtx);
if (mutex_type_count < 0)
DebugMutexInit();
initialized = mutex_type_count ? 1 : -1;
return initialized > 0;
}
};
static THREADLOCAL InternalDeadlockDetector deadlock_detector;
void CheckedMutex::LockImpl(uptr pc) { deadlock_detector.Lock(type_, pc); }
void CheckedMutex::UnlockImpl() { deadlock_detector.Unlock(type_); }
void CheckedMutex::CheckNoLocksImpl() { deadlock_detector.CheckNoLocks(); }
#endif
} // namespace __sanitizer