clang  14.0.0git
PthreadLockChecker.cpp
Go to the documentation of this file.
1 //===--- PthreadLockChecker.cpp - Check for locking problems ---*- C++ -*--===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines:
10 // * PthreadLockChecker, a simple lock -> unlock checker.
11 // Which also checks for XNU locks, which behave similarly enough to share
12 // code.
13 // * FuchsiaLocksChecker, which is also rather similar.
14 // * C11LockChecker which also closely follows Pthread semantics.
15 //
16 // TODO: Path notes.
17 //
18 //===----------------------------------------------------------------------===//
19 
26 
27 using namespace clang;
28 using namespace ento;
29 
30 namespace {
31 
32 struct LockState {
33  enum Kind {
34  Destroyed,
35  Locked,
36  Unlocked,
37  UntouchedAndPossiblyDestroyed,
38  UnlockedAndPossiblyDestroyed
39  } K;
40 
41 private:
42  LockState(Kind K) : K(K) {}
43 
44 public:
45  static LockState getLocked() { return LockState(Locked); }
46  static LockState getUnlocked() { return LockState(Unlocked); }
47  static LockState getDestroyed() { return LockState(Destroyed); }
48  static LockState getUntouchedAndPossiblyDestroyed() {
49  return LockState(UntouchedAndPossiblyDestroyed);
50  }
51  static LockState getUnlockedAndPossiblyDestroyed() {
52  return LockState(UnlockedAndPossiblyDestroyed);
53  }
54 
55  bool operator==(const LockState &X) const { return K == X.K; }
56 
57  bool isLocked() const { return K == Locked; }
58  bool isUnlocked() const { return K == Unlocked; }
59  bool isDestroyed() const { return K == Destroyed; }
60  bool isUntouchedAndPossiblyDestroyed() const {
61  return K == UntouchedAndPossiblyDestroyed;
62  }
63  bool isUnlockedAndPossiblyDestroyed() const {
64  return K == UnlockedAndPossiblyDestroyed;
65  }
66 
67  void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(K); }
68 };
69 
70 class PthreadLockChecker : public Checker<check::PostCall, check::DeadSymbols,
71  check::RegionChanges> {
72 public:
73  enum LockingSemantics { NotApplicable = 0, PthreadSemantics, XNUSemantics };
74  enum CheckerKind {
75  CK_PthreadLockChecker,
76  CK_FuchsiaLockChecker,
77  CK_C11LockChecker,
78  CK_NumCheckKinds
79  };
80  DefaultBool ChecksEnabled[CK_NumCheckKinds];
81  CheckerNameRef CheckNames[CK_NumCheckKinds];
82 
83 private:
84  typedef void (PthreadLockChecker::*FnCheck)(const CallEvent &Call,
85  CheckerContext &C,
86  CheckerKind CheckKind) const;
87  CallDescriptionMap<FnCheck> PThreadCallbacks = {
88  // Init.
89  {{"pthread_mutex_init", 2}, &PthreadLockChecker::InitAnyLock},
90  // TODO: pthread_rwlock_init(2 arguments).
91  // TODO: lck_mtx_init(3 arguments).
92  // TODO: lck_mtx_alloc_init(2 arguments) => returns the mutex.
93  // TODO: lck_rw_init(3 arguments).
94  // TODO: lck_rw_alloc_init(2 arguments) => returns the mutex.
95 
96  // Acquire.
97  {{"pthread_mutex_lock", 1}, &PthreadLockChecker::AcquirePthreadLock},
98  {{"pthread_rwlock_rdlock", 1}, &PthreadLockChecker::AcquirePthreadLock},
99  {{"pthread_rwlock_wrlock", 1}, &PthreadLockChecker::AcquirePthreadLock},
100  {{"lck_mtx_lock", 1}, &PthreadLockChecker::AcquireXNULock},
101  {{"lck_rw_lock_exclusive", 1}, &PthreadLockChecker::AcquireXNULock},
102  {{"lck_rw_lock_shared", 1}, &PthreadLockChecker::AcquireXNULock},
103 
104  // Try.
105  {{"pthread_mutex_trylock", 1}, &PthreadLockChecker::TryPthreadLock},
106  {{"pthread_rwlock_tryrdlock", 1}, &PthreadLockChecker::TryPthreadLock},
107  {{"pthread_rwlock_trywrlock", 1}, &PthreadLockChecker::TryPthreadLock},
108  {{"lck_mtx_try_lock", 1}, &PthreadLockChecker::TryXNULock},
109  {{"lck_rw_try_lock_exclusive", 1}, &PthreadLockChecker::TryXNULock},
110  {{"lck_rw_try_lock_shared", 1}, &PthreadLockChecker::TryXNULock},
111 
112  // Release.
113  {{"pthread_mutex_unlock", 1}, &PthreadLockChecker::ReleaseAnyLock},
114  {{"pthread_rwlock_unlock", 1}, &PthreadLockChecker::ReleaseAnyLock},
115  {{"lck_mtx_unlock", 1}, &PthreadLockChecker::ReleaseAnyLock},
116  {{"lck_rw_unlock_exclusive", 1}, &PthreadLockChecker::ReleaseAnyLock},
117  {{"lck_rw_unlock_shared", 1}, &PthreadLockChecker::ReleaseAnyLock},
118  {{"lck_rw_done", 1}, &PthreadLockChecker::ReleaseAnyLock},
119 
120  // Destroy.
121  {{"pthread_mutex_destroy", 1}, &PthreadLockChecker::DestroyPthreadLock},
122  {{"lck_mtx_destroy", 2}, &PthreadLockChecker::DestroyXNULock},
123  // TODO: pthread_rwlock_destroy(1 argument).
124  // TODO: lck_rw_destroy(2 arguments).
125  };
126 
127  CallDescriptionMap<FnCheck> FuchsiaCallbacks = {
128  // Init.
129  {{"spin_lock_init", 1}, &PthreadLockChecker::InitAnyLock},
130 
131  // Acquire.
132  {{"spin_lock", 1}, &PthreadLockChecker::AcquirePthreadLock},
133  {{"spin_lock_save", 3}, &PthreadLockChecker::AcquirePthreadLock},
134  {{"sync_mutex_lock", 1}, &PthreadLockChecker::AcquirePthreadLock},
135  {{"sync_mutex_lock_with_waiter", 1},
136  &PthreadLockChecker::AcquirePthreadLock},
137 
138  // Try.
139  {{"spin_trylock", 1}, &PthreadLockChecker::TryFuchsiaLock},
140  {{"sync_mutex_trylock", 1}, &PthreadLockChecker::TryFuchsiaLock},
141  {{"sync_mutex_timedlock", 2}, &PthreadLockChecker::TryFuchsiaLock},
142 
143  // Release.
144  {{"spin_unlock", 1}, &PthreadLockChecker::ReleaseAnyLock},
145  {{"spin_unlock_restore", 3}, &PthreadLockChecker::ReleaseAnyLock},
146  {{"sync_mutex_unlock", 1}, &PthreadLockChecker::ReleaseAnyLock},
147  };
148 
149  CallDescriptionMap<FnCheck> C11Callbacks = {
150  // Init.
151  {{"mtx_init", 2}, &PthreadLockChecker::InitAnyLock},
152 
153  // Acquire.
154  {{"mtx_lock", 1}, &PthreadLockChecker::AcquirePthreadLock},
155 
156  // Try.
157  {{"mtx_trylock", 1}, &PthreadLockChecker::TryC11Lock},
158  {{"mtx_timedlock", 2}, &PthreadLockChecker::TryC11Lock},
159 
160  // Release.
161  {{"mtx_unlock", 1}, &PthreadLockChecker::ReleaseAnyLock},
162 
163  // Destroy
164  {{"mtx_destroy", 1}, &PthreadLockChecker::DestroyPthreadLock},
165  };
166 
167  ProgramStateRef resolvePossiblyDestroyedMutex(ProgramStateRef state,
168  const MemRegion *lockR,
169  const SymbolRef *sym) const;
170  void reportBug(CheckerContext &C, std::unique_ptr<BugType> BT[],
171  const Expr *MtxExpr, CheckerKind CheckKind,
172  StringRef Desc) const;
173 
174  // Init.
175  void InitAnyLock(const CallEvent &Call, CheckerContext &C,
176  CheckerKind CheckKind) const;
177  void InitLockAux(const CallEvent &Call, CheckerContext &C,
178  const Expr *MtxExpr, SVal MtxVal,
179  CheckerKind CheckKind) const;
180 
181  // Lock, Try-lock.
182  void AcquirePthreadLock(const CallEvent &Call, CheckerContext &C,
183  CheckerKind CheckKind) const;
184  void AcquireXNULock(const CallEvent &Call, CheckerContext &C,
185  CheckerKind CheckKind) const;
186  void TryPthreadLock(const CallEvent &Call, CheckerContext &C,
187  CheckerKind CheckKind) const;
188  void TryXNULock(const CallEvent &Call, CheckerContext &C,
189  CheckerKind CheckKind) const;
190  void TryFuchsiaLock(const CallEvent &Call, CheckerContext &C,
191  CheckerKind CheckKind) const;
192  void TryC11Lock(const CallEvent &Call, CheckerContext &C,
193  CheckerKind CheckKind) const;
194  void AcquireLockAux(const CallEvent &Call, CheckerContext &C,
195  const Expr *MtxExpr, SVal MtxVal, bool IsTryLock,
196  LockingSemantics Semantics, CheckerKind CheckKind) const;
197 
198  // Release.
199  void ReleaseAnyLock(const CallEvent &Call, CheckerContext &C,
200  CheckerKind CheckKind) const;
201  void ReleaseLockAux(const CallEvent &Call, CheckerContext &C,
202  const Expr *MtxExpr, SVal MtxVal,
203  CheckerKind CheckKind) const;
204 
205  // Destroy.
206  void DestroyPthreadLock(const CallEvent &Call, CheckerContext &C,
207  CheckerKind CheckKind) const;
208  void DestroyXNULock(const CallEvent &Call, CheckerContext &C,
209  CheckerKind CheckKind) const;
210  void DestroyLockAux(const CallEvent &Call, CheckerContext &C,
211  const Expr *MtxExpr, SVal MtxVal,
212  LockingSemantics Semantics, CheckerKind CheckKind) const;
213 
214 public:
215  void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
216  void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const;
218  checkRegionChanges(ProgramStateRef State, const InvalidatedSymbols *Symbols,
219  ArrayRef<const MemRegion *> ExplicitRegions,
221  const LocationContext *LCtx, const CallEvent *Call) const;
222  void printState(raw_ostream &Out, ProgramStateRef State, const char *NL,
223  const char *Sep) const override;
224 
225 private:
226  mutable std::unique_ptr<BugType> BT_doublelock[CK_NumCheckKinds];
227  mutable std::unique_ptr<BugType> BT_doubleunlock[CK_NumCheckKinds];
228  mutable std::unique_ptr<BugType> BT_destroylock[CK_NumCheckKinds];
229  mutable std::unique_ptr<BugType> BT_initlock[CK_NumCheckKinds];
230  mutable std::unique_ptr<BugType> BT_lor[CK_NumCheckKinds];
231 
232  void initBugType(CheckerKind CheckKind) const {
233  if (BT_doublelock[CheckKind])
234  return;
235  BT_doublelock[CheckKind].reset(
236  new BugType{CheckNames[CheckKind], "Double locking", "Lock checker"});
237  BT_doubleunlock[CheckKind].reset(
238  new BugType{CheckNames[CheckKind], "Double unlocking", "Lock checker"});
239  BT_destroylock[CheckKind].reset(new BugType{
240  CheckNames[CheckKind], "Use destroyed lock", "Lock checker"});
241  BT_initlock[CheckKind].reset(new BugType{
242  CheckNames[CheckKind], "Init invalid lock", "Lock checker"});
243  BT_lor[CheckKind].reset(new BugType{CheckNames[CheckKind],
244  "Lock order reversal", "Lock checker"});
245  }
246 };
247 } // end anonymous namespace
248 
249 // A stack of locks for tracking lock-unlock order.
250 REGISTER_LIST_WITH_PROGRAMSTATE(LockSet, const MemRegion *)
251 
252 // An entry for tracking lock states.
253 REGISTER_MAP_WITH_PROGRAMSTATE(LockMap, const MemRegion *, LockState)
254 
255 // Return values for unresolved calls to pthread_mutex_destroy().
256 REGISTER_MAP_WITH_PROGRAMSTATE(DestroyRetVal, const MemRegion *, SymbolRef)
257 
258 void PthreadLockChecker::checkPostCall(const CallEvent &Call,
259  CheckerContext &C) const {
260  // An additional umbrella check that all functions modeled by this checker
261  // are global C functions.
262  // TODO: Maybe make this the default behavior of CallDescription
263  // with exactly one identifier?
264  // FIXME: Try to handle cases when the implementation was inlined rather
265  // than just giving up.
266  if (!Call.isGlobalCFunction() || C.wasInlined)
267  return;
268 
269  if (const FnCheck *Callback = PThreadCallbacks.lookup(Call))
270  (this->**Callback)(Call, C, CK_PthreadLockChecker);
271  else if (const FnCheck *Callback = FuchsiaCallbacks.lookup(Call))
272  (this->**Callback)(Call, C, CK_FuchsiaLockChecker);
273  else if (const FnCheck *Callback = C11Callbacks.lookup(Call))
274  (this->**Callback)(Call, C, CK_C11LockChecker);
275 }
276 
277 // When a lock is destroyed, in some semantics(like PthreadSemantics) we are not
278 // sure if the destroy call has succeeded or failed, and the lock enters one of
279 // the 'possibly destroyed' state. There is a short time frame for the
280 // programmer to check the return value to see if the lock was successfully
281 // destroyed. Before we model the next operation over that lock, we call this
282 // function to see if the return value was checked by now and set the lock state
283 // - either to destroyed state or back to its previous state.
284 
285 // In PthreadSemantics, pthread_mutex_destroy() returns zero if the lock is
286 // successfully destroyed and it returns a non-zero value otherwise.
287 ProgramStateRef PthreadLockChecker::resolvePossiblyDestroyedMutex(
288  ProgramStateRef state, const MemRegion *lockR, const SymbolRef *sym) const {
289  const LockState *lstate = state->get<LockMap>(lockR);
290  // Existence in DestroyRetVal ensures existence in LockMap.
291  // Existence in Destroyed also ensures that the lock state for lockR is either
292  // UntouchedAndPossiblyDestroyed or UnlockedAndPossiblyDestroyed.
293  assert(lstate->isUntouchedAndPossiblyDestroyed() ||
294  lstate->isUnlockedAndPossiblyDestroyed());
295 
296  ConstraintManager &CMgr = state->getConstraintManager();
297  ConditionTruthVal retZero = CMgr.isNull(state, *sym);
298  if (retZero.isConstrainedFalse()) {
299  if (lstate->isUntouchedAndPossiblyDestroyed())
300  state = state->remove<LockMap>(lockR);
301  else if (lstate->isUnlockedAndPossiblyDestroyed())
302  state = state->set<LockMap>(lockR, LockState::getUnlocked());
303  } else
304  state = state->set<LockMap>(lockR, LockState::getDestroyed());
305 
306  // Removing the map entry (lockR, sym) from DestroyRetVal as the lock state is
307  // now resolved.
308  state = state->remove<DestroyRetVal>(lockR);
309  return state;
310 }
311 
312 void PthreadLockChecker::printState(raw_ostream &Out, ProgramStateRef State,
313  const char *NL, const char *Sep) const {
314  LockMapTy LM = State->get<LockMap>();
315  if (!LM.isEmpty()) {
316  Out << Sep << "Mutex states:" << NL;
317  for (auto I : LM) {
318  I.first->dumpToStream(Out);
319  if (I.second.isLocked())
320  Out << ": locked";
321  else if (I.second.isUnlocked())
322  Out << ": unlocked";
323  else if (I.second.isDestroyed())
324  Out << ": destroyed";
325  else if (I.second.isUntouchedAndPossiblyDestroyed())
326  Out << ": not tracked, possibly destroyed";
327  else if (I.second.isUnlockedAndPossiblyDestroyed())
328  Out << ": unlocked, possibly destroyed";
329  Out << NL;
330  }
331  }
332 
333  LockSetTy LS = State->get<LockSet>();
334  if (!LS.isEmpty()) {
335  Out << Sep << "Mutex lock order:" << NL;
336  for (auto I : LS) {
337  I->dumpToStream(Out);
338  Out << NL;
339  }
340  }
341 
342  DestroyRetValTy DRV = State->get<DestroyRetVal>();
343  if (!DRV.isEmpty()) {
344  Out << Sep << "Mutexes in unresolved possibly destroyed state:" << NL;
345  for (auto I : DRV) {
346  I.first->dumpToStream(Out);
347  Out << ": ";
348  I.second->dumpToStream(Out);
349  Out << NL;
350  }
351  }
352 }
353 
354 void PthreadLockChecker::AcquirePthreadLock(const CallEvent &Call,
355  CheckerContext &C,
356  CheckerKind CheckKind) const {
357  AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), false,
358  PthreadSemantics, CheckKind);
359 }
360 
361 void PthreadLockChecker::AcquireXNULock(const CallEvent &Call,
362  CheckerContext &C,
363  CheckerKind CheckKind) const {
364  AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), false,
365  XNUSemantics, CheckKind);
366 }
367 
368 void PthreadLockChecker::TryPthreadLock(const CallEvent &Call,
369  CheckerContext &C,
370  CheckerKind CheckKind) const {
371  AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true,
372  PthreadSemantics, CheckKind);
373 }
374 
375 void PthreadLockChecker::TryXNULock(const CallEvent &Call, CheckerContext &C,
376  CheckerKind CheckKind) const {
377  AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true,
378  PthreadSemantics, CheckKind);
379 }
380 
381 void PthreadLockChecker::TryFuchsiaLock(const CallEvent &Call,
382  CheckerContext &C,
383  CheckerKind CheckKind) const {
384  AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true,
385  PthreadSemantics, CheckKind);
386 }
387 
388 void PthreadLockChecker::TryC11Lock(const CallEvent &Call, CheckerContext &C,
389  CheckerKind CheckKind) const {
390  AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true,
391  PthreadSemantics, CheckKind);
392 }
393 
394 void PthreadLockChecker::AcquireLockAux(const CallEvent &Call,
395  CheckerContext &C, const Expr *MtxExpr,
396  SVal MtxVal, bool IsTryLock,
397  enum LockingSemantics Semantics,
398  CheckerKind CheckKind) const {
399  if (!ChecksEnabled[CheckKind])
400  return;
401 
402  const MemRegion *lockR = MtxVal.getAsRegion();
403  if (!lockR)
404  return;
405 
406  ProgramStateRef state = C.getState();
407  const SymbolRef *sym = state->get<DestroyRetVal>(lockR);
408  if (sym)
409  state = resolvePossiblyDestroyedMutex(state, lockR, sym);
410 
411  if (const LockState *LState = state->get<LockMap>(lockR)) {
412  if (LState->isLocked()) {
413  reportBug(C, BT_doublelock, MtxExpr, CheckKind,
414  "This lock has already been acquired");
415  return;
416  } else if (LState->isDestroyed()) {
417  reportBug(C, BT_destroylock, MtxExpr, CheckKind,
418  "This lock has already been destroyed");
419  return;
420  }
421  }
422 
423  ProgramStateRef lockSucc = state;
424  if (IsTryLock) {
425  // Bifurcate the state, and allow a mode where the lock acquisition fails.
426  SVal RetVal = Call.getReturnValue();
427  if (auto DefinedRetVal = RetVal.getAs<DefinedSVal>()) {
428  ProgramStateRef lockFail;
429  switch (Semantics) {
430  case PthreadSemantics:
431  std::tie(lockFail, lockSucc) = state->assume(*DefinedRetVal);
432  break;
433  case XNUSemantics:
434  std::tie(lockSucc, lockFail) = state->assume(*DefinedRetVal);
435  break;
436  default:
437  llvm_unreachable("Unknown tryLock locking semantics");
438  }
439  assert(lockFail && lockSucc);
440  C.addTransition(lockFail);
441  }
442  // We might want to handle the case when the mutex lock function was inlined
443  // and returned an Unknown or Undefined value.
444  } else if (Semantics == PthreadSemantics) {
445  // Assume that the return value was 0.
446  SVal RetVal = Call.getReturnValue();
447  if (auto DefinedRetVal = RetVal.getAs<DefinedSVal>()) {
448  // FIXME: If the lock function was inlined and returned true,
449  // we need to behave sanely - at least generate sink.
450  lockSucc = state->assume(*DefinedRetVal, false);
451  assert(lockSucc);
452  }
453  // We might want to handle the case when the mutex lock function was inlined
454  // and returned an Unknown or Undefined value.
455  } else {
456  // XNU locking semantics return void on non-try locks
457  assert((Semantics == XNUSemantics) && "Unknown locking semantics");
458  lockSucc = state;
459  }
460 
461  // Record that the lock was acquired.
462  lockSucc = lockSucc->add<LockSet>(lockR);
463  lockSucc = lockSucc->set<LockMap>(lockR, LockState::getLocked());
464  C.addTransition(lockSucc);
465 }
466 
467 void PthreadLockChecker::ReleaseAnyLock(const CallEvent &Call,
468  CheckerContext &C,
469  CheckerKind CheckKind) const {
470  ReleaseLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), CheckKind);
471 }
472 
473 void PthreadLockChecker::ReleaseLockAux(const CallEvent &Call,
474  CheckerContext &C, const Expr *MtxExpr,
475  SVal MtxVal,
476  CheckerKind CheckKind) const {
477  if (!ChecksEnabled[CheckKind])
478  return;
479 
480  const MemRegion *lockR = MtxVal.getAsRegion();
481  if (!lockR)
482  return;
483 
484  ProgramStateRef state = C.getState();
485  const SymbolRef *sym = state->get<DestroyRetVal>(lockR);
486  if (sym)
487  state = resolvePossiblyDestroyedMutex(state, lockR, sym);
488 
489  if (const LockState *LState = state->get<LockMap>(lockR)) {
490  if (LState->isUnlocked()) {
491  reportBug(C, BT_doubleunlock, MtxExpr, CheckKind,
492  "This lock has already been unlocked");
493  return;
494  } else if (LState->isDestroyed()) {
495  reportBug(C, BT_destroylock, MtxExpr, CheckKind,
496  "This lock has already been destroyed");
497  return;
498  }
499  }
500 
501  LockSetTy LS = state->get<LockSet>();
502 
503  if (!LS.isEmpty()) {
504  const MemRegion *firstLockR = LS.getHead();
505  if (firstLockR != lockR) {
506  reportBug(C, BT_lor, MtxExpr, CheckKind,
507  "This was not the most recently acquired lock. Possible lock "
508  "order reversal");
509  return;
510  }
511  // Record that the lock was released.
512  state = state->set<LockSet>(LS.getTail());
513  }
514 
515  state = state->set<LockMap>(lockR, LockState::getUnlocked());
516  C.addTransition(state);
517 }
518 
519 void PthreadLockChecker::DestroyPthreadLock(const CallEvent &Call,
520  CheckerContext &C,
521  CheckerKind CheckKind) const {
522  DestroyLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0),
523  PthreadSemantics, CheckKind);
524 }
525 
526 void PthreadLockChecker::DestroyXNULock(const CallEvent &Call,
527  CheckerContext &C,
528  CheckerKind CheckKind) const {
529  DestroyLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), XNUSemantics,
530  CheckKind);
531 }
532 
533 void PthreadLockChecker::DestroyLockAux(const CallEvent &Call,
534  CheckerContext &C, const Expr *MtxExpr,
535  SVal MtxVal,
536  enum LockingSemantics Semantics,
537  CheckerKind CheckKind) const {
538  if (!ChecksEnabled[CheckKind])
539  return;
540 
541  const MemRegion *LockR = MtxVal.getAsRegion();
542  if (!LockR)
543  return;
544 
545  ProgramStateRef State = C.getState();
546 
547  const SymbolRef *sym = State->get<DestroyRetVal>(LockR);
548  if (sym)
549  State = resolvePossiblyDestroyedMutex(State, LockR, sym);
550 
551  const LockState *LState = State->get<LockMap>(LockR);
552  // Checking the return value of the destroy method only in the case of
553  // PthreadSemantics
554  if (Semantics == PthreadSemantics) {
555  if (!LState || LState->isUnlocked()) {
556  SymbolRef sym = Call.getReturnValue().getAsSymbol();
557  if (!sym) {
558  State = State->remove<LockMap>(LockR);
559  C.addTransition(State);
560  return;
561  }
562  State = State->set<DestroyRetVal>(LockR, sym);
563  if (LState && LState->isUnlocked())
564  State = State->set<LockMap>(
565  LockR, LockState::getUnlockedAndPossiblyDestroyed());
566  else
567  State = State->set<LockMap>(
568  LockR, LockState::getUntouchedAndPossiblyDestroyed());
569  C.addTransition(State);
570  return;
571  }
572  } else {
573  if (!LState || LState->isUnlocked()) {
574  State = State->set<LockMap>(LockR, LockState::getDestroyed());
575  C.addTransition(State);
576  return;
577  }
578  }
579 
580  StringRef Message = LState->isLocked()
581  ? "This lock is still locked"
582  : "This lock has already been destroyed";
583 
584  reportBug(C, BT_destroylock, MtxExpr, CheckKind, Message);
585 }
586 
587 void PthreadLockChecker::InitAnyLock(const CallEvent &Call, CheckerContext &C,
588  CheckerKind CheckKind) const {
589  InitLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), CheckKind);
590 }
591 
592 void PthreadLockChecker::InitLockAux(const CallEvent &Call, CheckerContext &C,
593  const Expr *MtxExpr, SVal MtxVal,
594  CheckerKind CheckKind) const {
595  if (!ChecksEnabled[CheckKind])
596  return;
597 
598  const MemRegion *LockR = MtxVal.getAsRegion();
599  if (!LockR)
600  return;
601 
602  ProgramStateRef State = C.getState();
603 
604  const SymbolRef *sym = State->get<DestroyRetVal>(LockR);
605  if (sym)
606  State = resolvePossiblyDestroyedMutex(State, LockR, sym);
607 
608  const struct LockState *LState = State->get<LockMap>(LockR);
609  if (!LState || LState->isDestroyed()) {
610  State = State->set<LockMap>(LockR, LockState::getUnlocked());
611  C.addTransition(State);
612  return;
613  }
614 
615  StringRef Message = LState->isLocked()
616  ? "This lock is still being held"
617  : "This lock has already been initialized";
618 
619  reportBug(C, BT_initlock, MtxExpr, CheckKind, Message);
620 }
621 
622 void PthreadLockChecker::reportBug(CheckerContext &C,
623  std::unique_ptr<BugType> BT[],
624  const Expr *MtxExpr, CheckerKind CheckKind,
625  StringRef Desc) const {
626  ExplodedNode *N = C.generateErrorNode();
627  if (!N)
628  return;
629  initBugType(CheckKind);
630  auto Report =
631  std::make_unique<PathSensitiveBugReport>(*BT[CheckKind], Desc, N);
632  Report->addRange(MtxExpr->getSourceRange());
633  C.emitReport(std::move(Report));
634 }
635 
636 void PthreadLockChecker::checkDeadSymbols(SymbolReaper &SymReaper,
637  CheckerContext &C) const {
638  ProgramStateRef State = C.getState();
639 
640  for (auto I : State->get<DestroyRetVal>()) {
641  // Once the return value symbol dies, no more checks can be performed
642  // against it. See if the return value was checked before this point.
643  // This would remove the symbol from the map as well.
644  if (SymReaper.isDead(I.second))
645  State = resolvePossiblyDestroyedMutex(State, I.first, &I.second);
646  }
647 
648  for (auto I : State->get<LockMap>()) {
649  // Stop tracking dead mutex regions as well.
650  if (!SymReaper.isLiveRegion(I.first)) {
651  State = State->remove<LockMap>(I.first);
652  State = State->remove<DestroyRetVal>(I.first);
653  }
654  }
655 
656  // TODO: We probably need to clean up the lock stack as well.
657  // It is tricky though: even if the mutex cannot be unlocked anymore,
658  // it can still participate in lock order reversal resolution.
659 
660  C.addTransition(State);
661 }
662 
663 ProgramStateRef PthreadLockChecker::checkRegionChanges(
664  ProgramStateRef State, const InvalidatedSymbols *Symbols,
665  ArrayRef<const MemRegion *> ExplicitRegions,
666  ArrayRef<const MemRegion *> Regions, const LocationContext *LCtx,
667  const CallEvent *Call) const {
668 
669  bool IsLibraryFunction = false;
670  if (Call && Call->isGlobalCFunction()) {
671  // Avoid invalidating mutex state when a known supported function is called.
672  if (PThreadCallbacks.lookup(*Call) || FuchsiaCallbacks.lookup(*Call) ||
673  C11Callbacks.lookup(*Call))
674  return State;
675 
676  if (Call->isInSystemHeader())
677  IsLibraryFunction = true;
678  }
679 
680  for (auto R : Regions) {
681  // We assume that system library function wouldn't touch the mutex unless
682  // it takes the mutex explicitly as an argument.
683  // FIXME: This is a bit quadratic.
684  if (IsLibraryFunction && !llvm::is_contained(ExplicitRegions, R))
685  continue;
686 
687  State = State->remove<LockMap>(R);
688  State = State->remove<DestroyRetVal>(R);
689 
690  // TODO: We need to invalidate the lock stack as well. This is tricky
691  // to implement correctly and efficiently though, because the effects
692  // of mutex escapes on lock order may be fairly varied.
693  }
694 
695  return State;
696 }
697 
698 void ento::registerPthreadLockBase(CheckerManager &mgr) {
699  mgr.registerChecker<PthreadLockChecker>();
700 }
701 
702 bool ento::shouldRegisterPthreadLockBase(const CheckerManager &mgr) { return true; }
703 
704 #define REGISTER_CHECKER(name) \
705  void ento::register##name(CheckerManager &mgr) { \
706  PthreadLockChecker *checker = mgr.getChecker<PthreadLockChecker>(); \
707  checker->ChecksEnabled[PthreadLockChecker::CK_##name] = true; \
708  checker->CheckNames[PthreadLockChecker::CK_##name] = \
709  mgr.getCurrentCheckerName(); \
710  } \
711  \
712  bool ento::shouldRegister##name(const CheckerManager &mgr) { return true; }
713 
714 REGISTER_CHECKER(PthreadLockChecker)
715 REGISTER_CHECKER(FuchsiaLockChecker)
716 REGISTER_CHECKER(C11LockChecker)
clang::LocationContext
It wraps the AnalysisDeclContext to represent both the call stack with the help of StackFrameContext ...
Definition: AnalysisDeclContext.h:215
clang::Stmt::getSourceRange
SourceRange getSourceRange() const LLVM_READONLY
SourceLocation tokens are not useful in isolation - they are low level value objects created/interpre...
Definition: Stmt.cpp:324
clang::ento::ProgramStateRef
IntrusiveRefCntPtr< const ProgramState > ProgramStateRef
Definition: ProgramState_Fwd.h:37
AttributeLangSupport::C
@ C
Definition: SemaDeclAttr.cpp:54
REGISTER_CHECKER
#define REGISTER_CHECKER(name)
Definition: PthreadLockChecker.cpp:704
clang::ento::SymbolRef
const SymExpr * SymbolRef
Definition: SymExpr.h:110
clang::tooling::X
static ToolExecutorPluginRegistry::Add< AllTUsToolExecutorPlugin > X("all-TUs", "Runs FrontendActions on all TUs in the compilation database. " "Tool results are stored in memory.")
REGISTER_LIST_WITH_PROGRAMSTATE
#define REGISTER_LIST_WITH_PROGRAMSTATE(Name, Elem)
Declares an immutable list type NameTy, suitable for placement into the ProgramState.
Definition: ProgramStateTrait.h:132
clang::index::SymbolRole::Call
@ Call
CallEvent.h
REGISTER_MAP_WITH_PROGRAMSTATE
#define REGISTER_MAP_WITH_PROGRAMSTATE(Name, Key, Value)
Declares an immutable map of type NameTy, suitable for placement into the ProgramState.
Definition: ProgramStateTrait.h:84
BuiltinCheckerRegistration.h
CheckerManager.h
state
and static some checkers Checker The latter are built on top of the former via the Checker and CheckerVisitor and attempts to isolate them from much of the gore of the internal analysis the analyzer is basically a source code simulator that traces out possible paths of execution The state of the and the combination of state and program point is a node in an exploded which has the entry program point and initial state
Definition: README.txt:30
BugType.h
llvm::ArrayRef
Definition: LLVM.h:34
clang::syntax::NodeRole::Message
@ Message
State
LineState State
Definition: UnwrappedLineFormatter.cpp:986
CheckerContext.h
clang::ObjCPropertyAttribute::Kind
Kind
Definition: DeclObjCCommon.h:22
Checker.h
clang::Builtin::ID
ID
Definition: Builtins.h:48
clang
Definition: CalledOnceCheck.h:17
clang::Expr
This represents one expression.
Definition: Expr.h:109
clang::ento::InvalidatedSymbols
llvm::DenseSet< SymbolRef > InvalidatedSymbols
Definition: Store.h:51
clang::operator==
bool operator==(const CallGraphNode::CallRecord &LHS, const CallGraphNode::CallRecord &RHS)
Definition: CallGraph.h:207