diff options
| -rw-r--r-- | lib/sanitizer_common/sanitizer_bvgraph.h | 14 | ||||
| -rw-r--r-- | lib/sanitizer_common/sanitizer_deadlock_detector.h | 10 | ||||
| -rw-r--r-- | lib/sanitizer_common/sanitizer_deadlock_detector1.cc | 2 | ||||
| -rw-r--r-- | lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc | 4 |
4 files changed, 30 insertions, 0 deletions
diff --git a/lib/sanitizer_common/sanitizer_bvgraph.h b/lib/sanitizer_common/sanitizer_bvgraph.h index a55757b5d..9a547d3d4 100644 --- a/lib/sanitizer_common/sanitizer_bvgraph.h +++ b/lib/sanitizer_common/sanitizer_bvgraph.h @@ -60,6 +60,20 @@ class BVGraph { return res; } + // *EXPERIMENTAL* + // Returns true if all edges 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; + } + // Returns true if the edge from=>to was removed. bool removeEdge(uptr from, uptr to) { return v[from].clearBit(to); diff --git a/lib/sanitizer_common/sanitizer_deadlock_detector.h b/lib/sanitizer_common/sanitizer_deadlock_detector.h index 33913137f..6d4cec86c 100644 --- a/lib/sanitizer_common/sanitizer_deadlock_detector.h +++ b/lib/sanitizer_common/sanitizer_deadlock_detector.h @@ -172,6 +172,16 @@ class DeadlockDetector { dtls->addLock(cur_idx, current_epoch_); } + // Experimental *racy* fast path function. + // Returns true if all edges from the currently held locks to cur_node exist. + bool hasAllEdges(DeadlockDetectorTLS<BV> *dtls, uptr cur_node) { + if (dtls->getEpoch() == nodeToEpoch(cur_node)) { + uptr cur_idx = nodeToIndexUnchecked(cur_node); + return g_.hasAllEdges(dtls->getLocks(current_epoch_), cur_idx); + } + return false; + } + // Adds edges from currently held locks to cur_node, // returns the number of added edges, and puts the sources of added edges // into added_edges[]. diff --git a/lib/sanitizer_common/sanitizer_deadlock_detector1.cc b/lib/sanitizer_common/sanitizer_deadlock_detector1.cc index 9dbb38f71..3f02b3417 100644 --- a/lib/sanitizer_common/sanitizer_deadlock_detector1.cc +++ b/lib/sanitizer_common/sanitizer_deadlock_detector1.cc @@ -100,6 +100,7 @@ void DD::MutexBeforeLock(DDCallback *cb, DDMutex *m, bool wlock) { DDLogicalThread *lt = cb->lt; if (lt->dd.empty()) return; // This will be the first lock held by lt. + if (dd.hasAllEdges(<->dd, m->id)) return; // We already have all edges. SpinMutexLock lk(&mtx); MutexEnsureID(lt, m); if (dd.isHeld(<->dd, m->id)) @@ -131,6 +132,7 @@ void DD::MutexAfterLock(DDCallback *cb, DDMutex *m, bool wlock, bool trylock) { // Printf("T%p MutexLock: %zx\n", lt, m->id); if (dd.onFirstLock(<->dd, m->id)) return; + // if (dd.hasAllEdges(<->dd, m->id)) return; SpinMutexLock lk(&mtx); MutexEnsureID(lt, m); if (wlock) // Only a recursive rlock may be held. diff --git a/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc b/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc index b7be2a862..d0f03800f 100644 --- a/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc +++ b/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc @@ -320,10 +320,14 @@ void RunAddEdgesTest() { 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_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_EQ(2U, added_edges[0]); EXPECT_EQ(3U, added_edges[1]); } |