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