1226633Sdim//===--- PthreadLockChecker.cpp - Check for locking problems ---*- C++ -*--===// 2218887Sdim// 3218887Sdim// The LLVM Compiler Infrastructure 4218887Sdim// 5218887Sdim// This file is distributed under the University of Illinois Open Source 6218887Sdim// License. See LICENSE.TXT for details. 7218887Sdim// 8218887Sdim//===----------------------------------------------------------------------===// 9218887Sdim// 10226633Sdim// This defines PthreadLockChecker, a simple lock -> unlock checker. 11226633Sdim// Also handles XNU locks, which behave similarly enough to share code. 12218887Sdim// 13218887Sdim//===----------------------------------------------------------------------===// 14218887Sdim 15218887Sdim#include "ClangSACheckers.h" 16249423Sdim#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 17221345Sdim#include "clang/StaticAnalyzer/Core/Checker.h" 18218887Sdim#include "clang/StaticAnalyzer/Core/CheckerManager.h" 19219077Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 20226633Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 21226633Sdim#include "llvm/ADT/ImmutableList.h" 22218887Sdim 23218887Sdimusing namespace clang; 24218887Sdimusing namespace ento; 25218887Sdim 26218887Sdimnamespace { 27276479Sdim 28276479Sdimstruct LockState { 29276479Sdim enum Kind { Destroyed, Locked, Unlocked } K; 30276479Sdim 31276479Sdimprivate: 32276479Sdim LockState(Kind K) : K(K) {} 33276479Sdim 34276479Sdimpublic: 35296417Sdim static LockState getLocked() { return LockState(Locked); } 36296417Sdim static LockState getUnlocked() { return LockState(Unlocked); } 37296417Sdim static LockState getDestroyed() { return LockState(Destroyed); } 38276479Sdim 39276479Sdim bool operator==(const LockState &X) const { 40276479Sdim return K == X.K; 41276479Sdim } 42276479Sdim 43276479Sdim bool isLocked() const { return K == Locked; } 44276479Sdim bool isUnlocked() const { return K == Unlocked; } 45276479Sdim bool isDestroyed() const { return K == Destroyed; } 46276479Sdim 47276479Sdim void Profile(llvm::FoldingSetNodeID &ID) const { 48276479Sdim ID.AddInteger(K); 49276479Sdim } 50276479Sdim}; 51276479Sdim 52226633Sdimclass PthreadLockChecker : public Checker< check::PostStmt<CallExpr> > { 53276479Sdim mutable std::unique_ptr<BugType> BT_doublelock; 54276479Sdim mutable std::unique_ptr<BugType> BT_doubleunlock; 55276479Sdim mutable std::unique_ptr<BugType> BT_destroylock; 56276479Sdim mutable std::unique_ptr<BugType> BT_initlock; 57276479Sdim mutable std::unique_ptr<BugType> BT_lor; 58226633Sdim enum LockingSemantics { 59226633Sdim NotApplicable = 0, 60226633Sdim PthreadSemantics, 61226633Sdim XNUSemantics 62226633Sdim }; 63218887Sdimpublic: 64219077Sdim void checkPostStmt(const CallExpr *CE, CheckerContext &C) const; 65296417Sdim 66226633Sdim void AcquireLock(CheckerContext &C, const CallExpr *CE, SVal lock, 67226633Sdim bool isTryLock, enum LockingSemantics semantics) const; 68296417Sdim 69226633Sdim void ReleaseLock(CheckerContext &C, const CallExpr *CE, SVal lock) const; 70276479Sdim void DestroyLock(CheckerContext &C, const CallExpr *CE, SVal Lock) const; 71276479Sdim void InitLock(CheckerContext &C, const CallExpr *CE, SVal Lock) const; 72276479Sdim void reportUseDestroyedBug(CheckerContext &C, const CallExpr *CE) const; 73218887Sdim}; 74218887Sdim} // end anonymous namespace 75218887Sdim 76218887Sdim// GDM Entry for tracking lock state. 77243830SdimREGISTER_LIST_WITH_PROGRAMSTATE(LockSet, const MemRegion *) 78218887Sdim 79276479SdimREGISTER_MAP_WITH_PROGRAMSTATE(LockMap, const MemRegion *, LockState) 80218887Sdim 81219077Sdimvoid PthreadLockChecker::checkPostStmt(const CallExpr *CE, 82219077Sdim CheckerContext &C) const { 83234353Sdim ProgramStateRef state = C.getState(); 84234353Sdim const LocationContext *LCtx = C.getLocationContext(); 85234353Sdim StringRef FName = C.getCalleeName(CE); 86234353Sdim if (FName.empty()) 87218887Sdim return; 88226633Sdim 89276479Sdim if (CE->getNumArgs() != 1 && CE->getNumArgs() != 2) 90226633Sdim return; 91226633Sdim 92226633Sdim if (FName == "pthread_mutex_lock" || 93226633Sdim FName == "pthread_rwlock_rdlock" || 94226633Sdim FName == "pthread_rwlock_wrlock") 95234353Sdim AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), 96234353Sdim false, PthreadSemantics); 97226633Sdim else if (FName == "lck_mtx_lock" || 98226633Sdim FName == "lck_rw_lock_exclusive" || 99296417Sdim FName == "lck_rw_lock_shared") 100234353Sdim AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), 101234353Sdim false, XNUSemantics); 102226633Sdim else if (FName == "pthread_mutex_trylock" || 103226633Sdim FName == "pthread_rwlock_tryrdlock" || 104276479Sdim FName == "pthread_rwlock_trywrlock") 105234353Sdim AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), 106234353Sdim true, PthreadSemantics); 107226633Sdim else if (FName == "lck_mtx_try_lock" || 108226633Sdim FName == "lck_rw_try_lock_exclusive" || 109226633Sdim FName == "lck_rw_try_lock_shared") 110234353Sdim AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), 111234353Sdim true, XNUSemantics); 112226633Sdim else if (FName == "pthread_mutex_unlock" || 113226633Sdim FName == "pthread_rwlock_unlock" || 114226633Sdim FName == "lck_mtx_unlock" || 115226633Sdim FName == "lck_rw_done") 116234353Sdim ReleaseLock(C, CE, state->getSVal(CE->getArg(0), LCtx)); 117276479Sdim else if (FName == "pthread_mutex_destroy" || 118276479Sdim FName == "lck_mtx_destroy") 119276479Sdim DestroyLock(C, CE, state->getSVal(CE->getArg(0), LCtx)); 120276479Sdim else if (FName == "pthread_mutex_init") 121276479Sdim InitLock(C, CE, state->getSVal(CE->getArg(0), LCtx)); 122218887Sdim} 123218887Sdim 124218887Sdimvoid PthreadLockChecker::AcquireLock(CheckerContext &C, const CallExpr *CE, 125226633Sdim SVal lock, bool isTryLock, 126226633Sdim enum LockingSemantics semantics) const { 127296417Sdim 128218887Sdim const MemRegion *lockR = lock.getAsRegion(); 129218887Sdim if (!lockR) 130218887Sdim return; 131296417Sdim 132234353Sdim ProgramStateRef state = C.getState(); 133296417Sdim 134234353Sdim SVal X = state->getSVal(CE, C.getLocationContext()); 135218887Sdim if (X.isUnknownOrUndef()) 136218887Sdim return; 137296417Sdim 138249423Sdim DefinedSVal retVal = X.castAs<DefinedSVal>(); 139226633Sdim 140276479Sdim if (const LockState *LState = state->get<LockMap>(lockR)) { 141276479Sdim if (LState->isLocked()) { 142276479Sdim if (!BT_doublelock) 143276479Sdim BT_doublelock.reset(new BugType(this, "Double locking", 144276479Sdim "Lock checker")); 145296417Sdim ExplodedNode *N = C.generateErrorNode(); 146276479Sdim if (!N) 147276479Sdim return; 148288943Sdim auto report = llvm::make_unique<BugReport>( 149288943Sdim *BT_doublelock, "This lock has already been acquired", N); 150276479Sdim report->addRange(CE->getArg(0)->getSourceRange()); 151288943Sdim C.emitReport(std::move(report)); 152226633Sdim return; 153276479Sdim } else if (LState->isDestroyed()) { 154276479Sdim reportUseDestroyedBug(C, CE); 155276479Sdim return; 156276479Sdim } 157226633Sdim } 158226633Sdim 159234353Sdim ProgramStateRef lockSucc = state; 160218887Sdim if (isTryLock) { 161226633Sdim // Bifurcate the state, and allow a mode where the lock acquisition fails. 162234353Sdim ProgramStateRef lockFail; 163226633Sdim switch (semantics) { 164226633Sdim case PthreadSemantics: 165276479Sdim std::tie(lockFail, lockSucc) = state->assume(retVal); 166226633Sdim break; 167226633Sdim case XNUSemantics: 168276479Sdim std::tie(lockSucc, lockFail) = state->assume(retVal); 169226633Sdim break; 170226633Sdim default: 171226633Sdim llvm_unreachable("Unknown tryLock locking semantics"); 172226633Sdim } 173218887Sdim assert(lockFail && lockSucc); 174226633Sdim C.addTransition(lockFail); 175226633Sdim 176226633Sdim } else if (semantics == PthreadSemantics) { 177226633Sdim // Assume that the return value was 0. 178218887Sdim lockSucc = state->assume(retVal, false); 179218887Sdim assert(lockSucc); 180226633Sdim 181226633Sdim } else { 182226633Sdim // XNU locking semantics return void on non-try locks 183226633Sdim assert((semantics == XNUSemantics) && "Unknown locking semantics"); 184226633Sdim lockSucc = state; 185218887Sdim } 186296417Sdim 187296417Sdim // Record that the lock was acquired. 188218887Sdim lockSucc = lockSucc->add<LockSet>(lockR); 189276479Sdim lockSucc = lockSucc->set<LockMap>(lockR, LockState::getLocked()); 190226633Sdim C.addTransition(lockSucc); 191218887Sdim} 192218887Sdim 193218887Sdimvoid PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE, 194219077Sdim SVal lock) const { 195218887Sdim 196218887Sdim const MemRegion *lockR = lock.getAsRegion(); 197218887Sdim if (!lockR) 198218887Sdim return; 199296417Sdim 200234353Sdim ProgramStateRef state = C.getState(); 201276479Sdim 202276479Sdim if (const LockState *LState = state->get<LockMap>(lockR)) { 203276479Sdim if (LState->isUnlocked()) { 204276479Sdim if (!BT_doubleunlock) 205276479Sdim BT_doubleunlock.reset(new BugType(this, "Double unlocking", 206276479Sdim "Lock checker")); 207296417Sdim ExplodedNode *N = C.generateErrorNode(); 208276479Sdim if (!N) 209276479Sdim return; 210288943Sdim auto Report = llvm::make_unique<BugReport>( 211288943Sdim *BT_doubleunlock, "This lock has already been unlocked", N); 212276479Sdim Report->addRange(CE->getArg(0)->getSourceRange()); 213288943Sdim C.emitReport(std::move(Report)); 214276479Sdim return; 215276479Sdim } else if (LState->isDestroyed()) { 216276479Sdim reportUseDestroyedBug(C, CE); 217276479Sdim return; 218276479Sdim } 219276479Sdim } 220276479Sdim 221243830Sdim LockSetTy LS = state->get<LockSet>(); 222218887Sdim 223226633Sdim // FIXME: Better analysis requires IPA for wrappers. 224276479Sdim 225276479Sdim if (!LS.isEmpty()) { 226276479Sdim const MemRegion *firstLockR = LS.getHead(); 227276479Sdim if (firstLockR != lockR) { 228276479Sdim if (!BT_lor) 229276479Sdim BT_lor.reset(new BugType(this, "Lock order reversal", "Lock checker")); 230296417Sdim ExplodedNode *N = C.generateErrorNode(); 231276479Sdim if (!N) 232276479Sdim return; 233288943Sdim auto report = llvm::make_unique<BugReport>( 234288943Sdim *BT_lor, "This was not the most recently acquired lock. Possible " 235288943Sdim "lock order reversal", N); 236276479Sdim report->addRange(CE->getArg(0)->getSourceRange()); 237288943Sdim C.emitReport(std::move(report)); 238226633Sdim return; 239276479Sdim } 240276479Sdim // Record that the lock was released. 241276479Sdim state = state->set<LockSet>(LS.getTail()); 242226633Sdim } 243226633Sdim 244276479Sdim state = state->set<LockMap>(lockR, LockState::getUnlocked()); 245226633Sdim C.addTransition(state); 246218887Sdim} 247219077Sdim 248276479Sdimvoid PthreadLockChecker::DestroyLock(CheckerContext &C, const CallExpr *CE, 249276479Sdim SVal Lock) const { 250226633Sdim 251276479Sdim const MemRegion *LockR = Lock.getAsRegion(); 252276479Sdim if (!LockR) 253276479Sdim return; 254276479Sdim 255276479Sdim ProgramStateRef State = C.getState(); 256276479Sdim 257276479Sdim const LockState *LState = State->get<LockMap>(LockR); 258276479Sdim if (!LState || LState->isUnlocked()) { 259276479Sdim State = State->set<LockMap>(LockR, LockState::getDestroyed()); 260276479Sdim C.addTransition(State); 261276479Sdim return; 262276479Sdim } 263276479Sdim 264276479Sdim StringRef Message; 265276479Sdim 266276479Sdim if (LState->isLocked()) { 267276479Sdim Message = "This lock is still locked"; 268276479Sdim } else { 269276479Sdim Message = "This lock has already been destroyed"; 270276479Sdim } 271276479Sdim 272276479Sdim if (!BT_destroylock) 273276479Sdim BT_destroylock.reset(new BugType(this, "Destroy invalid lock", 274276479Sdim "Lock checker")); 275296417Sdim ExplodedNode *N = C.generateErrorNode(); 276276479Sdim if (!N) 277276479Sdim return; 278288943Sdim auto Report = llvm::make_unique<BugReport>(*BT_destroylock, Message, N); 279276479Sdim Report->addRange(CE->getArg(0)->getSourceRange()); 280288943Sdim C.emitReport(std::move(Report)); 281276479Sdim} 282276479Sdim 283276479Sdimvoid PthreadLockChecker::InitLock(CheckerContext &C, const CallExpr *CE, 284276479Sdim SVal Lock) const { 285276479Sdim 286276479Sdim const MemRegion *LockR = Lock.getAsRegion(); 287276479Sdim if (!LockR) 288276479Sdim return; 289276479Sdim 290276479Sdim ProgramStateRef State = C.getState(); 291276479Sdim 292276479Sdim const struct LockState *LState = State->get<LockMap>(LockR); 293276479Sdim if (!LState || LState->isDestroyed()) { 294276479Sdim State = State->set<LockMap>(LockR, LockState::getUnlocked()); 295276479Sdim C.addTransition(State); 296276479Sdim return; 297276479Sdim } 298276479Sdim 299276479Sdim StringRef Message; 300276479Sdim 301276479Sdim if (LState->isLocked()) { 302276479Sdim Message = "This lock is still being held"; 303276479Sdim } else { 304276479Sdim Message = "This lock has already been initialized"; 305276479Sdim } 306276479Sdim 307276479Sdim if (!BT_initlock) 308276479Sdim BT_initlock.reset(new BugType(this, "Init invalid lock", 309276479Sdim "Lock checker")); 310296417Sdim ExplodedNode *N = C.generateErrorNode(); 311276479Sdim if (!N) 312276479Sdim return; 313288943Sdim auto Report = llvm::make_unique<BugReport>(*BT_initlock, Message, N); 314276479Sdim Report->addRange(CE->getArg(0)->getSourceRange()); 315288943Sdim C.emitReport(std::move(Report)); 316276479Sdim} 317276479Sdim 318276479Sdimvoid PthreadLockChecker::reportUseDestroyedBug(CheckerContext &C, 319276479Sdim const CallExpr *CE) const { 320276479Sdim if (!BT_destroylock) 321276479Sdim BT_destroylock.reset(new BugType(this, "Use destroyed lock", 322276479Sdim "Lock checker")); 323296417Sdim ExplodedNode *N = C.generateErrorNode(); 324276479Sdim if (!N) 325276479Sdim return; 326288943Sdim auto Report = llvm::make_unique<BugReport>( 327288943Sdim *BT_destroylock, "This lock has already been destroyed", N); 328276479Sdim Report->addRange(CE->getArg(0)->getSourceRange()); 329288943Sdim C.emitReport(std::move(Report)); 330276479Sdim} 331276479Sdim 332219077Sdimvoid ento::registerPthreadLockChecker(CheckerManager &mgr) { 333219077Sdim mgr.registerChecker<PthreadLockChecker>(); 334219077Sdim} 335