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); }
71class 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};
85 typedef void (PthreadLockChecker::*FnCheck)(
const CallEvent &
Call,
87 CheckerKind CheckKind)
const;
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},
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},
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},
172 const Expr *MtxExpr, CheckerKind CheckKind,
173 StringRef Desc)
const;
177 CheckerKind CheckKind)
const;
180 CheckerKind CheckKind)
const;
184 CheckerKind CheckKind)
const;
186 CheckerKind CheckKind)
const;
188 CheckerKind CheckKind)
const;
190 CheckerKind CheckKind)
const;
192 CheckerKind CheckKind)
const;
194 CheckerKind CheckKind)
const;
196 const Expr *MtxExpr,
SVal MtxVal,
bool IsTryLock,
197 LockingSemantics Semantics, CheckerKind CheckKind)
const;
201 CheckerKind CheckKind)
const;
204 CheckerKind CheckKind)
const;
208 CheckerKind CheckKind)
const;
210 CheckerKind CheckKind)
const;
213 LockingSemantics Semantics, CheckerKind CheckKind)
const;
223 void printState(raw_ostream &Out,
ProgramStateRef State,
const char *NL,
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"});
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);
295 assert(lstate->isUntouchedAndPossiblyDestroyed() ||
296 lstate->isUnlockedAndPossiblyDestroyed());
301 if (lstate->isUntouchedAndPossiblyDestroyed())
302 state = state->remove<LockMap>(lockR);
303 else if (lstate->isUnlockedAndPossiblyDestroyed())
304 state = state->set<LockMap>(lockR, LockState::getUnlocked());
306 state = state->set<LockMap>(lockR, LockState::getDestroyed());
310 state = state->remove<DestroyRetVal>(lockR);
314void PthreadLockChecker::printState(raw_ostream &Out,
ProgramStateRef State,
315 const char *NL,
const char *Sep)
const {
316 LockMapTy LM = State->get<LockMap>();
318 Out << Sep <<
"Mutex states:" << NL;
320 I.first->dumpToStream(Out);
321 if (I.second.isLocked())
323 else if (I.second.isUnlocked())
325 else if (I.second.isDestroyed())
326 Out <<
": destroyed";
327 else if (I.second.isUntouchedAndPossiblyDestroyed())
328 Out <<
": not tracked, possibly destroyed";
329 else if (I.second.isUnlockedAndPossiblyDestroyed())
330 Out <<
": unlocked, possibly destroyed";
335 LockSetTy LS = State->get<LockSet>();
337 Out << Sep <<
"Mutex lock order:" << NL;
339 I->dumpToStream(Out);
344 DestroyRetValTy DRV = State->get<DestroyRetVal>();
345 if (!DRV.isEmpty()) {
346 Out << Sep <<
"Mutexes in unresolved possibly destroyed state:" << NL;
348 I.first->dumpToStream(Out);
350 I.second->dumpToStream(Out);
356void PthreadLockChecker::AcquirePthreadLock(
const CallEvent &
Call,
358 CheckerKind CheckKind)
const {
359 AcquireLockAux(
Call,
C,
Call.getArgExpr(0),
Call.getArgSVal(0),
false,
360 PthreadSemantics, CheckKind);
363void PthreadLockChecker::AcquireXNULock(
const CallEvent &
Call,
365 CheckerKind CheckKind)
const {
366 AcquireLockAux(
Call,
C,
Call.getArgExpr(0),
Call.getArgSVal(0),
false,
367 XNUSemantics, CheckKind);
370void PthreadLockChecker::TryPthreadLock(
const CallEvent &
Call,
372 CheckerKind CheckKind)
const {
373 AcquireLockAux(
Call,
C,
Call.getArgExpr(0),
Call.getArgSVal(0),
true,
374 PthreadSemantics, CheckKind);
378 CheckerKind CheckKind)
const {
379 AcquireLockAux(
Call,
C,
Call.getArgExpr(0),
Call.getArgSVal(0),
true,
380 PthreadSemantics, CheckKind);
383void PthreadLockChecker::TryFuchsiaLock(
const CallEvent &
Call,
385 CheckerKind CheckKind)
const {
386 AcquireLockAux(
Call,
C,
Call.getArgExpr(0),
Call.getArgSVal(0),
true,
387 PthreadSemantics, CheckKind);
391 CheckerKind CheckKind)
const {
392 AcquireLockAux(
Call,
C,
Call.getArgExpr(0),
Call.getArgSVal(0),
true,
393 PthreadSemantics, CheckKind);
396void PthreadLockChecker::AcquireLockAux(
const CallEvent &
Call,
398 SVal MtxVal,
bool IsTryLock,
399 enum LockingSemantics Semantics,
400 CheckerKind CheckKind)
const {
401 if (!ChecksEnabled[CheckKind])
409 const SymbolRef *sym = state->get<DestroyRetVal>(lockR);
411 state = resolvePossiblyDestroyedMutex(state, lockR, sym);
413 if (
const LockState *LState = state->get<LockMap>(lockR)) {
414 if (LState->isLocked()) {
415 reportBug(
C, BT_doublelock, MtxExpr, CheckKind,
416 "This lock has already been acquired");
418 }
else if (LState->isDestroyed()) {
419 reportBug(
C, BT_destroylock, MtxExpr, CheckKind,
420 "This lock has already been destroyed");
428 SVal RetVal =
Call.getReturnValue();
432 case PthreadSemantics:
433 std::tie(lockFail, lockSucc) = state->assume(*DefinedRetVal);
436 std::tie(lockSucc, lockFail) = state->assume(*DefinedRetVal);
439 llvm_unreachable(
"Unknown tryLock locking semantics");
441 assert(lockFail && lockSucc);
442 C.addTransition(lockFail);
446 }
else if (Semantics == PthreadSemantics) {
448 SVal RetVal =
Call.getReturnValue();
452 lockSucc = state->assume(*DefinedRetVal,
false);
459 assert((Semantics == XNUSemantics) &&
"Unknown locking semantics");
464 lockSucc = lockSucc->add<LockSet>(lockR);
465 lockSucc = lockSucc->set<LockMap>(lockR, LockState::getLocked());
466 C.addTransition(lockSucc);
469void PthreadLockChecker::ReleaseAnyLock(
const CallEvent &
Call,
471 CheckerKind CheckKind)
const {
472 ReleaseLockAux(
Call,
C,
Call.getArgExpr(0),
Call.getArgSVal(0), CheckKind);
475void PthreadLockChecker::ReleaseLockAux(
const CallEvent &
Call,
478 CheckerKind CheckKind)
const {
479 if (!ChecksEnabled[CheckKind])
487 const SymbolRef *sym = state->get<DestroyRetVal>(lockR);
489 state = resolvePossiblyDestroyedMutex(state, lockR, sym);
491 if (
const LockState *LState = state->get<LockMap>(lockR)) {
492 if (LState->isUnlocked()) {
493 reportBug(
C, BT_doubleunlock, MtxExpr, CheckKind,
494 "This lock has already been unlocked");
496 }
else if (LState->isDestroyed()) {
497 reportBug(
C, BT_destroylock, MtxExpr, CheckKind,
498 "This lock has already been destroyed");
503 LockSetTy LS = state->get<LockSet>();
506 const MemRegion *firstLockR = LS.getHead();
507 if (firstLockR != lockR) {
508 reportBug(
C, BT_lor, MtxExpr, CheckKind,
509 "This was not the most recently acquired lock. Possible lock "
514 state = state->set<LockSet>(LS.getTail());
517 state = state->set<LockMap>(lockR, LockState::getUnlocked());
518 C.addTransition(state);
521void PthreadLockChecker::DestroyPthreadLock(
const CallEvent &
Call,
523 CheckerKind CheckKind)
const {
524 DestroyLockAux(
Call,
C,
Call.getArgExpr(0),
Call.getArgSVal(0),
525 PthreadSemantics, CheckKind);
528void PthreadLockChecker::DestroyXNULock(
const CallEvent &
Call,
530 CheckerKind CheckKind)
const {
531 DestroyLockAux(
Call,
C,
Call.getArgExpr(0),
Call.getArgSVal(0), XNUSemantics,
535void PthreadLockChecker::DestroyLockAux(
const CallEvent &
Call,
538 enum LockingSemantics Semantics,
539 CheckerKind CheckKind)
const {
540 if (!ChecksEnabled[CheckKind])
549 const SymbolRef *sym = State->get<DestroyRetVal>(LockR);
551 State = resolvePossiblyDestroyedMutex(State, LockR, sym);
553 const LockState *LState = State->get<LockMap>(LockR);
556 if (Semantics == PthreadSemantics) {
557 if (!LState || LState->isUnlocked()) {
560 State = State->remove<LockMap>(LockR);
561 C.addTransition(State);
564 State = State->set<DestroyRetVal>(LockR, sym);
565 if (LState && LState->isUnlocked())
566 State = State->set<LockMap>(
567 LockR, LockState::getUnlockedAndPossiblyDestroyed());
569 State = State->set<LockMap>(
570 LockR, LockState::getUntouchedAndPossiblyDestroyed());
571 C.addTransition(State);
575 if (!LState || LState->isUnlocked()) {
576 State = State->set<LockMap>(LockR, LockState::getDestroyed());
577 C.addTransition(State);
582 StringRef Message = LState->isLocked()
583 ?
"This lock is still locked"
584 :
"This lock has already been destroyed";
586 reportBug(
C, BT_destroylock, MtxExpr, CheckKind, Message);
590 CheckerKind CheckKind)
const {
591 InitLockAux(
Call,
C,
Call.getArgExpr(0),
Call.getArgSVal(0), CheckKind);
596 CheckerKind CheckKind)
const {
597 if (!ChecksEnabled[CheckKind])
606 const SymbolRef *sym = State->get<DestroyRetVal>(LockR);
608 State = resolvePossiblyDestroyedMutex(State, LockR, sym);
610 const struct LockState *LState = State->get<LockMap>(LockR);
611 if (!LState || LState->isDestroyed()) {
612 State = State->set<LockMap>(LockR, LockState::getUnlocked());
613 C.addTransition(State);
617 StringRef Message = LState->isLocked()
618 ?
"This lock is still being held"
619 :
"This lock has already been initialized";
621 reportBug(
C, BT_initlock, MtxExpr, CheckKind, Message);
625 std::unique_ptr<BugType> BT[],
626 const Expr *MtxExpr, CheckerKind CheckKind,
627 StringRef Desc)
const {
631 initBugType(CheckKind);
633 std::make_unique<PathSensitiveBugReport>(*BT[CheckKind], Desc, N);
635 C.emitReport(std::move(Report));
638void PthreadLockChecker::checkDeadSymbols(
SymbolReaper &SymReaper,
642 for (
auto I : State->get<DestroyRetVal>()) {
646 if (SymReaper.
isDead(I.second))
647 State = resolvePossiblyDestroyedMutex(State, I.first, &I.second);
650 for (
auto I : State->get<LockMap>()) {
653 State = State->remove<LockMap>(I.first);
654 State = State->remove<DestroyRetVal>(I.first);
662 C.addTransition(State);
671 bool IsLibraryFunction =
false;
672 if (
Call &&
Call->isGlobalCFunction()) {
674 if (PThreadCallbacks.lookup(*
Call) || FuchsiaCallbacks.
lookup(*
Call) ||
678 if (
Call->isInSystemHeader())
679 IsLibraryFunction =
true;
682 for (
auto R : Regions) {
686 if (IsLibraryFunction && !llvm::is_contained(ExplicitRegions, R))
689 State = State->remove<LockMap>(R);
690 State = State->remove<DestroyRetVal>(R);
704bool ento::shouldRegisterPthreadLockBase(
const CheckerManager &mgr) {
return true; }
706#define REGISTER_CHECKER(name) \
707 void ento::register##name(CheckerManager &mgr) { \
708 PthreadLockChecker *checker = mgr.getChecker<PthreadLockChecker>(); \
709 checker->ChecksEnabled[PthreadLockChecker::CK_##name] = true; \
710 checker->CheckNames[PthreadLockChecker::CK_##name] = \
711 mgr.getCurrentCheckerName(); \
714 bool ento::shouldRegister##name(const CheckerManager &mgr) { return true; }
#define REGISTER_MAP_WITH_PROGRAMSTATE(Name, Key, Value)
Declares an immutable map of type NameTy, suitable for placement into the ProgramState.
#define REGISTER_LIST_WITH_PROGRAMSTATE(Name, Elem)
Declares an immutable list type NameTy, suitable for placement into the ProgramState.
#define REGISTER_CHECKER(name)
This represents one expression.
It wraps the AnalysisDeclContext to represent both the call stack with the help of StackFrameContext ...
SourceRange getSourceRange() const LLVM_READONLY
SourceLocation tokens are not useful in isolation - they are low level value objects created/interpre...
An immutable map from CallDescriptions to arbitrary data.
const T * lookup(const CallEvent &Call) const
Represents an abstract call to a function or method along a particular path.
CHECKER * registerChecker(AT &&... Args)
Used to register checkers.
This wrapper is used to ensure that only StringRefs originating from the CheckerRegistry are used as ...
bool isConstrainedFalse() const
Return true if the constraint is perfectly constrained to 'false'.
ConditionTruthVal isNull(ProgramStateRef State, SymbolRef Sym)
Convenience method to query the state to see if a symbol is null or not null, or if neither assumptio...
MemRegion - The root abstract class for all memory regions.
SVal - This represents a symbolic expression, which can be either an L-value or an R-value.
std::optional< T > getAs() const
Convert to the specified SVal type, returning std::nullopt if this SVal is not of the desired type.
const MemRegion * getAsRegion() const
A class responsible for cleaning up unused symbols.
bool isDead(SymbolRef sym)
Returns whether or not a symbol has been confirmed dead.
bool isLiveRegion(const MemRegion *region)
bool operator==(const CallGraphNode::CallRecord &LHS, const CallGraphNode::CallRecord &RHS)