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 class PthreadLockChecker : public Checker< check::PostStmt<CallExpr> > {
  28   mutable OwningPtr<BugType> BT_doublelock;
  29   mutable 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 REGISTER_LIST_WITH_PROGRAMSTATE(LockSet, const MemRegion *)
  47
  48
  49 void PthreadLockChecker::checkPostStmt(const CallExpr *CE,
  50                                        CheckerContext &C) const {
  51   ProgramStateRef state = C.getState();
  52   const LocationContext *LCtx = C.getLocationContext();
  53   StringRef FName = C.getCalleeName(CE);
  54   if (FName.empty())
  55     return;
  56
  57   if (CE->getNumArgs() != 1)
  58     return;
  59
  60   if (FName == "pthread_mutex_lock" ||
  61       FName == "pthread_rwlock_rdlock" ||
  62       FName == "pthread_rwlock_wrlock")
  63     AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
  64                 false, PthreadSemantics);
  65   else if (FName == "lck_mtx_lock" ||
  66            FName == "lck_rw_lock_exclusive" ||
  67            FName == "lck_rw_lock_shared")
  68     AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
  69                 false, XNUSemantics);
  70   else if (FName == "pthread_mutex_trylock" ||
  71            FName == "pthread_rwlock_tryrdlock" ||
  72            FName == "pthread_rwlock_tryrwlock")
  73     AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
  74                 true, PthreadSemantics);
  75   else if (FName == "lck_mtx_try_lock" ||
  76            FName == "lck_rw_try_lock_exclusive" ||
  77            FName == "lck_rw_try_lock_shared")
  78     AcquireLock(C, CE, state->getSVal(CE->getArg(0), LCtx),
  79                 true, XNUSemantics);
  80   else if (FName == "pthread_mutex_unlock" ||
  81            FName == "pthread_rwlock_unlock" ||
  82            FName == "lck_mtx_unlock" ||
  83            FName == "lck_rw_done")
  84     ReleaseLock(C, CE, state->getSVal(CE->getArg(0), LCtx));
  85 }
  86
  87 void PthreadLockChecker::AcquireLock(CheckerContext &C, const CallExpr *CE,
  88                                      SVal lock, bool isTryLock,
  89                                      enum LockingSemantics semantics) const {
  90
  91   const MemRegion *lockR = lock.getAsRegion();
  92   if (!lockR)
  93     return;
  94
  95   ProgramStateRef state = C.getState();
  96
  97   SVal X = state->getSVal(CE, C.getLocationContext());
  98   if (X.isUnknownOrUndef())
  99     return;
 100
 101   DefinedSVal retVal = X.castAs<DefinedSVal>();
 102
 103   if (state->contains<LockSet>(lockR)) {
 104     if (!BT_doublelock)
 105       BT_doublelock.reset(new BugType("Double locking", "Lock checker"));
 106     ExplodedNode *N = C.generateSink();
 107     if (!N)
 108       return;
 109     BugReport *report = new BugReport(*BT_doublelock,
 110                                                       "This lock has already "
 111                                                       "been acquired", N);
 112     report->addRange(CE->getArg(0)->getSourceRange());
 113     C.emitReport(report);
 114     return;
 115   }
 116
 117   ProgramStateRef lockSucc = state;
 118   if (isTryLock) {
 119     // Bifurcate the state, and allow a mode where the lock acquisition fails.
 120     ProgramStateRef lockFail;
 121     switch (semantics) {
 122     case PthreadSemantics:
 123       llvm::tie(lockFail, lockSucc) = state->assume(retVal);
 124       break;
 125     case XNUSemantics:
 126       llvm::tie(lockSucc, lockFail) = state->assume(retVal);
 127       break;
 128     default:
 129       llvm_unreachable("Unknown tryLock locking semantics");
 130     }
 131     assert(lockFail && lockSucc);
 132     C.addTransition(lockFail);
 133
 134   } else if (semantics == PthreadSemantics) {
 135     // Assume that the return value was 0.
 136     lockSucc = state->assume(retVal, false);
 137     assert(lockSucc);
 138
 139   } else {
 140     // XNU locking semantics return void on non-try locks
 141     assert((semantics == XNUSemantics) && "Unknown locking semantics");
 142     lockSucc = state;
 143   }
 144
 145   // Record that the lock was acquired.
 146   lockSucc = lockSucc->add<LockSet>(lockR);
 147   C.addTransition(lockSucc);
 148 }
 149
 150 void PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE,
 151                                      SVal lock) const {
 152
 153   const MemRegion *lockR = lock.getAsRegion();
 154   if (!lockR)
 155     return;
 156
 157   ProgramStateRef state = C.getState();
 158   LockSetTy LS = state->get<LockSet>();
 159
 160   // FIXME: Better analysis requires IPA for wrappers.
 161   // FIXME: check for double unlocks
 162   if (LS.isEmpty())
 163     return;
 164
 165   const MemRegion *firstLockR = LS.getHead();
 166   if (firstLockR != lockR) {
 167     if (!BT_lor)
 168       BT_lor.reset(new BugType("Lock order reversal", "Lock checker"));
 169     ExplodedNode *N = C.generateSink();
 170     if (!N)
 171       return;
 172     BugReport *report = new BugReport(*BT_lor,
 173                                                       "This was not the most "
 174                                                       "recently acquired lock. "
 175                                                       "Possible lock order "
 176                                                       "reversal", N);
 177     report->addRange(CE->getArg(0)->getSourceRange());
 178     C.emitReport(report);
 179     return;
 180   }
 181
 182   // Record that the lock was released.
 183   state = state->set<LockSet>(LS.getTail());
 184   C.addTransition(state);
 185 }
 186
 187
 188 void ento::registerPthreadLockChecker(CheckerManager &mgr) {
 189   mgr.registerChecker<PthreadLockChecker>();
 190 }