MallocChecker.cpp revision b000fb5999265d12d54a1ef9f31848c9e334dcaa 
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 isReleased() const { return K == Released; }
46
47  const Stmt *getStmt() const { return S; }
48
49  bool operator==(const RefState &X) const {
50    return K == X.K && S == X.S;
51  }
52
53  static RefState getAllocateUnchecked(const Stmt *s) {
54    return RefState(AllocateUnchecked, s);
55  }
56  static RefState getAllocateFailed() {
57    return RefState(AllocateFailed, 0);
58  }
59  static RefState getReleased(const Stmt *s) { return RefState(Released, s); }
60  static RefState getEscaped(const Stmt *s) { return RefState(Escaped, s); }
61  static RefState getRelinquished(const Stmt *s) {
62    return RefState(Relinquished, s);
63  }
64
65  void Profile(llvm::FoldingSetNodeID &ID) const {
66    ID.AddInteger(K);
67    ID.AddPointer(S);
68  }
69};
70
71struct ReallocPair {
72  SymbolRef ReallocatedSym;
73  bool IsFreeOnFailure;
74  ReallocPair(SymbolRef S, bool F) : ReallocatedSym(S), IsFreeOnFailure(F) {}
75  void Profile(llvm::FoldingSetNodeID &ID) const {
76    ID.AddInteger(IsFreeOnFailure);
77    ID.AddPointer(ReallocatedSym);
78  }
79  bool operator==(const ReallocPair &X) const {
80    return ReallocatedSym == X.ReallocatedSym &&
81           IsFreeOnFailure == X.IsFreeOnFailure;
82  }
83};
84
85typedef std::pair<const Stmt*, const MemRegion*> LeakInfo;
86
87class MallocChecker : public Checker<check::DeadSymbols,
88                                     check::EndPath,
89                                     check::PreStmt<ReturnStmt>,
90                                     check::PreStmt<CallExpr>,
91                                     check::PostStmt<CallExpr>,
92                                     check::PostStmt<BlockExpr>,
93                                     check::Location,
94                                     check::Bind,
95                                     eval::Assume,
96                                     check::RegionChanges>
97{
98  mutable OwningPtr<BugType> BT_DoubleFree;
99  mutable OwningPtr<BugType> BT_Leak;
100  mutable OwningPtr<BugType> BT_UseFree;
101  mutable OwningPtr<BugType> BT_BadFree;
102  mutable IdentifierInfo *II_malloc, *II_free, *II_realloc, *II_calloc,
103                         *II_valloc, *II_reallocf, *II_strndup, *II_strdup;
104
105public:
106  MallocChecker() : II_malloc(0), II_free(0), II_realloc(0), II_calloc(0),
107                    II_valloc(0), II_reallocf(0), II_strndup(0), II_strdup(0) {}
108
109  /// In pessimistic mode, the checker assumes that it does not know which
110  /// functions might free the memory.
111  struct ChecksFilter {
112    DefaultBool CMallocPessimistic;
113    DefaultBool CMallocOptimistic;
114  };
115
116  ChecksFilter Filter;
117
118  void checkPreStmt(const CallExpr *S, CheckerContext &C) const;
119  void checkPostStmt(const CallExpr *CE, CheckerContext &C) const;
120  void checkPostStmt(const BlockExpr *BE, 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 doesNotFreeMemory(const CallOrObjCMessage *Call,
184                         ProgramStateRef State) const;
185
186  static bool SummarizeValue(raw_ostream &os, SVal V);
187  static bool SummarizeRegion(raw_ostream &os, const MemRegion *MR);
188  void ReportBadFree(CheckerContext &C, SVal ArgVal, SourceRange range) const;
189
190  /// Find the location of the allocation for Sym on the path leading to the
191  /// exploded node N.
192  LeakInfo getAllocationSite(const ExplodedNode *N, SymbolRef Sym,
193                             CheckerContext &C) const;
194
195  void reportLeak(SymbolRef Sym, ExplodedNode *N, CheckerContext &C) const;
196
197  /// The bug visitor which allows us to print extra diagnostics along the
198  /// BugReport path. For example, showing the allocation site of the leaked
199  /// region.
200  class MallocBugVisitor : public BugReporterVisitorImpl<MallocBugVisitor> {
201  protected:
202    enum NotificationMode {
203      Normal,
204      ReallocationFailed
205    };
206
207    // The allocated region symbol tracked by the main analysis.
208    SymbolRef Sym;
209
210     // The mode we are in, i.e. what kind of diagnostics will be emitted.
211     NotificationMode Mode;
212
213     // A symbol from when the primary region should have been reallocated.
214     SymbolRef FailedReallocSymbol;
215
216   public:
217     MallocBugVisitor(SymbolRef S)
218       : Sym(S), Mode(Normal), FailedReallocSymbol(0) {}
219
220    virtual ~MallocBugVisitor() {}
221
222    void Profile(llvm::FoldingSetNodeID &ID) const {
223      static int X = 0;
224      ID.AddPointer(&X);
225      ID.AddPointer(Sym);
226    }
227
228    inline bool isAllocated(const RefState *S, const RefState *SPrev,
229                            const Stmt *Stmt) {
230      // Did not track -> allocated. Other state (released) -> allocated.
231      return (Stmt && isa<CallExpr>(Stmt) &&
232              (S && S->isAllocated()) && (!SPrev || !SPrev->isAllocated()));
233    }
234
235    inline bool isReleased(const RefState *S, const RefState *SPrev,
236                           const Stmt *Stmt) {
237      // Did not track -> released. Other state (allocated) -> released.
238      return (Stmt && isa<CallExpr>(Stmt) &&
239              (S && S->isReleased()) && (!SPrev || !SPrev->isReleased()));
240    }
241
242    inline bool isReallocFailedCheck(const RefState *S, const RefState *SPrev,
243                                     const Stmt *Stmt) {
244      // If the expression is not a call, and the state change is
245      // released -> allocated, it must be the realloc return value
246      // check. If we have to handle more cases here, it might be cleaner just
247      // to track this extra bit in the state itself.
248      return ((!Stmt || !isa<CallExpr>(Stmt)) &&
249              (S && S->isAllocated()) && (SPrev && !SPrev->isAllocated()));
250    }
251
252    PathDiagnosticPiece *VisitNode(const ExplodedNode *N,
253                                   const ExplodedNode *PrevN,
254                                   BugReporterContext &BRC,
255                                   BugReport &BR);
256  private:
257    class StackHintGeneratorForReallocationFailed
258        : public StackHintGeneratorForSymbol {
259    public:
260      StackHintGeneratorForReallocationFailed(SymbolRef S, StringRef M)
261        : StackHintGeneratorForSymbol(S, M) {}
262
263      virtual std::string getMessageForArg(const Expr *ArgE, unsigned ArgIndex) {
264        SmallString<200> buf;
265        llvm::raw_svector_ostream os(buf);
266
267        os << "Reallocation of ";
268        // Printed parameters start at 1, not 0.
269        printOrdinal(++ArgIndex, os);
270        os << " parameter failed";
271
272        return os.str();
273      }
274
275      virtual std::string getMessageForReturn(const CallExpr *CallExpr) {
276        return "Reallocation of returned value failed";
277      }
278    };
279  };
280};
281} // end anonymous namespace
282
283typedef llvm::ImmutableMap<SymbolRef, RefState> RegionStateTy;
284typedef llvm::ImmutableMap<SymbolRef, ReallocPair > ReallocMap;
285class RegionState {};
286class ReallocPairs {};
287namespace clang {
288namespace ento {
289  template <>
290  struct ProgramStateTrait<RegionState>
291    : public ProgramStatePartialTrait<RegionStateTy> {
292    static void *GDMIndex() { static int x; return &x; }
293  };
294
295  template <>
296  struct ProgramStateTrait<ReallocPairs>
297    : public ProgramStatePartialTrait<ReallocMap> {
298    static void *GDMIndex() { static int x; return &x; }
299  };
300}
301}
302
303namespace {
304class StopTrackingCallback : public SymbolVisitor {
305  ProgramStateRef state;
306public:
307  StopTrackingCallback(ProgramStateRef st) : state(st) {}
308  ProgramStateRef getState() const { return state; }
309
310  bool VisitSymbol(SymbolRef sym) {
311    state = state->remove<RegionState>(sym);
312    return true;
313  }
314};
315} // end anonymous namespace
316
317void MallocChecker::initIdentifierInfo(ASTContext &Ctx) const {
318  if (!II_malloc)
319    II_malloc = &Ctx.Idents.get("malloc");
320  if (!II_free)
321    II_free = &Ctx.Idents.get("free");
322  if (!II_realloc)
323    II_realloc = &Ctx.Idents.get("realloc");
324  if (!II_reallocf)
325    II_reallocf = &Ctx.Idents.get("reallocf");
326  if (!II_calloc)
327    II_calloc = &Ctx.Idents.get("calloc");
328  if (!II_valloc)
329    II_valloc = &Ctx.Idents.get("valloc");
330  if (!II_strdup)
331    II_strdup = &Ctx.Idents.get("strdup");
332  if (!II_strndup)
333    II_strndup = &Ctx.Idents.get("strndup");
334}
335
336bool MallocChecker::isMemFunction(const FunctionDecl *FD, ASTContext &C) const {
337  if (!FD)
338    return false;
339  IdentifierInfo *FunI = FD->getIdentifier();
340  if (!FunI)
341    return false;
342
343  initIdentifierInfo(C);
344
345  if (FunI == II_malloc || FunI == II_free || FunI == II_realloc ||
346      FunI == II_reallocf || FunI == II_calloc || FunI == II_valloc ||
347      FunI == II_strdup || FunI == II_strndup)
348    return true;
349
350  if (Filter.CMallocOptimistic && FD->hasAttrs() &&
351      FD->specific_attr_begin<OwnershipAttr>() !=
352          FD->specific_attr_end<OwnershipAttr>())
353    return true;
354
355
356  return false;
357}
358
359void MallocChecker::checkPostStmt(const CallExpr *CE, CheckerContext &C) const {
360  const FunctionDecl *FD = C.getCalleeDecl(CE);
361  if (!FD)
362    return;
363
364  initIdentifierInfo(C.getASTContext());
365  IdentifierInfo *FunI = FD->getIdentifier();
366  if (!FunI)
367    return;
368
369  ProgramStateRef State = C.getState();
370  if (FunI == II_malloc || FunI == II_valloc) {
371    State = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(), State);
372  } else if (FunI == II_realloc) {
373    State = ReallocMem(C, CE, false);
374  } else if (FunI == II_reallocf) {
375    State = ReallocMem(C, CE, true);
376  } else if (FunI == II_calloc) {
377    State = CallocMem(C, CE);
378  } else if (FunI == II_free) {
379    State = FreeMemAux(C, CE, C.getState(), 0, false);
380  } else if (FunI == II_strdup) {
381    State = MallocUpdateRefState(C, CE, State);
382  } else if (FunI == II_strndup) {
383    State = MallocUpdateRefState(C, CE, State);
384  } else if (Filter.CMallocOptimistic) {
385    // Check all the attributes, if there are any.
386    // There can be multiple of these attributes.
387    if (FD->hasAttrs())
388      for (specific_attr_iterator<OwnershipAttr>
389          i = FD->specific_attr_begin<OwnershipAttr>(),
390          e = FD->specific_attr_end<OwnershipAttr>();
391          i != e; ++i) {
392        switch ((*i)->getOwnKind()) {
393        case OwnershipAttr::Returns:
394          State = MallocMemReturnsAttr(C, CE, *i);
395          break;
396        case OwnershipAttr::Takes:
397        case OwnershipAttr::Holds:
398          State = FreeMemAttr(C, CE, *i);
399          break;
400        }
401      }
402  }
403  C.addTransition(State);
404}
405
406ProgramStateRef MallocChecker::MallocMemReturnsAttr(CheckerContext &C,
407                                                    const CallExpr *CE,
408                                                    const OwnershipAttr* Att) {
409  if (Att->getModule() != "malloc")
410    return 0;
411
412  OwnershipAttr::args_iterator I = Att->args_begin(), E = Att->args_end();
413  if (I != E) {
414    return MallocMemAux(C, CE, CE->getArg(*I), UndefinedVal(), C.getState());
415  }
416  return MallocMemAux(C, CE, UnknownVal(), UndefinedVal(), C.getState());
417}
418
419ProgramStateRef MallocChecker::MallocMemAux(CheckerContext &C,
420                                           const CallExpr *CE,
421                                           SVal Size, SVal Init,
422                                           ProgramStateRef state) {
423  // Get the return value.
424  SVal retVal = state->getSVal(CE, C.getLocationContext());
425
426  // We expect the malloc functions to return a pointer.
427  if (!isa<Loc>(retVal))
428    return 0;
429
430  // Fill the region with the initialization value.
431  state = state->bindDefault(retVal, Init);
432
433  // Set the region's extent equal to the Size parameter.
434  const SymbolicRegion *R =
435      dyn_cast_or_null<SymbolicRegion>(retVal.getAsRegion());
436  if (!R)
437    return 0;
438  if (isa<DefinedOrUnknownSVal>(Size)) {
439    SValBuilder &svalBuilder = C.getSValBuilder();
440    DefinedOrUnknownSVal Extent = R->getExtent(svalBuilder);
441    DefinedOrUnknownSVal DefinedSize = cast<DefinedOrUnknownSVal>(Size);
442    DefinedOrUnknownSVal extentMatchesSize =
443        svalBuilder.evalEQ(state, Extent, DefinedSize);
444
445    state = state->assume(extentMatchesSize, true);
446    assert(state);
447  }
448
449  return MallocUpdateRefState(C, CE, state);
450}
451
452ProgramStateRef MallocChecker::MallocUpdateRefState(CheckerContext &C,
453                                                    const CallExpr *CE,
454                                                    ProgramStateRef state) {
455  // Get the return value.
456  SVal retVal = state->getSVal(CE, C.getLocationContext());
457
458  // We expect the malloc functions to return a pointer.
459  if (!isa<Loc>(retVal))
460    return 0;
461
462  SymbolRef Sym = retVal.getAsLocSymbol();
463  assert(Sym);
464
465  // Set the symbol's state to Allocated.
466  return state->set<RegionState>(Sym, RefState::getAllocateUnchecked(CE));
467
468}
469
470ProgramStateRef MallocChecker::FreeMemAttr(CheckerContext &C,
471                                           const CallExpr *CE,
472                                           const OwnershipAttr* Att) const {
473  if (Att->getModule() != "malloc")
474    return 0;
475
476  ProgramStateRef State = C.getState();
477
478  for (OwnershipAttr::args_iterator I = Att->args_begin(), E = Att->args_end();
479       I != E; ++I) {
480    ProgramStateRef StateI = FreeMemAux(C, CE, State, *I,
481                               Att->getOwnKind() == OwnershipAttr::Holds);
482    if (StateI)
483      State = StateI;
484  }
485  return State;
486}
487
488ProgramStateRef MallocChecker::FreeMemAux(CheckerContext &C,
489                                          const CallExpr *CE,
490                                          ProgramStateRef state,
491                                          unsigned Num,
492                                          bool Hold) const {
493  const Expr *ArgExpr = CE->getArg(Num);
494  SVal ArgVal = state->getSVal(ArgExpr, C.getLocationContext());
495  if (!isa<DefinedOrUnknownSVal>(ArgVal))
496    return 0;
497  DefinedOrUnknownSVal location = cast<DefinedOrUnknownSVal>(ArgVal);
498
499  // Check for null dereferences.
500  if (!isa<Loc>(location))
501    return 0;
502
503  // The explicit NULL case, no operation is performed.
504  ProgramStateRef notNullState, nullState;
505  llvm::tie(notNullState, nullState) = state->assume(location);
506  if (nullState && !notNullState)
507    return 0;
508
509  // Unknown values could easily be okay
510  // Undefined values are handled elsewhere
511  if (ArgVal.isUnknownOrUndef())
512    return 0;
513
514  const MemRegion *R = ArgVal.getAsRegion();
515
516  // Nonlocs can't be freed, of course.
517  // Non-region locations (labels and fixed addresses) also shouldn't be freed.
518  if (!R) {
519    ReportBadFree(C, ArgVal, ArgExpr->getSourceRange());
520    return 0;
521  }
522
523  R = R->StripCasts();
524
525  // Blocks might show up as heap data, but should not be free()d
526  if (isa<BlockDataRegion>(R)) {
527    ReportBadFree(C, ArgVal, ArgExpr->getSourceRange());
528    return 0;
529  }
530
531  const MemSpaceRegion *MS = R->getMemorySpace();
532
533  // Parameters, locals, statics, and globals shouldn't be freed.
534  if (!(isa<UnknownSpaceRegion>(MS) || isa<HeapSpaceRegion>(MS))) {
535    // FIXME: at the time this code was written, malloc() regions were
536    // represented by conjured symbols, which are all in UnknownSpaceRegion.
537    // This means that there isn't actually anything from HeapSpaceRegion
538    // that should be freed, even though we allow it here.
539    // Of course, free() can work on memory allocated outside the current
540    // function, so UnknownSpaceRegion is always a possibility.
541    // False negatives are better than false positives.
542
543    ReportBadFree(C, ArgVal, ArgExpr->getSourceRange());
544    return 0;
545  }
546
547  const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R);
548  // Various cases could lead to non-symbol values here.
549  // For now, ignore them.
550  if (!SR)
551    return 0;
552
553  SymbolRef Sym = SR->getSymbol();
554  const RefState *RS = state->get<RegionState>(Sym);
555
556  // If the symbol has not been tracked, return. This is possible when free() is
557  // called on a pointer that does not get its pointee directly from malloc().
558  // Full support of this requires inter-procedural analysis.
559  if (!RS)
560    return 0;
561
562  // Check double free.
563  if (RS->isReleased()) {
564    if (ExplodedNode *N = C.generateSink()) {
565      if (!BT_DoubleFree)
566        BT_DoubleFree.reset(
567          new BugType("Double free", "Memory Error"));
568      BugReport *R = new BugReport(*BT_DoubleFree,
569                        "Attempt to free released memory", N);
570      R->addRange(ArgExpr->getSourceRange());
571      R->markInteresting(Sym);
572      R->addVisitor(new MallocBugVisitor(Sym));
573      C.EmitReport(R);
574    }
575    return 0;
576  }
577
578  // Normal free.
579  if (Hold)
580    return state->set<RegionState>(Sym, RefState::getRelinquished(CE));
581  return state->set<RegionState>(Sym, RefState::getReleased(CE));
582}
583
584bool MallocChecker::SummarizeValue(raw_ostream &os, SVal V) {
585  if (nonloc::ConcreteInt *IntVal = dyn_cast<nonloc::ConcreteInt>(&V))
586    os << "an integer (" << IntVal->getValue() << ")";
587  else if (loc::ConcreteInt *ConstAddr = dyn_cast<loc::ConcreteInt>(&V))
588    os << "a constant address (" << ConstAddr->getValue() << ")";
589  else if (loc::GotoLabel *Label = dyn_cast<loc::GotoLabel>(&V))
590    os << "the address of the label '" << Label->getLabel()->getName() << "'";
591  else
592    return false;
593
594  return true;
595}
596
597bool MallocChecker::SummarizeRegion(raw_ostream &os,
598                                    const MemRegion *MR) {
599  switch (MR->getKind()) {
600  case MemRegion::FunctionTextRegionKind: {
601    const FunctionDecl *FD = cast<FunctionTextRegion>(MR)->getDecl();
602    if (FD)
603      os << "the address of the function '" << *FD << '\'';
604    else
605      os << "the address of a function";
606    return true;
607  }
608  case MemRegion::BlockTextRegionKind:
609    os << "block text";
610    return true;
611  case MemRegion::BlockDataRegionKind:
612    // FIXME: where the block came from?
613    os << "a block";
614    return true;
615  default: {
616    const MemSpaceRegion *MS = MR->getMemorySpace();
617
618    if (isa<StackLocalsSpaceRegion>(MS)) {
619      const VarRegion *VR = dyn_cast<VarRegion>(MR);
620      const VarDecl *VD;
621      if (VR)
622        VD = VR->getDecl();
623      else
624        VD = NULL;
625
626      if (VD)
627        os << "the address of the local variable '" << VD->getName() << "'";
628      else
629        os << "the address of a local stack variable";
630      return true;
631    }
632
633    if (isa<StackArgumentsSpaceRegion>(MS)) {
634      const VarRegion *VR = dyn_cast<VarRegion>(MR);
635      const VarDecl *VD;
636      if (VR)
637        VD = VR->getDecl();
638      else
639        VD = NULL;
640
641      if (VD)
642        os << "the address of the parameter '" << VD->getName() << "'";
643      else
644        os << "the address of a parameter";
645      return true;
646    }
647
648    if (isa<GlobalsSpaceRegion>(MS)) {
649      const VarRegion *VR = dyn_cast<VarRegion>(MR);
650      const VarDecl *VD;
651      if (VR)
652        VD = VR->getDecl();
653      else
654        VD = NULL;
655
656      if (VD) {
657        if (VD->isStaticLocal())
658          os << "the address of the static variable '" << VD->getName() << "'";
659        else
660          os << "the address of the global variable '" << VD->getName() << "'";
661      } else
662        os << "the address of a global variable";
663      return true;
664    }
665
666    return false;
667  }
668  }
669}
670
671void MallocChecker::ReportBadFree(CheckerContext &C, SVal ArgVal,
672                                  SourceRange range) const {
673  if (ExplodedNode *N = C.generateSink()) {
674    if (!BT_BadFree)
675      BT_BadFree.reset(new BugType("Bad free", "Memory Error"));
676
677    SmallString<100> buf;
678    llvm::raw_svector_ostream os(buf);
679
680    const MemRegion *MR = ArgVal.getAsRegion();
681    if (MR) {
682      while (const ElementRegion *ER = dyn_cast<ElementRegion>(MR))
683        MR = ER->getSuperRegion();
684
685      // Special case for alloca()
686      if (isa<AllocaRegion>(MR))
687        os << "Argument to free() was allocated by alloca(), not malloc()";
688      else {
689        os << "Argument to free() is ";
690        if (SummarizeRegion(os, MR))
691          os << ", which is not memory allocated by malloc()";
692        else
693          os << "not memory allocated by malloc()";
694      }
695    } else {
696      os << "Argument to free() is ";
697      if (SummarizeValue(os, ArgVal))
698        os << ", which is not memory allocated by malloc()";
699      else
700        os << "not memory allocated by malloc()";
701    }
702
703    BugReport *R = new BugReport(*BT_BadFree, os.str(), N);
704    R->markInteresting(MR);
705    R->addRange(range);
706    C.EmitReport(R);
707  }
708}
709
710ProgramStateRef MallocChecker::ReallocMem(CheckerContext &C,
711                                          const CallExpr *CE,
712                                          bool FreesOnFail) const {
713  ProgramStateRef state = C.getState();
714  const Expr *arg0Expr = CE->getArg(0);
715  const LocationContext *LCtx = C.getLocationContext();
716  SVal Arg0Val = state->getSVal(arg0Expr, LCtx);
717  if (!isa<DefinedOrUnknownSVal>(Arg0Val))
718    return 0;
719  DefinedOrUnknownSVal arg0Val = cast<DefinedOrUnknownSVal>(Arg0Val);
720
721  SValBuilder &svalBuilder = C.getSValBuilder();
722
723  DefinedOrUnknownSVal PtrEQ =
724    svalBuilder.evalEQ(state, arg0Val, svalBuilder.makeNull());
725
726  // Get the size argument. If there is no size arg then give up.
727  const Expr *Arg1 = CE->getArg(1);
728  if (!Arg1)
729    return 0;
730
731  // Get the value of the size argument.
732  SVal Arg1ValG = state->getSVal(Arg1, LCtx);
733  if (!isa<DefinedOrUnknownSVal>(Arg1ValG))
734    return 0;
735  DefinedOrUnknownSVal Arg1Val = cast<DefinedOrUnknownSVal>(Arg1ValG);
736
737  // Compare the size argument to 0.
738  DefinedOrUnknownSVal SizeZero =
739    svalBuilder.evalEQ(state, Arg1Val,
740                       svalBuilder.makeIntValWithPtrWidth(0, false));
741
742  ProgramStateRef StatePtrIsNull, StatePtrNotNull;
743  llvm::tie(StatePtrIsNull, StatePtrNotNull) = state->assume(PtrEQ);
744  ProgramStateRef StateSizeIsZero, StateSizeNotZero;
745  llvm::tie(StateSizeIsZero, StateSizeNotZero) = state->assume(SizeZero);
746  // We only assume exceptional states if they are definitely true; if the
747  // state is under-constrained, assume regular realloc behavior.
748  bool PrtIsNull = StatePtrIsNull && !StatePtrNotNull;
749  bool SizeIsZero = StateSizeIsZero && !StateSizeNotZero;
750
751  // If the ptr is NULL and the size is not 0, the call is equivalent to
752  // malloc(size).
753  if ( PrtIsNull && !SizeIsZero) {
754    ProgramStateRef stateMalloc = MallocMemAux(C, CE, CE->getArg(1),
755                                               UndefinedVal(), StatePtrIsNull);
756    return stateMalloc;
757  }
758
759  if (PrtIsNull && SizeIsZero)
760    return 0;
761
762  // Get the from and to pointer symbols as in toPtr = realloc(fromPtr, size).
763  assert(!PrtIsNull);
764  SymbolRef FromPtr = arg0Val.getAsSymbol();
765  SVal RetVal = state->getSVal(CE, LCtx);
766  SymbolRef ToPtr = RetVal.getAsSymbol();
767  if (!FromPtr || !ToPtr)
768    return 0;
769
770  // If the size is 0, free the memory.
771  if (SizeIsZero)
772    if (ProgramStateRef stateFree = FreeMemAux(C, CE, StateSizeIsZero,0,false)){
773      // The semantics of the return value are:
774      // If size was equal to 0, either NULL or a pointer suitable to be passed
775      // to free() is returned.
776      stateFree = stateFree->set<ReallocPairs>(ToPtr,
777                                            ReallocPair(FromPtr, FreesOnFail));
778      C.getSymbolManager().addSymbolDependency(ToPtr, FromPtr);
779      return stateFree;
780    }
781
782  // Default behavior.
783  if (ProgramStateRef stateFree = FreeMemAux(C, CE, state, 0, false)) {
784    // FIXME: We should copy the content of the original buffer.
785    ProgramStateRef stateRealloc = MallocMemAux(C, CE, CE->getArg(1),
786                                                UnknownVal(), stateFree);
787    if (!stateRealloc)
788      return 0;
789    stateRealloc = stateRealloc->set<ReallocPairs>(ToPtr,
790                                            ReallocPair(FromPtr, FreesOnFail));
791    C.getSymbolManager().addSymbolDependency(ToPtr, FromPtr);
792    return stateRealloc;
793  }
794  return 0;
795}
796
797ProgramStateRef MallocChecker::CallocMem(CheckerContext &C, const CallExpr *CE){
798  ProgramStateRef state = C.getState();
799  SValBuilder &svalBuilder = C.getSValBuilder();
800  const LocationContext *LCtx = C.getLocationContext();
801  SVal count = state->getSVal(CE->getArg(0), LCtx);
802  SVal elementSize = state->getSVal(CE->getArg(1), LCtx);
803  SVal TotalSize = svalBuilder.evalBinOp(state, BO_Mul, count, elementSize,
804                                        svalBuilder.getContext().getSizeType());
805  SVal zeroVal = svalBuilder.makeZeroVal(svalBuilder.getContext().CharTy);
806
807  return MallocMemAux(C, CE, TotalSize, zeroVal, state);
808}
809
810LeakInfo
811MallocChecker::getAllocationSite(const ExplodedNode *N, SymbolRef Sym,
812                                 CheckerContext &C) const {
813  const LocationContext *LeakContext = N->getLocationContext();
814  // Walk the ExplodedGraph backwards and find the first node that referred to
815  // the tracked symbol.
816  const ExplodedNode *AllocNode = N;
817  const MemRegion *ReferenceRegion = 0;
818
819  while (N) {
820    ProgramStateRef State = N->getState();
821    if (!State->get<RegionState>(Sym))
822      break;
823
824    // Find the most recent expression bound to the symbol in the current
825    // context.
826    if (!ReferenceRegion) {
827      if (const MemRegion *MR = C.getLocationRegionIfPostStore(N)) {
828        SVal Val = State->getSVal(MR);
829        if (Val.getAsLocSymbol() == Sym)
830          ReferenceRegion = MR;
831      }
832    }
833
834    // Allocation node, is the last node in the current context in which the
835    // symbol was tracked.
836    if (N->getLocationContext() == LeakContext)
837      AllocNode = N;
838    N = N->pred_empty() ? NULL : *(N->pred_begin());
839  }
840
841  ProgramPoint P = AllocNode->getLocation();
842  const Stmt *AllocationStmt = 0;
843  if (isa<StmtPoint>(P))
844    AllocationStmt = cast<StmtPoint>(P).getStmt();
845
846  return LeakInfo(AllocationStmt, ReferenceRegion);
847}
848
849void MallocChecker::reportLeak(SymbolRef Sym, ExplodedNode *N,
850                               CheckerContext &C) const {
851  assert(N);
852  if (!BT_Leak) {
853    BT_Leak.reset(new BugType("Memory leak", "Memory Error"));
854    // Leaks should not be reported if they are post-dominated by a sink:
855    // (1) Sinks are higher importance bugs.
856    // (2) NoReturnFunctionChecker uses sink nodes to represent paths ending
857    //     with __noreturn functions such as assert() or exit(). We choose not
858    //     to report leaks on such paths.
859    BT_Leak->setSuppressOnSink(true);
860  }
861
862  // Most bug reports are cached at the location where they occurred.
863  // With leaks, we want to unique them by the location where they were
864  // allocated, and only report a single path.
865  PathDiagnosticLocation LocUsedForUniqueing;
866  const Stmt *AllocStmt = 0;
867  const MemRegion *Region = 0;
868  llvm::tie(AllocStmt, Region) = getAllocationSite(N, Sym, C);
869  if (AllocStmt)
870    LocUsedForUniqueing = PathDiagnosticLocation::createBegin(AllocStmt,
871                            C.getSourceManager(), N->getLocationContext());
872
873  SmallString<200> buf;
874  llvm::raw_svector_ostream os(buf);
875  os << "Memory is never released; potential leak";
876  if (Region) {
877    os << " of memory pointed to by '";
878    Region->dumpPretty(os);
879    os <<'\'';
880  }
881
882  BugReport *R = new BugReport(*BT_Leak, os.str(), N, LocUsedForUniqueing);
883  R->markInteresting(Sym);
884  R->addVisitor(new MallocBugVisitor(Sym));
885  C.EmitReport(R);
886}
887
888void MallocChecker::checkDeadSymbols(SymbolReaper &SymReaper,
889                                     CheckerContext &C) const
890{
891  if (!SymReaper.hasDeadSymbols())
892    return;
893
894  ProgramStateRef state = C.getState();
895  RegionStateTy RS = state->get<RegionState>();
896  RegionStateTy::Factory &F = state->get_context<RegionState>();
897
898  bool generateReport = false;
899  llvm::SmallVector<SymbolRef, 2> Errors;
900  for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
901    if (SymReaper.isDead(I->first)) {
902      if (I->second.isAllocated()) {
903        generateReport = true;
904        Errors.push_back(I->first);
905      }
906      // Remove the dead symbol from the map.
907      RS = F.remove(RS, I->first);
908
909    }
910  }
911
912  // Cleanup the Realloc Pairs Map.
913  ReallocMap RP = state->get<ReallocPairs>();
914  for (ReallocMap::iterator I = RP.begin(), E = RP.end(); I != E; ++I) {
915    if (SymReaper.isDead(I->first) ||
916        SymReaper.isDead(I->second.ReallocatedSym)) {
917      state = state->remove<ReallocPairs>(I->first);
918    }
919  }
920
921  // Generate leak node.
922  static SimpleProgramPointTag Tag("MallocChecker : DeadSymbolsLeak");
923  ExplodedNode *N = C.addTransition(C.getState(), C.getPredecessor(), &Tag);
924
925  if (generateReport) {
926    for (llvm::SmallVector<SymbolRef, 2>::iterator
927         I = Errors.begin(), E = Errors.end(); I != E; ++I) {
928      reportLeak(*I, N, C);
929    }
930  }
931  C.addTransition(state->set<RegionState>(RS), N);
932}
933
934void MallocChecker::checkEndPath(CheckerContext &C) const {
935  ProgramStateRef state = C.getState();
936  RegionStateTy M = state->get<RegionState>();
937
938  // If inside inlined call, skip it.
939  if (C.getLocationContext()->getParent() != 0)
940    return;
941
942  for (RegionStateTy::iterator I = M.begin(), E = M.end(); I != E; ++I) {
943    RefState RS = I->second;
944    if (RS.isAllocated()) {
945      ExplodedNode *N = C.addTransition(state);
946      if (N)
947        reportLeak(I->first, N, C);
948    }
949  }
950}
951
952bool MallocChecker::checkEscape(SymbolRef Sym, const Stmt *S,
953                                CheckerContext &C) const {
954  ProgramStateRef state = C.getState();
955  const RefState *RS = state->get<RegionState>(Sym);
956  if (!RS)
957    return false;
958
959  if (RS->isAllocated()) {
960    state = state->set<RegionState>(Sym, RefState::getEscaped(S));
961    C.addTransition(state);
962    return true;
963  }
964  return false;
965}
966
967void MallocChecker::checkPreStmt(const CallExpr *CE, CheckerContext &C) const {
968  if (isMemFunction(C.getCalleeDecl(CE), C.getASTContext()))
969    return;
970
971  // Check use after free, when a freed pointer is passed to a call.
972  ProgramStateRef State = C.getState();
973  for (CallExpr::const_arg_iterator I = CE->arg_begin(),
974                                    E = CE->arg_end(); I != E; ++I) {
975    const Expr *A = *I;
976    if (A->getType().getTypePtr()->isAnyPointerType()) {
977      SymbolRef Sym = State->getSVal(A, C.getLocationContext()).getAsSymbol();
978      if (!Sym)
979        continue;
980      if (checkUseAfterFree(Sym, C, A))
981        return;
982    }
983  }
984}
985
986void MallocChecker::checkPreStmt(const ReturnStmt *S, CheckerContext &C) const {
987  const Expr *E = S->getRetValue();
988  if (!E)
989    return;
990
991  // Check if we are returning a symbol.
992  SVal RetVal = C.getState()->getSVal(E, C.getLocationContext());
993  SymbolRef Sym = RetVal.getAsSymbol();
994  if (!Sym)
995    // If we are returning a field of the allocated struct or an array element,
996    // the callee could still free the memory.
997    // TODO: This logic should be a part of generic symbol escape callback.
998    if (const MemRegion *MR = RetVal.getAsRegion())
999      if (isa<FieldRegion>(MR) || isa<ElementRegion>(MR))
1000        if (const SymbolicRegion *BMR =
1001              dyn_cast<SymbolicRegion>(MR->getBaseRegion()))
1002          Sym = BMR->getSymbol();
1003  if (!Sym)
1004    return;
1005
1006  // Check if we are returning freed memory.
1007  if (checkUseAfterFree(Sym, C, E))
1008    return;
1009
1010  // If this function body is not inlined, check if the symbol is escaping.
1011  if (C.getLocationContext()->getParent() == 0)
1012    checkEscape(Sym, E, C);
1013}
1014
1015// TODO: Blocks should be either inlined or should call invalidate regions
1016// upon invocation. After that's in place, special casing here will not be
1017// needed.
1018void MallocChecker::checkPostStmt(const BlockExpr *BE,
1019                                  CheckerContext &C) const {
1020
1021  // Scan the BlockDecRefExprs for any object the retain count checker
1022  // may be tracking.
1023  if (!BE->getBlockDecl()->hasCaptures())
1024    return;
1025
1026  ProgramStateRef state = C.getState();
1027  const BlockDataRegion *R =
1028    cast<BlockDataRegion>(state->getSVal(BE,
1029                                         C.getLocationContext()).getAsRegion());
1030
1031  BlockDataRegion::referenced_vars_iterator I = R->referenced_vars_begin(),
1032                                            E = R->referenced_vars_end();
1033
1034  if (I == E)
1035    return;
1036
1037  SmallVector<const MemRegion*, 10> Regions;
1038  const LocationContext *LC = C.getLocationContext();
1039  MemRegionManager &MemMgr = C.getSValBuilder().getRegionManager();
1040
1041  for ( ; I != E; ++I) {
1042    const VarRegion *VR = *I;
1043    if (VR->getSuperRegion() == R) {
1044      VR = MemMgr.getVarRegion(VR->getDecl(), LC);
1045    }
1046    Regions.push_back(VR);
1047  }
1048
1049  state =
1050    state->scanReachableSymbols<StopTrackingCallback>(Regions.data(),
1051                                    Regions.data() + Regions.size()).getState();
1052  C.addTransition(state);
1053}
1054
1055bool MallocChecker::checkUseAfterFree(SymbolRef Sym, CheckerContext &C,
1056                                      const Stmt *S) const {
1057  assert(Sym);
1058  const RefState *RS = C.getState()->get<RegionState>(Sym);
1059  if (RS && RS->isReleased()) {
1060    if (ExplodedNode *N = C.generateSink()) {
1061      if (!BT_UseFree)
1062        BT_UseFree.reset(new BugType("Use-after-free", "Memory Error"));
1063
1064      BugReport *R = new BugReport(*BT_UseFree,
1065                                   "Use of memory after it is freed",N);
1066      if (S)
1067        R->addRange(S->getSourceRange());
1068      R->markInteresting(Sym);
1069      R->addVisitor(new MallocBugVisitor(Sym));
1070      C.EmitReport(R);
1071      return true;
1072    }
1073  }
1074  return false;
1075}
1076
1077// Check if the location is a freed symbolic region.
1078void MallocChecker::checkLocation(SVal l, bool isLoad, const Stmt *S,
1079                                  CheckerContext &C) const {
1080  SymbolRef Sym = l.getLocSymbolInBase();
1081  if (Sym)
1082    checkUseAfterFree(Sym, C);
1083}
1084
1085//===----------------------------------------------------------------------===//
1086// Check various ways a symbol can be invalidated.
1087// TODO: This logic (the next 3 functions) is copied/similar to the
1088// RetainRelease checker. We might want to factor this out.
1089//===----------------------------------------------------------------------===//
1090
1091// Stop tracking symbols when a value escapes as a result of checkBind.
1092// A value escapes in three possible cases:
1093// (1) we are binding to something that is not a memory region.
1094// (2) we are binding to a memregion that does not have stack storage
1095// (3) we are binding to a memregion with stack storage that the store
1096//     does not understand.
1097void MallocChecker::checkBind(SVal loc, SVal val, const Stmt *S,
1098                              CheckerContext &C) const {
1099  // Are we storing to something that causes the value to "escape"?
1100  bool escapes = true;
1101  ProgramStateRef state = C.getState();
1102
1103  if (loc::MemRegionVal *regionLoc = dyn_cast<loc::MemRegionVal>(&loc)) {
1104    escapes = !regionLoc->getRegion()->hasStackStorage();
1105
1106    if (!escapes) {
1107      // To test (3), generate a new state with the binding added.  If it is
1108      // the same state, then it escapes (since the store cannot represent
1109      // the binding).
1110      escapes = (state == (state->bindLoc(*regionLoc, val)));
1111    }
1112    if (!escapes) {
1113      // Case 4: We do not currently model what happens when a symbol is
1114      // assigned to a struct field, so be conservative here and let the symbol
1115      // go. TODO: This could definitely be improved upon.
1116      escapes = !isa<VarRegion>(regionLoc->getRegion());
1117    }
1118  }
1119
1120  // If our store can represent the binding and we aren't storing to something
1121  // that doesn't have local storage then just return and have the simulation
1122  // state continue as is.
1123  if (!escapes)
1124      return;
1125
1126  // Otherwise, find all symbols referenced by 'val' that we are tracking
1127  // and stop tracking them.
1128  state = state->scanReachableSymbols<StopTrackingCallback>(val).getState();
1129  C.addTransition(state);
1130}
1131
1132// If a symbolic region is assumed to NULL (or another constant), stop tracking
1133// it - assuming that allocation failed on this path.
1134ProgramStateRef MallocChecker::evalAssume(ProgramStateRef state,
1135                                              SVal Cond,
1136                                              bool Assumption) const {
1137  RegionStateTy RS = state->get<RegionState>();
1138  for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
1139    // If the symbol is assumed to NULL or another constant, this will
1140    // return an APSInt*.
1141    if (state->getSymVal(I.getKey()))
1142      state = state->remove<RegionState>(I.getKey());
1143  }
1144
1145  // Realloc returns 0 when reallocation fails, which means that we should
1146  // restore the state of the pointer being reallocated.
1147  ReallocMap RP = state->get<ReallocPairs>();
1148  for (ReallocMap::iterator I = RP.begin(), E = RP.end(); I != E; ++I) {
1149    // If the symbol is assumed to NULL or another constant, this will
1150    // return an APSInt*.
1151    if (state->getSymVal(I.getKey())) {
1152      SymbolRef ReallocSym = I.getData().ReallocatedSym;
1153      const RefState *RS = state->get<RegionState>(ReallocSym);
1154      if (RS) {
1155        if (RS->isReleased() && ! I.getData().IsFreeOnFailure)
1156          state = state->set<RegionState>(ReallocSym,
1157                             RefState::getAllocateUnchecked(RS->getStmt()));
1158      }
1159      state = state->remove<ReallocPairs>(I.getKey());
1160    }
1161  }
1162
1163  return state;
1164}
1165
1166// Check if the function is known to us. So, for example, we could
1167// conservatively assume it can free/reallocate it's pointer arguments.
1168// (We assume that the pointers cannot escape through calls to system
1169// functions not handled by this checker.)
1170bool MallocChecker::doesNotFreeMemory(const CallOrObjCMessage *Call,
1171                                      ProgramStateRef State) const {
1172  if (!Call)
1173    return false;
1174
1175  // For now, assume that any C++ call can free memory.
1176  // TODO: If we want to be more optimistic here, we'll need to make sure that
1177  // regions escape to C++ containers. They seem to do that even now, but for
1178  // mysterious reasons.
1179  if (Call->isCXXCall())
1180    return false;
1181
1182  const Decl *D = Call->getDecl();
1183  if (!D)
1184    return false;
1185
1186  ASTContext &ASTC = State->getStateManager().getContext();
1187
1188  // If it's one of the allocation functions we can reason about, we model
1189  // its behavior explicitly.
1190  if (isa<FunctionDecl>(D) && isMemFunction(cast<FunctionDecl>(D), ASTC)) {
1191    return true;
1192  }
1193
1194  // If it's not a system call, assume it frees memory.
1195  SourceManager &SM = ASTC.getSourceManager();
1196  if (!SM.isInSystemHeader(D->getLocation()))
1197    return false;
1198
1199  // Process C/ObjC functions.
1200  if (const FunctionDecl *FD  = dyn_cast<FunctionDecl>(D)) {
1201    // White list the system functions whose arguments escape.
1202    const IdentifierInfo *II = FD->getIdentifier();
1203    if (!II)
1204      return true;
1205    StringRef FName = II->getName();
1206
1207    // White list thread local storage.
1208    if (FName.equals("pthread_setspecific"))
1209      return false;
1210
1211    // White list the 'XXXNoCopy' ObjC functions.
1212    if (FName.endswith("NoCopy")) {
1213      // Look for the deallocator argument. We know that the memory ownership
1214      // is not transfered only if the deallocator argument is
1215      // 'kCFAllocatorNull'.
1216      for (unsigned i = 1; i < Call->getNumArgs(); ++i) {
1217        const Expr *ArgE = Call->getArg(i)->IgnoreParenCasts();
1218        if (const DeclRefExpr *DE = dyn_cast<DeclRefExpr>(ArgE)) {
1219          StringRef DeallocatorName = DE->getFoundDecl()->getName();
1220          if (DeallocatorName == "kCFAllocatorNull")
1221            return true;
1222        }
1223      }
1224      return false;
1225    }
1226
1227    // PR12101
1228    // Many CoreFoundation and CoreGraphics might allow a tracked object
1229    // to escape.
1230    if (Call->isCFCGAllowingEscape(FName))
1231      return false;
1232
1233    // Associating streams with malloced buffers. The pointer can escape if
1234    // 'closefn' is specified (and if that function does free memory).
1235    // Currently, we do not inspect the 'closefn' function (PR12101).
1236    if (FName == "funopen")
1237      if (Call->getNumArgs() >= 4 && !Call->getArgSVal(4).isConstant(0))
1238        return false;
1239
1240    // Do not warn on pointers passed to 'setbuf' when used with std streams,
1241    // these leaks might be intentional when setting the buffer for stdio.
1242    // http://stackoverflow.com/questions/2671151/who-frees-setvbuf-buffer
1243    if (FName == "setbuf" || FName =="setbuffer" ||
1244        FName == "setlinebuf" || FName == "setvbuf") {
1245      if (Call->getNumArgs() >= 1)
1246        if (const DeclRefExpr *Arg =
1247              dyn_cast<DeclRefExpr>(Call->getArg(0)->IgnoreParenCasts()))
1248          if (const VarDecl *D = dyn_cast<VarDecl>(Arg->getDecl()))
1249              if (D->getCanonicalDecl()->getName().find("std")
1250                                                   != StringRef::npos)
1251                return false;
1252    }
1253
1254    // A bunch of other functions, which take ownership of a pointer (See retain
1255    // release checker). Not all the parameters here are invalidated, but the
1256    // Malloc checker cannot differentiate between them. The right way of doing
1257    // this would be to implement a pointer escapes callback.
1258    if (FName == "CVPixelBufferCreateWithBytes" ||
1259        FName == "CGBitmapContextCreateWithData" ||
1260        FName == "CVPixelBufferCreateWithPlanarBytes") {
1261      return false;
1262    }
1263
1264    // Otherwise, assume that the function does not free memory.
1265    // Most system calls, do not free the memory.
1266    return true;
1267
1268  // Process ObjC functions.
1269  } else if (const ObjCMethodDecl * ObjCD = dyn_cast<ObjCMethodDecl>(D)) {
1270    Selector S = ObjCD->getSelector();
1271
1272    // White list the ObjC functions which do free memory.
1273    // - Anything containing 'freeWhenDone' param set to 1.
1274    //   Ex: dataWithBytesNoCopy:length:freeWhenDone.
1275    for (unsigned i = 1; i < S.getNumArgs(); ++i) {
1276      if (S.getNameForSlot(i).equals("freeWhenDone")) {
1277        if (Call->getArgSVal(i).isConstant(1))
1278          return false;
1279        else
1280          return true;
1281      }
1282    }
1283
1284    // If the first selector ends with NoCopy, assume that the ownership is
1285    // transfered as well.
1286    // Ex:  [NSData dataWithBytesNoCopy:bytes length:10];
1287    if (S.getNameForSlot(0).endswith("NoCopy")) {
1288      return false;
1289    }
1290
1291    // Otherwise, assume that the function does not free memory.
1292    // Most system calls, do not free the memory.
1293    return true;
1294  }
1295
1296  // Otherwise, assume that the function can free memory.
1297  return false;
1298
1299}
1300
1301// If the symbol we are tracking is invalidated, but not explicitly (ex: the &p
1302// escapes, when we are tracking p), do not track the symbol as we cannot reason
1303// about it anymore.
1304ProgramStateRef
1305MallocChecker::checkRegionChanges(ProgramStateRef State,
1306                            const StoreManager::InvalidatedSymbols *invalidated,
1307                                    ArrayRef<const MemRegion *> ExplicitRegions,
1308                                    ArrayRef<const MemRegion *> Regions,
1309                                    const CallOrObjCMessage *Call) const {
1310  if (!invalidated || invalidated->empty())
1311    return State;
1312  llvm::SmallPtrSet<SymbolRef, 8> WhitelistedSymbols;
1313
1314  // If it's a call which might free or reallocate memory, we assume that all
1315  // regions (explicit and implicit) escaped.
1316
1317  // Otherwise, whitelist explicit pointers; we still can track them.
1318  if (!Call || doesNotFreeMemory(Call, State)) {
1319    for (ArrayRef<const MemRegion *>::iterator I = ExplicitRegions.begin(),
1320        E = ExplicitRegions.end(); I != E; ++I) {
1321      if (const SymbolicRegion *R = (*I)->StripCasts()->getAs<SymbolicRegion>())
1322        WhitelistedSymbols.insert(R->getSymbol());
1323    }
1324  }
1325
1326  for (StoreManager::InvalidatedSymbols::const_iterator I=invalidated->begin(),
1327       E = invalidated->end(); I!=E; ++I) {
1328    SymbolRef sym = *I;
1329    if (WhitelistedSymbols.count(sym))
1330      continue;
1331    // The symbol escaped.
1332    if (const RefState *RS = State->get<RegionState>(sym))
1333      State = State->set<RegionState>(sym, RefState::getEscaped(RS->getStmt()));
1334  }
1335  return State;
1336}
1337
1338static SymbolRef findFailedReallocSymbol(ProgramStateRef currState,
1339                                         ProgramStateRef prevState) {
1340  ReallocMap currMap = currState->get<ReallocPairs>();
1341  ReallocMap prevMap = prevState->get<ReallocPairs>();
1342
1343  for (ReallocMap::iterator I = prevMap.begin(), E = prevMap.end();
1344       I != E; ++I) {
1345    SymbolRef sym = I.getKey();
1346    if (!currMap.lookup(sym))
1347      return sym;
1348  }
1349
1350  return NULL;
1351}
1352
1353PathDiagnosticPiece *
1354MallocChecker::MallocBugVisitor::VisitNode(const ExplodedNode *N,
1355                                           const ExplodedNode *PrevN,
1356                                           BugReporterContext &BRC,
1357                                           BugReport &BR) {
1358  ProgramStateRef state = N->getState();
1359  ProgramStateRef statePrev = PrevN->getState();
1360
1361  const RefState *RS = state->get<RegionState>(Sym);
1362  const RefState *RSPrev = statePrev->get<RegionState>(Sym);
1363  if (!RS && !RSPrev)
1364    return 0;
1365
1366  const Stmt *S = 0;
1367  const char *Msg = 0;
1368  StackHintGeneratorForSymbol *StackHint = 0;
1369
1370  // Retrieve the associated statement.
1371  ProgramPoint ProgLoc = N->getLocation();
1372  if (isa<StmtPoint>(ProgLoc))
1373    S = cast<StmtPoint>(ProgLoc).getStmt();
1374  // If an assumption was made on a branch, it should be caught
1375  // here by looking at the state transition.
1376  if (isa<BlockEdge>(ProgLoc)) {
1377    const CFGBlock *srcBlk = cast<BlockEdge>(ProgLoc).getSrc();
1378    S = srcBlk->getTerminator();
1379  }
1380  if (!S)
1381    return 0;
1382
1383  // Find out if this is an interesting point and what is the kind.
1384  if (Mode == Normal) {
1385    if (isAllocated(RS, RSPrev, S)) {
1386      Msg = "Memory is allocated";
1387      StackHint = new StackHintGeneratorForSymbol(Sym,
1388                                                  "Returned allocated memory");
1389    } else if (isReleased(RS, RSPrev, S)) {
1390      Msg = "Memory is released";
1391      StackHint = new StackHintGeneratorForSymbol(Sym,
1392                                                  "Returned released memory");
1393    } else if (isReallocFailedCheck(RS, RSPrev, S)) {
1394      Mode = ReallocationFailed;
1395      Msg = "Reallocation failed";
1396      StackHint = new StackHintGeneratorForReallocationFailed(Sym,
1397                                                       "Reallocation failed");
1398
1399      if (SymbolRef sym = findFailedReallocSymbol(state, statePrev)) {
1400        // Is it possible to fail two reallocs WITHOUT testing in between?
1401        assert((!FailedReallocSymbol || FailedReallocSymbol == sym) &&
1402          "We only support one failed realloc at a time.");
1403        BR.markInteresting(sym);
1404        FailedReallocSymbol = sym;
1405      }
1406    }
1407
1408  // We are in a special mode if a reallocation failed later in the path.
1409  } else if (Mode == ReallocationFailed) {
1410    assert(FailedReallocSymbol && "No symbol to look for.");
1411
1412    // Is this is the first appearance of the reallocated symbol?
1413    if (!statePrev->get<RegionState>(FailedReallocSymbol)) {
1414      // If we ever hit this assert, that means BugReporter has decided to skip
1415      // node pairs or visit them out of order.
1416      assert(state->get<RegionState>(FailedReallocSymbol) &&
1417        "Missed the reallocation point");
1418
1419      // We're at the reallocation point.
1420      Msg = "Attempt to reallocate memory";
1421      StackHint = new StackHintGeneratorForSymbol(Sym,
1422                                                 "Returned reallocated memory");
1423      FailedReallocSymbol = NULL;
1424      Mode = Normal;
1425    }
1426  }
1427
1428  if (!Msg)
1429    return 0;
1430  assert(StackHint);
1431
1432  // Generate the extra diagnostic.
1433  PathDiagnosticLocation Pos(S, BRC.getSourceManager(),
1434                             N->getLocationContext());
1435  return new PathDiagnosticEventPiece(Pos, Msg, true, StackHint);
1436}
1437
1438
1439#define REGISTER_CHECKER(name) \
1440void ento::register##name(CheckerManager &mgr) {\
1441  registerCStringCheckerBasic(mgr); \
1442  mgr.registerChecker<MallocChecker>()->Filter.C##name = true;\
1443}
1444
1445REGISTER_CHECKER(MallocPessimistic)
1446REGISTER_CHECKER(MallocOptimistic)
1447