28 using namespace clang;
38 UntouchedAndPossiblyDestroyed,
39 UnlockedAndPossiblyDestroyed
43 LockState(
Kind K) : K(K) {}
46 static LockState getLocked() {
return LockState(Locked); }
47 static LockState getUnlocked() {
return LockState(Unlocked); }
48 static LockState getDestroyed() {
return LockState(Destroyed); }
49 static LockState getUntouchedAndPossiblyDestroyed() {
50 return LockState(UntouchedAndPossiblyDestroyed);
52 static LockState getUnlockedAndPossiblyDestroyed() {
53 return LockState(UnlockedAndPossiblyDestroyed);
56 bool operator==(
const LockState &
X)
const {
return K ==
X.K; }
58 bool isLocked()
const {
return K == Locked; }
59 bool isUnlocked()
const {
return K == Unlocked; }
60 bool isDestroyed()
const {
return K == Destroyed; }
61 bool isUntouchedAndPossiblyDestroyed()
const {
62 return K == UntouchedAndPossiblyDestroyed;
64 bool isUnlockedAndPossiblyDestroyed()
const {
65 return K == UnlockedAndPossiblyDestroyed;
68 void Profile(llvm::FoldingSetNodeID &
ID)
const {
ID.AddInteger(K); }
71 class PthreadLockChecker :
public Checker<check::PostCall, check::DeadSymbols,
72 check::RegionChanges> {
74 enum LockingSemantics { NotApplicable = 0, PthreadSemantics, XNUSemantics };
76 CK_PthreadLockChecker,
77 CK_FuchsiaLockChecker,
81 bool ChecksEnabled[CK_NumCheckKinds] = {
false};
82 CheckerNameRef CheckNames[CK_NumCheckKinds];
85 typedef void (PthreadLockChecker::*FnCheck)(
const CallEvent &
Call,
87 CheckerKind CheckKind)
const;
88 CallDescriptionMap<FnCheck> PThreadCallbacks = {
90 {{
"pthread_mutex_init", 2}, &PthreadLockChecker::InitAnyLock},
98 {{
"pthread_mutex_lock", 1}, &PthreadLockChecker::AcquirePthreadLock},
99 {{
"pthread_rwlock_rdlock", 1}, &PthreadLockChecker::AcquirePthreadLock},
100 {{
"pthread_rwlock_wrlock", 1}, &PthreadLockChecker::AcquirePthreadLock},
101 {{
"lck_mtx_lock", 1}, &PthreadLockChecker::AcquireXNULock},
102 {{
"lck_rw_lock_exclusive", 1}, &PthreadLockChecker::AcquireXNULock},
103 {{
"lck_rw_lock_shared", 1}, &PthreadLockChecker::AcquireXNULock},
106 {{
"pthread_mutex_trylock", 1}, &PthreadLockChecker::TryPthreadLock},
107 {{
"pthread_rwlock_tryrdlock", 1}, &PthreadLockChecker::TryPthreadLock},
108 {{
"pthread_rwlock_trywrlock", 1}, &PthreadLockChecker::TryPthreadLock},
109 {{
"lck_mtx_try_lock", 1}, &PthreadLockChecker::TryXNULock},
110 {{
"lck_rw_try_lock_exclusive", 1}, &PthreadLockChecker::TryXNULock},
111 {{
"lck_rw_try_lock_shared", 1}, &PthreadLockChecker::TryXNULock},
114 {{
"pthread_mutex_unlock", 1}, &PthreadLockChecker::ReleaseAnyLock},
115 {{
"pthread_rwlock_unlock", 1}, &PthreadLockChecker::ReleaseAnyLock},
116 {{
"lck_mtx_unlock", 1}, &PthreadLockChecker::ReleaseAnyLock},
117 {{
"lck_rw_unlock_exclusive", 1}, &PthreadLockChecker::ReleaseAnyLock},
118 {{
"lck_rw_unlock_shared", 1}, &PthreadLockChecker::ReleaseAnyLock},
119 {{
"lck_rw_done", 1}, &PthreadLockChecker::ReleaseAnyLock},
122 {{
"pthread_mutex_destroy", 1}, &PthreadLockChecker::DestroyPthreadLock},
123 {{
"lck_mtx_destroy", 2}, &PthreadLockChecker::DestroyXNULock},
128 CallDescriptionMap<FnCheck> FuchsiaCallbacks = {
130 {{
"spin_lock_init", 1}, &PthreadLockChecker::InitAnyLock},
133 {{
"spin_lock", 1}, &PthreadLockChecker::AcquirePthreadLock},
134 {{
"spin_lock_save", 3}, &PthreadLockChecker::AcquirePthreadLock},
135 {{
"sync_mutex_lock", 1}, &PthreadLockChecker::AcquirePthreadLock},
136 {{
"sync_mutex_lock_with_waiter", 1},
137 &PthreadLockChecker::AcquirePthreadLock},
140 {{
"spin_trylock", 1}, &PthreadLockChecker::TryFuchsiaLock},
141 {{
"sync_mutex_trylock", 1}, &PthreadLockChecker::TryFuchsiaLock},
142 {{
"sync_mutex_timedlock", 2}, &PthreadLockChecker::TryFuchsiaLock},
145 {{
"spin_unlock", 1}, &PthreadLockChecker::ReleaseAnyLock},
146 {{
"spin_unlock_restore", 3}, &PthreadLockChecker::ReleaseAnyLock},
147 {{
"sync_mutex_unlock", 1}, &PthreadLockChecker::ReleaseAnyLock},
150 CallDescriptionMap<FnCheck> C11Callbacks = {
152 {{
"mtx_init", 2}, &PthreadLockChecker::InitAnyLock},
155 {{
"mtx_lock", 1}, &PthreadLockChecker::AcquirePthreadLock},
158 {{
"mtx_trylock", 1}, &PthreadLockChecker::TryC11Lock},
159 {{
"mtx_timedlock", 2}, &PthreadLockChecker::TryC11Lock},
162 {{
"mtx_unlock", 1}, &PthreadLockChecker::ReleaseAnyLock},
165 {{
"mtx_destroy", 1}, &PthreadLockChecker::DestroyPthreadLock},
169 const MemRegion *lockR,
171 void reportBug(CheckerContext &C, std::unique_ptr<BugType> BT[],
172 const Expr *MtxExpr, CheckerKind CheckKind,
173 StringRef Desc)
const;
176 void InitAnyLock(
const CallEvent &Call, CheckerContext &C,
177 CheckerKind CheckKind)
const;
178 void InitLockAux(
const CallEvent &Call, CheckerContext &C,
179 const Expr *MtxExpr, SVal MtxVal,
180 CheckerKind CheckKind)
const;
183 void AcquirePthreadLock(
const CallEvent &Call, CheckerContext &C,
184 CheckerKind CheckKind)
const;
185 void AcquireXNULock(
const CallEvent &Call, CheckerContext &C,
186 CheckerKind CheckKind)
const;
187 void TryPthreadLock(
const CallEvent &Call, CheckerContext &C,
188 CheckerKind CheckKind)
const;
189 void TryXNULock(
const CallEvent &Call, CheckerContext &C,
190 CheckerKind CheckKind)
const;
191 void TryFuchsiaLock(
const CallEvent &Call, CheckerContext &C,
192 CheckerKind CheckKind)
const;
193 void TryC11Lock(
const CallEvent &Call, CheckerContext &C,
194 CheckerKind CheckKind)
const;
195 void AcquireLockAux(
const CallEvent &Call, CheckerContext &C,
196 const Expr *MtxExpr, SVal MtxVal,
bool IsTryLock,
197 LockingSemantics Semantics, CheckerKind CheckKind)
const;
200 void ReleaseAnyLock(
const CallEvent &Call, CheckerContext &C,
201 CheckerKind CheckKind)
const;
202 void ReleaseLockAux(
const CallEvent &Call, CheckerContext &C,
203 const Expr *MtxExpr, SVal MtxVal,
204 CheckerKind CheckKind)
const;
207 void DestroyPthreadLock(
const CallEvent &Call, CheckerContext &C,
208 CheckerKind CheckKind)
const;
209 void DestroyXNULock(
const CallEvent &Call, CheckerContext &C,
210 CheckerKind CheckKind)
const;
211 void DestroyLockAux(
const CallEvent &Call, CheckerContext &C,
212 const Expr *MtxExpr, SVal MtxVal,
213 LockingSemantics Semantics, CheckerKind CheckKind)
const;
216 void checkPostCall(
const CallEvent &Call, CheckerContext &C)
const;
217 void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C)
const;
224 const char *Sep)
const override;
227 mutable std::unique_ptr<BugType> BT_doublelock[CK_NumCheckKinds];
228 mutable std::unique_ptr<BugType> BT_doubleunlock[CK_NumCheckKinds];
229 mutable std::unique_ptr<BugType> BT_destroylock[CK_NumCheckKinds];
230 mutable std::unique_ptr<BugType> BT_initlock[CK_NumCheckKinds];
231 mutable std::unique_ptr<BugType> BT_lor[CK_NumCheckKinds];
233 void initBugType(CheckerKind CheckKind)
const {
234 if (BT_doublelock[CheckKind])
236 BT_doublelock[CheckKind].reset(
237 new BugType{CheckNames[CheckKind],
"Double locking",
"Lock checker"});
238 BT_doubleunlock[CheckKind].reset(
239 new BugType{CheckNames[CheckKind],
"Double unlocking",
"Lock checker"});
240 BT_destroylock[CheckKind].reset(
new BugType{
241 CheckNames[CheckKind],
"Use destroyed lock",
"Lock checker"});
242 BT_initlock[CheckKind].reset(
new BugType{
243 CheckNames[CheckKind],
"Init invalid lock",
"Lock checker"});
244 BT_lor[CheckKind].reset(
new BugType{CheckNames[CheckKind],
245 "Lock order reversal",
"Lock checker"});
259 void PthreadLockChecker::checkPostCall(
const CallEvent &Call,
260 CheckerContext &C)
const {
267 if (!
Call.isGlobalCFunction() ||
C.wasInlined)
270 if (
const FnCheck *Callback = PThreadCallbacks.lookup(Call))
271 (this->**Callback)(Call, C, CK_PthreadLockChecker);
272 else if (
const FnCheck *Callback = FuchsiaCallbacks.lookup(Call))
273 (this->**Callback)(
Call,
C, CK_FuchsiaLockChecker);
274 else if (
const FnCheck *Callback = C11Callbacks.lookup(Call))
275 (this->**Callback)(
Call,
C, CK_C11LockChecker);
290 const LockState *lstate =
state->get<LockMap>(lockR);
294 assert(lstate->isUntouchedAndPossiblyDestroyed() ||
295 lstate->isUnlockedAndPossiblyDestroyed());
297 ConstraintManager &CMgr =
state->getConstraintManager();
298 ConditionTruthVal retZero = CMgr.isNull(
state, *sym);
299 if (retZero.isConstrainedFalse()) {
300 if (lstate->isUntouchedAndPossiblyDestroyed())
302 else if (lstate->isUnlockedAndPossiblyDestroyed())
303 state =
state->set<LockMap>(lockR, LockState::getUnlocked());
305 state =
state->set<LockMap>(lockR, LockState::getDestroyed());
314 const char *NL,
const char *Sep)
const {
315 LockMapTy LM =
State->get<LockMap>();
317 Out << Sep <<
"Mutex states:" << NL;
319 I.first->dumpToStream(Out);
320 if (I.second.isLocked())
322 else if (I.second.isUnlocked())
324 else if (I.second.isDestroyed())
325 Out <<
": destroyed";
326 else if (I.second.isUntouchedAndPossiblyDestroyed())
327 Out <<
": not tracked, possibly destroyed";
328 else if (I.second.isUnlockedAndPossiblyDestroyed())
329 Out <<
": unlocked, possibly destroyed";
334 LockSetTy LS =
State->get<LockSet>();
336 Out << Sep <<
"Mutex lock order:" << NL;
338 I->dumpToStream(Out);
343 DestroyRetValTy DRV =
State->get<DestroyRetVal>();
344 if (!DRV.isEmpty()) {
345 Out << Sep <<
"Mutexes in unresolved possibly destroyed state:" << NL;
347 I.first->dumpToStream(Out);
349 I.second->dumpToStream(Out);
355 void PthreadLockChecker::AcquirePthreadLock(
const CallEvent &Call,
357 CheckerKind CheckKind)
const {
358 AcquireLockAux(Call, C,
Call.getArgExpr(0),
Call.getArgSVal(0),
false,
359 PthreadSemantics, CheckKind);
362 void PthreadLockChecker::AcquireXNULock(
const CallEvent &Call,
364 CheckerKind CheckKind)
const {
365 AcquireLockAux(Call, C,
Call.getArgExpr(0),
Call.getArgSVal(0),
false,
366 XNUSemantics, CheckKind);
369 void PthreadLockChecker::TryPthreadLock(
const CallEvent &Call,
371 CheckerKind CheckKind)
const {
372 AcquireLockAux(Call, C,
Call.getArgExpr(0),
Call.getArgSVal(0),
true,
373 PthreadSemantics, CheckKind);
376 void PthreadLockChecker::TryXNULock(
const CallEvent &Call, CheckerContext &C,
377 CheckerKind CheckKind)
const {
378 AcquireLockAux(Call, C,
Call.getArgExpr(0),
Call.getArgSVal(0),
true,
379 PthreadSemantics, CheckKind);
382 void PthreadLockChecker::TryFuchsiaLock(
const CallEvent &Call,
384 CheckerKind CheckKind)
const {
385 AcquireLockAux(Call, C,
Call.getArgExpr(0),
Call.getArgSVal(0),
true,
386 PthreadSemantics, CheckKind);
389 void PthreadLockChecker::TryC11Lock(
const CallEvent &Call, CheckerContext &C,
390 CheckerKind CheckKind)
const {
391 AcquireLockAux(Call, C,
Call.getArgExpr(0),
Call.getArgSVal(0),
true,
392 PthreadSemantics, CheckKind);
395 void PthreadLockChecker::AcquireLockAux(
const CallEvent &Call,
396 CheckerContext &C,
const Expr *MtxExpr,
397 SVal MtxVal,
bool IsTryLock,
398 enum LockingSemantics Semantics,
399 CheckerKind CheckKind)
const {
400 if (!ChecksEnabled[CheckKind])
403 const MemRegion *lockR = MtxVal.getAsRegion();
410 state = resolvePossiblyDestroyedMutex(
state, lockR, sym);
412 if (
const LockState *LState =
state->get<LockMap>(lockR)) {
413 if (LState->isLocked()) {
414 reportBug(C, BT_doublelock, MtxExpr, CheckKind,
415 "This lock has already been acquired");
417 }
else if (LState->isDestroyed()) {
418 reportBug(C, BT_destroylock, MtxExpr, CheckKind,
419 "This lock has already been destroyed");
427 SVal RetVal =
Call.getReturnValue();
428 if (
auto DefinedRetVal = RetVal.getAs<DefinedSVal>()) {
431 case PthreadSemantics:
432 std::tie(lockFail, lockSucc) =
state->assume(*DefinedRetVal);
435 std::tie(lockSucc, lockFail) =
state->assume(*DefinedRetVal);
438 llvm_unreachable(
"Unknown tryLock locking semantics");
440 assert(lockFail && lockSucc);
441 C.addTransition(lockFail);
445 }
else if (Semantics == PthreadSemantics) {
447 SVal RetVal =
Call.getReturnValue();
448 if (
auto DefinedRetVal = RetVal.getAs<DefinedSVal>()) {
451 lockSucc =
state->assume(*DefinedRetVal,
false);
458 assert((Semantics == XNUSemantics) &&
"Unknown locking semantics");
463 lockSucc = lockSucc->add<LockSet>(lockR);
464 lockSucc = lockSucc->set<LockMap>(lockR, LockState::getLocked());
465 C.addTransition(lockSucc);
468 void PthreadLockChecker::ReleaseAnyLock(
const CallEvent &Call,
470 CheckerKind CheckKind)
const {
471 ReleaseLockAux(Call, C,
Call.getArgExpr(0),
Call.getArgSVal(0), CheckKind);
474 void PthreadLockChecker::ReleaseLockAux(
const CallEvent &Call,
475 CheckerContext &C,
const Expr *MtxExpr,
477 CheckerKind CheckKind)
const {
478 if (!ChecksEnabled[CheckKind])
481 const MemRegion *lockR = MtxVal.getAsRegion();
488 state = resolvePossiblyDestroyedMutex(
state, lockR, sym);
490 if (
const LockState *LState =
state->get<LockMap>(lockR)) {
491 if (LState->isUnlocked()) {
492 reportBug(C, BT_doubleunlock, MtxExpr, CheckKind,
493 "This lock has already been unlocked");
495 }
else if (LState->isDestroyed()) {
496 reportBug(C, BT_destroylock, MtxExpr, CheckKind,
497 "This lock has already been destroyed");
502 LockSetTy LS =
state->get<LockSet>();
505 const MemRegion *firstLockR = LS.getHead();
506 if (firstLockR != lockR) {
507 reportBug(C, BT_lor, MtxExpr, CheckKind,
508 "This was not the most recently acquired lock. Possible lock "
516 state =
state->set<LockMap>(lockR, LockState::getUnlocked());
520 void PthreadLockChecker::DestroyPthreadLock(
const CallEvent &Call,
522 CheckerKind CheckKind)
const {
523 DestroyLockAux(Call, C,
Call.getArgExpr(0),
Call.getArgSVal(0),
524 PthreadSemantics, CheckKind);
527 void PthreadLockChecker::DestroyXNULock(
const CallEvent &Call,
529 CheckerKind CheckKind)
const {
530 DestroyLockAux(Call, C,
Call.getArgExpr(0),
Call.getArgSVal(0), XNUSemantics,
534 void PthreadLockChecker::DestroyLockAux(
const CallEvent &Call,
535 CheckerContext &C,
const Expr *MtxExpr,
537 enum LockingSemantics Semantics,
538 CheckerKind CheckKind)
const {
539 if (!ChecksEnabled[CheckKind])
542 const MemRegion *LockR = MtxVal.getAsRegion();
550 State = resolvePossiblyDestroyedMutex(
State, LockR, sym);
552 const LockState *LState =
State->get<LockMap>(LockR);
555 if (Semantics == PthreadSemantics) {
556 if (!LState || LState->isUnlocked()) {
563 State =
State->set<DestroyRetVal>(LockR, sym);
564 if (LState && LState->isUnlocked())
566 LockR, LockState::getUnlockedAndPossiblyDestroyed());
569 LockR, LockState::getUntouchedAndPossiblyDestroyed());
574 if (!LState || LState->isUnlocked()) {
575 State =
State->set<LockMap>(LockR, LockState::getDestroyed());
581 StringRef
Message = LState->isLocked()
582 ?
"This lock is still locked"
583 :
"This lock has already been destroyed";
585 reportBug(C, BT_destroylock, MtxExpr, CheckKind, Message);
588 void PthreadLockChecker::InitAnyLock(
const CallEvent &Call, CheckerContext &C,
589 CheckerKind CheckKind)
const {
590 InitLockAux(Call, C,
Call.getArgExpr(0),
Call.getArgSVal(0), CheckKind);
593 void PthreadLockChecker::InitLockAux(
const CallEvent &Call, CheckerContext &C,
594 const Expr *MtxExpr, SVal MtxVal,
595 CheckerKind CheckKind)
const {
596 if (!ChecksEnabled[CheckKind])
599 const MemRegion *LockR = MtxVal.getAsRegion();
607 State = resolvePossiblyDestroyedMutex(
State, LockR, sym);
609 const struct LockState *LState =
State->get<LockMap>(LockR);
610 if (!LState || LState->isDestroyed()) {
611 State =
State->set<LockMap>(LockR, LockState::getUnlocked());
616 StringRef
Message = LState->isLocked()
617 ?
"This lock is still being held"
618 :
"This lock has already been initialized";
620 reportBug(
C, BT_initlock, MtxExpr, CheckKind, Message);
623 void PthreadLockChecker::reportBug(CheckerContext &
C,
624 std::unique_ptr<BugType> BT[],
625 const Expr *MtxExpr, CheckerKind CheckKind,
626 StringRef Desc)
const {
627 ExplodedNode *N =
C.generateErrorNode();
630 initBugType(CheckKind);
632 std::make_unique<PathSensitiveBugReport>(*BT[CheckKind], Desc, N);
634 C.emitReport(std::move(Report));
637 void PthreadLockChecker::checkDeadSymbols(SymbolReaper &SymReaper,
638 CheckerContext &
C)
const {
641 for (
auto I :
State->get<DestroyRetVal>()) {
645 if (SymReaper.isDead(I.second))
646 State = resolvePossiblyDestroyedMutex(
State, I.first, &I.second);
649 for (
auto I :
State->get<LockMap>()) {
651 if (!SymReaper.isLiveRegion(I.first)) {
653 State =
State->remove<DestroyRetVal>(I.first);
668 const CallEvent *Call)
const {
670 bool IsLibraryFunction =
false;
671 if (Call &&
Call->isGlobalCFunction()) {
673 if (PThreadCallbacks.lookup(*Call) || FuchsiaCallbacks.lookup(*Call) ||
674 C11Callbacks.lookup(*Call))
677 if (
Call->isInSystemHeader())
678 IsLibraryFunction =
true;
681 for (
auto R : Regions) {
685 if (IsLibraryFunction && !llvm::is_contained(ExplicitRegions, R))
699 void ento::registerPthreadLockBase(CheckerManager &mgr) {
700 mgr.registerChecker<PthreadLockChecker>();
703 bool ento::shouldRegisterPthreadLockBase(
const CheckerManager &mgr) {
return true; }
705 #define REGISTER_CHECKER(name) \
706 void ento::register##name(CheckerManager &mgr) { \
707 PthreadLockChecker *checker = mgr.getChecker<PthreadLockChecker>(); \
708 checker->ChecksEnabled[PthreadLockChecker::CK_##name] = true; \
709 checker->CheckNames[PthreadLockChecker::CK_##name] = \
710 mgr.getCurrentCheckerName(); \
713 bool ento::shouldRegister##name(const CheckerManager &mgr) { return true; }