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