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