valgrind/unittest/deadlock_unittest.cc

/*
  This file is part of Valgrind, a dynamic binary instrumentation
  framework.

  Copyright (C) 2008-2008 Google Inc
     opensource (at) google.com

  This program is free software; you can redistribute it and/or
  modify it under the terms of the GNU General Public License as
  published by the Free Software Foundation; either version 2 of the
  License, or (at your option) any later version.

  This program is distributed in the hope that it will be useful, but
  WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  02111-1307, USA.

  The GNU General Public License is contained in the file COPYING.
*/

// Author: Konstantin Serebryany <opensource (at) google.com>
//
// This file contains a set of unit tests for a deadlock detection tool.
//
//
//
// This test can be compiled with pthreads (default) or
// with any other library that supports threads, locks, cond vars, etc.
//
// To compile with pthreads:
//   g++  deadlock_unittest.cc -lpthread -g
//
// To compile with different library:
//   1. cp thread_wrappers_pthread.h thread_wrappers_yourlib.h
//   2. edit thread_wrappers_yourlib.h
//   3. add '-DTHREAD_WRAPPERS="thread_wrappers_yourlib.h"' to your compilation.
//
//

#include <fcntl.h>
#include <queue>
#include <signal.h>
#include <stdlib.h>
#include <string>
#include <vector>

#include "old_test_suite.h"
#include "test_utils.h"

#include <gtest/gtest.h>

/*ProducerConsumerQueue *Q[4] = {
  new ProducerConsumerQueue(INT_MAX),
  new ProducerConsumerQueue(INT_MAX),
  new ProducerConsumerQueue(INT_MAX),
  new ProducerConsumerQueue(INT_MAX)
};
Mutex mu[4];*/

/*
void PutAndWait(int *work_item, int idx) {
  // Put work_item1.
  Q[idx]->Put(work_item);

  // Wait for work_item completion.
  mu[idx].LockWhen(Condition(&ArgIsOne, work_item));
  mu[idx].Unlock();
}

void GetAndServe(int idx) {
  // Get an item.
  int *item = reinterpret_cast<int*>(Q[idx]->Get());

  // Handle work item and signal completion.
  mu[idx].Lock();
  *item = 1;
  mu[idx].Unlock();
}


bool TryGetAndServe(int idx) {
  // Get an item.
  int *item;
  if (Q[idx]->TryGet(reinterpret_cast<void**>(&item))) {
    // Handle work item and signal completion.
    mu[idx].Lock();
    *item = 1;
    mu[idx].Unlock();
    return true;
  } else {
    return false;
  }
}*/

// Set of threads that execute the same function.
class MyThreadSet {
 public:
  typedef void (*F) (void);
  MyThreadSet(F f, int count)
    : count_(count) {
    CHECK(count_ >= 1 && count_ <= 1000);
    ar_ = new MyThread* [count_];
    for (int i = 0; i < count_; i++) {
      ar_[i] = new MyThread(f);
    }
  }
  void Start() {
    for (int i = 0; i < count_; i++) {
      ar_[i]->Start();
    }
  }
  void Join() {
    for (int i = 0; i < count_; i++) {
      ar_[i]->Join();
    }
  }
  ~MyThreadSet() {
    for (int i = 0; i < count_; i++) {
      delete ar_[i];
    }
    delete ar_;
  }

 private:
  MyThread **ar_;
  int count_;
};

int ThreadId() {
  static Mutex mu;
  static map<pthread_t, int> m;

  int id;
  pthread_t self = pthread_self();

  mu.Lock();
  map<pthread_t, int>::iterator it = m.find(self);
  if (it != m.end()) {
    id = it->second;
  } else {
    id = m.size();
    m[self] = id;
  }
  mu.Unlock();
  return id;
}

// test00: {{{1
namespace test00 {
void Run() {
  printf("test00: negative\n");
}
REGISTER_TEST(Run, 00)
}  // namespace test00

// test01: Simple deadlock, 2 threads. {{{1
namespace test01 {
Mutex mu1, mu2;
void Worker1()  {
  mu1.Lock();
  mu2.Lock();
  mu2.Unlock();
  mu1.Unlock();
}
void Worker2()  {
  usleep(1000);
  mu2.Lock();
  mu1.Lock();
  mu1.Unlock();
  mu2.Unlock();
}
void Run() {
  MyThreadArray t(Worker1, Worker2);
  t.Start();
  t.Join();
  printf("test01: positive, simple deadlock\n");
}
REGISTER_TEST(Run, 01)
}  // namespace test01

// test02: Simple deadlock, 4 threads. {{{1
namespace test02 {
Mutex mu1, mu2, mu3, mu4;
void Worker1()  {
  mu1.Lock();   mu2.Lock();
  mu2.Unlock(); mu1.Unlock();
}
void Worker2()  {
  usleep(1000);
  mu2.Lock();   mu3.Lock();
  mu3.Unlock(); mu2.Unlock();
}
void Worker3()  {
  usleep(2000);
  mu3.Lock();   mu4.Lock();
  mu4.Unlock(); mu3.Unlock();
}
void Worker4()  {
  usleep(3000);
  mu4.Lock();   mu1.Lock();
  mu1.Unlock(); mu4.Unlock();
}
void Run() {
  MyThreadArray t(Worker1, Worker2, Worker3, Worker4);
  t.Start();
  t.Join();
  printf("test02: positive, simple deadlock\n");
}
REGISTER_TEST(Run, 02)
}  // namespace test02
/*
// test03: Queue deadlock test, 2 workers. {{{1
// This test will deadlock for sure.
namespace  test03 {

void Worker1() {
  int *item = new int (0);
  PutAndWait(item, 0);
  GetAndServe(1);
}
void Worker2() {
  int *item = new int (0);
  PutAndWait(item, 1);
  GetAndServe(0);
}
void Run() {
  printf("test03: queue deadlock\n");
  MyThreadArray t(Worker1, Worker2);
  t.Start();
  t.Join();
}
REGISTER_TEST(Run, 03)
}  // namespace test03

// test04: Queue deadlock test, 3 workers. {{{1
// This test will deadlock for sure.
namespace  test04 {

void Worker1() {
  int *item = new int (0);
  PutAndWait(item, 0);
  GetAndServe(1);
}
void Worker2() {
  int *item = new int (0);
  PutAndWait(item, 1);
  GetAndServe(2);
}

void Worker3() {
  int *item = new int (0);
  PutAndWait(item, 2);
  GetAndServe(0);
}

void Run() {
  printf("test04: queue deadlock\n");
  MyThreadArray t(Worker1, Worker2, Worker3);
  t.Start();
  t.Join();
}
REGISTER_TEST(Run, 04)
}  // namespace test04

// test05: Queue deadlock test, 1 worker set. {{{1
// This test will deadlock after some number of served requests.
namespace  test05 {

int item_number = 0;  // Just for debug prints.


// This function randomly enqueues work and waits on it or serves a piece of work.
void Worker() {
  while(true) {
    int action = rand() % 100;
    if (action <= 1) {        // PutAndWait.
      int n = __sync_add_and_fetch(&item_number, 1);
      int *item = new int(0);
      PutAndWait(item, 0);
      if ((n % 10000) == 0) {
        printf("Done %d\n", n);
      }
      delete item;
    } else {                 // GetAndServe.
      TryGetAndServe(0);
    }
  }
}


void Run() {
  printf("test05: queue deadlock\n");
  MyThreadSet t(Worker, 5);
  t.Start();
  t.Join();
}
REGISTER_TEST(Run, 05)
}  // namespace test05

// test06: Queue deadlock test, 3 worker sets. {{{1
// This test will deadlock after some number of served requests.
namespace  test06 {

int item_number[3] = {0, 0, 0};  // Just for debug prints.

// This function randomly enqueues work to queue 'put_queue' and waits on it
// or serves a piece of work from queue 'get_queue'.
void Worker(int put_queue, int get_queue) {
  while(true) {
    int action = rand() % 1000;
    if (action <= 100) {        // PutAndWait.
      int n = __sync_add_and_fetch(&item_number[put_queue], 1);
      int *item = new int(0);
      PutAndWait(item, put_queue);
      if ((n % 1000) == 0) {
        printf("Q[%d]: done %d\n", put_queue, n);
      }
      delete item;
    } else {                 // TryGetAndServe.
      TryGetAndServe(get_queue);
    }
  }
}

void Worker1() { Worker(0, 1); }
void Worker2() { Worker(1, 2); }
void Worker3() { Worker(2, 0); }

void Run() {
  printf("test06: queue deadlock\n");
  MyThreadSet t1(Worker1, 4);
  MyThreadSet t2(Worker2, 4);
  MyThreadSet t3(Worker3, 4);
  t1.Start();
  t2.Start();
  t3.Start();
  t1.Join();
  t2.Join();
  t3.Join();
}
REGISTER_TEST(Run, 06)
}  // namespace test06
// test07: Simple deadlock which actually deadlocks, 2 threads. {{{1
namespace test07 {
Mutex mu1, mu2;
void Worker1()  {
  mu1.Lock();
  usleep(100000);
  mu2.Lock();
  mu2.Unlock();
  mu1.Unlock();
}
void Worker2()  {
  mu2.Lock();
  usleep(100000);
  mu1.Lock();
  mu1.Unlock();
  mu2.Unlock();
}
void Run() {
  mu1.EnableDebugLog("mu1");
  mu2.EnableDebugLog("mu2");
  printf("test07: positive, simple deadlock\n");
  MyThreadArray t(Worker1, Worker2);
  t.Start();
  t.Join();
}
REGISTER_TEST(Run, 07)
}  // namespace test07

*/