lib/GR/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 "GRExprEngineExperimentalChecks.h"
  16 #include "clang/GR/BugReporter/BugType.h"
  17 #include "clang/GR/PathSensitive/CheckerVisitor.h"
  18 #include "clang/GR/PathSensitive/GRState.h"
  19 #include "clang/GR/PathSensitive/GRStateTrait.h"
  20 #include "clang/GR/PathSensitive/SymbolManager.h"
  21 #include "llvm/ADT/ImmutableMap.h"
  22 using namespace clang;
  23 using namespace GR;
  24
  25 namespace {
  26
  27 class RefState {
  28   enum Kind { AllocateUnchecked, AllocateFailed, Released, Escaped,
  29               Relinquished } K;
  30   const Stmt *S;
  31
  32 public:
  33   RefState(Kind k, const Stmt *s) : K(k), S(s) {}
  34
  35   bool isAllocated() const { return K == AllocateUnchecked; }
  36   //bool isFailed() const { return K == AllocateFailed; }
  37   bool isReleased() const { return K == Released; }
  38   //bool isEscaped() const { return K == Escaped; }
  39   //bool isRelinquished() const { return K == Relinquished; }
  40
  41   bool operator==(const RefState &X) const {
  42     return K == X.K && S == X.S;
  43   }
  44
  45   static RefState getAllocateUnchecked(const Stmt *s) {
  46     return RefState(AllocateUnchecked, s);
  47   }
  48   static RefState getAllocateFailed() {
  49     return RefState(AllocateFailed, 0);
  50   }
  51   static RefState getReleased(const Stmt *s) { return RefState(Released, s); }
  52   static RefState getEscaped(const Stmt *s) { return RefState(Escaped, s); }
  53   static RefState getRelinquished(const Stmt *s) {
  54     return RefState(Relinquished, s);
  55   }
  56
  57   void Profile(llvm::FoldingSetNodeID &ID) const {
  58     ID.AddInteger(K);
  59     ID.AddPointer(S);
  60   }
  61 };
  62
  63 class RegionState {};
  64
  65 class MallocChecker : public CheckerVisitor<MallocChecker> {
  66   BuiltinBug *BT_DoubleFree;
  67   BuiltinBug *BT_Leak;
  68   BuiltinBug *BT_UseFree;
  69   BuiltinBug *BT_UseRelinquished;
  70   BuiltinBug *BT_BadFree;
  71   IdentifierInfo *II_malloc, *II_free, *II_realloc, *II_calloc;
  72
  73 public:
  74   MallocChecker()
  75     : BT_DoubleFree(0), BT_Leak(0), BT_UseFree(0), BT_UseRelinquished(0),
  76       BT_BadFree(0),
  77       II_malloc(0), II_free(0), II_realloc(0), II_calloc(0) {}
  78   static void *getTag();
  79   bool evalCallExpr(CheckerContext &C, const CallExpr *CE);
  80   void evalDeadSymbols(CheckerContext &C, SymbolReaper &SymReaper);
  81   void evalEndPath(GREndPathNodeBuilder &B, void *tag, GRExprEngine &Eng);
  82   void PreVisitReturnStmt(CheckerContext &C, const ReturnStmt *S);
  83   const GRState *evalAssume(const GRState *state, SVal Cond, bool Assumption,
  84                             bool *respondsToCallback);
  85   void visitLocation(CheckerContext &C, const Stmt *S, SVal l);
  86   virtual void PreVisitBind(CheckerContext &C, const Stmt *StoreE,
  87                             SVal location, SVal val);
  88
  89 private:
  90   void MallocMem(CheckerContext &C, const CallExpr *CE);
  91   void MallocMemReturnsAttr(CheckerContext &C, const CallExpr *CE,
  92                             const OwnershipAttr* Att);
  93   const GRState *MallocMemAux(CheckerContext &C, const CallExpr *CE,
  94                               const Expr *SizeEx, SVal Init,
  95                               const GRState *state) {
  96     return MallocMemAux(C, CE, state->getSVal(SizeEx), Init, state);
  97   }
  98   const GRState *MallocMemAux(CheckerContext &C, const CallExpr *CE,
  99                               SVal SizeEx, SVal Init,
 100                               const GRState *state);
 101
 102   void FreeMem(CheckerContext &C, const CallExpr *CE);
 103   void FreeMemAttr(CheckerContext &C, const CallExpr *CE,
 104                    const OwnershipAttr* Att);
 105   const GRState *FreeMemAux(CheckerContext &C, const CallExpr *CE,
 106                             const GRState *state, unsigned Num, bool Hold);
 107
 108   void ReallocMem(CheckerContext &C, const CallExpr *CE);
 109   void CallocMem(CheckerContext &C, const CallExpr *CE);
 110
 111   bool SummarizeValue(llvm::raw_ostream& os, SVal V);
 112   bool SummarizeRegion(llvm::raw_ostream& os, const MemRegion *MR);
 113   void ReportBadFree(CheckerContext &C, SVal ArgVal, SourceRange range);
 114 };
 115 } // end anonymous namespace
 116
 117 typedef llvm::ImmutableMap<SymbolRef, RefState> RegionStateTy;
 118
 119 namespace clang {
 120 namespace GR {
 121   template <>
 122   struct GRStateTrait<RegionState>
 123     : public GRStatePartialTrait<RegionStateTy> {
 124     static void *GDMIndex() { return MallocChecker::getTag(); }
 125   };
 126 }
 127 }
 128
 129 void GR::RegisterMallocChecker(GRExprEngine &Eng) {
 130   Eng.registerCheck(new MallocChecker());
 131 }
 132
 133 void *MallocChecker::getTag() {
 134   static int x;
 135   return &x;
 136 }
 137
 138 bool MallocChecker::evalCallExpr(CheckerContext &C, const CallExpr *CE) {
 139   const GRState *state = C.getState();
 140   const Expr *Callee = CE->getCallee();
 141   SVal L = state->getSVal(Callee);
 142
 143   const FunctionDecl *FD = L.getAsFunctionDecl();
 144   if (!FD)
 145     return false;
 146
 147   ASTContext &Ctx = C.getASTContext();
 148   if (!II_malloc)
 149     II_malloc = &Ctx.Idents.get("malloc");
 150   if (!II_free)
 151     II_free = &Ctx.Idents.get("free");
 152   if (!II_realloc)
 153     II_realloc = &Ctx.Idents.get("realloc");
 154   if (!II_calloc)
 155     II_calloc = &Ctx.Idents.get("calloc");
 156
 157   if (FD->getIdentifier() == II_malloc) {
 158     MallocMem(C, CE);
 159     return true;
 160   }
 161
 162   if (FD->getIdentifier() == II_free) {
 163     FreeMem(C, CE);
 164     return true;
 165   }
 166
 167   if (FD->getIdentifier() == II_realloc) {
 168     ReallocMem(C, CE);
 169     return true;
 170   }
 171
 172   if (FD->getIdentifier() == II_calloc) {
 173     CallocMem(C, CE);
 174     return true;
 175   }
 176
 177   // Check all the attributes, if there are any.
 178   // There can be multiple of these attributes.
 179   bool rv = false;
 180   if (FD->hasAttrs()) {
 181     for (specific_attr_iterator<OwnershipAttr>
 182                   i = FD->specific_attr_begin<OwnershipAttr>(),
 183                   e = FD->specific_attr_end<OwnershipAttr>();
 184          i != e; ++i) {
 185       switch ((*i)->getOwnKind()) {
 186       case OwnershipAttr::Returns: {
 187         MallocMemReturnsAttr(C, CE, *i);
 188         rv = true;
 189         break;
 190       }
 191       case OwnershipAttr::Takes:
 192       case OwnershipAttr::Holds: {
 193         FreeMemAttr(C, CE, *i);
 194         rv = true;
 195         break;
 196       }
 197       default:
 198         break;
 199       }
 200     }
 201   }
 202   return rv;
 203 }
 204
 205 void MallocChecker::MallocMem(CheckerContext &C, const CallExpr *CE) {
 206   const GRState *state = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(),
 207                                       C.getState());
 208   C.addTransition(state);
 209 }
 210
 211 void MallocChecker::MallocMemReturnsAttr(CheckerContext &C, const CallExpr *CE,
 212                                          const OwnershipAttr* Att) {
 213   if (Att->getModule() != "malloc")
 214     return;
 215
 216   OwnershipAttr::args_iterator I = Att->args_begin(), E = Att->args_end();
 217   if (I != E) {
 218     const GRState *state =
 219         MallocMemAux(C, CE, CE->getArg(*I), UndefinedVal(), C.getState());
 220     C.addTransition(state);
 221     return;
 222   }
 223   const GRState *state = MallocMemAux(C, CE, UnknownVal(), UndefinedVal(),
 224                                         C.getState());
 225   C.addTransition(state);
 226 }
 227
 228 const GRState *MallocChecker::MallocMemAux(CheckerContext &C,
 229                                            const CallExpr *CE,
 230                                            SVal Size, SVal Init,
 231                                            const GRState *state) {
 232   unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
 233   SValBuilder &svalBuilder = C.getSValBuilder();
 234
 235   // Set the return value.
 236   SVal retVal = svalBuilder.getConjuredSymbolVal(NULL, CE, CE->getType(), Count);
 237   state = state->BindExpr(CE, retVal);
 238
 239   // Fill the region with the initialization value.
 240   state = state->bindDefault(retVal, Init);
 241
 242   // Set the region's extent equal to the Size parameter.
 243   const SymbolicRegion *R = cast<SymbolicRegion>(retVal.getAsRegion());
 244   DefinedOrUnknownSVal Extent = R->getExtent(svalBuilder);
 245   DefinedOrUnknownSVal DefinedSize = cast<DefinedOrUnknownSVal>(Size);
 246   DefinedOrUnknownSVal extentMatchesSize =
 247     svalBuilder.evalEQ(state, Extent, DefinedSize);
 248
 249   state = state->assume(extentMatchesSize, true);
 250   assert(state);
 251
 252   SymbolRef Sym = retVal.getAsLocSymbol();
 253   assert(Sym);
 254
 255   // Set the symbol's state to Allocated.
 256   return state->set<RegionState>(Sym, RefState::getAllocateUnchecked(CE));
 257 }
 258
 259 void MallocChecker::FreeMem(CheckerContext &C, const CallExpr *CE) {
 260   const GRState *state = FreeMemAux(C, CE, C.getState(), 0, false);
 261
 262   if (state)
 263     C.addTransition(state);
 264 }
 265
 266 void MallocChecker::FreeMemAttr(CheckerContext &C, const CallExpr *CE,
 267                                 const OwnershipAttr* Att) {
 268   if (Att->getModule() != "malloc")
 269     return;
 270
 271   for (OwnershipAttr::args_iterator I = Att->args_begin(), E = Att->args_end();
 272        I != E; ++I) {
 273     const GRState *state = FreeMemAux(C, CE, C.getState(), *I,
 274                                       Att->getOwnKind() == OwnershipAttr::Holds);
 275     if (state)
 276       C.addTransition(state);
 277   }
 278 }
 279
 280 const GRState *MallocChecker::FreeMemAux(CheckerContext &C, const CallExpr *CE,
 281                                          const GRState *state, unsigned Num,
 282                                          bool Hold) {
 283   const Expr *ArgExpr = CE->getArg(Num);
 284   SVal ArgVal = state->getSVal(ArgExpr);
 285
 286   DefinedOrUnknownSVal location = cast<DefinedOrUnknownSVal>(ArgVal);
 287
 288   // Check for null dereferences.
 289   if (!isa<Loc>(location))
 290     return state;
 291
 292   // FIXME: Technically using 'Assume' here can result in a path
 293   //  bifurcation.  In such cases we need to return two states, not just one.
 294   const GRState *notNullState, *nullState;
 295   llvm::tie(notNullState, nullState) = state->assume(location);
 296
 297   // The explicit NULL case, no operation is performed.
 298   if (nullState && !notNullState)
 299     return nullState;
 300
 301   assert(notNullState);
 302
 303   // Unknown values could easily be okay
 304   // Undefined values are handled elsewhere
 305   if (ArgVal.isUnknownOrUndef())
 306     return notNullState;
 307
 308   const MemRegion *R = ArgVal.getAsRegion();
 309
 310   // Nonlocs can't be freed, of course.
 311   // Non-region locations (labels and fixed addresses) also shouldn't be freed.
 312   if (!R) {
 313     ReportBadFree(C, ArgVal, ArgExpr->getSourceRange());
 314     return NULL;
 315   }
 316
 317   R = R->StripCasts();
 318
 319   // Blocks might show up as heap data, but should not be free()d
 320   if (isa<BlockDataRegion>(R)) {
 321     ReportBadFree(C, ArgVal, ArgExpr->getSourceRange());
 322     return NULL;
 323   }
 324
 325   const MemSpaceRegion *MS = R->getMemorySpace();
 326
 327   // Parameters, locals, statics, and globals shouldn't be freed.
 328   if (!(isa<UnknownSpaceRegion>(MS) || isa<HeapSpaceRegion>(MS))) {
 329     // FIXME: at the time this code was written, malloc() regions were
 330     // represented by conjured symbols, which are all in UnknownSpaceRegion.
 331     // This means that there isn't actually anything from HeapSpaceRegion
 332     // that should be freed, even though we allow it here.
 333     // Of course, free() can work on memory allocated outside the current
 334     // function, so UnknownSpaceRegion is always a possibility.
 335     // False negatives are better than false positives.
 336
 337     ReportBadFree(C, ArgVal, ArgExpr->getSourceRange());
 338     return NULL;
 339   }
 340
 341   const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R);
 342   // Various cases could lead to non-symbol values here.
 343   // For now, ignore them.
 344   if (!SR)
 345     return notNullState;
 346
 347   SymbolRef Sym = SR->getSymbol();
 348   const RefState *RS = state->get<RegionState>(Sym);
 349
 350   // If the symbol has not been tracked, return. This is possible when free() is
 351   // called on a pointer that does not get its pointee directly from malloc().
 352   // Full support of this requires inter-procedural analysis.
 353   if (!RS)
 354     return notNullState;
 355
 356   // Check double free.
 357   if (RS->isReleased()) {
 358     if (ExplodedNode *N = C.generateSink()) {
 359       if (!BT_DoubleFree)
 360         BT_DoubleFree
 361           = new BuiltinBug("Double free",
 362                          "Try to free a memory block that has been released");
 363       // FIXME: should find where it's freed last time.
 364       BugReport *R = new BugReport(*BT_DoubleFree,
 365                                    BT_DoubleFree->getDescription(), N);
 366       C.EmitReport(R);
 367     }
 368     return NULL;
 369   }
 370
 371   // Normal free.
 372   if (Hold)
 373     return notNullState->set<RegionState>(Sym, RefState::getRelinquished(CE));
 374   return notNullState->set<RegionState>(Sym, RefState::getReleased(CE));
 375 }
 376
 377 bool MallocChecker::SummarizeValue(llvm::raw_ostream& os, SVal V) {
 378   if (nonloc::ConcreteInt *IntVal = dyn_cast<nonloc::ConcreteInt>(&V))
 379     os << "an integer (" << IntVal->getValue() << ")";
 380   else if (loc::ConcreteInt *ConstAddr = dyn_cast<loc::ConcreteInt>(&V))
 381     os << "a constant address (" << ConstAddr->getValue() << ")";
 382   else if (loc::GotoLabel *Label = dyn_cast<loc::GotoLabel>(&V))
 383     os << "the address of the label '"
 384        << Label->getLabel()->getID()->getName()
 385        << "'";
 386   else
 387     return false;
 388
 389   return true;
 390 }
 391
 392 bool MallocChecker::SummarizeRegion(llvm::raw_ostream& os,
 393                                     const MemRegion *MR) {
 394   switch (MR->getKind()) {
 395   case MemRegion::FunctionTextRegionKind: {
 396     const FunctionDecl *FD = cast<FunctionTextRegion>(MR)->getDecl();
 397     if (FD)
 398       os << "the address of the function '" << FD << "'";
 399     else
 400       os << "the address of a function";
 401     return true;
 402   }
 403   case MemRegion::BlockTextRegionKind:
 404     os << "block text";
 405     return true;
 406   case MemRegion::BlockDataRegionKind:
 407     // FIXME: where the block came from?
 408     os << "a block";
 409     return true;
 410   default: {
 411     const MemSpaceRegion *MS = MR->getMemorySpace();
 412
 413     switch (MS->getKind()) {
 414     case MemRegion::StackLocalsSpaceRegionKind: {
 415       const VarRegion *VR = dyn_cast<VarRegion>(MR);
 416       const VarDecl *VD;
 417       if (VR)
 418         VD = VR->getDecl();
 419       else
 420         VD = NULL;
 421
 422       if (VD)
 423         os << "the address of the local variable '" << VD->getName() << "'";
 424       else
 425         os << "the address of a local stack variable";
 426       return true;
 427     }
 428     case MemRegion::StackArgumentsSpaceRegionKind: {
 429       const VarRegion *VR = dyn_cast<VarRegion>(MR);
 430       const VarDecl *VD;
 431       if (VR)
 432         VD = VR->getDecl();
 433       else
 434         VD = NULL;
 435
 436       if (VD)
 437         os << "the address of the parameter '" << VD->getName() << "'";
 438       else
 439         os << "the address of a parameter";
 440       return true;
 441     }
 442     case MemRegion::NonStaticGlobalSpaceRegionKind:
 443     case MemRegion::StaticGlobalSpaceRegionKind: {
 444       const VarRegion *VR = dyn_cast<VarRegion>(MR);
 445       const VarDecl *VD;
 446       if (VR)
 447         VD = VR->getDecl();
 448       else
 449         VD = NULL;
 450
 451       if (VD) {
 452         if (VD->isStaticLocal())
 453           os << "the address of the static variable '" << VD->getName() << "'";
 454         else
 455           os << "the address of the global variable '" << VD->getName() << "'";
 456       } else
 457         os << "the address of a global variable";
 458       return true;
 459     }
 460     default:
 461       return false;
 462     }
 463   }
 464   }
 465 }
 466
 467 void MallocChecker::ReportBadFree(CheckerContext &C, SVal ArgVal,
 468                                   SourceRange range) {
 469   if (ExplodedNode *N = C.generateSink()) {
 470     if (!BT_BadFree)
 471       BT_BadFree = new BuiltinBug("Bad free");
 472
 473     llvm::SmallString<100> buf;
 474     llvm::raw_svector_ostream os(buf);
 475
 476     const MemRegion *MR = ArgVal.getAsRegion();
 477     if (MR) {
 478       while (const ElementRegion *ER = dyn_cast<ElementRegion>(MR))
 479         MR = ER->getSuperRegion();
 480
 481       // Special case for alloca()
 482       if (isa<AllocaRegion>(MR))
 483         os << "Argument to free() was allocated by alloca(), not malloc()";
 484       else {
 485         os << "Argument to free() is ";
 486         if (SummarizeRegion(os, MR))
 487           os << ", which is not memory allocated by malloc()";
 488         else
 489           os << "not memory allocated by malloc()";
 490       }
 491     } else {
 492       os << "Argument to free() is ";
 493       if (SummarizeValue(os, ArgVal))
 494         os << ", which is not memory allocated by malloc()";
 495       else
 496         os << "not memory allocated by malloc()";
 497     }
 498
 499     EnhancedBugReport *R = new EnhancedBugReport(*BT_BadFree, os.str(), N);
 500     R->addRange(range);
 501     C.EmitReport(R);
 502   }
 503 }
 504
 505 void MallocChecker::ReallocMem(CheckerContext &C, const CallExpr *CE) {
 506   const GRState *state = C.getState();
 507   const Expr *arg0Expr = CE->getArg(0);
 508   DefinedOrUnknownSVal arg0Val
 509     = cast<DefinedOrUnknownSVal>(state->getSVal(arg0Expr));
 510
 511   SValBuilder &svalBuilder = C.getSValBuilder();
 512
 513   DefinedOrUnknownSVal PtrEQ =
 514     svalBuilder.evalEQ(state, arg0Val, svalBuilder.makeNull());
 515
 516   // If the ptr is NULL, the call is equivalent to malloc(size).
 517   if (const GRState *stateEqual = state->assume(PtrEQ, true)) {
 518     // Hack: set the NULL symbolic region to released to suppress false warning.
 519     // In the future we should add more states for allocated regions, e.g.,
 520     // CheckedNull, CheckedNonNull.
 521
 522     SymbolRef Sym = arg0Val.getAsLocSymbol();
 523     if (Sym)
 524       stateEqual = stateEqual->set<RegionState>(Sym, RefState::getReleased(CE));
 525
 526     const GRState *stateMalloc = MallocMemAux(C, CE, CE->getArg(1),
 527                                               UndefinedVal(), stateEqual);
 528     C.addTransition(stateMalloc);
 529   }
 530
 531   if (const GRState *stateNotEqual = state->assume(PtrEQ, false)) {
 532     const Expr *Arg1 = CE->getArg(1);
 533     DefinedOrUnknownSVal Arg1Val =
 534       cast<DefinedOrUnknownSVal>(stateNotEqual->getSVal(Arg1));
 535     DefinedOrUnknownSVal SizeZero =
 536       svalBuilder.evalEQ(stateNotEqual, Arg1Val,
 537                          svalBuilder.makeIntValWithPtrWidth(0, false));
 538
 539     if (const GRState *stateSizeZero = stateNotEqual->assume(SizeZero, true))
 540       if (const GRState *stateFree = FreeMemAux(C, CE, stateSizeZero, 0, false))
 541         C.addTransition(stateFree->BindExpr(CE, UndefinedVal(), true));
 542
 543     if (const GRState *stateSizeNotZero = stateNotEqual->assume(SizeZero,false))
 544       if (const GRState *stateFree = FreeMemAux(C, CE, stateSizeNotZero,
 545                                                 0, false)) {
 546         // FIXME: We should copy the content of the original buffer.
 547         const GRState *stateRealloc = MallocMemAux(C, CE, CE->getArg(1),
 548                                                    UnknownVal(), stateFree);
 549         C.addTransition(stateRealloc);
 550       }
 551   }
 552 }
 553
 554 void MallocChecker::CallocMem(CheckerContext &C, const CallExpr *CE) {
 555   const GRState *state = C.getState();
 556   SValBuilder &svalBuilder = C.getSValBuilder();
 557
 558   SVal count = state->getSVal(CE->getArg(0));
 559   SVal elementSize = state->getSVal(CE->getArg(1));
 560   SVal TotalSize = svalBuilder.evalBinOp(state, BO_Mul, count, elementSize,
 561                                         svalBuilder.getContext().getSizeType());
 562   SVal zeroVal = svalBuilder.makeZeroVal(svalBuilder.getContext().CharTy);
 563
 564   C.addTransition(MallocMemAux(C, CE, TotalSize, zeroVal, state));
 565 }
 566
 567 void MallocChecker::evalDeadSymbols(CheckerContext &C, SymbolReaper &SymReaper)
 568 {
 569   if (!SymReaper.hasDeadSymbols())
 570     return;
 571
 572   const GRState *state = C.getState();
 573   RegionStateTy RS = state->get<RegionState>();
 574   RegionStateTy::Factory &F = state->get_context<RegionState>();
 575
 576   for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
 577     if (SymReaper.isDead(I->first)) {
 578       if (I->second.isAllocated()) {
 579         if (ExplodedNode *N = C.generateNode()) {
 580           if (!BT_Leak)
 581             BT_Leak = new BuiltinBug("Memory leak",
 582                      "Allocated memory never released. Potential memory leak.");
 583           // FIXME: where it is allocated.
 584           BugReport *R = new BugReport(*BT_Leak, BT_Leak->getDescription(), N);
 585           C.EmitReport(R);
 586         }
 587       }
 588
 589       // Remove the dead symbol from the map.
 590       RS = F.remove(RS, I->first);
 591     }
 592   }
 593   C.generateNode(state->set<RegionState>(RS));
 594 }
 595
 596 void MallocChecker::evalEndPath(GREndPathNodeBuilder &B, void *tag,
 597                                 GRExprEngine &Eng) {
 598   SaveAndRestore<bool> OldHasGen(B.HasGeneratedNode);
 599   const GRState *state = B.getState();
 600   RegionStateTy M = state->get<RegionState>();
 601
 602   for (RegionStateTy::iterator I = M.begin(), E = M.end(); I != E; ++I) {
 603     RefState RS = I->second;
 604     if (RS.isAllocated()) {
 605       ExplodedNode *N = B.generateNode(state, tag, B.getPredecessor());
 606       if (N) {
 607         if (!BT_Leak)
 608           BT_Leak = new BuiltinBug("Memory leak",
 609                      "Allocated memory never released. Potential memory leak.");
 610         BugReport *R = new BugReport(*BT_Leak, BT_Leak->getDescription(), N);
 611         Eng.getBugReporter().EmitReport(R);
 612       }
 613     }
 614   }
 615 }
 616
 617 void MallocChecker::PreVisitReturnStmt(CheckerContext &C, const ReturnStmt *S) {
 618   const Expr *retExpr = S->getRetValue();
 619   if (!retExpr)
 620     return;
 621
 622   const GRState *state = C.getState();
 623
 624   SymbolRef Sym = state->getSVal(retExpr).getAsSymbol();
 625   if (!Sym)
 626     return;
 627
 628   const RefState *RS = state->get<RegionState>(Sym);
 629   if (!RS)
 630     return;
 631
 632   // FIXME: check other cases.
 633   if (RS->isAllocated())
 634     state = state->set<RegionState>(Sym, RefState::getEscaped(S));
 635
 636   C.addTransition(state);
 637 }
 638
 639 const GRState *MallocChecker::evalAssume(const GRState *state, SVal Cond,
 640                                          bool Assumption,
 641                                          bool * /* respondsToCallback */) {
 642   // If a symblic region is assumed to NULL, set its state to AllocateFailed.
 643   // FIXME: should also check symbols assumed to non-null.
 644
 645   RegionStateTy RS = state->get<RegionState>();
 646
 647   for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
 648     if (state->getSymVal(I.getKey()))
 649       state = state->set<RegionState>(I.getKey(),RefState::getAllocateFailed());
 650   }
 651
 652   return state;
 653 }
 654
 655 // Check if the location is a freed symbolic region.
 656 void MallocChecker::visitLocation(CheckerContext &C, const Stmt *S, SVal l) {
 657   SymbolRef Sym = l.getLocSymbolInBase();
 658   if (Sym) {
 659     const RefState *RS = C.getState()->get<RegionState>(Sym);
 660     if (RS && RS->isReleased()) {
 661       if (ExplodedNode *N = C.generateNode()) {
 662         if (!BT_UseFree)
 663           BT_UseFree = new BuiltinBug("Use dynamically allocated memory after"
 664                                       " it is freed.");
 665
 666         BugReport *R = new BugReport(*BT_UseFree, BT_UseFree->getDescription(),
 667                                      N);
 668         C.EmitReport(R);
 669       }
 670     }
 671   }
 672 }
 673
 674 void MallocChecker::PreVisitBind(CheckerContext &C,
 675                                  const Stmt *StoreE,
 676                                  SVal location,
 677                                  SVal val) {
 678   // The PreVisitBind implements the same algorithm as already used by the
 679   // Objective C ownership checker: if the pointer escaped from this scope by
 680   // assignment, let it go.  However, assigning to fields of a stack-storage
 681   // structure does not transfer ownership.
 682
 683   const GRState *state = C.getState();
 684   DefinedOrUnknownSVal l = cast<DefinedOrUnknownSVal>(location);
 685
 686   // Check for null dereferences.
 687   if (!isa<Loc>(l))
 688     return;
 689
 690   // Before checking if the state is null, check if 'val' has a RefState.
 691   // Only then should we check for null and bifurcate the state.
 692   SymbolRef Sym = val.getLocSymbolInBase();
 693   if (Sym) {
 694     if (const RefState *RS = state->get<RegionState>(Sym)) {
 695       // If ptr is NULL, no operation is performed.
 696       const GRState *notNullState, *nullState;
 697       llvm::tie(notNullState, nullState) = state->assume(l);
 698
 699       // Generate a transition for 'nullState' to record the assumption
 700       // that the state was null.
 701       if (nullState)
 702         C.addTransition(nullState);
 703
 704       if (!notNullState)
 705         return;
 706
 707       if (RS->isAllocated()) {
 708         // Something we presently own is being assigned somewhere.
 709         const MemRegion *AR = location.getAsRegion();
 710         if (!AR)
 711           return;
 712         AR = AR->StripCasts()->getBaseRegion();
 713         do {
 714           // If it is on the stack, we still own it.
 715           if (AR->hasStackNonParametersStorage())
 716             break;
 717
 718           // If the state can't represent this binding, we still own it.
 719           if (notNullState == (notNullState->bindLoc(cast<Loc>(location),
 720                                                      UnknownVal())))
 721             break;
 722
 723           // We no longer own this pointer.
 724           notNullState =
 725             notNullState->set<RegionState>(Sym,
 726                                            RefState::getRelinquished(StoreE));
 727         }
 728         while (false);
 729       }
 730       C.addTransition(notNullState);
 731     }
 732   }
 733 }