[sanitizer] in bitset-based deadlock detector collect edge's stack trace when an edge is added to the graph (in following CLs these stack traces will be added to the report)

git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@203902 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 95 insertions, 19 deletions

diff --git a/lib/sanitizer_common/sanitizer_bvgraph.h b/lib/sanitizer_common/sanitizer_bvgraph.h
index 157b9320e..a55757b5d 100644
--- a/lib/sanitizer_common/sanitizer_bvgraph.h
+++ b/lib/sanitizer_common/sanitizer_bvgraph.h
@@ -47,12 +47,16 @@ class BVGraph {
   }
 
   // Returns true if at least one new edge was added.
-  bool addEdges(const BV &from, uptr to) {
-    bool res = false;
+  uptr addEdges(const BV &from, uptr to, uptr added_edges[],
+                uptr max_added_edges) {
+    uptr res = 0;
     t1.copyFrom(from);
-    while (!t1.empty())
-      if (v[t1.getAndClearFirstOne()].setBit(to))
-        res = true;
+    while (!t1.empty()) {
+      uptr node = t1.getAndClearFirstOne();
+      if (v[node].setBit(to))
+        if (res < max_added_edges)
+          added_edges[res++] = node;
+    }
     return res;
   }
 
diff --git a/lib/sanitizer_common/sanitizer_deadlock_detector.h b/lib/sanitizer_common/sanitizer_deadlock_detector.h
index 14762be4a..33913137f 100644
--- a/lib/sanitizer_common/sanitizer_deadlock_detector.h
+++ b/lib/sanitizer_common/sanitizer_deadlock_detector.h
@@ -112,6 +112,7 @@ class DeadlockDetector {
     available_nodes_.clear();
     recycled_nodes_.clear();
     g_.clear();
+    n_edges_ = 0;
   }
 
   // Allocate new deadlock detector node.
@@ -164,21 +165,49 @@ class DeadlockDetector {
     return g_.isReachable(cur_idx, dtls->getLocks(current_epoch_));
   }
 
-  // Returns true if a new edge has been added to the graph.
-  // Should be called before after the lock is acquired.
-  bool onLockAfter(DeadlockDetectorTLS<BV> *dtls, uptr cur_node) {
+  // Add cur_node to the set of locks held currently by dtls.
+  void onLockAfter(DeadlockDetectorTLS<BV> *dtls, uptr cur_node) {
     ensureCurrentEpoch(dtls);
     uptr cur_idx = nodeToIndex(cur_node);
-    g_.addEdges(dtls->getLocks(current_epoch_), cur_idx);
-    return dtls->addLock(cur_idx, current_epoch_);
+    dtls->addLock(cur_idx, current_epoch_);
+  }
+
+  // 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) {
+    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_))
+        edges_[n_edges_++] = Edge((u16)added_edges[i], (u16)cur_idx, stk);
+      // Printf("Edge [%zd]: %u %zd=>%zd\n", i, stk, added_edges[i], cur_idx);
+    }
+    return n_added_edges;
+  }
+
+  u32 findEdge(uptr from_node, uptr to_node) {
+    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)
+        return edges_[i].stk;
+    }
+    return 0;
   }
 
   // Test-only function. Handles the before/after lock events,
   // returns true if there is a cycle.
   bool onLock(DeadlockDetectorTLS<BV> *dtls, uptr cur_node) {
     ensureCurrentEpoch(dtls);
-    bool is_reachable = onLockBefore(dtls, cur_node);
-    return onLockAfter(dtls, cur_node) && is_reachable;
+    bool is_reachable = !isHeld(dtls, cur_node) && onLockBefore(dtls, cur_node);
+    addEdges(dtls, cur_node, 0);
+    onLockAfter(dtls, cur_node);
+    return is_reachable;
   }
 
   // Handles the try_lock event, returns false.
@@ -276,12 +305,23 @@ class DeadlockDetector {
     return indexToNode(idx);
   }
 
+  struct Edge {
+    u16 from;
+    u16 to;
+    u32 stk;
+    // FIXME: replace with initializer list once the tests are built as c++11.
+    Edge(u16 f, u16 t, u32 s) : from(f), to(t), stk(s) {}
+    Edge() {}
+  };
+
   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
diff --git a/lib/sanitizer_common/sanitizer_deadlock_detector1.cc b/lib/sanitizer_common/sanitizer_deadlock_detector1.cc
index 2f27b3cc5..9dbb38f71 100644
--- a/lib/sanitizer_common/sanitizer_deadlock_detector1.cc
+++ b/lib/sanitizer_common/sanitizer_deadlock_detector1.cc
@@ -112,8 +112,12 @@ void DD::MutexBeforeLock(DDCallback *cb,
     DDReport *rep = &lt->rep;
     rep->n = len;
     for (uptr i = 0; i < len; i++) {
-      DDMutex *m0 = (DDMutex*)dd.getData(path[i]);
-      DDMutex *m1 = (DDMutex*)dd.getData(path[i < len - 1 ? i + 1 : 0]);
+      uptr from = path[i];
+      uptr to = path[(i + 1) % len];
+      DDMutex *m0 = (DDMutex*)dd.getData(from);
+      DDMutex *m1 = (DDMutex*)dd.getData(to);
+
+      Printf("Edge: %zd=>%zd: %u\n", from, to, dd.findEdge(from, to));
       rep->loop[i].thr_ctx = 0;  // don't know
       rep->loop[i].mtx_ctx0 = m0->ctx;
       rep->loop[i].mtx_ctx1 = m1->ctx;
@@ -131,11 +135,9 @@ void DD::MutexAfterLock(DDCallback *cb, DDMutex *m, bool wlock, bool trylock) {
   MutexEnsureID(lt, m);
   if (wlock)  // Only a recursive rlock may be held.
     CHECK(!dd.isHeld(&lt->dd, m->id));
-  bool edge_added =
-      trylock ? dd.onTryLock(&lt->dd, m->id) : dd.onLockAfter(&lt->dd, m->id);
-  if (edge_added) {
-    // Printf("Edge added\n");
-  }
+  if (!trylock)
+    dd.addEdges(&lt->dd, m->id, cb->Unwind());
+  dd.onLockAfter(&lt->dd, m->id);
 }
 
 void DD::MutexBeforeUnlock(DDCallback *cb, DDMutex *m, bool wlock) {
diff --git a/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc b/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc
index e584a541f..b7be2a862 100644
--- a/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc
+++ b/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc
@@ -301,3 +301,33 @@ TEST(BVGraph, ShortestPath) {
   ShortestPath<BV3>();
   ShortestPath<BV4>();
 }
+
+template <class BV>
+void RunAddEdgesTest() {
+  BVGraph<BV> g;
+  BV from;
+  const int kMaxEdges = 10;
+  uptr added_edges[kMaxEdges];
+  g.clear();
+  from.clear();
+  EXPECT_EQ(0U, g.addEdges(from, 0, added_edges, kMaxEdges));
+  EXPECT_EQ(0U, g.addEdges(from, 1, added_edges, kMaxEdges));
+  from.setBit(0);
+  EXPECT_EQ(1U, g.addEdges(from, 1, added_edges, kMaxEdges));
+  EXPECT_EQ(0U, added_edges[0]);
+  EXPECT_EQ(0U, g.addEdges(from, 1, added_edges, kMaxEdges));
+
+  from.clear();
+  from.setBit(1);
+  EXPECT_EQ(1U, g.addEdges(from, 4, added_edges, kMaxEdges));
+  EXPECT_EQ(1U, added_edges[0]);
+  from.setBit(2);
+  from.setBit(3);
+  EXPECT_EQ(2U, g.addEdges(from, 4, added_edges, kMaxEdges));
+  EXPECT_EQ(2U, added_edges[0]);
+  EXPECT_EQ(3U, added_edges[1]);
+}
+
+TEST(BVGraph, AddEdgesTest) {
+  RunAddEdgesTest<BV2>();
+}