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-exception 6 // 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 share 12 // 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 28 using namespace clang; 29 using namespace ento; 30 31 namespace { 32 33 struct LockState { 34 enum Kind { 35 Destroyed, 36 Locked, 37 Unlocked, 38 UntouchedAndPossiblyDestroyed, 39 UnlockedAndPossiblyDestroyed 40 } K; 41 42 private: 43 LockState(Kind K) : K(K) {} 44 45 public: 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 71 class PthreadLockChecker : public Checker<check::PostCall, check::DeadSymbols, 72 check::RegionChanges> { 73 public: 74 enum LockingSemantics { NotApplicable = 0, PthreadSemantics, XNUSemantics }; 75 enum CheckerKind { 76 CK_PthreadLockChecker, 77 CK_FuchsiaLockChecker, 78 CK_C11LockChecker, 79 CK_NumCheckKinds 80 }; 81 bool ChecksEnabled[CK_NumCheckKinds] = {false}; 82 CheckerNameRef CheckNames[CK_NumCheckKinds]; 83 84 private: 85 typedef void (PthreadLockChecker::*FnCheck)(const CallEvent &Call, 86 CheckerContext &C, 87 CheckerKind CheckKind) const; 88 CallDescriptionMap<FnCheck> PThreadCallbacks = { 89 // Init. 90 {{{"pthread_mutex_init"}, 2}, &PthreadLockChecker::InitAnyLock}, 91 // TODO: pthread_rwlock_init(2 arguments). 92 // TODO: lck_mtx_init(3 arguments). 93 // TODO: lck_mtx_alloc_init(2 arguments) => returns the mutex. 94 // TODO: lck_rw_init(3 arguments). 95 // TODO: lck_rw_alloc_init(2 arguments) => returns the mutex. 96 97 // Acquire. 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}, 104 105 // Try. 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}, 112 113 // Release. 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}, 120 121 // Destroy. 122 {{{"pthread_mutex_destroy"}, 1}, &PthreadLockChecker::DestroyPthreadLock}, 123 {{{"lck_mtx_destroy"}, 2}, &PthreadLockChecker::DestroyXNULock}, 124 // TODO: pthread_rwlock_destroy(1 argument). 125 // TODO: lck_rw_destroy(2 arguments). 126 }; 127 128 CallDescriptionMap<FnCheck> FuchsiaCallbacks = { 129 // Init. 130 {{{"spin_lock_init"}, 1}, &PthreadLockChecker::InitAnyLock}, 131 132 // Acquire. 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}, 138 139 // Try. 140 {{{"spin_trylock"}, 1}, &PthreadLockChecker::TryFuchsiaLock}, 141 {{{"sync_mutex_trylock"}, 1}, &PthreadLockChecker::TryFuchsiaLock}, 142 {{{"sync_mutex_timedlock"}, 2}, &PthreadLockChecker::TryFuchsiaLock}, 143 144 // Release. 145 {{{"spin_unlock"}, 1}, &PthreadLockChecker::ReleaseAnyLock}, 146 {{{"spin_unlock_restore"}, 3}, &PthreadLockChecker::ReleaseAnyLock}, 147 {{{"sync_mutex_unlock"}, 1}, &PthreadLockChecker::ReleaseAnyLock}, 148 }; 149 150 CallDescriptionMap<FnCheck> C11Callbacks = { 151 // Init. 152 {{{"mtx_init"}, 2}, &PthreadLockChecker::InitAnyLock}, 153 154 // Acquire. 155 {{{"mtx_lock"}, 1}, &PthreadLockChecker::AcquirePthreadLock}, 156 157 // Try. 158 {{{"mtx_trylock"}, 1}, &PthreadLockChecker::TryC11Lock}, 159 {{{"mtx_timedlock"}, 2}, &PthreadLockChecker::TryC11Lock}, 160 161 // Release. 162 {{{"mtx_unlock"}, 1}, &PthreadLockChecker::ReleaseAnyLock}, 163 164 // Destroy 165 {{{"mtx_destroy"}, 1}, &PthreadLockChecker::DestroyPthreadLock}, 166 }; 167 168 ProgramStateRef resolvePossiblyDestroyedMutex(ProgramStateRef state, 169 const MemRegion *lockR, 170 const SymbolRef *sym) const; 171 void reportBug(CheckerContext &C, std::unique_ptr<BugType> BT[], 172 const Expr *MtxExpr, CheckerKind CheckKind, 173 StringRef Desc) const; 174 175 // Init. 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; 181 182 // Lock, Try-lock. 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; 198 199 // Release. 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; 205 206 // Destroy. 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; 214 215 public: 216 void checkPostCall(const CallEvent &Call, CheckerContext &C) const; 217 void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const; 218 ProgramStateRef 219 checkRegionChanges(ProgramStateRef State, const InvalidatedSymbols *Symbols, 220 ArrayRef<const MemRegion *> ExplicitRegions, 221 ArrayRef<const MemRegion *> Regions, 222 const LocationContext *LCtx, const CallEvent *Call) const; 223 void printState(raw_ostream &Out, ProgramStateRef State, const char *NL, 224 const char *Sep) const override; 225 226 private: 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]; 232 233 void initBugType(CheckerKind CheckKind) const { 234 if (BT_doublelock[CheckKind]) 235 return; 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"}); 246 } 247 }; 248 } // end anonymous namespace 249 250 // A stack of locks for tracking lock-unlock order. 251 REGISTER_LIST_WITH_PROGRAMSTATE(LockSet, const MemRegion *) 252 253 // An entry for tracking lock states. 254 REGISTER_MAP_WITH_PROGRAMSTATE(LockMap, const MemRegion *, LockState) 255 256 // Return values for unresolved calls to pthread_mutex_destroy(). 257 REGISTER_MAP_WITH_PROGRAMSTATE(DestroyRetVal, const MemRegion *, SymbolRef) 258 259 void PthreadLockChecker::checkPostCall(const CallEvent &Call, 260 CheckerContext &C) const { 261 // An additional umbrella check that all functions modeled by this checker 262 // are global C functions. 263 // TODO: Maybe make this the default behavior of CallDescription 264 // with exactly one identifier? 265 // FIXME: Try to handle cases when the implementation was inlined rather 266 // than just giving up. 267 if (!Call.isGlobalCFunction() || C.wasInlined) 268 return; 269 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); 276 } 277 278 // When a lock is destroyed, in some semantics(like PthreadSemantics) we are not 279 // sure if the destroy call has succeeded or failed, and the lock enters one of 280 // the 'possibly destroyed' state. There is a short time frame for the 281 // programmer to check the return value to see if the lock was successfully 282 // destroyed. Before we model the next operation over that lock, we call this 283 // function to see if the return value was checked by now and set the lock state 284 // - either to destroyed state or back to its previous state. 285 286 // In PthreadSemantics, pthread_mutex_destroy() returns zero if the lock is 287 // successfully destroyed and it returns a non-zero value otherwise. 288 ProgramStateRef PthreadLockChecker::resolvePossiblyDestroyedMutex( 289 ProgramStateRef state, const MemRegion *lockR, const SymbolRef *sym) const { 290 const LockState *lstate = state->get<LockMap>(lockR); 291 // Existence in DestroyRetVal ensures existence in LockMap. 292 // Existence in Destroyed also ensures that the lock state for lockR is either 293 // UntouchedAndPossiblyDestroyed or UnlockedAndPossiblyDestroyed. 294 assert(lstate->isUntouchedAndPossiblyDestroyed() || 295 lstate->isUnlockedAndPossiblyDestroyed()); 296 297 ConstraintManager &CMgr = state->getConstraintManager(); 298 ConditionTruthVal retZero = CMgr.isNull(state, *sym); 299 if (retZero.isConstrainedFalse()) { 300 if (lstate->isUntouchedAndPossiblyDestroyed()) 301 state = state->remove<LockMap>(lockR); 302 else if (lstate->isUnlockedAndPossiblyDestroyed()) 303 state = state->set<LockMap>(lockR, LockState::getUnlocked()); 304 } else 305 state = state->set<LockMap>(lockR, LockState::getDestroyed()); 306 307 // Removing the map entry (lockR, sym) from DestroyRetVal as the lock state is 308 // now resolved. 309 state = state->remove<DestroyRetVal>(lockR); 310 return state; 311 } 312 313 void PthreadLockChecker::printState(raw_ostream &Out, ProgramStateRef State, 314 const char *NL, const char *Sep) const { 315 LockMapTy LM = State->get<LockMap>(); 316 if (!LM.isEmpty()) { 317 Out << Sep << "Mutex states:" << NL; 318 for (auto I : LM) { 319 I.first->dumpToStream(Out); 320 if (I.second.isLocked()) 321 Out << ": locked"; 322 else if (I.second.isUnlocked()) 323 Out << ": unlocked"; 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"; 330 Out << NL; 331 } 332 } 333 334 LockSetTy LS = State->get<LockSet>(); 335 if (!LS.isEmpty()) { 336 Out << Sep << "Mutex lock order:" << NL; 337 for (auto I : LS) { 338 I->dumpToStream(Out); 339 Out << NL; 340 } 341 } 342 343 DestroyRetValTy DRV = State->get<DestroyRetVal>(); 344 if (!DRV.isEmpty()) { 345 Out << Sep << "Mutexes in unresolved possibly destroyed state:" << NL; 346 for (auto I : DRV) { 347 I.first->dumpToStream(Out); 348 Out << ": "; 349 I.second->dumpToStream(Out); 350 Out << NL; 351 } 352 } 353 } 354 355 void PthreadLockChecker::AcquirePthreadLock(const CallEvent &Call, 356 CheckerContext &C, 357 CheckerKind CheckKind) const { 358 AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), false, 359 PthreadSemantics, CheckKind); 360 } 361 362 void PthreadLockChecker::AcquireXNULock(const CallEvent &Call, 363 CheckerContext &C, 364 CheckerKind CheckKind) const { 365 AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), false, 366 XNUSemantics, CheckKind); 367 } 368 369 void PthreadLockChecker::TryPthreadLock(const CallEvent &Call, 370 CheckerContext &C, 371 CheckerKind CheckKind) const { 372 AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true, 373 PthreadSemantics, CheckKind); 374 } 375 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); 380 } 381 382 void PthreadLockChecker::TryFuchsiaLock(const CallEvent &Call, 383 CheckerContext &C, 384 CheckerKind CheckKind) const { 385 AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true, 386 PthreadSemantics, CheckKind); 387 } 388 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); 393 } 394 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]) 401 return; 402 403 const MemRegion *lockR = MtxVal.getAsRegion(); 404 if (!lockR) 405 return; 406 407 ProgramStateRef state = C.getState(); 408 const SymbolRef *sym = state->get<DestroyRetVal>(lockR); 409 if (sym) 410 state = resolvePossiblyDestroyedMutex(state, lockR, sym); 411 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"); 416 return; 417 } else if (LState->isDestroyed()) { 418 reportBug(C, BT_destroylock, MtxExpr, CheckKind, 419 "This lock has already been destroyed"); 420 return; 421 } 422 } 423 424 ProgramStateRef lockSucc = state; 425 if (IsTryLock) { 426 // Bifurcate the state, and allow a mode where the lock acquisition fails. 427 SVal RetVal = Call.getReturnValue(); 428 if (auto DefinedRetVal = RetVal.getAs<DefinedSVal>()) { 429 ProgramStateRef lockFail; 430 switch (Semantics) { 431 case PthreadSemantics: 432 std::tie(lockFail, lockSucc) = state->assume(*DefinedRetVal); 433 break; 434 case XNUSemantics: 435 std::tie(lockSucc, lockFail) = state->assume(*DefinedRetVal); 436 break; 437 default: 438 llvm_unreachable("Unknown tryLock locking semantics"); 439 } 440 assert(lockFail && lockSucc); 441 C.addTransition(lockFail); 442 } 443 // We might want to handle the case when the mutex lock function was inlined 444 // and returned an Unknown or Undefined value. 445 } else if (Semantics == PthreadSemantics) { 446 // Assume that the return value was 0. 447 SVal RetVal = Call.getReturnValue(); 448 if (auto DefinedRetVal = RetVal.getAs<DefinedSVal>()) { 449 // FIXME: If the lock function was inlined and returned true, 450 // we need to behave sanely - at least generate sink. 451 lockSucc = state->assume(*DefinedRetVal, false); 452 assert(lockSucc); 453 } 454 // We might want to handle the case when the mutex lock function was inlined 455 // and returned an Unknown or Undefined value. 456 } else { 457 // XNU locking semantics return void on non-try locks 458 assert((Semantics == XNUSemantics) && "Unknown locking semantics"); 459 lockSucc = state; 460 } 461 462 // Record that the lock was acquired. 463 lockSucc = lockSucc->add<LockSet>(lockR); 464 lockSucc = lockSucc->set<LockMap>(lockR, LockState::getLocked()); 465 C.addTransition(lockSucc); 466 } 467 468 void PthreadLockChecker::ReleaseAnyLock(const CallEvent &Call, 469 CheckerContext &C, 470 CheckerKind CheckKind) const { 471 ReleaseLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), CheckKind); 472 } 473 474 void PthreadLockChecker::ReleaseLockAux(const CallEvent &Call, 475 CheckerContext &C, const Expr *MtxExpr, 476 SVal MtxVal, 477 CheckerKind CheckKind) const { 478 if (!ChecksEnabled[CheckKind]) 479 return; 480 481 const MemRegion *lockR = MtxVal.getAsRegion(); 482 if (!lockR) 483 return; 484 485 ProgramStateRef state = C.getState(); 486 const SymbolRef *sym = state->get<DestroyRetVal>(lockR); 487 if (sym) 488 state = resolvePossiblyDestroyedMutex(state, lockR, sym); 489 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"); 494 return; 495 } else if (LState->isDestroyed()) { 496 reportBug(C, BT_destroylock, MtxExpr, CheckKind, 497 "This lock has already been destroyed"); 498 return; 499 } 500 } 501 502 LockSetTy LS = state->get<LockSet>(); 503 504 if (!LS.isEmpty()) { 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 " 509 "order reversal"); 510 return; 511 } 512 // Record that the lock was released. 513 state = state->set<LockSet>(LS.getTail()); 514 } 515 516 state = state->set<LockMap>(lockR, LockState::getUnlocked()); 517 C.addTransition(state); 518 } 519 520 void PthreadLockChecker::DestroyPthreadLock(const CallEvent &Call, 521 CheckerContext &C, 522 CheckerKind CheckKind) const { 523 DestroyLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), 524 PthreadSemantics, CheckKind); 525 } 526 527 void PthreadLockChecker::DestroyXNULock(const CallEvent &Call, 528 CheckerContext &C, 529 CheckerKind CheckKind) const { 530 DestroyLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), XNUSemantics, 531 CheckKind); 532 } 533 534 void PthreadLockChecker::DestroyLockAux(const CallEvent &Call, 535 CheckerContext &C, const Expr *MtxExpr, 536 SVal MtxVal, 537 enum LockingSemantics Semantics, 538 CheckerKind CheckKind) const { 539 if (!ChecksEnabled[CheckKind]) 540 return; 541 542 const MemRegion *LockR = MtxVal.getAsRegion(); 543 if (!LockR) 544 return; 545 546 ProgramStateRef State = C.getState(); 547 548 const SymbolRef *sym = State->get<DestroyRetVal>(LockR); 549 if (sym) 550 State = resolvePossiblyDestroyedMutex(State, LockR, sym); 551 552 const LockState *LState = State->get<LockMap>(LockR); 553 // Checking the return value of the destroy method only in the case of 554 // PthreadSemantics 555 if (Semantics == PthreadSemantics) { 556 if (!LState || LState->isUnlocked()) { 557 SymbolRef sym = Call.getReturnValue().getAsSymbol(); 558 if (!sym) { 559 State = State->remove<LockMap>(LockR); 560 C.addTransition(State); 561 return; 562 } 563 State = State->set<DestroyRetVal>(LockR, sym); 564 if (LState && LState->isUnlocked()) 565 State = State->set<LockMap>( 566 LockR, LockState::getUnlockedAndPossiblyDestroyed()); 567 else 568 State = State->set<LockMap>( 569 LockR, LockState::getUntouchedAndPossiblyDestroyed()); 570 C.addTransition(State); 571 return; 572 } 573 } else { 574 if (!LState || LState->isUnlocked()) { 575 State = State->set<LockMap>(LockR, LockState::getDestroyed()); 576 C.addTransition(State); 577 return; 578 } 579 } 580 581 StringRef Message = LState->isLocked() 582 ? "This lock is still locked" 583 : "This lock has already been destroyed"; 584 585 reportBug(C, BT_destroylock, MtxExpr, CheckKind, Message); 586 } 587 588 void PthreadLockChecker::InitAnyLock(const CallEvent &Call, CheckerContext &C, 589 CheckerKind CheckKind) const { 590 InitLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), CheckKind); 591 } 592 593 void PthreadLockChecker::InitLockAux(const CallEvent &Call, CheckerContext &C, 594 const Expr *MtxExpr, SVal MtxVal, 595 CheckerKind CheckKind) const { 596 if (!ChecksEnabled[CheckKind]) 597 return; 598 599 const MemRegion *LockR = MtxVal.getAsRegion(); 600 if (!LockR) 601 return; 602 603 ProgramStateRef State = C.getState(); 604 605 const SymbolRef *sym = State->get<DestroyRetVal>(LockR); 606 if (sym) 607 State = resolvePossiblyDestroyedMutex(State, LockR, sym); 608 609 const struct LockState *LState = State->get<LockMap>(LockR); 610 if (!LState || LState->isDestroyed()) { 611 State = State->set<LockMap>(LockR, LockState::getUnlocked()); 612 C.addTransition(State); 613 return; 614 } 615 616 StringRef Message = LState->isLocked() 617 ? "This lock is still being held" 618 : "This lock has already been initialized"; 619 620 reportBug(C, BT_initlock, MtxExpr, CheckKind, Message); 621 } 622 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(); 628 if (!N) 629 return; 630 initBugType(CheckKind); 631 auto Report = 632 std::make_unique<PathSensitiveBugReport>(*BT[CheckKind], Desc, N); 633 Report->addRange(MtxExpr->getSourceRange()); 634 C.emitReport(std::move(Report)); 635 } 636 637 void PthreadLockChecker::checkDeadSymbols(SymbolReaper &SymReaper, 638 CheckerContext &C) const { 639 ProgramStateRef State = C.getState(); 640 641 for (auto I : State->get<DestroyRetVal>()) { 642 // Once the return value symbol dies, no more checks can be performed 643 // against it. See if the return value was checked before this point. 644 // This would remove the symbol from the map as well. 645 if (SymReaper.isDead(I.second)) 646 State = resolvePossiblyDestroyedMutex(State, I.first, &I.second); 647 } 648 649 for (auto I : State->get<LockMap>()) { 650 // Stop tracking dead mutex regions as well. 651 if (!SymReaper.isLiveRegion(I.first)) { 652 State = State->remove<LockMap>(I.first); 653 State = State->remove<DestroyRetVal>(I.first); 654 } 655 } 656 657 // TODO: We probably need to clean up the lock stack as well. 658 // It is tricky though: even if the mutex cannot be unlocked anymore, 659 // it can still participate in lock order reversal resolution. 660 661 C.addTransition(State); 662 } 663 664 ProgramStateRef PthreadLockChecker::checkRegionChanges( 665 ProgramStateRef State, const InvalidatedSymbols *Symbols, 666 ArrayRef<const MemRegion *> ExplicitRegions, 667 ArrayRef<const MemRegion *> Regions, const LocationContext *LCtx, 668 const CallEvent *Call) const { 669 670 bool IsLibraryFunction = false; 671 if (Call && Call->isGlobalCFunction()) { 672 // Avoid invalidating mutex state when a known supported function is called. 673 if (PThreadCallbacks.lookup(*Call) || FuchsiaCallbacks.lookup(*Call) || 674 C11Callbacks.lookup(*Call)) 675 return State; 676 677 if (Call->isInSystemHeader()) 678 IsLibraryFunction = true; 679 } 680 681 for (auto R : Regions) { 682 // We assume that system library function wouldn't touch the mutex unless 683 // it takes the mutex explicitly as an argument. 684 // FIXME: This is a bit quadratic. 685 if (IsLibraryFunction && !llvm::is_contained(ExplicitRegions, R)) 686 continue; 687 688 State = State->remove<LockMap>(R); 689 State = State->remove<DestroyRetVal>(R); 690 691 // TODO: We need to invalidate the lock stack as well. This is tricky 692 // to implement correctly and efficiently though, because the effects 693 // of mutex escapes on lock order may be fairly varied. 694 } 695 696 return State; 697 } 698 699 void ento::registerPthreadLockBase(CheckerManager &mgr) { 700 mgr.registerChecker<PthreadLockChecker>(); 701 } 702 703 bool ento::shouldRegisterPthreadLockBase(const CheckerManager &mgr) { return true; } 704 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(); \ 711 } \ 712 \ 713 bool ento::shouldRegister##name(const CheckerManager &mgr) { return true; } 714 715 REGISTER_CHECKER(PthreadLockChecker) 716 REGISTER_CHECKER(FuchsiaLockChecker) 717 REGISTER_CHECKER(C11LockChecker) 718