Home | History | Annotate | Download | only in tests 
      1 //===-- sanitizer_deadlock_detector_test.cc -------------------------------===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // This file is a part of Sanitizer runtime.
     11 // Tests for sanitizer_deadlock_detector.h
     12 //
     13 //===----------------------------------------------------------------------===//
     14 #include "sanitizer_common/sanitizer_deadlock_detector.h"
     15 
     16 #include "sanitizer_test_utils.h"
     17 
     18 #include "gtest/gtest.h"
     19 
     20 #include <algorithm>
     21 #include <vector>
     22 #include <set>
     23 
     24 using namespace __sanitizer;
     25 using namespace std;
     26 
     27 typedef BasicBitVector<u8> BV1;
     28 typedef BasicBitVector<> BV2;
     29 typedef TwoLevelBitVector<> BV3;
     30 typedef TwoLevelBitVector<3, BasicBitVector<u8> > BV4;
     31 
     32 // Poor man's unique_ptr.
     33 template<class BV>
     34 struct ScopedDD {
     35   ScopedDD() {
     36     dp = new DeadlockDetector<BV>;
     37     dp->clear();
     38     dtls.clear();
     39   }
     40   ~ScopedDD() { delete dp; }
     41   DeadlockDetector<BV> *dp;
     42   DeadlockDetectorTLS<BV> dtls;
     43 };
     44 
     45 template <class BV>
     46 void RunBasicTest() {
     47   uptr path[10];
     48   ScopedDD<BV> sdd;
     49   DeadlockDetector<BV> &d = *sdd.dp;
     50   DeadlockDetectorTLS<BV> &dtls = sdd.dtls;
     51   set<uptr> s;
     52   for (size_t i = 0; i < d.size() * 3; i++) {
     53     uptr node = d.newNode(0);
     54     EXPECT_TRUE(s.insert(node).second);
     55   }
     56 
     57   d.clear();
     58   s.clear();
     59   // Add size() nodes.
     60   for (size_t i = 0; i < d.size(); i++) {
     61     uptr node = d.newNode(0);
     62     EXPECT_TRUE(s.insert(node).second);
     63   }
     64   // Remove all nodes.
     65   for (set<uptr>::iterator it = s.begin(); it != s.end(); ++it)
     66     d.removeNode(*it);
     67   // The nodes should be reused.
     68   for (size_t i = 0; i < d.size(); i++) {
     69     uptr node = d.newNode(0);
     70     EXPECT_FALSE(s.insert(node).second);
     71   }
     72 
     73   // Cycle: n1->n2->n1
     74   {
     75     d.clear();
     76     dtls.clear();
     77     uptr n1 = d.newNode(1);
     78     uptr n2 = d.newNode(2);
     79     EXPECT_FALSE(d.onLock(&dtls, n1));
     80     EXPECT_FALSE(d.onLock(&dtls, n2));
     81     d.onUnlock(&dtls, n2);
     82     d.onUnlock(&dtls, n1);
     83 
     84     EXPECT_FALSE(d.onLock(&dtls, n2));
     85     EXPECT_EQ(0U, d.findPathToLock(&dtls, n1, path, 1));
     86     EXPECT_EQ(2U, d.findPathToLock(&dtls, n1, path, 10));
     87     EXPECT_EQ(2U, d.findPathToLock(&dtls, n1, path, 2));
     88     EXPECT_TRUE(d.onLock(&dtls, n1));
     89     EXPECT_EQ(path[0], n1);
     90     EXPECT_EQ(path[1], n2);
     91     EXPECT_EQ(d.getData(n1), 1U);
     92     EXPECT_EQ(d.getData(n2), 2U);
     93     d.onUnlock(&dtls, n1);
     94     d.onUnlock(&dtls, n2);
     95   }
     96 
     97   // Cycle: n1->n2->n3->n1
     98   {
     99     d.clear();
    100     dtls.clear();
    101     uptr n1 = d.newNode(1);
    102     uptr n2 = d.newNode(2);
    103     uptr n3 = d.newNode(3);
    104 
    105     EXPECT_FALSE(d.onLock(&dtls, n1));
    106     EXPECT_FALSE(d.onLock(&dtls, n2));
    107     d.onUnlock(&dtls, n2);
    108     d.onUnlock(&dtls, n1);
    109 
    110     EXPECT_FALSE(d.onLock(&dtls, n2));
    111     EXPECT_FALSE(d.onLock(&dtls, n3));
    112     d.onUnlock(&dtls, n3);
    113     d.onUnlock(&dtls, n2);
    114 
    115     EXPECT_FALSE(d.onLock(&dtls, n3));
    116     EXPECT_EQ(0U, d.findPathToLock(&dtls, n1, path, 2));
    117     EXPECT_EQ(3U, d.findPathToLock(&dtls, n1, path, 10));
    118     EXPECT_TRUE(d.onLock(&dtls, n1));
    119     EXPECT_EQ(path[0], n1);
    120     EXPECT_EQ(path[1], n2);
    121     EXPECT_EQ(path[2], n3);
    122     EXPECT_EQ(d.getData(n1), 1U);
    123     EXPECT_EQ(d.getData(n2), 2U);
    124     EXPECT_EQ(d.getData(n3), 3U);
    125     d.onUnlock(&dtls, n1);
    126     d.onUnlock(&dtls, n3);
    127   }
    128 }
    129 
    130 TEST(DeadlockDetector, BasicTest) {
    131   RunBasicTest<BV1>();
    132   RunBasicTest<BV2>();
    133   RunBasicTest<BV3>();
    134   RunBasicTest<BV4>();
    135 }
    136 
    137 template <class BV>
    138 void RunRemoveNodeTest() {
    139   ScopedDD<BV> sdd;
    140   DeadlockDetector<BV> &d = *sdd.dp;
    141   DeadlockDetectorTLS<BV> &dtls = sdd.dtls;
    142 
    143   uptr l0 = d.newNode(0);
    144   uptr l1 = d.newNode(1);
    145   uptr l2 = d.newNode(2);
    146   uptr l3 = d.newNode(3);
    147   uptr l4 = d.newNode(4);
    148   uptr l5 = d.newNode(5);
    149 
    150   // l0=>l1=>l2
    151   d.onLock(&dtls, l0);
    152   d.onLock(&dtls, l1);
    153   d.onLock(&dtls, l2);
    154   d.onUnlock(&dtls, l1);
    155   d.onUnlock(&dtls, l0);
    156   d.onUnlock(&dtls, l2);
    157   // l3=>l4=>l5
    158   d.onLock(&dtls, l3);
    159   d.onLock(&dtls, l4);
    160   d.onLock(&dtls, l5);
    161   d.onUnlock(&dtls, l4);
    162   d.onUnlock(&dtls, l3);
    163   d.onUnlock(&dtls, l5);
    164 
    165   set<uptr> locks;
    166   locks.insert(l0);
    167   locks.insert(l1);
    168   locks.insert(l2);
    169   locks.insert(l3);
    170   locks.insert(l4);
    171   locks.insert(l5);
    172   for (uptr i = 6; i < d.size(); i++) {
    173     uptr lt = d.newNode(i);
    174     locks.insert(lt);
    175     d.onLock(&dtls, lt);
    176     d.onUnlock(&dtls, lt);
    177     d.removeNode(lt);
    178   }
    179   EXPECT_EQ(locks.size(), d.size());
    180   // l2=>l0
    181   EXPECT_FALSE(d.onLock(&dtls, l2));
    182   EXPECT_TRUE(d.onLock(&dtls, l0));
    183   d.onUnlock(&dtls, l2);
    184   d.onUnlock(&dtls, l0);
    185   // l4=>l3
    186   EXPECT_FALSE(d.onLock(&dtls, l4));
    187   EXPECT_TRUE(d.onLock(&dtls, l3));
    188   d.onUnlock(&dtls, l4);
    189   d.onUnlock(&dtls, l3);
    190 
    191   EXPECT_EQ(d.size(), d.testOnlyGetEpoch());
    192 
    193   d.removeNode(l2);
    194   d.removeNode(l3);
    195   locks.clear();
    196   // make sure no edges from or to l0,l1,l4,l5 left.
    197   for (uptr i = 4; i < d.size(); i++) {
    198     uptr lt = d.newNode(i);
    199     locks.insert(lt);
    200     uptr a, b;
    201     // l0 => lt?
    202     a = l0; b = lt;
    203     EXPECT_FALSE(d.onLock(&dtls, a));
    204     EXPECT_FALSE(d.onLock(&dtls, b));
    205     d.onUnlock(&dtls, a);
    206     d.onUnlock(&dtls, b);
    207     // l1 => lt?
    208     a = l1; b = lt;
    209     EXPECT_FALSE(d.onLock(&dtls, a));
    210     EXPECT_FALSE(d.onLock(&dtls, b));
    211     d.onUnlock(&dtls, a);
    212     d.onUnlock(&dtls, b);
    213     // lt => l4?
    214     a = lt; b = l4;
    215     EXPECT_FALSE(d.onLock(&dtls, a));
    216     EXPECT_FALSE(d.onLock(&dtls, b));
    217     d.onUnlock(&dtls, a);
    218     d.onUnlock(&dtls, b);
    219     // lt => l5?
    220     a = lt; b = l5;
    221     EXPECT_FALSE(d.onLock(&dtls, a));
    222     EXPECT_FALSE(d.onLock(&dtls, b));
    223     d.onUnlock(&dtls, a);
    224     d.onUnlock(&dtls, b);
    225 
    226     d.removeNode(lt);
    227   }
    228   // Still the same epoch.
    229   EXPECT_EQ(d.size(), d.testOnlyGetEpoch());
    230   EXPECT_EQ(locks.size(), d.size() - 4);
    231   // l2 and l3 should have ben reused.
    232   EXPECT_EQ(locks.count(l2), 1U);
    233   EXPECT_EQ(locks.count(l3), 1U);
    234 }
    235 
    236 TEST(DeadlockDetector, RemoveNodeTest) {
    237   RunRemoveNodeTest<BV1>();
    238   RunRemoveNodeTest<BV2>();
    239   RunRemoveNodeTest<BV3>();
    240   RunRemoveNodeTest<BV4>();
    241 }
    242 
    243 template <class BV>
    244 void RunMultipleEpochsTest() {
    245   ScopedDD<BV> sdd;
    246   DeadlockDetector<BV> &d = *sdd.dp;
    247   DeadlockDetectorTLS<BV> &dtls = sdd.dtls;
    248 
    249   set<uptr> locks;
    250   for (uptr i = 0; i < d.size(); i++) {
    251     EXPECT_TRUE(locks.insert(d.newNode(i)).second);
    252   }
    253   EXPECT_EQ(d.testOnlyGetEpoch(), d.size());
    254   for (uptr i = 0; i < d.size(); i++) {
    255     EXPECT_TRUE(locks.insert(d.newNode(i)).second);
    256     EXPECT_EQ(d.testOnlyGetEpoch(), d.size() * 2);
    257   }
    258   locks.clear();
    259 
    260   uptr l0 = d.newNode(0);
    261   uptr l1 = d.newNode(0);
    262   d.onLock(&dtls, l0);
    263   d.onLock(&dtls, l1);
    264   d.onUnlock(&dtls, l0);
    265   EXPECT_EQ(d.testOnlyGetEpoch(), 3 * d.size());
    266   for (uptr i = 0; i < d.size(); i++) {
    267     EXPECT_TRUE(locks.insert(d.newNode(i)).second);
    268   }
    269   EXPECT_EQ(d.testOnlyGetEpoch(), 4 * d.size());
    270 
    271 #if !SANITIZER_DEBUG
    272   // EXPECT_DEATH clones a thread with 4K stack,
    273   // which is overflown by tsan memory accesses functions in debug mode.
    274 
    275   // Can not handle the locks from the previous epoch.
    276   // The caller should update the lock id.
    277   EXPECT_DEATH(d.onLock(&dtls, l0), "CHECK failed.*current_epoch_");
    278 #endif
    279 }
    280 
    281 TEST(DeadlockDetector, MultipleEpochsTest) {
    282   RunMultipleEpochsTest<BV1>();
    283   RunMultipleEpochsTest<BV2>();
    284   RunMultipleEpochsTest<BV3>();
    285   RunMultipleEpochsTest<BV4>();
    286 }
    287 
    288 template <class BV>
    289 void RunCorrectEpochFlush() {
    290   ScopedDD<BV> sdd;
    291   DeadlockDetector<BV> &d = *sdd.dp;
    292   DeadlockDetectorTLS<BV> &dtls = sdd.dtls;
    293   vector<uptr> locks1;
    294   for (uptr i = 0; i < d.size(); i++)
    295     locks1.push_back(d.newNode(i));
    296   EXPECT_EQ(d.testOnlyGetEpoch(), d.size());
    297   d.onLock(&dtls, locks1[3]);
    298   d.onLock(&dtls, locks1[4]);
    299   d.onLock(&dtls, locks1[5]);
    300 
    301   // We have a new epoch, old locks in dtls will have to be forgotten.
    302   uptr l0 = d.newNode(0);
    303   EXPECT_EQ(d.testOnlyGetEpoch(), d.size() * 2);
    304   uptr l1 = d.newNode(0);
    305   EXPECT_EQ(d.testOnlyGetEpoch(), d.size() * 2);
    306   d.onLock(&dtls, l0);
    307   d.onLock(&dtls, l1);
    308   EXPECT_TRUE(d.testOnlyHasEdgeRaw(0, 1));
    309   EXPECT_FALSE(d.testOnlyHasEdgeRaw(1, 0));
    310   EXPECT_FALSE(d.testOnlyHasEdgeRaw(3, 0));
    311   EXPECT_FALSE(d.testOnlyHasEdgeRaw(4, 0));
    312   EXPECT_FALSE(d.testOnlyHasEdgeRaw(5, 0));
    313 }
    314 
    315 TEST(DeadlockDetector, CorrectEpochFlush) {
    316   RunCorrectEpochFlush<BV1>();
    317   RunCorrectEpochFlush<BV2>();
    318 }
    319 
    320 template <class BV>
    321 void RunTryLockTest() {
    322   ScopedDD<BV> sdd;
    323   DeadlockDetector<BV> &d = *sdd.dp;
    324   DeadlockDetectorTLS<BV> &dtls = sdd.dtls;
    325 
    326   uptr l0 = d.newNode(0);
    327   uptr l1 = d.newNode(0);
    328   uptr l2 = d.newNode(0);
    329   EXPECT_FALSE(d.onLock(&dtls, l0));
    330   EXPECT_FALSE(d.onTryLock(&dtls, l1));
    331   EXPECT_FALSE(d.onLock(&dtls, l2));
    332   EXPECT_TRUE(d.isHeld(&dtls, l0));
    333   EXPECT_TRUE(d.isHeld(&dtls, l1));
    334   EXPECT_TRUE(d.isHeld(&dtls, l2));
    335   EXPECT_FALSE(d.testOnlyHasEdge(l0, l1));
    336   EXPECT_TRUE(d.testOnlyHasEdge(l1, l2));
    337   d.onUnlock(&dtls, l0);
    338   d.onUnlock(&dtls, l1);
    339   d.onUnlock(&dtls, l2);
    340 }
    341 
    342 TEST(DeadlockDetector, TryLockTest) {
    343   RunTryLockTest<BV1>();
    344   RunTryLockTest<BV2>();
    345 }
    346 
    347 template <class BV>
    348 void RunOnFirstLockTest() {
    349   ScopedDD<BV> sdd;
    350   DeadlockDetector<BV> &d = *sdd.dp;
    351   DeadlockDetectorTLS<BV> &dtls = sdd.dtls;
    352 
    353   uptr l0 = d.newNode(0);
    354   uptr l1 = d.newNode(0);
    355   EXPECT_FALSE(d.onFirstLock(&dtls, l0));  // dtls has old epoch.
    356   d.onLock(&dtls, l0);
    357   d.onUnlock(&dtls, l0);
    358 
    359   EXPECT_TRUE(d.onFirstLock(&dtls, l0));  // Ok, same ecpoch, first lock.
    360   EXPECT_FALSE(d.onFirstLock(&dtls, l1));  // Second lock.
    361   d.onLock(&dtls, l1);
    362   d.onUnlock(&dtls, l1);
    363   d.onUnlock(&dtls, l0);
    364 
    365   EXPECT_TRUE(d.onFirstLock(&dtls, l0));  // Ok
    366   d.onUnlock(&dtls, l0);
    367 
    368   vector<uptr> locks1;
    369   for (uptr i = 0; i < d.size(); i++)
    370     locks1.push_back(d.newNode(i));
    371 
    372   EXPECT_TRUE(d.onFirstLock(&dtls, l0));  // Epoch has changed, but not in dtls.
    373 
    374   uptr l3 = d.newNode(0);
    375   d.onLock(&dtls, l3);
    376   d.onUnlock(&dtls, l3);
    377 
    378   EXPECT_FALSE(d.onFirstLock(&dtls, l0));  // Epoch has changed in dtls.
    379 }
    380 
    381 TEST(DeadlockDetector, onFirstLockTest) {
    382   RunOnFirstLockTest<BV2>();
    383 }
    384 
    385 template <class BV>
    386 void RunRecusriveLockTest() {
    387   ScopedDD<BV> sdd;
    388   DeadlockDetector<BV> &d = *sdd.dp;
    389   DeadlockDetectorTLS<BV> &dtls = sdd.dtls;
    390 
    391   uptr l0 = d.newNode(0);
    392   uptr l1 = d.newNode(0);
    393   uptr l2 = d.newNode(0);
    394   uptr l3 = d.newNode(0);
    395 
    396   EXPECT_FALSE(d.onLock(&dtls, l0));
    397   EXPECT_FALSE(d.onLock(&dtls, l1));
    398   EXPECT_FALSE(d.onLock(&dtls, l0));  // Recurisve.
    399   EXPECT_FALSE(d.onLock(&dtls, l2));
    400   d.onUnlock(&dtls, l0);
    401   EXPECT_FALSE(d.onLock(&dtls, l3));
    402   d.onUnlock(&dtls, l0);
    403   d.onUnlock(&dtls, l1);
    404   d.onUnlock(&dtls, l2);
    405   d.onUnlock(&dtls, l3);
    406   EXPECT_TRUE(d.testOnlyHasEdge(l0, l1));
    407   EXPECT_TRUE(d.testOnlyHasEdge(l0, l2));
    408   EXPECT_TRUE(d.testOnlyHasEdge(l0, l3));
    409 }
    410 
    411 TEST(DeadlockDetector, RecusriveLockTest) {
    412   RunRecusriveLockTest<BV2>();
    413 }
    414 
    415 template <class BV>
    416 void RunLockContextTest() {
    417   ScopedDD<BV> sdd;
    418   DeadlockDetector<BV> &d = *sdd.dp;
    419   DeadlockDetectorTLS<BV> &dtls = sdd.dtls;
    420 
    421   uptr l0 = d.newNode(0);
    422   uptr l1 = d.newNode(0);
    423   uptr l2 = d.newNode(0);
    424   uptr l3 = d.newNode(0);
    425   uptr l4 = d.newNode(0);
    426   EXPECT_FALSE(d.onLock(&dtls, l0, 10));
    427   EXPECT_FALSE(d.onLock(&dtls, l1, 11));
    428   EXPECT_FALSE(d.onLock(&dtls, l2, 12));
    429   EXPECT_FALSE(d.onLock(&dtls, l3, 13));
    430   EXPECT_EQ(10U, d.findLockContext(&dtls, l0));
    431   EXPECT_EQ(11U, d.findLockContext(&dtls, l1));
    432   EXPECT_EQ(12U, d.findLockContext(&dtls, l2));
    433   EXPECT_EQ(13U, d.findLockContext(&dtls, l3));
    434   d.onUnlock(&dtls, l0);
    435   EXPECT_EQ(0U, d.findLockContext(&dtls, l0));
    436   EXPECT_EQ(11U, d.findLockContext(&dtls, l1));
    437   EXPECT_EQ(12U, d.findLockContext(&dtls, l2));
    438   EXPECT_EQ(13U, d.findLockContext(&dtls, l3));
    439   d.onUnlock(&dtls, l2);
    440   EXPECT_EQ(0U, d.findLockContext(&dtls, l0));
    441   EXPECT_EQ(11U, d.findLockContext(&dtls, l1));
    442   EXPECT_EQ(0U, d.findLockContext(&dtls, l2));
    443   EXPECT_EQ(13U, d.findLockContext(&dtls, l3));
    444 
    445   EXPECT_FALSE(d.onLock(&dtls, l4, 14));
    446   EXPECT_EQ(14U, d.findLockContext(&dtls, l4));
    447 }
    448 
    449 TEST(DeadlockDetector, LockContextTest) {
    450   RunLockContextTest<BV2>();
    451 }
    452 
    453 template <class BV>
    454 void RunRemoveEdgesTest() {
    455   ScopedDD<BV> sdd;
    456   DeadlockDetector<BV> &d = *sdd.dp;
    457   DeadlockDetectorTLS<BV> &dtls = sdd.dtls;
    458   vector<uptr> node(BV::kSize);
    459   u32 stk_from = 0, stk_to = 0;
    460   int unique_tid = 0;
    461   for (size_t i = 0; i < BV::kSize; i++)
    462     node[i] = d.newNode(0);
    463 
    464   for (size_t i = 0; i < BV::kSize; i++)
    465     EXPECT_FALSE(d.onLock(&dtls, node[i], i + 1));
    466   for (size_t i = 0; i < BV::kSize; i++) {
    467     for (uptr j = i + 1; j < BV::kSize; j++) {
    468       EXPECT_TRUE(
    469           d.findEdge(node[i], node[j], &stk_from, &stk_to, &unique_tid));
    470       EXPECT_EQ(stk_from, i + 1);
    471       EXPECT_EQ(stk_to, j + 1);
    472     }
    473   }
    474   EXPECT_EQ(d.testOnlyGetEpoch(), d.size());
    475   // Remove and re-create half of the nodes.
    476   for (uptr i = 1; i < BV::kSize; i += 2)
    477     d.removeNode(node[i]);
    478   for (uptr i = 1; i < BV::kSize; i += 2)
    479     node[i] = d.newNode(0);
    480   EXPECT_EQ(d.testOnlyGetEpoch(), d.size());
    481   // The edges from or to the removed nodes should be gone.
    482   for (size_t i = 0; i < BV::kSize; i++) {
    483     for (uptr j = i + 1; j < BV::kSize; j++) {
    484       if ((i % 2) || (j % 2))
    485         EXPECT_FALSE(
    486             d.findEdge(node[i], node[j], &stk_from, &stk_to, &unique_tid));
    487       else
    488         EXPECT_TRUE(
    489             d.findEdge(node[i], node[j], &stk_from, &stk_to, &unique_tid));
    490     }
    491   }
    492 }
    493 
    494 TEST(DeadlockDetector, RemoveEdgesTest) {
    495   RunRemoveEdgesTest<BV1>();
    496 }
    497