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