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