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