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