MallocChecker.cpp revision b16ce45bd05b637b3d7b0bf70c05e5dfd4ddacc7 
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/ObjCMessage.h"
21#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
22#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
23#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
24#include "clang/Basic/SourceManager.h"
25#include "llvm/ADT/ImmutableMap.h"
26#include "llvm/ADT/SmallString.h"
27#include "llvm/ADT/STLExtras.h"
28using namespace clang;
29using namespace ento;
30
31namespace {
32
33class RefState {
34  enum Kind { AllocateUnchecked, AllocateFailed, Released, Escaped,
35              Relinquished } K;
36  const Stmt *S;
37
38public:
39  RefState(Kind k, const Stmt *s) : K(k), S(s) {}
40
41  bool isAllocated() const { return K == AllocateUnchecked; }
42  //bool isFailed() const { return K == AllocateFailed; }
43  bool isReleased() const { return K == Released; }
44  //bool isEscaped() const { return K == Escaped; }
45  //bool isRelinquished() const { return K == Relinquished; }
46  const Stmt *getStmt() const { return S; }
47
48  bool operator==(const RefState &X) const {
49    return K == X.K && S == X.S;
50  }
51
52  static RefState getAllocateUnchecked(const Stmt *s) {
53    return RefState(AllocateUnchecked, s);
54  }
55  static RefState getAllocateFailed() {
56    return RefState(AllocateFailed, 0);
57  }
58  static RefState getReleased(const Stmt *s) { return RefState(Released, s); }
59  static RefState getEscaped(const Stmt *s) { return RefState(Escaped, s); }
60  static RefState getRelinquished(const Stmt *s) {
61    return RefState(Relinquished, s);
62  }
63
64  void Profile(llvm::FoldingSetNodeID &ID) const {
65    ID.AddInteger(K);
66    ID.AddPointer(S);
67  }
68};
69
70class MallocChecker : public Checker<check::DeadSymbols,
71                                     check::EndPath,
72                                     check::PreStmt<ReturnStmt>,
73                                     check::PreStmt<CallExpr>,
74                                     check::PostStmt<CallExpr>,
75                                     check::Location,
76                                     check::Bind,
77                                     eval::Assume,
78                                     check::RegionChanges>
79{
80  mutable OwningPtr<BuiltinBug> BT_DoubleFree;
81  mutable OwningPtr<BuiltinBug> BT_Leak;
82  mutable OwningPtr<BuiltinBug> BT_UseFree;
83  mutable OwningPtr<BuiltinBug> BT_UseRelinquished;
84  mutable OwningPtr<BuiltinBug> BT_BadFree;
85  mutable IdentifierInfo *II_malloc, *II_free, *II_realloc, *II_calloc,
86                         *II_valloc;
87
88public:
89  MallocChecker() : II_malloc(0), II_free(0), II_realloc(0), II_calloc(0),
90                    II_valloc(0) {}
91
92  /// In pessimistic mode, the checker assumes that it does not know which
93  /// functions might free the memory.
94  struct ChecksFilter {
95    DefaultBool CMallocPessimistic;
96    DefaultBool CMallocOptimistic;
97  };
98
99  ChecksFilter Filter;
100
101  void checkPreStmt(const CallExpr *S, CheckerContext &C) const;
102  void checkPostStmt(const CallExpr *CE, CheckerContext &C) const;
103  void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const;
104  void checkEndPath(CheckerContext &C) const;
105  void checkPreStmt(const ReturnStmt *S, CheckerContext &C) const;
106  ProgramStateRef evalAssume(ProgramStateRef state, SVal Cond,
107                            bool Assumption) const;
108  void checkLocation(SVal l, bool isLoad, const Stmt *S,
109                     CheckerContext &C) const;
110  void checkBind(SVal location, SVal val, const Stmt*S,
111                 CheckerContext &C) const;
112  ProgramStateRef
113  checkRegionChanges(ProgramStateRef state,
114                     const StoreManager::InvalidatedSymbols *invalidated,
115                     ArrayRef<const MemRegion *> ExplicitRegions,
116                     ArrayRef<const MemRegion *> Regions,
117                     const CallOrObjCMessage *Call) const;
118  bool wantsRegionChangeUpdate(ProgramStateRef state) const {
119    return true;
120  }
121
122private:
123  void initIdentifierInfo(ASTContext &C) const;
124
125  /// Check if this is one of the functions which can allocate/reallocate memory
126  /// pointed to by one of its arguments.
127  bool isMemFunction(const FunctionDecl *FD, ASTContext &C) const;
128
129  static void MallocMem(CheckerContext &C, const CallExpr *CE);
130  static void MallocMemReturnsAttr(CheckerContext &C, const CallExpr *CE,
131                                   const OwnershipAttr* Att);
132  static ProgramStateRef MallocMemAux(CheckerContext &C, const CallExpr *CE,
133                                     const Expr *SizeEx, SVal Init,
134                                     ProgramStateRef state) {
135    return MallocMemAux(C, CE,
136                        state->getSVal(SizeEx, C.getLocationContext()),
137                        Init, state);
138  }
139  static ProgramStateRef MallocMemAux(CheckerContext &C, const CallExpr *CE,
140                                     SVal SizeEx, SVal Init,
141                                     ProgramStateRef state);
142
143  void FreeMem(CheckerContext &C, const CallExpr *CE) const;
144  void FreeMemAttr(CheckerContext &C, const CallExpr *CE,
145                   const OwnershipAttr* Att) const;
146  ProgramStateRef FreeMemAux(CheckerContext &C, const CallExpr *CE,
147                                 ProgramStateRef state, unsigned Num,
148                                 bool Hold) const;
149
150  void ReallocMem(CheckerContext &C, const CallExpr *CE) const;
151  static void CallocMem(CheckerContext &C, const CallExpr *CE);
152
153  bool checkEscape(SymbolRef Sym, const Stmt *S, CheckerContext &C) const;
154  bool checkUseAfterFree(SymbolRef Sym, CheckerContext &C,
155                         const Stmt *S = 0) const;
156
157  /// Check if the function is not known to us. So, for example, we could
158  /// conservatively assume it can free/reallocate it's pointer arguments.
159  bool hasUnknownBehavior(const FunctionDecl *FD, ProgramStateRef State) const;
160
161  static bool SummarizeValue(raw_ostream &os, SVal V);
162  static bool SummarizeRegion(raw_ostream &os, const MemRegion *MR);
163  void ReportBadFree(CheckerContext &C, SVal ArgVal, SourceRange range) const;
164
165  void reportLeak(SymbolRef Sym, ExplodedNode *N, CheckerContext &C) const;
166
167  /// The bug visitor which allows us to print extra diagnostics along the
168  /// BugReport path. For example, showing the allocation site of the leaked
169  /// region.
170  class MallocBugVisitor : public BugReporterVisitor {
171  protected:
172    // The allocated region symbol tracked by the main analysis.
173    SymbolRef Sym;
174
175  public:
176    MallocBugVisitor(SymbolRef S) : Sym(S) {}
177    virtual ~MallocBugVisitor() {}
178
179    void Profile(llvm::FoldingSetNodeID &ID) const {
180      static int X = 0;
181      ID.AddPointer(&X);
182      ID.AddPointer(Sym);
183    }
184
185    inline bool isAllocated(const RefState *S, const RefState *SPrev) {
186      // Did not track -> allocated. Other state (released) -> allocated.
187      return ((S && S->isAllocated()) && (!SPrev || !SPrev->isAllocated()));
188    }
189
190    inline bool isReleased(const RefState *S, const RefState *SPrev) {
191      // Did not track -> released. Other state (allocated) -> released.
192      return ((S && S->isReleased()) && (!SPrev || !SPrev->isReleased()));
193    }
194
195    PathDiagnosticPiece *VisitNode(const ExplodedNode *N,
196                                   const ExplodedNode *PrevN,
197                                   BugReporterContext &BRC,
198                                   BugReport &BR);
199  };
200};
201} // end anonymous namespace
202
203typedef llvm::ImmutableMap<SymbolRef, RefState> RegionStateTy;
204typedef llvm::ImmutableMap<SymbolRef, SymbolRef> SymRefToSymRefTy;
205class RegionState {};
206class ReallocPairs {};
207namespace clang {
208namespace ento {
209  template <>
210  struct ProgramStateTrait<RegionState>
211    : public ProgramStatePartialTrait<RegionStateTy> {
212    static void *GDMIndex() { static int x; return &x; }
213  };
214
215  template <>
216  struct ProgramStateTrait<ReallocPairs>
217    : public ProgramStatePartialTrait<SymRefToSymRefTy> {
218    static void *GDMIndex() { static int x; return &x; }
219  };
220}
221}
222
223namespace {
224class StopTrackingCallback : public SymbolVisitor {
225  ProgramStateRef state;
226public:
227  StopTrackingCallback(ProgramStateRef st) : state(st) {}
228  ProgramStateRef getState() const { return state; }
229
230  bool VisitSymbol(SymbolRef sym) {
231    state = state->remove<RegionState>(sym);
232    return true;
233  }
234};
235} // end anonymous namespace
236
237void MallocChecker::initIdentifierInfo(ASTContext &Ctx) const {
238  if (!II_malloc)
239    II_malloc = &Ctx.Idents.get("malloc");
240  if (!II_free)
241    II_free = &Ctx.Idents.get("free");
242  if (!II_realloc)
243    II_realloc = &Ctx.Idents.get("realloc");
244  if (!II_calloc)
245    II_calloc = &Ctx.Idents.get("calloc");
246  if (!II_valloc)
247    II_valloc = &Ctx.Idents.get("valloc");
248}
249
250bool MallocChecker::isMemFunction(const FunctionDecl *FD, ASTContext &C) const {
251  initIdentifierInfo(C);
252  IdentifierInfo *FunI = FD->getIdentifier();
253  if (!FunI)
254    return false;
255
256  // TODO: Add more here : ex: reallocf!
257  if (FunI == II_malloc || FunI == II_free ||
258      FunI == II_realloc || FunI == II_calloc || FunI == II_valloc)
259    return true;
260
261  if (Filter.CMallocOptimistic && FD->hasAttrs() &&
262      FD->specific_attr_begin<OwnershipAttr>() !=
263          FD->specific_attr_end<OwnershipAttr>())
264    return true;
265
266
267  return false;
268}
269
270void MallocChecker::checkPostStmt(const CallExpr *CE, CheckerContext &C) const {
271  const FunctionDecl *FD = C.getCalleeDecl(CE);
272  if (!FD)
273    return;
274
275  initIdentifierInfo(C.getASTContext());
276  IdentifierInfo *FunI = FD->getIdentifier();
277  if (!FunI)
278    return;
279
280  if (FunI == II_malloc || FunI == II_valloc) {
281    MallocMem(C, CE);
282    return;
283  } else if (FunI == II_realloc) {
284    ReallocMem(C, CE);
285    return;
286  } else if (FunI == II_calloc) {
287    CallocMem(C, CE);
288    return;
289  }else if (FunI == II_free) {
290    FreeMem(C, CE);
291    return;
292  }
293
294  if (Filter.CMallocOptimistic)
295  // Check all the attributes, if there are any.
296  // There can be multiple of these attributes.
297  if (FD->hasAttrs()) {
298    for (specific_attr_iterator<OwnershipAttr>
299                  i = FD->specific_attr_begin<OwnershipAttr>(),
300                  e = FD->specific_attr_end<OwnershipAttr>();
301         i != e; ++i) {
302      switch ((*i)->getOwnKind()) {
303      case OwnershipAttr::Returns: {
304        MallocMemReturnsAttr(C, CE, *i);
305        return;
306      }
307      case OwnershipAttr::Takes:
308      case OwnershipAttr::Holds: {
309        FreeMemAttr(C, CE, *i);
310        return;
311      }
312      }
313    }
314  }
315}
316
317void MallocChecker::MallocMem(CheckerContext &C, const CallExpr *CE) {
318  ProgramStateRef state = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(),
319                                      C.getState());
320  C.addTransition(state);
321}
322
323void MallocChecker::MallocMemReturnsAttr(CheckerContext &C, const CallExpr *CE,
324                                         const OwnershipAttr* Att) {
325  if (Att->getModule() != "malloc")
326    return;
327
328  OwnershipAttr::args_iterator I = Att->args_begin(), E = Att->args_end();
329  if (I != E) {
330    ProgramStateRef state =
331        MallocMemAux(C, CE, CE->getArg(*I), UndefinedVal(), C.getState());
332    C.addTransition(state);
333    return;
334  }
335  ProgramStateRef state = MallocMemAux(C, CE, UnknownVal(), UndefinedVal(),
336                                        C.getState());
337  C.addTransition(state);
338}
339
340ProgramStateRef MallocChecker::MallocMemAux(CheckerContext &C,
341                                           const CallExpr *CE,
342                                           SVal Size, SVal Init,
343                                           ProgramStateRef state) {
344  SValBuilder &svalBuilder = C.getSValBuilder();
345
346  // Get the return value.
347  SVal retVal = state->getSVal(CE, C.getLocationContext());
348
349  // We expect the malloc functions to return a pointer.
350  if (!isa<Loc>(retVal))
351    return 0;
352
353  // Fill the region with the initialization value.
354  state = state->bindDefault(retVal, Init);
355
356  // Set the region's extent equal to the Size parameter.
357  const SymbolicRegion *R =
358      dyn_cast_or_null<SymbolicRegion>(retVal.getAsRegion());
359  if (!R || !isa<DefinedOrUnknownSVal>(Size))
360    return 0;
361
362  DefinedOrUnknownSVal Extent = R->getExtent(svalBuilder);
363  DefinedOrUnknownSVal DefinedSize = cast<DefinedOrUnknownSVal>(Size);
364  DefinedOrUnknownSVal extentMatchesSize =
365    svalBuilder.evalEQ(state, Extent, DefinedSize);
366
367  state = state->assume(extentMatchesSize, true);
368  assert(state);
369
370  SymbolRef Sym = retVal.getAsLocSymbol();
371  assert(Sym);
372
373  // Set the symbol's state to Allocated.
374  return state->set<RegionState>(Sym, RefState::getAllocateUnchecked(CE));
375}
376
377void MallocChecker::FreeMem(CheckerContext &C, const CallExpr *CE) const {
378  ProgramStateRef state = FreeMemAux(C, CE, C.getState(), 0, false);
379
380  if (state)
381    C.addTransition(state);
382}
383
384void MallocChecker::FreeMemAttr(CheckerContext &C, const CallExpr *CE,
385                                const OwnershipAttr* Att) const {
386  if (Att->getModule() != "malloc")
387    return;
388
389  for (OwnershipAttr::args_iterator I = Att->args_begin(), E = Att->args_end();
390       I != E; ++I) {
391    ProgramStateRef state =
392      FreeMemAux(C, CE, C.getState(), *I,
393                 Att->getOwnKind() == OwnershipAttr::Holds);
394    if (state)
395      C.addTransition(state);
396  }
397}
398
399ProgramStateRef MallocChecker::FreeMemAux(CheckerContext &C,
400                                          const CallExpr *CE,
401                                          ProgramStateRef state,
402                                          unsigned Num,
403                                          bool Hold) const {
404  const Expr *ArgExpr = CE->getArg(Num);
405  SVal ArgVal = state->getSVal(ArgExpr, C.getLocationContext());
406  if (!isa<DefinedOrUnknownSVal>(ArgVal))
407    return 0;
408  DefinedOrUnknownSVal location = cast<DefinedOrUnknownSVal>(ArgVal);
409
410  // Check for null dereferences.
411  if (!isa<Loc>(location))
412    return 0;
413
414  // The explicit NULL case, no operation is performed.
415  ProgramStateRef notNullState, nullState;
416  llvm::tie(notNullState, nullState) = state->assume(location);
417  if (nullState && !notNullState)
418    return 0;
419
420  // Unknown values could easily be okay
421  // Undefined values are handled elsewhere
422  if (ArgVal.isUnknownOrUndef())
423    return 0;
424
425  const MemRegion *R = ArgVal.getAsRegion();
426
427  // Nonlocs can't be freed, of course.
428  // Non-region locations (labels and fixed addresses) also shouldn't be freed.
429  if (!R) {
430    ReportBadFree(C, ArgVal, ArgExpr->getSourceRange());
431    return 0;
432  }
433
434  R = R->StripCasts();
435
436  // Blocks might show up as heap data, but should not be free()d
437  if (isa<BlockDataRegion>(R)) {
438    ReportBadFree(C, ArgVal, ArgExpr->getSourceRange());
439    return 0;
440  }
441
442  const MemSpaceRegion *MS = R->getMemorySpace();
443
444  // Parameters, locals, statics, and globals shouldn't be freed.
445  if (!(isa<UnknownSpaceRegion>(MS) || isa<HeapSpaceRegion>(MS))) {
446    // FIXME: at the time this code was written, malloc() regions were
447    // represented by conjured symbols, which are all in UnknownSpaceRegion.
448    // This means that there isn't actually anything from HeapSpaceRegion
449    // that should be freed, even though we allow it here.
450    // Of course, free() can work on memory allocated outside the current
451    // function, so UnknownSpaceRegion is always a possibility.
452    // False negatives are better than false positives.
453
454    ReportBadFree(C, ArgVal, ArgExpr->getSourceRange());
455    return 0;
456  }
457
458  const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R);
459  // Various cases could lead to non-symbol values here.
460  // For now, ignore them.
461  if (!SR)
462    return 0;
463
464  SymbolRef Sym = SR->getSymbol();
465  const RefState *RS = state->get<RegionState>(Sym);
466
467  // If the symbol has not been tracked, return. This is possible when free() is
468  // called on a pointer that does not get its pointee directly from malloc().
469  // Full support of this requires inter-procedural analysis.
470  if (!RS)
471    return 0;
472
473  // Check double free.
474  if (RS->isReleased()) {
475    if (ExplodedNode *N = C.generateSink()) {
476      if (!BT_DoubleFree)
477        BT_DoubleFree.reset(
478          new BuiltinBug("Double free",
479                         "Try to free a memory block that has been released"));
480      BugReport *R = new BugReport(*BT_DoubleFree,
481                                   BT_DoubleFree->getDescription(), N);
482      R->addVisitor(new MallocBugVisitor(Sym));
483      C.EmitReport(R);
484    }
485    return 0;
486  }
487
488  // Normal free.
489  if (Hold)
490    return state->set<RegionState>(Sym, RefState::getRelinquished(CE));
491  return state->set<RegionState>(Sym, RefState::getReleased(CE));
492}
493
494bool MallocChecker::SummarizeValue(raw_ostream &os, SVal V) {
495  if (nonloc::ConcreteInt *IntVal = dyn_cast<nonloc::ConcreteInt>(&V))
496    os << "an integer (" << IntVal->getValue() << ")";
497  else if (loc::ConcreteInt *ConstAddr = dyn_cast<loc::ConcreteInt>(&V))
498    os << "a constant address (" << ConstAddr->getValue() << ")";
499  else if (loc::GotoLabel *Label = dyn_cast<loc::GotoLabel>(&V))
500    os << "the address of the label '" << Label->getLabel()->getName() << "'";
501  else
502    return false;
503
504  return true;
505}
506
507bool MallocChecker::SummarizeRegion(raw_ostream &os,
508                                    const MemRegion *MR) {
509  switch (MR->getKind()) {
510  case MemRegion::FunctionTextRegionKind: {
511    const FunctionDecl *FD = cast<FunctionTextRegion>(MR)->getDecl();
512    if (FD)
513      os << "the address of the function '" << *FD << '\'';
514    else
515      os << "the address of a function";
516    return true;
517  }
518  case MemRegion::BlockTextRegionKind:
519    os << "block text";
520    return true;
521  case MemRegion::BlockDataRegionKind:
522    // FIXME: where the block came from?
523    os << "a block";
524    return true;
525  default: {
526    const MemSpaceRegion *MS = MR->getMemorySpace();
527
528    if (isa<StackLocalsSpaceRegion>(MS)) {
529      const VarRegion *VR = dyn_cast<VarRegion>(MR);
530      const VarDecl *VD;
531      if (VR)
532        VD = VR->getDecl();
533      else
534        VD = NULL;
535
536      if (VD)
537        os << "the address of the local variable '" << VD->getName() << "'";
538      else
539        os << "the address of a local stack variable";
540      return true;
541    }
542
543    if (isa<StackArgumentsSpaceRegion>(MS)) {
544      const VarRegion *VR = dyn_cast<VarRegion>(MR);
545      const VarDecl *VD;
546      if (VR)
547        VD = VR->getDecl();
548      else
549        VD = NULL;
550
551      if (VD)
552        os << "the address of the parameter '" << VD->getName() << "'";
553      else
554        os << "the address of a parameter";
555      return true;
556    }
557
558    if (isa<GlobalsSpaceRegion>(MS)) {
559      const VarRegion *VR = dyn_cast<VarRegion>(MR);
560      const VarDecl *VD;
561      if (VR)
562        VD = VR->getDecl();
563      else
564        VD = NULL;
565
566      if (VD) {
567        if (VD->isStaticLocal())
568          os << "the address of the static variable '" << VD->getName() << "'";
569        else
570          os << "the address of the global variable '" << VD->getName() << "'";
571      } else
572        os << "the address of a global variable";
573      return true;
574    }
575
576    return false;
577  }
578  }
579}
580
581void MallocChecker::ReportBadFree(CheckerContext &C, SVal ArgVal,
582                                  SourceRange range) const {
583  if (ExplodedNode *N = C.generateSink()) {
584    if (!BT_BadFree)
585      BT_BadFree.reset(new BuiltinBug("Bad free"));
586
587    SmallString<100> buf;
588    llvm::raw_svector_ostream os(buf);
589
590    const MemRegion *MR = ArgVal.getAsRegion();
591    if (MR) {
592      while (const ElementRegion *ER = dyn_cast<ElementRegion>(MR))
593        MR = ER->getSuperRegion();
594
595      // Special case for alloca()
596      if (isa<AllocaRegion>(MR))
597        os << "Argument to free() was allocated by alloca(), not malloc()";
598      else {
599        os << "Argument to free() is ";
600        if (SummarizeRegion(os, MR))
601          os << ", which is not memory allocated by malloc()";
602        else
603          os << "not memory allocated by malloc()";
604      }
605    } else {
606      os << "Argument to free() is ";
607      if (SummarizeValue(os, ArgVal))
608        os << ", which is not memory allocated by malloc()";
609      else
610        os << "not memory allocated by malloc()";
611    }
612
613    BugReport *R = new BugReport(*BT_BadFree, os.str(), N);
614    R->addRange(range);
615    C.EmitReport(R);
616  }
617}
618
619void MallocChecker::ReallocMem(CheckerContext &C, const CallExpr *CE) const {
620  ProgramStateRef state = C.getState();
621  const Expr *arg0Expr = CE->getArg(0);
622  const LocationContext *LCtx = C.getLocationContext();
623  SVal Arg0Val = state->getSVal(arg0Expr, LCtx);
624  if (!isa<DefinedOrUnknownSVal>(Arg0Val))
625    return;
626  DefinedOrUnknownSVal arg0Val = cast<DefinedOrUnknownSVal>(Arg0Val);
627
628  SValBuilder &svalBuilder = C.getSValBuilder();
629
630  DefinedOrUnknownSVal PtrEQ =
631    svalBuilder.evalEQ(state, arg0Val, svalBuilder.makeNull());
632
633  // Get the size argument. If there is no size arg then give up.
634  const Expr *Arg1 = CE->getArg(1);
635  if (!Arg1)
636    return;
637
638  // Get the value of the size argument.
639  SVal Arg1ValG = state->getSVal(Arg1, LCtx);
640  if (!isa<DefinedOrUnknownSVal>(Arg1ValG))
641    return;
642  DefinedOrUnknownSVal Arg1Val = cast<DefinedOrUnknownSVal>(Arg1ValG);
643
644  // Compare the size argument to 0.
645  DefinedOrUnknownSVal SizeZero =
646    svalBuilder.evalEQ(state, Arg1Val,
647                       svalBuilder.makeIntValWithPtrWidth(0, false));
648
649  ProgramStateRef StatePtrIsNull, StatePtrNotNull;
650  llvm::tie(StatePtrIsNull, StatePtrNotNull) = state->assume(PtrEQ);
651  ProgramStateRef StateSizeIsZero, StateSizeNotZero;
652  llvm::tie(StateSizeIsZero, StateSizeNotZero) = state->assume(SizeZero);
653  // We only assume exceptional states if they are definitely true; if the
654  // state is under-constrained, assume regular realloc behavior.
655  bool PrtIsNull = StatePtrIsNull && !StatePtrNotNull;
656  bool SizeIsZero = StateSizeIsZero && !StateSizeNotZero;
657
658  // If the ptr is NULL and the size is not 0, the call is equivalent to
659  // malloc(size).
660  if ( PrtIsNull && !SizeIsZero) {
661    ProgramStateRef stateMalloc = MallocMemAux(C, CE, CE->getArg(1),
662                                               UndefinedVal(), StatePtrIsNull);
663    C.addTransition(stateMalloc);
664    return;
665  }
666
667  if (PrtIsNull && SizeIsZero)
668    return;
669
670  // Get the from and to pointer symbols as in toPtr = realloc(fromPtr, size).
671  assert(!PrtIsNull);
672  SymbolRef FromPtr = arg0Val.getAsSymbol();
673  SVal RetVal = state->getSVal(CE, LCtx);
674  SymbolRef ToPtr = RetVal.getAsSymbol();
675  if (!FromPtr || !ToPtr)
676    return;
677
678  // If the size is 0, free the memory.
679  if (SizeIsZero)
680    if (ProgramStateRef stateFree = FreeMemAux(C, CE, StateSizeIsZero,0,false)){
681      // The semantics of the return value are:
682      // If size was equal to 0, either NULL or a pointer suitable to be passed
683      // to free() is returned.
684      stateFree = stateFree->set<ReallocPairs>(ToPtr, FromPtr);
685      C.getSymbolManager().addSymbolDependency(ToPtr, FromPtr);
686      C.addTransition(stateFree);
687      return;
688    }
689
690  // Default behavior.
691  if (ProgramStateRef stateFree = FreeMemAux(C, CE, state, 0, false)) {
692    // FIXME: We should copy the content of the original buffer.
693    ProgramStateRef stateRealloc = MallocMemAux(C, CE, CE->getArg(1),
694                                                UnknownVal(), stateFree);
695    if (!stateRealloc)
696      return;
697    stateRealloc = stateRealloc->set<ReallocPairs>(ToPtr, FromPtr);
698    C.getSymbolManager().addSymbolDependency(ToPtr, FromPtr);
699    C.addTransition(stateRealloc);
700    return;
701  }
702}
703
704void MallocChecker::CallocMem(CheckerContext &C, const CallExpr *CE) {
705  ProgramStateRef state = C.getState();
706  SValBuilder &svalBuilder = C.getSValBuilder();
707  const LocationContext *LCtx = C.getLocationContext();
708  SVal count = state->getSVal(CE->getArg(0), LCtx);
709  SVal elementSize = state->getSVal(CE->getArg(1), LCtx);
710  SVal TotalSize = svalBuilder.evalBinOp(state, BO_Mul, count, elementSize,
711                                        svalBuilder.getContext().getSizeType());
712  SVal zeroVal = svalBuilder.makeZeroVal(svalBuilder.getContext().CharTy);
713
714  C.addTransition(MallocMemAux(C, CE, TotalSize, zeroVal, state));
715}
716
717void MallocChecker::reportLeak(SymbolRef Sym, ExplodedNode *N,
718                               CheckerContext &C) const {
719  assert(N);
720  if (!BT_Leak) {
721    BT_Leak.reset(new BuiltinBug("Memory leak",
722        "Allocated memory never released. Potential memory leak."));
723    // Leaks should not be reported if they are post-dominated by a sink:
724    // (1) Sinks are higher importance bugs.
725    // (2) NoReturnFunctionChecker uses sink nodes to represent paths ending
726    //     with __noreturn functions such as assert() or exit(). We choose not
727    //     to report leaks on such paths.
728    BT_Leak->setSuppressOnSink(true);
729  }
730
731  BugReport *R = new BugReport(*BT_Leak, BT_Leak->getDescription(), N);
732  R->addVisitor(new MallocBugVisitor(Sym));
733  C.EmitReport(R);
734}
735
736void MallocChecker::checkDeadSymbols(SymbolReaper &SymReaper,
737                                     CheckerContext &C) const
738{
739  if (!SymReaper.hasDeadSymbols())
740    return;
741
742  ProgramStateRef state = C.getState();
743  RegionStateTy RS = state->get<RegionState>();
744  RegionStateTy::Factory &F = state->get_context<RegionState>();
745
746  bool generateReport = false;
747  llvm::SmallVector<SymbolRef, 2> Errors;
748  for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
749    if (SymReaper.isDead(I->first)) {
750      if (I->second.isAllocated()) {
751        generateReport = true;
752        Errors.push_back(I->first);
753      }
754      // Remove the dead symbol from the map.
755      RS = F.remove(RS, I->first);
756
757    }
758  }
759
760  // Cleanup the Realloc Pairs Map.
761  SymRefToSymRefTy RP = state->get<ReallocPairs>();
762  for (SymRefToSymRefTy::iterator I = RP.begin(), E = RP.end(); I != E; ++I) {
763    if (SymReaper.isDead(I->first) || SymReaper.isDead(I->second)) {
764      state = state->remove<ReallocPairs>(I->first);
765    }
766  }
767
768  ExplodedNode *N = C.addTransition(state->set<RegionState>(RS));
769
770  if (N && generateReport) {
771    for (llvm::SmallVector<SymbolRef, 2>::iterator
772         I = Errors.begin(), E = Errors.end(); I != E; ++I) {
773      reportLeak(*I, N, C);
774    }
775  }
776}
777
778void MallocChecker::checkEndPath(CheckerContext &C) const {
779  ProgramStateRef state = C.getState();
780  RegionStateTy M = state->get<RegionState>();
781
782  for (RegionStateTy::iterator I = M.begin(), E = M.end(); I != E; ++I) {
783    RefState RS = I->second;
784    if (RS.isAllocated()) {
785      ExplodedNode *N = C.addTransition(state);
786      if (N)
787        reportLeak(I->first, N, C);
788    }
789  }
790}
791
792bool MallocChecker::checkEscape(SymbolRef Sym, const Stmt *S,
793                                CheckerContext &C) const {
794  ProgramStateRef state = C.getState();
795  const RefState *RS = state->get<RegionState>(Sym);
796  if (!RS)
797    return false;
798
799  if (RS->isAllocated()) {
800    state = state->set<RegionState>(Sym, RefState::getEscaped(S));
801    C.addTransition(state);
802    return true;
803  }
804  return false;
805}
806
807void MallocChecker::checkPreStmt(const CallExpr *CE, CheckerContext &C) const {
808  if (isMemFunction(C.getCalleeDecl(CE), C.getASTContext()))
809    return;
810
811  // Check use after free, when a freed pointer is passed to a call.
812  ProgramStateRef State = C.getState();
813  for (CallExpr::const_arg_iterator I = CE->arg_begin(),
814                                    E = CE->arg_end(); I != E; ++I) {
815    const Expr *A = *I;
816    if (A->getType().getTypePtr()->isAnyPointerType()) {
817      SymbolRef Sym = State->getSVal(A, C.getLocationContext()).getAsSymbol();
818      if (!Sym)
819        continue;
820      if (checkUseAfterFree(Sym, C, A))
821        return;
822    }
823  }
824}
825
826void MallocChecker::checkPreStmt(const ReturnStmt *S, CheckerContext &C) const {
827  const Expr *E = S->getRetValue();
828  if (!E)
829    return;
830
831  // Check if we are returning a symbol.
832  SymbolRef Sym = C.getState()->getSVal(E, C.getLocationContext()).getAsSymbol();
833  if (!Sym)
834    return;
835
836  // Check if we are returning freed memory.
837  if (checkUseAfterFree(Sym, C, S))
838    return;
839
840  // Check if the symbol is escaping.
841  checkEscape(Sym, S, C);
842}
843
844bool MallocChecker::checkUseAfterFree(SymbolRef Sym, CheckerContext &C,
845                                      const Stmt *S) const {
846  assert(Sym);
847  const RefState *RS = C.getState()->get<RegionState>(Sym);
848  if (RS && RS->isReleased()) {
849    if (ExplodedNode *N = C.generateSink()) {
850      if (!BT_UseFree)
851        BT_UseFree.reset(new BuiltinBug("Use of dynamically allocated memory "
852            "after it is freed."));
853
854      BugReport *R = new BugReport(*BT_UseFree, BT_UseFree->getDescription(),N);
855      if (S)
856        R->addRange(S->getSourceRange());
857      R->addVisitor(new MallocBugVisitor(Sym));
858      C.EmitReport(R);
859      return true;
860    }
861  }
862  return false;
863}
864
865// Check if the location is a freed symbolic region.
866void MallocChecker::checkLocation(SVal l, bool isLoad, const Stmt *S,
867                                  CheckerContext &C) const {
868  SymbolRef Sym = l.getLocSymbolInBase();
869  if (Sym)
870    checkUseAfterFree(Sym, C);
871}
872
873//===----------------------------------------------------------------------===//
874// Check various ways a symbol can be invalidated.
875// TODO: This logic (the next 3 functions) is copied/similar to the
876// RetainRelease checker. We might want to factor this out.
877//===----------------------------------------------------------------------===//
878
879// Stop tracking symbols when a value escapes as a result of checkBind.
880// A value escapes in three possible cases:
881// (1) we are binding to something that is not a memory region.
882// (2) we are binding to a memregion that does not have stack storage
883// (3) we are binding to a memregion with stack storage that the store
884//     does not understand.
885void MallocChecker::checkBind(SVal loc, SVal val, const Stmt *S,
886                              CheckerContext &C) const {
887  // Are we storing to something that causes the value to "escape"?
888  bool escapes = true;
889  ProgramStateRef state = C.getState();
890
891  if (loc::MemRegionVal *regionLoc = dyn_cast<loc::MemRegionVal>(&loc)) {
892    escapes = !regionLoc->getRegion()->hasStackStorage();
893
894    if (!escapes) {
895      // To test (3), generate a new state with the binding added.  If it is
896      // the same state, then it escapes (since the store cannot represent
897      // the binding).
898      escapes = (state == (state->bindLoc(*regionLoc, val)));
899    }
900  }
901
902  // If our store can represent the binding and we aren't storing to something
903  // that doesn't have local storage then just return and have the simulation
904  // state continue as is.
905  if (!escapes)
906      return;
907
908  // Otherwise, find all symbols referenced by 'val' that we are tracking
909  // and stop tracking them.
910  state = state->scanReachableSymbols<StopTrackingCallback>(val).getState();
911  C.addTransition(state);
912}
913
914// If a symbolic region is assumed to NULL (or another constant), stop tracking
915// it - assuming that allocation failed on this path.
916ProgramStateRef MallocChecker::evalAssume(ProgramStateRef state,
917                                              SVal Cond,
918                                              bool Assumption) const {
919  RegionStateTy RS = state->get<RegionState>();
920  for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
921    // If the symbol is assumed to NULL or another constant, this will
922    // return an APSInt*.
923    if (state->getSymVal(I.getKey()))
924      state = state->remove<RegionState>(I.getKey());
925  }
926
927  // Realloc returns 0 when reallocation fails, which means that we should
928  // restore the state of the pointer being reallocated.
929  SymRefToSymRefTy RP = state->get<ReallocPairs>();
930  for (SymRefToSymRefTy::iterator I = RP.begin(), E = RP.end(); I != E; ++I) {
931    // If the symbol is assumed to NULL or another constant, this will
932    // return an APSInt*.
933    if (state->getSymVal(I.getKey())) {
934      const RefState *RS = state->get<RegionState>(I.getData());
935      if (RS) {
936        if (RS->isReleased())
937          state = state->set<RegionState>(I.getData(),
938                             RefState::getAllocateUnchecked(RS->getStmt()));
939        else if (RS->isAllocated())
940          state = state->set<RegionState>(I.getData(),
941                             RefState::getReleased(RS->getStmt()));
942      }
943      state = state->remove<ReallocPairs>(I.getKey());
944    }
945  }
946
947  return state;
948}
949
950// Check if the function is not known to us. So, for example, we could
951// conservatively assume it can free/reallocate it's pointer arguments.
952// (We assume that the pointers cannot escape through calls to system
953// functions not handled by this checker.)
954bool MallocChecker::hasUnknownBehavior(const FunctionDecl *FD,
955                                       ProgramStateRef State) const {
956  ASTContext &ASTC = State->getStateManager().getContext();
957
958  // If it's one of the allocation functions we can reason about, we model it's
959  // behavior explicitly.
960  if (isMemFunction(FD, ASTC)) {
961    return false;
962  }
963
964  // If it's a system call, we know it does not free the memory.
965  SourceManager &SM = ASTC.getSourceManager();
966  if (SM.isInSystemHeader(FD->getLocation())) {
967    return false;
968  }
969
970  // Otherwise, assume that the function can free memory.
971  return true;
972}
973
974// If the symbol we are tracking is invalidated, but not explicitly (ex: the &p
975// escapes, when we are tracking p), do not track the symbol as we cannot reason
976// about it anymore.
977ProgramStateRef
978MallocChecker::checkRegionChanges(ProgramStateRef State,
979                            const StoreManager::InvalidatedSymbols *invalidated,
980                                    ArrayRef<const MemRegion *> ExplicitRegions,
981                                    ArrayRef<const MemRegion *> Regions,
982                                    const CallOrObjCMessage *Call) const {
983  if (!invalidated)
984    return State;
985  llvm::SmallPtrSet<SymbolRef, 8> WhitelistedSymbols;
986
987  const FunctionDecl *FD = (Call ? dyn_cast<FunctionDecl>(Call->getDecl()) : 0);
988
989  // If it's a call which might free or reallocate memory, we assume that all
990  // regions (explicit and implicit) escaped. Otherwise, whitelist explicit
991  // pointers; we still can track them.
992  if (!(FD && hasUnknownBehavior(FD, State))) {
993    for (ArrayRef<const MemRegion *>::iterator I = ExplicitRegions.begin(),
994        E = ExplicitRegions.end(); I != E; ++I) {
995      if (const SymbolicRegion *R = (*I)->StripCasts()->getAs<SymbolicRegion>())
996        WhitelistedSymbols.insert(R->getSymbol());
997    }
998  }
999
1000  for (StoreManager::InvalidatedSymbols::const_iterator I=invalidated->begin(),
1001       E = invalidated->end(); I!=E; ++I) {
1002    SymbolRef sym = *I;
1003    if (WhitelistedSymbols.count(sym))
1004      continue;
1005    // The symbol escaped.
1006    if (const RefState *RS = State->get<RegionState>(sym))
1007      State = State->set<RegionState>(sym, RefState::getEscaped(RS->getStmt()));
1008  }
1009  return State;
1010}
1011
1012PathDiagnosticPiece *
1013MallocChecker::MallocBugVisitor::VisitNode(const ExplodedNode *N,
1014                                           const ExplodedNode *PrevN,
1015                                           BugReporterContext &BRC,
1016                                           BugReport &BR) {
1017  const RefState *RS = N->getState()->get<RegionState>(Sym);
1018  const RefState *RSPrev = PrevN->getState()->get<RegionState>(Sym);
1019  if (!RS && !RSPrev)
1020    return 0;
1021
1022  // We expect the interesting locations be StmtPoints corresponding to call
1023  // expressions. We do not support indirect function calls as of now.
1024  const CallExpr *CE = 0;
1025  if (isa<StmtPoint>(N->getLocation()))
1026    CE = dyn_cast<CallExpr>(cast<StmtPoint>(N->getLocation()).getStmt());
1027  if (!CE)
1028    return 0;
1029  const FunctionDecl *funDecl = CE->getDirectCallee();
1030  if (!funDecl)
1031    return 0;
1032
1033  // Find out if this is an interesting point and what is the kind.
1034  const char *Msg = 0;
1035  if (isAllocated(RS, RSPrev))
1036    Msg = "Memory is allocated here";
1037  else if (isReleased(RS, RSPrev))
1038    Msg = "Memory is released here";
1039  if (!Msg)
1040    return 0;
1041
1042  // Generate the extra diagnostic.
1043  PathDiagnosticLocation Pos(CE, BRC.getSourceManager(),
1044                             N->getLocationContext());
1045  return new PathDiagnosticEventPiece(Pos, Msg);
1046}
1047
1048
1049#define REGISTER_CHECKER(name) \
1050void ento::register##name(CheckerManager &mgr) {\
1051  mgr.registerChecker<MallocChecker>()->Filter.C##name = true;\
1052}
1053
1054REGISTER_CHECKER(MallocPessimistic)
1055REGISTER_CHECKER(MallocOptimistic)
1056