[analyzer] Block in critical section

[zdtorok]

Summary

This checker should find the calls to blocking functions (for example: sleep, getc, fgets,read,recv etc.) inside a critical section. When sleep(x) is called while a mutex is held, other threads cannot lock the same mutex. This might take some time, leading to bad performance or even deadlock.

Example:

mutex_t m;

void f() {
  sleep(1000); // Error: sleep() while m is locked! [f() is called from foobar() while m is locked]
  // do some work
}

void foobar() {
  lock(m);
  f();
  unlock(m);
}

[NoQ]

Useful stuff!

When I see your approach with mutexCount, the following test case comes to mind:

std::mutex m;
void foo() {
  // Suppose this function is always called
  // with the mutex 'm' locked.
  m.unlock();
  // Here probably some useful work is done.
  m.lock();
  // What's the current mutex count?
  sleep(1); // expected-warning{{}}
}

lib/StaticAnalyzer/Checkers/BlockInCriticalSectionChecker.cpp

11

A bit of trailing whitespace here.

test/Analysis/block-in-critical-section.cpp

1

The run line is lacking -verify, and therefore these tests always pass. In your case, it'd be -Xclang -verify. On the other hand, i'm not sure if it's a good idea to run the test under the driver, instead of the standard -cc1 approach - after all, you aren't including any system headers in the test.

[zaks.anna]

Thanks for the patch!

Have you run this on a large codebase?

include/clang/StaticAnalyzer/Checkers/Checkers.td

406

"blocks" sounds a lot like blocks ObjC feature. I'd just be more explicit and say "Check for calls to blocking functions inside a critical section".

Please, change the name of the class as well.

lib/StaticAnalyzer/Checkers/BlockInCriticalSectionChecker.cpp

54

Counter -> MutexCounter or MutexState

61

Same here: "Block" sounds like an ObjC language feature. Also, the category name ("Unix Stream API Error") should be different.

85

Why is handling of unlock in preCall?

96

It would be great if you could implement a BugReporterVisitor that walks the path and explains where the lock has occurred. (This is not blocking for this commit.)

103

"Block in a critical section" -> "A blocking function %s is called inside a critical section."

test/Analysis/block-in-critical-section.cpp

12

Please, add inter-procedural examples like in the description of the checker.

[zdtorok]

Thank you for both of your comments and feedbacks! Also please excuse me for my (really) late response. Please have a look at my fixes and the new attached diff. Thanks!

lib/StaticAnalyzer/Checkers/BlockInCriticalSectionChecker.cpp

85

For some reason first I thought it's better for performance reasons - but now I've changed it to postCall.

[zdtorok]

Fixed based on the provided comments and feedbacks.

• added new inter-procedural tests
• minor styling fix (trailing whitespaces)
• fixed tests (missing verify option)
• fixed post, preCall checks

[NoQ]

I think there's still this problem i've outlined in the comment above: you can step into an integer-underflow if your analysis begins with unlock(). You could just ignore all unlocks that move you below 0, which would be ok.

Could you add this test?

std::mutex m;
void foo() {
  m.unlock(); // MutexCount = 4294967295, should be 0, just ignore this unlock.
  sleep(1); // no-warning
  m.lock(); // MutexCount = 0, should be 1, woohoo we're sure we're in the section now.
  sleep(1); // expected-warning{{}}
}

[zdtorok]

Fixed possible integer-underflow in case of unexpected unlocking function. Also added test for this.

[zdtorok]

You are right NoQ, thank you for the remark, I've upload a new diff containing a fix for the integer underflow case.

[zaks.anna]

LGTM! Thanks!

Future steps:
How do we plan to bring this checker out of alpha? Have you evaluated it on large codebases?

[zaks.anna]

Do you have commit access or should we commit?

[zdtorok]

As it's my first contribution I think I have no commit access.
So far I could not test it on larger codebase. I've tried to do so on clang but my computer was too slow for that. I will try it again.
What you mean by alpha-phase? What should be the next steps now?

[zaks.anna]

This checker is now in alpha.unix, because it is new and is in active development. However, alpha checkers are not supported and are not turned on by default, so we should move it into unix package once we think it is ready to be used.

Evaluation on a large real codebase (or several) would give us a higher confidence in the checker, so it will be valuable to perform that before we move the package out of alpha. However, clang is probably not a good codebase to test this on because it's not heavily multithreaded.

include/clang/StaticAnalyzer/Checkers/Checkers.td

 def StreamChecker : Checker<"Stream">,
   HelpText<"Check stream handling functions">,
   DescFile<"StreamChecker.cpp">;
 
 def SimpleStreamChecker : Checker<"SimpleStream">,
   HelpText<"Check for misuses of stream APIs">,
   DescFile<"SimpleStreamChecker.cpp">;
 
+def BlockInCriticalSectionChecker : Checker<"BlockInCriticalSection">,
+  HelpText<"Check for blocks in critical section">,
+  DescFile<"BlockInCriticalSectionChecker.cpp">;
+
 } // end "alpha.unix"
 
 let ParentPackage = CString in {
 
 def CStringNullArg : Checker<"NullArg">,
   HelpText<"Check for null pointers being passed as arguments to C string functions">,
   DescFile<"CStringChecker.cpp">;
 

lib/StaticAnalyzer/Checkers/BlockInCriticalSectionChecker.cpp

+//===-- BlockInCriticalSectionChecker.cpp -----------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines a checker for blocks in critical sections. This checker should find 
+// the calls to blocking functions (for example: sleep, getc, fgets, read, 
+// recv etc.) inside a critical section. When sleep(x) is called while a mutex
+// is held, other threades cannot lock the same mutex. This might take some 
+// time, leading to bad performance or even deadlock.
+//
+//===----------------------------------------------------------------------===//
+
+#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 BlockInCriticalSectionChecker : public Checker<check::PostCall,
+                                                     check::PreCall> {
+
+  CallDescription LockFn, UnlockFn, SleepFn, GetcFn, FgetsFn, ReadFn, RecvFn;
+
+  std::unique_ptr<BugType> BlockInCritSectionBugType;
+
+  void reportBlockInCritSection(SymbolRef FileDescSym,
+                                const CallEvent &call,
+                                CheckerContext &C) const;
+
+public:
+  BlockInCriticalSectionChecker();
+
+  /// Process lock.
+  /// Process blocking functions (sleep, getc, fgets, read, recv)
+  void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
+
+  /// Process unlock.
+  void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
+
+};
+
+} // end anonymous namespace
+
+REGISTER_TRAIT_WITH_PROGRAMSTATE(Counter, unsigned)
+
+BlockInCriticalSectionChecker::BlockInCriticalSectionChecker()
+    : LockFn("lock"), UnlockFn("unlock"), SleepFn("sleep"), GetcFn("getc"),
+      FgetsFn("fgets"), ReadFn("read"), RecvFn("recv") {
+  // Initialize the bug type.
+  BlockInCritSectionBugType.reset(
+      new BugType(this, "Block in critical section", "Unix Stream API Error"));
+}
+
+void BlockInCriticalSectionChecker::checkPostCall(const CallEvent &Call,
+                                                  CheckerContext &C) const {
+  if (!Call.isCalled(LockFn)
+      && !Call.isCalled(SleepFn)
+      && !Call.isCalled(GetcFn)
+      && !Call.isCalled(FgetsFn)
+      && !Call.isCalled(ReadFn)
+      && !Call.isCalled(RecvFn))
+    return;
+
+  ProgramStateRef State = C.getState();
+  unsigned mutexCount = State->get<Counter>();
+  if (Call.isCalled(LockFn)) {
+    State = State->set<Counter>(++mutexCount);
+    C.addTransition(State);
+  } else if (mutexCount > 0) {
+    SymbolRef BlockDesc = Call.getReturnValue().getAsSymbol();
+    reportBlockInCritSection(BlockDesc, Call, C);
+  }
+}
+
+void BlockInCriticalSectionChecker::checkPreCall(const CallEvent &Call,
+                                                 CheckerContext &C) const {
+  if (!Call.isCalled(UnlockFn))
+    return;
+
+  ProgramStateRef State = C.getState();
+  unsigned mutexCount = State->get<Counter>();
+  State = State->set<Counter>(--mutexCount);
+  C.addTransition(State);
+}
+
+void BlockInCriticalSectionChecker::reportBlockInCritSection(
+    SymbolRef BlockDescSym, const CallEvent &Call, CheckerContext &C) const {
+  ExplodedNode *ErrNode = C.generateNonFatalErrorNode();
+  if (!ErrNode)
+    return;
+
+  auto R = llvm::make_unique<BugReport>(*BlockInCritSectionBugType,
+      "Block in a critical section", ErrNode);
+  R->addRange(Call.getSourceRange());
+  R->markInteresting(BlockDescSym);
+  C.emitReport(std::move(R));
+}
+
+void ento::registerBlockInCriticalSectionChecker(CheckerManager &mgr) {
+  mgr.registerChecker<BlockInCriticalSectionChecker>();
+}

lib/StaticAnalyzer/Checkers/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Support
   )
 
 add_clang_library(clangStaticAnalyzerCheckers
   AllocationDiagnostics.cpp
   AnalyzerStatsChecker.cpp
   ArrayBoundChecker.cpp
   ArrayBoundCheckerV2.cpp
   BasicObjCFoundationChecks.cpp
+  BlockInCriticalSectionChecker.cpp
   BoolAssignmentChecker.cpp
   BuiltinFunctionChecker.cpp
   CStringChecker.cpp
   CStringSyntaxChecker.cpp
   CallAndMessageChecker.cpp
   CastSizeChecker.cpp
   CastToStructChecker.cpp
   CheckObjCDealloc.cpp

test/Analysis/block-in-critical-section.cpp

+// RUN: %clang --analyze -std=c++11 -Xclang -analyzer-checker -Xclang alpha.unix.BlockInCriticalSection %s
+
+void sleep(int x) {}
+
+namespace std {
+struct mutex {
+  void lock() {}
+  void unlock() {}
+};
+}
+
+void testBlockInCriticalSection() {
+  std::mutex m;
+  m.lock();
+  sleep(3); // expected-warning {{Block in a critical section}}
+  m.unlock();
+}
+
+void testBlockInCriticalSectionWithNestedMutexes() {
+  std::mutex m, n, k;
+  m.lock();
+  n.lock();
+  k.lock();
+  sleep(3); // expected-warning {{Block in a critical section}}
+  k.unlock();
+  sleep(5); // expected-warning {{Block in a critical section}}
+  n.unlock();
+  sleep(3); // expected-warning {{Block in a critical section}}
+  m.unlock();
+  sleep(3); // no-warning
+}