1 //===-- sanitizer_deadlock_detector.h ---------------------------*- C++ -*-===//
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 // This file is a part of Sanitizer runtime.
11 // The deadlock detector maintains a directed graph of lock acquisitions.
12 // When a lock event happens, the detector checks if the locks already held by
13 // the current thread are reachable from the newly acquired lock.
15 // The detector can handle only a fixed amount of simultaneously live locks
16 // (a lock is alive if it has been locked at least once and has not been
17 // destroyed). When the maximal number of locks is reached the entire graph
18 // is flushed and the new lock epoch is started. The node ids from the old
19 // epochs can not be used with any of the detector methods except for
20 // nodeBelongsToCurrentEpoch().
22 // FIXME: this is work in progress, nothing really works yet.
24 //===----------------------------------------------------------------------===//
26 #ifndef SANITIZER_DEADLOCK_DETECTOR_H
27 #define SANITIZER_DEADLOCK_DETECTOR_H
29 #include "sanitizer_common.h"
30 #include "sanitizer_bvgraph.h"
32 namespace __sanitizer
{
34 // Thread-local state for DeadlockDetector.
35 // It contains the locks currently held by the owning thread.
37 class DeadlockDetectorTLS
{
43 n_recursive_locks
= 0;
46 bool empty() const { return bv_
.empty(); }
48 void ensureCurrentEpoch(uptr current_epoch
) {
49 if (epoch_
== current_epoch
) return;
51 epoch_
= current_epoch
;
54 uptr
getEpoch() const { return epoch_
; }
56 // Returns true if this is the first (non-recursive) acquisition of this lock.
57 bool addLock(uptr lock_id
, uptr current_epoch
) {
58 // Printf("addLock: %zx %zx\n", lock_id, current_epoch);
59 CHECK_EQ(epoch_
, current_epoch
);
60 if (!bv_
.setBit(lock_id
)) {
61 // The lock is already held by this thread, it must be recursive.
62 CHECK_LT(n_recursive_locks
, ARRAY_SIZE(recursive_locks
));
63 recursive_locks
[n_recursive_locks
++] = lock_id
;
69 void removeLock(uptr lock_id
) {
70 if (n_recursive_locks
) {
71 for (sptr i
= n_recursive_locks
- 1; i
>= 0; i
--) {
72 if (recursive_locks
[i
] == lock_id
) {
74 Swap(recursive_locks
[i
], recursive_locks
[n_recursive_locks
]);
79 // Printf("remLock: %zx %zx\n", lock_id, epoch_);
80 CHECK(bv_
.clearBit(lock_id
));
83 const BV
&getLocks(uptr current_epoch
) const {
84 CHECK_EQ(epoch_
, current_epoch
);
91 uptr recursive_locks
[64];
92 uptr n_recursive_locks
;
96 // For deadlock detection to work we need one global DeadlockDetector object
97 // and one DeadlockDetectorTLS object per evey thread.
98 // This class is not thread safe, all concurrent accesses should be guarded
99 // by an external lock.
100 // Most of the methods of this class are not thread-safe (i.e. should
101 // be protected by an external lock) unless explicitly told otherwise.
103 class DeadlockDetector
{
105 typedef BV BitVector
;
107 uptr
size() const { return g_
.size(); }
112 available_nodes_
.clear();
113 recycled_nodes_
.clear();
118 // Allocate new deadlock detector node.
119 // If we are out of available nodes first try to recycle some.
120 // If there is nothing to recycle, flush the graph and increment the epoch.
121 // Associate 'data' (opaque user's object) with the new node.
122 uptr
newNode(uptr data
) {
123 if (!available_nodes_
.empty())
124 return getAvailableNode(data
);
125 if (!recycled_nodes_
.empty()) {
126 CHECK(available_nodes_
.empty());
127 // removeEdgesFrom was called in removeNode.
128 g_
.removeEdgesTo(recycled_nodes_
);
129 available_nodes_
.setUnion(recycled_nodes_
);
130 recycled_nodes_
.clear();
131 return getAvailableNode(data
);
133 // We are out of vacant nodes. Flush and increment the current_epoch_.
134 current_epoch_
+= size();
135 recycled_nodes_
.clear();
136 available_nodes_
.setAll();
138 return getAvailableNode(data
);
141 // Get data associated with the node created by newNode().
142 uptr
getData(uptr node
) const { return data_
[nodeToIndex(node
)]; }
144 bool nodeBelongsToCurrentEpoch(uptr node
) {
145 return node
&& (node
/ size() * size()) == current_epoch_
;
148 void removeNode(uptr node
) {
149 uptr idx
= nodeToIndex(node
);
150 CHECK(!available_nodes_
.getBit(idx
));
151 CHECK(recycled_nodes_
.setBit(idx
));
152 g_
.removeEdgesFrom(idx
);
155 void ensureCurrentEpoch(DeadlockDetectorTLS
<BV
> *dtls
) {
156 dtls
->ensureCurrentEpoch(current_epoch_
);
159 // Returns true if there is a cycle in the graph after this lock event.
160 // Ideally should be called before the lock is acquired so that we can
161 // report a deadlock before a real deadlock happens.
162 bool onLockBefore(DeadlockDetectorTLS
<BV
> *dtls
, uptr cur_node
) {
163 ensureCurrentEpoch(dtls
);
164 uptr cur_idx
= nodeToIndex(cur_node
);
165 return g_
.isReachable(cur_idx
, dtls
->getLocks(current_epoch_
));
168 // Add cur_node to the set of locks held currently by dtls.
169 void onLockAfter(DeadlockDetectorTLS
<BV
> *dtls
, uptr cur_node
) {
170 ensureCurrentEpoch(dtls
);
171 uptr cur_idx
= nodeToIndex(cur_node
);
172 dtls
->addLock(cur_idx
, current_epoch_
);
175 // Experimental *racy* fast path function.
176 // Returns true if all edges from the currently held locks to cur_node exist.
177 bool hasAllEdges(DeadlockDetectorTLS
<BV
> *dtls
, uptr cur_node
) {
178 uptr local_epoch
= dtls
->getEpoch();
179 // Read from current_epoch_ is racy.
180 if (cur_node
&& local_epoch
== current_epoch_
&&
181 local_epoch
== nodeToEpoch(cur_node
)) {
182 uptr cur_idx
= nodeToIndexUnchecked(cur_node
);
183 return g_
.hasAllEdges(dtls
->getLocks(local_epoch
), cur_idx
);
188 // Adds edges from currently held locks to cur_node,
189 // returns the number of added edges, and puts the sources of added edges
190 // into added_edges[].
191 // Should be called before onLockAfter.
192 uptr
addEdges(DeadlockDetectorTLS
<BV
> *dtls
, uptr cur_node
, u32 stk
) {
193 ensureCurrentEpoch(dtls
);
194 uptr cur_idx
= nodeToIndex(cur_node
);
195 uptr added_edges
[40];
196 uptr n_added_edges
= g_
.addEdges(dtls
->getLocks(current_epoch_
), cur_idx
,
197 added_edges
, ARRAY_SIZE(added_edges
));
198 for (uptr i
= 0; i
< n_added_edges
; i
++) {
199 if (n_edges_
< ARRAY_SIZE(edges_
))
200 edges_
[n_edges_
++] = Edge((u16
)added_edges
[i
], (u16
)cur_idx
, stk
);
201 // Printf("Edge [%zd]: %u %zd=>%zd\n", i, stk, added_edges[i], cur_idx);
203 return n_added_edges
;
206 u32
findEdge(uptr from_node
, uptr to_node
) {
207 uptr from_idx
= nodeToIndex(from_node
);
208 uptr to_idx
= nodeToIndex(to_node
);
209 for (uptr i
= 0; i
< n_edges_
; i
++) {
210 if (edges_
[i
].from
== from_idx
&& edges_
[i
].to
== to_idx
)
211 return edges_
[i
].stk
;
216 // Test-only function. Handles the before/after lock events,
217 // returns true if there is a cycle.
218 bool onLock(DeadlockDetectorTLS
<BV
> *dtls
, uptr cur_node
) {
219 ensureCurrentEpoch(dtls
);
220 bool is_reachable
= !isHeld(dtls
, cur_node
) && onLockBefore(dtls
, cur_node
);
221 addEdges(dtls
, cur_node
, 0);
222 onLockAfter(dtls
, cur_node
);
226 // Handles the try_lock event, returns false.
227 // When a try_lock event happens (i.e. a try_lock call succeeds) we need
228 // to add this lock to the currently held locks, but we should not try to
229 // change the lock graph or to detect a cycle. We may want to investigate
230 // whether a more aggressive strategy is possible for try_lock.
231 bool onTryLock(DeadlockDetectorTLS
<BV
> *dtls
, uptr cur_node
) {
232 ensureCurrentEpoch(dtls
);
233 uptr cur_idx
= nodeToIndex(cur_node
);
234 dtls
->addLock(cur_idx
, current_epoch_
);
238 // Returns true iff dtls is empty (no locks are currently held) and we can
239 // add the node to the currently held locks w/o chanding the global state.
240 // This operation is thread-safe as it only touches the dtls.
241 bool onFirstLock(DeadlockDetectorTLS
<BV
> *dtls
, uptr node
) {
242 if (!dtls
->empty()) return false;
243 if (dtls
->getEpoch() && dtls
->getEpoch() == nodeToEpoch(node
)) {
244 dtls
->addLock(nodeToIndexUnchecked(node
), nodeToEpoch(node
));
250 // Finds a path between the lock 'cur_node' (currently not held in dtls)
251 // and some currently held lock, returns the length of the path
253 uptr
findPathToLock(DeadlockDetectorTLS
<BV
> *dtls
, uptr cur_node
, uptr
*path
,
255 tmp_bv_
.copyFrom(dtls
->getLocks(current_epoch_
));
256 uptr idx
= nodeToIndex(cur_node
);
257 CHECK(!tmp_bv_
.getBit(idx
));
258 uptr res
= g_
.findShortestPath(idx
, tmp_bv_
, path
, path_size
);
259 for (uptr i
= 0; i
< res
; i
++)
260 path
[i
] = indexToNode(path
[i
]);
262 CHECK_EQ(path
[0], cur_node
);
266 // Handle the unlock event.
267 // This operation is thread-safe as it only touches the dtls.
268 void onUnlock(DeadlockDetectorTLS
<BV
> *dtls
, uptr node
) {
269 if (dtls
->getEpoch() == nodeToEpoch(node
))
270 dtls
->removeLock(nodeToIndexUnchecked(node
));
273 // Tries to handle the lock event w/o writing to global state.
274 // Returns true on success.
275 // This operation is thread-safe as it only touches the dtls
276 // (modulo racy nature of hasAllEdges).
277 bool onLockFast(DeadlockDetectorTLS
<BV
> *dtls
, uptr node
) {
278 if (hasAllEdges(dtls
, node
)) {
279 dtls
->addLock(nodeToIndexUnchecked(node
), nodeToEpoch(node
));
285 bool isHeld(DeadlockDetectorTLS
<BV
> *dtls
, uptr node
) const {
286 return dtls
->getLocks(current_epoch_
).getBit(nodeToIndex(node
));
289 uptr
testOnlyGetEpoch() const { return current_epoch_
; }
290 bool testOnlyHasEdge(uptr l1
, uptr l2
) {
291 return g_
.hasEdge(nodeToIndex(l1
), nodeToIndex(l2
));
293 // idx1 and idx2 are raw indices to g_, not lock IDs.
294 bool testOnlyHasEdgeRaw(uptr idx1
, uptr idx2
) {
295 return g_
.hasEdge(idx1
, idx2
);
299 for (uptr from
= 0; from
< size(); from
++)
300 for (uptr to
= 0; to
< size(); to
++)
301 if (g_
.hasEdge(from
, to
))
302 Printf(" %zx => %zx\n", from
, to
);
306 void check_idx(uptr idx
) const { CHECK_LT(idx
, size()); }
308 void check_node(uptr node
) const {
309 CHECK_GE(node
, size());
310 CHECK_EQ(current_epoch_
, nodeToEpoch(node
));
313 uptr
indexToNode(uptr idx
) const {
315 return idx
+ current_epoch_
;
318 uptr
nodeToIndexUnchecked(uptr node
) const { return node
% size(); }
320 uptr
nodeToIndex(uptr node
) const {
322 return nodeToIndexUnchecked(node
);
325 uptr
nodeToEpoch(uptr node
) const { return node
/ size() * size(); }
327 uptr
getAvailableNode(uptr data
) {
328 uptr idx
= available_nodes_
.getAndClearFirstOne();
330 return indexToNode(idx
);
337 // FIXME: replace with initializer list once the tests are built as c++11.
338 Edge(u16 f
, u16 t
, u32 s
) : from(f
), to(t
), stk(s
) {}
347 uptr data_
[BV::kSize
];
348 Edge edges_
[BV::kSize
* 32];
352 } // namespace __sanitizer
354 #endif // SANITIZER_DEADLOCK_DETECTOR_H