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