• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
24 using namespace __sanitizer;
25 using namespace std;
26 
27 typedef BasicBitVector<u8> BV1;
28 typedef BasicBitVector<> BV2;
29 typedef TwoLevelBitVector<> BV3;
30 typedef TwoLevelBitVector<3, BasicBitVector<u8> > BV4;
31 
32 // Poor man's unique_ptr.
33 template<class BV>
34 struct ScopedDD {
ScopedDDScopedDD35   ScopedDD() {
36     dp = new DeadlockDetector<BV>;
37     dp->clear();
38     dtls.clear();
39   }
~ScopedDDScopedDD40   ~ScopedDD() { delete dp; }
41   DeadlockDetector<BV> *dp;
42   DeadlockDetectorTLS<BV> dtls;
43 };
44 
45 template <class BV>
RunBasicTest()46 void 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 
TEST(DeadlockDetector,BasicTest)130 TEST(DeadlockDetector, BasicTest) {
131   RunBasicTest<BV1>();
132   RunBasicTest<BV2>();
133   RunBasicTest<BV3>();
134   RunBasicTest<BV4>();
135 }
136 
137 template <class BV>
RunRemoveNodeTest()138 void 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 
TEST(DeadlockDetector,RemoveNodeTest)236 TEST(DeadlockDetector, RemoveNodeTest) {
237   RunRemoveNodeTest<BV1>();
238   RunRemoveNodeTest<BV2>();
239   RunRemoveNodeTest<BV3>();
240   RunRemoveNodeTest<BV4>();
241 }
242 
243 template <class BV>
RunMultipleEpochsTest()244 void 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 
TEST(DeadlockDetector,MultipleEpochsTest)281 TEST(DeadlockDetector, MultipleEpochsTest) {
282   RunMultipleEpochsTest<BV1>();
283   RunMultipleEpochsTest<BV2>();
284   RunMultipleEpochsTest<BV3>();
285   RunMultipleEpochsTest<BV4>();
286 }
287 
288 template <class BV>
RunCorrectEpochFlush()289 void 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 
TEST(DeadlockDetector,CorrectEpochFlush)315 TEST(DeadlockDetector, CorrectEpochFlush) {
316   RunCorrectEpochFlush<BV1>();
317   RunCorrectEpochFlush<BV2>();
318 }
319 
320 template <class BV>
RunTryLockTest()321 void 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 
TEST(DeadlockDetector,TryLockTest)342 TEST(DeadlockDetector, TryLockTest) {
343   RunTryLockTest<BV1>();
344   RunTryLockTest<BV2>();
345 }
346 
347 template <class BV>
RunOnFirstLockTest()348 void 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 
TEST(DeadlockDetector,onFirstLockTest)381 TEST(DeadlockDetector, onFirstLockTest) {
382   RunOnFirstLockTest<BV2>();
383 }
384 
385 template <class BV>
RunRecusriveLockTest()386 void 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 
TEST(DeadlockDetector,RecusriveLockTest)411 TEST(DeadlockDetector, RecusriveLockTest) {
412   RunRecusriveLockTest<BV2>();
413 }
414 
415 template <class BV>
RunLockContextTest()416 void 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 
TEST(DeadlockDetector,LockContextTest)449 TEST(DeadlockDetector, LockContextTest) {
450   RunLockContextTest<BV2>();
451 }
452 
453 template <class BV>
RunRemoveEdgesTest()454 void 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 
TEST(DeadlockDetector,RemoveEdgesTest)494 TEST(DeadlockDetector, RemoveEdgesTest) {
495   RunRemoveEdgesTest<BV1>();
496 }
497