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