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/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)