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:
LockState__anon49f414400111::LockState37 LockState(Kind K) : K(K) {}
38
39 public:
getLocked__anon49f414400111::LockState40 static LockState getLocked() { return LockState(Locked); }
getUnlocked__anon49f414400111::LockState41 static LockState getUnlocked() { return LockState(Unlocked); }
getDestroyed__anon49f414400111::LockState42 static LockState getDestroyed() { return LockState(Destroyed); }
getUntouchedAndPossiblyDestroyed__anon49f414400111::LockState43 static LockState getUntouchedAndPossiblyDestroyed() {
44 return LockState(UntouchedAndPossiblyDestroyed);
45 }
getUnlockedAndPossiblyDestroyed__anon49f414400111::LockState46 static LockState getUnlockedAndPossiblyDestroyed() {
47 return LockState(UnlockedAndPossiblyDestroyed);
48 }
49
operator ==__anon49f414400111::LockState50 bool operator==(const LockState &X) const {
51 return K == X.K;
52 }
53
isLocked__anon49f414400111::LockState54 bool isLocked() const { return K == Locked; }
isUnlocked__anon49f414400111::LockState55 bool isUnlocked() const { return K == Unlocked; }
isDestroyed__anon49f414400111::LockState56 bool isDestroyed() const { return K == Destroyed; }
isUntouchedAndPossiblyDestroyed__anon49f414400111::LockState57 bool isUntouchedAndPossiblyDestroyed() const {
58 return K == UntouchedAndPossiblyDestroyed;
59 }
isUnlockedAndPossiblyDestroyed__anon49f414400111::LockState60 bool isUnlockedAndPossiblyDestroyed() const {
61 return K == UnlockedAndPossiblyDestroyed;
62 }
63
Profile__anon49f414400111::LockState64 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.
REGISTER_LIST_WITH_PROGRAMSTATE(LockSet,const MemRegion *)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.
resolvePossiblyDestroyedMutex(ProgramStateRef state,const MemRegion * lockR,const SymbolRef * sym) const159 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
printState(raw_ostream & Out,ProgramStateRef State,const char * NL,const char * Sep) const184 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
AcquireLock(CheckerContext & C,const CallExpr * CE,SVal lock,bool isTryLock,enum LockingSemantics semantics) const217 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
ReleaseLock(CheckerContext & C,const CallExpr * CE,SVal lock) const289 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
DestroyLock(CheckerContext & C,const CallExpr * CE,SVal Lock,enum LockingSemantics semantics) const347 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
InitLock(CheckerContext & C,const CallExpr * CE,SVal Lock) const408 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
reportUseDestroyedBug(CheckerContext & C,const CallExpr * CE) const447 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
checkDeadSymbols(SymbolReaper & SymReaper,CheckerContext & C) const461 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
registerPthreadLockChecker(CheckerManager & mgr)481 void ento::registerPthreadLockChecker(CheckerManager &mgr) {
482 mgr.registerChecker<PthreadLockChecker>();
483 }
484