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