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