//=== MallocChecker.cpp - A malloc/free checker -------------------*- 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

//

//===----------------------------------------------------------------------===//

//

// This file defines a variety of memory management related checkers, such as

// leak, double free, and use-after-free.

//

// The following checkers are defined here:

//

//   * MallocChecker

//       Despite its name, it models all sorts of memory allocations and

//       de- or reallocation, including but not limited to malloc, free,

//       relloc, new, delete. It also reports on a variety of memory misuse

//       errors.

//       Many other checkers interact very closely with this checker, in fact,

//       most are merely options to this one. Other checkers may register

//       MallocChecker, but do not enable MallocChecker's reports (more details

//       to follow around its field, ChecksEnabled).

//       It also has a boolean "Optimistic" checker option, which if set to true

//       will cause the checker to model user defined memory management related

//       functions annotated via the attribute ownership_takes, ownership_holds

//       and ownership_returns.

//

//   * NewDeleteChecker

//       Enables the modeling of new, new[], delete, delete[] in MallocChecker,

//       and checks for related double-free and use-after-free errors.

//

//   * NewDeleteLeaksChecker

//       Checks for leaks related to new, new[], delete, delete[].

//       Depends on NewDeleteChecker.

//

//   * MismatchedDeallocatorChecker

//       Enables checking whether memory is deallocated with the correspending

//       allocation function in MallocChecker, such as malloc() allocated

//       regions are only freed by free(), new by delete, new[] by delete[].

//

//  InnerPointerChecker interacts very closely with MallocChecker, but unlike

//  the above checkers, it has it's own file, hence the many InnerPointerChecker

//  related headers and non-static functions.

//

//===----------------------------------------------------------------------===//

#include "AllocationState.h"

#include "InterCheckerAPI.h"

#include "clang/AST/Attr.h"

#include "clang/AST/DeclCXX.h"

#include "clang/AST/DeclTemplate.h"

#include "clang/AST/Expr.h"

#include "clang/AST/ExprCXX.h"

#include "clang/AST/ParentMap.h"

#include "clang/ASTMatchers/ASTMatchFinder.h"

#include "clang/ASTMatchers/ASTMatchers.h"

#include "clang/Analysis/ProgramPoint.h"

#include "clang/Basic/LLVM.h"

#include "clang/Basic/SourceManager.h"

#include "clang/Basic/TargetInfo.h"

#include "clang/Lex/Lexer.h"

#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"

#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"

#include "clang/StaticAnalyzer/Core/BugReporter/CommonBugCategories.h"

#include "clang/StaticAnalyzer/Core/Checker.h"

#include "clang/StaticAnalyzer/Core/CheckerManager.h"

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

#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"

#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"

#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"

#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h"

#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"

#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"

#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"

#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"

#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"

#include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h"

#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"

#include "llvm/ADT/STLExtras.h"

#include "llvm/ADT/SetOperations.h"

#include "llvm/ADT/SmallString.h"

#include "llvm/ADT/StringExtras.h"

#include "llvm/Support/Casting.h"

#include "llvm/Support/Compiler.h"

#include "llvm/Support/ErrorHandling.h"

#include "llvm/Support/raw_ostream.h"

#include <climits>

#include <functional>

#include <optional>

#include <utility>

using namespace clang;

using namespace ento;

using namespace std::placeholders;

//===----------------------------------------------------------------------===//

// The types of allocation we're modeling. This is used to check whether a

// dynamically allocated object is deallocated with the correct function, like

// not using operator delete on an object created by malloc(), or alloca regions

// aren't ever deallocated manually.

//===----------------------------------------------------------------------===//

namespace {

// Used to check correspondence between allocators and deallocators.

enum AllocationFamily {

  AF_None,

  AF_Malloc,

  AF_CXXNew,

  AF_CXXNewArray,

  AF_IfNameIndex,

  AF_Alloca,

  AF_InnerBuffer

};

} // end of anonymous namespace

/// Print names of allocators and deallocators.

///

/// \returns true on success.

static bool printMemFnName(raw_ostream &os, CheckerContext &C, const Expr *E);

/// Print expected name of an allocator based on the deallocator's family

/// derived from the DeallocExpr.

static void printExpectedAllocName(raw_ostream &os, AllocationFamily Family);

/// Print expected name of a deallocator based on the allocator's

/// family.

static void printExpectedDeallocName(raw_ostream &os, AllocationFamily Family);

//===----------------------------------------------------------------------===//

// The state of a symbol, in terms of memory management.

//===----------------------------------------------------------------------===//

namespace {

class RefState {

  enum Kind {

    // Reference to allocated memory.

    Allocated,

    // Reference to zero-allocated memory.

    AllocatedOfSizeZero,

    // Reference to released/freed memory.

    Released,

    // The responsibility for freeing resources has transferred from

    // this reference. A relinquished symbol should not be freed.

    Relinquished,

    // We are no longer guaranteed to have observed all manipulations

    // of this pointer/memory. For example, it could have been

    // passed as a parameter to an opaque function.

    Escaped

  };

  const Stmt *S;

  Kind K;

  AllocationFamily Family;

  RefState(Kind k, const Stmt *s, AllocationFamily family)

      : S(s), K(k), Family(family) {

    assert(family != AF_None);

  }

public:

  bool isAllocated() const { return K == Allocated; }

  bool isAllocatedOfSizeZero() const { return K == AllocatedOfSizeZero; }

  bool isReleased() const { return K == Released; }

  bool isRelinquished() const { return K == Relinquished; }

  bool isEscaped() const { return K == Escaped; }

  AllocationFamily getAllocationFamily() const { return Family; }

  const Stmt *getStmt() const { return S; }

  bool operator==(const RefState &X) const {

    return K == X.K && S == X.S && Family == X.Family;

  }

  static RefState getAllocated(AllocationFamily family, const Stmt *s) {

    return RefState(Allocated, s, family);

  }

  static RefState getAllocatedOfSizeZero(const RefState *RS) {

    return RefState(AllocatedOfSizeZero, RS->getStmt(),

                    RS->getAllocationFamily());

  }

  static RefState getReleased(AllocationFamily family, const Stmt *s) {

    return RefState(Released, s, family);

  }

  static RefState getRelinquished(AllocationFamily family, const Stmt *s) {

    return RefState(Relinquished, s, family);

  }

  static RefState getEscaped(const RefState *RS) {

    return RefState(Escaped, RS->getStmt(), RS->getAllocationFamily());

  }

  void Profile(llvm::FoldingSetNodeID &ID) const {

    ID.AddInteger(K);

    ID.AddPointer(S);

    ID.AddInteger(Family);

  }

  LLVM_DUMP_METHOD void dump(raw_ostream &OS) const {

    switch (K) {

#define CASE(ID) case ID: OS << #ID; break;

    CASE(Allocated)

    CASE(AllocatedOfSizeZero)

    CASE(Released)

    CASE(Relinquished)

    CASE(Escaped)

    }

  }

  LLVM_DUMP_METHOD void dump() const { dump(llvm::errs()); }

};

} // end of anonymous namespace

REGISTER_MAP_WITH_PROGRAMSTATE(RegionState, SymbolRef, RefState)

/// Check if the memory associated with this symbol was released.

static bool isReleased(SymbolRef Sym, CheckerContext &C);

/// Update the RefState to reflect the new memory allocation.

/// The optional \p RetVal parameter specifies the newly allocated pointer

/// value; if unspecified, the value of expression \p E is used.

static ProgramStateRef

MallocUpdateRefState(CheckerContext &C, const Expr *E, ProgramStateRef State,

                     AllocationFamily Family,

                     std::optional<SVal> RetVal = std::nullopt);

//===----------------------------------------------------------------------===//

// The modeling of memory reallocation.

//

// The terminology 'toPtr' and 'fromPtr' will be used:

//   toPtr = realloc(fromPtr, 20);

//===----------------------------------------------------------------------===//

REGISTER_SET_WITH_PROGRAMSTATE(ReallocSizeZeroSymbols, SymbolRef)

namespace {

/// The state of 'fromPtr' after reallocation is known to have failed.

enum OwnershipAfterReallocKind {

  // The symbol needs to be freed (e.g.: realloc)

  OAR_ToBeFreedAfterFailure,

  // The symbol has been freed (e.g.: reallocf)

  OAR_FreeOnFailure,

  // The symbol doesn't have to freed (e.g.: we aren't sure if, how and where

  // 'fromPtr' was allocated:

  //    void Haha(int *ptr) {

  //      ptr = realloc(ptr, 67);

  //      // ...

  //    }

  // ).

  OAR_DoNotTrackAfterFailure

};

/// Stores information about the 'fromPtr' symbol after reallocation.

///

/// This is important because realloc may fail, and that needs special modeling.

/// Whether reallocation failed or not will not be known until later, so we'll

/// store whether upon failure 'fromPtr' will be freed, or needs to be freed

/// later, etc.

struct ReallocPair {

  // The 'fromPtr'.

  SymbolRef ReallocatedSym;

  OwnershipAfterReallocKind Kind;

  ReallocPair(SymbolRef S, OwnershipAfterReallocKind K)

      : ReallocatedSym(S), Kind(K) {}

  void Profile(llvm::FoldingSetNodeID &ID) const {

    ID.AddInteger(Kind);

    ID.AddPointer(ReallocatedSym);

  }

  bool operator==(const ReallocPair &X) const {

    return ReallocatedSym == X.ReallocatedSym &&

           Kind == X.Kind;

  }

};

} // end of anonymous namespace

REGISTER_MAP_WITH_PROGRAMSTATE(ReallocPairs, SymbolRef, ReallocPair)

/// Tells if the callee is one of the builtin new/delete operators, including

/// placement operators and other standard overloads.

static bool isStandardNewDelete(const FunctionDecl *FD);

static bool isStandardNewDelete(const CallEvent &Call) {

  if (!Call.getDecl() || 
!isa<FunctionDecl>(Call.getDecl())30.5k
)

    return false;

  return isStandardNewDelete(cast<FunctionDecl>(Call.getDecl()));

}

//===----------------------------------------------------------------------===//

// Definition of the MallocChecker class.

//===----------------------------------------------------------------------===//

namespace {

class MallocChecker

    : public Checker<check::DeadSymbols, check::PointerEscape,

                     check::ConstPointerEscape, check::PreStmt<ReturnStmt>,

                     check::EndFunction, check::PreCall, check::PostCall,

                     check::NewAllocator, check::PostStmt<BlockExpr>,

                     check::PostObjCMessage, check::Location, eval::Assume> {

public:

  /// In pessimistic mode, the checker assumes that it does not know which

  /// functions might free the memory.

  /// In optimistic mode, the checker assumes that all user-defined functions

  /// which might free a pointer are annotated.

  bool ShouldIncludeOwnershipAnnotatedFunctions = false;

  bool ShouldRegisterNoOwnershipChangeVisitor = false;

  /// Many checkers are essentially built into this one, so enabling them will

  /// make MallocChecker perform additional modeling and reporting.

  enum CheckKind {

    /// When a subchecker is enabled but MallocChecker isn't, model memory

    /// management but do not emit warnings emitted with MallocChecker only

    /// enabled.

    CK_MallocChecker,

    CK_NewDeleteChecker,

    CK_NewDeleteLeaksChecker,

    CK_MismatchedDeallocatorChecker,

    CK_InnerPointerChecker,

    CK_NumCheckKinds

  };

  using LeakInfo = std::pair<const ExplodedNode *, const MemRegion *>;

  bool ChecksEnabled[CK_NumCheckKinds] = {false};

  CheckerNameRef CheckNames[CK_NumCheckKinds];

  void checkPreCall(const CallEvent &Call, CheckerContext &C) const;

  void checkPostCall(const CallEvent &Call, CheckerContext &C) const;

  void checkNewAllocator(const CXXAllocatorCall &Call, CheckerContext &C) const;

  void checkPostObjCMessage(const ObjCMethodCall &Call, CheckerContext &C) const;

  void checkPostStmt(const BlockExpr *BE, CheckerContext &C) const;

  void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const;

  void checkPreStmt(const ReturnStmt *S, CheckerContext &C) const;

  void checkEndFunction(const ReturnStmt *S, CheckerContext &C) const;

  ProgramStateRef evalAssume(ProgramStateRef state, SVal Cond,

                            bool Assumption) const;

  void checkLocation(SVal l, bool isLoad, const Stmt *S,

                     CheckerContext &C) const;

  ProgramStateRef checkPointerEscape(ProgramStateRef State,

                                    const InvalidatedSymbols &Escaped,

                                    const CallEvent *Call,

                                    PointerEscapeKind Kind) const;

  ProgramStateRef checkConstPointerEscape(ProgramStateRef State,

                                          const InvalidatedSymbols &Escaped,

                                          const CallEvent *Call,

                                          PointerEscapeKind Kind) const;

  void printState(raw_ostream &Out, ProgramStateRef State,

                  const char *NL, const char *Sep) const override;

private:

  mutable std::unique_ptr<BugType> BT_DoubleFree[CK_NumCheckKinds];

  mutable std::unique_ptr<BugType> BT_DoubleDelete;

  mutable std::unique_ptr<BugType> BT_Leak[CK_NumCheckKinds];

  mutable std::unique_ptr<BugType> BT_UseFree[CK_NumCheckKinds];

  mutable std::unique_ptr<BugType> BT_BadFree[CK_NumCheckKinds];

  mutable std::unique_ptr<BugType> BT_FreeAlloca[CK_NumCheckKinds];

  mutable std::unique_ptr<BugType> BT_MismatchedDealloc;

  mutable std::unique_ptr<BugType> BT_OffsetFree[CK_NumCheckKinds];

  mutable std::unique_ptr<BugType> BT_UseZerroAllocated[CK_NumCheckKinds];

#define CHECK_FN(NAME)                                                         \

  void NAME(const CallEvent &Call, CheckerContext &C) const;

  CHECK_FN(checkFree)

  CHECK_FN(checkIfNameIndex)

  CHECK_FN(checkBasicAlloc)

  CHECK_FN(checkKernelMalloc)

  CHECK_FN(checkCalloc)

  CHECK_FN(checkAlloca)

  CHECK_FN(checkStrdup)

  CHECK_FN(checkIfFreeNameIndex)

  CHECK_FN(checkCXXNewOrCXXDelete)

  CHECK_FN(checkGMalloc0)

  CHECK_FN(checkGMemdup)

  CHECK_FN(checkGMallocN)

  CHECK_FN(checkGMallocN0)

  CHECK_FN(checkReallocN)

  CHECK_FN(checkOwnershipAttr)

  void checkRealloc(const CallEvent &Call, CheckerContext &C,

                    bool ShouldFreeOnFail) const;

  using CheckFn = std::function<void(const MallocChecker *,

                                     const CallEvent &Call, CheckerContext &C)>;

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

      {{CDF_MaybeBuiltin, {"strndup"}, 2}, &MallocChecker::checkStrdup},

      {{CDF_MaybeBuiltin, {"strdup"}, 1}, &MallocChecker::checkStrdup},

      {{{"_strdup"}, 1}, &MallocChecker::checkStrdup},

      {{{"kmalloc"}, 2}, &MallocChecker::checkKernelMalloc},

      {{{"if_nameindex"}, 1}, &MallocChecker::checkIfNameIndex},

      {{CDF_MaybeBuiltin, {"wcsdup"}, 1}, &MallocChecker::checkStrdup},

      {{CDF_MaybeBuiltin, {"_wcsdup"}, 1}, &MallocChecker::checkStrdup},

      {{{"g_malloc"}, 1}, &MallocChecker::checkBasicAlloc},

      {{{"g_malloc0"}, 1}, &MallocChecker::checkGMalloc0},

      {{{"g_try_malloc"}, 1}, &MallocChecker::checkBasicAlloc},

      {{{"g_try_malloc0"}, 1}, &MallocChecker::checkGMalloc0},

      {{{"g_memdup"}, 2}, &MallocChecker::checkGMemdup},

      {{{"g_malloc_n"}, 2}, &MallocChecker::checkGMallocN},

      {{{"g_malloc0_n"}, 2}, &MallocChecker::checkGMallocN0},

      {{{"g_try_malloc_n"}, 2}, &MallocChecker::checkGMallocN},

      {{{"g_try_malloc0_n"}, 2}, &MallocChecker::checkGMallocN0},

  };

  CallDescriptionMap<CheckFn> ReallocatingMemFnMap{

      {{{"realloc"}, 2},

       std::bind(&MallocChecker::checkRealloc, _1, _2, _3, false)},

      {{{"reallocf"}, 2},

       std::bind(&MallocChecker::checkRealloc, _1, _2, _3, true)},

      {{{"g_realloc"}, 2},

       std::bind(&MallocChecker::checkRealloc, _1, _2, _3, false)},

      {{{"g_try_realloc"}, 2},

       std::bind(&MallocChecker::checkRealloc, _1, _2, _3, false)},

      {{{"g_realloc_n"}, 3}, &MallocChecker::checkReallocN},

      {{{"g_try_realloc_n"}, 3}, &MallocChecker::checkReallocN},

  };

  bool isMemCall(const CallEvent &Call) const;

  // TODO: Remove mutable by moving the initializtaion to the registry function.

  mutable std::optional<uint64_t> KernelZeroFlagVal;

  using KernelZeroSizePtrValueTy = std::optional<int>;

  /// Store the value of macro called `ZERO_SIZE_PTR`.

  /// The value is initialized at first use, before first use the outer

  /// Optional is empty, afterwards it contains another Optional that indicates

  /// if the macro value could be determined, and if yes the value itself.

  mutable std::optional<KernelZeroSizePtrValueTy> KernelZeroSizePtrValue;

  /// Process C++ operator new()'s allocation, which is the part of C++

  /// new-expression that goes before the constructor.

  [[nodiscard]] ProgramStateRef

  processNewAllocation(const CXXAllocatorCall &Call, CheckerContext &C,

                       AllocationFamily Family) const;

  /// Perform a zero-allocation check.

  ///

  /// \param [in] Call The expression that allocates memory.

  /// \param [in] IndexOfSizeArg Index of the argument that specifies the size

  ///   of the memory that needs to be allocated. E.g. for malloc, this would be

  ///   0.

  /// \param [in] RetVal Specifies the newly allocated pointer value;

  ///   if unspecified, the value of expression \p E is used.

  [[nodiscard]] static ProgramStateRef

  ProcessZeroAllocCheck(const CallEvent &Call, const unsigned IndexOfSizeArg,

                        ProgramStateRef State,

                        std::optional<SVal> RetVal = std::nullopt);

  /// Model functions with the ownership_returns attribute.

  ///

  /// User-defined function may have the ownership_returns attribute, which

  /// annotates that the function returns with an object that was allocated on

  /// the heap, and passes the ownertship to the callee.

  ///

  ///   void __attribute((ownership_returns(malloc, 1))) *my_malloc(size_t);

  ///

  /// It has two parameters:

  ///   - first: name of the resource (e.g. 'malloc')

  ///   - (OPTIONAL) second: size of the allocated region

  ///

  /// \param [in] Call The expression that allocates memory.

  /// \param [in] Att The ownership_returns attribute.

  /// \param [in] State The \c ProgramState right before allocation.

  /// \returns The ProgramState right after allocation.

  [[nodiscard]] ProgramStateRef

  MallocMemReturnsAttr(CheckerContext &C, const CallEvent &Call,

                       const OwnershipAttr *Att, ProgramStateRef State) const;

  /// Models memory allocation.

  ///

  /// \param [in] Call The expression that allocates memory.

  /// \param [in] SizeEx Size of the memory that needs to be allocated.

  /// \param [in] Init The value the allocated memory needs to be initialized.

  /// with. For example, \c calloc initializes the allocated memory to 0,

  /// malloc leaves it undefined.

  /// \param [in] State The \c ProgramState right before allocation.

  /// \returns The ProgramState right after allocation.

  [[nodiscard]] static ProgramStateRef

  MallocMemAux(CheckerContext &C, const CallEvent &Call, const Expr *SizeEx,

               SVal Init, ProgramStateRef State, AllocationFamily Family);

  /// Models memory allocation.

  ///

  /// \param [in] Call The expression that allocates memory.

  /// \param [in] Size Size of the memory that needs to be allocated.

  /// \param [in] Init The value the allocated memory needs to be initialized.

  /// with. For example, \c calloc initializes the allocated memory to 0,

  /// malloc leaves it undefined.

  /// \param [in] State The \c ProgramState right before allocation.

  /// \returns The ProgramState right after allocation.

  [[nodiscard]] static ProgramStateRef

  MallocMemAux(CheckerContext &C, const CallEvent &Call, SVal Size, SVal Init,

               ProgramStateRef State, AllocationFamily Family);

  // Check if this malloc() for special flags. At present that means M_ZERO or

  // __GFP_ZERO (in which case, treat it like calloc).

  [[nodiscard]] std::optional<ProgramStateRef>

  performKernelMalloc(const CallEvent &Call, CheckerContext &C,

                      const ProgramStateRef &State) const;

  /// Model functions with the ownership_takes and ownership_holds attributes.

  ///

  /// User-defined function may have the ownership_takes and/or ownership_holds

  /// attributes, which annotates that the function frees the memory passed as a

  /// parameter.

  ///

  ///   void __attribute((ownership_takes(malloc, 1))) my_free(void *);

  ///   void __attribute((ownership_holds(malloc, 1))) my_hold(void *);

  ///

  /// They have two parameters:

  ///   - first: name of the resource (e.g. 'malloc')

  ///   - second: index of the parameter the attribute applies to

  ///

  /// \param [in] Call The expression that frees memory.

  /// \param [in] Att The ownership_takes or ownership_holds attribute.

  /// \param [in] State The \c ProgramState right before allocation.

  /// \returns The ProgramState right after deallocation.

  [[nodiscard]] ProgramStateRef FreeMemAttr(CheckerContext &C,

                                            const CallEvent &Call,

                                            const OwnershipAttr *Att,

                                            ProgramStateRef State) const;

  /// Models memory deallocation.

  ///

  /// \param [in] Call The expression that frees memory.

  /// \param [in] State The \c ProgramState right before allocation.

  /// \param [in] Num Index of the argument that needs to be freed. This is

  ///   normally 0, but for custom free functions it may be different.

  /// \param [in] Hold Whether the parameter at \p Index has the ownership_holds

  ///   attribute.

  /// \param [out] IsKnownToBeAllocated Whether the memory to be freed is known

  ///   to have been allocated, or in other words, the symbol to be freed was

  ///   registered as allocated by this checker. In the following case, \c ptr

  ///   isn't known to be allocated.

  ///      void Haha(int *ptr) {

  ///        ptr = realloc(ptr, 67);

  ///        // ...

  ///      }

  /// \param [in] ReturnsNullOnFailure Whether the memory deallocation function

  ///   we're modeling returns with Null on failure.

  /// \returns The ProgramState right after deallocation.

  [[nodiscard]] ProgramStateRef

  FreeMemAux(CheckerContext &C, const CallEvent &Call, ProgramStateRef State,

             unsigned Num, bool Hold, bool &IsKnownToBeAllocated,

             AllocationFamily Family, bool ReturnsNullOnFailure = false) const;

  /// Models memory deallocation.

  ///

  /// \param [in] ArgExpr The variable who's pointee needs to be freed.

  /// \param [in] Call The expression that frees the memory.

  /// \param [in] State The \c ProgramState right before allocation.

  ///   normally 0, but for custom free functions it may be different.

  /// \param [in] Hold Whether the parameter at \p Index has the ownership_holds

  ///   attribute.

  /// \param [out] IsKnownToBeAllocated Whether the memory to be freed is known

  ///   to have been allocated, or in other words, the symbol to be freed was

  ///   registered as allocated by this checker. In the following case, \c ptr

  ///   isn't known to be allocated.

  ///      void Haha(int *ptr) {

  ///        ptr = realloc(ptr, 67);

  ///        // ...

  ///      }

  /// \param [in] ReturnsNullOnFailure Whether the memory deallocation function

  ///   we're modeling returns with Null on failure.

  /// \returns The ProgramState right after deallocation.

  [[nodiscard]] ProgramStateRef

  FreeMemAux(CheckerContext &C, const Expr *ArgExpr, const CallEvent &Call,

             ProgramStateRef State, bool Hold, bool &IsKnownToBeAllocated,

             AllocationFamily Family, bool ReturnsNullOnFailure = false) const;

  // TODO: Needs some refactoring, as all other deallocation modeling

  // functions are suffering from out parameters and messy code due to how

  // realloc is handled.

  //

  /// Models memory reallocation.

  ///

  /// \param [in] Call The expression that reallocated memory

  /// \param [in] ShouldFreeOnFail Whether if reallocation fails, the supplied

  ///   memory should be freed.

  /// \param [in] State The \c ProgramState right before reallocation.

  /// \param [in] SuffixWithN Whether the reallocation function we're modeling

  ///   has an '_n' suffix, such as g_realloc_n.

  /// \returns The ProgramState right after reallocation.

  [[nodiscard]] ProgramStateRef

  ReallocMemAux(CheckerContext &C, const CallEvent &Call, bool ShouldFreeOnFail,

                ProgramStateRef State, AllocationFamily Family,

                bool SuffixWithN = false) const;

  /// Evaluates the buffer size that needs to be allocated.

  ///

  /// \param [in] Blocks The amount of blocks that needs to be allocated.

  /// \param [in] BlockBytes The size of a block.

  /// \returns The symbolic value of \p Blocks * \p BlockBytes.

  [[nodiscard]] static SVal evalMulForBufferSize(CheckerContext &C,

                                                 const Expr *Blocks,

                                                 const Expr *BlockBytes);

  /// Models zero initialized array allocation.

  ///

  /// \param [in] Call The expression that reallocated memory

  /// \param [in] State The \c ProgramState right before reallocation.

  /// \returns The ProgramState right after allocation.

  [[nodiscard]] static ProgramStateRef

  CallocMem(CheckerContext &C, const CallEvent &Call, ProgramStateRef State);

  /// See if deallocation happens in a suspicious context. If so, escape the

  /// pointers that otherwise would have been deallocated and return true.

  bool suppressDeallocationsInSuspiciousContexts(const CallEvent &Call,

                                                 CheckerContext &C) const;

  /// If in \p S  \p Sym is used, check whether \p Sym was already freed.

  bool checkUseAfterFree(SymbolRef Sym, CheckerContext &C, const Stmt *S) const;

  /// If in \p S \p Sym is used, check whether \p Sym was allocated as a zero

  /// sized memory region.

  void checkUseZeroAllocated(SymbolRef Sym, CheckerContext &C,

                             const Stmt *S) const;

  /// If in \p S \p Sym is being freed, check whether \p Sym was already freed.

  bool checkDoubleDelete(SymbolRef Sym, CheckerContext &C) const;

  /// Check if the function is known to free memory, or if it is

  /// "interesting" and should be modeled explicitly.

  ///

  /// \param [out] EscapingSymbol A function might not free memory in general,

  ///   but could be known to free a particular symbol. In this case, false is

  ///   returned and the single escaping symbol is returned through the out

  ///   parameter.

  ///

  /// We assume that pointers do not escape through calls to system functions

  /// not handled by this checker.

  bool mayFreeAnyEscapedMemoryOrIsModeledExplicitly(const CallEvent *Call,

                                   ProgramStateRef State,

                                   SymbolRef &EscapingSymbol) const;

  /// Implementation of the checkPointerEscape callbacks.

  [[nodiscard]] ProgramStateRef

  checkPointerEscapeAux(ProgramStateRef State,

                        const InvalidatedSymbols &Escaped,

                        const CallEvent *Call, PointerEscapeKind Kind,

                        bool IsConstPointerEscape) const;

  // Implementation of the checkPreStmt and checkEndFunction callbacks.

  void checkEscapeOnReturn(const ReturnStmt *S, CheckerContext &C) const;

  ///@{

  /// Tells if a given family/call/symbol is tracked by the current checker.

  /// Sets CheckKind to the kind of the checker responsible for this

  /// family/call/symbol.

  std::optional<CheckKind> getCheckIfTracked(AllocationFamily Family,

                                             bool IsALeakCheck = false) const;

  std::optional<CheckKind> getCheckIfTracked(CheckerContext &C, SymbolRef Sym,

                                             bool IsALeakCheck = false) const;

  ///@}

  static bool SummarizeValue(raw_ostream &os, SVal V);

  static bool SummarizeRegion(raw_ostream &os, const MemRegion *MR);

  void HandleNonHeapDealloc(CheckerContext &C, SVal ArgVal, SourceRange Range,

                            const Expr *DeallocExpr,

                            AllocationFamily Family) const;

  void HandleFreeAlloca(CheckerContext &C, SVal ArgVal,

                        SourceRange Range) const;

  void HandleMismatchedDealloc(CheckerContext &C, SourceRange Range,

                               const Expr *DeallocExpr, const RefState *RS,

                               SymbolRef Sym, bool OwnershipTransferred) const;

  void HandleOffsetFree(CheckerContext &C, SVal ArgVal, SourceRange Range,

                        const Expr *DeallocExpr, AllocationFamily Family,

                        const Expr *AllocExpr = nullptr) const;

  void HandleUseAfterFree(CheckerContext &C, SourceRange Range,

                          SymbolRef Sym) const;

  void HandleDoubleFree(CheckerContext &C, SourceRange Range, bool Released,

                        SymbolRef Sym, SymbolRef PrevSym) const;

  void HandleDoubleDelete(CheckerContext &C, SymbolRef Sym) const;

  void HandleUseZeroAlloc(CheckerContext &C, SourceRange Range,

                          SymbolRef Sym) const;

  void HandleFunctionPtrFree(CheckerContext &C, SVal ArgVal, SourceRange Range,

                             const Expr *FreeExpr,

                             AllocationFamily Family) const;

  /// Find the location of the allocation for Sym on the path leading to the

  /// exploded node N.

  static LeakInfo getAllocationSite(const ExplodedNode *N, SymbolRef Sym,

                                    CheckerContext &C);

  void HandleLeak(SymbolRef Sym, ExplodedNode *N, CheckerContext &C) const;

  /// Test if value in ArgVal equals to value in macro `ZERO_SIZE_PTR`.

  bool isArgZERO_SIZE_PTR(ProgramStateRef State, CheckerContext &C,

                          SVal ArgVal) const;

};

} // 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;

  public:

    OwnershipBindingsHandler(SymbolRef Sym, OwnerSet &Owners)

        : Sym(Sym), Owners(Owners) {}

    bool HandleBinding(StoreManager &SMgr, Store Store, const MemRegion *Region,

                       SVal Val) override {

      if (Val.getAsSymbol() == Sym)

        Owners.insert(Region);

      return true;

    }

    LLVM_DUMP_METHOD void dump() const { dumpToStream(llvm::errs()); }

    LLVM_DUMP_METHOD void dumpToStream(llvm::raw_ostream &out) const {

      out << "Owners: {\n";

      for (const MemRegion *Owner : Owners) {

        out << "  ";

        Owner->dumpToStream(out);

        out << ",\n";

      }

      out << "}\n";

    }

  };

protected:

  OwnerSet getOwnersAtNode(const ExplodedNode *N) {

    OwnerSet Ret;

    ProgramStateRef State = N->getState();

    OwnershipBindingsHandler Handler{Sym, Ret};

    State->getStateManager().getStoreManager().iterBindings(State->getStore(),

                                                            Handler);

    return Ret;

  }

  LLVM_DUMP_METHOD static std::string

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

      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()86
)

      return false;

    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;

  }

  bool wasModifiedInFunction(const ExplodedNode *CallEnterN,

                             const ExplodedNode *CallExitEndN) override {

    if (!doesFnIntendToHandleOwnership(

            CallExitEndN->getFirstPred()->getLocationContext()->getDecl(),

            CallExitEndN->getState()->getAnalysisManager().getASTContext()))

      return true;

    if (CallEnterN->getState()->get<RegionState>(Sym) !=

        CallExitEndN->getState()->get<RegionState>(Sym))

      return true;

    OwnerSet CurrOwners = getOwnersAtNode(CallEnterN);

    OwnerSet ExitOwners = getOwnersAtNode(CallExitEndN);

    // Owners in the current set may be purged from the analyzer later on.

    // If a variable is dead (is not referenced directly or indirectly after

    // some point), it will be removed from the Store before the end of its

    // actual lifetime.

    // This means that if the ownership status didn't change, CurrOwners

    // must be a superset of, but not necessarily equal to ExitOwners.

    return !llvm::set_is_subset(ExitOwners, CurrOwners);

  }

  static PathDiagnosticPieceRef emitNote(const ExplodedNode *N) {

    PathDiagnosticLocation L = PathDiagnosticLocation::create(

        N->getLocation(),

        N->getState()->getStateManager().getContext().getSourceManager());

    return std::make_shared<PathDiagnosticEventPiece>(

        L, "Returning without deallocating memory or storing the pointer for "

           "later deallocation");

  }

  PathDiagnosticPieceRef

  maybeEmitNoteForObjCSelf(PathSensitiveBugReport &R,

                           const ObjCMethodCall &Call,

                           const ExplodedNode *N) override {

    // TODO: Implement.

    return nullptr;

  }

  PathDiagnosticPieceRef

  maybeEmitNoteForCXXThis(PathSensitiveBugReport &R,

                          const CXXConstructorCall &Call,

                          const ExplodedNode *N) override {

    // TODO: Implement.

    return nullptr;

  }

  PathDiagnosticPieceRef

  maybeEmitNoteForParameters(PathSensitiveBugReport &R, const CallEvent &Call,

                             const ExplodedNode *N) override {

    // TODO: Factor the logic of "what constitutes as an entity being passed

    // into a function call" out by reusing the code in

    // NoStoreFuncVisitor::maybeEmitNoteForParameters, maybe by incorporating

    // the printing technology in UninitializedObject's FieldChainInfo.

    ArrayRef<ParmVarDecl *> Parameters = Call.parameters();

    for (unsigned I = 0; I < Call.getNumArgs() && 
I < Parameters.size()4
; 
++I1
) {

      SVal V = Call.getArgSVal(I);

      if (V.getAsSymbol() == Sym)

        return emitNote(N);

    }

    return nullptr;

  }

public:

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

  }

};

} // end anonymous namespace

//===----------------------------------------------------------------------===//

// Definition of MallocBugVisitor.

//===----------------------------------------------------------------------===//

namespace {

/// The bug visitor which allows us to print extra diagnostics along the

/// BugReport path. For example, showing the allocation site of the leaked

/// region.

class MallocBugVisitor final : public BugReporterVisitor {

protected:

  enum NotificationMode { Normal, ReallocationFailed };

  // The allocated region symbol tracked by the main analysis.

  SymbolRef Sym;

  // The mode we are in, i.e. what kind of diagnostics will be emitted.

  NotificationMode Mode;

  // A symbol from when the primary region should have been reallocated.

  SymbolRef FailedReallocSymbol;

  // A C++ destructor stack frame in which memory was released. Used for

  // miscellaneous false positive suppression.

  const StackFrameContext *ReleaseDestructorLC;

  bool IsLeak;

public:

  MallocBugVisitor(SymbolRef S, bool isLeak = false)

      : Sym(S), Mode(Normal), FailedReallocSymbol(nullptr),

        ReleaseDestructorLC(nullptr), IsLeak(isLeak) {}

  static void *getTag() {

    static int Tag = 0;

    return &Tag;

  }

  void Profile(llvm::FoldingSetNodeID &ID) const override {

    ID.AddPointer(getTag());

    ID.AddPointer(Sym);

  }

  /// Did not track -> allocated. Other state (released) -> allocated.

  static inline bool isAllocated(const RefState *RSCurr, const RefState *RSPrev,

                                 const Stmt *Stmt) {

    return (isa_and_nonnull<CallExpr, CXXNewExpr>(Stmt) &&

            
(4.36k
RSCurr4.36k
 &&

             
(2.04k
RSCurr->isAllocated()2.04k
 || 
RSCurr->isAllocatedOfSizeZero()452
)) &&

            
(1.66k
!RSPrev1.66k
 ||

             
!(1.23k
RSPrev->isAllocated()1.23k
 || 
RSPrev->isAllocatedOfSizeZero()28
)));

  }

  /// Did not track -> released. Other state (allocated) -> released.

  /// The statement associated with the release might be missing.

  static inline bool isReleased(const RefState *RSCurr, const RefState *RSPrev,

                                const Stmt *Stmt) {

    bool IsReleased =

        (RSCurr && 
RSCurr->isReleased()13.4k
) && 
(2.17k
!RSPrev2.17k
 || 
!RSPrev->isReleased()2.10k
);

    assert(!IsReleased || (isa_and_nonnull<CallExpr, CXXDeleteExpr>(Stmt)) ||

           (!Stmt && RSCurr->getAllocationFamily() == AF_InnerBuffer));

    return IsReleased;

  }

  /// Did not track -> relinquished. Other state (allocated) -> relinquished.

  static inline bool isRelinquished(const RefState *RSCurr,

                                    const RefState *RSPrev, const Stmt *Stmt) {

    return (

        isa_and_nonnull<CallExpr, ObjCMessageExpr, ObjCPropertyRefExpr>(Stmt) &&

        
(2.80k
RSCurr2.80k
 && 
RSCurr->isRelinquished()1.16k
) &&

        
(18
!RSPrev18
 || 
!RSPrev->isRelinquished()17
));

  }

  /// If the expression is not a call, and the state change is

  /// released -> allocated, it must be the realloc return value

  /// check. If we have to handle more cases here, it might be cleaner just

  /// to track this extra bit in the state itself.

  static inline bool hasReallocFailed(const RefState *RSCurr,

                                      const RefState *RSPrev,

                                      const Stmt *Stmt) {

    return ((!isa_and_nonnull<CallExpr>(Stmt)) &&

            
(21.1k
RSCurr21.1k
 &&

             
(12.1k
RSCurr->isAllocated()12.1k
 || 
RSCurr->isAllocatedOfSizeZero()2.42k
)) &&

            
(10.1k
RSPrev10.1k
 &&

             !(RSPrev->isAllocated() || 
RSPrev->isAllocatedOfSizeZero()446
)));

  }

  PathDiagnosticPieceRef VisitNode(const ExplodedNode *N,

                                   BugReporterContext &BRC,

                                   PathSensitiveBugReport &BR) override;

  PathDiagnosticPieceRef getEndPath(BugReporterContext &BRC,

                                    const ExplodedNode *EndPathNode,

                                    PathSensitiveBugReport &BR) override {

    if (!IsLeak)

      return nullptr;

    PathDiagnosticLocation L = BR.getLocation();

    // Do not add the statement itself as a range in case of leak.

    return std::make_shared<PathDiagnosticEventPiece>(L, BR.getDescription(),

                                                      false);

  }

private:

  class StackHintGeneratorForReallocationFailed

      : public StackHintGeneratorForSymbol {

  public:

    StackHintGeneratorForReallocationFailed(SymbolRef S, StringRef M)

        : StackHintGeneratorForSymbol(S, M) {}

    std::string getMessageForArg(const Expr *ArgE, unsigned ArgIndex) override {

      // Printed parameters start at 1, not 0.

      ++ArgIndex;

      SmallString<200> buf;

      llvm::raw_svector_ostream os(buf);

      os << "Reallocation of " << ArgIndex << llvm::getOrdinalSuffix(ArgIndex)

         << " parameter failed";

      return std::string(os.str());

    }

    std::string getMessageForReturn(const CallExpr *CallExpr) override {

      return "Reallocation of returned value failed";

    }

  };

};

} // end anonymous namespace

// A map from the freed symbol to the symbol representing the return value of

// the free function.

REGISTER_MAP_WITH_PROGRAMSTATE(FreeReturnValue, SymbolRef, SymbolRef)

namespace {

class StopTrackingCallback final : public SymbolVisitor {

  ProgramStateRef state;

public:

  StopTrackingCallback(ProgramStateRef st) : state(std::move(st)) {}

  ProgramStateRef getState() const { return state; }

  bool VisitSymbol(SymbolRef sym) override {

    state = state->remove<RegionState>(sym);

    return true;

  }

};

} // end anonymous namespace

static bool isStandardNewDelete(const FunctionDecl *FD) {

  if (!FD)

    return false;

  OverloadedOperatorKind Kind = FD->getOverloadedOperator();

  if (Kind != OO_New && 
Kind != OO_Array_New29.8k
 && 
Kind != OO_Delete29.6k
 &&

      
Kind != OO_Array_Delete29.0k
)

    return false;

  // This is standard if and only if it's not defined in a user file.

  SourceLocation L = FD->getLocation();

  // If the header for operator delete is not included, it's still defined

  // in an invalid source location. Check to make sure we don't crash.

  return !L.isValid() ||

         
FD->getASTContext().getSourceManager().isInSystemHeader(L)1.21k
;

}

//===----------------------------------------------------------------------===//

// Methods of MallocChecker and MallocBugVisitor.

//===----------------------------------------------------------------------===//