MallocChecker.cpp revision a3989b8f54421cd90a48ace8820c7147cea6bb3d 
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/AST/Attr.h"
18#include "clang/Basic/SourceManager.h"
19#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
20#include "clang/StaticAnalyzer/Core/Checker.h"
21#include "clang/StaticAnalyzer/Core/CheckerManager.h"
22#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
23#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
24#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
25#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
26#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
27#include "llvm/ADT/ImmutableMap.h"
28#include "llvm/ADT/STLExtras.h"
29#include "llvm/ADT/SmallString.h"
30#include "llvm/ADT/StringExtras.h"
31#include <climits>
32
33using namespace clang;
34using namespace ento;
35
36namespace {
37
38// Used to check correspondence between allocators and deallocators.
39enum AllocationFamily {
40  AF_None,
41  AF_Malloc,
42  AF_CXXNew,
43  AF_CXXNewArray
44};
45
46class RefState {
47  enum Kind { // Reference to allocated memory.
48              Allocated,
49              // Reference to released/freed memory.
50              Released,
51              // The responsibility for freeing resources has transfered from
52              // this reference. A relinquished symbol should not be freed.
53              Relinquished };
54
55  const Stmt *S;
56  unsigned K : 2; // Kind enum, but stored as a bitfield.
57  unsigned Family : 30; // Rest of 32-bit word, currently just an allocation
58                        // family.
59
60  RefState(Kind k, const Stmt *s, unsigned family)
61    : S(s), K(k), Family(family) {}
62public:
63  bool isAllocated() const { return K == Allocated; }
64  bool isReleased() const { return K == Released; }
65  bool isRelinquished() const { return K == Relinquished; }
66  AllocationFamily getAllocationFamily() const {
67    return (AllocationFamily)Family;
68  }
69  const Stmt *getStmt() const { return S; }
70
71  bool operator==(const RefState &X) const {
72    return K == X.K && S == X.S && Family == X.Family;
73  }
74
75  static RefState getAllocated(unsigned family, const Stmt *s) {
76    return RefState(Allocated, s, family);
77  }
78  static RefState getReleased(unsigned family, const Stmt *s) {
79    return RefState(Released, s, family);
80  }
81  static RefState getRelinquished(unsigned family, const Stmt *s) {
82    return RefState(Relinquished, s, family);
83  }
84
85  void Profile(llvm::FoldingSetNodeID &ID) const {
86    ID.AddInteger(K);
87    ID.AddPointer(S);
88    ID.AddInteger(Family);
89  }
90
91  void dump(raw_ostream &OS) const {
92    static const char *Table[] = {
93      "Allocated",
94      "Released",
95      "Relinquished"
96    };
97    OS << Table[(unsigned) K];
98  }
99
100  LLVM_ATTRIBUTE_USED void dump() const {
101    dump(llvm::errs());
102  }
103};
104
105enum ReallocPairKind {
106  RPToBeFreedAfterFailure,
107  // The symbol has been freed when reallocation failed.
108  RPIsFreeOnFailure,
109  // The symbol does not need to be freed after reallocation fails.
110  RPDoNotTrackAfterFailure
111};
112
113/// \class ReallocPair
114/// \brief Stores information about the symbol being reallocated by a call to
115/// 'realloc' to allow modeling failed reallocation later in the path.
116struct ReallocPair {
117  // \brief The symbol which realloc reallocated.
118  SymbolRef ReallocatedSym;
119  ReallocPairKind Kind;
120
121  ReallocPair(SymbolRef S, ReallocPairKind K) :
122    ReallocatedSym(S), Kind(K) {}
123  void Profile(llvm::FoldingSetNodeID &ID) const {
124    ID.AddInteger(Kind);
125    ID.AddPointer(ReallocatedSym);
126  }
127  bool operator==(const ReallocPair &X) const {
128    return ReallocatedSym == X.ReallocatedSym &&
129           Kind == X.Kind;
130  }
131};
132
133typedef std::pair<const ExplodedNode*, const MemRegion*> LeakInfo;
134
135class MallocChecker : public Checker<check::DeadSymbols,
136                                     check::PointerEscape,
137                                     check::ConstPointerEscape,
138                                     check::PreStmt<ReturnStmt>,
139                                     check::PreStmt<CallExpr>,
140                                     check::PostStmt<CallExpr>,
141                                     check::PostStmt<CXXNewExpr>,
142                                     check::PreStmt<CXXDeleteExpr>,
143                                     check::PostStmt<BlockExpr>,
144                                     check::PostObjCMessage,
145                                     check::Location,
146                                     eval::Assume>
147{
148  mutable OwningPtr<BugType> BT_DoubleFree;
149  mutable OwningPtr<BugType> BT_Leak;
150  mutable OwningPtr<BugType> BT_UseFree;
151  mutable OwningPtr<BugType> BT_BadFree;
152  mutable OwningPtr<BugType> BT_MismatchedDealloc;
153  mutable OwningPtr<BugType> BT_OffsetFree;
154  mutable IdentifierInfo *II_malloc, *II_free, *II_realloc, *II_calloc,
155                         *II_valloc, *II_reallocf, *II_strndup, *II_strdup;
156
157public:
158  MallocChecker() : II_malloc(0), II_free(0), II_realloc(0), II_calloc(0),
159                    II_valloc(0), II_reallocf(0), II_strndup(0), II_strdup(0) {}
160
161  /// In pessimistic mode, the checker assumes that it does not know which
162  /// functions might free the memory.
163  struct ChecksFilter {
164    DefaultBool CMallocPessimistic;
165    DefaultBool CMallocOptimistic;
166    DefaultBool CNewDeleteChecker;
167    DefaultBool CNewDeleteLeaksChecker;
168    DefaultBool CMismatchedDeallocatorChecker;
169  };
170
171  ChecksFilter Filter;
172
173  void checkPreStmt(const CallExpr *S, CheckerContext &C) const;
174  void checkPostStmt(const CallExpr *CE, CheckerContext &C) const;
175  void checkPostStmt(const CXXNewExpr *NE, CheckerContext &C) const;
176  void checkPreStmt(const CXXDeleteExpr *DE, CheckerContext &C) const;
177  void checkPostObjCMessage(const ObjCMethodCall &Call, CheckerContext &C) const;
178  void checkPostStmt(const BlockExpr *BE, CheckerContext &C) const;
179  void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const;
180  void checkPreStmt(const ReturnStmt *S, CheckerContext &C) const;
181  ProgramStateRef evalAssume(ProgramStateRef state, SVal Cond,
182                            bool Assumption) const;
183  void checkLocation(SVal l, bool isLoad, const Stmt *S,
184                     CheckerContext &C) const;
185
186  ProgramStateRef checkPointerEscape(ProgramStateRef State,
187                                    const InvalidatedSymbols &Escaped,
188                                    const CallEvent *Call,
189                                    PointerEscapeKind Kind) const;
190  ProgramStateRef checkConstPointerEscape(ProgramStateRef State,
191                                          const InvalidatedSymbols &Escaped,
192                                          const CallEvent *Call,
193                                          PointerEscapeKind Kind) const;
194
195  void printState(raw_ostream &Out, ProgramStateRef State,
196                  const char *NL, const char *Sep) const;
197
198private:
199  void initIdentifierInfo(ASTContext &C) const;
200
201  /// \brief Determine family of a deallocation expression.
202  AllocationFamily getAllocationFamily(CheckerContext &C, const Stmt *S) const;
203
204  /// \brief Print names of allocators and deallocators.
205  ///
206  /// \returns true on success.
207  bool printAllocDeallocName(raw_ostream &os, CheckerContext &C,
208                             const Expr *E) const;
209
210  /// \brief Print expected name of an allocator based on the deallocator's
211  /// family derived from the DeallocExpr.
212  void printExpectedAllocName(raw_ostream &os, CheckerContext &C,
213                              const Expr *DeallocExpr) const;
214  /// \brief Print expected name of a deallocator based on the allocator's
215  /// family.
216  void printExpectedDeallocName(raw_ostream &os, AllocationFamily Family) const;
217
218  ///@{
219  /// Check if this is one of the functions which can allocate/reallocate memory
220  /// pointed to by one of its arguments.
221  bool isMemFunction(const FunctionDecl *FD, ASTContext &C) const;
222  bool isFreeFunction(const FunctionDecl *FD, ASTContext &C) const;
223  bool isAllocationFunction(const FunctionDecl *FD, ASTContext &C) const;
224  bool isStandardNewDelete(const FunctionDecl *FD, ASTContext &C) const;
225  ///@}
226  static ProgramStateRef MallocMemReturnsAttr(CheckerContext &C,
227                                              const CallExpr *CE,
228                                              const OwnershipAttr* Att);
229  static ProgramStateRef MallocMemAux(CheckerContext &C, const CallExpr *CE,
230                                     const Expr *SizeEx, SVal Init,
231                                     ProgramStateRef State,
232                                     AllocationFamily Family = AF_Malloc) {
233    return MallocMemAux(C, CE,
234                        State->getSVal(SizeEx, C.getLocationContext()),
235                        Init, State, Family);
236  }
237
238  static ProgramStateRef MallocMemAux(CheckerContext &C, const CallExpr *CE,
239                                     SVal SizeEx, SVal Init,
240                                     ProgramStateRef State,
241                                     AllocationFamily Family = AF_Malloc);
242
243  /// Update the RefState to reflect the new memory allocation.
244  static ProgramStateRef
245  MallocUpdateRefState(CheckerContext &C, const Expr *E, ProgramStateRef State,
246                       AllocationFamily Family = AF_Malloc);
247
248  ProgramStateRef FreeMemAttr(CheckerContext &C, const CallExpr *CE,
249                              const OwnershipAttr* Att) const;
250  ProgramStateRef FreeMemAux(CheckerContext &C, const CallExpr *CE,
251                             ProgramStateRef state, unsigned Num,
252                             bool Hold,
253                             bool &ReleasedAllocated,
254                             bool ReturnsNullOnFailure = false) const;
255  ProgramStateRef FreeMemAux(CheckerContext &C, const Expr *Arg,
256                             const Expr *ParentExpr,
257                             ProgramStateRef State,
258                             bool Hold,
259                             bool &ReleasedAllocated,
260                             bool ReturnsNullOnFailure = false) const;
261
262  ProgramStateRef ReallocMem(CheckerContext &C, const CallExpr *CE,
263                             bool FreesMemOnFailure) const;
264  static ProgramStateRef CallocMem(CheckerContext &C, const CallExpr *CE);
265
266  ///\brief Check if the memory associated with this symbol was released.
267  bool isReleased(SymbolRef Sym, CheckerContext &C) const;
268
269  bool checkUseAfterFree(SymbolRef Sym, CheckerContext &C, const Stmt *S) const;
270
271  /// Check if the function is known not to free memory, or if it is
272  /// "interesting" and should be modeled explicitly.
273  ///
274  /// We assume that pointers do not escape through calls to system functions
275  /// not handled by this checker.
276  bool doesNotFreeMemOrInteresting(const CallEvent *Call,
277                                   ProgramStateRef State) const;
278
279  // Implementation of the checkPointerEscape callabcks.
280  ProgramStateRef checkPointerEscapeAux(ProgramStateRef State,
281                                  const InvalidatedSymbols &Escaped,
282                                  const CallEvent *Call,
283                                  PointerEscapeKind Kind,
284                                  bool(*CheckRefState)(const RefState*)) const;
285
286  // Used to suppress warnings if they are not related to the tracked family
287  // (derived from Sym or AllocDeallocStmt).
288  bool isTrackedFamily(AllocationFamily Family) const;
289  bool isTrackedFamily(CheckerContext &C, const Stmt *AllocDeallocStmt) const;
290  bool isTrackedFamily(CheckerContext &C, SymbolRef Sym) const;
291
292  static bool SummarizeValue(raw_ostream &os, SVal V);
293  static bool SummarizeRegion(raw_ostream &os, const MemRegion *MR);
294  void ReportBadFree(CheckerContext &C, SVal ArgVal, SourceRange Range,
295                     const Expr *DeallocExpr) const;
296  void ReportMismatchedDealloc(CheckerContext &C, SourceRange Range,
297                               const Expr *DeallocExpr, const RefState *RS,
298                               SymbolRef Sym) const;
299  void ReportOffsetFree(CheckerContext &C, SVal ArgVal, SourceRange Range,
300                        const Expr *DeallocExpr,
301                        const Expr *AllocExpr = 0) const;
302  void ReportUseAfterFree(CheckerContext &C, SourceRange Range,
303                          SymbolRef Sym) const;
304  void ReportDoubleFree(CheckerContext &C, SourceRange Range, bool Released,
305                        SymbolRef Sym, SymbolRef PrevSym) const;
306
307  /// Find the location of the allocation for Sym on the path leading to the
308  /// exploded node N.
309  LeakInfo getAllocationSite(const ExplodedNode *N, SymbolRef Sym,
310                             CheckerContext &C) const;
311
312  void reportLeak(SymbolRef Sym, ExplodedNode *N, CheckerContext &C) const;
313
314  /// The bug visitor which allows us to print extra diagnostics along the
315  /// BugReport path. For example, showing the allocation site of the leaked
316  /// region.
317  class MallocBugVisitor : public BugReporterVisitorImpl<MallocBugVisitor> {
318  protected:
319    enum NotificationMode {
320      Normal,
321      ReallocationFailed
322    };
323
324    // The allocated region symbol tracked by the main analysis.
325    SymbolRef Sym;
326
327    // The mode we are in, i.e. what kind of diagnostics will be emitted.
328    NotificationMode Mode;
329
330    // A symbol from when the primary region should have been reallocated.
331    SymbolRef FailedReallocSymbol;
332
333    bool IsLeak;
334
335  public:
336    MallocBugVisitor(SymbolRef S, bool isLeak = false)
337       : Sym(S), Mode(Normal), FailedReallocSymbol(0), IsLeak(isLeak) {}
338
339    virtual ~MallocBugVisitor() {}
340
341    void Profile(llvm::FoldingSetNodeID &ID) const {
342      static int X = 0;
343      ID.AddPointer(&X);
344      ID.AddPointer(Sym);
345    }
346
347    inline bool isAllocated(const RefState *S, const RefState *SPrev,
348                            const Stmt *Stmt) {
349      // Did not track -> allocated. Other state (released) -> allocated.
350      return (Stmt && (isa<CallExpr>(Stmt) || isa<CXXNewExpr>(Stmt)) &&
351              (S && S->isAllocated()) && (!SPrev || !SPrev->isAllocated()));
352    }
353
354    inline bool isReleased(const RefState *S, const RefState *SPrev,
355                           const Stmt *Stmt) {
356      // Did not track -> released. Other state (allocated) -> released.
357      return (Stmt && (isa<CallExpr>(Stmt) || isa<CXXDeleteExpr>(Stmt)) &&
358              (S && S->isReleased()) && (!SPrev || !SPrev->isReleased()));
359    }
360
361    inline bool isRelinquished(const RefState *S, const RefState *SPrev,
362                               const Stmt *Stmt) {
363      // Did not track -> relinquished. Other state (allocated) -> relinquished.
364      return (Stmt && (isa<CallExpr>(Stmt) || isa<ObjCMessageExpr>(Stmt) ||
365                                              isa<ObjCPropertyRefExpr>(Stmt)) &&
366              (S && S->isRelinquished()) &&
367              (!SPrev || !SPrev->isRelinquished()));
368    }
369
370    inline bool isReallocFailedCheck(const RefState *S, const RefState *SPrev,
371                                     const Stmt *Stmt) {
372      // If the expression is not a call, and the state change is
373      // released -> allocated, it must be the realloc return value
374      // check. If we have to handle more cases here, it might be cleaner just
375      // to track this extra bit in the state itself.
376      return ((!Stmt || !isa<CallExpr>(Stmt)) &&
377              (S && S->isAllocated()) && (SPrev && !SPrev->isAllocated()));
378    }
379
380    PathDiagnosticPiece *VisitNode(const ExplodedNode *N,
381                                   const ExplodedNode *PrevN,
382                                   BugReporterContext &BRC,
383                                   BugReport &BR);
384
385    PathDiagnosticPiece* getEndPath(BugReporterContext &BRC,
386                                    const ExplodedNode *EndPathNode,
387                                    BugReport &BR) {
388      if (!IsLeak)
389        return 0;
390
391      PathDiagnosticLocation L =
392        PathDiagnosticLocation::createEndOfPath(EndPathNode,
393                                                BRC.getSourceManager());
394      // Do not add the statement itself as a range in case of leak.
395      return new PathDiagnosticEventPiece(L, BR.getDescription(), false);
396    }
397
398  private:
399    class StackHintGeneratorForReallocationFailed
400        : public StackHintGeneratorForSymbol {
401    public:
402      StackHintGeneratorForReallocationFailed(SymbolRef S, StringRef M)
403        : StackHintGeneratorForSymbol(S, M) {}
404
405      virtual std::string getMessageForArg(const Expr *ArgE, unsigned ArgIndex) {
406        // Printed parameters start at 1, not 0.
407        ++ArgIndex;
408
409        SmallString<200> buf;
410        llvm::raw_svector_ostream os(buf);
411
412        os << "Reallocation of " << ArgIndex << llvm::getOrdinalSuffix(ArgIndex)
413           << " parameter failed";
414
415        return os.str();
416      }
417
418      virtual std::string getMessageForReturn(const CallExpr *CallExpr) {
419        return "Reallocation of returned value failed";
420      }
421    };
422  };
423};
424} // end anonymous namespace
425
426REGISTER_MAP_WITH_PROGRAMSTATE(RegionState, SymbolRef, RefState)
427REGISTER_MAP_WITH_PROGRAMSTATE(ReallocPairs, SymbolRef, ReallocPair)
428
429// A map from the freed symbol to the symbol representing the return value of
430// the free function.
431REGISTER_MAP_WITH_PROGRAMSTATE(FreeReturnValue, SymbolRef, SymbolRef)
432
433namespace {
434class StopTrackingCallback : public SymbolVisitor {
435  ProgramStateRef state;
436public:
437  StopTrackingCallback(ProgramStateRef st) : state(st) {}
438  ProgramStateRef getState() const { return state; }
439
440  bool VisitSymbol(SymbolRef sym) {
441    state = state->remove<RegionState>(sym);
442    return true;
443  }
444};
445} // end anonymous namespace
446
447void MallocChecker::initIdentifierInfo(ASTContext &Ctx) const {
448  if (II_malloc)
449    return;
450  II_malloc = &Ctx.Idents.get("malloc");
451  II_free = &Ctx.Idents.get("free");
452  II_realloc = &Ctx.Idents.get("realloc");
453  II_reallocf = &Ctx.Idents.get("reallocf");
454  II_calloc = &Ctx.Idents.get("calloc");
455  II_valloc = &Ctx.Idents.get("valloc");
456  II_strdup = &Ctx.Idents.get("strdup");
457  II_strndup = &Ctx.Idents.get("strndup");
458}
459
460bool MallocChecker::isMemFunction(const FunctionDecl *FD, ASTContext &C) const {
461  if (isFreeFunction(FD, C))
462    return true;
463
464  if (isAllocationFunction(FD, C))
465    return true;
466
467  if (isStandardNewDelete(FD, C))
468    return true;
469
470  return false;
471}
472
473bool MallocChecker::isAllocationFunction(const FunctionDecl *FD,
474                                         ASTContext &C) const {
475  if (!FD)
476    return false;
477
478  if (FD->getKind() == Decl::Function) {
479    IdentifierInfo *FunI = FD->getIdentifier();
480    initIdentifierInfo(C);
481
482    if (FunI == II_malloc || FunI == II_realloc ||
483        FunI == II_reallocf || FunI == II_calloc || FunI == II_valloc ||
484        FunI == II_strdup || FunI == II_strndup)
485      return true;
486  }
487
488  if (Filter.CMallocOptimistic && FD->hasAttrs())
489    for (specific_attr_iterator<OwnershipAttr>
490           i = FD->specific_attr_begin<OwnershipAttr>(),
491           e = FD->specific_attr_end<OwnershipAttr>();
492           i != e; ++i)
493      if ((*i)->getOwnKind() == OwnershipAttr::Returns)
494        return true;
495  return false;
496}
497
498bool MallocChecker::isFreeFunction(const FunctionDecl *FD, ASTContext &C) const {
499  if (!FD)
500    return false;
501
502  if (FD->getKind() == Decl::Function) {
503    IdentifierInfo *FunI = FD->getIdentifier();
504    initIdentifierInfo(C);
505
506    if (FunI == II_free || FunI == II_realloc || FunI == II_reallocf)
507      return true;
508  }
509
510  if (Filter.CMallocOptimistic && FD->hasAttrs())
511    for (specific_attr_iterator<OwnershipAttr>
512           i = FD->specific_attr_begin<OwnershipAttr>(),
513           e = FD->specific_attr_end<OwnershipAttr>();
514           i != e; ++i)
515      if ((*i)->getOwnKind() == OwnershipAttr::Takes ||
516          (*i)->getOwnKind() == OwnershipAttr::Holds)
517        return true;
518  return false;
519}
520
521// Tells if the callee is one of the following:
522// 1) A global non-placement new/delete operator function.
523// 2) A global placement operator function with the single placement argument
524//    of type std::nothrow_t.
525bool MallocChecker::isStandardNewDelete(const FunctionDecl *FD,
526                                        ASTContext &C) const {
527  if (!FD)
528    return false;
529
530  OverloadedOperatorKind Kind = FD->getOverloadedOperator();
531  if (Kind != OO_New && Kind != OO_Array_New &&
532      Kind != OO_Delete && Kind != OO_Array_Delete)
533    return false;
534
535  // Skip all operator new/delete methods.
536  if (isa<CXXMethodDecl>(FD))
537    return false;
538
539  // Return true if tested operator is a standard placement nothrow operator.
540  if (FD->getNumParams() == 2) {
541    QualType T = FD->getParamDecl(1)->getType();
542    if (const IdentifierInfo *II = T.getBaseTypeIdentifier())
543      return II->getName().equals("nothrow_t");
544  }
545
546  // Skip placement operators.
547  if (FD->getNumParams() != 1 || FD->isVariadic())
548    return false;
549
550  // One of the standard new/new[]/delete/delete[] non-placement operators.
551  return true;
552}
553
554void MallocChecker::checkPostStmt(const CallExpr *CE, CheckerContext &C) const {
555  if (C.wasInlined)
556    return;
557
558  const FunctionDecl *FD = C.getCalleeDecl(CE);
559  if (!FD)
560    return;
561
562  ProgramStateRef State = C.getState();
563  bool ReleasedAllocatedMemory = false;
564
565  if (FD->getKind() == Decl::Function) {
566    initIdentifierInfo(C.getASTContext());
567    IdentifierInfo *FunI = FD->getIdentifier();
568
569    if (FunI == II_malloc || FunI == II_valloc) {
570      if (CE->getNumArgs() < 1)
571        return;
572      State = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(), State);
573    } else if (FunI == II_realloc) {
574      State = ReallocMem(C, CE, false);
575    } else if (FunI == II_reallocf) {
576      State = ReallocMem(C, CE, true);
577    } else if (FunI == II_calloc) {
578      State = CallocMem(C, CE);
579    } else if (FunI == II_free) {
580      State = FreeMemAux(C, CE, State, 0, false, ReleasedAllocatedMemory);
581    } else if (FunI == II_strdup) {
582      State = MallocUpdateRefState(C, CE, State);
583    } else if (FunI == II_strndup) {
584      State = MallocUpdateRefState(C, CE, State);
585    }
586    else if (isStandardNewDelete(FD, C.getASTContext())) {
587      // Process direct calls to operator new/new[]/delete/delete[] functions
588      // as distinct from new/new[]/delete/delete[] expressions that are
589      // processed by the checkPostStmt callbacks for CXXNewExpr and
590      // CXXDeleteExpr.
591      OverloadedOperatorKind K = FD->getOverloadedOperator();
592      if (K == OO_New)
593        State = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(), State,
594                             AF_CXXNew);
595      else if (K == OO_Array_New)
596        State = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(), State,
597                             AF_CXXNewArray);
598      else if (K == OO_Delete || K == OO_Array_Delete)
599        State = FreeMemAux(C, CE, State, 0, false, ReleasedAllocatedMemory);
600      else
601        llvm_unreachable("not a new/delete operator");
602    }
603  }
604
605  if (Filter.CMallocOptimistic || Filter.CMismatchedDeallocatorChecker) {
606    // Check all the attributes, if there are any.
607    // There can be multiple of these attributes.
608    if (FD->hasAttrs())
609      for (specific_attr_iterator<OwnershipAttr>
610          i = FD->specific_attr_begin<OwnershipAttr>(),
611          e = FD->specific_attr_end<OwnershipAttr>();
612          i != e; ++i) {
613        switch ((*i)->getOwnKind()) {
614        case OwnershipAttr::Returns:
615          State = MallocMemReturnsAttr(C, CE, *i);
616          break;
617        case OwnershipAttr::Takes:
618        case OwnershipAttr::Holds:
619          State = FreeMemAttr(C, CE, *i);
620          break;
621        }
622      }
623  }
624  C.addTransition(State);
625}
626
627void MallocChecker::checkPostStmt(const CXXNewExpr *NE,
628                                  CheckerContext &C) const {
629
630  if (NE->getNumPlacementArgs())
631    for (CXXNewExpr::const_arg_iterator I = NE->placement_arg_begin(),
632         E = NE->placement_arg_end(); I != E; ++I)
633      if (SymbolRef Sym = C.getSVal(*I).getAsSymbol())
634        checkUseAfterFree(Sym, C, *I);
635
636  if (!isStandardNewDelete(NE->getOperatorNew(), C.getASTContext()))
637    return;
638
639  ProgramStateRef State = C.getState();
640  // The return value from operator new is bound to a specified initialization
641  // value (if any) and we don't want to loose this value. So we call
642  // MallocUpdateRefState() instead of MallocMemAux() which breakes the
643  // existing binding.
644  State = MallocUpdateRefState(C, NE, State, NE->isArray() ? AF_CXXNewArray
645                                                           : AF_CXXNew);
646  C.addTransition(State);
647}
648
649void MallocChecker::checkPreStmt(const CXXDeleteExpr *DE,
650                                 CheckerContext &C) const {
651
652  if (!Filter.CNewDeleteChecker)
653    if (SymbolRef Sym = C.getSVal(DE->getArgument()).getAsSymbol())
654      checkUseAfterFree(Sym, C, DE->getArgument());
655
656  if (!isStandardNewDelete(DE->getOperatorDelete(), C.getASTContext()))
657    return;
658
659  ProgramStateRef State = C.getState();
660  bool ReleasedAllocated;
661  State = FreeMemAux(C, DE->getArgument(), DE, State,
662                     /*Hold*/false, ReleasedAllocated);
663
664  C.addTransition(State);
665}
666
667static bool isKnownDeallocObjCMethodName(const ObjCMethodCall &Call) {
668  // If the first selector piece is one of the names below, assume that the
669  // object takes ownership of the memory, promising to eventually deallocate it
670  // with free().
671  // Ex:  [NSData dataWithBytesNoCopy:bytes length:10];
672  // (...unless a 'freeWhenDone' parameter is false, but that's checked later.)
673  StringRef FirstSlot = Call.getSelector().getNameForSlot(0);
674  if (FirstSlot == "dataWithBytesNoCopy" ||
675      FirstSlot == "initWithBytesNoCopy" ||
676      FirstSlot == "initWithCharactersNoCopy")
677    return true;
678
679  return false;
680}
681
682static Optional<bool> getFreeWhenDoneArg(const ObjCMethodCall &Call) {
683  Selector S = Call.getSelector();
684
685  // FIXME: We should not rely on fully-constrained symbols being folded.
686  for (unsigned i = 1; i < S.getNumArgs(); ++i)
687    if (S.getNameForSlot(i).equals("freeWhenDone"))
688      return !Call.getArgSVal(i).isZeroConstant();
689
690  return None;
691}
692
693void MallocChecker::checkPostObjCMessage(const ObjCMethodCall &Call,
694                                         CheckerContext &C) const {
695  if (C.wasInlined)
696    return;
697
698  if (!isKnownDeallocObjCMethodName(Call))
699    return;
700
701  if (Optional<bool> FreeWhenDone = getFreeWhenDoneArg(Call))
702    if (!*FreeWhenDone)
703      return;
704
705  bool ReleasedAllocatedMemory;
706  ProgramStateRef State = FreeMemAux(C, Call.getArgExpr(0),
707                                     Call.getOriginExpr(), C.getState(),
708                                     /*Hold=*/true, ReleasedAllocatedMemory,
709                                     /*RetNullOnFailure=*/true);
710
711  C.addTransition(State);
712}
713
714ProgramStateRef MallocChecker::MallocMemReturnsAttr(CheckerContext &C,
715                                                    const CallExpr *CE,
716                                                    const OwnershipAttr* Att) {
717  if (Att->getModule() != "malloc")
718    return 0;
719
720  OwnershipAttr::args_iterator I = Att->args_begin(), E = Att->args_end();
721  if (I != E) {
722    return MallocMemAux(C, CE, CE->getArg(*I), UndefinedVal(), C.getState());
723  }
724  return MallocMemAux(C, CE, UnknownVal(), UndefinedVal(), C.getState());
725}
726
727ProgramStateRef MallocChecker::MallocMemAux(CheckerContext &C,
728                                           const CallExpr *CE,
729                                           SVal Size, SVal Init,
730                                           ProgramStateRef State,
731                                           AllocationFamily Family) {
732
733  // Bind the return value to the symbolic value from the heap region.
734  // TODO: We could rewrite post visit to eval call; 'malloc' does not have
735  // side effects other than what we model here.
736  unsigned Count = C.blockCount();
737  SValBuilder &svalBuilder = C.getSValBuilder();
738  const LocationContext *LCtx = C.getPredecessor()->getLocationContext();
739  DefinedSVal RetVal = svalBuilder.getConjuredHeapSymbolVal(CE, LCtx, Count)
740      .castAs<DefinedSVal>();
741  State = State->BindExpr(CE, C.getLocationContext(), RetVal);
742
743  // We expect the malloc functions to return a pointer.
744  if (!RetVal.getAs<Loc>())
745    return 0;
746
747  // Fill the region with the initialization value.
748  State = State->bindDefault(RetVal, Init);
749
750  // Set the region's extent equal to the Size parameter.
751  const SymbolicRegion *R =
752      dyn_cast_or_null<SymbolicRegion>(RetVal.getAsRegion());
753  if (!R)
754    return 0;
755  if (Optional<DefinedOrUnknownSVal> DefinedSize =
756          Size.getAs<DefinedOrUnknownSVal>()) {
757    SValBuilder &svalBuilder = C.getSValBuilder();
758    DefinedOrUnknownSVal Extent = R->getExtent(svalBuilder);
759    DefinedOrUnknownSVal extentMatchesSize =
760        svalBuilder.evalEQ(State, Extent, *DefinedSize);
761
762    State = State->assume(extentMatchesSize, true);
763    assert(State);
764  }
765
766  return MallocUpdateRefState(C, CE, State, Family);
767}
768
769ProgramStateRef MallocChecker::MallocUpdateRefState(CheckerContext &C,
770                                                    const Expr *E,
771                                                    ProgramStateRef State,
772                                                    AllocationFamily Family) {
773  // Get the return value.
774  SVal retVal = State->getSVal(E, C.getLocationContext());
775
776  // We expect the malloc functions to return a pointer.
777  if (!retVal.getAs<Loc>())
778    return 0;
779
780  SymbolRef Sym = retVal.getAsLocSymbol();
781  assert(Sym);
782
783  // Set the symbol's state to Allocated.
784  return State->set<RegionState>(Sym, RefState::getAllocated(Family, E));
785}
786
787ProgramStateRef MallocChecker::FreeMemAttr(CheckerContext &C,
788                                           const CallExpr *CE,
789                                           const OwnershipAttr* Att) const {
790  if (Att->getModule() != "malloc")
791    return 0;
792
793  ProgramStateRef State = C.getState();
794  bool ReleasedAllocated = false;
795
796  for (OwnershipAttr::args_iterator I = Att->args_begin(), E = Att->args_end();
797       I != E; ++I) {
798    ProgramStateRef StateI = FreeMemAux(C, CE, State, *I,
799                               Att->getOwnKind() == OwnershipAttr::Holds,
800                               ReleasedAllocated);
801    if (StateI)
802      State = StateI;
803  }
804  return State;
805}
806
807ProgramStateRef MallocChecker::FreeMemAux(CheckerContext &C,
808                                          const CallExpr *CE,
809                                          ProgramStateRef state,
810                                          unsigned Num,
811                                          bool Hold,
812                                          bool &ReleasedAllocated,
813                                          bool ReturnsNullOnFailure) const {
814  if (CE->getNumArgs() < (Num + 1))
815    return 0;
816
817  return FreeMemAux(C, CE->getArg(Num), CE, state, Hold,
818                    ReleasedAllocated, ReturnsNullOnFailure);
819}
820
821/// Checks if the previous call to free on the given symbol failed - if free
822/// failed, returns true. Also, returns the corresponding return value symbol.
823static bool didPreviousFreeFail(ProgramStateRef State,
824                                SymbolRef Sym, SymbolRef &RetStatusSymbol) {
825  const SymbolRef *Ret = State->get<FreeReturnValue>(Sym);
826  if (Ret) {
827    assert(*Ret && "We should not store the null return symbol");
828    ConstraintManager &CMgr = State->getConstraintManager();
829    ConditionTruthVal FreeFailed = CMgr.isNull(State, *Ret);
830    RetStatusSymbol = *Ret;
831    return FreeFailed.isConstrainedTrue();
832  }
833  return false;
834}
835
836AllocationFamily MallocChecker::getAllocationFamily(CheckerContext &C,
837                                                    const Stmt *S) const {
838  if (!S)
839    return AF_None;
840
841  if (const CallExpr *CE = dyn_cast<CallExpr>(S)) {
842    const FunctionDecl *FD = C.getCalleeDecl(CE);
843
844    if (!FD)
845      FD = dyn_cast<FunctionDecl>(CE->getCalleeDecl());
846
847    ASTContext &Ctx = C.getASTContext();
848
849    if (isAllocationFunction(FD, Ctx) || isFreeFunction(FD, Ctx))
850      return AF_Malloc;
851
852    if (isStandardNewDelete(FD, Ctx)) {
853      OverloadedOperatorKind Kind = FD->getOverloadedOperator();
854      if (Kind == OO_New || Kind == OO_Delete)
855        return AF_CXXNew;
856      else if (Kind == OO_Array_New || Kind == OO_Array_Delete)
857        return AF_CXXNewArray;
858    }
859
860    return AF_None;
861  }
862
863  if (const CXXNewExpr *NE = dyn_cast<CXXNewExpr>(S))
864    return NE->isArray() ? AF_CXXNewArray : AF_CXXNew;
865
866  if (const CXXDeleteExpr *DE = dyn_cast<CXXDeleteExpr>(S))
867    return DE->isArrayForm() ? AF_CXXNewArray : AF_CXXNew;
868
869  if (isa<ObjCMessageExpr>(S))
870    return AF_Malloc;
871
872  return AF_None;
873}
874
875bool MallocChecker::printAllocDeallocName(raw_ostream &os, CheckerContext &C,
876                                          const Expr *E) const {
877  if (const CallExpr *CE = dyn_cast<CallExpr>(E)) {
878    // FIXME: This doesn't handle indirect calls.
879    const FunctionDecl *FD = CE->getDirectCallee();
880    if (!FD)
881      return false;
882
883    os << *FD;
884    if (!FD->isOverloadedOperator())
885      os << "()";
886    return true;
887  }
888
889  if (const ObjCMessageExpr *Msg = dyn_cast<ObjCMessageExpr>(E)) {
890    if (Msg->isInstanceMessage())
891      os << "-";
892    else
893      os << "+";
894    os << Msg->getSelector().getAsString();
895    return true;
896  }
897
898  if (const CXXNewExpr *NE = dyn_cast<CXXNewExpr>(E)) {
899    os << "'"
900       << getOperatorSpelling(NE->getOperatorNew()->getOverloadedOperator())
901       << "'";
902    return true;
903  }
904
905  if (const CXXDeleteExpr *DE = dyn_cast<CXXDeleteExpr>(E)) {
906    os << "'"
907       << getOperatorSpelling(DE->getOperatorDelete()->getOverloadedOperator())
908       << "'";
909    return true;
910  }
911
912  return false;
913}
914
915void MallocChecker::printExpectedAllocName(raw_ostream &os, CheckerContext &C,
916                                           const Expr *E) const {
917  AllocationFamily Family = getAllocationFamily(C, E);
918
919  switch(Family) {
920    case AF_Malloc: os << "malloc()"; return;
921    case AF_CXXNew: os << "'new'"; return;
922    case AF_CXXNewArray: os << "'new[]'"; return;
923    case AF_None: llvm_unreachable("not a deallocation expression");
924  }
925}
926
927void MallocChecker::printExpectedDeallocName(raw_ostream &os,
928                                             AllocationFamily Family) const {
929  switch(Family) {
930    case AF_Malloc: os << "free()"; return;
931    case AF_CXXNew: os << "'delete'"; return;
932    case AF_CXXNewArray: os << "'delete[]'"; return;
933    case AF_None: llvm_unreachable("suspicious AF_None argument");
934  }
935}
936
937ProgramStateRef MallocChecker::FreeMemAux(CheckerContext &C,
938                                          const Expr *ArgExpr,
939                                          const Expr *ParentExpr,
940                                          ProgramStateRef State,
941                                          bool Hold,
942                                          bool &ReleasedAllocated,
943                                          bool ReturnsNullOnFailure) const {
944
945  SVal ArgVal = State->getSVal(ArgExpr, C.getLocationContext());
946  if (!ArgVal.getAs<DefinedOrUnknownSVal>())
947    return 0;
948  DefinedOrUnknownSVal location = ArgVal.castAs<DefinedOrUnknownSVal>();
949
950  // Check for null dereferences.
951  if (!location.getAs<Loc>())
952    return 0;
953
954  // The explicit NULL case, no operation is performed.
955  ProgramStateRef notNullState, nullState;
956  llvm::tie(notNullState, nullState) = State->assume(location);
957  if (nullState && !notNullState)
958    return 0;
959
960  // Unknown values could easily be okay
961  // Undefined values are handled elsewhere
962  if (ArgVal.isUnknownOrUndef())
963    return 0;
964
965  const MemRegion *R = ArgVal.getAsRegion();
966
967  // Nonlocs can't be freed, of course.
968  // Non-region locations (labels and fixed addresses) also shouldn't be freed.
969  if (!R) {
970    ReportBadFree(C, ArgVal, ArgExpr->getSourceRange(), ParentExpr);
971    return 0;
972  }
973
974  R = R->StripCasts();
975
976  // Blocks might show up as heap data, but should not be free()d
977  if (isa<BlockDataRegion>(R)) {
978    ReportBadFree(C, ArgVal, ArgExpr->getSourceRange(), ParentExpr);
979    return 0;
980  }
981
982  const MemSpaceRegion *MS = R->getMemorySpace();
983
984  // Parameters, locals, statics, globals, and memory returned by alloca()
985  // shouldn't be freed.
986  if (!(isa<UnknownSpaceRegion>(MS) || isa<HeapSpaceRegion>(MS))) {
987    // FIXME: at the time this code was written, malloc() regions were
988    // represented by conjured symbols, which are all in UnknownSpaceRegion.
989    // This means that there isn't actually anything from HeapSpaceRegion
990    // that should be freed, even though we allow it here.
991    // Of course, free() can work on memory allocated outside the current
992    // function, so UnknownSpaceRegion is always a possibility.
993    // False negatives are better than false positives.
994
995    ReportBadFree(C, ArgVal, ArgExpr->getSourceRange(), ParentExpr);
996    return 0;
997  }
998
999  const SymbolicRegion *SrBase = dyn_cast<SymbolicRegion>(R->getBaseRegion());
1000  // Various cases could lead to non-symbol values here.
1001  // For now, ignore them.
1002  if (!SrBase)
1003    return 0;
1004
1005  SymbolRef SymBase = SrBase->getSymbol();
1006  const RefState *RsBase = State->get<RegionState>(SymBase);
1007  SymbolRef PreviousRetStatusSymbol = 0;
1008
1009  if (RsBase) {
1010
1011    bool DeallocMatchesAlloc =
1012      RsBase->getAllocationFamily() == AF_None ||
1013      RsBase->getAllocationFamily() == getAllocationFamily(C, ParentExpr);
1014
1015    // Check if an expected deallocation function matches the real one.
1016    if (!DeallocMatchesAlloc && RsBase->isAllocated()) {
1017      ReportMismatchedDealloc(C, ArgExpr->getSourceRange(), ParentExpr, RsBase,
1018                              SymBase);
1019      return 0;
1020    }
1021
1022    // Check double free.
1023    if (DeallocMatchesAlloc &&
1024        (RsBase->isReleased() || RsBase->isRelinquished()) &&
1025        !didPreviousFreeFail(State, SymBase, PreviousRetStatusSymbol)) {
1026      ReportDoubleFree(C, ParentExpr->getSourceRange(), RsBase->isReleased(),
1027                       SymBase, PreviousRetStatusSymbol);
1028      return 0;
1029    }
1030
1031    // Check if the memory location being freed is the actual location
1032    // allocated, or an offset.
1033    RegionOffset Offset = R->getAsOffset();
1034    if (RsBase->isAllocated() &&
1035        Offset.isValid() &&
1036        !Offset.hasSymbolicOffset() &&
1037        Offset.getOffset() != 0) {
1038      const Expr *AllocExpr = cast<Expr>(RsBase->getStmt());
1039      ReportOffsetFree(C, ArgVal, ArgExpr->getSourceRange(), ParentExpr,
1040                       AllocExpr);
1041      return 0;
1042    }
1043  }
1044
1045  ReleasedAllocated = (RsBase != 0);
1046
1047  // Clean out the info on previous call to free return info.
1048  State = State->remove<FreeReturnValue>(SymBase);
1049
1050  // Keep track of the return value. If it is NULL, we will know that free
1051  // failed.
1052  if (ReturnsNullOnFailure) {
1053    SVal RetVal = C.getSVal(ParentExpr);
1054    SymbolRef RetStatusSymbol = RetVal.getAsSymbol();
1055    if (RetStatusSymbol) {
1056      C.getSymbolManager().addSymbolDependency(SymBase, RetStatusSymbol);
1057      State = State->set<FreeReturnValue>(SymBase, RetStatusSymbol);
1058    }
1059  }
1060
1061  AllocationFamily Family = RsBase ? RsBase->getAllocationFamily()
1062                                   : getAllocationFamily(C, ParentExpr);
1063  // Normal free.
1064  if (Hold)
1065    return State->set<RegionState>(SymBase,
1066                                   RefState::getRelinquished(Family,
1067                                                             ParentExpr));
1068
1069  return State->set<RegionState>(SymBase,
1070                                 RefState::getReleased(Family, ParentExpr));
1071}
1072
1073bool MallocChecker::isTrackedFamily(AllocationFamily Family) const {
1074  switch (Family) {
1075  case AF_Malloc: {
1076    if (!Filter.CMallocOptimistic && !Filter.CMallocPessimistic)
1077      return false;
1078    return true;
1079  }
1080  case AF_CXXNew:
1081  case AF_CXXNewArray: {
1082    if (!Filter.CNewDeleteChecker)
1083      return false;
1084    return true;
1085  }
1086  case AF_None: {
1087    llvm_unreachable("no family");
1088  }
1089  }
1090  llvm_unreachable("unhandled family");
1091}
1092
1093bool MallocChecker::isTrackedFamily(CheckerContext &C,
1094                                    const Stmt *AllocDeallocStmt) const {
1095  return isTrackedFamily(getAllocationFamily(C, AllocDeallocStmt));
1096}
1097
1098bool MallocChecker::isTrackedFamily(CheckerContext &C, SymbolRef Sym) const {
1099
1100  const RefState *RS = C.getState()->get<RegionState>(Sym);
1101  assert(RS);
1102  return isTrackedFamily(RS->getAllocationFamily());
1103}
1104
1105bool MallocChecker::SummarizeValue(raw_ostream &os, SVal V) {
1106  if (Optional<nonloc::ConcreteInt> IntVal = V.getAs<nonloc::ConcreteInt>())
1107    os << "an integer (" << IntVal->getValue() << ")";
1108  else if (Optional<loc::ConcreteInt> ConstAddr = V.getAs<loc::ConcreteInt>())
1109    os << "a constant address (" << ConstAddr->getValue() << ")";
1110  else if (Optional<loc::GotoLabel> Label = V.getAs<loc::GotoLabel>())
1111    os << "the address of the label '" << Label->getLabel()->getName() << "'";
1112  else
1113    return false;
1114
1115  return true;
1116}
1117
1118bool MallocChecker::SummarizeRegion(raw_ostream &os,
1119                                    const MemRegion *MR) {
1120  switch (MR->getKind()) {
1121  case MemRegion::FunctionTextRegionKind: {
1122    const NamedDecl *FD = cast<FunctionTextRegion>(MR)->getDecl();
1123    if (FD)
1124      os << "the address of the function '" << *FD << '\'';
1125    else
1126      os << "the address of a function";
1127    return true;
1128  }
1129  case MemRegion::BlockTextRegionKind:
1130    os << "block text";
1131    return true;
1132  case MemRegion::BlockDataRegionKind:
1133    // FIXME: where the block came from?
1134    os << "a block";
1135    return true;
1136  default: {
1137    const MemSpaceRegion *MS = MR->getMemorySpace();
1138
1139    if (isa<StackLocalsSpaceRegion>(MS)) {
1140      const VarRegion *VR = dyn_cast<VarRegion>(MR);
1141      const VarDecl *VD;
1142      if (VR)
1143        VD = VR->getDecl();
1144      else
1145        VD = NULL;
1146
1147      if (VD)
1148        os << "the address of the local variable '" << VD->getName() << "'";
1149      else
1150        os << "the address of a local stack variable";
1151      return true;
1152    }
1153
1154    if (isa<StackArgumentsSpaceRegion>(MS)) {
1155      const VarRegion *VR = dyn_cast<VarRegion>(MR);
1156      const VarDecl *VD;
1157      if (VR)
1158        VD = VR->getDecl();
1159      else
1160        VD = NULL;
1161
1162      if (VD)
1163        os << "the address of the parameter '" << VD->getName() << "'";
1164      else
1165        os << "the address of a parameter";
1166      return true;
1167    }
1168
1169    if (isa<GlobalsSpaceRegion>(MS)) {
1170      const VarRegion *VR = dyn_cast<VarRegion>(MR);
1171      const VarDecl *VD;
1172      if (VR)
1173        VD = VR->getDecl();
1174      else
1175        VD = NULL;
1176
1177      if (VD) {
1178        if (VD->isStaticLocal())
1179          os << "the address of the static variable '" << VD->getName() << "'";
1180        else
1181          os << "the address of the global variable '" << VD->getName() << "'";
1182      } else
1183        os << "the address of a global variable";
1184      return true;
1185    }
1186
1187    return false;
1188  }
1189  }
1190}
1191
1192void MallocChecker::ReportBadFree(CheckerContext &C, SVal ArgVal,
1193                                  SourceRange Range,
1194                                  const Expr *DeallocExpr) const {
1195
1196  if (!Filter.CMallocOptimistic && !Filter.CMallocPessimistic &&
1197      !Filter.CNewDeleteChecker)
1198    return;
1199
1200  if (!isTrackedFamily(C, DeallocExpr))
1201    return;
1202
1203  if (ExplodedNode *N = C.generateSink()) {
1204    if (!BT_BadFree)
1205      BT_BadFree.reset(new BugType("Bad free", "Memory Error"));
1206
1207    SmallString<100> buf;
1208    llvm::raw_svector_ostream os(buf);
1209
1210    const MemRegion *MR = ArgVal.getAsRegion();
1211    while (const ElementRegion *ER = dyn_cast_or_null<ElementRegion>(MR))
1212      MR = ER->getSuperRegion();
1213
1214    if (MR && isa<AllocaRegion>(MR))
1215      os << "Memory allocated by alloca() should not be deallocated";
1216    else {
1217      os << "Argument to ";
1218      if (!printAllocDeallocName(os, C, DeallocExpr))
1219        os << "deallocator";
1220
1221      os << " is ";
1222      bool Summarized = MR ? SummarizeRegion(os, MR)
1223                           : SummarizeValue(os, ArgVal);
1224      if (Summarized)
1225        os << ", which is not memory allocated by ";
1226      else
1227        os << "not memory allocated by ";
1228
1229      printExpectedAllocName(os, C, DeallocExpr);
1230    }
1231
1232    BugReport *R = new BugReport(*BT_BadFree, os.str(), N);
1233    R->markInteresting(MR);
1234    R->addRange(Range);
1235    C.emitReport(R);
1236  }
1237}
1238
1239void MallocChecker::ReportMismatchedDealloc(CheckerContext &C,
1240                                            SourceRange Range,
1241                                            const Expr *DeallocExpr,
1242                                            const RefState *RS,
1243                                            SymbolRef Sym) const {
1244
1245  if (!Filter.CMismatchedDeallocatorChecker)
1246    return;
1247
1248  if (ExplodedNode *N = C.generateSink()) {
1249    if (!BT_MismatchedDealloc)
1250      BT_MismatchedDealloc.reset(new BugType("Bad deallocator",
1251                                             "Memory Error"));
1252
1253    SmallString<100> buf;
1254    llvm::raw_svector_ostream os(buf);
1255
1256    const Expr *AllocExpr = cast<Expr>(RS->getStmt());
1257    SmallString<20> AllocBuf;
1258    llvm::raw_svector_ostream AllocOs(AllocBuf);
1259    SmallString<20> DeallocBuf;
1260    llvm::raw_svector_ostream DeallocOs(DeallocBuf);
1261
1262    os << "Memory";
1263    if (printAllocDeallocName(AllocOs, C, AllocExpr))
1264      os << " allocated by " << AllocOs.str();
1265
1266    os << " should be deallocated by ";
1267      printExpectedDeallocName(os, RS->getAllocationFamily());
1268
1269    if (printAllocDeallocName(DeallocOs, C, DeallocExpr))
1270      os << ", not " << DeallocOs.str();
1271
1272    BugReport *R = new BugReport(*BT_MismatchedDealloc, os.str(), N);
1273    R->markInteresting(Sym);
1274    R->addRange(Range);
1275    R->addVisitor(new MallocBugVisitor(Sym));
1276    C.emitReport(R);
1277  }
1278}
1279
1280void MallocChecker::ReportOffsetFree(CheckerContext &C, SVal ArgVal,
1281                                     SourceRange Range, const Expr *DeallocExpr,
1282                                     const Expr *AllocExpr) const {
1283
1284  if (!Filter.CMallocOptimistic && !Filter.CMallocPessimistic &&
1285      !Filter.CNewDeleteChecker)
1286    return;
1287
1288  if (!isTrackedFamily(C, AllocExpr))
1289    return;
1290
1291  ExplodedNode *N = C.generateSink();
1292  if (N == NULL)
1293    return;
1294
1295  if (!BT_OffsetFree)
1296    BT_OffsetFree.reset(new BugType("Offset free", "Memory Error"));
1297
1298  SmallString<100> buf;
1299  llvm::raw_svector_ostream os(buf);
1300  SmallString<20> AllocNameBuf;
1301  llvm::raw_svector_ostream AllocNameOs(AllocNameBuf);
1302
1303  const MemRegion *MR = ArgVal.getAsRegion();
1304  assert(MR && "Only MemRegion based symbols can have offset free errors");
1305
1306  RegionOffset Offset = MR->getAsOffset();
1307  assert((Offset.isValid() &&
1308          !Offset.hasSymbolicOffset() &&
1309          Offset.getOffset() != 0) &&
1310         "Only symbols with a valid offset can have offset free errors");
1311
1312  int offsetBytes = Offset.getOffset() / C.getASTContext().getCharWidth();
1313
1314  os << "Argument to ";
1315  if (!printAllocDeallocName(os, C, DeallocExpr))
1316    os << "deallocator";
1317  os << " is offset by "
1318     << offsetBytes
1319     << " "
1320     << ((abs(offsetBytes) > 1) ? "bytes" : "byte")
1321     << " from the start of ";
1322  if (AllocExpr && printAllocDeallocName(AllocNameOs, C, AllocExpr))
1323    os << "memory allocated by " << AllocNameOs.str();
1324  else
1325    os << "allocated memory";
1326
1327  BugReport *R = new BugReport(*BT_OffsetFree, os.str(), N);
1328  R->markInteresting(MR->getBaseRegion());
1329  R->addRange(Range);
1330  C.emitReport(R);
1331}
1332
1333void MallocChecker::ReportUseAfterFree(CheckerContext &C, SourceRange Range,
1334                                       SymbolRef Sym) const {
1335
1336  if (!Filter.CMallocOptimistic && !Filter.CMallocPessimistic &&
1337      !Filter.CNewDeleteChecker)
1338    return;
1339
1340  if (!isTrackedFamily(C, Sym))
1341    return;
1342
1343  if (ExplodedNode *N = C.generateSink()) {
1344    if (!BT_UseFree)
1345      BT_UseFree.reset(new BugType("Use-after-free", "Memory Error"));
1346
1347    BugReport *R = new BugReport(*BT_UseFree,
1348                                 "Use of memory after it is freed", N);
1349
1350    R->markInteresting(Sym);
1351    R->addRange(Range);
1352    R->addVisitor(new MallocBugVisitor(Sym));
1353    C.emitReport(R);
1354  }
1355}
1356
1357void MallocChecker::ReportDoubleFree(CheckerContext &C, SourceRange Range,
1358                                     bool Released, SymbolRef Sym,
1359                                     SymbolRef PrevSym) const {
1360
1361  if (!Filter.CMallocOptimistic && !Filter.CMallocPessimistic &&
1362      !Filter.CNewDeleteChecker)
1363    return;
1364
1365  if (!isTrackedFamily(C, Sym))
1366    return;
1367
1368  if (ExplodedNode *N = C.generateSink()) {
1369    if (!BT_DoubleFree)
1370      BT_DoubleFree.reset(new BugType("Double free", "Memory Error"));
1371
1372    BugReport *R = new BugReport(*BT_DoubleFree,
1373      (Released ? "Attempt to free released memory"
1374                : "Attempt to free non-owned memory"),
1375      N);
1376    R->addRange(Range);
1377    R->markInteresting(Sym);
1378    if (PrevSym)
1379      R->markInteresting(PrevSym);
1380    R->addVisitor(new MallocBugVisitor(Sym));
1381    C.emitReport(R);
1382  }
1383}
1384
1385ProgramStateRef MallocChecker::ReallocMem(CheckerContext &C,
1386                                          const CallExpr *CE,
1387                                          bool FreesOnFail) const {
1388  if (CE->getNumArgs() < 2)
1389    return 0;
1390
1391  ProgramStateRef state = C.getState();
1392  const Expr *arg0Expr = CE->getArg(0);
1393  const LocationContext *LCtx = C.getLocationContext();
1394  SVal Arg0Val = state->getSVal(arg0Expr, LCtx);
1395  if (!Arg0Val.getAs<DefinedOrUnknownSVal>())
1396    return 0;
1397  DefinedOrUnknownSVal arg0Val = Arg0Val.castAs<DefinedOrUnknownSVal>();
1398
1399  SValBuilder &svalBuilder = C.getSValBuilder();
1400
1401  DefinedOrUnknownSVal PtrEQ =
1402    svalBuilder.evalEQ(state, arg0Val, svalBuilder.makeNull());
1403
1404  // Get the size argument. If there is no size arg then give up.
1405  const Expr *Arg1 = CE->getArg(1);
1406  if (!Arg1)
1407    return 0;
1408
1409  // Get the value of the size argument.
1410  SVal Arg1ValG = state->getSVal(Arg1, LCtx);
1411  if (!Arg1ValG.getAs<DefinedOrUnknownSVal>())
1412    return 0;
1413  DefinedOrUnknownSVal Arg1Val = Arg1ValG.castAs<DefinedOrUnknownSVal>();
1414
1415  // Compare the size argument to 0.
1416  DefinedOrUnknownSVal SizeZero =
1417    svalBuilder.evalEQ(state, Arg1Val,
1418                       svalBuilder.makeIntValWithPtrWidth(0, false));
1419
1420  ProgramStateRef StatePtrIsNull, StatePtrNotNull;
1421  llvm::tie(StatePtrIsNull, StatePtrNotNull) = state->assume(PtrEQ);
1422  ProgramStateRef StateSizeIsZero, StateSizeNotZero;
1423  llvm::tie(StateSizeIsZero, StateSizeNotZero) = state->assume(SizeZero);
1424  // We only assume exceptional states if they are definitely true; if the
1425  // state is under-constrained, assume regular realloc behavior.
1426  bool PrtIsNull = StatePtrIsNull && !StatePtrNotNull;
1427  bool SizeIsZero = StateSizeIsZero && !StateSizeNotZero;
1428
1429  // If the ptr is NULL and the size is not 0, the call is equivalent to
1430  // malloc(size).
1431  if ( PrtIsNull && !SizeIsZero) {
1432    ProgramStateRef stateMalloc = MallocMemAux(C, CE, CE->getArg(1),
1433                                               UndefinedVal(), StatePtrIsNull);
1434    return stateMalloc;
1435  }
1436
1437  if (PrtIsNull && SizeIsZero)
1438    return 0;
1439
1440  // Get the from and to pointer symbols as in toPtr = realloc(fromPtr, size).
1441  assert(!PrtIsNull);
1442  SymbolRef FromPtr = arg0Val.getAsSymbol();
1443  SVal RetVal = state->getSVal(CE, LCtx);
1444  SymbolRef ToPtr = RetVal.getAsSymbol();
1445  if (!FromPtr || !ToPtr)
1446    return 0;
1447
1448  bool ReleasedAllocated = false;
1449
1450  // If the size is 0, free the memory.
1451  if (SizeIsZero)
1452    if (ProgramStateRef stateFree = FreeMemAux(C, CE, StateSizeIsZero, 0,
1453                                               false, ReleasedAllocated)){
1454      // The semantics of the return value are:
1455      // If size was equal to 0, either NULL or a pointer suitable to be passed
1456      // to free() is returned. We just free the input pointer and do not add
1457      // any constrains on the output pointer.
1458      return stateFree;
1459    }
1460
1461  // Default behavior.
1462  if (ProgramStateRef stateFree =
1463        FreeMemAux(C, CE, state, 0, false, ReleasedAllocated)) {
1464
1465    ProgramStateRef stateRealloc = MallocMemAux(C, CE, CE->getArg(1),
1466                                                UnknownVal(), stateFree);
1467    if (!stateRealloc)
1468      return 0;
1469
1470    ReallocPairKind Kind = RPToBeFreedAfterFailure;
1471    if (FreesOnFail)
1472      Kind = RPIsFreeOnFailure;
1473    else if (!ReleasedAllocated)
1474      Kind = RPDoNotTrackAfterFailure;
1475
1476    // Record the info about the reallocated symbol so that we could properly
1477    // process failed reallocation.
1478    stateRealloc = stateRealloc->set<ReallocPairs>(ToPtr,
1479                                                   ReallocPair(FromPtr, Kind));
1480    // The reallocated symbol should stay alive for as long as the new symbol.
1481    C.getSymbolManager().addSymbolDependency(ToPtr, FromPtr);
1482    return stateRealloc;
1483  }
1484  return 0;
1485}
1486
1487ProgramStateRef MallocChecker::CallocMem(CheckerContext &C, const CallExpr *CE){
1488  if (CE->getNumArgs() < 2)
1489    return 0;
1490
1491  ProgramStateRef state = C.getState();
1492  SValBuilder &svalBuilder = C.getSValBuilder();
1493  const LocationContext *LCtx = C.getLocationContext();
1494  SVal count = state->getSVal(CE->getArg(0), LCtx);
1495  SVal elementSize = state->getSVal(CE->getArg(1), LCtx);
1496  SVal TotalSize = svalBuilder.evalBinOp(state, BO_Mul, count, elementSize,
1497                                        svalBuilder.getContext().getSizeType());
1498  SVal zeroVal = svalBuilder.makeZeroVal(svalBuilder.getContext().CharTy);
1499
1500  return MallocMemAux(C, CE, TotalSize, zeroVal, state);
1501}
1502
1503LeakInfo
1504MallocChecker::getAllocationSite(const ExplodedNode *N, SymbolRef Sym,
1505                                 CheckerContext &C) const {
1506  const LocationContext *LeakContext = N->getLocationContext();
1507  // Walk the ExplodedGraph backwards and find the first node that referred to
1508  // the tracked symbol.
1509  const ExplodedNode *AllocNode = N;
1510  const MemRegion *ReferenceRegion = 0;
1511
1512  while (N) {
1513    ProgramStateRef State = N->getState();
1514    if (!State->get<RegionState>(Sym))
1515      break;
1516
1517    // Find the most recent expression bound to the symbol in the current
1518    // context.
1519    if (!ReferenceRegion) {
1520      if (const MemRegion *MR = C.getLocationRegionIfPostStore(N)) {
1521        SVal Val = State->getSVal(MR);
1522        if (Val.getAsLocSymbol() == Sym)
1523          ReferenceRegion = MR;
1524      }
1525    }
1526
1527    // Allocation node, is the last node in the current context in which the
1528    // symbol was tracked.
1529    if (N->getLocationContext() == LeakContext)
1530      AllocNode = N;
1531    N = N->pred_empty() ? NULL : *(N->pred_begin());
1532  }
1533
1534  return LeakInfo(AllocNode, ReferenceRegion);
1535}
1536
1537void MallocChecker::reportLeak(SymbolRef Sym, ExplodedNode *N,
1538                               CheckerContext &C) const {
1539
1540  if (!Filter.CMallocOptimistic && !Filter.CMallocPessimistic &&
1541      !Filter.CNewDeleteLeaksChecker)
1542    return;
1543
1544  const RefState *RS = C.getState()->get<RegionState>(Sym);
1545  assert(RS && "cannot leak an untracked symbol");
1546  AllocationFamily Family = RS->getAllocationFamily();
1547  if (!isTrackedFamily(Family))
1548    return;
1549
1550  // Special case for new and new[]; these are controlled by a separate checker
1551  // flag so that they can be selectively disabled.
1552  if (Family == AF_CXXNew || Family == AF_CXXNewArray)
1553    if (!Filter.CNewDeleteLeaksChecker)
1554      return;
1555
1556  assert(N);
1557  if (!BT_Leak) {
1558    BT_Leak.reset(new BugType("Memory leak", "Memory Error"));
1559    // Leaks should not be reported if they are post-dominated by a sink:
1560    // (1) Sinks are higher importance bugs.
1561    // (2) NoReturnFunctionChecker uses sink nodes to represent paths ending
1562    //     with __noreturn functions such as assert() or exit(). We choose not
1563    //     to report leaks on such paths.
1564    BT_Leak->setSuppressOnSink(true);
1565  }
1566
1567  // Most bug reports are cached at the location where they occurred.
1568  // With leaks, we want to unique them by the location where they were
1569  // allocated, and only report a single path.
1570  PathDiagnosticLocation LocUsedForUniqueing;
1571  const ExplodedNode *AllocNode = 0;
1572  const MemRegion *Region = 0;
1573  llvm::tie(AllocNode, Region) = getAllocationSite(N, Sym, C);
1574
1575  ProgramPoint P = AllocNode->getLocation();
1576  const Stmt *AllocationStmt = 0;
1577  if (Optional<CallExitEnd> Exit = P.getAs<CallExitEnd>())
1578    AllocationStmt = Exit->getCalleeContext()->getCallSite();
1579  else if (Optional<StmtPoint> SP = P.getAs<StmtPoint>())
1580    AllocationStmt = SP->getStmt();
1581  if (AllocationStmt)
1582    LocUsedForUniqueing = PathDiagnosticLocation::createBegin(AllocationStmt,
1583                                              C.getSourceManager(),
1584                                              AllocNode->getLocationContext());
1585
1586  SmallString<200> buf;
1587  llvm::raw_svector_ostream os(buf);
1588  os << "Memory is never released; potential leak";
1589  if (Region && Region->canPrintPretty()) {
1590    os << " of memory pointed to by '";
1591    Region->printPretty(os);
1592    os << '\'';
1593  }
1594
1595  BugReport *R = new BugReport(*BT_Leak, os.str(), N,
1596                               LocUsedForUniqueing,
1597                               AllocNode->getLocationContext()->getDecl());
1598  R->markInteresting(Sym);
1599  R->addVisitor(new MallocBugVisitor(Sym, true));
1600  C.emitReport(R);
1601}
1602
1603void MallocChecker::checkDeadSymbols(SymbolReaper &SymReaper,
1604                                     CheckerContext &C) const
1605{
1606  if (!SymReaper.hasDeadSymbols())
1607    return;
1608
1609  ProgramStateRef state = C.getState();
1610  RegionStateTy RS = state->get<RegionState>();
1611  RegionStateTy::Factory &F = state->get_context<RegionState>();
1612
1613  SmallVector<SymbolRef, 2> Errors;
1614  for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
1615    if (SymReaper.isDead(I->first)) {
1616      if (I->second.isAllocated())
1617        Errors.push_back(I->first);
1618      // Remove the dead symbol from the map.
1619      RS = F.remove(RS, I->first);
1620
1621    }
1622  }
1623
1624  // Cleanup the Realloc Pairs Map.
1625  ReallocPairsTy RP = state->get<ReallocPairs>();
1626  for (ReallocPairsTy::iterator I = RP.begin(), E = RP.end(); I != E; ++I) {
1627    if (SymReaper.isDead(I->first) ||
1628        SymReaper.isDead(I->second.ReallocatedSym)) {
1629      state = state->remove<ReallocPairs>(I->first);
1630    }
1631  }
1632
1633  // Cleanup the FreeReturnValue Map.
1634  FreeReturnValueTy FR = state->get<FreeReturnValue>();
1635  for (FreeReturnValueTy::iterator I = FR.begin(), E = FR.end(); I != E; ++I) {
1636    if (SymReaper.isDead(I->first) ||
1637        SymReaper.isDead(I->second)) {
1638      state = state->remove<FreeReturnValue>(I->first);
1639    }
1640  }
1641
1642  // Generate leak node.
1643  ExplodedNode *N = C.getPredecessor();
1644  if (!Errors.empty()) {
1645    static SimpleProgramPointTag Tag("MallocChecker : DeadSymbolsLeak");
1646    N = C.addTransition(C.getState(), C.getPredecessor(), &Tag);
1647    for (SmallVector<SymbolRef, 2>::iterator
1648        I = Errors.begin(), E = Errors.end(); I != E; ++I) {
1649      reportLeak(*I, N, C);
1650    }
1651  }
1652
1653  C.addTransition(state->set<RegionState>(RS), N);
1654}
1655
1656void MallocChecker::checkPreStmt(const CallExpr *CE, CheckerContext &C) const {
1657  // We will check for double free in the post visit.
1658  if ((Filter.CMallocOptimistic || Filter.CMallocPessimistic) &&
1659      isFreeFunction(C.getCalleeDecl(CE), C.getASTContext()))
1660    return;
1661
1662  if (Filter.CNewDeleteChecker &&
1663      isStandardNewDelete(C.getCalleeDecl(CE), C.getASTContext()))
1664    return;
1665
1666  // Check use after free, when a freed pointer is passed to a call.
1667  ProgramStateRef State = C.getState();
1668  for (CallExpr::const_arg_iterator I = CE->arg_begin(),
1669                                    E = CE->arg_end(); I != E; ++I) {
1670    const Expr *A = *I;
1671    if (A->getType().getTypePtr()->isAnyPointerType()) {
1672      SymbolRef Sym = C.getSVal(A).getAsSymbol();
1673      if (!Sym)
1674        continue;
1675      if (checkUseAfterFree(Sym, C, A))
1676        return;
1677    }
1678  }
1679}
1680
1681void MallocChecker::checkPreStmt(const ReturnStmt *S, CheckerContext &C) const {
1682  const Expr *E = S->getRetValue();
1683  if (!E)
1684    return;
1685
1686  // Check if we are returning a symbol.
1687  ProgramStateRef State = C.getState();
1688  SVal RetVal = State->getSVal(E, C.getLocationContext());
1689  SymbolRef Sym = RetVal.getAsSymbol();
1690  if (!Sym)
1691    // If we are returning a field of the allocated struct or an array element,
1692    // the callee could still free the memory.
1693    // TODO: This logic should be a part of generic symbol escape callback.
1694    if (const MemRegion *MR = RetVal.getAsRegion())
1695      if (isa<FieldRegion>(MR) || isa<ElementRegion>(MR))
1696        if (const SymbolicRegion *BMR =
1697              dyn_cast<SymbolicRegion>(MR->getBaseRegion()))
1698          Sym = BMR->getSymbol();
1699
1700  // Check if we are returning freed memory.
1701  if (Sym)
1702    checkUseAfterFree(Sym, C, E);
1703}
1704
1705// TODO: Blocks should be either inlined or should call invalidate regions
1706// upon invocation. After that's in place, special casing here will not be
1707// needed.
1708void MallocChecker::checkPostStmt(const BlockExpr *BE,
1709                                  CheckerContext &C) const {
1710
1711  // Scan the BlockDecRefExprs for any object the retain count checker
1712  // may be tracking.
1713  if (!BE->getBlockDecl()->hasCaptures())
1714    return;
1715
1716  ProgramStateRef state = C.getState();
1717  const BlockDataRegion *R =
1718    cast<BlockDataRegion>(state->getSVal(BE,
1719                                         C.getLocationContext()).getAsRegion());
1720
1721  BlockDataRegion::referenced_vars_iterator I = R->referenced_vars_begin(),
1722                                            E = R->referenced_vars_end();
1723
1724  if (I == E)
1725    return;
1726
1727  SmallVector<const MemRegion*, 10> Regions;
1728  const LocationContext *LC = C.getLocationContext();
1729  MemRegionManager &MemMgr = C.getSValBuilder().getRegionManager();
1730
1731  for ( ; I != E; ++I) {
1732    const VarRegion *VR = I.getCapturedRegion();
1733    if (VR->getSuperRegion() == R) {
1734      VR = MemMgr.getVarRegion(VR->getDecl(), LC);
1735    }
1736    Regions.push_back(VR);
1737  }
1738
1739  state =
1740    state->scanReachableSymbols<StopTrackingCallback>(Regions.data(),
1741                                    Regions.data() + Regions.size()).getState();
1742  C.addTransition(state);
1743}
1744
1745bool MallocChecker::isReleased(SymbolRef Sym, CheckerContext &C) const {
1746  assert(Sym);
1747  const RefState *RS = C.getState()->get<RegionState>(Sym);
1748  return (RS && RS->isReleased());
1749}
1750
1751bool MallocChecker::checkUseAfterFree(SymbolRef Sym, CheckerContext &C,
1752                                      const Stmt *S) const {
1753
1754  if (isReleased(Sym, C)) {
1755    ReportUseAfterFree(C, S->getSourceRange(), Sym);
1756    return true;
1757  }
1758
1759  return false;
1760}
1761
1762// Check if the location is a freed symbolic region.
1763void MallocChecker::checkLocation(SVal l, bool isLoad, const Stmt *S,
1764                                  CheckerContext &C) const {
1765  SymbolRef Sym = l.getLocSymbolInBase();
1766  if (Sym)
1767    checkUseAfterFree(Sym, C, S);
1768}
1769
1770// If a symbolic region is assumed to NULL (or another constant), stop tracking
1771// it - assuming that allocation failed on this path.
1772ProgramStateRef MallocChecker::evalAssume(ProgramStateRef state,
1773                                              SVal Cond,
1774                                              bool Assumption) const {
1775  RegionStateTy RS = state->get<RegionState>();
1776  for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
1777    // If the symbol is assumed to be NULL, remove it from consideration.
1778    ConstraintManager &CMgr = state->getConstraintManager();
1779    ConditionTruthVal AllocFailed = CMgr.isNull(state, I.getKey());
1780    if (AllocFailed.isConstrainedTrue())
1781      state = state->remove<RegionState>(I.getKey());
1782  }
1783
1784  // Realloc returns 0 when reallocation fails, which means that we should
1785  // restore the state of the pointer being reallocated.
1786  ReallocPairsTy RP = state->get<ReallocPairs>();
1787  for (ReallocPairsTy::iterator I = RP.begin(), E = RP.end(); I != E; ++I) {
1788    // If the symbol is assumed to be NULL, remove it from consideration.
1789    ConstraintManager &CMgr = state->getConstraintManager();
1790    ConditionTruthVal AllocFailed = CMgr.isNull(state, I.getKey());
1791    if (!AllocFailed.isConstrainedTrue())
1792      continue;
1793
1794    SymbolRef ReallocSym = I.getData().ReallocatedSym;
1795    if (const RefState *RS = state->get<RegionState>(ReallocSym)) {
1796      if (RS->isReleased()) {
1797        if (I.getData().Kind == RPToBeFreedAfterFailure)
1798          state = state->set<RegionState>(ReallocSym,
1799              RefState::getAllocated(RS->getAllocationFamily(), RS->getStmt()));
1800        else if (I.getData().Kind == RPDoNotTrackAfterFailure)
1801          state = state->remove<RegionState>(ReallocSym);
1802        else
1803          assert(I.getData().Kind == RPIsFreeOnFailure);
1804      }
1805    }
1806    state = state->remove<ReallocPairs>(I.getKey());
1807  }
1808
1809  return state;
1810}
1811
1812bool MallocChecker::doesNotFreeMemOrInteresting(const CallEvent *Call,
1813                                                ProgramStateRef State) const {
1814  assert(Call);
1815
1816  // For now, assume that any C++ call can free memory.
1817  // TODO: If we want to be more optimistic here, we'll need to make sure that
1818  // regions escape to C++ containers. They seem to do that even now, but for
1819  // mysterious reasons.
1820  if (!(isa<FunctionCall>(Call) || isa<ObjCMethodCall>(Call)))
1821    return false;
1822
1823  // Check Objective-C messages by selector name.
1824  if (const ObjCMethodCall *Msg = dyn_cast<ObjCMethodCall>(Call)) {
1825    // If it's not a framework call, or if it takes a callback, assume it
1826    // can free memory.
1827    if (!Call->isInSystemHeader() || Call->hasNonZeroCallbackArg())
1828      return false;
1829
1830    // If it's a method we know about, handle it explicitly post-call.
1831    // This should happen before the "freeWhenDone" check below.
1832    if (isKnownDeallocObjCMethodName(*Msg))
1833      return true;
1834
1835    // If there's a "freeWhenDone" parameter, but the method isn't one we know
1836    // about, we can't be sure that the object will use free() to deallocate the
1837    // memory, so we can't model it explicitly. The best we can do is use it to
1838    // decide whether the pointer escapes.
1839    if (Optional<bool> FreeWhenDone = getFreeWhenDoneArg(*Msg))
1840      return !*FreeWhenDone;
1841
1842    // If the first selector piece ends with "NoCopy", and there is no
1843    // "freeWhenDone" parameter set to zero, we know ownership is being
1844    // transferred. Again, though, we can't be sure that the object will use
1845    // free() to deallocate the memory, so we can't model it explicitly.
1846    StringRef FirstSlot = Msg->getSelector().getNameForSlot(0);
1847    if (FirstSlot.endswith("NoCopy"))
1848      return false;
1849
1850    // If the first selector starts with addPointer, insertPointer,
1851    // or replacePointer, assume we are dealing with NSPointerArray or similar.
1852    // This is similar to C++ containers (vector); we still might want to check
1853    // that the pointers get freed by following the container itself.
1854    if (FirstSlot.startswith("addPointer") ||
1855        FirstSlot.startswith("insertPointer") ||
1856        FirstSlot.startswith("replacePointer")) {
1857      return false;
1858    }
1859
1860    // Otherwise, assume that the method does not free memory.
1861    // Most framework methods do not free memory.
1862    return true;
1863  }
1864
1865  // At this point the only thing left to handle is straight function calls.
1866  const FunctionDecl *FD = cast<FunctionCall>(Call)->getDecl();
1867  if (!FD)
1868    return false;
1869
1870  ASTContext &ASTC = State->getStateManager().getContext();
1871
1872  // If it's one of the allocation functions we can reason about, we model
1873  // its behavior explicitly.
1874  if (isMemFunction(FD, ASTC))
1875    return true;
1876
1877  // If it's not a system call, assume it frees memory.
1878  if (!Call->isInSystemHeader())
1879    return false;
1880
1881  // White list the system functions whose arguments escape.
1882  const IdentifierInfo *II = FD->getIdentifier();
1883  if (!II)
1884    return false;
1885  StringRef FName = II->getName();
1886
1887  // White list the 'XXXNoCopy' CoreFoundation functions.
1888  // We specifically check these before
1889  if (FName.endswith("NoCopy")) {
1890    // Look for the deallocator argument. We know that the memory ownership
1891    // is not transferred only if the deallocator argument is
1892    // 'kCFAllocatorNull'.
1893    for (unsigned i = 1; i < Call->getNumArgs(); ++i) {
1894      const Expr *ArgE = Call->getArgExpr(i)->IgnoreParenCasts();
1895      if (const DeclRefExpr *DE = dyn_cast<DeclRefExpr>(ArgE)) {
1896        StringRef DeallocatorName = DE->getFoundDecl()->getName();
1897        if (DeallocatorName == "kCFAllocatorNull")
1898          return true;
1899      }
1900    }
1901    return false;
1902  }
1903
1904  // Associating streams with malloced buffers. The pointer can escape if
1905  // 'closefn' is specified (and if that function does free memory),
1906  // but it will not if closefn is not specified.
1907  // Currently, we do not inspect the 'closefn' function (PR12101).
1908  if (FName == "funopen")
1909    if (Call->getNumArgs() >= 4 && Call->getArgSVal(4).isConstant(0))
1910      return true;
1911
1912  // Do not warn on pointers passed to 'setbuf' when used with std streams,
1913  // these leaks might be intentional when setting the buffer for stdio.
1914  // http://stackoverflow.com/questions/2671151/who-frees-setvbuf-buffer
1915  if (FName == "setbuf" || FName =="setbuffer" ||
1916      FName == "setlinebuf" || FName == "setvbuf") {
1917    if (Call->getNumArgs() >= 1) {
1918      const Expr *ArgE = Call->getArgExpr(0)->IgnoreParenCasts();
1919      if (const DeclRefExpr *ArgDRE = dyn_cast<DeclRefExpr>(ArgE))
1920        if (const VarDecl *D = dyn_cast<VarDecl>(ArgDRE->getDecl()))
1921          if (D->getCanonicalDecl()->getName().find("std") != StringRef::npos)
1922            return false;
1923    }
1924  }
1925
1926  // A bunch of other functions which either take ownership of a pointer or
1927  // wrap the result up in a struct or object, meaning it can be freed later.
1928  // (See RetainCountChecker.) Not all the parameters here are invalidated,
1929  // but the Malloc checker cannot differentiate between them. The right way
1930  // of doing this would be to implement a pointer escapes callback.
1931  if (FName == "CGBitmapContextCreate" ||
1932      FName == "CGBitmapContextCreateWithData" ||
1933      FName == "CVPixelBufferCreateWithBytes" ||
1934      FName == "CVPixelBufferCreateWithPlanarBytes" ||
1935      FName == "OSAtomicEnqueue") {
1936    return false;
1937  }
1938
1939  // Handle cases where we know a buffer's /address/ can escape.
1940  // Note that the above checks handle some special cases where we know that
1941  // even though the address escapes, it's still our responsibility to free the
1942  // buffer.
1943  if (Call->argumentsMayEscape())
1944    return false;
1945
1946  // Otherwise, assume that the function does not free memory.
1947  // Most system calls do not free the memory.
1948  return true;
1949}
1950
1951static bool retTrue(const RefState *RS) {
1952  return true;
1953}
1954
1955static bool checkIfNewOrNewArrayFamily(const RefState *RS) {
1956  return (RS->getAllocationFamily() == AF_CXXNewArray ||
1957          RS->getAllocationFamily() == AF_CXXNew);
1958}
1959
1960ProgramStateRef MallocChecker::checkPointerEscape(ProgramStateRef State,
1961                                             const InvalidatedSymbols &Escaped,
1962                                             const CallEvent *Call,
1963                                             PointerEscapeKind Kind) const {
1964  return checkPointerEscapeAux(State, Escaped, Call, Kind, &retTrue);
1965}
1966
1967ProgramStateRef MallocChecker::checkConstPointerEscape(ProgramStateRef State,
1968                                              const InvalidatedSymbols &Escaped,
1969                                              const CallEvent *Call,
1970                                              PointerEscapeKind Kind) const {
1971  return checkPointerEscapeAux(State, Escaped, Call, Kind,
1972                               &checkIfNewOrNewArrayFamily);
1973}
1974
1975ProgramStateRef MallocChecker::checkPointerEscapeAux(ProgramStateRef State,
1976                                              const InvalidatedSymbols &Escaped,
1977                                              const CallEvent *Call,
1978                                              PointerEscapeKind Kind,
1979                                  bool(*CheckRefState)(const RefState*)) const {
1980  // If we know that the call does not free memory, or we want to process the
1981  // call later, keep tracking the top level arguments.
1982  if ((Kind == PSK_DirectEscapeOnCall ||
1983       Kind == PSK_IndirectEscapeOnCall) &&
1984      doesNotFreeMemOrInteresting(Call, State)) {
1985    return State;
1986  }
1987
1988  for (InvalidatedSymbols::const_iterator I = Escaped.begin(),
1989       E = Escaped.end();
1990       I != E; ++I) {
1991    SymbolRef sym = *I;
1992
1993    if (const RefState *RS = State->get<RegionState>(sym)) {
1994      if (RS->isAllocated() && CheckRefState(RS))
1995        State = State->remove<RegionState>(sym);
1996    }
1997  }
1998  return State;
1999}
2000
2001static SymbolRef findFailedReallocSymbol(ProgramStateRef currState,
2002                                         ProgramStateRef prevState) {
2003  ReallocPairsTy currMap = currState->get<ReallocPairs>();
2004  ReallocPairsTy prevMap = prevState->get<ReallocPairs>();
2005
2006  for (ReallocPairsTy::iterator I = prevMap.begin(), E = prevMap.end();
2007       I != E; ++I) {
2008    SymbolRef sym = I.getKey();
2009    if (!currMap.lookup(sym))
2010      return sym;
2011  }
2012
2013  return NULL;
2014}
2015
2016PathDiagnosticPiece *
2017MallocChecker::MallocBugVisitor::VisitNode(const ExplodedNode *N,
2018                                           const ExplodedNode *PrevN,
2019                                           BugReporterContext &BRC,
2020                                           BugReport &BR) {
2021  ProgramStateRef state = N->getState();
2022  ProgramStateRef statePrev = PrevN->getState();
2023
2024  const RefState *RS = state->get<RegionState>(Sym);
2025  const RefState *RSPrev = statePrev->get<RegionState>(Sym);
2026  if (!RS)
2027    return 0;
2028
2029  const Stmt *S = 0;
2030  const char *Msg = 0;
2031  StackHintGeneratorForSymbol *StackHint = 0;
2032
2033  // Retrieve the associated statement.
2034  ProgramPoint ProgLoc = N->getLocation();
2035  if (Optional<StmtPoint> SP = ProgLoc.getAs<StmtPoint>()) {
2036    S = SP->getStmt();
2037  } else if (Optional<CallExitEnd> Exit = ProgLoc.getAs<CallExitEnd>()) {
2038    S = Exit->getCalleeContext()->getCallSite();
2039  } else if (Optional<BlockEdge> Edge = ProgLoc.getAs<BlockEdge>()) {
2040    // If an assumption was made on a branch, it should be caught
2041    // here by looking at the state transition.
2042    S = Edge->getSrc()->getTerminator();
2043  }
2044
2045  if (!S)
2046    return 0;
2047
2048  // FIXME: We will eventually need to handle non-statement-based events
2049  // (__attribute__((cleanup))).
2050
2051  // Find out if this is an interesting point and what is the kind.
2052  if (Mode == Normal) {
2053    if (isAllocated(RS, RSPrev, S)) {
2054      Msg = "Memory is allocated";
2055      StackHint = new StackHintGeneratorForSymbol(Sym,
2056                                                  "Returned allocated memory");
2057    } else if (isReleased(RS, RSPrev, S)) {
2058      Msg = "Memory is released";
2059      StackHint = new StackHintGeneratorForSymbol(Sym,
2060                                                  "Returned released memory");
2061    } else if (isRelinquished(RS, RSPrev, S)) {
2062      Msg = "Memory ownership is transfered";
2063      StackHint = new StackHintGeneratorForSymbol(Sym, "");
2064    } else if (isReallocFailedCheck(RS, RSPrev, S)) {
2065      Mode = ReallocationFailed;
2066      Msg = "Reallocation failed";
2067      StackHint = new StackHintGeneratorForReallocationFailed(Sym,
2068                                                       "Reallocation failed");
2069
2070      if (SymbolRef sym = findFailedReallocSymbol(state, statePrev)) {
2071        // Is it possible to fail two reallocs WITHOUT testing in between?
2072        assert((!FailedReallocSymbol || FailedReallocSymbol == sym) &&
2073          "We only support one failed realloc at a time.");
2074        BR.markInteresting(sym);
2075        FailedReallocSymbol = sym;
2076      }
2077    }
2078
2079  // We are in a special mode if a reallocation failed later in the path.
2080  } else if (Mode == ReallocationFailed) {
2081    assert(FailedReallocSymbol && "No symbol to look for.");
2082
2083    // Is this is the first appearance of the reallocated symbol?
2084    if (!statePrev->get<RegionState>(FailedReallocSymbol)) {
2085      // We're at the reallocation point.
2086      Msg = "Attempt to reallocate memory";
2087      StackHint = new StackHintGeneratorForSymbol(Sym,
2088                                                 "Returned reallocated memory");
2089      FailedReallocSymbol = NULL;
2090      Mode = Normal;
2091    }
2092  }
2093
2094  if (!Msg)
2095    return 0;
2096  assert(StackHint);
2097
2098  // Generate the extra diagnostic.
2099  PathDiagnosticLocation Pos(S, BRC.getSourceManager(),
2100                             N->getLocationContext());
2101  return new PathDiagnosticEventPiece(Pos, Msg, true, StackHint);
2102}
2103
2104void MallocChecker::printState(raw_ostream &Out, ProgramStateRef State,
2105                               const char *NL, const char *Sep) const {
2106
2107  RegionStateTy RS = State->get<RegionState>();
2108
2109  if (!RS.isEmpty()) {
2110    Out << Sep << "MallocChecker:" << NL;
2111    for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
2112      I.getKey()->dumpToStream(Out);
2113      Out << " : ";
2114      I.getData().dump(Out);
2115      Out << NL;
2116    }
2117  }
2118}
2119
2120#define REGISTER_CHECKER(name) \
2121void ento::register##name(CheckerManager &mgr) {\
2122  registerCStringCheckerBasic(mgr); \
2123  mgr.registerChecker<MallocChecker>()->Filter.C##name = true;\
2124}
2125
2126REGISTER_CHECKER(MallocPessimistic)
2127REGISTER_CHECKER(MallocOptimistic)
2128REGISTER_CHECKER(NewDeleteChecker)
2129REGISTER_CHECKER(NewDeleteLeaksChecker)
2130REGISTER_CHECKER(MismatchedDeallocatorChecker)
2131