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