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