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   void printState(raw_ostream &Out, ProgramStateRef State,
  85                   const char *NL, const char *Sep) const override;
  86
  87   void AcquireLock(CheckerContext &C, const CallExpr *CE, SVal lock,
  88                    bool isTryLock, enum LockingSemantics semantics) const;
  89
  90   void ReleaseLock(CheckerContext &C, const CallExpr *CE, SVal lock) const;
  91   void DestroyLock(CheckerContext &C, const CallExpr *CE, SVal Lock,
  92                    enum LockingSemantics semantics) const;
  93   void InitLock(CheckerContext &C, const CallExpr *CE, SVal Lock) const;
  94   void reportUseDestroyedBug(CheckerContext &C, const CallExpr *CE) const;
  95   ProgramStateRef resolvePossiblyDestroyedMutex(ProgramStateRef state,
  96                                                 const MemRegion *lockR,
  97                                                 const SymbolRef *sym) const;
  98 };
  99 } // end anonymous namespace
 100
 101 // A stack of locks for tracking lock-unlock order.
 102 REGISTER_LIST_WITH_PROGRAMSTATE(LockSet, const MemRegion *)
 103
 104 // An entry for tracking lock states.
 105 REGISTER_MAP_WITH_PROGRAMSTATE(LockMap, const MemRegion *, LockState)
 106
 107 // Return values for unresolved calls to pthread_mutex_destroy().
 108 REGISTER_MAP_WITH_PROGRAMSTATE(DestroyRetVal, const MemRegion *, SymbolRef)
 109
 110 void PthreadLockChecker::checkPostStmt(const CallExpr *CE,
 111                                        CheckerContext &C) const {
 112   ProgramStateRef state = C.getState();
 113   const LocationContext *LCtx = C.getLocationContext();
 114   StringRef FName = C.getCalleeName(CE);
 115   if (FName.empty())
 116     return;
 117
 118   if (CE->getNumArgs() != 1 && CE->getNumArgs() != 2)
 119     return;
 120
 121   if (FName == "pthread_mutex_lock" ||
 122       FName == "pthread_rwlock_rdlock" ||
 123       FName == "pthread_rwlock_wrlock")
 124     AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
 125                 false, PthreadSemantics);
 126   else if (FName == "lck_mtx_lock" ||
 127            FName == "lck_rw_lock_exclusive" ||
 128            FName == "lck_rw_lock_shared")
 129     AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
 130                 false, XNUSemantics);
 131   else if (FName == "pthread_mutex_trylock" ||
 132            FName == "pthread_rwlock_tryrdlock" ||
 133            FName == "pthread_rwlock_trywrlock")
 134     AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
 135                 true, PthreadSemantics);
 136   else if (FName == "lck_mtx_try_lock" ||
 137            FName == "lck_rw_try_lock_exclusive" ||
 138            FName == "lck_rw_try_lock_shared")
 139     AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
 140                 true, XNUSemantics);
 141   else if (FName == "pthread_mutex_unlock" ||
 142            FName == "pthread_rwlock_unlock" ||
 143            FName == "lck_mtx_unlock" ||
 144            FName == "lck_rw_done")
 145     ReleaseLock(C, CE, state->getSVal(CE->getArg(0), LCtx));
 146   else if (FName == "pthread_mutex_destroy")
 147     DestroyLock(C, CE, state->getSVal(CE->getArg(0), LCtx), PthreadSemantics);
 148   else if (FName == "lck_mtx_destroy")
 149     DestroyLock(C, CE, state->getSVal(CE->getArg(0), LCtx), XNUSemantics);
 150   else if (FName == "pthread_mutex_init")
 151     InitLock(C, CE, state->getSVal(CE->getArg(0), LCtx));
 152 }
 153
 154 // When a lock is destroyed, in some semantics(like PthreadSemantics) we are not
 155 // sure if the destroy call has succeeded or failed, and the lock enters one of
 156 // the 'possibly destroyed' state. There is a short time frame for the
 157 // programmer to check the return value to see if the lock was successfully
 158 // destroyed. Before we model the next operation over that lock, we call this
 159 // function to see if the return value was checked by now and set the lock state
 160 // - either to destroyed state or back to its previous state.
 161
 162 // In PthreadSemantics, pthread_mutex_destroy() returns zero if the lock is
 163 // successfully destroyed and it returns a non-zero value otherwise.
 164 ProgramStateRef PthreadLockChecker::resolvePossiblyDestroyedMutex(
 165     ProgramStateRef state, const MemRegion *lockR, const SymbolRef *sym) const {
 166   const LockState *lstate = state->get<LockMap>(lockR);
 167   // Existence in DestroyRetVal ensures existence in LockMap.
 168   // Existence in Destroyed also ensures that the lock state for lockR is either
 169   // UntouchedAndPossiblyDestroyed or UnlockedAndPossiblyDestroyed.
 170   assert(lstate->isUntouchedAndPossiblyDestroyed() ||
 171          lstate->isUnlockedAndPossiblyDestroyed());
 172
 173   ConstraintManager &CMgr = state->getConstraintManager();
 174   ConditionTruthVal retZero = CMgr.isNull(state, *sym);
 175   if (retZero.isConstrainedFalse()) {
 176     if (lstate->isUntouchedAndPossiblyDestroyed())
 177       state = state->remove<LockMap>(lockR);
 178     else if (lstate->isUnlockedAndPossiblyDestroyed())
 179       state = state->set<LockMap>(lockR, LockState::getUnlocked());
 180   } else
 181     state = state->set<LockMap>(lockR, LockState::getDestroyed());
 182
 183   // Removing the map entry (lockR, sym) from DestroyRetVal as the lock state is
 184   // now resolved.
 185   state = state->remove<DestroyRetVal>(lockR);
 186   return state;
 187 }
 188
 189 void PthreadLockChecker::printState(raw_ostream &Out, ProgramStateRef State,
 190                                     const char *NL, const char *Sep) const {
 191   LockMapTy LM = State->get<LockMap>();
 192   if (!LM.isEmpty()) {
 193     Out << Sep << "Mutex states:" << NL;
 194     for (auto I : LM) {
 195       I.first->dumpToStream(Out);
 196       if (I.second.isLocked())
 197         Out << ": locked";
 198       else if (I.second.isUnlocked())
 199         Out << ": unlocked";
 200       else if (I.second.isDestroyed())
 201         Out << ": destroyed";
 202       else if (I.second.isUntouchedAndPossiblyDestroyed())
 203         Out << ": not tracked, possibly destroyed";
 204       else if (I.second.isUnlockedAndPossiblyDestroyed())
 205         Out << ": unlocked, possibly destroyed";
 206       Out << NL;
 207     }
 208   }
 209
 210   LockSetTy LS = State->get<LockSet>();
 211   if (!LS.isEmpty()) {
 212     Out << Sep << "Mutex lock order:" << NL;
 213     for (auto I: LS) {
 214       I->dumpToStream(Out);
 215       Out << NL;
 216     }
 217   }
 218
 219   // TODO: Dump destroyed mutex symbols?
 220 }
 221
 222 void PthreadLockChecker::AcquireLock(CheckerContext &C, const CallExpr *CE,
 223                                      SVal lock, bool isTryLock,
 224                                      enum LockingSemantics semantics) const {
 225
 226   const MemRegion *lockR = lock.getAsRegion();
 227   if (!lockR)
 228     return;
 229
 230   ProgramStateRef state = C.getState();
 231   const SymbolRef *sym = state->get<DestroyRetVal>(lockR);
 232   if (sym)
 233     state = resolvePossiblyDestroyedMutex(state, lockR, sym);
 234
 235   SVal X = state->getSVal(CE, C.getLocationContext());
 236   if (X.isUnknownOrUndef())
 237     return;
 238
 239   DefinedSVal retVal = X.castAs<DefinedSVal>();
 240
 241   if (const LockState *LState = state->get<LockMap>(lockR)) {
 242     if (LState->isLocked()) {
 243       if (!BT_doublelock)
 244         BT_doublelock.reset(new BugType(this, "Double locking",
 245                                         "Lock checker"));
 246       ExplodedNode *N = C.generateErrorNode();
 247       if (!N)
 248         return;
 249       auto report = llvm::make_unique<BugReport>(
 250           *BT_doublelock, "This lock has already been acquired", N);
 251       report->addRange(CE->getArg(0)->getSourceRange());
 252       C.emitReport(std::move(report));
 253       return;
 254     } else if (LState->isDestroyed()) {
 255       reportUseDestroyedBug(C, CE);
 256       return;
 257     }
 258   }
 259
 260   ProgramStateRef lockSucc = state;
 261   if (isTryLock) {
 262     // Bifurcate the state, and allow a mode where the lock acquisition fails.
 263     ProgramStateRef lockFail;
 264     switch (semantics) {
 265     case PthreadSemantics:
 266       std::tie(lockFail, lockSucc) = state->assume(retVal);
 267       break;
 268     case XNUSemantics:
 269       std::tie(lockSucc, lockFail) = state->assume(retVal);
 270       break;
 271     default:
 272       llvm_unreachable("Unknown tryLock locking semantics");
 273     }
 274     assert(lockFail && lockSucc);
 275     C.addTransition(lockFail);
 276
 277   } else if (semantics == PthreadSemantics) {
 278     // Assume that the return value was 0.
 279     lockSucc = state->assume(retVal, false);
 280     assert(lockSucc);
 281
 282   } else {
 283     // XNU locking semantics return void on non-try locks
 284     assert((semantics == XNUSemantics) && "Unknown locking semantics");
 285     lockSucc = state;
 286   }
 287
 288   // Record that the lock was acquired.
 289   lockSucc = lockSucc->add<LockSet>(lockR);
 290   lockSucc = lockSucc->set<LockMap>(lockR, LockState::getLocked());
 291   C.addTransition(lockSucc);
 292 }
 293
 294 void PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE,
 295                                      SVal lock) const {
 296
 297   const MemRegion *lockR = lock.getAsRegion();
 298   if (!lockR)
 299     return;
 300
 301   ProgramStateRef state = C.getState();
 302   const SymbolRef *sym = state->get<DestroyRetVal>(lockR);
 303   if (sym)
 304     state = resolvePossiblyDestroyedMutex(state, lockR, sym);
 305
 306   if (const LockState *LState = state->get<LockMap>(lockR)) {
 307     if (LState->isUnlocked()) {
 308       if (!BT_doubleunlock)
 309         BT_doubleunlock.reset(new BugType(this, "Double unlocking",
 310                                           "Lock checker"));
 311       ExplodedNode *N = C.generateErrorNode();
 312       if (!N)
 313         return;
 314       auto Report = llvm::make_unique<BugReport>(
 315           *BT_doubleunlock, "This lock has already been unlocked", N);
 316       Report->addRange(CE->getArg(0)->getSourceRange());
 317       C.emitReport(std::move(Report));
 318       return;
 319     } else if (LState->isDestroyed()) {
 320       reportUseDestroyedBug(C, CE);
 321       return;
 322     }
 323   }
 324
 325   LockSetTy LS = state->get<LockSet>();
 326
 327   // FIXME: Better analysis requires IPA for wrappers.
 328
 329   if (!LS.isEmpty()) {
 330     const MemRegion *firstLockR = LS.getHead();
 331     if (firstLockR != lockR) {
 332       if (!BT_lor)
 333         BT_lor.reset(new BugType(this, "Lock order reversal", "Lock checker"));
 334       ExplodedNode *N = C.generateErrorNode();
 335       if (!N)
 336         return;
 337       auto report = llvm::make_unique<BugReport>(
 338           *BT_lor, "This was not the most recently acquired lock. Possible "
 339                    "lock order reversal", N);
 340       report->addRange(CE->getArg(0)->getSourceRange());
 341       C.emitReport(std::move(report));
 342       return;
 343     }
 344     // Record that the lock was released.
 345     state = state->set<LockSet>(LS.getTail());
 346   }
 347
 348   state = state->set<LockMap>(lockR, LockState::getUnlocked());
 349   C.addTransition(state);
 350 }
 351
 352 void PthreadLockChecker::DestroyLock(CheckerContext &C, const CallExpr *CE,
 353                                      SVal Lock,
 354                                      enum LockingSemantics semantics) const {
 355
 356   const MemRegion *LockR = Lock.getAsRegion();
 357   if (!LockR)
 358     return;
 359
 360   ProgramStateRef State = C.getState();
 361
 362   const SymbolRef *sym = State->get<DestroyRetVal>(LockR);
 363   if (sym)
 364     State = resolvePossiblyDestroyedMutex(State, LockR, sym);
 365
 366   const LockState *LState = State->get<LockMap>(LockR);
 367   // Checking the return value of the destroy method only in the case of
 368   // PthreadSemantics
 369   if (semantics == PthreadSemantics) {
 370     if (!LState || LState->isUnlocked()) {
 371       SymbolRef sym = C.getSVal(CE).getAsSymbol();
 372       if (!sym) {
 373         State = State->remove<LockMap>(LockR);
 374         C.addTransition(State);
 375         return;
 376       }
 377       State = State->set<DestroyRetVal>(LockR, sym);
 378       if (LState && LState->isUnlocked())
 379         State = State->set<LockMap>(
 380             LockR, LockState::getUnlockedAndPossiblyDestroyed());
 381       else
 382         State = State->set<LockMap>(
 383             LockR, LockState::getUntouchedAndPossiblyDestroyed());
 384       C.addTransition(State);
 385       return;
 386     }
 387   } else {
 388     if (!LState || LState->isUnlocked()) {
 389       State = State->set<LockMap>(LockR, LockState::getDestroyed());
 390       C.addTransition(State);
 391       return;
 392     }
 393   }
 394   StringRef Message;
 395
 396   if (LState->isLocked()) {
 397     Message = "This lock is still locked";
 398   } else {
 399     Message = "This lock has already been destroyed";
 400   }
 401
 402   if (!BT_destroylock)
 403     BT_destroylock.reset(new BugType(this, "Destroy invalid lock",
 404                                      "Lock checker"));
 405   ExplodedNode *N = C.generateErrorNode();
 406   if (!N)
 407     return;
 408   auto Report = llvm::make_unique<BugReport>(*BT_destroylock, Message, N);
 409   Report->addRange(CE->getArg(0)->getSourceRange());
 410   C.emitReport(std::move(Report));
 411 }
 412
 413 void PthreadLockChecker::InitLock(CheckerContext &C, const CallExpr *CE,
 414                                   SVal Lock) const {
 415
 416   const MemRegion *LockR = Lock.getAsRegion();
 417   if (!LockR)
 418     return;
 419
 420   ProgramStateRef State = C.getState();
 421
 422   const SymbolRef *sym = State->get<DestroyRetVal>(LockR);
 423   if (sym)
 424     State = resolvePossiblyDestroyedMutex(State, LockR, sym);
 425
 426   const struct LockState *LState = State->get<LockMap>(LockR);
 427   if (!LState || LState->isDestroyed()) {
 428     State = State->set<LockMap>(LockR, LockState::getUnlocked());
 429     C.addTransition(State);
 430     return;
 431   }
 432
 433   StringRef Message;
 434
 435   if (LState->isLocked()) {
 436     Message = "This lock is still being held";
 437   } else {
 438     Message = "This lock has already been initialized";
 439   }
 440
 441   if (!BT_initlock)
 442     BT_initlock.reset(new BugType(this, "Init invalid lock",
 443                                   "Lock checker"));
 444   ExplodedNode *N = C.generateErrorNode();
 445   if (!N)
 446     return;
 447   auto Report = llvm::make_unique<BugReport>(*BT_initlock, Message, N);
 448   Report->addRange(CE->getArg(0)->getSourceRange());
 449   C.emitReport(std::move(Report));
 450 }
 451
 452 void PthreadLockChecker::reportUseDestroyedBug(CheckerContext &C,
 453                                                const CallExpr *CE) const {
 454   if (!BT_destroylock)
 455     BT_destroylock.reset(new BugType(this, "Use destroyed lock",
 456                                      "Lock checker"));
 457   ExplodedNode *N = C.generateErrorNode();
 458   if (!N)
 459     return;
 460   auto Report = llvm::make_unique<BugReport>(
 461       *BT_destroylock, "This lock has already been destroyed", N);
 462   Report->addRange(CE->getArg(0)->getSourceRange());
 463   C.emitReport(std::move(Report));
 464 }
 465
 466 void PthreadLockChecker::checkDeadSymbols(SymbolReaper &SymReaper,
 467                                           CheckerContext &C) const {
 468   ProgramStateRef State = C.getState();
 469
 470   // TODO: Clean LockMap when a mutex region dies.
 471
 472   DestroyRetValTy TrackedSymbols = State->get<DestroyRetVal>();
 473   for (DestroyRetValTy::iterator I = TrackedSymbols.begin(),
 474                                  E = TrackedSymbols.end();
 475        I != E; ++I) {
 476     const SymbolRef Sym = I->second;
 477     const MemRegion *lockR = I->first;
 478     bool IsSymDead = SymReaper.isDead(Sym);
 479     // Remove the dead symbol from the return value symbols map.
 480     if (IsSymDead)
 481       State = resolvePossiblyDestroyedMutex(State, lockR, &Sym);
 482   }
 483   C.addTransition(State);
 484 }
 485
 486 void ento::registerPthreadLockChecker(CheckerManager &mgr) {
 487   mgr.registerChecker<PthreadLockChecker>();
 488 }