1 //===--- PthreadLockChecker.cpp - Check for locking problems ---*- C++ -*--===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This defines PthreadLockChecker, a simple lock -> unlock checker.
11 // Also handles XNU locks, which behave similarly enough to share code.
13 //===----------------------------------------------------------------------===//
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"
22 using namespace clang;
32 UntouchedAndPossiblyDestroyed,
33 UnlockedAndPossiblyDestroyed
37 LockState(Kind K) : K(K) {}
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);
46 static LockState getUnlockedAndPossiblyDestroyed() {
47 return LockState(UnlockedAndPossiblyDestroyed);
50 bool operator==(const LockState &X) const {
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;
60 bool isUnlockedAndPossiblyDestroyed() const {
61 return K == UnlockedAndPossiblyDestroyed;
64 void Profile(llvm::FoldingSetNodeID &ID) const {
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 {
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;
87 void AcquireLock(CheckerContext &C, const CallExpr *CE, SVal lock,
88 bool isTryLock, enum LockingSemantics semantics) const;
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;
99 } // end anonymous namespace
101 // A stack of locks for tracking lock-unlock order.
102 REGISTER_LIST_WITH_PROGRAMSTATE(LockSet, const MemRegion *)
104 // An entry for tracking lock states.
105 REGISTER_MAP_WITH_PROGRAMSTATE(LockMap, const MemRegion *, LockState)
107 // Return values for unresolved calls to pthread_mutex_destroy().
108 REGISTER_MAP_WITH_PROGRAMSTATE(DestroyRetVal, const MemRegion *, SymbolRef)
110 void PthreadLockChecker::checkPostStmt(const CallExpr *CE,
111 CheckerContext &C) const {
112 ProgramStateRef state = C.getState();
113 const LocationContext *LCtx = C.getLocationContext();
114 StringRef FName = C.getCalleeName(CE);
118 if (CE->getNumArgs() != 1 && CE->getNumArgs() != 2)
121 if (FName == "pthread_mutex_lock" ||
122 FName == "pthread_rwlock_rdlock" ||
123 FName == "pthread_rwlock_wrlock")
124 AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
125 false, PthreadSemantics);
126 else if (FName == "lck_mtx_lock" ||
127 FName == "lck_rw_lock_exclusive" ||
128 FName == "lck_rw_lock_shared")
129 AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
130 false, XNUSemantics);
131 else if (FName == "pthread_mutex_trylock" ||
132 FName == "pthread_rwlock_tryrdlock" ||
133 FName == "pthread_rwlock_trywrlock")
134 AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
135 true, PthreadSemantics);
136 else if (FName == "lck_mtx_try_lock" ||
137 FName == "lck_rw_try_lock_exclusive" ||
138 FName == "lck_rw_try_lock_shared")
139 AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
141 else if (FName == "pthread_mutex_unlock" ||
142 FName == "pthread_rwlock_unlock" ||
143 FName == "lck_mtx_unlock" ||
144 FName == "lck_rw_done")
145 ReleaseLock(C, CE, state->getSVal(CE->getArg(0), LCtx));
146 else if (FName == "pthread_mutex_destroy")
147 DestroyLock(C, CE, state->getSVal(CE->getArg(0), LCtx), PthreadSemantics);
148 else if (FName == "lck_mtx_destroy")
149 DestroyLock(C, CE, state->getSVal(CE->getArg(0), LCtx), XNUSemantics);
150 else if (FName == "pthread_mutex_init")
151 InitLock(C, CE, state->getSVal(CE->getArg(0), LCtx));
154 // When a lock is destroyed, in some semantics(like PthreadSemantics) we are not
155 // sure if the destroy call has succeeded or failed, and the lock enters one of
156 // the 'possibly destroyed' state. There is a short time frame for the
157 // programmer to check the return value to see if the lock was successfully
158 // destroyed. Before we model the next operation over that lock, we call this
159 // function to see if the return value was checked by now and set the lock state
160 // - either to destroyed state or back to its previous state.
162 // In PthreadSemantics, pthread_mutex_destroy() returns zero if the lock is
163 // successfully destroyed and it returns a non-zero value otherwise.
164 ProgramStateRef PthreadLockChecker::resolvePossiblyDestroyedMutex(
165 ProgramStateRef state, const MemRegion *lockR, const SymbolRef *sym) const {
166 const LockState *lstate = state->get<LockMap>(lockR);
167 // Existence in DestroyRetVal ensures existence in LockMap.
168 // Existence in Destroyed also ensures that the lock state for lockR is either
169 // UntouchedAndPossiblyDestroyed or UnlockedAndPossiblyDestroyed.
170 assert(lstate->isUntouchedAndPossiblyDestroyed() ||
171 lstate->isUnlockedAndPossiblyDestroyed());
173 ConstraintManager &CMgr = state->getConstraintManager();
174 ConditionTruthVal retZero = CMgr.isNull(state, *sym);
175 if (retZero.isConstrainedFalse()) {
176 if (lstate->isUntouchedAndPossiblyDestroyed())
177 state = state->remove<LockMap>(lockR);
178 else if (lstate->isUnlockedAndPossiblyDestroyed())
179 state = state->set<LockMap>(lockR, LockState::getUnlocked());
181 state = state->set<LockMap>(lockR, LockState::getDestroyed());
183 // Removing the map entry (lockR, sym) from DestroyRetVal as the lock state is
185 state = state->remove<DestroyRetVal>(lockR);
189 void PthreadLockChecker::printState(raw_ostream &Out, ProgramStateRef State,
190 const char *NL, const char *Sep) const {
191 LockMapTy LM = State->get<LockMap>();
193 Out << Sep << "Mutex states:" << NL;
195 I.first->dumpToStream(Out);
196 if (I.second.isLocked())
198 else if (I.second.isUnlocked())
200 else if (I.second.isDestroyed())
201 Out << ": destroyed";
202 else if (I.second.isUntouchedAndPossiblyDestroyed())
203 Out << ": not tracked, possibly destroyed";
204 else if (I.second.isUnlockedAndPossiblyDestroyed())
205 Out << ": unlocked, possibly destroyed";
210 LockSetTy LS = State->get<LockSet>();
212 Out << Sep << "Mutex lock order:" << NL;
214 I->dumpToStream(Out);
219 // TODO: Dump destroyed mutex symbols?
222 void PthreadLockChecker::AcquireLock(CheckerContext &C, const CallExpr *CE,
223 SVal lock, bool isTryLock,
224 enum LockingSemantics semantics) const {
226 const MemRegion *lockR = lock.getAsRegion();
230 ProgramStateRef state = C.getState();
231 const SymbolRef *sym = state->get<DestroyRetVal>(lockR);
233 state = resolvePossiblyDestroyedMutex(state, lockR, sym);
235 SVal X = state->getSVal(CE, C.getLocationContext());
236 if (X.isUnknownOrUndef())
239 DefinedSVal retVal = X.castAs<DefinedSVal>();
241 if (const LockState *LState = state->get<LockMap>(lockR)) {
242 if (LState->isLocked()) {
244 BT_doublelock.reset(new BugType(this, "Double locking",
246 ExplodedNode *N = C.generateErrorNode();
249 auto report = llvm::make_unique<BugReport>(
250 *BT_doublelock, "This lock has already been acquired", N);
251 report->addRange(CE->getArg(0)->getSourceRange());
252 C.emitReport(std::move(report));
254 } else if (LState->isDestroyed()) {
255 reportUseDestroyedBug(C, CE);
260 ProgramStateRef lockSucc = state;
262 // Bifurcate the state, and allow a mode where the lock acquisition fails.
263 ProgramStateRef lockFail;
265 case PthreadSemantics:
266 std::tie(lockFail, lockSucc) = state->assume(retVal);
269 std::tie(lockSucc, lockFail) = state->assume(retVal);
272 llvm_unreachable("Unknown tryLock locking semantics");
274 assert(lockFail && lockSucc);
275 C.addTransition(lockFail);
277 } else if (semantics == PthreadSemantics) {
278 // Assume that the return value was 0.
279 lockSucc = state->assume(retVal, false);
283 // XNU locking semantics return void on non-try locks
284 assert((semantics == XNUSemantics) && "Unknown locking semantics");
288 // Record that the lock was acquired.
289 lockSucc = lockSucc->add<LockSet>(lockR);
290 lockSucc = lockSucc->set<LockMap>(lockR, LockState::getLocked());
291 C.addTransition(lockSucc);
294 void PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE,
297 const MemRegion *lockR = lock.getAsRegion();
301 ProgramStateRef state = C.getState();
302 const SymbolRef *sym = state->get<DestroyRetVal>(lockR);
304 state = resolvePossiblyDestroyedMutex(state, lockR, sym);
306 if (const LockState *LState = state->get<LockMap>(lockR)) {
307 if (LState->isUnlocked()) {
308 if (!BT_doubleunlock)
309 BT_doubleunlock.reset(new BugType(this, "Double unlocking",
311 ExplodedNode *N = C.generateErrorNode();
314 auto Report = llvm::make_unique<BugReport>(
315 *BT_doubleunlock, "This lock has already been unlocked", N);
316 Report->addRange(CE->getArg(0)->getSourceRange());
317 C.emitReport(std::move(Report));
319 } else if (LState->isDestroyed()) {
320 reportUseDestroyedBug(C, CE);
325 LockSetTy LS = state->get<LockSet>();
327 // FIXME: Better analysis requires IPA for wrappers.
330 const MemRegion *firstLockR = LS.getHead();
331 if (firstLockR != lockR) {
333 BT_lor.reset(new BugType(this, "Lock order reversal", "Lock checker"));
334 ExplodedNode *N = C.generateErrorNode();
337 auto report = llvm::make_unique<BugReport>(
338 *BT_lor, "This was not the most recently acquired lock. Possible "
339 "lock order reversal", N);
340 report->addRange(CE->getArg(0)->getSourceRange());
341 C.emitReport(std::move(report));
344 // Record that the lock was released.
345 state = state->set<LockSet>(LS.getTail());
348 state = state->set<LockMap>(lockR, LockState::getUnlocked());
349 C.addTransition(state);
352 void PthreadLockChecker::DestroyLock(CheckerContext &C, const CallExpr *CE,
354 enum LockingSemantics semantics) const {
356 const MemRegion *LockR = Lock.getAsRegion();
360 ProgramStateRef State = C.getState();
362 const SymbolRef *sym = State->get<DestroyRetVal>(LockR);
364 State = resolvePossiblyDestroyedMutex(State, LockR, sym);
366 const LockState *LState = State->get<LockMap>(LockR);
367 // Checking the return value of the destroy method only in the case of
369 if (semantics == PthreadSemantics) {
370 if (!LState || LState->isUnlocked()) {
371 SymbolRef sym = C.getSVal(CE).getAsSymbol();
373 State = State->remove<LockMap>(LockR);
374 C.addTransition(State);
377 State = State->set<DestroyRetVal>(LockR, sym);
378 if (LState && LState->isUnlocked())
379 State = State->set<LockMap>(
380 LockR, LockState::getUnlockedAndPossiblyDestroyed());
382 State = State->set<LockMap>(
383 LockR, LockState::getUntouchedAndPossiblyDestroyed());
384 C.addTransition(State);
388 if (!LState || LState->isUnlocked()) {
389 State = State->set<LockMap>(LockR, LockState::getDestroyed());
390 C.addTransition(State);
396 if (LState->isLocked()) {
397 Message = "This lock is still locked";
399 Message = "This lock has already been destroyed";
403 BT_destroylock.reset(new BugType(this, "Destroy invalid lock",
405 ExplodedNode *N = C.generateErrorNode();
408 auto Report = llvm::make_unique<BugReport>(*BT_destroylock, Message, N);
409 Report->addRange(CE->getArg(0)->getSourceRange());
410 C.emitReport(std::move(Report));
413 void PthreadLockChecker::InitLock(CheckerContext &C, const CallExpr *CE,
416 const MemRegion *LockR = Lock.getAsRegion();
420 ProgramStateRef State = C.getState();
422 const SymbolRef *sym = State->get<DestroyRetVal>(LockR);
424 State = resolvePossiblyDestroyedMutex(State, LockR, sym);
426 const struct LockState *LState = State->get<LockMap>(LockR);
427 if (!LState || LState->isDestroyed()) {
428 State = State->set<LockMap>(LockR, LockState::getUnlocked());
429 C.addTransition(State);
435 if (LState->isLocked()) {
436 Message = "This lock is still being held";
438 Message = "This lock has already been initialized";
442 BT_initlock.reset(new BugType(this, "Init invalid lock",
444 ExplodedNode *N = C.generateErrorNode();
447 auto Report = llvm::make_unique<BugReport>(*BT_initlock, Message, N);
448 Report->addRange(CE->getArg(0)->getSourceRange());
449 C.emitReport(std::move(Report));
452 void PthreadLockChecker::reportUseDestroyedBug(CheckerContext &C,
453 const CallExpr *CE) const {
455 BT_destroylock.reset(new BugType(this, "Use destroyed lock",
457 ExplodedNode *N = C.generateErrorNode();
460 auto Report = llvm::make_unique<BugReport>(
461 *BT_destroylock, "This lock has already been destroyed", N);
462 Report->addRange(CE->getArg(0)->getSourceRange());
463 C.emitReport(std::move(Report));
466 void PthreadLockChecker::checkDeadSymbols(SymbolReaper &SymReaper,
467 CheckerContext &C) const {
468 ProgramStateRef State = C.getState();
470 // TODO: Clean LockMap when a mutex region dies.
472 DestroyRetValTy TrackedSymbols = State->get<DestroyRetVal>();
473 for (DestroyRetValTy::iterator I = TrackedSymbols.begin(),
474 E = TrackedSymbols.end();
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.
481 State = resolvePossiblyDestroyedMutex(State, lockR, &Sym);
483 C.addTransition(State);
486 void ento::registerPthreadLockChecker(CheckerManager &mgr) {
487 mgr.registerChecker<PthreadLockChecker>();