clang  8.0.0svn
PthreadLockChecker.cpp
Go to the documentation of this file.
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"
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  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.
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.
159 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 
184 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 
217 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 
289 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 
347 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 
408 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 
447 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 
461 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 
481 void ento::registerPthreadLockChecker(CheckerManager &mgr) {
482  mgr.registerChecker<PthreadLockChecker>();
483 }
Expr * getArg(unsigned Arg)
getArg - Return the specified argument.
Definition: Expr.h:2359
bool operator==(CanQual< T > x, CanQual< U > y)
const SymExpr * SymbolRef
unsigned getNumArgs() const
getNumArgs - Return the number of actual arguments to this call.
Definition: Expr.h:2347
IntrusiveRefCntPtr< const ProgramState > ProgramStateRef
LineState State
i32 captured_struct **param SharedsTy A type which contains references the shared variables *param Shareds Context with the list of shared variables from the p *TaskFunction *param Data Additional data for task generation like final * state
#define REGISTER_LIST_WITH_PROGRAMSTATE(Name, Elem)
Declares an immutable list type NameTy, suitable for placement into the ProgramState.
Kind
#define REGISTER_MAP_WITH_PROGRAMSTATE(Name, Key, Value)
Declares an immutable map of type NameTy, suitable for placement into the ProgramState.
Dataflow Directional Tag Classes.
X
Add a minimal nested name specifier fixit hint to allow lookup of a tag name from an outer enclosing ...
Definition: SemaDecl.cpp:13803
SourceRange getSourceRange() const LLVM_READONLY
SourceLocation tokens are not useful in isolation - they are low level value objects created/interpre...
Definition: Stmt.cpp:268
CallExpr - Represents a function call (C99 6.5.2.2, C++ [expr.call]).
Definition: Expr.h:2290