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/Checker.h"
     17 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
     18 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
     19 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.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 class PthreadLockChecker : public Checker< check::PostStmt<CallExpr> > {
     28   mutable llvm::OwningPtr<BugType> BT_doublelock;
     29   mutable llvm::OwningPtr<BugType> BT_lor;
     30   enum LockingSemantics {
     31     NotApplicable = 0,
     32     PthreadSemantics,
     33     XNUSemantics
     34   };
     35 public:
     36   void checkPostStmt(const CallExpr *CE, CheckerContext &C) const;
     37 
     38   void AcquireLock(CheckerContext &C, const CallExpr *CE, SVal lock,
     39                    bool isTryLock, enum LockingSemantics semantics) const;
     40 
     41   void ReleaseLock(CheckerContext &C, const CallExpr *CE, SVal lock) const;
     42 };
     43 } // end anonymous namespace
     44 
     45 // GDM Entry for tracking lock state.
     46 namespace { class LockSet {}; }
     47 namespace clang {
     48 namespace ento {
     49 template <> struct ProgramStateTrait<LockSet> :
     50   public ProgramStatePartialTrait<llvm::ImmutableList<const MemRegion*> > {
     51     static void *GDMIndex() { static int x = 0; return &x; }
     52 };
     53 } // end of ento (ProgramState) namespace
     54 } // end clang namespace
     55 
     56 
     57 void PthreadLockChecker::checkPostStmt(const CallExpr *CE,
     58                                        CheckerContext &C) const {
     59   const ProgramState *state = C.getState();
     60   const Expr *Callee = CE->getCallee();
     61   const FunctionDecl *FD = state->getSVal(Callee).getAsFunctionDecl();
     62 
     63   if (!FD)
     64     return;
     65 
     66   // Get the name of the callee.
     67   IdentifierInfo *II = FD->getIdentifier();
     68   if (!II)   // if no identifier, not a simple C function
     69     return;
     70   StringRef FName = II->getName();
     71 
     72   if (CE->getNumArgs() != 1)
     73     return;
     74 
     75   if (FName == "pthread_mutex_lock" ||
     76       FName == "pthread_rwlock_rdlock" ||
     77       FName == "pthread_rwlock_wrlock")
     78     AcquireLock(C, CE, state->getSVal(CE->getArg(0)), false, PthreadSemantics);
     79   else if (FName == "lck_mtx_lock" ||
     80            FName == "lck_rw_lock_exclusive" ||
     81            FName == "lck_rw_lock_shared")
     82     AcquireLock(C, CE, state->getSVal(CE->getArg(0)), false, XNUSemantics);
     83   else if (FName == "pthread_mutex_trylock" ||
     84            FName == "pthread_rwlock_tryrdlock" ||
     85            FName == "pthread_rwlock_tryrwlock")
     86     AcquireLock(C, CE, state->getSVal(CE->getArg(0)), true, PthreadSemantics);
     87   else if (FName == "lck_mtx_try_lock" ||
     88            FName == "lck_rw_try_lock_exclusive" ||
     89            FName == "lck_rw_try_lock_shared")
     90     AcquireLock(C, CE, state->getSVal(CE->getArg(0)), true, XNUSemantics);
     91   else if (FName == "pthread_mutex_unlock" ||
     92            FName == "pthread_rwlock_unlock" ||
     93            FName == "lck_mtx_unlock" ||
     94            FName == "lck_rw_done")
     95     ReleaseLock(C, CE, state->getSVal(CE->getArg(0)));
     96 }
     97 
     98 void PthreadLockChecker::AcquireLock(CheckerContext &C, const CallExpr *CE,
     99                                      SVal lock, bool isTryLock,
    100                                      enum LockingSemantics semantics) const {
    101 
    102   const MemRegion *lockR = lock.getAsRegion();
    103   if (!lockR)
    104     return;
    105 
    106   const ProgramState *state = C.getState();
    107 
    108   SVal X = state->getSVal(CE);
    109   if (X.isUnknownOrUndef())
    110     return;
    111 
    112   DefinedSVal retVal = cast<DefinedSVal>(X);
    113 
    114   if (state->contains<LockSet>(lockR)) {
    115     if (!BT_doublelock)
    116       BT_doublelock.reset(new BugType("Double locking", "Lock checker"));
    117     ExplodedNode *N = C.generateSink();
    118     if (!N)
    119       return;
    120     BugReport *report = new BugReport(*BT_doublelock,
    121                                                       "This lock has already "
    122                                                       "been acquired", N);
    123     report->addRange(CE->getArg(0)->getSourceRange());
    124     C.EmitReport(report);
    125     return;
    126   }
    127 
    128   const ProgramState *lockSucc = state;
    129   if (isTryLock) {
    130     // Bifurcate the state, and allow a mode where the lock acquisition fails.
    131     const ProgramState *lockFail;
    132     switch (semantics) {
    133     case PthreadSemantics:
    134       llvm::tie(lockFail, lockSucc) = state->assume(retVal);
    135       break;
    136     case XNUSemantics:
    137       llvm::tie(lockSucc, lockFail) = state->assume(retVal);
    138       break;
    139     default:
    140       llvm_unreachable("Unknown tryLock locking semantics");
    141       break;
    142     }
    143     assert(lockFail && lockSucc);
    144     C.addTransition(lockFail);
    145 
    146   } else if (semantics == PthreadSemantics) {
    147     // Assume that the return value was 0.
    148     lockSucc = state->assume(retVal, false);
    149     assert(lockSucc);
    150 
    151   } else {
    152     // XNU locking semantics return void on non-try locks
    153     assert((semantics == XNUSemantics) && "Unknown locking semantics");
    154     lockSucc = state;
    155   }
    156 
    157   // Record that the lock was acquired.
    158   lockSucc = lockSucc->add<LockSet>(lockR);
    159   C.addTransition(lockSucc);
    160 }
    161 
    162 void PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE,
    163                                      SVal lock) const {
    164 
    165   const MemRegion *lockR = lock.getAsRegion();
    166   if (!lockR)
    167     return;
    168 
    169   const ProgramState *state = C.getState();
    170   llvm::ImmutableList<const MemRegion*> LS = state->get<LockSet>();
    171 
    172   // FIXME: Better analysis requires IPA for wrappers.
    173   // FIXME: check for double unlocks
    174   if (LS.isEmpty())
    175     return;
    176 
    177   const MemRegion *firstLockR = LS.getHead();
    178   if (firstLockR != lockR) {
    179     if (!BT_lor)
    180       BT_lor.reset(new BugType("Lock order reversal", "Lock checker"));
    181     ExplodedNode *N = C.generateSink();
    182     if (!N)
    183       return;
    184     BugReport *report = new BugReport(*BT_lor,
    185                                                       "This was not the most "
    186                                                       "recently acquired lock. "
    187                                                       "Possible lock order "
    188                                                       "reversal", N);
    189     report->addRange(CE->getArg(0)->getSourceRange());
    190     C.EmitReport(report);
    191     return;
    192   }
    193 
    194   // Record that the lock was released.
    195   state = state->set<LockSet>(LS.getTail());
    196   C.addTransition(state);
    197 }
    198 
    199 
    200 void ento::registerPthreadLockChecker(CheckerManager &mgr) {
    201   mgr.registerChecker<PthreadLockChecker>();
    202 }
    203