xref: /llvm-project/clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp (revision 3aa5225d5ee00eb7847cb830e6c936e8dc08ee6a)
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 "clang/StaticAnalyzer/Core/Checker.h"
17 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
18 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
19 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
20 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
21 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
22 #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
23 #include "llvm/ADT/ImmutableMap.h"
24 #include "llvm/ADT/SmallString.h"
25 #include "llvm/ADT/STLExtras.h"
26 using namespace clang;
27 using namespace ento;
28 
29 namespace {
30 
31 class RefState {
32   enum Kind { AllocateUnchecked, AllocateFailed, Released, Escaped,
33               Relinquished } K;
34   const Stmt *S;
35 
36 public:
37   RefState(Kind k, const Stmt *s) : K(k), S(s) {}
38 
39   bool isAllocated() const { return K == AllocateUnchecked; }
40   //bool isFailed() const { return K == AllocateFailed; }
41   bool isReleased() const { return K == Released; }
42   //bool isEscaped() const { return K == Escaped; }
43   //bool isRelinquished() const { return K == Relinquished; }
44 
45   bool operator==(const RefState &X) const {
46     return K == X.K && S == X.S;
47   }
48 
49   static RefState getAllocateUnchecked(const Stmt *s) {
50     return RefState(AllocateUnchecked, s);
51   }
52   static RefState getAllocateFailed() {
53     return RefState(AllocateFailed, 0);
54   }
55   static RefState getReleased(const Stmt *s) { return RefState(Released, s); }
56   static RefState getEscaped(const Stmt *s) { return RefState(Escaped, s); }
57   static RefState getRelinquished(const Stmt *s) {
58     return RefState(Relinquished, s);
59   }
60 
61   void Profile(llvm::FoldingSetNodeID &ID) const {
62     ID.AddInteger(K);
63     ID.AddPointer(S);
64   }
65 };
66 
67 class RegionState {};
68 
69 class MallocChecker : public Checker<check::DeadSymbols,
70                                      check::EndPath,
71                                      check::PreStmt<ReturnStmt>,
72                                      check::PostStmt<CallExpr>,
73                                      check::Location,
74                                      check::Bind,
75                                      eval::Assume,
76                                      check::RegionChanges>
77 {
78   mutable OwningPtr<BuiltinBug> BT_DoubleFree;
79   mutable OwningPtr<BuiltinBug> BT_Leak;
80   mutable OwningPtr<BuiltinBug> BT_UseFree;
81   mutable OwningPtr<BuiltinBug> BT_UseRelinquished;
82   mutable OwningPtr<BuiltinBug> BT_BadFree;
83   mutable IdentifierInfo *II_malloc, *II_free, *II_realloc, *II_calloc;
84 
85 public:
86   MallocChecker() : II_malloc(0), II_free(0), II_realloc(0), II_calloc(0) {}
87 
88   /// In pessimistic mode, the checker assumes that it does not know which
89   /// functions might free the memory.
90   struct ChecksFilter {
91     DefaultBool CMallocPessimistic;
92     DefaultBool CMallocOptimistic;
93   };
94 
95   ChecksFilter Filter;
96 
97   void initIdentifierInfo(CheckerContext &C) const;
98 
99   void checkPostStmt(const CallExpr *CE, CheckerContext &C) const;
100   void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const;
101   void checkEndPath(CheckerContext &C) const;
102   void checkPreStmt(const ReturnStmt *S, CheckerContext &C) const;
103   ProgramStateRef evalAssume(ProgramStateRef state, SVal Cond,
104                             bool Assumption) const;
105   void checkLocation(SVal l, bool isLoad, const Stmt *S,
106                      CheckerContext &C) const;
107   void checkBind(SVal location, SVal val, const Stmt*S,
108                  CheckerContext &C) const;
109   ProgramStateRef
110   checkRegionChanges(ProgramStateRef state,
111                      const StoreManager::InvalidatedSymbols *invalidated,
112                      ArrayRef<const MemRegion *> ExplicitRegions,
113                      ArrayRef<const MemRegion *> Regions) const;
114   bool wantsRegionChangeUpdate(ProgramStateRef state) const {
115     return true;
116   }
117 
118 private:
119   static void MallocMem(CheckerContext &C, const CallExpr *CE);
120   static void MallocMemReturnsAttr(CheckerContext &C, const CallExpr *CE,
121                                    const OwnershipAttr* Att);
122   static ProgramStateRef MallocMemAux(CheckerContext &C, const CallExpr *CE,
123                                      const Expr *SizeEx, SVal Init,
124                                      ProgramStateRef state) {
125     return MallocMemAux(C, CE,
126                         state->getSVal(SizeEx, C.getLocationContext()),
127                         Init, state);
128   }
129   static ProgramStateRef MallocMemAux(CheckerContext &C, const CallExpr *CE,
130                                      SVal SizeEx, SVal Init,
131                                      ProgramStateRef state);
132 
133   void FreeMem(CheckerContext &C, const CallExpr *CE) const;
134   void FreeMemAttr(CheckerContext &C, const CallExpr *CE,
135                    const OwnershipAttr* Att) const;
136   ProgramStateRef FreeMemAux(CheckerContext &C, const CallExpr *CE,
137                                  ProgramStateRef state, unsigned Num,
138                                  bool Hold) const;
139 
140   void ReallocMem(CheckerContext &C, const CallExpr *CE) const;
141   static void CallocMem(CheckerContext &C, const CallExpr *CE);
142 
143   bool checkEscape(SymbolRef Sym, const Stmt *S, CheckerContext &C) const;
144   bool checkUseAfterFree(SymbolRef Sym, CheckerContext &C,
145                          const Stmt *S = 0) const;
146 
147   static bool SummarizeValue(raw_ostream &os, SVal V);
148   static bool SummarizeRegion(raw_ostream &os, const MemRegion *MR);
149   void ReportBadFree(CheckerContext &C, SVal ArgVal, SourceRange range) const;
150 
151   void reportLeak(SymbolRef Sym, ExplodedNode *N, CheckerContext &C) const;
152 
153   /// The bug visitor which allows us to print extra diagnostics along the
154   /// BugReport path. For example, showing the allocation site of the leaked
155   /// region.
156   class MallocBugVisitor : public BugReporterVisitor {
157   protected:
158     // The allocated region symbol tracked by the main analysis.
159     SymbolRef Sym;
160 
161   public:
162     MallocBugVisitor(SymbolRef S) : Sym(S) {}
163     virtual ~MallocBugVisitor() {}
164 
165     void Profile(llvm::FoldingSetNodeID &ID) const {
166       static int X = 0;
167       ID.AddPointer(&X);
168       ID.AddPointer(Sym);
169     }
170 
171     inline bool isAllocated(const RefState *S, const RefState *SPrev) {
172       // Did not track -> allocated. Other state (released) -> allocated.
173       return ((S && S->isAllocated()) && (!SPrev || !SPrev->isAllocated()));
174     }
175 
176     inline bool isReleased(const RefState *S, const RefState *SPrev) {
177       // Did not track -> released. Other state (allocated) -> released.
178       return ((S && S->isReleased()) && (!SPrev || !SPrev->isReleased()));
179     }
180 
181     PathDiagnosticPiece *VisitNode(const ExplodedNode *N,
182                                    const ExplodedNode *PrevN,
183                                    BugReporterContext &BRC,
184                                    BugReport &BR);
185   };
186 };
187 } // end anonymous namespace
188 
189 typedef llvm::ImmutableMap<SymbolRef, RefState> RegionStateTy;
190 
191 namespace clang {
192 namespace ento {
193   template <>
194   struct ProgramStateTrait<RegionState>
195     : public ProgramStatePartialTrait<RegionStateTy> {
196     static void *GDMIndex() { static int x; return &x; }
197   };
198 }
199 }
200 
201 namespace {
202 class StopTrackingCallback : public SymbolVisitor {
203   ProgramStateRef state;
204 public:
205   StopTrackingCallback(ProgramStateRef st) : state(st) {}
206   ProgramStateRef getState() const { return state; }
207 
208   bool VisitSymbol(SymbolRef sym) {
209     state = state->remove<RegionState>(sym);
210     return true;
211   }
212 };
213 } // end anonymous namespace
214 
215 void MallocChecker::initIdentifierInfo(CheckerContext &C) const {
216   ASTContext &Ctx = C.getASTContext();
217   if (!II_malloc)
218     II_malloc = &Ctx.Idents.get("malloc");
219   if (!II_free)
220     II_free = &Ctx.Idents.get("free");
221   if (!II_realloc)
222     II_realloc = &Ctx.Idents.get("realloc");
223   if (!II_calloc)
224     II_calloc = &Ctx.Idents.get("calloc");
225 }
226 
227 void MallocChecker::checkPostStmt(const CallExpr *CE, CheckerContext &C) const {
228   const FunctionDecl *FD = C.getCalleeDecl(CE);
229   if (!FD)
230     return;
231   initIdentifierInfo(C);
232 
233   if (FD->getIdentifier() == II_malloc) {
234     MallocMem(C, CE);
235     return;
236   }
237   if (FD->getIdentifier() == II_realloc) {
238     ReallocMem(C, CE);
239     return;
240   }
241 
242   if (FD->getIdentifier() == II_calloc) {
243     CallocMem(C, CE);
244     return;
245   }
246 
247   if (FD->getIdentifier() == II_free) {
248     FreeMem(C, CE);
249     return;
250   }
251 
252   if (Filter.CMallocOptimistic)
253   // Check all the attributes, if there are any.
254   // There can be multiple of these attributes.
255   if (FD->hasAttrs()) {
256     for (specific_attr_iterator<OwnershipAttr>
257                   i = FD->specific_attr_begin<OwnershipAttr>(),
258                   e = FD->specific_attr_end<OwnershipAttr>();
259          i != e; ++i) {
260       switch ((*i)->getOwnKind()) {
261       case OwnershipAttr::Returns: {
262         MallocMemReturnsAttr(C, CE, *i);
263         break;
264       }
265       case OwnershipAttr::Takes:
266       case OwnershipAttr::Holds: {
267         FreeMemAttr(C, CE, *i);
268         break;
269       }
270       }
271     }
272   }
273 
274   if (Filter.CMallocPessimistic) {
275     ProgramStateRef State = C.getState();
276     // The pointer might escape through a function call.
277     for (CallExpr::const_arg_iterator I = CE->arg_begin(),
278                                       E = CE->arg_end(); I != E; ++I) {
279       const Expr *A = *I;
280       if (A->getType().getTypePtr()->isAnyPointerType()) {
281         SymbolRef Sym = State->getSVal(A, C.getLocationContext()).getAsSymbol();
282         if (!Sym)
283           continue;
284         checkEscape(Sym, A, C);
285         checkUseAfterFree(Sym, C, A);
286       }
287     }
288   }
289 }
290 
291 void MallocChecker::MallocMem(CheckerContext &C, const CallExpr *CE) {
292   ProgramStateRef state = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(),
293                                       C.getState());
294   C.addTransition(state);
295 }
296 
297 void MallocChecker::MallocMemReturnsAttr(CheckerContext &C, const CallExpr *CE,
298                                          const OwnershipAttr* Att) {
299   if (Att->getModule() != "malloc")
300     return;
301 
302   OwnershipAttr::args_iterator I = Att->args_begin(), E = Att->args_end();
303   if (I != E) {
304     ProgramStateRef state =
305         MallocMemAux(C, CE, CE->getArg(*I), UndefinedVal(), C.getState());
306     C.addTransition(state);
307     return;
308   }
309   ProgramStateRef state = MallocMemAux(C, CE, UnknownVal(), UndefinedVal(),
310                                         C.getState());
311   C.addTransition(state);
312 }
313 
314 ProgramStateRef MallocChecker::MallocMemAux(CheckerContext &C,
315                                            const CallExpr *CE,
316                                            SVal Size, SVal Init,
317                                            ProgramStateRef state) {
318   SValBuilder &svalBuilder = C.getSValBuilder();
319 
320   // Get the return value.
321   SVal retVal = state->getSVal(CE, C.getLocationContext());
322 
323   // Fill the region with the initialization value.
324   state = state->bindDefault(retVal, Init);
325 
326   // Set the region's extent equal to the Size parameter.
327   const SymbolicRegion *R =
328       dyn_cast_or_null<SymbolicRegion>(retVal.getAsRegion());
329   if (!R || !isa<DefinedOrUnknownSVal>(Size))
330     return 0;
331 
332   DefinedOrUnknownSVal Extent = R->getExtent(svalBuilder);
333   DefinedOrUnknownSVal DefinedSize = cast<DefinedOrUnknownSVal>(Size);
334   DefinedOrUnknownSVal extentMatchesSize =
335     svalBuilder.evalEQ(state, Extent, DefinedSize);
336 
337   state = state->assume(extentMatchesSize, true);
338   assert(state);
339 
340   SymbolRef Sym = retVal.getAsLocSymbol();
341   assert(Sym);
342 
343   // Set the symbol's state to Allocated.
344   return state->set<RegionState>(Sym, RefState::getAllocateUnchecked(CE));
345 }
346 
347 void MallocChecker::FreeMem(CheckerContext &C, const CallExpr *CE) const {
348   ProgramStateRef state = FreeMemAux(C, CE, C.getState(), 0, false);
349 
350   if (state)
351     C.addTransition(state);
352 }
353 
354 void MallocChecker::FreeMemAttr(CheckerContext &C, const CallExpr *CE,
355                                 const OwnershipAttr* Att) const {
356   if (Att->getModule() != "malloc")
357     return;
358 
359   for (OwnershipAttr::args_iterator I = Att->args_begin(), E = Att->args_end();
360        I != E; ++I) {
361     ProgramStateRef state =
362       FreeMemAux(C, CE, C.getState(), *I,
363                  Att->getOwnKind() == OwnershipAttr::Holds);
364     if (state)
365       C.addTransition(state);
366   }
367 }
368 
369 ProgramStateRef MallocChecker::FreeMemAux(CheckerContext &C,
370                                           const CallExpr *CE,
371                                           ProgramStateRef state,
372                                           unsigned Num,
373                                           bool Hold) const {
374   const Expr *ArgExpr = CE->getArg(Num);
375   SVal ArgVal = state->getSVal(ArgExpr, C.getLocationContext());
376   if (!isa<DefinedOrUnknownSVal>(ArgVal))
377     return 0;
378   DefinedOrUnknownSVal location = cast<DefinedOrUnknownSVal>(ArgVal);
379 
380   // Check for null dereferences.
381   if (!isa<Loc>(location))
382     return 0;
383 
384   // FIXME: Technically using 'Assume' here can result in a path
385   //  bifurcation.  In such cases we need to return two states, not just one.
386   ProgramStateRef notNullState, nullState;
387   llvm::tie(notNullState, nullState) = state->assume(location);
388 
389   // The explicit NULL case, no operation is performed.
390   if (nullState && !notNullState)
391     return 0;
392 
393   assert(notNullState);
394 
395   // Unknown values could easily be okay
396   // Undefined values are handled elsewhere
397   if (ArgVal.isUnknownOrUndef())
398     return 0;
399 
400   const MemRegion *R = ArgVal.getAsRegion();
401 
402   // Nonlocs can't be freed, of course.
403   // Non-region locations (labels and fixed addresses) also shouldn't be freed.
404   if (!R) {
405     ReportBadFree(C, ArgVal, ArgExpr->getSourceRange());
406     return 0;
407   }
408 
409   R = R->StripCasts();
410 
411   // Blocks might show up as heap data, but should not be free()d
412   if (isa<BlockDataRegion>(R)) {
413     ReportBadFree(C, ArgVal, ArgExpr->getSourceRange());
414     return 0;
415   }
416 
417   const MemSpaceRegion *MS = R->getMemorySpace();
418 
419   // Parameters, locals, statics, and globals shouldn't be freed.
420   if (!(isa<UnknownSpaceRegion>(MS) || isa<HeapSpaceRegion>(MS))) {
421     // FIXME: at the time this code was written, malloc() regions were
422     // represented by conjured symbols, which are all in UnknownSpaceRegion.
423     // This means that there isn't actually anything from HeapSpaceRegion
424     // that should be freed, even though we allow it here.
425     // Of course, free() can work on memory allocated outside the current
426     // function, so UnknownSpaceRegion is always a possibility.
427     // False negatives are better than false positives.
428 
429     ReportBadFree(C, ArgVal, ArgExpr->getSourceRange());
430     return 0;
431   }
432 
433   const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R);
434   // Various cases could lead to non-symbol values here.
435   // For now, ignore them.
436   if (!SR)
437     return 0;
438 
439   SymbolRef Sym = SR->getSymbol();
440   const RefState *RS = state->get<RegionState>(Sym);
441 
442   // If the symbol has not been tracked, return. This is possible when free() is
443   // called on a pointer that does not get its pointee directly from malloc().
444   // Full support of this requires inter-procedural analysis.
445   if (!RS)
446     return 0;
447 
448   // Check double free.
449   if (RS->isReleased()) {
450     if (ExplodedNode *N = C.generateSink()) {
451       if (!BT_DoubleFree)
452         BT_DoubleFree.reset(
453           new BuiltinBug("Double free",
454                          "Try to free a memory block that has been released"));
455       BugReport *R = new BugReport(*BT_DoubleFree,
456                                    BT_DoubleFree->getDescription(), N);
457       R->addVisitor(new MallocBugVisitor(Sym));
458       C.EmitReport(R);
459     }
460     return 0;
461   }
462 
463   // Normal free.
464   if (Hold)
465     return notNullState->set<RegionState>(Sym, RefState::getRelinquished(CE));
466   return notNullState->set<RegionState>(Sym, RefState::getReleased(CE));
467 }
468 
469 bool MallocChecker::SummarizeValue(raw_ostream &os, SVal V) {
470   if (nonloc::ConcreteInt *IntVal = dyn_cast<nonloc::ConcreteInt>(&V))
471     os << "an integer (" << IntVal->getValue() << ")";
472   else if (loc::ConcreteInt *ConstAddr = dyn_cast<loc::ConcreteInt>(&V))
473     os << "a constant address (" << ConstAddr->getValue() << ")";
474   else if (loc::GotoLabel *Label = dyn_cast<loc::GotoLabel>(&V))
475     os << "the address of the label '" << Label->getLabel()->getName() << "'";
476   else
477     return false;
478 
479   return true;
480 }
481 
482 bool MallocChecker::SummarizeRegion(raw_ostream &os,
483                                     const MemRegion *MR) {
484   switch (MR->getKind()) {
485   case MemRegion::FunctionTextRegionKind: {
486     const FunctionDecl *FD = cast<FunctionTextRegion>(MR)->getDecl();
487     if (FD)
488       os << "the address of the function '" << *FD << '\'';
489     else
490       os << "the address of a function";
491     return true;
492   }
493   case MemRegion::BlockTextRegionKind:
494     os << "block text";
495     return true;
496   case MemRegion::BlockDataRegionKind:
497     // FIXME: where the block came from?
498     os << "a block";
499     return true;
500   default: {
501     const MemSpaceRegion *MS = MR->getMemorySpace();
502 
503     if (isa<StackLocalsSpaceRegion>(MS)) {
504       const VarRegion *VR = dyn_cast<VarRegion>(MR);
505       const VarDecl *VD;
506       if (VR)
507         VD = VR->getDecl();
508       else
509         VD = NULL;
510 
511       if (VD)
512         os << "the address of the local variable '" << VD->getName() << "'";
513       else
514         os << "the address of a local stack variable";
515       return true;
516     }
517 
518     if (isa<StackArgumentsSpaceRegion>(MS)) {
519       const VarRegion *VR = dyn_cast<VarRegion>(MR);
520       const VarDecl *VD;
521       if (VR)
522         VD = VR->getDecl();
523       else
524         VD = NULL;
525 
526       if (VD)
527         os << "the address of the parameter '" << VD->getName() << "'";
528       else
529         os << "the address of a parameter";
530       return true;
531     }
532 
533     if (isa<GlobalsSpaceRegion>(MS)) {
534       const VarRegion *VR = dyn_cast<VarRegion>(MR);
535       const VarDecl *VD;
536       if (VR)
537         VD = VR->getDecl();
538       else
539         VD = NULL;
540 
541       if (VD) {
542         if (VD->isStaticLocal())
543           os << "the address of the static variable '" << VD->getName() << "'";
544         else
545           os << "the address of the global variable '" << VD->getName() << "'";
546       } else
547         os << "the address of a global variable";
548       return true;
549     }
550 
551     return false;
552   }
553   }
554 }
555 
556 void MallocChecker::ReportBadFree(CheckerContext &C, SVal ArgVal,
557                                   SourceRange range) const {
558   if (ExplodedNode *N = C.generateSink()) {
559     if (!BT_BadFree)
560       BT_BadFree.reset(new BuiltinBug("Bad free"));
561 
562     SmallString<100> buf;
563     llvm::raw_svector_ostream os(buf);
564 
565     const MemRegion *MR = ArgVal.getAsRegion();
566     if (MR) {
567       while (const ElementRegion *ER = dyn_cast<ElementRegion>(MR))
568         MR = ER->getSuperRegion();
569 
570       // Special case for alloca()
571       if (isa<AllocaRegion>(MR))
572         os << "Argument to free() was allocated by alloca(), not malloc()";
573       else {
574         os << "Argument to free() is ";
575         if (SummarizeRegion(os, MR))
576           os << ", which is not memory allocated by malloc()";
577         else
578           os << "not memory allocated by malloc()";
579       }
580     } else {
581       os << "Argument to free() is ";
582       if (SummarizeValue(os, ArgVal))
583         os << ", which is not memory allocated by malloc()";
584       else
585         os << "not memory allocated by malloc()";
586     }
587 
588     BugReport *R = new BugReport(*BT_BadFree, os.str(), N);
589     R->addRange(range);
590     C.EmitReport(R);
591   }
592 }
593 
594 void MallocChecker::ReallocMem(CheckerContext &C, const CallExpr *CE) const {
595   ProgramStateRef state = C.getState();
596   const Expr *arg0Expr = CE->getArg(0);
597   const LocationContext *LCtx = C.getLocationContext();
598   SVal Arg0Val = state->getSVal(arg0Expr, LCtx);
599   if (!isa<DefinedOrUnknownSVal>(Arg0Val))
600     return;
601   DefinedOrUnknownSVal arg0Val = cast<DefinedOrUnknownSVal>(Arg0Val);
602 
603   SValBuilder &svalBuilder = C.getSValBuilder();
604 
605   DefinedOrUnknownSVal PtrEQ =
606     svalBuilder.evalEQ(state, arg0Val, svalBuilder.makeNull());
607 
608   // Get the size argument. If there is no size arg then give up.
609   const Expr *Arg1 = CE->getArg(1);
610   if (!Arg1)
611     return;
612 
613   // Get the value of the size argument.
614   SVal Arg1ValG = state->getSVal(Arg1, LCtx);
615   if (!isa<DefinedOrUnknownSVal>(Arg1ValG))
616     return;
617   DefinedOrUnknownSVal Arg1Val = cast<DefinedOrUnknownSVal>(Arg1ValG);
618 
619   // Compare the size argument to 0.
620   DefinedOrUnknownSVal SizeZero =
621     svalBuilder.evalEQ(state, Arg1Val,
622                        svalBuilder.makeIntValWithPtrWidth(0, false));
623 
624   // If the ptr is NULL and the size is not 0, the call is equivalent to
625   // malloc(size).
626   ProgramStateRef stateEqual = state->assume(PtrEQ, true);
627   if (stateEqual && state->assume(SizeZero, false)) {
628     // Hack: set the NULL symbolic region to released to suppress false warning.
629     // In the future we should add more states for allocated regions, e.g.,
630     // CheckedNull, CheckedNonNull.
631 
632     SymbolRef Sym = arg0Val.getAsLocSymbol();
633     if (Sym)
634       stateEqual = stateEqual->set<RegionState>(Sym, RefState::getReleased(CE));
635 
636     ProgramStateRef stateMalloc = MallocMemAux(C, CE, CE->getArg(1),
637                                               UndefinedVal(), stateEqual);
638     C.addTransition(stateMalloc);
639   }
640 
641   if (ProgramStateRef stateNotEqual = state->assume(PtrEQ, false)) {
642     // If the size is 0, free the memory.
643     if (ProgramStateRef stateSizeZero =
644           stateNotEqual->assume(SizeZero, true))
645       if (ProgramStateRef stateFree =
646           FreeMemAux(C, CE, stateSizeZero, 0, false)) {
647 
648         // Bind the return value to NULL because it is now free.
649         C.addTransition(stateFree->BindExpr(CE, LCtx,
650                                             svalBuilder.makeNull(), true));
651       }
652     if (ProgramStateRef stateSizeNotZero =
653           stateNotEqual->assume(SizeZero,false))
654       if (ProgramStateRef stateFree = FreeMemAux(C, CE, stateSizeNotZero,
655                                                 0, false)) {
656         // FIXME: We should copy the content of the original buffer.
657         ProgramStateRef stateRealloc = MallocMemAux(C, CE, CE->getArg(1),
658                                                    UnknownVal(), stateFree);
659         C.addTransition(stateRealloc);
660       }
661   }
662 }
663 
664 void MallocChecker::CallocMem(CheckerContext &C, const CallExpr *CE) {
665   ProgramStateRef state = C.getState();
666   SValBuilder &svalBuilder = C.getSValBuilder();
667   const LocationContext *LCtx = C.getLocationContext();
668   SVal count = state->getSVal(CE->getArg(0), LCtx);
669   SVal elementSize = state->getSVal(CE->getArg(1), LCtx);
670   SVal TotalSize = svalBuilder.evalBinOp(state, BO_Mul, count, elementSize,
671                                         svalBuilder.getContext().getSizeType());
672   SVal zeroVal = svalBuilder.makeZeroVal(svalBuilder.getContext().CharTy);
673 
674   C.addTransition(MallocMemAux(C, CE, TotalSize, zeroVal, state));
675 }
676 
677 void MallocChecker::reportLeak(SymbolRef Sym, ExplodedNode *N,
678                                CheckerContext &C) const {
679   assert(N);
680   if (!BT_Leak) {
681     BT_Leak.reset(new BuiltinBug("Memory leak",
682         "Allocated memory never released. Potential memory leak."));
683     // Leaks should not be reported if they are post-dominated by a sink:
684     // (1) Sinks are higher importance bugs.
685     // (2) NoReturnFunctionChecker uses sink nodes to represent paths ending
686     //     with __noreturn functions such as assert() or exit(). We choose not
687     //     to report leaks on such paths.
688     BT_Leak->setSuppressOnSink(true);
689   }
690 
691   BugReport *R = new BugReport(*BT_Leak, BT_Leak->getDescription(), N);
692   R->addVisitor(new MallocBugVisitor(Sym));
693   C.EmitReport(R);
694 }
695 
696 void MallocChecker::checkDeadSymbols(SymbolReaper &SymReaper,
697                                      CheckerContext &C) const
698 {
699   if (!SymReaper.hasDeadSymbols())
700     return;
701 
702   ProgramStateRef state = C.getState();
703   RegionStateTy RS = state->get<RegionState>();
704   RegionStateTy::Factory &F = state->get_context<RegionState>();
705 
706   bool generateReport = false;
707   llvm::SmallVector<SymbolRef, 2> Errors;
708   for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
709     if (SymReaper.isDead(I->first)) {
710       if (I->second.isAllocated()) {
711         generateReport = true;
712         Errors.push_back(I->first);
713       }
714       // Remove the dead symbol from the map.
715       RS = F.remove(RS, I->first);
716 
717     }
718   }
719 
720   ExplodedNode *N = C.addTransition(state->set<RegionState>(RS));
721 
722   if (N && generateReport) {
723     for (llvm::SmallVector<SymbolRef, 2>::iterator
724          I = Errors.begin(), E = Errors.end(); I != E; ++I) {
725       reportLeak(*I, N, C);
726     }
727   }
728 }
729 
730 void MallocChecker::checkEndPath(CheckerContext &C) const {
731   ProgramStateRef state = C.getState();
732   RegionStateTy M = state->get<RegionState>();
733 
734   for (RegionStateTy::iterator I = M.begin(), E = M.end(); I != E; ++I) {
735     RefState RS = I->second;
736     if (RS.isAllocated()) {
737       ExplodedNode *N = C.addTransition(state);
738       if (N)
739         reportLeak(I->first, N, C);
740     }
741   }
742 }
743 
744 bool MallocChecker::checkEscape(SymbolRef Sym, const Stmt *S,
745                                 CheckerContext &C) const {
746   ProgramStateRef state = C.getState();
747   const RefState *RS = state->get<RegionState>(Sym);
748   if (!RS)
749     return false;
750 
751   if (RS->isAllocated()) {
752     state = state->set<RegionState>(Sym, RefState::getEscaped(S));
753     C.addTransition(state);
754     return true;
755   }
756   return false;
757 }
758 
759 void MallocChecker::checkPreStmt(const ReturnStmt *S, CheckerContext &C) const {
760   const Expr *E = S->getRetValue();
761   if (!E)
762     return;
763 
764   // Check if we are returning a symbol.
765   SymbolRef Sym = C.getState()->getSVal(E, C.getLocationContext()).getAsSymbol();
766   if (!Sym)
767     return;
768 
769   // Check if we are returning freed memory.
770   checkUseAfterFree(Sym, C, S);
771 
772   // Check if the symbol is escaping.
773   checkEscape(Sym, S, C);
774 }
775 
776 bool MallocChecker::checkUseAfterFree(SymbolRef Sym, CheckerContext &C,
777                                       const Stmt *S) const {
778   assert(Sym);
779   const RefState *RS = C.getState()->get<RegionState>(Sym);
780   if (RS && RS->isReleased()) {
781     if (ExplodedNode *N = C.addTransition()) {
782       if (!BT_UseFree)
783         BT_UseFree.reset(new BuiltinBug("Use of dynamically allocated memory "
784             "after it is freed."));
785 
786       BugReport *R = new BugReport(*BT_UseFree, BT_UseFree->getDescription(),N);
787       if (S)
788         R->addRange(S->getSourceRange());
789       R->addVisitor(new MallocBugVisitor(Sym));
790       C.EmitReport(R);
791       return true;
792     }
793   }
794   return false;
795 }
796 
797 // Check if the location is a freed symbolic region.
798 void MallocChecker::checkLocation(SVal l, bool isLoad, const Stmt *S,
799                                   CheckerContext &C) const {
800   SymbolRef Sym = l.getLocSymbolInBase();
801   if (Sym)
802     checkUseAfterFree(Sym, C);
803 }
804 
805 //===----------------------------------------------------------------------===//
806 // Check various ways a symbol can be invalidated.
807 // TODO: This logic (the next 3 functions) is copied/similar to the
808 // RetainRelease checker. We might want to factor this out.
809 //===----------------------------------------------------------------------===//
810 
811 // Stop tracking symbols when a value escapes as a result of checkBind.
812 // A value escapes in three possible cases:
813 // (1) we are binding to something that is not a memory region.
814 // (2) we are binding to a memregion that does not have stack storage
815 // (3) we are binding to a memregion with stack storage that the store
816 //     does not understand.
817 void MallocChecker::checkBind(SVal loc, SVal val, const Stmt *S,
818                               CheckerContext &C) const {
819   // Are we storing to something that causes the value to "escape"?
820   bool escapes = true;
821   ProgramStateRef state = C.getState();
822 
823   if (loc::MemRegionVal *regionLoc = dyn_cast<loc::MemRegionVal>(&loc)) {
824     escapes = !regionLoc->getRegion()->hasStackStorage();
825 
826     if (!escapes) {
827       // To test (3), generate a new state with the binding added.  If it is
828       // the same state, then it escapes (since the store cannot represent
829       // the binding).
830       escapes = (state == (state->bindLoc(*regionLoc, val)));
831     }
832   }
833 
834   // If our store can represent the binding and we aren't storing to something
835   // that doesn't have local storage then just return and have the simulation
836   // state continue as is.
837   if (!escapes)
838       return;
839 
840   // Otherwise, find all symbols referenced by 'val' that we are tracking
841   // and stop tracking them.
842   state = state->scanReachableSymbols<StopTrackingCallback>(val).getState();
843   C.addTransition(state);
844 }
845 
846 // If a symbolic region is assumed to NULL (or another constant), stop tracking
847 // it - assuming that allocation failed on this path.
848 ProgramStateRef MallocChecker::evalAssume(ProgramStateRef state,
849                                               SVal Cond,
850                                               bool Assumption) const {
851   RegionStateTy RS = state->get<RegionState>();
852 
853   for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
854     // If the symbol is assumed to NULL or another constant, this will
855     // return an APSInt*.
856     if (state->getSymVal(I.getKey()))
857       state = state->remove<RegionState>(I.getKey());
858   }
859 
860   return state;
861 }
862 
863 // If the symbol we are tracking is invalidated, but not explicitly (ex: the &p
864 // escapes, when we are tracking p), do not track the symbol as we cannot reason
865 // about it anymore.
866 ProgramStateRef
867 MallocChecker::checkRegionChanges(ProgramStateRef state,
868                             const StoreManager::InvalidatedSymbols *invalidated,
869                                     ArrayRef<const MemRegion *> ExplicitRegions,
870                                     ArrayRef<const MemRegion *> Regions) const {
871   if (!invalidated)
872     return state;
873 
874   llvm::SmallPtrSet<SymbolRef, 8> WhitelistedSymbols;
875   for (ArrayRef<const MemRegion *>::iterator I = ExplicitRegions.begin(),
876        E = ExplicitRegions.end(); I != E; ++I) {
877     if (const SymbolicRegion *SR = (*I)->StripCasts()->getAs<SymbolicRegion>())
878       WhitelistedSymbols.insert(SR->getSymbol());
879   }
880 
881   for (StoreManager::InvalidatedSymbols::const_iterator I=invalidated->begin(),
882        E = invalidated->end(); I!=E; ++I) {
883     SymbolRef sym = *I;
884     if (WhitelistedSymbols.count(sym))
885       continue;
886     // Don't track the symbol.
887     state = state->remove<RegionState>(sym);
888   }
889   return state;
890 }
891 
892 PathDiagnosticPiece *
893 MallocChecker::MallocBugVisitor::VisitNode(const ExplodedNode *N,
894                                            const ExplodedNode *PrevN,
895                                            BugReporterContext &BRC,
896                                            BugReport &BR) {
897   const RefState *RS = N->getState()->get<RegionState>(Sym);
898   const RefState *RSPrev = PrevN->getState()->get<RegionState>(Sym);
899   if (!RS && !RSPrev)
900     return 0;
901 
902   // We expect the interesting locations be StmtPoints corresponding to call
903   // expressions. We do not support indirect function calls as of now.
904   const CallExpr *CE = 0;
905   if (isa<StmtPoint>(N->getLocation()))
906     CE = dyn_cast<CallExpr>(cast<StmtPoint>(N->getLocation()).getStmt());
907   if (!CE)
908     return 0;
909   const FunctionDecl *funDecl = CE->getDirectCallee();
910   if (!funDecl)
911     return 0;
912 
913   // Find out if this is an interesting point and what is the kind.
914   const char *Msg = 0;
915   if (isAllocated(RS, RSPrev))
916     Msg = "Memory is allocated here";
917   else if (isReleased(RS, RSPrev))
918     Msg = "Memory is released here";
919   if (!Msg)
920     return 0;
921 
922   // Generate the extra diagnostic.
923   PathDiagnosticLocation Pos(CE, BRC.getSourceManager(),
924                              N->getLocationContext());
925   return new PathDiagnosticEventPiece(Pos, Msg);
926 }
927 
928 
929 #define REGISTER_CHECKER(name) \
930 void ento::register##name(CheckerManager &mgr) {\
931   mgr.registerChecker<MallocChecker>()->Filter.C##name = true;\
932 }
933 
934 REGISTER_CHECKER(MallocPessimistic)
935 REGISTER_CHECKER(MallocOptimistic)
936