496 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file is a part of Sanitizer runtime.10// Tests for sanitizer_deadlock_detector.h11//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->n173 {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->n197 {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=>l2150 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=>l5157 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=>l0180 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=>l3185 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_DEBUG271 // 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#endif278}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)); // Ok365 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 else487 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