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