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