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 { Destroyed, Locked, Unlocked } K;
  29
  30 private:
  31   LockState(Kind K) : K(K) {}
  32
  33 public:
  34   static LockState getLocked() { return LockState(Locked); }
  35   static LockState getUnlocked() { return LockState(Unlocked); }
  36   static LockState getDestroyed() { return LockState(Destroyed); }
  37
  38   bool operator==(const LockState &X) const {
  39     return K == X.K;
  40   }
  41
  42   bool isLocked() const { return K == Locked; }
  43   bool isUnlocked() const { return K == Unlocked; }
  44   bool isDestroyed() const { return K == Destroyed; }
  45
  46   void Profile(llvm::FoldingSetNodeID &ID) const {
  47     ID.AddInteger(K);
  48   }
  49 };
  50
  51 class PthreadLockChecker : public Checker< check::PostStmt<CallExpr> > {
  52   mutable std::unique_ptr<BugType> BT_doublelock;
  53   mutable std::unique_ptr<BugType> BT_doubleunlock;
  54   mutable std::unique_ptr<BugType> BT_destroylock;
  55   mutable std::unique_ptr<BugType> BT_initlock;
  56   mutable std::unique_ptr<BugType> BT_lor;
  57   enum LockingSemantics {
  58     NotApplicable = 0,
  59     PthreadSemantics,
  60     XNUSemantics
  61   };
  62 public:
  63   void checkPostStmt(const CallExpr *CE, CheckerContext &C) const;
  64
  65   void AcquireLock(CheckerContext &C, const CallExpr *CE, SVal lock,
  66                    bool isTryLock, enum LockingSemantics semantics) const;
  67
  68   void ReleaseLock(CheckerContext &C, const CallExpr *CE, SVal lock) const;
  69   void DestroyLock(CheckerContext &C, const CallExpr *CE, SVal Lock) const;
  70   void InitLock(CheckerContext &C, const CallExpr *CE, SVal Lock) const;
  71   void reportUseDestroyedBug(CheckerContext &C, const CallExpr *CE) const;
  72 };
  73 } // end anonymous namespace
  74
  75 // GDM Entry for tracking lock state.
  76 REGISTER_LIST_WITH_PROGRAMSTATE(LockSet, const MemRegion *)
  77
  78 REGISTER_MAP_WITH_PROGRAMSTATE(LockMap, const MemRegion *, LockState)
  79
  80 void PthreadLockChecker::checkPostStmt(const CallExpr *CE,
  81                                        CheckerContext &C) const {
  82   ProgramStateRef state = C.getState();
  83   const LocationContext *LCtx = C.getLocationContext();
  84   StringRef FName = C.getCalleeName(CE);
  85   if (FName.empty())
  86     return;
  87
  88   if (CE->getNumArgs() != 1 && CE->getNumArgs() != 2)
  89     return;
  90
  91   if (FName == "pthread_mutex_lock" ||
  92       FName == "pthread_rwlock_rdlock" ||
  93       FName == "pthread_rwlock_wrlock")
  94     AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
  95                 false, PthreadSemantics);
  96   else if (FName == "lck_mtx_lock" ||
  97            FName == "lck_rw_lock_exclusive" ||
  98            FName == "lck_rw_lock_shared")
  99     AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
 100                 false, XNUSemantics);
 101   else if (FName == "pthread_mutex_trylock" ||
 102            FName == "pthread_rwlock_tryrdlock" ||
 103            FName == "pthread_rwlock_trywrlock")
 104     AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
 105                 true, PthreadSemantics);
 106   else if (FName == "lck_mtx_try_lock" ||
 107            FName == "lck_rw_try_lock_exclusive" ||
 108            FName == "lck_rw_try_lock_shared")
 109     AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
 110                 true, XNUSemantics);
 111   else if (FName == "pthread_mutex_unlock" ||
 112            FName == "pthread_rwlock_unlock" ||
 113            FName == "lck_mtx_unlock" ||
 114            FName == "lck_rw_done")
 115     ReleaseLock(C, CE, state->getSVal(CE->getArg(0), LCtx));
 116   else if (FName == "pthread_mutex_destroy" ||
 117            FName == "lck_mtx_destroy")
 118     DestroyLock(C, CE, state->getSVal(CE->getArg(0), LCtx));
 119   else if (FName == "pthread_mutex_init")
 120     InitLock(C, CE, state->getSVal(CE->getArg(0), LCtx));
 121 }
 122
 123 void PthreadLockChecker::AcquireLock(CheckerContext &C, const CallExpr *CE,
 124                                      SVal lock, bool isTryLock,
 125                                      enum LockingSemantics semantics) const {
 126
 127   const MemRegion *lockR = lock.getAsRegion();
 128   if (!lockR)
 129     return;
 130
 131   ProgramStateRef state = C.getState();
 132
 133   SVal X = state->getSVal(CE, C.getLocationContext());
 134   if (X.isUnknownOrUndef())
 135     return;
 136
 137   DefinedSVal retVal = X.castAs<DefinedSVal>();
 138
 139   if (const LockState *LState = state->get<LockMap>(lockR)) {
 140     if (LState->isLocked()) {
 141       if (!BT_doublelock)
 142         BT_doublelock.reset(new BugType(this, "Double locking",
 143                                         "Lock checker"));
 144       ExplodedNode *N = C.generateErrorNode();
 145       if (!N)
 146         return;
 147       auto report = llvm::make_unique<BugReport>(
 148           *BT_doublelock, "This lock has already been acquired", N);
 149       report->addRange(CE->getArg(0)->getSourceRange());
 150       C.emitReport(std::move(report));
 151       return;
 152     } else if (LState->isDestroyed()) {
 153       reportUseDestroyedBug(C, CE);
 154       return;
 155     }
 156   }
 157
 158   ProgramStateRef lockSucc = state;
 159   if (isTryLock) {
 160     // Bifurcate the state, and allow a mode where the lock acquisition fails.
 161     ProgramStateRef lockFail;
 162     switch (semantics) {
 163     case PthreadSemantics:
 164       std::tie(lockFail, lockSucc) = state->assume(retVal);
 165       break;
 166     case XNUSemantics:
 167       std::tie(lockSucc, lockFail) = state->assume(retVal);
 168       break;
 169     default:
 170       llvm_unreachable("Unknown tryLock locking semantics");
 171     }
 172     assert(lockFail && lockSucc);
 173     C.addTransition(lockFail);
 174
 175   } else if (semantics == PthreadSemantics) {
 176     // Assume that the return value was 0.
 177     lockSucc = state->assume(retVal, false);
 178     assert(lockSucc);
 179
 180   } else {
 181     // XNU locking semantics return void on non-try locks
 182     assert((semantics == XNUSemantics) && "Unknown locking semantics");
 183     lockSucc = state;
 184   }
 185
 186   // Record that the lock was acquired.
 187   lockSucc = lockSucc->add<LockSet>(lockR);
 188   lockSucc = lockSucc->set<LockMap>(lockR, LockState::getLocked());
 189   C.addTransition(lockSucc);
 190 }
 191
 192 void PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE,
 193                                      SVal lock) const {
 194
 195   const MemRegion *lockR = lock.getAsRegion();
 196   if (!lockR)
 197     return;
 198
 199   ProgramStateRef state = C.getState();
 200
 201   if (const LockState *LState = state->get<LockMap>(lockR)) {
 202     if (LState->isUnlocked()) {
 203       if (!BT_doubleunlock)
 204         BT_doubleunlock.reset(new BugType(this, "Double unlocking",
 205                                           "Lock checker"));
 206       ExplodedNode *N = C.generateErrorNode();
 207       if (!N)
 208         return;
 209       auto Report = llvm::make_unique<BugReport>(
 210           *BT_doubleunlock, "This lock has already been unlocked", N);
 211       Report->addRange(CE->getArg(0)->getSourceRange());
 212       C.emitReport(std::move(Report));
 213       return;
 214     } else if (LState->isDestroyed()) {
 215       reportUseDestroyedBug(C, CE);
 216       return;
 217     }
 218   }
 219
 220   LockSetTy LS = state->get<LockSet>();
 221
 222   // FIXME: Better analysis requires IPA for wrappers.
 223
 224   if (!LS.isEmpty()) {
 225     const MemRegion *firstLockR = LS.getHead();
 226     if (firstLockR != lockR) {
 227       if (!BT_lor)
 228         BT_lor.reset(new BugType(this, "Lock order reversal", "Lock checker"));
 229       ExplodedNode *N = C.generateErrorNode();
 230       if (!N)
 231         return;
 232       auto report = llvm::make_unique<BugReport>(
 233           *BT_lor, "This was not the most recently acquired lock. Possible "
 234                    "lock order reversal", N);
 235       report->addRange(CE->getArg(0)->getSourceRange());
 236       C.emitReport(std::move(report));
 237       return;
 238     }
 239     // Record that the lock was released.
 240     state = state->set<LockSet>(LS.getTail());
 241   }
 242
 243   state = state->set<LockMap>(lockR, LockState::getUnlocked());
 244   C.addTransition(state);
 245 }
 246
 247 void PthreadLockChecker::DestroyLock(CheckerContext &C, const CallExpr *CE,
 248                                      SVal Lock) const {
 249
 250   const MemRegion *LockR = Lock.getAsRegion();
 251   if (!LockR)
 252     return;
 253
 254   ProgramStateRef State = C.getState();
 255
 256   const LockState *LState = State->get<LockMap>(LockR);
 257   if (!LState || LState->isUnlocked()) {
 258     State = State->set<LockMap>(LockR, LockState::getDestroyed());
 259     C.addTransition(State);
 260     return;
 261   }
 262
 263   StringRef Message;
 264
 265   if (LState->isLocked()) {
 266     Message = "This lock is still locked";
 267   } else {
 268     Message = "This lock has already been destroyed";
 269   }
 270
 271   if (!BT_destroylock)
 272     BT_destroylock.reset(new BugType(this, "Destroy invalid lock",
 273                                      "Lock checker"));
 274   ExplodedNode *N = C.generateErrorNode();
 275   if (!N)
 276     return;
 277   auto Report = llvm::make_unique<BugReport>(*BT_destroylock, Message, N);
 278   Report->addRange(CE->getArg(0)->getSourceRange());
 279   C.emitReport(std::move(Report));
 280 }
 281
 282 void PthreadLockChecker::InitLock(CheckerContext &C, const CallExpr *CE,
 283                                   SVal Lock) const {
 284
 285   const MemRegion *LockR = Lock.getAsRegion();
 286   if (!LockR)
 287     return;
 288
 289   ProgramStateRef State = C.getState();
 290
 291   const struct LockState *LState = State->get<LockMap>(LockR);
 292   if (!LState || LState->isDestroyed()) {
 293     State = State->set<LockMap>(LockR, LockState::getUnlocked());
 294     C.addTransition(State);
 295     return;
 296   }
 297
 298   StringRef Message;
 299
 300   if (LState->isLocked()) {
 301     Message = "This lock is still being held";
 302   } else {
 303     Message = "This lock has already been initialized";
 304   }
 305
 306   if (!BT_initlock)
 307     BT_initlock.reset(new BugType(this, "Init invalid lock",
 308                                   "Lock checker"));
 309   ExplodedNode *N = C.generateErrorNode();
 310   if (!N)
 311     return;
 312   auto Report = llvm::make_unique<BugReport>(*BT_initlock, Message, N);
 313   Report->addRange(CE->getArg(0)->getSourceRange());
 314   C.emitReport(std::move(Report));
 315 }
 316
 317 void PthreadLockChecker::reportUseDestroyedBug(CheckerContext &C,
 318                                                const CallExpr *CE) const {
 319   if (!BT_destroylock)
 320     BT_destroylock.reset(new BugType(this, "Use destroyed lock",
 321                                      "Lock checker"));
 322   ExplodedNode *N = C.generateErrorNode();
 323   if (!N)
 324     return;
 325   auto Report = llvm::make_unique<BugReport>(
 326       *BT_destroylock, "This lock has already been destroyed", N);
 327   Report->addRange(CE->getArg(0)->getSourceRange());
 328   C.emitReport(std::move(Report));
 329 }
 330
 331 void ento::registerPthreadLockChecker(CheckerManager &mgr) {
 332   mgr.registerChecker<PthreadLockChecker>();
 333 }