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