[sanitizer] speed up the bitvector-based deadlock detector by ~15% (iterate over the currently held locks using the array, not the bitvector. Bitvector is not the best data structure to iterate over)
llvm-svn: 205168
diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_bvgraph.h b/compiler-rt/lib/sanitizer_common/sanitizer_bvgraph.h
index 9a547d3..df72f1c 100644
--- a/compiler-rt/lib/sanitizer_common/sanitizer_bvgraph.h
+++ b/compiler-rt/lib/sanitizer_common/sanitizer_bvgraph.h
@@ -61,18 +61,12 @@
}
// *EXPERIMENTAL*
- // Returns true if all edges from=>to exist.
+ // Returns true if an edge from=>to exist.
// This function does not use any global state except for 'this' itself,
// and thus can be called from different threads w/o locking.
// This would be racy.
// FIXME: investigate how much we can prove about this race being "benign".
- bool hasAllEdges(const BV &from, uptr to) {
- for (typename BV::Iterator it(from); it.hasNext(); ) {
- uptr idx = it.next();
- if (!v[idx].getBit(to)) return false;
- }
- return true;
- }
+ bool hasEdge(uptr from, uptr to) { return v[from].getBit(to); }
// Returns true if the edge from=>to was removed.
bool removeEdge(uptr from, uptr to) {
diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_deadlock_detector.h b/compiler-rt/lib/sanitizer_common/sanitizer_deadlock_detector.h
index a0a03cc..e0beb12 100644
--- a/compiler-rt/lib/sanitizer_common/sanitizer_deadlock_detector.h
+++ b/compiler-rt/lib/sanitizer_common/sanitizer_deadlock_detector.h
@@ -64,12 +64,10 @@
recursive_locks[n_recursive_locks++] = lock_id;
return false;
}
- if (stk) {
- CHECK_LT(n_all_locks_, ARRAY_SIZE(all_locks_with_contexts_));
- // lock_id < BV::kSize, can cast to a smaller int.
- u32 lock_id_short = static_cast<u32>(lock_id);
- all_locks_with_contexts_[n_all_locks_++] = {lock_id_short, stk};
- }
+ CHECK_LT(n_all_locks_, ARRAY_SIZE(all_locks_with_contexts_));
+ // lock_id < BV::kSize, can cast to a smaller int.
+ u32 lock_id_short = static_cast<u32>(lock_id);
+ all_locks_with_contexts_[n_all_locks_++] = {lock_id_short, stk};
return true;
}
@@ -109,6 +107,9 @@
return bv_;
}
+ uptr getNumLocks() const { return n_all_locks_; }
+ uptr getLock(uptr idx) const { return all_locks_with_contexts_[idx].lock; }
+
private:
BV bv_;
uptr epoch_;
@@ -222,7 +223,11 @@
if (cur_node && local_epoch == current_epoch_ &&
local_epoch == nodeToEpoch(cur_node)) {
uptr cur_idx = nodeToIndexUnchecked(cur_node);
- return g_.hasAllEdges(dtls->getLocks(local_epoch), cur_idx);
+ for (uptr i = 0, n = dtls->getNumLocks(); i < n; i++) {
+ if (!g_.hasEdge(dtls->getLock(i), cur_idx))
+ return false;
+ }
+ return true;
}
return false;
}
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 d0f0380..3b39f8d 100644
--- a/compiler-rt/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc
+++ b/compiler-rt/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc
@@ -320,14 +320,16 @@
from.clear();
from.setBit(1);
EXPECT_EQ(1U, g.addEdges(from, 4, added_edges, kMaxEdges));
- EXPECT_TRUE(g.hasAllEdges(from, 4));
- EXPECT_FALSE(g.hasAllEdges(from, 5));
+ EXPECT_TRUE(g.hasEdge(1, 4));
+ EXPECT_FALSE(g.hasEdge(1, 5));
EXPECT_EQ(1U, added_edges[0]);
from.setBit(2);
from.setBit(3);
- EXPECT_FALSE(g.hasAllEdges(from, 4));
EXPECT_EQ(2U, g.addEdges(from, 4, added_edges, kMaxEdges));
- EXPECT_TRUE(g.hasAllEdges(from, 4));
+ EXPECT_TRUE(g.hasEdge(2, 4));
+ EXPECT_FALSE(g.hasEdge(2, 5));
+ EXPECT_TRUE(g.hasEdge(3, 4));
+ EXPECT_FALSE(g.hasEdge(3, 5));
EXPECT_EQ(2U, added_edges[0]);
EXPECT_EQ(3U, added_edges[1]);
}