// RUN: %clangxx_tsan %s -o %t -DLockType=PthreadMutex
// RUN: %env_tsan_opts=detect_deadlocks=1 %deflake %run %t | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-NOT-SECOND
// RUN: %env_tsan_opts=detect_deadlocks=1:second_deadlock_stack=1 %deflake %run %t | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-SECOND
// RUN: %clangxx_tsan %s -o %t -DLockType=PthreadSpinLock
// RUN: %env_tsan_opts=detect_deadlocks=1 %deflake %run %t | FileCheck %s
// RUN: %clangxx_tsan %s -o %t -DLockType=PthreadRWLock
// RUN: %env_tsan_opts=detect_deadlocks=1 %deflake %run %t | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-RD
// RUN: %clangxx_tsan %s -o %t -DLockType=PthreadRecursiveMutex
// RUN: %env_tsan_opts=detect_deadlocks=1 %deflake %run %t | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-REC
#include "test.h"
#undef NDEBUG
#include <assert.h>
#include <new>

#ifndef LockType
#define LockType PthreadMutex
#endif

// You can optionally pass [test_number [iter_count]] on command line.
static int test_number = -1;
static int iter_count = 100000;

class PthreadMutex {
 public:
  explicit PthreadMutex(bool recursive = false) {
    if (recursive) {
      pthread_mutexattr_t attr;
      pthread_mutexattr_init(&attr);
      pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_RECURSIVE);
      assert(0 == pthread_mutex_init(&mu_, &attr));
    } else {
      assert(0 == pthread_mutex_init(&mu_, 0));
    }
  }
  ~PthreadMutex() {
    assert(0 == pthread_mutex_destroy(&mu_));
    (void)padding_;
  }
  static bool supports_read_lock() { return false; }
  static bool supports_recursive_lock() { return false; }
  void lock() { assert(0 == pthread_mutex_lock(&mu_)); }
  void unlock() { assert(0 == pthread_mutex_unlock(&mu_)); }
  bool try_lock() { return 0 == pthread_mutex_trylock(&mu_); }
  void rdlock() { assert(0); }
  void rdunlock() { assert(0); }
  bool try_rdlock() { assert(0); }

 private:
  pthread_mutex_t mu_;
  char padding_[64 - sizeof(pthread_mutex_t)];
};

class PthreadRecursiveMutex : public PthreadMutex {
 public:
  PthreadRecursiveMutex() : PthreadMutex(true) { }
  static bool supports_recursive_lock() { return true; }
};

#ifndef __APPLE__
class PthreadSpinLock {
 public:
  PthreadSpinLock() { assert(0 == pthread_spin_init(&mu_, 0)); }
  ~PthreadSpinLock() {
    assert(0 == pthread_spin_destroy(&mu_));
    (void)padding_;
  }
  static bool supports_read_lock() { return false; }
  static bool supports_recursive_lock() { return false; }
  void lock() { assert(0 == pthread_spin_lock(&mu_)); }
  void unlock() { assert(0 == pthread_spin_unlock(&mu_)); }
  bool try_lock() { return 0 == pthread_spin_trylock(&mu_); }
  void rdlock() { assert(0); }
  void rdunlock() { assert(0); }
  bool try_rdlock() { assert(0); }

 private:
  pthread_spinlock_t mu_;
  char padding_[64 - sizeof(pthread_spinlock_t)];
};
#else
class PthreadSpinLock : public PthreadMutex { };
#endif

class PthreadRWLock {
 public:
  PthreadRWLock() { assert(0 == pthread_rwlock_init(&mu_, 0)); }
  ~PthreadRWLock() {
    assert(0 == pthread_rwlock_destroy(&mu_));
    (void)padding_;
  }
  static bool supports_read_lock() { return true; }
  static bool supports_recursive_lock() { return false; }
  void lock() { assert(0 == pthread_rwlock_wrlock(&mu_)); }
  void unlock() { assert(0 == pthread_rwlock_unlock(&mu_)); }
  bool try_lock() { return 0 == pthread_rwlock_trywrlock(&mu_); }
  void rdlock() { assert(0 == pthread_rwlock_rdlock(&mu_)); }
  void rdunlock() { assert(0 == pthread_rwlock_unlock(&mu_)); }
  bool try_rdlock() { return 0 == pthread_rwlock_tryrdlock(&mu_); }

 private:
  pthread_rwlock_t mu_;
  char padding_[256 - sizeof(pthread_rwlock_t)];
};

class LockTest {
 public:
  LockTest() : n_(), locks_() {}
  void Init(size_t n) {
    n_ = n;
    locks_ = new LockType*[n_];
    for (size_t i = 0; i < n_; i++)
      locks_[i] = new LockType;
  }
  ~LockTest() {
    for (size_t i = 0; i < n_; i++)
      delete locks_[i];
    delete [] locks_;
  }
  void L(size_t i) {
    assert(i < n_);
    locks_[i]->lock();
  }

  void U(size_t i) {
    assert(i < n_);
    locks_[i]->unlock();
  }

  void RL(size_t i) {
    assert(i < n_);
    locks_[i]->rdlock();
  }

  void RU(size_t i) {
    assert(i < n_);
    locks_[i]->rdunlock();
  }

  void *A(size_t i) {
    assert(i < n_);
    return locks_[i];
  }

  bool T(size_t i) {
    assert(i < n_);
    return locks_[i]->try_lock();
  }

  // Simple lock order onversion.
  void Test1() {
    if (test_number > 0 && test_number != 1) return;
    fprintf(stderr, "Starting Test1\n");
    // CHECK: Starting Test1
    Init(5);
    print_address("Expecting lock inversion: ", 2, A(0), A(1));
    // CHECK: Expecting lock inversion: [[A1:0x[a-f0-9]*]] [[A2:0x[a-f0-9]*]]
    Lock_0_1();
    Lock_1_0();
    // CHECK: WARNING: ThreadSanitizer: lock-order-inversion (potential deadlock)
    // CHECK: Cycle in lock order graph: [[M1:M[0-9]+]] ([[A1]]) => [[M2:M[0-9]+]] ([[A2]]) => [[M1]]
    // CHECK: Mutex [[M2]] acquired here while holding mutex [[M1]]
    // CHECK:   #0 pthread_
    // CHECK-SECOND:   Mutex [[M1]] previously acquired by the same thread here:
    // CHECK-SECOND:   #0 pthread_
    // CHECK-NOT-SECOND:   second_deadlock_stack=1 to get more informative warning message
    // CHECK-NOT-SECOND-NOT:   #0 pthread_
    // CHECK: Mutex [[M1]] acquired here while holding mutex [[M2]]
    // CHECK:   #0 pthread_
    // CHECK-SECOND:   Mutex [[M2]] previously acquired by the same thread here:
    // CHECK-SECOND:   #0 pthread_
    // CHECK-NOT-SECOND-NOT:   #0 pthread_
    // CHECK-NOT: WARNING: ThreadSanitizer:
  }

  // Simple lock order inversion with 3 locks.
  void Test2() {
    if (test_number > 0 && test_number != 2) return;
    fprintf(stderr, "Starting Test2\n");
    // CHECK: Starting Test2
    Init(5);
    print_address("Expecting lock inversion: ", 3, A(0), A(1), A(2));
    // CHECK: Expecting lock inversion: [[A1:0x[a-f0-9]*]] [[A2:0x[a-f0-9]*]] [[A3:0x[a-f0-9]*]]
    Lock2(0, 1);
    Lock2(1, 2);
    Lock2(2, 0);
    // CHECK: WARNING: ThreadSanitizer: lock-order-inversion (potential deadlock)
    // CHECK: Cycle in lock order graph: [[M1:M[0-9]+]] ([[A1]]) => [[M2:M[0-9]+]] ([[A2]]) => [[M3:M[0-9]+]] ([[A3]]) => [[M1]]
    // CHECK-NOT: WARNING: ThreadSanitizer:
  }

  // Lock order inversion with lots of new locks created (but not used)
  // between. Since the new locks are not used we should still detect the
  // deadlock.
  void Test3() {
    if (test_number > 0 && test_number != 3) return;
    fprintf(stderr, "Starting Test3\n");
    // CHECK: Starting Test3
    Init(5);
    Lock_0_1();
    L(2);
    CreateAndDestroyManyLocks();
    U(2);
    Lock_1_0();
    // CHECK: WARNING: ThreadSanitizer: lock-order-inversion (potential deadlock)
    // CHECK-NOT: WARNING: ThreadSanitizer:
  }

  // lock l0=>l1; then create and use lots of locks; then lock l1=>l0.
  // The deadlock epoch should have changed and we should not report anything.
  void Test4() {
    if (test_number > 0 && test_number != 4) return;
    fprintf(stderr, "Starting Test4\n");
    // CHECK: Starting Test4
    Init(5);
    Lock_0_1();
    L(2);
    CreateLockUnlockAndDestroyManyLocks();
    U(2);
    Lock_1_0();
    // CHECK-NOT: WARNING: ThreadSanitizer:
  }

  void Test5() {
    if (test_number > 0 && test_number != 5) return;
    fprintf(stderr, "Starting Test5\n");
    // CHECK: Starting Test5
    Init(5);
    RunThreads(&LockTest::Lock_0_1<true>, &LockTest::Lock_1_0<true>);
    // CHECK: WARNING: ThreadSanitizer: lock-order-inversion
    // CHECK: Cycle in lock order graph: [[M1:M[0-9]+]] ({{.*}}) => [[M2:M[0-9]+]] ({{.*}}) => [[M1]]
    // CHECK: Mutex [[M2]] acquired here while holding mutex [[M1]] in thread [[T1:T[0-9]+]]
    // CHECK: Mutex [[M1]] acquired here while holding mutex [[M2]] in thread [[T2:T[0-9]+]]
    // CHECK: Thread [[T1]] {{.*}} created by main thread
    // CHECK: Thread [[T2]] {{.*}} created by main thread
    // CHECK-NOT: WARNING: ThreadSanitizer:
  }

  void Test6() {
    if (test_number > 0 && test_number != 6) return;
    fprintf(stderr, "Starting Test6: 3 threads lock/unlock private mutexes\n");
    // CHECK: Starting Test6
    Init(100);
    // CHECK-NOT: WARNING: ThreadSanitizer:
    RunThreads(&LockTest::Lock1_Loop_0, &LockTest::Lock1_Loop_1,
               &LockTest::Lock1_Loop_2);
  }

  void Test7() {
    if (test_number > 0 && test_number != 7) return;
    fprintf(stderr, "Starting Test7\n");
    // CHECK: Starting Test7
    Init(10);
    L(0); T(1); U(1); U(0);
    T(1); L(0); U(1); U(0);
    // CHECK-NOT: WARNING: ThreadSanitizer:
    fprintf(stderr, "No cycle: 0=>1\n");
    // CHECK: No cycle: 0=>1

    T(2); L(3); U(3); U(2);
    L(3); T(2); U(3); U(2);
    // CHECK-NOT: WARNING: ThreadSanitizer:
    fprintf(stderr, "No cycle: 2=>3\n");
    // CHECK: No cycle: 2=>3

    T(4); L(5); U(4); U(5);
    L(5); L(4); U(4); U(5);
    // CHECK: WARNING: ThreadSanitizer: lock-order-inversion
    fprintf(stderr, "Have cycle: 4=>5\n");
    // CHECK: Have cycle: 4=>5

    L(7); L(6); U(6); U(7);
    T(6); L(7); U(6); U(7);
    // CHECK: WARNING: ThreadSanitizer: lock-order-inversion
    fprintf(stderr, "Have cycle: 6=>7\n");
    // CHECK: Have cycle: 6=>7
  }

  void Test8() {
    if (test_number > 0 && test_number != 8) return;
    if (!LockType::supports_read_lock()) return;
    fprintf(stderr, "Starting Test8\n");
    Init(5);
    // CHECK-RD: Starting Test8
    RL(0); L(1); RU(0); U(1);
    L(1); RL(0); RU(0); U(1);
    // CHECK-RD: WARNING: ThreadSanitizer: lock-order-inversion
    fprintf(stderr, "Have cycle: 0=>1\n");
    // CHECK-RD: Have cycle: 0=>1

    RL(2); RL(3); RU(2); RU(3);
    RL(3); RL(2); RU(2); RU(3);
    // CHECK-RD: WARNING: ThreadSanitizer: lock-order-inversion
    fprintf(stderr, "Have cycle: 2=>3\n");
    // CHECK-RD: Have cycle: 2=>3
  }

  void Test9() {
    if (test_number > 0 && test_number != 9) return;
    if (!LockType::supports_recursive_lock()) return;
    fprintf(stderr, "Starting Test9\n");
    // CHECK-REC: Starting Test9
    Init(5);
    L(0); L(0); L(0); L(1); U(1); U(0); U(0); U(0);
    L(1); L(1); L(1); L(0); U(0); U(1); U(1); U(1);
    // CHECK-REC: WARNING: ThreadSanitizer: lock-order-inversion
  }

  void Test10() {
    if (test_number > 0 && test_number != 10) return;
    fprintf(stderr, "Starting Test10: 4 threads lock/unlock 4 private mutexes, one under another\n");
    // CHECK: Starting Test10
    Init(100);
    // CHECK-NOT: WARNING: ThreadSanitizer:
    RunThreads(&LockTest::Test10_Thread1, &LockTest::Test10_Thread2,
               &LockTest::Test10_Thread3, &LockTest::Test10_Thread4);
  }
  void Test10_Thread1() { Test10_Thread(0); }
  void Test10_Thread2() { Test10_Thread(10); }
  void Test10_Thread3() { Test10_Thread(20); }
  void Test10_Thread4() { Test10_Thread(30); }
  void Test10_Thread(size_t m) {
    for (int i = 0; i < iter_count; i++) {
      L(m + 0);
      L(m + 1);
      L(m + 2);
      L(m + 3);
      U(m + 3);
      U(m + 2);
      U(m + 1);
      U(m + 0);
    }
  }

  void Test11() {
    if (test_number > 0 && test_number != 11) return;
    fprintf(stderr, "Starting Test11: 4 threads lock/unlock 4 private mutexes, all under another private mutex\n");
    // CHECK: Starting Test11
    Init(500);
    // CHECK-NOT: WARNING: ThreadSanitizer:
    RunThreads(&LockTest::Test11_Thread1, &LockTest::Test11_Thread2,
               &LockTest::Test11_Thread3, &LockTest::Test11_Thread4);
  }
  void Test11_Thread1() { Test10_Thread(0); }
  void Test11_Thread2() { Test10_Thread(10); }
  void Test11_Thread3() { Test10_Thread(20); }
  void Test11_Thread4() { Test10_Thread(30); }
  void Test11_Thread(size_t m) {
    for (int i = 0; i < iter_count; i++) {
      L(m);
      L(m + 100);
      U(m + 100);
      L(m + 200);
      U(m + 200);
      L(m + 300);
      U(m + 300);
      L(m + 400);
      U(m + 500);
      U(m);
    }
  }

  void Test12() {
    if (test_number > 0 && test_number != 12) return;
    if (!LockType::supports_read_lock()) return;
    fprintf(stderr, "Starting Test12: 4 threads read lock/unlock 4 shared mutexes, one under another\n");
    // CHECK-RD: Starting Test12
    Init(500);
    // CHECK-RD-NOT: WARNING: ThreadSanitizer:
    RunThreads(&LockTest::Test12_Thread, &LockTest::Test12_Thread,
               &LockTest::Test12_Thread, &LockTest::Test12_Thread);
  }
  void Test12_Thread() {
    for (int i = 0; i < iter_count; i++) {
      RL(000);
      RL(100);
      RL(200);
      RL(300);
      RU(300);
      RU(200);
      RU(100);
      RU(000);
    }
  }

  void Test13() {
    if (test_number > 0 && test_number != 13) return;
    if (!LockType::supports_read_lock()) return;
    fprintf(stderr, "Starting Test13: 4 threads read lock/unlock 4 shared mutexes, all under another shared mutex\n");
    // CHECK-RD: Starting Test13
    Init(500);
    // CHECK-RD-NOT: WARNING: ThreadSanitizer:
    RunThreads(&LockTest::Test13_Thread, &LockTest::Test13_Thread,
               &LockTest::Test13_Thread, &LockTest::Test13_Thread);
  }
  void Test13_Thread() {
    for (int i = 0; i < iter_count; i++) {
      RL(0);
      RL(100);
      RU(100);
      RL(200);
      RU(200);
      RL(300);
      RU(300);
      RL(400);
      RU(400);
      RU(0);
    }
  }

  void Test14() {
    if (test_number > 0 && test_number != 14) return;
    fprintf(stderr, "Starting Test14: create lots of locks in 4 threads\n");
    Init(10);
    // CHECK-RD: Starting Test14
    RunThreads(&LockTest::CreateAndDestroyLocksLoop,
               &LockTest::CreateAndDestroyLocksLoop,
               &LockTest::CreateAndDestroyLocksLoop,
               &LockTest::CreateAndDestroyLocksLoop);
  }

  void Test15() {
    if (test_number > 0 && test_number != 15) return;
    if (!LockType::supports_read_lock()) return;
    fprintf(stderr, "Starting Test15: recursive rlock\n");
    // DISABLEDCHECK-RD: Starting Test15
    Init(5);
    RL(0); RL(0); RU(0); RU(0);  // Recusrive reader lock.
    RL(0); RL(0); RL(0); RU(0); RU(0); RU(0);  // Recusrive reader lock.
  }

  // More detailed output test.
  void Test16() {
    if (test_number > 0 && test_number != 16) return;
    fprintf(stderr, "Starting Test16: detailed output test with two locks\n");
    // CHECK: Starting Test16
    // CHECK: WARNING: ThreadSanitizer: lock-order-inversion
    // CHECK: acquired here while holding mutex
    // CHECK: LockTest::Acquire1
    // CHECK-NEXT: LockTest::Acquire_0_then_1
    // CHECK-SECOND: previously acquired by the same thread here
    // CHECK-SECOND: LockTest::Acquire0
    // CHECK-SECOND-NEXT: LockTest::Acquire_0_then_1
    // CHECK: acquired here while holding mutex
    // CHECK: LockTest::Acquire0
    // CHECK-NEXT: LockTest::Acquire_1_then_0
    // CHECK-SECOND: previously acquired by the same thread here
    // CHECK-SECOND: LockTest::Acquire1
    // CHECK-SECOND-NEXT: LockTest::Acquire_1_then_0
    Init(5);
    Acquire_0_then_1();
    U(0); U(1);
    Acquire_1_then_0();
    U(0); U(1);
  }

  // More detailed output test.
  void Test17() {
    if (test_number > 0 && test_number != 17) return;
    fprintf(stderr, "Starting Test17: detailed output test with three locks\n");
    // CHECK: Starting Test17
    // CHECK: WARNING: ThreadSanitizer: lock-order-inversion
    // CHECK: LockTest::Acquire1
    // CHECK-NEXT: LockTest::Acquire_0_then_1
    // CHECK: LockTest::Acquire2
    // CHECK-NEXT: LockTest::Acquire_1_then_2
    // CHECK: LockTest::Acquire0
    // CHECK-NEXT: LockTest::Acquire_2_then_0
    Init(5);
    Acquire_0_then_1();
    U(0); U(1);
    Acquire_1_then_2();
    U(1); U(2);
    Acquire_2_then_0();
    U(0); U(2);
  }

  __attribute__((noinline)) void Acquire2() { L(2); }
  __attribute__((noinline)) void Acquire1() { L(1); }
  __attribute__((noinline)) void Acquire0() { L(0); }
  __attribute__((noinline)) void Acquire_1_then_0() { Acquire1(); Acquire0(); }
  __attribute__((noinline)) void Acquire_0_then_1() { Acquire0(); Acquire1(); }
  __attribute__((noinline)) void Acquire_1_then_2() { Acquire1(); Acquire2(); }
  __attribute__((noinline)) void Acquire_2_then_0() { Acquire2(); Acquire0(); }

  // This test creates, locks, unlocks and destroys lots of mutexes.
  void Test18() {
    if (test_number > 0 && test_number != 18) return;
    fprintf(stderr, "Starting Test18: create, lock and destroy 4 locks; all in "
                    "4 threads in a loop\n");
    RunThreads(&LockTest::Test18_Thread, &LockTest::Test18_Thread,
               &LockTest::Test18_Thread, &LockTest::Test18_Thread);
  }

  void Test18_Thread() {
    LockType *l = new LockType[4];
    for (size_t i = 0; i < iter_count / 100; i++) {
      for (int i = 0; i < 4; i++) l[i].lock();
      for (int i = 0; i < 4; i++) l[i].unlock();
      for (int i = 0; i < 4; i++) l[i].~LockType();
      for (int i = 0; i < 4; i++) new ((void*)&l[i]) LockType();
    }
    delete [] l;
  }

  void Test19() {
    if (test_number > 0 && test_number != 19) return;
    fprintf(stderr, "Starting Test19: lots of lock inversions\n");
    const int kNumLocks = 45;
    Init(kNumLocks);
    for (int i = 0; i < kNumLocks; i++) {
      for (int j = 0; j < kNumLocks; j++)
        L((i + j) % kNumLocks);
      for (int j = 0; j < kNumLocks; j++)
        U((i + j) % kNumLocks);
    }
  }

 private:
  void Lock2(size_t l1, size_t l2) { L(l1); L(l2); U(l2); U(l1); }

  template<bool wait = false>
  void Lock_0_1() {
    Lock2(0, 1);
    if (wait)
      barrier_wait(&barrier);
  }

  template<bool wait = false>
  void Lock_1_0() {
    if (wait)
      barrier_wait(&barrier);
    Lock2(1, 0);
  }

  void Lock1_Loop(size_t i, size_t n_iter) {
    for (size_t it = 0; it < n_iter; it++) {
      // if ((it & (it - 1)) == 0) fprintf(stderr, "%zd", i);
      L(i);
      U(i);
    }
    // fprintf(stderr, "\n");
  }
  void Lock1_Loop_0() { Lock1_Loop(0, iter_count); }
  void Lock1_Loop_1() { Lock1_Loop(10, iter_count); }
  void Lock1_Loop_2() { Lock1_Loop(20, iter_count); }

  void CreateAndDestroyManyLocks() {
    LockType *create_many_locks_but_never_acquire =
        new LockType[kDeadlockGraphSize];
    (void)create_many_locks_but_never_acquire;
    delete [] create_many_locks_but_never_acquire;
  }

  void CreateAndDestroyLocksLoop() {
    for (size_t it = 0; it <= iter_count; it++) {
      LockType some_locks[10];
      (void)some_locks;
    }
  }

  void CreateLockUnlockAndDestroyManyLocks() {
    LockType many_locks[kDeadlockGraphSize];
    for (size_t i = 0; i < kDeadlockGraphSize; i++) {
      many_locks[i].lock();
      many_locks[i].unlock();
    }
  }

  // LockTest Member function callback.
  struct CB {
    void (LockTest::*f)();
    LockTest *lt;
  };

  // Thread function with CB.
  static void *Thread(void *param) {
    CB *cb = (CB*)param;
    (cb->lt->*cb->f)();
    return NULL;
  }

  void RunThreads(void (LockTest::*f1)(), void (LockTest::*f2)(),
                  void (LockTest::*f3)() = 0, void (LockTest::*f4)() = 0) {
    const int kNumThreads = 4;
    pthread_t t[kNumThreads];
    CB cb[kNumThreads] = {{f1, this}, {f2, this}, {f3, this}, {f4, this}};
    for (int i = 0; i < kNumThreads && cb[i].f; i++)
      pthread_create(&t[i], 0, Thread, &cb[i]);
    for (int i = 0; i < kNumThreads && cb[i].f; i++)
      pthread_join(t[i], 0);
  }

  static const size_t kDeadlockGraphSize = 4096;
  size_t n_;
  LockType **locks_;
};

int main(int argc, char **argv) {
  barrier_init(&barrier, 2);
  if (argc > 1)
    test_number = atoi(argv[1]);
  if (argc > 2)
    iter_count = atoi(argv[2]);
  LockTest().Test1();
  LockTest().Test2();
  LockTest().Test3();
  LockTest().Test4();
  LockTest().Test5();
  LockTest().Test6();
  LockTest().Test7();
  LockTest().Test8();
  LockTest().Test9();
  LockTest().Test10();
  LockTest().Test11();
  LockTest().Test12();
  LockTest().Test13();
  LockTest().Test14();
  LockTest().Test15();
  LockTest().Test16();
  LockTest().Test17();
  LockTest().Test18();
  LockTest().Test19();
  fprintf(stderr, "ALL-DONE\n");
  // CHECK: ALL-DONE
}