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