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/CallEvent.h"
25#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
26
27using namespace clang;
28using namespace ento;
29
30namespace {
31
32struct LockState {
33  enum Kind {
34    Destroyed,
35    Locked,
36    Unlocked,
37    UntouchedAndPossiblyDestroyed,
38    UnlockedAndPossiblyDestroyed
39  } K;
40
41private:
42  LockState(Kind K) : K(K) {}
43
44public:
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
70class PthreadLockChecker : public Checker<check::PostCall, check::DeadSymbols,
71                                          check::RegionChanges> {
72public:
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
83private:
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
214public:
215  void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
216  void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const;
217  ProgramStateRef
218  checkRegionChanges(ProgramStateRef State, const InvalidatedSymbols *Symbols,
219                     ArrayRef<const MemRegion *> ExplicitRegions,
220                     ArrayRef<const MemRegion *> Regions,
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
225private:
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.
250REGISTER_LIST_WITH_PROGRAMSTATE(LockSet, const MemRegion *)
251
252// An entry for tracking lock states.
253REGISTER_MAP_WITH_PROGRAMSTATE(LockMap, const MemRegion *, LockState)
254
255// Return values for unresolved calls to pthread_mutex_destroy().
256REGISTER_MAP_WITH_PROGRAMSTATE(DestroyRetVal, const MemRegion *, SymbolRef)
257
258void 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.
287ProgramStateRef 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
312void 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
354void 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
361void 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
368void 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
375void 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
381void 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
388void 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
394void 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
467void 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
473void 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
519void 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
526void 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
533void 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
587void PthreadLockChecker::InitAnyLock(const CallEvent &Call, CheckerContext &C,
588                                     CheckerKind CheckKind) const {
589  InitLockAux(Call, C, Call.getArgExpr(0), Call.getArgSVal(0), CheckKind);
590}
591
592void 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
622void 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
636void 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
663ProgramStateRef 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 &&
685        std::find(ExplicitRegions.begin(), ExplicitRegions.end(), R) ==
686            ExplicitRegions.end())
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