diff options
Diffstat (limited to 'lib/sanitizer_common')
4 files changed, 109 insertions, 23 deletions
diff --git a/lib/sanitizer_common/sanitizer_bvgraph.h b/lib/sanitizer_common/sanitizer_bvgraph.h index c54955a5a..157b9320e 100644 --- a/lib/sanitizer_common/sanitizer_bvgraph.h +++ b/lib/sanitizer_common/sanitizer_bvgraph.h @@ -129,6 +129,15 @@ class BVGraph { return 0; } + // Same as findPath, but finds a shortest path. + uptr findShortestPath(uptr from, const BV &targets, uptr *path, + uptr path_size) { + for (uptr p = 1; p <= path_size; p++) + if (findPath(from, targets, path, p) == p) + return p; + return 0; + } + private: void check(uptr idx1, uptr idx2) const { CHECK_LT(idx1, size()); diff --git a/lib/sanitizer_common/sanitizer_deadlock_detector.h b/lib/sanitizer_common/sanitizer_deadlock_detector.h index 48ea022a5..0bbaea53e 100644 --- a/lib/sanitizer_common/sanitizer_deadlock_detector.h +++ b/lib/sanitizer_common/sanitizer_deadlock_detector.h @@ -137,11 +137,31 @@ class DeadlockDetector { return is_reachable; } + // Finds a path between the lock 'cur_node' (which is currently held in dtls) + // and some other currently held lock, returns the length of the path + // or 0 on failure. + uptr findPathToHeldLock(DeadlockDetectorTLS<BV> *dtls, uptr cur_node, + uptr *path, uptr path_size) { + tmp_bv_.copyFrom(dtls->getLocks()); + uptr idx = nodeToIndex(cur_node); + CHECK(tmp_bv_.clearBit(idx)); + uptr res = g_.findShortestPath(idx, tmp_bv_, path, path_size); + for (uptr i = 0; i < res; i++) + path[i] = indexToNode(path[i]); + if (res) + CHECK_EQ(path[0], cur_node); + return res; + } + // Handle the unlock event. void onUnlock(DeadlockDetectorTLS<BV> *dtls, uptr node) { dtls->removeLock(nodeToIndex(node), current_epoch_); } + bool isHeld(DeadlockDetectorTLS<BV> *dtls, uptr node) const { + return dtls->getLocks().getBit(nodeToIndex(node)); + } + uptr testOnlyGetEpoch() const { return current_epoch_; } void Print() { @@ -178,6 +198,7 @@ class DeadlockDetector { uptr current_epoch_; BV available_nodes_; BV recycled_nodes_; + BV tmp_bv_; BVGraph<BV> g_; uptr data_[BV::kSize]; }; diff --git a/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc b/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc index 722fef673..e584a541f 100644 --- a/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc +++ b/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc @@ -212,10 +212,10 @@ void Test_isReachable() { } TEST(BVGraph, isReachable) { - Test_isReachable<BasicBitVector<u8> >(); - Test_isReachable<BasicBitVector<> >(); - Test_isReachable<TwoLevelBitVector<> >(); - Test_isReachable<TwoLevelBitVector<3, BasicBitVector<u8> > >(); + Test_isReachable<BV1>(); + Test_isReachable<BV2>(); + Test_isReachable<BV3>(); + Test_isReachable<BV4>(); } template <class BV> @@ -256,8 +256,48 @@ void LongCycle() { } TEST(BVGraph, LongCycle) { - LongCycle<BasicBitVector<u8> >(); - LongCycle<BasicBitVector<> >(); - LongCycle<TwoLevelBitVector<> >(); - LongCycle<TwoLevelBitVector<2, BasicBitVector<u8> > >(); + LongCycle<BV1>(); + LongCycle<BV2>(); + LongCycle<BV3>(); + LongCycle<BV4>(); +} + +template <class BV> +void ShortestPath() { + uptr path[8]; + BVGraph<BV> g; + g.clear(); + BV t7; + t7.clear(); + t7.setBit(7); + // 1=>2=>3=>4=>5=>6=>7 + // 1=>7 + g.addEdge(1, 2); + g.addEdge(2, 3); + g.addEdge(3, 4); + g.addEdge(4, 5); + g.addEdge(5, 6); + g.addEdge(6, 7); + g.addEdge(1, 7); + EXPECT_TRUE(g.isReachable(1, t7)); + // No path of length 1. + EXPECT_EQ(0U, g.findPath(1, t7, path, 1)); + // Trying to find a path of len 2..6 gives path of len 2. + EXPECT_EQ(2U, g.findPath(1, t7, path, 2)); + EXPECT_EQ(2U, g.findPath(1, t7, path, 3)); + EXPECT_EQ(2U, g.findPath(1, t7, path, 4)); + EXPECT_EQ(2U, g.findPath(1, t7, path, 5)); + EXPECT_EQ(2U, g.findPath(1, t7, path, 6)); + // Trying to find a path of len 7 gives path of len 7, because this is DFS. + EXPECT_EQ(7U, g.findPath(1, t7, path, 7)); + // But findShortestPath will find the shortest path. + EXPECT_EQ(2U, g.findShortestPath(1, t7, path, 2)); + EXPECT_EQ(2U, g.findShortestPath(1, t7, path, 7)); +} + +TEST(BVGraph, ShortestPath) { + ShortestPath<BV1>(); + ShortestPath<BV2>(); + ShortestPath<BV3>(); + ShortestPath<BV4>(); } diff --git a/lib/sanitizer_common/tests/sanitizer_deadlock_detector_test.cc b/lib/sanitizer_common/tests/sanitizer_deadlock_detector_test.cc index 3f93c2363..fa9a6a794 100644 --- a/lib/sanitizer_common/tests/sanitizer_deadlock_detector_test.cc +++ b/lib/sanitizer_common/tests/sanitizer_deadlock_detector_test.cc @@ -43,7 +43,8 @@ struct ScopedDD { }; template <class BV> -void BasicTest() { +void RunBasicTest() { + uptr path[10]; ScopedDD<BV> sdd; DeadlockDetector<BV> &d = *sdd.dp; DeadlockDetectorTLS<BV> &dtls = sdd.dtls; @@ -82,6 +83,13 @@ void BasicTest() { EXPECT_FALSE(d.onLock(&dtls, n2)); EXPECT_TRUE(d.onLock(&dtls, n1)); + EXPECT_EQ(0U, d.findPathToHeldLock(&dtls, n1, path, 1)); + EXPECT_EQ(2U, d.findPathToHeldLock(&dtls, n1, path, 10)); + EXPECT_EQ(2U, d.findPathToHeldLock(&dtls, n1, path, 2)); + EXPECT_EQ(path[0], n1); + EXPECT_EQ(path[1], n2); + EXPECT_EQ(d.getData(n1), 1U); + EXPECT_EQ(d.getData(n2), 2U); d.onUnlock(&dtls, n1); d.onUnlock(&dtls, n2); } @@ -106,20 +114,28 @@ void BasicTest() { EXPECT_FALSE(d.onLock(&dtls, n3)); EXPECT_TRUE(d.onLock(&dtls, n1)); + EXPECT_EQ(0U, d.findPathToHeldLock(&dtls, n1, path, 2)); + EXPECT_EQ(3U, d.findPathToHeldLock(&dtls, n1, path, 10)); + EXPECT_EQ(path[0], n1); + EXPECT_EQ(path[1], n2); + EXPECT_EQ(path[2], n3); + EXPECT_EQ(d.getData(n1), 1U); + EXPECT_EQ(d.getData(n2), 2U); + EXPECT_EQ(d.getData(n3), 3U); d.onUnlock(&dtls, n1); d.onUnlock(&dtls, n3); } } TEST(DeadlockDetector, BasicTest) { - BasicTest<BV1>(); - BasicTest<BV2>(); - BasicTest<BV3>(); - BasicTest<BV4>(); + RunBasicTest<BV1>(); + RunBasicTest<BV2>(); + RunBasicTest<BV3>(); + RunBasicTest<BV4>(); } template <class BV> -void RemoveNodeTest() { +void RunRemoveNodeTest() { ScopedDD<BV> sdd; DeadlockDetector<BV> &d = *sdd.dp; DeadlockDetectorTLS<BV> &dtls = sdd.dtls; @@ -218,14 +234,14 @@ void RemoveNodeTest() { } TEST(DeadlockDetector, RemoveNodeTest) { - RemoveNodeTest<BV1>(); - RemoveNodeTest<BV2>(); - RemoveNodeTest<BV3>(); - RemoveNodeTest<BV4>(); + RunRemoveNodeTest<BV1>(); + RunRemoveNodeTest<BV2>(); + RunRemoveNodeTest<BV3>(); + RunRemoveNodeTest<BV4>(); } template <class BV> -void MultipleEpochsTest() { +void RunMultipleEpochsTest() { ScopedDD<BV> sdd; DeadlockDetector<BV> &d = *sdd.dp; DeadlockDetectorTLS<BV> &dtls = sdd.dtls; @@ -259,10 +275,10 @@ void MultipleEpochsTest() { } TEST(DeadlockDetector, MultipleEpochsTest) { - MultipleEpochsTest<BV1>(); - MultipleEpochsTest<BV2>(); - MultipleEpochsTest<BV3>(); - MultipleEpochsTest<BV4>(); + RunMultipleEpochsTest<BV1>(); + RunMultipleEpochsTest<BV2>(); + RunMultipleEpochsTest<BV3>(); + RunMultipleEpochsTest<BV4>(); } |