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