contrib/llvm/tools/clang/lib/StaticAnalyzer/Checkers/PthreadLockChecker.cpp

   1 //===--- PthreadLockChecker.cpp - Check for locking problems ---*- C++ -*--===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This defines PthreadLockChecker, a simple lock -> unlock checker.
  11 // Also handles XNU locks, which behave similarly enough to share code.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "ClangSACheckers.h"
  16 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
  17 #include "clang/StaticAnalyzer/Core/Checker.h"
  18 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
  19 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
  20 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
  21
  22 using namespace clang;
  23 using namespace ento;
  24
  25 namespace {
  26
  27 struct LockState {
  28   enum Kind {
  29     Destroyed,
  30     Locked,
  31     Unlocked,
  32     UntouchedAndPossiblyDestroyed,
  33     UnlockedAndPossiblyDestroyed
  34   } K;
  35
  36 private:
  37   LockState(Kind K) : K(K) {}
  38
  39 public:
  40   static LockState getLocked() { return LockState(Locked); }
  41   static LockState getUnlocked() { return LockState(Unlocked); }
  42   static LockState getDestroyed() { return LockState(Destroyed); }
  43   static LockState getUntouchedAndPossiblyDestroyed() {
  44     return LockState(UntouchedAndPossiblyDestroyed);
  45   }
  46   static LockState getUnlockedAndPossiblyDestroyed() {
  47     return LockState(UnlockedAndPossiblyDestroyed);
  48   }
  49
  50   bool operator==(const LockState &X) const {
  51     return K == X.K;
  52   }
  53
  54   bool isLocked() const { return K == Locked; }
  55   bool isUnlocked() const { return K == Unlocked; }
  56   bool isDestroyed() const { return K == Destroyed; }
  57   bool isUntouchedAndPossiblyDestroyed() const {
  58     return K == UntouchedAndPossiblyDestroyed;
  59   }
  60   bool isUnlockedAndPossiblyDestroyed() const {
  61     return K == UnlockedAndPossiblyDestroyed;
  62   }
  63
  64   void Profile(llvm::FoldingSetNodeID &ID) const {
  65     ID.AddInteger(K);
  66   }
  67 };
  68
  69 class PthreadLockChecker
  70     : public Checker<check::PostStmt<CallExpr>, check::DeadSymbols> {
  71   mutable std::unique_ptr<BugType> BT_doublelock;
  72   mutable std::unique_ptr<BugType> BT_doubleunlock;
  73   mutable std::unique_ptr<BugType> BT_destroylock;
  74   mutable std::unique_ptr<BugType> BT_initlock;
  75   mutable std::unique_ptr<BugType> BT_lor;
  76   enum LockingSemantics {
  77     NotApplicable = 0,
  78     PthreadSemantics,
  79     XNUSemantics
  80   };
  81 public:
  82   void checkPostStmt(const CallExpr *CE, CheckerContext &C) const;
  83   void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const;
  84
  85   void AcquireLock(CheckerContext &C, const CallExpr *CE, SVal lock,
  86                    bool isTryLock, enum LockingSemantics semantics) const;
  87
  88   void ReleaseLock(CheckerContext &C, const CallExpr *CE, SVal lock) const;
  89   void DestroyLock(CheckerContext &C, const CallExpr *CE, SVal Lock,
  90                    enum LockingSemantics semantics) const;
  91   void InitLock(CheckerContext &C, const CallExpr *CE, SVal Lock) const;
  92   void reportUseDestroyedBug(CheckerContext &C, const CallExpr *CE) const;
  93   ProgramStateRef resolvePossiblyDestroyedMutex(ProgramStateRef state,
  94                                                 const MemRegion *lockR,
  95                                                 const SymbolRef *sym) const;
  96 };
  97 } // end anonymous namespace
  98
  99 // A stack of locks for tracking lock-unlock order.
 100 REGISTER_LIST_WITH_PROGRAMSTATE(LockSet, const MemRegion *)
 101
 102 // An entry for tracking lock states.
 103 REGISTER_MAP_WITH_PROGRAMSTATE(LockMap, const MemRegion *, LockState)
 104
 105 // Return values for unresolved calls to pthread_mutex_destroy().
 106 REGISTER_MAP_WITH_PROGRAMSTATE(DestroyRetVal, const MemRegion *, SymbolRef)
 107
 108 void PthreadLockChecker::checkPostStmt(const CallExpr *CE,
 109                                        CheckerContext &C) const {
 110   ProgramStateRef state = C.getState();
 111   const LocationContext *LCtx = C.getLocationContext();
 112   StringRef FName = C.getCalleeName(CE);
 113   if (FName.empty())
 114     return;
 115
 116   if (CE->getNumArgs() != 1 && CE->getNumArgs() != 2)
 117     return;
 118
 119   if (FName == "pthread_mutex_lock" ||
 120       FName == "pthread_rwlock_rdlock" ||
 121       FName == "pthread_rwlock_wrlock")
 122     AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
 123                 false, PthreadSemantics);
 124   else if (FName == "lck_mtx_lock" ||
 125            FName == "lck_rw_lock_exclusive" ||
 126            FName == "lck_rw_lock_shared")
 127     AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
 128                 false, XNUSemantics);
 129   else if (FName == "pthread_mutex_trylock" ||
 130            FName == "pthread_rwlock_tryrdlock" ||
 131            FName == "pthread_rwlock_trywrlock")
 132     AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
 133                 true, PthreadSemantics);
 134   else if (FName == "lck_mtx_try_lock" ||
 135            FName == "lck_rw_try_lock_exclusive" ||
 136            FName == "lck_rw_try_lock_shared")
 137     AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
 138                 true, XNUSemantics);
 139   else if (FName == "pthread_mutex_unlock" ||
 140            FName == "pthread_rwlock_unlock" ||
 141            FName == "lck_mtx_unlock" ||
 142            FName == "lck_rw_done")
 143     ReleaseLock(C, CE, state->getSVal(CE->getArg(0), LCtx));
 144   else if (FName == "pthread_mutex_destroy")
 145     DestroyLock(C, CE, state->getSVal(CE->getArg(0), LCtx), PthreadSemantics);
 146   else if (FName == "lck_mtx_destroy")
 147     DestroyLock(C, CE, state->getSVal(CE->getArg(0), LCtx), XNUSemantics);
 148   else if (FName == "pthread_mutex_init")
 149     InitLock(C, CE, state->getSVal(CE->getArg(0), LCtx));
 150 }
 151
 152 // When a lock is destroyed, in some semantics(like PthreadSemantics) we are not
 153 // sure if the destroy call has succeeded or failed, and the lock enters one of
 154 // the 'possibly destroyed' state. There is a short time frame for the
 155 // programmer to check the return value to see if the lock was successfully
 156 // destroyed. Before we model the next operation over that lock, we call this
 157 // function to see if the return value was checked by now and set the lock state
 158 // - either to destroyed state or back to its previous state.
 159
 160 // In PthreadSemantics, pthread_mutex_destroy() returns zero if the lock is
 161 // successfully destroyed and it returns a non-zero value otherwise.
 162 ProgramStateRef PthreadLockChecker::resolvePossiblyDestroyedMutex(
 163     ProgramStateRef state, const MemRegion *lockR, const SymbolRef *sym) const {
 164   const LockState *lstate = state->get<LockMap>(lockR);
 165   // Existence in DestroyRetVal ensures existence in LockMap.
 166   // Existence in Destroyed also ensures that the lock state for lockR is either
 167   // UntouchedAndPossiblyDestroyed or UnlockedAndPossiblyDestroyed.
 168   assert(lstate->isUntouchedAndPossiblyDestroyed() ||
 169          lstate->isUnlockedAndPossiblyDestroyed());
 170
 171   ConstraintManager &CMgr = state->getConstraintManager();
 172   ConditionTruthVal retZero = CMgr.isNull(state, *sym);
 173   if (retZero.isConstrainedFalse()) {
 174     if (lstate->isUntouchedAndPossiblyDestroyed())
 175       state = state->remove<LockMap>(lockR);
 176     else if (lstate->isUnlockedAndPossiblyDestroyed())
 177       state = state->set<LockMap>(lockR, LockState::getUnlocked());
 178   } else
 179     state = state->set<LockMap>(lockR, LockState::getDestroyed());
 180
 181   // Removing the map entry (lockR, sym) from DestroyRetVal as the lock state is
 182   // now resolved.
 183   state = state->remove<DestroyRetVal>(lockR);
 184   return state;
 185 }
 186
 187 void PthreadLockChecker::AcquireLock(CheckerContext &C, const CallExpr *CE,
 188                                      SVal lock, bool isTryLock,
 189                                      enum LockingSemantics semantics) const {
 190
 191   const MemRegion *lockR = lock.getAsRegion();
 192   if (!lockR)
 193     return;
 194
 195   ProgramStateRef state = C.getState();
 196   const SymbolRef *sym = state->get<DestroyRetVal>(lockR);
 197   if (sym)
 198     state = resolvePossiblyDestroyedMutex(state, lockR, sym);
 199
 200   SVal X = state->getSVal(CE, C.getLocationContext());
 201   if (X.isUnknownOrUndef())
 202     return;
 203
 204   DefinedSVal retVal = X.castAs<DefinedSVal>();
 205
 206   if (const LockState *LState = state->get<LockMap>(lockR)) {
 207     if (LState->isLocked()) {
 208       if (!BT_doublelock)
 209         BT_doublelock.reset(new BugType(this, "Double locking",
 210                                         "Lock checker"));
 211       ExplodedNode *N = C.generateErrorNode();
 212       if (!N)
 213         return;
 214       auto report = llvm::make_unique<BugReport>(
 215           *BT_doublelock, "This lock has already been acquired", N);
 216       report->addRange(CE->getArg(0)->getSourceRange());
 217       C.emitReport(std::move(report));
 218       return;
 219     } else if (LState->isDestroyed()) {
 220       reportUseDestroyedBug(C, CE);
 221       return;
 222     }
 223   }
 224
 225   ProgramStateRef lockSucc = state;
 226   if (isTryLock) {
 227     // Bifurcate the state, and allow a mode where the lock acquisition fails.
 228     ProgramStateRef lockFail;
 229     switch (semantics) {
 230     case PthreadSemantics:
 231       std::tie(lockFail, lockSucc) = state->assume(retVal);
 232       break;
 233     case XNUSemantics:
 234       std::tie(lockSucc, lockFail) = state->assume(retVal);
 235       break;
 236     default:
 237       llvm_unreachable("Unknown tryLock locking semantics");
 238     }
 239     assert(lockFail && lockSucc);
 240     C.addTransition(lockFail);
 241
 242   } else if (semantics == PthreadSemantics) {
 243     // Assume that the return value was 0.
 244     lockSucc = state->assume(retVal, false);
 245     assert(lockSucc);
 246
 247   } else {
 248     // XNU locking semantics return void on non-try locks
 249     assert((semantics == XNUSemantics) && "Unknown locking semantics");
 250     lockSucc = state;
 251   }
 252
 253   // Record that the lock was acquired.
 254   lockSucc = lockSucc->add<LockSet>(lockR);
 255   lockSucc = lockSucc->set<LockMap>(lockR, LockState::getLocked());
 256   C.addTransition(lockSucc);
 257 }
 258
 259 void PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE,
 260                                      SVal lock) const {
 261
 262   const MemRegion *lockR = lock.getAsRegion();
 263   if (!lockR)
 264     return;
 265
 266   ProgramStateRef state = C.getState();
 267   const SymbolRef *sym = state->get<DestroyRetVal>(lockR);
 268   if (sym)
 269     state = resolvePossiblyDestroyedMutex(state, lockR, sym);
 270
 271   if (const LockState *LState = state->get<LockMap>(lockR)) {
 272     if (LState->isUnlocked()) {
 273       if (!BT_doubleunlock)
 274         BT_doubleunlock.reset(new BugType(this, "Double unlocking",
 275                                           "Lock checker"));
 276       ExplodedNode *N = C.generateErrorNode();
 277       if (!N)
 278         return;
 279       auto Report = llvm::make_unique<BugReport>(
 280           *BT_doubleunlock, "This lock has already been unlocked", N);
 281       Report->addRange(CE->getArg(0)->getSourceRange());
 282       C.emitReport(std::move(Report));
 283       return;
 284     } else if (LState->isDestroyed()) {
 285       reportUseDestroyedBug(C, CE);
 286       return;
 287     }
 288   }
 289
 290   LockSetTy LS = state->get<LockSet>();
 291
 292   // FIXME: Better analysis requires IPA for wrappers.
 293
 294   if (!LS.isEmpty()) {
 295     const MemRegion *firstLockR = LS.getHead();
 296     if (firstLockR != lockR) {
 297       if (!BT_lor)
 298         BT_lor.reset(new BugType(this, "Lock order reversal", "Lock checker"));
 299       ExplodedNode *N = C.generateErrorNode();
 300       if (!N)
 301         return;
 302       auto report = llvm::make_unique<BugReport>(
 303           *BT_lor, "This was not the most recently acquired lock. Possible "
 304                    "lock order reversal", N);
 305       report->addRange(CE->getArg(0)->getSourceRange());
 306       C.emitReport(std::move(report));
 307       return;
 308     }
 309     // Record that the lock was released.
 310     state = state->set<LockSet>(LS.getTail());
 311   }
 312
 313   state = state->set<LockMap>(lockR, LockState::getUnlocked());
 314   C.addTransition(state);
 315 }
 316
 317 void PthreadLockChecker::DestroyLock(CheckerContext &C, const CallExpr *CE,
 318                                      SVal Lock,
 319                                      enum LockingSemantics semantics) const {
 320
 321   const MemRegion *LockR = Lock.getAsRegion();
 322   if (!LockR)
 323     return;
 324
 325   ProgramStateRef State = C.getState();
 326
 327   const SymbolRef *sym = State->get<DestroyRetVal>(LockR);
 328   if (sym)
 329     State = resolvePossiblyDestroyedMutex(State, LockR, sym);
 330
 331   const LockState *LState = State->get<LockMap>(LockR);
 332   // Checking the return value of the destroy method only in the case of
 333   // PthreadSemantics
 334   if (semantics == PthreadSemantics) {
 335     if (!LState || LState->isUnlocked()) {
 336       SymbolRef sym = C.getSVal(CE).getAsSymbol();
 337       if (!sym) {
 338         State = State->remove<LockMap>(LockR);
 339         C.addTransition(State);
 340         return;
 341       }
 342       State = State->set<DestroyRetVal>(LockR, sym);
 343       if (LState && LState->isUnlocked())
 344         State = State->set<LockMap>(
 345             LockR, LockState::getUnlockedAndPossiblyDestroyed());
 346       else
 347         State = State->set<LockMap>(
 348             LockR, LockState::getUntouchedAndPossiblyDestroyed());
 349       C.addTransition(State);
 350       return;
 351     }
 352   } else {
 353     if (!LState || LState->isUnlocked()) {
 354       State = State->set<LockMap>(LockR, LockState::getDestroyed());
 355       C.addTransition(State);
 356       return;
 357     }
 358   }
 359   StringRef Message;
 360
 361   if (LState->isLocked()) {
 362     Message = "This lock is still locked";
 363   } else {
 364     Message = "This lock has already been destroyed";
 365   }
 366
 367   if (!BT_destroylock)
 368     BT_destroylock.reset(new BugType(this, "Destroy invalid lock",
 369                                      "Lock checker"));
 370   ExplodedNode *N = C.generateErrorNode();
 371   if (!N)
 372     return;
 373   auto Report = llvm::make_unique<BugReport>(*BT_destroylock, Message, N);
 374   Report->addRange(CE->getArg(0)->getSourceRange());
 375   C.emitReport(std::move(Report));
 376 }
 377
 378 void PthreadLockChecker::InitLock(CheckerContext &C, const CallExpr *CE,
 379                                   SVal Lock) const {
 380
 381   const MemRegion *LockR = Lock.getAsRegion();
 382   if (!LockR)
 383     return;
 384
 385   ProgramStateRef State = C.getState();
 386
 387   const SymbolRef *sym = State->get<DestroyRetVal>(LockR);
 388   if (sym)
 389     State = resolvePossiblyDestroyedMutex(State, LockR, sym);
 390
 391   const struct LockState *LState = State->get<LockMap>(LockR);
 392   if (!LState || LState->isDestroyed()) {
 393     State = State->set<LockMap>(LockR, LockState::getUnlocked());
 394     C.addTransition(State);
 395     return;
 396   }
 397
 398   StringRef Message;
 399
 400   if (LState->isLocked()) {
 401     Message = "This lock is still being held";
 402   } else {
 403     Message = "This lock has already been initialized";
 404   }
 405
 406   if (!BT_initlock)
 407     BT_initlock.reset(new BugType(this, "Init invalid lock",
 408                                   "Lock checker"));
 409   ExplodedNode *N = C.generateErrorNode();
 410   if (!N)
 411     return;
 412   auto Report = llvm::make_unique<BugReport>(*BT_initlock, Message, N);
 413   Report->addRange(CE->getArg(0)->getSourceRange());
 414   C.emitReport(std::move(Report));
 415 }
 416
 417 void PthreadLockChecker::reportUseDestroyedBug(CheckerContext &C,
 418                                                const CallExpr *CE) const {
 419   if (!BT_destroylock)
 420     BT_destroylock.reset(new BugType(this, "Use destroyed lock",
 421                                      "Lock checker"));
 422   ExplodedNode *N = C.generateErrorNode();
 423   if (!N)
 424     return;
 425   auto Report = llvm::make_unique<BugReport>(
 426       *BT_destroylock, "This lock has already been destroyed", N);
 427   Report->addRange(CE->getArg(0)->getSourceRange());
 428   C.emitReport(std::move(Report));
 429 }
 430
 431 void PthreadLockChecker::checkDeadSymbols(SymbolReaper &SymReaper,
 432                                           CheckerContext &C) const {
 433   ProgramStateRef State = C.getState();
 434
 435   // TODO: Clean LockMap when a mutex region dies.
 436
 437   DestroyRetValTy TrackedSymbols = State->get<DestroyRetVal>();
 438   for (DestroyRetValTy::iterator I = TrackedSymbols.begin(),
 439                                  E = TrackedSymbols.end();
 440        I != E; ++I) {
 441     const SymbolRef Sym = I->second;
 442     const MemRegion *lockR = I->first;
 443     bool IsSymDead = SymReaper.isDead(Sym);
 444     // Remove the dead symbol from the return value symbols map.
 445     if (IsSymDead)
 446       State = resolvePossiblyDestroyedMutex(State, lockR, &Sym);
 447   }
 448   C.addTransition(State);
 449 }
 450
 451 void ento::registerPthreadLockChecker(CheckerManager &mgr) {
 452   mgr.registerChecker<PthreadLockChecker>();
 453 }