1 files changed, 122 insertions, 63 deletions

diff --git a/lib/StaticAnalyzer/Checkers/PthreadLockChecker.cpp b/lib/StaticAnalyzer/Checkers/PthreadLockChecker.cpp
index 74199bb1f6db..c02b5b14ca64 100644
--- a/lib/StaticAnalyzer/Checkers/PthreadLockChecker.cpp
+++ b/lib/StaticAnalyzer/Checkers/PthreadLockChecker.cpp
@@ -1,4 +1,4 @@
-//===--- PthreadLockChecker.h - Undefined arguments checker ----*- C++ -*--===//
+//===--- PthreadLockChecker.cpp - Check for locking problems ---*- C++ -*--===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -7,8 +7,8 @@
 //
 //===----------------------------------------------------------------------===//
 //
-// This defines PthreadLockChecker, a simple lock -> unlock checker.  Eventually
-// this shouldn't be registered with ExprEngineInternalChecks.
+// This defines PthreadLockChecker, a simple lock -> unlock checker.
+// Also handles XNU locks, which behave similarly enough to share code.
 //
 //===----------------------------------------------------------------------===//
 
@@ -16,25 +16,29 @@
 #include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
-#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
-#include "clang/StaticAnalyzer/Core/PathSensitive/GRStateTrait.h"
-#include "llvm/ADT/ImmutableSet.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
+#include "llvm/ADT/ImmutableList.h"
 
 using namespace clang;
 using namespace ento;
 
 namespace {
-class PthreadLockChecker
-  : public Checker< check::PostStmt<CallExpr> > {
+class PthreadLockChecker : public Checker< check::PostStmt<CallExpr> > {
+  mutable llvm::OwningPtr<BugType> BT_doublelock;
+  mutable llvm::OwningPtr<BugType> BT_lor;
+  enum LockingSemantics {
+    NotApplicable = 0,
+    PthreadSemantics,
+    XNUSemantics
+  };
 public:
   void checkPostStmt(const CallExpr *CE, CheckerContext &C) const;
     
-  void AcquireLock(CheckerContext &C, const CallExpr *CE,
-                   SVal lock, bool isTryLock) const;
+  void AcquireLock(CheckerContext &C, const CallExpr *CE, SVal lock,
+                   bool isTryLock, enum LockingSemantics semantics) const;
     
-  void ReleaseLock(CheckerContext &C, const CallExpr *CE,
-                    SVal lock) const;
-
+  void ReleaseLock(CheckerContext &C, const CallExpr *CE, SVal lock) const;
 };
 } // end anonymous namespace
 
@@ -42,80 +46,117 @@ public:
 namespace { class LockSet {}; }
 namespace clang {
 namespace ento {
-template <> struct GRStateTrait<LockSet> :
-  public GRStatePartialTrait<llvm::ImmutableSet<const MemRegion*> > {
-    static void* GDMIndex() { static int x = 0; return &x; }
+template <> struct ProgramStateTrait<LockSet> :
+  public ProgramStatePartialTrait<llvm::ImmutableList<const MemRegion*> > {
+    static void *GDMIndex() { static int x = 0; return &x; }
 };
-} // end GR namespace
+} // end of ento (ProgramState) namespace
 } // end clang namespace
 
 
 void PthreadLockChecker::checkPostStmt(const CallExpr *CE,
                                        CheckerContext &C) const {
-  const GRState *state = C.getState();
+  const ProgramState *state = C.getState();
   const Expr *Callee = CE->getCallee();
-  const FunctionTextRegion *R =
-    dyn_cast_or_null<FunctionTextRegion>(state->getSVal(Callee).getAsRegion());
-  
-  if (!R)
+  const FunctionDecl *FD = state->getSVal(Callee).getAsFunctionDecl();
+
+  if (!FD)
     return;
-  
-  IdentifierInfo *II = R->getDecl()->getIdentifier();
+
+  // Get the name of the callee.
+  IdentifierInfo *II = FD->getIdentifier();
   if (!II)   // if no identifier, not a simple C function
     return;
-  llvm::StringRef FName = II->getName();
-  
-  if (FName == "pthread_mutex_lock") {
-    if (CE->getNumArgs() != 1)
-      return;
-    AcquireLock(C, CE, state->getSVal(CE->getArg(0)), false);
-  }
-  else if (FName == "pthread_mutex_trylock") {
-    if (CE->getNumArgs() != 1)
-      return;
-    AcquireLock(C, CE, state->getSVal(CE->getArg(0)), true);
-  }  
-  else if (FName == "pthread_mutex_unlock") {
-    if (CE->getNumArgs() != 1)
-      return;
+  StringRef FName = II->getName();
+
+  if (CE->getNumArgs() != 1)
+    return;
+
+  if (FName == "pthread_mutex_lock" ||
+      FName == "pthread_rwlock_rdlock" ||
+      FName == "pthread_rwlock_wrlock")
+    AcquireLock(C, CE, state->getSVal(CE->getArg(0)), false, PthreadSemantics);
+  else if (FName == "lck_mtx_lock" ||
+           FName == "lck_rw_lock_exclusive" ||
+           FName == "lck_rw_lock_shared") 
+    AcquireLock(C, CE, state->getSVal(CE->getArg(0)), false, XNUSemantics);
+  else if (FName == "pthread_mutex_trylock" ||
+           FName == "pthread_rwlock_tryrdlock" ||
+           FName == "pthread_rwlock_tryrwlock")
+    AcquireLock(C, CE, state->getSVal(CE->getArg(0)), true, PthreadSemantics);
+  else if (FName == "lck_mtx_try_lock" ||
+           FName == "lck_rw_try_lock_exclusive" ||
+           FName == "lck_rw_try_lock_shared")
+    AcquireLock(C, CE, state->getSVal(CE->getArg(0)), true, XNUSemantics);
+  else if (FName == "pthread_mutex_unlock" ||
+           FName == "pthread_rwlock_unlock" ||
+           FName == "lck_mtx_unlock" ||
+           FName == "lck_rw_done")
     ReleaseLock(C, CE, state->getSVal(CE->getArg(0)));
-  }
 }
 
 void PthreadLockChecker::AcquireLock(CheckerContext &C, const CallExpr *CE,
-                                     SVal lock, bool isTryLock) const {
+                                     SVal lock, bool isTryLock,
+                                     enum LockingSemantics semantics) const {
   
   const MemRegion *lockR = lock.getAsRegion();
   if (!lockR)
     return;
   
-  const GRState *state = C.getState();
+  const ProgramState *state = C.getState();
   
   SVal X = state->getSVal(CE);
   if (X.isUnknownOrUndef())
     return;
   
   DefinedSVal retVal = cast<DefinedSVal>(X);
-  const GRState *lockSucc = state;
-  
+
+  if (state->contains<LockSet>(lockR)) {
+    if (!BT_doublelock)
+      BT_doublelock.reset(new BugType("Double locking", "Lock checker"));
+    ExplodedNode *N = C.generateSink();
+    if (!N)
+      return;
+    BugReport *report = new BugReport(*BT_doublelock,
+                                                      "This lock has already "
+                                                      "been acquired", N);
+    report->addRange(CE->getArg(0)->getSourceRange());
+    C.EmitReport(report);
+    return;
+  }
+
+  const ProgramState *lockSucc = state;
   if (isTryLock) {
-      // Bifurcate the state, and allow a mode where the lock acquisition fails.
-    const GRState *lockFail;
-    llvm::tie(lockFail, lockSucc) = state->assume(retVal);    
+    // Bifurcate the state, and allow a mode where the lock acquisition fails.
+    const ProgramState *lockFail;
+    switch (semantics) {
+    case PthreadSemantics:
+      llvm::tie(lockFail, lockSucc) = state->assume(retVal);    
+      break;
+    case XNUSemantics:
+      llvm::tie(lockSucc, lockFail) = state->assume(retVal);    
+      break;
+    default:
+      llvm_unreachable("Unknown tryLock locking semantics");
+      break;
+    }
     assert(lockFail && lockSucc);
-    C.addTransition(C.generateNode(CE, lockFail));
-  }
-  else {
-      // Assume that the return value was 0.
+    C.addTransition(lockFail);
+
+  } else if (semantics == PthreadSemantics) {
+    // Assume that the return value was 0.
     lockSucc = state->assume(retVal, false);
     assert(lockSucc);
+
+  } else {
+    // XNU locking semantics return void on non-try locks
+    assert((semantics == XNUSemantics) && "Unknown locking semantics");
+    lockSucc = state;
   }
   
-    // Record that the lock was acquired.  
+  // Record that the lock was acquired.  
   lockSucc = lockSucc->add<LockSet>(lockR);
-  
-  C.addTransition(lockSucc != state ? C.generateNode(CE, lockSucc) :
-                  C.getPredecessor());
+  C.addTransition(lockSucc);
 }
 
 void PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE,
@@ -125,19 +166,37 @@ void PthreadLockChecker::ReleaseLock(CheckerContext &C, const CallExpr *CE,
   if (!lockR)
     return;
   
-  const GRState *state = C.getState();
+  const ProgramState *state = C.getState();
+  llvm::ImmutableList<const MemRegion*> LS = state->get<LockSet>();
 
-  // Record that the lock was released.  
-  // FIXME: Handle unlocking locks that were never acquired.  This may
-  // require IPA for wrappers.
-  const GRState *unlockState = state->remove<LockSet>(lockR);
-  
-  if (state == unlockState)
+  // FIXME: Better analysis requires IPA for wrappers.
+  // FIXME: check for double unlocks
+  if (LS.isEmpty())
     return;
   
-  C.addTransition(C.generateNode(CE, unlockState));  
+  const MemRegion *firstLockR = LS.getHead();
+  if (firstLockR != lockR) {
+    if (!BT_lor)
+      BT_lor.reset(new BugType("Lock order reversal", "Lock checker"));
+    ExplodedNode *N = C.generateSink();
+    if (!N)
+      return;
+    BugReport *report = new BugReport(*BT_lor,
+                                                      "This was not the most "
+                                                      "recently acquired lock. "
+                                                      "Possible lock order "
+                                                      "reversal", N);
+    report->addRange(CE->getArg(0)->getSourceRange());
+    C.EmitReport(report);
+    return;
+  }
+
+  // Record that the lock was released. 
+  state = state->set<LockSet>(LS.getTail());
+  C.addTransition(state);
 }
 
+
 void ento::registerPthreadLockChecker(CheckerManager &mgr) {
   mgr.registerChecker<PthreadLockChecker>();
 }