From 73325589dc2c4d641a9615b79d70970c51289245 Mon Sep 17 00:00:00 2001 From: Kostya Serebryany Date: Mon, 17 Feb 2014 11:21:52 +0000 Subject: [PATCH] [sanitizer] implement node removal in Deadlock graph llvm-svn: 201509 --- .../lib/sanitizer_common/sanitizer_bitvector.h | 24 +++++ .../lib/sanitizer_common/sanitizer_bvgraph.h | 40 +++++++ .../sanitizer_common/sanitizer_deadlock_detector.h | 11 +- .../tests/sanitizer_bitvector_test.cc | 18 +++- .../tests/sanitizer_bvgraph_test.cc | 82 +++++++++++++- .../tests/sanitizer_deadlock_detector_test.cc | 119 ++++++++++++++++++++- 6 files changed, 278 insertions(+), 16 deletions(-) diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_bitvector.h b/compiler-rt/lib/sanitizer_common/sanitizer_bitvector.h index 4ad379b..d16205a 100644 --- a/compiler-rt/lib/sanitizer_common/sanitizer_bitvector.h +++ b/compiler-rt/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/compiler-rt/lib/sanitizer_common/sanitizer_bvgraph.h b/compiler-rt/lib/sanitizer_common/sanitizer_bvgraph.h index 8d3e6af..c54955a 100644 --- a/compiler-rt/lib/sanitizer_common/sanitizer_bvgraph.h +++ b/compiler-rt/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/compiler-rt/lib/sanitizer_common/sanitizer_deadlock_detector.h b/compiler-rt/lib/sanitizer_common/sanitizer_deadlock_detector.h index aa2644f..d0ff29d 100644 --- a/compiler-rt/lib/sanitizer_common/sanitizer_deadlock_detector.h +++ b/compiler-rt/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/compiler-rt/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc b/compiler-rt/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc index 1637fa8..706b4c5 100644 --- a/compiler-rt/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc +++ b/compiler-rt/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc @@ -67,7 +67,7 @@ void Print(const BV &bv) { } void Print(const set &s) { - for (set::reverse_iterator it = s.rbegin(); it != s.rend(); ++it) { + for (set::iterator it = s.begin(); it != s.end(); ++it) { fprintf(stderr, "%zd ", *it); } fprintf(stderr, "\n"); @@ -107,7 +107,8 @@ void TestBitVector(uptr expected_size) { } vectorbits(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 >(vec)); + t_s = set(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 > >(8 * 8); TestBitVector >(ws * ws); TestBitVector >(ws * ws * 2); TestBitVector >(ws * ws * 3); - TestBitVector > > - (16 * 16 * 3); + TestBitVector > >(16 * 16 * 3); } diff --git a/compiler-rt/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc b/compiler-rt/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc index fe3665f..722fef6 100644 --- a/compiler-rt/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc +++ b/compiler-rt/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc @@ -24,6 +24,10 @@ using namespace __sanitizer; using namespace std; +typedef BasicBitVector BV1; +typedef BasicBitVector<> BV2; +typedef TwoLevelBitVector<> BV3; +typedef TwoLevelBitVector<3, BasicBitVector > BV4; template 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 + void checkSameAs(G *g) { + for (set::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 s_; }; -TEST(SanitizerCommon, BVGraph) { - typedef TwoLevelBitVector<> BV; +template +void BasicTest() { BVGraph g; g.clear(); BV target; @@ -57,7 +75,7 @@ TEST(SanitizerCommon, BVGraph) { set s; set 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(); + BasicTest(); + BasicTest(); + BasicTest(); +} + +template +void RemoveEdges() { + SimpleGraph s_g; + BVGraph g; + g.clear(); + BV bv; + set 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::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::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(); + RemoveEdges(); + RemoveEdges(); + RemoveEdges(); +} + template 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 >(); Test_isReachable >(); Test_isReachable >(); @@ -183,7 +255,7 @@ void LongCycle() { } } -TEST(SanitizerCommon, BVGraph_LongCycle) { +TEST(BVGraph, LongCycle) { LongCycle >(); LongCycle >(); LongCycle >(); diff --git a/compiler-rt/lib/sanitizer_common/tests/sanitizer_deadlock_detector_test.cc b/compiler-rt/lib/sanitizer_common/tests/sanitizer_deadlock_detector_test.cc index 594ea08..115b233 100644 --- a/compiler-rt/lib/sanitizer_common/tests/sanitizer_deadlock_detector_test.cc +++ b/compiler-rt/lib/sanitizer_common/tests/sanitizer_deadlock_detector_test.cc @@ -24,6 +24,11 @@ using namespace __sanitizer; using namespace std; +typedef BasicBitVector BV1; +typedef BasicBitVector<> BV2; +typedef TwoLevelBitVector<> BV3; +typedef TwoLevelBitVector<3, BasicBitVector > BV4; + // Poor man's unique_ptr. template struct ScopedDD { @@ -103,7 +108,115 @@ void BasicTest() { } TEST(DeadlockDetector, BasicTest) { - BasicTest >(); - BasicTest >(); - BasicTest > >(); + BasicTest(); + BasicTest(); + BasicTest(); + BasicTest(); +} + +template +void RemoveNodeTest() { + ScopedDD sdd; + DeadlockDetector &d = *sdd.dp; + DeadlockDetectorTLS 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 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(); + RemoveNodeTest(); + RemoveNodeTest(); + RemoveNodeTest(); } -- 2.7.4