test/tsan/deadlock_detector_stress_test.cc

   1 // RUN: %clangxx_tsan %s -o %t -DLockType=PthreadMutex
   2 // RUN: TSAN_OPTIONS=detect_deadlocks=1 not %t 2>&1 | FileCheck %s
   3 // RUN: %clangxx_tsan %s -o %t -DLockType=PthreadSpinLock
   4 // RUN: TSAN_OPTIONS=detect_deadlocks=1 not %t 2>&1 | FileCheck %s
   5 // RUN: %clangxx_tsan %s -o %t -DLockType=PthreadRWLock
   6 // RUN: TSAN_OPTIONS=detect_deadlocks=1 not %t 2>&1 | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-RD
   7 // RUN: %clangxx_tsan %s -o %t -DLockType=PthreadRecursiveMutex
   8 // RUN: TSAN_OPTIONS=detect_deadlocks=1 not %t 2>&1 | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-REC
   9 #include <pthread.h>
  10 #undef NDEBUG
  11 #include <assert.h>
  12 #include <stdlib.h>
  13 #include <stdio.h>
  14 #include <unistd.h>
  15
  16 #ifndef LockType
  17 #define LockType PthreadMutex
  18 #endif
  19
  20 // You can optionally pass [test_number [iter_count]] on command line.
  21 static int test_number = -1;
  22 static int iter_count = 100000;
  23
  24 class PthreadMutex {
  25  public:
  26   explicit PthreadMutex(bool recursive = false) {
  27     pthread_mutexattr_t attr;
  28     pthread_mutexattr_init(&attr);
  29     if (recursive)
  30       pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_RECURSIVE);
  31     assert(0 == pthread_mutex_init(&mu_, &attr));
  32   }
  33   ~PthreadMutex() {
  34     assert(0 == pthread_mutex_destroy(&mu_));
  35     (void)padding_;
  36   }
  37   static bool supports_read_lock() { return false; }
  38   static bool supports_recursive_lock() { return false; }
  39   void lock() { assert(0 == pthread_mutex_lock(&mu_)); }
  40   void unlock() { assert(0 == pthread_mutex_unlock(&mu_)); }
  41   bool try_lock() { return 0 == pthread_mutex_trylock(&mu_); }
  42   void rdlock() { assert(0); }
  43   void rdunlock() { assert(0); }
  44   bool try_rdlock() { assert(0); }
  45
  46  private:
  47   pthread_mutex_t mu_;
  48   char padding_[64 - sizeof(pthread_mutex_t)];
  49 };
  50
  51 class PthreadRecursiveMutex : public PthreadMutex {
  52  public:
  53   PthreadRecursiveMutex() : PthreadMutex(true) { }
  54   static bool supports_recursive_lock() { return true; }
  55 };
  56
  57 class PthreadSpinLock {
  58  public:
  59   PthreadSpinLock() { assert(0 == pthread_spin_init(&mu_, 0)); }
  60   ~PthreadSpinLock() {
  61     assert(0 == pthread_spin_destroy(&mu_));
  62     (void)padding_;
  63   }
  64   static bool supports_read_lock() { return false; }
  65   static bool supports_recursive_lock() { return false; }
  66   void lock() { assert(0 == pthread_spin_lock(&mu_)); }
  67   void unlock() { assert(0 == pthread_spin_unlock(&mu_)); }
  68   bool try_lock() { return 0 == pthread_spin_trylock(&mu_); }
  69   void rdlock() { assert(0); }
  70   void rdunlock() { assert(0); }
  71   bool try_rdlock() { assert(0); }
  72
  73  private:
  74   pthread_spinlock_t mu_;
  75   char padding_[64 - sizeof(pthread_spinlock_t)];
  76 };
  77
  78 class PthreadRWLock {
  79  public:
  80   PthreadRWLock() { assert(0 == pthread_rwlock_init(&mu_, 0)); }
  81   ~PthreadRWLock() {
  82     assert(0 == pthread_rwlock_destroy(&mu_));
  83     (void)padding_;
  84   }
  85   static bool supports_read_lock() { return true; }
  86   static bool supports_recursive_lock() { return false; }
  87   void lock() { assert(0 == pthread_rwlock_wrlock(&mu_)); }
  88   void unlock() { assert(0 == pthread_rwlock_unlock(&mu_)); }
  89   bool try_lock() { return 0 == pthread_rwlock_trywrlock(&mu_); }
  90   void rdlock() { assert(0 == pthread_rwlock_rdlock(&mu_)); }
  91   void rdunlock() { assert(0 == pthread_rwlock_unlock(&mu_)); }
  92   bool try_rdlock() { return 0 == pthread_rwlock_tryrdlock(&mu_); }
  93
  94  private:
  95   pthread_rwlock_t mu_;
  96   char padding_[64 - sizeof(pthread_rwlock_t)];
  97 };
  98
  99 class LockTest {
 100  public:
 101   LockTest() : n_(), locks_() {}
 102   void Init(size_t n) {
 103     n_ = n;
 104     locks_ = new LockType*[n_];
 105     for (size_t i = 0; i < n_; i++)
 106       locks_[i] = new LockType;
 107   }
 108   ~LockTest() {
 109     for (size_t i = 0; i < n_; i++)
 110       delete locks_[i];
 111     delete [] locks_;
 112   }
 113   void L(size_t i) {
 114     assert(i < n_);
 115     locks_[i]->lock();
 116   }
 117
 118   void U(size_t i) {
 119     assert(i < n_);
 120     locks_[i]->unlock();
 121   }
 122
 123   void RL(size_t i) {
 124     assert(i < n_);
 125     locks_[i]->rdlock();
 126   }
 127
 128   void RU(size_t i) {
 129     assert(i < n_);
 130     locks_[i]->rdunlock();
 131   }
 132
 133   void *A(size_t i) {
 134     assert(i < n_);
 135     return locks_[i];
 136   }
 137
 138   bool T(size_t i) {
 139     assert(i < n_);
 140     return locks_[i]->try_lock();
 141   }
 142
 143   // Simple lock order onversion.
 144   void Test1() {
 145     if (test_number > 0 && test_number != 1) return;
 146     fprintf(stderr, "Starting Test1\n");
 147     // CHECK: Starting Test1
 148     Init(5);
 149     fprintf(stderr, "Expecting lock inversion: %p %p\n", A(0), A(1));
 150     // CHECK: Expecting lock inversion: [[A1:0x[a-f0-9]*]] [[A2:0x[a-f0-9]*]]
 151     Lock_0_1();
 152     Lock_1_0();
 153     // CHECK: WARNING: ThreadSanitizer: lock-order-inversion (potential deadlock)
 154     // CHECK: path: [[M1:M[0-9]+]] => [[M2:M[0-9]+]] => [[M1]]
 155     // CHECK: Mutex [[M1]] ([[A1]]) created at:
 156     // CHECK: Mutex [[M2]] ([[A2]]) created at:
 157     // CHECK-NOT: WARNING: ThreadSanitizer:
 158   }
 159
 160   // Simple lock order inversion with 3 locks.
 161   void Test2() {
 162     if (test_number > 0 && test_number != 2) return;
 163     fprintf(stderr, "Starting Test2\n");
 164     // CHECK: Starting Test2
 165     Init(5);
 166     fprintf(stderr, "Expecting lock inversion: %p %p %p\n", A(0), A(1), A(2));
 167     // CHECK: Expecting lock inversion: [[A1:0x[a-f0-9]*]] [[A2:0x[a-f0-9]*]] [[A3:0x[a-f0-9]*]]
 168     Lock2(0, 1);
 169     Lock2(1, 2);
 170     Lock2(2, 0);
 171     // CHECK: WARNING: ThreadSanitizer: lock-order-inversion (potential deadlock)
 172     // CHECK: path: [[M1:M[0-9]+]] => [[M2:M[0-9]+]] => [[M3:M[0-9]+]] => [[M1]]
 173     // CHECK: Mutex [[M1]] ([[A1]]) created at:
 174     // CHECK: Mutex [[M2]] ([[A2]]) created at:
 175     // CHECK: Mutex [[M3]] ([[A3]]) created at:
 176     // CHECK-NOT: WARNING: ThreadSanitizer:
 177   }
 178
 179   // Lock order inversion with lots of new locks created (but not used)
 180   // between. Since the new locks are not used we should still detect the
 181   // deadlock.
 182   void Test3() {
 183     if (test_number > 0 && test_number != 3) return;
 184     fprintf(stderr, "Starting Test3\n");
 185     // CHECK: Starting Test3
 186     Init(5);
 187     Lock_0_1();
 188     L(2);
 189     CreateAndDestroyManyLocks();
 190     U(2);
 191     Lock_1_0();
 192     // CHECK: WARNING: ThreadSanitizer: lock-order-inversion (potential deadlock)
 193     // CHECK-NOT: WARNING: ThreadSanitizer:
 194   }
 195
 196   // lock l0=>l1; then create and use lots of locks; then lock l1=>l0.
 197   // The deadlock epoch should have changed and we should not report anything.
 198   void Test4() {
 199     if (test_number > 0 && test_number != 4) return;
 200     fprintf(stderr, "Starting Test4\n");
 201     // CHECK: Starting Test4
 202     Init(5);
 203     Lock_0_1();
 204     L(2);
 205     CreateLockUnlockAndDestroyManyLocks();
 206     U(2);
 207     Lock_1_0();
 208     // CHECK-NOT: WARNING: ThreadSanitizer:
 209   }
 210
 211   void Test5() {
 212     if (test_number > 0 && test_number != 5) return;
 213     fprintf(stderr, "Starting Test5\n");
 214     // CHECK: Starting Test5
 215     Init(5);
 216     RunThreads(&LockTest::Lock_0_1, &LockTest::Lock_1_0);
 217     // CHECK: WARNING: ThreadSanitizer: lock-order-inversion
 218     // CHECK-NOT: WARNING: ThreadSanitizer:
 219   }
 220
 221   void Test6() {
 222     if (test_number > 0 && test_number != 6) return;
 223     fprintf(stderr, "Starting Test6: 3 threads lock/unlock private mutexes\n");
 224     // CHECK: Starting Test6
 225     Init(100);
 226     // CHECK-NOT: WARNING: ThreadSanitizer:
 227     RunThreads(&LockTest::Lock1_Loop_0, &LockTest::Lock1_Loop_1,
 228                &LockTest::Lock1_Loop_2);
 229   }
 230
 231   void Test7() {
 232     if (test_number > 0 && test_number != 7) return;
 233     fprintf(stderr, "Starting Test7\n");
 234     // CHECK: Starting Test7
 235     Init(10);
 236     L(0); T(1); U(1); U(0);
 237     T(1); L(0); U(1); U(0);
 238     // CHECK-NOT: WARNING: ThreadSanitizer:
 239     fprintf(stderr, "No cycle: 0=>1\n");
 240     // CHECK: No cycle: 0=>1
 241
 242     T(2); L(3); U(3); U(2);
 243     L(3); T(2); U(3); U(2);
 244     // CHECK-NOT: WARNING: ThreadSanitizer:
 245     fprintf(stderr, "No cycle: 2=>3\n");
 246     // CHECK: No cycle: 2=>3
 247
 248     T(4); L(5); U(4); U(5);
 249     L(5); L(4); U(4); U(5);
 250     // CHECK: WARNING: ThreadSanitizer: lock-order-inversion
 251     fprintf(stderr, "Have cycle: 4=>5\n");
 252     // CHECK: Have cycle: 4=>5
 253
 254     L(7); L(6); U(6); U(7);
 255     T(6); L(7); U(6); U(7);
 256     // CHECK: WARNING: ThreadSanitizer: lock-order-inversion
 257     fprintf(stderr, "Have cycle: 6=>7\n");
 258     // CHECK: Have cycle: 6=>7
 259   }
 260
 261   void Test8() {
 262     if (test_number > 0 && test_number != 8) return;
 263     if (!LockType::supports_read_lock()) return;
 264     fprintf(stderr, "Starting Test8\n");
 265     Init(5);
 266     // CHECK-RD: Starting Test8
 267     RL(0); L(1); RU(0); U(1);
 268     L(1); RL(0); RU(0); U(1);
 269     // CHECK-RD: WARNING: ThreadSanitizer: lock-order-inversion
 270     fprintf(stderr, "Have cycle: 0=>1\n");
 271     // CHECK-RD: Have cycle: 0=>1
 272
 273     RL(2); RL(3); RU(2); RU(3);
 274     RL(3); RL(2); RU(2); RU(3);
 275     // CHECK-RD: WARNING: ThreadSanitizer: lock-order-inversion
 276     fprintf(stderr, "Have cycle: 2=>3\n");
 277     // CHECK-RD: Have cycle: 2=>3
 278   }
 279
 280   void Test9() {
 281     if (test_number > 0 && test_number != 9) return;
 282     if (!LockType::supports_recursive_lock()) return;
 283     fprintf(stderr, "Starting Test9\n");
 284     // CHECK-REC: Starting Test9
 285     Init(5);
 286     L(0); L(0); L(0); L(1); U(1); U(0); U(0); U(0);
 287     L(1); L(1); L(1); L(0); U(0); U(1); U(1); U(1);
 288     // CHECK-REC: WARNING: ThreadSanitizer: lock-order-inversion
 289   }
 290
 291   void Test10() {
 292     if (test_number > 0 && test_number != 10) return;
 293     fprintf(stderr, "Starting Test10: 4 threads lock/unlock 4 private mutexes, one under another\n");
 294     // CHECK: Starting Test10
 295     Init(100);
 296     // CHECK-NOT: WARNING: ThreadSanitizer:
 297     RunThreads(&LockTest::Test10_Thread1, &LockTest::Test10_Thread2,
 298                &LockTest::Test10_Thread3, &LockTest::Test10_Thread4);
 299   }
 300   void Test10_Thread1() { Test10_Thread(0); }
 301   void Test10_Thread2() { Test10_Thread(10); }
 302   void Test10_Thread3() { Test10_Thread(20); }
 303   void Test10_Thread4() { Test10_Thread(30); }
 304   void Test10_Thread(size_t m) {
 305     for (int i = 0; i < iter_count; i++) {
 306       L(m + 0);
 307       L(m + 1);
 308       L(m + 2);
 309       L(m + 3);
 310       U(m + 3);
 311       U(m + 2);
 312       U(m + 1);
 313       U(m + 0);
 314     }
 315   }
 316
 317   void Test11() {
 318     if (test_number > 0 && test_number != 11) return;
 319     fprintf(stderr, "Starting Test11: 4 threads lock/unlock 4 private mutexes, all under another private mutex\n");
 320     // CHECK: Starting Test11
 321     Init(500);
 322     // CHECK-NOT: WARNING: ThreadSanitizer:
 323     RunThreads(&LockTest::Test11_Thread1, &LockTest::Test11_Thread2,
 324                &LockTest::Test11_Thread3, &LockTest::Test11_Thread4);
 325   }
 326   void Test11_Thread1() { Test10_Thread(0); }
 327   void Test11_Thread2() { Test10_Thread(10); }
 328   void Test11_Thread3() { Test10_Thread(20); }
 329   void Test11_Thread4() { Test10_Thread(30); }
 330   void Test11_Thread(size_t m) {
 331     for (int i = 0; i < iter_count; i++) {
 332       L(m);
 333       L(m + 100);
 334       U(m + 100);
 335       L(m + 200);
 336       U(m + 200);
 337       L(m + 300);
 338       U(m + 300);
 339       L(m + 400);
 340       U(m + 500);
 341       U(m);
 342     }
 343   }
 344
 345   void Test12() {
 346     if (test_number > 0 && test_number != 12) return;
 347     if (!LockType::supports_read_lock()) return;
 348     fprintf(stderr, "Starting Test12: 4 threads read lock/unlock 4 shared mutexes, one under another\n");
 349     // CHECK-RD: Starting Test12
 350     Init(500);
 351     // CHECK-RD-NOT: WARNING: ThreadSanitizer:
 352     RunThreads(&LockTest::Test12_Thread, &LockTest::Test12_Thread,
 353                &LockTest::Test12_Thread, &LockTest::Test12_Thread);
 354   }
 355   void Test12_Thread() {
 356     for (int i = 0; i < iter_count; i++) {
 357       RL(000);
 358       RL(100);
 359       RL(200);
 360       RL(300);
 361       RU(300);
 362       RU(200);
 363       RU(100);
 364       RU(000);
 365     }
 366   }
 367
 368   void Test13() {
 369     if (test_number > 0 && test_number != 13) return;
 370     if (!LockType::supports_read_lock()) return;
 371     fprintf(stderr, "Starting Test13: 4 threads read lock/unlock 4 shared mutexes, all under another shared mutex\n");
 372     // CHECK-RD: Starting Test13
 373     Init(500);
 374     // CHECK-RD-NOT: WARNING: ThreadSanitizer:
 375     RunThreads(&LockTest::Test13_Thread, &LockTest::Test13_Thread,
 376                &LockTest::Test13_Thread, &LockTest::Test13_Thread);
 377   }
 378   void Test13_Thread() {
 379     for (int i = 0; i < iter_count; i++) {
 380       RL(0);
 381       RL(100);
 382       RU(100);
 383       RL(200);
 384       RU(200);
 385       RL(300);
 386       RU(300);
 387       RL(400);
 388       RU(400);
 389       RU(0);
 390     }
 391   }
 392
 393   void Test14() {
 394     if (test_number > 0 && test_number != 14) return;
 395     fprintf(stderr, "Starting Test14: create lots of locks in 4 threads\n");
 396     Init(10);
 397     // CHECK-RD: Starting Test14
 398     RunThreads(&LockTest::CreateAndDestroyLocksLoop,
 399                &LockTest::CreateAndDestroyLocksLoop,
 400                &LockTest::CreateAndDestroyLocksLoop,
 401                &LockTest::CreateAndDestroyLocksLoop);
 402   }
 403
 404   void Test15() {
 405     if (test_number > 0 && test_number != 15) return;
 406     if (!LockType::supports_read_lock()) return;
 407     fprintf(stderr, "Starting Test15: recursive rlock\n");
 408     // DISABLEDCHECK-RD: Starting Test15
 409     Init(5);
 410     RL(0); RL(0); RU(0); RU(0);  // Recusrive reader lock.
 411   }
 412
 413  private:
 414   void Lock2(size_t l1, size_t l2) { L(l1); L(l2); U(l2); U(l1); }
 415   void Lock_0_1() { Lock2(0, 1); }
 416   void Lock_1_0() { sleep(1); Lock2(1, 0); }
 417   void Lock1_Loop(size_t i, size_t n_iter) {
 418     for (size_t it = 0; it < n_iter; it++) {
 419       // if ((it & (it - 1)) == 0) fprintf(stderr, "%zd", i);
 420       L(i);
 421       U(i);
 422     }
 423     // fprintf(stderr, "\n");
 424   }
 425   void Lock1_Loop_0() { Lock1_Loop(0, iter_count); }
 426   void Lock1_Loop_1() { Lock1_Loop(10, iter_count); }
 427   void Lock1_Loop_2() { Lock1_Loop(20, iter_count); }
 428
 429   void CreateAndDestroyManyLocks() {
 430     LockType *create_many_locks_but_never_acquire =
 431         new LockType[kDeadlockGraphSize];
 432     (void)create_many_locks_but_never_acquire;
 433     delete [] create_many_locks_but_never_acquire;
 434   }
 435
 436   void CreateAndDestroyLocksLoop() {
 437     for (size_t it = 0; it <= iter_count; it++) {
 438       LockType some_locks[10];
 439       (void)some_locks;
 440     }
 441   }
 442
 443   void CreateLockUnlockAndDestroyManyLocks() {
 444     LockType many_locks[kDeadlockGraphSize];
 445     for (size_t i = 0; i < kDeadlockGraphSize; i++) {
 446       many_locks[i].lock();
 447       many_locks[i].unlock();
 448     }
 449   }
 450
 451   // LockTest Member function callback.
 452   struct CB {
 453     void (LockTest::*f)();
 454     LockTest *lt;
 455   };
 456
 457   // Thread function with CB.
 458   static void *Thread(void *param) {
 459     CB *cb = (CB*)param;
 460     (cb->lt->*cb->f)();
 461     return NULL;
 462   }
 463
 464   void RunThreads(void (LockTest::*f1)(), void (LockTest::*f2)(),
 465                   void (LockTest::*f3)() = 0, void (LockTest::*f4)() = 0) {
 466     const int kNumThreads = 4;
 467     pthread_t t[kNumThreads];
 468     CB cb[kNumThreads] = {{f1, this}, {f2, this}, {f3, this}, {f4, this}};
 469     for (int i = 0; i < kNumThreads && cb[i].f; i++)
 470       pthread_create(&t[i], 0, Thread, &cb[i]);
 471     for (int i = 0; i < kNumThreads && cb[i].f; i++)
 472       pthread_join(t[i], 0);
 473   }
 474
 475   static const size_t kDeadlockGraphSize = 4096;
 476   size_t n_;
 477   LockType **locks_;
 478 };
 479
 480 int main(int argc, char **argv) {
 481   if (argc > 1)
 482     test_number = atoi(argv[1]);
 483   if (argc > 2)
 484     iter_count = atoi(argv[2]);
 485   LockTest().Test1();
 486   LockTest().Test2();
 487   LockTest().Test3();
 488   LockTest().Test4();
 489   LockTest().Test5();
 490   LockTest().Test6();
 491   LockTest().Test7();
 492   LockTest().Test8();
 493   LockTest().Test9();
 494   LockTest().Test10();
 495   LockTest().Test11();
 496   LockTest().Test12();
 497   LockTest().Test13();
 498   LockTest().Test14();
 499   // LockTest().Test15();  // FIXME: this is broken for PthreadRWLock
 500   fprintf(stderr, "ALL-DONE\n");
 501   // CHECK: ALL-DONE
 502 }