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