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:
37   LockState(Kind K) : K(K) {}
38 
39 public:
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);
45   }
46   static LockState getUnlockedAndPossiblyDestroyed() {
47     return LockState(UnlockedAndPossiblyDestroyed);
48   }
49 
50   bool operator==(const LockState &X) const {
51     return K == X.K;
52   }
53 
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;
59   }
60   bool isUnlockedAndPossiblyDestroyed() const {
61     return K == UnlockedAndPossiblyDestroyed;
62   }
63 
64   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 
85   void AcquireLock(CheckerContext &C, const CallExpr *CE, SVal lock,
86                    bool isTryLock, enum LockingSemantics semantics) const;
87 
88   void ReleaseLock(CheckerContext &C, const CallExpr *CE, SVal lock) const;
89   void DestroyLock(CheckerContext &C, const CallExpr *CE, SVal Lock,
90                    enum LockingSemantics semantics) const;
91   void InitLock(CheckerContext &C, const CallExpr *CE, SVal Lock) const;
92   void reportUseDestroyedBug(CheckerContext &C, const CallExpr *CE) const;
93   ProgramStateRef resolvePossiblyDestroyedMutex(ProgramStateRef state,
94                                                 const MemRegion *lockR,
95                                                 const SymbolRef *sym) const;
96 };
97 } // end anonymous namespace
98 
99 // A stack of locks for tracking lock-unlock order.
100 REGISTER_LIST_WITH_PROGRAMSTATE(LockSet, const MemRegion *)
101 
102 // An entry for tracking lock states.
103 REGISTER_MAP_WITH_PROGRAMSTATE(LockMap, const MemRegion *, LockState)
104 
105 // Return values for unresolved calls to pthread_mutex_destroy().
106 REGISTER_MAP_WITH_PROGRAMSTATE(DestroyRetVal, const MemRegion *, SymbolRef)
107 
108 void PthreadLockChecker::checkPostStmt(const CallExpr *CE,
109                                        CheckerContext &C) const {
110   ProgramStateRef state = C.getState();
111   const LocationContext *LCtx = C.getLocationContext();
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, state->getSVal(CE->getArg(0), LCtx),
123                 false, PthreadSemantics);
124   else if (FName == "lck_mtx_lock" ||
125            FName == "lck_rw_lock_exclusive" ||
126            FName == "lck_rw_lock_shared")
127     AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
128                 false, XNUSemantics);
129   else if (FName == "pthread_mutex_trylock" ||
130            FName == "pthread_rwlock_tryrdlock" ||
131            FName == "pthread_rwlock_trywrlock")
132     AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
133                 true, PthreadSemantics);
134   else if (FName == "lck_mtx_try_lock" ||
135            FName == "lck_rw_try_lock_exclusive" ||
136            FName == "lck_rw_try_lock_shared")
137     AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
138                 true, XNUSemantics);
139   else if (FName == "pthread_mutex_unlock" ||
140            FName == "pthread_rwlock_unlock" ||
141            FName == "lck_mtx_unlock" ||
142            FName == "lck_rw_done")
143     ReleaseLock(C, CE, state->getSVal(CE->getArg(0), LCtx));
144   else if (FName == "pthread_mutex_destroy")
145     DestroyLock(C, CE, state->getSVal(CE->getArg(0), LCtx), PthreadSemantics);
146   else if (FName == "lck_mtx_destroy")
147     DestroyLock(C, CE, state->getSVal(CE->getArg(0), LCtx), XNUSemantics);
148   else if (FName == "pthread_mutex_init")
149     InitLock(C, CE, state->getSVal(CE->getArg(0), LCtx));
150 }
151 
152 // When a lock is destroyed, in some semantics(like PthreadSemantics) we are not
153 // sure if the destroy call has succeeded or failed, and the lock enters one of
154 // the 'possibly destroyed' state. There is a short time frame for the
155 // programmer to check the return value to see if the lock was successfully
156 // destroyed. Before we model the next operation over that lock, we call this
157 // function to see if the return value was checked by now and set the lock state
158 // - either to destroyed state or back to its previous state.
159 
160 // In PthreadSemantics, pthread_mutex_destroy() returns zero if the lock is
161 // successfully destroyed and it returns a non-zero value otherwise.
162 ProgramStateRef PthreadLockChecker::resolvePossiblyDestroyedMutex(
163     ProgramStateRef state, const MemRegion *lockR, const SymbolRef *sym) const {
164   const LockState *lstate = state->get<LockMap>(lockR);
165   // Existence in DestroyRetVal ensures existence in LockMap.
166   // Existence in Destroyed also ensures that the lock state for lockR is either
167   // UntouchedAndPossiblyDestroyed or UnlockedAndPossiblyDestroyed.
168   assert(lstate->isUntouchedAndPossiblyDestroyed() ||
169          lstate->isUnlockedAndPossiblyDestroyed());
170 
171   ConstraintManager &CMgr = state->getConstraintManager();
172   ConditionTruthVal retZero = CMgr.isNull(state, *sym);
173   if (retZero.isConstrainedFalse()) {
174     if (lstate->isUntouchedAndPossiblyDestroyed())
175       state = state->remove<LockMap>(lockR);
176     else if (lstate->isUnlockedAndPossiblyDestroyed())
177       state = state->set<LockMap>(lockR, LockState::getUnlocked());
178   } else
179     state = state->set<LockMap>(lockR, LockState::getDestroyed());
180 
181   // Removing the map entry (lockR, sym) from DestroyRetVal as the lock state is
182   // now resolved.
183   state = state->remove<DestroyRetVal>(lockR);
184   return state;
185 }
186 
187 void PthreadLockChecker::AcquireLock(CheckerContext &C, const CallExpr *CE,
188                                      SVal lock, bool isTryLock,
189                                      enum LockingSemantics semantics) const {
190 
191   const MemRegion *lockR = lock.getAsRegion();
192   if (!lockR)
193     return;
194 
195   ProgramStateRef state = C.getState();
196   const SymbolRef *sym = state->get<DestroyRetVal>(lockR);
197   if (sym)
198     state = resolvePossiblyDestroyedMutex(state, lockR, sym);
199 
200   SVal X = state->getSVal(CE, C.getLocationContext());
201   if (X.isUnknownOrUndef())
202     return;
203 
204   DefinedSVal retVal = X.castAs<DefinedSVal>();
205 
206   if (const LockState *LState = state->get<LockMap>(lockR)) {
207     if (LState->isLocked()) {
208       if (!BT_doublelock)
209         BT_doublelock.reset(new BugType(this, "Double locking",
210                                         "Lock checker"));
211       ExplodedNode *N = C.generateErrorNode();
212       if (!N)
213         return;
214       auto report = llvm::make_unique<BugReport>(
215           *BT_doublelock, "This lock has already been acquired", N);
216       report->addRange(CE->getArg(0)->getSourceRange());
217       C.emitReport(std::move(report));
218       return;
219     } else if (LState->isDestroyed()) {
220       reportUseDestroyedBug(C, CE);
221       return;
222     }
223   }
224 
225   ProgramStateRef lockSucc = state;
226   if (isTryLock) {
227     // Bifurcate the state, and allow a mode where the lock acquisition fails.
228     ProgramStateRef lockFail;
229     switch (semantics) {
230     case PthreadSemantics:
231       std::tie(lockFail, lockSucc) = state->assume(retVal);
232       break;
233     case XNUSemantics:
234       std::tie(lockSucc, lockFail) = state->assume(retVal);
235       break;
236     default:
237       llvm_unreachable("Unknown tryLock locking semantics");
238     }
239     assert(lockFail && lockSucc);
240     C.addTransition(lockFail);
241 
242   } else if (semantics == PthreadSemantics) {
243     // Assume that the return value was 0.
244     lockSucc = state->assume(retVal, false);
245     assert(lockSucc);
246 
247   } else {
248     // XNU locking semantics return void on non-try locks
249     assert((semantics == XNUSemantics) && "Unknown locking semantics");
250     lockSucc = state;
251   }
252 
253   // Record that the lock was acquired.
254   lockSucc = lockSucc->add<LockSet>(lockR);
255   lockSucc = lockSucc->set<LockMap>(lockR, LockState::getLocked());
256   C.addTransition(lockSucc);
257 }
258 
259 void PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE,
260                                      SVal lock) const {
261 
262   const MemRegion *lockR = lock.getAsRegion();
263   if (!lockR)
264     return;
265 
266   ProgramStateRef state = C.getState();
267   const SymbolRef *sym = state->get<DestroyRetVal>(lockR);
268   if (sym)
269     state = resolvePossiblyDestroyedMutex(state, lockR, sym);
270 
271   if (const LockState *LState = state->get<LockMap>(lockR)) {
272     if (LState->isUnlocked()) {
273       if (!BT_doubleunlock)
274         BT_doubleunlock.reset(new BugType(this, "Double unlocking",
275                                           "Lock checker"));
276       ExplodedNode *N = C.generateErrorNode();
277       if (!N)
278         return;
279       auto Report = llvm::make_unique<BugReport>(
280           *BT_doubleunlock, "This lock has already been unlocked", N);
281       Report->addRange(CE->getArg(0)->getSourceRange());
282       C.emitReport(std::move(Report));
283       return;
284     } else if (LState->isDestroyed()) {
285       reportUseDestroyedBug(C, CE);
286       return;
287     }
288   }
289 
290   LockSetTy LS = state->get<LockSet>();
291 
292   // FIXME: Better analysis requires IPA for wrappers.
293 
294   if (!LS.isEmpty()) {
295     const MemRegion *firstLockR = LS.getHead();
296     if (firstLockR != lockR) {
297       if (!BT_lor)
298         BT_lor.reset(new BugType(this, "Lock order reversal", "Lock checker"));
299       ExplodedNode *N = C.generateErrorNode();
300       if (!N)
301         return;
302       auto report = llvm::make_unique<BugReport>(
303           *BT_lor, "This was not the most recently acquired lock. Possible "
304                    "lock order reversal", N);
305       report->addRange(CE->getArg(0)->getSourceRange());
306       C.emitReport(std::move(report));
307       return;
308     }
309     // Record that the lock was released.
310     state = state->set<LockSet>(LS.getTail());
311   }
312 
313   state = state->set<LockMap>(lockR, LockState::getUnlocked());
314   C.addTransition(state);
315 }
316 
317 void PthreadLockChecker::DestroyLock(CheckerContext &C, const CallExpr *CE,
318                                      SVal Lock,
319                                      enum LockingSemantics semantics) const {
320 
321   const MemRegion *LockR = Lock.getAsRegion();
322   if (!LockR)
323     return;
324 
325   ProgramStateRef State = C.getState();
326 
327   const SymbolRef *sym = State->get<DestroyRetVal>(LockR);
328   if (sym)
329     State = resolvePossiblyDestroyedMutex(State, LockR, sym);
330 
331   const LockState *LState = State->get<LockMap>(LockR);
332   // Checking the return value of the destroy method only in the case of
333   // PthreadSemantics
334   if (semantics == PthreadSemantics) {
335     if (!LState || LState->isUnlocked()) {
336       SymbolRef sym = C.getSVal(CE).getAsSymbol();
337       if (!sym) {
338         State = State->remove<LockMap>(LockR);
339         C.addTransition(State);
340         return;
341       }
342       State = State->set<DestroyRetVal>(LockR, sym);
343       if (LState && LState->isUnlocked())
344         State = State->set<LockMap>(
345             LockR, LockState::getUnlockedAndPossiblyDestroyed());
346       else
347         State = State->set<LockMap>(
348             LockR, LockState::getUntouchedAndPossiblyDestroyed());
349       C.addTransition(State);
350       return;
351     }
352   } else {
353     if (!LState || LState->isUnlocked()) {
354       State = State->set<LockMap>(LockR, LockState::getDestroyed());
355       C.addTransition(State);
356       return;
357     }
358   }
359   StringRef Message;
360 
361   if (LState->isLocked()) {
362     Message = "This lock is still locked";
363   } else {
364     Message = "This lock has already been destroyed";
365   }
366 
367   if (!BT_destroylock)
368     BT_destroylock.reset(new BugType(this, "Destroy invalid lock",
369                                      "Lock checker"));
370   ExplodedNode *N = C.generateErrorNode();
371   if (!N)
372     return;
373   auto Report = llvm::make_unique<BugReport>(*BT_destroylock, Message, N);
374   Report->addRange(CE->getArg(0)->getSourceRange());
375   C.emitReport(std::move(Report));
376 }
377 
378 void PthreadLockChecker::InitLock(CheckerContext &C, const CallExpr *CE,
379                                   SVal Lock) const {
380 
381   const MemRegion *LockR = Lock.getAsRegion();
382   if (!LockR)
383     return;
384 
385   ProgramStateRef State = C.getState();
386 
387   const SymbolRef *sym = State->get<DestroyRetVal>(LockR);
388   if (sym)
389     State = resolvePossiblyDestroyedMutex(State, LockR, sym);
390 
391   const struct LockState *LState = State->get<LockMap>(LockR);
392   if (!LState || LState->isDestroyed()) {
393     State = State->set<LockMap>(LockR, LockState::getUnlocked());
394     C.addTransition(State);
395     return;
396   }
397 
398   StringRef Message;
399 
400   if (LState->isLocked()) {
401     Message = "This lock is still being held";
402   } else {
403     Message = "This lock has already been initialized";
404   }
405 
406   if (!BT_initlock)
407     BT_initlock.reset(new BugType(this, "Init invalid lock",
408                                   "Lock checker"));
409   ExplodedNode *N = C.generateErrorNode();
410   if (!N)
411     return;
412   auto Report = llvm::make_unique<BugReport>(*BT_initlock, Message, N);
413   Report->addRange(CE->getArg(0)->getSourceRange());
414   C.emitReport(std::move(Report));
415 }
416 
417 void PthreadLockChecker::reportUseDestroyedBug(CheckerContext &C,
418                                                const CallExpr *CE) const {
419   if (!BT_destroylock)
420     BT_destroylock.reset(new BugType(this, "Use destroyed lock",
421                                      "Lock checker"));
422   ExplodedNode *N = C.generateErrorNode();
423   if (!N)
424     return;
425   auto Report = llvm::make_unique<BugReport>(
426       *BT_destroylock, "This lock has already been destroyed", N);
427   Report->addRange(CE->getArg(0)->getSourceRange());
428   C.emitReport(std::move(Report));
429 }
430 
431 void PthreadLockChecker::checkDeadSymbols(SymbolReaper &SymReaper,
432                                           CheckerContext &C) const {
433   ProgramStateRef State = C.getState();
434 
435   // TODO: Clean LockMap when a mutex region dies.
436 
437   DestroyRetValTy TrackedSymbols = State->get<DestroyRetVal>();
438   for (DestroyRetValTy::iterator I = TrackedSymbols.begin(),
439                                  E = TrackedSymbols.end();
440        I != E; ++I) {
441     const SymbolRef Sym = I->second;
442     const MemRegion *lockR = I->first;
443     bool IsSymDead = SymReaper.isDead(Sym);
444     // Remove the dead symbol from the return value symbols map.
445     if (IsSymDead)
446       State = resolvePossiblyDestroyedMutex(State, lockR, &Sym);
447   }
448   C.addTransition(State);
449 }
450 
451 void ento::registerPthreadLockChecker(CheckerManager &mgr) {
452   mgr.registerChecker<PthreadLockChecker>();
453 }
454