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