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