[analyzer] Improve NoOwnershipChangeVisitor's understanding of deallocators

[Szelethus]

Summary

The problem with leak bug reports is that the most interesting event in the code is likely the one that did not happen -- lack of ownership change and lack of deallocation, which is often present within the same function that the analyzer inlined anyway, but not on the path of execution on which the bug occured. We struggle to understand that a function was responsible for freeing the memory, but failed.

D105819 added a new visitor to improve memory leak bug reports. In addition to inspecting the ExplodedNodes of the bug pat, the visitor tries to guess whether the function was supposed to free memory, but failed to. Initially (in D108753), this was done by checking whether a CXXDeleteExpr is present in the function. If so, we assume that the function was at least party responsible, and prevent the analyzer from pruning bug report notes in it. This patch improves this heuristic by recognizing all deallocator functions that MallocChecker itself recognizes, by reusing MallocChecker::isFreeingCall.

[Szelethus]

Move CallDescription specific changes to D119004.

[steakhal]

I like it.
nits here and there;

clang/include/clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h

102 ↗

(On Diff #405541)

CallExpr

clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

750

What about having a const reference, or a const pointer to const?

802

You should probably add an example of when is it imprecise and an explanation of why we have this function.

807

837–838

I guess, this gets fixed by this patch.

837–838

Without braces, it would be slightly more compact & readable IMO.

837–838

Could you clarify what this wants to denote? I'm just curious.

1123

clang/test/Analysis/NewDeleteLeaks.cpp

169

I guess we would not have the warning if bar would accept the pointer P, since that way it would escape.
Am I correct?

[Szelethus]

Fixes according to reviewer comments.

clang/test/Analysis/NewDeleteLeaks.cpp

169

That is correct, but as an earlier todo states, we don't currently employ any heuristics to guess whether bar was responsible for storing P (as opposed to deallocating it, which is what this patch is about), but failed to.

[steakhal]

I'm content. Thanks for the patch.

clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

#define CHECK_FN(NAME)                                                         \
   const CallDescriptionMap<CheckFn> FreeingMemFnMap{
       {{"free", 1}, &MallocChecker::checkFree},
       {{"if_freenameindex", 1}, &MallocChecker::checkIfFreeNameIndex},
       {{"kfree", 1}, &MallocChecker::checkFree},
       {{"g_free", 1}, &MallocChecker::checkFree},
   };
 
   bool isFreeingCall(const CallEvent &Call) const;
+  static bool isFreeingOwnershipAttrCall(const FunctionDecl *Func);
+
+  friend class NoOwnershipChangeVisitor;
 
   CallDescriptionMap<CheckFn> AllocatingMemFnMap{
       {{"alloca", 1}, &MallocChecker::checkAlloca},
       {{"_alloca", 1}, &MallocChecker::checkAlloca},
       {{"malloc", 1}, &MallocChecker::checkBasicAlloc},
       {{"malloc", 3}, &MallocChecker::checkKernelMalloc},
       {{"calloc", 2}, &MallocChecker::checkCalloc},
       {{"valloc", 1}, &MallocChecker::checkBasicAlloc},

 } // end anonymous namespace
 
 //===----------------------------------------------------------------------===//
 // Definition of NoOwnershipChangeVisitor.
 //===----------------------------------------------------------------------===//
 
 namespace {
 class NoOwnershipChangeVisitor final : public NoStateChangeFuncVisitor {
+  // The symbol whose (lack of) ownership change we are interested in.
   SymbolRef Sym;
+  const MallocChecker &Checker;
   using OwnerSet = llvm::SmallPtrSet<const MemRegion *, 8>;
 
   // Collect which entities point to the allocated memory, and could be
   // responsible for deallocating it.
   class OwnershipBindingsHandler : public StoreManager::BindingsHandler {
     SymbolRef Sym;
     OwnerSet &Owners;
 
protected:
   getFunctionName(const ExplodedNode *CallEnterN) {
     if (const CallExpr *CE = llvm::dyn_cast_or_null<CallExpr>(
             CallEnterN->getLocationAs<CallEnter>()->getCallExpr()))
       if (const FunctionDecl *FD = CE->getDirectCallee())
         return FD->getQualifiedNameAsString();
     return "";
   }
 
+  /// Syntactically checks whether the callee is a deallocating function. Since
+  /// we have no path-sensitive information on this call (we would need a
+  /// CallEvent instead of a CallExpr for that), its possible that a
+  /// deallocation function was called indirectly through a function pointer,
+  /// but we are not able to tell, so this is a best effort analysis.
+  /// See namespace `memory_passed_to_fn_call_free_through_fn_ptr` in
+  /// clang/test/Analysis/NewDeleteLeaks.cpp.
+  bool isFreeingCallAsWritten(const CallExpr &Call) const {
+    if (Checker.FreeingMemFnMap.lookupAsWritten(Call) ||
+        Checker.ReallocatingMemFnMap.lookupAsWritten(Call))
+      return true;
+
+    if (const auto *Func =
+            llvm::dyn_cast_or_null<FunctionDecl>(Call.getCalleeDecl()))
+      return MallocChecker::isFreeingOwnershipAttrCall(Func);
+
+    return false;
+  }
+
+  /// Heuristically guess whether the callee intended to free memory. This is
+  /// done syntactically, because we are trying to argue about alternative
+  /// paths of execution, and as a consequence we don't have path-sensitive
+  /// information.
   bool doesFnIntendToHandleOwnership(const Decl *Callee, ASTContext &ACtx) {
     using namespace clang::ast_matchers;
     const FunctionDecl *FD = dyn_cast<FunctionDecl>(Callee);
 
     // Given that the stack frame was entered, the body should always be
     // theoretically obtainable. In case of body farms, the synthesized body
     // is not attached to declaration, thus triggering the '!FD->hasBody()'
     // branch. That said, would a synthesized body ever intend to handle
     // ownership? As of today they don't. And if they did, how would we
     // put notes inside it, given that it doesn't match any source locations?
     if (!FD || !FD->hasBody())
       return false;
 
-    // TODO: Operator delete is hardly the only deallocator -- Can we reuse
-    // isFreeingCall() or something thats already here?
-    auto Deallocations = match(
-        stmt(hasDescendant(cxxDeleteExpr().bind("delete"))
-             ), *FD->getBody(), ACtx);
-    // TODO: Ownership my change with an attempt to store the allocated memory.
-    return !Deallocations.empty();
+    auto Matches = match(findAll(stmt(anyOf(cxxDeleteExpr().bind("delete"),
+                                            callExpr().bind("call")))),
+                         *FD->getBody(), ACtx);
+    for (BoundNodes Match : Matches) {
+      if (Match.getNodeAs<CXXDeleteExpr>("delete"))
+        return true;
+
+      if (const auto *Call = Match.getNodeAs<CallExpr>("call"))
+        if (isFreeingCallAsWritten(*Call))
+          return true;
+    }
+    // TODO: Ownership might change with an attempt to store the allocated
+    // memory, not only through deallocation. Check for attempted stores as
+    // well.
+    return false;
   }
 
   virtual bool
   wasModifiedInFunction(const ExplodedNode *CallEnterN,
                         const ExplodedNode *CallExitEndN) override {
     if (!doesFnIntendToHandleOwnership(
             CallExitEndN->getFirstPred()->getLocationContext()->getDecl(),
             CallExitEndN->getState()->getAnalysisManager().getASTContext()))
for (unsigned I = 0; I < Call.getNumArgs() && I < Parameters.size(); ++I) {
       SVal V = Call.getArgSVal(I);
       if (V.getAsSymbol() == Sym)
         return emitNote(N);
     }
     return nullptr;
   }
 
 public:
-  NoOwnershipChangeVisitor(SymbolRef Sym)
-      : NoStateChangeFuncVisitor(bugreporter::TrackingKind::Thorough),
-        Sym(Sym) {}
+  NoOwnershipChangeVisitor(SymbolRef Sym, const MallocChecker *Checker)
+      : NoStateChangeFuncVisitor(bugreporter::TrackingKind::Thorough), Sym(Sym),
+        Checker(*Checker) {}
 
   void Profile(llvm::FoldingSetNodeID &ID) const override {
     static int Tag = 0;
     ID.AddPointer(&Tag);
     ID.AddPointer(Sym);
   }
 
   void *getTag() const {
static bool isStandardNewDelete(const FunctionDecl *FD) {
   return !L.isValid() ||
          FD->getASTContext().getSourceManager().isInSystemHeader(L);
 }
 
 //===----------------------------------------------------------------------===//
 // Methods of MallocChecker and MallocBugVisitor.
 //===----------------------------------------------------------------------===//
 
-bool MallocChecker::isFreeingCall(const CallEvent &Call) const {
-  if (FreeingMemFnMap.lookup(Call) || ReallocatingMemFnMap.lookup(Call))
-    return true;
-
-  const auto *Func = dyn_cast<FunctionDecl>(Call.getDecl());
-  if (Func && Func->hasAttrs()) {
+bool MallocChecker::isFreeingOwnershipAttrCall(const FunctionDecl *Func) {
+  if (Func->hasAttrs()) {
     for (const auto *I : Func->specific_attrs<OwnershipAttr>()) {
       OwnershipAttr::OwnershipKind OwnKind = I->getOwnKind();
       if (OwnKind == OwnershipAttr::Takes || OwnKind == OwnershipAttr::Holds)
         return true;
     }
   }
   return false;
 }
 
+bool MallocChecker::isFreeingCall(const CallEvent &Call) const {
+  if (FreeingMemFnMap.lookup(Call) || ReallocatingMemFnMap.lookup(Call))
+    return true;
+
+  if (const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl()))
+    return isFreeingOwnershipAttrCall(Func);
+
+  return false;
+}
+
 bool MallocChecker::isMemCall(const CallEvent &Call) const {
   if (FreeingMemFnMap.lookup(Call) || AllocatingMemFnMap.lookup(Call) ||
       ReallocatingMemFnMap.lookup(Call))
     return true;
 
   if (!ShouldIncludeOwnershipAnnotatedFunctions)
     return false;
 
void MallocChecker::HandleLeak(SymbolRef Sym, ExplodedNode *N,
   }
 
   auto R = std::make_unique<PathSensitiveBugReport>(
       *BT_Leak[*CheckKind], os.str(), N, LocUsedForUniqueing,
       AllocNode->getLocationContext()->getDecl());
   R->markInteresting(Sym);
   R->addVisitor<MallocBugVisitor>(Sym, true);
   if (ShouldRegisterNoOwnershipChangeVisitor)
-    R->addVisitor<NoOwnershipChangeVisitor>(Sym);
+    R->addVisitor<NoOwnershipChangeVisitor>(Sym, this);
   C.emitReport(std::move(R));
 }
 
 void MallocChecker::checkDeadSymbols(SymbolReaper &SymReaper,
                                      CheckerContext &C) const
 {
   ProgramStateRef state = C.getState();
   RegionStateTy OldRS = state->get<RegionState>();

clang/test/Analysis/NewDeleteLeaks.cpp

 
 void foo() {
   sink(new int(5)); // expected-note {{Memory is allocated}}
 } // expected-warning {{Potential memory leak [cplusplus.NewDeleteLeaks]}}
 // expected-note@-1 {{Potential memory leak}}
 
 } // namespace memory_allocated_in_fn_call
 
-namespace memory_passed_to_fn_call {
+// Realize that sink() intends to deallocate memory, assume that it should've
+// taken care of the leaked object as well.
+namespace memory_passed_to_fn_call_delete {
 
 void sink(int *P) {
   if (coin()) // ownership-note {{Assuming the condition is false}}
               // ownership-note@-1 {{Taking false branch}}
     delete P;
 } // ownership-note {{Returning without deallocating memory or storing the pointer for later deallocation}}
 
 void foo() {
   int *ptr = new int(5); // expected-note {{Memory is allocated}}
   sink(ptr);             // ownership-note {{Calling 'sink'}}
                          // ownership-note@-1 {{Returning from 'sink'}}
 } // expected-warning {{Potential leak of memory pointed to by 'ptr' [cplusplus.NewDeleteLeaks]}}
 // expected-note@-1 {{Potential leak}}
 
-} // namespace memory_passed_to_fn_call
+} // namespace memory_passed_to_fn_call_delete
+
+namespace memory_passed_to_fn_call_free {
+
+void sink(int *P) {
+  if (coin()) // ownership-note {{Assuming the condition is false}}
+              // ownership-note@-1 {{Taking false branch}}
+    free(P);
+} // ownership-note {{Returning without deallocating memory or storing the pointer for later deallocation}}
+
+void foo() {
+  int *ptr = (int *)malloc(sizeof(int)); // expected-note {{Memory is allocated}}
+  sink(ptr);                             // ownership-note {{Calling 'sink'}}
+                                         // ownership-note@-1 {{Returning from 'sink'}}
+} // expected-warning {{Potential leak of memory pointed to by 'ptr' [unix.Malloc]}}
+// expected-note@-1 {{Potential leak}}
+
+} // namespace memory_passed_to_fn_call_free
+
+// Function pointers cannot be resolved syntactically.
+namespace memory_passed_to_fn_call_free_through_fn_ptr {
+void (*freeFn)(void *) = free;
+
+void sink(int *P) {
+  if (coin())
+    freeFn(P);
+}
+
+void foo() {
+  int *ptr = (int *)malloc(sizeof(int)); // expected-note {{Memory is allocated}}
+  sink(ptr);
+} // expected-warning {{Potential leak of memory pointed to by 'ptr' [unix.Malloc]}}
+// expected-note@-1 {{Potential leak}}
+
+} // namespace memory_passed_to_fn_call_free_through_fn_ptr
 
 namespace memory_shared_with_ptr_of_shorter_lifetime {
 
 void sink(int *P) {
   int *Q = P;
   if (coin()) // ownership-note {{Assuming the condition is false}}
               // ownership-note@-1 {{Taking false branch}}
     delete P;

 void foo() {
   int *ptr = new int(5); // expected-note {{Memory is allocated}}
   sink(ptr);
 } // expected-warning {{Potential leak of memory pointed to by 'ptr' [cplusplus.NewDeleteLeaks]}}
 // expected-note@-1 {{Potential leak}}
 
 } // namespace memory_passed_into_fn_that_doesnt_intend_to_free
 
+namespace memory_passed_into_fn_that_doesnt_intend_to_free2 {
+
+void bar();
+
+void sink(int *P) {
+  // Correctly realize that calling bar() doesn't mean that this function would
+  // like to deallocate anything.
+  bar();
+}
+
+void foo() {
+  int *ptr = new int(5); // expected-note {{Memory is allocated}}
+  sink(ptr);
+} // expected-warning {{Potential leak of memory pointed to by 'ptr' [cplusplus.NewDeleteLeaks]}}
+// expected-note@-1 {{Potential leak}}
+
+} // namespace memory_passed_into_fn_that_doesnt_intend_to_free2
+
 namespace refkind_from_unoallocated_to_allocated {
 
 // RefKind of the symbol changed from nothing to Allocated. We don't want to
 // emit notes when the RefKind changes in the stack frame.
 static char *malloc_wrapper_ret() {
   return (char *)malloc(12); // expected-note {{Memory is allocated}}
 }
 void use_ret() {
   char *v;
   v = malloc_wrapper_ret(); // expected-note {{Calling 'malloc_wrapper_ret'}}
                             // expected-note@-1 {{Returned allocated memory}}
 } // expected-warning {{Potential leak of memory pointed to by 'v' [unix.Malloc]}}
 // expected-note@-1 {{Potential leak of memory pointed to by 'v'}}
 
 } // namespace refkind_from_unoallocated_to_allocated