summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--lib/sanitizer_common/CMakeLists.txt1
-rw-r--r--lib/sanitizer_common/sanitizer_bitvector.h8
-rw-r--r--lib/sanitizer_common/sanitizer_bvgraph.h6
-rw-r--r--lib/sanitizer_common/sanitizer_deadlock_detector.h158
-rw-r--r--lib/sanitizer_common/tests/CMakeLists.txt1
-rw-r--r--lib/sanitizer_common/tests/sanitizer_deadlock_detector_test.cc103
6 files changed, 274 insertions, 3 deletions
diff --git a/lib/sanitizer_common/CMakeLists.txt b/lib/sanitizer_common/CMakeLists.txt
index 3468bef42..207722804 100644
--- a/lib/sanitizer_common/CMakeLists.txt
+++ b/lib/sanitizer_common/CMakeLists.txt
@@ -51,6 +51,7 @@ set(SANITIZER_HEADERS
sanitizer_common_interceptors_ioctl.inc
sanitizer_common_interceptors_format.inc
sanitizer_common_syscalls.inc
+ sanitizer_deadlock_detector.h
sanitizer_flags.h
sanitizer_internal_defs.h
sanitizer_lfstack.h
diff --git a/lib/sanitizer_common/sanitizer_bitvector.h b/lib/sanitizer_common/sanitizer_bitvector.h
index 5f323ce63..da9082f0b 100644
--- a/lib/sanitizer_common/sanitizer_bitvector.h
+++ b/lib/sanitizer_common/sanitizer_bitvector.h
@@ -26,6 +26,7 @@ class BasicBitVector {
uptr size() const { return kSize; }
// No CTOR.
void clear() { bits_ = 0; }
+ void setAll() { bits_ = ~(basic_int_t)0; }
bool empty() const { return bits_ == 0; }
// Returns true if the bit has changed from 0 to 1.
bool setBit(uptr idx) {
@@ -85,6 +86,13 @@ class TwoLevelBitVector {
for (uptr i = 0; i < kLevel1Size; i++)
l1_[i].clear();
}
+ void setAll() {
+ for (uptr i0 = 0; i0 < kLevel1Size; i0++) {
+ l1_[i0].setAll();
+ for (uptr i1 = 0; i1 < BV::kSize; i1++)
+ l2_[i0][i1].setAll();
+ }
+ }
bool empty() {
for (uptr i = 0; i < kLevel1Size; i++)
if (!l1_[i].empty())
diff --git a/lib/sanitizer_common/sanitizer_bvgraph.h b/lib/sanitizer_common/sanitizer_bvgraph.h
index 7692c9f7a..5673a7a30 100644
--- a/lib/sanitizer_common/sanitizer_bvgraph.h
+++ b/lib/sanitizer_common/sanitizer_bvgraph.h
@@ -44,8 +44,8 @@ class BVGraph {
}
// Returns true if there is a path from the node 'from'
- // to any of the nodes in 'target'.
- bool isReachable(uptr from, const BV &target) {
+ // to any of the nodes in 'targets'.
+ bool isReachable(uptr from, const BV &targets) {
BV to_visit, visited;
to_visit.clear();
to_visit.setUnion(v[from]);
@@ -56,7 +56,7 @@ class BVGraph {
if (visited.setBit(idx))
to_visit.setUnion(v[idx]);
}
- return target.intersectsWith(visited);
+ return targets.intersectsWith(visited);
}
private:
diff --git a/lib/sanitizer_common/sanitizer_deadlock_detector.h b/lib/sanitizer_common/sanitizer_deadlock_detector.h
new file mode 100644
index 000000000..d1da120d8
--- /dev/null
+++ b/lib/sanitizer_common/sanitizer_deadlock_detector.h
@@ -0,0 +1,158 @@
+//===-- sanitizer_deadlock_detector.h ---------------------------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of Sanitizer runtime.
+// The deadlock detector maintains a directed graph of lock acquisitions.
+// When a lock event happens, the detector checks if the locks already held by
+// the current thread are reachable from the newly acquired lock.
+//
+// FIXME: this is work in progress, nothing really works yet.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef SANITIZER_DEADLOCK_DETECTOR_H
+#define SANITIZER_DEADLOCK_DETECTOR_H
+
+#include "sanitizer_common.h"
+#include "sanitizer_bvgraph.h"
+
+namespace __sanitizer {
+
+// Thread-local state for DeadlockDetector.
+// It contains the locks currently held by the owning thread.
+class DeadlockDetectorTLS {
+ public:
+ // No CTOR.
+ void clear() { n_locks_ = 0; }
+ void addLock(uptr node) {
+ CHECK_LT(n_locks_, ARRAY_SIZE(locks_));
+ locks_[n_locks_++] = node;
+ }
+ void removeLock(uptr node) {
+ CHECK_NE(n_locks_, 0U);
+ for (sptr i = n_locks_ - 1; i >= 0; i--) {
+ if (locks_[i] == node) {
+ locks_[i] = locks_[n_locks_ - 1];
+ n_locks_--;
+ return;
+ }
+ }
+ CHECK(0);
+ }
+ uptr numLocks() const { return n_locks_; }
+ uptr getLock(uptr idx) const {
+ CHECK_LT(idx, n_locks_);
+ return locks_[idx];
+ }
+
+ private:
+ uptr n_locks_;
+ uptr locks_[64];
+};
+
+// DeadlockDetector.
+// For deadlock detection to work we need one global DeadlockDetector object
+// and one DeadlockDetectorTLS object per evey thread.
+template <class BV>
+class DeadlockDetector {
+ public:
+ typedef BV BitVector;
+
+ uptr size() const { return g_.size(); }
+ // No CTOR.
+ void clear() {
+ current_epoch_ = 0;
+ available_nodes_.clear();
+ recycled_nodes_.clear();
+ g_.clear();
+ }
+
+ // Allocate new deadlock detector node.
+ // If we are out of available nodes first try to recycle some.
+ // If there is nothing to recycle, flush the graph and increment the epoch.
+ // Associate 'data' (opaque user's object) with the new node.
+ uptr newNode(uptr data) {
+ if (!available_nodes_.empty())
+ return getAvailableNode(data);
+ if (!recycled_nodes_.empty()) {
+ CHECK(available_nodes_.empty());
+ available_nodes_.setUnion(recycled_nodes_);
+ recycled_nodes_.clear();
+ // FIXME: actually recycle nodes in the graph.
+ return getAvailableNode(data);
+ }
+ // We are out of vacant nodes. Flush and increment the current_epoch_.
+ uptr new_epoch = current_epoch_ + BV::kSize;
+ clear();
+ current_epoch_ = new_epoch;
+ available_nodes_.setAll();
+ return getAvailableNode(data);
+ }
+
+ // Get data associated with the node created by newNode().
+ uptr getData(uptr node) const { return data_[nodeToIndex(node)]; }
+
+ void removeNode(uptr node) {
+ uptr idx = nodeToIndex(node);
+ CHECK(!available_nodes_.getBit(idx));
+ CHECK(recycled_nodes_.setBit(idx));
+ // FIXME: also remove from the graph.
+ }
+
+ // Handle the lock event, return true if there is a cycle.
+ // FIXME: handle RW locks, recusive locks, etc.
+ bool onLock(DeadlockDetectorTLS *dtls, uptr cur_node) {
+ BV cur_locks;
+ cur_locks.clear();
+ uptr cur_idx = nodeToIndex(cur_node);
+ for (uptr i = 0, n = dtls->numLocks(); i < n; i++) {
+ uptr prev_node = dtls->getLock(i);
+ uptr prev_idx = nodeToIndex(prev_node);
+ g_.addEdge(prev_idx, cur_idx);
+ cur_locks.setBit(prev_idx);
+ // Printf("OnLock %zx; prev %zx\n", cur_node, dtls->getLock(i));
+ }
+ dtls->addLock(cur_node);
+ return g_.isReachable(cur_idx, cur_locks);
+ }
+
+ // Handle the unlock event.
+ void onUnlock(DeadlockDetectorTLS *dtls, uptr node) {
+ dtls->removeLock(node);
+ }
+
+ private:
+ void check_idx(uptr idx) const { CHECK_LT(idx, size()); }
+ void check_node(uptr node) const {
+ CHECK_GE(node, size());
+ CHECK_EQ(current_epoch_, node / size() * size());
+ }
+ uptr indexToNode(uptr idx) {
+ check_idx(idx);
+ return idx | current_epoch_;
+ }
+ uptr nodeToIndex(uptr node) {
+ check_node(node);
+ return node % size();
+ }
+ uptr getAvailableNode(uptr data) {
+ uptr idx = available_nodes_.getAndClearFirstOne();
+ data_[idx] = data;
+ return indexToNode(idx);
+ }
+ uptr current_epoch_;
+ BV available_nodes_;
+ BV recycled_nodes_;
+ BVGraph<BV> g_;
+ uptr data_[BV::kSize];
+};
+
+} // namespace __sanitizer
+
+#endif // SANITIZER_DEADLOCK_DETECTOR_H
diff --git a/lib/sanitizer_common/tests/CMakeLists.txt b/lib/sanitizer_common/tests/CMakeLists.txt
index 47157221b..906db030b 100644
--- a/lib/sanitizer_common/tests/CMakeLists.txt
+++ b/lib/sanitizer_common/tests/CMakeLists.txt
@@ -6,6 +6,7 @@ set(SANITIZER_UNITTESTS
sanitizer_bitvector_test.cc
sanitizer_bvgraph_test.cc
sanitizer_common_test.cc
+ sanitizer_deadlock_detector_test.cc
sanitizer_flags_test.cc
sanitizer_format_interceptor_test.cc
sanitizer_ioctl_test.cc
diff --git a/lib/sanitizer_common/tests/sanitizer_deadlock_detector_test.cc b/lib/sanitizer_common/tests/sanitizer_deadlock_detector_test.cc
new file mode 100644
index 000000000..fb7c06b0e
--- /dev/null
+++ b/lib/sanitizer_common/tests/sanitizer_deadlock_detector_test.cc
@@ -0,0 +1,103 @@
+//===-- sanitizer_deadlock_detector_test.cc -------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of Sanitizer runtime.
+// Tests for sanitizer_deadlock_detector.h
+//
+//===----------------------------------------------------------------------===//
+#include "sanitizer_common/sanitizer_deadlock_detector.h"
+
+#include "sanitizer_test_utils.h"
+
+#include "gtest/gtest.h"
+
+#include <algorithm>
+#include <vector>
+#include <set>
+
+using namespace __sanitizer;
+using namespace std;
+
+template <class BV>
+void TestDeadlockDetector() {
+ // Can't allocate on stack.
+ DeadlockDetector<BV> *dp = new DeadlockDetector<BV>;
+ DeadlockDetector<BV> &d = *dp;
+ DeadlockDetectorTLS dtls;
+ d.clear();
+ set<uptr> s;
+ for (size_t i = 0; i < d.size() * 3; i++) {
+ uptr node = d.newNode(0);
+ EXPECT_TRUE(s.insert(node).second);
+ }
+
+ d.clear();
+ s.clear();
+ // Add size() nodes.
+ for (size_t i = 0; i < d.size(); i++) {
+ uptr node = d.newNode(0);
+ EXPECT_TRUE(s.insert(node).second);
+ }
+ // Remove all nodes.
+ for (set<uptr>::iterator it = s.begin(); it != s.end(); ++it)
+ d.removeNode(*it);
+ // The nodes should be reused.
+ for (size_t i = 0; i < d.size(); i++) {
+ uptr node = d.newNode(0);
+ EXPECT_FALSE(s.insert(node).second);
+ }
+
+ // Cycle: n1->n2->n1
+ {
+ d.clear();
+ dtls.clear();
+ uptr n1 = d.newNode(1);
+ uptr n2 = d.newNode(2);
+ EXPECT_FALSE(d.onLock(&dtls, n1));
+ EXPECT_FALSE(d.onLock(&dtls, n2));
+ d.onUnlock(&dtls, n2);
+ d.onUnlock(&dtls, n1);
+
+ EXPECT_FALSE(d.onLock(&dtls, n2));
+ EXPECT_TRUE(d.onLock(&dtls, n1));
+ d.onUnlock(&dtls, n1);
+ d.onUnlock(&dtls, n2);
+ }
+
+ // Cycle: n1->n2->n3->n1
+ {
+ d.clear();
+ dtls.clear();
+ uptr n1 = d.newNode(1);
+ uptr n2 = d.newNode(2);
+ uptr n3 = d.newNode(3);
+
+ EXPECT_FALSE(d.onLock(&dtls, n1));
+ EXPECT_FALSE(d.onLock(&dtls, n2));
+ d.onUnlock(&dtls, n2);
+ d.onUnlock(&dtls, n1);
+
+ EXPECT_FALSE(d.onLock(&dtls, n2));
+ EXPECT_FALSE(d.onLock(&dtls, n3));
+ d.onUnlock(&dtls, n3);
+ d.onUnlock(&dtls, n2);
+
+ EXPECT_FALSE(d.onLock(&dtls, n3));
+ EXPECT_TRUE(d.onLock(&dtls, n1));
+ d.onUnlock(&dtls, n1);
+ d.onUnlock(&dtls, n3);
+ }
+
+ delete dp;
+}
+
+TEST(SanitizerCommon, DeadlockDetector) {
+ TestDeadlockDetector<BasicBitVector<> >();
+ TestDeadlockDetector<TwoLevelBitVector<2> >();
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-03 15:35:09 +0000