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

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