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