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