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