[sanitizer] implement node removal in Deadlock graph

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

6 files changed, 278 insertions, 16 deletions

diff --git a/lib/sanitizer_common/sanitizer_bitvector.h b/lib/sanitizer_common/sanitizer_bitvector.h
index 4ad379b91..d16205a7c 100644
--- a/lib/sanitizer_common/sanitizer_bitvector.h
+++ b/lib/sanitizer_common/sanitizer_bitvector.h
@@ -67,6 +67,13 @@ class BasicBitVector {
     return bits_ != old;
   }
 
+  // Do "this &= ~v" and return whether any bits have been removed.
+  bool setDifference(const BasicBitVector &v) {
+    basic_int_t old = bits_;
+    bits_ &= ~v.bits_;
+    return bits_ != old;
+  }
+
   void copyFrom(const BasicBitVector &v) { bits_ = v.bits_; }
 
   // Returns true if 'this' intersects with 'v'.
@@ -221,6 +228,23 @@ class TwoLevelBitVector {
     return res;
   }
 
+  // Do "this &= ~v" and return whether any bits have been removed.
+  bool setDifference(const TwoLevelBitVector &v) {
+    bool res = false;
+    for (uptr i0 = 0; i0 < kLevel1Size; i0++) {
+      BV t = l1_[i0];
+      t.setIntersection(v.l1_[i0]);
+      while (!t.empty()) {
+        uptr i1 = t.getAndClearFirstOne();
+        if (l2_[i0][i1].setDifference(v.l2_[i0][i1]))
+          res = true;
+        if (l2_[i0][i1].empty())
+          l1_[i0].clearBit(i1);
+      }
+    }
+    return res;
+  }
+
   void copyFrom(const TwoLevelBitVector &v) {
     clear();
     setUnion(v);
diff --git a/lib/sanitizer_common/sanitizer_bvgraph.h b/lib/sanitizer_common/sanitizer_bvgraph.h
index 8d3e6afe8..c54955a5a 100644
--- a/lib/sanitizer_common/sanitizer_bvgraph.h
+++ b/lib/sanitizer_common/sanitizer_bvgraph.h
@@ -33,6 +33,13 @@ class BVGraph {
       v[i].clear();
   }
 
+  bool empty() const {
+    for (uptr i = 0; i < size(); i++)
+      if (!v[i].empty())
+        return false;
+    return true;
+  }
+
   // Returns true if a new edge was added.
   bool addEdge(uptr from, uptr to) {
     check(from, to);
@@ -49,6 +56,39 @@ class BVGraph {
     return res;
   }
 
+  // Returns true if the edge from=>to was removed.
+  bool removeEdge(uptr from, uptr to) {
+    return v[from].clearBit(to);
+  }
+
+  // Returns true if at least one edge *=>to was removed.
+  bool removeEdgesTo(const BV &to) {
+    bool res = 0;
+    for (uptr from = 0; from < size(); from++) {
+      if (v[from].setDifference(to))
+        res = true;
+    }
+    return res;
+  }
+
+  // Returns true if at least one edge from=>* was removed.
+  bool removeEdgesFrom(const BV &from) {
+    bool res = false;
+    t1.copyFrom(from);
+    while (!t1.empty()) {
+      uptr idx = t1.getAndClearFirstOne();
+      if (!v[idx].empty()) {
+        v[idx].clear();
+        res = true;
+      }
+    }
+    return res;
+  }
+
+  void removeEdgesFrom(uptr from) {
+    return v[from].clear();
+  }
+
   bool hasEdge(uptr from, uptr to) const {
     check(from, to);
     return v[from].getBit(to);
diff --git a/lib/sanitizer_common/sanitizer_deadlock_detector.h b/lib/sanitizer_common/sanitizer_deadlock_detector.h
index aa2644fd7..d0ff29de4 100644
--- a/lib/sanitizer_common/sanitizer_deadlock_detector.h
+++ b/lib/sanitizer_common/sanitizer_deadlock_detector.h
@@ -40,7 +40,7 @@ class DeadlockDetectorTLS {
       bv_.clear();
       epoch_ = current_epoch;
     }
-    bv_.setBit(lock_id);
+    CHECK(bv_.setBit(lock_id));
   }
 
   void removeLock(uptr lock_id, uptr current_epoch) {
@@ -48,7 +48,7 @@ class DeadlockDetectorTLS {
       bv_.clear();
       epoch_ = current_epoch;
     }
-    bv_.clearBit(lock_id);
+    CHECK(bv_.clearBit(lock_id));
   }
 
   const BV &getLocks() const { return bv_; }
@@ -88,9 +88,10 @@ class DeadlockDetector {
       return getAvailableNode(data);
     if (!recycled_nodes_.empty()) {
       CHECK(available_nodes_.empty());
+      // removeEdgesFrom was called in removeNode.
+      g_.removeEdgesTo(recycled_nodes_);
       available_nodes_.setUnion(recycled_nodes_);
       recycled_nodes_.clear();
-      // FIXME: actually recycle nodes in the graph.
       return getAvailableNode(data);
     }
     // We are out of vacant nodes. Flush and increment the current_epoch_.
@@ -108,7 +109,7 @@ class DeadlockDetector {
     uptr idx = nodeToIndex(node);
     CHECK(!available_nodes_.getBit(idx));
     CHECK(recycled_nodes_.setBit(idx));
-    // FIXME: also remove from the graph.
+    g_.removeEdgesFrom(idx);
   }
 
   // Handle the lock event, return true if there is a cycle.
@@ -126,6 +127,8 @@ class DeadlockDetector {
     dtls->removeLock(nodeToIndex(node), current_epoch_);
   }
 
+  uptr testOnlyGetEpoch() const { return current_epoch_; }
+
  private:
   void check_idx(uptr idx) const { CHECK_LT(idx, size()); }
 
diff --git a/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc b/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc
index 1637fa89d..706b4c589 100644
--- a/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc
+++ b/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc
@@ -67,7 +67,7 @@ void Print(const BV &bv) {
 }
 
 void Print(const set<uptr> &s) {
-  for (set<uptr>::reverse_iterator it = s.rbegin(); it != s.rend(); ++it) {
+  for (set<uptr>::iterator it = s.begin(); it != s.end(); ++it) {
     fprintf(stderr, "%zd ", *it);
   }
   fprintf(stderr, "\n");
@@ -107,7 +107,8 @@ void TestBitVector(uptr expected_size) {
   }
 
   vector<uptr>bits(bv.size());
-  // Test setUnion, setIntersection, intersectsWith, and getAndClearFirstOne.
+  // Test setUnion, setIntersection, setDifference,
+  // intersectsWith, and getAndClearFirstOne.
   for (uptr it = 0; it < 30; it++) {
     // iota
     for (size_t j = 0; j < bits.size(); j++) bits[j] = j;
@@ -147,6 +148,15 @@ void TestBitVector(uptr expected_size) {
     t_bv.copyFrom(bv);
     EXPECT_EQ(t_bv.setIntersection(bv1), s.size() != t_s.size());
     CheckBV(t_bv, t_s);
+
+    // setDifference
+    vec.clear();
+    set_difference(s.begin(), s.end(), s1.begin(), s1.end(),
+                     back_insert_iterator<vector<uptr> >(vec));
+    t_s = set<uptr>(vec.begin(), vec.end());
+    t_bv.copyFrom(bv);
+    EXPECT_EQ(t_bv.setDifference(bv1), s.size() != t_s.size());
+    CheckBV(t_bv, t_s);
   }
 }
 
@@ -158,9 +168,9 @@ TEST(SanitizerCommon, BasicBitVector) {
 
 TEST(SanitizerCommon, TwoLevelBitVector) {
   uptr ws = SANITIZER_WORDSIZE;
+  TestBitVector<TwoLevelBitVector<1, BasicBitVector<u8> > >(8 * 8);
   TestBitVector<TwoLevelBitVector<> >(ws * ws);
   TestBitVector<TwoLevelBitVector<2> >(ws * ws * 2);
   TestBitVector<TwoLevelBitVector<3> >(ws * ws * 3);
-  TestBitVector<TwoLevelBitVector<3, BasicBitVector<u16> > >
-      (16 * 16 * 3);
+  TestBitVector<TwoLevelBitVector<3, BasicBitVector<u16> > >(16 * 16 * 3);
 }
diff --git a/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc b/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc
index fe3665fe8..722fef673 100644
--- a/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc
+++ b/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc
@@ -24,6 +24,10 @@
 using namespace __sanitizer;
 using namespace std;
 
+typedef BasicBitVector<u8> BV1;
+typedef BasicBitVector<> BV2;
+typedef TwoLevelBitVector<> BV3;
+typedef TwoLevelBitVector<3, BasicBitVector<u8> > BV4;
 
 template<class G>
 void PrintGraph(const G &g) {
@@ -35,11 +39,25 @@ void PrintGraph(const G &g) {
   }
 }
 
+
 class SimpleGraph {
  public:
+  void clear() { s_.clear(); }
   bool addEdge(uptr from, uptr to) {
     return s_.insert(idx(from, to)).second;
   }
+  bool removeEdge(uptr from, uptr to) {
+    return s_.erase(idx(from, to));
+  }
+  template <class G>
+  void checkSameAs(G *g) {
+    for (set<uptr>::iterator it = s_.begin(); it != s_.end(); ++it) {
+      uptr from = *it >> 16;
+      uptr to = *it & ((1 << 16) - 1);
+      EXPECT_TRUE(g->removeEdge(from, to));
+    }
+    EXPECT_TRUE(g->empty());
+  }
  private:
   uptr idx(uptr from, uptr to) {
     CHECK_LE(from|to, 1 << 16);
@@ -48,8 +66,8 @@ class SimpleGraph {
   set<uptr> s_;
 };
 
-TEST(SanitizerCommon, BVGraph) {
-  typedef TwoLevelBitVector<> BV;
+template <class BV>
+void BasicTest() {
   BVGraph<BV> g;
   g.clear();
   BV target;
@@ -57,7 +75,7 @@ TEST(SanitizerCommon, BVGraph) {
   set<uptr> s;
   set<uptr> s_target;
   int num_reachable = 0;
-  for (int it = 0; it < 3000; it++) {
+  for (int it = 0; it < 1000; it++) {
     target.clear();
     s_target.clear();
     for (int t = 0; t < 4; t++) {
@@ -89,6 +107,60 @@ TEST(SanitizerCommon, BVGraph) {
   EXPECT_GT(num_reachable, 0);
 }
 
+TEST(BVGraph, BasicTest) {
+  BasicTest<BV1>();
+  BasicTest<BV2>();
+  BasicTest<BV3>();
+  BasicTest<BV4>();
+}
+
+template <class BV>
+void RemoveEdges() {
+  SimpleGraph s_g;
+  BVGraph<BV> g;
+  g.clear();
+  BV bv;
+  set<uptr> s;
+  for (int it = 0; it < 100; it++) {
+    s.clear();
+    bv.clear();
+    s_g.clear();
+    g.clear();
+    for (uptr j = 0; j < g.size() * 2; j++) {
+      uptr from = my_rand() % g.size();
+      uptr to = my_rand() % g.size();
+      EXPECT_EQ(g.addEdge(from, to), s_g.addEdge(from, to));
+    }
+    for (uptr j = 0; j < 5; j++) {
+      uptr idx = my_rand() % g.size();
+      s.insert(idx);
+      bv.setBit(idx);
+    }
+
+    if (it % 2) {
+      g.removeEdgesFrom(bv);
+      for (set<uptr>::iterator from = s.begin(); from != s.end(); ++from) {
+        for (uptr to = 0; to < g.size(); to++)
+          s_g.removeEdge(*from, to);
+      }
+    } else {
+      g.removeEdgesTo(bv);
+      for (set<uptr>::iterator to = s.begin(); to != s.end(); ++to) {
+        for (uptr from = 0; from < g.size(); from++)
+          s_g.removeEdge(from, *to);
+      }
+    }
+    s_g.checkSameAs(&g);
+  }
+}
+
+TEST(BVGraph, RemoveEdges) {
+  RemoveEdges<BV1>();
+  RemoveEdges<BV2>();
+  RemoveEdges<BV3>();
+  RemoveEdges<BV4>();
+}
+
 template <class BV>
 void Test_isReachable() {
   uptr path[5];
@@ -139,7 +211,7 @@ void Test_isReachable() {
   EXPECT_TRUE(g.isReachable(f3, target));
 }
 
-TEST(SanitizerCommon, BVGraph_isReachable) {
+TEST(BVGraph, isReachable) {
   Test_isReachable<BasicBitVector<u8> >();
   Test_isReachable<BasicBitVector<> >();
   Test_isReachable<TwoLevelBitVector<> >();
@@ -183,7 +255,7 @@ void LongCycle() {
   }
 }
 
-TEST(SanitizerCommon, BVGraph_LongCycle) {
+TEST(BVGraph, LongCycle) {
   LongCycle<BasicBitVector<u8> >();
   LongCycle<BasicBitVector<> >();
   LongCycle<TwoLevelBitVector<> >();
diff --git a/lib/sanitizer_common/tests/sanitizer_deadlock_detector_test.cc b/lib/sanitizer_common/tests/sanitizer_deadlock_detector_test.cc
index 594ea0829..115b233a7 100644
--- a/lib/sanitizer_common/tests/sanitizer_deadlock_detector_test.cc
+++ b/lib/sanitizer_common/tests/sanitizer_deadlock_detector_test.cc
@@ -24,6 +24,11 @@
 using namespace __sanitizer;
 using namespace std;
 
+typedef BasicBitVector<u8> BV1;
+typedef BasicBitVector<> BV2;
+typedef TwoLevelBitVector<> BV3;
+typedef TwoLevelBitVector<3, BasicBitVector<u8> > BV4;
+
 // Poor man's unique_ptr.
 template<class BV>
 struct ScopedDD {
@@ -103,7 +108,115 @@ void BasicTest() {
 }
 
 TEST(DeadlockDetector, BasicTest) {
-  BasicTest<BasicBitVector<> >();
-  BasicTest<TwoLevelBitVector<2> >();
-  BasicTest<TwoLevelBitVector<3, BasicBitVector<u16> > >();
+  BasicTest<BV1>();
+  BasicTest<BV2>();
+  BasicTest<BV3>();
+  BasicTest<BV4>();
+}
+
+template <class BV>
+void RemoveNodeTest() {
+  ScopedDD<BV> sdd;
+  DeadlockDetector<BV> &d = *sdd.dp;
+  DeadlockDetectorTLS<BV> dtls;
+  d.clear();
+
+  uptr l0 = d.newNode(0);
+  uptr l1 = d.newNode(1);
+  uptr l2 = d.newNode(2);
+  uptr l3 = d.newNode(3);
+  uptr l4 = d.newNode(4);
+  uptr l5 = d.newNode(5);
+
+  // l0=>l1=>l2
+  d.onLock(&dtls, l0);
+  d.onLock(&dtls, l1);
+  d.onLock(&dtls, l2);
+  d.onUnlock(&dtls, l1);
+  d.onUnlock(&dtls, l0);
+  d.onUnlock(&dtls, l2);
+  // l3=>l4=>l5
+  d.onLock(&dtls, l3);
+  d.onLock(&dtls, l4);
+  d.onLock(&dtls, l5);
+  d.onUnlock(&dtls, l4);
+  d.onUnlock(&dtls, l3);
+  d.onUnlock(&dtls, l5);
+
+  set<uptr> locks;
+  locks.insert(l0);
+  locks.insert(l1);
+  locks.insert(l2);
+  locks.insert(l3);
+  locks.insert(l4);
+  locks.insert(l5);
+  for (uptr i = 6; i < d.size(); i++) {
+    uptr lt = d.newNode(i);
+    locks.insert(lt);
+    d.onLock(&dtls, lt);
+    d.onUnlock(&dtls, lt);
+    d.removeNode(lt);
+  }
+  EXPECT_EQ(locks.size(), d.size());
+  // l2=>l0
+  EXPECT_FALSE(d.onLock(&dtls, l2));
+  EXPECT_TRUE(d.onLock(&dtls, l0));
+  d.onUnlock(&dtls, l2);
+  d.onUnlock(&dtls, l0);
+  // l4=>l3
+  EXPECT_FALSE(d.onLock(&dtls, l4));
+  EXPECT_TRUE(d.onLock(&dtls, l3));
+  d.onUnlock(&dtls, l4);
+  d.onUnlock(&dtls, l3);
+
+  EXPECT_EQ(d.size(), d.testOnlyGetEpoch());
+
+  d.removeNode(l2);
+  d.removeNode(l3);
+  locks.clear();
+  // make sure no edges from or to l0,l1,l4,l5 left.
+  for (uptr i = 4; i < d.size(); i++) {
+    uptr lt = d.newNode(i);
+    locks.insert(lt);
+    uptr a, b;
+    // l0 => lt?
+    a = l0; b = lt;
+    EXPECT_FALSE(d.onLock(&dtls, a));
+    EXPECT_FALSE(d.onLock(&dtls, b));
+    d.onUnlock(&dtls, a);
+    d.onUnlock(&dtls, b);
+    // l1 => lt?
+    a = l1; b = lt;
+    EXPECT_FALSE(d.onLock(&dtls, a));
+    EXPECT_FALSE(d.onLock(&dtls, b));
+    d.onUnlock(&dtls, a);
+    d.onUnlock(&dtls, b);
+    // lt => l4?
+    a = lt; b = l4;
+    EXPECT_FALSE(d.onLock(&dtls, a));
+    EXPECT_FALSE(d.onLock(&dtls, b));
+    d.onUnlock(&dtls, a);
+    d.onUnlock(&dtls, b);
+    // lt => l5?
+    a = lt; b = l5;
+    EXPECT_FALSE(d.onLock(&dtls, a));
+    EXPECT_FALSE(d.onLock(&dtls, b));
+    d.onUnlock(&dtls, a);
+    d.onUnlock(&dtls, b);
+
+    d.removeNode(lt);
+  }
+  // Still the same epoch.
+  EXPECT_EQ(d.size(), d.testOnlyGetEpoch());
+  EXPECT_EQ(locks.size(), d.size() - 4);
+  // l2 and l3 should have ben reused.
+  EXPECT_EQ(locks.count(l2), 1U);
+  EXPECT_EQ(locks.count(l3), 1U);
+}
+
+TEST(DeadlockDetector, RemoveNodeTest) {
+  RemoveNodeTest<BV1>();
+  RemoveNodeTest<BV2>();
+  RemoveNodeTest<BV3>();
+  RemoveNodeTest<BV4>();
 }