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 };
63 Mutex mu[4];*/
64
65 /*
66 void 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
75 void 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
86 bool 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.
101 class MyThreadSet {
102 public:
103 typedef void (*F) (void);
MyThreadSet(F f,int count)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 }
Start()112 void Start() {
113 for (int i = 0; i < count_; i++) {
114 ar_[i]->Start();
115 }
116 }
Join()117 void Join() {
118 for (int i = 0; i < count_; i++) {
119 ar_[i]->Join();
120 }
121 }
~MyThreadSet()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
ThreadId()134 int 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
154 namespace test00 {
Run()155 void Run() {
156 printf("test00: negative\n");
157 }
158 REGISTER_TEST(Run, 00)
159 } // namespace test00
160
161 // test01: Simple deadlock, 2 threads. {{{1
162 namespace test01 {
163 Mutex mu1, mu2;
Worker1()164 void Worker1() {
165 mu1.Lock();
166 mu2.Lock();
167 mu2.Unlock();
168 mu1.Unlock();
169 }
Worker2()170 void Worker2() {
171 usleep(1000);
172 mu2.Lock();
173 mu1.Lock();
174 mu1.Unlock();
175 mu2.Unlock();
176 }
Run()177 void Run() {
178 MyThreadArray t(Worker1, Worker2);
179 t.Start();
180 t.Join();
181 printf("test01: positive, simple deadlock\n");
182 }
183 REGISTER_TEST(Run, 01)
184 } // namespace test01
185
186 // test02: Simple deadlock, 4 threads. {{{1
187 namespace test02 {
188 Mutex mu1, mu2, mu3, mu4;
Worker1()189 void Worker1() {
190 mu1.Lock(); mu2.Lock();
191 mu2.Unlock(); mu1.Unlock();
192 }
Worker2()193 void Worker2() {
194 usleep(1000);
195 mu2.Lock(); mu3.Lock();
196 mu3.Unlock(); mu2.Unlock();
197 }
Worker3()198 void Worker3() {
199 usleep(2000);
200 mu3.Lock(); mu4.Lock();
201 mu4.Unlock(); mu3.Unlock();
202 }
Worker4()203 void Worker4() {
204 usleep(3000);
205 mu4.Lock(); mu1.Lock();
206 mu1.Unlock(); mu4.Unlock();
207 }
Run()208 void Run() {
209 MyThreadArray t(Worker1, Worker2, Worker3, Worker4);
210 t.Start();
211 t.Join();
212 printf("test02: positive, simple deadlock\n");
213 }
214 REGISTER_TEST(Run, 02)
215 } // namespace test02
216 /*
217 // test03: Queue deadlock test, 2 workers. {{{1
218 // This test will deadlock for sure.
219 namespace test03 {
220
221 void Worker1() {
222 int *item = new int (0);
223 PutAndWait(item, 0);
224 GetAndServe(1);
225 }
226 void Worker2() {
227 int *item = new int (0);
228 PutAndWait(item, 1);
229 GetAndServe(0);
230 }
231 void Run() {
232 printf("test03: queue deadlock\n");
233 MyThreadArray t(Worker1, Worker2);
234 t.Start();
235 t.Join();
236 }
237 REGISTER_TEST(Run, 03)
238 } // namespace test03
239
240 // test04: Queue deadlock test, 3 workers. {{{1
241 // This test will deadlock for sure.
242 namespace test04 {
243
244 void Worker1() {
245 int *item = new int (0);
246 PutAndWait(item, 0);
247 GetAndServe(1);
248 }
249 void Worker2() {
250 int *item = new int (0);
251 PutAndWait(item, 1);
252 GetAndServe(2);
253 }
254
255 void Worker3() {
256 int *item = new int (0);
257 PutAndWait(item, 2);
258 GetAndServe(0);
259 }
260
261 void Run() {
262 printf("test04: queue deadlock\n");
263 MyThreadArray t(Worker1, Worker2, Worker3);
264 t.Start();
265 t.Join();
266 }
267 REGISTER_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.
272 namespace test05 {
273
274 int 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.
278 void 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
296 void Run() {
297 printf("test05: queue deadlock\n");
298 MyThreadSet t(Worker, 5);
299 t.Start();
300 t.Join();
301 }
302 REGISTER_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.
307 namespace test06 {
308
309 int 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'.
313 void 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
330 void Worker1() { Worker(0, 1); }
331 void Worker2() { Worker(1, 2); }
332 void Worker3() { Worker(2, 0); }
333
334 void 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 }
346 REGISTER_TEST(Run, 06)
347 } // namespace test06
348 // test07: Simple deadlock which actually deadlocks, 2 threads. {{{1
349 namespace test07 {
350 Mutex mu1, mu2;
351 void Worker1() {
352 mu1.Lock();
353 usleep(100000);
354 mu2.Lock();
355 mu2.Unlock();
356 mu1.Unlock();
357 }
358 void Worker2() {
359 mu2.Lock();
360 usleep(100000);
361 mu1.Lock();
362 mu1.Unlock();
363 mu2.Unlock();
364 }
365 void 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 }
373 REGISTER_TEST(Run, 07)
374 } // namespace test07
375
376 */
377