MallocChecker.cpp revision 91c2a1192cdd4e7b2b4ac7838c5aceef200ea251 
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"
26using namespace clang;
27using namespace ento;
28
29namespace {
30
31class RefState {
32  enum Kind { AllocateUnchecked, AllocateFailed, Released, Escaped,
33              Relinquished } K;
34  const Stmt *S;
35
36public:
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
67class RegionState {};
68
69class 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{
77  mutable OwningPtr<BuiltinBug> BT_DoubleFree;
78  mutable OwningPtr<BuiltinBug> BT_Leak;
79  mutable OwningPtr<BuiltinBug> BT_UseFree;
80  mutable OwningPtr<BuiltinBug> BT_UseRelinquished;
81  mutable OwningPtr<BuiltinBug> BT_BadFree;
82  mutable IdentifierInfo *II_malloc, *II_free, *II_realloc, *II_calloc;
83
84public:
85  MallocChecker() : II_malloc(0), II_free(0), II_realloc(0), II_calloc(0) {}
86
87  /// In pessimistic mode, the checker assumes that it does not know which
88  /// functions might free the memory.
89  struct ChecksFilter {
90    DefaultBool CMallocPessimistic;
91    DefaultBool CMallocOptimistic;
92  };
93
94  ChecksFilter Filter;
95
96  void initIdentifierInfo(CheckerContext &C) const;
97
98  void checkPostStmt(const CallExpr *CE, CheckerContext &C) const;
99  void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const;
100  void checkEndPath(CheckerContext &C) const;
101  void checkPreStmt(const ReturnStmt *S, CheckerContext &C) const;
102  ProgramStateRef evalAssume(ProgramStateRef state, SVal Cond,
103                            bool Assumption) const;
104  void checkLocation(SVal l, bool isLoad, const Stmt *S,
105                     CheckerContext &C) const;
106  void checkBind(SVal location, SVal val, const Stmt*S,
107                 CheckerContext &C) const;
108
109private:
110  static void MallocMem(CheckerContext &C, const CallExpr *CE);
111  static void MallocMemReturnsAttr(CheckerContext &C, const CallExpr *CE,
112                                   const OwnershipAttr* Att);
113  static ProgramStateRef MallocMemAux(CheckerContext &C, const CallExpr *CE,
114                                     const Expr *SizeEx, SVal Init,
115                                     ProgramStateRef state) {
116    return MallocMemAux(C, CE,
117                        state->getSVal(SizeEx, C.getLocationContext()),
118                        Init, state);
119  }
120  static ProgramStateRef MallocMemAux(CheckerContext &C, const CallExpr *CE,
121                                     SVal SizeEx, SVal Init,
122                                     ProgramStateRef state);
123
124  void FreeMem(CheckerContext &C, const CallExpr *CE) const;
125  void FreeMemAttr(CheckerContext &C, const CallExpr *CE,
126                   const OwnershipAttr* Att) const;
127  ProgramStateRef FreeMemAux(CheckerContext &C, const CallExpr *CE,
128                                 ProgramStateRef state, unsigned Num,
129                                 bool Hold) const;
130
131  void ReallocMem(CheckerContext &C, const CallExpr *CE) const;
132  static void CallocMem(CheckerContext &C, const CallExpr *CE);
133
134  bool checkEscape(SymbolRef Sym, const Stmt *S, CheckerContext &C) const;
135  bool checkUseAfterFree(SymbolRef Sym, CheckerContext &C,
136                         const Stmt *S = 0) const;
137
138  static bool SummarizeValue(raw_ostream &os, SVal V);
139  static bool SummarizeRegion(raw_ostream &os, const MemRegion *MR);
140  void ReportBadFree(CheckerContext &C, SVal ArgVal, SourceRange range) const;
141};
142} // end anonymous namespace
143
144typedef llvm::ImmutableMap<SymbolRef, RefState> RegionStateTy;
145
146namespace clang {
147namespace ento {
148  template <>
149  struct ProgramStateTrait<RegionState>
150    : public ProgramStatePartialTrait<RegionStateTy> {
151    static void *GDMIndex() { static int x; return &x; }
152  };
153}
154}
155
156void MallocChecker::initIdentifierInfo(CheckerContext &C) const {
157  ASTContext &Ctx = C.getASTContext();
158  if (!II_malloc)
159    II_malloc = &Ctx.Idents.get("malloc");
160  if (!II_free)
161    II_free = &Ctx.Idents.get("free");
162  if (!II_realloc)
163    II_realloc = &Ctx.Idents.get("realloc");
164  if (!II_calloc)
165    II_calloc = &Ctx.Idents.get("calloc");
166}
167
168void MallocChecker::checkPostStmt(const CallExpr *CE, CheckerContext &C) const {
169  const FunctionDecl *FD = C.getCalleeDecl(CE);
170  if (!FD)
171    return;
172  initIdentifierInfo(C);
173
174  if (FD->getIdentifier() == II_malloc) {
175    MallocMem(C, CE);
176    return;
177  }
178  if (FD->getIdentifier() == II_realloc) {
179    ReallocMem(C, CE);
180    return;
181  }
182
183  if (FD->getIdentifier() == II_calloc) {
184    CallocMem(C, CE);
185    return;
186  }
187
188  if (FD->getIdentifier() == II_free) {
189    FreeMem(C, CE);
190    return;
191  }
192
193  if (Filter.CMallocOptimistic)
194  // Check all the attributes, if there are any.
195  // There can be multiple of these attributes.
196  if (FD->hasAttrs()) {
197    for (specific_attr_iterator<OwnershipAttr>
198                  i = FD->specific_attr_begin<OwnershipAttr>(),
199                  e = FD->specific_attr_end<OwnershipAttr>();
200         i != e; ++i) {
201      switch ((*i)->getOwnKind()) {
202      case OwnershipAttr::Returns: {
203        MallocMemReturnsAttr(C, CE, *i);
204        break;
205      }
206      case OwnershipAttr::Takes:
207      case OwnershipAttr::Holds: {
208        FreeMemAttr(C, CE, *i);
209        break;
210      }
211      }
212    }
213  }
214
215  if (Filter.CMallocPessimistic) {
216    ProgramStateRef State = C.getState();
217    // The pointer might escape through a function call.
218    for (CallExpr::const_arg_iterator I = CE->arg_begin(),
219                                      E = CE->arg_end(); I != E; ++I) {
220      const Expr *A = *I;
221      if (A->getType().getTypePtr()->isAnyPointerType()) {
222        SymbolRef Sym = State->getSVal(A, C.getLocationContext()).getAsSymbol();
223        if (!Sym)
224          return;
225        checkEscape(Sym, A, C);
226        checkUseAfterFree(Sym, C, A);
227      }
228    }
229  }
230}
231
232void MallocChecker::MallocMem(CheckerContext &C, const CallExpr *CE) {
233  ProgramStateRef state = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(),
234                                      C.getState());
235  C.addTransition(state);
236}
237
238void MallocChecker::MallocMemReturnsAttr(CheckerContext &C, const CallExpr *CE,
239                                         const OwnershipAttr* Att) {
240  if (Att->getModule() != "malloc")
241    return;
242
243  OwnershipAttr::args_iterator I = Att->args_begin(), E = Att->args_end();
244  if (I != E) {
245    ProgramStateRef state =
246        MallocMemAux(C, CE, CE->getArg(*I), UndefinedVal(), C.getState());
247    C.addTransition(state);
248    return;
249  }
250  ProgramStateRef state = MallocMemAux(C, CE, UnknownVal(), UndefinedVal(),
251                                        C.getState());
252  C.addTransition(state);
253}
254
255ProgramStateRef MallocChecker::MallocMemAux(CheckerContext &C,
256                                           const CallExpr *CE,
257                                           SVal Size, SVal Init,
258                                           ProgramStateRef state) {
259  SValBuilder &svalBuilder = C.getSValBuilder();
260
261  // Get the return value.
262  SVal retVal = state->getSVal(CE, C.getLocationContext());
263
264  // Fill the region with the initialization value.
265  state = state->bindDefault(retVal, Init);
266
267  // Set the region's extent equal to the Size parameter.
268  const SymbolicRegion *R = cast<SymbolicRegion>(retVal.getAsRegion());
269  DefinedOrUnknownSVal Extent = R->getExtent(svalBuilder);
270  DefinedOrUnknownSVal DefinedSize = cast<DefinedOrUnknownSVal>(Size);
271  DefinedOrUnknownSVal extentMatchesSize =
272    svalBuilder.evalEQ(state, Extent, DefinedSize);
273
274  state = state->assume(extentMatchesSize, true);
275  assert(state);
276
277  SymbolRef Sym = retVal.getAsLocSymbol();
278  assert(Sym);
279
280  // Set the symbol's state to Allocated.
281  return state->set<RegionState>(Sym, RefState::getAllocateUnchecked(CE));
282}
283
284void MallocChecker::FreeMem(CheckerContext &C, const CallExpr *CE) const {
285  ProgramStateRef state = FreeMemAux(C, CE, C.getState(), 0, false);
286
287  if (state)
288    C.addTransition(state);
289}
290
291void MallocChecker::FreeMemAttr(CheckerContext &C, const CallExpr *CE,
292                                const OwnershipAttr* Att) const {
293  if (Att->getModule() != "malloc")
294    return;
295
296  for (OwnershipAttr::args_iterator I = Att->args_begin(), E = Att->args_end();
297       I != E; ++I) {
298    ProgramStateRef state =
299      FreeMemAux(C, CE, C.getState(), *I,
300                 Att->getOwnKind() == OwnershipAttr::Holds);
301    if (state)
302      C.addTransition(state);
303  }
304}
305
306ProgramStateRef MallocChecker::FreeMemAux(CheckerContext &C,
307                                              const CallExpr *CE,
308                                              ProgramStateRef state,
309                                              unsigned Num,
310                                              bool Hold) const {
311  const Expr *ArgExpr = CE->getArg(Num);
312  SVal ArgVal = state->getSVal(ArgExpr, C.getLocationContext());
313
314  DefinedOrUnknownSVal location = cast<DefinedOrUnknownSVal>(ArgVal);
315
316  // Check for null dereferences.
317  if (!isa<Loc>(location))
318    return 0;
319
320  // FIXME: Technically using 'Assume' here can result in a path
321  //  bifurcation.  In such cases we need to return two states, not just one.
322  ProgramStateRef notNullState, nullState;
323  llvm::tie(notNullState, nullState) = state->assume(location);
324
325  // The explicit NULL case, no operation is performed.
326  if (nullState && !notNullState)
327    return 0;
328
329  assert(notNullState);
330
331  // Unknown values could easily be okay
332  // Undefined values are handled elsewhere
333  if (ArgVal.isUnknownOrUndef())
334    return 0;
335
336  const MemRegion *R = ArgVal.getAsRegion();
337
338  // Nonlocs can't be freed, of course.
339  // Non-region locations (labels and fixed addresses) also shouldn't be freed.
340  if (!R) {
341    ReportBadFree(C, ArgVal, ArgExpr->getSourceRange());
342    return 0;
343  }
344
345  R = R->StripCasts();
346
347  // Blocks might show up as heap data, but should not be free()d
348  if (isa<BlockDataRegion>(R)) {
349    ReportBadFree(C, ArgVal, ArgExpr->getSourceRange());
350    return 0;
351  }
352
353  const MemSpaceRegion *MS = R->getMemorySpace();
354
355  // TODO: Pessimize this. should be behinds a flag!
356  // Parameters, locals, statics, and globals shouldn't be freed.
357  if (!(isa<UnknownSpaceRegion>(MS) || isa<HeapSpaceRegion>(MS))) {
358    // FIXME: at the time this code was written, malloc() regions were
359    // represented by conjured symbols, which are all in UnknownSpaceRegion.
360    // This means that there isn't actually anything from HeapSpaceRegion
361    // that should be freed, even though we allow it here.
362    // Of course, free() can work on memory allocated outside the current
363    // function, so UnknownSpaceRegion is always a possibility.
364    // False negatives are better than false positives.
365
366    ReportBadFree(C, ArgVal, ArgExpr->getSourceRange());
367    return 0;
368  }
369
370  const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R);
371  // Various cases could lead to non-symbol values here.
372  // For now, ignore them.
373  if (!SR)
374    return 0;
375
376  SymbolRef Sym = SR->getSymbol();
377  const RefState *RS = state->get<RegionState>(Sym);
378
379  // If the symbol has not been tracked, return. This is possible when free() is
380  // called on a pointer that does not get its pointee directly from malloc().
381  // Full support of this requires inter-procedural analysis.
382  if (!RS)
383    return 0;
384
385  // Check double free.
386  if (RS->isReleased()) {
387    if (ExplodedNode *N = C.generateSink()) {
388      if (!BT_DoubleFree)
389        BT_DoubleFree.reset(
390          new BuiltinBug("Double free",
391                         "Try to free a memory block that has been released"));
392      // FIXME: should find where it's freed last time.
393      BugReport *R = new BugReport(*BT_DoubleFree,
394                                   BT_DoubleFree->getDescription(), N);
395      C.EmitReport(R);
396    }
397    return 0;
398  }
399
400  // Normal free.
401  if (Hold)
402    return notNullState->set<RegionState>(Sym, RefState::getRelinquished(CE));
403  return notNullState->set<RegionState>(Sym, RefState::getReleased(CE));
404}
405
406bool MallocChecker::SummarizeValue(raw_ostream &os, SVal V) {
407  if (nonloc::ConcreteInt *IntVal = dyn_cast<nonloc::ConcreteInt>(&V))
408    os << "an integer (" << IntVal->getValue() << ")";
409  else if (loc::ConcreteInt *ConstAddr = dyn_cast<loc::ConcreteInt>(&V))
410    os << "a constant address (" << ConstAddr->getValue() << ")";
411  else if (loc::GotoLabel *Label = dyn_cast<loc::GotoLabel>(&V))
412    os << "the address of the label '" << Label->getLabel()->getName() << "'";
413  else
414    return false;
415
416  return true;
417}
418
419bool MallocChecker::SummarizeRegion(raw_ostream &os,
420                                    const MemRegion *MR) {
421  switch (MR->getKind()) {
422  case MemRegion::FunctionTextRegionKind: {
423    const FunctionDecl *FD = cast<FunctionTextRegion>(MR)->getDecl();
424    if (FD)
425      os << "the address of the function '" << *FD << '\'';
426    else
427      os << "the address of a function";
428    return true;
429  }
430  case MemRegion::BlockTextRegionKind:
431    os << "block text";
432    return true;
433  case MemRegion::BlockDataRegionKind:
434    // FIXME: where the block came from?
435    os << "a block";
436    return true;
437  default: {
438    const MemSpaceRegion *MS = MR->getMemorySpace();
439
440    if (isa<StackLocalsSpaceRegion>(MS)) {
441      const VarRegion *VR = dyn_cast<VarRegion>(MR);
442      const VarDecl *VD;
443      if (VR)
444        VD = VR->getDecl();
445      else
446        VD = NULL;
447
448      if (VD)
449        os << "the address of the local variable '" << VD->getName() << "'";
450      else
451        os << "the address of a local stack variable";
452      return true;
453    }
454
455    if (isa<StackArgumentsSpaceRegion>(MS)) {
456      const VarRegion *VR = dyn_cast<VarRegion>(MR);
457      const VarDecl *VD;
458      if (VR)
459        VD = VR->getDecl();
460      else
461        VD = NULL;
462
463      if (VD)
464        os << "the address of the parameter '" << VD->getName() << "'";
465      else
466        os << "the address of a parameter";
467      return true;
468    }
469
470    if (isa<GlobalsSpaceRegion>(MS)) {
471      const VarRegion *VR = dyn_cast<VarRegion>(MR);
472      const VarDecl *VD;
473      if (VR)
474        VD = VR->getDecl();
475      else
476        VD = NULL;
477
478      if (VD) {
479        if (VD->isStaticLocal())
480          os << "the address of the static variable '" << VD->getName() << "'";
481        else
482          os << "the address of the global variable '" << VD->getName() << "'";
483      } else
484        os << "the address of a global variable";
485      return true;
486    }
487
488    return false;
489  }
490  }
491}
492
493void MallocChecker::ReportBadFree(CheckerContext &C, SVal ArgVal,
494                                  SourceRange range) const {
495  if (ExplodedNode *N = C.generateSink()) {
496    if (!BT_BadFree)
497      BT_BadFree.reset(new BuiltinBug("Bad free"));
498
499    SmallString<100> buf;
500    llvm::raw_svector_ostream os(buf);
501
502    const MemRegion *MR = ArgVal.getAsRegion();
503    if (MR) {
504      while (const ElementRegion *ER = dyn_cast<ElementRegion>(MR))
505        MR = ER->getSuperRegion();
506
507      // Special case for alloca()
508      if (isa<AllocaRegion>(MR))
509        os << "Argument to free() was allocated by alloca(), not malloc()";
510      else {
511        os << "Argument to free() is ";
512        if (SummarizeRegion(os, MR))
513          os << ", which is not memory allocated by malloc()";
514        else
515          os << "not memory allocated by malloc()";
516      }
517    } else {
518      os << "Argument to free() is ";
519      if (SummarizeValue(os, ArgVal))
520        os << ", which is not memory allocated by malloc()";
521      else
522        os << "not memory allocated by malloc()";
523    }
524
525    BugReport *R = new BugReport(*BT_BadFree, os.str(), N);
526    R->addRange(range);
527    C.EmitReport(R);
528  }
529}
530
531void MallocChecker::ReallocMem(CheckerContext &C, const CallExpr *CE) const {
532  ProgramStateRef state = C.getState();
533  const Expr *arg0Expr = CE->getArg(0);
534  const LocationContext *LCtx = C.getLocationContext();
535  DefinedOrUnknownSVal arg0Val
536    = cast<DefinedOrUnknownSVal>(state->getSVal(arg0Expr, LCtx));
537
538  SValBuilder &svalBuilder = C.getSValBuilder();
539
540  DefinedOrUnknownSVal PtrEQ =
541    svalBuilder.evalEQ(state, arg0Val, svalBuilder.makeNull());
542
543  // Get the size argument. If there is no size arg then give up.
544  const Expr *Arg1 = CE->getArg(1);
545  if (!Arg1)
546    return;
547
548  // Get the value of the size argument.
549  DefinedOrUnknownSVal Arg1Val =
550    cast<DefinedOrUnknownSVal>(state->getSVal(Arg1, LCtx));
551
552  // Compare the size argument to 0.
553  DefinedOrUnknownSVal SizeZero =
554    svalBuilder.evalEQ(state, Arg1Val,
555                       svalBuilder.makeIntValWithPtrWidth(0, false));
556
557  // If the ptr is NULL and the size is not 0, the call is equivalent to
558  // malloc(size).
559  ProgramStateRef stateEqual = state->assume(PtrEQ, true);
560  if (stateEqual && state->assume(SizeZero, false)) {
561    // Hack: set the NULL symbolic region to released to suppress false warning.
562    // In the future we should add more states for allocated regions, e.g.,
563    // CheckedNull, CheckedNonNull.
564
565    SymbolRef Sym = arg0Val.getAsLocSymbol();
566    if (Sym)
567      stateEqual = stateEqual->set<RegionState>(Sym, RefState::getReleased(CE));
568
569    ProgramStateRef stateMalloc = MallocMemAux(C, CE, CE->getArg(1),
570                                              UndefinedVal(), stateEqual);
571    C.addTransition(stateMalloc);
572  }
573
574  if (ProgramStateRef stateNotEqual = state->assume(PtrEQ, false)) {
575    // If the size is 0, free the memory.
576    if (ProgramStateRef stateSizeZero =
577          stateNotEqual->assume(SizeZero, true))
578      if (ProgramStateRef stateFree =
579          FreeMemAux(C, CE, stateSizeZero, 0, false)) {
580
581        // Bind the return value to NULL because it is now free.
582        C.addTransition(stateFree->BindExpr(CE, LCtx,
583                                            svalBuilder.makeNull(), true));
584      }
585    if (ProgramStateRef stateSizeNotZero =
586          stateNotEqual->assume(SizeZero,false))
587      if (ProgramStateRef stateFree = FreeMemAux(C, CE, stateSizeNotZero,
588                                                0, false)) {
589        // FIXME: We should copy the content of the original buffer.
590        ProgramStateRef stateRealloc = MallocMemAux(C, CE, CE->getArg(1),
591                                                   UnknownVal(), stateFree);
592        C.addTransition(stateRealloc);
593      }
594  }
595}
596
597void MallocChecker::CallocMem(CheckerContext &C, const CallExpr *CE) {
598  ProgramStateRef state = C.getState();
599  SValBuilder &svalBuilder = C.getSValBuilder();
600  const LocationContext *LCtx = C.getLocationContext();
601  SVal count = state->getSVal(CE->getArg(0), LCtx);
602  SVal elementSize = state->getSVal(CE->getArg(1), LCtx);
603  SVal TotalSize = svalBuilder.evalBinOp(state, BO_Mul, count, elementSize,
604                                        svalBuilder.getContext().getSizeType());
605  SVal zeroVal = svalBuilder.makeZeroVal(svalBuilder.getContext().CharTy);
606
607  C.addTransition(MallocMemAux(C, CE, TotalSize, zeroVal, state));
608}
609
610void MallocChecker::checkDeadSymbols(SymbolReaper &SymReaper,
611                                     CheckerContext &C) const
612{
613  if (!SymReaper.hasDeadSymbols())
614    return;
615
616  ProgramStateRef state = C.getState();
617  RegionStateTy RS = state->get<RegionState>();
618  RegionStateTy::Factory &F = state->get_context<RegionState>();
619
620  bool generateReport = false;
621
622  for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
623    if (SymReaper.isDead(I->first)) {
624      if (I->second.isAllocated())
625        generateReport = true;
626
627      // Remove the dead symbol from the map.
628      RS = F.remove(RS, I->first);
629
630    }
631  }
632
633  ExplodedNode *N = C.addTransition(state->set<RegionState>(RS));
634
635  // FIXME: This does not handle when we have multiple leaks at a single
636  // place.
637  if (N && generateReport) {
638    if (!BT_Leak)
639      BT_Leak.reset(new BuiltinBug("Memory leak",
640              "Allocated memory never released. Potential memory leak."));
641    // FIXME: where it is allocated.
642    BugReport *R = new BugReport(*BT_Leak, BT_Leak->getDescription(), N);
643    C.EmitReport(R);
644  }
645}
646
647void MallocChecker::checkEndPath(CheckerContext &Ctx) const {
648  ProgramStateRef state = Ctx.getState();
649  RegionStateTy M = state->get<RegionState>();
650
651  for (RegionStateTy::iterator I = M.begin(), E = M.end(); I != E; ++I) {
652    RefState RS = I->second;
653    if (RS.isAllocated()) {
654      ExplodedNode *N = Ctx.addTransition(state);
655      if (N) {
656        if (!BT_Leak)
657          BT_Leak.reset(new BuiltinBug("Memory leak",
658                    "Allocated memory never released. Potential memory leak."));
659        BugReport *R = new BugReport(*BT_Leak, BT_Leak->getDescription(), N);
660        Ctx.EmitReport(R);
661      }
662    }
663  }
664}
665
666bool MallocChecker::checkEscape(SymbolRef Sym, const Stmt *S,
667                                CheckerContext &C) const {
668  ProgramStateRef state = C.getState();
669  const RefState *RS = state->get<RegionState>(Sym);
670  if (!RS)
671    return false;
672
673  if (RS->isAllocated()) {
674    state = state->set<RegionState>(Sym, RefState::getEscaped(S));
675    C.addTransition(state);
676    return true;
677  }
678  return false;
679}
680
681void MallocChecker::checkPreStmt(const ReturnStmt *S, CheckerContext &C) const {
682  const Expr *E = S->getRetValue();
683  if (!E)
684    return;
685  SymbolRef Sym = C.getState()->getSVal(E, C.getLocationContext()).getAsSymbol();
686  if (!Sym)
687    return;
688
689  checkEscape(Sym, S, C);
690}
691
692ProgramStateRef MallocChecker::evalAssume(ProgramStateRef state,
693                                              SVal Cond,
694                                              bool Assumption) const {
695  // If a symbolic region is assumed to NULL, set its state to AllocateFailed.
696  // FIXME: should also check symbols assumed to non-null.
697
698  RegionStateTy RS = state->get<RegionState>();
699
700  for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
701    // If the symbol is assumed to NULL, this will return an APSInt*.
702    if (state->getSymVal(I.getKey()))
703      state = state->set<RegionState>(I.getKey(),RefState::getAllocateFailed());
704  }
705
706  return state;
707}
708
709bool MallocChecker::checkUseAfterFree(SymbolRef Sym, CheckerContext &C,
710                                      const Stmt *S) const {
711  assert(Sym);
712  const RefState *RS = C.getState()->get<RegionState>(Sym);
713  if (RS && RS->isReleased()) {
714    if (ExplodedNode *N = C.addTransition()) {
715      if (!BT_UseFree)
716        BT_UseFree.reset(new BuiltinBug("Use dynamically allocated memory "
717            "after it is freed."));
718
719      BugReport *R = new BugReport(*BT_UseFree, BT_UseFree->getDescription(),N);
720      if (S)
721        R->addRange(S->getSourceRange());
722      C.EmitReport(R);
723      return true;
724    }
725  }
726  return false;
727}
728
729// Check if the location is a freed symbolic region.
730void MallocChecker::checkLocation(SVal l, bool isLoad, const Stmt *S,
731                                  CheckerContext &C) const {
732  SymbolRef Sym = l.getLocSymbolInBase();
733  if (Sym)
734    checkUseAfterFree(Sym, C);
735}
736
737void MallocChecker::checkBind(SVal location, SVal val,
738                              const Stmt *BindS, CheckerContext &C) const {
739  // The PreVisitBind implements the same algorithm as already used by the
740  // Objective C ownership checker: if the pointer escaped from this scope by
741  // assignment, let it go.  However, assigning to fields of a stack-storage
742  // structure does not transfer ownership.
743
744  ProgramStateRef state = C.getState();
745  DefinedOrUnknownSVal l = cast<DefinedOrUnknownSVal>(location);
746
747  // Check for null dereferences.
748  if (!isa<Loc>(l))
749    return;
750
751  // Before checking if the state is null, check if 'val' has a RefState.
752  // Only then should we check for null and bifurcate the state.
753  SymbolRef Sym = val.getLocSymbolInBase();
754  if (Sym) {
755    if (const RefState *RS = state->get<RegionState>(Sym)) {
756      // If ptr is NULL, no operation is performed.
757      ProgramStateRef notNullState, nullState;
758      llvm::tie(notNullState, nullState) = state->assume(l);
759
760      // Generate a transition for 'nullState' to record the assumption
761      // that the state was null.
762      if (nullState)
763        C.addTransition(nullState);
764
765      if (!notNullState)
766        return;
767
768      if (RS->isAllocated()) {
769        // Something we presently own is being assigned somewhere.
770        const MemRegion *AR = location.getAsRegion();
771        if (!AR)
772          return;
773        AR = AR->StripCasts()->getBaseRegion();
774        do {
775          // If it is on the stack, we still own it.
776          if (AR->hasStackNonParametersStorage())
777            break;
778
779          // If the state can't represent this binding, we still own it.
780          if (notNullState == (notNullState->bindLoc(cast<Loc>(location),
781                                                     UnknownVal())))
782            break;
783
784          // We no longer own this pointer.
785          notNullState =
786            notNullState->set<RegionState>(Sym,
787                                        RefState::getRelinquished(BindS));
788        }
789        while (false);
790      }
791      C.addTransition(notNullState);
792    }
793  }
794}
795
796#define REGISTER_CHECKER(name) \
797void ento::register##name(CheckerManager &mgr) {\
798  mgr.registerChecker<MallocChecker>()->Filter.C##name = true;\
799}
800
801REGISTER_CHECKER(MallocPessimistic)
802REGISTER_CHECKER(MallocOptimistic)
803