1//===-- sanitizer_deadlock_detector_test.cc -------------------------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file is a part of Sanitizer runtime.
11// Tests for sanitizer_deadlock_detector.h
12//
13//===----------------------------------------------------------------------===//
14#include "sanitizer_common/sanitizer_deadlock_detector.h"
15
16#include "sanitizer_test_utils.h"
17
18#include "gtest/gtest.h"
19
20#include <algorithm>
21#include <vector>
22#include <set>
23
24using namespace __sanitizer;
25using namespace std;
26
27typedef BasicBitVector<u8> BV1;
28typedef BasicBitVector<> BV2;
29typedef TwoLevelBitVector<> BV3;
30typedef TwoLevelBitVector<3, BasicBitVector<u8> > BV4;
31
32// Poor man's unique_ptr.
33template<class BV>
34struct ScopedDD {
35  ScopedDD() {
36    dp = new DeadlockDetector<BV>;
37    dp->clear();
38    dtls.clear();
39  }
40  ~ScopedDD() { delete dp; }
41  DeadlockDetector<BV> *dp;
42  DeadlockDetectorTLS<BV> dtls;
43};
44
45template <class BV>
46void RunBasicTest() {
47  uptr path[10];
48  ScopedDD<BV> sdd;
49  DeadlockDetector<BV> &d = *sdd.dp;
50  DeadlockDetectorTLS<BV> &dtls = sdd.dtls;
51  set<uptr> s;
52  for (size_t i = 0; i < d.size() * 3; i++) {
53    uptr node = d.newNode(0);
54    EXPECT_TRUE(s.insert(node).second);
55  }
56
57  d.clear();
58  s.clear();
59  // Add size() nodes.
60  for (size_t i = 0; i < d.size(); i++) {
61    uptr node = d.newNode(0);
62    EXPECT_TRUE(s.insert(node).second);
63  }
64  // Remove all nodes.
65  for (set<uptr>::iterator it = s.begin(); it != s.end(); ++it)
66    d.removeNode(*it);
67  // The nodes should be reused.
68  for (size_t i = 0; i < d.size(); i++) {
69    uptr node = d.newNode(0);
70    EXPECT_FALSE(s.insert(node).second);
71  }
72
73  // Cycle: n1->n2->n1
74  {
75    d.clear();
76    dtls.clear();
77    uptr n1 = d.newNode(1);
78    uptr n2 = d.newNode(2);
79    EXPECT_FALSE(d.onLock(&dtls, n1));
80    EXPECT_FALSE(d.onLock(&dtls, n2));
81    d.onUnlock(&dtls, n2);
82    d.onUnlock(&dtls, n1);
83
84    EXPECT_FALSE(d.onLock(&dtls, n2));
85    EXPECT_EQ(0U, d.findPathToLock(&dtls, n1, path, 1));
86    EXPECT_EQ(2U, d.findPathToLock(&dtls, n1, path, 10));
87    EXPECT_EQ(2U, d.findPathToLock(&dtls, n1, path, 2));
88    EXPECT_TRUE(d.onLock(&dtls, n1));
89    EXPECT_EQ(path[0], n1);
90    EXPECT_EQ(path[1], n2);
91    EXPECT_EQ(d.getData(n1), 1U);
92    EXPECT_EQ(d.getData(n2), 2U);
93    d.onUnlock(&dtls, n1);
94    d.onUnlock(&dtls, n2);
95  }
96
97  // Cycle: n1->n2->n3->n1
98  {
99    d.clear();
100    dtls.clear();
101    uptr n1 = d.newNode(1);
102    uptr n2 = d.newNode(2);
103    uptr n3 = d.newNode(3);
104
105    EXPECT_FALSE(d.onLock(&dtls, n1));
106    EXPECT_FALSE(d.onLock(&dtls, n2));
107    d.onUnlock(&dtls, n2);
108    d.onUnlock(&dtls, n1);
109
110    EXPECT_FALSE(d.onLock(&dtls, n2));
111    EXPECT_FALSE(d.onLock(&dtls, n3));
112    d.onUnlock(&dtls, n3);
113    d.onUnlock(&dtls, n2);
114
115    EXPECT_FALSE(d.onLock(&dtls, n3));
116    EXPECT_EQ(0U, d.findPathToLock(&dtls, n1, path, 2));
117    EXPECT_EQ(3U, d.findPathToLock(&dtls, n1, path, 10));
118    EXPECT_TRUE(d.onLock(&dtls, n1));
119    EXPECT_EQ(path[0], n1);
120    EXPECT_EQ(path[1], n2);
121    EXPECT_EQ(path[2], n3);
122    EXPECT_EQ(d.getData(n1), 1U);
123    EXPECT_EQ(d.getData(n2), 2U);
124    EXPECT_EQ(d.getData(n3), 3U);
125    d.onUnlock(&dtls, n1);
126    d.onUnlock(&dtls, n3);
127  }
128}
129
130TEST(DeadlockDetector, BasicTest) {
131  RunBasicTest<BV1>();
132  RunBasicTest<BV2>();
133  RunBasicTest<BV3>();
134  RunBasicTest<BV4>();
135}
136
137template <class BV>
138void RunRemoveNodeTest() {
139  ScopedDD<BV> sdd;
140  DeadlockDetector<BV> &d = *sdd.dp;
141  DeadlockDetectorTLS<BV> &dtls = sdd.dtls;
142
143  uptr l0 = d.newNode(0);
144  uptr l1 = d.newNode(1);
145  uptr l2 = d.newNode(2);
146  uptr l3 = d.newNode(3);
147  uptr l4 = d.newNode(4);
148  uptr l5 = d.newNode(5);
149
150  // l0=>l1=>l2
151  d.onLock(&dtls, l0);
152  d.onLock(&dtls, l1);
153  d.onLock(&dtls, l2);
154  d.onUnlock(&dtls, l1);
155  d.onUnlock(&dtls, l0);
156  d.onUnlock(&dtls, l2);
157  // l3=>l4=>l5
158  d.onLock(&dtls, l3);
159  d.onLock(&dtls, l4);
160  d.onLock(&dtls, l5);
161  d.onUnlock(&dtls, l4);
162  d.onUnlock(&dtls, l3);
163  d.onUnlock(&dtls, l5);
164
165  set<uptr> locks;
166  locks.insert(l0);
167  locks.insert(l1);
168  locks.insert(l2);
169  locks.insert(l3);
170  locks.insert(l4);
171  locks.insert(l5);
172  for (uptr i = 6; i < d.size(); i++) {
173    uptr lt = d.newNode(i);
174    locks.insert(lt);
175    d.onLock(&dtls, lt);
176    d.onUnlock(&dtls, lt);
177    d.removeNode(lt);
178  }
179  EXPECT_EQ(locks.size(), d.size());
180  // l2=>l0
181  EXPECT_FALSE(d.onLock(&dtls, l2));
182  EXPECT_TRUE(d.onLock(&dtls, l0));
183  d.onUnlock(&dtls, l2);
184  d.onUnlock(&dtls, l0);
185  // l4=>l3
186  EXPECT_FALSE(d.onLock(&dtls, l4));
187  EXPECT_TRUE(d.onLock(&dtls, l3));
188  d.onUnlock(&dtls, l4);
189  d.onUnlock(&dtls, l3);
190
191  EXPECT_EQ(d.size(), d.testOnlyGetEpoch());
192
193  d.removeNode(l2);
194  d.removeNode(l3);
195  locks.clear();
196  // make sure no edges from or to l0,l1,l4,l5 left.
197  for (uptr i = 4; i < d.size(); i++) {
198    uptr lt = d.newNode(i);
199    locks.insert(lt);
200    uptr a, b;
201    // l0 => lt?
202    a = l0; b = lt;
203    EXPECT_FALSE(d.onLock(&dtls, a));
204    EXPECT_FALSE(d.onLock(&dtls, b));
205    d.onUnlock(&dtls, a);
206    d.onUnlock(&dtls, b);
207    // l1 => lt?
208    a = l1; b = lt;
209    EXPECT_FALSE(d.onLock(&dtls, a));
210    EXPECT_FALSE(d.onLock(&dtls, b));
211    d.onUnlock(&dtls, a);
212    d.onUnlock(&dtls, b);
213    // lt => l4?
214    a = lt; b = l4;
215    EXPECT_FALSE(d.onLock(&dtls, a));
216    EXPECT_FALSE(d.onLock(&dtls, b));
217    d.onUnlock(&dtls, a);
218    d.onUnlock(&dtls, b);
219    // lt => l5?
220    a = lt; b = l5;
221    EXPECT_FALSE(d.onLock(&dtls, a));
222    EXPECT_FALSE(d.onLock(&dtls, b));
223    d.onUnlock(&dtls, a);
224    d.onUnlock(&dtls, b);
225
226    d.removeNode(lt);
227  }
228  // Still the same epoch.
229  EXPECT_EQ(d.size(), d.testOnlyGetEpoch());
230  EXPECT_EQ(locks.size(), d.size() - 4);
231  // l2 and l3 should have ben reused.
232  EXPECT_EQ(locks.count(l2), 1U);
233  EXPECT_EQ(locks.count(l3), 1U);
234}
235
236TEST(DeadlockDetector, RemoveNodeTest) {
237  RunRemoveNodeTest<BV1>();
238  RunRemoveNodeTest<BV2>();
239  RunRemoveNodeTest<BV3>();
240  RunRemoveNodeTest<BV4>();
241}
242
243template <class BV>
244void RunMultipleEpochsTest() {
245  ScopedDD<BV> sdd;
246  DeadlockDetector<BV> &d = *sdd.dp;
247  DeadlockDetectorTLS<BV> &dtls = sdd.dtls;
248
249  set<uptr> locks;
250  for (uptr i = 0; i < d.size(); i++) {
251    EXPECT_TRUE(locks.insert(d.newNode(i)).second);
252  }
253  EXPECT_EQ(d.testOnlyGetEpoch(), d.size());
254  for (uptr i = 0; i < d.size(); i++) {
255    EXPECT_TRUE(locks.insert(d.newNode(i)).second);
256    EXPECT_EQ(d.testOnlyGetEpoch(), d.size() * 2);
257  }
258  locks.clear();
259
260  uptr l0 = d.newNode(0);
261  uptr l1 = d.newNode(0);
262  d.onLock(&dtls, l0);
263  d.onLock(&dtls, l1);
264  d.onUnlock(&dtls, l0);
265  EXPECT_EQ(d.testOnlyGetEpoch(), 3 * d.size());
266  for (uptr i = 0; i < d.size(); i++) {
267    EXPECT_TRUE(locks.insert(d.newNode(i)).second);
268  }
269  EXPECT_EQ(d.testOnlyGetEpoch(), 4 * d.size());
270
271#if !SANITIZER_DEBUG
272  // EXPECT_DEATH clones a thread with 4K stack,
273  // which is overflown by tsan memory accesses functions in debug mode.
274
275  // Can not handle the locks from the previous epoch.
276  // The caller should update the lock id.
277  EXPECT_DEATH(d.onLock(&dtls, l0), "CHECK failed.*current_epoch_");
278#endif
279}
280
281TEST(DeadlockDetector, MultipleEpochsTest) {
282  RunMultipleEpochsTest<BV1>();
283  RunMultipleEpochsTest<BV2>();
284  RunMultipleEpochsTest<BV3>();
285  RunMultipleEpochsTest<BV4>();
286}
287
288template <class BV>
289void RunCorrectEpochFlush() {
290  ScopedDD<BV> sdd;
291  DeadlockDetector<BV> &d = *sdd.dp;
292  DeadlockDetectorTLS<BV> &dtls = sdd.dtls;
293  vector<uptr> locks1;
294  for (uptr i = 0; i < d.size(); i++)
295    locks1.push_back(d.newNode(i));
296  EXPECT_EQ(d.testOnlyGetEpoch(), d.size());
297  d.onLock(&dtls, locks1[3]);
298  d.onLock(&dtls, locks1[4]);
299  d.onLock(&dtls, locks1[5]);
300
301  // We have a new epoch, old locks in dtls will have to be forgotten.
302  uptr l0 = d.newNode(0);
303  EXPECT_EQ(d.testOnlyGetEpoch(), d.size() * 2);
304  uptr l1 = d.newNode(0);
305  EXPECT_EQ(d.testOnlyGetEpoch(), d.size() * 2);
306  d.onLock(&dtls, l0);
307  d.onLock(&dtls, l1);
308  EXPECT_TRUE(d.testOnlyHasEdgeRaw(0, 1));
309  EXPECT_FALSE(d.testOnlyHasEdgeRaw(1, 0));
310  EXPECT_FALSE(d.testOnlyHasEdgeRaw(3, 0));
311  EXPECT_FALSE(d.testOnlyHasEdgeRaw(4, 0));
312  EXPECT_FALSE(d.testOnlyHasEdgeRaw(5, 0));
313}
314
315TEST(DeadlockDetector, CorrectEpochFlush) {
316  RunCorrectEpochFlush<BV1>();
317  RunCorrectEpochFlush<BV2>();
318}
319
320template <class BV>
321void RunTryLockTest() {
322  ScopedDD<BV> sdd;
323  DeadlockDetector<BV> &d = *sdd.dp;
324  DeadlockDetectorTLS<BV> &dtls = sdd.dtls;
325
326  uptr l0 = d.newNode(0);
327  uptr l1 = d.newNode(0);
328  uptr l2 = d.newNode(0);
329  EXPECT_FALSE(d.onLock(&dtls, l0));
330  EXPECT_FALSE(d.onTryLock(&dtls, l1));
331  EXPECT_FALSE(d.onLock(&dtls, l2));
332  EXPECT_TRUE(d.isHeld(&dtls, l0));
333  EXPECT_TRUE(d.isHeld(&dtls, l1));
334  EXPECT_TRUE(d.isHeld(&dtls, l2));
335  EXPECT_FALSE(d.testOnlyHasEdge(l0, l1));
336  EXPECT_TRUE(d.testOnlyHasEdge(l1, l2));
337  d.onUnlock(&dtls, l0);
338  d.onUnlock(&dtls, l1);
339  d.onUnlock(&dtls, l2);
340}
341
342TEST(DeadlockDetector, TryLockTest) {
343  RunTryLockTest<BV1>();
344  RunTryLockTest<BV2>();
345}
346
347template <class BV>
348void RunOnFirstLockTest() {
349  ScopedDD<BV> sdd;
350  DeadlockDetector<BV> &d = *sdd.dp;
351  DeadlockDetectorTLS<BV> &dtls = sdd.dtls;
352
353  uptr l0 = d.newNode(0);
354  uptr l1 = d.newNode(0);
355  EXPECT_FALSE(d.onFirstLock(&dtls, l0));  // dtls has old epoch.
356  d.onLock(&dtls, l0);
357  d.onUnlock(&dtls, l0);
358
359  EXPECT_TRUE(d.onFirstLock(&dtls, l0));  // Ok, same ecpoch, first lock.
360  EXPECT_FALSE(d.onFirstLock(&dtls, l1));  // Second lock.
361  d.onLock(&dtls, l1);
362  d.onUnlock(&dtls, l1);
363  d.onUnlock(&dtls, l0);
364
365  EXPECT_TRUE(d.onFirstLock(&dtls, l0));  // Ok
366  d.onUnlock(&dtls, l0);
367
368  vector<uptr> locks1;
369  for (uptr i = 0; i < d.size(); i++)
370    locks1.push_back(d.newNode(i));
371
372  EXPECT_TRUE(d.onFirstLock(&dtls, l0));  // Epoch has changed, but not in dtls.
373
374  uptr l3 = d.newNode(0);
375  d.onLock(&dtls, l3);
376  d.onUnlock(&dtls, l3);
377
378  EXPECT_FALSE(d.onFirstLock(&dtls, l0));  // Epoch has changed in dtls.
379}
380
381TEST(DeadlockDetector, onFirstLockTest) {
382  RunOnFirstLockTest<BV2>();
383}
384
385template <class BV>
386void RunRecusriveLockTest() {
387  ScopedDD<BV> sdd;
388  DeadlockDetector<BV> &d = *sdd.dp;
389  DeadlockDetectorTLS<BV> &dtls = sdd.dtls;
390
391  uptr l0 = d.newNode(0);
392  uptr l1 = d.newNode(0);
393  uptr l2 = d.newNode(0);
394  uptr l3 = d.newNode(0);
395
396  EXPECT_FALSE(d.onLock(&dtls, l0));
397  EXPECT_FALSE(d.onLock(&dtls, l1));
398  EXPECT_FALSE(d.onLock(&dtls, l0));  // Recurisve.
399  EXPECT_FALSE(d.onLock(&dtls, l2));
400  d.onUnlock(&dtls, l0);
401  EXPECT_FALSE(d.onLock(&dtls, l3));
402  d.onUnlock(&dtls, l0);
403  d.onUnlock(&dtls, l1);
404  d.onUnlock(&dtls, l2);
405  d.onUnlock(&dtls, l3);
406  EXPECT_TRUE(d.testOnlyHasEdge(l0, l1));
407  EXPECT_TRUE(d.testOnlyHasEdge(l0, l2));
408  EXPECT_TRUE(d.testOnlyHasEdge(l0, l3));
409}
410
411TEST(DeadlockDetector, RecusriveLockTest) {
412  RunRecusriveLockTest<BV2>();
413}
414
415template <class BV>
416void RunLockContextTest() {
417  ScopedDD<BV> sdd;
418  DeadlockDetector<BV> &d = *sdd.dp;
419  DeadlockDetectorTLS<BV> &dtls = sdd.dtls;
420
421  uptr l0 = d.newNode(0);
422  uptr l1 = d.newNode(0);
423  uptr l2 = d.newNode(0);
424  uptr l3 = d.newNode(0);
425  uptr l4 = d.newNode(0);
426  EXPECT_FALSE(d.onLock(&dtls, l0, 10));
427  EXPECT_FALSE(d.onLock(&dtls, l1, 11));
428  EXPECT_FALSE(d.onLock(&dtls, l2, 12));
429  EXPECT_FALSE(d.onLock(&dtls, l3, 13));
430  EXPECT_EQ(10U, d.findLockContext(&dtls, l0));
431  EXPECT_EQ(11U, d.findLockContext(&dtls, l1));
432  EXPECT_EQ(12U, d.findLockContext(&dtls, l2));
433  EXPECT_EQ(13U, d.findLockContext(&dtls, l3));
434  d.onUnlock(&dtls, l0);
435  EXPECT_EQ(0U, d.findLockContext(&dtls, l0));
436  EXPECT_EQ(11U, d.findLockContext(&dtls, l1));
437  EXPECT_EQ(12U, d.findLockContext(&dtls, l2));
438  EXPECT_EQ(13U, d.findLockContext(&dtls, l3));
439  d.onUnlock(&dtls, l2);
440  EXPECT_EQ(0U, d.findLockContext(&dtls, l0));
441  EXPECT_EQ(11U, d.findLockContext(&dtls, l1));
442  EXPECT_EQ(0U, d.findLockContext(&dtls, l2));
443  EXPECT_EQ(13U, d.findLockContext(&dtls, l3));
444
445  EXPECT_FALSE(d.onLock(&dtls, l4, 14));
446  EXPECT_EQ(14U, d.findLockContext(&dtls, l4));
447}
448
449TEST(DeadlockDetector, LockContextTest) {
450  RunLockContextTest<BV2>();
451}
452
453template <class BV>
454void RunRemoveEdgesTest() {
455  ScopedDD<BV> sdd;
456  DeadlockDetector<BV> &d = *sdd.dp;
457  DeadlockDetectorTLS<BV> &dtls = sdd.dtls;
458  vector<uptr> node(BV::kSize);
459  u32 stk_from = 0, stk_to = 0;
460  int unique_tid = 0;
461  for (size_t i = 0; i < BV::kSize; i++)
462    node[i] = d.newNode(0);
463
464  for (size_t i = 0; i < BV::kSize; i++)
465    EXPECT_FALSE(d.onLock(&dtls, node[i], i + 1));
466  for (size_t i = 0; i < BV::kSize; i++) {
467    for (uptr j = i + 1; j < BV::kSize; j++) {
468      EXPECT_TRUE(
469          d.findEdge(node[i], node[j], &stk_from, &stk_to, &unique_tid));
470      EXPECT_EQ(stk_from, i + 1);
471      EXPECT_EQ(stk_to, j + 1);
472    }
473  }
474  EXPECT_EQ(d.testOnlyGetEpoch(), d.size());
475  // Remove and re-create half of the nodes.
476  for (uptr i = 1; i < BV::kSize; i += 2)
477    d.removeNode(node[i]);
478  for (uptr i = 1; i < BV::kSize; i += 2)
479    node[i] = d.newNode(0);
480  EXPECT_EQ(d.testOnlyGetEpoch(), d.size());
481  // The edges from or to the removed nodes should be gone.
482  for (size_t i = 0; i < BV::kSize; i++) {
483    for (uptr j = i + 1; j < BV::kSize; j++) {
484      if ((i % 2) || (j % 2))
485        EXPECT_FALSE(
486            d.findEdge(node[i], node[j], &stk_from, &stk_to, &unique_tid));
487      else
488        EXPECT_TRUE(
489            d.findEdge(node[i], node[j], &stk_from, &stk_to, &unique_tid));
490    }
491  }
492}
493
494TEST(DeadlockDetector, RemoveEdgesTest) {
495  RunRemoveEdgesTest<BV1>();
496}
497