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 { Destroyed, Locked, Unlocked } K; 29 30 private: 31 LockState(Kind K) : K(K) {} 32 33 public: 34 static LockState getLocked() { return LockState(Locked); } 35 static LockState getUnlocked() { return LockState(Unlocked); } 36 static LockState getDestroyed() { return LockState(Destroyed); } 37 38 bool operator==(const LockState &X) const { 39 return K == X.K; 40 } 41 42 bool isLocked() const { return K == Locked; } 43 bool isUnlocked() const { return K == Unlocked; } 44 bool isDestroyed() const { return K == Destroyed; } 45 46 void Profile(llvm::FoldingSetNodeID &ID) const { 47 ID.AddInteger(K); 48 } 49 }; 50 51 class PthreadLockChecker : public Checker< check::PostStmt<CallExpr> > { 52 mutable std::unique_ptr<BugType> BT_doublelock; 53 mutable std::unique_ptr<BugType> BT_doubleunlock; 54 mutable std::unique_ptr<BugType> BT_destroylock; 55 mutable std::unique_ptr<BugType> BT_initlock; 56 mutable std::unique_ptr<BugType> BT_lor; 57 enum LockingSemantics { 58 NotApplicable = 0, 59 PthreadSemantics, 60 XNUSemantics 61 }; 62 public: 63 void checkPostStmt(const CallExpr *CE, CheckerContext &C) const; 64 65 void AcquireLock(CheckerContext &C, const CallExpr *CE, SVal lock, 66 bool isTryLock, enum LockingSemantics semantics) const; 67 68 void ReleaseLock(CheckerContext &C, const CallExpr *CE, SVal lock) const; 69 void DestroyLock(CheckerContext &C, const CallExpr *CE, SVal Lock) const; 70 void InitLock(CheckerContext &C, const CallExpr *CE, SVal Lock) const; 71 void reportUseDestroyedBug(CheckerContext &C, const CallExpr *CE) const; 72 }; 73 } // end anonymous namespace 74 75 // GDM Entry for tracking lock state. 76 REGISTER_LIST_WITH_PROGRAMSTATE(LockSet, const MemRegion *) 77 78 REGISTER_MAP_WITH_PROGRAMSTATE(LockMap, const MemRegion *, LockState) 79 80 void PthreadLockChecker::checkPostStmt(const CallExpr *CE, 81 CheckerContext &C) const { 82 ProgramStateRef state = C.getState(); 83 const LocationContext *LCtx = C.getLocationContext(); 84 StringRef FName = C.getCalleeName(CE); 85 if (FName.empty()) 86 return; 87 88 if (CE->getNumArgs() != 1 && CE->getNumArgs() != 2) 89 return; 90 91 if (FName == "pthread_mutex_lock" || 92 FName == "pthread_rwlock_rdlock" || 93 FName == "pthread_rwlock_wrlock") 94 AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), 95 false, PthreadSemantics); 96 else if (FName == "lck_mtx_lock" || 97 FName == "lck_rw_lock_exclusive" || 98 FName == "lck_rw_lock_shared") 99 AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), 100 false, XNUSemantics); 101 else if (FName == "pthread_mutex_trylock" || 102 FName == "pthread_rwlock_tryrdlock" || 103 FName == "pthread_rwlock_trywrlock") 104 AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), 105 true, PthreadSemantics); 106 else if (FName == "lck_mtx_try_lock" || 107 FName == "lck_rw_try_lock_exclusive" || 108 FName == "lck_rw_try_lock_shared") 109 AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx), 110 true, XNUSemantics); 111 else if (FName == "pthread_mutex_unlock" || 112 FName == "pthread_rwlock_unlock" || 113 FName == "lck_mtx_unlock" || 114 FName == "lck_rw_done") 115 ReleaseLock(C, CE, state->getSVal(CE->getArg(0), LCtx)); 116 else if (FName == "pthread_mutex_destroy" || 117 FName == "lck_mtx_destroy") 118 DestroyLock(C, CE, state->getSVal(CE->getArg(0), LCtx)); 119 else if (FName == "pthread_mutex_init") 120 InitLock(C, CE, state->getSVal(CE->getArg(0), LCtx)); 121 } 122 123 void PthreadLockChecker::AcquireLock(CheckerContext &C, const CallExpr *CE, 124 SVal lock, bool isTryLock, 125 enum LockingSemantics semantics) const { 126 127 const MemRegion *lockR = lock.getAsRegion(); 128 if (!lockR) 129 return; 130 131 ProgramStateRef state = C.getState(); 132 133 SVal X = state->getSVal(CE, C.getLocationContext()); 134 if (X.isUnknownOrUndef()) 135 return; 136 137 DefinedSVal retVal = X.castAs<DefinedSVal>(); 138 139 if (const LockState *LState = state->get<LockMap>(lockR)) { 140 if (LState->isLocked()) { 141 if (!BT_doublelock) 142 BT_doublelock.reset(new BugType(this, "Double locking", 143 "Lock checker")); 144 ExplodedNode *N = C.generateErrorNode(); 145 if (!N) 146 return; 147 auto report = llvm::make_unique<BugReport>( 148 *BT_doublelock, "This lock has already been acquired", N); 149 report->addRange(CE->getArg(0)->getSourceRange()); 150 C.emitReport(std::move(report)); 151 return; 152 } else if (LState->isDestroyed()) { 153 reportUseDestroyedBug(C, CE); 154 return; 155 } 156 } 157 158 ProgramStateRef lockSucc = state; 159 if (isTryLock) { 160 // Bifurcate the state, and allow a mode where the lock acquisition fails. 161 ProgramStateRef lockFail; 162 switch (semantics) { 163 case PthreadSemantics: 164 std::tie(lockFail, lockSucc) = state->assume(retVal); 165 break; 166 case XNUSemantics: 167 std::tie(lockSucc, lockFail) = state->assume(retVal); 168 break; 169 default: 170 llvm_unreachable("Unknown tryLock locking semantics"); 171 } 172 assert(lockFail && lockSucc); 173 C.addTransition(lockFail); 174 175 } else if (semantics == PthreadSemantics) { 176 // Assume that the return value was 0. 177 lockSucc = state->assume(retVal, false); 178 assert(lockSucc); 179 180 } else { 181 // XNU locking semantics return void on non-try locks 182 assert((semantics == XNUSemantics) && "Unknown locking semantics"); 183 lockSucc = state; 184 } 185 186 // Record that the lock was acquired. 187 lockSucc = lockSucc->add<LockSet>(lockR); 188 lockSucc = lockSucc->set<LockMap>(lockR, LockState::getLocked()); 189 C.addTransition(lockSucc); 190 } 191 192 void PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE, 193 SVal lock) const { 194 195 const MemRegion *lockR = lock.getAsRegion(); 196 if (!lockR) 197 return; 198 199 ProgramStateRef state = C.getState(); 200 201 if (const LockState *LState = state->get<LockMap>(lockR)) { 202 if (LState->isUnlocked()) { 203 if (!BT_doubleunlock) 204 BT_doubleunlock.reset(new BugType(this, "Double unlocking", 205 "Lock checker")); 206 ExplodedNode *N = C.generateErrorNode(); 207 if (!N) 208 return; 209 auto Report = llvm::make_unique<BugReport>( 210 *BT_doubleunlock, "This lock has already been unlocked", N); 211 Report->addRange(CE->getArg(0)->getSourceRange()); 212 C.emitReport(std::move(Report)); 213 return; 214 } else if (LState->isDestroyed()) { 215 reportUseDestroyedBug(C, CE); 216 return; 217 } 218 } 219 220 LockSetTy LS = state->get<LockSet>(); 221 222 // FIXME: Better analysis requires IPA for wrappers. 223 224 if (!LS.isEmpty()) { 225 const MemRegion *firstLockR = LS.getHead(); 226 if (firstLockR != lockR) { 227 if (!BT_lor) 228 BT_lor.reset(new BugType(this, "Lock order reversal", "Lock checker")); 229 ExplodedNode *N = C.generateErrorNode(); 230 if (!N) 231 return; 232 auto report = llvm::make_unique<BugReport>( 233 *BT_lor, "This was not the most recently acquired lock. Possible " 234 "lock order reversal", N); 235 report->addRange(CE->getArg(0)->getSourceRange()); 236 C.emitReport(std::move(report)); 237 return; 238 } 239 // Record that the lock was released. 240 state = state->set<LockSet>(LS.getTail()); 241 } 242 243 state = state->set<LockMap>(lockR, LockState::getUnlocked()); 244 C.addTransition(state); 245 } 246 247 void PthreadLockChecker::DestroyLock(CheckerContext &C, const CallExpr *CE, 248 SVal Lock) const { 249 250 const MemRegion *LockR = Lock.getAsRegion(); 251 if (!LockR) 252 return; 253 254 ProgramStateRef State = C.getState(); 255 256 const LockState *LState = State->get<LockMap>(LockR); 257 if (!LState || LState->isUnlocked()) { 258 State = State->set<LockMap>(LockR, LockState::getDestroyed()); 259 C.addTransition(State); 260 return; 261 } 262 263 StringRef Message; 264 265 if (LState->isLocked()) { 266 Message = "This lock is still locked"; 267 } else { 268 Message = "This lock has already been destroyed"; 269 } 270 271 if (!BT_destroylock) 272 BT_destroylock.reset(new BugType(this, "Destroy invalid lock", 273 "Lock checker")); 274 ExplodedNode *N = C.generateErrorNode(); 275 if (!N) 276 return; 277 auto Report = llvm::make_unique<BugReport>(*BT_destroylock, Message, N); 278 Report->addRange(CE->getArg(0)->getSourceRange()); 279 C.emitReport(std::move(Report)); 280 } 281 282 void PthreadLockChecker::InitLock(CheckerContext &C, const CallExpr *CE, 283 SVal Lock) const { 284 285 const MemRegion *LockR = Lock.getAsRegion(); 286 if (!LockR) 287 return; 288 289 ProgramStateRef State = C.getState(); 290 291 const struct LockState *LState = State->get<LockMap>(LockR); 292 if (!LState || LState->isDestroyed()) { 293 State = State->set<LockMap>(LockR, LockState::getUnlocked()); 294 C.addTransition(State); 295 return; 296 } 297 298 StringRef Message; 299 300 if (LState->isLocked()) { 301 Message = "This lock is still being held"; 302 } else { 303 Message = "This lock has already been initialized"; 304 } 305 306 if (!BT_initlock) 307 BT_initlock.reset(new BugType(this, "Init invalid lock", 308 "Lock checker")); 309 ExplodedNode *N = C.generateErrorNode(); 310 if (!N) 311 return; 312 auto Report = llvm::make_unique<BugReport>(*BT_initlock, Message, N); 313 Report->addRange(CE->getArg(0)->getSourceRange()); 314 C.emitReport(std::move(Report)); 315 } 316 317 void PthreadLockChecker::reportUseDestroyedBug(CheckerContext &C, 318 const CallExpr *CE) const { 319 if (!BT_destroylock) 320 BT_destroylock.reset(new BugType(this, "Use destroyed lock", 321 "Lock checker")); 322 ExplodedNode *N = C.generateErrorNode(); 323 if (!N) 324 return; 325 auto Report = llvm::make_unique<BugReport>( 326 *BT_destroylock, "This lock has already been destroyed", N); 327 Report->addRange(CE->getArg(0)->getSourceRange()); 328 C.emitReport(std::move(Report)); 329 } 330 331 void ento::registerPthreadLockChecker(CheckerManager &mgr) { 332 mgr.registerChecker<PthreadLockChecker>(); 333 } 334