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 defines PthreadLockChecker, a simple lock -> unlock checker. 10 // Also handles XNU locks, which behave similarly enough to share code. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h" 15 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 16 #include "clang/StaticAnalyzer/Core/Checker.h" 17 #include "clang/StaticAnalyzer/Core/CheckerManager.h" 18 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 19 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" 20 21 using namespace clang; 22 using namespace ento; 23 24 namespace { 25 26 struct LockState { 27 enum Kind { 28 Destroyed, 29 Locked, 30 Unlocked, 31 UntouchedAndPossiblyDestroyed, 32 UnlockedAndPossiblyDestroyed 33 } K; 34 35 private: 36 LockState(Kind K) : K(K) {} 37 38 public: 39 static LockState getLocked() { return LockState(Locked); } 40 static LockState getUnlocked() { return LockState(Unlocked); } 41 static LockState getDestroyed() { return LockState(Destroyed); } 42 static LockState getUntouchedAndPossiblyDestroyed() { 43 return LockState(UntouchedAndPossiblyDestroyed); 44 } 45 static LockState getUnlockedAndPossiblyDestroyed() { 46 return LockState(UnlockedAndPossiblyDestroyed); 47 } 48 49 bool operator==(const LockState &X) const { 50 return K == X.K; 51 } 52 53 bool isLocked() const { return K == Locked; } 54 bool isUnlocked() const { return K == Unlocked; } 55 bool isDestroyed() const { return K == Destroyed; } 56 bool isUntouchedAndPossiblyDestroyed() const { 57 return K == UntouchedAndPossiblyDestroyed; 58 } 59 bool isUnlockedAndPossiblyDestroyed() const { 60 return K == UnlockedAndPossiblyDestroyed; 61 } 62 63 void Profile(llvm::FoldingSetNodeID &ID) const { 64 ID.AddInteger(K); 65 } 66 }; 67 68 class PthreadLockChecker 69 : public Checker<check::PostCall, check::DeadSymbols> { 70 BugType BT_doublelock{this, "Double locking", "Lock checker"}, 71 BT_doubleunlock{this, "Double unlocking", "Lock checker"}, 72 BT_destroylock{this, "Use destroyed lock", "Lock checker"}, 73 BT_initlock{this, "Init invalid lock", "Lock checker"}, 74 BT_lor{this, "Lock order reversal", "Lock checker"}; 75 76 enum LockingSemantics { 77 NotApplicable = 0, 78 PthreadSemantics, 79 XNUSemantics 80 }; 81 82 typedef void (PthreadLockChecker::*FnCheck)(const CallEvent &Call, 83 CheckerContext &C) const; 84 CallDescriptionMap<FnCheck> Callbacks = { 85 // Init. 86 {{"pthread_mutex_init", 2}, &PthreadLockChecker::InitAnyLock}, 87 // TODO: pthread_rwlock_init(2 arguments). 88 // TODO: lck_mtx_init(3 arguments). 89 // TODO: lck_mtx_alloc_init(2 arguments) => returns the mutex. 90 // TODO: lck_rw_init(3 arguments). 91 // TODO: lck_rw_alloc_init(2 arguments) => returns the mutex. 92 93 // Acquire. 94 {{"pthread_mutex_lock", 1}, &PthreadLockChecker::AcquirePthreadLock}, 95 {{"pthread_rwlock_rdlock", 1}, &PthreadLockChecker::AcquirePthreadLock}, 96 {{"pthread_rwlock_wrlock", 1}, &PthreadLockChecker::AcquirePthreadLock}, 97 {{"lck_mtx_lock", 1}, &PthreadLockChecker::AcquireXNULock}, 98 {{"lck_rw_lock_exclusive", 1}, &PthreadLockChecker::AcquireXNULock}, 99 {{"lck_rw_lock_shared", 1}, &PthreadLockChecker::AcquireXNULock}, 100 101 // Try. 102 {{"pthread_mutex_trylock", 1}, &PthreadLockChecker::TryPthreadLock}, 103 {{"pthread_rwlock_tryrdlock", 1}, &PthreadLockChecker::TryPthreadLock}, 104 {{"pthread_rwlock_trywrlock", 1}, &PthreadLockChecker::TryPthreadLock}, 105 {{"lck_mtx_try_lock", 1}, &PthreadLockChecker::TryXNULock}, 106 {{"lck_rw_try_lock_exclusive", 1}, &PthreadLockChecker::TryXNULock}, 107 {{"lck_rw_try_lock_shared", 1}, &PthreadLockChecker::TryXNULock}, 108 109 // Release. 110 {{"pthread_mutex_unlock", 1}, &PthreadLockChecker::ReleaseAnyLock}, 111 {{"pthread_rwlock_unlock", 1}, &PthreadLockChecker::ReleaseAnyLock}, 112 {{"lck_mtx_unlock", 1}, &PthreadLockChecker::ReleaseAnyLock}, 113 {{"lck_rw_unlock_exclusive", 1}, &PthreadLockChecker::ReleaseAnyLock}, 114 {{"lck_rw_unlock_shared", 1}, &PthreadLockChecker::ReleaseAnyLock}, 115 {{"lck_rw_done", 1}, &PthreadLockChecker::ReleaseAnyLock}, 116 117 // Destroy. 118 {{"pthread_mutex_destroy", 1}, &PthreadLockChecker::DestroyPthreadLock}, 119 {{"lck_mtx_destroy", 2}, &PthreadLockChecker::DestroyXNULock}, 120 // TODO: pthread_rwlock_destroy(1 argument). 121 // TODO: lck_rw_destroy(2 arguments). 122 }; 123 124 ProgramStateRef resolvePossiblyDestroyedMutex(ProgramStateRef state, 125 const MemRegion *lockR, 126 const SymbolRef *sym) const; 127 void reportUseDestroyedBug(const CallEvent &Call, CheckerContext &C, 128 unsigned ArgNo) const; 129 130 // Init. 131 void InitAnyLock(const CallEvent &Call, CheckerContext &C) const; 132 void InitLockAux(const CallEvent &Call, CheckerContext &C, unsigned ArgNo, 133 SVal Lock) const; 134 135 // Lock, Try-lock. 136 void AcquirePthreadLock(const CallEvent &Call, CheckerContext &C) const; 137 void AcquireXNULock(const CallEvent &Call, CheckerContext &C) const; 138 void TryPthreadLock(const CallEvent &Call, CheckerContext &C) const; 139 void TryXNULock(const CallEvent &Call, CheckerContext &C) const; 140 void AcquireLockAux(const CallEvent &Call, CheckerContext &C, unsigned ArgNo, 141 SVal lock, bool isTryLock, 142 enum LockingSemantics semantics) const; 143 144 // Release. 145 void ReleaseAnyLock(const CallEvent &Call, CheckerContext &C) const; 146 void ReleaseLockAux(const CallEvent &Call, CheckerContext &C, unsigned ArgNo, 147 SVal lock) const; 148 149 // Destroy. 150 void DestroyPthreadLock(const CallEvent &Call, CheckerContext &C) const; 151 void DestroyXNULock(const CallEvent &Call, CheckerContext &C) const; 152 void DestroyLockAux(const CallEvent &Call, CheckerContext &C, unsigned ArgNo, 153 SVal Lock, enum LockingSemantics semantics) const; 154 155 public: 156 void checkPostCall(const CallEvent &Call, CheckerContext &C) const; 157 void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const; 158 void printState(raw_ostream &Out, ProgramStateRef State, 159 const char *NL, const char *Sep) const override; 160 }; 161 } // end anonymous namespace 162 163 // A stack of locks for tracking lock-unlock order. 164 REGISTER_LIST_WITH_PROGRAMSTATE(LockSet, const MemRegion *) 165 166 // An entry for tracking lock states. 167 REGISTER_MAP_WITH_PROGRAMSTATE(LockMap, const MemRegion *, LockState) 168 169 // Return values for unresolved calls to pthread_mutex_destroy(). 170 REGISTER_MAP_WITH_PROGRAMSTATE(DestroyRetVal, const MemRegion *, SymbolRef) 171 172 void PthreadLockChecker::checkPostCall(const CallEvent &Call, 173 CheckerContext &C) const { 174 // An additional umbrella check that all functions modeled by this checker 175 // are global C functions. 176 // TODO: Maybe make this the default behavior of CallDescription 177 // with exactly one identifier? 178 if (!Call.isGlobalCFunction()) 179 return; 180 181 if (const FnCheck *Callback = Callbacks.lookup(Call)) 182 (this->**Callback)(Call, C); 183 } 184 185 186 // When a lock is destroyed, in some semantics(like PthreadSemantics) we are not 187 // sure if the destroy call has succeeded or failed, and the lock enters one of 188 // the 'possibly destroyed' state. There is a short time frame for the 189 // programmer to check the return value to see if the lock was successfully 190 // destroyed. Before we model the next operation over that lock, we call this 191 // function to see if the return value was checked by now and set the lock state 192 // - either to destroyed state or back to its previous state. 193 194 // In PthreadSemantics, pthread_mutex_destroy() returns zero if the lock is 195 // successfully destroyed and it returns a non-zero value otherwise. 196 ProgramStateRef PthreadLockChecker::resolvePossiblyDestroyedMutex( 197 ProgramStateRef state, const MemRegion *lockR, const SymbolRef *sym) const { 198 const LockState *lstate = state->get<LockMap>(lockR); 199 // Existence in DestroyRetVal ensures existence in LockMap. 200 // Existence in Destroyed also ensures that the lock state for lockR is either 201 // UntouchedAndPossiblyDestroyed or UnlockedAndPossiblyDestroyed. 202 assert(lstate->isUntouchedAndPossiblyDestroyed() || 203 lstate->isUnlockedAndPossiblyDestroyed()); 204 205 ConstraintManager &CMgr = state->getConstraintManager(); 206 ConditionTruthVal retZero = CMgr.isNull(state, *sym); 207 if (retZero.isConstrainedFalse()) { 208 if (lstate->isUntouchedAndPossiblyDestroyed()) 209 state = state->remove<LockMap>(lockR); 210 else if (lstate->isUnlockedAndPossiblyDestroyed()) 211 state = state->set<LockMap>(lockR, LockState::getUnlocked()); 212 } else 213 state = state->set<LockMap>(lockR, LockState::getDestroyed()); 214 215 // Removing the map entry (lockR, sym) from DestroyRetVal as the lock state is 216 // now resolved. 217 state = state->remove<DestroyRetVal>(lockR); 218 return state; 219 } 220 221 void PthreadLockChecker::printState(raw_ostream &Out, ProgramStateRef State, 222 const char *NL, const char *Sep) const { 223 LockMapTy LM = State->get<LockMap>(); 224 if (!LM.isEmpty()) { 225 Out << Sep << "Mutex states:" << NL; 226 for (auto I : LM) { 227 I.first->dumpToStream(Out); 228 if (I.second.isLocked()) 229 Out << ": locked"; 230 else if (I.second.isUnlocked()) 231 Out << ": unlocked"; 232 else if (I.second.isDestroyed()) 233 Out << ": destroyed"; 234 else if (I.second.isUntouchedAndPossiblyDestroyed()) 235 Out << ": not tracked, possibly destroyed"; 236 else if (I.second.isUnlockedAndPossiblyDestroyed()) 237 Out << ": unlocked, possibly destroyed"; 238 Out << NL; 239 } 240 } 241 242 LockSetTy LS = State->get<LockSet>(); 243 if (!LS.isEmpty()) { 244 Out << Sep << "Mutex lock order:" << NL; 245 for (auto I: LS) { 246 I->dumpToStream(Out); 247 Out << NL; 248 } 249 } 250 251 // TODO: Dump destroyed mutex symbols? 252 } 253 254 void PthreadLockChecker::AcquirePthreadLock(const CallEvent &Call, 255 CheckerContext &C) const { 256 AcquireLockAux(Call, C, 0, Call.getArgSVal(0), false, PthreadSemantics); 257 } 258 259 void PthreadLockChecker::AcquireXNULock(const CallEvent &Call, 260 CheckerContext &C) const { 261 AcquireLockAux(Call, C, 0, Call.getArgSVal(0), false, XNUSemantics); 262 } 263 264 void PthreadLockChecker::TryPthreadLock(const CallEvent &Call, 265 CheckerContext &C) const { 266 AcquireLockAux(Call, C, 0, Call.getArgSVal(0), true, PthreadSemantics); 267 } 268 269 void PthreadLockChecker::TryXNULock(const CallEvent &Call, 270 CheckerContext &C) const { 271 AcquireLockAux(Call, C, 0, Call.getArgSVal(0), true, PthreadSemantics); 272 } 273 274 void PthreadLockChecker::AcquireLockAux(const CallEvent &Call, 275 CheckerContext &C, unsigned ArgNo, 276 SVal lock, bool isTryLock, 277 enum LockingSemantics semantics) const { 278 279 const MemRegion *lockR = lock.getAsRegion(); 280 if (!lockR) 281 return; 282 283 ProgramStateRef state = C.getState(); 284 const SymbolRef *sym = state->get<DestroyRetVal>(lockR); 285 if (sym) 286 state = resolvePossiblyDestroyedMutex(state, lockR, sym); 287 288 if (const LockState *LState = state->get<LockMap>(lockR)) { 289 if (LState->isLocked()) { 290 ExplodedNode *N = C.generateErrorNode(); 291 if (!N) 292 return; 293 auto report = std::make_unique<PathSensitiveBugReport>( 294 BT_doublelock, "This lock has already been acquired", N); 295 report->addRange(Call.getArgExpr(ArgNo)->getSourceRange()); 296 C.emitReport(std::move(report)); 297 return; 298 } else if (LState->isDestroyed()) { 299 reportUseDestroyedBug(Call, C, ArgNo); 300 return; 301 } 302 } 303 304 ProgramStateRef lockSucc = state; 305 if (isTryLock) { 306 // Bifurcate the state, and allow a mode where the lock acquisition fails. 307 SVal RetVal = Call.getReturnValue(); 308 if (auto DefinedRetVal = RetVal.getAs<DefinedSVal>()) { 309 ProgramStateRef lockFail; 310 switch (semantics) { 311 case PthreadSemantics: 312 std::tie(lockFail, lockSucc) = state->assume(*DefinedRetVal); 313 break; 314 case XNUSemantics: 315 std::tie(lockSucc, lockFail) = state->assume(*DefinedRetVal); 316 break; 317 default: 318 llvm_unreachable("Unknown tryLock locking semantics"); 319 } 320 assert(lockFail && lockSucc); 321 C.addTransition(lockFail); 322 } 323 // We might want to handle the case when the mutex lock function was inlined 324 // and returned an Unknown or Undefined value. 325 } else if (semantics == PthreadSemantics) { 326 // Assume that the return value was 0. 327 SVal RetVal = Call.getReturnValue(); 328 if (auto DefinedRetVal = RetVal.getAs<DefinedSVal>()) { 329 // FIXME: If the lock function was inlined and returned true, 330 // we need to behave sanely - at least generate sink. 331 lockSucc = state->assume(*DefinedRetVal, false); 332 assert(lockSucc); 333 } 334 // We might want to handle the case when the mutex lock function was inlined 335 // and returned an Unknown or Undefined value. 336 } else { 337 // XNU locking semantics return void on non-try locks 338 assert((semantics == XNUSemantics) && "Unknown locking semantics"); 339 lockSucc = state; 340 } 341 342 // Record that the lock was acquired. 343 lockSucc = lockSucc->add<LockSet>(lockR); 344 lockSucc = lockSucc->set<LockMap>(lockR, LockState::getLocked()); 345 C.addTransition(lockSucc); 346 } 347 348 void PthreadLockChecker::ReleaseAnyLock(const CallEvent &Call, 349 CheckerContext &C) const { 350 ReleaseLockAux(Call, C, 0, Call.getArgSVal(0)); 351 } 352 353 void PthreadLockChecker::ReleaseLockAux(const CallEvent &Call, 354 CheckerContext &C, unsigned ArgNo, 355 SVal lock) const { 356 357 const MemRegion *lockR = lock.getAsRegion(); 358 if (!lockR) 359 return; 360 361 ProgramStateRef state = C.getState(); 362 const SymbolRef *sym = state->get<DestroyRetVal>(lockR); 363 if (sym) 364 state = resolvePossiblyDestroyedMutex(state, lockR, sym); 365 366 if (const LockState *LState = state->get<LockMap>(lockR)) { 367 if (LState->isUnlocked()) { 368 ExplodedNode *N = C.generateErrorNode(); 369 if (!N) 370 return; 371 auto Report = std::make_unique<PathSensitiveBugReport>( 372 BT_doubleunlock, "This lock has already been unlocked", N); 373 Report->addRange(Call.getArgExpr(ArgNo)->getSourceRange()); 374 C.emitReport(std::move(Report)); 375 return; 376 } else if (LState->isDestroyed()) { 377 reportUseDestroyedBug(Call, C, ArgNo); 378 return; 379 } 380 } 381 382 LockSetTy LS = state->get<LockSet>(); 383 384 if (!LS.isEmpty()) { 385 const MemRegion *firstLockR = LS.getHead(); 386 if (firstLockR != lockR) { 387 ExplodedNode *N = C.generateErrorNode(); 388 if (!N) 389 return; 390 auto report = std::make_unique<PathSensitiveBugReport>( 391 BT_lor, "This was not the most recently acquired lock. Possible " 392 "lock order reversal", N); 393 report->addRange(Call.getArgExpr(ArgNo)->getSourceRange()); 394 C.emitReport(std::move(report)); 395 return; 396 } 397 // Record that the lock was released. 398 state = state->set<LockSet>(LS.getTail()); 399 } 400 401 state = state->set<LockMap>(lockR, LockState::getUnlocked()); 402 C.addTransition(state); 403 } 404 405 void PthreadLockChecker::DestroyPthreadLock(const CallEvent &Call, 406 CheckerContext &C) const { 407 DestroyLockAux(Call, C, 0, Call.getArgSVal(0), PthreadSemantics); 408 } 409 410 void PthreadLockChecker::DestroyXNULock(const CallEvent &Call, 411 CheckerContext &C) const { 412 DestroyLockAux(Call, C, 0, Call.getArgSVal(0), XNUSemantics); 413 } 414 415 void PthreadLockChecker::DestroyLockAux(const CallEvent &Call, 416 CheckerContext &C, unsigned ArgNo, 417 SVal Lock, 418 enum LockingSemantics semantics) const { 419 420 const MemRegion *LockR = Lock.getAsRegion(); 421 if (!LockR) 422 return; 423 424 ProgramStateRef State = C.getState(); 425 426 const SymbolRef *sym = State->get<DestroyRetVal>(LockR); 427 if (sym) 428 State = resolvePossiblyDestroyedMutex(State, LockR, sym); 429 430 const LockState *LState = State->get<LockMap>(LockR); 431 // Checking the return value of the destroy method only in the case of 432 // PthreadSemantics 433 if (semantics == PthreadSemantics) { 434 if (!LState || LState->isUnlocked()) { 435 SymbolRef sym = Call.getReturnValue().getAsSymbol(); 436 if (!sym) { 437 State = State->remove<LockMap>(LockR); 438 C.addTransition(State); 439 return; 440 } 441 State = State->set<DestroyRetVal>(LockR, sym); 442 if (LState && LState->isUnlocked()) 443 State = State->set<LockMap>( 444 LockR, LockState::getUnlockedAndPossiblyDestroyed()); 445 else 446 State = State->set<LockMap>( 447 LockR, LockState::getUntouchedAndPossiblyDestroyed()); 448 C.addTransition(State); 449 return; 450 } 451 } else { 452 if (!LState || LState->isUnlocked()) { 453 State = State->set<LockMap>(LockR, LockState::getDestroyed()); 454 C.addTransition(State); 455 return; 456 } 457 } 458 StringRef Message; 459 460 if (LState->isLocked()) { 461 Message = "This lock is still locked"; 462 } else { 463 Message = "This lock has already been destroyed"; 464 } 465 466 ExplodedNode *N = C.generateErrorNode(); 467 if (!N) 468 return; 469 auto Report = 470 std::make_unique<PathSensitiveBugReport>(BT_destroylock, Message, N); 471 Report->addRange(Call.getArgExpr(ArgNo)->getSourceRange()); 472 C.emitReport(std::move(Report)); 473 } 474 475 void PthreadLockChecker::InitAnyLock(const CallEvent &Call, 476 CheckerContext &C) const { 477 InitLockAux(Call, C, 0, Call.getArgSVal(0)); 478 } 479 480 void PthreadLockChecker::InitLockAux(const CallEvent &Call, CheckerContext &C, 481 unsigned ArgNo, SVal Lock) const { 482 483 const MemRegion *LockR = Lock.getAsRegion(); 484 if (!LockR) 485 return; 486 487 ProgramStateRef State = C.getState(); 488 489 const SymbolRef *sym = State->get<DestroyRetVal>(LockR); 490 if (sym) 491 State = resolvePossiblyDestroyedMutex(State, LockR, sym); 492 493 const struct LockState *LState = State->get<LockMap>(LockR); 494 if (!LState || LState->isDestroyed()) { 495 State = State->set<LockMap>(LockR, LockState::getUnlocked()); 496 C.addTransition(State); 497 return; 498 } 499 500 StringRef Message; 501 502 if (LState->isLocked()) { 503 Message = "This lock is still being held"; 504 } else { 505 Message = "This lock has already been initialized"; 506 } 507 508 ExplodedNode *N = C.generateErrorNode(); 509 if (!N) 510 return; 511 auto Report = 512 std::make_unique<PathSensitiveBugReport>(BT_initlock, Message, N); 513 Report->addRange(Call.getArgExpr(ArgNo)->getSourceRange()); 514 C.emitReport(std::move(Report)); 515 } 516 517 void PthreadLockChecker::reportUseDestroyedBug(const CallEvent &Call, 518 CheckerContext &C, 519 unsigned ArgNo) const { 520 ExplodedNode *N = C.generateErrorNode(); 521 if (!N) 522 return; 523 auto Report = std::make_unique<PathSensitiveBugReport>( 524 BT_destroylock, "This lock has already been destroyed", N); 525 Report->addRange(Call.getArgExpr(ArgNo)->getSourceRange()); 526 C.emitReport(std::move(Report)); 527 } 528 529 void PthreadLockChecker::checkDeadSymbols(SymbolReaper &SymReaper, 530 CheckerContext &C) const { 531 ProgramStateRef State = C.getState(); 532 533 // TODO: Clean LockMap when a mutex region dies. 534 535 DestroyRetValTy TrackedSymbols = State->get<DestroyRetVal>(); 536 for (DestroyRetValTy::iterator I = TrackedSymbols.begin(), 537 E = TrackedSymbols.end(); 538 I != E; ++I) { 539 const SymbolRef Sym = I->second; 540 const MemRegion *lockR = I->first; 541 bool IsSymDead = SymReaper.isDead(Sym); 542 // Remove the dead symbol from the return value symbols map. 543 if (IsSymDead) 544 State = resolvePossiblyDestroyedMutex(State, lockR, &Sym); 545 } 546 C.addTransition(State); 547 } 548 549 void ento::registerPthreadLockChecker(CheckerManager &mgr) { 550 mgr.registerChecker<PthreadLockChecker>(); 551 } 552 553 bool ento::shouldRegisterPthreadLockChecker(const LangOptions &LO) { 554 return true; 555 } 556