748 lines · cpp
1//===--- PthreadLockChecker.cpp - Check for locking problems ---*- C++ -*--===//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 defines:10// * PthreadLockChecker, a simple lock -> unlock checker.11// Which also checks for XNU locks, which behave similarly enough to share12// code.13// * FuchsiaLocksChecker, which is also rather similar.14// * C11LockChecker which also closely follows Pthread semantics.15//16// TODO: Path notes.17//18//===----------------------------------------------------------------------===//19 20#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"21#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"22#include "clang/StaticAnalyzer/Core/Checker.h"23#include "clang/StaticAnalyzer/Core/CheckerManager.h"24#include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"25#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"26#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"27 28using namespace clang;29using namespace ento;30 31namespace {32 33struct LockState {34 enum Kind {35 Destroyed,36 Locked,37 Unlocked,38 UntouchedAndPossiblyDestroyed,39 UnlockedAndPossiblyDestroyed40 } K;41 42private:43 LockState(Kind K) : K(K) {}44 45public: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);51 }52 static LockState getUnlockedAndPossiblyDestroyed() {53 return LockState(UnlockedAndPossiblyDestroyed);54 }55 56 bool operator==(const LockState &X) const { return K == X.K; }57 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;63 }64 bool isUnlockedAndPossiblyDestroyed() const {65 return K == UnlockedAndPossiblyDestroyed;66 }67 68 void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(K); }69};70 71class PthreadLockChecker : public Checker<check::PostCall, check::DeadSymbols,72 check::RegionChanges> {73public:74 enum LockingSemantics { NotApplicable = 0, PthreadSemantics, XNUSemantics };75 enum CheckerKind {76 CK_PthreadLockChecker,77 CK_FuchsiaLockChecker,78 CK_C11LockChecker,79 CK_NumCheckKinds80 };81 bool ChecksEnabled[CK_NumCheckKinds] = {false};82 CheckerNameRef CheckNames[CK_NumCheckKinds];83 84private:85 typedef void (PthreadLockChecker::*FnCheck)(const CallEvent &Call,86 CheckerContext &C,87 CheckerKind CheckKind) const;88 CallDescriptionMap<FnCheck> PThreadCallbacks = {89 // Init.90 {{CDM::CLibrary, {"pthread_mutex_init"}, 2},91 &PthreadLockChecker::InitAnyLock},92 // TODO: pthread_rwlock_init(2 arguments).93 // TODO: lck_mtx_init(3 arguments).94 // TODO: lck_mtx_alloc_init(2 arguments) => returns the mutex.95 // TODO: lck_rw_init(3 arguments).96 // TODO: lck_rw_alloc_init(2 arguments) => returns the mutex.97 98 // Acquire.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},111 112 // Try.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},125 126 // Release.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},139 140 // Destroy.141 {{CDM::CLibrary, {"pthread_mutex_destroy"}, 1},142 &PthreadLockChecker::DestroyPthreadLock},143 {{CDM::CLibrary, {"lck_mtx_destroy"}, 2},144 &PthreadLockChecker::DestroyXNULock},145 // TODO: pthread_rwlock_destroy(1 argument).146 // TODO: lck_rw_destroy(2 arguments).147 };148 149 CallDescriptionMap<FnCheck> FuchsiaCallbacks = {150 // Init.151 {{CDM::CLibrary, {"spin_lock_init"}, 1},152 &PthreadLockChecker::InitAnyLock},153 154 // Acquire.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},163 164 // Try.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},171 172 // Release.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},179 };180 181 CallDescriptionMap<FnCheck> C11Callbacks = {182 // Init.183 {{CDM::CLibrary, {"mtx_init"}, 2}, &PthreadLockChecker::InitAnyLock},184 185 // Acquire.186 {{CDM::CLibrary, {"mtx_lock"}, 1},187 &PthreadLockChecker::AcquirePthreadLock},188 189 // Try.190 {{CDM::CLibrary, {"mtx_trylock"}, 1}, &PthreadLockChecker::TryC11Lock},191 {{CDM::CLibrary, {"mtx_timedlock"}, 2}, &PthreadLockChecker::TryC11Lock},192 193 // Release.194 {{CDM::CLibrary, {"mtx_unlock"}, 1}, &PthreadLockChecker::ReleaseAnyLock},195 196 // Destroy197 {{CDM::CLibrary, {"mtx_destroy"}, 1},198 &PthreadLockChecker::DestroyPthreadLock},199 };200 201 ProgramStateRef resolvePossiblyDestroyedMutex(ProgramStateRef state,202 const MemRegion *lockR,203 const SymbolRef *sym) const;204 void reportBug(CheckerContext &C, std::unique_ptr<BugType> BT[],205 const Expr *MtxExpr, CheckerKind CheckKind,206 StringRef Desc) const;207 208 // Init.209 void InitAnyLock(const CallEvent &Call, CheckerContext &C,210 CheckerKind CheckKind) const;211 void InitLockAux(const CallEvent &Call, CheckerContext &C,212 const Expr *MtxExpr, SVal MtxVal,213 CheckerKind CheckKind) const;214 215 // Lock, Try-lock.216 void AcquirePthreadLock(const CallEvent &Call, CheckerContext &C,217 CheckerKind CheckKind) const;218 void AcquireXNULock(const CallEvent &Call, CheckerContext &C,219 CheckerKind CheckKind) const;220 void TryPthreadLock(const CallEvent &Call, CheckerContext &C,221 CheckerKind CheckKind) const;222 void TryXNULock(const CallEvent &Call, CheckerContext &C,223 CheckerKind CheckKind) const;224 void TryFuchsiaLock(const CallEvent &Call, CheckerContext &C,225 CheckerKind CheckKind) const;226 void TryC11Lock(const CallEvent &Call, CheckerContext &C,227 CheckerKind CheckKind) const;228 void AcquireLockAux(const CallEvent &Call, CheckerContext &C,229 const Expr *MtxExpr, SVal MtxVal, bool IsTryLock,230 LockingSemantics Semantics, CheckerKind CheckKind) const;231 232 // Release.233 void ReleaseAnyLock(const CallEvent &Call, CheckerContext &C,234 CheckerKind CheckKind) const;235 void ReleaseLockAux(const CallEvent &Call, CheckerContext &C,236 const Expr *MtxExpr, SVal MtxVal,237 CheckerKind CheckKind) const;238 239 // Destroy.240 void DestroyPthreadLock(const CallEvent &Call, CheckerContext &C,241 CheckerKind CheckKind) const;242 void DestroyXNULock(const CallEvent &Call, CheckerContext &C,243 CheckerKind CheckKind) const;244 void DestroyLockAux(const CallEvent &Call, CheckerContext &C,245 const Expr *MtxExpr, SVal MtxVal,246 LockingSemantics Semantics, CheckerKind CheckKind) const;247 248public:249 void checkPostCall(const CallEvent &Call, CheckerContext &C) const;250 void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const;251 ProgramStateRef252 checkRegionChanges(ProgramStateRef State, const InvalidatedSymbols *Symbols,253 ArrayRef<const MemRegion *> ExplicitRegions,254 ArrayRef<const MemRegion *> Regions,255 const LocationContext *LCtx, const CallEvent *Call) const;256 void printState(raw_ostream &Out, ProgramStateRef State, const char *NL,257 const char *Sep) const override;258 259private: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];265 266 void initBugType(CheckerKind CheckKind) const {267 if (BT_doublelock[CheckKind])268 return;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"});279 }280};281} // end anonymous namespace282 283// A stack of locks for tracking lock-unlock order.284REGISTER_LIST_WITH_PROGRAMSTATE(LockSet, const MemRegion *)285 286// An entry for tracking lock states.287REGISTER_MAP_WITH_PROGRAMSTATE(LockMap, const MemRegion *, LockState)288 289// Return values for unresolved calls to pthread_mutex_destroy().290REGISTER_MAP_WITH_PROGRAMSTATE(DestroyRetVal, const MemRegion *, SymbolRef)291 292void PthreadLockChecker::checkPostCall(const CallEvent &Call,293 CheckerContext &C) const {294 // FIXME: Try to handle cases when the implementation was inlined rather295 // than just giving up.296 if (C.wasInlined)297 return;298 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);305}306 307// When a lock is destroyed, in some semantics(like PthreadSemantics) we are not308// sure if the destroy call has succeeded or failed, and the lock enters one of309// the 'possibly destroyed' state. There is a short time frame for the310// programmer to check the return value to see if the lock was successfully311// destroyed. Before we model the next operation over that lock, we call this312// function to see if the return value was checked by now and set the lock state313// - either to destroyed state or back to its previous state.314 315// In PthreadSemantics, pthread_mutex_destroy() returns zero if the lock is316// successfully destroyed and it returns a non-zero value otherwise.317ProgramStateRef PthreadLockChecker::resolvePossiblyDestroyedMutex(318 ProgramStateRef state, const MemRegion *lockR, const SymbolRef *sym) const {319 const LockState *lstate = state->get<LockMap>(lockR);320 // Existence in DestroyRetVal ensures existence in LockMap.321 // Existence in Destroyed also ensures that the lock state for lockR is either322 // UntouchedAndPossiblyDestroyed or UnlockedAndPossiblyDestroyed.323 assert(lstate);324 assert(lstate->isUntouchedAndPossiblyDestroyed() ||325 lstate->isUnlockedAndPossiblyDestroyed());326 327 ConstraintManager &CMgr = state->getConstraintManager();328 ConditionTruthVal retZero = CMgr.isNull(state, *sym);329 if (retZero.isConstrainedFalse()) {330 if (lstate->isUntouchedAndPossiblyDestroyed())331 state = state->remove<LockMap>(lockR);332 else if (lstate->isUnlockedAndPossiblyDestroyed())333 state = state->set<LockMap>(lockR, LockState::getUnlocked());334 } else335 state = state->set<LockMap>(lockR, LockState::getDestroyed());336 337 // Removing the map entry (lockR, sym) from DestroyRetVal as the lock state is338 // now resolved.339 state = state->remove<DestroyRetVal>(lockR);340 return state;341}342 343void PthreadLockChecker::printState(raw_ostream &Out, ProgramStateRef State,344 const char *NL, const char *Sep) const {345 LockMapTy LM = State->get<LockMap>();346 if (!LM.isEmpty()) {347 Out << Sep << "Mutex states:" << NL;348 for (auto I : LM) {349 I.first->dumpToStream(Out);350 if (I.second.isLocked())351 Out << ": locked";352 else if (I.second.isUnlocked())353 Out << ": unlocked";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";360 Out << NL;361 }362 }363 364 LockSetTy LS = State->get<LockSet>();365 if (!LS.isEmpty()) {366 Out << Sep << "Mutex lock order:" << NL;367 for (auto I : LS) {368 I->dumpToStream(Out);369 Out << NL;370 }371 }372 373 DestroyRetValTy DRV = State->get<DestroyRetVal>();374 if (!DRV.isEmpty()) {375 Out << Sep << "Mutexes in unresolved possibly destroyed state:" << NL;376 for (auto I : DRV) {377 I.first->dumpToStream(Out);378 Out << ": ";379 I.second->dumpToStream(Out);380 Out << NL;381 }382 }383}384 385void PthreadLockChecker::AcquirePthreadLock(const CallEvent &Call,386 CheckerContext &C,387 CheckerKind CheckKind) const {388 AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), false,389 PthreadSemantics, CheckKind);390}391 392void PthreadLockChecker::AcquireXNULock(const CallEvent &Call,393 CheckerContext &C,394 CheckerKind CheckKind) const {395 AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), false,396 XNUSemantics, CheckKind);397}398 399void PthreadLockChecker::TryPthreadLock(const CallEvent &Call,400 CheckerContext &C,401 CheckerKind CheckKind) const {402 AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true,403 PthreadSemantics, CheckKind);404}405 406void PthreadLockChecker::TryXNULock(const CallEvent &Call, CheckerContext &C,407 CheckerKind CheckKind) const {408 AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true,409 PthreadSemantics, CheckKind);410}411 412void PthreadLockChecker::TryFuchsiaLock(const CallEvent &Call,413 CheckerContext &C,414 CheckerKind CheckKind) const {415 AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true,416 PthreadSemantics, CheckKind);417}418 419void PthreadLockChecker::TryC11Lock(const CallEvent &Call, CheckerContext &C,420 CheckerKind CheckKind) const {421 AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true,422 PthreadSemantics, CheckKind);423}424 425void PthreadLockChecker::AcquireLockAux(const CallEvent &Call,426 CheckerContext &C, const Expr *MtxExpr,427 SVal MtxVal, bool IsTryLock,428 enum LockingSemantics Semantics,429 CheckerKind CheckKind) const {430 if (!ChecksEnabled[CheckKind])431 return;432 433 const MemRegion *lockR = MtxVal.getAsRegion();434 if (!lockR)435 return;436 437 ProgramStateRef state = C.getState();438 const SymbolRef *sym = state->get<DestroyRetVal>(lockR);439 if (sym)440 state = resolvePossiblyDestroyedMutex(state, lockR, sym);441 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");446 return;447 } else if (LState->isDestroyed()) {448 reportBug(C, BT_destroylock, MtxExpr, CheckKind,449 "This lock has already been destroyed");450 return;451 }452 }453 454 ProgramStateRef lockSucc = state;455 if (IsTryLock) {456 // Bifurcate the state, and allow a mode where the lock acquisition fails.457 SVal RetVal = Call.getReturnValue();458 if (auto DefinedRetVal = RetVal.getAs<DefinedSVal>()) {459 ProgramStateRef lockFail;460 switch (Semantics) {461 case PthreadSemantics:462 std::tie(lockFail, lockSucc) = state->assume(*DefinedRetVal);463 break;464 case XNUSemantics:465 std::tie(lockSucc, lockFail) = state->assume(*DefinedRetVal);466 break;467 default:468 llvm_unreachable("Unknown tryLock locking semantics");469 }470 assert(lockFail && lockSucc);471 C.addTransition(lockFail);472 }473 // We might want to handle the case when the mutex lock function was inlined474 // and returned an Unknown or Undefined value.475 } else if (Semantics == PthreadSemantics) {476 // Assume that the return value was 0.477 SVal RetVal = Call.getReturnValue();478 if (auto DefinedRetVal = RetVal.getAs<DefinedSVal>()) {479 // FIXME: If the lock function was inlined and returned true,480 // we need to behave sanely - at least generate sink.481 lockSucc = state->assume(*DefinedRetVal, false);482 assert(lockSucc);483 }484 // We might want to handle the case when the mutex lock function was inlined485 // and returned an Unknown or Undefined value.486 } else {487 // XNU locking semantics return void on non-try locks488 assert((Semantics == XNUSemantics) && "Unknown locking semantics");489 lockSucc = state;490 }491 492 // Record that the lock was acquired.493 lockSucc = lockSucc->add<LockSet>(lockR);494 lockSucc = lockSucc->set<LockMap>(lockR, LockState::getLocked());495 C.addTransition(lockSucc);496}497 498void PthreadLockChecker::ReleaseAnyLock(const CallEvent &Call,499 CheckerContext &C,500 CheckerKind CheckKind) const {501 ReleaseLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), CheckKind);502}503 504void PthreadLockChecker::ReleaseLockAux(const CallEvent &Call,505 CheckerContext &C, const Expr *MtxExpr,506 SVal MtxVal,507 CheckerKind CheckKind) const {508 if (!ChecksEnabled[CheckKind])509 return;510 511 const MemRegion *lockR = MtxVal.getAsRegion();512 if (!lockR)513 return;514 515 ProgramStateRef state = C.getState();516 const SymbolRef *sym = state->get<DestroyRetVal>(lockR);517 if (sym)518 state = resolvePossiblyDestroyedMutex(state, lockR, sym);519 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");524 return;525 } else if (LState->isDestroyed()) {526 reportBug(C, BT_destroylock, MtxExpr, CheckKind,527 "This lock has already been destroyed");528 return;529 }530 }531 532 LockSetTy LS = state->get<LockSet>();533 534 if (!LS.isEmpty()) {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 "539 "order reversal");540 return;541 }542 // Record that the lock was released.543 state = state->set<LockSet>(LS.getTail());544 }545 546 state = state->set<LockMap>(lockR, LockState::getUnlocked());547 C.addTransition(state);548}549 550void PthreadLockChecker::DestroyPthreadLock(const CallEvent &Call,551 CheckerContext &C,552 CheckerKind CheckKind) const {553 DestroyLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0),554 PthreadSemantics, CheckKind);555}556 557void PthreadLockChecker::DestroyXNULock(const CallEvent &Call,558 CheckerContext &C,559 CheckerKind CheckKind) const {560 DestroyLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), XNUSemantics,561 CheckKind);562}563 564void PthreadLockChecker::DestroyLockAux(const CallEvent &Call,565 CheckerContext &C, const Expr *MtxExpr,566 SVal MtxVal,567 enum LockingSemantics Semantics,568 CheckerKind CheckKind) const {569 if (!ChecksEnabled[CheckKind])570 return;571 572 const MemRegion *LockR = MtxVal.getAsRegion();573 if (!LockR)574 return;575 576 ProgramStateRef State = C.getState();577 578 const SymbolRef *sym = State->get<DestroyRetVal>(LockR);579 if (sym)580 State = resolvePossiblyDestroyedMutex(State, LockR, sym);581 582 const LockState *LState = State->get<LockMap>(LockR);583 // Checking the return value of the destroy method only in the case of584 // PthreadSemantics585 if (Semantics == PthreadSemantics) {586 if (!LState || LState->isUnlocked()) {587 SymbolRef sym = Call.getReturnValue().getAsSymbol();588 if (!sym) {589 State = State->remove<LockMap>(LockR);590 C.addTransition(State);591 return;592 }593 State = State->set<DestroyRetVal>(LockR, sym);594 if (LState && LState->isUnlocked())595 State = State->set<LockMap>(596 LockR, LockState::getUnlockedAndPossiblyDestroyed());597 else598 State = State->set<LockMap>(599 LockR, LockState::getUntouchedAndPossiblyDestroyed());600 C.addTransition(State);601 return;602 }603 } else {604 if (!LState || LState->isUnlocked()) {605 State = State->set<LockMap>(LockR, LockState::getDestroyed());606 C.addTransition(State);607 return;608 }609 }610 611 StringRef Message = LState->isLocked()612 ? "This lock is still locked"613 : "This lock has already been destroyed";614 615 reportBug(C, BT_destroylock, MtxExpr, CheckKind, Message);616}617 618void PthreadLockChecker::InitAnyLock(const CallEvent &Call, CheckerContext &C,619 CheckerKind CheckKind) const {620 InitLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), CheckKind);621}622 623void PthreadLockChecker::InitLockAux(const CallEvent &Call, CheckerContext &C,624 const Expr *MtxExpr, SVal MtxVal,625 CheckerKind CheckKind) const {626 if (!ChecksEnabled[CheckKind])627 return;628 629 const MemRegion *LockR = MtxVal.getAsRegion();630 if (!LockR)631 return;632 633 ProgramStateRef State = C.getState();634 635 const SymbolRef *sym = State->get<DestroyRetVal>(LockR);636 if (sym)637 State = resolvePossiblyDestroyedMutex(State, LockR, sym);638 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);643 return;644 }645 646 StringRef Message = LState->isLocked()647 ? "This lock is still being held"648 : "This lock has already been initialized";649 650 reportBug(C, BT_initlock, MtxExpr, CheckKind, Message);651}652 653void PthreadLockChecker::reportBug(CheckerContext &C,654 std::unique_ptr<BugType> BT[],655 const Expr *MtxExpr, CheckerKind CheckKind,656 StringRef Desc) const {657 ExplodedNode *N = C.generateErrorNode();658 if (!N)659 return;660 initBugType(CheckKind);661 auto Report =662 std::make_unique<PathSensitiveBugReport>(*BT[CheckKind], Desc, N);663 Report->addRange(MtxExpr->getSourceRange());664 C.emitReport(std::move(Report));665}666 667void PthreadLockChecker::checkDeadSymbols(SymbolReaper &SymReaper,668 CheckerContext &C) const {669 ProgramStateRef State = C.getState();670 671 for (auto I : State->get<DestroyRetVal>()) {672 // Once the return value symbol dies, no more checks can be performed673 // against it. See if the return value was checked before this point.674 // This would remove the symbol from the map as well.675 if (SymReaper.isDead(I.second))676 State = resolvePossiblyDestroyedMutex(State, I.first, &I.second);677 }678 679 for (auto I : State->get<LockMap>()) {680 // Stop tracking dead mutex regions as well.681 if (!SymReaper.isLiveRegion(I.first)) {682 State = State->remove<LockMap>(I.first);683 State = State->remove<DestroyRetVal>(I.first);684 }685 }686 687 // TODO: We probably need to clean up the lock stack as well.688 // It is tricky though: even if the mutex cannot be unlocked anymore,689 // it can still participate in lock order reversal resolution.690 691 C.addTransition(State);692}693 694ProgramStateRef PthreadLockChecker::checkRegionChanges(695 ProgramStateRef State, const InvalidatedSymbols *Symbols,696 ArrayRef<const MemRegion *> ExplicitRegions,697 ArrayRef<const MemRegion *> Regions, const LocationContext *LCtx,698 const CallEvent *Call) const {699 700 bool IsLibraryFunction = false;701 if (Call && Call->isGlobalCFunction()) {702 // Avoid invalidating mutex state when a known supported function is called.703 if (PThreadCallbacks.lookup(*Call) || FuchsiaCallbacks.lookup(*Call) ||704 C11Callbacks.lookup(*Call))705 return State;706 707 if (Call->isInSystemHeader())708 IsLibraryFunction = true;709 }710 711 for (auto R : Regions) {712 // We assume that system library function wouldn't touch the mutex unless713 // it takes the mutex explicitly as an argument.714 // FIXME: This is a bit quadratic.715 if (IsLibraryFunction && !llvm::is_contained(ExplicitRegions, R))716 continue;717 718 State = State->remove<LockMap>(R);719 State = State->remove<DestroyRetVal>(R);720 721 // TODO: We need to invalidate the lock stack as well. This is tricky722 // to implement correctly and efficiently though, because the effects723 // of mutex escapes on lock order may be fairly varied.724 }725 726 return State;727}728 729void ento::registerPthreadLockBase(CheckerManager &mgr) {730 mgr.registerChecker<PthreadLockChecker>();731}732 733bool ento::shouldRegisterPthreadLockBase(const CheckerManager &mgr) { return true; }734 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(); \741 } \742 \743 bool ento::shouldRegister##name(const CheckerManager &mgr) { return true; }744 745REGISTER_CHECKER(PthreadLockChecker)746REGISTER_CHECKER(FuchsiaLockChecker)747REGISTER_CHECKER(C11LockChecker)748