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