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