ExprEngineCallAndReturn.cpp revision aca0ac58d2ae80d764e3832456667d7322445e0c
1//=-- ExprEngineCallAndReturn.cpp - Support for call/return -----*- 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 ExprEngine's support for calls and returns. 11// 12//===----------------------------------------------------------------------===// 13 14#include "clang/StaticAnalyzer/Core/CheckerManager.h" 15#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 16#include "clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h" 17#include "clang/AST/DeclCXX.h" 18#include "llvm/ADT/SmallSet.h" 19#include "llvm/Support/SaveAndRestore.h" 20 21using namespace clang; 22using namespace ento; 23 24void ExprEngine::processCallEnter(CallEnter CE, ExplodedNode *Pred) { 25 // Get the entry block in the CFG of the callee. 26 const StackFrameContext *calleeCtx = CE.getCalleeContext(); 27 const CFG *CalleeCFG = calleeCtx->getCFG(); 28 const CFGBlock *Entry = &(CalleeCFG->getEntry()); 29 30 // Validate the CFG. 31 assert(Entry->empty()); 32 assert(Entry->succ_size() == 1); 33 34 // Get the solitary sucessor. 35 const CFGBlock *Succ = *(Entry->succ_begin()); 36 37 // Construct an edge representing the starting location in the callee. 38 BlockEdge Loc(Entry, Succ, calleeCtx); 39 40 // Construct a new state which contains the mapping from actual to 41 // formal arguments. 42 const LocationContext *callerCtx = Pred->getLocationContext(); 43 ProgramStateRef state = Pred->getState()->enterStackFrame(callerCtx, 44 calleeCtx); 45 46 // Construct a new node and add it to the worklist. 47 bool isNew; 48 ExplodedNode *Node = G.getNode(Loc, state, false, &isNew); 49 Node->addPredecessor(Pred, G); 50 if (isNew) 51 Engine.getWorkList()->enqueue(Node); 52} 53 54// Find the last statement on the path to the exploded node and the 55// corresponding Block. 56static std::pair<const Stmt*, 57 const CFGBlock*> getLastStmt(const ExplodedNode *Node) { 58 const Stmt *S = 0; 59 const CFGBlock *Blk = 0; 60 const StackFrameContext *SF = 61 Node->getLocation().getLocationContext()->getCurrentStackFrame(); 62 while (Node) { 63 const ProgramPoint &PP = Node->getLocation(); 64 // Skip any BlockEdges, empty blocks, and the CallExitBegin node. 65 if (isa<BlockEdge>(PP) || isa<CallExitBegin>(PP) || isa<BlockEntrance>(PP)){ 66 assert(Node->pred_size() == 1); 67 Node = *Node->pred_begin(); 68 continue; 69 } 70 // If we reached the CallEnter, the function has no statements. 71 if (isa<CallEnter>(PP)) 72 break; 73 if (const StmtPoint *SP = dyn_cast<StmtPoint>(&PP)) { 74 S = SP->getStmt(); 75 // Now, get the enclosing basic block. 76 while (Node && Node->pred_size() >=1 ) { 77 const ProgramPoint &PP = Node->getLocation(); 78 if (isa<BlockEdge>(PP) && 79 (PP.getLocationContext()->getCurrentStackFrame() == SF)) { 80 BlockEdge &EPP = cast<BlockEdge>(PP); 81 Blk = EPP.getDst(); 82 break; 83 } 84 Node = *Node->pred_begin(); 85 } 86 break; 87 } 88 break; 89 } 90 return std::pair<const Stmt*, const CFGBlock*>(S, Blk); 91} 92 93/// The call exit is simulated with a sequence of nodes, which occur between 94/// CallExitBegin and CallExitEnd. The following operations occur between the 95/// two program points: 96/// 1. CallExitBegin (triggers the start of call exit sequence) 97/// 2. Bind the return value 98/// 3. Run Remove dead bindings to clean up the dead symbols from the callee. 99/// 4. CallExitEnd (switch to the caller context) 100/// 5. PostStmt<CallExpr> 101void ExprEngine::processCallExit(ExplodedNode *CEBNode) { 102 // Step 1 CEBNode was generated before the call. 103 104 const StackFrameContext *calleeCtx = 105 CEBNode->getLocationContext()->getCurrentStackFrame(); 106 const LocationContext *callerCtx = calleeCtx->getParent(); 107 const Stmt *CE = calleeCtx->getCallSite(); 108 ProgramStateRef state = CEBNode->getState(); 109 // Find the last statement in the function and the corresponding basic block. 110 const Stmt *LastSt = 0; 111 const CFGBlock *Blk = 0; 112 llvm::tie(LastSt, Blk) = getLastStmt(CEBNode); 113 114 // Step 2: generate node with binded return value: CEBNode -> BindedRetNode. 115 116 // If the callee returns an expression, bind its value to CallExpr. 117 if (const ReturnStmt *RS = dyn_cast_or_null<ReturnStmt>(LastSt)) { 118 const LocationContext *LCtx = CEBNode->getLocationContext(); 119 SVal V = state->getSVal(RS, LCtx); 120 state = state->BindExpr(CE, callerCtx, V); 121 } 122 123 // Bind the constructed object value to CXXConstructExpr. 124 if (const CXXConstructExpr *CCE = dyn_cast<CXXConstructExpr>(CE)) { 125 const CXXThisRegion *ThisR = 126 getCXXThisRegion(CCE->getConstructor()->getParent(), calleeCtx); 127 128 SVal ThisV = state->getSVal(ThisR); 129 // Always bind the region to the CXXConstructExpr. 130 state = state->BindExpr(CCE, CEBNode->getLocationContext(), ThisV); 131 } 132 133 static SimpleProgramPointTag retValBindTag("ExprEngine : Bind Return Value"); 134 PostStmt Loc(LastSt, calleeCtx, &retValBindTag); 135 bool isNew; 136 ExplodedNode *BindedRetNode = G.getNode(Loc, state, false, &isNew); 137 BindedRetNode->addPredecessor(CEBNode, G); 138 if (!isNew) 139 return; 140 141 // Step 3: BindedRetNode -> CleanedNodes 142 // If we can find a statement and a block in the inlined function, run remove 143 // dead bindings before returning from the call. This is important to ensure 144 // that we report the issues such as leaks in the stack contexts in which 145 // they occurred. 146 ExplodedNodeSet CleanedNodes; 147 if (LastSt && Blk) { 148 NodeBuilderContext Ctx(getCoreEngine(), Blk, BindedRetNode); 149 currentBuilderContext = &Ctx; 150 // Here, we call the Symbol Reaper with 0 statement and caller location 151 // context, telling it to clean up everything in the callee's context 152 // (and it's children). We use LastStmt as a diagnostic statement, which 153 // which the PreStmtPurge Dead point will be associated. 154 removeDead(BindedRetNode, CleanedNodes, 0, callerCtx, LastSt, 155 ProgramPoint::PostStmtPurgeDeadSymbolsKind); 156 currentBuilderContext = 0; 157 } 158 159 for (ExplodedNodeSet::iterator I = CleanedNodes.begin(), 160 E = CleanedNodes.end(); I != E; ++I) { 161 162 // Step 4: Generate the CallExit and leave the callee's context. 163 // CleanedNodes -> CEENode 164 CallExitEnd Loc(CE, callerCtx); 165 bool isNew; 166 ExplodedNode *CEENode = G.getNode(Loc, (*I)->getState(), false, &isNew); 167 CEENode->addPredecessor(*I, G); 168 if (!isNew) 169 return; 170 171 // Step 5: Perform the post-condition check of the CallExpr and enqueue the 172 // result onto the work list. 173 // CEENode -> Dst -> WorkList 174 ExplodedNodeSet Dst; 175 NodeBuilderContext Ctx(Engine, calleeCtx->getCallSiteBlock(), CEENode); 176 SaveAndRestore<const NodeBuilderContext*> NBCSave(currentBuilderContext, 177 &Ctx); 178 SaveAndRestore<unsigned> CBISave(currentStmtIdx, calleeCtx->getIndex()); 179 180 getCheckerManager().runCheckersForPostStmt(Dst, CEENode, CE, *this, true); 181 182 // Enqueue the next element in the block. 183 for (ExplodedNodeSet::iterator PSI = Dst.begin(), PSE = Dst.end(); 184 PSI != PSE; ++PSI) { 185 Engine.getWorkList()->enqueue(*PSI, calleeCtx->getCallSiteBlock(), 186 calleeCtx->getIndex()+1); 187 } 188 } 189} 190 191static unsigned getNumberStackFrames(const LocationContext *LCtx) { 192 unsigned count = 0; 193 while (LCtx) { 194 if (isa<StackFrameContext>(LCtx)) 195 ++count; 196 LCtx = LCtx->getParent(); 197 } 198 return count; 199} 200 201// Determine if we should inline the call. 202bool ExprEngine::shouldInlineDecl(const FunctionDecl *FD, ExplodedNode *Pred) { 203 AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(FD); 204 const CFG *CalleeCFG = CalleeADC->getCFG(); 205 206 // It is possible that the CFG cannot be constructed. 207 // Be safe, and check if the CalleeCFG is valid. 208 if (!CalleeCFG) 209 return false; 210 211 if (getNumberStackFrames(Pred->getLocationContext()) 212 == AMgr.InlineMaxStackDepth) 213 return false; 214 215 if (Engine.FunctionSummaries->hasReachedMaxBlockCount(FD)) 216 return false; 217 218 if (CalleeCFG->getNumBlockIDs() > AMgr.InlineMaxFunctionSize) 219 return false; 220 221 return true; 222} 223 224// For now, skip inlining variadic functions. 225// We also don't inline blocks. 226static bool shouldInlineCallExpr(const CallExpr *CE, ExprEngine *E) { 227 if (!E->getAnalysisManager().shouldInlineCall()) 228 return false; 229 QualType callee = CE->getCallee()->getType(); 230 const FunctionProtoType *FT = 0; 231 if (const PointerType *PT = callee->getAs<PointerType>()) 232 FT = dyn_cast<FunctionProtoType>(PT->getPointeeType()); 233 else if (const BlockPointerType *BT = callee->getAs<BlockPointerType>()) { 234 // FIXME: inline blocks. 235 // FT = dyn_cast<FunctionProtoType>(BT->getPointeeType()); 236 (void) BT; 237 return false; 238 } 239 // If we have no prototype, assume the function is okay. 240 if (!FT) 241 return true; 242 243 // Skip inlining of variadic functions. 244 return !FT->isVariadic(); 245} 246 247bool ExprEngine::InlineCall(ExplodedNodeSet &Dst, 248 const CallExpr *CE, 249 ExplodedNode *Pred) { 250 if (!shouldInlineCallExpr(CE, this)) 251 return false; 252 253 ProgramStateRef state = Pred->getState(); 254 const Expr *Callee = CE->getCallee(); 255 const FunctionDecl *FD = 256 state->getSVal(Callee, Pred->getLocationContext()).getAsFunctionDecl(); 257 if (!FD || !FD->hasBody(FD)) 258 return false; 259 260 switch (CE->getStmtClass()) { 261 default: 262 // FIXME: Handle C++. 263 break; 264 case Stmt::CallExprClass: { 265 if (!shouldInlineDecl(FD, Pred)) 266 return false; 267 268 // Construct a new stack frame for the callee. 269 AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(FD); 270 const StackFrameContext *CallerSFC = 271 Pred->getLocationContext()->getCurrentStackFrame(); 272 const StackFrameContext *CalleeSFC = 273 CalleeADC->getStackFrame(CallerSFC, CE, 274 currentBuilderContext->getBlock(), 275 currentStmtIdx); 276 277 CallEnter Loc(CE, CalleeSFC, Pred->getLocationContext()); 278 bool isNew; 279 if (ExplodedNode *N = G.getNode(Loc, state, false, &isNew)) { 280 N->addPredecessor(Pred, G); 281 if (isNew) 282 Engine.getWorkList()->enqueue(N); 283 } 284 return true; 285 } 286 } 287 return false; 288} 289 290static bool isPointerToConst(const ParmVarDecl *ParamDecl) { 291 QualType PointeeTy = ParamDecl->getOriginalType()->getPointeeType(); 292 if (PointeeTy != QualType() && PointeeTy.isConstQualified() && 293 !PointeeTy->isAnyPointerType() && !PointeeTy->isReferenceType()) { 294 return true; 295 } 296 return false; 297} 298 299// Try to retrieve the function declaration and find the function parameter 300// types which are pointers/references to a non-pointer const. 301// We do not invalidate the corresponding argument regions. 302static void findPtrToConstParams(llvm::SmallSet<unsigned, 1> &PreserveArgs, 303 const CallOrObjCMessage &Call) { 304 const Decl *CallDecl = Call.getDecl(); 305 if (!CallDecl) 306 return; 307 308 if (const FunctionDecl *FDecl = dyn_cast<FunctionDecl>(CallDecl)) { 309 const IdentifierInfo *II = FDecl->getIdentifier(); 310 311 // List the cases, where the region should be invalidated even if the 312 // argument is const. 313 if (II) { 314 StringRef FName = II->getName(); 315 // - 'int pthread_setspecific(ptheread_key k, const void *)' stores a 316 // value into thread local storage. The value can later be retrieved with 317 // 'void *ptheread_getspecific(pthread_key)'. So even thought the 318 // parameter is 'const void *', the region escapes through the call. 319 // - funopen - sets a buffer for future IO calls. 320 // - ObjC functions that end with "NoCopy" can free memory, of the passed 321 // in buffer. 322 // - Many CF containers allow objects to escape through custom 323 // allocators/deallocators upon container construction. 324 // - NSXXInsertXX, for example NSMapInsertIfAbsent, since they can 325 // be deallocated by NSMapRemove. 326 // - Any call that has a callback as one of the arguments. 327 if (FName == "pthread_setspecific" || 328 FName == "funopen" || 329 FName.endswith("NoCopy") || 330 (FName.startswith("NS") && 331 (FName.find("Insert") != StringRef::npos)) || 332 Call.isCFCGAllowingEscape(FName) || 333 Call.hasNonZeroCallbackArg()) 334 return; 335 } 336 337 for (unsigned Idx = 0, E = Call.getNumArgs(); Idx != E; ++Idx) { 338 if (FDecl && Idx < FDecl->getNumParams()) { 339 if (isPointerToConst(FDecl->getParamDecl(Idx))) 340 PreserveArgs.insert(Idx); 341 } 342 } 343 return; 344 } 345 346 if (const ObjCMethodDecl *MDecl = dyn_cast<ObjCMethodDecl>(CallDecl)) { 347 assert(MDecl->param_size() <= Call.getNumArgs()); 348 unsigned Idx = 0; 349 350 if (Call.hasNonZeroCallbackArg()) 351 return; 352 353 for (clang::ObjCMethodDecl::param_const_iterator 354 I = MDecl->param_begin(), E = MDecl->param_end(); I != E; ++I, ++Idx) { 355 if (isPointerToConst(*I)) 356 PreserveArgs.insert(Idx); 357 } 358 return; 359 } 360} 361 362ProgramStateRef 363ExprEngine::invalidateArguments(ProgramStateRef State, 364 const CallOrObjCMessage &Call, 365 const LocationContext *LC) { 366 SmallVector<const MemRegion *, 8> RegionsToInvalidate; 367 368 if (Call.isObjCMessage()) { 369 // Invalidate all instance variables of the receiver of an ObjC message. 370 // FIXME: We should be able to do better with inter-procedural analysis. 371 if (const MemRegion *MR = Call.getInstanceMessageReceiver(LC).getAsRegion()) 372 RegionsToInvalidate.push_back(MR); 373 374 } else if (Call.isCXXCall()) { 375 // Invalidate all instance variables for the callee of a C++ method call. 376 // FIXME: We should be able to do better with inter-procedural analysis. 377 // FIXME: We can probably do better for const versus non-const methods. 378 if (const MemRegion *Callee = Call.getCXXCallee().getAsRegion()) 379 RegionsToInvalidate.push_back(Callee); 380 381 } else if (Call.isFunctionCall()) { 382 // Block calls invalidate all captured-by-reference values. 383 SVal CalleeVal = Call.getFunctionCallee(); 384 if (const MemRegion *Callee = CalleeVal.getAsRegion()) { 385 if (isa<BlockDataRegion>(Callee)) 386 RegionsToInvalidate.push_back(Callee); 387 } 388 } 389 390 // Indexes of arguments whose values will be preserved by the call. 391 llvm::SmallSet<unsigned, 1> PreserveArgs; 392 findPtrToConstParams(PreserveArgs, Call); 393 394 for (unsigned idx = 0, e = Call.getNumArgs(); idx != e; ++idx) { 395 if (PreserveArgs.count(idx)) 396 continue; 397 398 SVal V = Call.getArgSVal(idx); 399 400 // If we are passing a location wrapped as an integer, unwrap it and 401 // invalidate the values referred by the location. 402 if (nonloc::LocAsInteger *Wrapped = dyn_cast<nonloc::LocAsInteger>(&V)) 403 V = Wrapped->getLoc(); 404 else if (!isa<Loc>(V)) 405 continue; 406 407 if (const MemRegion *R = V.getAsRegion()) { 408 // Invalidate the value of the variable passed by reference. 409 410 // Are we dealing with an ElementRegion? If the element type is 411 // a basic integer type (e.g., char, int) and the underlying region 412 // is a variable region then strip off the ElementRegion. 413 // FIXME: We really need to think about this for the general case 414 // as sometimes we are reasoning about arrays and other times 415 // about (char*), etc., is just a form of passing raw bytes. 416 // e.g., void *p = alloca(); foo((char*)p); 417 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) { 418 // Checking for 'integral type' is probably too promiscuous, but 419 // we'll leave it in for now until we have a systematic way of 420 // handling all of these cases. Eventually we need to come up 421 // with an interface to StoreManager so that this logic can be 422 // appropriately delegated to the respective StoreManagers while 423 // still allowing us to do checker-specific logic (e.g., 424 // invalidating reference counts), probably via callbacks. 425 if (ER->getElementType()->isIntegralOrEnumerationType()) { 426 const MemRegion *superReg = ER->getSuperRegion(); 427 if (isa<VarRegion>(superReg) || isa<FieldRegion>(superReg) || 428 isa<ObjCIvarRegion>(superReg)) 429 R = cast<TypedRegion>(superReg); 430 } 431 // FIXME: What about layers of ElementRegions? 432 } 433 434 // Mark this region for invalidation. We batch invalidate regions 435 // below for efficiency. 436 RegionsToInvalidate.push_back(R); 437 } else { 438 // Nuke all other arguments passed by reference. 439 // FIXME: is this necessary or correct? This handles the non-Region 440 // cases. Is it ever valid to store to these? 441 State = State->unbindLoc(cast<Loc>(V)); 442 } 443 } 444 445 // Invalidate designated regions using the batch invalidation API. 446 447 // FIXME: We can have collisions on the conjured symbol if the 448 // expression *I also creates conjured symbols. We probably want 449 // to identify conjured symbols by an expression pair: the enclosing 450 // expression (the context) and the expression itself. This should 451 // disambiguate conjured symbols. 452 unsigned Count = currentBuilderContext->getCurrentBlockCount(); 453 StoreManager::InvalidatedSymbols IS; 454 455 // NOTE: Even if RegionsToInvalidate is empty, we may still invalidate 456 // global variables. 457 return State->invalidateRegions(RegionsToInvalidate, 458 Call.getOriginExpr(), Count, LC, 459 &IS, &Call); 460 461} 462 463static ProgramStateRef getReplayWithoutInliningState(ExplodedNode *&N, 464 const CallExpr *CE) { 465 void *ReplayState = N->getState()->get<ReplayWithoutInlining>(); 466 if (!ReplayState) 467 return 0; 468 const CallExpr *ReplayCE = reinterpret_cast<const CallExpr*>(ReplayState); 469 if (CE == ReplayCE) { 470 return N->getState()->remove<ReplayWithoutInlining>(); 471 } 472 return 0; 473} 474 475void ExprEngine::VisitCallExpr(const CallExpr *CE, ExplodedNode *Pred, 476 ExplodedNodeSet &dst) { 477 // Perform the previsit of the CallExpr. 478 ExplodedNodeSet dstPreVisit; 479 getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, CE, *this); 480 481 // Now evaluate the call itself. 482 class DefaultEval : public GraphExpander { 483 ExprEngine &Eng; 484 const CallExpr *CE; 485 public: 486 487 DefaultEval(ExprEngine &eng, const CallExpr *ce) 488 : Eng(eng), CE(ce) {} 489 virtual void expandGraph(ExplodedNodeSet &Dst, ExplodedNode *Pred) { 490 491 ProgramStateRef state = getReplayWithoutInliningState(Pred, CE); 492 493 // First, try to inline the call. 494 if (state == 0 && Eng.InlineCall(Dst, CE, Pred)) 495 return; 496 497 // First handle the return value. 498 StmtNodeBuilder Bldr(Pred, Dst, *Eng.currentBuilderContext); 499 500 // Get the callee. 501 const Expr *Callee = CE->getCallee()->IgnoreParens(); 502 if (state == 0) 503 state = Pred->getState(); 504 SVal L = state->getSVal(Callee, Pred->getLocationContext()); 505 506 // Figure out the result type. We do this dance to handle references. 507 QualType ResultTy; 508 if (const FunctionDecl *FD = L.getAsFunctionDecl()) 509 ResultTy = FD->getResultType(); 510 else 511 ResultTy = CE->getType(); 512 513 if (CE->isLValue()) 514 ResultTy = Eng.getContext().getPointerType(ResultTy); 515 516 // Conjure a symbol value to use as the result. 517 SValBuilder &SVB = Eng.getSValBuilder(); 518 unsigned Count = Eng.currentBuilderContext->getCurrentBlockCount(); 519 const LocationContext *LCtx = Pred->getLocationContext(); 520 SVal RetVal = SVB.getConjuredSymbolVal(0, CE, LCtx, ResultTy, Count); 521 522 // Generate a new state with the return value set. 523 state = state->BindExpr(CE, LCtx, RetVal); 524 525 // Invalidate the arguments. 526 state = Eng.invalidateArguments(state, CallOrObjCMessage(CE, state, LCtx), 527 LCtx); 528 529 // And make the result node. 530 Bldr.generateNode(CE, Pred, state); 531 } 532 }; 533 534 // Finally, evaluate the function call. We try each of the checkers 535 // to see if the can evaluate the function call. 536 ExplodedNodeSet dstCallEvaluated; 537 DefaultEval defEval(*this, CE); 538 getCheckerManager().runCheckersForEvalCall(dstCallEvaluated, 539 dstPreVisit, 540 CE, *this, &defEval); 541 542 // Finally, perform the post-condition check of the CallExpr and store 543 // the created nodes in 'Dst'. 544 getCheckerManager().runCheckersForPostStmt(dst, dstCallEvaluated, CE, 545 *this); 546} 547 548void ExprEngine::VisitReturnStmt(const ReturnStmt *RS, ExplodedNode *Pred, 549 ExplodedNodeSet &Dst) { 550 551 ExplodedNodeSet dstPreVisit; 552 getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, RS, *this); 553 554 StmtNodeBuilder B(dstPreVisit, Dst, *currentBuilderContext); 555 556 if (RS->getRetValue()) { 557 for (ExplodedNodeSet::iterator it = dstPreVisit.begin(), 558 ei = dstPreVisit.end(); it != ei; ++it) { 559 B.generateNode(RS, *it, (*it)->getState()); 560 } 561 } 562} 563