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