From be1d22b631ed03f213e87acd0b9479be3d46ca79 Mon Sep 17 00:00:00 2001 From: Kostya Serebryany Date: Wed, 12 Feb 2014 11:28:09 +0000 Subject: [PATCH] [sanitizer] added class BVGraph, to be used in a deadlock detector; added more methods to the bit vectors llvm-svn: 201226 --- compiler-rt/lib/sanitizer_common/CMakeLists.txt | 1 + .../lib/sanitizer_common/sanitizer_bitvector.h | 79 ++++++++++++--- .../lib/sanitizer_common/sanitizer_bvgraph.h | 69 +++++++++++++ .../lib/sanitizer_common/tests/CMakeLists.txt | 1 + .../tests/sanitizer_bitvector_test.cc | 34 +++++-- .../tests/sanitizer_bvgraph_test.cc | 112 +++++++++++++++++++++ 6 files changed, 277 insertions(+), 19 deletions(-) create mode 100644 compiler-rt/lib/sanitizer_common/sanitizer_bvgraph.h create mode 100644 compiler-rt/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc diff --git a/compiler-rt/lib/sanitizer_common/CMakeLists.txt b/compiler-rt/lib/sanitizer_common/CMakeLists.txt index 26e6a27..3468bef 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 bef680c..5f323ce 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 0000000..7692c9f --- /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 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 551c312..4715722 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 adc6838..6a0e30d 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 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. vectorbits(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 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 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 vec; + set_intersection(s.begin(), s.end(), s1.begin(), s1.end(), + back_insert_iterator >(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 0000000..d84ccda --- /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 +#include +#include + +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 s_; +}; + +TEST(SanitizerCommon, BVGraph) { + typedef TwoLevelBitVector<> BV; + BVGraph g; + g.clear(); + BV target; + SimpleGraph s_g; + set s; + set 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 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)); +} -- 2.7.4