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