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