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