[analyzer] Add check for mutex acquisition during interrupt context in Magenta kernel

[khazem]

Summary

Acquiring a mutex during the Magenta kernel exception handler can cause deadlocks and races. This patch adds a checker that ensures that no mutexes are acquired during an interrupt context.

[NoQ]

This checker looks good to me! I don't see any obvious problems, and i think we can land it into non-alpha (enabled by default) once reviewers' comments are addressed.

include/clang/StaticAnalyzer/Checkers/Checkers.td

78

optin is for checkers for which we cannot make a good guess if the user wants those or not.

Can we make a guess by looking at the target triple in this case? If we can, then it should not go into optin, but rather auto-enabled on specific platform, similarly to how it works for eg. osx.

lib/StaticAnalyzer/Checkers/MagentaInterruptContextChecker.cpp

32

Indent slightly off.

54

To see if we're in an interrupt, take current LocationContext and see if its stack frame or a parent stack frame is for x86_exception_handler. I think you don't need a program state trait for that check - it's already in your location context - and checkBeginFunction()/checkEndFunction() can be removed. Also, as far as i remember (i may be wrong), AnalysisDeclContext will bring you the current top-level function declaration under analysis directly, without ascending the stack frames, if that's in fact all you need.

For exit-functions you'd still need a flag in the program state that says that there was an exit.

93

Probably a bool was intended. Also, this may be moved inside the assert body if not used anywhere else.

109

I'd suggest to use operator== for such cases because it's easier to read.

include/clang/StaticAnalyzer/Checkers/Checkers.td

 def LocalizabilityAlpha : Package<"localizability">, InPackage<CocoaAlpha>;
 def LocalizabilityOptIn : Package<"localizability">, InPackage<CocoaOptIn>;
 
+def Magenta : Package<"magenta">, InPackage<OptIn>;
+
 def MPI : Package<"mpi">, InPackage<OptIn>;
 
 def LLVM : Package<"llvm">;

   DescFile<"LocalizationChecker.cpp">;
 }
 
+let ParentPackage = Magenta in {
+  def MagentaInterruptContextChecker : Checker<"MutexInInterruptContext">,
+  HelpText<"Checks for the acquisition of mutexes during an interrupt context">,
+  DescFile<"MagentaInterruptContextChecker.cpp">;
+}
+
 let ParentPackage = MPI in {
   def MPIChecker : Checker<"MPI-Checker">,
   HelpText<"Checks MPI code">,

lib/StaticAnalyzer/Checkers/CMakeLists.txt

   LocalizationChecker.cpp
   MacOSKeychainAPIChecker.cpp
   MacOSXAPIChecker.cpp
+  MagentaInterruptContextChecker.cpp
   MallocChecker.cpp
   MallocOverflowSecurityChecker.cpp
   MallocSizeofChecker.cpp

lib/StaticAnalyzer/Checkers/MagentaInterruptContextChecker.cpp

+//===-- MagentaInterruptContextChecker.cpp -----------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This checker checks for acquisitions of mutexes during an interrupt context
+// in the Magenta kernel, as such an acquisition can lead to race conditions and
+// deadlocks.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ClangSACheckers.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
+#include "clang/StaticAnalyzer/Core/Checker.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+
+using namespace clang;
+using namespace ento;
+
+namespace {
+
+class MagentaInterruptContextChecker : public Checker<check::PreCall,
+                                                      check::BeginFunction,
+                                                      check::EndFunction> {
+  std::unique_ptr<BugType> MagentaInterruptContextBugType;
+  void reportMutexAcquisition(SymbolRef FileDescSym,
+                                const CallEvent &call,
+                                CheckerContext &C) const;
+
+  /// An interrupt context starts from this function
+  StringRef ExceptionHandler;
+
+  /// A list of functions that break out of an interrupt context
+  std::vector<CallDescription> ExitFuns;
+
+  /// A list of functions that must not be called during an interrupt context
+  std::vector<CallDescription> ProhibitedCalls;
+
+public:
+  MagentaInterruptContextChecker();
+
+  /// \brief Check if we've just started an interrupt context.
+  ///
+  /// We don't use PreCall for this because the interrupt context function is
+  /// never called from C code (thus there will never be a CallEvent for
+  /// x86_exception_handler). Therefore, we consider an interrupt context to
+  /// have started at the beginning of the body of ExceptionHandler, rather than
+  /// a call to that function.
+  void checkBeginFunction(CheckerContext &C) const;
+
+  /// \brief Check if we have exited from an interrupt context
+  ///
+  /// If the exception handler returns normally, then we're no longer in an
+  /// interrupt context and it it once again safe to call any of the
+  /// ProhibitedCalls.
+  void checkEndFunction(CheckerContext &C) const;
+
+  /// \brief Check for prohibited calls or for calls that exit an interrupt
+  ///        context
+  void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
+};
+
+} // end anonymous namespace
+
+REGISTER_TRAIT_WITH_PROGRAMSTATE(InInterrupt, bool)
+
+MagentaInterruptContextChecker::MagentaInterruptContextChecker()
+    : ExceptionHandler("x86_exception_handler"),
+      ExitFuns({CallDescription("panic"), CallDescription("_panic"),
+                CallDescription("thread_preempt")}),
+      ProhibitedCalls({CallDescription("mutex_acquire"),
+                       CallDescription("mutex_acquire_timeout"),
+                       CallDescription("mutex_acquire_timeout_internal")}) {
+  MagentaInterruptContextBugType.reset(
+      new BugType(this, "Mutex acquired during interrupt context",
+                        "Mutex Error"));
+}
+
+void MagentaInterruptContextChecker::checkBeginFunction(
+                                       CheckerContext &C) const {
+  const LocationContext *LCtx = C.getLocationContext();
+
+  const FunctionDecl *FD = dyn_cast_or_null<FunctionDecl>(LCtx->getDecl());
+  if (!FD)
+    return;
+
+  ProgramStateRef State = C.getState();
+  unsigned inInterrupt = State->get<InInterrupt>();
+  if (!(FD->getName().compare(ExceptionHandler))) {
+    assert(!inInterrupt && "exception handler cannot be recursively invoked");
+    State = State->set<InInterrupt>(true);
+    C.addTransition(State);
+  }
+}
+
+void MagentaInterruptContextChecker::checkEndFunction(
+                                       CheckerContext &C) const {
+  const LocationContext *LCtx = C.getLocationContext();
+  const FunctionDecl *FD = dyn_cast_or_null<FunctionDecl>(LCtx->getDecl());
+  if (!FD)
+    return;
+
+  ProgramStateRef State = C.getState();
+  if (!(FD->getName().compare(ExceptionHandler)))
+    State = State->set<InInterrupt>(false);
+}
+
+void MagentaInterruptContextChecker::checkPreCall(const CallEvent &Call,
+                                                  CheckerContext &C) const {
+  ProgramStateRef State = C.getState();
+  unsigned inInterrupt = State->get<InInterrupt>();
+
+  for (CallDescription ExitFun : ExitFuns)
+    if (Call.isCalled(ExitFun) && inInterrupt) {
+      State = State->set<InInterrupt>(false);
+      C.addTransition(State);
+      return;
+    }
+
+  for (CallDescription ProhibitedCall : ProhibitedCalls)
+    if (Call.isCalled(ProhibitedCall) && inInterrupt) {
+      SymbolRef BlockDesc = Call.getReturnValue().getAsSymbol();
+      reportMutexAcquisition(BlockDesc, Call, C);
+      return;
+    }
+}
+
+void MagentaInterruptContextChecker::reportMutexAcquisition(
+    SymbolRef BlockDescSym, const CallEvent &Call, CheckerContext &C) const {
+  ExplodedNode *ErrNode = C.generateNonFatalErrorNode();
+  if (!ErrNode)
+    return;
+
+  auto R = llvm::make_unique<BugReport>(*MagentaInterruptContextBugType,
+      "Mutex acquired during interrupt context", ErrNode);
+  R->addRange(Call.getSourceRange());
+  R->markInteresting(BlockDescSym);
+  C.emitReport(std::move(R));
+}
+
+void ento::registerMagentaInterruptContextChecker(CheckerManager &mgr) {
+  mgr.registerChecker<MagentaInterruptContextChecker>();
+}

test/Analysis/mutex-in-interrupt-context.cpp

+// RUN: %clang_cc1 -analyze -analyzer-checker=core,optin.magenta.MutexInInterruptContext -std=c++11 -verify %s
+
+// Exit critical region
+void thread_preempt() {}
+void panic() {}
+void _panic() {}
+
+// Don't call these during critical region
+void mutex_acquire() {}
+void mutex_acquire_timeout() {}
+void mutex_acquire_timeout_internal() {}
+
+void call_ma() {
+  mutex_acquire(); // expected-warning {{Mutex acquired during interrupt context}}
+}
+
+void call_mat() {
+  mutex_acquire_timeout(); // expected-warning {{Mutex acquired during interrupt context}}
+}
+
+void call_mati() {
+  mutex_acquire_timeout_internal(); // expected-warning {{Mutex acquired during interrupt context}}
+}
+
+void call_ma_safe() {
+  mutex_acquire(); // no-warning
+}
+
+// The exception handler doesn't get called from C code. We start
+// exploring from the beginning of this function
+void x86_exception_handler(int foo) {
+  switch (foo) {
+    case 0:
+      mutex_acquire(); // expected-warning {{Mutex acquired during interrupt context}}
+      break;
+
+    case 1:
+      mutex_acquire_timeout(); // expected-warning {{Mutex acquired during interrupt context}}
+      break;
+
+    case 2:
+      mutex_acquire_timeout_internal(); // expected-warning {{Mutex acquired during interrupt context}}
+      break;
+
+    case 3:
+      call_ma();
+      break;
+
+    case 4:
+      call_mat();
+      break;
+
+    case 5:
+      call_mati();
+      break;
+
+    case 6:
+      thread_preempt();
+      call_ma_safe();
+      break;
+
+    case 7:
+      panic();
+      call_ma_safe();
+      break;
+
+    case 8:
+      _panic();
+      call_ma_safe();
+      break;
+  }
+}