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