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