[sanitizer] added class BVGraph, to be used in a deadlock detector; added more methods to the bit vectors

llvm-svn: 201226

6 files changed, 277 insertions, 19 deletions

diff --git a/compiler-rt/lib/sanitizer_common/CMakeLists.txt b/compiler-rt/lib/sanitizer_common/CMakeLists.txt
index 26e6a27cd76..3468bef428c 100644
--- a/compiler-rt/lib/sanitizer_common/CMakeLists.txt
+++ b/compiler-rt/lib/sanitizer_common/CMakeLists.txt
@@ -45,6 +45,7 @@ set(SANITIZER_HEADERS
   sanitizer_atomic_clang.h
   sanitizer_atomic_msvc.h
   sanitizer_bitvector.h
+  sanitizer_bvgraph.h
   sanitizer_common.h
   sanitizer_common_interceptors.inc
   sanitizer_common_interceptors_ioctl.inc
diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_bitvector.h b/compiler-rt/lib/sanitizer_common/sanitizer_bitvector.h
index bef680c6538..5f323ce63c4 100644
--- a/compiler-rt/lib/sanitizer_common/sanitizer_bitvector.h
+++ b/compiler-rt/lib/sanitizer_common/sanitizer_bitvector.h
@@ -27,8 +27,18 @@ class BasicBitVector {
   // No CTOR.
   void clear() { bits_ = 0; }
   bool empty() const { return bits_ == 0; }
-  void setBit(uptr idx) { bits_ |= mask(idx); }
-  void clearBit(uptr idx) { bits_ &= ~mask(idx); }
+  // Returns true if the bit has changed from 0 to 1.
+  bool setBit(uptr idx) {
+    basic_int_t old = bits_;
+    bits_ |= mask(idx);
+    return bits_ != old;
+  }
+  // Returns true if the bit has changed from 1 to 0.
+  bool clearBit(uptr idx) {
+    basic_int_t old = bits_;
+    bits_ &= ~mask(idx);
+    return bits_ != old;
+  }
   bool getBit(uptr idx) const { return bits_ & mask(idx); }
   uptr getAndClearFirstOne() {
     CHECK(!empty());
@@ -38,6 +48,17 @@ class BasicBitVector {
     return idx;
   }
 
+  // Do "this |= v" and return whether new bits have been added.
+  bool setUnion(const BasicBitVector &v) {
+    basic_int_t old = bits_;
+    bits_ |= v.bits_;
+    return bits_ != old;
+  }
+
+  // Returns true if 'this' intersects with 'v'.
+  bool intersectsWith(const BasicBitVector &v) const { return bits_ & v.bits_; }
+
+
  private:
   basic_int_t mask(uptr idx) const {
     CHECK_LE(idx, size());
@@ -70,7 +91,8 @@ class TwoLevelBitVector {
         return false;
     return true;
   }
-  void setBit(uptr idx) {
+  // Returns true if the bit has changed from 0 to 1.
+  bool setBit(uptr idx) {
     check(idx);
     uptr i0 = idx0(idx);
     uptr i1 = idx1(idx);
@@ -79,21 +101,25 @@ class TwoLevelBitVector {
       l1_[i0].setBit(i1);
       l2_[i0][i1].clear();
     }
-    l2_[i0][i1].setBit(i2);
-    // Printf("%s: %zd => %zd %zd %zd\n", __FUNCTION__, idx, i0, i1, i2);
+    bool res = l2_[i0][i1].setBit(i2);
+    // Printf("%s: %zd => %zd %zd %zd; %d\n", __FUNCTION__,
+    // idx, i0, i1, i2, res);
+    return res;
   }
-  void clearBit(uptr idx) {
+  bool clearBit(uptr idx) {
     check(idx);
     uptr i0 = idx0(idx);
     uptr i1 = idx1(idx);
     uptr i2 = idx2(idx);
+    bool res = false;
     if (l1_[i0].getBit(i1)) {
-      l2_[i0][i1].clearBit(i2);
+      res = l2_[i0][i1].clearBit(i2);
       if (l2_[i0][i1].empty())
         l1_[i0].clearBit(i1);
     }
+    return res;
   }
-  bool getBit(uptr idx) {
+  bool getBit(uptr idx) const {
     check(idx);
     uptr i0 = idx0(idx);
     uptr i1 = idx1(idx);
@@ -115,20 +141,49 @@ class TwoLevelBitVector {
     CHECK(0);
     return 0;
   }
+  // Do "this |= v" and return whether new bits have been added.
+  bool setUnion(const TwoLevelBitVector &v) {
+    bool res = false;
+    for (uptr i0 = 0; i0 < kLevel1Size; i0++) {
+      BV t = v.l1_[i0];
+      while (!t.empty()) {
+        uptr i1 = t.getAndClearFirstOne();
+        if (l1_[i0].setBit(i1))
+          l2_[i0][i1].clear();
+        if (l2_[i0][i1].setUnion(v.l2_[i0][i1]))
+          res = true;
+      }
+    }
+    return res;
+  }
+
+  // Returns true if 'this' intersects with 'v'.
+  bool intersectsWith(const TwoLevelBitVector &v) const {
+    for (uptr i0 = 0; i0 < kLevel1Size; i0++) {
+      BV t = l1_[i0];
+      while (!t.empty()) {
+        uptr i1 = t.getAndClearFirstOne();
+        if (!v.l1_[i0].getBit(i1)) continue;
+        if (l2_[i0][i1].intersectsWith(v.l2_[i0][i1]))
+          return true;
+      }
+    }
+    return false;
+  }
 
  private:
-  void check(uptr idx) { CHECK_LE(idx, size()); }
-  uptr idx0(uptr idx) {
+  void check(uptr idx) const { CHECK_LE(idx, size()); }
+  uptr idx0(uptr idx) const {
     uptr res = idx / (BV::kSize * BV::kSize);
     CHECK_LE(res, kLevel1Size);
     return res;
   }
-  uptr idx1(uptr idx) {
+  uptr idx1(uptr idx) const {
     uptr res = (idx / BV::kSize) % BV::kSize;
     CHECK_LE(res, BV::kSize);
     return res;
   }
-  uptr idx2(uptr idx) {
+  uptr idx2(uptr idx) const {
     uptr res = idx % BV::kSize;
     CHECK_LE(res, BV::kSize);
     return res;
diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_bvgraph.h b/compiler-rt/lib/sanitizer_common/sanitizer_bvgraph.h
new file mode 100644
index 00000000000..7692c9f7a72
--- /dev/null
+++ b/compiler-rt/lib/sanitizer_common/sanitizer_bvgraph.h
@@ -0,0 +1,69 @@
+//===-- sanitizer_bvgraph.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.
+// BVGraph -- a directed graph.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef SANITIZER_BVGRAPH_H
+#define SANITIZER_BVGRAPH_H
+
+#include "sanitizer_common.h"
+#include "sanitizer_bitvector.h"
+
+namespace __sanitizer {
+
+// Directed graph of fixed size implemented as an array of bit vectors.
+template<class BV>
+class BVGraph {
+ public:
+  enum SizeEnum { kSize = BV::kSize };
+  uptr size() const { return kSize; }
+  // No CTOR.
+  void clear() {
+    for (uptr i = 0; i < size(); i++)
+      v[i].clear();
+  }
+
+  // Returns true if a new edge was added.
+  bool addEdge(uptr from, uptr to) {
+    check(from|to);
+    return v[from].setBit(to);
+  }
+
+  bool hasEdge(uptr from, uptr to) const {
+    check(from|to);
+    return v[from].getBit(to);
+  }
+
+  // Returns true if there is a path from the node 'from'
+  // to any of the nodes in 'target'.
+  bool isReachable(uptr from, const BV &target) {
+    BV to_visit, visited;
+    to_visit.clear();
+    to_visit.setUnion(v[from]);
+    visited.clear();
+    visited.setBit(from);
+    while (!to_visit.empty()) {
+      uptr idx = to_visit.getAndClearFirstOne();
+      if (visited.setBit(idx))
+        to_visit.setUnion(v[idx]);
+    }
+    return target.intersectsWith(visited);
+  }
+
+ private:
+  void check(uptr idx) const { CHECK_LE(idx, size()); }
+  BV v[kSize];
+};
+
+} // namespace __sanitizer
+
+#endif // SANITIZER_BVGRAPH_H
diff --git a/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt b/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt
index 551c312c119..47157221b94 100644
--- a/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt
+++ b/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt
@@ -4,6 +4,7 @@ set(SANITIZER_UNITTESTS
   sanitizer_allocator_test.cc
   sanitizer_atomic_test.cc
   sanitizer_bitvector_test.cc
+  sanitizer_bvgraph_test.cc
   sanitizer_common_test.cc
   sanitizer_flags_test.cc
   sanitizer_format_interceptor_test.cc
diff --git a/compiler-rt/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc b/compiler-rt/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc
index adc68385dc4..6a0e30dcfe4 100644
--- a/compiler-rt/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc
+++ b/compiler-rt/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc
@@ -26,7 +26,7 @@ using namespace std;
 
 template <class BV>
 void TestBitVector(uptr expected_size) {
-  BV bv;
+  BV bv, bv1;
   EXPECT_EQ(expected_size, BV::kSize);
   bv.clear();
   EXPECT_TRUE(bv.empty());
@@ -46,31 +46,51 @@ void TestBitVector(uptr expected_size) {
     EXPECT_EQ(bv.getBit(bit), s.count(bit) == 1);
     switch (my_rand() % 2) {
       case 0:
-        bv.setBit(bit);
-        s.insert(bit);
+        EXPECT_EQ(bv.setBit(bit), s.insert(bit).second);
         break;
       case 1:
-        bv.clearBit(bit);
+        size_t old_size = s.size();
         s.erase(bit);
+        EXPECT_EQ(bv.clearBit(bit), old_size > s.size());
         break;
     }
     EXPECT_EQ(bv.getBit(bit), s.count(bit) == 1);
   }
 
-  // test getAndClearFirstOne.
   vector<uptr>bits(bv.size());
+  // Test setUnion, intersectsWith, and getAndClearFirstOne.
   for (uptr it = 0; it < 30; it++) {
     // iota
     for (size_t j = 0; j < bits.size(); j++) bits[j] = j;
     random_shuffle(bits.begin(), bits.end());
+    set<uptr> s, s1;
+    bv.clear();
+    bv1.clear();
     uptr n_bits = ((uptr)my_rand() % bv.size()) + 1;
+    uptr n_bits1 = (uptr)my_rand() % (bv.size() / 2);
     EXPECT_TRUE(n_bits > 0 && n_bits <= bv.size());
-    bv.clear();
-    set<uptr> s(bits.begin(), bits.begin() + n_bits);
+    EXPECT_TRUE(n_bits1 < bv.size() / 2);
     for (uptr i = 0; i < n_bits; i++) {
       bv.setBit(bits[i]);
       s.insert(bits[i]);
     }
+    for (uptr i = 0; i < n_bits1; i++) {
+      bv1.setBit(bits[bv.size() / 2 + i]);
+      s1.insert(bits[bv.size() / 2 + i]);
+    }
+
+    vector<uptr> vec;
+    set_intersection(s.begin(), s.end(), s1.begin(), s1.end(),
+                     back_insert_iterator<vector<uptr> >(vec));
+    EXPECT_EQ(bv.intersectsWith(bv1), !vec.empty());
+
+    size_t old_size = s.size();
+    s.insert(s1.begin(), s1.end());
+    EXPECT_EQ(bv.setUnion(bv1), old_size != s.size());
+    if (0)
+      printf("union %zd %zd: %zd => %zd;  added %zd; intersection: %zd\n",
+             n_bits, n_bits1, old_size, s.size(), s.size() - old_size,
+             vec.size());
     while (!bv.empty()) {
       uptr idx = bv.getAndClearFirstOne();
       EXPECT_TRUE(s.erase(idx));
diff --git a/compiler-rt/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc b/compiler-rt/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc
new file mode 100644
index 00000000000..d84ccdafd30
--- /dev/null
+++ b/compiler-rt/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc
@@ -0,0 +1,112 @@
+//===-- sanitizer_bvgraph_test.cc -----------------------------------------===//
+//
+//                     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.
+// Tests for sanitizer_bvgraph.h.
+//
+//===----------------------------------------------------------------------===//
+#include "sanitizer_common/sanitizer_bvgraph.h"
+
+#include "sanitizer_test_utils.h"
+
+#include "gtest/gtest.h"
+
+#include <algorithm>
+#include <vector>
+#include <set>
+
+using namespace __sanitizer;
+using namespace std;
+
+class SimpleGraph {
+ public:
+  bool addEdge(uptr from, uptr to) {
+    return s_.insert(idx(from, to)).second;
+  }
+ private:
+  uptr idx(uptr from, uptr to) {
+    CHECK_LE(from|to, 1 << 16);
+    return (from << 16) + to;
+  }
+  set<uptr> s_;
+};
+
+TEST(SanitizerCommon, BVGraph) {
+  typedef TwoLevelBitVector<> BV;
+  BVGraph<BV> g;
+  g.clear();
+  BV target;
+  SimpleGraph s_g;
+  set<uptr> s;
+  set<uptr> s_target;
+  int num_reachable = 0;
+  for (int it = 0; it < 3000; it++) {
+    target.clear();
+    s_target.clear();
+    for (int t = 0; t < 4; t++) {
+      uptr idx = (uptr)my_rand() % g.size();
+      EXPECT_EQ(target.setBit(idx), s_target.insert(idx).second);
+    }
+    uptr from = my_rand() % g.size();
+    uptr to = my_rand() % g.size();
+    EXPECT_EQ(g.addEdge(from, to), s_g.addEdge(from, to));
+    EXPECT_TRUE(g.hasEdge(from, to));
+    for (int i = 0; i < 10; i++) {
+      from = my_rand() % g.size();
+      bool is_reachable = g.isReachable(from, target);
+      if (is_reachable) {
+        // printf("reachable: %d %zd\n", it, from);
+        num_reachable++;
+      }
+    }
+  }
+  EXPECT_GT(num_reachable, 0);
+}
+
+TEST(SanitizerCommon, BVGraph_isReachable) {
+  typedef TwoLevelBitVector<> BV;
+  BVGraph<BV> g;
+  g.clear();
+  BV target;
+  target.clear();
+  uptr t0 = 100;
+  uptr t1 = g.size() - 1;
+  target.setBit(t0);
+  target.setBit(t1);
+
+  uptr f0 = 0;
+  uptr f1 = 99;
+  uptr f2 = 200;
+  uptr f3 = g.size() - 2;
+
+  EXPECT_FALSE(g.isReachable(f0, target));
+  EXPECT_FALSE(g.isReachable(f1, target));
+  EXPECT_FALSE(g.isReachable(f2, target));
+  EXPECT_FALSE(g.isReachable(f3, target));
+
+  g.addEdge(f0, f1);
+  g.addEdge(f1, f2);
+  g.addEdge(f2, f3);
+  EXPECT_FALSE(g.isReachable(f0, target));
+  EXPECT_FALSE(g.isReachable(f1, target));
+  EXPECT_FALSE(g.isReachable(f2, target));
+  EXPECT_FALSE(g.isReachable(f3, target));
+
+  g.addEdge(f1, t0);
+  EXPECT_TRUE(g.isReachable(f0, target));
+  EXPECT_TRUE(g.isReachable(f1, target));
+  EXPECT_FALSE(g.isReachable(f2, target));
+  EXPECT_FALSE(g.isReachable(f3, target));
+
+  g.addEdge(f3, t1);
+  EXPECT_TRUE(g.isReachable(f0, target));
+  EXPECT_TRUE(g.isReachable(f1, target));
+  EXPECT_TRUE(g.isReachable(f2, target));
+  EXPECT_TRUE(g.isReachable(f3, target));
+}