diff options
author | Kostya Serebryany <kcc@google.com> | 2014-03-14 08:06:15 +0000 |
---|---|---|
committer | Kostya Serebryany <kcc@google.com> | 2014-03-14 08:06:15 +0000 |
commit | 30fd39fe12a619c9317d0dbd605b63cd044a0f43 (patch) | |
tree | 0cd41a70a56273f668c6d54384832c66a9025f36 /lib | |
parent | de54e50adca1ed8572a97ec8a923b9823d8850ae (diff) | |
download | compiler-rt-30fd39fe12a619c9317d0dbd605b63cd044a0f43.tar.gz |
[sanitizer] partially implement racy fast path in bitset-based deadlock detector
git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@203904 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib')
-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]); } |