[analysis] Add checks for double-locking and lock order reversal bugs for
pthread and XNU locks. Patch by Rui Paulo!
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@135515 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/StaticAnalyzer/Checkers/PthreadLockChecker.cpp b/lib/StaticAnalyzer/Checkers/PthreadLockChecker.cpp
index 74199bb..df54d49 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
//
@@ -17,24 +17,29 @@
#include "clang/StaticAnalyzer/Core/CheckerManager.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/GRStateTrait.h"
-#include "llvm/ADT/ImmutableSet.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
@@ -43,7 +48,7 @@
namespace clang {
namespace ento {
template <> struct GRStateTrait<LockSet> :
- public GRStatePartialTrait<llvm::ImmutableSet<const MemRegion*> > {
+ public GRStatePartialTrait<llvm::ImmutableList<const MemRegion*> > {
static void* GDMIndex() { static int x = 0; return &x; }
};
} // end GR namespace
@@ -64,26 +69,35 @@
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;
+
+ 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)
@@ -96,26 +110,55 @@
return;
DefinedSVal retVal = cast<DefinedSVal>(X);
- const GRState *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);
- assert(lockFail && lockSucc);
- C.addTransition(C.generateNode(CE, lockFail));
+
+ llvm::ImmutableList<const MemRegion*> LS = state->get<LockSet>();
+
+ if (state->contains<LockSet>(lockR)) {
+ if (!BT_doublelock)
+ BT_doublelock.reset(new BugType("Double locking", "Lock checker"));
+ ExplodedNode *N = C.generateSink();
+ if (!N)
+ return;
+ EnhancedBugReport *report = new EnhancedBugReport(*BT_doublelock,
+ "This lock has already "
+ "been acquired", N);
+ report->addRange(CE->getArg(0)->getSourceRange());
+ C.EmitReport(report);
+ return;
}
- else {
- // Assume that the return value was 0.
+
+ const GRState *lockSucc = state;
+ if (isTryLock) {
+ // Bifurcate the state, and allow a mode where the lock acquisition fails.
+ const GRState *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(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,
@@ -126,18 +169,36 @@
return;
const GRState *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;
+ EnhancedBugReport *report = new EnhancedBugReport(*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>();
}