contrib/llvm/tools/clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

   1 //=== MallocChecker.cpp - A malloc/free checker -------------------*- C++ -*--//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file defines malloc/free checker, which checks for potential memory
  10 // leaks, double free, and use-after-free problems.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
  15 #include "InterCheckerAPI.h"
  16 #include "clang/AST/Attr.h"
  17 #include "clang/AST/ParentMap.h"
  18 #include "clang/Basic/SourceManager.h"
  19 #include "clang/Basic/TargetInfo.h"
  20 #include "clang/Lex/Lexer.h"
  21 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
  22 #include "clang/StaticAnalyzer/Core/BugReporter/CommonBugCategories.h"
  23 #include "clang/StaticAnalyzer/Core/Checker.h"
  24 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
  25 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
  26 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
  27 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
  28 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
  29 #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
  30 #include "llvm/ADT/STLExtras.h"
  31 #include "llvm/ADT/SmallString.h"
  32 #include "llvm/ADT/StringExtras.h"
  33 #include "AllocationState.h"
  34 #include <climits>
  35 #include <utility>
  36
  37 using namespace clang;
  38 using namespace ento;
  39
  40 namespace {
  41
  42 // Used to check correspondence between allocators and deallocators.
  43 enum AllocationFamily {
  44   AF_None,
  45   AF_Malloc,
  46   AF_CXXNew,
  47   AF_CXXNewArray,
  48   AF_IfNameIndex,
  49   AF_Alloca,
  50   AF_InnerBuffer
  51 };
  52
  53 class RefState {
  54   enum Kind { // Reference to allocated memory.
  55               Allocated,
  56               // Reference to zero-allocated memory.
  57               AllocatedOfSizeZero,
  58               // Reference to released/freed memory.
  59               Released,
  60               // The responsibility for freeing resources has transferred from
  61               // this reference. A relinquished symbol should not be freed.
  62               Relinquished,
  63               // We are no longer guaranteed to have observed all manipulations
  64               // of this pointer/memory. For example, it could have been
  65               // passed as a parameter to an opaque function.
  66               Escaped
  67   };
  68
  69   const Stmt *S;
  70   unsigned K : 3; // Kind enum, but stored as a bitfield.
  71   unsigned Family : 29; // Rest of 32-bit word, currently just an allocation
  72                         // family.
  73
  74   RefState(Kind k, const Stmt *s, unsigned family)
  75     : S(s), K(k), Family(family) {
  76     assert(family != AF_None);
  77   }
  78 public:
  79   bool isAllocated() const { return K == Allocated; }
  80   bool isAllocatedOfSizeZero() const { return K == AllocatedOfSizeZero; }
  81   bool isReleased() const { return K == Released; }
  82   bool isRelinquished() const { return K == Relinquished; }
  83   bool isEscaped() const { return K == Escaped; }
  84   AllocationFamily getAllocationFamily() const {
  85     return (AllocationFamily)Family;
  86   }
  87   const Stmt *getStmt() const { return S; }
  88
  89   bool operator==(const RefState &X) const {
  90     return K == X.K && S == X.S && Family == X.Family;
  91   }
  92
  93   static RefState getAllocated(unsigned family, const Stmt *s) {
  94     return RefState(Allocated, s, family);
  95   }
  96   static RefState getAllocatedOfSizeZero(const RefState *RS) {
  97     return RefState(AllocatedOfSizeZero, RS->getStmt(),
  98                     RS->getAllocationFamily());
  99   }
 100   static RefState getReleased(unsigned family, const Stmt *s) {
 101     return RefState(Released, s, family);
 102   }
 103   static RefState getRelinquished(unsigned family, const Stmt *s) {
 104     return RefState(Relinquished, s, family);
 105   }
 106   static RefState getEscaped(const RefState *RS) {
 107     return RefState(Escaped, RS->getStmt(), RS->getAllocationFamily());
 108   }
 109
 110   void Profile(llvm::FoldingSetNodeID &ID) const {
 111     ID.AddInteger(K);
 112     ID.AddPointer(S);
 113     ID.AddInteger(Family);
 114   }
 115
 116   void dump(raw_ostream &OS) const {
 117     switch (static_cast<Kind>(K)) {
 118 #define CASE(ID) case ID: OS << #ID; break;
 119     CASE(Allocated)
 120     CASE(AllocatedOfSizeZero)
 121     CASE(Released)
 122     CASE(Relinquished)
 123     CASE(Escaped)
 124     }
 125   }
 126
 127   LLVM_DUMP_METHOD void dump() const { dump(llvm::errs()); }
 128 };
 129
 130 enum ReallocPairKind {
 131   RPToBeFreedAfterFailure,
 132   // The symbol has been freed when reallocation failed.
 133   RPIsFreeOnFailure,
 134   // The symbol does not need to be freed after reallocation fails.
 135   RPDoNotTrackAfterFailure
 136 };
 137
 138 /// \class ReallocPair
 139 /// Stores information about the symbol being reallocated by a call to
 140 /// 'realloc' to allow modeling failed reallocation later in the path.
 141 struct ReallocPair {
 142   // The symbol which realloc reallocated.
 143   SymbolRef ReallocatedSym;
 144   ReallocPairKind Kind;
 145
 146   ReallocPair(SymbolRef S, ReallocPairKind K) :
 147     ReallocatedSym(S), Kind(K) {}
 148   void Profile(llvm::FoldingSetNodeID &ID) const {
 149     ID.AddInteger(Kind);
 150     ID.AddPointer(ReallocatedSym);
 151   }
 152   bool operator==(const ReallocPair &X) const {
 153     return ReallocatedSym == X.ReallocatedSym &&
 154            Kind == X.Kind;
 155   }
 156 };
 157
 158 typedef std::pair<const ExplodedNode*, const MemRegion*> LeakInfo;
 159
 160 class MallocChecker : public Checker<check::DeadSymbols,
 161                                      check::PointerEscape,
 162                                      check::ConstPointerEscape,
 163                                      check::PreStmt<ReturnStmt>,
 164                                      check::EndFunction,
 165                                      check::PreCall,
 166                                      check::PostStmt<CallExpr>,
 167                                      check::PostStmt<CXXNewExpr>,
 168                                      check::NewAllocator,
 169                                      check::PreStmt<CXXDeleteExpr>,
 170                                      check::PostStmt<BlockExpr>,
 171                                      check::PostObjCMessage,
 172                                      check::Location,
 173                                      eval::Assume>
 174 {
 175 public:
 176   MallocChecker()
 177       : II_alloca(nullptr), II_win_alloca(nullptr), II_malloc(nullptr),
 178         II_free(nullptr), II_realloc(nullptr), II_calloc(nullptr),
 179         II_valloc(nullptr), II_reallocf(nullptr), II_strndup(nullptr),
 180         II_strdup(nullptr), II_win_strdup(nullptr), II_kmalloc(nullptr),
 181         II_kfree(nullptr), II_if_nameindex(nullptr),
 182         II_if_freenameindex(nullptr), II_wcsdup(nullptr),
 183         II_win_wcsdup(nullptr), II_g_malloc(nullptr), II_g_malloc0(nullptr),
 184         II_g_realloc(nullptr), II_g_try_malloc(nullptr),
 185         II_g_try_malloc0(nullptr), II_g_try_realloc(nullptr),
 186         II_g_free(nullptr), II_g_memdup(nullptr), II_g_malloc_n(nullptr),
 187         II_g_malloc0_n(nullptr), II_g_realloc_n(nullptr),
 188         II_g_try_malloc_n(nullptr), II_g_try_malloc0_n(nullptr),
 189         II_g_try_realloc_n(nullptr) {}
 190
 191   /// In pessimistic mode, the checker assumes that it does not know which
 192   /// functions might free the memory.
 193   enum CheckKind {
 194     CK_MallocChecker,
 195     CK_NewDeleteChecker,
 196     CK_NewDeleteLeaksChecker,
 197     CK_MismatchedDeallocatorChecker,
 198     CK_InnerPointerChecker,
 199     CK_NumCheckKinds
 200   };
 201
 202   enum class MemoryOperationKind {
 203     MOK_Allocate,
 204     MOK_Free,
 205     MOK_Any
 206   };
 207
 208   DefaultBool IsOptimistic;
 209
 210   DefaultBool ChecksEnabled[CK_NumCheckKinds];
 211   CheckName CheckNames[CK_NumCheckKinds];
 212
 213   void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
 214   void checkPostStmt(const CallExpr *CE, CheckerContext &C) const;
 215   void checkPostStmt(const CXXNewExpr *NE, CheckerContext &C) const;
 216   void checkNewAllocator(const CXXNewExpr *NE, SVal Target,
 217                          CheckerContext &C) const;
 218   void checkPreStmt(const CXXDeleteExpr *DE, CheckerContext &C) const;
 219   void checkPostObjCMessage(const ObjCMethodCall &Call, CheckerContext &C) const;
 220   void checkPostStmt(const BlockExpr *BE, CheckerContext &C) const;
 221   void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const;
 222   void checkPreStmt(const ReturnStmt *S, CheckerContext &C) const;
 223   void checkEndFunction(const ReturnStmt *S, CheckerContext &C) const;
 224   ProgramStateRef evalAssume(ProgramStateRef state, SVal Cond,
 225                             bool Assumption) const;
 226   void checkLocation(SVal l, bool isLoad, const Stmt *S,
 227                      CheckerContext &C) const;
 228
 229   ProgramStateRef checkPointerEscape(ProgramStateRef State,
 230                                     const InvalidatedSymbols &Escaped,
 231                                     const CallEvent *Call,
 232                                     PointerEscapeKind Kind) const;
 233   ProgramStateRef checkConstPointerEscape(ProgramStateRef State,
 234                                           const InvalidatedSymbols &Escaped,
 235                                           const CallEvent *Call,
 236                                           PointerEscapeKind Kind) const;
 237
 238   void printState(raw_ostream &Out, ProgramStateRef State,
 239                   const char *NL, const char *Sep) const override;
 240
 241 private:
 242   mutable std::unique_ptr<BugType> BT_DoubleFree[CK_NumCheckKinds];
 243   mutable std::unique_ptr<BugType> BT_DoubleDelete;
 244   mutable std::unique_ptr<BugType> BT_Leak[CK_NumCheckKinds];
 245   mutable std::unique_ptr<BugType> BT_UseFree[CK_NumCheckKinds];
 246   mutable std::unique_ptr<BugType> BT_BadFree[CK_NumCheckKinds];
 247   mutable std::unique_ptr<BugType> BT_FreeAlloca[CK_NumCheckKinds];
 248   mutable std::unique_ptr<BugType> BT_MismatchedDealloc;
 249   mutable std::unique_ptr<BugType> BT_OffsetFree[CK_NumCheckKinds];
 250   mutable std::unique_ptr<BugType> BT_UseZerroAllocated[CK_NumCheckKinds];
 251   mutable IdentifierInfo *II_alloca, *II_win_alloca, *II_malloc, *II_free,
 252                          *II_realloc, *II_calloc, *II_valloc, *II_reallocf,
 253                          *II_strndup, *II_strdup, *II_win_strdup, *II_kmalloc,
 254                          *II_kfree, *II_if_nameindex, *II_if_freenameindex,
 255                          *II_wcsdup, *II_win_wcsdup, *II_g_malloc,
 256                          *II_g_malloc0, *II_g_realloc, *II_g_try_malloc,
 257                          *II_g_try_malloc0, *II_g_try_realloc, *II_g_free,
 258                          *II_g_memdup, *II_g_malloc_n, *II_g_malloc0_n,
 259                          *II_g_realloc_n, *II_g_try_malloc_n,
 260                          *II_g_try_malloc0_n, *II_g_try_realloc_n;
 261   mutable Optional<uint64_t> KernelZeroFlagVal;
 262
 263   void initIdentifierInfo(ASTContext &C) const;
 264
 265   /// Determine family of a deallocation expression.
 266   AllocationFamily getAllocationFamily(CheckerContext &C, const Stmt *S) const;
 267
 268   /// Print names of allocators and deallocators.
 269   ///
 270   /// \returns true on success.
 271   bool printAllocDeallocName(raw_ostream &os, CheckerContext &C,
 272                              const Expr *E) const;
 273
 274   /// Print expected name of an allocator based on the deallocator's
 275   /// family derived from the DeallocExpr.
 276   void printExpectedAllocName(raw_ostream &os, CheckerContext &C,
 277                               const Expr *DeallocExpr) const;
 278   /// Print expected name of a deallocator based on the allocator's
 279   /// family.
 280   void printExpectedDeallocName(raw_ostream &os, AllocationFamily Family) const;
 281
 282   ///@{
 283   /// Check if this is one of the functions which can allocate/reallocate memory
 284   /// pointed to by one of its arguments.
 285   bool isMemFunction(const FunctionDecl *FD, ASTContext &C) const;
 286   bool isCMemFunction(const FunctionDecl *FD,
 287                       ASTContext &C,
 288                       AllocationFamily Family,
 289                       MemoryOperationKind MemKind) const;
 290   bool isStandardNewDelete(const FunctionDecl *FD, ASTContext &C) const;
 291   ///@}
 292
 293   /// Process C++ operator new()'s allocation, which is the part of C++
 294   /// new-expression that goes before the constructor.
 295   void processNewAllocation(const CXXNewExpr *NE, CheckerContext &C,
 296                             SVal Target) const;
 297
 298   /// Perform a zero-allocation check.
 299   /// The optional \p RetVal parameter specifies the newly allocated pointer
 300   /// value; if unspecified, the value of expression \p E is used.
 301   ProgramStateRef ProcessZeroAllocation(CheckerContext &C, const Expr *E,
 302                                         const unsigned AllocationSizeArg,
 303                                         ProgramStateRef State,
 304                                         Optional<SVal> RetVal = None) const;
 305
 306   ProgramStateRef MallocMemReturnsAttr(CheckerContext &C,
 307                                        const CallExpr *CE,
 308                                        const OwnershipAttr* Att,
 309                                        ProgramStateRef State) const;
 310   static ProgramStateRef MallocMemAux(CheckerContext &C, const CallExpr *CE,
 311                                       const Expr *SizeEx, SVal Init,
 312                                       ProgramStateRef State,
 313                                       AllocationFamily Family = AF_Malloc);
 314   static ProgramStateRef MallocMemAux(CheckerContext &C, const CallExpr *CE,
 315                                       SVal SizeEx, SVal Init,
 316                                       ProgramStateRef State,
 317                                       AllocationFamily Family = AF_Malloc);
 318
 319   static ProgramStateRef addExtentSize(CheckerContext &C, const CXXNewExpr *NE,
 320                                        ProgramStateRef State, SVal Target);
 321
 322   // Check if this malloc() for special flags. At present that means M_ZERO or
 323   // __GFP_ZERO (in which case, treat it like calloc).
 324   llvm::Optional<ProgramStateRef>
 325   performKernelMalloc(const CallExpr *CE, CheckerContext &C,
 326                       const ProgramStateRef &State) const;
 327
 328   /// Update the RefState to reflect the new memory allocation.
 329   /// The optional \p RetVal parameter specifies the newly allocated pointer
 330   /// value; if unspecified, the value of expression \p E is used.
 331   static ProgramStateRef
 332   MallocUpdateRefState(CheckerContext &C, const Expr *E, ProgramStateRef State,
 333                        AllocationFamily Family = AF_Malloc,
 334                        Optional<SVal> RetVal = None);
 335
 336   ProgramStateRef FreeMemAttr(CheckerContext &C, const CallExpr *CE,
 337                               const OwnershipAttr* Att,
 338                               ProgramStateRef State) const;
 339   ProgramStateRef FreeMemAux(CheckerContext &C, const CallExpr *CE,
 340                              ProgramStateRef state, unsigned Num,
 341                              bool Hold,
 342                              bool &ReleasedAllocated,
 343                              bool ReturnsNullOnFailure = false) const;
 344   ProgramStateRef FreeMemAux(CheckerContext &C, const Expr *Arg,
 345                              const Expr *ParentExpr,
 346                              ProgramStateRef State,
 347                              bool Hold,
 348                              bool &ReleasedAllocated,
 349                              bool ReturnsNullOnFailure = false) const;
 350
 351   ProgramStateRef ReallocMemAux(CheckerContext &C, const CallExpr *CE,
 352                                 bool FreesMemOnFailure,
 353                                 ProgramStateRef State,
 354                                 bool SuffixWithN = false) const;
 355   static SVal evalMulForBufferSize(CheckerContext &C, const Expr *Blocks,
 356                                    const Expr *BlockBytes);
 357   static ProgramStateRef CallocMem(CheckerContext &C, const CallExpr *CE,
 358                                    ProgramStateRef State);
 359
 360   /// Check if the memory associated with this symbol was released.
 361   bool isReleased(SymbolRef Sym, CheckerContext &C) const;
 362
 363   /// See if deallocation happens in a suspicious context. If so, escape the
 364   /// pointers that otherwise would have been deallocated and return true.
 365   bool suppressDeallocationsInSuspiciousContexts(const CallExpr *CE,
 366                                                  CheckerContext &C) const;
 367
 368   bool checkUseAfterFree(SymbolRef Sym, CheckerContext &C, const Stmt *S) const;
 369
 370   void checkUseZeroAllocated(SymbolRef Sym, CheckerContext &C,
 371                              const Stmt *S) const;
 372
 373   bool checkDoubleDelete(SymbolRef Sym, CheckerContext &C) const;
 374
 375   /// Check if the function is known free memory, or if it is
 376   /// "interesting" and should be modeled explicitly.
 377   ///
 378   /// \param [out] EscapingSymbol A function might not free memory in general,
 379   ///   but could be known to free a particular symbol. In this case, false is
 380   ///   returned and the single escaping symbol is returned through the out
 381   ///   parameter.
 382   ///
 383   /// We assume that pointers do not escape through calls to system functions
 384   /// not handled by this checker.
 385   bool mayFreeAnyEscapedMemoryOrIsModeledExplicitly(const CallEvent *Call,
 386                                    ProgramStateRef State,
 387                                    SymbolRef &EscapingSymbol) const;
 388
 389   // Implementation of the checkPointerEscape callbacks.
 390   ProgramStateRef checkPointerEscapeAux(ProgramStateRef State,
 391                                   const InvalidatedSymbols &Escaped,
 392                                   const CallEvent *Call,
 393                                   PointerEscapeKind Kind,
 394                                   bool(*CheckRefState)(const RefState*)) const;
 395
 396   // Implementation of the checkPreStmt and checkEndFunction callbacks.
 397   void checkEscapeOnReturn(const ReturnStmt *S, CheckerContext &C) const;
 398
 399   ///@{
 400   /// Tells if a given family/call/symbol is tracked by the current checker.
 401   /// Sets CheckKind to the kind of the checker responsible for this
 402   /// family/call/symbol.
 403   Optional<CheckKind> getCheckIfTracked(AllocationFamily Family,
 404                                         bool IsALeakCheck = false) const;
 405   Optional<CheckKind> getCheckIfTracked(CheckerContext &C,
 406                                         const Stmt *AllocDeallocStmt,
 407                                         bool IsALeakCheck = false) const;
 408   Optional<CheckKind> getCheckIfTracked(CheckerContext &C, SymbolRef Sym,
 409                                         bool IsALeakCheck = false) const;
 410   ///@}
 411   static bool SummarizeValue(raw_ostream &os, SVal V);
 412   static bool SummarizeRegion(raw_ostream &os, const MemRegion *MR);
 413   void ReportBadFree(CheckerContext &C, SVal ArgVal, SourceRange Range,
 414                      const Expr *DeallocExpr) const;
 415   void ReportFreeAlloca(CheckerContext &C, SVal ArgVal,
 416                         SourceRange Range) const;
 417   void ReportMismatchedDealloc(CheckerContext &C, SourceRange Range,
 418                                const Expr *DeallocExpr, const RefState *RS,
 419                                SymbolRef Sym, bool OwnershipTransferred) const;
 420   void ReportOffsetFree(CheckerContext &C, SVal ArgVal, SourceRange Range,
 421                         const Expr *DeallocExpr,
 422                         const Expr *AllocExpr = nullptr) const;
 423   void ReportUseAfterFree(CheckerContext &C, SourceRange Range,
 424                           SymbolRef Sym) const;
 425   void ReportDoubleFree(CheckerContext &C, SourceRange Range, bool Released,
 426                         SymbolRef Sym, SymbolRef PrevSym) const;
 427
 428   void ReportDoubleDelete(CheckerContext &C, SymbolRef Sym) const;
 429
 430   void ReportUseZeroAllocated(CheckerContext &C, SourceRange Range,
 431                               SymbolRef Sym) const;
 432
 433   void ReportFunctionPointerFree(CheckerContext &C, SVal ArgVal,
 434                                  SourceRange Range, const Expr *FreeExpr) const;
 435
 436   /// Find the location of the allocation for Sym on the path leading to the
 437   /// exploded node N.
 438   LeakInfo getAllocationSite(const ExplodedNode *N, SymbolRef Sym,
 439                              CheckerContext &C) const;
 440
 441   void reportLeak(SymbolRef Sym, ExplodedNode *N, CheckerContext &C) const;
 442
 443   /// The bug visitor which allows us to print extra diagnostics along the
 444   /// BugReport path. For example, showing the allocation site of the leaked
 445   /// region.
 446   class MallocBugVisitor final : public BugReporterVisitor {
 447   protected:
 448     enum NotificationMode {
 449       Normal,
 450       ReallocationFailed
 451     };
 452
 453     // The allocated region symbol tracked by the main analysis.
 454     SymbolRef Sym;
 455
 456     // The mode we are in, i.e. what kind of diagnostics will be emitted.
 457     NotificationMode Mode;
 458
 459     // A symbol from when the primary region should have been reallocated.
 460     SymbolRef FailedReallocSymbol;
 461
 462     // A C++ destructor stack frame in which memory was released. Used for
 463     // miscellaneous false positive suppression.
 464     const StackFrameContext *ReleaseDestructorLC;
 465
 466     bool IsLeak;
 467
 468   public:
 469     MallocBugVisitor(SymbolRef S, bool isLeak = false)
 470         : Sym(S), Mode(Normal), FailedReallocSymbol(nullptr),
 471           ReleaseDestructorLC(nullptr), IsLeak(isLeak) {}
 472
 473     static void *getTag() {
 474       static int Tag = 0;
 475       return &Tag;
 476     }
 477
 478     void Profile(llvm::FoldingSetNodeID &ID) const override {
 479       ID.AddPointer(getTag());
 480       ID.AddPointer(Sym);
 481     }
 482
 483     inline bool isAllocated(const RefState *S, const RefState *SPrev,
 484                             const Stmt *Stmt) {
 485       // Did not track -> allocated. Other state (released) -> allocated.
 486       return (Stmt && (isa<CallExpr>(Stmt) || isa<CXXNewExpr>(Stmt)) &&
 487               (S && (S->isAllocated() || S->isAllocatedOfSizeZero())) &&
 488               (!SPrev || !(SPrev->isAllocated() ||
 489                            SPrev->isAllocatedOfSizeZero())));
 490     }
 491
 492     inline bool isReleased(const RefState *S, const RefState *SPrev,
 493                            const Stmt *Stmt) {
 494       // Did not track -> released. Other state (allocated) -> released.
 495       // The statement associated with the release might be missing.
 496       bool IsReleased = (S && S->isReleased()) &&
 497                         (!SPrev || !SPrev->isReleased());
 498       assert(!IsReleased ||
 499              (Stmt && (isa<CallExpr>(Stmt) || isa<CXXDeleteExpr>(Stmt))) ||
 500              (!Stmt && S->getAllocationFamily() == AF_InnerBuffer));
 501       return IsReleased;
 502     }
 503
 504     inline bool isRelinquished(const RefState *S, const RefState *SPrev,
 505                                const Stmt *Stmt) {
 506       // Did not track -> relinquished. Other state (allocated) -> relinquished.
 507       return (Stmt && (isa<CallExpr>(Stmt) || isa<ObjCMessageExpr>(Stmt) ||
 508                                               isa<ObjCPropertyRefExpr>(Stmt)) &&
 509               (S && S->isRelinquished()) &&
 510               (!SPrev || !SPrev->isRelinquished()));
 511     }
 512
 513     inline bool isReallocFailedCheck(const RefState *S, const RefState *SPrev,
 514                                      const Stmt *Stmt) {
 515       // If the expression is not a call, and the state change is
 516       // released -> allocated, it must be the realloc return value
 517       // check. If we have to handle more cases here, it might be cleaner just
 518       // to track this extra bit in the state itself.
 519       return ((!Stmt || !isa<CallExpr>(Stmt)) &&
 520               (S && (S->isAllocated() || S->isAllocatedOfSizeZero())) &&
 521               (SPrev && !(SPrev->isAllocated() ||
 522                           SPrev->isAllocatedOfSizeZero())));
 523     }
 524
 525     std::shared_ptr<PathDiagnosticPiece> VisitNode(const ExplodedNode *N,
 526                                                    BugReporterContext &BRC,
 527                                                    BugReport &BR) override;
 528
 529     std::shared_ptr<PathDiagnosticPiece>
 530     getEndPath(BugReporterContext &BRC, const ExplodedNode *EndPathNode,
 531                BugReport &BR) override {
 532       if (!IsLeak)
 533         return nullptr;
 534
 535       PathDiagnosticLocation L =
 536         PathDiagnosticLocation::createEndOfPath(EndPathNode,
 537                                                 BRC.getSourceManager());
 538       // Do not add the statement itself as a range in case of leak.
 539       return std::make_shared<PathDiagnosticEventPiece>(L, BR.getDescription(),
 540                                                          false);
 541     }
 542
 543   private:
 544     class StackHintGeneratorForReallocationFailed
 545         : public StackHintGeneratorForSymbol {
 546     public:
 547       StackHintGeneratorForReallocationFailed(SymbolRef S, StringRef M)
 548         : StackHintGeneratorForSymbol(S, M) {}
 549
 550       std::string getMessageForArg(const Expr *ArgE,
 551                                    unsigned ArgIndex) override {
 552         // Printed parameters start at 1, not 0.
 553         ++ArgIndex;
 554
 555         SmallString<200> buf;
 556         llvm::raw_svector_ostream os(buf);
 557
 558         os << "Reallocation of " << ArgIndex << llvm::getOrdinalSuffix(ArgIndex)
 559            << " parameter failed";
 560
 561         return os.str();
 562       }
 563
 564       std::string getMessageForReturn(const CallExpr *CallExpr) override {
 565         return "Reallocation of returned value failed";
 566       }
 567     };
 568   };
 569 };
 570 } // end anonymous namespace
 571
 572 REGISTER_MAP_WITH_PROGRAMSTATE(RegionState, SymbolRef, RefState)
 573 REGISTER_MAP_WITH_PROGRAMSTATE(ReallocPairs, SymbolRef, ReallocPair)
 574 REGISTER_SET_WITH_PROGRAMSTATE(ReallocSizeZeroSymbols, SymbolRef)
 575
 576 // A map from the freed symbol to the symbol representing the return value of
 577 // the free function.
 578 REGISTER_MAP_WITH_PROGRAMSTATE(FreeReturnValue, SymbolRef, SymbolRef)
 579
 580 namespace {
 581 class StopTrackingCallback final : public SymbolVisitor {
 582   ProgramStateRef state;
 583 public:
 584   StopTrackingCallback(ProgramStateRef st) : state(std::move(st)) {}
 585   ProgramStateRef getState() const { return state; }
 586
 587   bool VisitSymbol(SymbolRef sym) override {
 588     state = state->remove<RegionState>(sym);
 589     return true;
 590   }
 591 };
 592 } // end anonymous namespace
 593
 594 void MallocChecker::initIdentifierInfo(ASTContext &Ctx) const {
 595   if (II_malloc)
 596     return;
 597   II_alloca = &Ctx.Idents.get("alloca");
 598   II_malloc = &Ctx.Idents.get("malloc");
 599   II_free = &Ctx.Idents.get("free");
 600   II_realloc = &Ctx.Idents.get("realloc");
 601   II_reallocf = &Ctx.Idents.get("reallocf");
 602   II_calloc = &Ctx.Idents.get("calloc");
 603   II_valloc = &Ctx.Idents.get("valloc");
 604   II_strdup = &Ctx.Idents.get("strdup");
 605   II_strndup = &Ctx.Idents.get("strndup");
 606   II_wcsdup = &Ctx.Idents.get("wcsdup");
 607   II_kmalloc = &Ctx.Idents.get("kmalloc");
 608   II_kfree = &Ctx.Idents.get("kfree");
 609   II_if_nameindex = &Ctx.Idents.get("if_nameindex");
 610   II_if_freenameindex = &Ctx.Idents.get("if_freenameindex");
 611
 612   //MSVC uses `_`-prefixed instead, so we check for them too.
 613   II_win_strdup = &Ctx.Idents.get("_strdup");
 614   II_win_wcsdup = &Ctx.Idents.get("_wcsdup");
 615   II_win_alloca = &Ctx.Idents.get("_alloca");
 616
 617   // Glib
 618   II_g_malloc = &Ctx.Idents.get("g_malloc");
 619   II_g_malloc0 = &Ctx.Idents.get("g_malloc0");
 620   II_g_realloc = &Ctx.Idents.get("g_realloc");
 621   II_g_try_malloc = &Ctx.Idents.get("g_try_malloc");
 622   II_g_try_malloc0 = &Ctx.Idents.get("g_try_malloc0");
 623   II_g_try_realloc = &Ctx.Idents.get("g_try_realloc");
 624   II_g_free = &Ctx.Idents.get("g_free");
 625   II_g_memdup = &Ctx.Idents.get("g_memdup");
 626   II_g_malloc_n = &Ctx.Idents.get("g_malloc_n");
 627   II_g_malloc0_n = &Ctx.Idents.get("g_malloc0_n");
 628   II_g_realloc_n = &Ctx.Idents.get("g_realloc_n");
 629   II_g_try_malloc_n = &Ctx.Idents.get("g_try_malloc_n");
 630   II_g_try_malloc0_n = &Ctx.Idents.get("g_try_malloc0_n");
 631   II_g_try_realloc_n = &Ctx.Idents.get("g_try_realloc_n");
 632 }
 633
 634 bool MallocChecker::isMemFunction(const FunctionDecl *FD, ASTContext &C) const {
 635   if (isCMemFunction(FD, C, AF_Malloc, MemoryOperationKind::MOK_Any))
 636     return true;
 637
 638   if (isCMemFunction(FD, C, AF_IfNameIndex, MemoryOperationKind::MOK_Any))
 639     return true;
 640
 641   if (isCMemFunction(FD, C, AF_Alloca, MemoryOperationKind::MOK_Any))
 642     return true;
 643
 644   if (isStandardNewDelete(FD, C))
 645     return true;
 646
 647   return false;
 648 }
 649
 650 bool MallocChecker::isCMemFunction(const FunctionDecl *FD,
 651                                    ASTContext &C,
 652                                    AllocationFamily Family,
 653                                    MemoryOperationKind MemKind) const {
 654   if (!FD)
 655     return false;
 656
 657   bool CheckFree = (MemKind == MemoryOperationKind::MOK_Any ||
 658                     MemKind == MemoryOperationKind::MOK_Free);
 659   bool CheckAlloc = (MemKind == MemoryOperationKind::MOK_Any ||
 660                      MemKind == MemoryOperationKind::MOK_Allocate);
 661
 662   if (FD->getKind() == Decl::Function) {
 663     const IdentifierInfo *FunI = FD->getIdentifier();
 664     initIdentifierInfo(C);
 665
 666     if (Family == AF_Malloc && CheckFree) {
 667       if (FunI == II_free || FunI == II_realloc || FunI == II_reallocf ||
 668           FunI == II_g_free || FunI == II_kfree)
 669         return true;
 670     }
 671
 672     if (Family == AF_Malloc && CheckAlloc) {
 673       if (FunI == II_malloc || FunI == II_realloc || FunI == II_reallocf ||
 674           FunI == II_calloc || FunI == II_valloc || FunI == II_strdup ||
 675           FunI == II_win_strdup || FunI == II_strndup || FunI == II_wcsdup ||
 676           FunI == II_win_wcsdup || FunI == II_kmalloc ||
 677           FunI == II_g_malloc || FunI == II_g_malloc0 ||
 678           FunI == II_g_realloc || FunI == II_g_try_malloc ||
 679           FunI == II_g_try_malloc0 || FunI == II_g_try_realloc ||
 680           FunI == II_g_memdup || FunI == II_g_malloc_n ||
 681           FunI == II_g_malloc0_n || FunI == II_g_realloc_n ||
 682           FunI == II_g_try_malloc_n || FunI == II_g_try_malloc0_n ||
 683           FunI == II_g_try_realloc_n)
 684         return true;
 685     }
 686
 687     if (Family == AF_IfNameIndex && CheckFree) {
 688       if (FunI == II_if_freenameindex)
 689         return true;
 690     }
 691
 692     if (Family == AF_IfNameIndex && CheckAlloc) {
 693       if (FunI == II_if_nameindex)
 694         return true;
 695     }
 696
 697     if (Family == AF_Alloca && CheckAlloc) {
 698       if (FunI == II_alloca || FunI == II_win_alloca)
 699         return true;
 700     }
 701   }
 702
 703   if (Family != AF_Malloc)
 704     return false;
 705
 706   if (IsOptimistic && FD->hasAttrs()) {
 707     for (const auto *I : FD->specific_attrs<OwnershipAttr>()) {
 708       OwnershipAttr::OwnershipKind OwnKind = I->getOwnKind();
 709       if(OwnKind == OwnershipAttr::Takes || OwnKind == OwnershipAttr::Holds) {
 710         if (CheckFree)
 711           return true;
 712       } else if (OwnKind == OwnershipAttr::Returns) {
 713         if (CheckAlloc)
 714           return true;
 715       }
 716     }
 717   }
 718
 719   return false;
 720 }
 721
 722 // Tells if the callee is one of the builtin new/delete operators, including
 723 // placement operators and other standard overloads.
 724 bool MallocChecker::isStandardNewDelete(const FunctionDecl *FD,
 725                                         ASTContext &C) const {
 726   if (!FD)
 727     return false;
 728
 729   OverloadedOperatorKind Kind = FD->getOverloadedOperator();
 730   if (Kind != OO_New && Kind != OO_Array_New &&
 731       Kind != OO_Delete && Kind != OO_Array_Delete)
 732     return false;
 733
 734   // This is standard if and only if it's not defined in a user file.
 735   SourceLocation L = FD->getLocation();
 736   // If the header for operator delete is not included, it's still defined
 737   // in an invalid source location. Check to make sure we don't crash.
 738   return !L.isValid() || C.getSourceManager().isInSystemHeader(L);
 739 }
 740
 741 llvm::Optional<ProgramStateRef> MallocChecker::performKernelMalloc(
 742   const CallExpr *CE, CheckerContext &C, const ProgramStateRef &State) const {
 743   // 3-argument malloc(), as commonly used in {Free,Net,Open}BSD Kernels:
 744   //
 745   // void *malloc(unsigned long size, struct malloc_type *mtp, int flags);
 746   //
 747   // One of the possible flags is M_ZERO, which means 'give me back an
 748   // allocation which is already zeroed', like calloc.
 749
 750   // 2-argument kmalloc(), as used in the Linux kernel:
 751   //
 752   // void *kmalloc(size_t size, gfp_t flags);
 753   //
 754   // Has the similar flag value __GFP_ZERO.
 755
 756   // This logic is largely cloned from O_CREAT in UnixAPIChecker, maybe some
 757   // code could be shared.
 758
 759   ASTContext &Ctx = C.getASTContext();
 760   llvm::Triple::OSType OS = Ctx.getTargetInfo().getTriple().getOS();
 761
 762   if (!KernelZeroFlagVal.hasValue()) {
 763     if (OS == llvm::Triple::FreeBSD)
 764       KernelZeroFlagVal = 0x0100;
 765     else if (OS == llvm::Triple::NetBSD)
 766       KernelZeroFlagVal = 0x0002;
 767     else if (OS == llvm::Triple::OpenBSD)
 768       KernelZeroFlagVal = 0x0008;
 769     else if (OS == llvm::Triple::Linux)
 770       // __GFP_ZERO
 771       KernelZeroFlagVal = 0x8000;
 772     else
 773       // FIXME: We need a more general way of getting the M_ZERO value.
 774       // See also: O_CREAT in UnixAPIChecker.cpp.
 775
 776       // Fall back to normal malloc behavior on platforms where we don't
 777       // know M_ZERO.
 778       return None;
 779   }
 780
 781   // We treat the last argument as the flags argument, and callers fall-back to
 782   // normal malloc on a None return. This works for the FreeBSD kernel malloc
 783   // as well as Linux kmalloc.
 784   if (CE->getNumArgs() < 2)
 785     return None;
 786
 787   const Expr *FlagsEx = CE->getArg(CE->getNumArgs() - 1);
 788   const SVal V = C.getSVal(FlagsEx);
 789   if (!V.getAs<NonLoc>()) {
 790     // The case where 'V' can be a location can only be due to a bad header,
 791     // so in this case bail out.
 792     return None;
 793   }
 794
 795   NonLoc Flags = V.castAs<NonLoc>();
 796   NonLoc ZeroFlag = C.getSValBuilder()
 797       .makeIntVal(KernelZeroFlagVal.getValue(), FlagsEx->getType())
 798       .castAs<NonLoc>();
 799   SVal MaskedFlagsUC = C.getSValBuilder().evalBinOpNN(State, BO_And,
 800                                                       Flags, ZeroFlag,
 801                                                       FlagsEx->getType());
 802   if (MaskedFlagsUC.isUnknownOrUndef())
 803     return None;
 804   DefinedSVal MaskedFlags = MaskedFlagsUC.castAs<DefinedSVal>();
 805
 806   // Check if maskedFlags is non-zero.
 807   ProgramStateRef TrueState, FalseState;
 808   std::tie(TrueState, FalseState) = State->assume(MaskedFlags);
 809
 810   // If M_ZERO is set, treat this like calloc (initialized).
 811   if (TrueState && !FalseState) {
 812     SVal ZeroVal = C.getSValBuilder().makeZeroVal(Ctx.CharTy);
 813     return MallocMemAux(C, CE, CE->getArg(0), ZeroVal, TrueState);
 814   }
 815
 816   return None;
 817 }
 818
 819 SVal MallocChecker::evalMulForBufferSize(CheckerContext &C, const Expr *Blocks,
 820                                          const Expr *BlockBytes) {
 821   SValBuilder &SB = C.getSValBuilder();
 822   SVal BlocksVal = C.getSVal(Blocks);
 823   SVal BlockBytesVal = C.getSVal(BlockBytes);
 824   ProgramStateRef State = C.getState();
 825   SVal TotalSize = SB.evalBinOp(State, BO_Mul, BlocksVal, BlockBytesVal,
 826                                 SB.getContext().getSizeType());
 827   return TotalSize;
 828 }
 829
 830 void MallocChecker::checkPostStmt(const CallExpr *CE, CheckerContext &C) const {
 831   if (C.wasInlined)
 832     return;
 833
 834   const FunctionDecl *FD = C.getCalleeDecl(CE);
 835   if (!FD)
 836     return;
 837
 838   ProgramStateRef State = C.getState();
 839   bool ReleasedAllocatedMemory = false;
 840
 841   if (FD->getKind() == Decl::Function) {
 842     initIdentifierInfo(C.getASTContext());
 843     IdentifierInfo *FunI = FD->getIdentifier();
 844
 845     if (FunI == II_malloc || FunI == II_g_malloc || FunI == II_g_try_malloc) {
 846       if (CE->getNumArgs() < 1)
 847         return;
 848       if (CE->getNumArgs() < 3) {
 849         State = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(), State);
 850         if (CE->getNumArgs() == 1)
 851           State = ProcessZeroAllocation(C, CE, 0, State);
 852       } else if (CE->getNumArgs() == 3) {
 853         llvm::Optional<ProgramStateRef> MaybeState =
 854           performKernelMalloc(CE, C, State);
 855         if (MaybeState.hasValue())
 856           State = MaybeState.getValue();
 857         else
 858           State = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(), State);
 859       }
 860     } else if (FunI == II_kmalloc) {
 861       if (CE->getNumArgs() < 1)
 862         return;
 863       llvm::Optional<ProgramStateRef> MaybeState =
 864         performKernelMalloc(CE, C, State);
 865       if (MaybeState.hasValue())
 866         State = MaybeState.getValue();
 867       else
 868         State = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(), State);
 869     } else if (FunI == II_valloc) {
 870       if (CE->getNumArgs() < 1)
 871         return;
 872       State = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(), State);
 873       State = ProcessZeroAllocation(C, CE, 0, State);
 874     } else if (FunI == II_realloc || FunI == II_g_realloc ||
 875                FunI == II_g_try_realloc) {
 876       State = ReallocMemAux(C, CE, false, State);
 877       State = ProcessZeroAllocation(C, CE, 1, State);
 878     } else if (FunI == II_reallocf) {
 879       State = ReallocMemAux(C, CE, true, State);
 880       State = ProcessZeroAllocation(C, CE, 1, State);
 881     } else if (FunI == II_calloc) {
 882       State = CallocMem(C, CE, State);
 883       State = ProcessZeroAllocation(C, CE, 0, State);
 884       State = ProcessZeroAllocation(C, CE, 1, State);
 885     } else if (FunI == II_free || FunI == II_g_free || FunI == II_kfree) {
 886       if (suppressDeallocationsInSuspiciousContexts(CE, C))
 887         return;
 888
 889       State = FreeMemAux(C, CE, State, 0, false, ReleasedAllocatedMemory);
 890     } else if (FunI == II_strdup || FunI == II_win_strdup ||
 891                FunI == II_wcsdup || FunI == II_win_wcsdup) {
 892       State = MallocUpdateRefState(C, CE, State);
 893     } else if (FunI == II_strndup) {
 894       State = MallocUpdateRefState(C, CE, State);
 895     } else if (FunI == II_alloca || FunI == II_win_alloca) {
 896       if (CE->getNumArgs() < 1)
 897         return;
 898       State = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(), State,
 899                            AF_Alloca);
 900       State = ProcessZeroAllocation(C, CE, 0, State);
 901     } else if (isStandardNewDelete(FD, C.getASTContext())) {
 902       // Process direct calls to operator new/new[]/delete/delete[] functions
 903       // as distinct from new/new[]/delete/delete[] expressions that are
 904       // processed by the checkPostStmt callbacks for CXXNewExpr and
 905       // CXXDeleteExpr.
 906       OverloadedOperatorKind K = FD->getOverloadedOperator();
 907       if (K == OO_New) {
 908         State = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(), State,
 909                              AF_CXXNew);
 910         State = ProcessZeroAllocation(C, CE, 0, State);
 911       }
 912       else if (K == OO_Array_New) {
 913         State = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(), State,
 914                              AF_CXXNewArray);
 915         State = ProcessZeroAllocation(C, CE, 0, State);
 916       }
 917       else if (K == OO_Delete || K == OO_Array_Delete)
 918         State = FreeMemAux(C, CE, State, 0, false, ReleasedAllocatedMemory);
 919       else
 920         llvm_unreachable("not a new/delete operator");
 921     } else if (FunI == II_if_nameindex) {
 922       // Should we model this differently? We can allocate a fixed number of
 923       // elements with zeros in the last one.
 924       State = MallocMemAux(C, CE, UnknownVal(), UnknownVal(), State,
 925                            AF_IfNameIndex);
 926     } else if (FunI == II_if_freenameindex) {
 927       State = FreeMemAux(C, CE, State, 0, false, ReleasedAllocatedMemory);
 928     } else if (FunI == II_g_malloc0 || FunI == II_g_try_malloc0) {
 929       if (CE->getNumArgs() < 1)
 930         return;
 931       SValBuilder &svalBuilder = C.getSValBuilder();
 932       SVal zeroVal = svalBuilder.makeZeroVal(svalBuilder.getContext().CharTy);
 933       State = MallocMemAux(C, CE, CE->getArg(0), zeroVal, State);
 934       State = ProcessZeroAllocation(C, CE, 0, State);
 935     } else if (FunI == II_g_memdup) {
 936       if (CE->getNumArgs() < 2)
 937         return;
 938       State = MallocMemAux(C, CE, CE->getArg(1), UndefinedVal(), State);
 939       State = ProcessZeroAllocation(C, CE, 1, State);
 940     } else if (FunI == II_g_malloc_n || FunI == II_g_try_malloc_n ||
 941                FunI == II_g_malloc0_n || FunI == II_g_try_malloc0_n) {
 942       if (CE->getNumArgs() < 2)
 943         return;
 944       SVal Init = UndefinedVal();
 945       if (FunI == II_g_malloc0_n || FunI == II_g_try_malloc0_n) {
 946         SValBuilder &SB = C.getSValBuilder();
 947         Init = SB.makeZeroVal(SB.getContext().CharTy);
 948       }
 949       SVal TotalSize = evalMulForBufferSize(C, CE->getArg(0), CE->getArg(1));
 950       State = MallocMemAux(C, CE, TotalSize, Init, State);
 951       State = ProcessZeroAllocation(C, CE, 0, State);
 952       State = ProcessZeroAllocation(C, CE, 1, State);
 953     } else if (FunI == II_g_realloc_n || FunI == II_g_try_realloc_n) {
 954       if (CE->getNumArgs() < 3)
 955         return;
 956       State = ReallocMemAux(C, CE, false, State, true);
 957       State = ProcessZeroAllocation(C, CE, 1, State);
 958       State = ProcessZeroAllocation(C, CE, 2, State);
 959     }
 960   }
 961
 962   if (IsOptimistic || ChecksEnabled[CK_MismatchedDeallocatorChecker]) {
 963     // Check all the attributes, if there are any.
 964     // There can be multiple of these attributes.
 965     if (FD->hasAttrs())
 966       for (const auto *I : FD->specific_attrs<OwnershipAttr>()) {
 967         switch (I->getOwnKind()) {
 968         case OwnershipAttr::Returns:
 969           State = MallocMemReturnsAttr(C, CE, I, State);
 970           break;
 971         case OwnershipAttr::Takes:
 972         case OwnershipAttr::Holds:
 973           State = FreeMemAttr(C, CE, I, State);
 974           break;
 975         }
 976       }
 977   }
 978   C.addTransition(State);
 979 }
 980
 981 // Performs a 0-sized allocations check.
 982 ProgramStateRef MallocChecker::ProcessZeroAllocation(
 983     CheckerContext &C, const Expr *E, const unsigned AllocationSizeArg,
 984     ProgramStateRef State, Optional<SVal> RetVal) const {
 985   if (!State)
 986     return nullptr;
 987
 988   if (!RetVal)
 989     RetVal = C.getSVal(E);
 990
 991   const Expr *Arg = nullptr;
 992
 993   if (const CallExpr *CE = dyn_cast<CallExpr>(E)) {
 994     Arg = CE->getArg(AllocationSizeArg);
 995   }
 996   else if (const CXXNewExpr *NE = dyn_cast<CXXNewExpr>(E)) {
 997     if (NE->isArray())
 998       Arg = *NE->getArraySize();
 999     else
1000       return State;
1001   }
1002   else
1003     llvm_unreachable("not a CallExpr or CXXNewExpr");
1004
1005   assert(Arg);
1006
1007   Optional<DefinedSVal> DefArgVal = C.getSVal(Arg).getAs<DefinedSVal>();
1008
1009   if (!DefArgVal)
1010     return State;
1011
1012   // Check if the allocation size is 0.
1013   ProgramStateRef TrueState, FalseState;
1014   SValBuilder &SvalBuilder = C.getSValBuilder();
1015   DefinedSVal Zero =
1016       SvalBuilder.makeZeroVal(Arg->getType()).castAs<DefinedSVal>();
1017
1018   std::tie(TrueState, FalseState) =
1019       State->assume(SvalBuilder.evalEQ(State, *DefArgVal, Zero));
1020
1021   if (TrueState && !FalseState) {
1022     SymbolRef Sym = RetVal->getAsLocSymbol();
1023     if (!Sym)
1024       return State;
1025
1026     const RefState *RS = State->get<RegionState>(Sym);
1027     if (RS) {
1028       if (RS->isAllocated())
1029         return TrueState->set<RegionState>(Sym,
1030                                           RefState::getAllocatedOfSizeZero(RS));
1031       else
1032         return State;
1033     } else {
1034       // Case of zero-size realloc. Historically 'realloc(ptr, 0)' is treated as
1035       // 'free(ptr)' and the returned value from 'realloc(ptr, 0)' is not
1036       // tracked. Add zero-reallocated Sym to the state to catch references
1037       // to zero-allocated memory.
1038       return TrueState->add<ReallocSizeZeroSymbols>(Sym);
1039     }
1040   }
1041
1042   // Assume the value is non-zero going forward.
1043   assert(FalseState);
1044   return FalseState;
1045 }
1046
1047 static QualType getDeepPointeeType(QualType T) {
1048   QualType Result = T, PointeeType = T->getPointeeType();
1049   while (!PointeeType.isNull()) {
1050     Result = PointeeType;
1051     PointeeType = PointeeType->getPointeeType();
1052   }
1053   return Result;
1054 }
1055
1056 static bool treatUnusedNewEscaped(const CXXNewExpr *NE) {
1057
1058   const CXXConstructExpr *ConstructE = NE->getConstructExpr();
1059   if (!ConstructE)
1060     return false;
1061
1062   if (!NE->getAllocatedType()->getAsCXXRecordDecl())
1063     return false;
1064
1065   const CXXConstructorDecl *CtorD = ConstructE->getConstructor();
1066
1067   // Iterate over the constructor parameters.
1068   for (const auto *CtorParam : CtorD->parameters()) {
1069
1070     QualType CtorParamPointeeT = CtorParam->getType()->getPointeeType();
1071     if (CtorParamPointeeT.isNull())
1072       continue;
1073
1074     CtorParamPointeeT = getDeepPointeeType(CtorParamPointeeT);
1075
1076     if (CtorParamPointeeT->getAsCXXRecordDecl())
1077       return true;
1078   }
1079
1080   return false;
1081 }
1082
1083 void MallocChecker::processNewAllocation(const CXXNewExpr *NE,
1084                                          CheckerContext &C,
1085                                          SVal Target) const {
1086   if (!isStandardNewDelete(NE->getOperatorNew(), C.getASTContext()))
1087     return;
1088
1089   ParentMap &PM = C.getLocationContext()->getParentMap();
1090   if (!PM.isConsumedExpr(NE) && treatUnusedNewEscaped(NE))
1091     return;
1092
1093   ProgramStateRef State = C.getState();
1094   // The return value from operator new is bound to a specified initialization
1095   // value (if any) and we don't want to loose this value. So we call
1096   // MallocUpdateRefState() instead of MallocMemAux() which breaks the
1097   // existing binding.
1098   State = MallocUpdateRefState(C, NE, State, NE->isArray() ? AF_CXXNewArray
1099                                                            : AF_CXXNew, Target);
1100   State = addExtentSize(C, NE, State, Target);
1101   State = ProcessZeroAllocation(C, NE, 0, State, Target);
1102   C.addTransition(State);
1103 }
1104
1105 void MallocChecker::checkPostStmt(const CXXNewExpr *NE,
1106                                   CheckerContext &C) const {
1107   if (!C.getAnalysisManager().getAnalyzerOptions().MayInlineCXXAllocator)
1108     processNewAllocation(NE, C, C.getSVal(NE));
1109 }
1110
1111 void MallocChecker::checkNewAllocator(const CXXNewExpr *NE, SVal Target,
1112                                       CheckerContext &C) const {
1113   if (!C.wasInlined)
1114     processNewAllocation(NE, C, Target);
1115 }
1116
1117 // Sets the extent value of the MemRegion allocated by
1118 // new expression NE to its size in Bytes.
1119 //
1120 ProgramStateRef MallocChecker::addExtentSize(CheckerContext &C,
1121                                              const CXXNewExpr *NE,
1122                                              ProgramStateRef State,
1123                                              SVal Target) {
1124   if (!State)
1125     return nullptr;
1126   SValBuilder &svalBuilder = C.getSValBuilder();
1127   SVal ElementCount;
1128   const SubRegion *Region;
1129   if (NE->isArray()) {
1130     const Expr *SizeExpr = *NE->getArraySize();
1131     ElementCount = C.getSVal(SizeExpr);
1132     // Store the extent size for the (symbolic)region
1133     // containing the elements.
1134     Region = Target.getAsRegion()
1135                  ->getAs<SubRegion>()
1136                  ->StripCasts()
1137                  ->getAs<SubRegion>();
1138   } else {
1139     ElementCount = svalBuilder.makeIntVal(1, true);
1140     Region = Target.getAsRegion()->getAs<SubRegion>();
1141   }
1142   assert(Region);
1143
1144   // Set the region's extent equal to the Size in Bytes.
1145   QualType ElementType = NE->getAllocatedType();
1146   ASTContext &AstContext = C.getASTContext();
1147   CharUnits TypeSize = AstContext.getTypeSizeInChars(ElementType);
1148
1149   if (ElementCount.getAs<NonLoc>()) {
1150     DefinedOrUnknownSVal Extent = Region->getExtent(svalBuilder);
1151     // size in Bytes = ElementCount*TypeSize
1152     SVal SizeInBytes = svalBuilder.evalBinOpNN(
1153         State, BO_Mul, ElementCount.castAs<NonLoc>(),
1154         svalBuilder.makeArrayIndex(TypeSize.getQuantity()),
1155         svalBuilder.getArrayIndexType());
1156     DefinedOrUnknownSVal extentMatchesSize = svalBuilder.evalEQ(
1157         State, Extent, SizeInBytes.castAs<DefinedOrUnknownSVal>());
1158     State = State->assume(extentMatchesSize, true);
1159   }
1160   return State;
1161 }
1162
1163 void MallocChecker::checkPreStmt(const CXXDeleteExpr *DE,
1164                                  CheckerContext &C) const {
1165
1166   if (!ChecksEnabled[CK_NewDeleteChecker])
1167     if (SymbolRef Sym = C.getSVal(DE->getArgument()).getAsSymbol())
1168       checkUseAfterFree(Sym, C, DE->getArgument());
1169
1170   if (!isStandardNewDelete(DE->getOperatorDelete(), C.getASTContext()))
1171     return;
1172
1173   ProgramStateRef State = C.getState();
1174   bool ReleasedAllocated;
1175   State = FreeMemAux(C, DE->getArgument(), DE, State,
1176                      /*Hold*/false, ReleasedAllocated);
1177
1178   C.addTransition(State);
1179 }
1180
1181 static bool isKnownDeallocObjCMethodName(const ObjCMethodCall &Call) {
1182   // If the first selector piece is one of the names below, assume that the
1183   // object takes ownership of the memory, promising to eventually deallocate it
1184   // with free().
1185   // Ex:  [NSData dataWithBytesNoCopy:bytes length:10];
1186   // (...unless a 'freeWhenDone' parameter is false, but that's checked later.)
1187   StringRef FirstSlot = Call.getSelector().getNameForSlot(0);
1188   return FirstSlot == "dataWithBytesNoCopy" ||
1189          FirstSlot == "initWithBytesNoCopy" ||
1190          FirstSlot == "initWithCharactersNoCopy";
1191 }
1192
1193 static Optional<bool> getFreeWhenDoneArg(const ObjCMethodCall &Call) {
1194   Selector S = Call.getSelector();
1195
1196   // FIXME: We should not rely on fully-constrained symbols being folded.
1197   for (unsigned i = 1; i < S.getNumArgs(); ++i)
1198     if (S.getNameForSlot(i).equals("freeWhenDone"))
1199       return !Call.getArgSVal(i).isZeroConstant();
1200
1201   return None;
1202 }
1203
1204 void MallocChecker::checkPostObjCMessage(const ObjCMethodCall &Call,
1205                                          CheckerContext &C) const {
1206   if (C.wasInlined)
1207     return;
1208
1209   if (!isKnownDeallocObjCMethodName(Call))
1210     return;
1211
1212   if (Optional<bool> FreeWhenDone = getFreeWhenDoneArg(Call))
1213     if (!*FreeWhenDone)
1214       return;
1215
1216   bool ReleasedAllocatedMemory;
1217   ProgramStateRef State = FreeMemAux(C, Call.getArgExpr(0),
1218                                      Call.getOriginExpr(), C.getState(),
1219                                      /*Hold=*/true, ReleasedAllocatedMemory,
1220                                      /*ReturnsNullOnFailure=*/true);
1221
1222   C.addTransition(State);
1223 }
1224
1225 ProgramStateRef
1226 MallocChecker::MallocMemReturnsAttr(CheckerContext &C, const CallExpr *CE,
1227                                     const OwnershipAttr *Att,
1228                                     ProgramStateRef State) const {
1229   if (!State)
1230     return nullptr;
1231
1232   if (Att->getModule() != II_malloc)
1233     return nullptr;
1234
1235   OwnershipAttr::args_iterator I = Att->args_begin(), E = Att->args_end();
1236   if (I != E) {
1237     return MallocMemAux(C, CE, CE->getArg(I->getASTIndex()), UndefinedVal(),
1238                         State);
1239   }
1240   return MallocMemAux(C, CE, UnknownVal(), UndefinedVal(), State);
1241 }
1242
1243 ProgramStateRef MallocChecker::MallocMemAux(CheckerContext &C,
1244                                             const CallExpr *CE,
1245                                             const Expr *SizeEx, SVal Init,
1246                                             ProgramStateRef State,
1247                                             AllocationFamily Family) {
1248   if (!State)
1249     return nullptr;
1250
1251   return MallocMemAux(C, CE, C.getSVal(SizeEx), Init, State, Family);
1252 }
1253
1254 ProgramStateRef MallocChecker::MallocMemAux(CheckerContext &C,
1255                                            const CallExpr *CE,
1256                                            SVal Size, SVal Init,
1257                                            ProgramStateRef State,
1258                                            AllocationFamily Family) {
1259   if (!State)
1260     return nullptr;
1261
1262   // We expect the malloc functions to return a pointer.
1263   if (!Loc::isLocType(CE->getType()))
1264     return nullptr;
1265
1266   // Bind the return value to the symbolic value from the heap region.
1267   // TODO: We could rewrite post visit to eval call; 'malloc' does not have
1268   // side effects other than what we model here.
1269   unsigned Count = C.blockCount();
1270   SValBuilder &svalBuilder = C.getSValBuilder();
1271   const LocationContext *LCtx = C.getPredecessor()->getLocationContext();
1272   DefinedSVal RetVal = svalBuilder.getConjuredHeapSymbolVal(CE, LCtx, Count)
1273       .castAs<DefinedSVal>();
1274   State = State->BindExpr(CE, C.getLocationContext(), RetVal);
1275
1276   // Fill the region with the initialization value.
1277   State = State->bindDefaultInitial(RetVal, Init, LCtx);
1278
1279   // Set the region's extent equal to the Size parameter.
1280   const SymbolicRegion *R =
1281       dyn_cast_or_null<SymbolicRegion>(RetVal.getAsRegion());
1282   if (!R)
1283     return nullptr;
1284   if (Optional<DefinedOrUnknownSVal> DefinedSize =
1285           Size.getAs<DefinedOrUnknownSVal>()) {
1286     SValBuilder &svalBuilder = C.getSValBuilder();
1287     DefinedOrUnknownSVal Extent = R->getExtent(svalBuilder);
1288     DefinedOrUnknownSVal extentMatchesSize =
1289         svalBuilder.evalEQ(State, Extent, *DefinedSize);
1290
1291     State = State->assume(extentMatchesSize, true);
1292     assert(State);
1293   }
1294
1295   return MallocUpdateRefState(C, CE, State, Family);
1296 }
1297
1298 ProgramStateRef MallocChecker::MallocUpdateRefState(CheckerContext &C,
1299                                                     const Expr *E,
1300                                                     ProgramStateRef State,
1301                                                     AllocationFamily Family,
1302                                                     Optional<SVal> RetVal) {
1303   if (!State)
1304     return nullptr;
1305
1306   // Get the return value.
1307   if (!RetVal)
1308     RetVal = C.getSVal(E);
1309
1310   // We expect the malloc functions to return a pointer.
1311   if (!RetVal->getAs<Loc>())
1312     return nullptr;
1313
1314   SymbolRef Sym = RetVal->getAsLocSymbol();
1315   // This is a return value of a function that was not inlined, such as malloc()
1316   // or new(). We've checked that in the caller. Therefore, it must be a symbol.
1317   assert(Sym);
1318
1319   // Set the symbol's state to Allocated.
1320   return State->set<RegionState>(Sym, RefState::getAllocated(Family, E));
1321 }
1322
1323 ProgramStateRef MallocChecker::FreeMemAttr(CheckerContext &C,
1324                                            const CallExpr *CE,
1325                                            const OwnershipAttr *Att,
1326                                            ProgramStateRef State) const {
1327   if (!State)
1328     return nullptr;
1329
1330   if (Att->getModule() != II_malloc)
1331     return nullptr;
1332
1333   bool ReleasedAllocated = false;
1334
1335   for (const auto &Arg : Att->args()) {
1336     ProgramStateRef StateI = FreeMemAux(
1337         C, CE, State, Arg.getASTIndex(),
1338         Att->getOwnKind() == OwnershipAttr::Holds, ReleasedAllocated);
1339     if (StateI)
1340       State = StateI;
1341   }
1342   return State;
1343 }
1344
1345 ProgramStateRef MallocChecker::FreeMemAux(CheckerContext &C,
1346                                           const CallExpr *CE,
1347                                           ProgramStateRef State,
1348                                           unsigned Num,
1349                                           bool Hold,
1350                                           bool &ReleasedAllocated,
1351                                           bool ReturnsNullOnFailure) const {
1352   if (!State)
1353     return nullptr;
1354
1355   if (CE->getNumArgs() < (Num + 1))
1356     return nullptr;
1357
1358   return FreeMemAux(C, CE->getArg(Num), CE, State, Hold,
1359                     ReleasedAllocated, ReturnsNullOnFailure);
1360 }
1361
1362 /// Checks if the previous call to free on the given symbol failed - if free
1363 /// failed, returns true. Also, returns the corresponding return value symbol.
1364 static bool didPreviousFreeFail(ProgramStateRef State,
1365                                 SymbolRef Sym, SymbolRef &RetStatusSymbol) {
1366   const SymbolRef *Ret = State->get<FreeReturnValue>(Sym);
1367   if (Ret) {
1368     assert(*Ret && "We should not store the null return symbol");
1369     ConstraintManager &CMgr = State->getConstraintManager();
1370     ConditionTruthVal FreeFailed = CMgr.isNull(State, *Ret);
1371     RetStatusSymbol = *Ret;
1372     return FreeFailed.isConstrainedTrue();
1373   }
1374   return false;
1375 }
1376
1377 AllocationFamily MallocChecker::getAllocationFamily(CheckerContext &C,
1378                                                     const Stmt *S) const {
1379   if (!S)
1380     return AF_None;
1381
1382   if (const CallExpr *CE = dyn_cast<CallExpr>(S)) {
1383     const FunctionDecl *FD = C.getCalleeDecl(CE);
1384
1385     if (!FD)
1386       FD = dyn_cast<FunctionDecl>(CE->getCalleeDecl());
1387
1388     ASTContext &Ctx = C.getASTContext();
1389
1390     if (isCMemFunction(FD, Ctx, AF_Malloc, MemoryOperationKind::MOK_Any))
1391       return AF_Malloc;
1392
1393     if (isStandardNewDelete(FD, Ctx)) {
1394       OverloadedOperatorKind Kind = FD->getOverloadedOperator();
1395       if (Kind == OO_New || Kind == OO_Delete)
1396         return AF_CXXNew;
1397       else if (Kind == OO_Array_New || Kind == OO_Array_Delete)
1398         return AF_CXXNewArray;
1399     }
1400
1401     if (isCMemFunction(FD, Ctx, AF_IfNameIndex, MemoryOperationKind::MOK_Any))
1402       return AF_IfNameIndex;
1403
1404     if (isCMemFunction(FD, Ctx, AF_Alloca, MemoryOperationKind::MOK_Any))
1405       return AF_Alloca;
1406
1407     return AF_None;
1408   }
1409
1410   if (const CXXNewExpr *NE = dyn_cast<CXXNewExpr>(S))
1411     return NE->isArray() ? AF_CXXNewArray : AF_CXXNew;
1412
1413   if (const CXXDeleteExpr *DE = dyn_cast<CXXDeleteExpr>(S))
1414     return DE->isArrayForm() ? AF_CXXNewArray : AF_CXXNew;
1415
1416   if (isa<ObjCMessageExpr>(S))
1417     return AF_Malloc;
1418
1419   return AF_None;
1420 }
1421
1422 bool MallocChecker::printAllocDeallocName(raw_ostream &os, CheckerContext &C,
1423                                           const Expr *E) const {
1424   if (const CallExpr *CE = dyn_cast<CallExpr>(E)) {
1425     // FIXME: This doesn't handle indirect calls.
1426     const FunctionDecl *FD = CE->getDirectCallee();
1427     if (!FD)
1428       return false;
1429
1430     os << *FD;
1431     if (!FD->isOverloadedOperator())
1432       os << "()";
1433     return true;
1434   }
1435
1436   if (const ObjCMessageExpr *Msg = dyn_cast<ObjCMessageExpr>(E)) {
1437     if (Msg->isInstanceMessage())
1438       os << "-";
1439     else
1440       os << "+";
1441     Msg->getSelector().print(os);
1442     return true;
1443   }
1444
1445   if (const CXXNewExpr *NE = dyn_cast<CXXNewExpr>(E)) {
1446     os << "'"
1447        << getOperatorSpelling(NE->getOperatorNew()->getOverloadedOperator())
1448        << "'";
1449     return true;
1450   }
1451
1452   if (const CXXDeleteExpr *DE = dyn_cast<CXXDeleteExpr>(E)) {
1453     os << "'"
1454        << getOperatorSpelling(DE->getOperatorDelete()->getOverloadedOperator())
1455        << "'";
1456     return true;
1457   }
1458
1459   return false;
1460 }
1461
1462 void MallocChecker::printExpectedAllocName(raw_ostream &os, CheckerContext &C,
1463                                            const Expr *E) const {
1464   AllocationFamily Family = getAllocationFamily(C, E);
1465
1466   switch(Family) {
1467     case AF_Malloc: os << "malloc()"; return;
1468     case AF_CXXNew: os << "'new'"; return;
1469     case AF_CXXNewArray: os << "'new[]'"; return;
1470     case AF_IfNameIndex: os << "'if_nameindex()'"; return;
1471     case AF_InnerBuffer: os << "container-specific allocator"; return;
1472     case AF_Alloca:
1473     case AF_None: llvm_unreachable("not a deallocation expression");
1474   }
1475 }
1476
1477 void MallocChecker::printExpectedDeallocName(raw_ostream &os,
1478                                              AllocationFamily Family) const {
1479   switch(Family) {
1480     case AF_Malloc: os << "free()"; return;
1481     case AF_CXXNew: os << "'delete'"; return;
1482     case AF_CXXNewArray: os << "'delete[]'"; return;
1483     case AF_IfNameIndex: os << "'if_freenameindex()'"; return;
1484     case AF_InnerBuffer: os << "container-specific deallocator"; return;
1485     case AF_Alloca:
1486     case AF_None: llvm_unreachable("suspicious argument");
1487   }
1488 }
1489
1490 ProgramStateRef MallocChecker::FreeMemAux(CheckerContext &C,
1491                                           const Expr *ArgExpr,
1492                                           const Expr *ParentExpr,
1493                                           ProgramStateRef State,
1494                                           bool Hold,
1495                                           bool &ReleasedAllocated,
1496                                           bool ReturnsNullOnFailure) const {
1497
1498   if (!State)
1499     return nullptr;
1500
1501   SVal ArgVal = C.getSVal(ArgExpr);
1502   if (!ArgVal.getAs<DefinedOrUnknownSVal>())
1503     return nullptr;
1504   DefinedOrUnknownSVal location = ArgVal.castAs<DefinedOrUnknownSVal>();
1505
1506   // Check for null dereferences.
1507   if (!location.getAs<Loc>())
1508     return nullptr;
1509
1510   // The explicit NULL case, no operation is performed.
1511   ProgramStateRef notNullState, nullState;
1512   std::tie(notNullState, nullState) = State->assume(location);
1513   if (nullState && !notNullState)
1514     return nullptr;
1515
1516   // Unknown values could easily be okay
1517   // Undefined values are handled elsewhere
1518   if (ArgVal.isUnknownOrUndef())
1519     return nullptr;
1520
1521   const MemRegion *R = ArgVal.getAsRegion();
1522
1523   // Nonlocs can't be freed, of course.
1524   // Non-region locations (labels and fixed addresses) also shouldn't be freed.
1525   if (!R) {
1526     ReportBadFree(C, ArgVal, ArgExpr->getSourceRange(), ParentExpr);
1527     return nullptr;
1528   }
1529
1530   R = R->StripCasts();
1531
1532   // Blocks might show up as heap data, but should not be free()d
1533   if (isa<BlockDataRegion>(R)) {
1534     ReportBadFree(C, ArgVal, ArgExpr->getSourceRange(), ParentExpr);
1535     return nullptr;
1536   }
1537
1538   const MemSpaceRegion *MS = R->getMemorySpace();
1539
1540   // Parameters, locals, statics, globals, and memory returned by
1541   // __builtin_alloca() shouldn't be freed.
1542   if (!(isa<UnknownSpaceRegion>(MS) || isa<HeapSpaceRegion>(MS))) {
1543     // FIXME: at the time this code was written, malloc() regions were
1544     // represented by conjured symbols, which are all in UnknownSpaceRegion.
1545     // This means that there isn't actually anything from HeapSpaceRegion
1546     // that should be freed, even though we allow it here.
1547     // Of course, free() can work on memory allocated outside the current
1548     // function, so UnknownSpaceRegion is always a possibility.
1549     // False negatives are better than false positives.
1550
1551     if (isa<AllocaRegion>(R))
1552       ReportFreeAlloca(C, ArgVal, ArgExpr->getSourceRange());
1553     else
1554       ReportBadFree(C, ArgVal, ArgExpr->getSourceRange(), ParentExpr);
1555
1556     return nullptr;
1557   }
1558
1559   const SymbolicRegion *SrBase = dyn_cast<SymbolicRegion>(R->getBaseRegion());
1560   // Various cases could lead to non-symbol values here.
1561   // For now, ignore them.
1562   if (!SrBase)
1563     return nullptr;
1564
1565   SymbolRef SymBase = SrBase->getSymbol();
1566   const RefState *RsBase = State->get<RegionState>(SymBase);
1567   SymbolRef PreviousRetStatusSymbol = nullptr;
1568
1569   if (RsBase) {
1570
1571     // Memory returned by alloca() shouldn't be freed.
1572     if (RsBase->getAllocationFamily() == AF_Alloca) {
1573       ReportFreeAlloca(C, ArgVal, ArgExpr->getSourceRange());
1574       return nullptr;
1575     }
1576
1577     // Check for double free first.
1578     if ((RsBase->isReleased() || RsBase->isRelinquished()) &&
1579         !didPreviousFreeFail(State, SymBase, PreviousRetStatusSymbol)) {
1580       ReportDoubleFree(C, ParentExpr->getSourceRange(), RsBase->isReleased(),
1581                        SymBase, PreviousRetStatusSymbol);
1582       return nullptr;
1583
1584     // If the pointer is allocated or escaped, but we are now trying to free it,
1585     // check that the call to free is proper.
1586     } else if (RsBase->isAllocated() || RsBase->isAllocatedOfSizeZero() ||
1587                RsBase->isEscaped()) {
1588
1589       // Check if an expected deallocation function matches the real one.
1590       bool DeallocMatchesAlloc =
1591         RsBase->getAllocationFamily() == getAllocationFamily(C, ParentExpr);
1592       if (!DeallocMatchesAlloc) {
1593         ReportMismatchedDealloc(C, ArgExpr->getSourceRange(),
1594                                 ParentExpr, RsBase, SymBase, Hold);
1595         return nullptr;
1596       }
1597
1598       // Check if the memory location being freed is the actual location
1599       // allocated, or an offset.
1600       RegionOffset Offset = R->getAsOffset();
1601       if (Offset.isValid() &&
1602           !Offset.hasSymbolicOffset() &&
1603           Offset.getOffset() != 0) {
1604         const Expr *AllocExpr = cast<Expr>(RsBase->getStmt());
1605         ReportOffsetFree(C, ArgVal, ArgExpr->getSourceRange(), ParentExpr,
1606                          AllocExpr);
1607         return nullptr;
1608       }
1609     }
1610   }
1611
1612   if (SymBase->getType()->isFunctionPointerType()) {
1613     ReportFunctionPointerFree(C, ArgVal, ArgExpr->getSourceRange(), ParentExpr);
1614     return nullptr;
1615   }
1616
1617   ReleasedAllocated = (RsBase != nullptr) && (RsBase->isAllocated() ||
1618                                               RsBase->isAllocatedOfSizeZero());
1619
1620   // Clean out the info on previous call to free return info.
1621   State = State->remove<FreeReturnValue>(SymBase);
1622
1623   // Keep track of the return value. If it is NULL, we will know that free
1624   // failed.
1625   if (ReturnsNullOnFailure) {
1626     SVal RetVal = C.getSVal(ParentExpr);
1627     SymbolRef RetStatusSymbol = RetVal.getAsSymbol();
1628     if (RetStatusSymbol) {
1629       C.getSymbolManager().addSymbolDependency(SymBase, RetStatusSymbol);
1630       State = State->set<FreeReturnValue>(SymBase, RetStatusSymbol);
1631     }
1632   }
1633
1634   AllocationFamily Family = RsBase ? RsBase->getAllocationFamily()
1635                                    : getAllocationFamily(C, ParentExpr);
1636   // Normal free.
1637   if (Hold)
1638     return State->set<RegionState>(SymBase,
1639                                    RefState::getRelinquished(Family,
1640                                                              ParentExpr));
1641
1642   return State->set<RegionState>(SymBase,
1643                                  RefState::getReleased(Family, ParentExpr));
1644 }
1645
1646 Optional<MallocChecker::CheckKind>
1647 MallocChecker::getCheckIfTracked(AllocationFamily Family,
1648                                  bool IsALeakCheck) const {
1649   switch (Family) {
1650   case AF_Malloc:
1651   case AF_Alloca:
1652   case AF_IfNameIndex: {
1653     if (ChecksEnabled[CK_MallocChecker])
1654       return CK_MallocChecker;
1655     return None;
1656   }
1657   case AF_CXXNew:
1658   case AF_CXXNewArray: {
1659     if (IsALeakCheck) {
1660       if (ChecksEnabled[CK_NewDeleteLeaksChecker])
1661         return CK_NewDeleteLeaksChecker;
1662     }
1663     else {
1664       if (ChecksEnabled[CK_NewDeleteChecker])
1665         return CK_NewDeleteChecker;
1666     }
1667     return None;
1668   }
1669   case AF_InnerBuffer: {
1670     if (ChecksEnabled[CK_InnerPointerChecker])
1671       return CK_InnerPointerChecker;
1672     return None;
1673   }
1674   case AF_None: {
1675     llvm_unreachable("no family");
1676   }
1677   }
1678   llvm_unreachable("unhandled family");
1679 }
1680
1681 Optional<MallocChecker::CheckKind>
1682 MallocChecker::getCheckIfTracked(CheckerContext &C,
1683                                  const Stmt *AllocDeallocStmt,
1684                                  bool IsALeakCheck) const {
1685   return getCheckIfTracked(getAllocationFamily(C, AllocDeallocStmt),
1686                            IsALeakCheck);
1687 }
1688
1689 Optional<MallocChecker::CheckKind>
1690 MallocChecker::getCheckIfTracked(CheckerContext &C, SymbolRef Sym,
1691                                  bool IsALeakCheck) const {
1692   if (C.getState()->contains<ReallocSizeZeroSymbols>(Sym))
1693     return CK_MallocChecker;
1694
1695   const RefState *RS = C.getState()->get<RegionState>(Sym);
1696   assert(RS);
1697   return getCheckIfTracked(RS->getAllocationFamily(), IsALeakCheck);
1698 }
1699
1700 bool MallocChecker::SummarizeValue(raw_ostream &os, SVal V) {
1701   if (Optional<nonloc::ConcreteInt> IntVal = V.getAs<nonloc::ConcreteInt>())
1702     os << "an integer (" << IntVal->getValue() << ")";
1703   else if (Optional<loc::ConcreteInt> ConstAddr = V.getAs<loc::ConcreteInt>())
1704     os << "a constant address (" << ConstAddr->getValue() << ")";
1705   else if (Optional<loc::GotoLabel> Label = V.getAs<loc::GotoLabel>())
1706     os << "the address of the label '" << Label->getLabel()->getName() << "'";
1707   else
1708     return false;
1709
1710   return true;
1711 }
1712
1713 bool MallocChecker::SummarizeRegion(raw_ostream &os,
1714                                     const MemRegion *MR) {
1715   switch (MR->getKind()) {
1716   case MemRegion::FunctionCodeRegionKind: {
1717     const NamedDecl *FD = cast<FunctionCodeRegion>(MR)->getDecl();
1718     if (FD)
1719       os << "the address of the function '" << *FD << '\'';
1720     else
1721       os << "the address of a function";
1722     return true;
1723   }
1724   case MemRegion::BlockCodeRegionKind:
1725     os << "block text";
1726     return true;
1727   case MemRegion::BlockDataRegionKind:
1728     // FIXME: where the block came from?
1729     os << "a block";
1730     return true;
1731   default: {
1732     const MemSpaceRegion *MS = MR->getMemorySpace();
1733
1734     if (isa<StackLocalsSpaceRegion>(MS)) {
1735       const VarRegion *VR = dyn_cast<VarRegion>(MR);
1736       const VarDecl *VD;
1737       if (VR)
1738         VD = VR->getDecl();
1739       else
1740         VD = nullptr;
1741
1742       if (VD)
1743         os << "the address of the local variable '" << VD->getName() << "'";
1744       else
1745         os << "the address of a local stack variable";
1746       return true;
1747     }
1748
1749     if (isa<StackArgumentsSpaceRegion>(MS)) {
1750       const VarRegion *VR = dyn_cast<VarRegion>(MR);
1751       const VarDecl *VD;
1752       if (VR)
1753         VD = VR->getDecl();
1754       else
1755         VD = nullptr;
1756
1757       if (VD)
1758         os << "the address of the parameter '" << VD->getName() << "'";
1759       else
1760         os << "the address of a parameter";
1761       return true;
1762     }
1763
1764     if (isa<GlobalsSpaceRegion>(MS)) {
1765       const VarRegion *VR = dyn_cast<VarRegion>(MR);
1766       const VarDecl *VD;
1767       if (VR)
1768         VD = VR->getDecl();
1769       else
1770         VD = nullptr;
1771
1772       if (VD) {
1773         if (VD->isStaticLocal())
1774           os << "the address of the static variable '" << VD->getName() << "'";
1775         else
1776           os << "the address of the global variable '" << VD->getName() << "'";
1777       } else
1778         os << "the address of a global variable";
1779       return true;
1780     }
1781
1782     return false;
1783   }
1784   }
1785 }
1786
1787 void MallocChecker::ReportBadFree(CheckerContext &C, SVal ArgVal,
1788                                   SourceRange Range,
1789                                   const Expr *DeallocExpr) const {
1790
1791   if (!ChecksEnabled[CK_MallocChecker] &&
1792       !ChecksEnabled[CK_NewDeleteChecker])
1793     return;
1794
1795   Optional<MallocChecker::CheckKind> CheckKind =
1796       getCheckIfTracked(C, DeallocExpr);
1797   if (!CheckKind.hasValue())
1798     return;
1799
1800   if (ExplodedNode *N = C.generateErrorNode()) {
1801     if (!BT_BadFree[*CheckKind])
1802       BT_BadFree[*CheckKind].reset(new BugType(
1803           CheckNames[*CheckKind], "Bad free", categories::MemoryError));
1804
1805     SmallString<100> buf;
1806     llvm::raw_svector_ostream os(buf);
1807
1808     const MemRegion *MR = ArgVal.getAsRegion();
1809     while (const ElementRegion *ER = dyn_cast_or_null<ElementRegion>(MR))
1810       MR = ER->getSuperRegion();
1811
1812     os << "Argument to ";
1813     if (!printAllocDeallocName(os, C, DeallocExpr))
1814       os << "deallocator";
1815
1816     os << " is ";
1817     bool Summarized = MR ? SummarizeRegion(os, MR)
1818                          : SummarizeValue(os, ArgVal);
1819     if (Summarized)
1820       os << ", which is not memory allocated by ";
1821     else
1822       os << "not memory allocated by ";
1823
1824     printExpectedAllocName(os, C, DeallocExpr);
1825
1826     auto R = llvm::make_unique<BugReport>(*BT_BadFree[*CheckKind], os.str(), N);
1827     R->markInteresting(MR);
1828     R->addRange(Range);
1829     C.emitReport(std::move(R));
1830   }
1831 }
1832
1833 void MallocChecker::ReportFreeAlloca(CheckerContext &C, SVal ArgVal,
1834                                      SourceRange Range) const {
1835
1836   Optional<MallocChecker::CheckKind> CheckKind;
1837
1838   if (ChecksEnabled[CK_MallocChecker])
1839     CheckKind = CK_MallocChecker;
1840   else if (ChecksEnabled[CK_MismatchedDeallocatorChecker])
1841     CheckKind = CK_MismatchedDeallocatorChecker;
1842   else
1843     return;
1844
1845   if (ExplodedNode *N = C.generateErrorNode()) {
1846     if (!BT_FreeAlloca[*CheckKind])
1847       BT_FreeAlloca[*CheckKind].reset(new BugType(
1848           CheckNames[*CheckKind], "Free alloca()", categories::MemoryError));
1849
1850     auto R = llvm::make_unique<BugReport>(
1851         *BT_FreeAlloca[*CheckKind],
1852         "Memory allocated by alloca() should not be deallocated", N);
1853     R->markInteresting(ArgVal.getAsRegion());
1854     R->addRange(Range);
1855     C.emitReport(std::move(R));
1856   }
1857 }
1858
1859 void MallocChecker::ReportMismatchedDealloc(CheckerContext &C,
1860                                             SourceRange Range,
1861                                             const Expr *DeallocExpr,
1862                                             const RefState *RS,
1863                                             SymbolRef Sym,
1864                                             bool OwnershipTransferred) const {
1865
1866   if (!ChecksEnabled[CK_MismatchedDeallocatorChecker])
1867     return;
1868
1869   if (ExplodedNode *N = C.generateErrorNode()) {
1870     if (!BT_MismatchedDealloc)
1871       BT_MismatchedDealloc.reset(
1872           new BugType(CheckNames[CK_MismatchedDeallocatorChecker],
1873                       "Bad deallocator", categories::MemoryError));
1874
1875     SmallString<100> buf;
1876     llvm::raw_svector_ostream os(buf);
1877
1878     const Expr *AllocExpr = cast<Expr>(RS->getStmt());
1879     SmallString<20> AllocBuf;
1880     llvm::raw_svector_ostream AllocOs(AllocBuf);
1881     SmallString<20> DeallocBuf;
1882     llvm::raw_svector_ostream DeallocOs(DeallocBuf);
1883
1884     if (OwnershipTransferred) {
1885       if (printAllocDeallocName(DeallocOs, C, DeallocExpr))
1886         os << DeallocOs.str() << " cannot";
1887       else
1888         os << "Cannot";
1889
1890       os << " take ownership of memory";
1891
1892       if (printAllocDeallocName(AllocOs, C, AllocExpr))
1893         os << " allocated by " << AllocOs.str();
1894     } else {
1895       os << "Memory";
1896       if (printAllocDeallocName(AllocOs, C, AllocExpr))
1897         os << " allocated by " << AllocOs.str();
1898
1899       os << " should be deallocated by ";
1900         printExpectedDeallocName(os, RS->getAllocationFamily());
1901
1902       if (printAllocDeallocName(DeallocOs, C, DeallocExpr))
1903         os << ", not " << DeallocOs.str();
1904     }
1905
1906     auto R = llvm::make_unique<BugReport>(*BT_MismatchedDealloc, os.str(), N);
1907     R->markInteresting(Sym);
1908     R->addRange(Range);
1909     R->addVisitor(llvm::make_unique<MallocBugVisitor>(Sym));
1910     C.emitReport(std::move(R));
1911   }
1912 }
1913
1914 void MallocChecker::ReportOffsetFree(CheckerContext &C, SVal ArgVal,
1915                                      SourceRange Range, const Expr *DeallocExpr,
1916                                      const Expr *AllocExpr) const {
1917
1918
1919   if (!ChecksEnabled[CK_MallocChecker] &&
1920       !ChecksEnabled[CK_NewDeleteChecker])
1921     return;
1922
1923   Optional<MallocChecker::CheckKind> CheckKind =
1924       getCheckIfTracked(C, AllocExpr);
1925   if (!CheckKind.hasValue())
1926     return;
1927
1928   ExplodedNode *N = C.generateErrorNode();
1929   if (!N)
1930     return;
1931
1932   if (!BT_OffsetFree[*CheckKind])
1933     BT_OffsetFree[*CheckKind].reset(new BugType(
1934         CheckNames[*CheckKind], "Offset free", categories::MemoryError));
1935
1936   SmallString<100> buf;
1937   llvm::raw_svector_ostream os(buf);
1938   SmallString<20> AllocNameBuf;
1939   llvm::raw_svector_ostream AllocNameOs(AllocNameBuf);
1940
1941   const MemRegion *MR = ArgVal.getAsRegion();
1942   assert(MR && "Only MemRegion based symbols can have offset free errors");
1943
1944   RegionOffset Offset = MR->getAsOffset();
1945   assert((Offset.isValid() &&
1946           !Offset.hasSymbolicOffset() &&
1947           Offset.getOffset() != 0) &&
1948          "Only symbols with a valid offset can have offset free errors");
1949
1950   int offsetBytes = Offset.getOffset() / C.getASTContext().getCharWidth();
1951
1952   os << "Argument to ";
1953   if (!printAllocDeallocName(os, C, DeallocExpr))
1954     os << "deallocator";
1955   os << " is offset by "
1956      << offsetBytes
1957      << " "
1958      << ((abs(offsetBytes) > 1) ? "bytes" : "byte")
1959      << " from the start of ";
1960   if (AllocExpr && printAllocDeallocName(AllocNameOs, C, AllocExpr))
1961     os << "memory allocated by " << AllocNameOs.str();
1962   else
1963     os << "allocated memory";
1964
1965   auto R = llvm::make_unique<BugReport>(*BT_OffsetFree[*CheckKind], os.str(), N);
1966   R->markInteresting(MR->getBaseRegion());
1967   R->addRange(Range);
1968   C.emitReport(std::move(R));
1969 }
1970
1971 void MallocChecker::ReportUseAfterFree(CheckerContext &C, SourceRange Range,
1972                                        SymbolRef Sym) const {
1973
1974   if (!ChecksEnabled[CK_MallocChecker] &&
1975       !ChecksEnabled[CK_NewDeleteChecker] &&
1976       !ChecksEnabled[CK_InnerPointerChecker])
1977     return;
1978
1979   Optional<MallocChecker::CheckKind> CheckKind = getCheckIfTracked(C, Sym);
1980   if (!CheckKind.hasValue())
1981     return;
1982
1983   if (ExplodedNode *N = C.generateErrorNode()) {
1984     if (!BT_UseFree[*CheckKind])
1985       BT_UseFree[*CheckKind].reset(new BugType(
1986           CheckNames[*CheckKind], "Use-after-free", categories::MemoryError));
1987
1988     AllocationFamily AF =
1989         C.getState()->get<RegionState>(Sym)->getAllocationFamily();
1990
1991     auto R = llvm::make_unique<BugReport>(*BT_UseFree[*CheckKind],
1992         AF == AF_InnerBuffer
1993               ? "Inner pointer of container used after re/deallocation"
1994               : "Use of memory after it is freed",
1995         N);
1996
1997     R->markInteresting(Sym);
1998     R->addRange(Range);
1999     R->addVisitor(llvm::make_unique<MallocBugVisitor>(Sym));
2000
2001     if (AF == AF_InnerBuffer)
2002       R->addVisitor(allocation_state::getInnerPointerBRVisitor(Sym));
2003
2004     C.emitReport(std::move(R));
2005   }
2006 }
2007
2008 void MallocChecker::ReportDoubleFree(CheckerContext &C, SourceRange Range,
2009                                      bool Released, SymbolRef Sym,
2010                                      SymbolRef PrevSym) const {
2011
2012   if (!ChecksEnabled[CK_MallocChecker] &&
2013       !ChecksEnabled[CK_NewDeleteChecker])
2014     return;
2015
2016   Optional<MallocChecker::CheckKind> CheckKind = getCheckIfTracked(C, Sym);
2017   if (!CheckKind.hasValue())
2018     return;
2019
2020   if (ExplodedNode *N = C.generateErrorNode()) {
2021     if (!BT_DoubleFree[*CheckKind])
2022       BT_DoubleFree[*CheckKind].reset(new BugType(
2023           CheckNames[*CheckKind], "Double free", categories::MemoryError));
2024
2025     auto R = llvm::make_unique<BugReport>(
2026         *BT_DoubleFree[*CheckKind],
2027         (Released ? "Attempt to free released memory"
2028                   : "Attempt to free non-owned memory"),
2029         N);
2030     R->addRange(Range);
2031     R->markInteresting(Sym);
2032     if (PrevSym)
2033       R->markInteresting(PrevSym);
2034     R->addVisitor(llvm::make_unique<MallocBugVisitor>(Sym));
2035     C.emitReport(std::move(R));
2036   }
2037 }
2038
2039 void MallocChecker::ReportDoubleDelete(CheckerContext &C, SymbolRef Sym) const {
2040
2041   if (!ChecksEnabled[CK_NewDeleteChecker])
2042     return;
2043
2044   Optional<MallocChecker::CheckKind> CheckKind = getCheckIfTracked(C, Sym);
2045   if (!CheckKind.hasValue())
2046     return;
2047
2048   if (ExplodedNode *N = C.generateErrorNode()) {
2049     if (!BT_DoubleDelete)
2050       BT_DoubleDelete.reset(new BugType(CheckNames[CK_NewDeleteChecker],
2051                                         "Double delete",
2052                                         categories::MemoryError));
2053
2054     auto R = llvm::make_unique<BugReport>(
2055         *BT_DoubleDelete, "Attempt to delete released memory", N);
2056
2057     R->markInteresting(Sym);
2058     R->addVisitor(llvm::make_unique<MallocBugVisitor>(Sym));
2059     C.emitReport(std::move(R));
2060   }
2061 }
2062
2063 void MallocChecker::ReportUseZeroAllocated(CheckerContext &C,
2064                                            SourceRange Range,
2065                                            SymbolRef Sym) const {
2066
2067   if (!ChecksEnabled[CK_MallocChecker] &&
2068       !ChecksEnabled[CK_NewDeleteChecker])
2069     return;
2070
2071   Optional<MallocChecker::CheckKind> CheckKind = getCheckIfTracked(C, Sym);
2072
2073   if (!CheckKind.hasValue())
2074     return;
2075
2076   if (ExplodedNode *N = C.generateErrorNode()) {
2077     if (!BT_UseZerroAllocated[*CheckKind])
2078       BT_UseZerroAllocated[*CheckKind].reset(
2079           new BugType(CheckNames[*CheckKind], "Use of zero allocated",
2080                       categories::MemoryError));
2081
2082     auto R = llvm::make_unique<BugReport>(*BT_UseZerroAllocated[*CheckKind],
2083                                          "Use of zero-allocated memory", N);
2084
2085     R->addRange(Range);
2086     if (Sym) {
2087       R->markInteresting(Sym);
2088       R->addVisitor(llvm::make_unique<MallocBugVisitor>(Sym));
2089     }
2090     C.emitReport(std::move(R));
2091   }
2092 }
2093
2094 void MallocChecker::ReportFunctionPointerFree(CheckerContext &C, SVal ArgVal,
2095                                               SourceRange Range,
2096                                               const Expr *FreeExpr) const {
2097   if (!ChecksEnabled[CK_MallocChecker])
2098     return;
2099
2100   Optional<MallocChecker::CheckKind> CheckKind = getCheckIfTracked(C, FreeExpr);
2101   if (!CheckKind.hasValue())
2102     return;
2103
2104   if (ExplodedNode *N = C.generateErrorNode()) {
2105     if (!BT_BadFree[*CheckKind])
2106       BT_BadFree[*CheckKind].reset(new BugType(
2107           CheckNames[*CheckKind], "Bad free", categories::MemoryError));
2108
2109     SmallString<100> Buf;
2110     llvm::raw_svector_ostream Os(Buf);
2111
2112     const MemRegion *MR = ArgVal.getAsRegion();
2113     while (const ElementRegion *ER = dyn_cast_or_null<ElementRegion>(MR))
2114       MR = ER->getSuperRegion();
2115
2116     Os << "Argument to ";
2117     if (!printAllocDeallocName(Os, C, FreeExpr))
2118       Os << "deallocator";
2119
2120     Os << " is a function pointer";
2121
2122     auto R = llvm::make_unique<BugReport>(*BT_BadFree[*CheckKind], Os.str(), N);
2123     R->markInteresting(MR);
2124     R->addRange(Range);
2125     C.emitReport(std::move(R));
2126   }
2127 }
2128
2129 ProgramStateRef MallocChecker::ReallocMemAux(CheckerContext &C,
2130                                              const CallExpr *CE,
2131                                              bool FreesOnFail,
2132                                              ProgramStateRef State,
2133                                              bool SuffixWithN) const {
2134   if (!State)
2135     return nullptr;
2136
2137   if (SuffixWithN && CE->getNumArgs() < 3)
2138     return nullptr;
2139   else if (CE->getNumArgs() < 2)
2140     return nullptr;
2141
2142   const Expr *arg0Expr = CE->getArg(0);
2143   SVal Arg0Val = C.getSVal(arg0Expr);
2144   if (!Arg0Val.getAs<DefinedOrUnknownSVal>())
2145     return nullptr;
2146   DefinedOrUnknownSVal arg0Val = Arg0Val.castAs<DefinedOrUnknownSVal>();
2147
2148   SValBuilder &svalBuilder = C.getSValBuilder();
2149
2150   DefinedOrUnknownSVal PtrEQ =
2151     svalBuilder.evalEQ(State, arg0Val, svalBuilder.makeNull());
2152
2153   // Get the size argument.
2154   const Expr *Arg1 = CE->getArg(1);
2155
2156   // Get the value of the size argument.
2157   SVal TotalSize = C.getSVal(Arg1);
2158   if (SuffixWithN)
2159     TotalSize = evalMulForBufferSize(C, Arg1, CE->getArg(2));
2160   if (!TotalSize.getAs<DefinedOrUnknownSVal>())
2161     return nullptr;
2162
2163   // Compare the size argument to 0.
2164   DefinedOrUnknownSVal SizeZero =
2165     svalBuilder.evalEQ(State, TotalSize.castAs<DefinedOrUnknownSVal>(),
2166                        svalBuilder.makeIntValWithPtrWidth(0, false));
2167
2168   ProgramStateRef StatePtrIsNull, StatePtrNotNull;
2169   std::tie(StatePtrIsNull, StatePtrNotNull) = State->assume(PtrEQ);
2170   ProgramStateRef StateSizeIsZero, StateSizeNotZero;
2171   std::tie(StateSizeIsZero, StateSizeNotZero) = State->assume(SizeZero);
2172   // We only assume exceptional states if they are definitely true; if the
2173   // state is under-constrained, assume regular realloc behavior.
2174   bool PrtIsNull = StatePtrIsNull && !StatePtrNotNull;
2175   bool SizeIsZero = StateSizeIsZero && !StateSizeNotZero;
2176
2177   // If the ptr is NULL and the size is not 0, the call is equivalent to
2178   // malloc(size).
2179   if (PrtIsNull && !SizeIsZero) {
2180     ProgramStateRef stateMalloc = MallocMemAux(C, CE, TotalSize,
2181                                                UndefinedVal(), StatePtrIsNull);
2182     return stateMalloc;
2183   }
2184
2185   if (PrtIsNull && SizeIsZero)
2186     return State;
2187
2188   // Get the from and to pointer symbols as in toPtr = realloc(fromPtr, size).
2189   assert(!PrtIsNull);
2190   SymbolRef FromPtr = arg0Val.getAsSymbol();
2191   SVal RetVal = C.getSVal(CE);
2192   SymbolRef ToPtr = RetVal.getAsSymbol();
2193   if (!FromPtr || !ToPtr)
2194     return nullptr;
2195
2196   bool ReleasedAllocated = false;
2197
2198   // If the size is 0, free the memory.
2199   if (SizeIsZero)
2200     if (ProgramStateRef stateFree = FreeMemAux(C, CE, StateSizeIsZero, 0,
2201                                                false, ReleasedAllocated)){
2202       // The semantics of the return value are:
2203       // If size was equal to 0, either NULL or a pointer suitable to be passed
2204       // to free() is returned. We just free the input pointer and do not add
2205       // any constrains on the output pointer.
2206       return stateFree;
2207     }
2208
2209   // Default behavior.
2210   if (ProgramStateRef stateFree =
2211         FreeMemAux(C, CE, State, 0, false, ReleasedAllocated)) {
2212
2213     ProgramStateRef stateRealloc = MallocMemAux(C, CE, TotalSize,
2214                                                 UnknownVal(), stateFree);
2215     if (!stateRealloc)
2216       return nullptr;
2217
2218     ReallocPairKind Kind = RPToBeFreedAfterFailure;
2219     if (FreesOnFail)
2220       Kind = RPIsFreeOnFailure;
2221     else if (!ReleasedAllocated)
2222       Kind = RPDoNotTrackAfterFailure;
2223
2224     // Record the info about the reallocated symbol so that we could properly
2225     // process failed reallocation.
2226     stateRealloc = stateRealloc->set<ReallocPairs>(ToPtr,
2227                                                    ReallocPair(FromPtr, Kind));
2228     // The reallocated symbol should stay alive for as long as the new symbol.
2229     C.getSymbolManager().addSymbolDependency(ToPtr, FromPtr);
2230     return stateRealloc;
2231   }
2232   return nullptr;
2233 }
2234
2235 ProgramStateRef MallocChecker::CallocMem(CheckerContext &C, const CallExpr *CE,
2236                                          ProgramStateRef State) {
2237   if (!State)
2238     return nullptr;
2239
2240   if (CE->getNumArgs() < 2)
2241     return nullptr;
2242
2243   SValBuilder &svalBuilder = C.getSValBuilder();
2244   SVal zeroVal = svalBuilder.makeZeroVal(svalBuilder.getContext().CharTy);
2245   SVal TotalSize = evalMulForBufferSize(C, CE->getArg(0), CE->getArg(1));
2246
2247   return MallocMemAux(C, CE, TotalSize, zeroVal, State);
2248 }
2249
2250 LeakInfo
2251 MallocChecker::getAllocationSite(const ExplodedNode *N, SymbolRef Sym,
2252                                  CheckerContext &C) const {
2253   const LocationContext *LeakContext = N->getLocationContext();
2254   // Walk the ExplodedGraph backwards and find the first node that referred to
2255   // the tracked symbol.
2256   const ExplodedNode *AllocNode = N;
2257   const MemRegion *ReferenceRegion = nullptr;
2258
2259   while (N) {
2260     ProgramStateRef State = N->getState();
2261     if (!State->get<RegionState>(Sym))
2262       break;
2263
2264     // Find the most recent expression bound to the symbol in the current
2265     // context.
2266       if (!ReferenceRegion) {
2267         if (const MemRegion *MR = C.getLocationRegionIfPostStore(N)) {
2268           SVal Val = State->getSVal(MR);
2269           if (Val.getAsLocSymbol() == Sym) {
2270             const VarRegion* VR = MR->getBaseRegion()->getAs<VarRegion>();
2271             // Do not show local variables belonging to a function other than
2272             // where the error is reported.
2273             if (!VR ||
2274                 (VR->getStackFrame() == LeakContext->getStackFrame()))
2275               ReferenceRegion = MR;
2276           }
2277         }
2278       }
2279
2280     // Allocation node, is the last node in the current or parent context in
2281     // which the symbol was tracked.
2282     const LocationContext *NContext = N->getLocationContext();
2283     if (NContext == LeakContext ||
2284         NContext->isParentOf(LeakContext))
2285       AllocNode = N;
2286     N = N->pred_empty() ? nullptr : *(N->pred_begin());
2287   }
2288
2289   return LeakInfo(AllocNode, ReferenceRegion);
2290 }
2291
2292 void MallocChecker::reportLeak(SymbolRef Sym, ExplodedNode *N,
2293                                CheckerContext &C) const {
2294
2295   if (!ChecksEnabled[CK_MallocChecker] &&
2296       !ChecksEnabled[CK_NewDeleteLeaksChecker])
2297     return;
2298
2299   const RefState *RS = C.getState()->get<RegionState>(Sym);
2300   assert(RS && "cannot leak an untracked symbol");
2301   AllocationFamily Family = RS->getAllocationFamily();
2302
2303   if (Family == AF_Alloca)
2304     return;
2305
2306   Optional<MallocChecker::CheckKind>
2307       CheckKind = getCheckIfTracked(Family, true);
2308
2309   if (!CheckKind.hasValue())
2310     return;
2311
2312   assert(N);
2313   if (!BT_Leak[*CheckKind]) {
2314     // Leaks should not be reported if they are post-dominated by a sink:
2315     // (1) Sinks are higher importance bugs.
2316     // (2) NoReturnFunctionChecker uses sink nodes to represent paths ending
2317     //     with __noreturn functions such as assert() or exit(). We choose not
2318     //     to report leaks on such paths.
2319     BT_Leak[*CheckKind].reset(new BugType(CheckNames[*CheckKind], "Memory leak",
2320                                           categories::MemoryError,
2321                                           /*SuppressOnSink=*/true));
2322   }
2323
2324   // Most bug reports are cached at the location where they occurred.
2325   // With leaks, we want to unique them by the location where they were
2326   // allocated, and only report a single path.
2327   PathDiagnosticLocation LocUsedForUniqueing;
2328   const ExplodedNode *AllocNode = nullptr;
2329   const MemRegion *Region = nullptr;
2330   std::tie(AllocNode, Region) = getAllocationSite(N, Sym, C);
2331
2332   const Stmt *AllocationStmt = PathDiagnosticLocation::getStmt(AllocNode);
2333   if (AllocationStmt)
2334     LocUsedForUniqueing = PathDiagnosticLocation::createBegin(AllocationStmt,
2335                                               C.getSourceManager(),
2336                                               AllocNode->getLocationContext());
2337
2338   SmallString<200> buf;
2339   llvm::raw_svector_ostream os(buf);
2340   if (Region && Region->canPrintPretty()) {
2341     os << "Potential leak of memory pointed to by ";
2342     Region->printPretty(os);
2343   } else {
2344     os << "Potential memory leak";
2345   }
2346
2347   auto R = llvm::make_unique<BugReport>(
2348       *BT_Leak[*CheckKind], os.str(), N, LocUsedForUniqueing,
2349       AllocNode->getLocationContext()->getDecl());
2350   R->markInteresting(Sym);
2351   R->addVisitor(llvm::make_unique<MallocBugVisitor>(Sym, true));
2352   C.emitReport(std::move(R));
2353 }
2354
2355 void MallocChecker::checkDeadSymbols(SymbolReaper &SymReaper,
2356                                      CheckerContext &C) const
2357 {
2358   ProgramStateRef state = C.getState();
2359   RegionStateTy OldRS = state->get<RegionState>();
2360   RegionStateTy::Factory &F = state->get_context<RegionState>();
2361
2362   RegionStateTy RS = OldRS;
2363   SmallVector<SymbolRef, 2> Errors;
2364   for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
2365     if (SymReaper.isDead(I->first)) {
2366       if (I->second.isAllocated() || I->second.isAllocatedOfSizeZero())
2367         Errors.push_back(I->first);
2368       // Remove the dead symbol from the map.
2369       RS = F.remove(RS, I->first);
2370     }
2371   }
2372
2373   if (RS == OldRS) {
2374     // We shouldn't have touched other maps yet.
2375     assert(state->get<ReallocPairs>() ==
2376            C.getState()->get<ReallocPairs>());
2377     assert(state->get<FreeReturnValue>() ==
2378            C.getState()->get<FreeReturnValue>());
2379     return;
2380   }
2381
2382   // Cleanup the Realloc Pairs Map.
2383   ReallocPairsTy RP = state->get<ReallocPairs>();
2384   for (ReallocPairsTy::iterator I = RP.begin(), E = RP.end(); I != E; ++I) {
2385     if (SymReaper.isDead(I->first) ||
2386         SymReaper.isDead(I->second.ReallocatedSym)) {
2387       state = state->remove<ReallocPairs>(I->first);
2388     }
2389   }
2390
2391   // Cleanup the FreeReturnValue Map.
2392   FreeReturnValueTy FR = state->get<FreeReturnValue>();
2393   for (FreeReturnValueTy::iterator I = FR.begin(), E = FR.end(); I != E; ++I) {
2394     if (SymReaper.isDead(I->first) ||
2395         SymReaper.isDead(I->second)) {
2396       state = state->remove<FreeReturnValue>(I->first);
2397     }
2398   }
2399
2400   // Generate leak node.
2401   ExplodedNode *N = C.getPredecessor();
2402   if (!Errors.empty()) {
2403     static CheckerProgramPointTag Tag("MallocChecker", "DeadSymbolsLeak");
2404     N = C.generateNonFatalErrorNode(C.getState(), &Tag);
2405     if (N) {
2406       for (SmallVectorImpl<SymbolRef>::iterator
2407            I = Errors.begin(), E = Errors.end(); I != E; ++I) {
2408         reportLeak(*I, N, C);
2409       }
2410     }
2411   }
2412
2413   C.addTransition(state->set<RegionState>(RS), N);
2414 }
2415
2416 void MallocChecker::checkPreCall(const CallEvent &Call,
2417                                  CheckerContext &C) const {
2418
2419   if (const CXXDestructorCall *DC = dyn_cast<CXXDestructorCall>(&Call)) {
2420     SymbolRef Sym = DC->getCXXThisVal().getAsSymbol();
2421     if (!Sym || checkDoubleDelete(Sym, C))
2422       return;
2423   }
2424
2425   // We will check for double free in the post visit.
2426   if (const AnyFunctionCall *FC = dyn_cast<AnyFunctionCall>(&Call)) {
2427     const FunctionDecl *FD = FC->getDecl();
2428     if (!FD)
2429       return;
2430
2431     ASTContext &Ctx = C.getASTContext();
2432     if (ChecksEnabled[CK_MallocChecker] &&
2433         (isCMemFunction(FD, Ctx, AF_Malloc, MemoryOperationKind::MOK_Free) ||
2434          isCMemFunction(FD, Ctx, AF_IfNameIndex,
2435                         MemoryOperationKind::MOK_Free)))
2436       return;
2437   }
2438
2439   // Check if the callee of a method is deleted.
2440   if (const CXXInstanceCall *CC = dyn_cast<CXXInstanceCall>(&Call)) {
2441     SymbolRef Sym = CC->getCXXThisVal().getAsSymbol();
2442     if (!Sym || checkUseAfterFree(Sym, C, CC->getCXXThisExpr()))
2443       return;
2444   }
2445
2446   // Check arguments for being used after free.
2447   for (unsigned I = 0, E = Call.getNumArgs(); I != E; ++I) {
2448     SVal ArgSVal = Call.getArgSVal(I);
2449     if (ArgSVal.getAs<Loc>()) {
2450       SymbolRef Sym = ArgSVal.getAsSymbol();
2451       if (!Sym)
2452         continue;
2453       if (checkUseAfterFree(Sym, C, Call.getArgExpr(I)))
2454         return;
2455     }
2456   }
2457 }
2458
2459 void MallocChecker::checkPreStmt(const ReturnStmt *S,
2460                                  CheckerContext &C) const {
2461   checkEscapeOnReturn(S, C);
2462 }
2463
2464 // In the CFG, automatic destructors come after the return statement.
2465 // This callback checks for returning memory that is freed by automatic
2466 // destructors, as those cannot be reached in checkPreStmt().
2467 void MallocChecker::checkEndFunction(const ReturnStmt *S,
2468                                      CheckerContext &C) const {
2469   checkEscapeOnReturn(S, C);
2470 }
2471
2472 void MallocChecker::checkEscapeOnReturn(const ReturnStmt *S,
2473                                         CheckerContext &C) const {
2474   if (!S)
2475     return;
2476
2477   const Expr *E = S->getRetValue();
2478   if (!E)
2479     return;
2480
2481   // Check if we are returning a symbol.
2482   ProgramStateRef State = C.getState();
2483   SVal RetVal = C.getSVal(E);
2484   SymbolRef Sym = RetVal.getAsSymbol();
2485   if (!Sym)
2486     // If we are returning a field of the allocated struct or an array element,
2487     // the callee could still free the memory.
2488     // TODO: This logic should be a part of generic symbol escape callback.
2489     if (const MemRegion *MR = RetVal.getAsRegion())
2490       if (isa<FieldRegion>(MR) || isa<ElementRegion>(MR))
2491         if (const SymbolicRegion *BMR =
2492               dyn_cast<SymbolicRegion>(MR->getBaseRegion()))
2493           Sym = BMR->getSymbol();
2494
2495   // Check if we are returning freed memory.
2496   if (Sym)
2497     checkUseAfterFree(Sym, C, E);
2498 }
2499
2500 // TODO: Blocks should be either inlined or should call invalidate regions
2501 // upon invocation. After that's in place, special casing here will not be
2502 // needed.
2503 void MallocChecker::checkPostStmt(const BlockExpr *BE,
2504                                   CheckerContext &C) const {
2505
2506   // Scan the BlockDecRefExprs for any object the retain count checker
2507   // may be tracking.
2508   if (!BE->getBlockDecl()->hasCaptures())
2509     return;
2510
2511   ProgramStateRef state = C.getState();
2512   const BlockDataRegion *R =
2513     cast<BlockDataRegion>(C.getSVal(BE).getAsRegion());
2514
2515   BlockDataRegion::referenced_vars_iterator I = R->referenced_vars_begin(),
2516                                             E = R->referenced_vars_end();
2517
2518   if (I == E)
2519     return;
2520
2521   SmallVector<const MemRegion*, 10> Regions;
2522   const LocationContext *LC = C.getLocationContext();
2523   MemRegionManager &MemMgr = C.getSValBuilder().getRegionManager();
2524
2525   for ( ; I != E; ++I) {
2526     const VarRegion *VR = I.getCapturedRegion();
2527     if (VR->getSuperRegion() == R) {
2528       VR = MemMgr.getVarRegion(VR->getDecl(), LC);
2529     }
2530     Regions.push_back(VR);
2531   }
2532
2533   state =
2534     state->scanReachableSymbols<StopTrackingCallback>(Regions).getState();
2535   C.addTransition(state);
2536 }
2537
2538 bool MallocChecker::isReleased(SymbolRef Sym, CheckerContext &C) const {
2539   assert(Sym);
2540   const RefState *RS = C.getState()->get<RegionState>(Sym);
2541   return (RS && RS->isReleased());
2542 }
2543
2544 bool MallocChecker::suppressDeallocationsInSuspiciousContexts(
2545     const CallExpr *CE, CheckerContext &C) const {
2546   if (CE->getNumArgs() == 0)
2547     return false;
2548
2549   StringRef FunctionStr = "";
2550   if (const auto *FD = dyn_cast<FunctionDecl>(C.getStackFrame()->getDecl()))
2551     if (const Stmt *Body = FD->getBody())
2552       if (Body->getBeginLoc().isValid())
2553         FunctionStr =
2554             Lexer::getSourceText(CharSourceRange::getTokenRange(
2555                                      {FD->getBeginLoc(), Body->getBeginLoc()}),
2556                                  C.getSourceManager(), C.getLangOpts());
2557
2558   // We do not model the Integer Set Library's retain-count based allocation.
2559   if (!FunctionStr.contains("__isl_"))
2560     return false;
2561
2562   ProgramStateRef State = C.getState();
2563
2564   for (const Expr *Arg : CE->arguments())
2565     if (SymbolRef Sym = C.getSVal(Arg).getAsSymbol())
2566       if (const RefState *RS = State->get<RegionState>(Sym))
2567         State = State->set<RegionState>(Sym, RefState::getEscaped(RS));
2568
2569   C.addTransition(State);
2570   return true;
2571 }
2572
2573 bool MallocChecker::checkUseAfterFree(SymbolRef Sym, CheckerContext &C,
2574                                       const Stmt *S) const {
2575
2576   if (isReleased(Sym, C)) {
2577     ReportUseAfterFree(C, S->getSourceRange(), Sym);
2578     return true;
2579   }
2580
2581   return false;
2582 }
2583
2584 void MallocChecker::checkUseZeroAllocated(SymbolRef Sym, CheckerContext &C,
2585                                           const Stmt *S) const {
2586   assert(Sym);
2587
2588   if (const RefState *RS = C.getState()->get<RegionState>(Sym)) {
2589     if (RS->isAllocatedOfSizeZero())
2590       ReportUseZeroAllocated(C, RS->getStmt()->getSourceRange(), Sym);
2591   }
2592   else if (C.getState()->contains<ReallocSizeZeroSymbols>(Sym)) {
2593     ReportUseZeroAllocated(C, S->getSourceRange(), Sym);
2594   }
2595 }
2596
2597 bool MallocChecker::checkDoubleDelete(SymbolRef Sym, CheckerContext &C) const {
2598
2599   if (isReleased(Sym, C)) {
2600     ReportDoubleDelete(C, Sym);
2601     return true;
2602   }
2603   return false;
2604 }
2605
2606 // Check if the location is a freed symbolic region.
2607 void MallocChecker::checkLocation(SVal l, bool isLoad, const Stmt *S,
2608                                   CheckerContext &C) const {
2609   SymbolRef Sym = l.getLocSymbolInBase();
2610   if (Sym) {
2611     checkUseAfterFree(Sym, C, S);
2612     checkUseZeroAllocated(Sym, C, S);
2613   }
2614 }
2615
2616 // If a symbolic region is assumed to NULL (or another constant), stop tracking
2617 // it - assuming that allocation failed on this path.
2618 ProgramStateRef MallocChecker::evalAssume(ProgramStateRef state,
2619                                               SVal Cond,
2620                                               bool Assumption) const {
2621   RegionStateTy RS = state->get<RegionState>();
2622   for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
2623     // If the symbol is assumed to be NULL, remove it from consideration.
2624     ConstraintManager &CMgr = state->getConstraintManager();
2625     ConditionTruthVal AllocFailed = CMgr.isNull(state, I.getKey());
2626     if (AllocFailed.isConstrainedTrue())
2627       state = state->remove<RegionState>(I.getKey());
2628   }
2629
2630   // Realloc returns 0 when reallocation fails, which means that we should
2631   // restore the state of the pointer being reallocated.
2632   ReallocPairsTy RP = state->get<ReallocPairs>();
2633   for (ReallocPairsTy::iterator I = RP.begin(), E = RP.end(); I != E; ++I) {
2634     // If the symbol is assumed to be NULL, remove it from consideration.
2635     ConstraintManager &CMgr = state->getConstraintManager();
2636     ConditionTruthVal AllocFailed = CMgr.isNull(state, I.getKey());
2637     if (!AllocFailed.isConstrainedTrue())
2638       continue;
2639
2640     SymbolRef ReallocSym = I.getData().ReallocatedSym;
2641     if (const RefState *RS = state->get<RegionState>(ReallocSym)) {
2642       if (RS->isReleased()) {
2643         if (I.getData().Kind == RPToBeFreedAfterFailure)
2644           state = state->set<RegionState>(ReallocSym,
2645               RefState::getAllocated(RS->getAllocationFamily(), RS->getStmt()));
2646         else if (I.getData().Kind == RPDoNotTrackAfterFailure)
2647           state = state->remove<RegionState>(ReallocSym);
2648         else
2649           assert(I.getData().Kind == RPIsFreeOnFailure);
2650       }
2651     }
2652     state = state->remove<ReallocPairs>(I.getKey());
2653   }
2654
2655   return state;
2656 }
2657
2658 bool MallocChecker::mayFreeAnyEscapedMemoryOrIsModeledExplicitly(
2659                                               const CallEvent *Call,
2660                                               ProgramStateRef State,
2661                                               SymbolRef &EscapingSymbol) const {
2662   assert(Call);
2663   EscapingSymbol = nullptr;
2664
2665   // For now, assume that any C++ or block call can free memory.
2666   // TODO: If we want to be more optimistic here, we'll need to make sure that
2667   // regions escape to C++ containers. They seem to do that even now, but for
2668   // mysterious reasons.
2669   if (!(isa<SimpleFunctionCall>(Call) || isa<ObjCMethodCall>(Call)))
2670     return true;
2671
2672   // Check Objective-C messages by selector name.
2673   if (const ObjCMethodCall *Msg = dyn_cast<ObjCMethodCall>(Call)) {
2674     // If it's not a framework call, or if it takes a callback, assume it
2675     // can free memory.
2676     if (!Call->isInSystemHeader() || Call->argumentsMayEscape())
2677       return true;
2678
2679     // If it's a method we know about, handle it explicitly post-call.
2680     // This should happen before the "freeWhenDone" check below.
2681     if (isKnownDeallocObjCMethodName(*Msg))
2682       return false;
2683
2684     // If there's a "freeWhenDone" parameter, but the method isn't one we know
2685     // about, we can't be sure that the object will use free() to deallocate the
2686     // memory, so we can't model it explicitly. The best we can do is use it to
2687     // decide whether the pointer escapes.
2688     if (Optional<bool> FreeWhenDone = getFreeWhenDoneArg(*Msg))
2689       return *FreeWhenDone;
2690
2691     // If the first selector piece ends with "NoCopy", and there is no
2692     // "freeWhenDone" parameter set to zero, we know ownership is being
2693     // transferred. Again, though, we can't be sure that the object will use
2694     // free() to deallocate the memory, so we can't model it explicitly.
2695     StringRef FirstSlot = Msg->getSelector().getNameForSlot(0);
2696     if (FirstSlot.endswith("NoCopy"))
2697       return true;
2698
2699     // If the first selector starts with addPointer, insertPointer,
2700     // or replacePointer, assume we are dealing with NSPointerArray or similar.
2701     // This is similar to C++ containers (vector); we still might want to check
2702     // that the pointers get freed by following the container itself.
2703     if (FirstSlot.startswith("addPointer") ||
2704         FirstSlot.startswith("insertPointer") ||
2705         FirstSlot.startswith("replacePointer") ||
2706         FirstSlot.equals("valueWithPointer")) {
2707       return true;
2708     }
2709
2710     // We should escape receiver on call to 'init'. This is especially relevant
2711     // to the receiver, as the corresponding symbol is usually not referenced
2712     // after the call.
2713     if (Msg->getMethodFamily() == OMF_init) {
2714       EscapingSymbol = Msg->getReceiverSVal().getAsSymbol();
2715       return true;
2716     }
2717
2718     // Otherwise, assume that the method does not free memory.
2719     // Most framework methods do not free memory.
2720     return false;
2721   }
2722
2723   // At this point the only thing left to handle is straight function calls.
2724   const FunctionDecl *FD = cast<SimpleFunctionCall>(Call)->getDecl();
2725   if (!FD)
2726     return true;
2727
2728   ASTContext &ASTC = State->getStateManager().getContext();
2729
2730   // If it's one of the allocation functions we can reason about, we model
2731   // its behavior explicitly.
2732   if (isMemFunction(FD, ASTC))
2733     return false;
2734
2735   // If it's not a system call, assume it frees memory.
2736   if (!Call->isInSystemHeader())
2737     return true;
2738
2739   // White list the system functions whose arguments escape.
2740   const IdentifierInfo *II = FD->getIdentifier();
2741   if (!II)
2742     return true;
2743   StringRef FName = II->getName();
2744
2745   // White list the 'XXXNoCopy' CoreFoundation functions.
2746   // We specifically check these before
2747   if (FName.endswith("NoCopy")) {
2748     // Look for the deallocator argument. We know that the memory ownership
2749     // is not transferred only if the deallocator argument is
2750     // 'kCFAllocatorNull'.
2751     for (unsigned i = 1; i < Call->getNumArgs(); ++i) {
2752       const Expr *ArgE = Call->getArgExpr(i)->IgnoreParenCasts();
2753       if (const DeclRefExpr *DE = dyn_cast<DeclRefExpr>(ArgE)) {
2754         StringRef DeallocatorName = DE->getFoundDecl()->getName();
2755         if (DeallocatorName == "kCFAllocatorNull")
2756           return false;
2757       }
2758     }
2759     return true;
2760   }
2761
2762   // Associating streams with malloced buffers. The pointer can escape if
2763   // 'closefn' is specified (and if that function does free memory),
2764   // but it will not if closefn is not specified.
2765   // Currently, we do not inspect the 'closefn' function (PR12101).
2766   if (FName == "funopen")
2767     if (Call->getNumArgs() >= 4 && Call->getArgSVal(4).isConstant(0))
2768       return false;
2769
2770   // Do not warn on pointers passed to 'setbuf' when used with std streams,
2771   // these leaks might be intentional when setting the buffer for stdio.
2772   // http://stackoverflow.com/questions/2671151/who-frees-setvbuf-buffer
2773   if (FName == "setbuf" || FName =="setbuffer" ||
2774       FName == "setlinebuf" || FName == "setvbuf") {
2775     if (Call->getNumArgs() >= 1) {
2776       const Expr *ArgE = Call->getArgExpr(0)->IgnoreParenCasts();
2777       if (const DeclRefExpr *ArgDRE = dyn_cast<DeclRefExpr>(ArgE))
2778         if (const VarDecl *D = dyn_cast<VarDecl>(ArgDRE->getDecl()))
2779           if (D->getCanonicalDecl()->getName().find("std") != StringRef::npos)
2780             return true;
2781     }
2782   }
2783
2784   // A bunch of other functions which either take ownership of a pointer or
2785   // wrap the result up in a struct or object, meaning it can be freed later.
2786   // (See RetainCountChecker.) Not all the parameters here are invalidated,
2787   // but the Malloc checker cannot differentiate between them. The right way
2788   // of doing this would be to implement a pointer escapes callback.
2789   if (FName == "CGBitmapContextCreate" ||
2790       FName == "CGBitmapContextCreateWithData" ||
2791       FName == "CVPixelBufferCreateWithBytes" ||
2792       FName == "CVPixelBufferCreateWithPlanarBytes" ||
2793       FName == "OSAtomicEnqueue") {
2794     return true;
2795   }
2796
2797   if (FName == "postEvent" &&
2798       FD->getQualifiedNameAsString() == "QCoreApplication::postEvent") {
2799     return true;
2800   }
2801
2802   if (FName == "postEvent" &&
2803       FD->getQualifiedNameAsString() == "QCoreApplication::postEvent") {
2804     return true;
2805   }
2806
2807   if (FName == "connectImpl" &&
2808       FD->getQualifiedNameAsString() == "QObject::connectImpl") {
2809     return true;
2810   }
2811
2812   // Handle cases where we know a buffer's /address/ can escape.
2813   // Note that the above checks handle some special cases where we know that
2814   // even though the address escapes, it's still our responsibility to free the
2815   // buffer.
2816   if (Call->argumentsMayEscape())
2817     return true;
2818
2819   // Otherwise, assume that the function does not free memory.
2820   // Most system calls do not free the memory.
2821   return false;
2822 }
2823
2824 static bool retTrue(const RefState *RS) {
2825   return true;
2826 }
2827
2828 static bool checkIfNewOrNewArrayFamily(const RefState *RS) {
2829   return (RS->getAllocationFamily() == AF_CXXNewArray ||
2830           RS->getAllocationFamily() == AF_CXXNew);
2831 }
2832
2833 ProgramStateRef MallocChecker::checkPointerEscape(ProgramStateRef State,
2834                                              const InvalidatedSymbols &Escaped,
2835                                              const CallEvent *Call,
2836                                              PointerEscapeKind Kind) const {
2837   return checkPointerEscapeAux(State, Escaped, Call, Kind, &retTrue);
2838 }
2839
2840 ProgramStateRef MallocChecker::checkConstPointerEscape(ProgramStateRef State,
2841                                               const InvalidatedSymbols &Escaped,
2842                                               const CallEvent *Call,
2843                                               PointerEscapeKind Kind) const {
2844   return checkPointerEscapeAux(State, Escaped, Call, Kind,
2845                                &checkIfNewOrNewArrayFamily);
2846 }
2847
2848 ProgramStateRef MallocChecker::checkPointerEscapeAux(ProgramStateRef State,
2849                                               const InvalidatedSymbols &Escaped,
2850                                               const CallEvent *Call,
2851                                               PointerEscapeKind Kind,
2852                                   bool(*CheckRefState)(const RefState*)) const {
2853   // If we know that the call does not free memory, or we want to process the
2854   // call later, keep tracking the top level arguments.
2855   SymbolRef EscapingSymbol = nullptr;
2856   if (Kind == PSK_DirectEscapeOnCall &&
2857       !mayFreeAnyEscapedMemoryOrIsModeledExplicitly(Call, State,
2858                                                     EscapingSymbol) &&
2859       !EscapingSymbol) {
2860     return State;
2861   }
2862
2863   for (InvalidatedSymbols::const_iterator I = Escaped.begin(),
2864        E = Escaped.end();
2865        I != E; ++I) {
2866     SymbolRef sym = *I;
2867
2868     if (EscapingSymbol && EscapingSymbol != sym)
2869       continue;
2870
2871     if (const RefState *RS = State->get<RegionState>(sym)) {
2872       if ((RS->isAllocated() || RS->isAllocatedOfSizeZero()) &&
2873           CheckRefState(RS)) {
2874         State = State->set<RegionState>(sym, RefState::getEscaped(RS));
2875       }
2876     }
2877   }
2878   return State;
2879 }
2880
2881 static SymbolRef findFailedReallocSymbol(ProgramStateRef currState,
2882                                          ProgramStateRef prevState) {
2883   ReallocPairsTy currMap = currState->get<ReallocPairs>();
2884   ReallocPairsTy prevMap = prevState->get<ReallocPairs>();
2885
2886   for (ReallocPairsTy::iterator I = prevMap.begin(), E = prevMap.end();
2887        I != E; ++I) {
2888     SymbolRef sym = I.getKey();
2889     if (!currMap.lookup(sym))
2890       return sym;
2891   }
2892
2893   return nullptr;
2894 }
2895
2896 static bool isReferenceCountingPointerDestructor(const CXXDestructorDecl *DD) {
2897   if (const IdentifierInfo *II = DD->getParent()->getIdentifier()) {
2898     StringRef N = II->getName();
2899     if (N.contains_lower("ptr") || N.contains_lower("pointer")) {
2900       if (N.contains_lower("ref") || N.contains_lower("cnt") ||
2901           N.contains_lower("intrusive") || N.contains_lower("shared")) {
2902         return true;
2903       }
2904     }
2905   }
2906   return false;
2907 }
2908
2909 std::shared_ptr<PathDiagnosticPiece> MallocChecker::MallocBugVisitor::VisitNode(
2910     const ExplodedNode *N, BugReporterContext &BRC, BugReport &BR) {
2911
2912   ProgramStateRef state = N->getState();
2913   ProgramStateRef statePrev = N->getFirstPred()->getState();
2914
2915   const RefState *RS = state->get<RegionState>(Sym);
2916   const RefState *RSPrev = statePrev->get<RegionState>(Sym);
2917
2918   const Stmt *S = PathDiagnosticLocation::getStmt(N);
2919   // When dealing with containers, we sometimes want to give a note
2920   // even if the statement is missing.
2921   if (!S && (!RS || RS->getAllocationFamily() != AF_InnerBuffer))
2922     return nullptr;
2923
2924   const LocationContext *CurrentLC = N->getLocationContext();
2925
2926   // If we find an atomic fetch_add or fetch_sub within the destructor in which
2927   // the pointer was released (before the release), this is likely a destructor
2928   // of a shared pointer.
2929   // Because we don't model atomics, and also because we don't know that the
2930   // original reference count is positive, we should not report use-after-frees
2931   // on objects deleted in such destructors. This can probably be improved
2932   // through better shared pointer modeling.
2933   if (ReleaseDestructorLC) {
2934     if (const auto *AE = dyn_cast<AtomicExpr>(S)) {
2935       AtomicExpr::AtomicOp Op = AE->getOp();
2936       if (Op == AtomicExpr::AO__c11_atomic_fetch_add ||
2937           Op == AtomicExpr::AO__c11_atomic_fetch_sub) {
2938         if (ReleaseDestructorLC == CurrentLC ||
2939             ReleaseDestructorLC->isParentOf(CurrentLC)) {
2940           BR.markInvalid(getTag(), S);
2941         }
2942       }
2943     }
2944   }
2945
2946   // FIXME: We will eventually need to handle non-statement-based events
2947   // (__attribute__((cleanup))).
2948
2949   // Find out if this is an interesting point and what is the kind.
2950   StringRef Msg;
2951   StackHintGeneratorForSymbol *StackHint = nullptr;
2952   SmallString<256> Buf;
2953   llvm::raw_svector_ostream OS(Buf);
2954
2955   if (Mode == Normal) {
2956     if (isAllocated(RS, RSPrev, S)) {
2957       Msg = "Memory is allocated";
2958       StackHint = new StackHintGeneratorForSymbol(Sym,
2959                                                   "Returned allocated memory");
2960     } else if (isReleased(RS, RSPrev, S)) {
2961       const auto Family = RS->getAllocationFamily();
2962       switch (Family) {
2963         case AF_Alloca:
2964         case AF_Malloc:
2965         case AF_CXXNew:
2966         case AF_CXXNewArray:
2967         case AF_IfNameIndex:
2968           Msg = "Memory is released";
2969           StackHint = new StackHintGeneratorForSymbol(Sym,
2970                                               "Returning; memory was released");
2971           break;
2972         case AF_InnerBuffer: {
2973           const MemRegion *ObjRegion =
2974               allocation_state::getContainerObjRegion(statePrev, Sym);
2975           const auto *TypedRegion = cast<TypedValueRegion>(ObjRegion);
2976           QualType ObjTy = TypedRegion->getValueType();
2977           OS << "Inner buffer of '" << ObjTy.getAsString() << "' ";
2978
2979           if (N->getLocation().getKind() == ProgramPoint::PostImplicitCallKind) {
2980             OS << "deallocated by call to destructor";
2981             StackHint = new StackHintGeneratorForSymbol(Sym,
2982                                       "Returning; inner buffer was deallocated");
2983           } else {
2984             OS << "reallocated by call to '";
2985             const Stmt *S = RS->getStmt();
2986             if (const auto *MemCallE = dyn_cast<CXXMemberCallExpr>(S)) {
2987               OS << MemCallE->getMethodDecl()->getNameAsString();
2988             } else if (const auto *OpCallE = dyn_cast<CXXOperatorCallExpr>(S)) {
2989               OS << OpCallE->getDirectCallee()->getNameAsString();
2990             } else if (const auto *CallE = dyn_cast<CallExpr>(S)) {
2991               auto &CEMgr = BRC.getStateManager().getCallEventManager();
2992               CallEventRef<> Call = CEMgr.getSimpleCall(CallE, state, CurrentLC);
2993               const auto *D = dyn_cast_or_null<NamedDecl>(Call->getDecl());
2994               OS << (D ? D->getNameAsString() : "unknown");
2995             }
2996             OS << "'";
2997             StackHint = new StackHintGeneratorForSymbol(Sym,
2998                                       "Returning; inner buffer was reallocated");
2999           }
3000           Msg = OS.str();
3001           break;
3002         }
3003         case AF_None:
3004           llvm_unreachable("Unhandled allocation family!");
3005       }
3006
3007       // See if we're releasing memory while inlining a destructor
3008       // (or one of its callees). This turns on various common
3009       // false positive suppressions.
3010       bool FoundAnyDestructor = false;
3011       for (const LocationContext *LC = CurrentLC; LC; LC = LC->getParent()) {
3012         if (const auto *DD = dyn_cast<CXXDestructorDecl>(LC->getDecl())) {
3013           if (isReferenceCountingPointerDestructor(DD)) {
3014             // This immediately looks like a reference-counting destructor.
3015             // We're bad at guessing the original reference count of the object,
3016             // so suppress the report for now.
3017             BR.markInvalid(getTag(), DD);
3018           } else if (!FoundAnyDestructor) {
3019             assert(!ReleaseDestructorLC &&
3020                    "There can be only one release point!");
3021             // Suspect that it's a reference counting pointer destructor.
3022             // On one of the next nodes might find out that it has atomic
3023             // reference counting operations within it (see the code above),
3024             // and if so, we'd conclude that it likely is a reference counting
3025             // pointer destructor.
3026             ReleaseDestructorLC = LC->getStackFrame();
3027             // It is unlikely that releasing memory is delegated to a destructor
3028             // inside a destructor of a shared pointer, because it's fairly hard
3029             // to pass the information that the pointer indeed needs to be
3030             // released into it. So we're only interested in the innermost
3031             // destructor.
3032             FoundAnyDestructor = true;
3033           }
3034         }
3035       }
3036     } else if (isRelinquished(RS, RSPrev, S)) {
3037       Msg = "Memory ownership is transferred";
3038       StackHint = new StackHintGeneratorForSymbol(Sym, "");
3039     } else if (isReallocFailedCheck(RS, RSPrev, S)) {
3040       Mode = ReallocationFailed;
3041       Msg = "Reallocation failed";
3042       StackHint = new StackHintGeneratorForReallocationFailed(Sym,
3043                                                        "Reallocation failed");
3044
3045       if (SymbolRef sym = findFailedReallocSymbol(state, statePrev)) {
3046         // Is it possible to fail two reallocs WITHOUT testing in between?
3047         assert((!FailedReallocSymbol || FailedReallocSymbol == sym) &&
3048           "We only support one failed realloc at a time.");
3049         BR.markInteresting(sym);
3050         FailedReallocSymbol = sym;
3051       }
3052     }
3053
3054   // We are in a special mode if a reallocation failed later in the path.
3055   } else if (Mode == ReallocationFailed) {
3056     assert(FailedReallocSymbol && "No symbol to look for.");
3057
3058     // Is this is the first appearance of the reallocated symbol?
3059     if (!statePrev->get<RegionState>(FailedReallocSymbol)) {
3060       // We're at the reallocation point.
3061       Msg = "Attempt to reallocate memory";
3062       StackHint = new StackHintGeneratorForSymbol(Sym,
3063                                                  "Returned reallocated memory");
3064       FailedReallocSymbol = nullptr;
3065       Mode = Normal;
3066     }
3067   }
3068
3069   if (Msg.empty())
3070     return nullptr;
3071   assert(StackHint);
3072
3073   // Generate the extra diagnostic.
3074   PathDiagnosticLocation Pos;
3075   if (!S) {
3076     assert(RS->getAllocationFamily() == AF_InnerBuffer);
3077     auto PostImplCall = N->getLocation().getAs<PostImplicitCall>();
3078     if (!PostImplCall)
3079       return nullptr;
3080     Pos = PathDiagnosticLocation(PostImplCall->getLocation(),
3081                                  BRC.getSourceManager());
3082   } else {
3083     Pos = PathDiagnosticLocation(S, BRC.getSourceManager(),
3084                                  N->getLocationContext());
3085   }
3086
3087   return std::make_shared<PathDiagnosticEventPiece>(Pos, Msg, true, StackHint);
3088 }
3089
3090 void MallocChecker::printState(raw_ostream &Out, ProgramStateRef State,
3091                                const char *NL, const char *Sep) const {
3092
3093   RegionStateTy RS = State->get<RegionState>();
3094
3095   if (!RS.isEmpty()) {
3096     Out << Sep << "MallocChecker :" << NL;
3097     for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
3098       const RefState *RefS = State->get<RegionState>(I.getKey());
3099       AllocationFamily Family = RefS->getAllocationFamily();
3100       Optional<MallocChecker::CheckKind> CheckKind = getCheckIfTracked(Family);
3101       if (!CheckKind.hasValue())
3102          CheckKind = getCheckIfTracked(Family, true);
3103
3104       I.getKey()->dumpToStream(Out);
3105       Out << " : ";
3106       I.getData().dump(Out);
3107       if (CheckKind.hasValue())
3108         Out << " (" << CheckNames[*CheckKind].getName() << ")";
3109       Out << NL;
3110     }
3111   }
3112 }
3113
3114 namespace clang {
3115 namespace ento {
3116 namespace allocation_state {
3117
3118 ProgramStateRef
3119 markReleased(ProgramStateRef State, SymbolRef Sym, const Expr *Origin) {
3120   AllocationFamily Family = AF_InnerBuffer;
3121   return State->set<RegionState>(Sym, RefState::getReleased(Family, Origin));
3122 }
3123
3124 } // end namespace allocation_state
3125 } // end namespace ento
3126 } // end namespace clang
3127
3128 // Intended to be used in InnerPointerChecker to register the part of
3129 // MallocChecker connected to it.
3130 void ento::registerInnerPointerCheckerAux(CheckerManager &mgr) {
3131   MallocChecker *checker = mgr.getChecker<MallocChecker>();
3132   checker->ChecksEnabled[MallocChecker::CK_InnerPointerChecker] = true;
3133   checker->CheckNames[MallocChecker::CK_InnerPointerChecker] =
3134       mgr.getCurrentCheckName();
3135 }
3136
3137 void ento::registerDynamicMemoryModeling(CheckerManager &mgr) {
3138   auto *checker = mgr.registerChecker<MallocChecker>();
3139   checker->IsOptimistic = mgr.getAnalyzerOptions().getCheckerBooleanOption(
3140                                                          checker, "Optimistic");
3141 }
3142
3143 bool ento::shouldRegisterDynamicMemoryModeling(const LangOptions &LO) {
3144   return true;
3145 }
3146
3147 #define REGISTER_CHECKER(name)                                                 \
3148   void ento::register##name(CheckerManager &mgr) {                             \
3149     MallocChecker *checker = mgr.getChecker<MallocChecker>();                  \
3150     checker->ChecksEnabled[MallocChecker::CK_##name] = true;                   \
3151     checker->CheckNames[MallocChecker::CK_##name] = mgr.getCurrentCheckName(); \
3152   }                                                                            \
3153                                                                                \
3154   bool ento::shouldRegister##name(const LangOptions &LO) {                     \
3155     return true;                                                               \
3156   }
3157
3158 REGISTER_CHECKER(MallocChecker)
3159 REGISTER_CHECKER(NewDeleteChecker)
3160 REGISTER_CHECKER(NewDeleteLeaksChecker)
3161 REGISTER_CHECKER(MismatchedDeallocatorChecker)