Skip to content

Commit a63632a

Browse files
committedFeb 14, 2014
[tsan] rudimentary support for deadlock detector in tsan (nothing really works yet except for a single tiny test). Also rename tsan's DeadlockDetector to InternalDeadlockDetector
llvm-svn: 201407
1 parent 127e93e commit a63632a

File tree

7 files changed

+72
-10
lines changed

7 files changed

+72
-10
lines changed
 
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
// RUN: %clangxx_tsan %s -o %t
2+
// RUN: TSAN_OPTIONS=detect_deadlocks=1 %t 2>&1 | FileCheck %s
3+
#include <pthread.h>
4+
5+
int main() {
6+
pthread_mutex_t mu1, mu2;
7+
pthread_mutex_init(&mu1, NULL);
8+
pthread_mutex_init(&mu2, NULL);
9+
10+
// mu1 => mu2
11+
pthread_mutex_lock(&mu1);
12+
pthread_mutex_lock(&mu2);
13+
pthread_mutex_unlock(&mu2);
14+
pthread_mutex_unlock(&mu1);
15+
16+
// mu2 => mu1
17+
pthread_mutex_lock(&mu2);
18+
pthread_mutex_lock(&mu1);
19+
// CHECK: ThreadSanitizer: lock-order-inversion (potential deadlock)
20+
pthread_mutex_unlock(&mu1);
21+
pthread_mutex_unlock(&mu2);
22+
23+
pthread_mutex_destroy(&mu1);
24+
pthread_mutex_destroy(&mu2);
25+
}

‎compiler-rt/lib/tsan/rtl/tsan_mutex.cc

+7-7
Original file line numberDiff line numberDiff line change
@@ -123,12 +123,12 @@ void InitializeMutex() {
123123
#endif
124124
}
125125

126-
DeadlockDetector::DeadlockDetector() {
126+
InternalDeadlockDetector::InternalDeadlockDetector() {
127127
// Rely on zero initialization because some mutexes can be locked before ctor.
128128
}
129129

130130
#if TSAN_DEBUG && !TSAN_GO
131-
void DeadlockDetector::Lock(MutexType t) {
131+
void InternalDeadlockDetector::Lock(MutexType t) {
132132
// Printf("LOCK %d @%zu\n", t, seq_ + 1);
133133
CHECK_GT(t, MutexTypeInvalid);
134134
CHECK_LT(t, MutexTypeCount);
@@ -155,7 +155,7 @@ void DeadlockDetector::Lock(MutexType t) {
155155
}
156156
}
157157

158-
void DeadlockDetector::Unlock(MutexType t) {
158+
void InternalDeadlockDetector::Unlock(MutexType t) {
159159
// Printf("UNLO %d @%zu #%zu\n", t, seq_, locked_[t]);
160160
CHECK(locked_[t]);
161161
locked_[t] = 0;
@@ -210,7 +210,7 @@ Mutex::~Mutex() {
210210

211211
void Mutex::Lock() {
212212
#if TSAN_DEBUG && !TSAN_GO
213-
cur_thread()->deadlock_detector.Lock(type_);
213+
cur_thread()->internal_deadlock_detector.Lock(type_);
214214
#endif
215215
uptr cmp = kUnlocked;
216216
if (atomic_compare_exchange_strong(&state_, &cmp, kWriteLock,
@@ -235,13 +235,13 @@ void Mutex::Unlock() {
235235
(void)prev;
236236
DCHECK_NE(prev & kWriteLock, 0);
237237
#if TSAN_DEBUG && !TSAN_GO
238-
cur_thread()->deadlock_detector.Unlock(type_);
238+
cur_thread()->internal_deadlock_detector.Unlock(type_);
239239
#endif
240240
}
241241

242242
void Mutex::ReadLock() {
243243
#if TSAN_DEBUG && !TSAN_GO
244-
cur_thread()->deadlock_detector.Lock(type_);
244+
cur_thread()->internal_deadlock_detector.Lock(type_);
245245
#endif
246246
uptr prev = atomic_fetch_add(&state_, kReadLock, memory_order_acquire);
247247
if ((prev & kWriteLock) == 0)
@@ -263,7 +263,7 @@ void Mutex::ReadUnlock() {
263263
DCHECK_EQ(prev & kWriteLock, 0);
264264
DCHECK_GT(prev & ~kWriteLock, 0);
265265
#if TSAN_DEBUG && !TSAN_GO
266-
cur_thread()->deadlock_detector.Unlock(type_);
266+
cur_thread()->internal_deadlock_detector.Unlock(type_);
267267
#endif
268268
}
269269

‎compiler-rt/lib/tsan/rtl/tsan_mutex.h

+2-2
Original file line numberDiff line numberDiff line change
@@ -65,9 +65,9 @@ class Mutex {
6565
typedef GenericScopedLock<Mutex> Lock;
6666
typedef GenericScopedReadLock<Mutex> ReadLock;
6767

68-
class DeadlockDetector {
68+
class InternalDeadlockDetector {
6969
public:
70-
DeadlockDetector();
70+
InternalDeadlockDetector();
7171
void Lock(MutexType t);
7272
void Unlock(MutexType t);
7373
private:

‎compiler-rt/lib/tsan/rtl/tsan_rtl.h

+3-1
Original file line numberDiff line numberDiff line change
@@ -30,6 +30,7 @@
3030
#include "sanitizer_common/sanitizer_allocator_internal.h"
3131
#include "sanitizer_common/sanitizer_asm.h"
3232
#include "sanitizer_common/sanitizer_common.h"
33+
#include "sanitizer_common/sanitizer_deadlock_detector.h"
3334
#include "sanitizer_common/sanitizer_libignore.h"
3435
#include "sanitizer_common/sanitizer_suppressions.h"
3536
#include "sanitizer_common/sanitizer_thread_registry.h"
@@ -449,7 +450,8 @@ struct ThreadState {
449450
const uptr tls_size;
450451
ThreadContext *tctx;
451452

452-
DeadlockDetector deadlock_detector;
453+
InternalDeadlockDetector internal_deadlock_detector;
454+
__sanitizer::DeadlockDetectorTLS deadlock_detector_tls;
453455

454456
bool in_signal_handler;
455457
SignalContext *signal_ctx;

‎compiler-rt/lib/tsan/rtl/tsan_rtl_mutex.cc

+33
Original file line numberDiff line numberDiff line change
@@ -11,6 +11,8 @@
1111
//
1212
//===----------------------------------------------------------------------===//
1313

14+
#include <sanitizer_common/sanitizer_deadlock_detector.h>
15+
1416
#include "tsan_rtl.h"
1517
#include "tsan_flags.h"
1618
#include "tsan_sync.h"
@@ -20,6 +22,14 @@
2022

2123
namespace __tsan {
2224

25+
static __sanitizer::DeadlockDetector<TwoLevelBitVector<> > g_deadlock_detector;
26+
27+
static void EnsureDeadlockDetectorID(ThreadState *thr, SyncVar *s) {
28+
if (!s->deadlock_detector_id)
29+
s->deadlock_detector_id =
30+
g_deadlock_detector.newNode(reinterpret_cast<uptr>(s));
31+
}
32+
2333
void MutexCreate(ThreadState *thr, uptr pc, uptr addr,
2434
bool rw, bool recursive, bool linker_init) {
2535
Context *ctx = CTX();
@@ -35,6 +45,10 @@ void MutexCreate(ThreadState *thr, uptr pc, uptr addr,
3545
s->is_rw = rw;
3646
s->is_recursive = recursive;
3747
s->is_linker_init = linker_init;
48+
if (common_flags()->detect_deadlocks) {
49+
EnsureDeadlockDetectorID(thr, s);
50+
Printf("MutexCreate: %zx\n", s->deadlock_detector_id);
51+
}
3852
s->mtx.Unlock();
3953
}
4054

@@ -51,6 +65,10 @@ void MutexDestroy(ThreadState *thr, uptr pc, uptr addr) {
5165
SyncVar *s = ctx->synctab.GetAndRemove(thr, pc, addr);
5266
if (s == 0)
5367
return;
68+
if (common_flags()->detect_deadlocks) {
69+
EnsureDeadlockDetectorID(thr, s);
70+
Printf("MutexDestroy: %zx\n", s->deadlock_detector_id);
71+
}
5472
if (IsAppMem(addr)) {
5573
CHECK(!thr->is_freeing);
5674
thr->is_freeing = true;
@@ -104,6 +122,15 @@ void MutexLock(ThreadState *thr, uptr pc, uptr addr, int rec) {
104122
}
105123
s->recursion += rec;
106124
thr->mset.Add(s->GetId(), true, thr->fast_state.epoch());
125+
if (common_flags()->detect_deadlocks) {
126+
EnsureDeadlockDetectorID(thr, s);
127+
bool has_deadlock = g_deadlock_detector.onLock(&thr->deadlock_detector_tls,
128+
s->deadlock_detector_id);
129+
Printf("MutexLock: %zx;%s\n", s->deadlock_detector_id,
130+
has_deadlock
131+
? " ThreadSanitizer: lock-order-inversion (potential deadlock)"
132+
: "");
133+
}
107134
s->mtx.Unlock();
108135
}
109136

@@ -140,6 +167,12 @@ int MutexUnlock(ThreadState *thr, uptr pc, uptr addr, bool all) {
140167
}
141168
}
142169
thr->mset.Del(s->GetId(), true);
170+
if (common_flags()->detect_deadlocks) {
171+
EnsureDeadlockDetectorID(thr, s);
172+
Printf("MutexUnlock: %zx\n", s->deadlock_detector_id);
173+
g_deadlock_detector.onUnlock(&thr->deadlock_detector_tls,
174+
s->deadlock_detector_id);
175+
}
143176
s->mtx.Unlock();
144177
return rec;
145178
}

‎compiler-rt/lib/tsan/rtl/tsan_sync.cc

+1
Original file line numberDiff line numberDiff line change
@@ -62,6 +62,7 @@ SyncVar* SyncTab::Create(ThreadState *thr, uptr pc, uptr addr) {
6262
void *mem = internal_alloc(MBlockSync, sizeof(SyncVar));
6363
const u64 uid = atomic_fetch_add(&uid_gen_, 1, memory_order_relaxed);
6464
SyncVar *res = new(mem) SyncVar(addr, uid);
65+
res->deadlock_detector_id = 0;
6566
#ifndef TSAN_GO
6667
res->creation_stack_id = CurrentStackId(thr, pc);
6768
#endif

‎compiler-rt/lib/tsan/rtl/tsan_sync.h

+1
Original file line numberDiff line numberDiff line change
@@ -61,6 +61,7 @@ struct SyncVar {
6161
SyncClock read_clock; // Used for rw mutexes only.
6262
u32 creation_stack_id;
6363
int owner_tid; // Set only by exclusive owners.
64+
uptr deadlock_detector_id;
6465
u64 last_lock;
6566
int recursion;
6667
bool is_rw;

0 commit comments

Comments
 (0)
Please sign in to comment.