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); 295 assert(lstate->isUntouchedAndPossiblyDestroyed() || 296 lstate->isUnlockedAndPossiblyDestroyed()); 297 298 ConstraintManager &CMgr = state->getConstraintManager(); 299 ConditionTruthVal retZero = CMgr.isNull(state, *sym); 300 if (retZero.isConstrainedFalse()) { 301 if (lstate->isUntouchedAndPossiblyDestroyed()) 302 state = state->remove<LockMap>(lockR); 303 else if (lstate->isUnlockedAndPossiblyDestroyed()) 304 state = state->set<LockMap>(lockR, LockState::getUnlocked()); 305 } else 306 state = state->set<LockMap>(lockR, LockState::getDestroyed()); 307 308 // Removing the map entry (lockR, sym) from DestroyRetVal as the lock state is 309 // now resolved. 310 state = state->remove<DestroyRetVal>(lockR); 311 return state; 312 } 313 314 void PthreadLockChecker::printState(raw_ostream &Out, ProgramStateRef State, 315 const char *NL, const char *Sep) const { 316 LockMapTy LM = State->get<LockMap>(); 317 if (!LM.isEmpty()) { 318 Out << Sep << "Mutex states:" << NL; 319 for (auto I : LM) { 320 I.first->dumpToStream(Out); 321 if (I.second.isLocked()) 322 Out << ": locked"; 323 else if (I.second.isUnlocked()) 324 Out << ": unlocked"; 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"; 331 Out << NL; 332 } 333 } 334 335 LockSetTy LS = State->get<LockSet>(); 336 if (!LS.isEmpty()) { 337 Out << Sep << "Mutex lock order:" << NL; 338 for (auto I : LS) { 339 I->dumpToStream(Out); 340 Out << NL; 341 } 342 } 343 344 DestroyRetValTy DRV = State->get<DestroyRetVal>(); 345 if (!DRV.isEmpty()) { 346 Out << Sep << "Mutexes in unresolved possibly destroyed state:" << NL; 347 for (auto I : DRV) { 348 I.first->dumpToStream(Out); 349 Out << ": "; 350 I.second->dumpToStream(Out); 351 Out << NL; 352 } 353 } 354 } 355 356 void PthreadLockChecker::AcquirePthreadLock(const CallEvent &Call, 357 CheckerContext &C, 358 CheckerKind CheckKind) const { 359 AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), false, 360 PthreadSemantics, CheckKind); 361 } 362 363 void PthreadLockChecker::AcquireXNULock(const CallEvent &Call, 364 CheckerContext &C, 365 CheckerKind CheckKind) const { 366 AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), false, 367 XNUSemantics, CheckKind); 368 } 369 370 void PthreadLockChecker::TryPthreadLock(const CallEvent &Call, 371 CheckerContext &C, 372 CheckerKind CheckKind) const { 373 AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true, 374 PthreadSemantics, CheckKind); 375 } 376 377 void PthreadLockChecker::TryXNULock(const CallEvent &Call, CheckerContext &C, 378 CheckerKind CheckKind) const { 379 AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true, 380 PthreadSemantics, CheckKind); 381 } 382 383 void PthreadLockChecker::TryFuchsiaLock(const CallEvent &Call, 384 CheckerContext &C, 385 CheckerKind CheckKind) const { 386 AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true, 387 PthreadSemantics, CheckKind); 388 } 389 390 void PthreadLockChecker::TryC11Lock(const CallEvent &Call, CheckerContext &C, 391 CheckerKind CheckKind) const { 392 AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true, 393 PthreadSemantics, CheckKind); 394 } 395 396 void PthreadLockChecker::AcquireLockAux(const CallEvent &Call, 397 CheckerContext &C, const Expr *MtxExpr, 398 SVal MtxVal, bool IsTryLock, 399 enum LockingSemantics Semantics, 400 CheckerKind CheckKind) const { 401 if (!ChecksEnabled[CheckKind]) 402 return; 403 404 const MemRegion *lockR = MtxVal.getAsRegion(); 405 if (!lockR) 406 return; 407 408 ProgramStateRef state = C.getState(); 409 const SymbolRef *sym = state->get<DestroyRetVal>(lockR); 410 if (sym) 411 state = resolvePossiblyDestroyedMutex(state, lockR, sym); 412 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"); 417 return; 418 } else if (LState->isDestroyed()) { 419 reportBug(C, BT_destroylock, MtxExpr, CheckKind, 420 "This lock has already been destroyed"); 421 return; 422 } 423 } 424 425 ProgramStateRef lockSucc = state; 426 if (IsTryLock) { 427 // Bifurcate the state, and allow a mode where the lock acquisition fails. 428 SVal RetVal = Call.getReturnValue(); 429 if (auto DefinedRetVal = RetVal.getAs<DefinedSVal>()) { 430 ProgramStateRef lockFail; 431 switch (Semantics) { 432 case PthreadSemantics: 433 std::tie(lockFail, lockSucc) = state->assume(*DefinedRetVal); 434 break; 435 case XNUSemantics: 436 std::tie(lockSucc, lockFail) = state->assume(*DefinedRetVal); 437 break; 438 default: 439 llvm_unreachable("Unknown tryLock locking semantics"); 440 } 441 assert(lockFail && lockSucc); 442 C.addTransition(lockFail); 443 } 444 // We might want to handle the case when the mutex lock function was inlined 445 // and returned an Unknown or Undefined value. 446 } else if (Semantics == PthreadSemantics) { 447 // Assume that the return value was 0. 448 SVal RetVal = Call.getReturnValue(); 449 if (auto DefinedRetVal = RetVal.getAs<DefinedSVal>()) { 450 // FIXME: If the lock function was inlined and returned true, 451 // we need to behave sanely - at least generate sink. 452 lockSucc = state->assume(*DefinedRetVal, false); 453 assert(lockSucc); 454 } 455 // We might want to handle the case when the mutex lock function was inlined 456 // and returned an Unknown or Undefined value. 457 } else { 458 // XNU locking semantics return void on non-try locks 459 assert((Semantics == XNUSemantics) && "Unknown locking semantics"); 460 lockSucc = state; 461 } 462 463 // Record that the lock was acquired. 464 lockSucc = lockSucc->add<LockSet>(lockR); 465 lockSucc = lockSucc->set<LockMap>(lockR, LockState::getLocked()); 466 C.addTransition(lockSucc); 467 } 468 469 void PthreadLockChecker::ReleaseAnyLock(const CallEvent &Call, 470 CheckerContext &C, 471 CheckerKind CheckKind) const { 472 ReleaseLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), CheckKind); 473 } 474 475 void PthreadLockChecker::ReleaseLockAux(const CallEvent &Call, 476 CheckerContext &C, const Expr *MtxExpr, 477 SVal MtxVal, 478 CheckerKind CheckKind) const { 479 if (!ChecksEnabled[CheckKind]) 480 return; 481 482 const MemRegion *lockR = MtxVal.getAsRegion(); 483 if (!lockR) 484 return; 485 486 ProgramStateRef state = C.getState(); 487 const SymbolRef *sym = state->get<DestroyRetVal>(lockR); 488 if (sym) 489 state = resolvePossiblyDestroyedMutex(state, lockR, sym); 490 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"); 495 return; 496 } else if (LState->isDestroyed()) { 497 reportBug(C, BT_destroylock, MtxExpr, CheckKind, 498 "This lock has already been destroyed"); 499 return; 500 } 501 } 502 503 LockSetTy LS = state->get<LockSet>(); 504 505 if (!LS.isEmpty()) { 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 " 510 "order reversal"); 511 return; 512 } 513 // Record that the lock was released. 514 state = state->set<LockSet>(LS.getTail()); 515 } 516 517 state = state->set<LockMap>(lockR, LockState::getUnlocked()); 518 C.addTransition(state); 519 } 520 521 void PthreadLockChecker::DestroyPthreadLock(const CallEvent &Call, 522 CheckerContext &C, 523 CheckerKind CheckKind) const { 524 DestroyLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), 525 PthreadSemantics, CheckKind); 526 } 527 528 void PthreadLockChecker::DestroyXNULock(const CallEvent &Call, 529 CheckerContext &C, 530 CheckerKind CheckKind) const { 531 DestroyLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), XNUSemantics, 532 CheckKind); 533 } 534 535 void PthreadLockChecker::DestroyLockAux(const CallEvent &Call, 536 CheckerContext &C, const Expr *MtxExpr, 537 SVal MtxVal, 538 enum LockingSemantics Semantics, 539 CheckerKind CheckKind) const { 540 if (!ChecksEnabled[CheckKind]) 541 return; 542 543 const MemRegion *LockR = MtxVal.getAsRegion(); 544 if (!LockR) 545 return; 546 547 ProgramStateRef State = C.getState(); 548 549 const SymbolRef *sym = State->get<DestroyRetVal>(LockR); 550 if (sym) 551 State = resolvePossiblyDestroyedMutex(State, LockR, sym); 552 553 const LockState *LState = State->get<LockMap>(LockR); 554 // Checking the return value of the destroy method only in the case of 555 // PthreadSemantics 556 if (Semantics == PthreadSemantics) { 557 if (!LState || LState->isUnlocked()) { 558 SymbolRef sym = Call.getReturnValue().getAsSymbol(); 559 if (!sym) { 560 State = State->remove<LockMap>(LockR); 561 C.addTransition(State); 562 return; 563 } 564 State = State->set<DestroyRetVal>(LockR, sym); 565 if (LState && LState->isUnlocked()) 566 State = State->set<LockMap>( 567 LockR, LockState::getUnlockedAndPossiblyDestroyed()); 568 else 569 State = State->set<LockMap>( 570 LockR, LockState::getUntouchedAndPossiblyDestroyed()); 571 C.addTransition(State); 572 return; 573 } 574 } else { 575 if (!LState || LState->isUnlocked()) { 576 State = State->set<LockMap>(LockR, LockState::getDestroyed()); 577 C.addTransition(State); 578 return; 579 } 580 } 581 582 StringRef Message = LState->isLocked() 583 ? "This lock is still locked" 584 : "This lock has already been destroyed"; 585 586 reportBug(C, BT_destroylock, MtxExpr, CheckKind, Message); 587 } 588 589 void PthreadLockChecker::InitAnyLock(const CallEvent &Call, CheckerContext &C, 590 CheckerKind CheckKind) const { 591 InitLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), CheckKind); 592 } 593 594 void PthreadLockChecker::InitLockAux(const CallEvent &Call, CheckerContext &C, 595 const Expr *MtxExpr, SVal MtxVal, 596 CheckerKind CheckKind) const { 597 if (!ChecksEnabled[CheckKind]) 598 return; 599 600 const MemRegion *LockR = MtxVal.getAsRegion(); 601 if (!LockR) 602 return; 603 604 ProgramStateRef State = C.getState(); 605 606 const SymbolRef *sym = State->get<DestroyRetVal>(LockR); 607 if (sym) 608 State = resolvePossiblyDestroyedMutex(State, LockR, sym); 609 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); 614 return; 615 } 616 617 StringRef Message = LState->isLocked() 618 ? "This lock is still being held" 619 : "This lock has already been initialized"; 620 621 reportBug(C, BT_initlock, MtxExpr, CheckKind, Message); 622 } 623 624 void PthreadLockChecker::reportBug(CheckerContext &C, 625 std::unique_ptr<BugType> BT[], 626 const Expr *MtxExpr, CheckerKind CheckKind, 627 StringRef Desc) const { 628 ExplodedNode *N = C.generateErrorNode(); 629 if (!N) 630 return; 631 initBugType(CheckKind); 632 auto Report = 633 std::make_unique<PathSensitiveBugReport>(*BT[CheckKind], Desc, N); 634 Report->addRange(MtxExpr->getSourceRange()); 635 C.emitReport(std::move(Report)); 636 } 637 638 void PthreadLockChecker::checkDeadSymbols(SymbolReaper &SymReaper, 639 CheckerContext &C) const { 640 ProgramStateRef State = C.getState(); 641 642 for (auto I : State->get<DestroyRetVal>()) { 643 // Once the return value symbol dies, no more checks can be performed 644 // against it. See if the return value was checked before this point. 645 // This would remove the symbol from the map as well. 646 if (SymReaper.isDead(I.second)) 647 State = resolvePossiblyDestroyedMutex(State, I.first, &I.second); 648 } 649 650 for (auto I : State->get<LockMap>()) { 651 // Stop tracking dead mutex regions as well. 652 if (!SymReaper.isLiveRegion(I.first)) { 653 State = State->remove<LockMap>(I.first); 654 State = State->remove<DestroyRetVal>(I.first); 655 } 656 } 657 658 // TODO: We probably need to clean up the lock stack as well. 659 // It is tricky though: even if the mutex cannot be unlocked anymore, 660 // it can still participate in lock order reversal resolution. 661 662 C.addTransition(State); 663 } 664 665 ProgramStateRef PthreadLockChecker::checkRegionChanges( 666 ProgramStateRef State, const InvalidatedSymbols *Symbols, 667 ArrayRef<const MemRegion *> ExplicitRegions, 668 ArrayRef<const MemRegion *> Regions, const LocationContext *LCtx, 669 const CallEvent *Call) const { 670 671 bool IsLibraryFunction = false; 672 if (Call && Call->isGlobalCFunction()) { 673 // Avoid invalidating mutex state when a known supported function is called. 674 if (PThreadCallbacks.lookup(*Call) || FuchsiaCallbacks.lookup(*Call) || 675 C11Callbacks.lookup(*Call)) 676 return State; 677 678 if (Call->isInSystemHeader()) 679 IsLibraryFunction = true; 680 } 681 682 for (auto R : Regions) { 683 // We assume that system library function wouldn't touch the mutex unless 684 // it takes the mutex explicitly as an argument. 685 // FIXME: This is a bit quadratic. 686 if (IsLibraryFunction && !llvm::is_contained(ExplicitRegions, R)) 687 continue; 688 689 State = State->remove<LockMap>(R); 690 State = State->remove<DestroyRetVal>(R); 691 692 // TODO: We need to invalidate the lock stack as well. This is tricky 693 // to implement correctly and efficiently though, because the effects 694 // of mutex escapes on lock order may be fairly varied. 695 } 696 697 return State; 698 } 699 700 void ento::registerPthreadLockBase(CheckerManager &mgr) { 701 mgr.registerChecker<PthreadLockChecker>(); 702 } 703 704 bool ento::shouldRegisterPthreadLockBase(const CheckerManager &mgr) { return true; } 705 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(); \ 712 } \ 713 \ 714 bool ento::shouldRegister##name(const CheckerManager &mgr) { return true; } 715 716 REGISTER_CHECKER(PthreadLockChecker) 717 REGISTER_CHECKER(FuchsiaLockChecker) 718 REGISTER_CHECKER(C11LockChecker) 719