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 {{CDM::CLibrary, {
"pthread_mutex_init"}, 2},
91 &PthreadLockChecker::InitAnyLock},
99 {{CDM::CLibrary, {
"pthread_mutex_lock"}, 1},
100 &PthreadLockChecker::AcquirePthreadLock},
101 {{CDM::CLibrary, {
"pthread_rwlock_rdlock"}, 1},
102 &PthreadLockChecker::AcquirePthreadLock},
103 {{CDM::CLibrary, {
"pthread_rwlock_wrlock"}, 1},
104 &PthreadLockChecker::AcquirePthreadLock},
105 {{CDM::CLibrary, {
"lck_mtx_lock"}, 1},
106 &PthreadLockChecker::AcquireXNULock},
107 {{CDM::CLibrary, {
"lck_rw_lock_exclusive"}, 1},
108 &PthreadLockChecker::AcquireXNULock},
109 {{CDM::CLibrary, {
"lck_rw_lock_shared"}, 1},
110 &PthreadLockChecker::AcquireXNULock},
113 {{CDM::CLibrary, {
"pthread_mutex_trylock"}, 1},
114 &PthreadLockChecker::TryPthreadLock},
115 {{CDM::CLibrary, {
"pthread_rwlock_tryrdlock"}, 1},
116 &PthreadLockChecker::TryPthreadLock},
117 {{CDM::CLibrary, {
"pthread_rwlock_trywrlock"}, 1},
118 &PthreadLockChecker::TryPthreadLock},
119 {{CDM::CLibrary, {
"lck_mtx_try_lock"}, 1},
120 &PthreadLockChecker::TryXNULock},
121 {{CDM::CLibrary, {
"lck_rw_try_lock_exclusive"}, 1},
122 &PthreadLockChecker::TryXNULock},
123 {{CDM::CLibrary, {
"lck_rw_try_lock_shared"}, 1},
124 &PthreadLockChecker::TryXNULock},
127 {{CDM::CLibrary, {
"pthread_mutex_unlock"}, 1},
128 &PthreadLockChecker::ReleaseAnyLock},
129 {{CDM::CLibrary, {
"pthread_rwlock_unlock"}, 1},
130 &PthreadLockChecker::ReleaseAnyLock},
131 {{CDM::CLibrary, {
"lck_mtx_unlock"}, 1},
132 &PthreadLockChecker::ReleaseAnyLock},
133 {{CDM::CLibrary, {
"lck_rw_unlock_exclusive"}, 1},
134 &PthreadLockChecker::ReleaseAnyLock},
135 {{CDM::CLibrary, {
"lck_rw_unlock_shared"}, 1},
136 &PthreadLockChecker::ReleaseAnyLock},
137 {{CDM::CLibrary, {
"lck_rw_done"}, 1},
138 &PthreadLockChecker::ReleaseAnyLock},
141 {{CDM::CLibrary, {
"pthread_mutex_destroy"}, 1},
142 &PthreadLockChecker::DestroyPthreadLock},
143 {{CDM::CLibrary, {
"lck_mtx_destroy"}, 2},
144 &PthreadLockChecker::DestroyXNULock},
151 {{CDM::CLibrary, {
"spin_lock_init"}, 1},
152 &PthreadLockChecker::InitAnyLock},
155 {{CDM::CLibrary, {
"spin_lock"}, 1},
156 &PthreadLockChecker::AcquirePthreadLock},
157 {{CDM::CLibrary, {
"spin_lock_save"}, 3},
158 &PthreadLockChecker::AcquirePthreadLock},
159 {{CDM::CLibrary, {
"sync_mutex_lock"}, 1},
160 &PthreadLockChecker::AcquirePthreadLock},
161 {{CDM::CLibrary, {
"sync_mutex_lock_with_waiter"}, 1},
162 &PthreadLockChecker::AcquirePthreadLock},
165 {{CDM::CLibrary, {
"spin_trylock"}, 1},
166 &PthreadLockChecker::TryFuchsiaLock},
167 {{CDM::CLibrary, {
"sync_mutex_trylock"}, 1},
168 &PthreadLockChecker::TryFuchsiaLock},
169 {{CDM::CLibrary, {
"sync_mutex_timedlock"}, 2},
170 &PthreadLockChecker::TryFuchsiaLock},
173 {{CDM::CLibrary, {
"spin_unlock"}, 1},
174 &PthreadLockChecker::ReleaseAnyLock},
175 {{CDM::CLibrary, {
"spin_unlock_restore"}, 3},
176 &PthreadLockChecker::ReleaseAnyLock},
177 {{CDM::CLibrary, {
"sync_mutex_unlock"}, 1},
178 &PthreadLockChecker::ReleaseAnyLock},
183 {{CDM::CLibrary, {
"mtx_init"}, 2}, &PthreadLockChecker::InitAnyLock},
186 {{CDM::CLibrary, {
"mtx_lock"}, 1},
187 &PthreadLockChecker::AcquirePthreadLock},
190 {{CDM::CLibrary, {
"mtx_trylock"}, 1}, &PthreadLockChecker::TryC11Lock},
191 {{CDM::CLibrary, {
"mtx_timedlock"}, 2}, &PthreadLockChecker::TryC11Lock},
194 {{CDM::CLibrary, {
"mtx_unlock"}, 1}, &PthreadLockChecker::ReleaseAnyLock},
197 {{CDM::CLibrary, {
"mtx_destroy"}, 1},
198 &PthreadLockChecker::DestroyPthreadLock},
205 const Expr *MtxExpr, CheckerKind CheckKind,
206 StringRef Desc)
const;
210 CheckerKind CheckKind)
const;
213 CheckerKind CheckKind)
const;
217 CheckerKind CheckKind)
const;
219 CheckerKind CheckKind)
const;
221 CheckerKind CheckKind)
const;
223 CheckerKind CheckKind)
const;
225 CheckerKind CheckKind)
const;
227 CheckerKind CheckKind)
const;
229 const Expr *MtxExpr,
SVal MtxVal,
bool IsTryLock,
230 LockingSemantics Semantics, CheckerKind CheckKind)
const;
234 CheckerKind CheckKind)
const;
237 CheckerKind CheckKind)
const;
241 CheckerKind CheckKind)
const;
243 CheckerKind CheckKind)
const;
246 LockingSemantics Semantics, CheckerKind CheckKind)
const;
256 void printState(raw_ostream &Out,
ProgramStateRef State,
const char *NL,
257 const char *Sep)
const override;
260 mutable std::unique_ptr<BugType> BT_doublelock[CK_NumCheckKinds];
261 mutable std::unique_ptr<BugType> BT_doubleunlock[CK_NumCheckKinds];
262 mutable std::unique_ptr<BugType> BT_destroylock[CK_NumCheckKinds];
263 mutable std::unique_ptr<BugType> BT_initlock[CK_NumCheckKinds];
264 mutable std::unique_ptr<BugType> BT_lor[CK_NumCheckKinds];
266 void initBugType(CheckerKind CheckKind)
const {
267 if (BT_doublelock[CheckKind])
269 BT_doublelock[CheckKind].reset(
270 new BugType{CheckNames[CheckKind],
"Double locking",
"Lock checker"});
271 BT_doubleunlock[CheckKind].reset(
272 new BugType{CheckNames[CheckKind],
"Double unlocking",
"Lock checker"});
273 BT_destroylock[CheckKind].reset(
new BugType{
274 CheckNames[CheckKind],
"Use destroyed lock",
"Lock checker"});
275 BT_initlock[CheckKind].reset(
new BugType{
276 CheckNames[CheckKind],
"Init invalid lock",
"Lock checker"});
277 BT_lor[CheckKind].reset(
new BugType{CheckNames[CheckKind],
278 "Lock order reversal",
"Lock checker"});
299 if (
const FnCheck *Callback = PThreadCallbacks.lookup(
Call))
300 (this->**Callback)(
Call,
C, CK_PthreadLockChecker);
301 else if (
const FnCheck *Callback = FuchsiaCallbacks.
lookup(
Call))
302 (this->**Callback)(
Call,
C, CK_FuchsiaLockChecker);
303 else if (
const FnCheck *Callback = C11Callbacks.
lookup(
Call))
304 (this->**Callback)(
Call,
C, CK_C11LockChecker);
319 const LockState *lstate = state->get<LockMap>(lockR);
324 assert(lstate->isUntouchedAndPossiblyDestroyed() ||
325 lstate->isUnlockedAndPossiblyDestroyed());
330 if (lstate->isUntouchedAndPossiblyDestroyed())
331 state = state->remove<LockMap>(lockR);
332 else if (lstate->isUnlockedAndPossiblyDestroyed())
333 state = state->set<LockMap>(lockR, LockState::getUnlocked());
335 state = state->set<LockMap>(lockR, LockState::getDestroyed());
339 state = state->remove<DestroyRetVal>(lockR);
343void PthreadLockChecker::printState(raw_ostream &Out,
ProgramStateRef State,
344 const char *NL,
const char *Sep)
const {
345 LockMapTy LM = State->get<LockMap>();
347 Out << Sep <<
"Mutex states:" << NL;
349 I.first->dumpToStream(Out);
350 if (I.second.isLocked())
352 else if (I.second.isUnlocked())
354 else if (I.second.isDestroyed())
355 Out <<
": destroyed";
356 else if (I.second.isUntouchedAndPossiblyDestroyed())
357 Out <<
": not tracked, possibly destroyed";
358 else if (I.second.isUnlockedAndPossiblyDestroyed())
359 Out <<
": unlocked, possibly destroyed";
364 LockSetTy LS = State->get<LockSet>();
366 Out << Sep <<
"Mutex lock order:" << NL;
368 I->dumpToStream(Out);
373 DestroyRetValTy DRV = State->get<DestroyRetVal>();
374 if (!DRV.isEmpty()) {
375 Out << Sep <<
"Mutexes in unresolved possibly destroyed state:" << NL;
377 I.first->dumpToStream(Out);
379 I.second->dumpToStream(Out);
385void PthreadLockChecker::AcquirePthreadLock(
const CallEvent &
Call,
387 CheckerKind CheckKind)
const {
388 AcquireLockAux(
Call,
C,
Call.getArgExpr(0),
Call.getArgSVal(0),
false,
389 PthreadSemantics, CheckKind);
392void PthreadLockChecker::AcquireXNULock(
const CallEvent &
Call,
394 CheckerKind CheckKind)
const {
395 AcquireLockAux(
Call,
C,
Call.getArgExpr(0),
Call.getArgSVal(0),
false,
396 XNUSemantics, CheckKind);
399void PthreadLockChecker::TryPthreadLock(
const CallEvent &
Call,
401 CheckerKind CheckKind)
const {
402 AcquireLockAux(
Call,
C,
Call.getArgExpr(0),
Call.getArgSVal(0),
true,
403 PthreadSemantics, CheckKind);
407 CheckerKind CheckKind)
const {
408 AcquireLockAux(
Call,
C,
Call.getArgExpr(0),
Call.getArgSVal(0),
true,
409 PthreadSemantics, CheckKind);
412void PthreadLockChecker::TryFuchsiaLock(
const CallEvent &
Call,
414 CheckerKind CheckKind)
const {
415 AcquireLockAux(
Call,
C,
Call.getArgExpr(0),
Call.getArgSVal(0),
true,
416 PthreadSemantics, CheckKind);
420 CheckerKind CheckKind)
const {
421 AcquireLockAux(
Call,
C,
Call.getArgExpr(0),
Call.getArgSVal(0),
true,
422 PthreadSemantics, CheckKind);
425void PthreadLockChecker::AcquireLockAux(
const CallEvent &
Call,
427 SVal MtxVal,
bool IsTryLock,
428 enum LockingSemantics Semantics,
429 CheckerKind CheckKind)
const {
430 if (!ChecksEnabled[CheckKind])
438 const SymbolRef *sym = state->get<DestroyRetVal>(lockR);
440 state = resolvePossiblyDestroyedMutex(state, lockR, sym);
442 if (
const LockState *LState = state->get<LockMap>(lockR)) {
443 if (LState->isLocked()) {
444 reportBug(
C, BT_doublelock, MtxExpr, CheckKind,
445 "This lock has already been acquired");
447 }
else if (LState->isDestroyed()) {
448 reportBug(
C, BT_destroylock, MtxExpr, CheckKind,
449 "This lock has already been destroyed");
457 SVal RetVal =
Call.getReturnValue();
461 case PthreadSemantics:
462 std::tie(lockFail, lockSucc) = state->assume(*DefinedRetVal);
465 std::tie(lockSucc, lockFail) = state->assume(*DefinedRetVal);
468 llvm_unreachable(
"Unknown tryLock locking semantics");
470 assert(lockFail && lockSucc);
471 C.addTransition(lockFail);
475 }
else if (Semantics == PthreadSemantics) {
477 SVal RetVal =
Call.getReturnValue();
481 lockSucc = state->assume(*DefinedRetVal,
false);
488 assert((Semantics == XNUSemantics) &&
"Unknown locking semantics");
493 lockSucc = lockSucc->add<LockSet>(lockR);
494 lockSucc = lockSucc->set<LockMap>(lockR, LockState::getLocked());
495 C.addTransition(lockSucc);
498void PthreadLockChecker::ReleaseAnyLock(
const CallEvent &
Call,
500 CheckerKind CheckKind)
const {
501 ReleaseLockAux(
Call,
C,
Call.getArgExpr(0),
Call.getArgSVal(0), CheckKind);
504void PthreadLockChecker::ReleaseLockAux(
const CallEvent &
Call,
507 CheckerKind CheckKind)
const {
508 if (!ChecksEnabled[CheckKind])
516 const SymbolRef *sym = state->get<DestroyRetVal>(lockR);
518 state = resolvePossiblyDestroyedMutex(state, lockR, sym);
520 if (
const LockState *LState = state->get<LockMap>(lockR)) {
521 if (LState->isUnlocked()) {
522 reportBug(
C, BT_doubleunlock, MtxExpr, CheckKind,
523 "This lock has already been unlocked");
525 }
else if (LState->isDestroyed()) {
526 reportBug(
C, BT_destroylock, MtxExpr, CheckKind,
527 "This lock has already been destroyed");
532 LockSetTy LS = state->get<LockSet>();
535 const MemRegion *firstLockR = LS.getHead();
536 if (firstLockR != lockR) {
537 reportBug(
C, BT_lor, MtxExpr, CheckKind,
538 "This was not the most recently acquired lock. Possible lock "
543 state = state->set<LockSet>(LS.getTail());
546 state = state->set<LockMap>(lockR, LockState::getUnlocked());
547 C.addTransition(state);
550void PthreadLockChecker::DestroyPthreadLock(
const CallEvent &
Call,
552 CheckerKind CheckKind)
const {
553 DestroyLockAux(
Call,
C,
Call.getArgExpr(0),
Call.getArgSVal(0),
554 PthreadSemantics, CheckKind);
557void PthreadLockChecker::DestroyXNULock(
const CallEvent &
Call,
559 CheckerKind CheckKind)
const {
560 DestroyLockAux(
Call,
C,
Call.getArgExpr(0),
Call.getArgSVal(0), XNUSemantics,
564void PthreadLockChecker::DestroyLockAux(
const CallEvent &
Call,
567 enum LockingSemantics Semantics,
568 CheckerKind CheckKind)
const {
569 if (!ChecksEnabled[CheckKind])
578 const SymbolRef *sym = State->get<DestroyRetVal>(LockR);
580 State = resolvePossiblyDestroyedMutex(State, LockR, sym);
582 const LockState *LState = State->get<LockMap>(LockR);
585 if (Semantics == PthreadSemantics) {
586 if (!LState || LState->isUnlocked()) {
589 State = State->remove<LockMap>(LockR);
590 C.addTransition(State);
593 State = State->set<DestroyRetVal>(LockR, sym);
594 if (LState && LState->isUnlocked())
595 State = State->set<LockMap>(
596 LockR, LockState::getUnlockedAndPossiblyDestroyed());
598 State = State->set<LockMap>(
599 LockR, LockState::getUntouchedAndPossiblyDestroyed());
600 C.addTransition(State);
604 if (!LState || LState->isUnlocked()) {
605 State = State->set<LockMap>(LockR, LockState::getDestroyed());
606 C.addTransition(State);
611 StringRef Message = LState->isLocked()
612 ?
"This lock is still locked"
613 :
"This lock has already been destroyed";
615 reportBug(
C, BT_destroylock, MtxExpr, CheckKind, Message);
619 CheckerKind CheckKind)
const {
620 InitLockAux(
Call,
C,
Call.getArgExpr(0),
Call.getArgSVal(0), CheckKind);
625 CheckerKind CheckKind)
const {
626 if (!ChecksEnabled[CheckKind])
635 const SymbolRef *sym = State->get<DestroyRetVal>(LockR);
637 State = resolvePossiblyDestroyedMutex(State, LockR, sym);
639 const struct LockState *LState = State->get<LockMap>(LockR);
640 if (!LState || LState->isDestroyed()) {
641 State = State->set<LockMap>(LockR, LockState::getUnlocked());
642 C.addTransition(State);
646 StringRef Message = LState->isLocked()
647 ?
"This lock is still being held"
648 :
"This lock has already been initialized";
650 reportBug(
C, BT_initlock, MtxExpr, CheckKind, Message);
654 std::unique_ptr<BugType> BT[],
655 const Expr *MtxExpr, CheckerKind CheckKind,
656 StringRef Desc)
const {
660 initBugType(CheckKind);
662 std::make_unique<PathSensitiveBugReport>(*BT[CheckKind], Desc, N);
664 C.emitReport(std::move(Report));
667void PthreadLockChecker::checkDeadSymbols(
SymbolReaper &SymReaper,
671 for (
auto I : State->get<DestroyRetVal>()) {
675 if (SymReaper.
isDead(I.second))
676 State = resolvePossiblyDestroyedMutex(State, I.first, &I.second);
679 for (
auto I : State->get<LockMap>()) {
682 State = State->remove<LockMap>(I.first);
683 State = State->remove<DestroyRetVal>(I.first);
691 C.addTransition(State);
700 bool IsLibraryFunction =
false;
701 if (
Call &&
Call->isGlobalCFunction()) {
703 if (PThreadCallbacks.lookup(*
Call) || FuchsiaCallbacks.
lookup(*
Call) ||
707 if (
Call->isInSystemHeader())
708 IsLibraryFunction =
true;
711 for (
auto R : Regions) {
715 if (IsLibraryFunction && !llvm::is_contained(ExplicitRegions, R))
718 State = State->remove<LockMap>(R);
719 State = State->remove<DestroyRetVal>(R);
733bool ento::shouldRegisterPthreadLockBase(
const CheckerManager &mgr) {
return true; }
735#define REGISTER_CHECKER(name) \
736 void ento::register##name(CheckerManager &mgr) { \
737 PthreadLockChecker *checker = mgr.getChecker<PthreadLockChecker>(); \
738 checker->ChecksEnabled[PthreadLockChecker::CK_##name] = true; \
739 checker->CheckNames[PthreadLockChecker::CK_##name] = \
740 mgr.getCurrentCheckerName(); \
743 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)
llvm::DenseSet< SymbolRef > InvalidatedSymbols
The JSON file list parser is used to communicate input to InstallAPI.
bool operator==(const CallGraphNode::CallRecord &LHS, const CallGraphNode::CallRecord &RHS)