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