xref: /llvm-project/clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp (revision b34366091413a8021e21bd7ae1656bf74d1ef54c)
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/StaticAnalyzer/Core/Checker.h"
18 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
19 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
20 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
21 #include "clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h"
22 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
23 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
24 #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
25 #include "clang/Basic/SourceManager.h"
26 #include "llvm/ADT/ImmutableMap.h"
27 #include "llvm/ADT/SmallString.h"
28 #include "llvm/ADT/STLExtras.h"
29 #include <climits>
30 
31 using namespace clang;
32 using namespace ento;
33 
34 namespace {
35 
36 class RefState {
37   enum Kind { AllocateUnchecked, AllocateFailed, Released, Escaped,
38               Relinquished } K;
39   const Stmt *S;
40 
41 public:
42   RefState(Kind k, const Stmt *s) : K(k), S(s) {}
43 
44   bool isAllocated() const { return K == AllocateUnchecked; }
45   bool isReleased() const { return K == Released; }
46 
47   const Stmt *getStmt() const { return S; }
48 
49   bool operator==(const RefState &X) const {
50     return K == X.K && S == X.S;
51   }
52 
53   static RefState getAllocateUnchecked(const Stmt *s) {
54     return RefState(AllocateUnchecked, s);
55   }
56   static RefState getAllocateFailed() {
57     return RefState(AllocateFailed, 0);
58   }
59   static RefState getReleased(const Stmt *s) { return RefState(Released, s); }
60   static RefState getEscaped(const Stmt *s) { return RefState(Escaped, s); }
61   static RefState getRelinquished(const Stmt *s) {
62     return RefState(Relinquished, s);
63   }
64 
65   void Profile(llvm::FoldingSetNodeID &ID) const {
66     ID.AddInteger(K);
67     ID.AddPointer(S);
68   }
69 };
70 
71 struct ReallocPair {
72   SymbolRef ReallocatedSym;
73   bool IsFreeOnFailure;
74   ReallocPair(SymbolRef S, bool F) : ReallocatedSym(S), IsFreeOnFailure(F) {}
75   void Profile(llvm::FoldingSetNodeID &ID) const {
76     ID.AddInteger(IsFreeOnFailure);
77     ID.AddPointer(ReallocatedSym);
78   }
79   bool operator==(const ReallocPair &X) const {
80     return ReallocatedSym == X.ReallocatedSym &&
81            IsFreeOnFailure == X.IsFreeOnFailure;
82   }
83 };
84 
85 typedef std::pair<const Stmt*, const MemRegion*> LeakInfo;
86 
87 class MallocChecker : public Checker<check::DeadSymbols,
88                                      check::EndPath,
89                                      check::PreStmt<ReturnStmt>,
90                                      check::PreStmt<CallExpr>,
91                                      check::PostStmt<CallExpr>,
92                                      check::PostStmt<BlockExpr>,
93                                      check::Location,
94                                      check::Bind,
95                                      eval::Assume,
96                                      check::RegionChanges>
97 {
98   mutable OwningPtr<BugType> BT_DoubleFree;
99   mutable OwningPtr<BugType> BT_Leak;
100   mutable OwningPtr<BugType> BT_UseFree;
101   mutable OwningPtr<BugType> BT_BadFree;
102   mutable IdentifierInfo *II_malloc, *II_free, *II_realloc, *II_calloc,
103                          *II_valloc, *II_reallocf, *II_strndup, *II_strdup;
104 
105 public:
106   MallocChecker() : II_malloc(0), II_free(0), II_realloc(0), II_calloc(0),
107                     II_valloc(0), II_reallocf(0), II_strndup(0), II_strdup(0) {}
108 
109   /// In pessimistic mode, the checker assumes that it does not know which
110   /// functions might free the memory.
111   struct ChecksFilter {
112     DefaultBool CMallocPessimistic;
113     DefaultBool CMallocOptimistic;
114   };
115 
116   ChecksFilter Filter;
117 
118   void checkPreStmt(const CallExpr *S, CheckerContext &C) const;
119   void checkPostStmt(const CallExpr *CE, CheckerContext &C) const;
120   void checkPostStmt(const BlockExpr *BE, CheckerContext &C) const;
121   void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const;
122   void checkEndPath(CheckerContext &C) const;
123   void checkPreStmt(const ReturnStmt *S, CheckerContext &C) const;
124   ProgramStateRef evalAssume(ProgramStateRef state, SVal Cond,
125                             bool Assumption) const;
126   void checkLocation(SVal l, bool isLoad, const Stmt *S,
127                      CheckerContext &C) const;
128   void checkBind(SVal location, SVal val, const Stmt*S,
129                  CheckerContext &C) const;
130   ProgramStateRef
131   checkRegionChanges(ProgramStateRef state,
132                      const StoreManager::InvalidatedSymbols *invalidated,
133                      ArrayRef<const MemRegion *> ExplicitRegions,
134                      ArrayRef<const MemRegion *> Regions,
135                      const CallOrObjCMessage *Call) const;
136   bool wantsRegionChangeUpdate(ProgramStateRef state) const {
137     return true;
138   }
139 
140   void printState(raw_ostream &Out, ProgramStateRef State,
141                   const char *NL, const char *Sep) const;
142 
143 private:
144   void initIdentifierInfo(ASTContext &C) const;
145 
146   /// Check if this is one of the functions which can allocate/reallocate memory
147   /// pointed to by one of its arguments.
148   bool isMemFunction(const FunctionDecl *FD, ASTContext &C) const;
149   bool isFreeFunction(const FunctionDecl *FD, ASTContext &C) const;
150   bool isAllocationFunction(const FunctionDecl *FD, ASTContext &C) const;
151 
152   static ProgramStateRef MallocMemReturnsAttr(CheckerContext &C,
153                                               const CallExpr *CE,
154                                               const OwnershipAttr* Att);
155   static ProgramStateRef MallocMemAux(CheckerContext &C, const CallExpr *CE,
156                                      const Expr *SizeEx, SVal Init,
157                                      ProgramStateRef state) {
158     return MallocMemAux(C, CE,
159                         state->getSVal(SizeEx, C.getLocationContext()),
160                         Init, state);
161   }
162 
163   static ProgramStateRef MallocMemAux(CheckerContext &C, const CallExpr *CE,
164                                      SVal SizeEx, SVal Init,
165                                      ProgramStateRef state);
166 
167   /// Update the RefState to reflect the new memory allocation.
168   static ProgramStateRef MallocUpdateRefState(CheckerContext &C,
169                                               const CallExpr *CE,
170                                               ProgramStateRef state);
171 
172   ProgramStateRef FreeMemAttr(CheckerContext &C, const CallExpr *CE,
173                               const OwnershipAttr* Att) const;
174   ProgramStateRef FreeMemAux(CheckerContext &C, const CallExpr *CE,
175                                  ProgramStateRef state, unsigned Num,
176                                  bool Hold) const;
177 
178   ProgramStateRef ReallocMem(CheckerContext &C, const CallExpr *CE,
179                              bool FreesMemOnFailure) const;
180   static ProgramStateRef CallocMem(CheckerContext &C, const CallExpr *CE);
181 
182   ///\brief Check if the memory associated with this symbol was released.
183   bool isReleased(SymbolRef Sym, CheckerContext &C) const;
184 
185   bool checkEscape(SymbolRef Sym, const Stmt *S, CheckerContext &C) const;
186   bool checkUseAfterFree(SymbolRef Sym, CheckerContext &C,
187                          const Stmt *S = 0) const;
188 
189   /// Check if the function is not known to us. So, for example, we could
190   /// conservatively assume it can free/reallocate it's pointer arguments.
191   bool doesNotFreeMemory(const CallOrObjCMessage *Call,
192                          ProgramStateRef State) const;
193 
194   static bool SummarizeValue(raw_ostream &os, SVal V);
195   static bool SummarizeRegion(raw_ostream &os, const MemRegion *MR);
196   void ReportBadFree(CheckerContext &C, SVal ArgVal, SourceRange range) const;
197 
198   /// Find the location of the allocation for Sym on the path leading to the
199   /// exploded node N.
200   LeakInfo getAllocationSite(const ExplodedNode *N, SymbolRef Sym,
201                              CheckerContext &C) const;
202 
203   void reportLeak(SymbolRef Sym, ExplodedNode *N, CheckerContext &C) const;
204 
205   /// The bug visitor which allows us to print extra diagnostics along the
206   /// BugReport path. For example, showing the allocation site of the leaked
207   /// region.
208   class MallocBugVisitor : public BugReporterVisitorImpl<MallocBugVisitor> {
209   protected:
210     enum NotificationMode {
211       Normal,
212       ReallocationFailed
213     };
214 
215     // The allocated region symbol tracked by the main analysis.
216     SymbolRef Sym;
217 
218     // The mode we are in, i.e. what kind of diagnostics will be emitted.
219     NotificationMode Mode;
220 
221     // A symbol from when the primary region should have been reallocated.
222     SymbolRef FailedReallocSymbol;
223 
224     bool IsLeak;
225 
226   public:
227     MallocBugVisitor(SymbolRef S, bool isLeak = false)
228        : Sym(S), Mode(Normal), FailedReallocSymbol(0), IsLeak(isLeak) {}
229 
230     virtual ~MallocBugVisitor() {}
231 
232     void Profile(llvm::FoldingSetNodeID &ID) const {
233       static int X = 0;
234       ID.AddPointer(&X);
235       ID.AddPointer(Sym);
236     }
237 
238     inline bool isAllocated(const RefState *S, const RefState *SPrev,
239                             const Stmt *Stmt) {
240       // Did not track -> allocated. Other state (released) -> allocated.
241       return (Stmt && isa<CallExpr>(Stmt) &&
242               (S && S->isAllocated()) && (!SPrev || !SPrev->isAllocated()));
243     }
244 
245     inline bool isReleased(const RefState *S, const RefState *SPrev,
246                            const Stmt *Stmt) {
247       // Did not track -> released. Other state (allocated) -> released.
248       return (Stmt && isa<CallExpr>(Stmt) &&
249               (S && S->isReleased()) && (!SPrev || !SPrev->isReleased()));
250     }
251 
252     inline bool isReallocFailedCheck(const RefState *S, const RefState *SPrev,
253                                      const Stmt *Stmt) {
254       // If the expression is not a call, and the state change is
255       // released -> allocated, it must be the realloc return value
256       // check. If we have to handle more cases here, it might be cleaner just
257       // to track this extra bit in the state itself.
258       return ((!Stmt || !isa<CallExpr>(Stmt)) &&
259               (S && S->isAllocated()) && (SPrev && !SPrev->isAllocated()));
260     }
261 
262     PathDiagnosticPiece *VisitNode(const ExplodedNode *N,
263                                    const ExplodedNode *PrevN,
264                                    BugReporterContext &BRC,
265                                    BugReport &BR);
266 
267     PathDiagnosticPiece* getEndPath(BugReporterContext &BRC,
268                                     const ExplodedNode *EndPathNode,
269                                     BugReport &BR) {
270       if (!IsLeak)
271         return 0;
272 
273       PathDiagnosticLocation L =
274         PathDiagnosticLocation::createEndOfPath(EndPathNode,
275                                                 BRC.getSourceManager());
276       // Do not add the statement itself as a range in case of leak.
277       return new PathDiagnosticEventPiece(L, BR.getDescription(), false);
278     }
279 
280   private:
281     class StackHintGeneratorForReallocationFailed
282         : public StackHintGeneratorForSymbol {
283     public:
284       StackHintGeneratorForReallocationFailed(SymbolRef S, StringRef M)
285         : StackHintGeneratorForSymbol(S, M) {}
286 
287       virtual std::string getMessageForArg(const Expr *ArgE, unsigned ArgIndex) {
288         SmallString<200> buf;
289         llvm::raw_svector_ostream os(buf);
290 
291         os << "Reallocation of ";
292         // Printed parameters start at 1, not 0.
293         printOrdinal(++ArgIndex, os);
294         os << " parameter failed";
295 
296         return os.str();
297       }
298 
299       virtual std::string getMessageForReturn(const CallExpr *CallExpr) {
300         return "Reallocation of returned value failed";
301       }
302     };
303   };
304 };
305 } // end anonymous namespace
306 
307 typedef llvm::ImmutableMap<SymbolRef, RefState> RegionStateTy;
308 typedef llvm::ImmutableMap<SymbolRef, ReallocPair > ReallocMap;
309 class RegionState {};
310 class ReallocPairs {};
311 namespace clang {
312 namespace ento {
313   template <>
314   struct ProgramStateTrait<RegionState>
315     : public ProgramStatePartialTrait<RegionStateTy> {
316     static void *GDMIndex() { static int x; return &x; }
317   };
318 
319   template <>
320   struct ProgramStateTrait<ReallocPairs>
321     : public ProgramStatePartialTrait<ReallocMap> {
322     static void *GDMIndex() { static int x; return &x; }
323   };
324 }
325 }
326 
327 namespace {
328 class StopTrackingCallback : public SymbolVisitor {
329   ProgramStateRef state;
330 public:
331   StopTrackingCallback(ProgramStateRef st) : state(st) {}
332   ProgramStateRef getState() const { return state; }
333 
334   bool VisitSymbol(SymbolRef sym) {
335     state = state->remove<RegionState>(sym);
336     return true;
337   }
338 };
339 } // end anonymous namespace
340 
341 void MallocChecker::initIdentifierInfo(ASTContext &Ctx) const {
342   if (II_malloc)
343     return;
344   II_malloc = &Ctx.Idents.get("malloc");
345   II_free = &Ctx.Idents.get("free");
346   II_realloc = &Ctx.Idents.get("realloc");
347   II_reallocf = &Ctx.Idents.get("reallocf");
348   II_calloc = &Ctx.Idents.get("calloc");
349   II_valloc = &Ctx.Idents.get("valloc");
350   II_strdup = &Ctx.Idents.get("strdup");
351   II_strndup = &Ctx.Idents.get("strndup");
352 }
353 
354 bool MallocChecker::isMemFunction(const FunctionDecl *FD, ASTContext &C) const {
355   if (isFreeFunction(FD, C))
356     return true;
357 
358   if (isAllocationFunction(FD, C))
359     return true;
360 
361   return false;
362 }
363 
364 bool MallocChecker::isAllocationFunction(const FunctionDecl *FD,
365                                          ASTContext &C) const {
366   if (!FD)
367     return false;
368 
369   IdentifierInfo *FunI = FD->getIdentifier();
370   if (!FunI)
371     return false;
372 
373   initIdentifierInfo(C);
374 
375   if (FunI == II_malloc || FunI == II_realloc ||
376       FunI == II_reallocf || FunI == II_calloc || FunI == II_valloc ||
377       FunI == II_strdup || FunI == II_strndup)
378     return true;
379 
380   if (Filter.CMallocOptimistic && FD->hasAttrs())
381     for (specific_attr_iterator<OwnershipAttr>
382            i = FD->specific_attr_begin<OwnershipAttr>(),
383            e = FD->specific_attr_end<OwnershipAttr>();
384            i != e; ++i)
385       if ((*i)->getOwnKind() == OwnershipAttr::Returns)
386         return true;
387   return false;
388 }
389 
390 bool MallocChecker::isFreeFunction(const FunctionDecl *FD, ASTContext &C) const {
391   if (!FD)
392     return false;
393 
394   IdentifierInfo *FunI = FD->getIdentifier();
395   if (!FunI)
396     return false;
397 
398   initIdentifierInfo(C);
399 
400   if (FunI == II_free || FunI == II_realloc || FunI == II_reallocf)
401     return true;
402 
403   if (Filter.CMallocOptimistic && FD->hasAttrs())
404     for (specific_attr_iterator<OwnershipAttr>
405            i = FD->specific_attr_begin<OwnershipAttr>(),
406            e = FD->specific_attr_end<OwnershipAttr>();
407            i != e; ++i)
408       if ((*i)->getOwnKind() == OwnershipAttr::Takes ||
409           (*i)->getOwnKind() == OwnershipAttr::Holds)
410         return true;
411   return false;
412 }
413 
414 void MallocChecker::checkPostStmt(const CallExpr *CE, CheckerContext &C) const {
415   const FunctionDecl *FD = C.getCalleeDecl(CE);
416   if (!FD)
417     return;
418 
419   initIdentifierInfo(C.getASTContext());
420   IdentifierInfo *FunI = FD->getIdentifier();
421   if (!FunI)
422     return;
423 
424   ProgramStateRef State = C.getState();
425   if (FunI == II_malloc || FunI == II_valloc) {
426     if (CE->getNumArgs() < 1)
427       return;
428     State = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(), State);
429   } else if (FunI == II_realloc) {
430     State = ReallocMem(C, CE, false);
431   } else if (FunI == II_reallocf) {
432     State = ReallocMem(C, CE, true);
433   } else if (FunI == II_calloc) {
434     State = CallocMem(C, CE);
435   } else if (FunI == II_free) {
436     State = FreeMemAux(C, CE, C.getState(), 0, false);
437   } else if (FunI == II_strdup) {
438     State = MallocUpdateRefState(C, CE, State);
439   } else if (FunI == II_strndup) {
440     State = MallocUpdateRefState(C, CE, State);
441   } else if (Filter.CMallocOptimistic) {
442     // Check all the attributes, if there are any.
443     // There can be multiple of these attributes.
444     if (FD->hasAttrs())
445       for (specific_attr_iterator<OwnershipAttr>
446           i = FD->specific_attr_begin<OwnershipAttr>(),
447           e = FD->specific_attr_end<OwnershipAttr>();
448           i != e; ++i) {
449         switch ((*i)->getOwnKind()) {
450         case OwnershipAttr::Returns:
451           State = MallocMemReturnsAttr(C, CE, *i);
452           break;
453         case OwnershipAttr::Takes:
454         case OwnershipAttr::Holds:
455           State = FreeMemAttr(C, CE, *i);
456           break;
457         }
458       }
459   }
460   C.addTransition(State);
461 }
462 
463 ProgramStateRef MallocChecker::MallocMemReturnsAttr(CheckerContext &C,
464                                                     const CallExpr *CE,
465                                                     const OwnershipAttr* Att) {
466   if (Att->getModule() != "malloc")
467     return 0;
468 
469   OwnershipAttr::args_iterator I = Att->args_begin(), E = Att->args_end();
470   if (I != E) {
471     return MallocMemAux(C, CE, CE->getArg(*I), UndefinedVal(), C.getState());
472   }
473   return MallocMemAux(C, CE, UnknownVal(), UndefinedVal(), C.getState());
474 }
475 
476 ProgramStateRef MallocChecker::MallocMemAux(CheckerContext &C,
477                                            const CallExpr *CE,
478                                            SVal Size, SVal Init,
479                                            ProgramStateRef state) {
480   // Get the return value.
481   SVal retVal = state->getSVal(CE, C.getLocationContext());
482 
483   // We expect the malloc functions to return a pointer.
484   if (!isa<Loc>(retVal))
485     return 0;
486 
487   // Fill the region with the initialization value.
488   state = state->bindDefault(retVal, Init);
489 
490   // Set the region's extent equal to the Size parameter.
491   const SymbolicRegion *R =
492       dyn_cast_or_null<SymbolicRegion>(retVal.getAsRegion());
493   if (!R)
494     return 0;
495   if (isa<DefinedOrUnknownSVal>(Size)) {
496     SValBuilder &svalBuilder = C.getSValBuilder();
497     DefinedOrUnknownSVal Extent = R->getExtent(svalBuilder);
498     DefinedOrUnknownSVal DefinedSize = cast<DefinedOrUnknownSVal>(Size);
499     DefinedOrUnknownSVal extentMatchesSize =
500         svalBuilder.evalEQ(state, Extent, DefinedSize);
501 
502     state = state->assume(extentMatchesSize, true);
503     assert(state);
504   }
505 
506   return MallocUpdateRefState(C, CE, state);
507 }
508 
509 ProgramStateRef MallocChecker::MallocUpdateRefState(CheckerContext &C,
510                                                     const CallExpr *CE,
511                                                     ProgramStateRef state) {
512   // Get the return value.
513   SVal retVal = state->getSVal(CE, C.getLocationContext());
514 
515   // We expect the malloc functions to return a pointer.
516   if (!isa<Loc>(retVal))
517     return 0;
518 
519   SymbolRef Sym = retVal.getAsLocSymbol();
520   assert(Sym);
521 
522   // Set the symbol's state to Allocated.
523   return state->set<RegionState>(Sym, RefState::getAllocateUnchecked(CE));
524 
525 }
526 
527 ProgramStateRef MallocChecker::FreeMemAttr(CheckerContext &C,
528                                            const CallExpr *CE,
529                                            const OwnershipAttr* Att) const {
530   if (Att->getModule() != "malloc")
531     return 0;
532 
533   ProgramStateRef State = C.getState();
534 
535   for (OwnershipAttr::args_iterator I = Att->args_begin(), E = Att->args_end();
536        I != E; ++I) {
537     ProgramStateRef StateI = FreeMemAux(C, CE, State, *I,
538                                Att->getOwnKind() == OwnershipAttr::Holds);
539     if (StateI)
540       State = StateI;
541   }
542   return State;
543 }
544 
545 ProgramStateRef MallocChecker::FreeMemAux(CheckerContext &C,
546                                           const CallExpr *CE,
547                                           ProgramStateRef state,
548                                           unsigned Num,
549                                           bool Hold) const {
550   if (CE->getNumArgs() < (Num + 1))
551     return 0;
552 
553   const Expr *ArgExpr = CE->getArg(Num);
554   SVal ArgVal = state->getSVal(ArgExpr, C.getLocationContext());
555   if (!isa<DefinedOrUnknownSVal>(ArgVal))
556     return 0;
557   DefinedOrUnknownSVal location = cast<DefinedOrUnknownSVal>(ArgVal);
558 
559   // Check for null dereferences.
560   if (!isa<Loc>(location))
561     return 0;
562 
563   // The explicit NULL case, no operation is performed.
564   ProgramStateRef notNullState, nullState;
565   llvm::tie(notNullState, nullState) = state->assume(location);
566   if (nullState && !notNullState)
567     return 0;
568 
569   // Unknown values could easily be okay
570   // Undefined values are handled elsewhere
571   if (ArgVal.isUnknownOrUndef())
572     return 0;
573 
574   const MemRegion *R = ArgVal.getAsRegion();
575 
576   // Nonlocs can't be freed, of course.
577   // Non-region locations (labels and fixed addresses) also shouldn't be freed.
578   if (!R) {
579     ReportBadFree(C, ArgVal, ArgExpr->getSourceRange());
580     return 0;
581   }
582 
583   R = R->StripCasts();
584 
585   // Blocks might show up as heap data, but should not be free()d
586   if (isa<BlockDataRegion>(R)) {
587     ReportBadFree(C, ArgVal, ArgExpr->getSourceRange());
588     return 0;
589   }
590 
591   const MemSpaceRegion *MS = R->getMemorySpace();
592 
593   // Parameters, locals, statics, and globals shouldn't be freed.
594   if (!(isa<UnknownSpaceRegion>(MS) || isa<HeapSpaceRegion>(MS))) {
595     // FIXME: at the time this code was written, malloc() regions were
596     // represented by conjured symbols, which are all in UnknownSpaceRegion.
597     // This means that there isn't actually anything from HeapSpaceRegion
598     // that should be freed, even though we allow it here.
599     // Of course, free() can work on memory allocated outside the current
600     // function, so UnknownSpaceRegion is always a possibility.
601     // False negatives are better than false positives.
602 
603     ReportBadFree(C, ArgVal, ArgExpr->getSourceRange());
604     return 0;
605   }
606 
607   const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R);
608   // Various cases could lead to non-symbol values here.
609   // For now, ignore them.
610   if (!SR)
611     return 0;
612 
613   SymbolRef Sym = SR->getSymbol();
614   const RefState *RS = state->get<RegionState>(Sym);
615 
616   // If the symbol has not been tracked, return. This is possible when free() is
617   // called on a pointer that does not get its pointee directly from malloc().
618   // Full support of this requires inter-procedural analysis.
619   if (!RS)
620     return 0;
621 
622   // Check double free.
623   if (RS->isReleased()) {
624     if (ExplodedNode *N = C.generateSink()) {
625       if (!BT_DoubleFree)
626         BT_DoubleFree.reset(
627           new BugType("Double free", "Memory Error"));
628       BugReport *R = new BugReport(*BT_DoubleFree,
629                         "Attempt to free released memory", N);
630       R->addRange(ArgExpr->getSourceRange());
631       R->markInteresting(Sym);
632       R->addVisitor(new MallocBugVisitor(Sym));
633       C.EmitReport(R);
634     }
635     return 0;
636   }
637 
638   // Normal free.
639   if (Hold)
640     return state->set<RegionState>(Sym, RefState::getRelinquished(CE));
641   return state->set<RegionState>(Sym, RefState::getReleased(CE));
642 }
643 
644 bool MallocChecker::SummarizeValue(raw_ostream &os, SVal V) {
645   if (nonloc::ConcreteInt *IntVal = dyn_cast<nonloc::ConcreteInt>(&V))
646     os << "an integer (" << IntVal->getValue() << ")";
647   else if (loc::ConcreteInt *ConstAddr = dyn_cast<loc::ConcreteInt>(&V))
648     os << "a constant address (" << ConstAddr->getValue() << ")";
649   else if (loc::GotoLabel *Label = dyn_cast<loc::GotoLabel>(&V))
650     os << "the address of the label '" << Label->getLabel()->getName() << "'";
651   else
652     return false;
653 
654   return true;
655 }
656 
657 bool MallocChecker::SummarizeRegion(raw_ostream &os,
658                                     const MemRegion *MR) {
659   switch (MR->getKind()) {
660   case MemRegion::FunctionTextRegionKind: {
661     const FunctionDecl *FD = cast<FunctionTextRegion>(MR)->getDecl();
662     if (FD)
663       os << "the address of the function '" << *FD << '\'';
664     else
665       os << "the address of a function";
666     return true;
667   }
668   case MemRegion::BlockTextRegionKind:
669     os << "block text";
670     return true;
671   case MemRegion::BlockDataRegionKind:
672     // FIXME: where the block came from?
673     os << "a block";
674     return true;
675   default: {
676     const MemSpaceRegion *MS = MR->getMemorySpace();
677 
678     if (isa<StackLocalsSpaceRegion>(MS)) {
679       const VarRegion *VR = dyn_cast<VarRegion>(MR);
680       const VarDecl *VD;
681       if (VR)
682         VD = VR->getDecl();
683       else
684         VD = NULL;
685 
686       if (VD)
687         os << "the address of the local variable '" << VD->getName() << "'";
688       else
689         os << "the address of a local stack variable";
690       return true;
691     }
692 
693     if (isa<StackArgumentsSpaceRegion>(MS)) {
694       const VarRegion *VR = dyn_cast<VarRegion>(MR);
695       const VarDecl *VD;
696       if (VR)
697         VD = VR->getDecl();
698       else
699         VD = NULL;
700 
701       if (VD)
702         os << "the address of the parameter '" << VD->getName() << "'";
703       else
704         os << "the address of a parameter";
705       return true;
706     }
707 
708     if (isa<GlobalsSpaceRegion>(MS)) {
709       const VarRegion *VR = dyn_cast<VarRegion>(MR);
710       const VarDecl *VD;
711       if (VR)
712         VD = VR->getDecl();
713       else
714         VD = NULL;
715 
716       if (VD) {
717         if (VD->isStaticLocal())
718           os << "the address of the static variable '" << VD->getName() << "'";
719         else
720           os << "the address of the global variable '" << VD->getName() << "'";
721       } else
722         os << "the address of a global variable";
723       return true;
724     }
725 
726     return false;
727   }
728   }
729 }
730 
731 void MallocChecker::ReportBadFree(CheckerContext &C, SVal ArgVal,
732                                   SourceRange range) const {
733   if (ExplodedNode *N = C.generateSink()) {
734     if (!BT_BadFree)
735       BT_BadFree.reset(new BugType("Bad free", "Memory Error"));
736 
737     SmallString<100> buf;
738     llvm::raw_svector_ostream os(buf);
739 
740     const MemRegion *MR = ArgVal.getAsRegion();
741     if (MR) {
742       while (const ElementRegion *ER = dyn_cast<ElementRegion>(MR))
743         MR = ER->getSuperRegion();
744 
745       // Special case for alloca()
746       if (isa<AllocaRegion>(MR))
747         os << "Argument to free() was allocated by alloca(), not malloc()";
748       else {
749         os << "Argument to free() is ";
750         if (SummarizeRegion(os, MR))
751           os << ", which is not memory allocated by malloc()";
752         else
753           os << "not memory allocated by malloc()";
754       }
755     } else {
756       os << "Argument to free() is ";
757       if (SummarizeValue(os, ArgVal))
758         os << ", which is not memory allocated by malloc()";
759       else
760         os << "not memory allocated by malloc()";
761     }
762 
763     BugReport *R = new BugReport(*BT_BadFree, os.str(), N);
764     R->markInteresting(MR);
765     R->addRange(range);
766     C.EmitReport(R);
767   }
768 }
769 
770 ProgramStateRef MallocChecker::ReallocMem(CheckerContext &C,
771                                           const CallExpr *CE,
772                                           bool FreesOnFail) const {
773   if (CE->getNumArgs() < 2)
774     return 0;
775 
776   ProgramStateRef state = C.getState();
777   const Expr *arg0Expr = CE->getArg(0);
778   const LocationContext *LCtx = C.getLocationContext();
779   SVal Arg0Val = state->getSVal(arg0Expr, LCtx);
780   if (!isa<DefinedOrUnknownSVal>(Arg0Val))
781     return 0;
782   DefinedOrUnknownSVal arg0Val = cast<DefinedOrUnknownSVal>(Arg0Val);
783 
784   SValBuilder &svalBuilder = C.getSValBuilder();
785 
786   DefinedOrUnknownSVal PtrEQ =
787     svalBuilder.evalEQ(state, arg0Val, svalBuilder.makeNull());
788 
789   // Get the size argument. If there is no size arg then give up.
790   const Expr *Arg1 = CE->getArg(1);
791   if (!Arg1)
792     return 0;
793 
794   // Get the value of the size argument.
795   SVal Arg1ValG = state->getSVal(Arg1, LCtx);
796   if (!isa<DefinedOrUnknownSVal>(Arg1ValG))
797     return 0;
798   DefinedOrUnknownSVal Arg1Val = cast<DefinedOrUnknownSVal>(Arg1ValG);
799 
800   // Compare the size argument to 0.
801   DefinedOrUnknownSVal SizeZero =
802     svalBuilder.evalEQ(state, Arg1Val,
803                        svalBuilder.makeIntValWithPtrWidth(0, false));
804 
805   ProgramStateRef StatePtrIsNull, StatePtrNotNull;
806   llvm::tie(StatePtrIsNull, StatePtrNotNull) = state->assume(PtrEQ);
807   ProgramStateRef StateSizeIsZero, StateSizeNotZero;
808   llvm::tie(StateSizeIsZero, StateSizeNotZero) = state->assume(SizeZero);
809   // We only assume exceptional states if they are definitely true; if the
810   // state is under-constrained, assume regular realloc behavior.
811   bool PrtIsNull = StatePtrIsNull && !StatePtrNotNull;
812   bool SizeIsZero = StateSizeIsZero && !StateSizeNotZero;
813 
814   // If the ptr is NULL and the size is not 0, the call is equivalent to
815   // malloc(size).
816   if ( PrtIsNull && !SizeIsZero) {
817     ProgramStateRef stateMalloc = MallocMemAux(C, CE, CE->getArg(1),
818                                                UndefinedVal(), StatePtrIsNull);
819     return stateMalloc;
820   }
821 
822   if (PrtIsNull && SizeIsZero)
823     return 0;
824 
825   // Get the from and to pointer symbols as in toPtr = realloc(fromPtr, size).
826   assert(!PrtIsNull);
827   SymbolRef FromPtr = arg0Val.getAsSymbol();
828   SVal RetVal = state->getSVal(CE, LCtx);
829   SymbolRef ToPtr = RetVal.getAsSymbol();
830   if (!FromPtr || !ToPtr)
831     return 0;
832 
833   // If the size is 0, free the memory.
834   if (SizeIsZero)
835     if (ProgramStateRef stateFree = FreeMemAux(C, CE, StateSizeIsZero,0,false)){
836       // The semantics of the return value are:
837       // If size was equal to 0, either NULL or a pointer suitable to be passed
838       // to free() is returned.
839       stateFree = stateFree->set<ReallocPairs>(ToPtr,
840                                             ReallocPair(FromPtr, FreesOnFail));
841       C.getSymbolManager().addSymbolDependency(ToPtr, FromPtr);
842       return stateFree;
843     }
844 
845   // Default behavior.
846   if (ProgramStateRef stateFree = FreeMemAux(C, CE, state, 0, false)) {
847     // FIXME: We should copy the content of the original buffer.
848     ProgramStateRef stateRealloc = MallocMemAux(C, CE, CE->getArg(1),
849                                                 UnknownVal(), stateFree);
850     if (!stateRealloc)
851       return 0;
852     stateRealloc = stateRealloc->set<ReallocPairs>(ToPtr,
853                                             ReallocPair(FromPtr, FreesOnFail));
854     C.getSymbolManager().addSymbolDependency(ToPtr, FromPtr);
855     return stateRealloc;
856   }
857   return 0;
858 }
859 
860 ProgramStateRef MallocChecker::CallocMem(CheckerContext &C, const CallExpr *CE){
861   if (CE->getNumArgs() < 2)
862     return 0;
863 
864   ProgramStateRef state = C.getState();
865   SValBuilder &svalBuilder = C.getSValBuilder();
866   const LocationContext *LCtx = C.getLocationContext();
867   SVal count = state->getSVal(CE->getArg(0), LCtx);
868   SVal elementSize = state->getSVal(CE->getArg(1), LCtx);
869   SVal TotalSize = svalBuilder.evalBinOp(state, BO_Mul, count, elementSize,
870                                         svalBuilder.getContext().getSizeType());
871   SVal zeroVal = svalBuilder.makeZeroVal(svalBuilder.getContext().CharTy);
872 
873   return MallocMemAux(C, CE, TotalSize, zeroVal, state);
874 }
875 
876 LeakInfo
877 MallocChecker::getAllocationSite(const ExplodedNode *N, SymbolRef Sym,
878                                  CheckerContext &C) const {
879   const LocationContext *LeakContext = N->getLocationContext();
880   // Walk the ExplodedGraph backwards and find the first node that referred to
881   // the tracked symbol.
882   const ExplodedNode *AllocNode = N;
883   const MemRegion *ReferenceRegion = 0;
884 
885   while (N) {
886     ProgramStateRef State = N->getState();
887     if (!State->get<RegionState>(Sym))
888       break;
889 
890     // Find the most recent expression bound to the symbol in the current
891     // context.
892     if (!ReferenceRegion) {
893       if (const MemRegion *MR = C.getLocationRegionIfPostStore(N)) {
894         SVal Val = State->getSVal(MR);
895         if (Val.getAsLocSymbol() == Sym)
896           ReferenceRegion = MR;
897       }
898     }
899 
900     // Allocation node, is the last node in the current context in which the
901     // symbol was tracked.
902     if (N->getLocationContext() == LeakContext)
903       AllocNode = N;
904     N = N->pred_empty() ? NULL : *(N->pred_begin());
905   }
906 
907   ProgramPoint P = AllocNode->getLocation();
908   const Stmt *AllocationStmt = 0;
909   if (isa<StmtPoint>(P))
910     AllocationStmt = cast<StmtPoint>(P).getStmt();
911 
912   return LeakInfo(AllocationStmt, ReferenceRegion);
913 }
914 
915 void MallocChecker::reportLeak(SymbolRef Sym, ExplodedNode *N,
916                                CheckerContext &C) const {
917   assert(N);
918   if (!BT_Leak) {
919     BT_Leak.reset(new BugType("Memory leak", "Memory Error"));
920     // Leaks should not be reported if they are post-dominated by a sink:
921     // (1) Sinks are higher importance bugs.
922     // (2) NoReturnFunctionChecker uses sink nodes to represent paths ending
923     //     with __noreturn functions such as assert() or exit(). We choose not
924     //     to report leaks on such paths.
925     BT_Leak->setSuppressOnSink(true);
926   }
927 
928   // Most bug reports are cached at the location where they occurred.
929   // With leaks, we want to unique them by the location where they were
930   // allocated, and only report a single path.
931   PathDiagnosticLocation LocUsedForUniqueing;
932   const Stmt *AllocStmt = 0;
933   const MemRegion *Region = 0;
934   llvm::tie(AllocStmt, Region) = getAllocationSite(N, Sym, C);
935   if (AllocStmt)
936     LocUsedForUniqueing = PathDiagnosticLocation::createBegin(AllocStmt,
937                             C.getSourceManager(), N->getLocationContext());
938 
939   SmallString<200> buf;
940   llvm::raw_svector_ostream os(buf);
941   os << "Memory is never released; potential leak";
942   if (Region) {
943     os << " of memory pointed to by '";
944     Region->dumpPretty(os);
945     os <<'\'';
946   }
947 
948   BugReport *R = new BugReport(*BT_Leak, os.str(), N, LocUsedForUniqueing);
949   R->markInteresting(Sym);
950   R->addVisitor(new MallocBugVisitor(Sym, true));
951   C.EmitReport(R);
952 }
953 
954 void MallocChecker::checkDeadSymbols(SymbolReaper &SymReaper,
955                                      CheckerContext &C) const
956 {
957   if (!SymReaper.hasDeadSymbols())
958     return;
959 
960   ProgramStateRef state = C.getState();
961   RegionStateTy RS = state->get<RegionState>();
962   RegionStateTy::Factory &F = state->get_context<RegionState>();
963 
964   bool generateReport = false;
965   llvm::SmallVector<SymbolRef, 2> Errors;
966   for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
967     if (SymReaper.isDead(I->first)) {
968       if (I->second.isAllocated()) {
969         generateReport = true;
970         Errors.push_back(I->first);
971       }
972       // Remove the dead symbol from the map.
973       RS = F.remove(RS, I->first);
974 
975     }
976   }
977 
978   // Cleanup the Realloc Pairs Map.
979   ReallocMap RP = state->get<ReallocPairs>();
980   for (ReallocMap::iterator I = RP.begin(), E = RP.end(); I != E; ++I) {
981     if (SymReaper.isDead(I->first) ||
982         SymReaper.isDead(I->second.ReallocatedSym)) {
983       state = state->remove<ReallocPairs>(I->first);
984     }
985   }
986 
987   // Generate leak node.
988   static SimpleProgramPointTag Tag("MallocChecker : DeadSymbolsLeak");
989   ExplodedNode *N = C.addTransition(C.getState(), C.getPredecessor(), &Tag);
990 
991   if (generateReport) {
992     for (llvm::SmallVector<SymbolRef, 2>::iterator
993          I = Errors.begin(), E = Errors.end(); I != E; ++I) {
994       reportLeak(*I, N, C);
995     }
996   }
997   C.addTransition(state->set<RegionState>(RS), N);
998 }
999 
1000 void MallocChecker::checkEndPath(CheckerContext &C) const {
1001   ProgramStateRef state = C.getState();
1002   RegionStateTy M = state->get<RegionState>();
1003 
1004   // If inside inlined call, skip it.
1005   if (C.getLocationContext()->getParent() != 0)
1006     return;
1007 
1008   for (RegionStateTy::iterator I = M.begin(), E = M.end(); I != E; ++I) {
1009     RefState RS = I->second;
1010     if (RS.isAllocated()) {
1011       ExplodedNode *N = C.addTransition(state);
1012       if (N)
1013         reportLeak(I->first, N, C);
1014     }
1015   }
1016 }
1017 
1018 bool MallocChecker::checkEscape(SymbolRef Sym, const Stmt *S,
1019                                 CheckerContext &C) const {
1020   ProgramStateRef state = C.getState();
1021   const RefState *RS = state->get<RegionState>(Sym);
1022   if (!RS)
1023     return false;
1024 
1025   if (RS->isAllocated()) {
1026     state = state->set<RegionState>(Sym, RefState::getEscaped(S));
1027     C.addTransition(state);
1028     return true;
1029   }
1030   return false;
1031 }
1032 
1033 void MallocChecker::checkPreStmt(const CallExpr *CE, CheckerContext &C) const {
1034   // We will check for double free in the post visit.
1035   if (isFreeFunction(C.getCalleeDecl(CE), C.getASTContext()))
1036     return;
1037 
1038   // Check use after free, when a freed pointer is passed to a call.
1039   ProgramStateRef State = C.getState();
1040   for (CallExpr::const_arg_iterator I = CE->arg_begin(),
1041                                     E = CE->arg_end(); I != E; ++I) {
1042     const Expr *A = *I;
1043     if (A->getType().getTypePtr()->isAnyPointerType()) {
1044       SymbolRef Sym = State->getSVal(A, C.getLocationContext()).getAsSymbol();
1045       if (!Sym)
1046         continue;
1047       if (checkUseAfterFree(Sym, C, A))
1048         return;
1049     }
1050   }
1051 }
1052 
1053 void MallocChecker::checkPreStmt(const ReturnStmt *S, CheckerContext &C) const {
1054   const Expr *E = S->getRetValue();
1055   if (!E)
1056     return;
1057 
1058   // Check if we are returning a symbol.
1059   SVal RetVal = C.getState()->getSVal(E, C.getLocationContext());
1060   SymbolRef Sym = RetVal.getAsSymbol();
1061   if (!Sym)
1062     // If we are returning a field of the allocated struct or an array element,
1063     // the callee could still free the memory.
1064     // TODO: This logic should be a part of generic symbol escape callback.
1065     if (const MemRegion *MR = RetVal.getAsRegion())
1066       if (isa<FieldRegion>(MR) || isa<ElementRegion>(MR))
1067         if (const SymbolicRegion *BMR =
1068               dyn_cast<SymbolicRegion>(MR->getBaseRegion()))
1069           Sym = BMR->getSymbol();
1070   if (!Sym)
1071     return;
1072 
1073   // Check if we are returning freed memory.
1074   if (checkUseAfterFree(Sym, C, E))
1075     return;
1076 
1077   // If this function body is not inlined, check if the symbol is escaping.
1078   if (C.getLocationContext()->getParent() == 0)
1079     checkEscape(Sym, E, C);
1080 }
1081 
1082 // TODO: Blocks should be either inlined or should call invalidate regions
1083 // upon invocation. After that's in place, special casing here will not be
1084 // needed.
1085 void MallocChecker::checkPostStmt(const BlockExpr *BE,
1086                                   CheckerContext &C) const {
1087 
1088   // Scan the BlockDecRefExprs for any object the retain count checker
1089   // may be tracking.
1090   if (!BE->getBlockDecl()->hasCaptures())
1091     return;
1092 
1093   ProgramStateRef state = C.getState();
1094   const BlockDataRegion *R =
1095     cast<BlockDataRegion>(state->getSVal(BE,
1096                                          C.getLocationContext()).getAsRegion());
1097 
1098   BlockDataRegion::referenced_vars_iterator I = R->referenced_vars_begin(),
1099                                             E = R->referenced_vars_end();
1100 
1101   if (I == E)
1102     return;
1103 
1104   SmallVector<const MemRegion*, 10> Regions;
1105   const LocationContext *LC = C.getLocationContext();
1106   MemRegionManager &MemMgr = C.getSValBuilder().getRegionManager();
1107 
1108   for ( ; I != E; ++I) {
1109     const VarRegion *VR = *I;
1110     if (VR->getSuperRegion() == R) {
1111       VR = MemMgr.getVarRegion(VR->getDecl(), LC);
1112     }
1113     Regions.push_back(VR);
1114   }
1115 
1116   state =
1117     state->scanReachableSymbols<StopTrackingCallback>(Regions.data(),
1118                                     Regions.data() + Regions.size()).getState();
1119   C.addTransition(state);
1120 }
1121 
1122 bool MallocChecker::isReleased(SymbolRef Sym, CheckerContext &C) const {
1123   assert(Sym);
1124   const RefState *RS = C.getState()->get<RegionState>(Sym);
1125   return (RS && RS->isReleased());
1126 }
1127 
1128 bool MallocChecker::checkUseAfterFree(SymbolRef Sym, CheckerContext &C,
1129                                       const Stmt *S) const {
1130   if (isReleased(Sym, C)) {
1131     if (ExplodedNode *N = C.generateSink()) {
1132       if (!BT_UseFree)
1133         BT_UseFree.reset(new BugType("Use-after-free", "Memory Error"));
1134 
1135       BugReport *R = new BugReport(*BT_UseFree,
1136                                    "Use of memory after it is freed",N);
1137       if (S)
1138         R->addRange(S->getSourceRange());
1139       R->markInteresting(Sym);
1140       R->addVisitor(new MallocBugVisitor(Sym));
1141       C.EmitReport(R);
1142       return true;
1143     }
1144   }
1145   return false;
1146 }
1147 
1148 // Check if the location is a freed symbolic region.
1149 void MallocChecker::checkLocation(SVal l, bool isLoad, const Stmt *S,
1150                                   CheckerContext &C) const {
1151   SymbolRef Sym = l.getLocSymbolInBase();
1152   if (Sym)
1153     checkUseAfterFree(Sym, C, S);
1154 }
1155 
1156 //===----------------------------------------------------------------------===//
1157 // Check various ways a symbol can be invalidated.
1158 // TODO: This logic (the next 3 functions) is copied/similar to the
1159 // RetainRelease checker. We might want to factor this out.
1160 //===----------------------------------------------------------------------===//
1161 
1162 // Stop tracking symbols when a value escapes as a result of checkBind.
1163 // A value escapes in three possible cases:
1164 // (1) we are binding to something that is not a memory region.
1165 // (2) we are binding to a memregion that does not have stack storage
1166 // (3) we are binding to a memregion with stack storage that the store
1167 //     does not understand.
1168 void MallocChecker::checkBind(SVal loc, SVal val, const Stmt *S,
1169                               CheckerContext &C) const {
1170   // Are we storing to something that causes the value to "escape"?
1171   bool escapes = true;
1172   ProgramStateRef state = C.getState();
1173 
1174   if (loc::MemRegionVal *regionLoc = dyn_cast<loc::MemRegionVal>(&loc)) {
1175     escapes = !regionLoc->getRegion()->hasStackStorage();
1176 
1177     if (!escapes) {
1178       // To test (3), generate a new state with the binding added.  If it is
1179       // the same state, then it escapes (since the store cannot represent
1180       // the binding).
1181       // Do this only if we know that the store is not supposed to generate the
1182       // same state.
1183       SVal StoredVal = state->getSVal(regionLoc->getRegion());
1184       if (StoredVal != val)
1185         escapes = (state == (state->bindLoc(*regionLoc, val)));
1186     }
1187     if (!escapes) {
1188       // Case 4: We do not currently model what happens when a symbol is
1189       // assigned to a struct field, so be conservative here and let the symbol
1190       // go. TODO: This could definitely be improved upon.
1191       escapes = !isa<VarRegion>(regionLoc->getRegion());
1192     }
1193   }
1194 
1195   // If our store can represent the binding and we aren't storing to something
1196   // that doesn't have local storage then just return and have the simulation
1197   // state continue as is.
1198   if (!escapes)
1199       return;
1200 
1201   // Otherwise, find all symbols referenced by 'val' that we are tracking
1202   // and stop tracking them.
1203   state = state->scanReachableSymbols<StopTrackingCallback>(val).getState();
1204   C.addTransition(state);
1205 }
1206 
1207 // If a symbolic region is assumed to NULL (or another constant), stop tracking
1208 // it - assuming that allocation failed on this path.
1209 ProgramStateRef MallocChecker::evalAssume(ProgramStateRef state,
1210                                               SVal Cond,
1211                                               bool Assumption) const {
1212   RegionStateTy RS = state->get<RegionState>();
1213   for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
1214     // If the symbol is assumed to NULL or another constant, this will
1215     // return an APSInt*.
1216     if (state->getSymVal(I.getKey()))
1217       state = state->remove<RegionState>(I.getKey());
1218   }
1219 
1220   // Realloc returns 0 when reallocation fails, which means that we should
1221   // restore the state of the pointer being reallocated.
1222   ReallocMap RP = state->get<ReallocPairs>();
1223   for (ReallocMap::iterator I = RP.begin(), E = RP.end(); I != E; ++I) {
1224     // If the symbol is assumed to NULL or another constant, this will
1225     // return an APSInt*.
1226     if (state->getSymVal(I.getKey())) {
1227       SymbolRef ReallocSym = I.getData().ReallocatedSym;
1228       const RefState *RS = state->get<RegionState>(ReallocSym);
1229       if (RS) {
1230         if (RS->isReleased() && ! I.getData().IsFreeOnFailure)
1231           state = state->set<RegionState>(ReallocSym,
1232                              RefState::getAllocateUnchecked(RS->getStmt()));
1233       }
1234       state = state->remove<ReallocPairs>(I.getKey());
1235     }
1236   }
1237 
1238   return state;
1239 }
1240 
1241 // Check if the function is known to us. So, for example, we could
1242 // conservatively assume it can free/reallocate it's pointer arguments.
1243 // (We assume that the pointers cannot escape through calls to system
1244 // functions not handled by this checker.)
1245 bool MallocChecker::doesNotFreeMemory(const CallOrObjCMessage *Call,
1246                                       ProgramStateRef State) const {
1247   if (!Call)
1248     return false;
1249 
1250   // For now, assume that any C++ call can free memory.
1251   // TODO: If we want to be more optimistic here, we'll need to make sure that
1252   // regions escape to C++ containers. They seem to do that even now, but for
1253   // mysterious reasons.
1254   if (Call->isCXXCall())
1255     return false;
1256 
1257   const Decl *D = Call->getDecl();
1258   if (!D)
1259     return false;
1260 
1261   ASTContext &ASTC = State->getStateManager().getContext();
1262 
1263   // If it's one of the allocation functions we can reason about, we model
1264   // its behavior explicitly.
1265   if (isa<FunctionDecl>(D) && isMemFunction(cast<FunctionDecl>(D), ASTC)) {
1266     return true;
1267   }
1268 
1269   // If it's not a system call, assume it frees memory.
1270   SourceManager &SM = ASTC.getSourceManager();
1271   if (!SM.isInSystemHeader(D->getLocation()))
1272     return false;
1273 
1274   // Process C/ObjC functions.
1275   if (const FunctionDecl *FD  = dyn_cast<FunctionDecl>(D)) {
1276     // White list the system functions whose arguments escape.
1277     const IdentifierInfo *II = FD->getIdentifier();
1278     if (!II)
1279       return true;
1280     StringRef FName = II->getName();
1281 
1282     // White list thread local storage.
1283     if (FName.equals("pthread_setspecific"))
1284       return false;
1285 
1286     // White list the 'XXXNoCopy' ObjC functions.
1287     if (FName.endswith("NoCopy")) {
1288       // Look for the deallocator argument. We know that the memory ownership
1289       // is not transfered only if the deallocator argument is
1290       // 'kCFAllocatorNull'.
1291       for (unsigned i = 1; i < Call->getNumArgs(); ++i) {
1292         const Expr *ArgE = Call->getArg(i)->IgnoreParenCasts();
1293         if (const DeclRefExpr *DE = dyn_cast<DeclRefExpr>(ArgE)) {
1294           StringRef DeallocatorName = DE->getFoundDecl()->getName();
1295           if (DeallocatorName == "kCFAllocatorNull")
1296             return true;
1297         }
1298       }
1299       return false;
1300     }
1301 
1302     // PR12101
1303     // Many CoreFoundation and CoreGraphics might allow a tracked object
1304     // to escape.
1305     if (Call->isCFCGAllowingEscape(FName))
1306       return false;
1307 
1308     // Associating streams with malloced buffers. The pointer can escape if
1309     // 'closefn' is specified (and if that function does free memory).
1310     // Currently, we do not inspect the 'closefn' function (PR12101).
1311     if (FName == "funopen")
1312       if (Call->getNumArgs() >= 4 && !Call->getArgSVal(4).isConstant(0))
1313         return false;
1314 
1315     // Do not warn on pointers passed to 'setbuf' when used with std streams,
1316     // these leaks might be intentional when setting the buffer for stdio.
1317     // http://stackoverflow.com/questions/2671151/who-frees-setvbuf-buffer
1318     if (FName == "setbuf" || FName =="setbuffer" ||
1319         FName == "setlinebuf" || FName == "setvbuf") {
1320       if (Call->getNumArgs() >= 1)
1321         if (const DeclRefExpr *Arg =
1322               dyn_cast<DeclRefExpr>(Call->getArg(0)->IgnoreParenCasts()))
1323           if (const VarDecl *D = dyn_cast<VarDecl>(Arg->getDecl()))
1324               if (D->getCanonicalDecl()->getName().find("std")
1325                                                    != StringRef::npos)
1326                 return false;
1327     }
1328 
1329     // A bunch of other functions, which take ownership of a pointer (See retain
1330     // release checker). Not all the parameters here are invalidated, but the
1331     // Malloc checker cannot differentiate between them. The right way of doing
1332     // this would be to implement a pointer escapes callback.
1333     if (FName == "CVPixelBufferCreateWithBytes" ||
1334         FName == "CGBitmapContextCreateWithData" ||
1335         FName == "CVPixelBufferCreateWithPlanarBytes" ||
1336         FName == "OSAtomicEnqueue") {
1337       return false;
1338     }
1339 
1340     // Whitelist NSXXInsertXX, for example NSMapInsertIfAbsent, since they can
1341     // be deallocated by NSMapRemove.
1342     if (FName.startswith("NS") && (FName.find("Insert") != StringRef::npos))
1343       return false;
1344 
1345     // If the call has a callback as an argument, assume the memory
1346     // can be freed.
1347     if (Call->hasNonZeroCallbackArg())
1348       return false;
1349 
1350     // Otherwise, assume that the function does not free memory.
1351     // Most system calls, do not free the memory.
1352     return true;
1353 
1354   // Process ObjC functions.
1355   } else if (const ObjCMethodDecl * ObjCD = dyn_cast<ObjCMethodDecl>(D)) {
1356     Selector S = ObjCD->getSelector();
1357 
1358     // White list the ObjC functions which do free memory.
1359     // - Anything containing 'freeWhenDone' param set to 1.
1360     //   Ex: dataWithBytesNoCopy:length:freeWhenDone.
1361     for (unsigned i = 1; i < S.getNumArgs(); ++i) {
1362       if (S.getNameForSlot(i).equals("freeWhenDone")) {
1363         if (Call->getArgSVal(i).isConstant(1))
1364           return false;
1365         else
1366           return true;
1367       }
1368     }
1369 
1370     // If the first selector ends with NoCopy, assume that the ownership is
1371     // transfered as well.
1372     // Ex:  [NSData dataWithBytesNoCopy:bytes length:10];
1373     if (S.getNameForSlot(0).endswith("NoCopy")) {
1374       return false;
1375     }
1376 
1377     // If the call has a callback as an argument, assume the memory
1378     // can be freed.
1379     if (Call->hasNonZeroCallbackArg())
1380       return false;
1381 
1382     // Otherwise, assume that the function does not free memory.
1383     // Most system calls, do not free the memory.
1384     return true;
1385   }
1386 
1387   // Otherwise, assume that the function can free memory.
1388   return false;
1389 
1390 }
1391 
1392 // If the symbol we are tracking is invalidated, but not explicitly (ex: the &p
1393 // escapes, when we are tracking p), do not track the symbol as we cannot reason
1394 // about it anymore.
1395 ProgramStateRef
1396 MallocChecker::checkRegionChanges(ProgramStateRef State,
1397                             const StoreManager::InvalidatedSymbols *invalidated,
1398                                     ArrayRef<const MemRegion *> ExplicitRegions,
1399                                     ArrayRef<const MemRegion *> Regions,
1400                                     const CallOrObjCMessage *Call) const {
1401   if (!invalidated || invalidated->empty())
1402     return State;
1403   llvm::SmallPtrSet<SymbolRef, 8> WhitelistedSymbols;
1404 
1405   // If it's a call which might free or reallocate memory, we assume that all
1406   // regions (explicit and implicit) escaped.
1407 
1408   // Otherwise, whitelist explicit pointers; we still can track them.
1409   if (!Call || doesNotFreeMemory(Call, State)) {
1410     for (ArrayRef<const MemRegion *>::iterator I = ExplicitRegions.begin(),
1411         E = ExplicitRegions.end(); I != E; ++I) {
1412       if (const SymbolicRegion *R = (*I)->StripCasts()->getAs<SymbolicRegion>())
1413         WhitelistedSymbols.insert(R->getSymbol());
1414     }
1415   }
1416 
1417   for (StoreManager::InvalidatedSymbols::const_iterator I=invalidated->begin(),
1418        E = invalidated->end(); I!=E; ++I) {
1419     SymbolRef sym = *I;
1420     if (WhitelistedSymbols.count(sym))
1421       continue;
1422     // The symbol escaped.
1423     if (const RefState *RS = State->get<RegionState>(sym))
1424       State = State->set<RegionState>(sym, RefState::getEscaped(RS->getStmt()));
1425   }
1426   return State;
1427 }
1428 
1429 static SymbolRef findFailedReallocSymbol(ProgramStateRef currState,
1430                                          ProgramStateRef prevState) {
1431   ReallocMap currMap = currState->get<ReallocPairs>();
1432   ReallocMap prevMap = prevState->get<ReallocPairs>();
1433 
1434   for (ReallocMap::iterator I = prevMap.begin(), E = prevMap.end();
1435        I != E; ++I) {
1436     SymbolRef sym = I.getKey();
1437     if (!currMap.lookup(sym))
1438       return sym;
1439   }
1440 
1441   return NULL;
1442 }
1443 
1444 PathDiagnosticPiece *
1445 MallocChecker::MallocBugVisitor::VisitNode(const ExplodedNode *N,
1446                                            const ExplodedNode *PrevN,
1447                                            BugReporterContext &BRC,
1448                                            BugReport &BR) {
1449   ProgramStateRef state = N->getState();
1450   ProgramStateRef statePrev = PrevN->getState();
1451 
1452   const RefState *RS = state->get<RegionState>(Sym);
1453   const RefState *RSPrev = statePrev->get<RegionState>(Sym);
1454   if (!RS && !RSPrev)
1455     return 0;
1456 
1457   const Stmt *S = 0;
1458   const char *Msg = 0;
1459   StackHintGeneratorForSymbol *StackHint = 0;
1460 
1461   // Retrieve the associated statement.
1462   ProgramPoint ProgLoc = N->getLocation();
1463   if (isa<StmtPoint>(ProgLoc))
1464     S = cast<StmtPoint>(ProgLoc).getStmt();
1465   // If an assumption was made on a branch, it should be caught
1466   // here by looking at the state transition.
1467   if (isa<BlockEdge>(ProgLoc)) {
1468     const CFGBlock *srcBlk = cast<BlockEdge>(ProgLoc).getSrc();
1469     S = srcBlk->getTerminator();
1470   }
1471   if (!S)
1472     return 0;
1473 
1474   // Find out if this is an interesting point and what is the kind.
1475   if (Mode == Normal) {
1476     if (isAllocated(RS, RSPrev, S)) {
1477       Msg = "Memory is allocated";
1478       StackHint = new StackHintGeneratorForSymbol(Sym,
1479                                                   "Returned allocated memory");
1480     } else if (isReleased(RS, RSPrev, S)) {
1481       Msg = "Memory is released";
1482       StackHint = new StackHintGeneratorForSymbol(Sym,
1483                                                   "Returned released memory");
1484     } else if (isReallocFailedCheck(RS, RSPrev, S)) {
1485       Mode = ReallocationFailed;
1486       Msg = "Reallocation failed";
1487       StackHint = new StackHintGeneratorForReallocationFailed(Sym,
1488                                                        "Reallocation failed");
1489 
1490       if (SymbolRef sym = findFailedReallocSymbol(state, statePrev)) {
1491         // Is it possible to fail two reallocs WITHOUT testing in between?
1492         assert((!FailedReallocSymbol || FailedReallocSymbol == sym) &&
1493           "We only support one failed realloc at a time.");
1494         BR.markInteresting(sym);
1495         FailedReallocSymbol = sym;
1496       }
1497     }
1498 
1499   // We are in a special mode if a reallocation failed later in the path.
1500   } else if (Mode == ReallocationFailed) {
1501     assert(FailedReallocSymbol && "No symbol to look for.");
1502 
1503     // Is this is the first appearance of the reallocated symbol?
1504     if (!statePrev->get<RegionState>(FailedReallocSymbol)) {
1505       // If we ever hit this assert, that means BugReporter has decided to skip
1506       // node pairs or visit them out of order.
1507       assert(state->get<RegionState>(FailedReallocSymbol) &&
1508         "Missed the reallocation point");
1509 
1510       // We're at the reallocation point.
1511       Msg = "Attempt to reallocate memory";
1512       StackHint = new StackHintGeneratorForSymbol(Sym,
1513                                                  "Returned reallocated memory");
1514       FailedReallocSymbol = NULL;
1515       Mode = Normal;
1516     }
1517   }
1518 
1519   if (!Msg)
1520     return 0;
1521   assert(StackHint);
1522 
1523   // Generate the extra diagnostic.
1524   PathDiagnosticLocation Pos(S, BRC.getSourceManager(),
1525                              N->getLocationContext());
1526   return new PathDiagnosticEventPiece(Pos, Msg, true, StackHint);
1527 }
1528 
1529 void MallocChecker::printState(raw_ostream &Out, ProgramStateRef State,
1530                                const char *NL, const char *Sep) const {
1531 
1532   RegionStateTy RS = State->get<RegionState>();
1533 
1534   if (!RS.isEmpty())
1535     Out << "Has Malloc data" << NL;
1536 }
1537 
1538 #define REGISTER_CHECKER(name) \
1539 void ento::register##name(CheckerManager &mgr) {\
1540   registerCStringCheckerBasic(mgr); \
1541   mgr.registerChecker<MallocChecker>()->Filter.C##name = true;\
1542 }
1543 
1544 REGISTER_CHECKER(MallocPessimistic)
1545 REGISTER_CHECKER(MallocOptimistic)
1546