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 reportUseDestroyedBug(const CallEvent &Call, CheckerContext &C,
171                             unsigned ArgNo, CheckerKind checkKind) const;
172
173  // Init.
174  void InitAnyLock(const CallEvent &Call, CheckerContext &C,
175                   CheckerKind checkkind) const;
176  void InitLockAux(const CallEvent &Call, CheckerContext &C, unsigned ArgNo,
177                   SVal Lock, CheckerKind checkkind) const;
178
179  // Lock, Try-lock.
180  void AcquirePthreadLock(const CallEvent &Call, CheckerContext &C,
181                          CheckerKind checkkind) const;
182  void AcquireXNULock(const CallEvent &Call, CheckerContext &C,
183                      CheckerKind checkkind) const;
184  void TryPthreadLock(const CallEvent &Call, CheckerContext &C,
185                      CheckerKind checkkind) const;
186  void TryXNULock(const CallEvent &Call, CheckerContext &C,
187                  CheckerKind checkkind) const;
188  void TryFuchsiaLock(const CallEvent &Call, CheckerContext &C,
189                      CheckerKind checkkind) const;
190  void TryC11Lock(const CallEvent &Call, CheckerContext &C,
191                  CheckerKind checkkind) const;
192  void AcquireLockAux(const CallEvent &Call, CheckerContext &C, unsigned ArgNo,
193                      SVal lock, bool isTryLock, LockingSemantics semantics,
194                      CheckerKind checkkind) const;
195
196  // Release.
197  void ReleaseAnyLock(const CallEvent &Call, CheckerContext &C,
198                      CheckerKind checkkind) const;
199  void ReleaseLockAux(const CallEvent &Call, CheckerContext &C, unsigned ArgNo,
200                      SVal lock, CheckerKind checkkind) const;
201
202  // Destroy.
203  void DestroyPthreadLock(const CallEvent &Call, CheckerContext &C,
204                          CheckerKind checkkind) const;
205  void DestroyXNULock(const CallEvent &Call, CheckerContext &C,
206                      CheckerKind checkkind) const;
207  void DestroyLockAux(const CallEvent &Call, CheckerContext &C, unsigned ArgNo,
208                      SVal Lock, LockingSemantics semantics,
209                      CheckerKind checkkind) const;
210
211public:
212  void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
213  void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const;
214  ProgramStateRef
215  checkRegionChanges(ProgramStateRef State, const InvalidatedSymbols *Symbols,
216                     ArrayRef<const MemRegion *> ExplicitRegions,
217                     ArrayRef<const MemRegion *> Regions,
218                     const LocationContext *LCtx, const CallEvent *Call) const;
219  void printState(raw_ostream &Out, ProgramStateRef State, const char *NL,
220                  const char *Sep) const override;
221
222private:
223  mutable std::unique_ptr<BugType> BT_doublelock[CK_NumCheckKinds];
224  mutable std::unique_ptr<BugType> BT_doubleunlock[CK_NumCheckKinds];
225  mutable std::unique_ptr<BugType> BT_destroylock[CK_NumCheckKinds];
226  mutable std::unique_ptr<BugType> BT_initlock[CK_NumCheckKinds];
227  mutable std::unique_ptr<BugType> BT_lor[CK_NumCheckKinds];
228
229  void initBugType(CheckerKind checkKind) const {
230    if (BT_doublelock[checkKind])
231      return;
232    BT_doublelock[checkKind].reset(
233        new BugType{CheckNames[checkKind], "Double locking", "Lock checker"});
234    BT_doubleunlock[checkKind].reset(
235        new BugType{CheckNames[checkKind], "Double unlocking", "Lock checker"});
236    BT_destroylock[checkKind].reset(new BugType{
237        CheckNames[checkKind], "Use destroyed lock", "Lock checker"});
238    BT_initlock[checkKind].reset(new BugType{
239        CheckNames[checkKind], "Init invalid lock", "Lock checker"});
240    BT_lor[checkKind].reset(new BugType{CheckNames[checkKind],
241                                        "Lock order reversal", "Lock checker"});
242  }
243};
244} // end anonymous namespace
245
246// A stack of locks for tracking lock-unlock order.
247REGISTER_LIST_WITH_PROGRAMSTATE(LockSet, const MemRegion *)
248
249// An entry for tracking lock states.
250REGISTER_MAP_WITH_PROGRAMSTATE(LockMap, const MemRegion *, LockState)
251
252// Return values for unresolved calls to pthread_mutex_destroy().
253REGISTER_MAP_WITH_PROGRAMSTATE(DestroyRetVal, const MemRegion *, SymbolRef)
254
255void PthreadLockChecker::checkPostCall(const CallEvent &Call,
256                                       CheckerContext &C) const {
257  // An additional umbrella check that all functions modeled by this checker
258  // are global C functions.
259  // TODO: Maybe make this the default behavior of CallDescription
260  // with exactly one identifier?
261  // FIXME: Try to handle cases when the implementation was inlined rather
262  // than just giving up.
263  if (!Call.isGlobalCFunction() || C.wasInlined)
264    return;
265
266  if (const FnCheck *Callback = PThreadCallbacks.lookup(Call))
267    (this->**Callback)(Call, C, CK_PthreadLockChecker);
268  else if (const FnCheck *Callback = FuchsiaCallbacks.lookup(Call))
269    (this->**Callback)(Call, C, CK_FuchsiaLockChecker);
270  else if (const FnCheck *Callback = C11Callbacks.lookup(Call))
271    (this->**Callback)(Call, C, CK_C11LockChecker);
272}
273
274// When a lock is destroyed, in some semantics(like PthreadSemantics) we are not
275// sure if the destroy call has succeeded or failed, and the lock enters one of
276// the 'possibly destroyed' state. There is a short time frame for the
277// programmer to check the return value to see if the lock was successfully
278// destroyed. Before we model the next operation over that lock, we call this
279// function to see if the return value was checked by now and set the lock state
280// - either to destroyed state or back to its previous state.
281
282// In PthreadSemantics, pthread_mutex_destroy() returns zero if the lock is
283// successfully destroyed and it returns a non-zero value otherwise.
284ProgramStateRef PthreadLockChecker::resolvePossiblyDestroyedMutex(
285    ProgramStateRef state, const MemRegion *lockR, const SymbolRef *sym) const {
286  const LockState *lstate = state->get<LockMap>(lockR);
287  // Existence in DestroyRetVal ensures existence in LockMap.
288  // Existence in Destroyed also ensures that the lock state for lockR is either
289  // UntouchedAndPossiblyDestroyed or UnlockedAndPossiblyDestroyed.
290  assert(lstate->isUntouchedAndPossiblyDestroyed() ||
291         lstate->isUnlockedAndPossiblyDestroyed());
292
293  ConstraintManager &CMgr = state->getConstraintManager();
294  ConditionTruthVal retZero = CMgr.isNull(state, *sym);
295  if (retZero.isConstrainedFalse()) {
296    if (lstate->isUntouchedAndPossiblyDestroyed())
297      state = state->remove<LockMap>(lockR);
298    else if (lstate->isUnlockedAndPossiblyDestroyed())
299      state = state->set<LockMap>(lockR, LockState::getUnlocked());
300  } else
301    state = state->set<LockMap>(lockR, LockState::getDestroyed());
302
303  // Removing the map entry (lockR, sym) from DestroyRetVal as the lock state is
304  // now resolved.
305  state = state->remove<DestroyRetVal>(lockR);
306  return state;
307}
308
309void PthreadLockChecker::printState(raw_ostream &Out, ProgramStateRef State,
310                                    const char *NL, const char *Sep) const {
311  LockMapTy LM = State->get<LockMap>();
312  if (!LM.isEmpty()) {
313    Out << Sep << "Mutex states:" << NL;
314    for (auto I : LM) {
315      I.first->dumpToStream(Out);
316      if (I.second.isLocked())
317        Out << ": locked";
318      else if (I.second.isUnlocked())
319        Out << ": unlocked";
320      else if (I.second.isDestroyed())
321        Out << ": destroyed";
322      else if (I.second.isUntouchedAndPossiblyDestroyed())
323        Out << ": not tracked, possibly destroyed";
324      else if (I.second.isUnlockedAndPossiblyDestroyed())
325        Out << ": unlocked, possibly destroyed";
326      Out << NL;
327    }
328  }
329
330  LockSetTy LS = State->get<LockSet>();
331  if (!LS.isEmpty()) {
332    Out << Sep << "Mutex lock order:" << NL;
333    for (auto I : LS) {
334      I->dumpToStream(Out);
335      Out << NL;
336    }
337  }
338
339  // TODO: Dump destroyed mutex symbols?
340}
341
342void PthreadLockChecker::AcquirePthreadLock(const CallEvent &Call,
343                                            CheckerContext &C,
344                                            CheckerKind checkKind) const {
345  AcquireLockAux(Call, C, 0, Call.getArgSVal(0), false, PthreadSemantics,
346                 checkKind);
347}
348
349void PthreadLockChecker::AcquireXNULock(const CallEvent &Call,
350                                        CheckerContext &C,
351                                        CheckerKind checkKind) const {
352  AcquireLockAux(Call, C, 0, Call.getArgSVal(0), false, XNUSemantics,
353                 checkKind);
354}
355
356void PthreadLockChecker::TryPthreadLock(const CallEvent &Call,
357                                        CheckerContext &C,
358                                        CheckerKind checkKind) const {
359  AcquireLockAux(Call, C, 0, Call.getArgSVal(0), true, PthreadSemantics,
360                 checkKind);
361}
362
363void PthreadLockChecker::TryXNULock(const CallEvent &Call, CheckerContext &C,
364                                    CheckerKind checkKind) const {
365  AcquireLockAux(Call, C, 0, Call.getArgSVal(0), true, PthreadSemantics,
366                 checkKind);
367}
368
369void PthreadLockChecker::TryFuchsiaLock(const CallEvent &Call,
370                                        CheckerContext &C,
371                                        CheckerKind checkKind) const {
372  AcquireLockAux(Call, C, 0, Call.getArgSVal(0), true, PthreadSemantics,
373                 checkKind);
374}
375
376void PthreadLockChecker::TryC11Lock(const CallEvent &Call, CheckerContext &C,
377                                    CheckerKind checkKind) const {
378  AcquireLockAux(Call, C, 0, Call.getArgSVal(0), true, PthreadSemantics,
379                 checkKind);
380}
381
382void PthreadLockChecker::AcquireLockAux(const CallEvent &Call,
383                                        CheckerContext &C, unsigned ArgNo,
384                                        SVal lock, bool isTryLock,
385                                        enum LockingSemantics semantics,
386                                        CheckerKind checkKind) const {
387  if (!ChecksEnabled[checkKind])
388    return;
389
390  const MemRegion *lockR = lock.getAsRegion();
391  if (!lockR)
392    return;
393
394  ProgramStateRef state = C.getState();
395  const SymbolRef *sym = state->get<DestroyRetVal>(lockR);
396  if (sym)
397    state = resolvePossiblyDestroyedMutex(state, lockR, sym);
398
399  if (const LockState *LState = state->get<LockMap>(lockR)) {
400    if (LState->isLocked()) {
401      ExplodedNode *N = C.generateErrorNode();
402      if (!N)
403        return;
404      initBugType(checkKind);
405      auto report = std::make_unique<PathSensitiveBugReport>(
406          *BT_doublelock[checkKind], "This lock has already been acquired", N);
407      report->addRange(Call.getArgExpr(ArgNo)->getSourceRange());
408      C.emitReport(std::move(report));
409      return;
410    } else if (LState->isDestroyed()) {
411      reportUseDestroyedBug(Call, C, ArgNo, checkKind);
412      return;
413    }
414  }
415
416  ProgramStateRef lockSucc = state;
417  if (isTryLock) {
418    // Bifurcate the state, and allow a mode where the lock acquisition fails.
419    SVal RetVal = Call.getReturnValue();
420    if (auto DefinedRetVal = RetVal.getAs<DefinedSVal>()) {
421      ProgramStateRef lockFail;
422      switch (semantics) {
423      case PthreadSemantics:
424        std::tie(lockFail, lockSucc) = state->assume(*DefinedRetVal);
425        break;
426      case XNUSemantics:
427        std::tie(lockSucc, lockFail) = state->assume(*DefinedRetVal);
428        break;
429      default:
430        llvm_unreachable("Unknown tryLock locking semantics");
431      }
432      assert(lockFail && lockSucc);
433      C.addTransition(lockFail);
434    }
435    // We might want to handle the case when the mutex lock function was inlined
436    // and returned an Unknown or Undefined value.
437  } else if (semantics == PthreadSemantics) {
438    // Assume that the return value was 0.
439    SVal RetVal = Call.getReturnValue();
440    if (auto DefinedRetVal = RetVal.getAs<DefinedSVal>()) {
441      // FIXME: If the lock function was inlined and returned true,
442      // we need to behave sanely - at least generate sink.
443      lockSucc = state->assume(*DefinedRetVal, false);
444      assert(lockSucc);
445    }
446    // We might want to handle the case when the mutex lock function was inlined
447    // and returned an Unknown or Undefined value.
448  } else {
449    // XNU locking semantics return void on non-try locks
450    assert((semantics == XNUSemantics) && "Unknown locking semantics");
451    lockSucc = state;
452  }
453
454  // Record that the lock was acquired.
455  lockSucc = lockSucc->add<LockSet>(lockR);
456  lockSucc = lockSucc->set<LockMap>(lockR, LockState::getLocked());
457  C.addTransition(lockSucc);
458}
459
460void PthreadLockChecker::ReleaseAnyLock(const CallEvent &Call,
461                                        CheckerContext &C,
462                                        CheckerKind checkKind) const {
463  ReleaseLockAux(Call, C, 0, Call.getArgSVal(0), checkKind);
464}
465
466void PthreadLockChecker::ReleaseLockAux(const CallEvent &Call,
467                                        CheckerContext &C, unsigned ArgNo,
468                                        SVal lock,
469                                        CheckerKind checkKind) const {
470  if (!ChecksEnabled[checkKind])
471    return;
472
473  const MemRegion *lockR = lock.getAsRegion();
474  if (!lockR)
475    return;
476
477  ProgramStateRef state = C.getState();
478  const SymbolRef *sym = state->get<DestroyRetVal>(lockR);
479  if (sym)
480    state = resolvePossiblyDestroyedMutex(state, lockR, sym);
481
482  if (const LockState *LState = state->get<LockMap>(lockR)) {
483    if (LState->isUnlocked()) {
484      ExplodedNode *N = C.generateErrorNode();
485      if (!N)
486        return;
487      initBugType(checkKind);
488      auto Report = std::make_unique<PathSensitiveBugReport>(
489          *BT_doubleunlock[checkKind], "This lock has already been unlocked",
490          N);
491      Report->addRange(Call.getArgExpr(ArgNo)->getSourceRange());
492      C.emitReport(std::move(Report));
493      return;
494    } else if (LState->isDestroyed()) {
495      reportUseDestroyedBug(Call, C, ArgNo, checkKind);
496      return;
497    }
498  }
499
500  LockSetTy LS = state->get<LockSet>();
501
502  if (!LS.isEmpty()) {
503    const MemRegion *firstLockR = LS.getHead();
504    if (firstLockR != lockR) {
505      ExplodedNode *N = C.generateErrorNode();
506      if (!N)
507        return;
508      initBugType(checkKind);
509      auto report = std::make_unique<PathSensitiveBugReport>(
510          *BT_lor[checkKind],
511          "This was not the most recently acquired lock. Possible "
512          "lock order reversal",
513          N);
514      report->addRange(Call.getArgExpr(ArgNo)->getSourceRange());
515      C.emitReport(std::move(report));
516      return;
517    }
518    // Record that the lock was released.
519    state = state->set<LockSet>(LS.getTail());
520  }
521
522  state = state->set<LockMap>(lockR, LockState::getUnlocked());
523  C.addTransition(state);
524}
525
526void PthreadLockChecker::DestroyPthreadLock(const CallEvent &Call,
527                                            CheckerContext &C,
528                                            CheckerKind checkKind) const {
529  DestroyLockAux(Call, C, 0, Call.getArgSVal(0), PthreadSemantics, checkKind);
530}
531
532void PthreadLockChecker::DestroyXNULock(const CallEvent &Call,
533                                        CheckerContext &C,
534                                        CheckerKind checkKind) const {
535  DestroyLockAux(Call, C, 0, Call.getArgSVal(0), XNUSemantics, checkKind);
536}
537
538void PthreadLockChecker::DestroyLockAux(const CallEvent &Call,
539                                        CheckerContext &C, unsigned ArgNo,
540                                        SVal Lock,
541                                        enum LockingSemantics semantics,
542                                        CheckerKind checkKind) const {
543  if (!ChecksEnabled[checkKind])
544    return;
545
546  const MemRegion *LockR = Lock.getAsRegion();
547  if (!LockR)
548    return;
549
550  ProgramStateRef State = C.getState();
551
552  const SymbolRef *sym = State->get<DestroyRetVal>(LockR);
553  if (sym)
554    State = resolvePossiblyDestroyedMutex(State, LockR, sym);
555
556  const LockState *LState = State->get<LockMap>(LockR);
557  // Checking the return value of the destroy method only in the case of
558  // PthreadSemantics
559  if (semantics == PthreadSemantics) {
560    if (!LState || LState->isUnlocked()) {
561      SymbolRef sym = Call.getReturnValue().getAsSymbol();
562      if (!sym) {
563        State = State->remove<LockMap>(LockR);
564        C.addTransition(State);
565        return;
566      }
567      State = State->set<DestroyRetVal>(LockR, sym);
568      if (LState && LState->isUnlocked())
569        State = State->set<LockMap>(
570            LockR, LockState::getUnlockedAndPossiblyDestroyed());
571      else
572        State = State->set<LockMap>(
573            LockR, LockState::getUntouchedAndPossiblyDestroyed());
574      C.addTransition(State);
575      return;
576    }
577  } else {
578    if (!LState || LState->isUnlocked()) {
579      State = State->set<LockMap>(LockR, LockState::getDestroyed());
580      C.addTransition(State);
581      return;
582    }
583  }
584  StringRef Message;
585
586  if (LState->isLocked()) {
587    Message = "This lock is still locked";
588  } else {
589    Message = "This lock has already been destroyed";
590  }
591
592  ExplodedNode *N = C.generateErrorNode();
593  if (!N)
594    return;
595  initBugType(checkKind);
596  auto Report = std::make_unique<PathSensitiveBugReport>(
597      *BT_destroylock[checkKind], Message, N);
598  Report->addRange(Call.getArgExpr(ArgNo)->getSourceRange());
599  C.emitReport(std::move(Report));
600}
601
602void PthreadLockChecker::InitAnyLock(const CallEvent &Call, CheckerContext &C,
603                                     CheckerKind checkKind) const {
604  InitLockAux(Call, C, 0, Call.getArgSVal(0), checkKind);
605}
606
607void PthreadLockChecker::InitLockAux(const CallEvent &Call, CheckerContext &C,
608                                     unsigned ArgNo, SVal Lock,
609                                     CheckerKind checkKind) const {
610  if (!ChecksEnabled[checkKind])
611    return;
612
613  const MemRegion *LockR = Lock.getAsRegion();
614  if (!LockR)
615    return;
616
617  ProgramStateRef State = C.getState();
618
619  const SymbolRef *sym = State->get<DestroyRetVal>(LockR);
620  if (sym)
621    State = resolvePossiblyDestroyedMutex(State, LockR, sym);
622
623  const struct LockState *LState = State->get<LockMap>(LockR);
624  if (!LState || LState->isDestroyed()) {
625    State = State->set<LockMap>(LockR, LockState::getUnlocked());
626    C.addTransition(State);
627    return;
628  }
629
630  StringRef Message;
631
632  if (LState->isLocked()) {
633    Message = "This lock is still being held";
634  } else {
635    Message = "This lock has already been initialized";
636  }
637
638  ExplodedNode *N = C.generateErrorNode();
639  if (!N)
640    return;
641  initBugType(checkKind);
642  auto Report = std::make_unique<PathSensitiveBugReport>(
643      *BT_initlock[checkKind], Message, N);
644  Report->addRange(Call.getArgExpr(ArgNo)->getSourceRange());
645  C.emitReport(std::move(Report));
646}
647
648void PthreadLockChecker::reportUseDestroyedBug(const CallEvent &Call,
649                                               CheckerContext &C,
650                                               unsigned ArgNo,
651                                               CheckerKind checkKind) const {
652  ExplodedNode *N = C.generateErrorNode();
653  if (!N)
654    return;
655  initBugType(checkKind);
656  auto Report = std::make_unique<PathSensitiveBugReport>(
657      *BT_destroylock[checkKind], "This lock has already been destroyed", N);
658  Report->addRange(Call.getArgExpr(ArgNo)->getSourceRange());
659  C.emitReport(std::move(Report));
660}
661
662void PthreadLockChecker::checkDeadSymbols(SymbolReaper &SymReaper,
663                                          CheckerContext &C) const {
664  ProgramStateRef State = C.getState();
665
666  for (auto I : State->get<DestroyRetVal>()) {
667    // Once the return value symbol dies, no more checks can be performed
668    // against it. See if the return value was checked before this point.
669    // This would remove the symbol from the map as well.
670    if (SymReaper.isDead(I.second))
671      State = resolvePossiblyDestroyedMutex(State, I.first, &I.second);
672  }
673
674  for (auto I : State->get<LockMap>()) {
675    // Stop tracking dead mutex regions as well.
676    if (!SymReaper.isLiveRegion(I.first))
677      State = State->remove<LockMap>(I.first);
678  }
679
680  // TODO: We probably need to clean up the lock stack as well.
681  // It is tricky though: even if the mutex cannot be unlocked anymore,
682  // it can still participate in lock order reversal resolution.
683
684  C.addTransition(State);
685}
686
687ProgramStateRef PthreadLockChecker::checkRegionChanges(
688    ProgramStateRef State, const InvalidatedSymbols *Symbols,
689    ArrayRef<const MemRegion *> ExplicitRegions,
690    ArrayRef<const MemRegion *> Regions, const LocationContext *LCtx,
691    const CallEvent *Call) const {
692
693  bool IsLibraryFunction = false;
694  if (Call && Call->isGlobalCFunction()) {
695    // Avoid invalidating mutex state when a known supported function is called.
696    if (PThreadCallbacks.lookup(*Call) || FuchsiaCallbacks.lookup(*Call) ||
697        C11Callbacks.lookup(*Call))
698      return State;
699
700    if (Call->isInSystemHeader())
701      IsLibraryFunction = true;
702  }
703
704  for (auto R : Regions) {
705    // We assume that system library function wouldn't touch the mutex unless
706    // it takes the mutex explicitly as an argument.
707    // FIXME: This is a bit quadratic.
708    if (IsLibraryFunction &&
709        std::find(ExplicitRegions.begin(), ExplicitRegions.end(), R) ==
710            ExplicitRegions.end())
711      continue;
712
713    State = State->remove<LockMap>(R);
714    State = State->remove<DestroyRetVal>(R);
715
716    // TODO: We need to invalidate the lock stack as well. This is tricky
717    // to implement correctly and efficiently though, because the effects
718    // of mutex escapes on lock order may be fairly varied.
719  }
720
721  return State;
722}
723
724void ento::registerPthreadLockBase(CheckerManager &mgr) {
725  mgr.registerChecker<PthreadLockChecker>();
726}
727
728bool ento::shouldRegisterPthreadLockBase(const CheckerManager &mgr) { return true; }
729
730#define REGISTER_CHECKER(name)                                                 \
731  void ento::register##name(CheckerManager &mgr) {                             \
732    PthreadLockChecker *checker = mgr.getChecker<PthreadLockChecker>();        \
733    checker->ChecksEnabled[PthreadLockChecker::CK_##name] = true;              \
734    checker->CheckNames[PthreadLockChecker::CK_##name] =                       \
735        mgr.getCurrentCheckerName();                                           \
736  }                                                                            \
737                                                                               \
738  bool ento::shouldRegister##name(const CheckerManager &mgr) { return true; }
739
740REGISTER_CHECKER(PthreadLockChecker)
741REGISTER_CHECKER(FuchsiaLockChecker)
742REGISTER_CHECKER(C11LockChecker)
743