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/CallEvent.h" 25 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 26 27 using namespace clang; 28 using namespace ento; 29 30 namespace { 31 32 struct LockState { 33 enum Kind { 34 Destroyed, 35 Locked, 36 Unlocked, 37 UntouchedAndPossiblyDestroyed, 38 UnlockedAndPossiblyDestroyed 39 } K; 40 41 private: 42 LockState(Kind K) : K(K) {} 43 44 public: 45 static LockState getLocked() { return LockState(Locked); } 46 static LockState getUnlocked() { return LockState(Unlocked); } 47 static LockState getDestroyed() { return LockState(Destroyed); } 48 static LockState getUntouchedAndPossiblyDestroyed() { 49 return LockState(UntouchedAndPossiblyDestroyed); 50 } 51 static LockState getUnlockedAndPossiblyDestroyed() { 52 return LockState(UnlockedAndPossiblyDestroyed); 53 } 54 55 bool operator==(const LockState &X) const { return K == X.K; } 56 57 bool isLocked() const { return K == Locked; } 58 bool isUnlocked() const { return K == Unlocked; } 59 bool isDestroyed() const { return K == Destroyed; } 60 bool isUntouchedAndPossiblyDestroyed() const { 61 return K == UntouchedAndPossiblyDestroyed; 62 } 63 bool isUnlockedAndPossiblyDestroyed() const { 64 return K == UnlockedAndPossiblyDestroyed; 65 } 66 67 void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(K); } 68 }; 69 70 class PthreadLockChecker : public Checker<check::PostCall, check::DeadSymbols, 71 check::RegionChanges> { 72 public: 73 enum LockingSemantics { NotApplicable = 0, PthreadSemantics, XNUSemantics }; 74 enum CheckerKind { 75 CK_PthreadLockChecker, 76 CK_FuchsiaLockChecker, 77 CK_C11LockChecker, 78 CK_NumCheckKinds 79 }; 80 DefaultBool ChecksEnabled[CK_NumCheckKinds]; 81 CheckerNameRef CheckNames[CK_NumCheckKinds]; 82 83 private: 84 typedef void (PthreadLockChecker::*FnCheck)(const CallEvent &Call, 85 CheckerContext &C, 86 CheckerKind CheckKind) const; 87 CallDescriptionMap<FnCheck> PThreadCallbacks = { 88 // Init. 89 {{"pthread_mutex_init", 2}, &PthreadLockChecker::InitAnyLock}, 90 // TODO: pthread_rwlock_init(2 arguments). 91 // TODO: lck_mtx_init(3 arguments). 92 // TODO: lck_mtx_alloc_init(2 arguments) => returns the mutex. 93 // TODO: lck_rw_init(3 arguments). 94 // TODO: lck_rw_alloc_init(2 arguments) => returns the mutex. 95 96 // Acquire. 97 {{"pthread_mutex_lock", 1}, &PthreadLockChecker::AcquirePthreadLock}, 98 {{"pthread_rwlock_rdlock", 1}, &PthreadLockChecker::AcquirePthreadLock}, 99 {{"pthread_rwlock_wrlock", 1}, &PthreadLockChecker::AcquirePthreadLock}, 100 {{"lck_mtx_lock", 1}, &PthreadLockChecker::AcquireXNULock}, 101 {{"lck_rw_lock_exclusive", 1}, &PthreadLockChecker::AcquireXNULock}, 102 {{"lck_rw_lock_shared", 1}, &PthreadLockChecker::AcquireXNULock}, 103 104 // Try. 105 {{"pthread_mutex_trylock", 1}, &PthreadLockChecker::TryPthreadLock}, 106 {{"pthread_rwlock_tryrdlock", 1}, &PthreadLockChecker::TryPthreadLock}, 107 {{"pthread_rwlock_trywrlock", 1}, &PthreadLockChecker::TryPthreadLock}, 108 {{"lck_mtx_try_lock", 1}, &PthreadLockChecker::TryXNULock}, 109 {{"lck_rw_try_lock_exclusive", 1}, &PthreadLockChecker::TryXNULock}, 110 {{"lck_rw_try_lock_shared", 1}, &PthreadLockChecker::TryXNULock}, 111 112 // Release. 113 {{"pthread_mutex_unlock", 1}, &PthreadLockChecker::ReleaseAnyLock}, 114 {{"pthread_rwlock_unlock", 1}, &PthreadLockChecker::ReleaseAnyLock}, 115 {{"lck_mtx_unlock", 1}, &PthreadLockChecker::ReleaseAnyLock}, 116 {{"lck_rw_unlock_exclusive", 1}, &PthreadLockChecker::ReleaseAnyLock}, 117 {{"lck_rw_unlock_shared", 1}, &PthreadLockChecker::ReleaseAnyLock}, 118 {{"lck_rw_done", 1}, &PthreadLockChecker::ReleaseAnyLock}, 119 120 // Destroy. 121 {{"pthread_mutex_destroy", 1}, &PthreadLockChecker::DestroyPthreadLock}, 122 {{"lck_mtx_destroy", 2}, &PthreadLockChecker::DestroyXNULock}, 123 // TODO: pthread_rwlock_destroy(1 argument). 124 // TODO: lck_rw_destroy(2 arguments). 125 }; 126 127 CallDescriptionMap<FnCheck> FuchsiaCallbacks = { 128 // Init. 129 {{"spin_lock_init", 1}, &PthreadLockChecker::InitAnyLock}, 130 131 // Acquire. 132 {{"spin_lock", 1}, &PthreadLockChecker::AcquirePthreadLock}, 133 {{"spin_lock_save", 3}, &PthreadLockChecker::AcquirePthreadLock}, 134 {{"sync_mutex_lock", 1}, &PthreadLockChecker::AcquirePthreadLock}, 135 {{"sync_mutex_lock_with_waiter", 1}, 136 &PthreadLockChecker::AcquirePthreadLock}, 137 138 // Try. 139 {{"spin_trylock", 1}, &PthreadLockChecker::TryFuchsiaLock}, 140 {{"sync_mutex_trylock", 1}, &PthreadLockChecker::TryFuchsiaLock}, 141 {{"sync_mutex_timedlock", 2}, &PthreadLockChecker::TryFuchsiaLock}, 142 143 // Release. 144 {{"spin_unlock", 1}, &PthreadLockChecker::ReleaseAnyLock}, 145 {{"spin_unlock_restore", 3}, &PthreadLockChecker::ReleaseAnyLock}, 146 {{"sync_mutex_unlock", 1}, &PthreadLockChecker::ReleaseAnyLock}, 147 }; 148 149 CallDescriptionMap<FnCheck> C11Callbacks = { 150 // Init. 151 {{"mtx_init", 2}, &PthreadLockChecker::InitAnyLock}, 152 153 // Acquire. 154 {{"mtx_lock", 1}, &PthreadLockChecker::AcquirePthreadLock}, 155 156 // Try. 157 {{"mtx_trylock", 1}, &PthreadLockChecker::TryC11Lock}, 158 {{"mtx_timedlock", 2}, &PthreadLockChecker::TryC11Lock}, 159 160 // Release. 161 {{"mtx_unlock", 1}, &PthreadLockChecker::ReleaseAnyLock}, 162 163 // Destroy 164 {{"mtx_destroy", 1}, &PthreadLockChecker::DestroyPthreadLock}, 165 }; 166 167 ProgramStateRef resolvePossiblyDestroyedMutex(ProgramStateRef state, 168 const MemRegion *lockR, 169 const SymbolRef *sym) const; 170 void reportBug(CheckerContext &C, std::unique_ptr<BugType> BT[], 171 const Expr *MtxExpr, CheckerKind CheckKind, 172 StringRef Desc) const; 173 174 // Init. 175 void InitAnyLock(const CallEvent &Call, CheckerContext &C, 176 CheckerKind CheckKind) const; 177 void InitLockAux(const CallEvent &Call, CheckerContext &C, 178 const Expr *MtxExpr, SVal MtxVal, 179 CheckerKind CheckKind) const; 180 181 // Lock, Try-lock. 182 void AcquirePthreadLock(const CallEvent &Call, CheckerContext &C, 183 CheckerKind CheckKind) const; 184 void AcquireXNULock(const CallEvent &Call, CheckerContext &C, 185 CheckerKind CheckKind) const; 186 void TryPthreadLock(const CallEvent &Call, CheckerContext &C, 187 CheckerKind CheckKind) const; 188 void TryXNULock(const CallEvent &Call, CheckerContext &C, 189 CheckerKind CheckKind) const; 190 void TryFuchsiaLock(const CallEvent &Call, CheckerContext &C, 191 CheckerKind CheckKind) const; 192 void TryC11Lock(const CallEvent &Call, CheckerContext &C, 193 CheckerKind CheckKind) const; 194 void AcquireLockAux(const CallEvent &Call, CheckerContext &C, 195 const Expr *MtxExpr, SVal MtxVal, bool IsTryLock, 196 LockingSemantics Semantics, CheckerKind CheckKind) const; 197 198 // Release. 199 void ReleaseAnyLock(const CallEvent &Call, CheckerContext &C, 200 CheckerKind CheckKind) const; 201 void ReleaseLockAux(const CallEvent &Call, CheckerContext &C, 202 const Expr *MtxExpr, SVal MtxVal, 203 CheckerKind CheckKind) const; 204 205 // Destroy. 206 void DestroyPthreadLock(const CallEvent &Call, CheckerContext &C, 207 CheckerKind CheckKind) const; 208 void DestroyXNULock(const CallEvent &Call, CheckerContext &C, 209 CheckerKind CheckKind) const; 210 void DestroyLockAux(const CallEvent &Call, CheckerContext &C, 211 const Expr *MtxExpr, SVal MtxVal, 212 LockingSemantics Semantics, CheckerKind CheckKind) const; 213 214 public: 215 void checkPostCall(const CallEvent &Call, CheckerContext &C) const; 216 void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const; 217 ProgramStateRef 218 checkRegionChanges(ProgramStateRef State, const InvalidatedSymbols *Symbols, 219 ArrayRef<const MemRegion *> ExplicitRegions, 220 ArrayRef<const MemRegion *> Regions, 221 const LocationContext *LCtx, const CallEvent *Call) const; 222 void printState(raw_ostream &Out, ProgramStateRef State, const char *NL, 223 const char *Sep) const override; 224 225 private: 226 mutable std::unique_ptr<BugType> BT_doublelock[CK_NumCheckKinds]; 227 mutable std::unique_ptr<BugType> BT_doubleunlock[CK_NumCheckKinds]; 228 mutable std::unique_ptr<BugType> BT_destroylock[CK_NumCheckKinds]; 229 mutable std::unique_ptr<BugType> BT_initlock[CK_NumCheckKinds]; 230 mutable std::unique_ptr<BugType> BT_lor[CK_NumCheckKinds]; 231 232 void initBugType(CheckerKind CheckKind) const { 233 if (BT_doublelock[CheckKind]) 234 return; 235 BT_doublelock[CheckKind].reset( 236 new BugType{CheckNames[CheckKind], "Double locking", "Lock checker"}); 237 BT_doubleunlock[CheckKind].reset( 238 new BugType{CheckNames[CheckKind], "Double unlocking", "Lock checker"}); 239 BT_destroylock[CheckKind].reset(new BugType{ 240 CheckNames[CheckKind], "Use destroyed lock", "Lock checker"}); 241 BT_initlock[CheckKind].reset(new BugType{ 242 CheckNames[CheckKind], "Init invalid lock", "Lock checker"}); 243 BT_lor[CheckKind].reset(new BugType{CheckNames[CheckKind], 244 "Lock order reversal", "Lock checker"}); 245 } 246 }; 247 } // end anonymous namespace 248 249 // A stack of locks for tracking lock-unlock order. 250 REGISTER_LIST_WITH_PROGRAMSTATE(LockSet, const MemRegion *) 251 252 // An entry for tracking lock states. 253 REGISTER_MAP_WITH_PROGRAMSTATE(LockMap, const MemRegion *, LockState) 254 255 // Return values for unresolved calls to pthread_mutex_destroy(). 256 REGISTER_MAP_WITH_PROGRAMSTATE(DestroyRetVal, const MemRegion *, SymbolRef) 257 258 void PthreadLockChecker::checkPostCall(const CallEvent &Call, 259 CheckerContext &C) const { 260 // An additional umbrella check that all functions modeled by this checker 261 // are global C functions. 262 // TODO: Maybe make this the default behavior of CallDescription 263 // with exactly one identifier? 264 // FIXME: Try to handle cases when the implementation was inlined rather 265 // than just giving up. 266 if (!Call.isGlobalCFunction() || C.wasInlined) 267 return; 268 269 if (const FnCheck *Callback = PThreadCallbacks.lookup(Call)) 270 (this->**Callback)(Call, C, CK_PthreadLockChecker); 271 else if (const FnCheck *Callback = FuchsiaCallbacks.lookup(Call)) 272 (this->**Callback)(Call, C, CK_FuchsiaLockChecker); 273 else if (const FnCheck *Callback = C11Callbacks.lookup(Call)) 274 (this->**Callback)(Call, C, CK_C11LockChecker); 275 } 276 277 // When a lock is destroyed, in some semantics(like PthreadSemantics) we are not 278 // sure if the destroy call has succeeded or failed, and the lock enters one of 279 // the 'possibly destroyed' state. There is a short time frame for the 280 // programmer to check the return value to see if the lock was successfully 281 // destroyed. Before we model the next operation over that lock, we call this 282 // function to see if the return value was checked by now and set the lock state 283 // - either to destroyed state or back to its previous state. 284 285 // In PthreadSemantics, pthread_mutex_destroy() returns zero if the lock is 286 // successfully destroyed and it returns a non-zero value otherwise. 287 ProgramStateRef PthreadLockChecker::resolvePossiblyDestroyedMutex( 288 ProgramStateRef state, const MemRegion *lockR, const SymbolRef *sym) const { 289 const LockState *lstate = state->get<LockMap>(lockR); 290 // Existence in DestroyRetVal ensures existence in LockMap. 291 // Existence in Destroyed also ensures that the lock state for lockR is either 292 // UntouchedAndPossiblyDestroyed or UnlockedAndPossiblyDestroyed. 293 assert(lstate->isUntouchedAndPossiblyDestroyed() || 294 lstate->isUnlockedAndPossiblyDestroyed()); 295 296 ConstraintManager &CMgr = state->getConstraintManager(); 297 ConditionTruthVal retZero = CMgr.isNull(state, *sym); 298 if (retZero.isConstrainedFalse()) { 299 if (lstate->isUntouchedAndPossiblyDestroyed()) 300 state = state->remove<LockMap>(lockR); 301 else if (lstate->isUnlockedAndPossiblyDestroyed()) 302 state = state->set<LockMap>(lockR, LockState::getUnlocked()); 303 } else 304 state = state->set<LockMap>(lockR, LockState::getDestroyed()); 305 306 // Removing the map entry (lockR, sym) from DestroyRetVal as the lock state is 307 // now resolved. 308 state = state->remove<DestroyRetVal>(lockR); 309 return state; 310 } 311 312 void PthreadLockChecker::printState(raw_ostream &Out, ProgramStateRef State, 313 const char *NL, const char *Sep) const { 314 LockMapTy LM = State->get<LockMap>(); 315 if (!LM.isEmpty()) { 316 Out << Sep << "Mutex states:" << NL; 317 for (auto I : LM) { 318 I.first->dumpToStream(Out); 319 if (I.second.isLocked()) 320 Out << ": locked"; 321 else if (I.second.isUnlocked()) 322 Out << ": unlocked"; 323 else if (I.second.isDestroyed()) 324 Out << ": destroyed"; 325 else if (I.second.isUntouchedAndPossiblyDestroyed()) 326 Out << ": not tracked, possibly destroyed"; 327 else if (I.second.isUnlockedAndPossiblyDestroyed()) 328 Out << ": unlocked, possibly destroyed"; 329 Out << NL; 330 } 331 } 332 333 LockSetTy LS = State->get<LockSet>(); 334 if (!LS.isEmpty()) { 335 Out << Sep << "Mutex lock order:" << NL; 336 for (auto I : LS) { 337 I->dumpToStream(Out); 338 Out << NL; 339 } 340 } 341 342 DestroyRetValTy DRV = State->get<DestroyRetVal>(); 343 if (!DRV.isEmpty()) { 344 Out << Sep << "Mutexes in unresolved possibly destroyed state:" << NL; 345 for (auto I : DRV) { 346 I.first->dumpToStream(Out); 347 Out << ": "; 348 I.second->dumpToStream(Out); 349 Out << NL; 350 } 351 } 352 } 353 354 void PthreadLockChecker::AcquirePthreadLock(const CallEvent &Call, 355 CheckerContext &C, 356 CheckerKind CheckKind) const { 357 AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), false, 358 PthreadSemantics, CheckKind); 359 } 360 361 void PthreadLockChecker::AcquireXNULock(const CallEvent &Call, 362 CheckerContext &C, 363 CheckerKind CheckKind) const { 364 AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), false, 365 XNUSemantics, CheckKind); 366 } 367 368 void PthreadLockChecker::TryPthreadLock(const CallEvent &Call, 369 CheckerContext &C, 370 CheckerKind CheckKind) const { 371 AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true, 372 PthreadSemantics, CheckKind); 373 } 374 375 void PthreadLockChecker::TryXNULock(const CallEvent &Call, CheckerContext &C, 376 CheckerKind CheckKind) const { 377 AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true, 378 PthreadSemantics, CheckKind); 379 } 380 381 void PthreadLockChecker::TryFuchsiaLock(const CallEvent &Call, 382 CheckerContext &C, 383 CheckerKind CheckKind) const { 384 AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true, 385 PthreadSemantics, CheckKind); 386 } 387 388 void PthreadLockChecker::TryC11Lock(const CallEvent &Call, CheckerContext &C, 389 CheckerKind CheckKind) const { 390 AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true, 391 PthreadSemantics, CheckKind); 392 } 393 394 void PthreadLockChecker::AcquireLockAux(const CallEvent &Call, 395 CheckerContext &C, const Expr *MtxExpr, 396 SVal MtxVal, bool IsTryLock, 397 enum LockingSemantics Semantics, 398 CheckerKind CheckKind) const { 399 if (!ChecksEnabled[CheckKind]) 400 return; 401 402 const MemRegion *lockR = MtxVal.getAsRegion(); 403 if (!lockR) 404 return; 405 406 ProgramStateRef state = C.getState(); 407 const SymbolRef *sym = state->get<DestroyRetVal>(lockR); 408 if (sym) 409 state = resolvePossiblyDestroyedMutex(state, lockR, sym); 410 411 if (const LockState *LState = state->get<LockMap>(lockR)) { 412 if (LState->isLocked()) { 413 reportBug(C, BT_doublelock, MtxExpr, CheckKind, 414 "This lock has already been acquired"); 415 return; 416 } else if (LState->isDestroyed()) { 417 reportBug(C, BT_destroylock, MtxExpr, CheckKind, 418 "This lock has already been destroyed"); 419 return; 420 } 421 } 422 423 ProgramStateRef lockSucc = state; 424 if (IsTryLock) { 425 // Bifurcate the state, and allow a mode where the lock acquisition fails. 426 SVal RetVal = Call.getReturnValue(); 427 if (auto DefinedRetVal = RetVal.getAs<DefinedSVal>()) { 428 ProgramStateRef lockFail; 429 switch (Semantics) { 430 case PthreadSemantics: 431 std::tie(lockFail, lockSucc) = state->assume(*DefinedRetVal); 432 break; 433 case XNUSemantics: 434 std::tie(lockSucc, lockFail) = state->assume(*DefinedRetVal); 435 break; 436 default: 437 llvm_unreachable("Unknown tryLock locking semantics"); 438 } 439 assert(lockFail && lockSucc); 440 C.addTransition(lockFail); 441 } 442 // We might want to handle the case when the mutex lock function was inlined 443 // and returned an Unknown or Undefined value. 444 } else if (Semantics == PthreadSemantics) { 445 // Assume that the return value was 0. 446 SVal RetVal = Call.getReturnValue(); 447 if (auto DefinedRetVal = RetVal.getAs<DefinedSVal>()) { 448 // FIXME: If the lock function was inlined and returned true, 449 // we need to behave sanely - at least generate sink. 450 lockSucc = state->assume(*DefinedRetVal, false); 451 assert(lockSucc); 452 } 453 // We might want to handle the case when the mutex lock function was inlined 454 // and returned an Unknown or Undefined value. 455 } else { 456 // XNU locking semantics return void on non-try locks 457 assert((Semantics == XNUSemantics) && "Unknown locking semantics"); 458 lockSucc = state; 459 } 460 461 // Record that the lock was acquired. 462 lockSucc = lockSucc->add<LockSet>(lockR); 463 lockSucc = lockSucc->set<LockMap>(lockR, LockState::getLocked()); 464 C.addTransition(lockSucc); 465 } 466 467 void PthreadLockChecker::ReleaseAnyLock(const CallEvent &Call, 468 CheckerContext &C, 469 CheckerKind CheckKind) const { 470 ReleaseLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), CheckKind); 471 } 472 473 void PthreadLockChecker::ReleaseLockAux(const CallEvent &Call, 474 CheckerContext &C, const Expr *MtxExpr, 475 SVal MtxVal, 476 CheckerKind CheckKind) const { 477 if (!ChecksEnabled[CheckKind]) 478 return; 479 480 const MemRegion *lockR = MtxVal.getAsRegion(); 481 if (!lockR) 482 return; 483 484 ProgramStateRef state = C.getState(); 485 const SymbolRef *sym = state->get<DestroyRetVal>(lockR); 486 if (sym) 487 state = resolvePossiblyDestroyedMutex(state, lockR, sym); 488 489 if (const LockState *LState = state->get<LockMap>(lockR)) { 490 if (LState->isUnlocked()) { 491 reportBug(C, BT_doubleunlock, MtxExpr, CheckKind, 492 "This lock has already been unlocked"); 493 return; 494 } else if (LState->isDestroyed()) { 495 reportBug(C, BT_destroylock, MtxExpr, CheckKind, 496 "This lock has already been destroyed"); 497 return; 498 } 499 } 500 501 LockSetTy LS = state->get<LockSet>(); 502 503 if (!LS.isEmpty()) { 504 const MemRegion *firstLockR = LS.getHead(); 505 if (firstLockR != lockR) { 506 reportBug(C, BT_lor, MtxExpr, CheckKind, 507 "This was not the most recently acquired lock. Possible lock " 508 "order reversal"); 509 return; 510 } 511 // Record that the lock was released. 512 state = state->set<LockSet>(LS.getTail()); 513 } 514 515 state = state->set<LockMap>(lockR, LockState::getUnlocked()); 516 C.addTransition(state); 517 } 518 519 void PthreadLockChecker::DestroyPthreadLock(const CallEvent &Call, 520 CheckerContext &C, 521 CheckerKind CheckKind) const { 522 DestroyLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), 523 PthreadSemantics, CheckKind); 524 } 525 526 void PthreadLockChecker::DestroyXNULock(const CallEvent &Call, 527 CheckerContext &C, 528 CheckerKind CheckKind) const { 529 DestroyLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), XNUSemantics, 530 CheckKind); 531 } 532 533 void PthreadLockChecker::DestroyLockAux(const CallEvent &Call, 534 CheckerContext &C, const Expr *MtxExpr, 535 SVal MtxVal, 536 enum LockingSemantics Semantics, 537 CheckerKind CheckKind) const { 538 if (!ChecksEnabled[CheckKind]) 539 return; 540 541 const MemRegion *LockR = MtxVal.getAsRegion(); 542 if (!LockR) 543 return; 544 545 ProgramStateRef State = C.getState(); 546 547 const SymbolRef *sym = State->get<DestroyRetVal>(LockR); 548 if (sym) 549 State = resolvePossiblyDestroyedMutex(State, LockR, sym); 550 551 const LockState *LState = State->get<LockMap>(LockR); 552 // Checking the return value of the destroy method only in the case of 553 // PthreadSemantics 554 if (Semantics == PthreadSemantics) { 555 if (!LState || LState->isUnlocked()) { 556 SymbolRef sym = Call.getReturnValue().getAsSymbol(); 557 if (!sym) { 558 State = State->remove<LockMap>(LockR); 559 C.addTransition(State); 560 return; 561 } 562 State = State->set<DestroyRetVal>(LockR, sym); 563 if (LState && LState->isUnlocked()) 564 State = State->set<LockMap>( 565 LockR, LockState::getUnlockedAndPossiblyDestroyed()); 566 else 567 State = State->set<LockMap>( 568 LockR, LockState::getUntouchedAndPossiblyDestroyed()); 569 C.addTransition(State); 570 return; 571 } 572 } else { 573 if (!LState || LState->isUnlocked()) { 574 State = State->set<LockMap>(LockR, LockState::getDestroyed()); 575 C.addTransition(State); 576 return; 577 } 578 } 579 580 StringRef Message = LState->isLocked() 581 ? "This lock is still locked" 582 : "This lock has already been destroyed"; 583 584 reportBug(C, BT_destroylock, MtxExpr, CheckKind, Message); 585 } 586 587 void PthreadLockChecker::InitAnyLock(const CallEvent &Call, CheckerContext &C, 588 CheckerKind CheckKind) const { 589 InitLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), CheckKind); 590 } 591 592 void PthreadLockChecker::InitLockAux(const CallEvent &Call, CheckerContext &C, 593 const Expr *MtxExpr, SVal MtxVal, 594 CheckerKind CheckKind) const { 595 if (!ChecksEnabled[CheckKind]) 596 return; 597 598 const MemRegion *LockR = MtxVal.getAsRegion(); 599 if (!LockR) 600 return; 601 602 ProgramStateRef State = C.getState(); 603 604 const SymbolRef *sym = State->get<DestroyRetVal>(LockR); 605 if (sym) 606 State = resolvePossiblyDestroyedMutex(State, LockR, sym); 607 608 const struct LockState *LState = State->get<LockMap>(LockR); 609 if (!LState || LState->isDestroyed()) { 610 State = State->set<LockMap>(LockR, LockState::getUnlocked()); 611 C.addTransition(State); 612 return; 613 } 614 615 StringRef Message = LState->isLocked() 616 ? "This lock is still being held" 617 : "This lock has already been initialized"; 618 619 reportBug(C, BT_initlock, MtxExpr, CheckKind, Message); 620 } 621 622 void PthreadLockChecker::reportBug(CheckerContext &C, 623 std::unique_ptr<BugType> BT[], 624 const Expr *MtxExpr, CheckerKind CheckKind, 625 StringRef Desc) const { 626 ExplodedNode *N = C.generateErrorNode(); 627 if (!N) 628 return; 629 initBugType(CheckKind); 630 auto Report = 631 std::make_unique<PathSensitiveBugReport>(*BT[CheckKind], Desc, N); 632 Report->addRange(MtxExpr->getSourceRange()); 633 C.emitReport(std::move(Report)); 634 } 635 636 void PthreadLockChecker::checkDeadSymbols(SymbolReaper &SymReaper, 637 CheckerContext &C) const { 638 ProgramStateRef State = C.getState(); 639 640 for (auto I : State->get<DestroyRetVal>()) { 641 // Once the return value symbol dies, no more checks can be performed 642 // against it. See if the return value was checked before this point. 643 // This would remove the symbol from the map as well. 644 if (SymReaper.isDead(I.second)) 645 State = resolvePossiblyDestroyedMutex(State, I.first, &I.second); 646 } 647 648 for (auto I : State->get<LockMap>()) { 649 // Stop tracking dead mutex regions as well. 650 if (!SymReaper.isLiveRegion(I.first)) { 651 State = State->remove<LockMap>(I.first); 652 State = State->remove<DestroyRetVal>(I.first); 653 } 654 } 655 656 // TODO: We probably need to clean up the lock stack as well. 657 // It is tricky though: even if the mutex cannot be unlocked anymore, 658 // it can still participate in lock order reversal resolution. 659 660 C.addTransition(State); 661 } 662 663 ProgramStateRef PthreadLockChecker::checkRegionChanges( 664 ProgramStateRef State, const InvalidatedSymbols *Symbols, 665 ArrayRef<const MemRegion *> ExplicitRegions, 666 ArrayRef<const MemRegion *> Regions, const LocationContext *LCtx, 667 const CallEvent *Call) const { 668 669 bool IsLibraryFunction = false; 670 if (Call && Call->isGlobalCFunction()) { 671 // Avoid invalidating mutex state when a known supported function is called. 672 if (PThreadCallbacks.lookup(*Call) || FuchsiaCallbacks.lookup(*Call) || 673 C11Callbacks.lookup(*Call)) 674 return State; 675 676 if (Call->isInSystemHeader()) 677 IsLibraryFunction = true; 678 } 679 680 for (auto R : Regions) { 681 // We assume that system library function wouldn't touch the mutex unless 682 // it takes the mutex explicitly as an argument. 683 // FIXME: This is a bit quadratic. 684 if (IsLibraryFunction && 685 std::find(ExplicitRegions.begin(), ExplicitRegions.end(), R) == 686 ExplicitRegions.end()) 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