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