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