[analyzer] Add SpinLockChecker for the Magenta kernel

[khazem]

Summary

This patch adds a new Static Analyzer checker for the correct use of spin locks in the Magenta kernel. The checker checks that a lock is not locked twice in a row, nor unlocked twice in a row.

The checker was authored by Farid Molazem Tabrizi.

[khazem]

Minor edit, the list of libraries in CMakeLists.txt is now in alphabetical order.

[dcoughlin]

Thanks for upstreaming this! (And it was great to meet you at the developer conference.)

lib/StaticAnalyzer/Checkers/SpinLockChecker.cpp

62

In the LLVM/clang codebase we try very hard to avoid running constructors for globals, as this can have adverse effects on startup time. Typically we try to lazily initialize things like these or have them refer to constant data that the linker will handle automatically (such as a c string constant).

Can these be a C string constant instead? Or can they be instance members of the SpinLockChecker class? (See the note about CallDescription below, which may be helpful.)

119

In the analyzer codebase we try to use IdentifierInfo pointers to compare identifiers. Since these are interned it lets us perform pointer comparisons rather than expensive string comparisons.

There is a CallDescription class in CallEvent.h that encapsulates this logic. You can see an example of how it is used in SimpleStreamChecker.cpp.

183

For these kinds of diagnostics it is often very helpful to emit a path note indicating where the first unlock was.

To do this, you can add a custom bug report visitor that will get called on each node in the path to a diagnostic and emit a note, if appropriate. In this case you would look for nodes with calls to unlock taking the same region as the one you are now reporting for.

There is an example of how to implement a bug report visitor in 'SuperDeallocBRVisitor'.

193

It would be good to emit a path note for the first lock, too.

[khazem]

Good to meet you too, thanks for the useful comments and pointers to helpful examples! I'm going to update the diff twice: the first one to address your first two comments, and the second one to address your last two.

[khazem]

The strings for Spin{Unl,L}ockFuncName and LockErrorCategory are now initialized when constructing a SpinLockChecker object rather than being static globals, in order to avoid adverse effects on startup time.

Also, the Spin*FuncName variables are now of type CallDescription. This is to enable pointer rather than string comparisons of the function name.

[khazem]

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.

[khazem]

Devin, based on Artem's review of the other checker that I have posted [1] I am wondering about merging both this SpinLockChecker and the MutexChecker into PthreadLockChecker. Do you think it is still worth landing this SpinLockChecker, or do you suppose that abandoning this patch and working on merging all the checkers would be a good idea? I've noted how the checkers might be merged in my reply to Artem: [2].

[1] https://reviews.llvm.org/D26342
[2] https://reviews.llvm.org/D26342#590881

[dcoughlin]

Thanks for adding the path notes and adopting CallDescription. I've added some additional comments inline, which are mostly minor nits.

Two additional important changes -- and I should have noted these in the initial review -- is that it would be good to remove a MemRegion mapping from the program state when a MemRegion escapes and also when it becomes dead. These should both be small changes.

Escaping
Removing the mapping when the lock escapes will avoid false positives when the lock is passed to a function that the analyzer doesn't inline (for example, if it is in another translation unit) that unlocks it:

void foo(lock_t *l) {
  spin_lock(l);
  ...
  do_stuff_and_unlock(l);
  ..
  spin_lock();
}

If do_stuff_and_unlock() is in another translation unit the analyzer won't see the unlock and so will report a false positive if you don't remove the mapping when the lock escapes.

If you remove the mapping when the lock escapes, the analyzer will optimistically assume the best-case scenario the next time it sees a lock or unlock operation. There is an example of how to do this in ObjCContainersChecker::checkPointerEscape()

Removing Dead Symbols
It is also important for performance to remove mappings that are no longer relevant. There is a cost to keep around mappings in the program state: both memory (because the analyzer keeps some states around for use in the bug reporter visitor) and time (because the analyzer has to iterate over the map when determining whether two states are the same). There is an example of how to do this in ObjCLoopChecker::checkDeadSymbols.

include/clang/StaticAnalyzer/Checkers/Checkers.td

728

Nit: I think it would good to add a little bit more context to disambiguate so that future maintainers will be able to do a web search to learn about what these checkers are for. For example, maybe something like "Checkers for the Magenta kernel"?

lib/StaticAnalyzer/Checkers/SpinLockChecker.cpp

208

Nit: it is enough to have the message be "Spinlock is unlocked twice in a row". I don't think it is necessary to explicitly mention the execution path (especially now that you have a path note for the first unlock).

224

Nit: Same here.

test/Analysis/spinlock_correct.c

1

Nit: Typically in the analyzer codebase we try to keep the number of test files to a minimum. Can these three test files all be combined into one?

1

Another nit: The analyzer relies on always having core checkers enabled because they model important aspects of the language. You should change this to ... -analyzer-checker=core,magenta.SpinLock ...

[dcoughlin]

In D26340#590882, @khazem wrote:

Devin, based on Artem's review of the other checker that I have posted [1] I am wondering about merging both this SpinLockChecker and the MutexChecker into PthreadLockChecker. Do you think it is still worth landing this SpinLockChecker, or do you suppose that abandoning this patch and working on merging all the checkers would be a good idea? I've noted how the checkers might be merged in my reply to Artem: [2].

Merging seems reasonable to me. It is also a good way to make it less likely that the Magenta checkers accidentally regress since the main logic of the checker will be exercised when checking a much more common API.

include/clang/StaticAnalyzer/Checkers/Checkers.td

 
 def MPI : Package<"mpi">, InPackage<OptIn>;
 
 def LLVM : Package<"llvm">;
 def Debug : Package<"debug">;
 
 def CloneDetectionAlpha : Package<"clone">, InPackage<Alpha>, Hidden;
 
+def Magenta : Package<"magenta">;
+
 //===----------------------------------------------------------------------===//
 // Core Checkers.
 //===----------------------------------------------------------------------===//
 
 let ParentPackage = Core in {
 
 def DereferenceChecker : Checker<"NullDereference">,
   HelpText<"Check for dereferences of null pointers">,

 let ParentPackage = CloneDetectionAlpha in {
 
 def CloneChecker : Checker<"CloneChecker">,
   HelpText<"Reports similar pieces of code.">,
   DescFile<"CloneChecker.cpp">;
 
 } // end "clone"
 
+//===----------------------------------------------------------------------===//
+// Magenta checkers.
+//===----------------------------------------------------------------------===//
+
+let ParentPackage = Magenta in {
+
+def SpinLockChecker : Checker<"SpinLock">,
+  HelpText<"Check for correct handling of spinlocks">,
+  DescFile<"SpinLockChecker.cpp">;
+
+} // end "magenta"

lib/StaticAnalyzer/Checkers/CMakeLists.txt

add_clang_library(clangStaticAnalyzerCheckers
   PaddingChecker.cpp
   PointerArithChecker.cpp
   PointerSubChecker.cpp
   PthreadLockChecker.cpp
   RetainCountChecker.cpp
   ReturnPointerRangeChecker.cpp
   ReturnUndefChecker.cpp
   SimpleStreamChecker.cpp
+  SpinLockChecker.cpp
   StackAddrEscapeChecker.cpp
   StdLibraryFunctionsChecker.cpp
   StreamChecker.cpp
   TaintTesterChecker.cpp
   TestAfterDivZeroChecker.cpp
   TraversalChecker.cpp
   UndefBranchChecker.cpp
   UndefCapturedBlockVarChecker.cpp

lib/StaticAnalyzer/Checkers/SpinLockChecker.cpp

+//== 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;
+}

test/Analysis/spinlock_correct.c

+// 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;
+}
+

test/Analysis/spinlock_double_lock.c

+// 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;
+}
+

test/Analysis/spinlock_double_release.c

+// 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;
+}
+