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