clang/lib/StaticAnalyzer/Checkers/PthreadLockChecker.cpp

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