[analyzer] Syntactic matcher for leaks associated with run loop and autoreleasepool

[george.karpenkov]

Summary

A checker for detecting leaks resulting from allocating temporary
autoreleasing objects before starting the main run loop.

Checks for two antipatterns:
1. ObjCMessageExpr followed by [[NARunLoop mainRunLoop] run] in the same
autorelease pool.
2. ObjCMessageExpr followed by [[NARunLoop mainRunLoop] run] in no
autorelease pool.

Happens-before relationship is modeled purely syntactically.

rdar://39299145

[NoQ]

clang/lib/StaticAnalyzer/Checkers/RunLoopAutoreleaseLeakChecker.cpp

60 ↗

(On Diff #156198)

*makes a joke about QuadBoolTy and runs away*

88 ↗

(On Diff #156198)

I wonder if we could make a reusable matcher out of this: hasDescendantsInOrder(A, ..., B).

89 ↗

(On Diff #156198)

This memoization map is short-lived. I don't quite understand how would we ever encounter the same statement twice during our traversal, could you give an example? Like, you're traversing the AST in a manner in which RecursiveASTVisitors usually do that, and i'm pretty sure that they encounter every statement just once, and you throw away the map immediately after that. What am i missing?

91 ↗

(On Diff #156198)

So is the optional here only to add an assertion? It's essentially a non-optional in release mode(?) Maybe just assert in the callee that we never return None?

188–189 ↗

(On Diff #156198)

That'd match non-functions and C++ methods and stuff like that.

In the non-matcher world i'd have checked FunctionDecl::isMain() here, but i don't think we have a matcher for that, but i guess we may add it.

clang/test/Analysis/html_diagnostics/relevant_lines/macros_same_file.c

16 ↗

(On Diff #156198)

I guess this is accidental.

[NoQ]

clang/lib/StaticAnalyzer/Checkers/RunLoopAutoreleaseLeakChecker.cpp

88 ↗

(On Diff #156198)

Aha, i guess you're already discussing it on the mailing list, i didn't intend to block the patch on that.

[george.karpenkov]

clang/lib/StaticAnalyzer/Checkers/RunLoopAutoreleaseLeakChecker.cpp

89 ↗

(On Diff #156198)

i think we've discussed that some statements can still be DAGs (e.g. elvis operator)

[NoQ]

Looks good!

clang/lib/StaticAnalyzer/Checkers/RunLoopAutoreleaseLeakChecker.cpp

89 ↗

(On Diff #156198)

Yeah, apparently it has as many as 4 (!!) sub-expressions, 3 of which partially overlap. Still not sure it's worth the memoization, but let's add a comment explaining why we did that.

[dcoughlin]

It is great to see a check for this!

clang/include/clang/StaticAnalyzer/Checkers/Checkers.td

572 ↗

(On Diff #156904)

Mentioning "loops" three times here doesn't seem right.

"Check for leaked memory in autorelease pools that will never be popped"

clang/lib/StaticAnalyzer/Checkers/RunLoopAutoreleaseLeakChecker.cpp

12 ↗

(On Diff #156904)

"autoreleasing" --> "autoreleased"

19 ↗

(On Diff #156904)

I think it would be good to explain why this pattern may lead to leaks/abandoned memory.

Something like: "Any temporary objects autoreleased in code called in the expression will not be deallocated until the program exits and so are effectively leaks."

133 ↗

(On Diff #156904)

Should "mainRunLoop" really be camelCase? Does "mainRunLoop" make sense when the call is to xpc_main?

Why not just "the main run loop"?

134 ↗

(On Diff #156904)

The comma here should be a semi-colon to match our other diagnostics: "may never get released; consider moving them to a".

[dcoughlin]

clang/lib/StaticAnalyzer/Checkers/RunLoopAutoreleaseLeakChecker.cpp

15 ↗

(On Diff #156904)

Also note the typo: "NARunLoop" --> "NSRunLoop"

include/clang/StaticAnalyzer/Checkers/Checkers.td

 def ObjCPropertyChecker : Checker<"ObjCProperty">,
   HelpText<"Check for proper uses of Objective-C properties">,
   DescFile<"ObjCPropertyChecker.cpp">;
 
 } // end "osx"
 
 let ParentPackage = Cocoa in {
 
+def RunLoopAutoreleaseLeakChecker : Checker<"RunLoopAutoreleaseLeak">,
+  HelpText<"Check for leaked memory in autorelease pools that will never be drained">,
+  DescFile<"RunLoopAutoreleaseLeakChecker.cpp">;
+
 def ObjCAtSyncChecker : Checker<"AtSync">,
   HelpText<"Check for nil pointers used as mutexes for @synchronized">,
   DescFile<"ObjCAtSyncChecker.cpp">;
 
 def NilArgChecker : Checker<"NilArg">,
   HelpText<"Check for prohibited nil arguments to ObjC method calls">,
   DescFile<"BasicObjCFoundationChecks.cpp">;
 

lib/StaticAnalyzer/Checkers/CMakeLists.txt

add_clang_library(clangStaticAnalyzerCheckers
   ObjCUnusedIVarsChecker.cpp
   PaddingChecker.cpp
   PointerArithChecker.cpp
   PointerSubChecker.cpp
   PthreadLockChecker.cpp
   RetainCountChecker.cpp
   ReturnPointerRangeChecker.cpp
   ReturnUndefChecker.cpp
+  RunLoopAutoreleaseLeakChecker.cpp
   SimpleStreamChecker.cpp
   StackAddrEscapeChecker.cpp
   StdLibraryFunctionsChecker.cpp
   StreamChecker.cpp
   TaintTesterChecker.cpp
   TestAfterDivZeroChecker.cpp
   TraversalChecker.cpp
   TrustNonnullChecker.cpp

lib/StaticAnalyzer/Checkers/RunLoopAutoreleaseLeakChecker.cpp

+//=- RunLoopAutoreleaseLeakChecker.cpp --------------------------*- C++ -*-==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//
+//===----------------------------------------------------------------------===//
+//
+// A checker for detecting leaks resulting from allocating temporary
+// autoreleased objects before starting the main run loop.
+//
+// Checks for two antipatterns:
+// 1. ObjCMessageExpr followed by [[NSRunLoop mainRunLoop] run] in the same
+// autorelease pool.
+// 2. ObjCMessageExpr followed by [[NSRunLoop mainRunLoop] run] in no
+// autorelease pool.
+//
+// Any temporary objects autoreleased in code called in those expressions
+// will not be deallocated until the program exits, and are effectively leaks.
+//
+//===----------------------------------------------------------------------===//
+//
+
+#include "ClangSACheckers.h"
+#include "clang/AST/Decl.h"
+#include "clang/AST/DeclObjC.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/CheckerManager.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
+
+using namespace clang;
+using namespace ento;
+using namespace ast_matchers;
+
+namespace {
+
+const char * RunLoopBind = "NSRunLoopM";
+const char * RunLoopRunBind = "RunLoopRunM";
+const char * OtherMsgBind = "OtherMessageSentM";
+const char * AutoreleasePoolBind = "AutoreleasePoolM";
+
+class RunLoopAutoreleaseLeakChecker : public Checker<
+                                      check::ASTCodeBody> {
+
+public:
+  void checkASTCodeBody(const Decl *D,
+                        AnalysisManager &AM,
+                        BugReporter &BR) const;
+
+};
+
+} // end anonymous namespace
+
+
+using TriBoolTy = Optional<bool>;
+using MemoizationMapTy = llvm::DenseMap<const Stmt *, Optional<TriBoolTy>>;
+
+static TriBoolTy
+seenBeforeRec(const Stmt *Parent, const Stmt *A, const Stmt *B,
+              MemoizationMapTy &Memoization) {
+  for (const Stmt *C : Parent->children()) {
+    if (C == A)
+      return true;
+
+    if (C == B)
+      return false;
+
+    Optional<TriBoolTy> &Cached = Memoization[C];
+    if (!Cached)
+      Cached = seenBeforeRec(C, A, B, Memoization);
+
+    if (Cached->hasValue())
+      return Cached->getValue();
+  }
+
+  return None;
+}
+
+/// \return Whether {@code A} occurs before {@code B} in traversal of
+/// {@code Parent}.
+/// Conceptually a very incomplete/unsound approximation of happens-before
+/// relationship (A is likely to be evaluated before B),
+/// but useful enough in this case.
+static bool seenBefore(const Stmt *Parent, const Stmt *A, const Stmt *B) {
+  MemoizationMapTy Memoization;
+  TriBoolTy Val = seenBeforeRec(Parent, A, B, Memoization);
+  return Val.getValue();
+}
+
+static void emitDiagnostics(BoundNodes &Match,
+                            const Decl *D,
+                            BugReporter &BR,
+                            AnalysisManager &AM,
+                            const RunLoopAutoreleaseLeakChecker *Checker) {
+
+  assert(D->hasBody());
+  const Stmt *DeclBody = D->getBody();
+
+  AnalysisDeclContext *ADC = AM.getAnalysisDeclContext(D);
+
+  const auto *ME = Match.getNodeAs<ObjCMessageExpr>(OtherMsgBind);
+  assert(ME);
+
+  const auto *AP =
+      Match.getNodeAs<ObjCAutoreleasePoolStmt>(AutoreleasePoolBind);
+  bool HasAutoreleasePool = (AP != nullptr);
+
+  const auto *RL = Match.getNodeAs<ObjCMessageExpr>(RunLoopBind);
+  const auto *RLR = Match.getNodeAs<Stmt>(RunLoopRunBind);
+  assert(RLR && "Run loop launch not found");
+
+  assert(ME != RLR);
+  if (HasAutoreleasePool && seenBefore(AP, RLR, ME))
+    return;
+
+  if (!HasAutoreleasePool && seenBefore(DeclBody, RLR, ME))
+    return;
+
+  PathDiagnosticLocation Location = PathDiagnosticLocation::createBegin(
+    ME, BR.getSourceManager(), ADC);
+  SourceRange Range = ME->getSourceRange();
+
+  BR.EmitBasicReport(ADC->getDecl(), Checker,
+                     /*Name=*/"Memory leak inside autorelease pool",
+                     /*Category=*/"Memory",
+                     /*Name=*/
+                     (Twine("Temporary objects allocated in the") +
+                      " autorelease pool " +
+                      (HasAutoreleasePool ? "" : "of last resort ") +
+                      "followed by the launch of " +
+                      (RL ? "main run loop " : "xpc_main ") +
+                      "may never get released; consider moving them to a "
+                      "separate autorelease pool")
+                         .str(),
+                     Location, Range);
+}
+
+static StatementMatcher getRunLoopRunM(StatementMatcher Extra = anything()) {
+  StatementMatcher MainRunLoopM =
+      objcMessageExpr(hasSelector("mainRunLoop"),
+                      hasReceiverType(asString("NSRunLoop")),
+                      Extra)
+          .bind(RunLoopBind);
+
+  StatementMatcher MainRunLoopRunM = objcMessageExpr(hasSelector("run"),
+                         hasReceiver(MainRunLoopM),
+                         Extra).bind(RunLoopRunBind);
+
+  StatementMatcher XPCRunM =
+      callExpr(callee(functionDecl(hasName("xpc_main")))).bind(RunLoopRunBind);
+  return anyOf(MainRunLoopRunM, XPCRunM);
+}
+
+static StatementMatcher getOtherMessageSentM(StatementMatcher Extra = anything()) {
+  return objcMessageExpr(unless(anyOf(equalsBoundNode(RunLoopBind),
+                                      equalsBoundNode(RunLoopRunBind))),
+                         Extra)
+      .bind(OtherMsgBind);
+}
+
+static void
+checkTempObjectsInSamePool(const Decl *D, AnalysisManager &AM, BugReporter &BR,
+                           const RunLoopAutoreleaseLeakChecker *Chkr) {
+  StatementMatcher RunLoopRunM = getRunLoopRunM();
+  StatementMatcher OtherMessageSentM = getOtherMessageSentM();
+
+  StatementMatcher RunLoopInAutorelease =
+      autoreleasePoolStmt(
+        hasDescendant(RunLoopRunM),
+        hasDescendant(OtherMessageSentM)).bind(AutoreleasePoolBind);
+
+  DeclarationMatcher GroupM = decl(hasDescendant(RunLoopInAutorelease));
+
+  auto Matches = match(GroupM, *D, AM.getASTContext());
+  for (BoundNodes Match : Matches)
+    emitDiagnostics(Match, D, BR, AM, Chkr);
+}
+
+static void
+checkTempObjectsInNoPool(const Decl *D, AnalysisManager &AM, BugReporter &BR,
+                         const RunLoopAutoreleaseLeakChecker *Chkr) {
+
+  auto NoPoolM = unless(hasAncestor(autoreleasePoolStmt()));
+
+  StatementMatcher RunLoopRunM = getRunLoopRunM(NoPoolM);
+  StatementMatcher OtherMessageSentM = getOtherMessageSentM(NoPoolM);
+
+  DeclarationMatcher GroupM = functionDecl(
+    isMain(),
+    hasDescendant(RunLoopRunM),
+    hasDescendant(OtherMessageSentM)
+  );
+
+  auto Matches = match(GroupM, *D, AM.getASTContext());
+
+  for (BoundNodes Match : Matches)
+    emitDiagnostics(Match, D, BR, AM, Chkr);
+
+}
+
+void RunLoopAutoreleaseLeakChecker::checkASTCodeBody(const Decl *D,
+                        AnalysisManager &AM,
+                        BugReporter &BR) const {
+  checkTempObjectsInSamePool(D, AM, BR, this);
+  checkTempObjectsInNoPool(D, AM, BR, this);
+}
+
+void ento::registerRunLoopAutoreleaseLeakChecker(CheckerManager &mgr) {
+  mgr.registerChecker<RunLoopAutoreleaseLeakChecker>();
+}

test/Analysis/Checkers/RunLoopAutoreleaseLeakChecker.m

+// UNSUPPORTED: system-windows
+// RUN: %clang_analyze_cc1 -fobjc-arc -analyzer-checker=core,osx.cocoa.RunLoopAutoreleaseLeak %s -triple x86_64-darwin -verify
+// RUN: %clang_analyze_cc1 -DEXTRA=1 -DAP1=1 -fobjc-arc -analyzer-checker=core,osx.cocoa.RunLoopAutoreleaseLeak %s -triple x86_64-darwin -verify
+// RUN: %clang_analyze_cc1 -DEXTRA=1 -DAP2=1 -fobjc-arc -analyzer-checker=core,osx.cocoa.RunLoopAutoreleaseLeak %s -triple x86_64-darwin -verify
+// RUN: %clang_analyze_cc1 -DEXTRA=1 -DAP3=1 -fobjc-arc -analyzer-checker=core,osx.cocoa.RunLoopAutoreleaseLeak %s -triple x86_64-darwin -verify
+// RUN: %clang_analyze_cc1 -DEXTRA=1 -DAP4=1 -fobjc-arc -analyzer-checker=core,osx.cocoa.RunLoopAutoreleaseLeak %s -triple x86_64-darwin -verify
+
+#include "../Inputs/system-header-simulator-for-objc-dealloc.h"
+
+#ifndef EXTRA
+
+void just_runloop() { // No warning: no statements in between
+  @autoreleasepool {
+    [[NSRunLoop mainRunLoop] run]; // no-warning
+  }
+}
+
+void just_xpcmain() { // No warning: no statements in between
+  @autoreleasepool {
+    xpc_main(); // no-warning
+  }
+}
+
+void runloop_init_before() { // Warning: object created before the loop.
+  @autoreleasepool {
+    NSObject *object = [[NSObject alloc] init]; // expected-warning{{Temporary objects allocated in the autorelease pool followed by the launch of main run loop may never get released; consider moving them to a separate autorelease pool}}
+    (void) object;
+    [[NSRunLoop mainRunLoop] run]; 
+  }
+}
+
+void xpcmain_init_before() { // Warning: object created before the loop.
+  @autoreleasepool {
+    NSObject *object = [[NSObject alloc] init]; // expected-warning{{Temporary objects allocated in the autorelease pool followed by the launch of xpc_main may never get released; consider moving them to a separate autorelease pool}}
+    (void) object;
+    xpc_main(); 
+  }
+}
+
+void runloop_init_before_two_objects() { // Warning: object created before the loop.
+  @autoreleasepool {
+    NSObject *object = [[NSObject alloc] init]; // expected-warning{{Temporary objects allocated in the autorelease pool followed by the launch of main run loop may never get released; consider moving them to a separate autorelease pool}}
+    NSObject *object2 = [[NSObject alloc] init]; // no-warning, warning on the first one is enough.
+    (void) object;
+    (void) object2;
+    [[NSRunLoop mainRunLoop] run]; 
+  }
+}
+
+void runloop_no_autoreleasepool() {
+  NSObject *object = [[NSObject alloc] init]; // no-warning
+  (void)object;
+  [[NSRunLoop mainRunLoop] run];
+}
+
+void runloop_init_after() { // No warning: objects created after the loop
+  @autoreleasepool {
+    [[NSRunLoop mainRunLoop] run]; 
+    NSObject *object = [[NSObject alloc] init]; // no-warning
+    (void) object;
+  }
+}
+
+#endif
+
+#ifdef AP1
+int main() {
+    NSObject *object = [[NSObject alloc] init]; // expected-warning{{Temporary objects allocated in the autorelease pool of last resort followed by the launch of main run loop may never get released; consider moving them to a separate autorelease pool}}
+    (void) object;
+    [[NSRunLoop mainRunLoop] run]; 
+    return 0;
+}
+#endif
+
+#ifdef AP2
+// expected-no-diagnostics
+int main() {
+  NSObject *object = [[NSObject alloc] init]; // no-warning
+  (void) object;
+  @autoreleasepool {
+    [[NSRunLoop mainRunLoop] run]; 
+  }
+  return 0;
+}
+#endif
+
+#ifdef AP3
+// expected-no-diagnostics
+int main() {
+    [[NSRunLoop mainRunLoop] run];
+    NSObject *object = [[NSObject alloc] init]; // no-warning
+    (void) object;
+    return 0;
+}
+#endif
+
+#ifdef AP4
+int main() {
+    NSObject *object = [[NSObject alloc] init]; // expected-warning{{Temporary objects allocated in the autorelease pool of last resort followed by the launch of xpc_main may never get released; consider moving them to a separate autorelease pool}}
+    (void) object;
+    xpc_main();
+    return 0;
+}
+#endif

test/Analysis/Inputs/system-header-simulator-for-objc-dealloc.h

 - (void)dealloc;
 - (id)init;
 - (id)retain;
 - (oneway void)release;
 @end
 
 @interface NSRunLoop : NSObject
 + (NSRunLoop *)currentRunLoop;
++ (NSRunLoop *)mainRunLoop;
+- (void) run;
 - (void)cancelPerformSelectorsWithTarget:(id)target;
 @end
 
 @interface NSNotificationCenter : NSObject
 + (NSNotificationCenter *)defaultCenter;
 - (void)removeObserver:(id)observer;
 @end
 
 typedef struct objc_selector *SEL;
 
 void _Block_release(const void *aBlock);
 #define Block_release(...) _Block_release((const void *)(__VA_ARGS__))
 
 @interface CIFilter : NSObject
 @end
+
+extern void xpc_main(void);