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