unittest/deadlock_unittest.cc - platform/external/valgrind - Git at Google

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

   Copyright (C) 2008-2008 Google Inc
      opensource@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@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

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

	Copyright (C) 2008-2008 Google Inc
	opensource@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@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

	*/