Daily bump.
[official-gcc.git] / libsanitizer / sanitizer_common / sanitizer_deadlock_detector.h
blob949c486a14acc6386649f6dc349b759d5f29686e
1 //===-- sanitizer_deadlock_detector.h ---------------------------*- C++ -*-===//
2 //
3 // This file is distributed under the University of Illinois Open Source
4 // License. See LICENSE.TXT for details.
5 //
6 //===----------------------------------------------------------------------===//
7 //
8 // This file is a part of Sanitizer runtime.
9 // The deadlock detector maintains a directed graph of lock acquisitions.
10 // When a lock event happens, the detector checks if the locks already held by
11 // the current thread are reachable from the newly acquired lock.
13 // The detector can handle only a fixed amount of simultaneously live locks
14 // (a lock is alive if it has been locked at least once and has not been
15 // destroyed). When the maximal number of locks is reached the entire graph
16 // is flushed and the new lock epoch is started. The node ids from the old
17 // epochs can not be used with any of the detector methods except for
18 // nodeBelongsToCurrentEpoch().
20 // FIXME: this is work in progress, nothing really works yet.
22 //===----------------------------------------------------------------------===//
24 #ifndef SANITIZER_DEADLOCK_DETECTOR_H
25 #define SANITIZER_DEADLOCK_DETECTOR_H
27 #include "sanitizer_common.h"
28 #include "sanitizer_bvgraph.h"
30 namespace __sanitizer {
32 // Thread-local state for DeadlockDetector.
33 // It contains the locks currently held by the owning thread.
34 template <class BV>
35 class DeadlockDetectorTLS {
36 public:
37 // No CTOR.
38 void clear() {
39 bv_.clear();
40 epoch_ = 0;
41 n_recursive_locks = 0;
42 n_all_locks_ = 0;
45 bool empty() const { return bv_.empty(); }
47 void ensureCurrentEpoch(uptr current_epoch) {
48 if (epoch_ == current_epoch) return;
49 bv_.clear();
50 epoch_ = current_epoch;
53 uptr getEpoch() const { return epoch_; }
55 // Returns true if this is the first (non-recursive) acquisition of this lock.
56 bool addLock(uptr lock_id, uptr current_epoch, u32 stk) {
57 // Printf("addLock: %zx %zx stk %u\n", lock_id, current_epoch, stk);
58 CHECK_EQ(epoch_, current_epoch);
59 if (!bv_.setBit(lock_id)) {
60 // The lock is already held by this thread, it must be recursive.
61 CHECK_LT(n_recursive_locks, ARRAY_SIZE(recursive_locks));
62 recursive_locks[n_recursive_locks++] = lock_id;
63 return false;
65 CHECK_LT(n_all_locks_, ARRAY_SIZE(all_locks_with_contexts_));
66 // lock_id < BV::kSize, can cast to a smaller int.
67 u32 lock_id_short = static_cast<u32>(lock_id);
68 LockWithContext l = {lock_id_short, stk};
69 all_locks_with_contexts_[n_all_locks_++] = l;
70 return true;
73 void removeLock(uptr lock_id) {
74 if (n_recursive_locks) {
75 for (sptr i = n_recursive_locks - 1; i >= 0; i--) {
76 if (recursive_locks[i] == lock_id) {
77 n_recursive_locks--;
78 Swap(recursive_locks[i], recursive_locks[n_recursive_locks]);
79 return;
83 // Printf("remLock: %zx %zx\n", lock_id, epoch_);
84 CHECK(bv_.clearBit(lock_id));
85 if (n_all_locks_) {
86 for (sptr i = n_all_locks_ - 1; i >= 0; i--) {
87 if (all_locks_with_contexts_[i].lock == static_cast<u32>(lock_id)) {
88 Swap(all_locks_with_contexts_[i],
89 all_locks_with_contexts_[n_all_locks_ - 1]);
90 n_all_locks_--;
91 break;
97 u32 findLockContext(uptr lock_id) {
98 for (uptr i = 0; i < n_all_locks_; i++)
99 if (all_locks_with_contexts_[i].lock == static_cast<u32>(lock_id))
100 return all_locks_with_contexts_[i].stk;
101 return 0;
104 const BV &getLocks(uptr current_epoch) const {
105 CHECK_EQ(epoch_, current_epoch);
106 return bv_;
109 uptr getNumLocks() const { return n_all_locks_; }
110 uptr getLock(uptr idx) const { return all_locks_with_contexts_[idx].lock; }
112 private:
113 BV bv_;
114 uptr epoch_;
115 uptr recursive_locks[64];
116 uptr n_recursive_locks;
117 struct LockWithContext {
118 u32 lock;
119 u32 stk;
121 LockWithContext all_locks_with_contexts_[64];
122 uptr n_all_locks_;
125 // DeadlockDetector.
126 // For deadlock detection to work we need one global DeadlockDetector object
127 // and one DeadlockDetectorTLS object per evey thread.
128 // This class is not thread safe, all concurrent accesses should be guarded
129 // by an external lock.
130 // Most of the methods of this class are not thread-safe (i.e. should
131 // be protected by an external lock) unless explicitly told otherwise.
132 template <class BV>
133 class DeadlockDetector {
134 public:
135 typedef BV BitVector;
137 uptr size() const { return g_.size(); }
139 // No CTOR.
140 void clear() {
141 current_epoch_ = 0;
142 available_nodes_.clear();
143 recycled_nodes_.clear();
144 g_.clear();
145 n_edges_ = 0;
148 // Allocate new deadlock detector node.
149 // If we are out of available nodes first try to recycle some.
150 // If there is nothing to recycle, flush the graph and increment the epoch.
151 // Associate 'data' (opaque user's object) with the new node.
152 uptr newNode(uptr data) {
153 if (!available_nodes_.empty())
154 return getAvailableNode(data);
155 if (!recycled_nodes_.empty()) {
156 // Printf("recycling: n_edges_ %zd\n", n_edges_);
157 for (sptr i = n_edges_ - 1; i >= 0; i--) {
158 if (recycled_nodes_.getBit(edges_[i].from) ||
159 recycled_nodes_.getBit(edges_[i].to)) {
160 Swap(edges_[i], edges_[n_edges_ - 1]);
161 n_edges_--;
164 CHECK(available_nodes_.empty());
165 // removeEdgesFrom was called in removeNode.
166 g_.removeEdgesTo(recycled_nodes_);
167 available_nodes_.setUnion(recycled_nodes_);
168 recycled_nodes_.clear();
169 return getAvailableNode(data);
171 // We are out of vacant nodes. Flush and increment the current_epoch_.
172 current_epoch_ += size();
173 recycled_nodes_.clear();
174 available_nodes_.setAll();
175 g_.clear();
176 return getAvailableNode(data);
179 // Get data associated with the node created by newNode().
180 uptr getData(uptr node) const { return data_[nodeToIndex(node)]; }
182 bool nodeBelongsToCurrentEpoch(uptr node) {
183 return node && (node / size() * size()) == current_epoch_;
186 void removeNode(uptr node) {
187 uptr idx = nodeToIndex(node);
188 CHECK(!available_nodes_.getBit(idx));
189 CHECK(recycled_nodes_.setBit(idx));
190 g_.removeEdgesFrom(idx);
193 void ensureCurrentEpoch(DeadlockDetectorTLS<BV> *dtls) {
194 dtls->ensureCurrentEpoch(current_epoch_);
197 // Returns true if there is a cycle in the graph after this lock event.
198 // Ideally should be called before the lock is acquired so that we can
199 // report a deadlock before a real deadlock happens.
200 bool onLockBefore(DeadlockDetectorTLS<BV> *dtls, uptr cur_node) {
201 ensureCurrentEpoch(dtls);
202 uptr cur_idx = nodeToIndex(cur_node);
203 return g_.isReachable(cur_idx, dtls->getLocks(current_epoch_));
206 u32 findLockContext(DeadlockDetectorTLS<BV> *dtls, uptr node) {
207 return dtls->findLockContext(nodeToIndex(node));
210 // Add cur_node to the set of locks held currently by dtls.
211 void onLockAfter(DeadlockDetectorTLS<BV> *dtls, uptr cur_node, u32 stk = 0) {
212 ensureCurrentEpoch(dtls);
213 uptr cur_idx = nodeToIndex(cur_node);
214 dtls->addLock(cur_idx, current_epoch_, stk);
217 // Experimental *racy* fast path function.
218 // Returns true if all edges from the currently held locks to cur_node exist.
219 bool hasAllEdges(DeadlockDetectorTLS<BV> *dtls, uptr cur_node) {
220 uptr local_epoch = dtls->getEpoch();
221 // Read from current_epoch_ is racy.
222 if (cur_node && local_epoch == current_epoch_ &&
223 local_epoch == nodeToEpoch(cur_node)) {
224 uptr cur_idx = nodeToIndexUnchecked(cur_node);
225 for (uptr i = 0, n = dtls->getNumLocks(); i < n; i++) {
226 if (!g_.hasEdge(dtls->getLock(i), cur_idx))
227 return false;
229 return true;
231 return false;
234 // Adds edges from currently held locks to cur_node,
235 // returns the number of added edges, and puts the sources of added edges
236 // into added_edges[].
237 // Should be called before onLockAfter.
238 uptr addEdges(DeadlockDetectorTLS<BV> *dtls, uptr cur_node, u32 stk,
239 int unique_tid) {
240 ensureCurrentEpoch(dtls);
241 uptr cur_idx = nodeToIndex(cur_node);
242 uptr added_edges[40];
243 uptr n_added_edges = g_.addEdges(dtls->getLocks(current_epoch_), cur_idx,
244 added_edges, ARRAY_SIZE(added_edges));
245 for (uptr i = 0; i < n_added_edges; i++) {
246 if (n_edges_ < ARRAY_SIZE(edges_)) {
247 Edge e = {(u16)added_edges[i], (u16)cur_idx,
248 dtls->findLockContext(added_edges[i]), stk,
249 unique_tid};
250 edges_[n_edges_++] = e;
252 // Printf("Edge%zd: %u %zd=>%zd in T%d\n",
253 // n_edges_, stk, added_edges[i], cur_idx, unique_tid);
255 return n_added_edges;
258 bool findEdge(uptr from_node, uptr to_node, u32 *stk_from, u32 *stk_to,
259 int *unique_tid) {
260 uptr from_idx = nodeToIndex(from_node);
261 uptr to_idx = nodeToIndex(to_node);
262 for (uptr i = 0; i < n_edges_; i++) {
263 if (edges_[i].from == from_idx && edges_[i].to == to_idx) {
264 *stk_from = edges_[i].stk_from;
265 *stk_to = edges_[i].stk_to;
266 *unique_tid = edges_[i].unique_tid;
267 return true;
270 return false;
273 // Test-only function. Handles the before/after lock events,
274 // returns true if there is a cycle.
275 bool onLock(DeadlockDetectorTLS<BV> *dtls, uptr cur_node, u32 stk = 0) {
276 ensureCurrentEpoch(dtls);
277 bool is_reachable = !isHeld(dtls, cur_node) && onLockBefore(dtls, cur_node);
278 addEdges(dtls, cur_node, stk, 0);
279 onLockAfter(dtls, cur_node, stk);
280 return is_reachable;
283 // Handles the try_lock event, returns false.
284 // When a try_lock event happens (i.e. a try_lock call succeeds) we need
285 // to add this lock to the currently held locks, but we should not try to
286 // change the lock graph or to detect a cycle. We may want to investigate
287 // whether a more aggressive strategy is possible for try_lock.
288 bool onTryLock(DeadlockDetectorTLS<BV> *dtls, uptr cur_node, u32 stk = 0) {
289 ensureCurrentEpoch(dtls);
290 uptr cur_idx = nodeToIndex(cur_node);
291 dtls->addLock(cur_idx, current_epoch_, stk);
292 return false;
295 // Returns true iff dtls is empty (no locks are currently held) and we can
296 // add the node to the currently held locks w/o chanding the global state.
297 // This operation is thread-safe as it only touches the dtls.
298 bool onFirstLock(DeadlockDetectorTLS<BV> *dtls, uptr node, u32 stk = 0) {
299 if (!dtls->empty()) return false;
300 if (dtls->getEpoch() && dtls->getEpoch() == nodeToEpoch(node)) {
301 dtls->addLock(nodeToIndexUnchecked(node), nodeToEpoch(node), stk);
302 return true;
304 return false;
307 // Finds a path between the lock 'cur_node' (currently not held in dtls)
308 // and some currently held lock, returns the length of the path
309 // or 0 on failure.
310 uptr findPathToLock(DeadlockDetectorTLS<BV> *dtls, uptr cur_node, uptr *path,
311 uptr path_size) {
312 tmp_bv_.copyFrom(dtls->getLocks(current_epoch_));
313 uptr idx = nodeToIndex(cur_node);
314 CHECK(!tmp_bv_.getBit(idx));
315 uptr res = g_.findShortestPath(idx, tmp_bv_, path, path_size);
316 for (uptr i = 0; i < res; i++)
317 path[i] = indexToNode(path[i]);
318 if (res)
319 CHECK_EQ(path[0], cur_node);
320 return res;
323 // Handle the unlock event.
324 // This operation is thread-safe as it only touches the dtls.
325 void onUnlock(DeadlockDetectorTLS<BV> *dtls, uptr node) {
326 if (dtls->getEpoch() == nodeToEpoch(node))
327 dtls->removeLock(nodeToIndexUnchecked(node));
330 // Tries to handle the lock event w/o writing to global state.
331 // Returns true on success.
332 // This operation is thread-safe as it only touches the dtls
333 // (modulo racy nature of hasAllEdges).
334 bool onLockFast(DeadlockDetectorTLS<BV> *dtls, uptr node, u32 stk = 0) {
335 if (hasAllEdges(dtls, node)) {
336 dtls->addLock(nodeToIndexUnchecked(node), nodeToEpoch(node), stk);
337 return true;
339 return false;
342 bool isHeld(DeadlockDetectorTLS<BV> *dtls, uptr node) const {
343 return dtls->getLocks(current_epoch_).getBit(nodeToIndex(node));
346 uptr testOnlyGetEpoch() const { return current_epoch_; }
347 bool testOnlyHasEdge(uptr l1, uptr l2) {
348 return g_.hasEdge(nodeToIndex(l1), nodeToIndex(l2));
350 // idx1 and idx2 are raw indices to g_, not lock IDs.
351 bool testOnlyHasEdgeRaw(uptr idx1, uptr idx2) {
352 return g_.hasEdge(idx1, idx2);
355 void Print() {
356 for (uptr from = 0; from < size(); from++)
357 for (uptr to = 0; to < size(); to++)
358 if (g_.hasEdge(from, to))
359 Printf(" %zx => %zx\n", from, to);
362 private:
363 void check_idx(uptr idx) const { CHECK_LT(idx, size()); }
365 void check_node(uptr node) const {
366 CHECK_GE(node, size());
367 CHECK_EQ(current_epoch_, nodeToEpoch(node));
370 uptr indexToNode(uptr idx) const {
371 check_idx(idx);
372 return idx + current_epoch_;
375 uptr nodeToIndexUnchecked(uptr node) const { return node % size(); }
377 uptr nodeToIndex(uptr node) const {
378 check_node(node);
379 return nodeToIndexUnchecked(node);
382 uptr nodeToEpoch(uptr node) const { return node / size() * size(); }
384 uptr getAvailableNode(uptr data) {
385 uptr idx = available_nodes_.getAndClearFirstOne();
386 data_[idx] = data;
387 return indexToNode(idx);
390 struct Edge {
391 u16 from;
392 u16 to;
393 u32 stk_from;
394 u32 stk_to;
395 int unique_tid;
398 uptr current_epoch_;
399 BV available_nodes_;
400 BV recycled_nodes_;
401 BV tmp_bv_;
402 BVGraph<BV> g_;
403 uptr data_[BV::kSize];
404 Edge edges_[BV::kSize * 32];
405 uptr n_edges_;
408 } // namespace __sanitizer
410 #endif // SANITIZER_DEADLOCK_DETECTOR_H