MallocChecker.cpp revision e17fdb2d5dbf0ffefd417587003eebbe5baf5984
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 481 // Bind the return value to the symbolic value from the heap region. 482 // TODO: We could rewrite post visit to eval call; 'malloc' does not have 483 // side effects other than what we model here. 484 unsigned Count = C.getCurrentBlockCount(); 485 SValBuilder &svalBuilder = C.getSValBuilder(); 486 const LocationContext *LCtx = C.getPredecessor()->getLocationContext(); 487 DefinedSVal RetVal = 488 cast<DefinedSVal>(svalBuilder.getConjuredHeapSymbolVal(CE, LCtx, Count)); 489 state = state->BindExpr(CE, C.getLocationContext(), RetVal); 490 491 // We expect the malloc functions to return a pointer. 492 if (!isa<Loc>(RetVal)) 493 return 0; 494 495 // Fill the region with the initialization value. 496 state = state->bindDefault(RetVal, Init); 497 498 // Set the region's extent equal to the Size parameter. 499 const SymbolicRegion *R = 500 dyn_cast_or_null<SymbolicRegion>(RetVal.getAsRegion()); 501 if (!R) 502 return 0; 503 if (isa<DefinedOrUnknownSVal>(Size)) { 504 SValBuilder &svalBuilder = C.getSValBuilder(); 505 DefinedOrUnknownSVal Extent = R->getExtent(svalBuilder); 506 DefinedOrUnknownSVal DefinedSize = cast<DefinedOrUnknownSVal>(Size); 507 DefinedOrUnknownSVal extentMatchesSize = 508 svalBuilder.evalEQ(state, Extent, DefinedSize); 509 510 state = state->assume(extentMatchesSize, true); 511 assert(state); 512 } 513 514 return MallocUpdateRefState(C, CE, state); 515} 516 517ProgramStateRef MallocChecker::MallocUpdateRefState(CheckerContext &C, 518 const CallExpr *CE, 519 ProgramStateRef state) { 520 // Get the return value. 521 SVal retVal = state->getSVal(CE, C.getLocationContext()); 522 523 // We expect the malloc functions to return a pointer. 524 if (!isa<Loc>(retVal)) 525 return 0; 526 527 SymbolRef Sym = retVal.getAsLocSymbol(); 528 assert(Sym); 529 530 // Set the symbol's state to Allocated. 531 return state->set<RegionState>(Sym, RefState::getAllocateUnchecked(CE)); 532 533} 534 535ProgramStateRef MallocChecker::FreeMemAttr(CheckerContext &C, 536 const CallExpr *CE, 537 const OwnershipAttr* Att) const { 538 if (Att->getModule() != "malloc") 539 return 0; 540 541 ProgramStateRef State = C.getState(); 542 543 for (OwnershipAttr::args_iterator I = Att->args_begin(), E = Att->args_end(); 544 I != E; ++I) { 545 ProgramStateRef StateI = FreeMemAux(C, CE, State, *I, 546 Att->getOwnKind() == OwnershipAttr::Holds); 547 if (StateI) 548 State = StateI; 549 } 550 return State; 551} 552 553ProgramStateRef MallocChecker::FreeMemAux(CheckerContext &C, 554 const CallExpr *CE, 555 ProgramStateRef state, 556 unsigned Num, 557 bool Hold) const { 558 if (CE->getNumArgs() < (Num + 1)) 559 return 0; 560 561 const Expr *ArgExpr = CE->getArg(Num); 562 SVal ArgVal = state->getSVal(ArgExpr, C.getLocationContext()); 563 if (!isa<DefinedOrUnknownSVal>(ArgVal)) 564 return 0; 565 DefinedOrUnknownSVal location = cast<DefinedOrUnknownSVal>(ArgVal); 566 567 // Check for null dereferences. 568 if (!isa<Loc>(location)) 569 return 0; 570 571 // The explicit NULL case, no operation is performed. 572 ProgramStateRef notNullState, nullState; 573 llvm::tie(notNullState, nullState) = state->assume(location); 574 if (nullState && !notNullState) 575 return 0; 576 577 // Unknown values could easily be okay 578 // Undefined values are handled elsewhere 579 if (ArgVal.isUnknownOrUndef()) 580 return 0; 581 582 const MemRegion *R = ArgVal.getAsRegion(); 583 584 // Nonlocs can't be freed, of course. 585 // Non-region locations (labels and fixed addresses) also shouldn't be freed. 586 if (!R) { 587 ReportBadFree(C, ArgVal, ArgExpr->getSourceRange()); 588 return 0; 589 } 590 591 R = R->StripCasts(); 592 593 // Blocks might show up as heap data, but should not be free()d 594 if (isa<BlockDataRegion>(R)) { 595 ReportBadFree(C, ArgVal, ArgExpr->getSourceRange()); 596 return 0; 597 } 598 599 const MemSpaceRegion *MS = R->getMemorySpace(); 600 601 // Parameters, locals, statics, and globals shouldn't be freed. 602 if (!(isa<UnknownSpaceRegion>(MS) || isa<HeapSpaceRegion>(MS))) { 603 // FIXME: at the time this code was written, malloc() regions were 604 // represented by conjured symbols, which are all in UnknownSpaceRegion. 605 // This means that there isn't actually anything from HeapSpaceRegion 606 // that should be freed, even though we allow it here. 607 // Of course, free() can work on memory allocated outside the current 608 // function, so UnknownSpaceRegion is always a possibility. 609 // False negatives are better than false positives. 610 611 ReportBadFree(C, ArgVal, ArgExpr->getSourceRange()); 612 return 0; 613 } 614 615 const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R); 616 // Various cases could lead to non-symbol values here. 617 // For now, ignore them. 618 if (!SR) 619 return 0; 620 621 SymbolRef Sym = SR->getSymbol(); 622 const RefState *RS = state->get<RegionState>(Sym); 623 624 // If the symbol has not been tracked, return. This is possible when free() is 625 // called on a pointer that does not get its pointee directly from malloc(). 626 // Full support of this requires inter-procedural analysis. 627 if (!RS) 628 return 0; 629 630 // Check double free. 631 if (RS->isReleased()) { 632 if (ExplodedNode *N = C.generateSink()) { 633 if (!BT_DoubleFree) 634 BT_DoubleFree.reset( 635 new BugType("Double free", "Memory Error")); 636 BugReport *R = new BugReport(*BT_DoubleFree, 637 "Attempt to free released memory", N); 638 R->addRange(ArgExpr->getSourceRange()); 639 R->markInteresting(Sym); 640 R->addVisitor(new MallocBugVisitor(Sym)); 641 C.EmitReport(R); 642 } 643 return 0; 644 } 645 646 // Normal free. 647 if (Hold) 648 return state->set<RegionState>(Sym, RefState::getRelinquished(CE)); 649 return state->set<RegionState>(Sym, RefState::getReleased(CE)); 650} 651 652bool MallocChecker::SummarizeValue(raw_ostream &os, SVal V) { 653 if (nonloc::ConcreteInt *IntVal = dyn_cast<nonloc::ConcreteInt>(&V)) 654 os << "an integer (" << IntVal->getValue() << ")"; 655 else if (loc::ConcreteInt *ConstAddr = dyn_cast<loc::ConcreteInt>(&V)) 656 os << "a constant address (" << ConstAddr->getValue() << ")"; 657 else if (loc::GotoLabel *Label = dyn_cast<loc::GotoLabel>(&V)) 658 os << "the address of the label '" << Label->getLabel()->getName() << "'"; 659 else 660 return false; 661 662 return true; 663} 664 665bool MallocChecker::SummarizeRegion(raw_ostream &os, 666 const MemRegion *MR) { 667 switch (MR->getKind()) { 668 case MemRegion::FunctionTextRegionKind: { 669 const FunctionDecl *FD = cast<FunctionTextRegion>(MR)->getDecl(); 670 if (FD) 671 os << "the address of the function '" << *FD << '\''; 672 else 673 os << "the address of a function"; 674 return true; 675 } 676 case MemRegion::BlockTextRegionKind: 677 os << "block text"; 678 return true; 679 case MemRegion::BlockDataRegionKind: 680 // FIXME: where the block came from? 681 os << "a block"; 682 return true; 683 default: { 684 const MemSpaceRegion *MS = MR->getMemorySpace(); 685 686 if (isa<StackLocalsSpaceRegion>(MS)) { 687 const VarRegion *VR = dyn_cast<VarRegion>(MR); 688 const VarDecl *VD; 689 if (VR) 690 VD = VR->getDecl(); 691 else 692 VD = NULL; 693 694 if (VD) 695 os << "the address of the local variable '" << VD->getName() << "'"; 696 else 697 os << "the address of a local stack variable"; 698 return true; 699 } 700 701 if (isa<StackArgumentsSpaceRegion>(MS)) { 702 const VarRegion *VR = dyn_cast<VarRegion>(MR); 703 const VarDecl *VD; 704 if (VR) 705 VD = VR->getDecl(); 706 else 707 VD = NULL; 708 709 if (VD) 710 os << "the address of the parameter '" << VD->getName() << "'"; 711 else 712 os << "the address of a parameter"; 713 return true; 714 } 715 716 if (isa<GlobalsSpaceRegion>(MS)) { 717 const VarRegion *VR = dyn_cast<VarRegion>(MR); 718 const VarDecl *VD; 719 if (VR) 720 VD = VR->getDecl(); 721 else 722 VD = NULL; 723 724 if (VD) { 725 if (VD->isStaticLocal()) 726 os << "the address of the static variable '" << VD->getName() << "'"; 727 else 728 os << "the address of the global variable '" << VD->getName() << "'"; 729 } else 730 os << "the address of a global variable"; 731 return true; 732 } 733 734 return false; 735 } 736 } 737} 738 739void MallocChecker::ReportBadFree(CheckerContext &C, SVal ArgVal, 740 SourceRange range) const { 741 if (ExplodedNode *N = C.generateSink()) { 742 if (!BT_BadFree) 743 BT_BadFree.reset(new BugType("Bad free", "Memory Error")); 744 745 SmallString<100> buf; 746 llvm::raw_svector_ostream os(buf); 747 748 const MemRegion *MR = ArgVal.getAsRegion(); 749 if (MR) { 750 while (const ElementRegion *ER = dyn_cast<ElementRegion>(MR)) 751 MR = ER->getSuperRegion(); 752 753 // Special case for alloca() 754 if (isa<AllocaRegion>(MR)) 755 os << "Argument to free() was allocated by alloca(), not malloc()"; 756 else { 757 os << "Argument to free() is "; 758 if (SummarizeRegion(os, MR)) 759 os << ", which is not memory allocated by malloc()"; 760 else 761 os << "not memory allocated by malloc()"; 762 } 763 } else { 764 os << "Argument to free() is "; 765 if (SummarizeValue(os, ArgVal)) 766 os << ", which is not memory allocated by malloc()"; 767 else 768 os << "not memory allocated by malloc()"; 769 } 770 771 BugReport *R = new BugReport(*BT_BadFree, os.str(), N); 772 R->markInteresting(MR); 773 R->addRange(range); 774 C.EmitReport(R); 775 } 776} 777 778ProgramStateRef MallocChecker::ReallocMem(CheckerContext &C, 779 const CallExpr *CE, 780 bool FreesOnFail) const { 781 if (CE->getNumArgs() < 2) 782 return 0; 783 784 ProgramStateRef state = C.getState(); 785 const Expr *arg0Expr = CE->getArg(0); 786 const LocationContext *LCtx = C.getLocationContext(); 787 SVal Arg0Val = state->getSVal(arg0Expr, LCtx); 788 if (!isa<DefinedOrUnknownSVal>(Arg0Val)) 789 return 0; 790 DefinedOrUnknownSVal arg0Val = cast<DefinedOrUnknownSVal>(Arg0Val); 791 792 SValBuilder &svalBuilder = C.getSValBuilder(); 793 794 DefinedOrUnknownSVal PtrEQ = 795 svalBuilder.evalEQ(state, arg0Val, svalBuilder.makeNull()); 796 797 // Get the size argument. If there is no size arg then give up. 798 const Expr *Arg1 = CE->getArg(1); 799 if (!Arg1) 800 return 0; 801 802 // Get the value of the size argument. 803 SVal Arg1ValG = state->getSVal(Arg1, LCtx); 804 if (!isa<DefinedOrUnknownSVal>(Arg1ValG)) 805 return 0; 806 DefinedOrUnknownSVal Arg1Val = cast<DefinedOrUnknownSVal>(Arg1ValG); 807 808 // Compare the size argument to 0. 809 DefinedOrUnknownSVal SizeZero = 810 svalBuilder.evalEQ(state, Arg1Val, 811 svalBuilder.makeIntValWithPtrWidth(0, false)); 812 813 ProgramStateRef StatePtrIsNull, StatePtrNotNull; 814 llvm::tie(StatePtrIsNull, StatePtrNotNull) = state->assume(PtrEQ); 815 ProgramStateRef StateSizeIsZero, StateSizeNotZero; 816 llvm::tie(StateSizeIsZero, StateSizeNotZero) = state->assume(SizeZero); 817 // We only assume exceptional states if they are definitely true; if the 818 // state is under-constrained, assume regular realloc behavior. 819 bool PrtIsNull = StatePtrIsNull && !StatePtrNotNull; 820 bool SizeIsZero = StateSizeIsZero && !StateSizeNotZero; 821 822 // If the ptr is NULL and the size is not 0, the call is equivalent to 823 // malloc(size). 824 if ( PrtIsNull && !SizeIsZero) { 825 ProgramStateRef stateMalloc = MallocMemAux(C, CE, CE->getArg(1), 826 UndefinedVal(), StatePtrIsNull); 827 return stateMalloc; 828 } 829 830 if (PrtIsNull && SizeIsZero) 831 return 0; 832 833 // Get the from and to pointer symbols as in toPtr = realloc(fromPtr, size). 834 assert(!PrtIsNull); 835 SymbolRef FromPtr = arg0Val.getAsSymbol(); 836 SVal RetVal = state->getSVal(CE, LCtx); 837 SymbolRef ToPtr = RetVal.getAsSymbol(); 838 if (!FromPtr || !ToPtr) 839 return 0; 840 841 // If the size is 0, free the memory. 842 if (SizeIsZero) 843 if (ProgramStateRef stateFree = FreeMemAux(C, CE, StateSizeIsZero,0,false)){ 844 // The semantics of the return value are: 845 // If size was equal to 0, either NULL or a pointer suitable to be passed 846 // to free() is returned. 847 stateFree = stateFree->set<ReallocPairs>(ToPtr, 848 ReallocPair(FromPtr, FreesOnFail)); 849 C.getSymbolManager().addSymbolDependency(ToPtr, FromPtr); 850 return stateFree; 851 } 852 853 // Default behavior. 854 if (ProgramStateRef stateFree = FreeMemAux(C, CE, state, 0, false)) { 855 // FIXME: We should copy the content of the original buffer. 856 ProgramStateRef stateRealloc = MallocMemAux(C, CE, CE->getArg(1), 857 UnknownVal(), stateFree); 858 if (!stateRealloc) 859 return 0; 860 stateRealloc = stateRealloc->set<ReallocPairs>(ToPtr, 861 ReallocPair(FromPtr, FreesOnFail)); 862 C.getSymbolManager().addSymbolDependency(ToPtr, FromPtr); 863 return stateRealloc; 864 } 865 return 0; 866} 867 868ProgramStateRef MallocChecker::CallocMem(CheckerContext &C, const CallExpr *CE){ 869 if (CE->getNumArgs() < 2) 870 return 0; 871 872 ProgramStateRef state = C.getState(); 873 SValBuilder &svalBuilder = C.getSValBuilder(); 874 const LocationContext *LCtx = C.getLocationContext(); 875 SVal count = state->getSVal(CE->getArg(0), LCtx); 876 SVal elementSize = state->getSVal(CE->getArg(1), LCtx); 877 SVal TotalSize = svalBuilder.evalBinOp(state, BO_Mul, count, elementSize, 878 svalBuilder.getContext().getSizeType()); 879 SVal zeroVal = svalBuilder.makeZeroVal(svalBuilder.getContext().CharTy); 880 881 return MallocMemAux(C, CE, TotalSize, zeroVal, state); 882} 883 884LeakInfo 885MallocChecker::getAllocationSite(const ExplodedNode *N, SymbolRef Sym, 886 CheckerContext &C) const { 887 const LocationContext *LeakContext = N->getLocationContext(); 888 // Walk the ExplodedGraph backwards and find the first node that referred to 889 // the tracked symbol. 890 const ExplodedNode *AllocNode = N; 891 const MemRegion *ReferenceRegion = 0; 892 893 while (N) { 894 ProgramStateRef State = N->getState(); 895 if (!State->get<RegionState>(Sym)) 896 break; 897 898 // Find the most recent expression bound to the symbol in the current 899 // context. 900 if (!ReferenceRegion) { 901 if (const MemRegion *MR = C.getLocationRegionIfPostStore(N)) { 902 SVal Val = State->getSVal(MR); 903 if (Val.getAsLocSymbol() == Sym) 904 ReferenceRegion = MR; 905 } 906 } 907 908 // Allocation node, is the last node in the current context in which the 909 // symbol was tracked. 910 if (N->getLocationContext() == LeakContext) 911 AllocNode = N; 912 N = N->pred_empty() ? NULL : *(N->pred_begin()); 913 } 914 915 ProgramPoint P = AllocNode->getLocation(); 916 const Stmt *AllocationStmt = 0; 917 if (isa<StmtPoint>(P)) 918 AllocationStmt = cast<StmtPoint>(P).getStmt(); 919 920 return LeakInfo(AllocationStmt, ReferenceRegion); 921} 922 923void MallocChecker::reportLeak(SymbolRef Sym, ExplodedNode *N, 924 CheckerContext &C) const { 925 assert(N); 926 if (!BT_Leak) { 927 BT_Leak.reset(new BugType("Memory leak", "Memory Error")); 928 // Leaks should not be reported if they are post-dominated by a sink: 929 // (1) Sinks are higher importance bugs. 930 // (2) NoReturnFunctionChecker uses sink nodes to represent paths ending 931 // with __noreturn functions such as assert() or exit(). We choose not 932 // to report leaks on such paths. 933 BT_Leak->setSuppressOnSink(true); 934 } 935 936 // Most bug reports are cached at the location where they occurred. 937 // With leaks, we want to unique them by the location where they were 938 // allocated, and only report a single path. 939 PathDiagnosticLocation LocUsedForUniqueing; 940 const Stmt *AllocStmt = 0; 941 const MemRegion *Region = 0; 942 llvm::tie(AllocStmt, Region) = getAllocationSite(N, Sym, C); 943 if (AllocStmt) 944 LocUsedForUniqueing = PathDiagnosticLocation::createBegin(AllocStmt, 945 C.getSourceManager(), N->getLocationContext()); 946 947 SmallString<200> buf; 948 llvm::raw_svector_ostream os(buf); 949 os << "Memory is never released; potential leak"; 950 if (Region) { 951 os << " of memory pointed to by '"; 952 Region->dumpPretty(os); 953 os <<'\''; 954 } 955 956 BugReport *R = new BugReport(*BT_Leak, os.str(), N, LocUsedForUniqueing); 957 R->markInteresting(Sym); 958 R->addVisitor(new MallocBugVisitor(Sym, true)); 959 C.EmitReport(R); 960} 961 962void MallocChecker::checkDeadSymbols(SymbolReaper &SymReaper, 963 CheckerContext &C) const 964{ 965 if (!SymReaper.hasDeadSymbols()) 966 return; 967 968 ProgramStateRef state = C.getState(); 969 RegionStateTy RS = state->get<RegionState>(); 970 RegionStateTy::Factory &F = state->get_context<RegionState>(); 971 972 bool generateReport = false; 973 llvm::SmallVector<SymbolRef, 2> Errors; 974 for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) { 975 if (SymReaper.isDead(I->first)) { 976 if (I->second.isAllocated()) { 977 generateReport = true; 978 Errors.push_back(I->first); 979 } 980 // Remove the dead symbol from the map. 981 RS = F.remove(RS, I->first); 982 983 } 984 } 985 986 // Cleanup the Realloc Pairs Map. 987 ReallocMap RP = state->get<ReallocPairs>(); 988 for (ReallocMap::iterator I = RP.begin(), E = RP.end(); I != E; ++I) { 989 if (SymReaper.isDead(I->first) || 990 SymReaper.isDead(I->second.ReallocatedSym)) { 991 state = state->remove<ReallocPairs>(I->first); 992 } 993 } 994 995 // Generate leak node. 996 static SimpleProgramPointTag Tag("MallocChecker : DeadSymbolsLeak"); 997 ExplodedNode *N = C.addTransition(C.getState(), C.getPredecessor(), &Tag); 998 999 if (generateReport) { 1000 for (llvm::SmallVector<SymbolRef, 2>::iterator 1001 I = Errors.begin(), E = Errors.end(); I != E; ++I) { 1002 reportLeak(*I, N, C); 1003 } 1004 } 1005 C.addTransition(state->set<RegionState>(RS), N); 1006} 1007 1008void MallocChecker::checkEndPath(CheckerContext &C) const { 1009 ProgramStateRef state = C.getState(); 1010 RegionStateTy M = state->get<RegionState>(); 1011 1012 // If inside inlined call, skip it. 1013 if (C.getLocationContext()->getParent() != 0) 1014 return; 1015 1016 for (RegionStateTy::iterator I = M.begin(), E = M.end(); I != E; ++I) { 1017 RefState RS = I->second; 1018 if (RS.isAllocated()) { 1019 ExplodedNode *N = C.addTransition(state); 1020 if (N) 1021 reportLeak(I->first, N, C); 1022 } 1023 } 1024} 1025 1026bool MallocChecker::checkEscape(SymbolRef Sym, const Stmt *S, 1027 CheckerContext &C) const { 1028 ProgramStateRef state = C.getState(); 1029 const RefState *RS = state->get<RegionState>(Sym); 1030 if (!RS) 1031 return false; 1032 1033 if (RS->isAllocated()) { 1034 state = state->set<RegionState>(Sym, RefState::getEscaped(S)); 1035 C.addTransition(state); 1036 return true; 1037 } 1038 return false; 1039} 1040 1041void MallocChecker::checkPreStmt(const CallExpr *CE, CheckerContext &C) const { 1042 // We will check for double free in the post visit. 1043 if (isFreeFunction(C.getCalleeDecl(CE), C.getASTContext())) 1044 return; 1045 1046 // Check use after free, when a freed pointer is passed to a call. 1047 ProgramStateRef State = C.getState(); 1048 for (CallExpr::const_arg_iterator I = CE->arg_begin(), 1049 E = CE->arg_end(); I != E; ++I) { 1050 const Expr *A = *I; 1051 if (A->getType().getTypePtr()->isAnyPointerType()) { 1052 SymbolRef Sym = State->getSVal(A, C.getLocationContext()).getAsSymbol(); 1053 if (!Sym) 1054 continue; 1055 if (checkUseAfterFree(Sym, C, A)) 1056 return; 1057 } 1058 } 1059} 1060 1061void MallocChecker::checkPreStmt(const ReturnStmt *S, CheckerContext &C) const { 1062 const Expr *E = S->getRetValue(); 1063 if (!E) 1064 return; 1065 1066 // Check if we are returning a symbol. 1067 SVal RetVal = C.getState()->getSVal(E, C.getLocationContext()); 1068 SymbolRef Sym = RetVal.getAsSymbol(); 1069 if (!Sym) 1070 // If we are returning a field of the allocated struct or an array element, 1071 // the callee could still free the memory. 1072 // TODO: This logic should be a part of generic symbol escape callback. 1073 if (const MemRegion *MR = RetVal.getAsRegion()) 1074 if (isa<FieldRegion>(MR) || isa<ElementRegion>(MR)) 1075 if (const SymbolicRegion *BMR = 1076 dyn_cast<SymbolicRegion>(MR->getBaseRegion())) 1077 Sym = BMR->getSymbol(); 1078 if (!Sym) 1079 return; 1080 1081 // Check if we are returning freed memory. 1082 if (checkUseAfterFree(Sym, C, E)) 1083 return; 1084 1085 // If this function body is not inlined, check if the symbol is escaping. 1086 if (C.getLocationContext()->getParent() == 0) 1087 checkEscape(Sym, E, C); 1088} 1089 1090// TODO: Blocks should be either inlined or should call invalidate regions 1091// upon invocation. After that's in place, special casing here will not be 1092// needed. 1093void MallocChecker::checkPostStmt(const BlockExpr *BE, 1094 CheckerContext &C) const { 1095 1096 // Scan the BlockDecRefExprs for any object the retain count checker 1097 // may be tracking. 1098 if (!BE->getBlockDecl()->hasCaptures()) 1099 return; 1100 1101 ProgramStateRef state = C.getState(); 1102 const BlockDataRegion *R = 1103 cast<BlockDataRegion>(state->getSVal(BE, 1104 C.getLocationContext()).getAsRegion()); 1105 1106 BlockDataRegion::referenced_vars_iterator I = R->referenced_vars_begin(), 1107 E = R->referenced_vars_end(); 1108 1109 if (I == E) 1110 return; 1111 1112 SmallVector<const MemRegion*, 10> Regions; 1113 const LocationContext *LC = C.getLocationContext(); 1114 MemRegionManager &MemMgr = C.getSValBuilder().getRegionManager(); 1115 1116 for ( ; I != E; ++I) { 1117 const VarRegion *VR = *I; 1118 if (VR->getSuperRegion() == R) { 1119 VR = MemMgr.getVarRegion(VR->getDecl(), LC); 1120 } 1121 Regions.push_back(VR); 1122 } 1123 1124 state = 1125 state->scanReachableSymbols<StopTrackingCallback>(Regions.data(), 1126 Regions.data() + Regions.size()).getState(); 1127 C.addTransition(state); 1128} 1129 1130bool MallocChecker::isReleased(SymbolRef Sym, CheckerContext &C) const { 1131 assert(Sym); 1132 const RefState *RS = C.getState()->get<RegionState>(Sym); 1133 return (RS && RS->isReleased()); 1134} 1135 1136bool MallocChecker::checkUseAfterFree(SymbolRef Sym, CheckerContext &C, 1137 const Stmt *S) const { 1138 if (isReleased(Sym, C)) { 1139 if (ExplodedNode *N = C.generateSink()) { 1140 if (!BT_UseFree) 1141 BT_UseFree.reset(new BugType("Use-after-free", "Memory Error")); 1142 1143 BugReport *R = new BugReport(*BT_UseFree, 1144 "Use of memory after it is freed",N); 1145 if (S) 1146 R->addRange(S->getSourceRange()); 1147 R->markInteresting(Sym); 1148 R->addVisitor(new MallocBugVisitor(Sym)); 1149 C.EmitReport(R); 1150 return true; 1151 } 1152 } 1153 return false; 1154} 1155 1156// Check if the location is a freed symbolic region. 1157void MallocChecker::checkLocation(SVal l, bool isLoad, const Stmt *S, 1158 CheckerContext &C) const { 1159 SymbolRef Sym = l.getLocSymbolInBase(); 1160 if (Sym) 1161 checkUseAfterFree(Sym, C, S); 1162} 1163 1164//===----------------------------------------------------------------------===// 1165// Check various ways a symbol can be invalidated. 1166// TODO: This logic (the next 3 functions) is copied/similar to the 1167// RetainRelease checker. We might want to factor this out. 1168//===----------------------------------------------------------------------===// 1169 1170// Stop tracking symbols when a value escapes as a result of checkBind. 1171// A value escapes in three possible cases: 1172// (1) we are binding to something that is not a memory region. 1173// (2) we are binding to a memregion that does not have stack storage 1174// (3) we are binding to a memregion with stack storage that the store 1175// does not understand. 1176void MallocChecker::checkBind(SVal loc, SVal val, const Stmt *S, 1177 CheckerContext &C) const { 1178 // Are we storing to something that causes the value to "escape"? 1179 bool escapes = true; 1180 ProgramStateRef state = C.getState(); 1181 1182 if (loc::MemRegionVal *regionLoc = dyn_cast<loc::MemRegionVal>(&loc)) { 1183 escapes = !regionLoc->getRegion()->hasStackStorage(); 1184 1185 if (!escapes) { 1186 // To test (3), generate a new state with the binding added. If it is 1187 // the same state, then it escapes (since the store cannot represent 1188 // the binding). 1189 // Do this only if we know that the store is not supposed to generate the 1190 // same state. 1191 SVal StoredVal = state->getSVal(regionLoc->getRegion()); 1192 if (StoredVal != val) 1193 escapes = (state == (state->bindLoc(*regionLoc, val))); 1194 } 1195 if (!escapes) { 1196 // Case 4: We do not currently model what happens when a symbol is 1197 // assigned to a struct field, so be conservative here and let the symbol 1198 // go. TODO: This could definitely be improved upon. 1199 escapes = !isa<VarRegion>(regionLoc->getRegion()); 1200 } 1201 } 1202 1203 // If our store can represent the binding and we aren't storing to something 1204 // that doesn't have local storage then just return and have the simulation 1205 // state continue as is. 1206 if (!escapes) 1207 return; 1208 1209 // Otherwise, find all symbols referenced by 'val' that we are tracking 1210 // and stop tracking them. 1211 state = state->scanReachableSymbols<StopTrackingCallback>(val).getState(); 1212 C.addTransition(state); 1213} 1214 1215// If a symbolic region is assumed to NULL (or another constant), stop tracking 1216// it - assuming that allocation failed on this path. 1217ProgramStateRef MallocChecker::evalAssume(ProgramStateRef state, 1218 SVal Cond, 1219 bool Assumption) const { 1220 RegionStateTy RS = state->get<RegionState>(); 1221 for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) { 1222 // If the symbol is assumed to NULL or another constant, this will 1223 // return an APSInt*. 1224 if (state->getSymVal(I.getKey())) 1225 state = state->remove<RegionState>(I.getKey()); 1226 } 1227 1228 // Realloc returns 0 when reallocation fails, which means that we should 1229 // restore the state of the pointer being reallocated. 1230 ReallocMap RP = state->get<ReallocPairs>(); 1231 for (ReallocMap::iterator I = RP.begin(), E = RP.end(); I != E; ++I) { 1232 // If the symbol is assumed to NULL or another constant, this will 1233 // return an APSInt*. 1234 if (state->getSymVal(I.getKey())) { 1235 SymbolRef ReallocSym = I.getData().ReallocatedSym; 1236 const RefState *RS = state->get<RegionState>(ReallocSym); 1237 if (RS) { 1238 if (RS->isReleased() && ! I.getData().IsFreeOnFailure) 1239 state = state->set<RegionState>(ReallocSym, 1240 RefState::getAllocateUnchecked(RS->getStmt())); 1241 } 1242 state = state->remove<ReallocPairs>(I.getKey()); 1243 } 1244 } 1245 1246 return state; 1247} 1248 1249// Check if the function is known to us. So, for example, we could 1250// conservatively assume it can free/reallocate it's pointer arguments. 1251// (We assume that the pointers cannot escape through calls to system 1252// functions not handled by this checker.) 1253bool MallocChecker::doesNotFreeMemory(const CallOrObjCMessage *Call, 1254 ProgramStateRef State) const { 1255 if (!Call) 1256 return false; 1257 1258 // For now, assume that any C++ call can free memory. 1259 // TODO: If we want to be more optimistic here, we'll need to make sure that 1260 // regions escape to C++ containers. They seem to do that even now, but for 1261 // mysterious reasons. 1262 if (Call->isCXXCall()) 1263 return false; 1264 1265 const Decl *D = Call->getDecl(); 1266 if (!D) 1267 return false; 1268 1269 ASTContext &ASTC = State->getStateManager().getContext(); 1270 1271 // If it's one of the allocation functions we can reason about, we model 1272 // its behavior explicitly. 1273 if (isa<FunctionDecl>(D) && isMemFunction(cast<FunctionDecl>(D), ASTC)) { 1274 return true; 1275 } 1276 1277 // If it's not a system call, assume it frees memory. 1278 SourceManager &SM = ASTC.getSourceManager(); 1279 if (!SM.isInSystemHeader(D->getLocation())) 1280 return false; 1281 1282 // Process C/ObjC functions. 1283 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 1284 // White list the system functions whose arguments escape. 1285 const IdentifierInfo *II = FD->getIdentifier(); 1286 if (!II) 1287 return true; 1288 StringRef FName = II->getName(); 1289 1290 // White list thread local storage. 1291 if (FName.equals("pthread_setspecific")) 1292 return false; 1293 1294 // White list the 'XXXNoCopy' ObjC functions. 1295 if (FName.endswith("NoCopy")) { 1296 // Look for the deallocator argument. We know that the memory ownership 1297 // is not transferred only if the deallocator argument is 1298 // 'kCFAllocatorNull'. 1299 for (unsigned i = 1; i < Call->getNumArgs(); ++i) { 1300 const Expr *ArgE = Call->getArg(i)->IgnoreParenCasts(); 1301 if (const DeclRefExpr *DE = dyn_cast<DeclRefExpr>(ArgE)) { 1302 StringRef DeallocatorName = DE->getFoundDecl()->getName(); 1303 if (DeallocatorName == "kCFAllocatorNull") 1304 return true; 1305 } 1306 } 1307 return false; 1308 } 1309 1310 // PR12101 1311 // Many CoreFoundation and CoreGraphics might allow a tracked object 1312 // to escape. 1313 if (Call->isCFCGAllowingEscape(FName)) 1314 return false; 1315 1316 // Associating streams with malloced buffers. The pointer can escape if 1317 // 'closefn' is specified (and if that function does free memory). 1318 // Currently, we do not inspect the 'closefn' function (PR12101). 1319 if (FName == "funopen") 1320 if (Call->getNumArgs() >= 4 && !Call->getArgSVal(4).isConstant(0)) 1321 return false; 1322 1323 // Do not warn on pointers passed to 'setbuf' when used with std streams, 1324 // these leaks might be intentional when setting the buffer for stdio. 1325 // http://stackoverflow.com/questions/2671151/who-frees-setvbuf-buffer 1326 if (FName == "setbuf" || FName =="setbuffer" || 1327 FName == "setlinebuf" || FName == "setvbuf") { 1328 if (Call->getNumArgs() >= 1) 1329 if (const DeclRefExpr *Arg = 1330 dyn_cast<DeclRefExpr>(Call->getArg(0)->IgnoreParenCasts())) 1331 if (const VarDecl *D = dyn_cast<VarDecl>(Arg->getDecl())) 1332 if (D->getCanonicalDecl()->getName().find("std") 1333 != StringRef::npos) 1334 return false; 1335 } 1336 1337 // A bunch of other functions, which take ownership of a pointer (See retain 1338 // release checker). Not all the parameters here are invalidated, but the 1339 // Malloc checker cannot differentiate between them. The right way of doing 1340 // this would be to implement a pointer escapes callback. 1341 if (FName == "CVPixelBufferCreateWithBytes" || 1342 FName == "CGBitmapContextCreateWithData" || 1343 FName == "CVPixelBufferCreateWithPlanarBytes" || 1344 FName == "OSAtomicEnqueue") { 1345 return false; 1346 } 1347 1348 // Whitelist NSXXInsertXX, for example NSMapInsertIfAbsent, since they can 1349 // be deallocated by NSMapRemove. 1350 if (FName.startswith("NS") && (FName.find("Insert") != StringRef::npos)) 1351 return false; 1352 1353 // If the call has a callback as an argument, assume the memory 1354 // can be freed. 1355 if (Call->hasNonZeroCallbackArg()) 1356 return false; 1357 1358 // Otherwise, assume that the function does not free memory. 1359 // Most system calls, do not free the memory. 1360 return true; 1361 1362 // Process ObjC functions. 1363 } else if (const ObjCMethodDecl * ObjCD = dyn_cast<ObjCMethodDecl>(D)) { 1364 Selector S = ObjCD->getSelector(); 1365 1366 // White list the ObjC functions which do free memory. 1367 // - Anything containing 'freeWhenDone' param set to 1. 1368 // Ex: dataWithBytesNoCopy:length:freeWhenDone. 1369 for (unsigned i = 1; i < S.getNumArgs(); ++i) { 1370 if (S.getNameForSlot(i).equals("freeWhenDone")) { 1371 if (Call->getArgSVal(i).isConstant(1)) 1372 return false; 1373 else 1374 return true; 1375 } 1376 } 1377 1378 // If the first selector ends with NoCopy, assume that the ownership is 1379 // transferred as well. 1380 // Ex: [NSData dataWithBytesNoCopy:bytes length:10]; 1381 if (S.getNameForSlot(0).endswith("NoCopy")) { 1382 return false; 1383 } 1384 1385 // If the call has a callback as an argument, assume the memory 1386 // can be freed. 1387 if (Call->hasNonZeroCallbackArg()) 1388 return false; 1389 1390 // Otherwise, assume that the function does not free memory. 1391 // Most system calls, do not free the memory. 1392 return true; 1393 } 1394 1395 // Otherwise, assume that the function can free memory. 1396 return false; 1397 1398} 1399 1400// If the symbol we are tracking is invalidated, but not explicitly (ex: the &p 1401// escapes, when we are tracking p), do not track the symbol as we cannot reason 1402// about it anymore. 1403ProgramStateRef 1404MallocChecker::checkRegionChanges(ProgramStateRef State, 1405 const StoreManager::InvalidatedSymbols *invalidated, 1406 ArrayRef<const MemRegion *> ExplicitRegions, 1407 ArrayRef<const MemRegion *> Regions, 1408 const CallOrObjCMessage *Call) const { 1409 if (!invalidated || invalidated->empty()) 1410 return State; 1411 llvm::SmallPtrSet<SymbolRef, 8> WhitelistedSymbols; 1412 1413 // If it's a call which might free or reallocate memory, we assume that all 1414 // regions (explicit and implicit) escaped. 1415 1416 // Otherwise, whitelist explicit pointers; we still can track them. 1417 if (!Call || doesNotFreeMemory(Call, State)) { 1418 for (ArrayRef<const MemRegion *>::iterator I = ExplicitRegions.begin(), 1419 E = ExplicitRegions.end(); I != E; ++I) { 1420 if (const SymbolicRegion *R = (*I)->StripCasts()->getAs<SymbolicRegion>()) 1421 WhitelistedSymbols.insert(R->getSymbol()); 1422 } 1423 } 1424 1425 for (StoreManager::InvalidatedSymbols::const_iterator I=invalidated->begin(), 1426 E = invalidated->end(); I!=E; ++I) { 1427 SymbolRef sym = *I; 1428 if (WhitelistedSymbols.count(sym)) 1429 continue; 1430 // The symbol escaped. 1431 if (const RefState *RS = State->get<RegionState>(sym)) 1432 State = State->set<RegionState>(sym, RefState::getEscaped(RS->getStmt())); 1433 } 1434 return State; 1435} 1436 1437static SymbolRef findFailedReallocSymbol(ProgramStateRef currState, 1438 ProgramStateRef prevState) { 1439 ReallocMap currMap = currState->get<ReallocPairs>(); 1440 ReallocMap prevMap = prevState->get<ReallocPairs>(); 1441 1442 for (ReallocMap::iterator I = prevMap.begin(), E = prevMap.end(); 1443 I != E; ++I) { 1444 SymbolRef sym = I.getKey(); 1445 if (!currMap.lookup(sym)) 1446 return sym; 1447 } 1448 1449 return NULL; 1450} 1451 1452PathDiagnosticPiece * 1453MallocChecker::MallocBugVisitor::VisitNode(const ExplodedNode *N, 1454 const ExplodedNode *PrevN, 1455 BugReporterContext &BRC, 1456 BugReport &BR) { 1457 ProgramStateRef state = N->getState(); 1458 ProgramStateRef statePrev = PrevN->getState(); 1459 1460 const RefState *RS = state->get<RegionState>(Sym); 1461 const RefState *RSPrev = statePrev->get<RegionState>(Sym); 1462 if (!RS && !RSPrev) 1463 return 0; 1464 1465 const Stmt *S = 0; 1466 const char *Msg = 0; 1467 StackHintGeneratorForSymbol *StackHint = 0; 1468 1469 // Retrieve the associated statement. 1470 ProgramPoint ProgLoc = N->getLocation(); 1471 if (isa<StmtPoint>(ProgLoc)) 1472 S = cast<StmtPoint>(ProgLoc).getStmt(); 1473 // If an assumption was made on a branch, it should be caught 1474 // here by looking at the state transition. 1475 if (isa<BlockEdge>(ProgLoc)) { 1476 const CFGBlock *srcBlk = cast<BlockEdge>(ProgLoc).getSrc(); 1477 S = srcBlk->getTerminator(); 1478 } 1479 if (!S) 1480 return 0; 1481 1482 // Find out if this is an interesting point and what is the kind. 1483 if (Mode == Normal) { 1484 if (isAllocated(RS, RSPrev, S)) { 1485 Msg = "Memory is allocated"; 1486 StackHint = new StackHintGeneratorForSymbol(Sym, 1487 "Returned allocated memory"); 1488 } else if (isReleased(RS, RSPrev, S)) { 1489 Msg = "Memory is released"; 1490 StackHint = new StackHintGeneratorForSymbol(Sym, 1491 "Returned released memory"); 1492 } else if (isReallocFailedCheck(RS, RSPrev, S)) { 1493 Mode = ReallocationFailed; 1494 Msg = "Reallocation failed"; 1495 StackHint = new StackHintGeneratorForReallocationFailed(Sym, 1496 "Reallocation failed"); 1497 1498 if (SymbolRef sym = findFailedReallocSymbol(state, statePrev)) { 1499 // Is it possible to fail two reallocs WITHOUT testing in between? 1500 assert((!FailedReallocSymbol || FailedReallocSymbol == sym) && 1501 "We only support one failed realloc at a time."); 1502 BR.markInteresting(sym); 1503 FailedReallocSymbol = sym; 1504 } 1505 } 1506 1507 // We are in a special mode if a reallocation failed later in the path. 1508 } else if (Mode == ReallocationFailed) { 1509 assert(FailedReallocSymbol && "No symbol to look for."); 1510 1511 // Is this is the first appearance of the reallocated symbol? 1512 if (!statePrev->get<RegionState>(FailedReallocSymbol)) { 1513 // If we ever hit this assert, that means BugReporter has decided to skip 1514 // node pairs or visit them out of order. 1515 assert(state->get<RegionState>(FailedReallocSymbol) && 1516 "Missed the reallocation point"); 1517 1518 // We're at the reallocation point. 1519 Msg = "Attempt to reallocate memory"; 1520 StackHint = new StackHintGeneratorForSymbol(Sym, 1521 "Returned reallocated memory"); 1522 FailedReallocSymbol = NULL; 1523 Mode = Normal; 1524 } 1525 } 1526 1527 if (!Msg) 1528 return 0; 1529 assert(StackHint); 1530 1531 // Generate the extra diagnostic. 1532 PathDiagnosticLocation Pos(S, BRC.getSourceManager(), 1533 N->getLocationContext()); 1534 return new PathDiagnosticEventPiece(Pos, Msg, true, StackHint); 1535} 1536 1537void MallocChecker::printState(raw_ostream &Out, ProgramStateRef State, 1538 const char *NL, const char *Sep) const { 1539 1540 RegionStateTy RS = State->get<RegionState>(); 1541 1542 if (!RS.isEmpty()) 1543 Out << "Has Malloc data" << NL; 1544} 1545 1546#define REGISTER_CHECKER(name) \ 1547void ento::register##name(CheckerManager &mgr) {\ 1548 registerCStringCheckerBasic(mgr); \ 1549 mgr.registerChecker<MallocChecker>()->Filter.C##name = true;\ 1550} 1551 1552REGISTER_CHECKER(MallocPessimistic) 1553REGISTER_CHECKER(MallocOptimistic) 1554