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