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