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