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