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