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(void) { return LockState(Locked); }
     36   static LockState getUnlocked(void) { return LockState(Unlocked); }
     37   static LockState getDestroyed(void) { 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.generateSink();
    146       if (!N)
    147         return;
    148       BugReport *report = new BugReport(*BT_doublelock,
    149                                         "This lock has already been acquired",
    150                                         N);
    151       report->addRange(CE->getArg(0)->getSourceRange());
    152       C.emitReport(report);
    153       return;
    154     } else if (LState->isDestroyed()) {
    155       reportUseDestroyedBug(C, CE);
    156       return;
    157     }
    158   }
    159 
    160   ProgramStateRef lockSucc = state;
    161   if (isTryLock) {
    162     // Bifurcate the state, and allow a mode where the lock acquisition fails.
    163     ProgramStateRef lockFail;
    164     switch (semantics) {
    165     case PthreadSemantics:
    166       std::tie(lockFail, lockSucc) = state->assume(retVal);
    167       break;
    168     case XNUSemantics:
    169       std::tie(lockSucc, lockFail) = state->assume(retVal);
    170       break;
    171     default:
    172       llvm_unreachable("Unknown tryLock locking semantics");
    173     }
    174     assert(lockFail && lockSucc);
    175     C.addTransition(lockFail);
    176 
    177   } else if (semantics == PthreadSemantics) {
    178     // Assume that the return value was 0.
    179     lockSucc = state->assume(retVal, false);
    180     assert(lockSucc);
    181 
    182   } else {
    183     // XNU locking semantics return void on non-try locks
    184     assert((semantics == XNUSemantics) && "Unknown locking semantics");
    185     lockSucc = state;
    186   }
    187 
    188   // Record that the lock was acquired.
    189   lockSucc = lockSucc->add<LockSet>(lockR);
    190   lockSucc = lockSucc->set<LockMap>(lockR, LockState::getLocked());
    191   C.addTransition(lockSucc);
    192 }
    193 
    194 void PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE,
    195                                      SVal lock) const {
    196 
    197   const MemRegion *lockR = lock.getAsRegion();
    198   if (!lockR)
    199     return;
    200 
    201   ProgramStateRef state = C.getState();
    202 
    203   if (const LockState *LState = state->get<LockMap>(lockR)) {
    204     if (LState->isUnlocked()) {
    205       if (!BT_doubleunlock)
    206         BT_doubleunlock.reset(new BugType(this, "Double unlocking",
    207                                           "Lock checker"));
    208       ExplodedNode *N = C.generateSink();
    209       if (!N)
    210         return;
    211       BugReport *Report = new BugReport(*BT_doubleunlock,
    212                                         "This lock has already been unlocked",
    213                                         N);
    214       Report->addRange(CE->getArg(0)->getSourceRange());
    215       C.emitReport(Report);
    216       return;
    217     } else if (LState->isDestroyed()) {
    218       reportUseDestroyedBug(C, CE);
    219       return;
    220     }
    221   }
    222 
    223   LockSetTy LS = state->get<LockSet>();
    224 
    225   // FIXME: Better analysis requires IPA for wrappers.
    226 
    227   if (!LS.isEmpty()) {
    228     const MemRegion *firstLockR = LS.getHead();
    229     if (firstLockR != lockR) {
    230       if (!BT_lor)
    231         BT_lor.reset(new BugType(this, "Lock order reversal", "Lock checker"));
    232       ExplodedNode *N = C.generateSink();
    233       if (!N)
    234         return;
    235       BugReport *report = new BugReport(*BT_lor,
    236                                         "This was not the most recently "
    237                                         "acquired lock. Possible lock order "
    238                                         "reversal",
    239                                         N);
    240       report->addRange(CE->getArg(0)->getSourceRange());
    241       C.emitReport(report);
    242       return;
    243     }
    244     // Record that the lock was released.
    245     state = state->set<LockSet>(LS.getTail());
    246   }
    247 
    248   state = state->set<LockMap>(lockR, LockState::getUnlocked());
    249   C.addTransition(state);
    250 }
    251 
    252 void PthreadLockChecker::DestroyLock(CheckerContext &C, const CallExpr *CE,
    253                                      SVal Lock) const {
    254 
    255   const MemRegion *LockR = Lock.getAsRegion();
    256   if (!LockR)
    257     return;
    258 
    259   ProgramStateRef State = C.getState();
    260 
    261   const LockState *LState = State->get<LockMap>(LockR);
    262   if (!LState || LState->isUnlocked()) {
    263     State = State->set<LockMap>(LockR, LockState::getDestroyed());
    264     C.addTransition(State);
    265     return;
    266   }
    267 
    268   StringRef Message;
    269 
    270   if (LState->isLocked()) {
    271     Message = "This lock is still locked";
    272   } else {
    273     Message = "This lock has already been destroyed";
    274   }
    275 
    276   if (!BT_destroylock)
    277     BT_destroylock.reset(new BugType(this, "Destroy invalid lock",
    278                                      "Lock checker"));
    279   ExplodedNode *N = C.generateSink();
    280   if (!N)
    281     return;
    282   BugReport *Report = new BugReport(*BT_destroylock, Message, N);
    283   Report->addRange(CE->getArg(0)->getSourceRange());
    284   C.emitReport(Report);
    285 }
    286 
    287 void PthreadLockChecker::InitLock(CheckerContext &C, const CallExpr *CE,
    288                                   SVal Lock) const {
    289 
    290   const MemRegion *LockR = Lock.getAsRegion();
    291   if (!LockR)
    292     return;
    293 
    294   ProgramStateRef State = C.getState();
    295 
    296   const struct LockState *LState = State->get<LockMap>(LockR);
    297   if (!LState || LState->isDestroyed()) {
    298     State = State->set<LockMap>(LockR, LockState::getUnlocked());
    299     C.addTransition(State);
    300     return;
    301   }
    302 
    303   StringRef Message;
    304 
    305   if (LState->isLocked()) {
    306     Message = "This lock is still being held";
    307   } else {
    308     Message = "This lock has already been initialized";
    309   }
    310 
    311   if (!BT_initlock)
    312     BT_initlock.reset(new BugType(this, "Init invalid lock",
    313                                   "Lock checker"));
    314   ExplodedNode *N = C.generateSink();
    315   if (!N)
    316     return;
    317   BugReport *Report = new BugReport(*BT_initlock, Message, N);
    318   Report->addRange(CE->getArg(0)->getSourceRange());
    319   C.emitReport(Report);
    320 }
    321 
    322 void PthreadLockChecker::reportUseDestroyedBug(CheckerContext &C,
    323                                                const CallExpr *CE) const {
    324   if (!BT_destroylock)
    325     BT_destroylock.reset(new BugType(this, "Use destroyed lock",
    326                                      "Lock checker"));
    327   ExplodedNode *N = C.generateSink();
    328   if (!N)
    329     return;
    330   BugReport *Report = new BugReport(*BT_destroylock,
    331                                     "This lock has already been destroyed",
    332                                     N);
    333   Report->addRange(CE->getArg(0)->getSourceRange());
    334   C.emitReport(Report);
    335 }
    336 
    337 void ento::registerPthreadLockChecker(CheckerManager &mgr) {
    338   mgr.registerChecker<PthreadLockChecker>();
    339 }
    340