1 //===-- sanitizer_deadlock_detector1.cc -----------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Deadlock detector implementation based on NxN adjacency bit matrix.
12 //===----------------------------------------------------------------------===//
14 #include "sanitizer_deadlock_detector_interface.h"
15 #include "sanitizer_deadlock_detector.h"
16 #include "sanitizer_allocator_internal.h"
17 #include "sanitizer_placement_new.h"
18 #include "sanitizer_mutex.h"
20 #if SANITIZER_DEADLOCK_DETECTOR_VERSION == 1
22 namespace __sanitizer
{
24 typedef TwoLevelBitVector
<> DDBV
; // DeadlockDetector's bit vector.
26 struct DDPhysicalThread
{
29 struct DDLogicalThread
{
31 DeadlockDetectorTLS
<DDBV
> dd
;
36 struct DD
: public DDetector
{
38 DeadlockDetector
<DDBV
> dd
;
41 explicit DD(const DDFlags
*flags
);
43 DDPhysicalThread
* CreatePhysicalThread();
44 void DestroyPhysicalThread(DDPhysicalThread
*pt
);
46 DDLogicalThread
* CreateLogicalThread(u64 ctx
);
47 void DestroyLogicalThread(DDLogicalThread
*lt
);
49 void MutexInit(DDCallback
*cb
, DDMutex
*m
);
50 void MutexBeforeLock(DDCallback
*cb
, DDMutex
*m
, bool wlock
);
51 void MutexAfterLock(DDCallback
*cb
, DDMutex
*m
, bool wlock
, bool trylock
);
52 void MutexBeforeUnlock(DDCallback
*cb
, DDMutex
*m
, bool wlock
);
53 void MutexDestroy(DDCallback
*cb
, DDMutex
*m
);
55 DDReport
*GetReport(DDCallback
*cb
);
57 void MutexEnsureID(DDLogicalThread
*lt
, DDMutex
*m
);
58 void ReportDeadlock(DDCallback
*cb
, DDMutex
*m
);
61 DDetector
*DDetector::Create(const DDFlags
*flags
) {
63 void *mem
= MmapOrDie(sizeof(DD
), "deadlock detector");
64 return new(mem
) DD(flags
);
67 DD::DD(const DDFlags
*flags
)
72 DDPhysicalThread
* DD::CreatePhysicalThread() {
76 void DD::DestroyPhysicalThread(DDPhysicalThread
*pt
) {
79 DDLogicalThread
* DD::CreateLogicalThread(u64 ctx
) {
80 DDLogicalThread
*lt
= (DDLogicalThread
*)InternalAlloc(sizeof(*lt
));
83 lt
->report_pending
= false;
87 void DD::DestroyLogicalThread(DDLogicalThread
*lt
) {
88 lt
->~DDLogicalThread();
92 void DD::MutexInit(DDCallback
*cb
, DDMutex
*m
) {
94 m
->stk
= cb
->Unwind();
97 void DD::MutexEnsureID(DDLogicalThread
*lt
, DDMutex
*m
) {
98 if (!dd
.nodeBelongsToCurrentEpoch(m
->id
))
99 m
->id
= dd
.newNode(reinterpret_cast<uptr
>(m
));
100 dd
.ensureCurrentEpoch(<
->dd
);
103 void DD::MutexBeforeLock(DDCallback
*cb
,
104 DDMutex
*m
, bool wlock
) {
105 DDLogicalThread
*lt
= cb
->lt
;
106 if (lt
->dd
.empty()) return; // This will be the first lock held by lt.
107 if (dd
.hasAllEdges(<
->dd
, m
->id
)) return; // We already have all edges.
108 SpinMutexLock
lk(&mtx
);
109 MutexEnsureID(lt
, m
);
110 if (dd
.isHeld(<
->dd
, m
->id
))
111 return; // FIXME: allow this only for recursive locks.
112 if (dd
.onLockBefore(<
->dd
, m
->id
)) {
113 // Actually add this edge now so that we have all the stack traces.
114 dd
.addEdges(<
->dd
, m
->id
, cb
->Unwind(), cb
->UniqueTid());
115 ReportDeadlock(cb
, m
);
119 void DD::ReportDeadlock(DDCallback
*cb
, DDMutex
*m
) {
120 DDLogicalThread
*lt
= cb
->lt
;
122 uptr len
= dd
.findPathToLock(<
->dd
, m
->id
, path
, ARRAY_SIZE(path
));
123 CHECK_GT(len
, 0U); // Hm.. cycle of 10 locks? I'd like to see that.
124 CHECK_EQ(m
->id
, path
[0]);
125 lt
->report_pending
= true;
126 DDReport
*rep
= <
->rep
;
128 for (uptr i
= 0; i
< len
; i
++) {
130 uptr to
= path
[(i
+ 1) % len
];
131 DDMutex
*m0
= (DDMutex
*)dd
.getData(from
);
132 DDMutex
*m1
= (DDMutex
*)dd
.getData(to
);
134 u32 stk_from
= -1U, stk_to
= -1U;
136 dd
.findEdge(from
, to
, &stk_from
, &stk_to
, &unique_tid
);
137 // Printf("Edge: %zd=>%zd: %u/%u T%d\n", from, to, stk_from, stk_to,
139 rep
->loop
[i
].thr_ctx
= unique_tid
;
140 rep
->loop
[i
].mtx_ctx0
= m0
->ctx
;
141 rep
->loop
[i
].mtx_ctx1
= m1
->ctx
;
142 rep
->loop
[i
].stk
[0] = stk_to
;
143 rep
->loop
[i
].stk
[1] = stk_from
;
147 void DD::MutexAfterLock(DDCallback
*cb
, DDMutex
*m
, bool wlock
, bool trylock
) {
148 DDLogicalThread
*lt
= cb
->lt
;
150 if (flags
.second_deadlock_stack
)
152 // Printf("T%p MutexLock: %zx stk %u\n", lt, m->id, stk);
153 if (dd
.onFirstLock(<
->dd
, m
->id
, stk
))
155 if (dd
.onLockFast(<
->dd
, m
->id
, stk
))
158 SpinMutexLock
lk(&mtx
);
159 MutexEnsureID(lt
, m
);
160 if (wlock
) // Only a recursive rlock may be held.
161 CHECK(!dd
.isHeld(<
->dd
, m
->id
));
163 dd
.addEdges(<
->dd
, m
->id
, stk
? stk
: cb
->Unwind(), cb
->UniqueTid());
164 dd
.onLockAfter(<
->dd
, m
->id
, stk
);
167 void DD::MutexBeforeUnlock(DDCallback
*cb
, DDMutex
*m
, bool wlock
) {
168 // Printf("T%p MutexUnLock: %zx\n", cb->lt, m->id);
169 dd
.onUnlock(&cb
->lt
->dd
, m
->id
);
172 void DD::MutexDestroy(DDCallback
*cb
,
175 SpinMutexLock
lk(&mtx
);
176 if (dd
.nodeBelongsToCurrentEpoch(m
->id
))
177 dd
.removeNode(m
->id
);
181 DDReport
*DD::GetReport(DDCallback
*cb
) {
182 if (!cb
->lt
->report_pending
)
184 cb
->lt
->report_pending
= false;
188 } // namespace __sanitizer
189 #endif // #if SANITIZER_DEADLOCK_DETECTOR_VERSION == 1