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