//===-- sanitizer_deadlock_detector_test.cpp ------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// 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;
typedef BasicBitVector<u8> BV1;
typedef BasicBitVector<> BV2;
typedef TwoLevelBitVector<> BV3;
typedef TwoLevelBitVector<3, BasicBitVector<u8> > BV4;
// Poor man's unique_ptr.
template<class BV>
struct ScopedDD {
ScopedDD() {
dp = new DeadlockDetector<BV>;
dp->clear();
dtls.clear();
}
~ScopedDD() { delete dp; }
DeadlockDetector<BV> *dp;
DeadlockDetectorTLS<BV> dtls;
};
template <class BV>
void RunBasicTest() {
uptr path[10];
ScopedDD<BV> sdd;
DeadlockDetector<BV> &d = *sdd.dp;
DeadlockDetectorTLS<BV> &dtls = sdd.dtls;
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_EQ(0U, d.findPathToLock(&dtls, n1, path, 1));
EXPECT_EQ(2U, d.findPathToLock(&dtls, n1, path, 10));
EXPECT_EQ(2U, d.findPathToLock(&dtls, n1, path, 2));
EXPECT_TRUE(d.onLock(&dtls, n1));
EXPECT_EQ(path[0], n1);
EXPECT_EQ(path[1], n2);
EXPECT_EQ(d.getData(n1), 1U);
EXPECT_EQ(d.getData(n2), 2U);
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_EQ(0U, d.findPathToLock(&dtls, n1, path, 2));
EXPECT_EQ(3U, d.findPathToLock(&dtls, n1, path, 10));
EXPECT_TRUE(d.onLock(&dtls, n1));
EXPECT_EQ(path[0], n1);
EXPECT_EQ(path[1], n2);
EXPECT_EQ(path[2], n3);
EXPECT_EQ(d.getData(n1), 1U);
EXPECT_EQ(d.getData(n2), 2U);
EXPECT_EQ(d.getData(n3), 3U);
d.onUnlock(&dtls, n1);
d.onUnlock(&dtls, n3);
}
}
TEST(DeadlockDetector, BasicTest) {
RunBasicTest<BV1>();
RunBasicTest<BV2>();
RunBasicTest<BV3>();
RunBasicTest<BV4>();
}
template <class BV>
void RunRemoveNodeTest() {
ScopedDD<BV> sdd;
DeadlockDetector<BV> &d = *sdd.dp;
DeadlockDetectorTLS<BV> &dtls = sdd.dtls;
uptr l0 = d.newNode(0);
uptr l1 = d.newNode(1);
uptr l2 = d.newNode(2);
uptr l3 = d.newNode(3);
uptr l4 = d.newNode(4);
uptr l5 = d.newNode(5);
// l0=>l1=>l2
d.onLock(&dtls, l0);
d.onLock(&dtls, l1);
d.onLock(&dtls, l2);
d.onUnlock(&dtls, l1);
d.onUnlock(&dtls, l0);
d.onUnlock(&dtls, l2);
// l3=>l4=>l5
d.onLock(&dtls, l3);
d.onLock(&dtls, l4);
d.onLock(&dtls, l5);
d.onUnlock(&dtls, l4);
d.onUnlock(&dtls, l3);
d.onUnlock(&dtls, l5);
set<uptr> locks;
locks.insert(l0);
locks.insert(l1);
locks.insert(l2);
locks.insert(l3);
locks.insert(l4);
locks.insert(l5);
for (uptr i = 6; i < d.size(); i++) {
uptr lt = d.newNode(i);
locks.insert(lt);
d.onLock(&dtls, lt);
d.onUnlock(&dtls, lt);
d.removeNode(lt);
}
EXPECT_EQ(locks.size(), d.size());
// l2=>l0
EXPECT_FALSE(d.onLock(&dtls, l2));
EXPECT_TRUE(d.onLock(&dtls, l0));
d.onUnlock(&dtls, l2);
d.onUnlock(&dtls, l0);
// l4=>l3
EXPECT_FALSE(d.onLock(&dtls, l4));
EXPECT_TRUE(d.onLock(&dtls, l3));
d.onUnlock(&dtls, l4);
d.onUnlock(&dtls, l3);
EXPECT_EQ(d.size(), d.testOnlyGetEpoch());
d.removeNode(l2);
d.removeNode(l3);
locks.clear();
// make sure no edges from or to l0,l1,l4,l5 left.
for (uptr i = 4; i < d.size(); i++) {
uptr lt = d.newNode(i);
locks.insert(lt);
uptr a, b;
// l0 => lt?
a = l0; b = lt;
EXPECT_FALSE(d.onLock(&dtls, a));
EXPECT_FALSE(d.onLock(&dtls, b));
d.onUnlock(&dtls, a);
d.onUnlock(&dtls, b);
// l1 => lt?
a = l1; b = lt;
EXPECT_FALSE(d.onLock(&dtls, a));
EXPECT_FALSE(d.onLock(&dtls, b));
d.onUnlock(&dtls, a);
d.onUnlock(&dtls, b);
// lt => l4?
a = lt; b = l4;
EXPECT_FALSE(d.onLock(&dtls, a));
EXPECT_FALSE(d.onLock(&dtls, b));
d.onUnlock(&dtls, a);
d.onUnlock(&dtls, b);
// lt => l5?
a = lt; b = l5;
EXPECT_FALSE(d.onLock(&dtls, a));
EXPECT_FALSE(d.onLock(&dtls, b));
d.onUnlock(&dtls, a);
d.onUnlock(&dtls, b);
d.removeNode(lt);
}
// Still the same epoch.
EXPECT_EQ(d.size(), d.testOnlyGetEpoch());
EXPECT_EQ(locks.size(), d.size() - 4);
// l2 and l3 should have ben reused.
EXPECT_EQ(locks.count(l2), 1U);
EXPECT_EQ(locks.count(l3), 1U);
}
TEST(DeadlockDetector, RemoveNodeTest) {
RunRemoveNodeTest<BV1>();
RunRemoveNodeTest<BV2>();
RunRemoveNodeTest<BV3>();
RunRemoveNodeTest<BV4>();
}
template <class BV>
void RunMultipleEpochsTest() {
ScopedDD<BV> sdd;
DeadlockDetector<BV> &d = *sdd.dp;
DeadlockDetectorTLS<BV> &dtls = sdd.dtls;
set<uptr> locks;
for (uptr i = 0; i < d.size(); i++) {
EXPECT_TRUE(locks.insert(d.newNode(i)).second);
}
EXPECT_EQ(d.testOnlyGetEpoch(), d.size());
for (uptr i = 0; i < d.size(); i++) {
EXPECT_TRUE(locks.insert(d.newNode(i)).second);
EXPECT_EQ(d.testOnlyGetEpoch(), d.size() * 2);
}
locks.clear();
uptr l0 = d.newNode(0);
uptr l1 = d.newNode(0);
d.onLock(&dtls, l0);
d.onLock(&dtls, l1);
d.onUnlock(&dtls, l0);
EXPECT_EQ(d.testOnlyGetEpoch(), 3 * d.size());
for (uptr i = 0; i < d.size(); i++) {
EXPECT_TRUE(locks.insert(d.newNode(i)).second);
}
EXPECT_EQ(d.testOnlyGetEpoch(), 4 * d.size());
#if !SANITIZER_DEBUG
// EXPECT_DEATH clones a thread with 4K stack,
// which is overflown by tsan memory accesses functions in debug mode.
// Can not handle the locks from the previous epoch.
// The caller should update the lock id.
EXPECT_DEATH(d.onLock(&dtls, l0), "CHECK failed.*current_epoch_");
#endif
}
TEST(DeadlockDetector, MultipleEpochsTest) {
RunMultipleEpochsTest<BV1>();
RunMultipleEpochsTest<BV2>();
RunMultipleEpochsTest<BV3>();
RunMultipleEpochsTest<BV4>();
}
template <class BV>
void RunCorrectEpochFlush() {
ScopedDD<BV> sdd;
DeadlockDetector<BV> &d = *sdd.dp;
DeadlockDetectorTLS<BV> &dtls = sdd.dtls;
vector<uptr> locks1;
for (uptr i = 0; i < d.size(); i++)
locks1.push_back(d.newNode(i));
EXPECT_EQ(d.testOnlyGetEpoch(), d.size());
d.onLock(&dtls, locks1[3]);
d.onLock(&dtls, locks1[4]);
d.onLock(&dtls, locks1[5]);
// We have a new epoch, old locks in dtls will have to be forgotten.
uptr l0 = d.newNode(0);
EXPECT_EQ(d.testOnlyGetEpoch(), d.size() * 2);
uptr l1 = d.newNode(0);
EXPECT_EQ(d.testOnlyGetEpoch(), d.size() * 2);
d.onLock(&dtls, l0);
d.onLock(&dtls, l1);
EXPECT_TRUE(d.testOnlyHasEdgeRaw(0, 1));
EXPECT_FALSE(d.testOnlyHasEdgeRaw(1, 0));
EXPECT_FALSE(d.testOnlyHasEdgeRaw(3, 0));
EXPECT_FALSE(d.testOnlyHasEdgeRaw(4, 0));
EXPECT_FALSE(d.testOnlyHasEdgeRaw(5, 0));
}
TEST(DeadlockDetector, CorrectEpochFlush) {
RunCorrectEpochFlush<BV1>();
RunCorrectEpochFlush<BV2>();
}
template <class BV>
void RunTryLockTest() {
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);
EXPECT_FALSE(d.onLock(&dtls, l0));
EXPECT_FALSE(d.onTryLock(&dtls, l1));
EXPECT_FALSE(d.onLock(&dtls, l2));
EXPECT_TRUE(d.isHeld(&dtls, l0));
EXPECT_TRUE(d.isHeld(&dtls, l1));
EXPECT_TRUE(d.isHeld(&dtls, l2));
EXPECT_FALSE(d.testOnlyHasEdge(l0, l1));
EXPECT_TRUE(d.testOnlyHasEdge(l1, l2));
d.onUnlock(&dtls, l0);
d.onUnlock(&dtls, l1);
d.onUnlock(&dtls, l2);
}
TEST(DeadlockDetector, TryLockTest) {
RunTryLockTest<BV1>();
RunTryLockTest<BV2>();
}
template <class BV>
void RunOnFirstLockTest() {
ScopedDD<BV> sdd;
DeadlockDetector<BV> &d = *sdd.dp;
DeadlockDetectorTLS<BV> &dtls = sdd.dtls;
uptr l0 = d.newNode(0);
uptr l1 = d.newNode(0);
EXPECT_FALSE(d.onFirstLock(&dtls, l0)); // dtls has old epoch.
d.onLock(&dtls, l0);
d.onUnlock(&dtls, l0);
EXPECT_TRUE(d.onFirstLock(&dtls, l0)); // Ok, same ecpoch, first lock.
EXPECT_FALSE(d.onFirstLock(&dtls, l1)); // Second lock.
d.onLock(&dtls, l1);
d.onUnlock(&dtls, l1);
d.onUnlock(&dtls, l0);
EXPECT_TRUE(d.onFirstLock(&dtls, l0)); // Ok
d.onUnlock(&dtls, l0);
vector<uptr> locks1;
for (uptr i = 0; i < d.size(); i++)
locks1.push_back(d.newNode(i));
EXPECT_TRUE(d.onFirstLock(&dtls, l0)); // Epoch has changed, but not in dtls.
uptr l3 = d.newNode(0);
d.onLock(&dtls, l3);
d.onUnlock(&dtls, l3);
EXPECT_FALSE(d.onFirstLock(&dtls, l0)); // Epoch has changed in dtls.
}
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>();
}
template <class BV>
void RunLockContextTest() {
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);
uptr l4 = d.newNode(0);
EXPECT_FALSE(d.onLock(&dtls, l0, 10));
EXPECT_FALSE(d.onLock(&dtls, l1, 11));
EXPECT_FALSE(d.onLock(&dtls, l2, 12));
EXPECT_FALSE(d.onLock(&dtls, l3, 13));
EXPECT_EQ(10U, d.findLockContext(&dtls, l0));
EXPECT_EQ(11U, d.findLockContext(&dtls, l1));
EXPECT_EQ(12U, d.findLockContext(&dtls, l2));
EXPECT_EQ(13U, d.findLockContext(&dtls, l3));
d.onUnlock(&dtls, l0);
EXPECT_EQ(0U, d.findLockContext(&dtls, l0));
EXPECT_EQ(11U, d.findLockContext(&dtls, l1));
EXPECT_EQ(12U, d.findLockContext(&dtls, l2));
EXPECT_EQ(13U, d.findLockContext(&dtls, l3));
d.onUnlock(&dtls, l2);
EXPECT_EQ(0U, d.findLockContext(&dtls, l0));
EXPECT_EQ(11U, d.findLockContext(&dtls, l1));
EXPECT_EQ(0U, d.findLockContext(&dtls, l2));
EXPECT_EQ(13U, d.findLockContext(&dtls, l3));
EXPECT_FALSE(d.onLock(&dtls, l4, 14));
EXPECT_EQ(14U, d.findLockContext(&dtls, l4));
}
TEST(DeadlockDetector, LockContextTest) {
RunLockContextTest<BV2>();
}
template <class BV>
void RunRemoveEdgesTest() {
ScopedDD<BV> sdd;
DeadlockDetector<BV> &d = *sdd.dp;
DeadlockDetectorTLS<BV> &dtls = sdd.dtls;
vector<uptr> node(BV::kSize);
u32 stk_from = 0, stk_to = 0;
int unique_tid = 0;
for (size_t i = 0; i < BV::kSize; i++)
node[i] = d.newNode(0);
for (size_t i = 0; i < BV::kSize; i++)
EXPECT_FALSE(d.onLock(&dtls, node[i], i + 1));
for (size_t i = 0; i < BV::kSize; i++) {
for (uptr j = i + 1; j < BV::kSize; j++) {
EXPECT_TRUE(
d.findEdge(node[i], node[j], &stk_from, &stk_to, &unique_tid));
EXPECT_EQ(stk_from, i + 1);
EXPECT_EQ(stk_to, j + 1);
}
}
EXPECT_EQ(d.testOnlyGetEpoch(), d.size());
// Remove and re-create half of the nodes.
for (uptr i = 1; i < BV::kSize; i += 2)
d.removeNode(node[i]);
for (uptr i = 1; i < BV::kSize; i += 2)
node[i] = d.newNode(0);
EXPECT_EQ(d.testOnlyGetEpoch(), d.size());
// The edges from or to the removed nodes should be gone.
for (size_t i = 0; i < BV::kSize; i++) {
for (uptr j = i + 1; j < BV::kSize; j++) {
if ((i % 2) || (j % 2))
EXPECT_FALSE(
d.findEdge(node[i], node[j], &stk_from, &stk_to, &unique_tid));
else
EXPECT_TRUE(
d.findEdge(node[i], node[j], &stk_from, &stk_to, &unique_tid));
}
}
}
TEST(DeadlockDetector, RemoveEdgesTest) {
RunRemoveEdgesTest<BV1>();
}
Codebase Browser
llvm