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