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