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