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