1 files changed, 412 insertions, 0 deletions
diff --git a/contrib/compiler-rt/lib/sanitizer_common/sanitizer_deadlock_detector.h b/contrib/compiler-rt/lib/sanitizer_common/sanitizer_deadlock_detector.h
new file mode 100644
index 000000000000..90e1cc4eb597
--- /dev/null
+++ b/contrib/compiler-rt/lib/sanitizer_common/sanitizer_deadlock_detector.h
@@ -0,0 +1,412 @@
+//===-- sanitizer_deadlock_detector.h ---------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// 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_common.h"
+#include "sanitizer_bvgraph.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;
+  }
+
+  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) {
+    // Printf("addLock: %zx %zx stk %u\n", lock_id, current_epoch, 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;
+        }
+      }
+    }
+    // Printf("remLock: %zx %zx\n", lock_id, epoch_);
+    CHECK(bv_.clearBit(lock_id));
+    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()) {
+      // Printf("recycling: n_edges_ %zd\n", n_edges_);
+      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();
+    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;
+      }
+      // Printf("Edge%zd: %u %zd=>%zd in T%d\n",
+      //        n_edges_, stk, added_edges[i], cur_idx, unique_tid);
+    }
+    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