contrib/llvm/tools/clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

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