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