MallocChecker.cpp revision 48d798ce32447607144db70a484cdb99c1180663
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 "InterCheckerAPI.h" 17#include "clang/StaticAnalyzer/Core/Checker.h" 18#include "clang/StaticAnalyzer/Core/CheckerManager.h" 19#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 20#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 21#include "clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h" 22#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 23#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 24#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h" 25#include "clang/Basic/SourceManager.h" 26#include "llvm/ADT/ImmutableMap.h" 27#include "llvm/ADT/SmallString.h" 28#include "llvm/ADT/STLExtras.h" 29#include <climits> 30 31using namespace clang; 32using namespace ento; 33 34namespace { 35 36class RefState { 37 enum Kind { AllocateUnchecked, AllocateFailed, Released, Escaped, 38 Relinquished } K; 39 const Stmt *S; 40 41public: 42 RefState(Kind k, const Stmt *s) : K(k), S(s) {} 43 44 bool isAllocated() const { return K == AllocateUnchecked; } 45 bool isReleased() const { return K == Released; } 46 47 const Stmt *getStmt() const { return S; } 48 49 bool operator==(const RefState &X) const { 50 return K == X.K && S == X.S; 51 } 52 53 static RefState getAllocateUnchecked(const Stmt *s) { 54 return RefState(AllocateUnchecked, s); 55 } 56 static RefState getAllocateFailed() { 57 return RefState(AllocateFailed, 0); 58 } 59 static RefState getReleased(const Stmt *s) { return RefState(Released, s); } 60 static RefState getEscaped(const Stmt *s) { return RefState(Escaped, s); } 61 static RefState getRelinquished(const Stmt *s) { 62 return RefState(Relinquished, s); 63 } 64 65 void Profile(llvm::FoldingSetNodeID &ID) const { 66 ID.AddInteger(K); 67 ID.AddPointer(S); 68 } 69}; 70 71struct ReallocPair { 72 SymbolRef ReallocatedSym; 73 bool IsFreeOnFailure; 74 ReallocPair(SymbolRef S, bool F) : ReallocatedSym(S), IsFreeOnFailure(F) {} 75 void Profile(llvm::FoldingSetNodeID &ID) const { 76 ID.AddInteger(IsFreeOnFailure); 77 ID.AddPointer(ReallocatedSym); 78 } 79 bool operator==(const ReallocPair &X) const { 80 return ReallocatedSym == X.ReallocatedSym && 81 IsFreeOnFailure == X.IsFreeOnFailure; 82 } 83}; 84 85typedef std::pair<const Stmt*, const MemRegion*> LeakInfo; 86 87class MallocChecker : public Checker<check::DeadSymbols, 88 check::EndPath, 89 check::PreStmt<ReturnStmt>, 90 check::PreStmt<CallExpr>, 91 check::PostStmt<CallExpr>, 92 check::PostStmt<BlockExpr>, 93 check::Location, 94 check::Bind, 95 eval::Assume, 96 check::RegionChanges> 97{ 98 mutable OwningPtr<BugType> BT_DoubleFree; 99 mutable OwningPtr<BugType> BT_Leak; 100 mutable OwningPtr<BugType> BT_UseFree; 101 mutable OwningPtr<BugType> BT_BadFree; 102 mutable IdentifierInfo *II_malloc, *II_free, *II_realloc, *II_calloc, 103 *II_valloc, *II_reallocf, *II_strndup, *II_strdup; 104 105public: 106 MallocChecker() : II_malloc(0), II_free(0), II_realloc(0), II_calloc(0), 107 II_valloc(0), II_reallocf(0), II_strndup(0), II_strdup(0) {} 108 109 /// In pessimistic mode, the checker assumes that it does not know which 110 /// functions might free the memory. 111 struct ChecksFilter { 112 DefaultBool CMallocPessimistic; 113 DefaultBool CMallocOptimistic; 114 }; 115 116 ChecksFilter Filter; 117 118 void checkPreStmt(const CallExpr *S, CheckerContext &C) const; 119 void checkPostStmt(const CallExpr *CE, CheckerContext &C) const; 120 void checkPostStmt(const BlockExpr *BE, CheckerContext &C) const; 121 void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const; 122 void checkEndPath(CheckerContext &C) const; 123 void checkPreStmt(const ReturnStmt *S, CheckerContext &C) const; 124 ProgramStateRef evalAssume(ProgramStateRef state, SVal Cond, 125 bool Assumption) const; 126 void checkLocation(SVal l, bool isLoad, const Stmt *S, 127 CheckerContext &C) const; 128 void checkBind(SVal location, SVal val, const Stmt*S, 129 CheckerContext &C) const; 130 ProgramStateRef 131 checkRegionChanges(ProgramStateRef state, 132 const StoreManager::InvalidatedSymbols *invalidated, 133 ArrayRef<const MemRegion *> ExplicitRegions, 134 ArrayRef<const MemRegion *> Regions, 135 const CallOrObjCMessage *Call) const; 136 bool wantsRegionChangeUpdate(ProgramStateRef state) const { 137 return true; 138 } 139 140 void printState(raw_ostream &Out, ProgramStateRef State, 141 const char *NL, const char *Sep) const; 142 143private: 144 void initIdentifierInfo(ASTContext &C) const; 145 146 /// Check if this is one of the functions which can allocate/reallocate memory 147 /// pointed to by one of its arguments. 148 bool isMemFunction(const FunctionDecl *FD, ASTContext &C) const; 149 bool isFreeFunction(const FunctionDecl *FD, ASTContext &C) const; 150 bool isAllocationFunction(const FunctionDecl *FD, ASTContext &C) const; 151 152 static ProgramStateRef MallocMemReturnsAttr(CheckerContext &C, 153 const CallExpr *CE, 154 const OwnershipAttr* Att); 155 static ProgramStateRef MallocMemAux(CheckerContext &C, const CallExpr *CE, 156 const Expr *SizeEx, SVal Init, 157 ProgramStateRef state) { 158 return MallocMemAux(C, CE, 159 state->getSVal(SizeEx, C.getLocationContext()), 160 Init, state); 161 } 162 163 static ProgramStateRef MallocMemAux(CheckerContext &C, const CallExpr *CE, 164 SVal SizeEx, SVal Init, 165 ProgramStateRef state); 166 167 /// Update the RefState to reflect the new memory allocation. 168 static ProgramStateRef MallocUpdateRefState(CheckerContext &C, 169 const CallExpr *CE, 170 ProgramStateRef state); 171 172 ProgramStateRef FreeMemAttr(CheckerContext &C, const CallExpr *CE, 173 const OwnershipAttr* Att) const; 174 ProgramStateRef FreeMemAux(CheckerContext &C, const CallExpr *CE, 175 ProgramStateRef state, unsigned Num, 176 bool Hold) const; 177 178 ProgramStateRef ReallocMem(CheckerContext &C, const CallExpr *CE, 179 bool FreesMemOnFailure) const; 180 static ProgramStateRef CallocMem(CheckerContext &C, const CallExpr *CE); 181 182 ///\brief Check if the memory associated with this symbol was released. 183 bool isReleased(SymbolRef Sym, CheckerContext &C) const; 184 185 bool checkEscape(SymbolRef Sym, const Stmt *S, CheckerContext &C) const; 186 bool checkUseAfterFree(SymbolRef Sym, CheckerContext &C, 187 const Stmt *S = 0) const; 188 189 /// Check if the function is not known to us. So, for example, we could 190 /// conservatively assume it can free/reallocate it's pointer arguments. 191 bool doesNotFreeMemory(const CallOrObjCMessage *Call, 192 ProgramStateRef State) const; 193 194 static bool SummarizeValue(raw_ostream &os, SVal V); 195 static bool SummarizeRegion(raw_ostream &os, const MemRegion *MR); 196 void ReportBadFree(CheckerContext &C, SVal ArgVal, SourceRange range) const; 197 198 /// Find the location of the allocation for Sym on the path leading to the 199 /// exploded node N. 200 LeakInfo getAllocationSite(const ExplodedNode *N, SymbolRef Sym, 201 CheckerContext &C) const; 202 203 void reportLeak(SymbolRef Sym, ExplodedNode *N, CheckerContext &C) const; 204 205 /// The bug visitor which allows us to print extra diagnostics along the 206 /// BugReport path. For example, showing the allocation site of the leaked 207 /// region. 208 class MallocBugVisitor : public BugReporterVisitorImpl<MallocBugVisitor> { 209 protected: 210 enum NotificationMode { 211 Normal, 212 ReallocationFailed 213 }; 214 215 // The allocated region symbol tracked by the main analysis. 216 SymbolRef Sym; 217 218 // The mode we are in, i.e. what kind of diagnostics will be emitted. 219 NotificationMode Mode; 220 221 // A symbol from when the primary region should have been reallocated. 222 SymbolRef FailedReallocSymbol; 223 224 bool IsLeak; 225 226 public: 227 MallocBugVisitor(SymbolRef S, bool isLeak = false) 228 : Sym(S), Mode(Normal), FailedReallocSymbol(0), IsLeak(isLeak) {} 229 230 virtual ~MallocBugVisitor() {} 231 232 void Profile(llvm::FoldingSetNodeID &ID) const { 233 static int X = 0; 234 ID.AddPointer(&X); 235 ID.AddPointer(Sym); 236 } 237 238 inline bool isAllocated(const RefState *S, const RefState *SPrev, 239 const Stmt *Stmt) { 240 // Did not track -> allocated. Other state (released) -> allocated. 241 return (Stmt && isa<CallExpr>(Stmt) && 242 (S && S->isAllocated()) && (!SPrev || !SPrev->isAllocated())); 243 } 244 245 inline bool isReleased(const RefState *S, const RefState *SPrev, 246 const Stmt *Stmt) { 247 // Did not track -> released. Other state (allocated) -> released. 248 return (Stmt && isa<CallExpr>(Stmt) && 249 (S && S->isReleased()) && (!SPrev || !SPrev->isReleased())); 250 } 251 252 inline bool isReallocFailedCheck(const RefState *S, const RefState *SPrev, 253 const Stmt *Stmt) { 254 // If the expression is not a call, and the state change is 255 // released -> allocated, it must be the realloc return value 256 // check. If we have to handle more cases here, it might be cleaner just 257 // to track this extra bit in the state itself. 258 return ((!Stmt || !isa<CallExpr>(Stmt)) && 259 (S && S->isAllocated()) && (SPrev && !SPrev->isAllocated())); 260 } 261 262 PathDiagnosticPiece *VisitNode(const ExplodedNode *N, 263 const ExplodedNode *PrevN, 264 BugReporterContext &BRC, 265 BugReport &BR); 266 267 PathDiagnosticPiece* getEndPath(BugReporterContext &BRC, 268 const ExplodedNode *EndPathNode, 269 BugReport &BR) { 270 if (!IsLeak) 271 return 0; 272 273 PathDiagnosticLocation L = 274 PathDiagnosticLocation::createEndOfPath(EndPathNode, 275 BRC.getSourceManager()); 276 // Do not add the statement itself as a range in case of leak. 277 return new PathDiagnosticEventPiece(L, BR.getDescription(), false); 278 } 279 280 private: 281 class StackHintGeneratorForReallocationFailed 282 : public StackHintGeneratorForSymbol { 283 public: 284 StackHintGeneratorForReallocationFailed(SymbolRef S, StringRef M) 285 : StackHintGeneratorForSymbol(S, M) {} 286 287 virtual std::string getMessageForArg(const Expr *ArgE, unsigned ArgIndex) { 288 SmallString<200> buf; 289 llvm::raw_svector_ostream os(buf); 290 291 os << "Reallocation of "; 292 // Printed parameters start at 1, not 0. 293 printOrdinal(++ArgIndex, os); 294 os << " parameter failed"; 295 296 return os.str(); 297 } 298 299 virtual std::string getMessageForReturn(const CallExpr *CallExpr) { 300 return "Reallocation of returned value failed"; 301 } 302 }; 303 }; 304}; 305} // end anonymous namespace 306 307typedef llvm::ImmutableMap<SymbolRef, RefState> RegionStateTy; 308typedef llvm::ImmutableMap<SymbolRef, ReallocPair > ReallocMap; 309class RegionState {}; 310class ReallocPairs {}; 311namespace clang { 312namespace ento { 313 template <> 314 struct ProgramStateTrait<RegionState> 315 : public ProgramStatePartialTrait<RegionStateTy> { 316 static void *GDMIndex() { static int x; return &x; } 317 }; 318 319 template <> 320 struct ProgramStateTrait<ReallocPairs> 321 : public ProgramStatePartialTrait<ReallocMap> { 322 static void *GDMIndex() { static int x; return &x; } 323 }; 324} 325} 326 327namespace { 328class StopTrackingCallback : public SymbolVisitor { 329 ProgramStateRef state; 330public: 331 StopTrackingCallback(ProgramStateRef st) : state(st) {} 332 ProgramStateRef getState() const { return state; } 333 334 bool VisitSymbol(SymbolRef sym) { 335 state = state->remove<RegionState>(sym); 336 return true; 337 } 338}; 339} // end anonymous namespace 340 341void MallocChecker::initIdentifierInfo(ASTContext &Ctx) const { 342 if (II_malloc) 343 return; 344 II_malloc = &Ctx.Idents.get("malloc"); 345 II_free = &Ctx.Idents.get("free"); 346 II_realloc = &Ctx.Idents.get("realloc"); 347 II_reallocf = &Ctx.Idents.get("reallocf"); 348 II_calloc = &Ctx.Idents.get("calloc"); 349 II_valloc = &Ctx.Idents.get("valloc"); 350 II_strdup = &Ctx.Idents.get("strdup"); 351 II_strndup = &Ctx.Idents.get("strndup"); 352} 353 354bool MallocChecker::isMemFunction(const FunctionDecl *FD, ASTContext &C) const { 355 if (isFreeFunction(FD, C)) 356 return true; 357 358 if (isAllocationFunction(FD, C)) 359 return true; 360 361 return false; 362} 363 364bool MallocChecker::isAllocationFunction(const FunctionDecl *FD, 365 ASTContext &C) const { 366 if (!FD) 367 return false; 368 369 IdentifierInfo *FunI = FD->getIdentifier(); 370 if (!FunI) 371 return false; 372 373 initIdentifierInfo(C); 374 375 if (FunI == II_malloc || FunI == II_realloc || 376 FunI == II_reallocf || FunI == II_calloc || FunI == II_valloc || 377 FunI == II_strdup || FunI == II_strndup) 378 return true; 379 380 if (Filter.CMallocOptimistic && FD->hasAttrs()) 381 for (specific_attr_iterator<OwnershipAttr> 382 i = FD->specific_attr_begin<OwnershipAttr>(), 383 e = FD->specific_attr_end<OwnershipAttr>(); 384 i != e; ++i) 385 if ((*i)->getOwnKind() == OwnershipAttr::Returns) 386 return true; 387 return false; 388} 389 390bool MallocChecker::isFreeFunction(const FunctionDecl *FD, ASTContext &C) const { 391 if (!FD) 392 return false; 393 394 IdentifierInfo *FunI = FD->getIdentifier(); 395 if (!FunI) 396 return false; 397 398 initIdentifierInfo(C); 399 400 if (FunI == II_free || FunI == II_realloc || FunI == II_reallocf) 401 return true; 402 403 if (Filter.CMallocOptimistic && FD->hasAttrs()) 404 for (specific_attr_iterator<OwnershipAttr> 405 i = FD->specific_attr_begin<OwnershipAttr>(), 406 e = FD->specific_attr_end<OwnershipAttr>(); 407 i != e; ++i) 408 if ((*i)->getOwnKind() == OwnershipAttr::Takes || 409 (*i)->getOwnKind() == OwnershipAttr::Holds) 410 return true; 411 return false; 412} 413 414void MallocChecker::checkPostStmt(const CallExpr *CE, CheckerContext &C) const { 415 const FunctionDecl *FD = C.getCalleeDecl(CE); 416 if (!FD) 417 return; 418 419 initIdentifierInfo(C.getASTContext()); 420 IdentifierInfo *FunI = FD->getIdentifier(); 421 if (!FunI) 422 return; 423 424 ProgramStateRef State = C.getState(); 425 if (FunI == II_malloc || FunI == II_valloc) { 426 if (CE->getNumArgs() < 1) 427 return; 428 State = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(), State); 429 } else if (FunI == II_realloc) { 430 State = ReallocMem(C, CE, false); 431 } else if (FunI == II_reallocf) { 432 State = ReallocMem(C, CE, true); 433 } else if (FunI == II_calloc) { 434 State = CallocMem(C, CE); 435 } else if (FunI == II_free) { 436 State = FreeMemAux(C, CE, C.getState(), 0, false); 437 } else if (FunI == II_strdup) { 438 State = MallocUpdateRefState(C, CE, State); 439 } else if (FunI == II_strndup) { 440 State = MallocUpdateRefState(C, CE, State); 441 } else if (Filter.CMallocOptimistic) { 442 // Check all the attributes, if there are any. 443 // There can be multiple of these attributes. 444 if (FD->hasAttrs()) 445 for (specific_attr_iterator<OwnershipAttr> 446 i = FD->specific_attr_begin<OwnershipAttr>(), 447 e = FD->specific_attr_end<OwnershipAttr>(); 448 i != e; ++i) { 449 switch ((*i)->getOwnKind()) { 450 case OwnershipAttr::Returns: 451 State = MallocMemReturnsAttr(C, CE, *i); 452 break; 453 case OwnershipAttr::Takes: 454 case OwnershipAttr::Holds: 455 State = FreeMemAttr(C, CE, *i); 456 break; 457 } 458 } 459 } 460 C.addTransition(State); 461} 462 463ProgramStateRef MallocChecker::MallocMemReturnsAttr(CheckerContext &C, 464 const CallExpr *CE, 465 const OwnershipAttr* Att) { 466 if (Att->getModule() != "malloc") 467 return 0; 468 469 OwnershipAttr::args_iterator I = Att->args_begin(), E = Att->args_end(); 470 if (I != E) { 471 return MallocMemAux(C, CE, CE->getArg(*I), UndefinedVal(), C.getState()); 472 } 473 return MallocMemAux(C, CE, UnknownVal(), UndefinedVal(), C.getState()); 474} 475 476ProgramStateRef MallocChecker::MallocMemAux(CheckerContext &C, 477 const CallExpr *CE, 478 SVal Size, SVal Init, 479 ProgramStateRef state) { 480 // Get the return value. 481 SVal retVal = state->getSVal(CE, C.getLocationContext()); 482 483 // We expect the malloc functions to return a pointer. 484 if (!isa<Loc>(retVal)) 485 return 0; 486 487 // Fill the region with the initialization value. 488 state = state->bindDefault(retVal, Init); 489 490 // Set the region's extent equal to the Size parameter. 491 const SymbolicRegion *R = 492 dyn_cast_or_null<SymbolicRegion>(retVal.getAsRegion()); 493 if (!R) 494 return 0; 495 if (isa<DefinedOrUnknownSVal>(Size)) { 496 SValBuilder &svalBuilder = C.getSValBuilder(); 497 DefinedOrUnknownSVal Extent = R->getExtent(svalBuilder); 498 DefinedOrUnknownSVal DefinedSize = cast<DefinedOrUnknownSVal>(Size); 499 DefinedOrUnknownSVal extentMatchesSize = 500 svalBuilder.evalEQ(state, Extent, DefinedSize); 501 502 state = state->assume(extentMatchesSize, true); 503 assert(state); 504 } 505 506 return MallocUpdateRefState(C, CE, state); 507} 508 509ProgramStateRef MallocChecker::MallocUpdateRefState(CheckerContext &C, 510 const CallExpr *CE, 511 ProgramStateRef state) { 512 // Get the return value. 513 SVal retVal = state->getSVal(CE, C.getLocationContext()); 514 515 // We expect the malloc functions to return a pointer. 516 if (!isa<Loc>(retVal)) 517 return 0; 518 519 SymbolRef Sym = retVal.getAsLocSymbol(); 520 assert(Sym); 521 522 // Set the symbol's state to Allocated. 523 return state->set<RegionState>(Sym, RefState::getAllocateUnchecked(CE)); 524 525} 526 527ProgramStateRef MallocChecker::FreeMemAttr(CheckerContext &C, 528 const CallExpr *CE, 529 const OwnershipAttr* Att) const { 530 if (Att->getModule() != "malloc") 531 return 0; 532 533 ProgramStateRef State = C.getState(); 534 535 for (OwnershipAttr::args_iterator I = Att->args_begin(), E = Att->args_end(); 536 I != E; ++I) { 537 ProgramStateRef StateI = FreeMemAux(C, CE, State, *I, 538 Att->getOwnKind() == OwnershipAttr::Holds); 539 if (StateI) 540 State = StateI; 541 } 542 return State; 543} 544 545ProgramStateRef MallocChecker::FreeMemAux(CheckerContext &C, 546 const CallExpr *CE, 547 ProgramStateRef state, 548 unsigned Num, 549 bool Hold) const { 550 if (CE->getNumArgs() < (Num + 1)) 551 return 0; 552 553 const Expr *ArgExpr = CE->getArg(Num); 554 SVal ArgVal = state->getSVal(ArgExpr, C.getLocationContext()); 555 if (!isa<DefinedOrUnknownSVal>(ArgVal)) 556 return 0; 557 DefinedOrUnknownSVal location = cast<DefinedOrUnknownSVal>(ArgVal); 558 559 // Check for null dereferences. 560 if (!isa<Loc>(location)) 561 return 0; 562 563 // The explicit NULL case, no operation is performed. 564 ProgramStateRef notNullState, nullState; 565 llvm::tie(notNullState, nullState) = state->assume(location); 566 if (nullState && !notNullState) 567 return 0; 568 569 // Unknown values could easily be okay 570 // Undefined values are handled elsewhere 571 if (ArgVal.isUnknownOrUndef()) 572 return 0; 573 574 const MemRegion *R = ArgVal.getAsRegion(); 575 576 // Nonlocs can't be freed, of course. 577 // Non-region locations (labels and fixed addresses) also shouldn't be freed. 578 if (!R) { 579 ReportBadFree(C, ArgVal, ArgExpr->getSourceRange()); 580 return 0; 581 } 582 583 R = R->StripCasts(); 584 585 // Blocks might show up as heap data, but should not be free()d 586 if (isa<BlockDataRegion>(R)) { 587 ReportBadFree(C, ArgVal, ArgExpr->getSourceRange()); 588 return 0; 589 } 590 591 const MemSpaceRegion *MS = R->getMemorySpace(); 592 593 // Parameters, locals, statics, and globals shouldn't be freed. 594 if (!(isa<UnknownSpaceRegion>(MS) || isa<HeapSpaceRegion>(MS))) { 595 // FIXME: at the time this code was written, malloc() regions were 596 // represented by conjured symbols, which are all in UnknownSpaceRegion. 597 // This means that there isn't actually anything from HeapSpaceRegion 598 // that should be freed, even though we allow it here. 599 // Of course, free() can work on memory allocated outside the current 600 // function, so UnknownSpaceRegion is always a possibility. 601 // False negatives are better than false positives. 602 603 ReportBadFree(C, ArgVal, ArgExpr->getSourceRange()); 604 return 0; 605 } 606 607 const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R); 608 // Various cases could lead to non-symbol values here. 609 // For now, ignore them. 610 if (!SR) 611 return 0; 612 613 SymbolRef Sym = SR->getSymbol(); 614 const RefState *RS = state->get<RegionState>(Sym); 615 616 // If the symbol has not been tracked, return. This is possible when free() is 617 // called on a pointer that does not get its pointee directly from malloc(). 618 // Full support of this requires inter-procedural analysis. 619 if (!RS) 620 return 0; 621 622 // Check double free. 623 if (RS->isReleased()) { 624 if (ExplodedNode *N = C.generateSink()) { 625 if (!BT_DoubleFree) 626 BT_DoubleFree.reset( 627 new BugType("Double free", "Memory Error")); 628 BugReport *R = new BugReport(*BT_DoubleFree, 629 "Attempt to free released memory", N); 630 R->addRange(ArgExpr->getSourceRange()); 631 R->markInteresting(Sym); 632 R->addVisitor(new MallocBugVisitor(Sym)); 633 C.EmitReport(R); 634 } 635 return 0; 636 } 637 638 // Normal free. 639 if (Hold) 640 return state->set<RegionState>(Sym, RefState::getRelinquished(CE)); 641 return state->set<RegionState>(Sym, RefState::getReleased(CE)); 642} 643 644bool MallocChecker::SummarizeValue(raw_ostream &os, SVal V) { 645 if (nonloc::ConcreteInt *IntVal = dyn_cast<nonloc::ConcreteInt>(&V)) 646 os << "an integer (" << IntVal->getValue() << ")"; 647 else if (loc::ConcreteInt *ConstAddr = dyn_cast<loc::ConcreteInt>(&V)) 648 os << "a constant address (" << ConstAddr->getValue() << ")"; 649 else if (loc::GotoLabel *Label = dyn_cast<loc::GotoLabel>(&V)) 650 os << "the address of the label '" << Label->getLabel()->getName() << "'"; 651 else 652 return false; 653 654 return true; 655} 656 657bool MallocChecker::SummarizeRegion(raw_ostream &os, 658 const MemRegion *MR) { 659 switch (MR->getKind()) { 660 case MemRegion::FunctionTextRegionKind: { 661 const FunctionDecl *FD = cast<FunctionTextRegion>(MR)->getDecl(); 662 if (FD) 663 os << "the address of the function '" << *FD << '\''; 664 else 665 os << "the address of a function"; 666 return true; 667 } 668 case MemRegion::BlockTextRegionKind: 669 os << "block text"; 670 return true; 671 case MemRegion::BlockDataRegionKind: 672 // FIXME: where the block came from? 673 os << "a block"; 674 return true; 675 default: { 676 const MemSpaceRegion *MS = MR->getMemorySpace(); 677 678 if (isa<StackLocalsSpaceRegion>(MS)) { 679 const VarRegion *VR = dyn_cast<VarRegion>(MR); 680 const VarDecl *VD; 681 if (VR) 682 VD = VR->getDecl(); 683 else 684 VD = NULL; 685 686 if (VD) 687 os << "the address of the local variable '" << VD->getName() << "'"; 688 else 689 os << "the address of a local stack variable"; 690 return true; 691 } 692 693 if (isa<StackArgumentsSpaceRegion>(MS)) { 694 const VarRegion *VR = dyn_cast<VarRegion>(MR); 695 const VarDecl *VD; 696 if (VR) 697 VD = VR->getDecl(); 698 else 699 VD = NULL; 700 701 if (VD) 702 os << "the address of the parameter '" << VD->getName() << "'"; 703 else 704 os << "the address of a parameter"; 705 return true; 706 } 707 708 if (isa<GlobalsSpaceRegion>(MS)) { 709 const VarRegion *VR = dyn_cast<VarRegion>(MR); 710 const VarDecl *VD; 711 if (VR) 712 VD = VR->getDecl(); 713 else 714 VD = NULL; 715 716 if (VD) { 717 if (VD->isStaticLocal()) 718 os << "the address of the static variable '" << VD->getName() << "'"; 719 else 720 os << "the address of the global variable '" << VD->getName() << "'"; 721 } else 722 os << "the address of a global variable"; 723 return true; 724 } 725 726 return false; 727 } 728 } 729} 730 731void MallocChecker::ReportBadFree(CheckerContext &C, SVal ArgVal, 732 SourceRange range) const { 733 if (ExplodedNode *N = C.generateSink()) { 734 if (!BT_BadFree) 735 BT_BadFree.reset(new BugType("Bad free", "Memory Error")); 736 737 SmallString<100> buf; 738 llvm::raw_svector_ostream os(buf); 739 740 const MemRegion *MR = ArgVal.getAsRegion(); 741 if (MR) { 742 while (const ElementRegion *ER = dyn_cast<ElementRegion>(MR)) 743 MR = ER->getSuperRegion(); 744 745 // Special case for alloca() 746 if (isa<AllocaRegion>(MR)) 747 os << "Argument to free() was allocated by alloca(), not malloc()"; 748 else { 749 os << "Argument to free() is "; 750 if (SummarizeRegion(os, MR)) 751 os << ", which is not memory allocated by malloc()"; 752 else 753 os << "not memory allocated by malloc()"; 754 } 755 } else { 756 os << "Argument to free() is "; 757 if (SummarizeValue(os, ArgVal)) 758 os << ", which is not memory allocated by malloc()"; 759 else 760 os << "not memory allocated by malloc()"; 761 } 762 763 BugReport *R = new BugReport(*BT_BadFree, os.str(), N); 764 R->markInteresting(MR); 765 R->addRange(range); 766 C.EmitReport(R); 767 } 768} 769 770ProgramStateRef MallocChecker::ReallocMem(CheckerContext &C, 771 const CallExpr *CE, 772 bool FreesOnFail) const { 773 if (CE->getNumArgs() < 2) 774 return 0; 775 776 ProgramStateRef state = C.getState(); 777 const Expr *arg0Expr = CE->getArg(0); 778 const LocationContext *LCtx = C.getLocationContext(); 779 SVal Arg0Val = state->getSVal(arg0Expr, LCtx); 780 if (!isa<DefinedOrUnknownSVal>(Arg0Val)) 781 return 0; 782 DefinedOrUnknownSVal arg0Val = cast<DefinedOrUnknownSVal>(Arg0Val); 783 784 SValBuilder &svalBuilder = C.getSValBuilder(); 785 786 DefinedOrUnknownSVal PtrEQ = 787 svalBuilder.evalEQ(state, arg0Val, svalBuilder.makeNull()); 788 789 // Get the size argument. If there is no size arg then give up. 790 const Expr *Arg1 = CE->getArg(1); 791 if (!Arg1) 792 return 0; 793 794 // Get the value of the size argument. 795 SVal Arg1ValG = state->getSVal(Arg1, LCtx); 796 if (!isa<DefinedOrUnknownSVal>(Arg1ValG)) 797 return 0; 798 DefinedOrUnknownSVal Arg1Val = cast<DefinedOrUnknownSVal>(Arg1ValG); 799 800 // Compare the size argument to 0. 801 DefinedOrUnknownSVal SizeZero = 802 svalBuilder.evalEQ(state, Arg1Val, 803 svalBuilder.makeIntValWithPtrWidth(0, false)); 804 805 ProgramStateRef StatePtrIsNull, StatePtrNotNull; 806 llvm::tie(StatePtrIsNull, StatePtrNotNull) = state->assume(PtrEQ); 807 ProgramStateRef StateSizeIsZero, StateSizeNotZero; 808 llvm::tie(StateSizeIsZero, StateSizeNotZero) = state->assume(SizeZero); 809 // We only assume exceptional states if they are definitely true; if the 810 // state is under-constrained, assume regular realloc behavior. 811 bool PrtIsNull = StatePtrIsNull && !StatePtrNotNull; 812 bool SizeIsZero = StateSizeIsZero && !StateSizeNotZero; 813 814 // If the ptr is NULL and the size is not 0, the call is equivalent to 815 // malloc(size). 816 if ( PrtIsNull && !SizeIsZero) { 817 ProgramStateRef stateMalloc = MallocMemAux(C, CE, CE->getArg(1), 818 UndefinedVal(), StatePtrIsNull); 819 return stateMalloc; 820 } 821 822 if (PrtIsNull && SizeIsZero) 823 return 0; 824 825 // Get the from and to pointer symbols as in toPtr = realloc(fromPtr, size). 826 assert(!PrtIsNull); 827 SymbolRef FromPtr = arg0Val.getAsSymbol(); 828 SVal RetVal = state->getSVal(CE, LCtx); 829 SymbolRef ToPtr = RetVal.getAsSymbol(); 830 if (!FromPtr || !ToPtr) 831 return 0; 832 833 // If the size is 0, free the memory. 834 if (SizeIsZero) 835 if (ProgramStateRef stateFree = FreeMemAux(C, CE, StateSizeIsZero,0,false)){ 836 // The semantics of the return value are: 837 // If size was equal to 0, either NULL or a pointer suitable to be passed 838 // to free() is returned. 839 stateFree = stateFree->set<ReallocPairs>(ToPtr, 840 ReallocPair(FromPtr, FreesOnFail)); 841 C.getSymbolManager().addSymbolDependency(ToPtr, FromPtr); 842 return stateFree; 843 } 844 845 // Default behavior. 846 if (ProgramStateRef stateFree = FreeMemAux(C, CE, state, 0, false)) { 847 // FIXME: We should copy the content of the original buffer. 848 ProgramStateRef stateRealloc = MallocMemAux(C, CE, CE->getArg(1), 849 UnknownVal(), stateFree); 850 if (!stateRealloc) 851 return 0; 852 stateRealloc = stateRealloc->set<ReallocPairs>(ToPtr, 853 ReallocPair(FromPtr, FreesOnFail)); 854 C.getSymbolManager().addSymbolDependency(ToPtr, FromPtr); 855 return stateRealloc; 856 } 857 return 0; 858} 859 860ProgramStateRef MallocChecker::CallocMem(CheckerContext &C, const CallExpr *CE){ 861 if (CE->getNumArgs() < 2) 862 return 0; 863 864 ProgramStateRef state = C.getState(); 865 SValBuilder &svalBuilder = C.getSValBuilder(); 866 const LocationContext *LCtx = C.getLocationContext(); 867 SVal count = state->getSVal(CE->getArg(0), LCtx); 868 SVal elementSize = state->getSVal(CE->getArg(1), LCtx); 869 SVal TotalSize = svalBuilder.evalBinOp(state, BO_Mul, count, elementSize, 870 svalBuilder.getContext().getSizeType()); 871 SVal zeroVal = svalBuilder.makeZeroVal(svalBuilder.getContext().CharTy); 872 873 return MallocMemAux(C, CE, TotalSize, zeroVal, state); 874} 875 876LeakInfo 877MallocChecker::getAllocationSite(const ExplodedNode *N, SymbolRef Sym, 878 CheckerContext &C) const { 879 const LocationContext *LeakContext = N->getLocationContext(); 880 // Walk the ExplodedGraph backwards and find the first node that referred to 881 // the tracked symbol. 882 const ExplodedNode *AllocNode = N; 883 const MemRegion *ReferenceRegion = 0; 884 885 while (N) { 886 ProgramStateRef State = N->getState(); 887 if (!State->get<RegionState>(Sym)) 888 break; 889 890 // Find the most recent expression bound to the symbol in the current 891 // context. 892 if (!ReferenceRegion) { 893 if (const MemRegion *MR = C.getLocationRegionIfPostStore(N)) { 894 SVal Val = State->getSVal(MR); 895 if (Val.getAsLocSymbol() == Sym) 896 ReferenceRegion = MR; 897 } 898 } 899 900 // Allocation node, is the last node in the current context in which the 901 // symbol was tracked. 902 if (N->getLocationContext() == LeakContext) 903 AllocNode = N; 904 N = N->pred_empty() ? NULL : *(N->pred_begin()); 905 } 906 907 ProgramPoint P = AllocNode->getLocation(); 908 const Stmt *AllocationStmt = 0; 909 if (isa<StmtPoint>(P)) 910 AllocationStmt = cast<StmtPoint>(P).getStmt(); 911 912 return LeakInfo(AllocationStmt, ReferenceRegion); 913} 914 915void MallocChecker::reportLeak(SymbolRef Sym, ExplodedNode *N, 916 CheckerContext &C) const { 917 assert(N); 918 if (!BT_Leak) { 919 BT_Leak.reset(new BugType("Memory leak", "Memory Error")); 920 // Leaks should not be reported if they are post-dominated by a sink: 921 // (1) Sinks are higher importance bugs. 922 // (2) NoReturnFunctionChecker uses sink nodes to represent paths ending 923 // with __noreturn functions such as assert() or exit(). We choose not 924 // to report leaks on such paths. 925 BT_Leak->setSuppressOnSink(true); 926 } 927 928 // Most bug reports are cached at the location where they occurred. 929 // With leaks, we want to unique them by the location where they were 930 // allocated, and only report a single path. 931 PathDiagnosticLocation LocUsedForUniqueing; 932 const Stmt *AllocStmt = 0; 933 const MemRegion *Region = 0; 934 llvm::tie(AllocStmt, Region) = getAllocationSite(N, Sym, C); 935 if (AllocStmt) 936 LocUsedForUniqueing = PathDiagnosticLocation::createBegin(AllocStmt, 937 C.getSourceManager(), N->getLocationContext()); 938 939 SmallString<200> buf; 940 llvm::raw_svector_ostream os(buf); 941 os << "Memory is never released; potential leak"; 942 if (Region) { 943 os << " of memory pointed to by '"; 944 Region->dumpPretty(os); 945 os <<'\''; 946 } 947 948 BugReport *R = new BugReport(*BT_Leak, os.str(), N, LocUsedForUniqueing); 949 R->markInteresting(Sym); 950 R->addVisitor(new MallocBugVisitor(Sym, true)); 951 C.EmitReport(R); 952} 953 954void MallocChecker::checkDeadSymbols(SymbolReaper &SymReaper, 955 CheckerContext &C) const 956{ 957 if (!SymReaper.hasDeadSymbols()) 958 return; 959 960 ProgramStateRef state = C.getState(); 961 RegionStateTy RS = state->get<RegionState>(); 962 RegionStateTy::Factory &F = state->get_context<RegionState>(); 963 964 bool generateReport = false; 965 llvm::SmallVector<SymbolRef, 2> Errors; 966 for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) { 967 if (SymReaper.isDead(I->first)) { 968 if (I->second.isAllocated()) { 969 generateReport = true; 970 Errors.push_back(I->first); 971 } 972 // Remove the dead symbol from the map. 973 RS = F.remove(RS, I->first); 974 975 } 976 } 977 978 // Cleanup the Realloc Pairs Map. 979 ReallocMap RP = state->get<ReallocPairs>(); 980 for (ReallocMap::iterator I = RP.begin(), E = RP.end(); I != E; ++I) { 981 if (SymReaper.isDead(I->first) || 982 SymReaper.isDead(I->second.ReallocatedSym)) { 983 state = state->remove<ReallocPairs>(I->first); 984 } 985 } 986 987 // Generate leak node. 988 static SimpleProgramPointTag Tag("MallocChecker : DeadSymbolsLeak"); 989 ExplodedNode *N = C.addTransition(C.getState(), C.getPredecessor(), &Tag); 990 991 if (generateReport) { 992 for (llvm::SmallVector<SymbolRef, 2>::iterator 993 I = Errors.begin(), E = Errors.end(); I != E; ++I) { 994 reportLeak(*I, N, C); 995 } 996 } 997 C.addTransition(state->set<RegionState>(RS), N); 998} 999 1000void MallocChecker::checkEndPath(CheckerContext &C) const { 1001 ProgramStateRef state = C.getState(); 1002 RegionStateTy M = state->get<RegionState>(); 1003 1004 // If inside inlined call, skip it. 1005 if (C.getLocationContext()->getParent() != 0) 1006 return; 1007 1008 for (RegionStateTy::iterator I = M.begin(), E = M.end(); I != E; ++I) { 1009 RefState RS = I->second; 1010 if (RS.isAllocated()) { 1011 ExplodedNode *N = C.addTransition(state); 1012 if (N) 1013 reportLeak(I->first, N, C); 1014 } 1015 } 1016} 1017 1018bool MallocChecker::checkEscape(SymbolRef Sym, const Stmt *S, 1019 CheckerContext &C) const { 1020 ProgramStateRef state = C.getState(); 1021 const RefState *RS = state->get<RegionState>(Sym); 1022 if (!RS) 1023 return false; 1024 1025 if (RS->isAllocated()) { 1026 state = state->set<RegionState>(Sym, RefState::getEscaped(S)); 1027 C.addTransition(state); 1028 return true; 1029 } 1030 return false; 1031} 1032 1033void MallocChecker::checkPreStmt(const CallExpr *CE, CheckerContext &C) const { 1034 // We will check for double free in the post visit. 1035 if (isFreeFunction(C.getCalleeDecl(CE), C.getASTContext())) 1036 return; 1037 1038 // Check use after free, when a freed pointer is passed to a call. 1039 ProgramStateRef State = C.getState(); 1040 for (CallExpr::const_arg_iterator I = CE->arg_begin(), 1041 E = CE->arg_end(); I != E; ++I) { 1042 const Expr *A = *I; 1043 if (A->getType().getTypePtr()->isAnyPointerType()) { 1044 SymbolRef Sym = State->getSVal(A, C.getLocationContext()).getAsSymbol(); 1045 if (!Sym) 1046 continue; 1047 if (checkUseAfterFree(Sym, C, A)) 1048 return; 1049 } 1050 } 1051} 1052 1053void MallocChecker::checkPreStmt(const ReturnStmt *S, CheckerContext &C) const { 1054 const Expr *E = S->getRetValue(); 1055 if (!E) 1056 return; 1057 1058 // Check if we are returning a symbol. 1059 SVal RetVal = C.getState()->getSVal(E, C.getLocationContext()); 1060 SymbolRef Sym = RetVal.getAsSymbol(); 1061 if (!Sym) 1062 // If we are returning a field of the allocated struct or an array element, 1063 // the callee could still free the memory. 1064 // TODO: This logic should be a part of generic symbol escape callback. 1065 if (const MemRegion *MR = RetVal.getAsRegion()) 1066 if (isa<FieldRegion>(MR) || isa<ElementRegion>(MR)) 1067 if (const SymbolicRegion *BMR = 1068 dyn_cast<SymbolicRegion>(MR->getBaseRegion())) 1069 Sym = BMR->getSymbol(); 1070 if (!Sym) 1071 return; 1072 1073 // Check if we are returning freed memory. 1074 if (checkUseAfterFree(Sym, C, E)) 1075 return; 1076 1077 // If this function body is not inlined, check if the symbol is escaping. 1078 if (C.getLocationContext()->getParent() == 0) 1079 checkEscape(Sym, E, C); 1080} 1081 1082// TODO: Blocks should be either inlined or should call invalidate regions 1083// upon invocation. After that's in place, special casing here will not be 1084// needed. 1085void MallocChecker::checkPostStmt(const BlockExpr *BE, 1086 CheckerContext &C) const { 1087 1088 // Scan the BlockDecRefExprs for any object the retain count checker 1089 // may be tracking. 1090 if (!BE->getBlockDecl()->hasCaptures()) 1091 return; 1092 1093 ProgramStateRef state = C.getState(); 1094 const BlockDataRegion *R = 1095 cast<BlockDataRegion>(state->getSVal(BE, 1096 C.getLocationContext()).getAsRegion()); 1097 1098 BlockDataRegion::referenced_vars_iterator I = R->referenced_vars_begin(), 1099 E = R->referenced_vars_end(); 1100 1101 if (I == E) 1102 return; 1103 1104 SmallVector<const MemRegion*, 10> Regions; 1105 const LocationContext *LC = C.getLocationContext(); 1106 MemRegionManager &MemMgr = C.getSValBuilder().getRegionManager(); 1107 1108 for ( ; I != E; ++I) { 1109 const VarRegion *VR = *I; 1110 if (VR->getSuperRegion() == R) { 1111 VR = MemMgr.getVarRegion(VR->getDecl(), LC); 1112 } 1113 Regions.push_back(VR); 1114 } 1115 1116 state = 1117 state->scanReachableSymbols<StopTrackingCallback>(Regions.data(), 1118 Regions.data() + Regions.size()).getState(); 1119 C.addTransition(state); 1120} 1121 1122bool MallocChecker::isReleased(SymbolRef Sym, CheckerContext &C) const { 1123 assert(Sym); 1124 const RefState *RS = C.getState()->get<RegionState>(Sym); 1125 return (RS && RS->isReleased()); 1126} 1127 1128bool MallocChecker::checkUseAfterFree(SymbolRef Sym, CheckerContext &C, 1129 const Stmt *S) const { 1130 if (isReleased(Sym, C)) { 1131 if (ExplodedNode *N = C.generateSink()) { 1132 if (!BT_UseFree) 1133 BT_UseFree.reset(new BugType("Use-after-free", "Memory Error")); 1134 1135 BugReport *R = new BugReport(*BT_UseFree, 1136 "Use of memory after it is freed",N); 1137 if (S) 1138 R->addRange(S->getSourceRange()); 1139 R->markInteresting(Sym); 1140 R->addVisitor(new MallocBugVisitor(Sym)); 1141 C.EmitReport(R); 1142 return true; 1143 } 1144 } 1145 return false; 1146} 1147 1148// Check if the location is a freed symbolic region. 1149void MallocChecker::checkLocation(SVal l, bool isLoad, const Stmt *S, 1150 CheckerContext &C) const { 1151 SymbolRef Sym = l.getLocSymbolInBase(); 1152 if (Sym) 1153 checkUseAfterFree(Sym, C, S); 1154} 1155 1156//===----------------------------------------------------------------------===// 1157// Check various ways a symbol can be invalidated. 1158// TODO: This logic (the next 3 functions) is copied/similar to the 1159// RetainRelease checker. We might want to factor this out. 1160//===----------------------------------------------------------------------===// 1161 1162// Stop tracking symbols when a value escapes as a result of checkBind. 1163// A value escapes in three possible cases: 1164// (1) we are binding to something that is not a memory region. 1165// (2) we are binding to a memregion that does not have stack storage 1166// (3) we are binding to a memregion with stack storage that the store 1167// does not understand. 1168void MallocChecker::checkBind(SVal loc, SVal val, const Stmt *S, 1169 CheckerContext &C) const { 1170 // Are we storing to something that causes the value to "escape"? 1171 bool escapes = true; 1172 ProgramStateRef state = C.getState(); 1173 1174 if (loc::MemRegionVal *regionLoc = dyn_cast<loc::MemRegionVal>(&loc)) { 1175 escapes = !regionLoc->getRegion()->hasStackStorage(); 1176 1177 if (!escapes) { 1178 // To test (3), generate a new state with the binding added. If it is 1179 // the same state, then it escapes (since the store cannot represent 1180 // the binding). 1181 // Do this only if we know that the store is not supposed to generate the 1182 // same state. 1183 SVal StoredVal = state->getSVal(regionLoc->getRegion()); 1184 if (StoredVal != val) 1185 escapes = (state == (state->bindLoc(*regionLoc, val))); 1186 } 1187 if (!escapes) { 1188 // Case 4: We do not currently model what happens when a symbol is 1189 // assigned to a struct field, so be conservative here and let the symbol 1190 // go. TODO: This could definitely be improved upon. 1191 escapes = !isa<VarRegion>(regionLoc->getRegion()); 1192 } 1193 } 1194 1195 // If our store can represent the binding and we aren't storing to something 1196 // that doesn't have local storage then just return and have the simulation 1197 // state continue as is. 1198 if (!escapes) 1199 return; 1200 1201 // Otherwise, find all symbols referenced by 'val' that we are tracking 1202 // and stop tracking them. 1203 state = state->scanReachableSymbols<StopTrackingCallback>(val).getState(); 1204 C.addTransition(state); 1205} 1206 1207// If a symbolic region is assumed to NULL (or another constant), stop tracking 1208// it - assuming that allocation failed on this path. 1209ProgramStateRef MallocChecker::evalAssume(ProgramStateRef state, 1210 SVal Cond, 1211 bool Assumption) const { 1212 RegionStateTy RS = state->get<RegionState>(); 1213 for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) { 1214 // If the symbol is assumed to NULL or another constant, this will 1215 // return an APSInt*. 1216 if (state->getSymVal(I.getKey())) 1217 state = state->remove<RegionState>(I.getKey()); 1218 } 1219 1220 // Realloc returns 0 when reallocation fails, which means that we should 1221 // restore the state of the pointer being reallocated. 1222 ReallocMap RP = state->get<ReallocPairs>(); 1223 for (ReallocMap::iterator I = RP.begin(), E = RP.end(); I != E; ++I) { 1224 // If the symbol is assumed to NULL or another constant, this will 1225 // return an APSInt*. 1226 if (state->getSymVal(I.getKey())) { 1227 SymbolRef ReallocSym = I.getData().ReallocatedSym; 1228 const RefState *RS = state->get<RegionState>(ReallocSym); 1229 if (RS) { 1230 if (RS->isReleased() && ! I.getData().IsFreeOnFailure) 1231 state = state->set<RegionState>(ReallocSym, 1232 RefState::getAllocateUnchecked(RS->getStmt())); 1233 } 1234 state = state->remove<ReallocPairs>(I.getKey()); 1235 } 1236 } 1237 1238 return state; 1239} 1240 1241// Check if the function is known to us. So, for example, we could 1242// conservatively assume it can free/reallocate it's pointer arguments. 1243// (We assume that the pointers cannot escape through calls to system 1244// functions not handled by this checker.) 1245bool MallocChecker::doesNotFreeMemory(const CallOrObjCMessage *Call, 1246 ProgramStateRef State) const { 1247 if (!Call) 1248 return false; 1249 1250 // For now, assume that any C++ call can free memory. 1251 // TODO: If we want to be more optimistic here, we'll need to make sure that 1252 // regions escape to C++ containers. They seem to do that even now, but for 1253 // mysterious reasons. 1254 if (Call->isCXXCall()) 1255 return false; 1256 1257 const Decl *D = Call->getDecl(); 1258 if (!D) 1259 return false; 1260 1261 ASTContext &ASTC = State->getStateManager().getContext(); 1262 1263 // If it's one of the allocation functions we can reason about, we model 1264 // its behavior explicitly. 1265 if (isa<FunctionDecl>(D) && isMemFunction(cast<FunctionDecl>(D), ASTC)) { 1266 return true; 1267 } 1268 1269 // If it's not a system call, assume it frees memory. 1270 SourceManager &SM = ASTC.getSourceManager(); 1271 if (!SM.isInSystemHeader(D->getLocation())) 1272 return false; 1273 1274 // Process C/ObjC functions. 1275 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 1276 // White list the system functions whose arguments escape. 1277 const IdentifierInfo *II = FD->getIdentifier(); 1278 if (!II) 1279 return true; 1280 StringRef FName = II->getName(); 1281 1282 // White list thread local storage. 1283 if (FName.equals("pthread_setspecific")) 1284 return false; 1285 1286 // White list the 'XXXNoCopy' ObjC functions. 1287 if (FName.endswith("NoCopy")) { 1288 // Look for the deallocator argument. We know that the memory ownership 1289 // is not transferred only if the deallocator argument is 1290 // 'kCFAllocatorNull'. 1291 for (unsigned i = 1; i < Call->getNumArgs(); ++i) { 1292 const Expr *ArgE = Call->getArg(i)->IgnoreParenCasts(); 1293 if (const DeclRefExpr *DE = dyn_cast<DeclRefExpr>(ArgE)) { 1294 StringRef DeallocatorName = DE->getFoundDecl()->getName(); 1295 if (DeallocatorName == "kCFAllocatorNull") 1296 return true; 1297 } 1298 } 1299 return false; 1300 } 1301 1302 // PR12101 1303 // Many CoreFoundation and CoreGraphics might allow a tracked object 1304 // to escape. 1305 if (Call->isCFCGAllowingEscape(FName)) 1306 return false; 1307 1308 // Associating streams with malloced buffers. The pointer can escape if 1309 // 'closefn' is specified (and if that function does free memory). 1310 // Currently, we do not inspect the 'closefn' function (PR12101). 1311 if (FName == "funopen") 1312 if (Call->getNumArgs() >= 4 && !Call->getArgSVal(4).isConstant(0)) 1313 return false; 1314 1315 // Do not warn on pointers passed to 'setbuf' when used with std streams, 1316 // these leaks might be intentional when setting the buffer for stdio. 1317 // http://stackoverflow.com/questions/2671151/who-frees-setvbuf-buffer 1318 if (FName == "setbuf" || FName =="setbuffer" || 1319 FName == "setlinebuf" || FName == "setvbuf") { 1320 if (Call->getNumArgs() >= 1) 1321 if (const DeclRefExpr *Arg = 1322 dyn_cast<DeclRefExpr>(Call->getArg(0)->IgnoreParenCasts())) 1323 if (const VarDecl *D = dyn_cast<VarDecl>(Arg->getDecl())) 1324 if (D->getCanonicalDecl()->getName().find("std") 1325 != StringRef::npos) 1326 return false; 1327 } 1328 1329 // A bunch of other functions, which take ownership of a pointer (See retain 1330 // release checker). Not all the parameters here are invalidated, but the 1331 // Malloc checker cannot differentiate between them. The right way of doing 1332 // this would be to implement a pointer escapes callback. 1333 if (FName == "CVPixelBufferCreateWithBytes" || 1334 FName == "CGBitmapContextCreateWithData" || 1335 FName == "CVPixelBufferCreateWithPlanarBytes" || 1336 FName == "OSAtomicEnqueue") { 1337 return false; 1338 } 1339 1340 // Whitelist NSXXInsertXX, for example NSMapInsertIfAbsent, since they can 1341 // be deallocated by NSMapRemove. 1342 if (FName.startswith("NS") && (FName.find("Insert") != StringRef::npos)) 1343 return false; 1344 1345 // If the call has a callback as an argument, assume the memory 1346 // can be freed. 1347 if (Call->hasNonZeroCallbackArg()) 1348 return false; 1349 1350 // Otherwise, assume that the function does not free memory. 1351 // Most system calls, do not free the memory. 1352 return true; 1353 1354 // Process ObjC functions. 1355 } else if (const ObjCMethodDecl * ObjCD = dyn_cast<ObjCMethodDecl>(D)) { 1356 Selector S = ObjCD->getSelector(); 1357 1358 // White list the ObjC functions which do free memory. 1359 // - Anything containing 'freeWhenDone' param set to 1. 1360 // Ex: dataWithBytesNoCopy:length:freeWhenDone. 1361 for (unsigned i = 1; i < S.getNumArgs(); ++i) { 1362 if (S.getNameForSlot(i).equals("freeWhenDone")) { 1363 if (Call->getArgSVal(i).isConstant(1)) 1364 return false; 1365 else 1366 return true; 1367 } 1368 } 1369 1370 // If the first selector ends with NoCopy, assume that the ownership is 1371 // transferred as well. 1372 // Ex: [NSData dataWithBytesNoCopy:bytes length:10]; 1373 if (S.getNameForSlot(0).endswith("NoCopy")) { 1374 return false; 1375 } 1376 1377 // If the call has a callback as an argument, assume the memory 1378 // can be freed. 1379 if (Call->hasNonZeroCallbackArg()) 1380 return false; 1381 1382 // Otherwise, assume that the function does not free memory. 1383 // Most system calls, do not free the memory. 1384 return true; 1385 } 1386 1387 // Otherwise, assume that the function can free memory. 1388 return false; 1389 1390} 1391 1392// If the symbol we are tracking is invalidated, but not explicitly (ex: the &p 1393// escapes, when we are tracking p), do not track the symbol as we cannot reason 1394// about it anymore. 1395ProgramStateRef 1396MallocChecker::checkRegionChanges(ProgramStateRef State, 1397 const StoreManager::InvalidatedSymbols *invalidated, 1398 ArrayRef<const MemRegion *> ExplicitRegions, 1399 ArrayRef<const MemRegion *> Regions, 1400 const CallOrObjCMessage *Call) const { 1401 if (!invalidated || invalidated->empty()) 1402 return State; 1403 llvm::SmallPtrSet<SymbolRef, 8> WhitelistedSymbols; 1404 1405 // If it's a call which might free or reallocate memory, we assume that all 1406 // regions (explicit and implicit) escaped. 1407 1408 // Otherwise, whitelist explicit pointers; we still can track them. 1409 if (!Call || doesNotFreeMemory(Call, State)) { 1410 for (ArrayRef<const MemRegion *>::iterator I = ExplicitRegions.begin(), 1411 E = ExplicitRegions.end(); I != E; ++I) { 1412 if (const SymbolicRegion *R = (*I)->StripCasts()->getAs<SymbolicRegion>()) 1413 WhitelistedSymbols.insert(R->getSymbol()); 1414 } 1415 } 1416 1417 for (StoreManager::InvalidatedSymbols::const_iterator I=invalidated->begin(), 1418 E = invalidated->end(); I!=E; ++I) { 1419 SymbolRef sym = *I; 1420 if (WhitelistedSymbols.count(sym)) 1421 continue; 1422 // The symbol escaped. 1423 if (const RefState *RS = State->get<RegionState>(sym)) 1424 State = State->set<RegionState>(sym, RefState::getEscaped(RS->getStmt())); 1425 } 1426 return State; 1427} 1428 1429static SymbolRef findFailedReallocSymbol(ProgramStateRef currState, 1430 ProgramStateRef prevState) { 1431 ReallocMap currMap = currState->get<ReallocPairs>(); 1432 ReallocMap prevMap = prevState->get<ReallocPairs>(); 1433 1434 for (ReallocMap::iterator I = prevMap.begin(), E = prevMap.end(); 1435 I != E; ++I) { 1436 SymbolRef sym = I.getKey(); 1437 if (!currMap.lookup(sym)) 1438 return sym; 1439 } 1440 1441 return NULL; 1442} 1443 1444PathDiagnosticPiece * 1445MallocChecker::MallocBugVisitor::VisitNode(const ExplodedNode *N, 1446 const ExplodedNode *PrevN, 1447 BugReporterContext &BRC, 1448 BugReport &BR) { 1449 ProgramStateRef state = N->getState(); 1450 ProgramStateRef statePrev = PrevN->getState(); 1451 1452 const RefState *RS = state->get<RegionState>(Sym); 1453 const RefState *RSPrev = statePrev->get<RegionState>(Sym); 1454 if (!RS && !RSPrev) 1455 return 0; 1456 1457 const Stmt *S = 0; 1458 const char *Msg = 0; 1459 StackHintGeneratorForSymbol *StackHint = 0; 1460 1461 // Retrieve the associated statement. 1462 ProgramPoint ProgLoc = N->getLocation(); 1463 if (isa<StmtPoint>(ProgLoc)) 1464 S = cast<StmtPoint>(ProgLoc).getStmt(); 1465 // If an assumption was made on a branch, it should be caught 1466 // here by looking at the state transition. 1467 if (isa<BlockEdge>(ProgLoc)) { 1468 const CFGBlock *srcBlk = cast<BlockEdge>(ProgLoc).getSrc(); 1469 S = srcBlk->getTerminator(); 1470 } 1471 if (!S) 1472 return 0; 1473 1474 // Find out if this is an interesting point and what is the kind. 1475 if (Mode == Normal) { 1476 if (isAllocated(RS, RSPrev, S)) { 1477 Msg = "Memory is allocated"; 1478 StackHint = new StackHintGeneratorForSymbol(Sym, 1479 "Returned allocated memory"); 1480 } else if (isReleased(RS, RSPrev, S)) { 1481 Msg = "Memory is released"; 1482 StackHint = new StackHintGeneratorForSymbol(Sym, 1483 "Returned released memory"); 1484 } else if (isReallocFailedCheck(RS, RSPrev, S)) { 1485 Mode = ReallocationFailed; 1486 Msg = "Reallocation failed"; 1487 StackHint = new StackHintGeneratorForReallocationFailed(Sym, 1488 "Reallocation failed"); 1489 1490 if (SymbolRef sym = findFailedReallocSymbol(state, statePrev)) { 1491 // Is it possible to fail two reallocs WITHOUT testing in between? 1492 assert((!FailedReallocSymbol || FailedReallocSymbol == sym) && 1493 "We only support one failed realloc at a time."); 1494 BR.markInteresting(sym); 1495 FailedReallocSymbol = sym; 1496 } 1497 } 1498 1499 // We are in a special mode if a reallocation failed later in the path. 1500 } else if (Mode == ReallocationFailed) { 1501 assert(FailedReallocSymbol && "No symbol to look for."); 1502 1503 // Is this is the first appearance of the reallocated symbol? 1504 if (!statePrev->get<RegionState>(FailedReallocSymbol)) { 1505 // If we ever hit this assert, that means BugReporter has decided to skip 1506 // node pairs or visit them out of order. 1507 assert(state->get<RegionState>(FailedReallocSymbol) && 1508 "Missed the reallocation point"); 1509 1510 // We're at the reallocation point. 1511 Msg = "Attempt to reallocate memory"; 1512 StackHint = new StackHintGeneratorForSymbol(Sym, 1513 "Returned reallocated memory"); 1514 FailedReallocSymbol = NULL; 1515 Mode = Normal; 1516 } 1517 } 1518 1519 if (!Msg) 1520 return 0; 1521 assert(StackHint); 1522 1523 // Generate the extra diagnostic. 1524 PathDiagnosticLocation Pos(S, BRC.getSourceManager(), 1525 N->getLocationContext()); 1526 return new PathDiagnosticEventPiece(Pos, Msg, true, StackHint); 1527} 1528 1529void MallocChecker::printState(raw_ostream &Out, ProgramStateRef State, 1530 const char *NL, const char *Sep) const { 1531 1532 RegionStateTy RS = State->get<RegionState>(); 1533 1534 if (!RS.isEmpty()) 1535 Out << "Has Malloc data" << NL; 1536} 1537 1538#define REGISTER_CHECKER(name) \ 1539void ento::register##name(CheckerManager &mgr) {\ 1540 registerCStringCheckerBasic(mgr); \ 1541 mgr.registerChecker<MallocChecker>()->Filter.C##name = true;\ 1542} 1543 1544REGISTER_CHECKER(MallocPessimistic) 1545REGISTER_CHECKER(MallocOptimistic) 1546