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