xref: /llvm-project/clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp (revision 40a7eb38375699a9956bbe3cbb713433bf1d7b8c)
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 isFailed() const { return K == AllocateFailed; }
46   bool isReleased() const { return K == Released; }
47   //bool isEscaped() const { return K == Escaped; }
48   //bool isRelinquished() const { return K == Relinquished; }
49   const Stmt *getStmt() const { return S; }
50 
51   bool operator==(const RefState &X) const {
52     return K == X.K && S == X.S;
53   }
54 
55   static RefState getAllocateUnchecked(const Stmt *s) {
56     return RefState(AllocateUnchecked, s);
57   }
58   static RefState getAllocateFailed() {
59     return RefState(AllocateFailed, 0);
60   }
61   static RefState getReleased(const Stmt *s) { return RefState(Released, s); }
62   static RefState getEscaped(const Stmt *s) { return RefState(Escaped, s); }
63   static RefState getRelinquished(const Stmt *s) {
64     return RefState(Relinquished, s);
65   }
66 
67   void Profile(llvm::FoldingSetNodeID &ID) const {
68     ID.AddInteger(K);
69     ID.AddPointer(S);
70   }
71 };
72 
73 struct ReallocPair {
74   SymbolRef ReallocatedSym;
75   bool IsFreeOnFailure;
76   ReallocPair(SymbolRef S, bool F) : ReallocatedSym(S), IsFreeOnFailure(F) {}
77   void Profile(llvm::FoldingSetNodeID &ID) const {
78     ID.AddInteger(IsFreeOnFailure);
79     ID.AddPointer(ReallocatedSym);
80   }
81   bool operator==(const ReallocPair &X) const {
82     return ReallocatedSym == X.ReallocatedSym &&
83            IsFreeOnFailure == X.IsFreeOnFailure;
84   }
85 };
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::Location,
93                                      check::Bind,
94                                      eval::Assume,
95                                      check::RegionChanges>
96 {
97   mutable OwningPtr<BugType> BT_DoubleFree;
98   mutable OwningPtr<BugType> BT_Leak;
99   mutable OwningPtr<BugType> BT_UseFree;
100   mutable OwningPtr<BugType> BT_BadFree;
101   mutable IdentifierInfo *II_malloc, *II_free, *II_realloc, *II_calloc,
102                          *II_valloc, *II_reallocf, *II_strndup, *II_strdup;
103 
104   static const unsigned InvalidArgIndex = UINT_MAX;
105 
106 public:
107   MallocChecker() : II_malloc(0), II_free(0), II_realloc(0), II_calloc(0),
108                     II_valloc(0), II_reallocf(0), II_strndup(0), II_strdup(0) {}
109 
110   /// In pessimistic mode, the checker assumes that it does not know which
111   /// functions might free the memory.
112   struct ChecksFilter {
113     DefaultBool CMallocPessimistic;
114     DefaultBool CMallocOptimistic;
115   };
116 
117   ChecksFilter Filter;
118 
119   void checkPreStmt(const CallExpr *S, CheckerContext &C) const;
120   void checkPostStmt(const CallExpr *CE, 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 private:
141   void initIdentifierInfo(ASTContext &C) const;
142 
143   /// Check if this is one of the functions which can allocate/reallocate memory
144   /// pointed to by one of its arguments.
145   bool isMemFunction(const FunctionDecl *FD, ASTContext &C) const;
146 
147   static ProgramStateRef MallocMemReturnsAttr(CheckerContext &C,
148                                               const CallExpr *CE,
149                                               const OwnershipAttr* Att);
150   static ProgramStateRef MallocMemAux(CheckerContext &C, const CallExpr *CE,
151                                      const Expr *SizeEx, SVal Init,
152                                      ProgramStateRef state) {
153     return MallocMemAux(C, CE,
154                         state->getSVal(SizeEx, C.getLocationContext()),
155                         Init, state);
156   }
157 
158   static ProgramStateRef MallocMemAux(CheckerContext &C, const CallExpr *CE,
159                                      SVal SizeEx, SVal Init,
160                                      ProgramStateRef state);
161 
162   /// Update the RefState to reflect the new memory allocation.
163   static ProgramStateRef MallocUpdateRefState(CheckerContext &C,
164                                               const CallExpr *CE,
165                                               ProgramStateRef state);
166 
167   ProgramStateRef FreeMemAttr(CheckerContext &C, const CallExpr *CE,
168                               const OwnershipAttr* Att) const;
169   ProgramStateRef FreeMemAux(CheckerContext &C, const CallExpr *CE,
170                                  ProgramStateRef state, unsigned Num,
171                                  bool Hold) const;
172 
173   ProgramStateRef ReallocMem(CheckerContext &C, const CallExpr *CE,
174                              bool FreesMemOnFailure) const;
175   static ProgramStateRef CallocMem(CheckerContext &C, const CallExpr *CE);
176 
177   bool checkEscape(SymbolRef Sym, const Stmt *S, CheckerContext &C) const;
178   bool checkUseAfterFree(SymbolRef Sym, CheckerContext &C,
179                          const Stmt *S = 0) const;
180 
181   /// Check if the function is not known to us. So, for example, we could
182   /// conservatively assume it can free/reallocate it's pointer arguments.
183   bool hasUnknownBehavior(const FunctionDecl *FD, ProgramStateRef State) const;
184 
185   static bool SummarizeValue(raw_ostream &os, SVal V);
186   static bool SummarizeRegion(raw_ostream &os, const MemRegion *MR);
187   void ReportBadFree(CheckerContext &C, SVal ArgVal, SourceRange range) const;
188 
189   void reportLeak(SymbolRef Sym, ExplodedNode *N, CheckerContext &C) const;
190 
191   /// The bug visitor which allows us to print extra diagnostics along the
192   /// BugReport path. For example, showing the allocation site of the leaked
193   /// region.
194   class MallocBugVisitor : public BugReporterVisitor {
195   protected:
196     enum NotificationMode {
197       Normal,
198       Complete,
199       ReallocationFailed
200     };
201 
202     // The allocated region symbol tracked by the main analysis.
203     SymbolRef Sym;
204     NotificationMode Mode;
205 
206   public:
207     MallocBugVisitor(SymbolRef S) : Sym(S), Mode(Normal) {}
208     virtual ~MallocBugVisitor() {}
209 
210     void Profile(llvm::FoldingSetNodeID &ID) const {
211       static int X = 0;
212       ID.AddPointer(&X);
213       ID.AddPointer(Sym);
214     }
215 
216     inline bool isAllocated(const RefState *S, const RefState *SPrev,
217                             const Stmt *Stmt) {
218       // Did not track -> allocated. Other state (released) -> allocated.
219       return (Stmt && isa<CallExpr>(Stmt) &&
220               (S && S->isAllocated()) && (!SPrev || !SPrev->isAllocated()));
221     }
222 
223     inline bool isReleased(const RefState *S, const RefState *SPrev,
224                            const Stmt *Stmt) {
225       // Did not track -> released. Other state (allocated) -> released.
226       return (Stmt && isa<CallExpr>(Stmt) &&
227               (S && S->isReleased()) && (!SPrev || !SPrev->isReleased()));
228     }
229 
230     inline bool isReallocFailedCheck(const RefState *S, const RefState *SPrev,
231                                      const Stmt *Stmt) {
232       // If the expression is not a call, and the state change is
233       // released -> allocated, it must be the realloc return value
234       // check. If we have to handle more cases here, it might be cleaner just
235       // to track this extra bit in the state itself.
236       return ((!Stmt || !isa<CallExpr>(Stmt)) &&
237               (S && S->isAllocated()) && (SPrev && !SPrev->isAllocated()));
238     }
239 
240     PathDiagnosticPiece *VisitNode(const ExplodedNode *N,
241                                    const ExplodedNode *PrevN,
242                                    BugReporterContext &BRC,
243                                    BugReport &BR);
244   };
245 };
246 } // end anonymous namespace
247 
248 typedef llvm::ImmutableMap<SymbolRef, RefState> RegionStateTy;
249 typedef llvm::ImmutableMap<SymbolRef, ReallocPair > ReallocMap;
250 class RegionState {};
251 class ReallocPairs {};
252 namespace clang {
253 namespace ento {
254   template <>
255   struct ProgramStateTrait<RegionState>
256     : public ProgramStatePartialTrait<RegionStateTy> {
257     static void *GDMIndex() { static int x; return &x; }
258   };
259 
260   template <>
261   struct ProgramStateTrait<ReallocPairs>
262     : public ProgramStatePartialTrait<ReallocMap> {
263     static void *GDMIndex() { static int x; return &x; }
264   };
265 }
266 }
267 
268 namespace {
269 class StopTrackingCallback : public SymbolVisitor {
270   ProgramStateRef state;
271 public:
272   StopTrackingCallback(ProgramStateRef st) : state(st) {}
273   ProgramStateRef getState() const { return state; }
274 
275   bool VisitSymbol(SymbolRef sym) {
276     state = state->remove<RegionState>(sym);
277     return true;
278   }
279 };
280 } // end anonymous namespace
281 
282 void MallocChecker::initIdentifierInfo(ASTContext &Ctx) const {
283   if (!II_malloc)
284     II_malloc = &Ctx.Idents.get("malloc");
285   if (!II_free)
286     II_free = &Ctx.Idents.get("free");
287   if (!II_realloc)
288     II_realloc = &Ctx.Idents.get("realloc");
289   if (!II_reallocf)
290     II_reallocf = &Ctx.Idents.get("reallocf");
291   if (!II_calloc)
292     II_calloc = &Ctx.Idents.get("calloc");
293   if (!II_valloc)
294     II_valloc = &Ctx.Idents.get("valloc");
295   if (!II_strdup)
296     II_strdup = &Ctx.Idents.get("strdup");
297   if (!II_strndup)
298     II_strndup = &Ctx.Idents.get("strndup");
299 }
300 
301 bool MallocChecker::isMemFunction(const FunctionDecl *FD, ASTContext &C) const {
302   if (!FD)
303     return false;
304   IdentifierInfo *FunI = FD->getIdentifier();
305   if (!FunI)
306     return false;
307 
308   initIdentifierInfo(C);
309 
310   if (FunI == II_malloc || FunI == II_free || FunI == II_realloc ||
311       FunI == II_reallocf || FunI == II_calloc || FunI == II_valloc ||
312       FunI == II_strdup || FunI == II_strndup)
313     return true;
314 
315   if (Filter.CMallocOptimistic && FD->hasAttrs() &&
316       FD->specific_attr_begin<OwnershipAttr>() !=
317           FD->specific_attr_end<OwnershipAttr>())
318     return true;
319 
320 
321   return false;
322 }
323 
324 void MallocChecker::checkPostStmt(const CallExpr *CE, CheckerContext &C) const {
325   const FunctionDecl *FD = C.getCalleeDecl(CE);
326   if (!FD)
327     return;
328 
329   initIdentifierInfo(C.getASTContext());
330   IdentifierInfo *FunI = FD->getIdentifier();
331   if (!FunI)
332     return;
333 
334   ProgramStateRef State = C.getState();
335   if (FunI == II_malloc || FunI == II_valloc) {
336     State = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(), State);
337   } else if (FunI == II_realloc) {
338     State = ReallocMem(C, CE, false);
339   } else if (FunI == II_reallocf) {
340     State = ReallocMem(C, CE, true);
341   } else if (FunI == II_calloc) {
342     State = CallocMem(C, CE);
343   } else if (FunI == II_free) {
344     State = FreeMemAux(C, CE, C.getState(), 0, false);
345   } else if (FunI == II_strdup) {
346     State = MallocUpdateRefState(C, CE, State);
347   } else if (FunI == II_strndup) {
348     State = MallocUpdateRefState(C, CE, State);
349   } else if (Filter.CMallocOptimistic) {
350     // Check all the attributes, if there are any.
351     // There can be multiple of these attributes.
352     if (FD->hasAttrs())
353       for (specific_attr_iterator<OwnershipAttr>
354           i = FD->specific_attr_begin<OwnershipAttr>(),
355           e = FD->specific_attr_end<OwnershipAttr>();
356           i != e; ++i) {
357         switch ((*i)->getOwnKind()) {
358         case OwnershipAttr::Returns:
359           State = MallocMemReturnsAttr(C, CE, *i);
360           break;
361         case OwnershipAttr::Takes:
362         case OwnershipAttr::Holds:
363           State = FreeMemAttr(C, CE, *i);
364           break;
365         }
366       }
367   }
368   C.addTransition(State);
369 }
370 
371 ProgramStateRef MallocChecker::MallocMemReturnsAttr(CheckerContext &C,
372                                                     const CallExpr *CE,
373                                                     const OwnershipAttr* Att) {
374   if (Att->getModule() != "malloc")
375     return 0;
376 
377   OwnershipAttr::args_iterator I = Att->args_begin(), E = Att->args_end();
378   if (I != E) {
379     return MallocMemAux(C, CE, CE->getArg(*I), UndefinedVal(), C.getState());
380   }
381   return MallocMemAux(C, CE, UnknownVal(), UndefinedVal(), C.getState());
382 }
383 
384 ProgramStateRef MallocChecker::MallocMemAux(CheckerContext &C,
385                                            const CallExpr *CE,
386                                            SVal Size, SVal Init,
387                                            ProgramStateRef state) {
388   // Get the return value.
389   SVal retVal = state->getSVal(CE, C.getLocationContext());
390 
391   // We expect the malloc functions to return a pointer.
392   if (!isa<Loc>(retVal))
393     return 0;
394 
395   // Fill the region with the initialization value.
396   state = state->bindDefault(retVal, Init);
397 
398   // Set the region's extent equal to the Size parameter.
399   const SymbolicRegion *R =
400       dyn_cast_or_null<SymbolicRegion>(retVal.getAsRegion());
401   if (!R)
402     return 0;
403   if (isa<DefinedOrUnknownSVal>(Size)) {
404     SValBuilder &svalBuilder = C.getSValBuilder();
405     DefinedOrUnknownSVal Extent = R->getExtent(svalBuilder);
406     DefinedOrUnknownSVal DefinedSize = cast<DefinedOrUnknownSVal>(Size);
407     DefinedOrUnknownSVal extentMatchesSize =
408         svalBuilder.evalEQ(state, Extent, DefinedSize);
409 
410     state = state->assume(extentMatchesSize, true);
411     assert(state);
412   }
413 
414   return MallocUpdateRefState(C, CE, state);
415 }
416 
417 ProgramStateRef MallocChecker::MallocUpdateRefState(CheckerContext &C,
418                                                     const CallExpr *CE,
419                                                     ProgramStateRef state) {
420   // Get the return value.
421   SVal retVal = state->getSVal(CE, C.getLocationContext());
422 
423   // We expect the malloc functions to return a pointer.
424   if (!isa<Loc>(retVal))
425     return 0;
426 
427   SymbolRef Sym = retVal.getAsLocSymbol();
428   assert(Sym);
429 
430   // Set the symbol's state to Allocated.
431   return state->set<RegionState>(Sym, RefState::getAllocateUnchecked(CE));
432 
433 }
434 
435 ProgramStateRef MallocChecker::FreeMemAttr(CheckerContext &C,
436                                            const CallExpr *CE,
437                                            const OwnershipAttr* Att) const {
438   if (Att->getModule() != "malloc")
439     return 0;
440 
441   for (OwnershipAttr::args_iterator I = Att->args_begin(), E = Att->args_end();
442        I != E; ++I) {
443     return FreeMemAux(C, CE, C.getState(), *I,
444                       Att->getOwnKind() == OwnershipAttr::Holds);
445   }
446   return 0;
447 }
448 
449 ProgramStateRef MallocChecker::FreeMemAux(CheckerContext &C,
450                                           const CallExpr *CE,
451                                           ProgramStateRef state,
452                                           unsigned Num,
453                                           bool Hold) const {
454   const Expr *ArgExpr = CE->getArg(Num);
455   SVal ArgVal = state->getSVal(ArgExpr, C.getLocationContext());
456   if (!isa<DefinedOrUnknownSVal>(ArgVal))
457     return 0;
458   DefinedOrUnknownSVal location = cast<DefinedOrUnknownSVal>(ArgVal);
459 
460   // Check for null dereferences.
461   if (!isa<Loc>(location))
462     return 0;
463 
464   // The explicit NULL case, no operation is performed.
465   ProgramStateRef notNullState, nullState;
466   llvm::tie(notNullState, nullState) = state->assume(location);
467   if (nullState && !notNullState)
468     return 0;
469 
470   // Unknown values could easily be okay
471   // Undefined values are handled elsewhere
472   if (ArgVal.isUnknownOrUndef())
473     return 0;
474 
475   const MemRegion *R = ArgVal.getAsRegion();
476 
477   // Nonlocs can't be freed, of course.
478   // Non-region locations (labels and fixed addresses) also shouldn't be freed.
479   if (!R) {
480     ReportBadFree(C, ArgVal, ArgExpr->getSourceRange());
481     return 0;
482   }
483 
484   R = R->StripCasts();
485 
486   // Blocks might show up as heap data, but should not be free()d
487   if (isa<BlockDataRegion>(R)) {
488     ReportBadFree(C, ArgVal, ArgExpr->getSourceRange());
489     return 0;
490   }
491 
492   const MemSpaceRegion *MS = R->getMemorySpace();
493 
494   // Parameters, locals, statics, and globals shouldn't be freed.
495   if (!(isa<UnknownSpaceRegion>(MS) || isa<HeapSpaceRegion>(MS))) {
496     // FIXME: at the time this code was written, malloc() regions were
497     // represented by conjured symbols, which are all in UnknownSpaceRegion.
498     // This means that there isn't actually anything from HeapSpaceRegion
499     // that should be freed, even though we allow it here.
500     // Of course, free() can work on memory allocated outside the current
501     // function, so UnknownSpaceRegion is always a possibility.
502     // False negatives are better than false positives.
503 
504     ReportBadFree(C, ArgVal, ArgExpr->getSourceRange());
505     return 0;
506   }
507 
508   const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R);
509   // Various cases could lead to non-symbol values here.
510   // For now, ignore them.
511   if (!SR)
512     return 0;
513 
514   SymbolRef Sym = SR->getSymbol();
515   const RefState *RS = state->get<RegionState>(Sym);
516 
517   // If the symbol has not been tracked, return. This is possible when free() is
518   // called on a pointer that does not get its pointee directly from malloc().
519   // Full support of this requires inter-procedural analysis.
520   if (!RS)
521     return 0;
522 
523   // Check double free.
524   if (RS->isReleased()) {
525     if (ExplodedNode *N = C.generateSink()) {
526       if (!BT_DoubleFree)
527         BT_DoubleFree.reset(
528           new BugType("Double free", "Memory Error"));
529       BugReport *R = new BugReport(*BT_DoubleFree,
530                         "Attempt to free released memory", N);
531       R->addRange(ArgExpr->getSourceRange());
532       R->addVisitor(new MallocBugVisitor(Sym));
533       C.EmitReport(R);
534     }
535     return 0;
536   }
537 
538   // Normal free.
539   if (Hold)
540     return state->set<RegionState>(Sym, RefState::getRelinquished(CE));
541   return state->set<RegionState>(Sym, RefState::getReleased(CE));
542 }
543 
544 bool MallocChecker::SummarizeValue(raw_ostream &os, SVal V) {
545   if (nonloc::ConcreteInt *IntVal = dyn_cast<nonloc::ConcreteInt>(&V))
546     os << "an integer (" << IntVal->getValue() << ")";
547   else if (loc::ConcreteInt *ConstAddr = dyn_cast<loc::ConcreteInt>(&V))
548     os << "a constant address (" << ConstAddr->getValue() << ")";
549   else if (loc::GotoLabel *Label = dyn_cast<loc::GotoLabel>(&V))
550     os << "the address of the label '" << Label->getLabel()->getName() << "'";
551   else
552     return false;
553 
554   return true;
555 }
556 
557 bool MallocChecker::SummarizeRegion(raw_ostream &os,
558                                     const MemRegion *MR) {
559   switch (MR->getKind()) {
560   case MemRegion::FunctionTextRegionKind: {
561     const FunctionDecl *FD = cast<FunctionTextRegion>(MR)->getDecl();
562     if (FD)
563       os << "the address of the function '" << *FD << '\'';
564     else
565       os << "the address of a function";
566     return true;
567   }
568   case MemRegion::BlockTextRegionKind:
569     os << "block text";
570     return true;
571   case MemRegion::BlockDataRegionKind:
572     // FIXME: where the block came from?
573     os << "a block";
574     return true;
575   default: {
576     const MemSpaceRegion *MS = MR->getMemorySpace();
577 
578     if (isa<StackLocalsSpaceRegion>(MS)) {
579       const VarRegion *VR = dyn_cast<VarRegion>(MR);
580       const VarDecl *VD;
581       if (VR)
582         VD = VR->getDecl();
583       else
584         VD = NULL;
585 
586       if (VD)
587         os << "the address of the local variable '" << VD->getName() << "'";
588       else
589         os << "the address of a local stack variable";
590       return true;
591     }
592 
593     if (isa<StackArgumentsSpaceRegion>(MS)) {
594       const VarRegion *VR = dyn_cast<VarRegion>(MR);
595       const VarDecl *VD;
596       if (VR)
597         VD = VR->getDecl();
598       else
599         VD = NULL;
600 
601       if (VD)
602         os << "the address of the parameter '" << VD->getName() << "'";
603       else
604         os << "the address of a parameter";
605       return true;
606     }
607 
608     if (isa<GlobalsSpaceRegion>(MS)) {
609       const VarRegion *VR = dyn_cast<VarRegion>(MR);
610       const VarDecl *VD;
611       if (VR)
612         VD = VR->getDecl();
613       else
614         VD = NULL;
615 
616       if (VD) {
617         if (VD->isStaticLocal())
618           os << "the address of the static variable '" << VD->getName() << "'";
619         else
620           os << "the address of the global variable '" << VD->getName() << "'";
621       } else
622         os << "the address of a global variable";
623       return true;
624     }
625 
626     return false;
627   }
628   }
629 }
630 
631 void MallocChecker::ReportBadFree(CheckerContext &C, SVal ArgVal,
632                                   SourceRange range) const {
633   if (ExplodedNode *N = C.generateSink()) {
634     if (!BT_BadFree)
635       BT_BadFree.reset(new BugType("Bad free", "Memory Error"));
636 
637     SmallString<100> buf;
638     llvm::raw_svector_ostream os(buf);
639 
640     const MemRegion *MR = ArgVal.getAsRegion();
641     if (MR) {
642       while (const ElementRegion *ER = dyn_cast<ElementRegion>(MR))
643         MR = ER->getSuperRegion();
644 
645       // Special case for alloca()
646       if (isa<AllocaRegion>(MR))
647         os << "Argument to free() was allocated by alloca(), not malloc()";
648       else {
649         os << "Argument to free() is ";
650         if (SummarizeRegion(os, MR))
651           os << ", which is not memory allocated by malloc()";
652         else
653           os << "not memory allocated by malloc()";
654       }
655     } else {
656       os << "Argument to free() is ";
657       if (SummarizeValue(os, ArgVal))
658         os << ", which is not memory allocated by malloc()";
659       else
660         os << "not memory allocated by malloc()";
661     }
662 
663     BugReport *R = new BugReport(*BT_BadFree, os.str(), N);
664     R->addRange(range);
665     C.EmitReport(R);
666   }
667 }
668 
669 ProgramStateRef MallocChecker::ReallocMem(CheckerContext &C,
670                                           const CallExpr *CE,
671                                           bool FreesOnFail) const {
672   ProgramStateRef state = C.getState();
673   const Expr *arg0Expr = CE->getArg(0);
674   const LocationContext *LCtx = C.getLocationContext();
675   SVal Arg0Val = state->getSVal(arg0Expr, LCtx);
676   if (!isa<DefinedOrUnknownSVal>(Arg0Val))
677     return 0;
678   DefinedOrUnknownSVal arg0Val = cast<DefinedOrUnknownSVal>(Arg0Val);
679 
680   SValBuilder &svalBuilder = C.getSValBuilder();
681 
682   DefinedOrUnknownSVal PtrEQ =
683     svalBuilder.evalEQ(state, arg0Val, svalBuilder.makeNull());
684 
685   // Get the size argument. If there is no size arg then give up.
686   const Expr *Arg1 = CE->getArg(1);
687   if (!Arg1)
688     return 0;
689 
690   // Get the value of the size argument.
691   SVal Arg1ValG = state->getSVal(Arg1, LCtx);
692   if (!isa<DefinedOrUnknownSVal>(Arg1ValG))
693     return 0;
694   DefinedOrUnknownSVal Arg1Val = cast<DefinedOrUnknownSVal>(Arg1ValG);
695 
696   // Compare the size argument to 0.
697   DefinedOrUnknownSVal SizeZero =
698     svalBuilder.evalEQ(state, Arg1Val,
699                        svalBuilder.makeIntValWithPtrWidth(0, false));
700 
701   ProgramStateRef StatePtrIsNull, StatePtrNotNull;
702   llvm::tie(StatePtrIsNull, StatePtrNotNull) = state->assume(PtrEQ);
703   ProgramStateRef StateSizeIsZero, StateSizeNotZero;
704   llvm::tie(StateSizeIsZero, StateSizeNotZero) = state->assume(SizeZero);
705   // We only assume exceptional states if they are definitely true; if the
706   // state is under-constrained, assume regular realloc behavior.
707   bool PrtIsNull = StatePtrIsNull && !StatePtrNotNull;
708   bool SizeIsZero = StateSizeIsZero && !StateSizeNotZero;
709 
710   // If the ptr is NULL and the size is not 0, the call is equivalent to
711   // malloc(size).
712   if ( PrtIsNull && !SizeIsZero) {
713     ProgramStateRef stateMalloc = MallocMemAux(C, CE, CE->getArg(1),
714                                                UndefinedVal(), StatePtrIsNull);
715     return stateMalloc;
716   }
717 
718   if (PrtIsNull && SizeIsZero)
719     return 0;
720 
721   // Get the from and to pointer symbols as in toPtr = realloc(fromPtr, size).
722   assert(!PrtIsNull);
723   SymbolRef FromPtr = arg0Val.getAsSymbol();
724   SVal RetVal = state->getSVal(CE, LCtx);
725   SymbolRef ToPtr = RetVal.getAsSymbol();
726   if (!FromPtr || !ToPtr)
727     return 0;
728 
729   // If the size is 0, free the memory.
730   if (SizeIsZero)
731     if (ProgramStateRef stateFree = FreeMemAux(C, CE, StateSizeIsZero,0,false)){
732       // The semantics of the return value are:
733       // If size was equal to 0, either NULL or a pointer suitable to be passed
734       // to free() is returned.
735       stateFree = stateFree->set<ReallocPairs>(ToPtr,
736                                             ReallocPair(FromPtr, FreesOnFail));
737       C.getSymbolManager().addSymbolDependency(ToPtr, FromPtr);
738       return stateFree;
739     }
740 
741   // Default behavior.
742   if (ProgramStateRef stateFree = FreeMemAux(C, CE, state, 0, false)) {
743     // FIXME: We should copy the content of the original buffer.
744     ProgramStateRef stateRealloc = MallocMemAux(C, CE, CE->getArg(1),
745                                                 UnknownVal(), stateFree);
746     if (!stateRealloc)
747       return 0;
748     stateRealloc = stateRealloc->set<ReallocPairs>(ToPtr,
749                                             ReallocPair(FromPtr, FreesOnFail));
750     C.getSymbolManager().addSymbolDependency(ToPtr, FromPtr);
751     return stateRealloc;
752   }
753   return 0;
754 }
755 
756 ProgramStateRef MallocChecker::CallocMem(CheckerContext &C, const CallExpr *CE){
757   ProgramStateRef state = C.getState();
758   SValBuilder &svalBuilder = C.getSValBuilder();
759   const LocationContext *LCtx = C.getLocationContext();
760   SVal count = state->getSVal(CE->getArg(0), LCtx);
761   SVal elementSize = state->getSVal(CE->getArg(1), LCtx);
762   SVal TotalSize = svalBuilder.evalBinOp(state, BO_Mul, count, elementSize,
763                                         svalBuilder.getContext().getSizeType());
764   SVal zeroVal = svalBuilder.makeZeroVal(svalBuilder.getContext().CharTy);
765 
766   return MallocMemAux(C, CE, TotalSize, zeroVal, state);
767 }
768 
769 void MallocChecker::reportLeak(SymbolRef Sym, ExplodedNode *N,
770                                CheckerContext &C) const {
771   assert(N);
772   if (!BT_Leak) {
773     BT_Leak.reset(new BugType("Memory leak", "Memory Error"));
774     // Leaks should not be reported if they are post-dominated by a sink:
775     // (1) Sinks are higher importance bugs.
776     // (2) NoReturnFunctionChecker uses sink nodes to represent paths ending
777     //     with __noreturn functions such as assert() or exit(). We choose not
778     //     to report leaks on such paths.
779     BT_Leak->setSuppressOnSink(true);
780   }
781 
782   BugReport *R = new BugReport(*BT_Leak,
783                   "Memory is never released; potential memory leak", N);
784   R->addVisitor(new MallocBugVisitor(Sym));
785   C.EmitReport(R);
786 }
787 
788 void MallocChecker::checkDeadSymbols(SymbolReaper &SymReaper,
789                                      CheckerContext &C) const
790 {
791   if (!SymReaper.hasDeadSymbols())
792     return;
793 
794   ProgramStateRef state = C.getState();
795   RegionStateTy RS = state->get<RegionState>();
796   RegionStateTy::Factory &F = state->get_context<RegionState>();
797 
798   bool generateReport = false;
799   llvm::SmallVector<SymbolRef, 2> Errors;
800   for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
801     if (SymReaper.isDead(I->first)) {
802       if (I->second.isAllocated()) {
803         generateReport = true;
804         Errors.push_back(I->first);
805       }
806       // Remove the dead symbol from the map.
807       RS = F.remove(RS, I->first);
808 
809     }
810   }
811 
812   // Cleanup the Realloc Pairs Map.
813   ReallocMap RP = state->get<ReallocPairs>();
814   for (ReallocMap::iterator I = RP.begin(), E = RP.end(); I != E; ++I) {
815     if (SymReaper.isDead(I->first) ||
816         SymReaper.isDead(I->second.ReallocatedSym)) {
817       state = state->remove<ReallocPairs>(I->first);
818     }
819   }
820 
821   ExplodedNode *N = C.addTransition(state->set<RegionState>(RS));
822 
823   if (N && generateReport) {
824     for (llvm::SmallVector<SymbolRef, 2>::iterator
825          I = Errors.begin(), E = Errors.end(); I != E; ++I) {
826       reportLeak(*I, N, C);
827     }
828   }
829 }
830 
831 void MallocChecker::checkEndPath(CheckerContext &C) const {
832   ProgramStateRef state = C.getState();
833   RegionStateTy M = state->get<RegionState>();
834 
835   // If inside inlined call, skip it.
836   if (C.getLocationContext()->getParent() != 0)
837     return;
838 
839   for (RegionStateTy::iterator I = M.begin(), E = M.end(); I != E; ++I) {
840     RefState RS = I->second;
841     if (RS.isAllocated()) {
842       ExplodedNode *N = C.addTransition(state);
843       if (N)
844         reportLeak(I->first, N, C);
845     }
846   }
847 }
848 
849 bool MallocChecker::checkEscape(SymbolRef Sym, const Stmt *S,
850                                 CheckerContext &C) const {
851   ProgramStateRef state = C.getState();
852   const RefState *RS = state->get<RegionState>(Sym);
853   if (!RS)
854     return false;
855 
856   if (RS->isAllocated()) {
857     state = state->set<RegionState>(Sym, RefState::getEscaped(S));
858     C.addTransition(state);
859     return true;
860   }
861   return false;
862 }
863 
864 void MallocChecker::checkPreStmt(const CallExpr *CE, CheckerContext &C) const {
865   if (isMemFunction(C.getCalleeDecl(CE), C.getASTContext()))
866     return;
867 
868   // Check use after free, when a freed pointer is passed to a call.
869   ProgramStateRef State = C.getState();
870   for (CallExpr::const_arg_iterator I = CE->arg_begin(),
871                                     E = CE->arg_end(); I != E; ++I) {
872     const Expr *A = *I;
873     if (A->getType().getTypePtr()->isAnyPointerType()) {
874       SymbolRef Sym = State->getSVal(A, C.getLocationContext()).getAsSymbol();
875       if (!Sym)
876         continue;
877       if (checkUseAfterFree(Sym, C, A))
878         return;
879     }
880   }
881 }
882 
883 void MallocChecker::checkPreStmt(const ReturnStmt *S, CheckerContext &C) const {
884   const Expr *E = S->getRetValue();
885   if (!E)
886     return;
887 
888   // Check if we are returning a symbol.
889   SVal RetVal = C.getState()->getSVal(E, C.getLocationContext());
890   SymbolRef Sym = RetVal.getAsSymbol();
891   if (!Sym)
892     // If we are returning a field of the allocated struct or an array element,
893     // the callee could still free the memory.
894     // TODO: This logic should be a part of generic symbol escape callback.
895     if (const MemRegion *MR = RetVal.getAsRegion())
896       if (isa<FieldRegion>(MR) || isa<ElementRegion>(MR))
897         if (const SymbolicRegion *BMR =
898               dyn_cast<SymbolicRegion>(MR->getBaseRegion()))
899           Sym = BMR->getSymbol();
900   if (!Sym)
901     return;
902 
903   // Check if we are returning freed memory.
904   if (checkUseAfterFree(Sym, C, E))
905     return;
906 
907   // If this function body is not inlined, check if the symbol is escaping.
908   if (C.getLocationContext()->getParent() == 0)
909     checkEscape(Sym, E, C);
910 }
911 
912 bool MallocChecker::checkUseAfterFree(SymbolRef Sym, CheckerContext &C,
913                                       const Stmt *S) const {
914   assert(Sym);
915   const RefState *RS = C.getState()->get<RegionState>(Sym);
916   if (RS && RS->isReleased()) {
917     if (ExplodedNode *N = C.generateSink()) {
918       if (!BT_UseFree)
919         BT_UseFree.reset(new BugType("Use-after-free", "Memory Error"));
920 
921       BugReport *R = new BugReport(*BT_UseFree,
922                                    "Use of memory after it is freed",N);
923       if (S)
924         R->addRange(S->getSourceRange());
925       R->addVisitor(new MallocBugVisitor(Sym));
926       C.EmitReport(R);
927       return true;
928     }
929   }
930   return false;
931 }
932 
933 // Check if the location is a freed symbolic region.
934 void MallocChecker::checkLocation(SVal l, bool isLoad, const Stmt *S,
935                                   CheckerContext &C) const {
936   SymbolRef Sym = l.getLocSymbolInBase();
937   if (Sym)
938     checkUseAfterFree(Sym, C);
939 }
940 
941 //===----------------------------------------------------------------------===//
942 // Check various ways a symbol can be invalidated.
943 // TODO: This logic (the next 3 functions) is copied/similar to the
944 // RetainRelease checker. We might want to factor this out.
945 //===----------------------------------------------------------------------===//
946 
947 // Stop tracking symbols when a value escapes as a result of checkBind.
948 // A value escapes in three possible cases:
949 // (1) we are binding to something that is not a memory region.
950 // (2) we are binding to a memregion that does not have stack storage
951 // (3) we are binding to a memregion with stack storage that the store
952 //     does not understand.
953 void MallocChecker::checkBind(SVal loc, SVal val, const Stmt *S,
954                               CheckerContext &C) const {
955   // Are we storing to something that causes the value to "escape"?
956   bool escapes = true;
957   ProgramStateRef state = C.getState();
958 
959   if (loc::MemRegionVal *regionLoc = dyn_cast<loc::MemRegionVal>(&loc)) {
960     escapes = !regionLoc->getRegion()->hasStackStorage();
961 
962     if (!escapes) {
963       // To test (3), generate a new state with the binding added.  If it is
964       // the same state, then it escapes (since the store cannot represent
965       // the binding).
966       escapes = (state == (state->bindLoc(*regionLoc, val)));
967     }
968     if (!escapes) {
969       // Case 4: We do not currently model what happens when a symbol is
970       // assigned to a struct field, so be conservative here and let the symbol
971       // go. TODO: This could definitely be improved upon.
972       escapes = !isa<VarRegion>(regionLoc->getRegion());
973     }
974   }
975 
976   // If our store can represent the binding and we aren't storing to something
977   // that doesn't have local storage then just return and have the simulation
978   // state continue as is.
979   if (!escapes)
980       return;
981 
982   // Otherwise, find all symbols referenced by 'val' that we are tracking
983   // and stop tracking them.
984   state = state->scanReachableSymbols<StopTrackingCallback>(val).getState();
985   C.addTransition(state);
986 }
987 
988 // If a symbolic region is assumed to NULL (or another constant), stop tracking
989 // it - assuming that allocation failed on this path.
990 ProgramStateRef MallocChecker::evalAssume(ProgramStateRef state,
991                                               SVal Cond,
992                                               bool Assumption) const {
993   RegionStateTy RS = state->get<RegionState>();
994   for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
995     // If the symbol is assumed to NULL or another constant, this will
996     // return an APSInt*.
997     if (state->getSymVal(I.getKey()))
998       state = state->remove<RegionState>(I.getKey());
999   }
1000 
1001   // Realloc returns 0 when reallocation fails, which means that we should
1002   // restore the state of the pointer being reallocated.
1003   ReallocMap RP = state->get<ReallocPairs>();
1004   for (ReallocMap::iterator I = RP.begin(), E = RP.end(); I != E; ++I) {
1005     // If the symbol is assumed to NULL or another constant, this will
1006     // return an APSInt*.
1007     if (state->getSymVal(I.getKey())) {
1008       SymbolRef ReallocSym = I.getData().ReallocatedSym;
1009       const RefState *RS = state->get<RegionState>(ReallocSym);
1010       if (RS) {
1011         if (RS->isReleased() && ! I.getData().IsFreeOnFailure)
1012           state = state->set<RegionState>(ReallocSym,
1013                              RefState::getAllocateUnchecked(RS->getStmt()));
1014       }
1015       state = state->remove<ReallocPairs>(I.getKey());
1016     }
1017   }
1018 
1019   return state;
1020 }
1021 
1022 // Check if the function is not known to us. So, for example, we could
1023 // conservatively assume it can free/reallocate it's pointer arguments.
1024 // (We assume that the pointers cannot escape through calls to system
1025 // functions not handled by this checker.)
1026 bool MallocChecker::hasUnknownBehavior(const FunctionDecl *FD,
1027                                        ProgramStateRef State) const {
1028   ASTContext &ASTC = State->getStateManager().getContext();
1029 
1030   // If it's one of the allocation functions we can reason about, we model it's
1031   // behavior explicitly.
1032   if (isMemFunction(FD, ASTC)) {
1033     return false;
1034   }
1035 
1036   // If it's a system call, we know it does not free the memory.
1037   SourceManager &SM = ASTC.getSourceManager();
1038   if (SM.isInSystemHeader(FD->getLocation())) {
1039     return false;
1040   }
1041 
1042   // Otherwise, assume that the function can free memory.
1043   return true;
1044 }
1045 
1046 // If the symbol we are tracking is invalidated, but not explicitly (ex: the &p
1047 // escapes, when we are tracking p), do not track the symbol as we cannot reason
1048 // about it anymore.
1049 ProgramStateRef
1050 MallocChecker::checkRegionChanges(ProgramStateRef State,
1051                             const StoreManager::InvalidatedSymbols *invalidated,
1052                                     ArrayRef<const MemRegion *> ExplicitRegions,
1053                                     ArrayRef<const MemRegion *> Regions,
1054                                     const CallOrObjCMessage *Call) const {
1055   if (!invalidated)
1056     return State;
1057   llvm::SmallPtrSet<SymbolRef, 8> WhitelistedSymbols;
1058 
1059   const FunctionDecl *FD = (Call ?
1060                             dyn_cast_or_null<FunctionDecl>(Call->getDecl()) :0);
1061 
1062   // If it's a call which might free or reallocate memory, we assume that all
1063   // regions (explicit and implicit) escaped. Otherwise, whitelist explicit
1064   // pointers; we still can track them.
1065   if (!(FD && hasUnknownBehavior(FD, State))) {
1066     for (ArrayRef<const MemRegion *>::iterator I = ExplicitRegions.begin(),
1067         E = ExplicitRegions.end(); I != E; ++I) {
1068       if (const SymbolicRegion *R = (*I)->StripCasts()->getAs<SymbolicRegion>())
1069         WhitelistedSymbols.insert(R->getSymbol());
1070     }
1071   }
1072 
1073   for (StoreManager::InvalidatedSymbols::const_iterator I=invalidated->begin(),
1074        E = invalidated->end(); I!=E; ++I) {
1075     SymbolRef sym = *I;
1076     if (WhitelistedSymbols.count(sym))
1077       continue;
1078     // The symbol escaped.
1079     if (const RefState *RS = State->get<RegionState>(sym))
1080       State = State->set<RegionState>(sym, RefState::getEscaped(RS->getStmt()));
1081   }
1082   return State;
1083 }
1084 
1085 PathDiagnosticPiece *
1086 MallocChecker::MallocBugVisitor::VisitNode(const ExplodedNode *N,
1087                                            const ExplodedNode *PrevN,
1088                                            BugReporterContext &BRC,
1089                                            BugReport &BR) {
1090   const RefState *RS = N->getState()->get<RegionState>(Sym);
1091   const RefState *RSPrev = PrevN->getState()->get<RegionState>(Sym);
1092   if (!RS && !RSPrev)
1093     return 0;
1094 
1095   const Stmt *S = 0;
1096   const char *Msg = 0;
1097 
1098   // Retrieve the associated statement.
1099   ProgramPoint ProgLoc = N->getLocation();
1100   if (isa<StmtPoint>(ProgLoc))
1101     S = cast<StmtPoint>(ProgLoc).getStmt();
1102   // If an assumption was made on a branch, it should be caught
1103   // here by looking at the state transition.
1104   if (isa<BlockEdge>(ProgLoc)) {
1105     const CFGBlock *srcBlk = cast<BlockEdge>(ProgLoc).getSrc();
1106     S = srcBlk->getTerminator();
1107   }
1108   if (!S)
1109     return 0;
1110 
1111   // Find out if this is an interesting point and what is the kind.
1112   if (Mode == Normal) {
1113     if (isAllocated(RS, RSPrev, S))
1114       Msg = "Memory is allocated";
1115     else if (isReleased(RS, RSPrev, S))
1116       Msg = "Memory is released";
1117     else if (isReallocFailedCheck(RS, RSPrev, S)) {
1118       Mode = ReallocationFailed;
1119       Msg = "Reallocation failed";
1120     }
1121 
1122   // We are in a special mode if a reallocation failed later in the path.
1123   } else if (Mode == ReallocationFailed) {
1124     // Generate a special diagnostic for the first realloc we find.
1125     if (!isAllocated(RS, RSPrev, S) && !isReleased(RS, RSPrev, S))
1126       return 0;
1127 
1128     // Check that the name of the function is realloc.
1129     const CallExpr *CE = dyn_cast<CallExpr>(S);
1130     if (!CE)
1131       return 0;
1132     const FunctionDecl *funDecl = CE->getDirectCallee();
1133     if (!funDecl)
1134       return 0;
1135     StringRef FunName = funDecl->getName();
1136     if (!(FunName.equals("realloc") || FunName.equals("reallocf")))
1137       return 0;
1138     Msg = "Attempt to reallocate memory";
1139     Mode = Normal;
1140   }
1141 
1142   if (!Msg)
1143     return 0;
1144 
1145   // Generate the extra diagnostic.
1146   PathDiagnosticLocation Pos(S, BRC.getSourceManager(),
1147                              N->getLocationContext());
1148   return new PathDiagnosticEventPiece(Pos, Msg);
1149 }
1150 
1151 
1152 #define REGISTER_CHECKER(name) \
1153 void ento::register##name(CheckerManager &mgr) {\
1154   registerCStringCheckerBasic(mgr); \
1155   mgr.registerChecker<MallocChecker>()->Filter.C##name = true;\
1156 }
1157 
1158 REGISTER_CHECKER(MallocPessimistic)
1159 REGISTER_CHECKER(MallocOptimistic)
1160