summaryrefslogtreecommitdiff
path: root/lib/sanitizer_common/sanitizer_deadlock_detector.h
blob: b80cff460edab3d01d9bc4dc2e161444dd5d4fa3 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
//===-- sanitizer_deadlock_detector.h ---------------------------*- C++ -*-===//
//
// 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 a part of Sanitizer runtime.
// The deadlock detector maintains a directed graph of lock acquisitions.
// When a lock event happens, the detector checks if the locks already held by
// the current thread are reachable from the newly acquired lock.
//
// The detector can handle only a fixed amount of simultaneously live locks
// (a lock is alive if it has been locked at least once and has not been
// destroyed). When the maximal number of locks is reached the entire graph
// is flushed and the new lock epoch is started. The node ids from the old
// epochs can not be used with any of the detector methods except for
// nodeBelongsToCurrentEpoch().
//
// FIXME: this is work in progress, nothing really works yet.
//
//===----------------------------------------------------------------------===//

#ifndef SANITIZER_DEADLOCK_DETECTOR_H
#define SANITIZER_DEADLOCK_DETECTOR_H

#include "sanitizer_bvgraph.h"
#include "sanitizer_common.h"

namespace __sanitizer {

// Thread-local state for DeadlockDetector.
// It contains the locks currently held by the owning thread.
template <class BV>
class DeadlockDetectorTLS {
 public:
  // No CTOR.
  void clear() {
    bv_.clear();
    epoch_ = 0;
    n_recursive_locks = 0;
    n_all_locks_ = 0;
  }

  bool empty() const { return bv_.empty(); }

  void ensureCurrentEpoch(uptr current_epoch) {
    if (epoch_ == current_epoch) return;
    bv_.clear();
    epoch_ = current_epoch;
    n_recursive_locks = 0;
    n_all_locks_ = 0;
  }

  uptr getEpoch() const { return epoch_; }

  // Returns true if this is the first (non-recursive) acquisition of this lock.
  bool addLock(uptr lock_id, uptr current_epoch, u32 stk) {
    CHECK_EQ(epoch_, current_epoch);
    if (!bv_.setBit(lock_id)) {
      // The lock is already held by this thread, it must be recursive.
      CHECK_LT(n_recursive_locks, ARRAY_SIZE(recursive_locks));
      recursive_locks[n_recursive_locks++] = lock_id;
      return false;
    }
    CHECK_LT(n_all_locks_, ARRAY_SIZE(all_locks_with_contexts_));
    // lock_id < BV::kSize, can cast to a smaller int.
    u32 lock_id_short = static_cast<u32>(lock_id);
    LockWithContext l = {lock_id_short, stk};
    all_locks_with_contexts_[n_all_locks_++] = l;
    return true;
  }

  void removeLock(uptr lock_id) {
    if (n_recursive_locks) {
      for (sptr i = n_recursive_locks - 1; i >= 0; i--) {
        if (recursive_locks[i] == lock_id) {
          n_recursive_locks--;
          Swap(recursive_locks[i], recursive_locks[n_recursive_locks]);
          return;
        }
      }
    }
    if (!bv_.clearBit(lock_id))
      return;  // probably addLock happened before flush
    if (n_all_locks_) {
      for (sptr i = n_all_locks_ - 1; i >= 0; i--) {
        if (all_locks_with_contexts_[i].lock == static_cast<u32>(lock_id)) {
          Swap(all_locks_with_contexts_[i],
               all_locks_with_contexts_[n_all_locks_ - 1]);
          n_all_locks_--;
          break;
        }
      }
    }
  }

  u32 findLockContext(uptr lock_id) {
    for (uptr i = 0; i < n_all_locks_; i++)
      if (all_locks_with_contexts_[i].lock == static_cast<u32>(lock_id))
        return all_locks_with_contexts_[i].stk;
    return 0;
  }

  const BV &getLocks(uptr current_epoch) const {
    CHECK_EQ(epoch_, current_epoch);
    return bv_;
  }

  uptr getNumLocks() const { return n_all_locks_; }
  uptr getLock(uptr idx) const { return all_locks_with_contexts_[idx].lock; }

 private:
  BV bv_;
  uptr epoch_;
  uptr recursive_locks[64];
  uptr n_recursive_locks;
  struct LockWithContext {
    u32 lock;
    u32 stk;
  };
  LockWithContext all_locks_with_contexts_[64];
  uptr n_all_locks_;
};

// DeadlockDetector.
// For deadlock detection to work we need one global DeadlockDetector object
// and one DeadlockDetectorTLS object per evey thread.
// This class is not thread safe, all concurrent accesses should be guarded
// by an external lock.
// Most of the methods of this class are not thread-safe (i.e. should
// be protected by an external lock) unless explicitly told otherwise.
template <class BV>
class DeadlockDetector {
 public:
  typedef BV BitVector;

  uptr size() const { return g_.size(); }

  // No CTOR.
  void clear() {
    current_epoch_ = 0;
    available_nodes_.clear();
    recycled_nodes_.clear();
    g_.clear();
    n_edges_ = 0;
  }

  // Allocate new deadlock detector node.
  // If we are out of available nodes first try to recycle some.
  // If there is nothing to recycle, flush the graph and increment the epoch.
  // Associate 'data' (opaque user's object) with the new node.
  uptr newNode(uptr data) {
    if (!available_nodes_.empty())
      return getAvailableNode(data);
    if (!recycled_nodes_.empty()) {
      for (sptr i = n_edges_ - 1; i >= 0; i--) {
        if (recycled_nodes_.getBit(edges_[i].from) ||
            recycled_nodes_.getBit(edges_[i].to)) {
          Swap(edges_[i], edges_[n_edges_ - 1]);
          n_edges_--;
        }
      }
      CHECK(available_nodes_.empty());
      // removeEdgesFrom was called in removeNode.
      g_.removeEdgesTo(recycled_nodes_);
      available_nodes_.setUnion(recycled_nodes_);
      recycled_nodes_.clear();
      return getAvailableNode(data);
    }
    // We are out of vacant nodes. Flush and increment the current_epoch_.
    current_epoch_ += size();
    recycled_nodes_.clear();
    available_nodes_.setAll();
    g_.clear();
    n_edges_ = 0;
    return getAvailableNode(data);
  }

  // Get data associated with the node created by newNode().
  uptr getData(uptr node) const { return data_[nodeToIndex(node)]; }

  bool nodeBelongsToCurrentEpoch(uptr node) {
    return node && (node / size() * size()) == current_epoch_;
  }

  void removeNode(uptr node) {
    uptr idx = nodeToIndex(node);
    CHECK(!available_nodes_.getBit(idx));
    CHECK(recycled_nodes_.setBit(idx));
    g_.removeEdgesFrom(idx);
  }

  void ensureCurrentEpoch(DeadlockDetectorTLS<BV> *dtls) {
    dtls->ensureCurrentEpoch(current_epoch_);
  }

  // Returns true if there is a cycle in the graph after this lock event.
  // Ideally should be called before the lock is acquired so that we can
  // report a deadlock before a real deadlock happens.
  bool onLockBefore(DeadlockDetectorTLS<BV> *dtls, uptr cur_node) {
    ensureCurrentEpoch(dtls);
    uptr cur_idx = nodeToIndex(cur_node);
    return g_.isReachable(cur_idx, dtls->getLocks(current_epoch_));
  }

  u32 findLockContext(DeadlockDetectorTLS<BV> *dtls, uptr node) {
    return dtls->findLockContext(nodeToIndex(node));
  }

  // Add cur_node to the set of locks held currently by dtls.
  void onLockAfter(DeadlockDetectorTLS<BV> *dtls, uptr cur_node, u32 stk = 0) {
    ensureCurrentEpoch(dtls);
    uptr cur_idx = nodeToIndex(cur_node);
    dtls->addLock(cur_idx, current_epoch_, stk);
  }

  // Experimental *racy* fast path function.
  // Returns true if all edges from the currently held locks to cur_node exist.
  bool hasAllEdges(DeadlockDetectorTLS<BV> *dtls, uptr cur_node) {
    uptr local_epoch = dtls->getEpoch();
    // Read from current_epoch_ is racy.
    if (cur_node && local_epoch == current_epoch_ &&
        local_epoch == nodeToEpoch(cur_node)) {
      uptr cur_idx = nodeToIndexUnchecked(cur_node);
      for (uptr i = 0, n = dtls->getNumLocks(); i < n; i++) {
        if (!g_.hasEdge(dtls->getLock(i), cur_idx))
          return false;
      }
      return true;
    }
    return false;
  }

  // Adds edges from currently held locks to cur_node,
  // returns the number of added edges, and puts the sources of added edges
  // into added_edges[].
  // Should be called before onLockAfter.
  uptr addEdges(DeadlockDetectorTLS<BV> *dtls, uptr cur_node, u32 stk,
                int unique_tid) {
    ensureCurrentEpoch(dtls);
    uptr cur_idx = nodeToIndex(cur_node);
    uptr added_edges[40];
    uptr n_added_edges = g_.addEdges(dtls->getLocks(current_epoch_), cur_idx,
                                     added_edges, ARRAY_SIZE(added_edges));
    for (uptr i = 0; i < n_added_edges; i++) {
      if (n_edges_ < ARRAY_SIZE(edges_)) {
        Edge e = {(u16)added_edges[i], (u16)cur_idx,
                  dtls->findLockContext(added_edges[i]), stk,
                  unique_tid};
        edges_[n_edges_++] = e;
      }
    }
    return n_added_edges;
  }

  bool findEdge(uptr from_node, uptr to_node, u32 *stk_from, u32 *stk_to,
                int *unique_tid) {
    uptr from_idx = nodeToIndex(from_node);
    uptr to_idx = nodeToIndex(to_node);
    for (uptr i = 0; i < n_edges_; i++) {
      if (edges_[i].from == from_idx && edges_[i].to == to_idx) {
        *stk_from = edges_[i].stk_from;
        *stk_to = edges_[i].stk_to;
        *unique_tid = edges_[i].unique_tid;
        return true;
      }
    }
    return false;
  }

  // Test-only function. Handles the before/after lock events,
  // returns true if there is a cycle.
  bool onLock(DeadlockDetectorTLS<BV> *dtls, uptr cur_node, u32 stk = 0) {
    ensureCurrentEpoch(dtls);
    bool is_reachable = !isHeld(dtls, cur_node) && onLockBefore(dtls, cur_node);
    addEdges(dtls, cur_node, stk, 0);
    onLockAfter(dtls, cur_node, stk);
    return is_reachable;
  }

  // Handles the try_lock event, returns false.
  // When a try_lock event happens (i.e. a try_lock call succeeds) we need
  // to add this lock to the currently held locks, but we should not try to
  // change the lock graph or to detect a cycle.  We may want to investigate
  // whether a more aggressive strategy is possible for try_lock.
  bool onTryLock(DeadlockDetectorTLS<BV> *dtls, uptr cur_node, u32 stk = 0) {
    ensureCurrentEpoch(dtls);
    uptr cur_idx = nodeToIndex(cur_node);
    dtls->addLock(cur_idx, current_epoch_, stk);
    return false;
  }

  // Returns true iff dtls is empty (no locks are currently held) and we can
  // add the node to the currently held locks w/o chanding the global state.
  // This operation is thread-safe as it only touches the dtls.
  bool onFirstLock(DeadlockDetectorTLS<BV> *dtls, uptr node, u32 stk = 0) {
    if (!dtls->empty()) return false;
    if (dtls->getEpoch() && dtls->getEpoch() == nodeToEpoch(node)) {
      dtls->addLock(nodeToIndexUnchecked(node), nodeToEpoch(node), stk);
      return true;
    }
    return false;
  }

  // Finds a path between the lock 'cur_node' (currently not held in dtls)
  // and some currently held lock, returns the length of the path
  // or 0 on failure.
  uptr findPathToLock(DeadlockDetectorTLS<BV> *dtls, uptr cur_node, uptr *path,
                      uptr path_size) {
    tmp_bv_.copyFrom(dtls->getLocks(current_epoch_));
    uptr idx = nodeToIndex(cur_node);
    CHECK(!tmp_bv_.getBit(idx));
    uptr res = g_.findShortestPath(idx, tmp_bv_, path, path_size);
    for (uptr i = 0; i < res; i++)
      path[i] = indexToNode(path[i]);
    if (res)
      CHECK_EQ(path[0], cur_node);
    return res;
  }

  // Handle the unlock event.
  // This operation is thread-safe as it only touches the dtls.
  void onUnlock(DeadlockDetectorTLS<BV> *dtls, uptr node) {
    if (dtls->getEpoch() == nodeToEpoch(node))
      dtls->removeLock(nodeToIndexUnchecked(node));
  }

  // Tries to handle the lock event w/o writing to global state.
  // Returns true on success.
  // This operation is thread-safe as it only touches the dtls
  // (modulo racy nature of hasAllEdges).
  bool onLockFast(DeadlockDetectorTLS<BV> *dtls, uptr node, u32 stk = 0) {
    if (hasAllEdges(dtls, node)) {
      dtls->addLock(nodeToIndexUnchecked(node), nodeToEpoch(node), stk);
      return true;
    }
    return false;
  }

  bool isHeld(DeadlockDetectorTLS<BV> *dtls, uptr node) const {
    return dtls->getLocks(current_epoch_).getBit(nodeToIndex(node));
  }

  uptr testOnlyGetEpoch() const { return current_epoch_; }
  bool testOnlyHasEdge(uptr l1, uptr l2) {
    return g_.hasEdge(nodeToIndex(l1), nodeToIndex(l2));
  }
  // idx1 and idx2 are raw indices to g_, not lock IDs.
  bool testOnlyHasEdgeRaw(uptr idx1, uptr idx2) {
    return g_.hasEdge(idx1, idx2);
  }

  void Print() {
    for (uptr from = 0; from < size(); from++)
      for (uptr to = 0; to < size(); to++)
        if (g_.hasEdge(from, to))
          Printf("  %zx => %zx\n", from, to);
  }

 private:
  void check_idx(uptr idx) const { CHECK_LT(idx, size()); }

  void check_node(uptr node) const {
    CHECK_GE(node, size());
    CHECK_EQ(current_epoch_, nodeToEpoch(node));
  }

  uptr indexToNode(uptr idx) const {
    check_idx(idx);
    return idx + current_epoch_;
  }

  uptr nodeToIndexUnchecked(uptr node) const { return node % size(); }

  uptr nodeToIndex(uptr node) const {
    check_node(node);
    return nodeToIndexUnchecked(node);
  }

  uptr nodeToEpoch(uptr node) const { return node / size() * size(); }

  uptr getAvailableNode(uptr data) {
    uptr idx = available_nodes_.getAndClearFirstOne();
    data_[idx] = data;
    return indexToNode(idx);
  }

  struct Edge {
    u16 from;
    u16 to;
    u32 stk_from;
    u32 stk_to;
    int unique_tid;
  };

  uptr current_epoch_;
  BV available_nodes_;
  BV recycled_nodes_;
  BV tmp_bv_;
  BVGraph<BV> g_;
  uptr data_[BV::kSize];
  Edge edges_[BV::kSize * 32];
  uptr n_edges_;
};

} // namespace __sanitizer

#endif // SANITIZER_DEADLOCK_DETECTOR_H