1 //===- SymbolManager.h - Management of Symbolic Values --------------------===// 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 SymbolManager, a class that manages symbolic values 11 // created for use by ExprEngine and related classes. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h" 16 #include "clang/AST/ASTContext.h" 17 #include "clang/AST/Expr.h" 18 #include "clang/Analysis/Analyses/LiveVariables.h" 19 #include "clang/Analysis/AnalysisDeclContext.h" 20 #include "clang/Basic/LLVM.h" 21 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" 22 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" 23 #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h" 24 #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h" 25 #include "llvm/ADT/FoldingSet.h" 26 #include "llvm/ADT/STLExtras.h" 27 #include "llvm/Support/Casting.h" 28 #include "llvm/Support/Compiler.h" 29 #include "llvm/Support/ErrorHandling.h" 30 #include "llvm/Support/raw_ostream.h" 31 #include <cassert> 32 33 using namespace clang; 34 using namespace ento; 35 36 void SymExpr::anchor() {} 37 38 LLVM_DUMP_METHOD void SymExpr::dump() const { 39 dumpToStream(llvm::errs()); 40 } 41 42 void SymIntExpr::dumpToStream(raw_ostream &os) const { 43 os << '('; 44 getLHS()->dumpToStream(os); 45 os << ") " 46 << BinaryOperator::getOpcodeStr(getOpcode()) << ' '; 47 if (getRHS().isUnsigned()) 48 os << getRHS().getZExtValue(); 49 else 50 os << getRHS().getSExtValue(); 51 if (getRHS().isUnsigned()) 52 os << 'U'; 53 } 54 55 void IntSymExpr::dumpToStream(raw_ostream &os) const { 56 if (getLHS().isUnsigned()) 57 os << getLHS().getZExtValue(); 58 else 59 os << getLHS().getSExtValue(); 60 if (getLHS().isUnsigned()) 61 os << 'U'; 62 os << ' ' 63 << BinaryOperator::getOpcodeStr(getOpcode()) 64 << " ("; 65 getRHS()->dumpToStream(os); 66 os << ')'; 67 } 68 69 void SymSymExpr::dumpToStream(raw_ostream &os) const { 70 os << '('; 71 getLHS()->dumpToStream(os); 72 os << ") " 73 << BinaryOperator::getOpcodeStr(getOpcode()) 74 << " ("; 75 getRHS()->dumpToStream(os); 76 os << ')'; 77 } 78 79 void SymbolCast::dumpToStream(raw_ostream &os) const { 80 os << '(' << ToTy.getAsString() << ") ("; 81 Operand->dumpToStream(os); 82 os << ')'; 83 } 84 85 void SymbolConjured::dumpToStream(raw_ostream &os) const { 86 os << "conj_$" << getSymbolID() << '{' << T.getAsString() << ", LC" 87 << LCtx->getID(); 88 if (S) 89 os << ", S" << S->getID(LCtx->getDecl()->getASTContext()); 90 else 91 os << ", no stmt"; 92 os << ", #" << Count << '}'; 93 } 94 95 void SymbolDerived::dumpToStream(raw_ostream &os) const { 96 os << "derived_$" << getSymbolID() << '{' 97 << getParentSymbol() << ',' << getRegion() << '}'; 98 } 99 100 void SymbolExtent::dumpToStream(raw_ostream &os) const { 101 os << "extent_$" << getSymbolID() << '{' << getRegion() << '}'; 102 } 103 104 void SymbolMetadata::dumpToStream(raw_ostream &os) const { 105 os << "meta_$" << getSymbolID() << '{' 106 << getRegion() << ',' << T.getAsString() << '}'; 107 } 108 109 void SymbolData::anchor() {} 110 111 void SymbolRegionValue::dumpToStream(raw_ostream &os) const { 112 os << "reg_$" << getSymbolID() 113 << '<' << getType().getAsString() << ' ' << R << '>'; 114 } 115 116 bool SymExpr::symbol_iterator::operator==(const symbol_iterator &X) const { 117 return itr == X.itr; 118 } 119 120 bool SymExpr::symbol_iterator::operator!=(const symbol_iterator &X) const { 121 return itr != X.itr; 122 } 123 124 SymExpr::symbol_iterator::symbol_iterator(const SymExpr *SE) { 125 itr.push_back(SE); 126 } 127 128 SymExpr::symbol_iterator &SymExpr::symbol_iterator::operator++() { 129 assert(!itr.empty() && "attempting to iterate on an 'end' iterator"); 130 expand(); 131 return *this; 132 } 133 134 SymbolRef SymExpr::symbol_iterator::operator*() { 135 assert(!itr.empty() && "attempting to dereference an 'end' iterator"); 136 return itr.back(); 137 } 138 139 void SymExpr::symbol_iterator::expand() { 140 const SymExpr *SE = itr.pop_back_val(); 141 142 switch (SE->getKind()) { 143 case SymExpr::SymbolRegionValueKind: 144 case SymExpr::SymbolConjuredKind: 145 case SymExpr::SymbolDerivedKind: 146 case SymExpr::SymbolExtentKind: 147 case SymExpr::SymbolMetadataKind: 148 return; 149 case SymExpr::SymbolCastKind: 150 itr.push_back(cast<SymbolCast>(SE)->getOperand()); 151 return; 152 case SymExpr::SymIntExprKind: 153 itr.push_back(cast<SymIntExpr>(SE)->getLHS()); 154 return; 155 case SymExpr::IntSymExprKind: 156 itr.push_back(cast<IntSymExpr>(SE)->getRHS()); 157 return; 158 case SymExpr::SymSymExprKind: { 159 const auto *x = cast<SymSymExpr>(SE); 160 itr.push_back(x->getLHS()); 161 itr.push_back(x->getRHS()); 162 return; 163 } 164 } 165 llvm_unreachable("unhandled expansion case"); 166 } 167 168 const SymbolRegionValue* 169 SymbolManager::getRegionValueSymbol(const TypedValueRegion* R) { 170 llvm::FoldingSetNodeID profile; 171 SymbolRegionValue::Profile(profile, R); 172 void *InsertPos; 173 SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 174 if (!SD) { 175 SD = (SymExpr*) BPAlloc.Allocate<SymbolRegionValue>(); 176 new (SD) SymbolRegionValue(SymbolCounter, R); 177 DataSet.InsertNode(SD, InsertPos); 178 ++SymbolCounter; 179 } 180 181 return cast<SymbolRegionValue>(SD); 182 } 183 184 const SymbolConjured* SymbolManager::conjureSymbol(const Stmt *E, 185 const LocationContext *LCtx, 186 QualType T, 187 unsigned Count, 188 const void *SymbolTag) { 189 llvm::FoldingSetNodeID profile; 190 SymbolConjured::Profile(profile, E, T, Count, LCtx, SymbolTag); 191 void *InsertPos; 192 SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 193 if (!SD) { 194 SD = (SymExpr*) BPAlloc.Allocate<SymbolConjured>(); 195 new (SD) SymbolConjured(SymbolCounter, E, LCtx, T, Count, SymbolTag); 196 DataSet.InsertNode(SD, InsertPos); 197 ++SymbolCounter; 198 } 199 200 return cast<SymbolConjured>(SD); 201 } 202 203 const SymbolDerived* 204 SymbolManager::getDerivedSymbol(SymbolRef parentSymbol, 205 const TypedValueRegion *R) { 206 llvm::FoldingSetNodeID profile; 207 SymbolDerived::Profile(profile, parentSymbol, R); 208 void *InsertPos; 209 SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 210 if (!SD) { 211 SD = (SymExpr*) BPAlloc.Allocate<SymbolDerived>(); 212 new (SD) SymbolDerived(SymbolCounter, parentSymbol, R); 213 DataSet.InsertNode(SD, InsertPos); 214 ++SymbolCounter; 215 } 216 217 return cast<SymbolDerived>(SD); 218 } 219 220 const SymbolExtent* 221 SymbolManager::getExtentSymbol(const SubRegion *R) { 222 llvm::FoldingSetNodeID profile; 223 SymbolExtent::Profile(profile, R); 224 void *InsertPos; 225 SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 226 if (!SD) { 227 SD = (SymExpr*) BPAlloc.Allocate<SymbolExtent>(); 228 new (SD) SymbolExtent(SymbolCounter, R); 229 DataSet.InsertNode(SD, InsertPos); 230 ++SymbolCounter; 231 } 232 233 return cast<SymbolExtent>(SD); 234 } 235 236 const SymbolMetadata * 237 SymbolManager::getMetadataSymbol(const MemRegion* R, const Stmt *S, QualType T, 238 const LocationContext *LCtx, 239 unsigned Count, const void *SymbolTag) { 240 llvm::FoldingSetNodeID profile; 241 SymbolMetadata::Profile(profile, R, S, T, LCtx, Count, SymbolTag); 242 void *InsertPos; 243 SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); 244 if (!SD) { 245 SD = (SymExpr*) BPAlloc.Allocate<SymbolMetadata>(); 246 new (SD) SymbolMetadata(SymbolCounter, R, S, T, LCtx, Count, SymbolTag); 247 DataSet.InsertNode(SD, InsertPos); 248 ++SymbolCounter; 249 } 250 251 return cast<SymbolMetadata>(SD); 252 } 253 254 const SymbolCast* 255 SymbolManager::getCastSymbol(const SymExpr *Op, 256 QualType From, QualType To) { 257 llvm::FoldingSetNodeID ID; 258 SymbolCast::Profile(ID, Op, From, To); 259 void *InsertPos; 260 SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); 261 if (!data) { 262 data = (SymbolCast*) BPAlloc.Allocate<SymbolCast>(); 263 new (data) SymbolCast(Op, From, To); 264 DataSet.InsertNode(data, InsertPos); 265 } 266 267 return cast<SymbolCast>(data); 268 } 269 270 const SymIntExpr *SymbolManager::getSymIntExpr(const SymExpr *lhs, 271 BinaryOperator::Opcode op, 272 const llvm::APSInt& v, 273 QualType t) { 274 llvm::FoldingSetNodeID ID; 275 SymIntExpr::Profile(ID, lhs, op, v, t); 276 void *InsertPos; 277 SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); 278 279 if (!data) { 280 data = (SymIntExpr*) BPAlloc.Allocate<SymIntExpr>(); 281 new (data) SymIntExpr(lhs, op, v, t); 282 DataSet.InsertNode(data, InsertPos); 283 } 284 285 return cast<SymIntExpr>(data); 286 } 287 288 const IntSymExpr *SymbolManager::getIntSymExpr(const llvm::APSInt& lhs, 289 BinaryOperator::Opcode op, 290 const SymExpr *rhs, 291 QualType t) { 292 llvm::FoldingSetNodeID ID; 293 IntSymExpr::Profile(ID, lhs, op, rhs, t); 294 void *InsertPos; 295 SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); 296 297 if (!data) { 298 data = (IntSymExpr*) BPAlloc.Allocate<IntSymExpr>(); 299 new (data) IntSymExpr(lhs, op, rhs, t); 300 DataSet.InsertNode(data, InsertPos); 301 } 302 303 return cast<IntSymExpr>(data); 304 } 305 306 const SymSymExpr *SymbolManager::getSymSymExpr(const SymExpr *lhs, 307 BinaryOperator::Opcode op, 308 const SymExpr *rhs, 309 QualType t) { 310 llvm::FoldingSetNodeID ID; 311 SymSymExpr::Profile(ID, lhs, op, rhs, t); 312 void *InsertPos; 313 SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); 314 315 if (!data) { 316 data = (SymSymExpr*) BPAlloc.Allocate<SymSymExpr>(); 317 new (data) SymSymExpr(lhs, op, rhs, t); 318 DataSet.InsertNode(data, InsertPos); 319 } 320 321 return cast<SymSymExpr>(data); 322 } 323 324 QualType SymbolConjured::getType() const { 325 return T; 326 } 327 328 QualType SymbolDerived::getType() const { 329 return R->getValueType(); 330 } 331 332 QualType SymbolExtent::getType() const { 333 ASTContext &Ctx = R->getMemRegionManager()->getContext(); 334 return Ctx.getSizeType(); 335 } 336 337 QualType SymbolMetadata::getType() const { 338 return T; 339 } 340 341 QualType SymbolRegionValue::getType() const { 342 return R->getValueType(); 343 } 344 345 SymbolManager::~SymbolManager() { 346 llvm::DeleteContainerSeconds(SymbolDependencies); 347 } 348 349 bool SymbolManager::canSymbolicate(QualType T) { 350 T = T.getCanonicalType(); 351 352 if (Loc::isLocType(T)) 353 return true; 354 355 if (T->isIntegralOrEnumerationType()) 356 return true; 357 358 if (T->isRecordType() && !T->isUnionType()) 359 return true; 360 361 return false; 362 } 363 364 void SymbolManager::addSymbolDependency(const SymbolRef Primary, 365 const SymbolRef Dependent) { 366 SymbolDependTy::iterator I = SymbolDependencies.find(Primary); 367 SymbolRefSmallVectorTy *dependencies = nullptr; 368 if (I == SymbolDependencies.end()) { 369 dependencies = new SymbolRefSmallVectorTy(); 370 SymbolDependencies[Primary] = dependencies; 371 } else { 372 dependencies = I->second; 373 } 374 dependencies->push_back(Dependent); 375 } 376 377 const SymbolRefSmallVectorTy *SymbolManager::getDependentSymbols( 378 const SymbolRef Primary) { 379 SymbolDependTy::const_iterator I = SymbolDependencies.find(Primary); 380 if (I == SymbolDependencies.end()) 381 return nullptr; 382 return I->second; 383 } 384 385 void SymbolReaper::markDependentsLive(SymbolRef sym) { 386 // Do not mark dependents more then once. 387 SymbolMapTy::iterator LI = TheLiving.find(sym); 388 assert(LI != TheLiving.end() && "The primary symbol is not live."); 389 if (LI->second == HaveMarkedDependents) 390 return; 391 LI->second = HaveMarkedDependents; 392 393 if (const SymbolRefSmallVectorTy *Deps = SymMgr.getDependentSymbols(sym)) { 394 for (const auto I : *Deps) { 395 if (TheLiving.find(I) != TheLiving.end()) 396 continue; 397 markLive(I); 398 } 399 } 400 } 401 402 void SymbolReaper::markLive(SymbolRef sym) { 403 TheLiving[sym] = NotProcessed; 404 markDependentsLive(sym); 405 } 406 407 void SymbolReaper::markLive(const MemRegion *region) { 408 RegionRoots.insert(region->getBaseRegion()); 409 markElementIndicesLive(region); 410 } 411 412 void SymbolReaper::markElementIndicesLive(const MemRegion *region) { 413 for (auto SR = dyn_cast<SubRegion>(region); SR; 414 SR = dyn_cast<SubRegion>(SR->getSuperRegion())) { 415 if (const auto ER = dyn_cast<ElementRegion>(SR)) { 416 SVal Idx = ER->getIndex(); 417 for (auto SI = Idx.symbol_begin(), SE = Idx.symbol_end(); SI != SE; ++SI) 418 markLive(*SI); 419 } 420 } 421 } 422 423 void SymbolReaper::markInUse(SymbolRef sym) { 424 if (isa<SymbolMetadata>(sym)) 425 MetadataInUse.insert(sym); 426 } 427 428 bool SymbolReaper::isLiveRegion(const MemRegion *MR) { 429 // TODO: For now, liveness of a memory region is equivalent to liveness of its 430 // base region. In fact we can do a bit better: say, if a particular FieldDecl 431 // is not used later in the path, we can diagnose a leak of a value within 432 // that field earlier than, say, the variable that contains the field dies. 433 MR = MR->getBaseRegion(); 434 435 if (RegionRoots.count(MR)) 436 return true; 437 438 if (const auto *SR = dyn_cast<SymbolicRegion>(MR)) 439 return isLive(SR->getSymbol()); 440 441 if (const auto *VR = dyn_cast<VarRegion>(MR)) 442 return isLive(VR, true); 443 444 // FIXME: This is a gross over-approximation. What we really need is a way to 445 // tell if anything still refers to this region. Unlike SymbolicRegions, 446 // AllocaRegions don't have associated symbols, though, so we don't actually 447 // have a way to track their liveness. 448 if (isa<AllocaRegion>(MR)) 449 return true; 450 451 if (isa<CXXThisRegion>(MR)) 452 return true; 453 454 if (isa<MemSpaceRegion>(MR)) 455 return true; 456 457 if (isa<CodeTextRegion>(MR)) 458 return true; 459 460 return false; 461 } 462 463 bool SymbolReaper::isLive(SymbolRef sym) { 464 if (TheLiving.count(sym)) { 465 markDependentsLive(sym); 466 return true; 467 } 468 469 bool KnownLive; 470 471 switch (sym->getKind()) { 472 case SymExpr::SymbolRegionValueKind: 473 KnownLive = isLiveRegion(cast<SymbolRegionValue>(sym)->getRegion()); 474 break; 475 case SymExpr::SymbolConjuredKind: 476 KnownLive = false; 477 break; 478 case SymExpr::SymbolDerivedKind: 479 KnownLive = isLive(cast<SymbolDerived>(sym)->getParentSymbol()); 480 break; 481 case SymExpr::SymbolExtentKind: 482 KnownLive = isLiveRegion(cast<SymbolExtent>(sym)->getRegion()); 483 break; 484 case SymExpr::SymbolMetadataKind: 485 KnownLive = MetadataInUse.count(sym) && 486 isLiveRegion(cast<SymbolMetadata>(sym)->getRegion()); 487 if (KnownLive) 488 MetadataInUse.erase(sym); 489 break; 490 case SymExpr::SymIntExprKind: 491 KnownLive = isLive(cast<SymIntExpr>(sym)->getLHS()); 492 break; 493 case SymExpr::IntSymExprKind: 494 KnownLive = isLive(cast<IntSymExpr>(sym)->getRHS()); 495 break; 496 case SymExpr::SymSymExprKind: 497 KnownLive = isLive(cast<SymSymExpr>(sym)->getLHS()) && 498 isLive(cast<SymSymExpr>(sym)->getRHS()); 499 break; 500 case SymExpr::SymbolCastKind: 501 KnownLive = isLive(cast<SymbolCast>(sym)->getOperand()); 502 break; 503 } 504 505 if (KnownLive) 506 markLive(sym); 507 508 return KnownLive; 509 } 510 511 bool 512 SymbolReaper::isLive(const Stmt *ExprVal, const LocationContext *ELCtx) const { 513 if (LCtx == nullptr) 514 return false; 515 516 if (LCtx != ELCtx) { 517 // If the reaper's location context is a parent of the expression's 518 // location context, then the expression value is now "out of scope". 519 if (LCtx->isParentOf(ELCtx)) 520 return false; 521 return true; 522 } 523 524 // If no statement is provided, everything is this and parent contexts is live. 525 if (!Loc) 526 return true; 527 528 return LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, ExprVal); 529 } 530 531 bool SymbolReaper::isLive(const VarRegion *VR, bool includeStoreBindings) const{ 532 const StackFrameContext *VarContext = VR->getStackFrame(); 533 534 if (!VarContext) 535 return true; 536 537 if (!LCtx) 538 return false; 539 const StackFrameContext *CurrentContext = LCtx->getStackFrame(); 540 541 if (VarContext == CurrentContext) { 542 // If no statement is provided, everything is live. 543 if (!Loc) 544 return true; 545 546 if (LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, VR->getDecl())) 547 return true; 548 549 if (!includeStoreBindings) 550 return false; 551 552 unsigned &cachedQuery = 553 const_cast<SymbolReaper *>(this)->includedRegionCache[VR]; 554 555 if (cachedQuery) { 556 return cachedQuery == 1; 557 } 558 559 // Query the store to see if the region occurs in any live bindings. 560 if (Store store = reapedStore.getStore()) { 561 bool hasRegion = 562 reapedStore.getStoreManager().includedInBindings(store, VR); 563 cachedQuery = hasRegion ? 1 : 2; 564 return hasRegion; 565 } 566 567 return false; 568 } 569 570 return VarContext->isParentOf(CurrentContext); 571 } 572