Home | History | Annotate | Download | only in Checkers 
      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 }
    335