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

source code of compiler-rt/lib/sanitizer_common/tests/sanitizer_deadlock_detector_test.cpp