From 6239ca0fb2741276c55e3eac783e24108cc4f71e Mon Sep 17 00:00:00 2001
From: Kostya Serebryany <kcc@google.com>
Date: Mon, 31 Mar 2014 07:23:50 +0000
Subject: [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)

git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@205168 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/sanitizer_common/sanitizer_bvgraph.h             | 10 ++--------
 lib/sanitizer_common/sanitizer_deadlock_detector.h   | 19 ++++++++++++-------
 lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc | 10 ++++++----
 3 files changed, 20 insertions(+), 19 deletions(-)

(limited to 'lib')

diff --git a/lib/sanitizer_common/sanitizer_bvgraph.h b/lib/sanitizer_common/sanitizer_bvgraph.h
index 9a547d3d4..df72f1c2d 100644
--- a/lib/sanitizer_common/sanitizer_bvgraph.h
+++ b/lib/sanitizer_common/sanitizer_bvgraph.h
@@ -61,18 +61,12 @@ class BVGraph {
   }
 
   // *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/lib/sanitizer_common/sanitizer_deadlock_detector.h b/lib/sanitizer_common/sanitizer_deadlock_detector.h
index a0a03ccbb..e0beb1261 100644
--- a/lib/sanitizer_common/sanitizer_deadlock_detector.h
+++ b/lib/sanitizer_common/sanitizer_deadlock_detector.h
@@ -64,12 +64,10 @@ class DeadlockDetectorTLS {
       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 @@ class DeadlockDetectorTLS {
     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 @@ class DeadlockDetector {
     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/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc b/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc
index d0f03800f..3b39f8dd7 100644
--- a/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc
+++ b/lib/sanitizer_common/tests/sanitizer_bvgraph_test.cc
@@ -320,14 +320,16 @@ 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_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]);
 }
-- 
cgit v1.2.1