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