khazem updated this revision to Diff 77277.
khazem added a comment.
If a double-lock or double-release is detected, path notes are now emitted on
the _first_ lock or release event. Also updated the tests to check for these
notes.
https://reviews.llvm.org/D26340
Files:
include/clang/StaticAnalyzer/Checkers/Checkers.td
lib/StaticAnalyzer/Checkers/CMakeLists.txt
lib/StaticAnalyzer/Checkers/SpinLockChecker.cpp
test/Analysis/spinlock_correct.c
test/Analysis/spinlock_double_lock.c
test/Analysis/spinlock_double_release.c
Index: test/Analysis/spinlock_double_release.c
===================================================================
--- /dev/null
+++ test/Analysis/spinlock_double_release.c
@@ -0,0 +1,38 @@
+// RUN: %clang_cc1 -analyze -analyzer-output=text -analyzer-checker=magenta.SpinLock -verify %s
+
+typedef unsigned int lock_t;
+
+typedef struct S {
+ int a;
+ lock_t l;
+} S_t;
+
+static S_t st;
+
+void spin_lock(lock_t *lock);
+void spin_unlock(lock_t *lock);
+int bar();
+
+void bar1(lock_t *y) {
+ spin_unlock(y); // expected-note {{First unlocked here}}
+}
+
+void bar2(lock_t *x) {
+ spin_unlock(x); // expected-warning{{Execution path found where spinlock is unlocked twice in a row}}
+ // expected-note@-1 0+ {{Execution path found where spinlock is unlocked twice in a row}}
+}
+
+int foo() {
+ int a = bar();
+ if (a > 0) { // expected-note {{Assuming 'a' is > 0}} \
+ // expected-note {{Taking true branch}}
+ spin_lock(&st.l);
+ bar1(&st.l); // expected-note {{Calling 'bar1'}} \
+ expected-note {{Returning from 'bar1'}}
+ }
+
+ lock_t *c = &st.l;
+ bar2(c); // expected-note {{Calling 'bar2'}}
+ return 0;
+}
+
Index: test/Analysis/spinlock_double_lock.c
===================================================================
--- /dev/null
+++ test/Analysis/spinlock_double_lock.c
@@ -0,0 +1,26 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=magenta.SpinLock -analyzer-output=text -verify %s
+
+typedef unsigned int lock_t;
+
+static lock_t l;
+
+void spin_lock(lock_t *lock);
+void spin_unlock(lock_t *lock);
+int bar();
+
+int foo() {
+ int a = bar();
+ if (a > 0) // expected-note{{Assuming 'a' is > 0}} \
+ expected-note{{Taking true branch}}
+
+ spin_lock(&l); // expected-note{{First locked here}}
+ if (a > 10) // expected-note{{Assuming 'a' is > 10}} \
+ expected-note{{Taking true branch}}
+
+ spin_lock(&l); // expected-warning{{Execution path found where spinlock is locked twice in a row}}
+// expected-note@-1 0+ {{Execution path found where spinlock is locked twice in a row}}
+
+
+ return 0;
+}
+
Index: test/Analysis/spinlock_correct.c
===================================================================
--- /dev/null
+++ test/Analysis/spinlock_correct.c
@@ -0,0 +1,30 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=magenta.SpinLock -verify %s
+// expected-no-diagnostics
+
+typedef unsigned int lock_t;
+
+static lock_t l;
+
+void spin_lock(lock_t *lock);
+void spin_unlock(lock_t *lock);
+int bar();
+
+int foo() {
+ int a = bar();
+ if (a > 0) {
+ spin_lock(&l);
+ }
+
+ if (a < -10) {
+ spin_lock(&l);
+ }
+
+ if (a > 0)
+ spin_unlock(&l);
+
+ if (a < -10)
+ spin_unlock(&l);
+
+ return 0;
+}
+
Index: lib/StaticAnalyzer/Checkers/SpinLockChecker.cpp
===================================================================
--- /dev/null
+++ lib/StaticAnalyzer/Checkers/SpinLockChecker.cpp
@@ -0,0 +1,262 @@
+//== SpinLockChecker.cpp - SpinLock checker ---------------------*- C++ -*--==//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This defines SpinLockChecker, a check for the Magenta kernel. It
+// checks that there are no execution paths where spinlocks are locked
+// twice in a row, or unlocked twice in a row.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ClangSACheckers.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
+#include "clang/StaticAnalyzer/Core/CheckerManager.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "llvm/ADT/SmallString.h"
+
+using namespace clang;
+using namespace ento;
+
+namespace {
+
+struct LockInfo {
+
+ enum Kind { Locked, Released } K;
+
+ LockInfo(Kind kind) : K(kind) {}
+
+ bool operator==(const LockInfo &LI) const { return K == LI.K; }
+
+ void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(K); }
+
+ bool isLocked() const { return K == Locked; }
+
+ bool isReleased() const { return K == Released; }
+
+ static LockInfo getLocked() { return LockInfo(Locked); }
+
+ static LockInfo getReleased() { return LockInfo(Released); }
+
+};
+
+// When we detect a double-lock or double-release, we want to place a
+// diagnostic path note on the _first_ lock as well as the second one.
+// This is implemented in SpinLockBRVisitor. Since the logic is almost
+// identical for locking and releasing, we use the same VisitNode
+// function for both. The only difference is checking if the state has
+// changed from locked to unlocked (or the other way round) between the
+// last state and the current one; this is implemented by a
+// StateChangedDecision lambda function that is passed into the
+// SpinLockBRVisitor on construction.
+
+typedef std::function<bool (const LockInfo*, const LockInfo*)>
+ StateChangedDecision;
+
+class SpinLockBRVisitor final
+ : public BugReporterVisitorImpl<SpinLockBRVisitor> {
+
+ const MemRegion *SpinLockLocation;
+ const StringRef PathNoteMessage;
+ const StateChangedDecision StateChanged;
+ bool AlreadyEmitted;
+
+public:
+ SpinLockBRVisitor(const MemRegion *SpinLockLocation,
+ const StringRef PathNoteMessage,
+ const StateChangedDecision StateChanged) :
+ SpinLockLocation(SpinLockLocation), PathNoteMessage(PathNoteMessage),
+ StateChanged(StateChanged), AlreadyEmitted(false) {}
+
+ PathDiagnosticPiece *VisitNode(const ExplodedNode *Succ,
+ const ExplodedNode *Pred,
+ BugReporterContext &BRC,
+ BugReport &BR) override;
+
+ void Profile(llvm::FoldingSetNodeID &ID) const override {
+ ID.Add(SpinLockLocation);
+ }
+
+};
+
+}
+
+/// We keep track of the locks in a map. SpinLockMap maps the
+/// memory region of a spinlock to its status (locked, released).
+/// The reason that we keep track of spinlocks as memory region is
+/// that the lock/unlock functions take lock arguments as pointers.
+REGISTER_MAP_WITH_PROGRAMSTATE(SpinLockMap, const MemRegion *, LockInfo)
+
+namespace {
+
+class SpinLockChecker : public Checker<check::PreCall> {
+
+ /// When facing a spin_unlock function call, check the record of the
+ /// corresponding lock in SpinLockMap and make sure that there are no
+ /// problems such as double unlocks.
+ void processSpinUnlockCall(const CallEvent &Call, CheckerContext &C,
+ const MemRegion *SpinLockLocation) const;
+
+ /// When facing a spin_lock function call, check the record of the
+ /// corresponding lock in SpinLockMap and make sure that there are no
+ /// problems such as double locks.
+ void processSpinLockCall(const CallEvent &Call, CheckerContext &C,
+ const MemRegion *SpinLockLocation) const;
+ void reportDoubleLock(const CallEvent &Call, CheckerContext &C,
+ const MemRegion *Mem) const;
+ void reportDoubleUnlock(ExplodedNode *Node, CheckerContext &C,
+ const MemRegion *Mem) const;
+ std::unique_ptr<BugType> DoubleLockBugType;
+ std::unique_ptr<BugType> DoubleUnlockBugType;
+
+ const CallDescription SpinLockFuncName;
+ const CallDescription SpinUnlockFuncName;
+ const StringRef LockErrorCategory;
+
+public:
+ SpinLockChecker();
+ void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
+
+};
+}
+
+void ento::registerSpinLockChecker(CheckerManager &Mgr) {
+ Mgr.registerChecker<SpinLockChecker>();
+}
+
+SpinLockChecker::SpinLockChecker() :
+ SpinLockFuncName("spin_lock"), SpinUnlockFuncName("spin_unlock"),
+ LockErrorCategory("Lock Error") {
+ DoubleLockBugType.reset(
+ new BugType(this, "Double SpinLock", LockErrorCategory));
+
+ DoubleUnlockBugType.reset(
+ new BugType(this, "Double SpinUnlock", LockErrorCategory));
+}
+
+/// Run the necessary processing before a spin_lock/spin_unlock function call
+void SpinLockChecker::checkPreCall(const CallEvent &Call,
+ CheckerContext &C) const {
+ if (!Call.getCalleeIdentifier())
+ return;
+
+ if (!Call.isCalled(SpinLockFuncName) && !Call.isCalled(SpinUnlockFuncName))
+ return;
+
+ if (Call.getNumArgs() == 0)
+ return;
+
+ // Memory region of the spinlock
+ const MemRegion *SpinLockLocation = Call.getArgSVal(0).getAsRegion();
+ // If SpinLockLocation is NULL, this is likely due to changes in the
+ // signature of spin_lock/spin_unlock functions, and we have to update
+ // the checker accordingly. For now, we terminate with an error
+ // message.
+ if (!SpinLockLocation)
+ llvm_unreachable("No spinlock pointer passed to spin_lock/spin_unlock!");
+
+ if (Call.isCalled(SpinLockFuncName))
+ processSpinLockCall(Call, C, SpinLockLocation);
+ else
+ processSpinUnlockCall(Call, C, SpinLockLocation);
+}
+
+void SpinLockChecker::processSpinLockCall(
+ const CallEvent &Call, CheckerContext &C,
+ const MemRegion *SpinLockLocation) const {
+ ProgramStateRef St = C.getState();
+ const LockInfo *LI = St->get<SpinLockMap>(SpinLockLocation);
+ if (LI && LI->isLocked()) {
+ // This spinlock has been locked before!
+ reportDoubleLock(Call, C, SpinLockLocation);
+ return;
+ }
+
+ St = St->set<SpinLockMap>(SpinLockLocation, LockInfo::getLocked());
+ C.addTransition(St);
+}
+
+void SpinLockChecker::processSpinUnlockCall(
+ const CallEvent &Call, CheckerContext &C,
+ const MemRegion *SpinLockLocation) const {
+ ProgramStateRef St = C.getState();
+ const LockInfo *LI = St->get<SpinLockMap>(SpinLockLocation);
+ if (LI && LI->isReleased()) {
+ // Unlocking a key twice! Does not cause an error, but may be an
+ // indication of an incorrect logic (maybe the spinlock was supposed to
+ // be locked again before the second unlocking attempt).
+ ExplodedNode *Node = C.generateNonFatalErrorNode(St);
+ if (!Node)
+ return;
+ reportDoubleUnlock(Node, C, SpinLockLocation);
+ }
+
+ St = St->set<SpinLockMap>(SpinLockLocation, LockInfo::getReleased());
+ C.addTransition(St);
+}
+
+void SpinLockChecker::reportDoubleUnlock(
+ ExplodedNode *Node, CheckerContext &C,
+ const MemRegion *SpinLockLocation) const {
+ auto Report = llvm::make_unique<BugReport>(
+ *DoubleUnlockBugType,
+ "Execution path found where spinlock is unlocked twice in a row", Node);
+ Report->markInteresting(SpinLockLocation);
+ Report->addVisitor(llvm::make_unique<SpinLockBRVisitor>(SpinLockLocation,
+ "First unlocked here", [](const LockInfo *Succ, const LockInfo *Pred)
+ { return Succ->isReleased() && (!Pred || !Pred->isReleased()); }));
+ C.emitReport(std::move(Report));
+}
+
+void SpinLockChecker::reportDoubleLock(
+ const CallEvent &Call, CheckerContext &C,
+ const MemRegion *SpinLockLocation) const {
+ ExplodedNode *Node = C.generateErrorNode();
+ if (!Node)
+ return;
+ auto Report = llvm::make_unique<BugReport>(
+ *DoubleLockBugType,
+ "Execution path found where spinlock is locked twice in a row", Node);
+ Report->addRange(Call.getSourceRange());
+ Report->markInteresting(SpinLockLocation);
+ Report->addVisitor(llvm::make_unique<SpinLockBRVisitor>(SpinLockLocation,
+ "First locked here", [](const LockInfo *Succ, const LockInfo *Pred)
+ { return Succ->isLocked() && (!Pred || !Pred->isLocked()); }));
+ C.emitReport(std::move(Report));
+}
+
+PathDiagnosticPiece *SpinLockBRVisitor::VisitNode(const ExplodedNode *Succ,
+ const ExplodedNode *Pred,
+ BugReporterContext &BRC,
+ BugReport &BR) {
+ if (AlreadyEmitted)
+ return nullptr;
+
+ const LockInfo *PredInfo = Pred->getState()->
+ get<SpinLockMap>(SpinLockLocation);
+ const LockInfo *SuccInfo = Succ->getState()->
+ get<SpinLockMap>(SpinLockLocation);
+
+ if (!SuccInfo)
+ return nullptr;
+
+ if (StateChanged(SuccInfo, PredInfo)){
+ AlreadyEmitted = true;
+
+ ProgramPoint P = Succ->getLocation();
+ PathDiagnosticLocation L =
+ PathDiagnosticLocation::create(P, BRC.getSourceManager());
+
+ if (!L.isValid() || !L.asLocation().isValid())
+ return nullptr;
+
+ return new PathDiagnosticEventPiece(L, PathNoteMessage);
+ }
+
+ return nullptr;
+}
Index: lib/StaticAnalyzer/Checkers/CMakeLists.txt
===================================================================
--- lib/StaticAnalyzer/Checkers/CMakeLists.txt
+++ lib/StaticAnalyzer/Checkers/CMakeLists.txt
@@ -70,6 +70,7 @@
ReturnPointerRangeChecker.cpp
ReturnUndefChecker.cpp
SimpleStreamChecker.cpp
+ SpinLockChecker.cpp
StackAddrEscapeChecker.cpp
StdLibraryFunctionsChecker.cpp
StreamChecker.cpp
Index: include/clang/StaticAnalyzer/Checkers/Checkers.td
===================================================================
--- include/clang/StaticAnalyzer/Checkers/Checkers.td
+++ include/clang/StaticAnalyzer/Checkers/Checkers.td
@@ -82,6 +82,8 @@
def CloneDetectionAlpha : Package<"clone">, InPackage<Alpha>, Hidden;
+def Magenta : Package<"magenta">;
+
//===----------------------------------------------------------------------===//
// Core Checkers.
//===----------------------------------------------------------------------===//
@@ -722,3 +724,14 @@
} // end "clone"
+//===----------------------------------------------------------------------===//
+// Magenta checkers.
+//===----------------------------------------------------------------------===//
+
+let ParentPackage = Magenta in {
+
+def SpinLockChecker : Checker<"SpinLock">,
+ HelpText<"Check for correct handling of spinlocks">,
+ DescFile<"SpinLockChecker.cpp">;
+
+} // end "magenta"
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
