1/*
2  This file is part of Valgrind, a dynamic binary instrumentation
3  framework.
4
5  Copyright (C) 2008-2008 Google Inc
6     opensource@google.com
7
8  This program is free software; you can redistribute it and/or
9  modify it under the terms of the GNU General Public License as
10  published by the Free Software Foundation; either version 2 of the
11  License, or (at your option) any later version.
12
13  This program is distributed in the hope that it will be useful, but
14  WITHOUT ANY WARRANTY; without even the implied warranty of
15  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
16  General Public License for more details.
17
18  You should have received a copy of the GNU General Public License
19  along with this program; if not, write to the Free Software
20  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
21  02111-1307, USA.
22
23  The GNU General Public License is contained in the file COPYING.
24*/
25
26// Author: Konstantin Serebryany <opensource@google.com>
27//
28// This file contains a set of unit tests for a deadlock detection tool.
29//
30//
31//
32// This test can be compiled with pthreads (default) or
33// with any other library that supports threads, locks, cond vars, etc.
34//
35// To compile with pthreads:
36//   g++  deadlock_unittest.cc -lpthread -g
37//
38// To compile with different library:
39//   1. cp thread_wrappers_pthread.h thread_wrappers_yourlib.h
40//   2. edit thread_wrappers_yourlib.h
41//   3. add '-DTHREAD_WRAPPERS="thread_wrappers_yourlib.h"' to your compilation.
42//
43//
44
45#include <fcntl.h>
46#include <queue>
47#include <signal.h>
48#include <stdlib.h>
49#include <string>
50#include <vector>
51
52#include "old_test_suite.h"
53#include "test_utils.h"
54
55#include <gtest/gtest.h>
56
57/*ProducerConsumerQueue *Q[4] = {
58  new ProducerConsumerQueue(INT_MAX),
59  new ProducerConsumerQueue(INT_MAX),
60  new ProducerConsumerQueue(INT_MAX),
61  new ProducerConsumerQueue(INT_MAX)
62};
63Mutex mu[4];*/
64
65/*
66void PutAndWait(int *work_item, int idx) {
67  // Put work_item1.
68  Q[idx]->Put(work_item);
69
70  // Wait for work_item completion.
71  mu[idx].LockWhen(Condition(&ArgIsOne, work_item));
72  mu[idx].Unlock();
73}
74
75void GetAndServe(int idx) {
76  // Get an item.
77  int *item = reinterpret_cast<int*>(Q[idx]->Get());
78
79  // Handle work item and signal completion.
80  mu[idx].Lock();
81  *item = 1;
82  mu[idx].Unlock();
83}
84
85
86bool TryGetAndServe(int idx) {
87  // Get an item.
88  int *item;
89  if (Q[idx]->TryGet(reinterpret_cast<void**>(&item))) {
90    // Handle work item and signal completion.
91    mu[idx].Lock();
92    *item = 1;
93    mu[idx].Unlock();
94    return true;
95  } else {
96    return false;
97  }
98}*/
99
100// Set of threads that execute the same function.
101class MyThreadSet {
102 public:
103  typedef void (*F) (void);
104  MyThreadSet(F f, int count)
105    : count_(count) {
106    CHECK(count_ >= 1 && count_ <= 1000);
107    ar_ = new MyThread* [count_];
108    for (int i = 0; i < count_; i++) {
109      ar_[i] = new MyThread(f);
110    }
111  }
112  void Start() {
113    for (int i = 0; i < count_; i++) {
114      ar_[i]->Start();
115    }
116  }
117  void Join() {
118    for (int i = 0; i < count_; i++) {
119      ar_[i]->Join();
120    }
121  }
122  ~MyThreadSet() {
123    for (int i = 0; i < count_; i++) {
124      delete ar_[i];
125    }
126    delete ar_;
127  }
128
129 private:
130  MyThread **ar_;
131  int count_;
132};
133
134int ThreadId() {
135  static Mutex mu;
136  static map<pthread_t, int> m;
137
138  int id;
139  pthread_t self = pthread_self();
140
141  mu.Lock();
142  map<pthread_t, int>::iterator it = m.find(self);
143  if (it != m.end()) {
144    id = it->second;
145  } else {
146    id = m.size();
147    m[self] = id;
148  }
149  mu.Unlock();
150  return id;
151}
152
153// test00: {{{1
154namespace test00 {
155void Run() {
156  printf("test00: negative\n");
157}
158REGISTER_TEST(Run, 00)
159}  // namespace test00
160
161// test01: Simple deadlock, 2 threads. {{{1
162namespace test01 {
163Mutex mu1, mu2;
164void Worker1()  {
165  mu1.Lock();
166  mu2.Lock();
167  mu2.Unlock();
168  mu1.Unlock();
169}
170void Worker2()  {
171  usleep(1000);
172  mu2.Lock();
173  mu1.Lock();
174  mu1.Unlock();
175  mu2.Unlock();
176}
177void Run() {
178  MyThreadArray t(Worker1, Worker2);
179  t.Start();
180  t.Join();
181  printf("test01: positive, simple deadlock\n");
182}
183REGISTER_TEST(Run, 01)
184}  // namespace test01
185
186// test02: Simple deadlock, 4 threads. {{{1
187namespace test02 {
188Mutex mu1, mu2, mu3, mu4;
189void Worker1()  {
190  mu1.Lock();   mu2.Lock();
191  mu2.Unlock(); mu1.Unlock();
192}
193void Worker2()  {
194  usleep(1000);
195  mu2.Lock();   mu3.Lock();
196  mu3.Unlock(); mu2.Unlock();
197}
198void Worker3()  {
199  usleep(2000);
200  mu3.Lock();   mu4.Lock();
201  mu4.Unlock(); mu3.Unlock();
202}
203void Worker4()  {
204  usleep(3000);
205  mu4.Lock();   mu1.Lock();
206  mu1.Unlock(); mu4.Unlock();
207}
208void Run() {
209  MyThreadArray t(Worker1, Worker2, Worker3, Worker4);
210  t.Start();
211  t.Join();
212  printf("test02: positive, simple deadlock\n");
213}
214REGISTER_TEST(Run, 02)
215}  // namespace test02
216/*
217// test03: Queue deadlock test, 2 workers. {{{1
218// This test will deadlock for sure.
219namespace  test03 {
220
221void Worker1() {
222  int *item = new int (0);
223  PutAndWait(item, 0);
224  GetAndServe(1);
225}
226void Worker2() {
227  int *item = new int (0);
228  PutAndWait(item, 1);
229  GetAndServe(0);
230}
231void Run() {
232  printf("test03: queue deadlock\n");
233  MyThreadArray t(Worker1, Worker2);
234  t.Start();
235  t.Join();
236}
237REGISTER_TEST(Run, 03)
238}  // namespace test03
239
240// test04: Queue deadlock test, 3 workers. {{{1
241// This test will deadlock for sure.
242namespace  test04 {
243
244void Worker1() {
245  int *item = new int (0);
246  PutAndWait(item, 0);
247  GetAndServe(1);
248}
249void Worker2() {
250  int *item = new int (0);
251  PutAndWait(item, 1);
252  GetAndServe(2);
253}
254
255void Worker3() {
256  int *item = new int (0);
257  PutAndWait(item, 2);
258  GetAndServe(0);
259}
260
261void Run() {
262  printf("test04: queue deadlock\n");
263  MyThreadArray t(Worker1, Worker2, Worker3);
264  t.Start();
265  t.Join();
266}
267REGISTER_TEST(Run, 04)
268}  // namespace test04
269
270// test05: Queue deadlock test, 1 worker set. {{{1
271// This test will deadlock after some number of served requests.
272namespace  test05 {
273
274int item_number = 0;  // Just for debug prints.
275
276
277// This function randomly enqueues work and waits on it or serves a piece of work.
278void Worker() {
279  while(true) {
280    int action = rand() % 100;
281    if (action <= 1) {        // PutAndWait.
282      int n = __sync_add_and_fetch(&item_number, 1);
283      int *item = new int(0);
284      PutAndWait(item, 0);
285      if ((n % 10000) == 0) {
286        printf("Done %d\n", n);
287      }
288      delete item;
289    } else {                 // GetAndServe.
290      TryGetAndServe(0);
291    }
292  }
293}
294
295
296void Run() {
297  printf("test05: queue deadlock\n");
298  MyThreadSet t(Worker, 5);
299  t.Start();
300  t.Join();
301}
302REGISTER_TEST(Run, 05)
303}  // namespace test05
304
305// test06: Queue deadlock test, 3 worker sets. {{{1
306// This test will deadlock after some number of served requests.
307namespace  test06 {
308
309int item_number[3] = {0, 0, 0};  // Just for debug prints.
310
311// This function randomly enqueues work to queue 'put_queue' and waits on it
312// or serves a piece of work from queue 'get_queue'.
313void Worker(int put_queue, int get_queue) {
314  while(true) {
315    int action = rand() % 1000;
316    if (action <= 100) {        // PutAndWait.
317      int n = __sync_add_and_fetch(&item_number[put_queue], 1);
318      int *item = new int(0);
319      PutAndWait(item, put_queue);
320      if ((n % 1000) == 0) {
321        printf("Q[%d]: done %d\n", put_queue, n);
322      }
323      delete item;
324    } else {                 // TryGetAndServe.
325      TryGetAndServe(get_queue);
326    }
327  }
328}
329
330void Worker1() { Worker(0, 1); }
331void Worker2() { Worker(1, 2); }
332void Worker3() { Worker(2, 0); }
333
334void Run() {
335  printf("test06: queue deadlock\n");
336  MyThreadSet t1(Worker1, 4);
337  MyThreadSet t2(Worker2, 4);
338  MyThreadSet t3(Worker3, 4);
339  t1.Start();
340  t2.Start();
341  t3.Start();
342  t1.Join();
343  t2.Join();
344  t3.Join();
345}
346REGISTER_TEST(Run, 06)
347}  // namespace test06
348// test07: Simple deadlock which actually deadlocks, 2 threads. {{{1
349namespace test07 {
350Mutex mu1, mu2;
351void Worker1()  {
352  mu1.Lock();
353  usleep(100000);
354  mu2.Lock();
355  mu2.Unlock();
356  mu1.Unlock();
357}
358void Worker2()  {
359  mu2.Lock();
360  usleep(100000);
361  mu1.Lock();
362  mu1.Unlock();
363  mu2.Unlock();
364}
365void Run() {
366  mu1.EnableDebugLog("mu1");
367  mu2.EnableDebugLog("mu2");
368  printf("test07: positive, simple deadlock\n");
369  MyThreadArray t(Worker1, Worker2);
370  t.Start();
371  t.Join();
372}
373REGISTER_TEST(Run, 07)
374}  // namespace test07
375
376*/
377