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