12d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines//===-- sanitizer_deadlock_detector_test.cc -------------------------------===// 22d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 32d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// The LLVM Compiler Infrastructure 42d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 52d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// This file is distributed under the University of Illinois Open Source 62d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// License. See LICENSE.TXT for details. 72d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 82d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines//===----------------------------------------------------------------------===// 92d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// This file is a part of Sanitizer runtime. 112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// Tests for sanitizer_deadlock_detector.h 122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines//===----------------------------------------------------------------------===// 142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include "sanitizer_common/sanitizer_deadlock_detector.h" 152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include "sanitizer_test_utils.h" 172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include "gtest/gtest.h" 192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include <algorithm> 212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include <vector> 222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include <set> 232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesusing namespace __sanitizer; 252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesusing namespace std; 262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestypedef BasicBitVector<u8> BV1; 282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestypedef BasicBitVector<> BV2; 292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestypedef TwoLevelBitVector<> BV3; 302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestypedef TwoLevelBitVector<3, BasicBitVector<u8> > BV4; 312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// Poor man's unique_ptr. 332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate<class BV> 342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesstruct ScopedDD { 352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ScopedDD() { 362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dp = new DeadlockDetector<BV>; 372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dp->clear(); 382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dtls.clear(); 392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ~ScopedDD() { delete dp; } 412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines DeadlockDetector<BV> *dp; 422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines DeadlockDetectorTLS<BV> dtls; 432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines}; 442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate <class BV> 462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesvoid RunBasicTest() { 472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr path[10]; 482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ScopedDD<BV> sdd; 492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines DeadlockDetector<BV> &d = *sdd.dp; 502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines DeadlockDetectorTLS<BV> &dtls = sdd.dtls; 512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines set<uptr> s; 522d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (size_t i = 0; i < d.size() * 3; i++) { 532d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr node = d.newNode(0); 542d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(s.insert(node).second); 552d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 562d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 572d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.clear(); 582d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines s.clear(); 592d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Add size() nodes. 602d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (size_t i = 0; i < d.size(); i++) { 612d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr node = d.newNode(0); 622d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(s.insert(node).second); 632d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 642d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Remove all nodes. 652d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (set<uptr>::iterator it = s.begin(); it != s.end(); ++it) 662d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.removeNode(*it); 672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // The nodes should be reused. 682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (size_t i = 0; i < d.size(); i++) { 692d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr node = d.newNode(0); 702d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(s.insert(node).second); 712d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 722d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 732d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Cycle: n1->n2->n1 742d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines { 752d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.clear(); 762d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dtls.clear(); 772d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr n1 = d.newNode(1); 782d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr n2 = d.newNode(2); 792d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onLock(&dtls, n1)); 802d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onLock(&dtls, n2)); 812d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, n2); 822d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, n1); 832d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 842d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onLock(&dtls, n2)); 852d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(0U, d.findPathToLock(&dtls, n1, path, 1)); 862d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(2U, d.findPathToLock(&dtls, n1, path, 10)); 872d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(2U, d.findPathToLock(&dtls, n1, path, 2)); 882d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(d.onLock(&dtls, n1)); 892d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(path[0], n1); 902d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(path[1], n2); 912d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(d.getData(n1), 1U); 922d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(d.getData(n2), 2U); 932d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, n1); 942d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, n2); 952d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 962d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 972d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Cycle: n1->n2->n3->n1 982d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines { 992d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.clear(); 1002d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines dtls.clear(); 1012d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr n1 = d.newNode(1); 1022d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr n2 = d.newNode(2); 1032d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr n3 = d.newNode(3); 1042d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1052d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onLock(&dtls, n1)); 1062d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onLock(&dtls, n2)); 1072d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, n2); 1082d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, n1); 1092d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onLock(&dtls, n2)); 1112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onLock(&dtls, n3)); 1122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, n3); 1132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, n2); 1142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onLock(&dtls, n3)); 1162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(0U, d.findPathToLock(&dtls, n1, path, 2)); 1172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(3U, d.findPathToLock(&dtls, n1, path, 10)); 1182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(d.onLock(&dtls, n1)); 1192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(path[0], n1); 1202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(path[1], n2); 1212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(path[2], n3); 1222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(d.getData(n1), 1U); 1232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(d.getData(n2), 2U); 1242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(d.getData(n3), 3U); 1252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, n1); 1262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, n3); 1272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 1292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesTEST(DeadlockDetector, BasicTest) { 1312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines RunBasicTest<BV1>(); 1322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines RunBasicTest<BV2>(); 1332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines RunBasicTest<BV3>(); 1342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines RunBasicTest<BV4>(); 1352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 1362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate <class BV> 1382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesvoid RunRemoveNodeTest() { 1392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ScopedDD<BV> sdd; 1402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines DeadlockDetector<BV> &d = *sdd.dp; 1412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines DeadlockDetectorTLS<BV> &dtls = sdd.dtls; 1422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr l0 = d.newNode(0); 1442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr l1 = d.newNode(1); 1452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr l2 = d.newNode(2); 1462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr l3 = d.newNode(3); 1472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr l4 = d.newNode(4); 1482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr l5 = d.newNode(5); 1492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // l0=>l1=>l2 1512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onLock(&dtls, l0); 1522d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onLock(&dtls, l1); 1532d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onLock(&dtls, l2); 1542d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, l1); 1552d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, l0); 1562d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, l2); 1572d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // l3=>l4=>l5 1582d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onLock(&dtls, l3); 1592d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onLock(&dtls, l4); 1602d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onLock(&dtls, l5); 1612d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, l4); 1622d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, l3); 1632d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, l5); 1642d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1652d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines set<uptr> locks; 1662d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines locks.insert(l0); 1672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines locks.insert(l1); 1682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines locks.insert(l2); 1692d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines locks.insert(l3); 1702d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines locks.insert(l4); 1712d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines locks.insert(l5); 1722d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 6; i < d.size(); i++) { 1732d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr lt = d.newNode(i); 1742d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines locks.insert(lt); 1752d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onLock(&dtls, lt); 1762d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, lt); 1772d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.removeNode(lt); 1782d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1792d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(locks.size(), d.size()); 1802d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // l2=>l0 1812d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onLock(&dtls, l2)); 1822d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(d.onLock(&dtls, l0)); 1832d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, l2); 1842d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, l0); 1852d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // l4=>l3 1862d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onLock(&dtls, l4)); 1872d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(d.onLock(&dtls, l3)); 1882d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, l4); 1892d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, l3); 1902d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1912d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(d.size(), d.testOnlyGetEpoch()); 1922d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1932d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.removeNode(l2); 1942d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.removeNode(l3); 1952d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines locks.clear(); 1962d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // make sure no edges from or to l0,l1,l4,l5 left. 1972d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 4; i < d.size(); i++) { 1982d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr lt = d.newNode(i); 1992d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines locks.insert(lt); 2002d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr a, b; 2012d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // l0 => lt? 2022d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines a = l0; b = lt; 2032d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onLock(&dtls, a)); 2042d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onLock(&dtls, b)); 2052d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, a); 2062d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, b); 2072d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // l1 => lt? 2082d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines a = l1; b = lt; 2092d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onLock(&dtls, a)); 2102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onLock(&dtls, b)); 2112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, a); 2122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, b); 2132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // lt => l4? 2142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines a = lt; b = l4; 2152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onLock(&dtls, a)); 2162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onLock(&dtls, b)); 2172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, a); 2182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, b); 2192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // lt => l5? 2202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines a = lt; b = l5; 2212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onLock(&dtls, a)); 2222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onLock(&dtls, b)); 2232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, a); 2242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, b); 2252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.removeNode(lt); 2272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Still the same epoch. 2292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(d.size(), d.testOnlyGetEpoch()); 2302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(locks.size(), d.size() - 4); 2312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // l2 and l3 should have ben reused. 2322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(locks.count(l2), 1U); 2332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(locks.count(l3), 1U); 2342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 2352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesTEST(DeadlockDetector, RemoveNodeTest) { 2372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines RunRemoveNodeTest<BV1>(); 2382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines RunRemoveNodeTest<BV2>(); 2392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines RunRemoveNodeTest<BV3>(); 2402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines RunRemoveNodeTest<BV4>(); 2412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 2422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate <class BV> 2442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesvoid RunMultipleEpochsTest() { 2452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ScopedDD<BV> sdd; 2462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines DeadlockDetector<BV> &d = *sdd.dp; 2472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines DeadlockDetectorTLS<BV> &dtls = sdd.dtls; 2482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines set<uptr> locks; 2502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < d.size(); i++) { 2512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(locks.insert(d.newNode(i)).second); 2522d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2532d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(d.testOnlyGetEpoch(), d.size()); 2542d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < d.size(); i++) { 2552d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(locks.insert(d.newNode(i)).second); 2562d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(d.testOnlyGetEpoch(), d.size() * 2); 2572d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2582d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines locks.clear(); 2592d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2602d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr l0 = d.newNode(0); 2612d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr l1 = d.newNode(0); 2622d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onLock(&dtls, l0); 2632d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onLock(&dtls, l1); 2642d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, l0); 2652d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(d.testOnlyGetEpoch(), 3 * d.size()); 2662d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < d.size(); i++) { 2672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(locks.insert(d.newNode(i)).second); 2682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2692d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(d.testOnlyGetEpoch(), 4 * d.size()); 2702d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2715d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines#if TSAN_DEBUG == 0 2725d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines // EXPECT_DEATH clones a thread with 4K stack, 2735d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines // which is overflown by tsan memory accesses functions in debug mode. 2745d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines 2752d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Can not handle the locks from the previous epoch. 2762d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // The caller should update the lock id. 2772d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_DEATH(d.onLock(&dtls, l0), "CHECK failed.*current_epoch_"); 2785d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines#endif 2792d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 2802d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2812d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesTEST(DeadlockDetector, MultipleEpochsTest) { 2822d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines RunMultipleEpochsTest<BV1>(); 2832d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines RunMultipleEpochsTest<BV2>(); 2842d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines RunMultipleEpochsTest<BV3>(); 2852d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines RunMultipleEpochsTest<BV4>(); 2862d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 2872d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2882d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate <class BV> 2892d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesvoid RunCorrectEpochFlush() { 2902d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ScopedDD<BV> sdd; 2912d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines DeadlockDetector<BV> &d = *sdd.dp; 2922d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines DeadlockDetectorTLS<BV> &dtls = sdd.dtls; 2932d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines vector<uptr> locks1; 2942d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < d.size(); i++) 2952d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines locks1.push_back(d.newNode(i)); 2962d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(d.testOnlyGetEpoch(), d.size()); 2972d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onLock(&dtls, locks1[3]); 2982d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onLock(&dtls, locks1[4]); 2992d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onLock(&dtls, locks1[5]); 3002d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3012d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // We have a new epoch, old locks in dtls will have to be forgotten. 3022d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr l0 = d.newNode(0); 3032d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(d.testOnlyGetEpoch(), d.size() * 2); 3042d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr l1 = d.newNode(0); 3052d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(d.testOnlyGetEpoch(), d.size() * 2); 3062d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onLock(&dtls, l0); 3072d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onLock(&dtls, l1); 3082d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(d.testOnlyHasEdgeRaw(0, 1)); 3092d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.testOnlyHasEdgeRaw(1, 0)); 3102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.testOnlyHasEdgeRaw(3, 0)); 3112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.testOnlyHasEdgeRaw(4, 0)); 3122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.testOnlyHasEdgeRaw(5, 0)); 3132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 3142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesTEST(DeadlockDetector, CorrectEpochFlush) { 3162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines RunCorrectEpochFlush<BV1>(); 3172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines RunCorrectEpochFlush<BV2>(); 3182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 3192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate <class BV> 3212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesvoid RunTryLockTest() { 3222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ScopedDD<BV> sdd; 3232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines DeadlockDetector<BV> &d = *sdd.dp; 3242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines DeadlockDetectorTLS<BV> &dtls = sdd.dtls; 3252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr l0 = d.newNode(0); 3272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr l1 = d.newNode(0); 3282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr l2 = d.newNode(0); 3292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onLock(&dtls, l0)); 3302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onTryLock(&dtls, l1)); 3312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onLock(&dtls, l2)); 3322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(d.isHeld(&dtls, l0)); 3332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(d.isHeld(&dtls, l1)); 3342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(d.isHeld(&dtls, l2)); 3352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.testOnlyHasEdge(l0, l1)); 3362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(d.testOnlyHasEdge(l1, l2)); 3372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, l0); 3382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, l1); 3392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, l2); 3402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 3412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesTEST(DeadlockDetector, TryLockTest) { 3432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines RunTryLockTest<BV1>(); 3442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines RunTryLockTest<BV2>(); 3452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 3462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate <class BV> 3482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesvoid RunOnFirstLockTest() { 3492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ScopedDD<BV> sdd; 3502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines DeadlockDetector<BV> &d = *sdd.dp; 3512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines DeadlockDetectorTLS<BV> &dtls = sdd.dtls; 3522d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3532d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr l0 = d.newNode(0); 3542d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr l1 = d.newNode(0); 3552d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onFirstLock(&dtls, l0)); // dtls has old epoch. 3562d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onLock(&dtls, l0); 3572d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, l0); 3582d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3592d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(d.onFirstLock(&dtls, l0)); // Ok, same ecpoch, first lock. 3602d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onFirstLock(&dtls, l1)); // Second lock. 3612d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onLock(&dtls, l1); 3622d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, l1); 3632d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, l0); 3642d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3652d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(d.onFirstLock(&dtls, l0)); // Ok 3662d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, l0); 3672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines vector<uptr> locks1; 3692d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < d.size(); i++) 3702d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines locks1.push_back(d.newNode(i)); 3712d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3722d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(d.onFirstLock(&dtls, l0)); // Epoch has changed, but not in dtls. 3732d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3742d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr l3 = d.newNode(0); 3752d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onLock(&dtls, l3); 3762d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, l3); 3772d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3782d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onFirstLock(&dtls, l0)); // Epoch has changed in dtls. 3792d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 3802d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3812d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesTEST(DeadlockDetector, onFirstLockTest) { 3822d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines RunOnFirstLockTest<BV2>(); 3832d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 3842d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3852d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate <class BV> 3862d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesvoid RunRecusriveLockTest() { 3872d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ScopedDD<BV> sdd; 3882d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines DeadlockDetector<BV> &d = *sdd.dp; 3892d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines DeadlockDetectorTLS<BV> &dtls = sdd.dtls; 3902d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3912d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr l0 = d.newNode(0); 3922d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr l1 = d.newNode(0); 3932d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr l2 = d.newNode(0); 3942d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr l3 = d.newNode(0); 3952d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3962d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onLock(&dtls, l0)); 3972d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onLock(&dtls, l1)); 3982d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onLock(&dtls, l0)); // Recurisve. 3992d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onLock(&dtls, l2)); 4002d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, l0); 4012d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onLock(&dtls, l3)); 4022d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, l0); 4032d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, l1); 4042d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, l2); 4052d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, l3); 4062d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(d.testOnlyHasEdge(l0, l1)); 4072d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(d.testOnlyHasEdge(l0, l2)); 4082d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(d.testOnlyHasEdge(l0, l3)); 4092d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 4102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 4112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesTEST(DeadlockDetector, RecusriveLockTest) { 4122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines RunRecusriveLockTest<BV2>(); 4132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 4142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 4152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate <class BV> 4162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesvoid RunLockContextTest() { 4172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ScopedDD<BV> sdd; 4182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines DeadlockDetector<BV> &d = *sdd.dp; 4192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines DeadlockDetectorTLS<BV> &dtls = sdd.dtls; 4202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 4212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr l0 = d.newNode(0); 4222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr l1 = d.newNode(0); 4232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr l2 = d.newNode(0); 4242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr l3 = d.newNode(0); 4252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr l4 = d.newNode(0); 4262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onLock(&dtls, l0, 10)); 4272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onLock(&dtls, l1, 11)); 4282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onLock(&dtls, l2, 12)); 4292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onLock(&dtls, l3, 13)); 4302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(10U, d.findLockContext(&dtls, l0)); 4312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(11U, d.findLockContext(&dtls, l1)); 4322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(12U, d.findLockContext(&dtls, l2)); 4332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(13U, d.findLockContext(&dtls, l3)); 4342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, l0); 4352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(0U, d.findLockContext(&dtls, l0)); 4362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(11U, d.findLockContext(&dtls, l1)); 4372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(12U, d.findLockContext(&dtls, l2)); 4382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(13U, d.findLockContext(&dtls, l3)); 4392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.onUnlock(&dtls, l2); 4402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(0U, d.findLockContext(&dtls, l0)); 4412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(11U, d.findLockContext(&dtls, l1)); 4422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(0U, d.findLockContext(&dtls, l2)); 4432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(13U, d.findLockContext(&dtls, l3)); 4442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 4452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onLock(&dtls, l4, 14)); 4462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(14U, d.findLockContext(&dtls, l4)); 4472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 4482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 4492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesTEST(DeadlockDetector, LockContextTest) { 4502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines RunLockContextTest<BV2>(); 4512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 4522d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 4532d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate <class BV> 4542d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesvoid RunRemoveEdgesTest() { 4552d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ScopedDD<BV> sdd; 4562d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines DeadlockDetector<BV> &d = *sdd.dp; 4572d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines DeadlockDetectorTLS<BV> &dtls = sdd.dtls; 4582d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines vector<uptr> node(BV::kSize); 4592d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines u32 stk_from = 0, stk_to = 0; 4602d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines int unique_tid = 0; 4612d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (size_t i = 0; i < BV::kSize; i++) 4622d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines node[i] = d.newNode(0); 4632d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 4642d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (size_t i = 0; i < BV::kSize; i++) 4652d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(d.onLock(&dtls, node[i], i + 1)); 4662d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (size_t i = 0; i < BV::kSize; i++) { 4672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr j = i + 1; j < BV::kSize; j++) { 4682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE( 4692d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.findEdge(node[i], node[j], &stk_from, &stk_to, &unique_tid)); 4702d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(stk_from, i + 1); 4712d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(stk_to, j + 1); 4722d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 4732d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 4742d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(d.testOnlyGetEpoch(), d.size()); 4752d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Remove and re-create half of the nodes. 4762d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 1; i < BV::kSize; i += 2) 4772d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.removeNode(node[i]); 4782d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 1; i < BV::kSize; i += 2) 4792d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines node[i] = d.newNode(0); 4802d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(d.testOnlyGetEpoch(), d.size()); 4812d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // The edges from or to the removed nodes should be gone. 4822d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (size_t i = 0; i < BV::kSize; i++) { 4832d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr j = i + 1; j < BV::kSize; j++) { 4842d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if ((i % 2) || (j % 2)) 4852d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE( 4862d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.findEdge(node[i], node[j], &stk_from, &stk_to, &unique_tid)); 4872d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines else 4882d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE( 4892d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines d.findEdge(node[i], node[j], &stk_from, &stk_to, &unique_tid)); 4902d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 4912d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 4922d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 4932d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 4942d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesTEST(DeadlockDetector, RemoveEdgesTest) { 4952d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines RunRemoveEdgesTest<BV1>(); 4962d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 497