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