clang  6.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.
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 {
113  const LocationContext *LCtx = C.getLocationContext();
114  StringRef FName = C.getCalleeName(CE);
115  if (FName.empty())
116  return;
117 
118  if (CE->getNumArgs() != 1 && CE->getNumArgs() != 2)
119  return;
120 
121  if (FName == "pthread_mutex_lock" ||
122  FName == "pthread_rwlock_rdlock" ||
123  FName == "pthread_rwlock_wrlock")
124  AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
125  false, PthreadSemantics);
126  else if (FName == "lck_mtx_lock" ||
127  FName == "lck_rw_lock_exclusive" ||
128  FName == "lck_rw_lock_shared")
129  AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
130  false, XNUSemantics);
131  else if (FName == "pthread_mutex_trylock" ||
132  FName == "pthread_rwlock_tryrdlock" ||
133  FName == "pthread_rwlock_trywrlock")
134  AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
135  true, PthreadSemantics);
136  else if (FName == "lck_mtx_try_lock" ||
137  FName == "lck_rw_try_lock_exclusive" ||
138  FName == "lck_rw_try_lock_shared")
139  AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
140  true, XNUSemantics);
141  else if (FName == "pthread_mutex_unlock" ||
142  FName == "pthread_rwlock_unlock" ||
143  FName == "lck_mtx_unlock" ||
144  FName == "lck_rw_done")
145  ReleaseLock(C, CE, state->getSVal(CE->getArg(0), LCtx));
146  else if (FName == "pthread_mutex_destroy")
147  DestroyLock(C, CE, state->getSVal(CE->getArg(0), LCtx), PthreadSemantics);
148  else if (FName == "lck_mtx_destroy")
149  DestroyLock(C, CE, state->getSVal(CE->getArg(0), LCtx), XNUSemantics);
150  else if (FName == "pthread_mutex_init")
151  InitLock(C, CE, state->getSVal(CE->getArg(0), LCtx));
152 }
153 
154 // When a lock is destroyed, in some semantics(like PthreadSemantics) we are not
155 // sure if the destroy call has succeeded or failed, and the lock enters one of
156 // the 'possibly destroyed' state. There is a short time frame for the
157 // programmer to check the return value to see if the lock was successfully
158 // destroyed. Before we model the next operation over that lock, we call this
159 // function to see if the return value was checked by now and set the lock state
160 // - either to destroyed state or back to its previous state.
161 
162 // In PthreadSemantics, pthread_mutex_destroy() returns zero if the lock is
163 // successfully destroyed and it returns a non-zero value otherwise.
164 ProgramStateRef PthreadLockChecker::resolvePossiblyDestroyedMutex(
165  ProgramStateRef state, const MemRegion *lockR, const SymbolRef *sym) const {
166  const LockState *lstate = state->get<LockMap>(lockR);
167  // Existence in DestroyRetVal ensures existence in LockMap.
168  // Existence in Destroyed also ensures that the lock state for lockR is either
169  // UntouchedAndPossiblyDestroyed or UnlockedAndPossiblyDestroyed.
170  assert(lstate->isUntouchedAndPossiblyDestroyed() ||
171  lstate->isUnlockedAndPossiblyDestroyed());
172 
173  ConstraintManager &CMgr = state->getConstraintManager();
174  ConditionTruthVal retZero = CMgr.isNull(state, *sym);
175  if (retZero.isConstrainedFalse()) {
176  if (lstate->isUntouchedAndPossiblyDestroyed())
177  state = state->remove<LockMap>(lockR);
178  else if (lstate->isUnlockedAndPossiblyDestroyed())
179  state = state->set<LockMap>(lockR, LockState::getUnlocked());
180  } else
181  state = state->set<LockMap>(lockR, LockState::getDestroyed());
182 
183  // Removing the map entry (lockR, sym) from DestroyRetVal as the lock state is
184  // now resolved.
185  state = state->remove<DestroyRetVal>(lockR);
186  return state;
187 }
188 
189 void PthreadLockChecker::printState(raw_ostream &Out, ProgramStateRef State,
190  const char *NL, const char *Sep) const {
191  LockMapTy LM = State->get<LockMap>();
192  if (!LM.isEmpty()) {
193  Out << Sep << "Mutex states:" << NL;
194  for (auto I : LM) {
195  I.first->dumpToStream(Out);
196  if (I.second.isLocked())
197  Out << ": locked";
198  else if (I.second.isUnlocked())
199  Out << ": unlocked";
200  else if (I.second.isDestroyed())
201  Out << ": destroyed";
202  else if (I.second.isUntouchedAndPossiblyDestroyed())
203  Out << ": not tracked, possibly destroyed";
204  else if (I.second.isUnlockedAndPossiblyDestroyed())
205  Out << ": unlocked, possibly destroyed";
206  Out << NL;
207  }
208  }
209 
210  LockSetTy LS = State->get<LockSet>();
211  if (!LS.isEmpty()) {
212  Out << Sep << "Mutex lock order:" << NL;
213  for (auto I: LS) {
214  I->dumpToStream(Out);
215  Out << NL;
216  }
217  }
218 
219  // TODO: Dump destroyed mutex symbols?
220 }
221 
222 void PthreadLockChecker::AcquireLock(CheckerContext &C, const CallExpr *CE,
223  SVal lock, bool isTryLock,
224  enum LockingSemantics semantics) const {
225 
226  const MemRegion *lockR = lock.getAsRegion();
227  if (!lockR)
228  return;
229 
230  ProgramStateRef state = C.getState();
231  const SymbolRef *sym = state->get<DestroyRetVal>(lockR);
232  if (sym)
233  state = resolvePossiblyDestroyedMutex(state, lockR, sym);
234 
235  SVal X = state->getSVal(CE, C.getLocationContext());
236  if (X.isUnknownOrUndef())
237  return;
238 
239  DefinedSVal retVal = X.castAs<DefinedSVal>();
240 
241  if (const LockState *LState = state->get<LockMap>(lockR)) {
242  if (LState->isLocked()) {
243  if (!BT_doublelock)
244  BT_doublelock.reset(new BugType(this, "Double locking",
245  "Lock checker"));
247  if (!N)
248  return;
249  auto report = llvm::make_unique<BugReport>(
250  *BT_doublelock, "This lock has already been acquired", N);
251  report->addRange(CE->getArg(0)->getSourceRange());
252  C.emitReport(std::move(report));
253  return;
254  } else if (LState->isDestroyed()) {
255  reportUseDestroyedBug(C, CE);
256  return;
257  }
258  }
259 
260  ProgramStateRef lockSucc = state;
261  if (isTryLock) {
262  // Bifurcate the state, and allow a mode where the lock acquisition fails.
263  ProgramStateRef lockFail;
264  switch (semantics) {
265  case PthreadSemantics:
266  std::tie(lockFail, lockSucc) = state->assume(retVal);
267  break;
268  case XNUSemantics:
269  std::tie(lockSucc, lockFail) = state->assume(retVal);
270  break;
271  default:
272  llvm_unreachable("Unknown tryLock locking semantics");
273  }
274  assert(lockFail && lockSucc);
275  C.addTransition(lockFail);
276 
277  } else if (semantics == PthreadSemantics) {
278  // Assume that the return value was 0.
279  lockSucc = state->assume(retVal, false);
280  assert(lockSucc);
281 
282  } else {
283  // XNU locking semantics return void on non-try locks
284  assert((semantics == XNUSemantics) && "Unknown locking semantics");
285  lockSucc = state;
286  }
287 
288  // Record that the lock was acquired.
289  lockSucc = lockSucc->add<LockSet>(lockR);
290  lockSucc = lockSucc->set<LockMap>(lockR, LockState::getLocked());
291  C.addTransition(lockSucc);
292 }
293 
294 void PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE,
295  SVal lock) const {
296 
297  const MemRegion *lockR = lock.getAsRegion();
298  if (!lockR)
299  return;
300 
301  ProgramStateRef state = C.getState();
302  const SymbolRef *sym = state->get<DestroyRetVal>(lockR);
303  if (sym)
304  state = resolvePossiblyDestroyedMutex(state, lockR, sym);
305 
306  if (const LockState *LState = state->get<LockMap>(lockR)) {
307  if (LState->isUnlocked()) {
308  if (!BT_doubleunlock)
309  BT_doubleunlock.reset(new BugType(this, "Double unlocking",
310  "Lock checker"));
312  if (!N)
313  return;
314  auto Report = llvm::make_unique<BugReport>(
315  *BT_doubleunlock, "This lock has already been unlocked", N);
316  Report->addRange(CE->getArg(0)->getSourceRange());
317  C.emitReport(std::move(Report));
318  return;
319  } else if (LState->isDestroyed()) {
320  reportUseDestroyedBug(C, CE);
321  return;
322  }
323  }
324 
325  LockSetTy LS = state->get<LockSet>();
326 
327  // FIXME: Better analysis requires IPA for wrappers.
328 
329  if (!LS.isEmpty()) {
330  const MemRegion *firstLockR = LS.getHead();
331  if (firstLockR != lockR) {
332  if (!BT_lor)
333  BT_lor.reset(new BugType(this, "Lock order reversal", "Lock checker"));
335  if (!N)
336  return;
337  auto report = llvm::make_unique<BugReport>(
338  *BT_lor, "This was not the most recently acquired lock. Possible "
339  "lock order reversal", N);
340  report->addRange(CE->getArg(0)->getSourceRange());
341  C.emitReport(std::move(report));
342  return;
343  }
344  // Record that the lock was released.
345  state = state->set<LockSet>(LS.getTail());
346  }
347 
348  state = state->set<LockMap>(lockR, LockState::getUnlocked());
349  C.addTransition(state);
350 }
351 
352 void PthreadLockChecker::DestroyLock(CheckerContext &C, const CallExpr *CE,
353  SVal Lock,
354  enum LockingSemantics semantics) const {
355 
356  const MemRegion *LockR = Lock.getAsRegion();
357  if (!LockR)
358  return;
359 
360  ProgramStateRef State = C.getState();
361 
362  const SymbolRef *sym = State->get<DestroyRetVal>(LockR);
363  if (sym)
364  State = resolvePossiblyDestroyedMutex(State, LockR, sym);
365 
366  const LockState *LState = State->get<LockMap>(LockR);
367  // Checking the return value of the destroy method only in the case of
368  // PthreadSemantics
369  if (semantics == PthreadSemantics) {
370  if (!LState || LState->isUnlocked()) {
371  SymbolRef sym = C.getSVal(CE).getAsSymbol();
372  if (!sym) {
373  State = State->remove<LockMap>(LockR);
374  C.addTransition(State);
375  return;
376  }
377  State = State->set<DestroyRetVal>(LockR, sym);
378  if (LState && LState->isUnlocked())
379  State = State->set<LockMap>(
380  LockR, LockState::getUnlockedAndPossiblyDestroyed());
381  else
382  State = State->set<LockMap>(
383  LockR, LockState::getUntouchedAndPossiblyDestroyed());
384  C.addTransition(State);
385  return;
386  }
387  } else {
388  if (!LState || LState->isUnlocked()) {
389  State = State->set<LockMap>(LockR, LockState::getDestroyed());
390  C.addTransition(State);
391  return;
392  }
393  }
394  StringRef Message;
395 
396  if (LState->isLocked()) {
397  Message = "This lock is still locked";
398  } else {
399  Message = "This lock has already been destroyed";
400  }
401 
402  if (!BT_destroylock)
403  BT_destroylock.reset(new BugType(this, "Destroy invalid lock",
404  "Lock checker"));
406  if (!N)
407  return;
408  auto Report = llvm::make_unique<BugReport>(*BT_destroylock, Message, N);
409  Report->addRange(CE->getArg(0)->getSourceRange());
410  C.emitReport(std::move(Report));
411 }
412 
413 void PthreadLockChecker::InitLock(CheckerContext &C, const CallExpr *CE,
414  SVal Lock) const {
415 
416  const MemRegion *LockR = Lock.getAsRegion();
417  if (!LockR)
418  return;
419 
420  ProgramStateRef State = C.getState();
421 
422  const SymbolRef *sym = State->get<DestroyRetVal>(LockR);
423  if (sym)
424  State = resolvePossiblyDestroyedMutex(State, LockR, sym);
425 
426  const struct LockState *LState = State->get<LockMap>(LockR);
427  if (!LState || LState->isDestroyed()) {
428  State = State->set<LockMap>(LockR, LockState::getUnlocked());
429  C.addTransition(State);
430  return;
431  }
432 
433  StringRef Message;
434 
435  if (LState->isLocked()) {
436  Message = "This lock is still being held";
437  } else {
438  Message = "This lock has already been initialized";
439  }
440 
441  if (!BT_initlock)
442  BT_initlock.reset(new BugType(this, "Init invalid lock",
443  "Lock checker"));
445  if (!N)
446  return;
447  auto Report = llvm::make_unique<BugReport>(*BT_initlock, Message, N);
448  Report->addRange(CE->getArg(0)->getSourceRange());
449  C.emitReport(std::move(Report));
450 }
451 
452 void PthreadLockChecker::reportUseDestroyedBug(CheckerContext &C,
453  const CallExpr *CE) const {
454  if (!BT_destroylock)
455  BT_destroylock.reset(new BugType(this, "Use destroyed lock",
456  "Lock checker"));
458  if (!N)
459  return;
460  auto Report = llvm::make_unique<BugReport>(
461  *BT_destroylock, "This lock has already been destroyed", N);
462  Report->addRange(CE->getArg(0)->getSourceRange());
463  C.emitReport(std::move(Report));
464 }
465 
466 void PthreadLockChecker::checkDeadSymbols(SymbolReaper &SymReaper,
467  CheckerContext &C) const {
468  ProgramStateRef State = C.getState();
469 
470  // TODO: Clean LockMap when a mutex region dies.
471 
472  DestroyRetValTy TrackedSymbols = State->get<DestroyRetVal>();
473  for (DestroyRetValTy::iterator I = TrackedSymbols.begin(),
474  E = TrackedSymbols.end();
475  I != E; ++I) {
476  const SymbolRef Sym = I->second;
477  const MemRegion *lockR = I->first;
478  bool IsSymDead = SymReaper.isDead(Sym);
479  // Remove the dead symbol from the return value symbols map.
480  if (IsSymDead)
481  State = resolvePossiblyDestroyedMutex(State, lockR, &Sym);
482  }
483  C.addTransition(State);
484 }
485 
486 void ento::registerPthreadLockChecker(CheckerManager &mgr) {
487  mgr.registerChecker<PthreadLockChecker>();
488 }
bool isConstrainedFalse() const
Return true if the constraint is perfectly constrained to &#39;false&#39;.
MemRegion - The root abstract class for all memory regions.
Definition: MemRegion.h:79
ExplodedNode * generateErrorNode(ProgramStateRef State=nullptr, const ProgramPointTag *Tag=nullptr)
Generate a transition to a node that will be used to report an error.
Expr * getArg(unsigned Arg)
getArg - Return the specified argument.
Definition: Expr.h:2278
bool operator==(CanQual< T > x, CanQual< U > y)
unsigned getNumArgs() const
getNumArgs - Return the number of actual arguments to this call.
Definition: Expr.h:2266
ExplodedNode * addTransition(ProgramStateRef State=nullptr, const ProgramPointTag *Tag=nullptr)
Generates a new transition in the program state graph (ExplodedGraph).
bool isDead(SymbolRef sym) const
Returns whether or not a symbol has been confirmed dead.
SVal getSVal(const Stmt *S) const
Get the value of arbitrary expressions at this point in the path.
Symbolic value.
Definition: SymExpr.h:29
StringRef getCalleeName(const FunctionDecl *FunDecl) const
Get the name of the called function (path-sensitive).
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
SymbolRef getAsSymbol(bool IncludeBaseRegions=false) const
If this SVal wraps a symbol return that SymbolRef.
Definition: SVals.cpp:116
#define REGISTER_MAP_WITH_PROGRAMSTATE(Name, Key, Value)
Declares an immutable map of type NameTy, suitable for placement into the ProgramState.
void emitReport(std::unique_ptr< BugReport > R)
Emit the diagnostics report.
Kind
CHECKER * registerChecker()
Used to register checkers.
const MemRegion * getAsRegion() const
Definition: SVals.cpp:140
SVal - This represents a symbolic expression, which can be either an L-value or an R-value...
Definition: SVals.h:63
A class responsible for cleaning up unused symbols.
Dataflow Directional Tag Classes.
T castAs() const
Convert to the specified SVal type, asserting that this SVal is of the desired type.
Definition: SVals.h:92
const ProgramStateRef & getState() const
X
Add a minimal nested name specifier fixit hint to allow lookup of a tag name from an outer enclosing ...
Definition: SemaDecl.cpp:13010
#define REGISTER_LIST_WITH_PROGRAMSTATE(Name, Elem)
Declares an immutable list of type NameTy, suitable for placement into the ProgramState.
SourceRange getSourceRange() const LLVM_READONLY
SourceLocation tokens are not useful in isolation - they are low level value objects created/interpre...
Definition: Stmt.cpp:265
CallExpr - Represents a function call (C99 6.5.2.2, C++ [expr.call]).
Definition: Expr.h:2209
const LocationContext * getLocationContext() const
bool isUnknownOrUndef() const
Definition: SVals.h:133