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