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

   1 //=== MallocChecker.cpp - A malloc/free checker -------------------*- C++ -*--//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines malloc/free checker, which checks for potential memory
  11 // leaks, double free, and use-after-free problems.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "ClangSACheckers.h"
  16 #include "InterCheckerAPI.h"
  17 #include "clang/AST/Attr.h"
  18 #include "clang/Basic/SourceManager.h"
  19 #include "clang/Basic/TargetInfo.h"
  20 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
  21 #include "clang/StaticAnalyzer/Core/Checker.h"
  22 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
  23 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
  24 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
  25 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
  26 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
  27 #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
  28 #include "llvm/ADT/ImmutableMap.h"
  29 #include "llvm/ADT/STLExtras.h"
  30 #include "llvm/ADT/SmallString.h"
  31 #include "llvm/ADT/StringExtras.h"
  32 #include <climits>
  33
  34 using namespace clang;
  35 using namespace ento;
  36
  37 namespace {
  38
  39 // Used to check correspondence between allocators and deallocators.
  40 enum AllocationFamily {
  41   AF_None,
  42   AF_Malloc,
  43   AF_CXXNew,
  44   AF_CXXNewArray
  45 };
  46
  47 class RefState {
  48   enum Kind { // Reference to allocated memory.
  49               Allocated,
  50               // Reference to released/freed memory.
  51               Released,
  52               // The responsibility for freeing resources has transferred from
  53               // this reference. A relinquished symbol should not be freed.
  54               Relinquished,
  55               // We are no longer guaranteed to have observed all manipulations
  56               // of this pointer/memory. For example, it could have been
  57               // passed as a parameter to an opaque function.
  58               Escaped
  59   };
  60
  61   const Stmt *S;
  62   unsigned K : 2; // Kind enum, but stored as a bitfield.
  63   unsigned Family : 30; // Rest of 32-bit word, currently just an allocation
  64                         // family.
  65
  66   RefState(Kind k, const Stmt *s, unsigned family)
  67     : S(s), K(k), Family(family) {
  68     assert(family != AF_None);
  69   }
  70 public:
  71   bool isAllocated() const { return K == Allocated; }
  72   bool isReleased() const { return K == Released; }
  73   bool isRelinquished() const { return K == Relinquished; }
  74   bool isEscaped() const { return K == Escaped; }
  75   AllocationFamily getAllocationFamily() const {
  76     return (AllocationFamily)Family;
  77   }
  78   const Stmt *getStmt() const { return S; }
  79
  80   bool operator==(const RefState &X) const {
  81     return K == X.K && S == X.S && Family == X.Family;
  82   }
  83
  84   static RefState getAllocated(unsigned family, const Stmt *s) {
  85     return RefState(Allocated, s, family);
  86   }
  87   static RefState getReleased(unsigned family, const Stmt *s) {
  88     return RefState(Released, s, family);
  89   }
  90   static RefState getRelinquished(unsigned family, const Stmt *s) {
  91     return RefState(Relinquished, s, family);
  92   }
  93   static RefState getEscaped(const RefState *RS) {
  94     return RefState(Escaped, RS->getStmt(), RS->getAllocationFamily());
  95   }
  96
  97   void Profile(llvm::FoldingSetNodeID &ID) const {
  98     ID.AddInteger(K);
  99     ID.AddPointer(S);
 100     ID.AddInteger(Family);
 101   }
 102
 103   void dump(raw_ostream &OS) const {
 104     switch (static_cast<Kind>(K)) {
 105 #define CASE(ID) case ID: OS << #ID; break;
 106     CASE(Allocated)
 107     CASE(Released)
 108     CASE(Relinquished)
 109     CASE(Escaped)
 110     }
 111   }
 112
 113   LLVM_DUMP_METHOD void dump() const { dump(llvm::errs()); }
 114 };
 115
 116 enum ReallocPairKind {
 117   RPToBeFreedAfterFailure,
 118   // The symbol has been freed when reallocation failed.
 119   RPIsFreeOnFailure,
 120   // The symbol does not need to be freed after reallocation fails.
 121   RPDoNotTrackAfterFailure
 122 };
 123
 124 /// \class ReallocPair
 125 /// \brief Stores information about the symbol being reallocated by a call to
 126 /// 'realloc' to allow modeling failed reallocation later in the path.
 127 struct ReallocPair {
 128   // \brief The symbol which realloc reallocated.
 129   SymbolRef ReallocatedSym;
 130   ReallocPairKind Kind;
 131
 132   ReallocPair(SymbolRef S, ReallocPairKind K) :
 133     ReallocatedSym(S), Kind(K) {}
 134   void Profile(llvm::FoldingSetNodeID &ID) const {
 135     ID.AddInteger(Kind);
 136     ID.AddPointer(ReallocatedSym);
 137   }
 138   bool operator==(const ReallocPair &X) const {
 139     return ReallocatedSym == X.ReallocatedSym &&
 140            Kind == X.Kind;
 141   }
 142 };
 143
 144 typedef std::pair<const ExplodedNode*, const MemRegion*> LeakInfo;
 145
 146 class MallocChecker : public Checker<check::DeadSymbols,
 147                                      check::PointerEscape,
 148                                      check::ConstPointerEscape,
 149                                      check::PreStmt<ReturnStmt>,
 150                                      check::PreCall,
 151                                      check::PostStmt<CallExpr>,
 152                                      check::PostStmt<CXXNewExpr>,
 153                                      check::PreStmt<CXXDeleteExpr>,
 154                                      check::PostStmt<BlockExpr>,
 155                                      check::PostObjCMessage,
 156                                      check::Location,
 157                                      eval::Assume>
 158 {
 159 public:
 160   MallocChecker()
 161       : II_malloc(nullptr), II_free(nullptr), II_realloc(nullptr),
 162         II_calloc(nullptr), II_valloc(nullptr), II_reallocf(nullptr),
 163         II_strndup(nullptr), II_strdup(nullptr), II_kmalloc(nullptr) {}
 164
 165   /// In pessimistic mode, the checker assumes that it does not know which
 166   /// functions might free the memory.
 167   enum CheckKind {
 168     CK_MallocPessimistic,
 169     CK_MallocOptimistic,
 170     CK_NewDeleteChecker,
 171     CK_NewDeleteLeaksChecker,
 172     CK_MismatchedDeallocatorChecker,
 173     CK_NumCheckKinds
 174   };
 175
 176   DefaultBool ChecksEnabled[CK_NumCheckKinds];
 177   CheckName CheckNames[CK_NumCheckKinds];
 178
 179   void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
 180   void checkPostStmt(const CallExpr *CE, CheckerContext &C) const;
 181   void checkPostStmt(const CXXNewExpr *NE, CheckerContext &C) const;
 182   void checkPreStmt(const CXXDeleteExpr *DE, CheckerContext &C) const;
 183   void checkPostObjCMessage(const ObjCMethodCall &Call, CheckerContext &C) const;
 184   void checkPostStmt(const BlockExpr *BE, CheckerContext &C) const;
 185   void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const;
 186   void checkPreStmt(const ReturnStmt *S, CheckerContext &C) const;
 187   ProgramStateRef evalAssume(ProgramStateRef state, SVal Cond,
 188                             bool Assumption) const;
 189   void checkLocation(SVal l, bool isLoad, const Stmt *S,
 190                      CheckerContext &C) const;
 191
 192   ProgramStateRef checkPointerEscape(ProgramStateRef State,
 193                                     const InvalidatedSymbols &Escaped,
 194                                     const CallEvent *Call,
 195                                     PointerEscapeKind Kind) const;
 196   ProgramStateRef checkConstPointerEscape(ProgramStateRef State,
 197                                           const InvalidatedSymbols &Escaped,
 198                                           const CallEvent *Call,
 199                                           PointerEscapeKind Kind) const;
 200
 201   void printState(raw_ostream &Out, ProgramStateRef State,
 202                   const char *NL, const char *Sep) const override;
 203
 204 private:
 205   mutable std::unique_ptr<BugType> BT_DoubleFree[CK_NumCheckKinds];
 206   mutable std::unique_ptr<BugType> BT_DoubleDelete;
 207   mutable std::unique_ptr<BugType> BT_Leak[CK_NumCheckKinds];
 208   mutable std::unique_ptr<BugType> BT_UseFree[CK_NumCheckKinds];
 209   mutable std::unique_ptr<BugType> BT_BadFree[CK_NumCheckKinds];
 210   mutable std::unique_ptr<BugType> BT_MismatchedDealloc;
 211   mutable std::unique_ptr<BugType> BT_OffsetFree[CK_NumCheckKinds];
 212   mutable IdentifierInfo *II_malloc, *II_free, *II_realloc, *II_calloc,
 213                          *II_valloc, *II_reallocf, *II_strndup, *II_strdup,
 214                          *II_kmalloc;
 215   mutable Optional<uint64_t> KernelZeroFlagVal;
 216
 217   void initIdentifierInfo(ASTContext &C) const;
 218
 219   /// \brief Determine family of a deallocation expression.
 220   AllocationFamily getAllocationFamily(CheckerContext &C, const Stmt *S) const;
 221
 222   /// \brief Print names of allocators and deallocators.
 223   ///
 224   /// \returns true on success.
 225   bool printAllocDeallocName(raw_ostream &os, CheckerContext &C,
 226                              const Expr *E) const;
 227
 228   /// \brief Print expected name of an allocator based on the deallocator's
 229   /// family derived from the DeallocExpr.
 230   void printExpectedAllocName(raw_ostream &os, CheckerContext &C,
 231                               const Expr *DeallocExpr) const;
 232   /// \brief Print expected name of a deallocator based on the allocator's
 233   /// family.
 234   void printExpectedDeallocName(raw_ostream &os, AllocationFamily Family) const;
 235
 236   ///@{
 237   /// Check if this is one of the functions which can allocate/reallocate memory
 238   /// pointed to by one of its arguments.
 239   bool isMemFunction(const FunctionDecl *FD, ASTContext &C) const;
 240   bool isFreeFunction(const FunctionDecl *FD, ASTContext &C) const;
 241   bool isAllocationFunction(const FunctionDecl *FD, ASTContext &C) const;
 242   bool isStandardNewDelete(const FunctionDecl *FD, ASTContext &C) const;
 243   ///@}
 244   ProgramStateRef MallocMemReturnsAttr(CheckerContext &C,
 245                                        const CallExpr *CE,
 246                                        const OwnershipAttr* Att) const;
 247   static ProgramStateRef MallocMemAux(CheckerContext &C, const CallExpr *CE,
 248                                      const Expr *SizeEx, SVal Init,
 249                                      ProgramStateRef State,
 250                                      AllocationFamily Family = AF_Malloc) {
 251     return MallocMemAux(C, CE,
 252                         State->getSVal(SizeEx, C.getLocationContext()),
 253                         Init, State, Family);
 254   }
 255
 256   static ProgramStateRef MallocMemAux(CheckerContext &C, const CallExpr *CE,
 257                                      SVal SizeEx, SVal Init,
 258                                      ProgramStateRef State,
 259                                      AllocationFamily Family = AF_Malloc);
 260
 261   // Check if this malloc() for special flags. At present that means M_ZERO or
 262   // __GFP_ZERO (in which case, treat it like calloc).
 263   llvm::Optional<ProgramStateRef>
 264   performKernelMalloc(const CallExpr *CE, CheckerContext &C,
 265                       const ProgramStateRef &State) const;
 266
 267   /// Update the RefState to reflect the new memory allocation.
 268   static ProgramStateRef
 269   MallocUpdateRefState(CheckerContext &C, const Expr *E, ProgramStateRef State,
 270                        AllocationFamily Family = AF_Malloc);
 271
 272   ProgramStateRef FreeMemAttr(CheckerContext &C, const CallExpr *CE,
 273                               const OwnershipAttr* Att) const;
 274   ProgramStateRef FreeMemAux(CheckerContext &C, const CallExpr *CE,
 275                              ProgramStateRef state, unsigned Num,
 276                              bool Hold,
 277                              bool &ReleasedAllocated,
 278                              bool ReturnsNullOnFailure = false) const;
 279   ProgramStateRef FreeMemAux(CheckerContext &C, const Expr *Arg,
 280                              const Expr *ParentExpr,
 281                              ProgramStateRef State,
 282                              bool Hold,
 283                              bool &ReleasedAllocated,
 284                              bool ReturnsNullOnFailure = false) const;
 285
 286   ProgramStateRef ReallocMem(CheckerContext &C, const CallExpr *CE,
 287                              bool FreesMemOnFailure) const;
 288   static ProgramStateRef CallocMem(CheckerContext &C, const CallExpr *CE);
 289
 290   ///\brief Check if the memory associated with this symbol was released.
 291   bool isReleased(SymbolRef Sym, CheckerContext &C) const;
 292
 293   bool checkUseAfterFree(SymbolRef Sym, CheckerContext &C, const Stmt *S) const;
 294
 295   bool checkDoubleDelete(SymbolRef Sym, CheckerContext &C) const;
 296
 297   /// Check if the function is known free memory, or if it is
 298   /// "interesting" and should be modeled explicitly.
 299   ///
 300   /// \param [out] EscapingSymbol A function might not free memory in general,
 301   ///   but could be known to free a particular symbol. In this case, false is
 302   ///   returned and the single escaping symbol is returned through the out
 303   ///   parameter.
 304   ///
 305   /// We assume that pointers do not escape through calls to system functions
 306   /// not handled by this checker.
 307   bool mayFreeAnyEscapedMemoryOrIsModeledExplicitly(const CallEvent *Call,
 308                                    ProgramStateRef State,
 309                                    SymbolRef &EscapingSymbol) const;
 310
 311   // Implementation of the checkPointerEscape callabcks.
 312   ProgramStateRef checkPointerEscapeAux(ProgramStateRef State,
 313                                   const InvalidatedSymbols &Escaped,
 314                                   const CallEvent *Call,
 315                                   PointerEscapeKind Kind,
 316                                   bool(*CheckRefState)(const RefState*)) const;
 317
 318   ///@{
 319   /// Tells if a given family/call/symbol is tracked by the current checker.
 320   /// Sets CheckKind to the kind of the checker responsible for this
 321   /// family/call/symbol.
 322   Optional<CheckKind> getCheckIfTracked(AllocationFamily Family) const;
 323   Optional<CheckKind> getCheckIfTracked(CheckerContext &C,
 324                                         const Stmt *AllocDeallocStmt) const;
 325   Optional<CheckKind> getCheckIfTracked(CheckerContext &C, SymbolRef Sym) const;
 326   ///@}
 327   static bool SummarizeValue(raw_ostream &os, SVal V);
 328   static bool SummarizeRegion(raw_ostream &os, const MemRegion *MR);
 329   void ReportBadFree(CheckerContext &C, SVal ArgVal, SourceRange Range,
 330                      const Expr *DeallocExpr) const;
 331   void ReportMismatchedDealloc(CheckerContext &C, SourceRange Range,
 332                                const Expr *DeallocExpr, const RefState *RS,
 333                                SymbolRef Sym, bool OwnershipTransferred) const;
 334   void ReportOffsetFree(CheckerContext &C, SVal ArgVal, SourceRange Range,
 335                         const Expr *DeallocExpr,
 336                         const Expr *AllocExpr = nullptr) const;
 337   void ReportUseAfterFree(CheckerContext &C, SourceRange Range,
 338                           SymbolRef Sym) const;
 339   void ReportDoubleFree(CheckerContext &C, SourceRange Range, bool Released,
 340                         SymbolRef Sym, SymbolRef PrevSym) const;
 341
 342   void ReportDoubleDelete(CheckerContext &C, SymbolRef Sym) const;
 343
 344   /// Find the location of the allocation for Sym on the path leading to the
 345   /// exploded node N.
 346   LeakInfo getAllocationSite(const ExplodedNode *N, SymbolRef Sym,
 347                              CheckerContext &C) const;
 348
 349   void reportLeak(SymbolRef Sym, ExplodedNode *N, CheckerContext &C) const;
 350
 351   /// The bug visitor which allows us to print extra diagnostics along the
 352   /// BugReport path. For example, showing the allocation site of the leaked
 353   /// region.
 354   class MallocBugVisitor : public BugReporterVisitorImpl<MallocBugVisitor> {
 355   protected:
 356     enum NotificationMode {
 357       Normal,
 358       ReallocationFailed
 359     };
 360
 361     // The allocated region symbol tracked by the main analysis.
 362     SymbolRef Sym;
 363
 364     // The mode we are in, i.e. what kind of diagnostics will be emitted.
 365     NotificationMode Mode;
 366
 367     // A symbol from when the primary region should have been reallocated.
 368     SymbolRef FailedReallocSymbol;
 369
 370     bool IsLeak;
 371
 372   public:
 373     MallocBugVisitor(SymbolRef S, bool isLeak = false)
 374        : Sym(S), Mode(Normal), FailedReallocSymbol(nullptr), IsLeak(isLeak) {}
 375
 376     virtual ~MallocBugVisitor() {}
 377
 378     void Profile(llvm::FoldingSetNodeID &ID) const override {
 379       static int X = 0;
 380       ID.AddPointer(&X);
 381       ID.AddPointer(Sym);
 382     }
 383
 384     inline bool isAllocated(const RefState *S, const RefState *SPrev,
 385                             const Stmt *Stmt) {
 386       // Did not track -> allocated. Other state (released) -> allocated.
 387       return (Stmt && (isa<CallExpr>(Stmt) || isa<CXXNewExpr>(Stmt)) &&
 388               (S && S->isAllocated()) && (!SPrev || !SPrev->isAllocated()));
 389     }
 390
 391     inline bool isReleased(const RefState *S, const RefState *SPrev,
 392                            const Stmt *Stmt) {
 393       // Did not track -> released. Other state (allocated) -> released.
 394       return (Stmt && (isa<CallExpr>(Stmt) || isa<CXXDeleteExpr>(Stmt)) &&
 395               (S && S->isReleased()) && (!SPrev || !SPrev->isReleased()));
 396     }
 397
 398     inline bool isRelinquished(const RefState *S, const RefState *SPrev,
 399                                const Stmt *Stmt) {
 400       // Did not track -> relinquished. Other state (allocated) -> relinquished.
 401       return (Stmt && (isa<CallExpr>(Stmt) || isa<ObjCMessageExpr>(Stmt) ||
 402                                               isa<ObjCPropertyRefExpr>(Stmt)) &&
 403               (S && S->isRelinquished()) &&
 404               (!SPrev || !SPrev->isRelinquished()));
 405     }
 406
 407     inline bool isReallocFailedCheck(const RefState *S, const RefState *SPrev,
 408                                      const Stmt *Stmt) {
 409       // If the expression is not a call, and the state change is
 410       // released -> allocated, it must be the realloc return value
 411       // check. If we have to handle more cases here, it might be cleaner just
 412       // to track this extra bit in the state itself.
 413       return ((!Stmt || !isa<CallExpr>(Stmt)) &&
 414               (S && S->isAllocated()) && (SPrev && !SPrev->isAllocated()));
 415     }
 416
 417     PathDiagnosticPiece *VisitNode(const ExplodedNode *N,
 418                                    const ExplodedNode *PrevN,
 419                                    BugReporterContext &BRC,
 420                                    BugReport &BR) override;
 421
 422     PathDiagnosticPiece* getEndPath(BugReporterContext &BRC,
 423                                     const ExplodedNode *EndPathNode,
 424                                     BugReport &BR) override {
 425       if (!IsLeak)
 426         return nullptr;
 427
 428       PathDiagnosticLocation L =
 429         PathDiagnosticLocation::createEndOfPath(EndPathNode,
 430                                                 BRC.getSourceManager());
 431       // Do not add the statement itself as a range in case of leak.
 432       return new PathDiagnosticEventPiece(L, BR.getDescription(), false);
 433     }
 434
 435   private:
 436     class StackHintGeneratorForReallocationFailed
 437         : public StackHintGeneratorForSymbol {
 438     public:
 439       StackHintGeneratorForReallocationFailed(SymbolRef S, StringRef M)
 440         : StackHintGeneratorForSymbol(S, M) {}
 441
 442       std::string getMessageForArg(const Expr *ArgE,
 443                                    unsigned ArgIndex) override {
 444         // Printed parameters start at 1, not 0.
 445         ++ArgIndex;
 446
 447         SmallString<200> buf;
 448         llvm::raw_svector_ostream os(buf);
 449
 450         os << "Reallocation of " << ArgIndex << llvm::getOrdinalSuffix(ArgIndex)
 451            << " parameter failed";
 452
 453         return os.str();
 454       }
 455
 456       std::string getMessageForReturn(const CallExpr *CallExpr) override {
 457         return "Reallocation of returned value failed";
 458       }
 459     };
 460   };
 461 };
 462 } // end anonymous namespace
 463
 464 REGISTER_MAP_WITH_PROGRAMSTATE(RegionState, SymbolRef, RefState)
 465 REGISTER_MAP_WITH_PROGRAMSTATE(ReallocPairs, SymbolRef, ReallocPair)
 466
 467 // A map from the freed symbol to the symbol representing the return value of
 468 // the free function.
 469 REGISTER_MAP_WITH_PROGRAMSTATE(FreeReturnValue, SymbolRef, SymbolRef)
 470
 471 namespace {
 472 class StopTrackingCallback : public SymbolVisitor {
 473   ProgramStateRef state;
 474 public:
 475   StopTrackingCallback(ProgramStateRef st) : state(st) {}
 476   ProgramStateRef getState() const { return state; }
 477
 478   bool VisitSymbol(SymbolRef sym) override {
 479     state = state->remove<RegionState>(sym);
 480     return true;
 481   }
 482 };
 483 } // end anonymous namespace
 484
 485 void MallocChecker::initIdentifierInfo(ASTContext &Ctx) const {
 486   if (II_malloc)
 487     return;
 488   II_malloc = &Ctx.Idents.get("malloc");
 489   II_free = &Ctx.Idents.get("free");
 490   II_realloc = &Ctx.Idents.get("realloc");
 491   II_reallocf = &Ctx.Idents.get("reallocf");
 492   II_calloc = &Ctx.Idents.get("calloc");
 493   II_valloc = &Ctx.Idents.get("valloc");
 494   II_strdup = &Ctx.Idents.get("strdup");
 495   II_strndup = &Ctx.Idents.get("strndup");
 496   II_kmalloc = &Ctx.Idents.get("kmalloc");
 497 }
 498
 499 bool MallocChecker::isMemFunction(const FunctionDecl *FD, ASTContext &C) const {
 500   if (isFreeFunction(FD, C))
 501     return true;
 502
 503   if (isAllocationFunction(FD, C))
 504     return true;
 505
 506   if (isStandardNewDelete(FD, C))
 507     return true;
 508
 509   return false;
 510 }
 511
 512 bool MallocChecker::isAllocationFunction(const FunctionDecl *FD,
 513                                          ASTContext &C) const {
 514   if (!FD)
 515     return false;
 516
 517   if (FD->getKind() == Decl::Function) {
 518     IdentifierInfo *FunI = FD->getIdentifier();
 519     initIdentifierInfo(C);
 520
 521     if (FunI == II_malloc || FunI == II_realloc ||
 522         FunI == II_reallocf || FunI == II_calloc || FunI == II_valloc ||
 523         FunI == II_strdup || FunI == II_strndup || FunI == II_kmalloc)
 524       return true;
 525   }
 526
 527   if (ChecksEnabled[CK_MallocOptimistic] && FD->hasAttrs())
 528     for (const auto *I : FD->specific_attrs<OwnershipAttr>())
 529       if (I->getOwnKind() == OwnershipAttr::Returns)
 530         return true;
 531   return false;
 532 }
 533
 534 bool MallocChecker::isFreeFunction(const FunctionDecl *FD, ASTContext &C) const {
 535   if (!FD)
 536     return false;
 537
 538   if (FD->getKind() == Decl::Function) {
 539     IdentifierInfo *FunI = FD->getIdentifier();
 540     initIdentifierInfo(C);
 541
 542     if (FunI == II_free || FunI == II_realloc || FunI == II_reallocf)
 543       return true;
 544   }
 545
 546   if (ChecksEnabled[CK_MallocOptimistic] && FD->hasAttrs())
 547     for (const auto *I : FD->specific_attrs<OwnershipAttr>())
 548       if (I->getOwnKind() == OwnershipAttr::Takes ||
 549           I->getOwnKind() == OwnershipAttr::Holds)
 550         return true;
 551   return false;
 552 }
 553
 554 // Tells if the callee is one of the following:
 555 // 1) A global non-placement new/delete operator function.
 556 // 2) A global placement operator function with the single placement argument
 557 //    of type std::nothrow_t.
 558 bool MallocChecker::isStandardNewDelete(const FunctionDecl *FD,
 559                                         ASTContext &C) const {
 560   if (!FD)
 561     return false;
 562
 563   OverloadedOperatorKind Kind = FD->getOverloadedOperator();
 564   if (Kind != OO_New && Kind != OO_Array_New &&
 565       Kind != OO_Delete && Kind != OO_Array_Delete)
 566     return false;
 567
 568   // Skip all operator new/delete methods.
 569   if (isa<CXXMethodDecl>(FD))
 570     return false;
 571
 572   // Return true if tested operator is a standard placement nothrow operator.
 573   if (FD->getNumParams() == 2) {
 574     QualType T = FD->getParamDecl(1)->getType();
 575     if (const IdentifierInfo *II = T.getBaseTypeIdentifier())
 576       return II->getName().equals("nothrow_t");
 577   }
 578
 579   // Skip placement operators.
 580   if (FD->getNumParams() != 1 || FD->isVariadic())
 581     return false;
 582
 583   // One of the standard new/new[]/delete/delete[] non-placement operators.
 584   return true;
 585 }
 586
 587 llvm::Optional<ProgramStateRef> MallocChecker::performKernelMalloc(
 588   const CallExpr *CE, CheckerContext &C, const ProgramStateRef &State) const {
 589   // 3-argument malloc(), as commonly used in {Free,Net,Open}BSD Kernels:
 590   //
 591   // void *malloc(unsigned long size, struct malloc_type *mtp, int flags);
 592   //
 593   // One of the possible flags is M_ZERO, which means 'give me back an
 594   // allocation which is already zeroed', like calloc.
 595
 596   // 2-argument kmalloc(), as used in the Linux kernel:
 597   //
 598   // void *kmalloc(size_t size, gfp_t flags);
 599   //
 600   // Has the similar flag value __GFP_ZERO.
 601
 602   // This logic is largely cloned from O_CREAT in UnixAPIChecker, maybe some
 603   // code could be shared.
 604
 605   ASTContext &Ctx = C.getASTContext();
 606   llvm::Triple::OSType OS = Ctx.getTargetInfo().getTriple().getOS();
 607
 608   if (!KernelZeroFlagVal.hasValue()) {
 609     if (OS == llvm::Triple::FreeBSD)
 610       KernelZeroFlagVal = 0x0100;
 611     else if (OS == llvm::Triple::NetBSD)
 612       KernelZeroFlagVal = 0x0002;
 613     else if (OS == llvm::Triple::OpenBSD)
 614       KernelZeroFlagVal = 0x0008;
 615     else if (OS == llvm::Triple::Linux)
 616       // __GFP_ZERO
 617       KernelZeroFlagVal = 0x8000;
 618     else
 619       // FIXME: We need a more general way of getting the M_ZERO value.
 620       // See also: O_CREAT in UnixAPIChecker.cpp.
 621
 622       // Fall back to normal malloc behavior on platforms where we don't
 623       // know M_ZERO.
 624       return None;
 625   }
 626
 627   // We treat the last argument as the flags argument, and callers fall-back to
 628   // normal malloc on a None return. This works for the FreeBSD kernel malloc
 629   // as well as Linux kmalloc.
 630   if (CE->getNumArgs() < 2)
 631     return None;
 632
 633   const Expr *FlagsEx = CE->getArg(CE->getNumArgs() - 1);
 634   const SVal V = State->getSVal(FlagsEx, C.getLocationContext());
 635   if (!V.getAs<NonLoc>()) {
 636     // The case where 'V' can be a location can only be due to a bad header,
 637     // so in this case bail out.
 638     return None;
 639   }
 640
 641   NonLoc Flags = V.castAs<NonLoc>();
 642   NonLoc ZeroFlag = C.getSValBuilder()
 643       .makeIntVal(KernelZeroFlagVal.getValue(), FlagsEx->getType())
 644       .castAs<NonLoc>();
 645   SVal MaskedFlagsUC = C.getSValBuilder().evalBinOpNN(State, BO_And,
 646                                                       Flags, ZeroFlag,
 647                                                       FlagsEx->getType());
 648   if (MaskedFlagsUC.isUnknownOrUndef())
 649     return None;
 650   DefinedSVal MaskedFlags = MaskedFlagsUC.castAs<DefinedSVal>();
 651
 652   // Check if maskedFlags is non-zero.
 653   ProgramStateRef TrueState, FalseState;
 654   std::tie(TrueState, FalseState) = State->assume(MaskedFlags);
 655
 656   // If M_ZERO is set, treat this like calloc (initialized).
 657   if (TrueState && !FalseState) {
 658     SVal ZeroVal = C.getSValBuilder().makeZeroVal(Ctx.CharTy);
 659     return MallocMemAux(C, CE, CE->getArg(0), ZeroVal, TrueState);
 660   }
 661
 662   return None;
 663 }
 664
 665 void MallocChecker::checkPostStmt(const CallExpr *CE, CheckerContext &C) const {
 666   if (C.wasInlined)
 667     return;
 668
 669   const FunctionDecl *FD = C.getCalleeDecl(CE);
 670   if (!FD)
 671     return;
 672
 673   ProgramStateRef State = C.getState();
 674   bool ReleasedAllocatedMemory = false;
 675
 676   if (FD->getKind() == Decl::Function) {
 677     initIdentifierInfo(C.getASTContext());
 678     IdentifierInfo *FunI = FD->getIdentifier();
 679
 680     if (FunI == II_malloc) {
 681       if (CE->getNumArgs() < 1)
 682         return;
 683       if (CE->getNumArgs() < 3) {
 684         State = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(), State);
 685       } else if (CE->getNumArgs() == 3) {
 686         llvm::Optional<ProgramStateRef> MaybeState =
 687           performKernelMalloc(CE, C, State);
 688         if (MaybeState.hasValue())
 689           State = MaybeState.getValue();
 690         else
 691           State = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(), State);
 692       }
 693     } else if (FunI == II_kmalloc) {
 694       llvm::Optional<ProgramStateRef> MaybeState =
 695         performKernelMalloc(CE, C, State);
 696       if (MaybeState.hasValue())
 697         State = MaybeState.getValue();
 698       else
 699         State = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(), State);
 700     } else if (FunI == II_valloc) {
 701       if (CE->getNumArgs() < 1)
 702         return;
 703       State = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(), State);
 704     } else if (FunI == II_realloc) {
 705       State = ReallocMem(C, CE, false);
 706     } else if (FunI == II_reallocf) {
 707       State = ReallocMem(C, CE, true);
 708     } else if (FunI == II_calloc) {
 709       State = CallocMem(C, CE);
 710     } else if (FunI == II_free) {
 711       State = FreeMemAux(C, CE, State, 0, false, ReleasedAllocatedMemory);
 712     } else if (FunI == II_strdup) {
 713       State = MallocUpdateRefState(C, CE, State);
 714     } else if (FunI == II_strndup) {
 715       State = MallocUpdateRefState(C, CE, State);
 716     }
 717     else if (isStandardNewDelete(FD, C.getASTContext())) {
 718       // Process direct calls to operator new/new[]/delete/delete[] functions
 719       // as distinct from new/new[]/delete/delete[] expressions that are
 720       // processed by the checkPostStmt callbacks for CXXNewExpr and
 721       // CXXDeleteExpr.
 722       OverloadedOperatorKind K = FD->getOverloadedOperator();
 723       if (K == OO_New)
 724         State = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(), State,
 725                              AF_CXXNew);
 726       else if (K == OO_Array_New)
 727         State = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(), State,
 728                              AF_CXXNewArray);
 729       else if (K == OO_Delete || K == OO_Array_Delete)
 730         State = FreeMemAux(C, CE, State, 0, false, ReleasedAllocatedMemory);
 731       else
 732         llvm_unreachable("not a new/delete operator");
 733     }
 734   }
 735
 736   if (ChecksEnabled[CK_MallocOptimistic] ||
 737       ChecksEnabled[CK_MismatchedDeallocatorChecker]) {
 738     // Check all the attributes, if there are any.
 739     // There can be multiple of these attributes.
 740     if (FD->hasAttrs())
 741       for (const auto *I : FD->specific_attrs<OwnershipAttr>()) {
 742         switch (I->getOwnKind()) {
 743         case OwnershipAttr::Returns:
 744           State = MallocMemReturnsAttr(C, CE, I);
 745           break;
 746         case OwnershipAttr::Takes:
 747         case OwnershipAttr::Holds:
 748           State = FreeMemAttr(C, CE, I);
 749           break;
 750         }
 751       }
 752   }
 753   C.addTransition(State);
 754 }
 755
 756 void MallocChecker::checkPostStmt(const CXXNewExpr *NE,
 757                                   CheckerContext &C) const {
 758
 759   if (NE->getNumPlacementArgs())
 760     for (CXXNewExpr::const_arg_iterator I = NE->placement_arg_begin(),
 761          E = NE->placement_arg_end(); I != E; ++I)
 762       if (SymbolRef Sym = C.getSVal(*I).getAsSymbol())
 763         checkUseAfterFree(Sym, C, *I);
 764
 765   if (!isStandardNewDelete(NE->getOperatorNew(), C.getASTContext()))
 766     return;
 767
 768   ProgramStateRef State = C.getState();
 769   // The return value from operator new is bound to a specified initialization
 770   // value (if any) and we don't want to loose this value. So we call
 771   // MallocUpdateRefState() instead of MallocMemAux() which breakes the
 772   // existing binding.
 773   State = MallocUpdateRefState(C, NE, State, NE->isArray() ? AF_CXXNewArray
 774                                                            : AF_CXXNew);
 775   C.addTransition(State);
 776 }
 777
 778 void MallocChecker::checkPreStmt(const CXXDeleteExpr *DE,
 779                                  CheckerContext &C) const {
 780
 781   if (!ChecksEnabled[CK_NewDeleteChecker])
 782     if (SymbolRef Sym = C.getSVal(DE->getArgument()).getAsSymbol())
 783       checkUseAfterFree(Sym, C, DE->getArgument());
 784
 785   if (!isStandardNewDelete(DE->getOperatorDelete(), C.getASTContext()))
 786     return;
 787
 788   ProgramStateRef State = C.getState();
 789   bool ReleasedAllocated;
 790   State = FreeMemAux(C, DE->getArgument(), DE, State,
 791                      /*Hold*/false, ReleasedAllocated);
 792
 793   C.addTransition(State);
 794 }
 795
 796 static bool isKnownDeallocObjCMethodName(const ObjCMethodCall &Call) {
 797   // If the first selector piece is one of the names below, assume that the
 798   // object takes ownership of the memory, promising to eventually deallocate it
 799   // with free().
 800   // Ex:  [NSData dataWithBytesNoCopy:bytes length:10];
 801   // (...unless a 'freeWhenDone' parameter is false, but that's checked later.)
 802   StringRef FirstSlot = Call.getSelector().getNameForSlot(0);
 803   if (FirstSlot == "dataWithBytesNoCopy" ||
 804       FirstSlot == "initWithBytesNoCopy" ||
 805       FirstSlot == "initWithCharactersNoCopy")
 806     return true;
 807
 808   return false;
 809 }
 810
 811 static Optional<bool> getFreeWhenDoneArg(const ObjCMethodCall &Call) {
 812   Selector S = Call.getSelector();
 813
 814   // FIXME: We should not rely on fully-constrained symbols being folded.
 815   for (unsigned i = 1; i < S.getNumArgs(); ++i)
 816     if (S.getNameForSlot(i).equals("freeWhenDone"))
 817       return !Call.getArgSVal(i).isZeroConstant();
 818
 819   return None;
 820 }
 821
 822 void MallocChecker::checkPostObjCMessage(const ObjCMethodCall &Call,
 823                                          CheckerContext &C) const {
 824   if (C.wasInlined)
 825     return;
 826
 827   if (!isKnownDeallocObjCMethodName(Call))
 828     return;
 829
 830   if (Optional<bool> FreeWhenDone = getFreeWhenDoneArg(Call))
 831     if (!*FreeWhenDone)
 832       return;
 833
 834   bool ReleasedAllocatedMemory;
 835   ProgramStateRef State = FreeMemAux(C, Call.getArgExpr(0),
 836                                      Call.getOriginExpr(), C.getState(),
 837                                      /*Hold=*/true, ReleasedAllocatedMemory,
 838                                      /*RetNullOnFailure=*/true);
 839
 840   C.addTransition(State);
 841 }
 842
 843 ProgramStateRef
 844 MallocChecker::MallocMemReturnsAttr(CheckerContext &C, const CallExpr *CE,
 845                                     const OwnershipAttr *Att) const {
 846   if (Att->getModule() != II_malloc)
 847     return nullptr;
 848
 849   OwnershipAttr::args_iterator I = Att->args_begin(), E = Att->args_end();
 850   if (I != E) {
 851     return MallocMemAux(C, CE, CE->getArg(*I), UndefinedVal(), C.getState());
 852   }
 853   return MallocMemAux(C, CE, UnknownVal(), UndefinedVal(), C.getState());
 854 }
 855
 856 ProgramStateRef MallocChecker::MallocMemAux(CheckerContext &C,
 857                                            const CallExpr *CE,
 858                                            SVal Size, SVal Init,
 859                                            ProgramStateRef State,
 860                                            AllocationFamily Family) {
 861
 862   // Bind the return value to the symbolic value from the heap region.
 863   // TODO: We could rewrite post visit to eval call; 'malloc' does not have
 864   // side effects other than what we model here.
 865   unsigned Count = C.blockCount();
 866   SValBuilder &svalBuilder = C.getSValBuilder();
 867   const LocationContext *LCtx = C.getPredecessor()->getLocationContext();
 868   DefinedSVal RetVal = svalBuilder.getConjuredHeapSymbolVal(CE, LCtx, Count)
 869       .castAs<DefinedSVal>();
 870   State = State->BindExpr(CE, C.getLocationContext(), RetVal);
 871
 872   // We expect the malloc functions to return a pointer.
 873   if (!RetVal.getAs<Loc>())
 874     return nullptr;
 875
 876   // Fill the region with the initialization value.
 877   State = State->bindDefault(RetVal, Init);
 878
 879   // Set the region's extent equal to the Size parameter.
 880   const SymbolicRegion *R =
 881       dyn_cast_or_null<SymbolicRegion>(RetVal.getAsRegion());
 882   if (!R)
 883     return nullptr;
 884   if (Optional<DefinedOrUnknownSVal> DefinedSize =
 885           Size.getAs<DefinedOrUnknownSVal>()) {
 886     SValBuilder &svalBuilder = C.getSValBuilder();
 887     DefinedOrUnknownSVal Extent = R->getExtent(svalBuilder);
 888     DefinedOrUnknownSVal extentMatchesSize =
 889         svalBuilder.evalEQ(State, Extent, *DefinedSize);
 890
 891     State = State->assume(extentMatchesSize, true);
 892     assert(State);
 893   }
 894
 895   return MallocUpdateRefState(C, CE, State, Family);
 896 }
 897
 898 ProgramStateRef MallocChecker::MallocUpdateRefState(CheckerContext &C,
 899                                                     const Expr *E,
 900                                                     ProgramStateRef State,
 901                                                     AllocationFamily Family) {
 902   // Get the return value.
 903   SVal retVal = State->getSVal(E, C.getLocationContext());
 904
 905   // We expect the malloc functions to return a pointer.
 906   if (!retVal.getAs<Loc>())
 907     return nullptr;
 908
 909   SymbolRef Sym = retVal.getAsLocSymbol();
 910   assert(Sym);
 911
 912   // Set the symbol's state to Allocated.
 913   return State->set<RegionState>(Sym, RefState::getAllocated(Family, E));
 914 }
 915
 916 ProgramStateRef MallocChecker::FreeMemAttr(CheckerContext &C,
 917                                            const CallExpr *CE,
 918                                            const OwnershipAttr *Att) const {
 919   if (Att->getModule() != II_malloc)
 920     return nullptr;
 921
 922   ProgramStateRef State = C.getState();
 923   bool ReleasedAllocated = false;
 924
 925   for (const auto &Arg : Att->args()) {
 926     ProgramStateRef StateI = FreeMemAux(C, CE, State, Arg,
 927                                Att->getOwnKind() == OwnershipAttr::Holds,
 928                                ReleasedAllocated);
 929     if (StateI)
 930       State = StateI;
 931   }
 932   return State;
 933 }
 934
 935 ProgramStateRef MallocChecker::FreeMemAux(CheckerContext &C,
 936                                           const CallExpr *CE,
 937                                           ProgramStateRef state,
 938                                           unsigned Num,
 939                                           bool Hold,
 940                                           bool &ReleasedAllocated,
 941                                           bool ReturnsNullOnFailure) const {
 942   if (CE->getNumArgs() < (Num + 1))
 943     return nullptr;
 944
 945   return FreeMemAux(C, CE->getArg(Num), CE, state, Hold,
 946                     ReleasedAllocated, ReturnsNullOnFailure);
 947 }
 948
 949 /// Checks if the previous call to free on the given symbol failed - if free
 950 /// failed, returns true. Also, returns the corresponding return value symbol.
 951 static bool didPreviousFreeFail(ProgramStateRef State,
 952                                 SymbolRef Sym, SymbolRef &RetStatusSymbol) {
 953   const SymbolRef *Ret = State->get<FreeReturnValue>(Sym);
 954   if (Ret) {
 955     assert(*Ret && "We should not store the null return symbol");
 956     ConstraintManager &CMgr = State->getConstraintManager();
 957     ConditionTruthVal FreeFailed = CMgr.isNull(State, *Ret);
 958     RetStatusSymbol = *Ret;
 959     return FreeFailed.isConstrainedTrue();
 960   }
 961   return false;
 962 }
 963
 964 AllocationFamily MallocChecker::getAllocationFamily(CheckerContext &C,
 965                                                     const Stmt *S) const {
 966   if (!S)
 967     return AF_None;
 968
 969   if (const CallExpr *CE = dyn_cast<CallExpr>(S)) {
 970     const FunctionDecl *FD = C.getCalleeDecl(CE);
 971
 972     if (!FD)
 973       FD = dyn_cast<FunctionDecl>(CE->getCalleeDecl());
 974
 975     ASTContext &Ctx = C.getASTContext();
 976
 977     if (isAllocationFunction(FD, Ctx) || isFreeFunction(FD, Ctx))
 978       return AF_Malloc;
 979
 980     if (isStandardNewDelete(FD, Ctx)) {
 981       OverloadedOperatorKind Kind = FD->getOverloadedOperator();
 982       if (Kind == OO_New || Kind == OO_Delete)
 983         return AF_CXXNew;
 984       else if (Kind == OO_Array_New || Kind == OO_Array_Delete)
 985         return AF_CXXNewArray;
 986     }
 987
 988     return AF_None;
 989   }
 990
 991   if (const CXXNewExpr *NE = dyn_cast<CXXNewExpr>(S))
 992     return NE->isArray() ? AF_CXXNewArray : AF_CXXNew;
 993
 994   if (const CXXDeleteExpr *DE = dyn_cast<CXXDeleteExpr>(S))
 995     return DE->isArrayForm() ? AF_CXXNewArray : AF_CXXNew;
 996
 997   if (isa<ObjCMessageExpr>(S))
 998     return AF_Malloc;
 999
1000   return AF_None;
1001 }
1002
1003 bool MallocChecker::printAllocDeallocName(raw_ostream &os, CheckerContext &C,
1004                                           const Expr *E) const {
1005   if (const CallExpr *CE = dyn_cast<CallExpr>(E)) {
1006     // FIXME: This doesn't handle indirect calls.
1007     const FunctionDecl *FD = CE->getDirectCallee();
1008     if (!FD)
1009       return false;
1010
1011     os << *FD;
1012     if (!FD->isOverloadedOperator())
1013       os << "()";
1014     return true;
1015   }
1016
1017   if (const ObjCMessageExpr *Msg = dyn_cast<ObjCMessageExpr>(E)) {
1018     if (Msg->isInstanceMessage())
1019       os << "-";
1020     else
1021       os << "+";
1022     Msg->getSelector().print(os);
1023     return true;
1024   }
1025
1026   if (const CXXNewExpr *NE = dyn_cast<CXXNewExpr>(E)) {
1027     os << "'"
1028        << getOperatorSpelling(NE->getOperatorNew()->getOverloadedOperator())
1029        << "'";
1030     return true;
1031   }
1032
1033   if (const CXXDeleteExpr *DE = dyn_cast<CXXDeleteExpr>(E)) {
1034     os << "'"
1035        << getOperatorSpelling(DE->getOperatorDelete()->getOverloadedOperator())
1036        << "'";
1037     return true;
1038   }
1039
1040   return false;
1041 }
1042
1043 void MallocChecker::printExpectedAllocName(raw_ostream &os, CheckerContext &C,
1044                                            const Expr *E) const {
1045   AllocationFamily Family = getAllocationFamily(C, E);
1046
1047   switch(Family) {
1048     case AF_Malloc: os << "malloc()"; return;
1049     case AF_CXXNew: os << "'new'"; return;
1050     case AF_CXXNewArray: os << "'new[]'"; return;
1051     case AF_None: llvm_unreachable("not a deallocation expression");
1052   }
1053 }
1054
1055 void MallocChecker::printExpectedDeallocName(raw_ostream &os,
1056                                              AllocationFamily Family) const {
1057   switch(Family) {
1058     case AF_Malloc: os << "free()"; return;
1059     case AF_CXXNew: os << "'delete'"; return;
1060     case AF_CXXNewArray: os << "'delete[]'"; return;
1061     case AF_None: llvm_unreachable("suspicious AF_None argument");
1062   }
1063 }
1064
1065 ProgramStateRef MallocChecker::FreeMemAux(CheckerContext &C,
1066                                           const Expr *ArgExpr,
1067                                           const Expr *ParentExpr,
1068                                           ProgramStateRef State,
1069                                           bool Hold,
1070                                           bool &ReleasedAllocated,
1071                                           bool ReturnsNullOnFailure) const {
1072
1073   SVal ArgVal = State->getSVal(ArgExpr, C.getLocationContext());
1074   if (!ArgVal.getAs<DefinedOrUnknownSVal>())
1075     return nullptr;
1076   DefinedOrUnknownSVal location = ArgVal.castAs<DefinedOrUnknownSVal>();
1077
1078   // Check for null dereferences.
1079   if (!location.getAs<Loc>())
1080     return nullptr;
1081
1082   // The explicit NULL case, no operation is performed.
1083   ProgramStateRef notNullState, nullState;
1084   std::tie(notNullState, nullState) = State->assume(location);
1085   if (nullState && !notNullState)
1086     return nullptr;
1087
1088   // Unknown values could easily be okay
1089   // Undefined values are handled elsewhere
1090   if (ArgVal.isUnknownOrUndef())
1091     return nullptr;
1092
1093   const MemRegion *R = ArgVal.getAsRegion();
1094
1095   // Nonlocs can't be freed, of course.
1096   // Non-region locations (labels and fixed addresses) also shouldn't be freed.
1097   if (!R) {
1098     ReportBadFree(C, ArgVal, ArgExpr->getSourceRange(), ParentExpr);
1099     return nullptr;
1100   }
1101
1102   R = R->StripCasts();
1103
1104   // Blocks might show up as heap data, but should not be free()d
1105   if (isa<BlockDataRegion>(R)) {
1106     ReportBadFree(C, ArgVal, ArgExpr->getSourceRange(), ParentExpr);
1107     return nullptr;
1108   }
1109
1110   const MemSpaceRegion *MS = R->getMemorySpace();
1111
1112   // Parameters, locals, statics, globals, and memory returned by alloca()
1113   // shouldn't be freed.
1114   if (!(isa<UnknownSpaceRegion>(MS) || isa<HeapSpaceRegion>(MS))) {
1115     // FIXME: at the time this code was written, malloc() regions were
1116     // represented by conjured symbols, which are all in UnknownSpaceRegion.
1117     // This means that there isn't actually anything from HeapSpaceRegion
1118     // that should be freed, even though we allow it here.
1119     // Of course, free() can work on memory allocated outside the current
1120     // function, so UnknownSpaceRegion is always a possibility.
1121     // False negatives are better than false positives.
1122
1123     ReportBadFree(C, ArgVal, ArgExpr->getSourceRange(), ParentExpr);
1124     return nullptr;
1125   }
1126
1127   const SymbolicRegion *SrBase = dyn_cast<SymbolicRegion>(R->getBaseRegion());
1128   // Various cases could lead to non-symbol values here.
1129   // For now, ignore them.
1130   if (!SrBase)
1131     return nullptr;
1132
1133   SymbolRef SymBase = SrBase->getSymbol();
1134   const RefState *RsBase = State->get<RegionState>(SymBase);
1135   SymbolRef PreviousRetStatusSymbol = nullptr;
1136
1137   if (RsBase) {
1138
1139     // Check for double free first.
1140     if ((RsBase->isReleased() || RsBase->isRelinquished()) &&
1141         !didPreviousFreeFail(State, SymBase, PreviousRetStatusSymbol)) {
1142       ReportDoubleFree(C, ParentExpr->getSourceRange(), RsBase->isReleased(),
1143                        SymBase, PreviousRetStatusSymbol);
1144       return nullptr;
1145
1146     // If the pointer is allocated or escaped, but we are now trying to free it,
1147     // check that the call to free is proper.
1148     } else if (RsBase->isAllocated() || RsBase->isEscaped()) {
1149
1150       // Check if an expected deallocation function matches the real one.
1151       bool DeallocMatchesAlloc =
1152         RsBase->getAllocationFamily() == getAllocationFamily(C, ParentExpr);
1153       if (!DeallocMatchesAlloc) {
1154         ReportMismatchedDealloc(C, ArgExpr->getSourceRange(),
1155                                 ParentExpr, RsBase, SymBase, Hold);
1156         return nullptr;
1157       }
1158
1159       // Check if the memory location being freed is the actual location
1160       // allocated, or an offset.
1161       RegionOffset Offset = R->getAsOffset();
1162       if (Offset.isValid() &&
1163           !Offset.hasSymbolicOffset() &&
1164           Offset.getOffset() != 0) {
1165         const Expr *AllocExpr = cast<Expr>(RsBase->getStmt());
1166         ReportOffsetFree(C, ArgVal, ArgExpr->getSourceRange(), ParentExpr,
1167                          AllocExpr);
1168         return nullptr;
1169       }
1170     }
1171   }
1172
1173   ReleasedAllocated = (RsBase != nullptr) && RsBase->isAllocated();
1174
1175   // Clean out the info on previous call to free return info.
1176   State = State->remove<FreeReturnValue>(SymBase);
1177
1178   // Keep track of the return value. If it is NULL, we will know that free
1179   // failed.
1180   if (ReturnsNullOnFailure) {
1181     SVal RetVal = C.getSVal(ParentExpr);
1182     SymbolRef RetStatusSymbol = RetVal.getAsSymbol();
1183     if (RetStatusSymbol) {
1184       C.getSymbolManager().addSymbolDependency(SymBase, RetStatusSymbol);
1185       State = State->set<FreeReturnValue>(SymBase, RetStatusSymbol);
1186     }
1187   }
1188
1189   AllocationFamily Family = RsBase ? RsBase->getAllocationFamily()
1190                                    : getAllocationFamily(C, ParentExpr);
1191   // Normal free.
1192   if (Hold)
1193     return State->set<RegionState>(SymBase,
1194                                    RefState::getRelinquished(Family,
1195                                                              ParentExpr));
1196
1197   return State->set<RegionState>(SymBase,
1198                                  RefState::getReleased(Family, ParentExpr));
1199 }
1200
1201 Optional<MallocChecker::CheckKind>
1202 MallocChecker::getCheckIfTracked(AllocationFamily Family) const {
1203   switch (Family) {
1204   case AF_Malloc: {
1205     if (ChecksEnabled[CK_MallocOptimistic]) {
1206       return CK_MallocOptimistic;
1207     } else if (ChecksEnabled[CK_MallocPessimistic]) {
1208       return CK_MallocPessimistic;
1209     }
1210     return Optional<MallocChecker::CheckKind>();
1211   }
1212   case AF_CXXNew:
1213   case AF_CXXNewArray: {
1214     if (ChecksEnabled[CK_NewDeleteChecker]) {
1215       return CK_NewDeleteChecker;
1216     }
1217     return Optional<MallocChecker::CheckKind>();
1218   }
1219   case AF_None: {
1220     llvm_unreachable("no family");
1221   }
1222   }
1223   llvm_unreachable("unhandled family");
1224 }
1225
1226 Optional<MallocChecker::CheckKind>
1227 MallocChecker::getCheckIfTracked(CheckerContext &C,
1228                                  const Stmt *AllocDeallocStmt) const {
1229   return getCheckIfTracked(getAllocationFamily(C, AllocDeallocStmt));
1230 }
1231
1232 Optional<MallocChecker::CheckKind>
1233 MallocChecker::getCheckIfTracked(CheckerContext &C, SymbolRef Sym) const {
1234
1235   const RefState *RS = C.getState()->get<RegionState>(Sym);
1236   assert(RS);
1237   return getCheckIfTracked(RS->getAllocationFamily());
1238 }
1239
1240 bool MallocChecker::SummarizeValue(raw_ostream &os, SVal V) {
1241   if (Optional<nonloc::ConcreteInt> IntVal = V.getAs<nonloc::ConcreteInt>())
1242     os << "an integer (" << IntVal->getValue() << ")";
1243   else if (Optional<loc::ConcreteInt> ConstAddr = V.getAs<loc::ConcreteInt>())
1244     os << "a constant address (" << ConstAddr->getValue() << ")";
1245   else if (Optional<loc::GotoLabel> Label = V.getAs<loc::GotoLabel>())
1246     os << "the address of the label '" << Label->getLabel()->getName() << "'";
1247   else
1248     return false;
1249
1250   return true;
1251 }
1252
1253 bool MallocChecker::SummarizeRegion(raw_ostream &os,
1254                                     const MemRegion *MR) {
1255   switch (MR->getKind()) {
1256   case MemRegion::FunctionTextRegionKind: {
1257     const NamedDecl *FD = cast<FunctionTextRegion>(MR)->getDecl();
1258     if (FD)
1259       os << "the address of the function '" << *FD << '\'';
1260     else
1261       os << "the address of a function";
1262     return true;
1263   }
1264   case MemRegion::BlockTextRegionKind:
1265     os << "block text";
1266     return true;
1267   case MemRegion::BlockDataRegionKind:
1268     // FIXME: where the block came from?
1269     os << "a block";
1270     return true;
1271   default: {
1272     const MemSpaceRegion *MS = MR->getMemorySpace();
1273
1274     if (isa<StackLocalsSpaceRegion>(MS)) {
1275       const VarRegion *VR = dyn_cast<VarRegion>(MR);
1276       const VarDecl *VD;
1277       if (VR)
1278         VD = VR->getDecl();
1279       else
1280         VD = nullptr;
1281
1282       if (VD)
1283         os << "the address of the local variable '" << VD->getName() << "'";
1284       else
1285         os << "the address of a local stack variable";
1286       return true;
1287     }
1288
1289     if (isa<StackArgumentsSpaceRegion>(MS)) {
1290       const VarRegion *VR = dyn_cast<VarRegion>(MR);
1291       const VarDecl *VD;
1292       if (VR)
1293         VD = VR->getDecl();
1294       else
1295         VD = nullptr;
1296
1297       if (VD)
1298         os << "the address of the parameter '" << VD->getName() << "'";
1299       else
1300         os << "the address of a parameter";
1301       return true;
1302     }
1303
1304     if (isa<GlobalsSpaceRegion>(MS)) {
1305       const VarRegion *VR = dyn_cast<VarRegion>(MR);
1306       const VarDecl *VD;
1307       if (VR)
1308         VD = VR->getDecl();
1309       else
1310         VD = nullptr;
1311
1312       if (VD) {
1313         if (VD->isStaticLocal())
1314           os << "the address of the static variable '" << VD->getName() << "'";
1315         else
1316           os << "the address of the global variable '" << VD->getName() << "'";
1317       } else
1318         os << "the address of a global variable";
1319       return true;
1320     }
1321
1322     return false;
1323   }
1324   }
1325 }
1326
1327 void MallocChecker::ReportBadFree(CheckerContext &C, SVal ArgVal,
1328                                   SourceRange Range,
1329                                   const Expr *DeallocExpr) const {
1330
1331   if (!ChecksEnabled[CK_MallocOptimistic] &&
1332       !ChecksEnabled[CK_MallocPessimistic] &&
1333       !ChecksEnabled[CK_NewDeleteChecker])
1334     return;
1335
1336   Optional<MallocChecker::CheckKind> CheckKind =
1337       getCheckIfTracked(C, DeallocExpr);
1338   if (!CheckKind.hasValue())
1339     return;
1340
1341   if (ExplodedNode *N = C.generateSink()) {
1342     if (!BT_BadFree[*CheckKind])
1343       BT_BadFree[*CheckKind].reset(
1344           new BugType(CheckNames[*CheckKind], "Bad free", "Memory Error"));
1345
1346     SmallString<100> buf;
1347     llvm::raw_svector_ostream os(buf);
1348
1349     const MemRegion *MR = ArgVal.getAsRegion();
1350     while (const ElementRegion *ER = dyn_cast_or_null<ElementRegion>(MR))
1351       MR = ER->getSuperRegion();
1352
1353     if (MR && isa<AllocaRegion>(MR))
1354       os << "Memory allocated by alloca() should not be deallocated";
1355     else {
1356       os << "Argument to ";
1357       if (!printAllocDeallocName(os, C, DeallocExpr))
1358         os << "deallocator";
1359
1360       os << " is ";
1361       bool Summarized = MR ? SummarizeRegion(os, MR)
1362                            : SummarizeValue(os, ArgVal);
1363       if (Summarized)
1364         os << ", which is not memory allocated by ";
1365       else
1366         os << "not memory allocated by ";
1367
1368       printExpectedAllocName(os, C, DeallocExpr);
1369     }
1370
1371     BugReport *R = new BugReport(*BT_BadFree[*CheckKind], os.str(), N);
1372     R->markInteresting(MR);
1373     R->addRange(Range);
1374     C.emitReport(R);
1375   }
1376 }
1377
1378 void MallocChecker::ReportMismatchedDealloc(CheckerContext &C,
1379                                             SourceRange Range,
1380                                             const Expr *DeallocExpr,
1381                                             const RefState *RS,
1382                                             SymbolRef Sym,
1383                                             bool OwnershipTransferred) const {
1384
1385   if (!ChecksEnabled[CK_MismatchedDeallocatorChecker])
1386     return;
1387
1388   if (ExplodedNode *N = C.generateSink()) {
1389     if (!BT_MismatchedDealloc)
1390       BT_MismatchedDealloc.reset(
1391           new BugType(CheckNames[CK_MismatchedDeallocatorChecker],
1392                       "Bad deallocator", "Memory Error"));
1393
1394     SmallString<100> buf;
1395     llvm::raw_svector_ostream os(buf);
1396
1397     const Expr *AllocExpr = cast<Expr>(RS->getStmt());
1398     SmallString<20> AllocBuf;
1399     llvm::raw_svector_ostream AllocOs(AllocBuf);
1400     SmallString<20> DeallocBuf;
1401     llvm::raw_svector_ostream DeallocOs(DeallocBuf);
1402
1403     if (OwnershipTransferred) {
1404       if (printAllocDeallocName(DeallocOs, C, DeallocExpr))
1405         os << DeallocOs.str() << " cannot";
1406       else
1407         os << "Cannot";
1408
1409       os << " take ownership of memory";
1410
1411       if (printAllocDeallocName(AllocOs, C, AllocExpr))
1412         os << " allocated by " << AllocOs.str();
1413     } else {
1414       os << "Memory";
1415       if (printAllocDeallocName(AllocOs, C, AllocExpr))
1416         os << " allocated by " << AllocOs.str();
1417
1418       os << " should be deallocated by ";
1419         printExpectedDeallocName(os, RS->getAllocationFamily());
1420
1421       if (printAllocDeallocName(DeallocOs, C, DeallocExpr))
1422         os << ", not " << DeallocOs.str();
1423     }
1424
1425     BugReport *R = new BugReport(*BT_MismatchedDealloc, os.str(), N);
1426     R->markInteresting(Sym);
1427     R->addRange(Range);
1428     R->addVisitor(new MallocBugVisitor(Sym));
1429     C.emitReport(R);
1430   }
1431 }
1432
1433 void MallocChecker::ReportOffsetFree(CheckerContext &C, SVal ArgVal,
1434                                      SourceRange Range, const Expr *DeallocExpr,
1435                                      const Expr *AllocExpr) const {
1436
1437   if (!ChecksEnabled[CK_MallocOptimistic] &&
1438       !ChecksEnabled[CK_MallocPessimistic] &&
1439       !ChecksEnabled[CK_NewDeleteChecker])
1440     return;
1441
1442   Optional<MallocChecker::CheckKind> CheckKind =
1443       getCheckIfTracked(C, AllocExpr);
1444   if (!CheckKind.hasValue())
1445     return;
1446
1447   ExplodedNode *N = C.generateSink();
1448   if (!N)
1449     return;
1450
1451   if (!BT_OffsetFree[*CheckKind])
1452     BT_OffsetFree[*CheckKind].reset(
1453         new BugType(CheckNames[*CheckKind], "Offset free", "Memory Error"));
1454
1455   SmallString<100> buf;
1456   llvm::raw_svector_ostream os(buf);
1457   SmallString<20> AllocNameBuf;
1458   llvm::raw_svector_ostream AllocNameOs(AllocNameBuf);
1459
1460   const MemRegion *MR = ArgVal.getAsRegion();
1461   assert(MR && "Only MemRegion based symbols can have offset free errors");
1462
1463   RegionOffset Offset = MR->getAsOffset();
1464   assert((Offset.isValid() &&
1465           !Offset.hasSymbolicOffset() &&
1466           Offset.getOffset() != 0) &&
1467          "Only symbols with a valid offset can have offset free errors");
1468
1469   int offsetBytes = Offset.getOffset() / C.getASTContext().getCharWidth();
1470
1471   os << "Argument to ";
1472   if (!printAllocDeallocName(os, C, DeallocExpr))
1473     os << "deallocator";
1474   os << " is offset by "
1475      << offsetBytes
1476      << " "
1477      << ((abs(offsetBytes) > 1) ? "bytes" : "byte")
1478      << " from the start of ";
1479   if (AllocExpr && printAllocDeallocName(AllocNameOs, C, AllocExpr))
1480     os << "memory allocated by " << AllocNameOs.str();
1481   else
1482     os << "allocated memory";
1483
1484   BugReport *R = new BugReport(*BT_OffsetFree[*CheckKind], os.str(), N);
1485   R->markInteresting(MR->getBaseRegion());
1486   R->addRange(Range);
1487   C.emitReport(R);
1488 }
1489
1490 void MallocChecker::ReportUseAfterFree(CheckerContext &C, SourceRange Range,
1491                                        SymbolRef Sym) const {
1492
1493   if (!ChecksEnabled[CK_MallocOptimistic] &&
1494       !ChecksEnabled[CK_MallocPessimistic] &&
1495       !ChecksEnabled[CK_NewDeleteChecker])
1496     return;
1497
1498   Optional<MallocChecker::CheckKind> CheckKind = getCheckIfTracked(C, Sym);
1499   if (!CheckKind.hasValue())
1500     return;
1501
1502   if (ExplodedNode *N = C.generateSink()) {
1503     if (!BT_UseFree[*CheckKind])
1504       BT_UseFree[*CheckKind].reset(new BugType(
1505           CheckNames[*CheckKind], "Use-after-free", "Memory Error"));
1506
1507     BugReport *R = new BugReport(*BT_UseFree[*CheckKind],
1508                                  "Use of memory after it is freed", N);
1509
1510     R->markInteresting(Sym);
1511     R->addRange(Range);
1512     R->addVisitor(new MallocBugVisitor(Sym));
1513     C.emitReport(R);
1514   }
1515 }
1516
1517 void MallocChecker::ReportDoubleFree(CheckerContext &C, SourceRange Range,
1518                                      bool Released, SymbolRef Sym,
1519                                      SymbolRef PrevSym) const {
1520
1521   if (!ChecksEnabled[CK_MallocOptimistic] &&
1522       !ChecksEnabled[CK_MallocPessimistic] &&
1523       !ChecksEnabled[CK_NewDeleteChecker])
1524     return;
1525
1526   Optional<MallocChecker::CheckKind> CheckKind = getCheckIfTracked(C, Sym);
1527   if (!CheckKind.hasValue())
1528     return;
1529
1530   if (ExplodedNode *N = C.generateSink()) {
1531     if (!BT_DoubleFree[*CheckKind])
1532       BT_DoubleFree[*CheckKind].reset(
1533           new BugType(CheckNames[*CheckKind], "Double free", "Memory Error"));
1534
1535     BugReport *R =
1536         new BugReport(*BT_DoubleFree[*CheckKind],
1537                       (Released ? "Attempt to free released memory"
1538                                 : "Attempt to free non-owned memory"),
1539                       N);
1540     R->addRange(Range);
1541     R->markInteresting(Sym);
1542     if (PrevSym)
1543       R->markInteresting(PrevSym);
1544     R->addVisitor(new MallocBugVisitor(Sym));
1545     C.emitReport(R);
1546   }
1547 }
1548
1549 void MallocChecker::ReportDoubleDelete(CheckerContext &C, SymbolRef Sym) const {
1550
1551   if (!ChecksEnabled[CK_NewDeleteChecker])
1552     return;
1553
1554   Optional<MallocChecker::CheckKind> CheckKind = getCheckIfTracked(C, Sym);
1555   if (!CheckKind.hasValue())
1556     return;
1557   assert(*CheckKind == CK_NewDeleteChecker && "invalid check kind");
1558
1559   if (ExplodedNode *N = C.generateSink()) {
1560     if (!BT_DoubleDelete)
1561       BT_DoubleDelete.reset(new BugType(CheckNames[CK_NewDeleteChecker],
1562                                         "Double delete", "Memory Error"));
1563
1564     BugReport *R = new BugReport(*BT_DoubleDelete,
1565                                  "Attempt to delete released memory", N);
1566
1567     R->markInteresting(Sym);
1568     R->addVisitor(new MallocBugVisitor(Sym));
1569     C.emitReport(R);
1570   }
1571 }
1572
1573 ProgramStateRef MallocChecker::ReallocMem(CheckerContext &C,
1574                                           const CallExpr *CE,
1575                                           bool FreesOnFail) const {
1576   if (CE->getNumArgs() < 2)
1577     return nullptr;
1578
1579   ProgramStateRef state = C.getState();
1580   const Expr *arg0Expr = CE->getArg(0);
1581   const LocationContext *LCtx = C.getLocationContext();
1582   SVal Arg0Val = state->getSVal(arg0Expr, LCtx);
1583   if (!Arg0Val.getAs<DefinedOrUnknownSVal>())
1584     return nullptr;
1585   DefinedOrUnknownSVal arg0Val = Arg0Val.castAs<DefinedOrUnknownSVal>();
1586
1587   SValBuilder &svalBuilder = C.getSValBuilder();
1588
1589   DefinedOrUnknownSVal PtrEQ =
1590     svalBuilder.evalEQ(state, arg0Val, svalBuilder.makeNull());
1591
1592   // Get the size argument. If there is no size arg then give up.
1593   const Expr *Arg1 = CE->getArg(1);
1594   if (!Arg1)
1595     return nullptr;
1596
1597   // Get the value of the size argument.
1598   SVal Arg1ValG = state->getSVal(Arg1, LCtx);
1599   if (!Arg1ValG.getAs<DefinedOrUnknownSVal>())
1600     return nullptr;
1601   DefinedOrUnknownSVal Arg1Val = Arg1ValG.castAs<DefinedOrUnknownSVal>();
1602
1603   // Compare the size argument to 0.
1604   DefinedOrUnknownSVal SizeZero =
1605     svalBuilder.evalEQ(state, Arg1Val,
1606                        svalBuilder.makeIntValWithPtrWidth(0, false));
1607
1608   ProgramStateRef StatePtrIsNull, StatePtrNotNull;
1609   std::tie(StatePtrIsNull, StatePtrNotNull) = state->assume(PtrEQ);
1610   ProgramStateRef StateSizeIsZero, StateSizeNotZero;
1611   std::tie(StateSizeIsZero, StateSizeNotZero) = state->assume(SizeZero);
1612   // We only assume exceptional states if they are definitely true; if the
1613   // state is under-constrained, assume regular realloc behavior.
1614   bool PrtIsNull = StatePtrIsNull && !StatePtrNotNull;
1615   bool SizeIsZero = StateSizeIsZero && !StateSizeNotZero;
1616
1617   // If the ptr is NULL and the size is not 0, the call is equivalent to
1618   // malloc(size).
1619   if ( PrtIsNull && !SizeIsZero) {
1620     ProgramStateRef stateMalloc = MallocMemAux(C, CE, CE->getArg(1),
1621                                                UndefinedVal(), StatePtrIsNull);
1622     return stateMalloc;
1623   }
1624
1625   if (PrtIsNull && SizeIsZero)
1626     return nullptr;
1627
1628   // Get the from and to pointer symbols as in toPtr = realloc(fromPtr, size).
1629   assert(!PrtIsNull);
1630   SymbolRef FromPtr = arg0Val.getAsSymbol();
1631   SVal RetVal = state->getSVal(CE, LCtx);
1632   SymbolRef ToPtr = RetVal.getAsSymbol();
1633   if (!FromPtr || !ToPtr)
1634     return nullptr;
1635
1636   bool ReleasedAllocated = false;
1637
1638   // If the size is 0, free the memory.
1639   if (SizeIsZero)
1640     if (ProgramStateRef stateFree = FreeMemAux(C, CE, StateSizeIsZero, 0,
1641                                                false, ReleasedAllocated)){
1642       // The semantics of the return value are:
1643       // If size was equal to 0, either NULL or a pointer suitable to be passed
1644       // to free() is returned. We just free the input pointer and do not add
1645       // any constrains on the output pointer.
1646       return stateFree;
1647     }
1648
1649   // Default behavior.
1650   if (ProgramStateRef stateFree =
1651         FreeMemAux(C, CE, state, 0, false, ReleasedAllocated)) {
1652
1653     ProgramStateRef stateRealloc = MallocMemAux(C, CE, CE->getArg(1),
1654                                                 UnknownVal(), stateFree);
1655     if (!stateRealloc)
1656       return nullptr;
1657
1658     ReallocPairKind Kind = RPToBeFreedAfterFailure;
1659     if (FreesOnFail)
1660       Kind = RPIsFreeOnFailure;
1661     else if (!ReleasedAllocated)
1662       Kind = RPDoNotTrackAfterFailure;
1663
1664     // Record the info about the reallocated symbol so that we could properly
1665     // process failed reallocation.
1666     stateRealloc = stateRealloc->set<ReallocPairs>(ToPtr,
1667                                                    ReallocPair(FromPtr, Kind));
1668     // The reallocated symbol should stay alive for as long as the new symbol.
1669     C.getSymbolManager().addSymbolDependency(ToPtr, FromPtr);
1670     return stateRealloc;
1671   }
1672   return nullptr;
1673 }
1674
1675 ProgramStateRef MallocChecker::CallocMem(CheckerContext &C, const CallExpr *CE){
1676   if (CE->getNumArgs() < 2)
1677     return nullptr;
1678
1679   ProgramStateRef state = C.getState();
1680   SValBuilder &svalBuilder = C.getSValBuilder();
1681   const LocationContext *LCtx = C.getLocationContext();
1682   SVal count = state->getSVal(CE->getArg(0), LCtx);
1683   SVal elementSize = state->getSVal(CE->getArg(1), LCtx);
1684   SVal TotalSize = svalBuilder.evalBinOp(state, BO_Mul, count, elementSize,
1685                                         svalBuilder.getContext().getSizeType());
1686   SVal zeroVal = svalBuilder.makeZeroVal(svalBuilder.getContext().CharTy);
1687
1688   return MallocMemAux(C, CE, TotalSize, zeroVal, state);
1689 }
1690
1691 LeakInfo
1692 MallocChecker::getAllocationSite(const ExplodedNode *N, SymbolRef Sym,
1693                                  CheckerContext &C) const {
1694   const LocationContext *LeakContext = N->getLocationContext();
1695   // Walk the ExplodedGraph backwards and find the first node that referred to
1696   // the tracked symbol.
1697   const ExplodedNode *AllocNode = N;
1698   const MemRegion *ReferenceRegion = nullptr;
1699
1700   while (N) {
1701     ProgramStateRef State = N->getState();
1702     if (!State->get<RegionState>(Sym))
1703       break;
1704
1705     // Find the most recent expression bound to the symbol in the current
1706     // context.
1707       if (!ReferenceRegion) {
1708         if (const MemRegion *MR = C.getLocationRegionIfPostStore(N)) {
1709           SVal Val = State->getSVal(MR);
1710           if (Val.getAsLocSymbol() == Sym) {
1711             const VarRegion* VR = MR->getBaseRegion()->getAs<VarRegion>();
1712             // Do not show local variables belonging to a function other than
1713             // where the error is reported.
1714             if (!VR ||
1715                 (VR->getStackFrame() == LeakContext->getCurrentStackFrame()))
1716               ReferenceRegion = MR;
1717           }
1718         }
1719       }
1720
1721     // Allocation node, is the last node in the current context in which the
1722     // symbol was tracked.
1723     if (N->getLocationContext() == LeakContext)
1724       AllocNode = N;
1725     N = N->pred_empty() ? nullptr : *(N->pred_begin());
1726   }
1727
1728   return LeakInfo(AllocNode, ReferenceRegion);
1729 }
1730
1731 void MallocChecker::reportLeak(SymbolRef Sym, ExplodedNode *N,
1732                                CheckerContext &C) const {
1733
1734   if (!ChecksEnabled[CK_MallocOptimistic] &&
1735       !ChecksEnabled[CK_MallocPessimistic] &&
1736       !ChecksEnabled[CK_NewDeleteLeaksChecker])
1737     return;
1738
1739   const RefState *RS = C.getState()->get<RegionState>(Sym);
1740   assert(RS && "cannot leak an untracked symbol");
1741   AllocationFamily Family = RS->getAllocationFamily();
1742   Optional<MallocChecker::CheckKind> CheckKind = getCheckIfTracked(Family);
1743   if (!CheckKind.hasValue())
1744     return;
1745
1746   // Special case for new and new[]; these are controlled by a separate checker
1747   // flag so that they can be selectively disabled.
1748   if (Family == AF_CXXNew || Family == AF_CXXNewArray)
1749     if (!ChecksEnabled[CK_NewDeleteLeaksChecker])
1750       return;
1751
1752   assert(N);
1753   if (!BT_Leak[*CheckKind]) {
1754     BT_Leak[*CheckKind].reset(
1755         new BugType(CheckNames[*CheckKind], "Memory leak", "Memory Error"));
1756     // Leaks should not be reported if they are post-dominated by a sink:
1757     // (1) Sinks are higher importance bugs.
1758     // (2) NoReturnFunctionChecker uses sink nodes to represent paths ending
1759     //     with __noreturn functions such as assert() or exit(). We choose not
1760     //     to report leaks on such paths.
1761     BT_Leak[*CheckKind]->setSuppressOnSink(true);
1762   }
1763
1764   // Most bug reports are cached at the location where they occurred.
1765   // With leaks, we want to unique them by the location where they were
1766   // allocated, and only report a single path.
1767   PathDiagnosticLocation LocUsedForUniqueing;
1768   const ExplodedNode *AllocNode = nullptr;
1769   const MemRegion *Region = nullptr;
1770   std::tie(AllocNode, Region) = getAllocationSite(N, Sym, C);
1771
1772   ProgramPoint P = AllocNode->getLocation();
1773   const Stmt *AllocationStmt = nullptr;
1774   if (Optional<CallExitEnd> Exit = P.getAs<CallExitEnd>())
1775     AllocationStmt = Exit->getCalleeContext()->getCallSite();
1776   else if (Optional<StmtPoint> SP = P.getAs<StmtPoint>())
1777     AllocationStmt = SP->getStmt();
1778   if (AllocationStmt)
1779     LocUsedForUniqueing = PathDiagnosticLocation::createBegin(AllocationStmt,
1780                                               C.getSourceManager(),
1781                                               AllocNode->getLocationContext());
1782
1783   SmallString<200> buf;
1784   llvm::raw_svector_ostream os(buf);
1785   if (Region && Region->canPrintPretty()) {
1786     os << "Potential leak of memory pointed to by ";
1787     Region->printPretty(os);
1788   } else {
1789     os << "Potential memory leak";
1790   }
1791
1792   BugReport *R =
1793       new BugReport(*BT_Leak[*CheckKind], os.str(), N, LocUsedForUniqueing,
1794                     AllocNode->getLocationContext()->getDecl());
1795   R->markInteresting(Sym);
1796   R->addVisitor(new MallocBugVisitor(Sym, true));
1797   C.emitReport(R);
1798 }
1799
1800 void MallocChecker::checkDeadSymbols(SymbolReaper &SymReaper,
1801                                      CheckerContext &C) const
1802 {
1803   if (!SymReaper.hasDeadSymbols())
1804     return;
1805
1806   ProgramStateRef state = C.getState();
1807   RegionStateTy RS = state->get<RegionState>();
1808   RegionStateTy::Factory &F = state->get_context<RegionState>();
1809
1810   SmallVector<SymbolRef, 2> Errors;
1811   for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
1812     if (SymReaper.isDead(I->first)) {
1813       if (I->second.isAllocated())
1814         Errors.push_back(I->first);
1815       // Remove the dead symbol from the map.
1816       RS = F.remove(RS, I->first);
1817
1818     }
1819   }
1820
1821   // Cleanup the Realloc Pairs Map.
1822   ReallocPairsTy RP = state->get<ReallocPairs>();
1823   for (ReallocPairsTy::iterator I = RP.begin(), E = RP.end(); I != E; ++I) {
1824     if (SymReaper.isDead(I->first) ||
1825         SymReaper.isDead(I->second.ReallocatedSym)) {
1826       state = state->remove<ReallocPairs>(I->first);
1827     }
1828   }
1829
1830   // Cleanup the FreeReturnValue Map.
1831   FreeReturnValueTy FR = state->get<FreeReturnValue>();
1832   for (FreeReturnValueTy::iterator I = FR.begin(), E = FR.end(); I != E; ++I) {
1833     if (SymReaper.isDead(I->first) ||
1834         SymReaper.isDead(I->second)) {
1835       state = state->remove<FreeReturnValue>(I->first);
1836     }
1837   }
1838
1839   // Generate leak node.
1840   ExplodedNode *N = C.getPredecessor();
1841   if (!Errors.empty()) {
1842     static CheckerProgramPointTag Tag("MallocChecker", "DeadSymbolsLeak");
1843     N = C.addTransition(C.getState(), C.getPredecessor(), &Tag);
1844     for (SmallVectorImpl<SymbolRef>::iterator
1845            I = Errors.begin(), E = Errors.end(); I != E; ++I) {
1846       reportLeak(*I, N, C);
1847     }
1848   }
1849
1850   C.addTransition(state->set<RegionState>(RS), N);
1851 }
1852
1853 void MallocChecker::checkPreCall(const CallEvent &Call,
1854                                  CheckerContext &C) const {
1855
1856   if (const CXXDestructorCall *DC = dyn_cast<CXXDestructorCall>(&Call)) {
1857     SymbolRef Sym = DC->getCXXThisVal().getAsSymbol();
1858     if (!Sym || checkDoubleDelete(Sym, C))
1859       return;
1860   }
1861
1862   // We will check for double free in the post visit.
1863   if (const AnyFunctionCall *FC = dyn_cast<AnyFunctionCall>(&Call)) {
1864     const FunctionDecl *FD = FC->getDecl();
1865     if (!FD)
1866       return;
1867
1868     if ((ChecksEnabled[CK_MallocOptimistic] ||
1869          ChecksEnabled[CK_MallocPessimistic]) &&
1870         isFreeFunction(FD, C.getASTContext()))
1871       return;
1872
1873     if (ChecksEnabled[CK_NewDeleteChecker] &&
1874         isStandardNewDelete(FD, C.getASTContext()))
1875       return;
1876   }
1877
1878   // Check if the callee of a method is deleted.
1879   if (const CXXInstanceCall *CC = dyn_cast<CXXInstanceCall>(&Call)) {
1880     SymbolRef Sym = CC->getCXXThisVal().getAsSymbol();
1881     if (!Sym || checkUseAfterFree(Sym, C, CC->getCXXThisExpr()))
1882       return;
1883   }
1884
1885   // Check arguments for being used after free.
1886   for (unsigned I = 0, E = Call.getNumArgs(); I != E; ++I) {
1887     SVal ArgSVal = Call.getArgSVal(I);
1888     if (ArgSVal.getAs<Loc>()) {
1889       SymbolRef Sym = ArgSVal.getAsSymbol();
1890       if (!Sym)
1891         continue;
1892       if (checkUseAfterFree(Sym, C, Call.getArgExpr(I)))
1893         return;
1894     }
1895   }
1896 }
1897
1898 void MallocChecker::checkPreStmt(const ReturnStmt *S, CheckerContext &C) const {
1899   const Expr *E = S->getRetValue();
1900   if (!E)
1901     return;
1902
1903   // Check if we are returning a symbol.
1904   ProgramStateRef State = C.getState();
1905   SVal RetVal = State->getSVal(E, C.getLocationContext());
1906   SymbolRef Sym = RetVal.getAsSymbol();
1907   if (!Sym)
1908     // If we are returning a field of the allocated struct or an array element,
1909     // the callee could still free the memory.
1910     // TODO: This logic should be a part of generic symbol escape callback.
1911     if (const MemRegion *MR = RetVal.getAsRegion())
1912       if (isa<FieldRegion>(MR) || isa<ElementRegion>(MR))
1913         if (const SymbolicRegion *BMR =
1914               dyn_cast<SymbolicRegion>(MR->getBaseRegion()))
1915           Sym = BMR->getSymbol();
1916
1917   // Check if we are returning freed memory.
1918   if (Sym)
1919     checkUseAfterFree(Sym, C, E);
1920 }
1921
1922 // TODO: Blocks should be either inlined or should call invalidate regions
1923 // upon invocation. After that's in place, special casing here will not be
1924 // needed.
1925 void MallocChecker::checkPostStmt(const BlockExpr *BE,
1926                                   CheckerContext &C) const {
1927
1928   // Scan the BlockDecRefExprs for any object the retain count checker
1929   // may be tracking.
1930   if (!BE->getBlockDecl()->hasCaptures())
1931     return;
1932
1933   ProgramStateRef state = C.getState();
1934   const BlockDataRegion *R =
1935     cast<BlockDataRegion>(state->getSVal(BE,
1936                                          C.getLocationContext()).getAsRegion());
1937
1938   BlockDataRegion::referenced_vars_iterator I = R->referenced_vars_begin(),
1939                                             E = R->referenced_vars_end();
1940
1941   if (I == E)
1942     return;
1943
1944   SmallVector<const MemRegion*, 10> Regions;
1945   const LocationContext *LC = C.getLocationContext();
1946   MemRegionManager &MemMgr = C.getSValBuilder().getRegionManager();
1947
1948   for ( ; I != E; ++I) {
1949     const VarRegion *VR = I.getCapturedRegion();
1950     if (VR->getSuperRegion() == R) {
1951       VR = MemMgr.getVarRegion(VR->getDecl(), LC);
1952     }
1953     Regions.push_back(VR);
1954   }
1955
1956   state =
1957     state->scanReachableSymbols<StopTrackingCallback>(Regions.data(),
1958                                     Regions.data() + Regions.size()).getState();
1959   C.addTransition(state);
1960 }
1961
1962 bool MallocChecker::isReleased(SymbolRef Sym, CheckerContext &C) const {
1963   assert(Sym);
1964   const RefState *RS = C.getState()->get<RegionState>(Sym);
1965   return (RS && RS->isReleased());
1966 }
1967
1968 bool MallocChecker::checkUseAfterFree(SymbolRef Sym, CheckerContext &C,
1969                                       const Stmt *S) const {
1970
1971   if (isReleased(Sym, C)) {
1972     ReportUseAfterFree(C, S->getSourceRange(), Sym);
1973     return true;
1974   }
1975
1976   return false;
1977 }
1978
1979 bool MallocChecker::checkDoubleDelete(SymbolRef Sym, CheckerContext &C) const {
1980
1981   if (isReleased(Sym, C)) {
1982     ReportDoubleDelete(C, Sym);
1983     return true;
1984   }
1985   return false;
1986 }
1987
1988 // Check if the location is a freed symbolic region.
1989 void MallocChecker::checkLocation(SVal l, bool isLoad, const Stmt *S,
1990                                   CheckerContext &C) const {
1991   SymbolRef Sym = l.getLocSymbolInBase();
1992   if (Sym)
1993     checkUseAfterFree(Sym, C, S);
1994 }
1995
1996 // If a symbolic region is assumed to NULL (or another constant), stop tracking
1997 // it - assuming that allocation failed on this path.
1998 ProgramStateRef MallocChecker::evalAssume(ProgramStateRef state,
1999                                               SVal Cond,
2000                                               bool Assumption) const {
2001   RegionStateTy RS = state->get<RegionState>();
2002   for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
2003     // If the symbol is assumed to be NULL, remove it from consideration.
2004     ConstraintManager &CMgr = state->getConstraintManager();
2005     ConditionTruthVal AllocFailed = CMgr.isNull(state, I.getKey());
2006     if (AllocFailed.isConstrainedTrue())
2007       state = state->remove<RegionState>(I.getKey());
2008   }
2009
2010   // Realloc returns 0 when reallocation fails, which means that we should
2011   // restore the state of the pointer being reallocated.
2012   ReallocPairsTy RP = state->get<ReallocPairs>();
2013   for (ReallocPairsTy::iterator I = RP.begin(), E = RP.end(); I != E; ++I) {
2014     // If the symbol is assumed to be NULL, remove it from consideration.
2015     ConstraintManager &CMgr = state->getConstraintManager();
2016     ConditionTruthVal AllocFailed = CMgr.isNull(state, I.getKey());
2017     if (!AllocFailed.isConstrainedTrue())
2018       continue;
2019
2020     SymbolRef ReallocSym = I.getData().ReallocatedSym;
2021     if (const RefState *RS = state->get<RegionState>(ReallocSym)) {
2022       if (RS->isReleased()) {
2023         if (I.getData().Kind == RPToBeFreedAfterFailure)
2024           state = state->set<RegionState>(ReallocSym,
2025               RefState::getAllocated(RS->getAllocationFamily(), RS->getStmt()));
2026         else if (I.getData().Kind == RPDoNotTrackAfterFailure)
2027           state = state->remove<RegionState>(ReallocSym);
2028         else
2029           assert(I.getData().Kind == RPIsFreeOnFailure);
2030       }
2031     }
2032     state = state->remove<ReallocPairs>(I.getKey());
2033   }
2034
2035   return state;
2036 }
2037
2038 bool MallocChecker::mayFreeAnyEscapedMemoryOrIsModeledExplicitly(
2039                                               const CallEvent *Call,
2040                                               ProgramStateRef State,
2041                                               SymbolRef &EscapingSymbol) const {
2042   assert(Call);
2043   EscapingSymbol = nullptr;
2044
2045   // For now, assume that any C++ or block call can free memory.
2046   // TODO: If we want to be more optimistic here, we'll need to make sure that
2047   // regions escape to C++ containers. They seem to do that even now, but for
2048   // mysterious reasons.
2049   if (!(isa<SimpleFunctionCall>(Call) || isa<ObjCMethodCall>(Call)))
2050     return true;
2051
2052   // Check Objective-C messages by selector name.
2053   if (const ObjCMethodCall *Msg = dyn_cast<ObjCMethodCall>(Call)) {
2054     // If it's not a framework call, or if it takes a callback, assume it
2055     // can free memory.
2056     if (!Call->isInSystemHeader() || Call->hasNonZeroCallbackArg())
2057       return true;
2058
2059     // If it's a method we know about, handle it explicitly post-call.
2060     // This should happen before the "freeWhenDone" check below.
2061     if (isKnownDeallocObjCMethodName(*Msg))
2062       return false;
2063
2064     // If there's a "freeWhenDone" parameter, but the method isn't one we know
2065     // about, we can't be sure that the object will use free() to deallocate the
2066     // memory, so we can't model it explicitly. The best we can do is use it to
2067     // decide whether the pointer escapes.
2068     if (Optional<bool> FreeWhenDone = getFreeWhenDoneArg(*Msg))
2069       return *FreeWhenDone;
2070
2071     // If the first selector piece ends with "NoCopy", and there is no
2072     // "freeWhenDone" parameter set to zero, we know ownership is being
2073     // transferred. Again, though, we can't be sure that the object will use
2074     // free() to deallocate the memory, so we can't model it explicitly.
2075     StringRef FirstSlot = Msg->getSelector().getNameForSlot(0);
2076     if (FirstSlot.endswith("NoCopy"))
2077       return true;
2078
2079     // If the first selector starts with addPointer, insertPointer,
2080     // or replacePointer, assume we are dealing with NSPointerArray or similar.
2081     // This is similar to C++ containers (vector); we still might want to check
2082     // that the pointers get freed by following the container itself.
2083     if (FirstSlot.startswith("addPointer") ||
2084         FirstSlot.startswith("insertPointer") ||
2085         FirstSlot.startswith("replacePointer") ||
2086         FirstSlot.equals("valueWithPointer")) {
2087       return true;
2088     }
2089
2090     // We should escape receiver on call to 'init'. This is especially relevant
2091     // to the receiver, as the corresponding symbol is usually not referenced
2092     // after the call.
2093     if (Msg->getMethodFamily() == OMF_init) {
2094       EscapingSymbol = Msg->getReceiverSVal().getAsSymbol();
2095       return true;
2096     }
2097
2098     // Otherwise, assume that the method does not free memory.
2099     // Most framework methods do not free memory.
2100     return false;
2101   }
2102
2103   // At this point the only thing left to handle is straight function calls.
2104   const FunctionDecl *FD = cast<SimpleFunctionCall>(Call)->getDecl();
2105   if (!FD)
2106     return true;
2107
2108   ASTContext &ASTC = State->getStateManager().getContext();
2109
2110   // If it's one of the allocation functions we can reason about, we model
2111   // its behavior explicitly.
2112   if (isMemFunction(FD, ASTC))
2113     return false;
2114
2115   // If it's not a system call, assume it frees memory.
2116   if (!Call->isInSystemHeader())
2117     return true;
2118
2119   // White list the system functions whose arguments escape.
2120   const IdentifierInfo *II = FD->getIdentifier();
2121   if (!II)
2122     return true;
2123   StringRef FName = II->getName();
2124
2125   // White list the 'XXXNoCopy' CoreFoundation functions.
2126   // We specifically check these before
2127   if (FName.endswith("NoCopy")) {
2128     // Look for the deallocator argument. We know that the memory ownership
2129     // is not transferred only if the deallocator argument is
2130     // 'kCFAllocatorNull'.
2131     for (unsigned i = 1; i < Call->getNumArgs(); ++i) {
2132       const Expr *ArgE = Call->getArgExpr(i)->IgnoreParenCasts();
2133       if (const DeclRefExpr *DE = dyn_cast<DeclRefExpr>(ArgE)) {
2134         StringRef DeallocatorName = DE->getFoundDecl()->getName();
2135         if (DeallocatorName == "kCFAllocatorNull")
2136           return false;
2137       }
2138     }
2139     return true;
2140   }
2141
2142   // Associating streams with malloced buffers. The pointer can escape if
2143   // 'closefn' is specified (and if that function does free memory),
2144   // but it will not if closefn is not specified.
2145   // Currently, we do not inspect the 'closefn' function (PR12101).
2146   if (FName == "funopen")
2147     if (Call->getNumArgs() >= 4 && Call->getArgSVal(4).isConstant(0))
2148       return false;
2149
2150   // Do not warn on pointers passed to 'setbuf' when used with std streams,
2151   // these leaks might be intentional when setting the buffer for stdio.
2152   // http://stackoverflow.com/questions/2671151/who-frees-setvbuf-buffer
2153   if (FName == "setbuf" || FName =="setbuffer" ||
2154       FName == "setlinebuf" || FName == "setvbuf") {
2155     if (Call->getNumArgs() >= 1) {
2156       const Expr *ArgE = Call->getArgExpr(0)->IgnoreParenCasts();
2157       if (const DeclRefExpr *ArgDRE = dyn_cast<DeclRefExpr>(ArgE))
2158         if (const VarDecl *D = dyn_cast<VarDecl>(ArgDRE->getDecl()))
2159           if (D->getCanonicalDecl()->getName().find("std") != StringRef::npos)
2160             return true;
2161     }
2162   }
2163
2164   // A bunch of other functions which either take ownership of a pointer or
2165   // wrap the result up in a struct or object, meaning it can be freed later.
2166   // (See RetainCountChecker.) Not all the parameters here are invalidated,
2167   // but the Malloc checker cannot differentiate between them. The right way
2168   // of doing this would be to implement a pointer escapes callback.
2169   if (FName == "CGBitmapContextCreate" ||
2170       FName == "CGBitmapContextCreateWithData" ||
2171       FName == "CVPixelBufferCreateWithBytes" ||
2172       FName == "CVPixelBufferCreateWithPlanarBytes" ||
2173       FName == "OSAtomicEnqueue") {
2174     return true;
2175   }
2176
2177   // Handle cases where we know a buffer's /address/ can escape.
2178   // Note that the above checks handle some special cases where we know that
2179   // even though the address escapes, it's still our responsibility to free the
2180   // buffer.
2181   if (Call->argumentsMayEscape())
2182     return true;
2183
2184   // Otherwise, assume that the function does not free memory.
2185   // Most system calls do not free the memory.
2186   return false;
2187 }
2188
2189 static bool retTrue(const RefState *RS) {
2190   return true;
2191 }
2192
2193 static bool checkIfNewOrNewArrayFamily(const RefState *RS) {
2194   return (RS->getAllocationFamily() == AF_CXXNewArray ||
2195           RS->getAllocationFamily() == AF_CXXNew);
2196 }
2197
2198 ProgramStateRef MallocChecker::checkPointerEscape(ProgramStateRef State,
2199                                              const InvalidatedSymbols &Escaped,
2200                                              const CallEvent *Call,
2201                                              PointerEscapeKind Kind) const {
2202   return checkPointerEscapeAux(State, Escaped, Call, Kind, &retTrue);
2203 }
2204
2205 ProgramStateRef MallocChecker::checkConstPointerEscape(ProgramStateRef State,
2206                                               const InvalidatedSymbols &Escaped,
2207                                               const CallEvent *Call,
2208                                               PointerEscapeKind Kind) const {
2209   return checkPointerEscapeAux(State, Escaped, Call, Kind,
2210                                &checkIfNewOrNewArrayFamily);
2211 }
2212
2213 ProgramStateRef MallocChecker::checkPointerEscapeAux(ProgramStateRef State,
2214                                               const InvalidatedSymbols &Escaped,
2215                                               const CallEvent *Call,
2216                                               PointerEscapeKind Kind,
2217                                   bool(*CheckRefState)(const RefState*)) const {
2218   // If we know that the call does not free memory, or we want to process the
2219   // call later, keep tracking the top level arguments.
2220   SymbolRef EscapingSymbol = nullptr;
2221   if (Kind == PSK_DirectEscapeOnCall &&
2222       !mayFreeAnyEscapedMemoryOrIsModeledExplicitly(Call, State,
2223                                                     EscapingSymbol) &&
2224       !EscapingSymbol) {
2225     return State;
2226   }
2227
2228   for (InvalidatedSymbols::const_iterator I = Escaped.begin(),
2229        E = Escaped.end();
2230        I != E; ++I) {
2231     SymbolRef sym = *I;
2232
2233     if (EscapingSymbol && EscapingSymbol != sym)
2234       continue;
2235
2236     if (const RefState *RS = State->get<RegionState>(sym)) {
2237       if (RS->isAllocated() && CheckRefState(RS)) {
2238         State = State->remove<RegionState>(sym);
2239         State = State->set<RegionState>(sym, RefState::getEscaped(RS));
2240       }
2241     }
2242   }
2243   return State;
2244 }
2245
2246 static SymbolRef findFailedReallocSymbol(ProgramStateRef currState,
2247                                          ProgramStateRef prevState) {
2248   ReallocPairsTy currMap = currState->get<ReallocPairs>();
2249   ReallocPairsTy prevMap = prevState->get<ReallocPairs>();
2250
2251   for (ReallocPairsTy::iterator I = prevMap.begin(), E = prevMap.end();
2252        I != E; ++I) {
2253     SymbolRef sym = I.getKey();
2254     if (!currMap.lookup(sym))
2255       return sym;
2256   }
2257
2258   return nullptr;
2259 }
2260
2261 PathDiagnosticPiece *
2262 MallocChecker::MallocBugVisitor::VisitNode(const ExplodedNode *N,
2263                                            const ExplodedNode *PrevN,
2264                                            BugReporterContext &BRC,
2265                                            BugReport &BR) {
2266   ProgramStateRef state = N->getState();
2267   ProgramStateRef statePrev = PrevN->getState();
2268
2269   const RefState *RS = state->get<RegionState>(Sym);
2270   const RefState *RSPrev = statePrev->get<RegionState>(Sym);
2271   if (!RS)
2272     return nullptr;
2273
2274   const Stmt *S = nullptr;
2275   const char *Msg = nullptr;
2276   StackHintGeneratorForSymbol *StackHint = nullptr;
2277
2278   // Retrieve the associated statement.
2279   ProgramPoint ProgLoc = N->getLocation();
2280   if (Optional<StmtPoint> SP = ProgLoc.getAs<StmtPoint>()) {
2281     S = SP->getStmt();
2282   } else if (Optional<CallExitEnd> Exit = ProgLoc.getAs<CallExitEnd>()) {
2283     S = Exit->getCalleeContext()->getCallSite();
2284   } else if (Optional<BlockEdge> Edge = ProgLoc.getAs<BlockEdge>()) {
2285     // If an assumption was made on a branch, it should be caught
2286     // here by looking at the state transition.
2287     S = Edge->getSrc()->getTerminator();
2288   }
2289
2290   if (!S)
2291     return nullptr;
2292
2293   // FIXME: We will eventually need to handle non-statement-based events
2294   // (__attribute__((cleanup))).
2295
2296   // Find out if this is an interesting point and what is the kind.
2297   if (Mode == Normal) {
2298     if (isAllocated(RS, RSPrev, S)) {
2299       Msg = "Memory is allocated";
2300       StackHint = new StackHintGeneratorForSymbol(Sym,
2301                                                   "Returned allocated memory");
2302     } else if (isReleased(RS, RSPrev, S)) {
2303       Msg = "Memory is released";
2304       StackHint = new StackHintGeneratorForSymbol(Sym,
2305                                              "Returning; memory was released");
2306     } else if (isRelinquished(RS, RSPrev, S)) {
2307       Msg = "Memory ownership is transferred";
2308       StackHint = new StackHintGeneratorForSymbol(Sym, "");
2309     } else if (isReallocFailedCheck(RS, RSPrev, S)) {
2310       Mode = ReallocationFailed;
2311       Msg = "Reallocation failed";
2312       StackHint = new StackHintGeneratorForReallocationFailed(Sym,
2313                                                        "Reallocation failed");
2314
2315       if (SymbolRef sym = findFailedReallocSymbol(state, statePrev)) {
2316         // Is it possible to fail two reallocs WITHOUT testing in between?
2317         assert((!FailedReallocSymbol || FailedReallocSymbol == sym) &&
2318           "We only support one failed realloc at a time.");
2319         BR.markInteresting(sym);
2320         FailedReallocSymbol = sym;
2321       }
2322     }
2323
2324   // We are in a special mode if a reallocation failed later in the path.
2325   } else if (Mode == ReallocationFailed) {
2326     assert(FailedReallocSymbol && "No symbol to look for.");
2327
2328     // Is this is the first appearance of the reallocated symbol?
2329     if (!statePrev->get<RegionState>(FailedReallocSymbol)) {
2330       // We're at the reallocation point.
2331       Msg = "Attempt to reallocate memory";
2332       StackHint = new StackHintGeneratorForSymbol(Sym,
2333                                                  "Returned reallocated memory");
2334       FailedReallocSymbol = nullptr;
2335       Mode = Normal;
2336     }
2337   }
2338
2339   if (!Msg)
2340     return nullptr;
2341   assert(StackHint);
2342
2343   // Generate the extra diagnostic.
2344   PathDiagnosticLocation Pos(S, BRC.getSourceManager(),
2345                              N->getLocationContext());
2346   return new PathDiagnosticEventPiece(Pos, Msg, true, StackHint);
2347 }
2348
2349 void MallocChecker::printState(raw_ostream &Out, ProgramStateRef State,
2350                                const char *NL, const char *Sep) const {
2351
2352   RegionStateTy RS = State->get<RegionState>();
2353
2354   if (!RS.isEmpty()) {
2355     Out << Sep << "MallocChecker :" << NL;
2356     for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
2357       const RefState *RefS = State->get<RegionState>(I.getKey());
2358       AllocationFamily Family = RefS->getAllocationFamily();
2359       Optional<MallocChecker::CheckKind> CheckKind = getCheckIfTracked(Family);
2360
2361       I.getKey()->dumpToStream(Out);
2362       Out << " : ";
2363       I.getData().dump(Out);
2364       if (CheckKind.hasValue())
2365         Out << " (" << CheckNames[*CheckKind].getName() << ")";
2366       Out << NL;
2367     }
2368   }
2369 }
2370
2371 void ento::registerNewDeleteLeaksChecker(CheckerManager &mgr) {
2372   registerCStringCheckerBasic(mgr);
2373   MallocChecker *checker = mgr.registerChecker<MallocChecker>();
2374   checker->ChecksEnabled[MallocChecker::CK_NewDeleteLeaksChecker] = true;
2375   checker->CheckNames[MallocChecker::CK_NewDeleteLeaksChecker] =
2376       mgr.getCurrentCheckName();
2377   // We currently treat NewDeleteLeaks checker as a subchecker of NewDelete
2378   // checker.
2379   if (!checker->ChecksEnabled[MallocChecker::CK_NewDeleteChecker])
2380     checker->ChecksEnabled[MallocChecker::CK_NewDeleteChecker] = true;
2381 }
2382
2383 #define REGISTER_CHECKER(name)                                                 \
2384   void ento::register##name(CheckerManager &mgr) {                             \
2385     registerCStringCheckerBasic(mgr);                                          \
2386     MallocChecker *checker = mgr.registerChecker<MallocChecker>();             \
2387     checker->ChecksEnabled[MallocChecker::CK_##name] = true;                   \
2388     checker->CheckNames[MallocChecker::CK_##name] = mgr.getCurrentCheckName(); \
2389   }
2390
2391 REGISTER_CHECKER(MallocPessimistic)
2392 REGISTER_CHECKER(MallocOptimistic)
2393 REGISTER_CHECKER(NewDeleteChecker)
2394 REGISTER_CHECKER(MismatchedDeallocatorChecker)