diff options
author | Kostya Serebryany <kcc@google.com> | 2014-03-19 13:53:37 +0000 |
---|---|---|
committer | Kostya Serebryany <kcc@google.com> | 2014-03-19 13:53:37 +0000 |
commit | 75ac702b0cde5be4497a023b3d86de9cb1f859b2 (patch) | |
tree | a4ce24571a1d35b3b3bba932065a1cd09b90d88d /lib | |
parent | af3a2afe05edae65ac5f98f83bd10d5bbb97be88 (diff) |
[sanitizer] when recycling deadlock graph nodes, properly recycle edges
git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@204233 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib')
-rw-r--r-- | lib/sanitizer_common/sanitizer_deadlock_detector.h | 12 | ||||
-rw-r--r-- | lib/sanitizer_common/tests/sanitizer_deadlock_detector_test.cc | 41 |
2 files changed, 51 insertions, 2 deletions
diff --git a/lib/sanitizer_common/sanitizer_deadlock_detector.h b/lib/sanitizer_common/sanitizer_deadlock_detector.h index 637153c90..965bd8042 100644 --- a/lib/sanitizer_common/sanitizer_deadlock_detector.h +++ b/lib/sanitizer_common/sanitizer_deadlock_detector.h @@ -153,6 +153,14 @@ class DeadlockDetector { if (!available_nodes_.empty()) return getAvailableNode(data); if (!recycled_nodes_.empty()) { + // Printf("recycling: n_edges_ %zd\n", n_edges_); + for (sptr i = n_edges_ - 1; i >= 0; i--) { + if (recycled_nodes_.getBit(edges_[i].from) || + recycled_nodes_.getBit(edges_[i].to)) { + Swap(edges_[i], edges_[n_edges_ - 1]); + n_edges_--; + } + } CHECK(available_nodes_.empty()); // removeEdgesFrom was called in removeNode. g_.removeEdgesTo(recycled_nodes_); @@ -233,7 +241,7 @@ class DeadlockDetector { if (n_edges_ < ARRAY_SIZE(edges_)) edges_[n_edges_++] = Edge((u16)added_edges[i], (u16)cur_idx, dtls->findLockContext(added_edges[i]), stk); - // Printf("Edge [%zd]: %u %zd=>%zd\n", i, stk, added_edges[i], cur_idx); + // Printf("E%zd: %u %zd=>%zd\n", n_edges_, stk, added_edges[i], cur_idx); } return n_added_edges; } @@ -256,7 +264,7 @@ class DeadlockDetector { bool onLock(DeadlockDetectorTLS<BV> *dtls, uptr cur_node, u32 stk = 0) { ensureCurrentEpoch(dtls); bool is_reachable = !isHeld(dtls, cur_node) && onLockBefore(dtls, cur_node); - addEdges(dtls, cur_node, 0); + addEdges(dtls, cur_node, stk); onLockAfter(dtls, cur_node, stk); return is_reachable; } diff --git a/lib/sanitizer_common/tests/sanitizer_deadlock_detector_test.cc b/lib/sanitizer_common/tests/sanitizer_deadlock_detector_test.cc index a11b5a514..8f9bb329d 100644 --- a/lib/sanitizer_common/tests/sanitizer_deadlock_detector_test.cc +++ b/lib/sanitizer_common/tests/sanitizer_deadlock_detector_test.cc @@ -444,3 +444,44 @@ void RunLockContextTest() { TEST(DeadlockDetector, LockContextTest) { RunLockContextTest<BV2>(); } + +template <class BV> +void RunRemoveEdgesTest() { + ScopedDD<BV> sdd; + DeadlockDetector<BV> &d = *sdd.dp; + DeadlockDetectorTLS<BV> &dtls = sdd.dtls; + vector<uptr> node(BV::kSize); + u32 stk_from = 0, stk_to = 0; + for (size_t i = 0; i < BV::kSize; i++) + node[i] = d.newNode(0); + + for (size_t i = 0; i < BV::kSize; i++) + EXPECT_FALSE(d.onLock(&dtls, node[i], i + 1)); + for (size_t i = 0; i < BV::kSize; i++) { + for (uptr j = i + 1; j < BV::kSize; j++) { + EXPECT_TRUE(d.findEdge(node[i], node[j], &stk_from, &stk_to)); + EXPECT_EQ(stk_from, i + 1); + EXPECT_EQ(stk_to, j + 1); + } + } + EXPECT_EQ(d.testOnlyGetEpoch(), d.size()); + // Remove and re-create half of the nodes. + for (uptr i = 1; i < BV::kSize; i += 2) + d.removeNode(node[i]); + for (uptr i = 1; i < BV::kSize; i += 2) + node[i] = d.newNode(0); + EXPECT_EQ(d.testOnlyGetEpoch(), d.size()); + // The edges from or to the removed nodes should be gone. + for (size_t i = 0; i < BV::kSize; i++) { + for (uptr j = i + 1; j < BV::kSize; j++) { + if ((i % 2) || (j % 2)) + EXPECT_FALSE(d.findEdge(node[i], node[j], &stk_from, &stk_to)); + else + EXPECT_TRUE(d.findEdge(node[i], node[j], &stk_from, &stk_to)); + } + } +} + +TEST(DeadlockDetector, RemoveEdgesTest) { + RunRemoveEdgesTest<BV1>(); +} |