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/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 }