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