[sanitizer] support recursive rwlocks in bitset-based deadlock detector

llvm-svn: 203779

3 files changed, 54 insertions, 5 deletions

diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_deadlock_detector.h b/compiler-rt/lib/sanitizer_common/sanitizer_deadlock_detector.h
index 68cd1a53262..d2f7b5d7044 100644
--- a/compiler-rt/lib/sanitizer_common/sanitizer_deadlock_detector.h
+++ b/compiler-rt/lib/sanitizer_common/sanitizer_deadlock_detector.h
@@ -40,6 +40,7 @@ class DeadlockDetectorTLS {
   void clear() {
     bv_.clear();
     epoch_ = 0;
+    n_recursive_locks = 0;
   }
 
   bool empty() const { return bv_.empty(); }
@@ -52,14 +53,30 @@ class DeadlockDetectorTLS {
 
   uptr getEpoch() const { return epoch_; }
 
-  void addLock(uptr lock_id, uptr current_epoch) {
+  // Returns true if this is the first (non-recursive) acquisition of this lock.
+  bool addLock(uptr lock_id, uptr current_epoch) {
     // Printf("addLock: %zx %zx\n", lock_id, current_epoch);
     CHECK_EQ(epoch_, current_epoch);
-    CHECK(bv_.setBit(lock_id));
+    if (!bv_.setBit(lock_id)) {
+      // The lock is already held by this thread, it must be recursive.
+      CHECK_LT(n_recursive_locks, ARRAY_SIZE(recursive_locks));
+      recursive_locks[n_recursive_locks++] = lock_id;
+      return false;
+    }
+    return true;
   }
 
   void removeLock(uptr lock_id) {
     // Printf("remLock: %zx %zx\n", lock_id, current_epoch);
+    if (n_recursive_locks) {
+      for (sptr i = n_recursive_locks - 1; i >= 0; i--) {
+        if (recursive_locks[i] == lock_id) {
+          n_recursive_locks--;
+          Swap(recursive_locks[i], recursive_locks[n_recursive_locks]);
+          return;
+        }
+      }
+    }
     CHECK(bv_.clearBit(lock_id));
   }
 
@@ -71,6 +88,8 @@ class DeadlockDetectorTLS {
  private:
   BV bv_;
   uptr epoch_;
+  uptr recursive_locks[64];
+  uptr n_recursive_locks;
 };
 
 // DeadlockDetector.
@@ -143,8 +162,7 @@ class DeadlockDetector {
     uptr cur_idx = nodeToIndex(cur_node);
     bool is_reachable = g_.isReachable(cur_idx, dtls->getLocks(current_epoch_));
     g_.addEdges(dtls->getLocks(current_epoch_), cur_idx);
-    dtls->addLock(cur_idx, current_epoch_);
-    return is_reachable;
+    return dtls->addLock(cur_idx, current_epoch_) && is_reachable;
   }
 
   // Handles the try_lock event, returns false.
diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_deadlock_detector1.cc b/compiler-rt/lib/sanitizer_common/sanitizer_deadlock_detector1.cc
index 5ecf5e45cbe..adf6bd33678 100644
--- a/compiler-rt/lib/sanitizer_common/sanitizer_deadlock_detector1.cc
+++ b/compiler-rt/lib/sanitizer_common/sanitizer_deadlock_detector1.cc
@@ -106,7 +106,8 @@ void DD::MutexAfterLock(DDCallback *cb, DDMutex *m, bool wlock, bool trylock) {
     return;
   SpinMutexLock lk(&mtx);
   MutexEnsureID(lt, m);
-  CHECK(!dd.isHeld(&lt->dd, m->id));
+  if (wlock)  // Only a recursive rlock may be held.
+    CHECK(!dd.isHeld(&lt->dd, m->id));
   // Printf("T%d MutexLock:   %zx\n", thr->tid, s->deadlock_detector_id);
   bool has_deadlock = trylock
       ? dd.onTryLock(&lt->dd, m->id)
diff --git a/compiler-rt/lib/sanitizer_common/tests/sanitizer_deadlock_detector_test.cc b/compiler-rt/lib/sanitizer_common/tests/sanitizer_deadlock_detector_test.cc
index c6f20731871..b7a925d1fb2 100644
--- a/compiler-rt/lib/sanitizer_common/tests/sanitizer_deadlock_detector_test.cc
+++ b/compiler-rt/lib/sanitizer_common/tests/sanitizer_deadlock_detector_test.cc
@@ -376,3 +376,33 @@ void RunOnFirstLockTest() {
 TEST(DeadlockDetector, onFirstLockTest) {
   RunOnFirstLockTest<BV2>();
 }
+
+template <class BV>
+void RunRecusriveLockTest() {
+  ScopedDD<BV> sdd;
+  DeadlockDetector<BV> &d = *sdd.dp;
+  DeadlockDetectorTLS<BV> &dtls = sdd.dtls;
+
+  uptr l0 = d.newNode(0);
+  uptr l1 = d.newNode(0);
+  uptr l2 = d.newNode(0);
+  uptr l3 = d.newNode(0);
+
+  EXPECT_FALSE(d.onLock(&dtls, l0));
+  EXPECT_FALSE(d.onLock(&dtls, l1));
+  EXPECT_FALSE(d.onLock(&dtls, l0));  // Recurisve.
+  EXPECT_FALSE(d.onLock(&dtls, l2));
+  d.onUnlock(&dtls, l0);
+  EXPECT_FALSE(d.onLock(&dtls, l3));
+  d.onUnlock(&dtls, l0);
+  d.onUnlock(&dtls, l1);
+  d.onUnlock(&dtls, l2);
+  d.onUnlock(&dtls, l3);
+  EXPECT_TRUE(d.testOnlyHasEdge(l0, l1));
+  EXPECT_TRUE(d.testOnlyHasEdge(l0, l2));
+  EXPECT_TRUE(d.testOnlyHasEdge(l0, l3));
+}
+
+TEST(DeadlockDetector, RecusriveLockTest) {
+  RunRecusriveLockTest<BV2>();
+}