diff options
-rw-r--r-- | lib/sanitizer_common/sanitizer_bitvector.h | 29 | ||||
-rw-r--r-- | lib/sanitizer_common/sanitizer_bvgraph.h | 5 | ||||
-rw-r--r-- | lib/sanitizer_common/sanitizer_deadlock_detector.h | 6 | ||||
-rw-r--r-- | lib/sanitizer_common/tests/sanitizer_bitvector_test.cc | 77 |
4 files changed, 91 insertions, 26 deletions
diff --git a/lib/sanitizer_common/sanitizer_bitvector.h b/lib/sanitizer_common/sanitizer_bitvector.h index cf7b8ccba..93b99a4ce 100644 --- a/lib/sanitizer_common/sanitizer_bitvector.h +++ b/lib/sanitizer_common/sanitizer_bitvector.h @@ -61,6 +61,13 @@ class BasicBitVector { return bits_ != old; } + // Do "this &= v" and return whether any bits have been removed. + bool setIntersection(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'. @@ -180,6 +187,26 @@ class TwoLevelBitVector { return res; } + // Do "this &= v" and return whether any bits have been removed. + bool setIntersection(const TwoLevelBitVector &v) { + bool res = false; + for (uptr i0 = 0; i0 < kLevel1Size; i0++) { + if (l1_[i0].setIntersection(v.l1_[i0])) + res = true; + if (!l1_[i0].empty()) { + BV t = l1_[i0]; + while (!t.empty()) { + uptr i1 = t.getAndClearFirstOne(); + if (l2_[i0][i1].setIntersection(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); @@ -189,7 +216,7 @@ class TwoLevelBitVector { bool intersectsWith(const TwoLevelBitVector &v) const { for (uptr i0 = 0; i0 < kLevel1Size; i0++) { BV t = l1_[i0]; - // FIXME: optimization: t &= v.l1_[i0] + t.setIntersection(v.l1_[i0]); while (!t.empty()) { uptr i1 = t.getAndClearFirstOne(); if (!v.l1_[i0].getBit(i1)) continue; diff --git a/lib/sanitizer_common/sanitizer_bvgraph.h b/lib/sanitizer_common/sanitizer_bvgraph.h index 958dd4d2a..4aed87ab5 100644 --- a/lib/sanitizer_common/sanitizer_bvgraph.h +++ b/lib/sanitizer_common/sanitizer_bvgraph.h @@ -78,7 +78,10 @@ class BVGraph { } private: - void check(uptr idx1, uptr idx2) const { CHECK_LE(idx1|idx2, size()); } + void check(uptr idx1, uptr idx2) const { + CHECK_LT(idx1, size()); + CHECK_LT(idx2, size()); + } BV v[kSize]; }; diff --git a/lib/sanitizer_common/sanitizer_deadlock_detector.h b/lib/sanitizer_common/sanitizer_deadlock_detector.h index 66ec0186d..fcdc3f2e5 100644 --- a/lib/sanitizer_common/sanitizer_deadlock_detector.h +++ b/lib/sanitizer_common/sanitizer_deadlock_detector.h @@ -95,10 +95,10 @@ class DeadlockDetector { return getAvailableNode(data); } // We are out of vacant nodes. Flush and increment the current_epoch_. - uptr new_epoch = current_epoch_ + size(); - clear(); - current_epoch_ = new_epoch; + current_epoch_ += size(); + recycled_nodes_.clear(); available_nodes_.setAll(); + g_.clear(); return getAvailableNode(data); } diff --git a/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc b/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc index d512f57dd..f32c4c27a 100644 --- a/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc +++ b/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc @@ -24,19 +24,50 @@ using namespace __sanitizer; using namespace std; + +template <class BV> +static void SameAs(const BV &bv, const set<uptr> &s) { + BV t; + t.copyFrom(bv); + set<uptr> t_s(s); + while (!t.empty()) { + uptr idx = t.getAndClearFirstOne(); + EXPECT_TRUE(t_s.erase(idx)); + } + EXPECT_TRUE(t_s.empty()); +} + +template <class BV> +void Print(const BV &bv) { + BV t; + t.copyFrom(bv); + while (!t.empty()) { + uptr idx = t.getAndClearFirstOne(); + fprintf(stderr, "%zd ", idx); + } + fprintf(stderr, "\n"); +} + +void Print(const set<uptr> &s) { + for (set<uptr>::reverse_iterator it = s.rbegin(); it != s.rend(); ++it) { + fprintf(stderr, "%zd ", *it); + } + fprintf(stderr, "\n"); +} + template <class BV> void TestBitVector(uptr expected_size) { - BV bv, bv1; + BV bv, bv1, t_bv; EXPECT_EQ(expected_size, BV::kSize); bv.clear(); EXPECT_TRUE(bv.empty()); - bv.setBit(13); + bv.setBit(5); EXPECT_FALSE(bv.empty()); - EXPECT_FALSE(bv.getBit(12)); - EXPECT_FALSE(bv.getBit(14)); - EXPECT_TRUE(bv.getBit(13)); - bv.clearBit(13); - EXPECT_FALSE(bv.getBit(13)); + EXPECT_FALSE(bv.getBit(4)); + EXPECT_FALSE(bv.getBit(6)); + EXPECT_TRUE(bv.getBit(5)); + bv.clearBit(5); + EXPECT_FALSE(bv.getBit(5)); // test random bits bv.clear(); @@ -58,12 +89,12 @@ void TestBitVector(uptr expected_size) { } vector<uptr>bits(bv.size()); - // Test setUnion, intersectsWith, and getAndClearFirstOne. + // Test setUnion, setIntersection, 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; + set<uptr> s, s1, t_s; bv.clear(); bv1.clear(); uptr n_bits = ((uptr)my_rand() % bv.size()) + 1; @@ -74,32 +105,36 @@ void TestBitVector(uptr expected_size) { bv.setBit(bits[i]); s.insert(bits[i]); } + SameAs(bv, s); for (uptr i = 0; i < n_bits1; i++) { bv1.setBit(bits[bv.size() / 2 + i]); s1.insert(bits[bv.size() / 2 + i]); } + SameAs(bv1, s1); 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)); - } - EXPECT_TRUE(s.empty()); + // setUnion + t_s = s; + t_bv.copyFrom(bv); + t_s.insert(s1.begin(), s1.end()); + EXPECT_EQ(t_bv.setUnion(bv1), s.size() != t_s.size()); + SameAs(t_bv, t_s); + + // setIntersection + t_s = set<uptr>(vec.begin(), vec.end()); + t_bv.copyFrom(bv); + EXPECT_EQ(t_bv.setIntersection(bv1), s.size() != t_s.size()); + SameAs(t_bv, t_s); } } TEST(SanitizerCommon, BasicBitVector) { + TestBitVector<BasicBitVector<u8> >(8); + TestBitVector<BasicBitVector<u16> >(16); TestBitVector<BasicBitVector<> >(SANITIZER_WORDSIZE); } |