compiler-rt/lib/sanitizer_common/tests/sanitizer_deadlock_detector_test.cpp

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