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->isUntouchedAndPossiblyDestroyed() ||
295         lstate->isUnlockedAndPossiblyDestroyed());
296
297  ConstraintManager &CMgr = state->getConstraintManager();
298  ConditionTruthVal retZero = CMgr.isNull(state, *sym);
299  if (retZero.isConstrainedFalse()) {
300    if (lstate->isUntouchedAndPossiblyDestroyed())
301      state = state->remove<LockMap>(lockR);
302    else if (lstate->isUnlockedAndPossiblyDestroyed())
303      state = state->set<LockMap>(lockR, LockState::getUnlocked());
304  } else
305    state = state->set<LockMap>(lockR, LockState::getDestroyed());
306
307  // Removing the map entry (lockR, sym) from DestroyRetVal as the lock state is
308  // now resolved.
309  state = state->remove<DestroyRetVal>(lockR);
310  return state;
311}
312
313void PthreadLockChecker::printState(raw_ostream &Out, ProgramStateRef State,
314                                    const char *NL, const char *Sep) const {
315  LockMapTy LM = State->get<LockMap>();
316  if (!LM.isEmpty()) {
317    Out << Sep << "Mutex states:" << NL;
318    for (auto I : LM) {
319      I.first->dumpToStream(Out);
320      if (I.second.isLocked())
321        Out << ": locked";
322      else if (I.second.isUnlocked())
323        Out << ": unlocked";
324      else if (I.second.isDestroyed())
325        Out << ": destroyed";
326      else if (I.second.isUntouchedAndPossiblyDestroyed())
327        Out << ": not tracked, possibly destroyed";
328      else if (I.second.isUnlockedAndPossiblyDestroyed())
329        Out << ": unlocked, possibly destroyed";
330      Out << NL;
331    }
332  }
333
334  LockSetTy LS = State->get<LockSet>();
335  if (!LS.isEmpty()) {
336    Out << Sep << "Mutex lock order:" << NL;
337    for (auto I : LS) {
338      I->dumpToStream(Out);
339      Out << NL;
340    }
341  }
342
343  DestroyRetValTy DRV = State->get<DestroyRetVal>();
344  if (!DRV.isEmpty()) {
345    Out << Sep << "Mutexes in unresolved possibly destroyed state:" << NL;
346    for (auto I : DRV) {
347      I.first->dumpToStream(Out);
348      Out << ": ";
349      I.second->dumpToStream(Out);
350      Out << NL;
351    }
352  }
353}
354
355void PthreadLockChecker::AcquirePthreadLock(const CallEvent &Call,
356                                            CheckerContext &C,
357                                            CheckerKind CheckKind) const {
358  AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), false,
359                 PthreadSemantics, CheckKind);
360}
361
362void PthreadLockChecker::AcquireXNULock(const CallEvent &Call,
363                                        CheckerContext &C,
364                                        CheckerKind CheckKind) const {
365  AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), false,
366                 XNUSemantics, CheckKind);
367}
368
369void PthreadLockChecker::TryPthreadLock(const CallEvent &Call,
370                                        CheckerContext &C,
371                                        CheckerKind CheckKind) const {
372  AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true,
373                 PthreadSemantics, CheckKind);
374}
375
376void PthreadLockChecker::TryXNULock(const CallEvent &Call, CheckerContext &C,
377                                    CheckerKind CheckKind) const {
378  AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true,
379                 PthreadSemantics, CheckKind);
380}
381
382void PthreadLockChecker::TryFuchsiaLock(const CallEvent &Call,
383                                        CheckerContext &C,
384                                        CheckerKind CheckKind) const {
385  AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true,
386                 PthreadSemantics, CheckKind);
387}
388
389void PthreadLockChecker::TryC11Lock(const CallEvent &Call, CheckerContext &C,
390                                    CheckerKind CheckKind) const {
391  AcquireLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), true,
392                 PthreadSemantics, CheckKind);
393}
394
395void PthreadLockChecker::AcquireLockAux(const CallEvent &Call,
396                                        CheckerContext &C, const Expr *MtxExpr,
397                                        SVal MtxVal, bool IsTryLock,
398                                        enum LockingSemantics Semantics,
399                                        CheckerKind CheckKind) const {
400  if (!ChecksEnabled[CheckKind])
401    return;
402
403  const MemRegion *lockR = MtxVal.getAsRegion();
404  if (!lockR)
405    return;
406
407  ProgramStateRef state = C.getState();
408  const SymbolRef *sym = state->get<DestroyRetVal>(lockR);
409  if (sym)
410    state = resolvePossiblyDestroyedMutex(state, lockR, sym);
411
412  if (const LockState *LState = state->get<LockMap>(lockR)) {
413    if (LState->isLocked()) {
414      reportBug(C, BT_doublelock, MtxExpr, CheckKind,
415                "This lock has already been acquired");
416      return;
417    } else if (LState->isDestroyed()) {
418      reportBug(C, BT_destroylock, MtxExpr, CheckKind,
419                "This lock has already been destroyed");
420      return;
421    }
422  }
423
424  ProgramStateRef lockSucc = state;
425  if (IsTryLock) {
426    // Bifurcate the state, and allow a mode where the lock acquisition fails.
427    SVal RetVal = Call.getReturnValue();
428    if (auto DefinedRetVal = RetVal.getAs<DefinedSVal>()) {
429      ProgramStateRef lockFail;
430      switch (Semantics) {
431      case PthreadSemantics:
432        std::tie(lockFail, lockSucc) = state->assume(*DefinedRetVal);
433        break;
434      case XNUSemantics:
435        std::tie(lockSucc, lockFail) = state->assume(*DefinedRetVal);
436        break;
437      default:
438        llvm_unreachable("Unknown tryLock locking semantics");
439      }
440      assert(lockFail && lockSucc);
441      C.addTransition(lockFail);
442    }
443    // We might want to handle the case when the mutex lock function was inlined
444    // and returned an Unknown or Undefined value.
445  } else if (Semantics == PthreadSemantics) {
446    // Assume that the return value was 0.
447    SVal RetVal = Call.getReturnValue();
448    if (auto DefinedRetVal = RetVal.getAs<DefinedSVal>()) {
449      // FIXME: If the lock function was inlined and returned true,
450      // we need to behave sanely - at least generate sink.
451      lockSucc = state->assume(*DefinedRetVal, false);
452      assert(lockSucc);
453    }
454    // We might want to handle the case when the mutex lock function was inlined
455    // and returned an Unknown or Undefined value.
456  } else {
457    // XNU locking semantics return void on non-try locks
458    assert((Semantics == XNUSemantics) && "Unknown locking semantics");
459    lockSucc = state;
460  }
461
462  // Record that the lock was acquired.
463  lockSucc = lockSucc->add<LockSet>(lockR);
464  lockSucc = lockSucc->set<LockMap>(lockR, LockState::getLocked());
465  C.addTransition(lockSucc);
466}
467
468void PthreadLockChecker::ReleaseAnyLock(const CallEvent &Call,
469                                        CheckerContext &C,
470                                        CheckerKind CheckKind) const {
471  ReleaseLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), CheckKind);
472}
473
474void PthreadLockChecker::ReleaseLockAux(const CallEvent &Call,
475                                        CheckerContext &C, const Expr *MtxExpr,
476                                        SVal MtxVal,
477                                        CheckerKind CheckKind) const {
478  if (!ChecksEnabled[CheckKind])
479    return;
480
481  const MemRegion *lockR = MtxVal.getAsRegion();
482  if (!lockR)
483    return;
484
485  ProgramStateRef state = C.getState();
486  const SymbolRef *sym = state->get<DestroyRetVal>(lockR);
487  if (sym)
488    state = resolvePossiblyDestroyedMutex(state, lockR, sym);
489
490  if (const LockState *LState = state->get<LockMap>(lockR)) {
491    if (LState->isUnlocked()) {
492      reportBug(C, BT_doubleunlock, MtxExpr, CheckKind,
493                "This lock has already been unlocked");
494      return;
495    } else if (LState->isDestroyed()) {
496      reportBug(C, BT_destroylock, MtxExpr, CheckKind,
497                "This lock has already been destroyed");
498      return;
499    }
500  }
501
502  LockSetTy LS = state->get<LockSet>();
503
504  if (!LS.isEmpty()) {
505    const MemRegion *firstLockR = LS.getHead();
506    if (firstLockR != lockR) {
507      reportBug(C, BT_lor, MtxExpr, CheckKind,
508                "This was not the most recently acquired lock. Possible lock "
509                "order reversal");
510      return;
511    }
512    // Record that the lock was released.
513    state = state->set<LockSet>(LS.getTail());
514  }
515
516  state = state->set<LockMap>(lockR, LockState::getUnlocked());
517  C.addTransition(state);
518}
519
520void PthreadLockChecker::DestroyPthreadLock(const CallEvent &Call,
521                                            CheckerContext &C,
522                                            CheckerKind CheckKind) const {
523  DestroyLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0),
524                 PthreadSemantics, CheckKind);
525}
526
527void PthreadLockChecker::DestroyXNULock(const CallEvent &Call,
528                                        CheckerContext &C,
529                                        CheckerKind CheckKind) const {
530  DestroyLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), XNUSemantics,
531                 CheckKind);
532}
533
534void PthreadLockChecker::DestroyLockAux(const CallEvent &Call,
535                                        CheckerContext &C, const Expr *MtxExpr,
536                                        SVal MtxVal,
537                                        enum LockingSemantics Semantics,
538                                        CheckerKind CheckKind) const {
539  if (!ChecksEnabled[CheckKind])
540    return;
541
542  const MemRegion *LockR = MtxVal.getAsRegion();
543  if (!LockR)
544    return;
545
546  ProgramStateRef State = C.getState();
547
548  const SymbolRef *sym = State->get<DestroyRetVal>(LockR);
549  if (sym)
550    State = resolvePossiblyDestroyedMutex(State, LockR, sym);
551
552  const LockState *LState = State->get<LockMap>(LockR);
553  // Checking the return value of the destroy method only in the case of
554  // PthreadSemantics
555  if (Semantics == PthreadSemantics) {
556    if (!LState || LState->isUnlocked()) {
557      SymbolRef sym = Call.getReturnValue().getAsSymbol();
558      if (!sym) {
559        State = State->remove<LockMap>(LockR);
560        C.addTransition(State);
561        return;
562      }
563      State = State->set<DestroyRetVal>(LockR, sym);
564      if (LState && LState->isUnlocked())
565        State = State->set<LockMap>(
566            LockR, LockState::getUnlockedAndPossiblyDestroyed());
567      else
568        State = State->set<LockMap>(
569            LockR, LockState::getUntouchedAndPossiblyDestroyed());
570      C.addTransition(State);
571      return;
572    }
573  } else {
574    if (!LState || LState->isUnlocked()) {
575      State = State->set<LockMap>(LockR, LockState::getDestroyed());
576      C.addTransition(State);
577      return;
578    }
579  }
580
581  StringRef Message = LState->isLocked()
582                          ? "This lock is still locked"
583                          : "This lock has already been destroyed";
584
585  reportBug(C, BT_destroylock, MtxExpr, CheckKind, Message);
586}
587
588void PthreadLockChecker::InitAnyLock(const CallEvent &Call, CheckerContext &C,
589                                     CheckerKind CheckKind) const {
590  InitLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), CheckKind);
591}
592
593void PthreadLockChecker::InitLockAux(const CallEvent &Call, CheckerContext &C,
594                                     const Expr *MtxExpr, SVal MtxVal,
595                                     CheckerKind CheckKind) const {
596  if (!ChecksEnabled[CheckKind])
597    return;
598
599  const MemRegion *LockR = MtxVal.getAsRegion();
600  if (!LockR)
601    return;
602
603  ProgramStateRef State = C.getState();
604
605  const SymbolRef *sym = State->get<DestroyRetVal>(LockR);
606  if (sym)
607    State = resolvePossiblyDestroyedMutex(State, LockR, sym);
608
609  const struct LockState *LState = State->get<LockMap>(LockR);
610  if (!LState || LState->isDestroyed()) {
611    State = State->set<LockMap>(LockR, LockState::getUnlocked());
612    C.addTransition(State);
613    return;
614  }
615
616  StringRef Message = LState->isLocked()
617                          ? "This lock is still being held"
618                          : "This lock has already been initialized";
619
620  reportBug(C, BT_initlock, MtxExpr, CheckKind, Message);
621}
622
623void PthreadLockChecker::reportBug(CheckerContext &C,
624                                   std::unique_ptr<BugType> BT[],
625                                   const Expr *MtxExpr, CheckerKind CheckKind,
626                                   StringRef Desc) const {
627  ExplodedNode *N = C.generateErrorNode();
628  if (!N)
629    return;
630  initBugType(CheckKind);
631  auto Report =
632      std::make_unique<PathSensitiveBugReport>(*BT[CheckKind], Desc, N);
633  Report->addRange(MtxExpr->getSourceRange());
634  C.emitReport(std::move(Report));
635}
636
637void PthreadLockChecker::checkDeadSymbols(SymbolReaper &SymReaper,
638                                          CheckerContext &C) const {
639  ProgramStateRef State = C.getState();
640
641  for (auto I : State->get<DestroyRetVal>()) {
642    // Once the return value symbol dies, no more checks can be performed
643    // against it. See if the return value was checked before this point.
644    // This would remove the symbol from the map as well.
645    if (SymReaper.isDead(I.second))
646      State = resolvePossiblyDestroyedMutex(State, I.first, &I.second);
647  }
648
649  for (auto I : State->get<LockMap>()) {
650    // Stop tracking dead mutex regions as well.
651    if (!SymReaper.isLiveRegion(I.first)) {
652      State = State->remove<LockMap>(I.first);
653      State = State->remove<DestroyRetVal>(I.first);
654    }
655  }
656
657  // TODO: We probably need to clean up the lock stack as well.
658  // It is tricky though: even if the mutex cannot be unlocked anymore,
659  // it can still participate in lock order reversal resolution.
660
661  C.addTransition(State);
662}
663
664ProgramStateRef PthreadLockChecker::checkRegionChanges(
665    ProgramStateRef State, const InvalidatedSymbols *Symbols,
666    ArrayRef<const MemRegion *> ExplicitRegions,
667    ArrayRef<const MemRegion *> Regions, const LocationContext *LCtx,
668    const CallEvent *Call) const {
669
670  bool IsLibraryFunction = false;
671  if (Call && Call->isGlobalCFunction()) {
672    // Avoid invalidating mutex state when a known supported function is called.
673    if (PThreadCallbacks.lookup(*Call) || FuchsiaCallbacks.lookup(*Call) ||
674        C11Callbacks.lookup(*Call))
675      return State;
676
677    if (Call->isInSystemHeader())
678      IsLibraryFunction = true;
679  }
680
681  for (auto R : Regions) {
682    // We assume that system library function wouldn't touch the mutex unless
683    // it takes the mutex explicitly as an argument.
684    // FIXME: This is a bit quadratic.
685    if (IsLibraryFunction && !llvm::is_contained(ExplicitRegions, R))
686      continue;
687
688    State = State->remove<LockMap>(R);
689    State = State->remove<DestroyRetVal>(R);
690
691    // TODO: We need to invalidate the lock stack as well. This is tricky
692    // to implement correctly and efficiently though, because the effects
693    // of mutex escapes on lock order may be fairly varied.
694  }
695
696  return State;
697}
698
699void ento::registerPthreadLockBase(CheckerManager &mgr) {
700  mgr.registerChecker<PthreadLockChecker>();
701}
702
703bool ento::shouldRegisterPthreadLockBase(const CheckerManager &mgr) { return true; }
704
705#define REGISTER_CHECKER(name)                                                 \
706  void ento::register##name(CheckerManager &mgr) {                             \
707    PthreadLockChecker *checker = mgr.getChecker<PthreadLockChecker>();        \
708    checker->ChecksEnabled[PthreadLockChecker::CK_##name] = true;              \
709    checker->CheckNames[PthreadLockChecker::CK_##name] =                       \
710        mgr.getCurrentCheckerName();                                           \
711  }                                                                            \
712                                                                               \
713  bool ento::shouldRegister##name(const CheckerManager &mgr) { return true; }
714
715REGISTER_CHECKER(PthreadLockChecker)
716REGISTER_CHECKER(FuchsiaLockChecker)
717REGISTER_CHECKER(C11LockChecker)
718