[analyzer] AST-matching checker to detect global central dispatch performance anti-pattern

[george.karpenkov]

Summary

rdar://37312818

The checker does not care about the ordering of callbacks.

[a.sidorin]

Hello George. I don't see any problems; just a comment inline.

lib/StaticAnalyzer/Checkers/GCDAsyncSemaphorChecker.cpp

71 ↗

(On Diff #136885)

hasDescendant() will fire only once even if there are multiple usages of this pattern in same function. If it can be a common case, it is better to use forEachDescendant() instead; if not, could you add a comment describing your decision?

[NoQ]

lib/StaticAnalyzer/Checkers/GCDAsyncSemaphorChecker.cpp

71 ↗

(On Diff #136885)

Because we need a descendant for which all three hold, i guess it'd take a dual-layer construct (forEachDescendant(compoundStmt(hasDescendant, hasDescendant, hasDescendant))) and then somehow sort them to pick the smallest match if nested compound statements are present (if we need, but i guess it's not necessary because we won't highlight the whole statement, and unique-ing will do the rest for us).

lib/StaticAnalyzer/Checkers/GCDAsyncSemaphoreChecker.cpp

66–67

*crosses fingers for that to compile on all buildbots*

86

To me this sounds like a named constant that stores the name of another named constant.

[NoQ]

test/gcdasyncsemaphorechecker_test.m

14–16

Looks like an accidental leftover.

[george.karpenkov]

lib/StaticAnalyzer/Checkers/GCDAsyncSemaphorChecker.cpp

71 ↗

(On Diff #136885)

I guess it depends on whether we want to add path notes for signaling and creating the semaphore. If not, just changing all hasDescendant to forEachDescendant somehow magically works.

lib/StaticAnalyzer/Checkers/GCDAsyncSemaphoreChecker.cpp

66–67

Seems standard C++11?...

86

Do you propose to rename it? To what?

[NoQ]

lib/StaticAnalyzer/Checkers/GCDAsyncSemaphorChecker.cpp

71 ↗

(On Diff #136885)

Heh. I guess you could add a test with two wait calls on the same semaphore and mark it as a FIXME.

lib/StaticAnalyzer/Checkers/GCDAsyncSemaphoreChecker.cpp

86

Just use the string everywhere?

[george.karpenkov]

lib/StaticAnalyzer/Checkers/GCDAsyncSemaphoreChecker.cpp

86

But the current usage protects against typos in multiple usages.

[NoQ]

Yay lgtm now. Let's see how it evolves :)

lib/StaticAnalyzer/Checkers/GCDAsyncSemaphoreChecker.cpp

86

Hmm okay.

[dcoughlin]

This looks good. Some minor post-commit review inline.

include/clang/StaticAnalyzer/Checkers/Checkers.td

615

This should have a more general name so that we can add related checks to it in the future. I suggest "GCDAntipattern".

616

We don't use "checker" as a term in user-facing text. I suggest "Check for performance anti-patterns when using Grand Central Dispatch".

lib/StaticAnalyzer/Checkers/GCDAsyncSemaphoreChecker.cpp

12

Nit: missing "e" at end of "semaphor".

23

Nit: same here "semaphores"

92

It would be good to look at both the method/function name and the class name name for "test", "Test", "mock", and "Mock".

144

We should tell the user more information about why they should believe this is bad.

I suggest "Waiting on a semaphore with Grand Central Dispatch creates useless threads and is subject to priority inversion"

include/clang/StaticAnalyzer/Checkers/Checkers.td

def ObjCDeallocChecker : Checker<"Dealloc">,
   DescFile<"CheckObjCDealloc.cpp">;
 
 def ObjCSuperDeallocChecker : Checker<"SuperDealloc">,
   HelpText<"Warn about improper use of '[super dealloc]' in Objective-C">,
   DescFile<"ObjCSuperDeallocChecker.cpp">;
 
 } // end "osx.cocoa"
 
+let ParentPackage = OSXAlpha in {
+
+def GCDAsyncSemaphoreChecker : Checker<"GCDAsyncSemaphore">,
+  HelpText<"Checker for performance anti-pattern when using semaphors from async API">,
+  DescFile<"GCDAsyncSemaphoreChecker.cpp">;
+} // end "alpha.osx"
+
 let ParentPackage = CocoaAlpha in {
 
 def InstanceVariableInvalidation : Checker<"InstanceVariableInvalidation">,
   HelpText<"Check that the invalidatable instance variables are invalidated in the methods annotated with objc_instance_variable_invalidator">,
   DescFile<"IvarInvalidationChecker.cpp">;
 
 def MissingInvalidationMethod : Checker<"MissingInvalidationMethod">,
   HelpText<"Check that the invalidation methods are present in classes that contain invalidatable instance variables">,

lib/StaticAnalyzer/Checkers/CMakeLists.txt

add_clang_library(clangStaticAnalyzerCheckers
   DeleteWithNonVirtualDtorChecker.cpp
   DereferenceChecker.cpp
   DirectIvarAssignment.cpp
   DivZeroChecker.cpp
   DynamicTypePropagation.cpp
   DynamicTypeChecker.cpp
   ExprInspectionChecker.cpp
   FixedAddressChecker.cpp
+  GCDAsyncSemaphoreChecker.cpp
   GenericTaintChecker.cpp
   GTestChecker.cpp
   IdenticalExprChecker.cpp
   IteratorChecker.cpp
   IvarInvalidationChecker.cpp
   LLVMConventionsChecker.cpp
   LocalizationChecker.cpp
   MacOSKeychainAPIChecker.cpp

lib/StaticAnalyzer/Checkers/GCDAsyncSemaphoreChecker.cpp

+//===- GCDAsyncSemaphoreChecker.cpp -----------------------------*- C++ -*-==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines GCDAsyncSemaphoreChecker which checks against a common
+// antipattern when synchronous API is emulated from asynchronous callbacks
+// using a semaphor:
+//
+//   dispatch_semapshore_t sema = dispatch_semaphore_create(0);
+
+//   AnyCFunctionCall(^{
+//     // code…
+//     dispatch_semapshore_signal(sema);
+//   })
+//   dispatch_semapshore_wait(sema, *)
+//
+// Such code is a common performance problem, due to inability of GCD to
+// properly handle QoS when a combination of queues and semaphors is used.
+// Good code would either use asynchronous API (when available), or perform
+// the necessary action in asynchronous callback.
+//
+// Currently, the check is performed using a simple heuristical AST pattern
+// matching.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ClangSACheckers.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
+#include "clang/StaticAnalyzer/Core/Checker.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
+#include "llvm/Support/Debug.h"
+
+#define DEBUG_TYPE "gcdasyncsemaphorechecker"
+
+using namespace clang;
+using namespace ento;
+using namespace ast_matchers;
+
+namespace {
+
+const char *WarningBinding = "semaphore_wait";
+
+class GCDAsyncSemaphoreChecker : public Checker<check::ASTCodeBody> {
+public:
+  void checkASTCodeBody(const Decl *D,
+                        AnalysisManager &AM,
+                        BugReporter &BR) const;
+};
+
+class Callback : public MatchFinder::MatchCallback {
+  BugReporter &BR;
+  const GCDAsyncSemaphoreChecker *C;
+  AnalysisDeclContext *ADC;
+
+public:
+  Callback(BugReporter &BR,
+           AnalysisDeclContext *ADC,
+           const GCDAsyncSemaphoreChecker *C) : BR(BR), C(C), ADC(ADC) {}
+
+  virtual void run(const MatchFinder::MatchResult &Result) override;
+};
+
+auto callsName(const char *FunctionName)
+    -> decltype(callee(functionDecl())) {
+  return callee(functionDecl(hasName(FunctionName)));
+}
+
+auto equalsBoundArgDecl(int ArgIdx, const char *DeclName)
+    -> decltype(hasArgument(0, expr())) {
+  return hasArgument(ArgIdx, ignoringParenCasts(declRefExpr(
+                                 to(varDecl(equalsBoundNode(DeclName))))));
+}
+
+auto bindAssignmentToDecl(const char *DeclName) -> decltype(hasLHS(expr())) {
+  return hasLHS(ignoringParenImpCasts(
+                         declRefExpr(to(varDecl().bind(DeclName)))));
+}
+
+void GCDAsyncSemaphoreChecker::checkASTCodeBody(const Decl *D,
+                                               AnalysisManager &AM,
+                                               BugReporter &BR) const {
+
+  // The pattern is very common in tests, and it is OK to use it there.
+  if (const auto* ND = dyn_cast<NamedDecl>(D))
+    if (ND->getName().startswith("test"))
+      return;
+
+  const char *SemaphoreBinding = "semaphore_name";
+  auto SemaphoreCreateM = callExpr(callsName("dispatch_semaphore_create"));
+
+  auto SemaphoreBindingM = anyOf(
+      forEachDescendant(
+          varDecl(hasDescendant(SemaphoreCreateM)).bind(SemaphoreBinding)),
+      forEachDescendant(binaryOperator(bindAssignmentToDecl(SemaphoreBinding),
+                     hasRHS(SemaphoreCreateM))));
+
+  auto SemaphoreWaitM = forEachDescendant(
+    callExpr(
+      allOf(
+        callsName("dispatch_semaphore_wait"),
+        equalsBoundArgDecl(0, SemaphoreBinding)
+      )
+    ).bind(WarningBinding));
+
+  auto AcceptsBlockM =
+    forEachDescendant(callExpr(hasAnyArgument(hasType(
+            hasCanonicalType(blockPointerType())
+            ))));
+
+  auto BlockSignallingM =
+    forEachDescendant(callExpr(hasAnyArgument(hasDescendant(callExpr(
+          allOf(
+              callsName("dispatch_semaphore_signal"),
+              equalsBoundArgDecl(0, SemaphoreBinding)
+              ))))));
+
+  auto FinalM = compoundStmt(
+      SemaphoreBindingM,
+      SemaphoreWaitM,
+      AcceptsBlockM,
+      BlockSignallingM);
+
+  MatchFinder F;
+  Callback CB(BR, AM.getAnalysisDeclContext(D), this);
+
+  F.addMatcher(FinalM, &CB);
+  F.match(*D->getBody(), AM.getASTContext());
+}
+
+void Callback::run(const MatchFinder::MatchResult &Result) {
+  const auto *SW = Result.Nodes.getNodeAs<CallExpr>(WarningBinding);
+  assert(SW);
+  BR.EmitBasicReport(
+      ADC->getDecl(), C,
+      /*Name=*/"Semaphore performance anti-pattern",
+      /*Category=*/"Performance",
+      "Possible semaphore performance anti-pattern: wait on a semaphore "
+      "signalled to in a callback",
+      PathDiagnosticLocation::createBegin(SW, BR.getSourceManager(), ADC),
+      SW->getSourceRange());
+}
+
+}
+
+void ento::registerGCDAsyncSemaphoreChecker(CheckerManager &Mgr) {
+  Mgr.registerChecker<GCDAsyncSemaphoreChecker>();
+}

test/gcdasyncsemaphorechecker_test.m

+// RUN: %clang_analyze_cc1 -analyzer-checker=core,alpha.osx.GCDAsyncSemaphore %s -fblocks -verify
+//
+typedef int dispatch_semaphore_t;
+typedef void (^block_t)();
+
+dispatch_semaphore_t dispatch_semaphore_create(int);
+void dispatch_semaphore_wait(dispatch_semaphore_t, int);
+void dispatch_semaphore_signal(dispatch_semaphore_t);
+
+void func(void (^)(void));
+void func_w_typedef(block_t);
+
+int coin();
+
+void use_semaphor_antipattern() {
+  dispatch_semaphore_t sema = dispatch_semaphore_create(0);
+
+  func(^{
+      dispatch_semaphore_signal(sema);
+  });
+  dispatch_semaphore_wait(sema, 100); // expected-warning{{Possible semaphore performance anti-pattern}}
+}
+
+// It's OK to use pattern in tests.
+// We simply match the containing function name against ^test.
+void test_no_warning() {
+  dispatch_semaphore_t sema = dispatch_semaphore_create(0);
+
+  func(^{
+      dispatch_semaphore_signal(sema);
+  });
+  dispatch_semaphore_wait(sema, 100);
+}
+
+void use_semaphor_antipattern_multiple_times() {
+  dispatch_semaphore_t sema1 = dispatch_semaphore_create(0);
+
+  func(^{
+      dispatch_semaphore_signal(sema1);
+  });
+  dispatch_semaphore_wait(sema1, 100); // expected-warning{{Possible semaphore performance anti-pattern}}
+
+  dispatch_semaphore_t sema2 = dispatch_semaphore_create(0);
+
+  func(^{
+      dispatch_semaphore_signal(sema2);
+  });
+  dispatch_semaphore_wait(sema2, 100); // expected-warning{{Possible semaphore performance anti-pattern}}
+}
+
+void use_semaphor_antipattern_multiple_wait() {
+  dispatch_semaphore_t sema1 = dispatch_semaphore_create(0);
+
+  func(^{
+      dispatch_semaphore_signal(sema1);
+  });
+  // FIXME: multiple waits on same semaphor should not raise a warning.
+  dispatch_semaphore_wait(sema1, 100); // expected-warning{{Possible semaphore performance anti-pattern}}
+  dispatch_semaphore_wait(sema1, 100); // expected-warning{{Possible semaphore performance anti-pattern}}
+}
+
+void warn_incorrect_order() {
+  // FIXME: ASTMatchers do not allow ordered matching, so would match even
+  // if out of order.
+  dispatch_semaphore_t sema = dispatch_semaphore_create(0);
+
+  dispatch_semaphore_wait(sema, 100); // expected-warning{{Possible semaphore performance anti-pattern}}
+  func(^{
+      dispatch_semaphore_signal(sema);
+  });
+}
+
+void warn_w_typedef() {
+  dispatch_semaphore_t sema = dispatch_semaphore_create(0);
+
+  func_w_typedef(^{
+      dispatch_semaphore_signal(sema);
+  });
+  dispatch_semaphore_wait(sema, 100); // expected-warning{{Possible semaphore performance anti-pattern}}
+}
+
+void warn_nested_ast() {
+  dispatch_semaphore_t sema = dispatch_semaphore_create(0);
+
+  if (coin()) {
+    func(^{
+         dispatch_semaphore_signal(sema);
+         });
+  } else {
+    func(^{
+         dispatch_semaphore_signal(sema);
+         });
+  }
+  dispatch_semaphore_wait(sema, 100); // expected-warning{{Possible semaphore performance anti-pattern}}
+}
+
+void use_semaphore_assignment() {
+  dispatch_semaphore_t sema;
+  sema = dispatch_semaphore_create(0);
+
+  func(^{
+      dispatch_semaphore_signal(sema);
+  });
+  dispatch_semaphore_wait(sema, 100); // expected-warning{{Possible semaphore performance anti-pattern}}
+}
+
+void use_semaphore_assignment_init() {
+  dispatch_semaphore_t sema = dispatch_semaphore_create(0);
+  sema = dispatch_semaphore_create(1);
+
+  func(^{
+      dispatch_semaphore_signal(sema);
+  });
+  dispatch_semaphore_wait(sema, 100); // expected-warning{{Possible semaphore performance anti-pattern}}
+}
+
+void differentsemaphoreok() {
+  dispatch_semaphore_t sema1 = dispatch_semaphore_create(0);
+  dispatch_semaphore_t sema2 = dispatch_semaphore_create(0);
+
+  func(^{
+      dispatch_semaphore_signal(sema1);
+  });
+  dispatch_semaphore_wait(sema2, 100); // no-warning
+}
+
+void nosignalok() {
+  dispatch_semaphore_t sema1 = dispatch_semaphore_create(0);
+  dispatch_semaphore_wait(sema1, 100);
+}
+
+void nowaitok() {
+  dispatch_semaphore_t sema = dispatch_semaphore_create(0);
+  func(^{
+      dispatch_semaphore_signal(sema);
+  });
+}
+
+void noblockok() {
+  dispatch_semaphore_t sema = dispatch_semaphore_create(0);
+  dispatch_semaphore_signal(sema);
+  dispatch_semaphore_wait(sema, 100);
+}
+
+void storedblockok() {
+  dispatch_semaphore_t sema = dispatch_semaphore_create(0);
+  block_t b = ^{
+      dispatch_semaphore_signal(sema);
+  };
+  dispatch_semaphore_wait(sema, 100);
+}
+
+void passed_semaphore_ok(dispatch_semaphore_t sema) {
+  func(^{
+      dispatch_semaphore_signal(sema);
+  });
+  dispatch_semaphore_wait(sema, 100);
+}
+
+void warn_with_cast() {
+  dispatch_semaphore_t sema = dispatch_semaphore_create(0);
+
+  func(^{
+      dispatch_semaphore_signal((int)sema);
+  });
+  dispatch_semaphore_wait((int)sema, 100); // expected-warning{{Possible semaphore performance anti-pattern}}
+}
+
+