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() { return LockState(Locked); }
36  static LockState getUnlocked() { return LockState(Unlocked); }
37  static LockState getDestroyed() { 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.generateErrorNode();
146      if (!N)
147        return;
148      auto report = llvm::make_unique<BugReport>(
149          *BT_doublelock, "This lock has already been acquired", N);
150      report->addRange(CE->getArg(0)->getSourceRange());
151      C.emitReport(std::move(report));
152      return;
153    } else if (LState->isDestroyed()) {
154      reportUseDestroyedBug(C, CE);
155      return;
156    }
157  }
158
159  ProgramStateRef lockSucc = state;
160  if (isTryLock) {
161    // Bifurcate the state, and allow a mode where the lock acquisition fails.
162    ProgramStateRef lockFail;
163    switch (semantics) {
164    case PthreadSemantics:
165      std::tie(lockFail, lockSucc) = state->assume(retVal);
166      break;
167    case XNUSemantics:
168      std::tie(lockSucc, lockFail) = state->assume(retVal);
169      break;
170    default:
171      llvm_unreachable("Unknown tryLock locking semantics");
172    }
173    assert(lockFail && lockSucc);
174    C.addTransition(lockFail);
175
176  } else if (semantics == PthreadSemantics) {
177    // Assume that the return value was 0.
178    lockSucc = state->assume(retVal, false);
179    assert(lockSucc);
180
181  } else {
182    // XNU locking semantics return void on non-try locks
183    assert((semantics == XNUSemantics) && "Unknown locking semantics");
184    lockSucc = state;
185  }
186
187  // Record that the lock was acquired.
188  lockSucc = lockSucc->add<LockSet>(lockR);
189  lockSucc = lockSucc->set<LockMap>(lockR, LockState::getLocked());
190  C.addTransition(lockSucc);
191}
192
193void PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE,
194                                     SVal lock) const {
195
196  const MemRegion *lockR = lock.getAsRegion();
197  if (!lockR)
198    return;
199
200  ProgramStateRef state = C.getState();
201
202  if (const LockState *LState = state->get<LockMap>(lockR)) {
203    if (LState->isUnlocked()) {
204      if (!BT_doubleunlock)
205        BT_doubleunlock.reset(new BugType(this, "Double unlocking",
206                                          "Lock checker"));
207      ExplodedNode *N = C.generateErrorNode();
208      if (!N)
209        return;
210      auto Report = llvm::make_unique<BugReport>(
211          *BT_doubleunlock, "This lock has already been unlocked", N);
212      Report->addRange(CE->getArg(0)->getSourceRange());
213      C.emitReport(std::move(Report));
214      return;
215    } else if (LState->isDestroyed()) {
216      reportUseDestroyedBug(C, CE);
217      return;
218    }
219  }
220
221  LockSetTy LS = state->get<LockSet>();
222
223  // FIXME: Better analysis requires IPA for wrappers.
224
225  if (!LS.isEmpty()) {
226    const MemRegion *firstLockR = LS.getHead();
227    if (firstLockR != lockR) {
228      if (!BT_lor)
229        BT_lor.reset(new BugType(this, "Lock order reversal", "Lock checker"));
230      ExplodedNode *N = C.generateErrorNode();
231      if (!N)
232        return;
233      auto report = llvm::make_unique<BugReport>(
234          *BT_lor, "This was not the most recently acquired lock. Possible "
235                   "lock order reversal", N);
236      report->addRange(CE->getArg(0)->getSourceRange());
237      C.emitReport(std::move(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
248void 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.generateErrorNode();
276  if (!N)
277    return;
278  auto Report = llvm::make_unique<BugReport>(*BT_destroylock, Message, N);
279  Report->addRange(CE->getArg(0)->getSourceRange());
280  C.emitReport(std::move(Report));
281}
282
283void PthreadLockChecker::InitLock(CheckerContext &C, const CallExpr *CE,
284                                  SVal Lock) const {
285
286  const MemRegion *LockR = Lock.getAsRegion();
287  if (!LockR)
288    return;
289
290  ProgramStateRef State = C.getState();
291
292  const struct LockState *LState = State->get<LockMap>(LockR);
293  if (!LState || LState->isDestroyed()) {
294    State = State->set<LockMap>(LockR, LockState::getUnlocked());
295    C.addTransition(State);
296    return;
297  }
298
299  StringRef Message;
300
301  if (LState->isLocked()) {
302    Message = "This lock is still being held";
303  } else {
304    Message = "This lock has already been initialized";
305  }
306
307  if (!BT_initlock)
308    BT_initlock.reset(new BugType(this, "Init invalid lock",
309                                  "Lock checker"));
310  ExplodedNode *N = C.generateErrorNode();
311  if (!N)
312    return;
313  auto Report = llvm::make_unique<BugReport>(*BT_initlock, Message, N);
314  Report->addRange(CE->getArg(0)->getSourceRange());
315  C.emitReport(std::move(Report));
316}
317
318void PthreadLockChecker::reportUseDestroyedBug(CheckerContext &C,
319                                               const CallExpr *CE) const {
320  if (!BT_destroylock)
321    BT_destroylock.reset(new BugType(this, "Use destroyed lock",
322                                     "Lock checker"));
323  ExplodedNode *N = C.generateErrorNode();
324  if (!N)
325    return;
326  auto Report = llvm::make_unique<BugReport>(
327      *BT_destroylock, "This lock has already been destroyed", N);
328  Report->addRange(CE->getArg(0)->getSourceRange());
329  C.emitReport(std::move(Report));
330}
331
332void ento::registerPthreadLockChecker(CheckerManager &mgr) {
333  mgr.registerChecker<PthreadLockChecker>();
334}
335