[analyzer] Add MutexChecker for the Magenta kernel

[khazem]

Summary

This patch adds a new Static Analyzer checker for the correct use of mutexes in the Magenta kernel.The checker analyzes uses of mutex_init, mutex_acquire, mutex_release, and mutex_destroy. It performs the core checks on usage of these APIs on mutex to make sure they are correct. For instance, we want to make sure mutexes are always initialized in the constructor and destroyed in the destructor. Also, we do not want to have paths where a mutex is released while not having been acquired first.

The checker was authored by Farid Molazem Tabrizi.

[NoQ]

It's great to see more domain-specific checks coming in! We're glad to be useful. The code is also well-commented, and a lot of tests are provided, which is great.

This checker seems to be relatively similar to the existing alpha.unix.PthreadLock checker (which also handles XNU kernel locks already). In fact, the part that checks init-lock-unlock-destroy paths might actually fit in there by simply adding more function identifiers; it also shares the same problems, like not supporting pointer escapes (if a pointer to a mutex escapes to an external function, this function may lock or unlock the mutex without us knowing), or never cleaning up the program state maps (even when regions are dead and could no longer be referenced - useful for performance, and also may find more defects, eg. mutex region becoming dead in a locked state is probably a problem). So i think there's an opportunity for some code re-use, if you're interested (it wouldn't immediately benefit any of the checkers, but any later changes would naturally land into both checkers). And the escape and cleanup problems should be easy to address.

I see you also have a feature that's not covered by the existing checker, which is checking the constructor-destructor lock-unlock match. I suspect that this sub-check needs a bit more testing. My first concern is that checkEndFunction is a callback that fires once per path through end of function, not once per function. Here's a test i could come up with, which currently fails - i'm deliberately tricking the analyzer into analyzing branches in different order by alternating between if-branch of a condition and else-branch of an inverted condition; i think there may be more false positives of this kind if there's more of the complicated control flow in constructors/destructors:

bool glob;

class Foo {
  mutex_t lock;

public:
  Foo() {
    if (glob) {
    } else {
      mutex_init(&lock);
    }
  }
  ~Foo() {
    if (!glob) {
      mutex_destroy(&lock);
    } else {
    }
  }
};

void foo() {
  Foo F; // Warns "Mutex was not destroyed in the destructor", perhaps shouldn't.
}

I also have another kind of concern for this sub-check: it relies on the core analyzing all paths through the constructor/destructor. However, the analyzer never promises to cover all paths during analysis, and in fact reserves the right to drop paths arbitrarily - this is a kind of fundamental limitation for the symbolic execution technique, otherwise the analysis would never terminate on most code. So additional hacks might be needed to avoid false positives that may arise if, for example, the path on which the mutex_destroy call in the destructor was completely skipped during analysis. It should be possible to hang up to checkEndAnalysis to see if there is extra stuff in the worklist at the end, which would indicate that some paths were dropped.

It also might be a good idea to make this check path-insensitive instead, which should be more reliable and transparent for this case - simply scan the AST of constructor and destructor bodies for references to mutex variables within init/destroy call expressions, compose the sets of variable declarations referenced that way, and compare those.

To summarize, depending on how much time you'd like to invest into this checker, and if any of the thoughts above sounded as a useful feedback, in no particular order and with no urgency and without really blocking this patch from landing you may want to:

1. Try to merge with PthreadLock checker,
2. Handle mutex pointer escapes,
3. Handle dead symbols,
4. Move constructor-destructor init-destroy sets to the program state to make them path-aware,
5. Or otherwise move the checks to checkEndOfTranslationUnit to make sure all paths were covered;
6. Check if any paths were skipped during analysis (not sure if it'd be necessary after 4.),
7. Maybe make the constructor-destructor init-destroy check AST-based (instead of 4.-6.).

Generally, i think this checker is good in its current shape, and issues above can anyway be addressed later, in an incremental manner. Unless you prefer to make major changes to this patch at this point, i should be able to follow up with minor comments.

lib/StaticAnalyzer/Checkers/MutexChecker.cpp

228

Before i forget: this API is a bit tricky, and there's a common but completely unobvious mistake that you're making here. reportMutexError(..., false) is producing a transition to a non-fatal error node. The whole point of the non-fatal error node is that analysis continues past this node. After adding the transition on this line, you effectively split the analysis into two paths, one following the non-fatal error node, another containing the MutexMap change.

This doubles up the time it takes to analyze the rest of the code (growing exponentially if encountered multiple times; probably rises to the node limit very soon, destroying coverage), and the additional path through the error node is not expected here (but it might be for some checkers, so the API is not quite at fault) - the behavior of the checker on this path might also be unexpected (it essentially skips the initialization of the mutex).

The right way to do this is to remember the exploded node generated by generateNonFatalErrorNode(), and put the new transition on top of that node (if the report has actually been thrown) by using the addTransition(St, N) override (or make the transition normally if it isn't).

I really wish there was a good and universal solution to make the transition API more obvious, feel sorry about that every time i see one of those problems.

[khazem]

Thanks for the detailed review Artem!

I think that it's sensible to try merging this with PthreadLockChecker. In fact, I could also try merging the SpinLockChecker [1] that I've posted for review with PthreadLockChecker also, since they all implement similar functionality. This would be in line with what we discussed at the developer meeting, where there was a consensus that there could be too many domain-specific checkers that were only different in what function names they look for.

Here is my proposal: I could try refactoring the PthreadLockChecker into a LockChecker class, which would be instantiated as various subclasses (for Pthread, XNU, Magenta, and others in the future). The common functionality would be implemented in LockChecker, but the user would ask for a specific checker using command-line flags. Using subclasses would hopefully prevent the class from becoming a mess of if/switch statements, while allowing future LockCheckers to be implemented for other lock APIs. Does this seem reasonable?

I could then have a go at the other improvements that you mentioned, and they would hopefully apply to all LockCheckers and not just our Magenta one.

[1] https://reviews.llvm.org/D26340

[NoQ]

In D26342#590881, @khazem wrote:

I think that it's sensible to try merging this with PthreadLockChecker. In fact, I could also try merging the SpinLockChecker [1] that I've posted for review with PthreadLockChecker also, since they all implement similar functionality.

That'd be great!

In D26342#590881, @khazem wrote:

Here is my proposal: I could try refactoring the PthreadLockChecker into a LockChecker class, which would be instantiated as various subclasses (for Pthread, XNU, Magenta, and others in the future). The common functionality would be implemented in LockChecker, but the user would ask for a specific checker using command-line flags. Using subclasses would hopefully prevent the class from becoming a mess of if/switch statements, while allowing future LockCheckers to be implemented for other lock APIs. Does this seem reasonable?

We usually go with the if/switch approach (in this case we instantly see what's the difference between the two APIs), and i think we don't do checker inheritance anywhere, but i don't have good reasons to instantly prefer one over the other, so it's be nice to know if inheritance is actually better here.

Note that if all you want is to enable/disable platform-specific checks separately with -analyzer-checker options, or have separate lines for the checks in Checkers.td (and auto-enable magenta checkers if the magenta target platform is detected), then you don't necessarily need to produce separate Checker<> classes/instances in your C++ code for that. We can have different checkers point to the same C++ checker object. See unix.Malloc and cplusplus.NewDelete as an example (they're essentially the same checker) - the tricks are in registerChecker procedure.

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 MutexChecker : Checker<"MutexChecker">,
+  HelpText<"Check for correct handling of mutexes">,
+  DescFile<"MutexChecker.cpp">;
+
+} // end "magenta"

lib/StaticAnalyzer/Checkers/CMakeLists.txt

add_clang_library(clangStaticAnalyzerCheckers
   MacOSKeychainAPIChecker.cpp
   MacOSXAPIChecker.cpp
   MallocChecker.cpp
   MallocOverflowSecurityChecker.cpp
   MallocSizeofChecker.cpp
   MPI-Checker/MPIBugReporter.cpp
   MPI-Checker/MPIChecker.cpp
   MPI-Checker/MPIFunctionClassifier.cpp
+  MutexChecker.cpp
   NSAutoreleasePoolChecker.cpp
   NSErrorChecker.cpp
   NoReturnFunctionChecker.cpp
   NonNullParamChecker.cpp
   NullabilityChecker.cpp
   NumberObjectConversionChecker.cpp
   ObjCAtSyncChecker.cpp
   ObjCContainersASTChecker.cpp

lib/StaticAnalyzer/Checkers/MutexChecker.cpp

+//== MutexChecker.cpp - Mutex 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 MutexChecker for the Magenta kernel. MutexChecker makes
+// sure that mutexes are only released after being acquired, and are not
+// acquired twice in a row by the same thread. It also makes sure that
+// the mutexes that are initialized during the construction of an object
+// match the mutexes destroyed during the destruction of that object.
+//
+//===----------------------------------------------------------------------===//
+
+#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/StringSwitch.h"
+
+using namespace clang;
+using namespace ento;
+
+namespace {
+
+struct MutexInfo {
+
+  enum Kind { Initialized, Acquired, Released, Destroyed } K;
+
+  MutexInfo(Kind kind) : K(kind) {}
+
+  bool operator==(const MutexInfo &LI) const { return K == LI.K; }
+
+  void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(K); }
+
+  bool isInitialized() const { return K == Initialized; }
+
+  bool isAcquired() const { return K == Acquired; }
+
+  bool isReleased() const { return K == Released; }
+
+  bool isDestroyed() const { return K == Destroyed; }
+
+  static MutexInfo getInitialized() { return MutexInfo(Initialized); }
+
+  static MutexInfo getAcquired() { return MutexInfo(Acquired); }
+
+  static MutexInfo getReleased() { return MutexInfo(Released); }
+
+  static MutexInfo getDestroyed() { return MutexInfo(Destroyed); }
+};
+}
+
+/// Keeps track of the state of each mutex during an execution path.
+REGISTER_MAP_WITH_PROGRAMSTATE(MutexMap, const MemRegion *, MutexInfo)
+
+namespace {
+
+class MutexChecker : public Checker<check::PreCall, check::EndFunction> {
+  typedef std::set<std::string> MutexSet;
+  typedef std::map<std::string, MutexSet> ClassToMutexMap;
+  typedef void (MutexChecker::*MutexProcessingFn)(const CallEvent &,
+                                                  CheckerContext &,
+                                                  const MemRegion *) const;
+
+  mutable std::map<std::string, bool> ConstructorProcessed;
+  mutable std::map<std::string, bool> DestructorProcessed;
+  mutable ClassToMutexMap InitializedSet;
+  mutable ClassToMutexMap DestroyedSet;
+
+  void processMutexInitCall(const CallEvent &Call, CheckerContext &C,
+                            const MemRegion *SpinLockLocation) const;
+
+  /// When facing a mutex_acquire function call, check the record of the
+  /// corresponding mutex in MutexMap and make sure that there are no
+  /// problems. For example, the mutex has to be already initialized at this
+  /// point.
+  void processMutexAcquireCall(const CallEvent &Call, CheckerContext &C,
+                               const MemRegion *SpinLockLocation) const;
+
+  /// When facing a mutex_release function call, check the record of the
+  /// corresponding mutex in MutexMap and make sure that there are no
+  /// problems. For example, the mutex has to be already acquired at this point.
+  void processMutexReleaseCall(const CallEvent &Call, CheckerContext &C,
+                               const MemRegion *SpinLockLocation) const;
+
+  /// When facing a mutex_destroy function call, check the record of the
+  /// corresponding mutex in MutexMap and make sure that there are no
+  /// problems. For example, the mutex should not be acquired.
+  void processMutexDestroyCall(const CallEvent &Call, CheckerContext &C,
+                               const MemRegion *SpinLockLocation) const;
+
+  void reportMutexError(CheckerContext &C, const MemRegion *MutexMemRegion,
+                        StringRef ErrMsg, bool Fatal) const;
+
+  /// Make sure the initialized and destroyed mutexes in the constructor and
+  /// destructor match.
+  void analyzeInitializedAndDestroyedMutexes(CheckerContext &C) const;
+
+  /// We do not analyze the implementation of the Mutex class itself. We rather
+  /// analyze the use of Mutex APIs in other parts of the code. Therefore, we
+  /// consider Mutex class an exception in our analysis and ignore it.
+  bool isException(const MemRegion *MutexMemRegion) const;
+
+  /// Helper function to find out if the current function is type T.
+  /// T could be constructor, destructor, CXXMethod, etc.
+  template <class T> bool isFunctionType(const Decl *D) const;
+
+  /// Helper function to find out if we are in the context of function type T.
+  /// T could be constructor, destructor, CXXMethod, etc.
+  template <class T> bool isInContextOfFuncType(CheckerContext &C) const;
+
+  /// Find the class name from the current context.
+  std::string getClassName(CheckerContext &C) const;
+
+  std::unique_ptr<BugType> MutexBugType;
+
+public:
+  MutexChecker();
+  void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
+  void checkEndFunction(CheckerContext &C) const;
+};
+}
+
+void ento::registerMutexChecker(CheckerManager &Mgr) {
+  Mgr.registerChecker<MutexChecker>();
+}
+
+MutexChecker::MutexChecker() {
+  MutexBugType.reset(new BugType(this, "Mutex error", "Lock Error"));
+}
+
+bool MutexChecker::isException(const MemRegion *MutexMemRegion) const {
+  // In this function, to detect if the analyzer is analyzing the
+  // Mutex class, we take advantage of the fact that in this situation
+  // the SuperRegion that includes the memory region of mutex_t object
+  // included in Mutex class is of kind SymbolicMemoryRegionKind.
+  if (MutexMemRegion->getKind() != MemRegion::FieldRegionKind)
+    return false;
+
+  const FieldRegion *FR = dyn_cast<FieldRegion>(MutexMemRegion);
+  if (!FR)
+    return false;
+
+  const FieldDecl *FDecl = FR->getDecl();
+  if (!FDecl)
+    return false;
+
+  // if mutex_t is a member of a class other than Mutex, we want to
+  // analyze the class.
+  const RecordDecl *RDecl = FDecl->getParent();
+  if (!RDecl || RDecl->getNameAsString() != "Mutex")
+    return false;
+
+  const SubRegion *SubR = dyn_cast<SubRegion>(MutexMemRegion);
+  if (!SubR)
+    return false;
+
+  const MemRegion *SuperR = SubR->getSuperRegion();
+  if (!SuperR)
+    return false;
+
+  return SuperR->getKind() == MemRegion::SymbolicRegionKind;
+}
+
+void MutexChecker::checkPreCall(const CallEvent &Call,
+                                CheckerContext &C) const {
+
+  if (!Call.getCalleeIdentifier())
+    return;
+
+  std::string CalleeName = Call.getCalleeIdentifier()->getName();
+
+  if (CalleeName != "mutex_init" && CalleeName != "mutex_acquire" &&
+      CalleeName != "mutex_release" && CalleeName != "mutex_destroy")
+    return;
+
+  if (Call.getNumArgs() == 0)
+    return;
+
+  // Memory region of the mutex
+  const MemRegion *MutexMemRegion = Call.getArgSVal(0).getAsRegion();
+  // If SpinLocLocation is NULL, this is likely due to changes in the signature
+  // of mutex functions.
+  if (!MutexMemRegion) {
+    llvm_unreachable("No mutex pointer passed to mutex_acquire/mutex_release!");
+  }
+
+  // If it is the exception case, no need to perform analysis.
+  if (isException(MutexMemRegion))
+    return;
+
+  MutexProcessingFn ProcessMutexCall =
+      llvm::StringSwitch<MutexProcessingFn>(CalleeName)
+          .Case("mutex_init", &MutexChecker::processMutexInitCall)
+          .Case("mutex_acquire", &MutexChecker::processMutexAcquireCall)
+          .Case("mutex_release", &MutexChecker::processMutexReleaseCall)
+          .Case("mutex_destroy", &MutexChecker::processMutexDestroyCall);
+
+  (this->*ProcessMutexCall)(Call, C, MutexMemRegion);
+}
+
+void MutexChecker::processMutexInitCall(const CallEvent &Call,
+                                        CheckerContext &C,
+                                        const MemRegion *MutexMemRegion) const {
+  ProgramStateRef St = C.getState();
+
+  // Gather all the init calls in the constructor.
+  if (isInContextOfFuncType<CXXConstructorDecl>(C)) {
+    std::string CurrClass = getClassName(C);
+    if (!ConstructorProcessed[CurrClass])
+      InitializedSet[CurrClass].insert(MutexMemRegion->getString());
+  }
+
+  const MutexInfo *LI = St->get<MutexMap>(MutexMemRegion);
+  if (LI)
+    // Initializing a mutex after being used! report a bug
+    reportMutexError(
+        C, MutexMemRegion,
+        "Found an execution path where mutex is being initialized after use",
+        false);
+
+  St = St->set<MutexMap>(MutexMemRegion, MutexInfo::getInitialized());
+  C.addTransition(St);
+}
+
+void MutexChecker::processMutexAcquireCall(
+    const CallEvent &Call, CheckerContext &C,
+    const MemRegion *MutexMemRegion) const {
+  ProgramStateRef St = C.getState();
+  const MutexInfo *LI = St->get<MutexMap>(MutexMemRegion);
+  if (LI && (LI->isAcquired() || LI->isDestroyed()))
+    // Mutex cannot be acquired if it is acquired before, or after it is
+    // destroyed
+    reportMutexError(
+        C, MutexMemRegion,
+        "Found an execution path where a destroyed/acquired mutex is taken",
+        false);
+
+  St = St->set<MutexMap>(MutexMemRegion, MutexInfo::getAcquired());
+  C.addTransition(St);
+}
+
+void MutexChecker::processMutexReleaseCall(
+    const CallEvent &Call, CheckerContext &C,
+    const MemRegion *MutexMemRegion) const {
+  ProgramStateRef St = C.getState();
+  const MutexInfo *LI = St->get<MutexMap>(MutexMemRegion);
+  if (!LI)
+    // This is the first time this mutex is being used, and it is not
+    // initialized.
+    reportMutexError(
+        C, MutexMemRegion,
+        "Found an execution path where an uninitialized mutex is used", false);
+  else if (!LI->isAcquired())
+    // Releasing a mutex that is not acquired.
+    reportMutexError(
+        C, MutexMemRegion,
+        "Found an execution path where an unacquired mutex is released", false);
+
+  St = St->set<MutexMap>(MutexMemRegion, MutexInfo::getReleased());
+  C.addTransition(St);
+}
+
+void MutexChecker::processMutexDestroyCall(
+    const CallEvent &Call, CheckerContext &C,
+    const MemRegion *MutexMemRegion) const {
+  ProgramStateRef St = C.getState();
+  // Gather all the destroy calls in the destructor.
+  if (isInContextOfFuncType<CXXDestructorDecl>(C)) {
+    std::string CurrClass = getClassName(C);
+    if (!DestructorProcessed[CurrClass])
+      DestroyedSet[CurrClass].insert(MutexMemRegion->getString());
+  }
+
+  St = St->set<MutexMap>(MutexMemRegion, MutexInfo::getDestroyed());
+  C.addTransition(St);
+}
+
+void MutexChecker::reportMutexError(CheckerContext &C,
+                                    const MemRegion *MutexMemRegion,
+                                    StringRef ErrMsg, bool Fatal) const {
+  ExplodedNode *Node;
+  if (Fatal)
+    Node = C.generateErrorNode();
+  else
+    Node = C.generateNonFatalErrorNode(C.getState());
+  if (!Node)
+    return;
+  auto Report = llvm::make_unique<BugReport>(*MutexBugType, ErrMsg, Node);
+  if (MutexMemRegion)
+    Report->markInteresting(MutexMemRegion);
+  C.emitReport(std::move(Report));
+}
+
+template <class T> bool MutexChecker::isFunctionType(const Decl *D) const {
+  if (!D)
+    return false;
+
+  if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
+    return isa<T>(FD);
+
+  return false;
+}
+
+std::string MutexChecker::getClassName(CheckerContext &C) const {
+  std::string Name = "";
+  const LocationContext *LC = C.getLocationContext();
+  while (LC && !isFunctionType<CXXMethodDecl>(LC->getDecl()))
+    LC = LC->getParent();
+
+  if (LC) {
+    const CXXMethodDecl *MDecl = dyn_cast<CXXMethodDecl>(LC->getDecl());
+    Name = MDecl->getParent()->getNameAsString();
+  }
+
+  return Name;
+}
+
+template <class T>
+bool MutexChecker::isInContextOfFuncType(CheckerContext &C) const {
+  const LocationContext *LC = C.getLocationContext();
+  while (LC && !isFunctionType<T>(LC->getDecl()))
+    LC = LC->getParent();
+
+  if (LC)
+    return true;
+
+  return false;
+}
+
+void MutexChecker::checkEndFunction(CheckerContext &C) const {
+  // Unset flags if we are leaving constructor/destructor
+  ExplodedNode *Node = C.getPredecessor();
+  if (!Node)
+    return;
+
+  bool ExitingConstructor =
+      isFunctionType<CXXConstructorDecl>(&Node->getCodeDecl());
+  bool ExitingDestructor =
+      isFunctionType<CXXDestructorDecl>(&Node->getCodeDecl());
+
+  if (!ExitingConstructor && !ExitingDestructor)
+    return;
+
+  std::string CurrClass = getClassName(C);
+  if (!CurrClass.size())
+    return;
+
+  // We have already done the processing, nothing left to do
+  if (DestructorProcessed[CurrClass] && ConstructorProcessed[CurrClass])
+    return;
+
+  if (ExitingConstructor)
+    ConstructorProcessed[CurrClass] = true;
+
+  if (ExitingDestructor)
+    DestructorProcessed[CurrClass] = true;
+
+  // If this is the first time both constructor and destructor are processed,
+  // compare initialized and destroyed mutexes
+  if (DestructorProcessed[CurrClass] && ConstructorProcessed[CurrClass])
+    analyzeInitializedAndDestroyedMutexes(C);
+}
+
+void MutexChecker::analyzeInitializedAndDestroyedMutexes(
+    CheckerContext &C) const {
+  std::string CurrClass = getClassName(C);
+  for (auto I = InitializedSet[CurrClass].begin(),
+            End = InitializedSet[CurrClass].end();
+       I != End; ++I) {
+    std::string InitLoc = *I;
+    if (!DestroyedSet[CurrClass].count(InitLoc))
+      reportMutexError(C, NULL, "Mutex was not destroyed in the destructor",
+                       false);
+  }
+
+  for (auto I = DestroyedSet[CurrClass].begin(),
+            End = DestroyedSet[CurrClass].end();
+       I != End; ++I) {
+    std::string DestroyedLoc = *I;
+    if (!InitializedSet[CurrClass].count(DestroyedLoc))
+      reportMutexError(C, NULL, "Mutex was not initialized in the constructor",
+                       false);
+  }
+}

test/Analysis/mutex_correct1.cpp

+// RUN: %clang_cc1 -analyze -analyzer-checker=magenta.MutexChecker -verify %s
+// expected-no-diagnostics
+
+struct mutex_t {
+    unsigned int count;
+};
+
+void mutex_init(mutex_t *);
+void mutex_acquire(mutex_t *);
+void mutex_release(mutex_t *);
+void mutex_destroy(mutex_t *);
+
+class Mutex {
+  mutex_t m;
+ public:
+  Mutex() { mutex_init(&m); }
+  void acquire() { mutex_acquire(&m); }
+  void release() { mutex_release(&m); }
+  ~Mutex() { mutex_destroy(&m); }
+};
+
+int f();
+
+class Test {
+  mutex_t lock1;
+  mutex_t lock2;
+ public:
+  Test() { mutex_init(&lock1); mutex_init(&lock2);}
+  void action();
+  ~Test() { mutex_destroy(&lock1); mutex_destroy(&lock2); }
+};
+
+void Test::action() {
+  int x = f();
+
+  if (x > 10)
+    mutex_acquire(&lock1);
+  else
+    mutex_acquire(&lock2);
+
+  if (x > 10)
+    mutex_release(&lock1);
+  else
+    mutex_release(&lock2);
+}

test/Analysis/mutex_correct2.cpp

+// RUN: %clang_cc1 -analyze -analyzer-checker=magenta.MutexChecker -verify %s
+// expected-no-diagnostics
+
+struct mutex_t {
+    unsigned int count;
+};
+
+void mutex_init(mutex_t *);
+void mutex_acquire(mutex_t *);
+void mutex_release(mutex_t *);
+void mutex_destroy(mutex_t *);
+
+class Mutex {
+  mutex_t m;
+ public:
+  Mutex() { mutex_init(&m); }
+  void acquire() { mutex_acquire(&m); }
+  void release() { mutex_release(&m); }
+  ~Mutex() { mutex_destroy(&m); }
+};
+
+int f();
+
+class Test {
+  Mutex m;
+ public:
+  Test() { }
+  void action();
+  ~Test() { }
+};
+
+void Test::action() {
+  int x = f();
+
+  if (x > 10)
+    m.acquire();
+  else
+    m.acquire();
+
+  if (x > 10)
+    m.release();
+  else
+    m.release();
+}
+
+void mutHandler() {
+  Mutex mut1;
+  mutex_t mut2;
+  mutex_init(&mut2);
+  mut1.acquire();
+  mutex_acquire(&mut2);
+  f();
+  mutex_release(&mut2);
+  mut1.release();
+  mutex_destroy(&mut2);
+}

test/Analysis/mutex_double_acquired1.cpp

+// RUN: %clang_cc1 -analyze -analyzer-checker=magenta.MutexChecker -verify %s
+
+struct mutex_t {
+    unsigned int count;
+};
+
+void mutex_init(mutex_t *);
+void mutex_acquire(mutex_t *);
+void mutex_release(mutex_t *);
+void mutex_destroy(mutex_t *);
+
+class Mutex {
+  mutex_t m;
+ public:
+  Mutex() { mutex_init(&m); }
+  void acquire() { mutex_acquire(&m); }
+  void release() { mutex_release(&m); }
+  ~Mutex() { mutex_destroy(&m); }
+};
+
+int f();
+
+class Test {
+  mutex_t lock;
+ public:
+  Test() { mutex_init(&lock); }
+  void action();
+  ~Test() { mutex_destroy(&lock); }
+};
+
+void Test::action() {
+  int x = f();
+  if (x > 10)
+    mutex_acquire(&lock);
+
+  if (x > 25)
+    mutex_acquire(&lock); // expected-warning{{Found an execution path where a destroyed/acquired mutex is taken}}
+
+  mutex_release(&lock); // expected-warning{{Found an execution path where an unacquired mutex is released}}
+}
+
+int main() {
+  Test testClass;
+  testClass.action();
+  return 0;
+}
+

test/Analysis/mutex_double_acquired2.cpp

+// RUN: %clang_cc1 -analyze -analyzer-checker=magenta.MutexChecker -verify %s
+
+struct mutex_t {
+    unsigned int count;
+};
+
+void mutex_init(mutex_t *);
+void mutex_acquire(mutex_t *);
+void mutex_release(mutex_t *);
+void mutex_destroy(mutex_t *);
+
+class Mutex {
+  mutex_t m;
+ public:
+  Mutex() { mutex_init(&m); }
+  void acquire() { mutex_acquire(&m); } // expected-warning{{Found an execution path where a destroyed/acquired mutex is taken}}
+
+  void release() { mutex_release(&m); } // expected-warning{{Found an execution path where an unacquired mutex is released}}
+
+  ~Mutex() { mutex_destroy(&m); }
+};
+
+int f();
+
+class Hidden {
+  Mutex m;
+ public:
+  Hidden() {}
+  ~Hidden() {}
+  void action();
+};
+
+void Hidden::action() {
+  int x = f();
+  if (x > 10)
+    m.acquire();
+
+  if (x > 25)
+    m.acquire();
+  m.release();
+}
+
+class Test {
+ public:
+  Test() { Hidden h; h.action(); }
+  void action();
+  ~Test() { }
+};

test/Analysis/mutex_double_released1.cpp

+// RUN: %clang_cc1 -analyze -analyzer-checker=magenta.MutexChecker -verify %s
+
+struct mutex_t {
+    unsigned int count;
+};
+
+void mutex_init(mutex_t *);
+void mutex_acquire(mutex_t *);
+void mutex_release(mutex_t *);
+void mutex_destroy(mutex_t *);
+
+class Mutex {
+  mutex_t m;
+ public:
+  Mutex() { mutex_init(&m); }
+  void acquire() { mutex_acquire(&m); }
+  void release() { mutex_release(&m); }
+  ~Mutex() { mutex_destroy(&m); }
+};
+
+int f();
+
+class Test {
+  mutex_t lock;
+ public:
+  Test() { mutex_init(&lock); }
+  void action();
+  ~Test() { mutex_destroy(&lock); }
+};
+
+void Test::action() {
+  int x = f();
+  if (x > 10)
+    mutex_acquire(&lock);
+
+  if (x > 10)
+    mutex_release(&lock);
+
+  mutex_release(&lock); // expected-warning{{Found an execution path where an unacquired mutex is released}}
+}
+
+int main() {
+  Test testClass;
+  testClass.action();
+  return 0;
+}

test/Analysis/mutex_double_released2.cpp

+// RUN: %clang_cc1 -analyze -analyzer-checker=magenta.MutexChecker -verify %s
+
+struct mutex_t {
+    unsigned int count;
+};
+
+void mutex_init(mutex_t *);
+void mutex_acquire(mutex_t *);
+void mutex_release(mutex_t *);
+void mutex_destroy(mutex_t *);
+
+class Mutex {
+  mutex_t m;
+ public:
+  Mutex() { mutex_init(&m); }
+  void acquire() { mutex_acquire(&m); }
+  void release() { mutex_release(&m); } // expected-warning{{Found an execution path where an unacquired mutex is released}}
+  ~Mutex() { mutex_destroy(&m); }
+};
+
+int f();
+
+class Test {
+  Mutex lock;
+ public:
+  Test() { }
+  void action();
+  ~Test() { }
+};
+
+void Test::action() {
+  int x = f();
+  if (x > 10)
+    lock.acquire();
+
+  if (x > 10)
+    lock.release();
+
+  lock.release();
+}
+
+int main() {
+  Test testClass;
+  testClass.action();
+  return 0;
+}

test/Analysis/mutex_incorrect_release.cpp

+// RUN: %clang_cc1 -analyze -analyzer-checker=magenta.MutexChecker -verify %s
+
+struct mutex_t {
+    unsigned int count;
+};
+
+void mutex_init(mutex_t *);
+void mutex_acquire(mutex_t *);
+void mutex_release(mutex_t *);
+void mutex_destroy(mutex_t *);
+
+class Mutex {
+  mutex_t m;
+ public:
+  Mutex() { mutex_init(&m); }
+  void acquire() { mutex_acquire(&m); }
+  void release() { mutex_release(&m); }
+  ~Mutex() { mutex_destroy(&m); }
+};
+
+int f();
+
+class Test {
+  mutex_t lock;
+ public:
+  Test() { mutex_init(&lock); }
+  void action();
+  ~Test() { mutex_destroy(&lock); }
+};
+
+void Test::action() {
+  int x = f();
+  if (x > 10)
+    mutex_acquire(&lock);
+
+  if (x < 15)
+    mutex_release(&lock); // expected-warning{{Found an execution path where an unacquired mutex is released}}
+}
+
+int main() {
+  Test testClass;
+  testClass.action();
+  return 0;
+}
+

test/Analysis/mutex_not_destroyed1.cpp

+// RUN: %clang_cc1 -analyze -analyzer-checker=magenta.MutexChecker -verify %s
+
+struct mutex_t {
+    unsigned int count;
+};
+
+void mutex_init(mutex_t *);
+void mutex_acquire(mutex_t *);
+void mutex_release(mutex_t *);
+void mutex_destroy(mutex_t *);
+
+class Mutex {
+  mutex_t m;
+ public:
+  Mutex() { mutex_init(&m); }
+  void acquire() { mutex_acquire(&m); }
+  void release() { mutex_release(&m); }
+  ~Mutex() { mutex_destroy(&m); }
+};
+
+class Test {
+  mutex_t lock;
+ public:
+  void action() { }
+  Test() { mutex_init(&lock); } // expected-warning{{Mutex was not destroyed in the destructor}}
+  ~Test() { }
+};

test/Analysis/mutex_not_destroyed2.cpp

+// RUN: %clang_cc1 -analyze -analyzer-checker=magenta.MutexChecker -verify %s
+
+struct mutex_t {
+    unsigned int count;
+};
+
+void mutex_init(mutex_t *);
+void mutex_acquire(mutex_t *);
+void mutex_release(mutex_t *);
+void mutex_destroy(mutex_t *);
+
+class Mutex {
+  mutex_t m;
+ public:
+  Mutex() { mutex_init(&m); }
+  void acquire() { mutex_acquire(&m); }
+  void release() { mutex_release(&m); }
+  ~Mutex() { mutex_destroy(&m); }
+};
+
+int f();
+class Hidden {
+  Mutex m;
+  mutex_t m2;
+ public:
+  Hidden() { mutex_init(&m2); }
+  ~Hidden() { mutex_destroy(&m2); }
+  void action();
+};
+
+void Hidden::action() {
+  int x = f();
+  if (x > 10)
+    m.acquire();
+
+  if (x > 10)
+    m.release();
+}
+
+class Test {
+  mutex_t m;
+ public:
+  Test() { Hidden h; h.action(); mutex_init(&m); } // expected-warning{{Mutex was not destroyed in the destructor}}
+  void action();
+  ~Test() { }
+};

test/Analysis/mutex_uninitialized.cpp

+// RUN: %clang_cc1 -analyze -analyzer-checker=magenta.MutexChecker -verify %s
+
+struct mutex_t {
+    unsigned int count;
+};
+
+void mutex_init(mutex_t *);
+void mutex_acquire(mutex_t *);
+void mutex_release(mutex_t *);
+void mutex_destroy(mutex_t *);
+
+class Mutex {
+  mutex_t m;
+ public:
+  Mutex() { mutex_init(&m); }
+  void acquire() { mutex_acquire(&m); }
+  void release() { mutex_release(&m); }
+  ~Mutex() { mutex_destroy(&m); }
+};
+
+class Test {
+  mutex_t lock;
+ public:
+  Test() { }
+  void action() { }
+  ~Test() { mutex_destroy(&lock); } // expected-warning{{Mutex was not initialized in the constructor}}
+};
+
+int main()
+{
+  Test testClass;
+  return 0;
+}