[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

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

818–820

I guess, this gets fixed by this patch.

820–832

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

832

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

1104

clang/test/Analysis/NewDeleteLeaks.cpp

152

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

152

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/include/clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h

public:
 
   /// Returns true if the CallEvent is a call to a function that matches
   /// the CallDescription.
   ///
   /// \note This function is not intended to be used to match Obj-C method
   /// calls.
   bool matches(const CallEvent &Call) const;
 
+  /// Returns true if the CallEvent is a call to a function that matches
+  /// the CallDescription.
+  ///
+  /// When available, always prefer matching with a CallEvent! This function
+  /// exists only when that is not available, for example, when _only_
+  /// syntactic check is done on a piece of code.
+  ///
+  /// Also, StdLibraryFunctionsChecker::Signature is likely a better candicade
+  /// for syntactic only matching if you are writing a new checker. This is
+  /// handy if a CallDescriptionMap is already there.
+  ///
+  /// The function is imprecise because CallEvent understands the precise
+  /// argument count better (see comments for CallEvent::getNumArgs).
+  bool matchesImprecise(const CallExpr &CE) const;
+
+private:
+  bool matchesImpl(const FunctionDecl *Callee, size_t ArgCount,
+                   size_t ParamCount) const;
+
+public:
   /// Returns true whether the CallEvent matches on any of the CallDescriptions
   /// supplied.
   ///
   /// \note This function is not intended to be used to match Obj-C method
   /// calls.
   friend bool matchesAny(const CallEvent &Call, const CallDescription &CD1) {
     return CD1.matches(Call);
   }
LLVM_NODISCARD const T *lookup(const CallEvent &Call) const {
     // Slow path: linear lookup.
     // TODO: Implement some sort of fast path.
     for (const std::pair<CallDescription, T> &I : LinearMap)
       if (I.first.matches(Call))
         return &I.second;
 
     return nullptr;
   }
+
+  /// ALWAYS prefer lookup with a CallEvent, when available. See comments above
+  /// CallDescription::matchesImprecise.
+  LLVM_NODISCARD const T *lookupImprecise(const CallExpr &Call) const {
+    // Slow path: linear lookup.
+    // TODO: Implement some sort of fast path.
+    for (const std::pair<CallDescription, T> &I : LinearMap)
+      if (I.first.matchesImprecise(Call))
+        return &I.second;
+
+    return nullptr;
+  }
 };
 
 /// An immutable set of CallDescriptions.
 /// Checkers can efficiently decide if a given CallEvent matches any
 /// CallDescription in the set.
 class CallDescriptionSet {
   CallDescriptionMap<bool /*unused*/> Impl = {};
 

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 "";
   }
 
+  bool isFreeingCallImprecise(const CallExpr &Call) const {
+    if (Checker->FreeingMemFnMap.lookupImprecise(Call) ||
+        Checker->ReallocatingMemFnMap.lookupImprecise(Call))
+      return true;
+
+    if (const auto *Func = dyn_cast<FunctionDecl>(Call.getCalleeDecl()))
+      return MallocChecker::isFreeingOwnershipAttrCall(Func);
+
+    return false;
+  }
+
   bool doesFnIntendToHandleOwnership(const Decl *Callee, ASTContext &ACtx) {
     using namespace clang::ast_matchers;
     const FunctionDecl *FD = dyn_cast<FunctionDecl>(Callee);
     if (!FD)
       return false;
-    // TODO: Operator delete is hardly the only deallocator -- Can we reuse
+    // TODO: Operator delete is hardly the only deallocatr -- Can we reuse
     // isFreeingCall() or something thats already here?
-    auto Deallocations = match(
-        stmt(hasDescendant(cxxDeleteExpr().bind("delete"))
-             ), *FD->getBody(), ACtx);
+    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 (isFreeingCallImprecise(*Call))
+          return true;
+      }
+    }
     // TODO: Ownership my change with an attempt to store the allocated memory.
-    return !Deallocations.empty();
+    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<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/lib/StaticAnalyzer/Core/CallDescription.cpp

 //===- CallDescription.cpp - function/method call matching     --*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 /// \file This file defines a generic mechanism for matching for function and
 /// method calls of C, C++, and Objective-C languages. Instances of these
 /// classes are frequently used together with the CallEvent classes.
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
+#include "clang/AST/Decl.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/Optional.h"
 #include <iterator>
 
 using namespace llvm;
 using namespace clang;
bool ento::CallDescription::matches(const CallEvent &Call) const {
   // FIXME: Add ObjC Message support.
   if (Call.getKind() == CE_ObjCMessage)
     return false;
 
   const auto *FD = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
   if (!FD)
     return false;
 
+  return matchesImpl(FD, Call.getNumArgs(), Call.parameters().size());
+}
+
+bool ento::CallDescription::matchesImprecise(const CallExpr &CE) const {
+  const auto *FD = dyn_cast_or_null<FunctionDecl>(CE.getCalleeDecl());
+  if (!FD)
+    return false;
+
+  return matchesImpl(FD, CE.getNumArgs(), FD->param_size());
+}
+
+bool ento::CallDescription::matchesImpl(const FunctionDecl *Callee,
+                                        size_t ArgCount,
+                                        size_t ParamCount) const {
+  const auto *FD = Callee;
+  if (!FD)
+    return false;
+
   if (Flags & CDF_MaybeBuiltin) {
     return CheckerContext::isCLibraryFunction(FD, getFunctionName()) &&
-           (!RequiredArgs || *RequiredArgs <= Call.getNumArgs()) &&
-           (!RequiredParams || *RequiredParams <= Call.parameters().size());
+           (!RequiredArgs || *RequiredArgs <= ArgCount) &&
+           (!RequiredParams || *RequiredParams <= ParamCount);
   }
 
   if (!II.hasValue()) {
-    II = &Call.getState()->getStateManager().getContext().Idents.get(
-        getFunctionName());
+    II = &FD->getASTContext().Idents.get(getFunctionName());
   }
 
   const auto MatchNameOnly = [](const CallDescription &CD,
                                 const NamedDecl *ND) -> bool {
     DeclarationName Name = ND->getDeclName();
     if (const auto *II = Name.getAsIdentifierInfo())
       return II == CD.II.getValue(); // Fast case.
 
     // Fallback to the slow stringification and comparison for:
     // C++ overloaded operators, constructors, destructors, etc.
     // FIXME This comparison is way SLOWER than comparing pointers.
     // At some point in the future, we should compare FunctionDecl pointers.
     return Name.getAsString() == CD.getFunctionName();
   };
 
   const auto ExactMatchArgAndParamCounts =
-      [](const CallEvent &Call, const CallDescription &CD) -> bool {
-    const bool ArgsMatch =
-        !CD.RequiredArgs || *CD.RequiredArgs == Call.getNumArgs();
+      [](size_t ArgCount, size_t ParamCount,
+         const CallDescription &CD) -> bool {
+    const bool ArgsMatch = !CD.RequiredArgs || *CD.RequiredArgs == ArgCount;
     const bool ParamsMatch =
-        !CD.RequiredParams || *CD.RequiredParams == Call.parameters().size();
+        !CD.RequiredParams || *CD.RequiredParams == ParamCount;
     return ArgsMatch && ParamsMatch;
   };
 
   const auto MatchQualifiedNameParts = [](const CallDescription &CD,
                                           const Decl *D) -> bool {
     const auto FindNextNamespaceOrRecord =
         [](const DeclContext *Ctx) -> const DeclContext * {
       while (Ctx && !isa<NamespaceDecl, RecordDecl>(Ctx))
for (; Ctx && QualifierPartsIt != QualifierPartsEndIt;
       ++QualifierPartsIt;
     }
 
     // We matched if we consumed all expected qualifier segments.
     return QualifierPartsIt == QualifierPartsEndIt;
   };
 
   // Let's start matching...
-  if (!ExactMatchArgAndParamCounts(Call, *this))
+  if (!ExactMatchArgAndParamCounts(ArgCount, ParamCount, *this))
     return false;
 
   if (!MatchNameOnly(*this, FD))
     return false;
 
   if (!hasQualifiedNameParts())
     return true;
 

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
 
 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