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/ProgramStateTrait.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::PostStmt<CallExpr>, check::DeadSymbols> { 70 mutable std::unique_ptr<BugType> BT_doublelock; 71 mutable std::unique_ptr<BugType> BT_doubleunlock; 72 mutable std::unique_ptr<BugType> BT_destroylock; 73 mutable std::unique_ptr<BugType> BT_initlock; 74 mutable std::unique_ptr<BugType> BT_lor; 75 enum LockingSemantics { 76 NotApplicable = 0, 77 PthreadSemantics, 78 XNUSemantics 79 }; 80 public: 81 void checkPostStmt(const CallExpr *CE, CheckerContext &C) const; 82 void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const; 83 void printState(raw_ostream &Out, ProgramStateRef State, 84 const char *NL, const char *Sep) const override; 85 86 void AcquireLock(CheckerContext &C, const CallExpr *CE, SVal lock, 87 bool isTryLock, enum LockingSemantics semantics) const; 88 89 void ReleaseLock(CheckerContext &C, const CallExpr *CE, SVal lock) const; 90 void DestroyLock(CheckerContext &C, const CallExpr *CE, SVal Lock, 91 enum LockingSemantics semantics) const; 92 void InitLock(CheckerContext &C, const CallExpr *CE, SVal Lock) const; 93 void reportUseDestroyedBug(CheckerContext &C, const CallExpr *CE) const; 94 ProgramStateRef resolvePossiblyDestroyedMutex(ProgramStateRef state, 95 const MemRegion *lockR, 96 const SymbolRef *sym) const; 97 }; 98 } // end anonymous namespace 99 100 // A stack of locks for tracking lock-unlock order. 101 REGISTER_LIST_WITH_PROGRAMSTATE(LockSet, const MemRegion *) 102 103 // An entry for tracking lock states. 104 REGISTER_MAP_WITH_PROGRAMSTATE(LockMap, const MemRegion *, LockState) 105 106 // Return values for unresolved calls to pthread_mutex_destroy(). 107 REGISTER_MAP_WITH_PROGRAMSTATE(DestroyRetVal, const MemRegion *, SymbolRef) 108 109 void PthreadLockChecker::checkPostStmt(const CallExpr *CE, 110 CheckerContext &C) const { 111 StringRef FName = C.getCalleeName(CE); 112 if (FName.empty()) 113 return; 114 115 if (CE->getNumArgs() != 1 && CE->getNumArgs() != 2) 116 return; 117 118 if (FName == "pthread_mutex_lock" || 119 FName == "pthread_rwlock_rdlock" || 120 FName == "pthread_rwlock_wrlock") 121 AcquireLock(C, CE, C.getSVal(CE->getArg(0)), false, PthreadSemantics); 122 else if (FName == "lck_mtx_lock" || 123 FName == "lck_rw_lock_exclusive" || 124 FName == "lck_rw_lock_shared") 125 AcquireLock(C, CE, C.getSVal(CE->getArg(0)), false, XNUSemantics); 126 else if (FName == "pthread_mutex_trylock" || 127 FName == "pthread_rwlock_tryrdlock" || 128 FName == "pthread_rwlock_trywrlock") 129 AcquireLock(C, CE, C.getSVal(CE->getArg(0)), 130 true, PthreadSemantics); 131 else if (FName == "lck_mtx_try_lock" || 132 FName == "lck_rw_try_lock_exclusive" || 133 FName == "lck_rw_try_lock_shared") 134 AcquireLock(C, CE, C.getSVal(CE->getArg(0)), true, XNUSemantics); 135 else if (FName == "pthread_mutex_unlock" || 136 FName == "pthread_rwlock_unlock" || 137 FName == "lck_mtx_unlock" || 138 FName == "lck_rw_done") 139 ReleaseLock(C, CE, C.getSVal(CE->getArg(0))); 140 else if (FName == "pthread_mutex_destroy") 141 DestroyLock(C, CE, C.getSVal(CE->getArg(0)), PthreadSemantics); 142 else if (FName == "lck_mtx_destroy") 143 DestroyLock(C, CE, C.getSVal(CE->getArg(0)), XNUSemantics); 144 else if (FName == "pthread_mutex_init") 145 InitLock(C, CE, C.getSVal(CE->getArg(0))); 146 } 147 148 // When a lock is destroyed, in some semantics(like PthreadSemantics) we are not 149 // sure if the destroy call has succeeded or failed, and the lock enters one of 150 // the 'possibly destroyed' state. There is a short time frame for the 151 // programmer to check the return value to see if the lock was successfully 152 // destroyed. Before we model the next operation over that lock, we call this 153 // function to see if the return value was checked by now and set the lock state 154 // - either to destroyed state or back to its previous state. 155 156 // In PthreadSemantics, pthread_mutex_destroy() returns zero if the lock is 157 // successfully destroyed and it returns a non-zero value otherwise. 158 ProgramStateRef PthreadLockChecker::resolvePossiblyDestroyedMutex( 159 ProgramStateRef state, const MemRegion *lockR, const SymbolRef *sym) const { 160 const LockState *lstate = state->get<LockMap>(lockR); 161 // Existence in DestroyRetVal ensures existence in LockMap. 162 // Existence in Destroyed also ensures that the lock state for lockR is either 163 // UntouchedAndPossiblyDestroyed or UnlockedAndPossiblyDestroyed. 164 assert(lstate->isUntouchedAndPossiblyDestroyed() || 165 lstate->isUnlockedAndPossiblyDestroyed()); 166 167 ConstraintManager &CMgr = state->getConstraintManager(); 168 ConditionTruthVal retZero = CMgr.isNull(state, *sym); 169 if (retZero.isConstrainedFalse()) { 170 if (lstate->isUntouchedAndPossiblyDestroyed()) 171 state = state->remove<LockMap>(lockR); 172 else if (lstate->isUnlockedAndPossiblyDestroyed()) 173 state = state->set<LockMap>(lockR, LockState::getUnlocked()); 174 } else 175 state = state->set<LockMap>(lockR, LockState::getDestroyed()); 176 177 // Removing the map entry (lockR, sym) from DestroyRetVal as the lock state is 178 // now resolved. 179 state = state->remove<DestroyRetVal>(lockR); 180 return state; 181 } 182 183 void PthreadLockChecker::printState(raw_ostream &Out, ProgramStateRef State, 184 const char *NL, const char *Sep) const { 185 LockMapTy LM = State->get<LockMap>(); 186 if (!LM.isEmpty()) { 187 Out << Sep << "Mutex states:" << NL; 188 for (auto I : LM) { 189 I.first->dumpToStream(Out); 190 if (I.second.isLocked()) 191 Out << ": locked"; 192 else if (I.second.isUnlocked()) 193 Out << ": unlocked"; 194 else if (I.second.isDestroyed()) 195 Out << ": destroyed"; 196 else if (I.second.isUntouchedAndPossiblyDestroyed()) 197 Out << ": not tracked, possibly destroyed"; 198 else if (I.second.isUnlockedAndPossiblyDestroyed()) 199 Out << ": unlocked, possibly destroyed"; 200 Out << NL; 201 } 202 } 203 204 LockSetTy LS = State->get<LockSet>(); 205 if (!LS.isEmpty()) { 206 Out << Sep << "Mutex lock order:" << NL; 207 for (auto I: LS) { 208 I->dumpToStream(Out); 209 Out << NL; 210 } 211 } 212 213 // TODO: Dump destroyed mutex symbols? 214 } 215 216 void PthreadLockChecker::AcquireLock(CheckerContext &C, const CallExpr *CE, 217 SVal lock, bool isTryLock, 218 enum LockingSemantics semantics) const { 219 220 const MemRegion *lockR = lock.getAsRegion(); 221 if (!lockR) 222 return; 223 224 ProgramStateRef state = C.getState(); 225 const SymbolRef *sym = state->get<DestroyRetVal>(lockR); 226 if (sym) 227 state = resolvePossiblyDestroyedMutex(state, lockR, sym); 228 229 if (const LockState *LState = state->get<LockMap>(lockR)) { 230 if (LState->isLocked()) { 231 if (!BT_doublelock) 232 BT_doublelock.reset(new BugType(this, "Double locking", 233 "Lock checker")); 234 ExplodedNode *N = C.generateErrorNode(); 235 if (!N) 236 return; 237 auto report = std::make_unique<PathSensitiveBugReport>( 238 *BT_doublelock, "This lock has already been acquired", N); 239 report->addRange(CE->getArg(0)->getSourceRange()); 240 C.emitReport(std::move(report)); 241 return; 242 } else if (LState->isDestroyed()) { 243 reportUseDestroyedBug(C, CE); 244 return; 245 } 246 } 247 248 ProgramStateRef lockSucc = state; 249 if (isTryLock) { 250 // Bifurcate the state, and allow a mode where the lock acquisition fails. 251 SVal RetVal = state->getSVal(CE, C.getLocationContext()); 252 if (auto DefinedRetVal = RetVal.getAs<DefinedSVal>()) { 253 ProgramStateRef lockFail; 254 switch (semantics) { 255 case PthreadSemantics: 256 std::tie(lockFail, lockSucc) = state->assume(*DefinedRetVal); 257 break; 258 case XNUSemantics: 259 std::tie(lockSucc, lockFail) = state->assume(*DefinedRetVal); 260 break; 261 default: 262 llvm_unreachable("Unknown tryLock locking semantics"); 263 } 264 assert(lockFail && lockSucc); 265 C.addTransition(lockFail); 266 } 267 // We might want to handle the case when the mutex lock function was inlined 268 // and returned an Unknown or Undefined value. 269 } else if (semantics == PthreadSemantics) { 270 // Assume that the return value was 0. 271 SVal RetVal = state->getSVal(CE, C.getLocationContext()); 272 if (auto DefinedRetVal = RetVal.getAs<DefinedSVal>()) { 273 // FIXME: If the lock function was inlined and returned true, 274 // we need to behave sanely - at least generate sink. 275 lockSucc = state->assume(*DefinedRetVal, false); 276 assert(lockSucc); 277 } 278 // We might want to handle the case when the mutex lock function was inlined 279 // and returned an Unknown or Undefined value. 280 } else { 281 // XNU locking semantics return void on non-try locks 282 assert((semantics == XNUSemantics) && "Unknown locking semantics"); 283 lockSucc = state; 284 } 285 286 // Record that the lock was acquired. 287 lockSucc = lockSucc->add<LockSet>(lockR); 288 lockSucc = lockSucc->set<LockMap>(lockR, LockState::getLocked()); 289 C.addTransition(lockSucc); 290 } 291 292 void PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE, 293 SVal lock) const { 294 295 const MemRegion *lockR = lock.getAsRegion(); 296 if (!lockR) 297 return; 298 299 ProgramStateRef state = C.getState(); 300 const SymbolRef *sym = state->get<DestroyRetVal>(lockR); 301 if (sym) 302 state = resolvePossiblyDestroyedMutex(state, lockR, sym); 303 304 if (const LockState *LState = state->get<LockMap>(lockR)) { 305 if (LState->isUnlocked()) { 306 if (!BT_doubleunlock) 307 BT_doubleunlock.reset(new BugType(this, "Double unlocking", 308 "Lock checker")); 309 ExplodedNode *N = C.generateErrorNode(); 310 if (!N) 311 return; 312 auto Report = std::make_unique<PathSensitiveBugReport>( 313 *BT_doubleunlock, "This lock has already been unlocked", N); 314 Report->addRange(CE->getArg(0)->getSourceRange()); 315 C.emitReport(std::move(Report)); 316 return; 317 } else if (LState->isDestroyed()) { 318 reportUseDestroyedBug(C, CE); 319 return; 320 } 321 } 322 323 LockSetTy LS = state->get<LockSet>(); 324 325 // FIXME: Better analysis requires IPA for wrappers. 326 327 if (!LS.isEmpty()) { 328 const MemRegion *firstLockR = LS.getHead(); 329 if (firstLockR != lockR) { 330 if (!BT_lor) 331 BT_lor.reset(new BugType(this, "Lock order reversal", "Lock checker")); 332 ExplodedNode *N = C.generateErrorNode(); 333 if (!N) 334 return; 335 auto report = std::make_unique<PathSensitiveBugReport>( 336 *BT_lor, "This was not the most recently acquired lock. Possible " 337 "lock order reversal", N); 338 report->addRange(CE->getArg(0)->getSourceRange()); 339 C.emitReport(std::move(report)); 340 return; 341 } 342 // Record that the lock was released. 343 state = state->set<LockSet>(LS.getTail()); 344 } 345 346 state = state->set<LockMap>(lockR, LockState::getUnlocked()); 347 C.addTransition(state); 348 } 349 350 void PthreadLockChecker::DestroyLock(CheckerContext &C, const CallExpr *CE, 351 SVal Lock, 352 enum LockingSemantics semantics) const { 353 354 const MemRegion *LockR = Lock.getAsRegion(); 355 if (!LockR) 356 return; 357 358 ProgramStateRef State = C.getState(); 359 360 const SymbolRef *sym = State->get<DestroyRetVal>(LockR); 361 if (sym) 362 State = resolvePossiblyDestroyedMutex(State, LockR, sym); 363 364 const LockState *LState = State->get<LockMap>(LockR); 365 // Checking the return value of the destroy method only in the case of 366 // PthreadSemantics 367 if (semantics == PthreadSemantics) { 368 if (!LState || LState->isUnlocked()) { 369 SymbolRef sym = C.getSVal(CE).getAsSymbol(); 370 if (!sym) { 371 State = State->remove<LockMap>(LockR); 372 C.addTransition(State); 373 return; 374 } 375 State = State->set<DestroyRetVal>(LockR, sym); 376 if (LState && LState->isUnlocked()) 377 State = State->set<LockMap>( 378 LockR, LockState::getUnlockedAndPossiblyDestroyed()); 379 else 380 State = State->set<LockMap>( 381 LockR, LockState::getUntouchedAndPossiblyDestroyed()); 382 C.addTransition(State); 383 return; 384 } 385 } else { 386 if (!LState || LState->isUnlocked()) { 387 State = State->set<LockMap>(LockR, LockState::getDestroyed()); 388 C.addTransition(State); 389 return; 390 } 391 } 392 StringRef Message; 393 394 if (LState->isLocked()) { 395 Message = "This lock is still locked"; 396 } else { 397 Message = "This lock has already been destroyed"; 398 } 399 400 if (!BT_destroylock) 401 BT_destroylock.reset(new BugType(this, "Destroy invalid lock", 402 "Lock checker")); 403 ExplodedNode *N = C.generateErrorNode(); 404 if (!N) 405 return; 406 auto Report = 407 std::make_unique<PathSensitiveBugReport>(*BT_destroylock, Message, N); 408 Report->addRange(CE->getArg(0)->getSourceRange()); 409 C.emitReport(std::move(Report)); 410 } 411 412 void PthreadLockChecker::InitLock(CheckerContext &C, const CallExpr *CE, 413 SVal Lock) const { 414 415 const MemRegion *LockR = Lock.getAsRegion(); 416 if (!LockR) 417 return; 418 419 ProgramStateRef State = C.getState(); 420 421 const SymbolRef *sym = State->get<DestroyRetVal>(LockR); 422 if (sym) 423 State = resolvePossiblyDestroyedMutex(State, LockR, sym); 424 425 const struct LockState *LState = State->get<LockMap>(LockR); 426 if (!LState || LState->isDestroyed()) { 427 State = State->set<LockMap>(LockR, LockState::getUnlocked()); 428 C.addTransition(State); 429 return; 430 } 431 432 StringRef Message; 433 434 if (LState->isLocked()) { 435 Message = "This lock is still being held"; 436 } else { 437 Message = "This lock has already been initialized"; 438 } 439 440 if (!BT_initlock) 441 BT_initlock.reset(new BugType(this, "Init invalid lock", 442 "Lock checker")); 443 ExplodedNode *N = C.generateErrorNode(); 444 if (!N) 445 return; 446 auto Report = 447 std::make_unique<PathSensitiveBugReport>(*BT_initlock, Message, N); 448 Report->addRange(CE->getArg(0)->getSourceRange()); 449 C.emitReport(std::move(Report)); 450 } 451 452 void PthreadLockChecker::reportUseDestroyedBug(CheckerContext &C, 453 const CallExpr *CE) const { 454 if (!BT_destroylock) 455 BT_destroylock.reset(new BugType(this, "Use destroyed lock", 456 "Lock checker")); 457 ExplodedNode *N = C.generateErrorNode(); 458 if (!N) 459 return; 460 auto Report = std::make_unique<PathSensitiveBugReport>( 461 *BT_destroylock, "This lock has already been destroyed", N); 462 Report->addRange(CE->getArg(0)->getSourceRange()); 463 C.emitReport(std::move(Report)); 464 } 465 466 void PthreadLockChecker::checkDeadSymbols(SymbolReaper &SymReaper, 467 CheckerContext &C) const { 468 ProgramStateRef State = C.getState(); 469 470 // TODO: Clean LockMap when a mutex region dies. 471 472 DestroyRetValTy TrackedSymbols = State->get<DestroyRetVal>(); 473 for (DestroyRetValTy::iterator I = TrackedSymbols.begin(), 474 E = TrackedSymbols.end(); 475 I != E; ++I) { 476 const SymbolRef Sym = I->second; 477 const MemRegion *lockR = I->first; 478 bool IsSymDead = SymReaper.isDead(Sym); 479 // Remove the dead symbol from the return value symbols map. 480 if (IsSymDead) 481 State = resolvePossiblyDestroyedMutex(State, lockR, &Sym); 482 } 483 C.addTransition(State); 484 } 485 486 void ento::registerPthreadLockChecker(CheckerManager &mgr) { 487 mgr.registerChecker<PthreadLockChecker>(); 488 } 489 490 bool ento::shouldRegisterPthreadLockChecker(const LangOptions &LO) { 491 return true; 492 } 493