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/Support/Compiler.h"
25 #include "llvm/Support/ErrorHandling.h"
26 #include "llvm/Support/raw_ostream.h"
27 #include <cassert>
28
29 using namespace clang;
30 using namespace ento;
31
anchor()32 void SymExpr::anchor() {}
33
getKindStr() const34 StringRef SymbolConjured::getKindStr() const { return "conj_$"; }
getKindStr() const35 StringRef SymbolDerived::getKindStr() const { return "derived_$"; }
getKindStr() const36 StringRef SymbolExtent::getKindStr() const { return "extent_$"; }
getKindStr() const37 StringRef SymbolMetadata::getKindStr() const { return "meta_$"; }
getKindStr() const38 StringRef SymbolRegionValue::getKindStr() const { return "reg_$"; }
39
dump() const40 LLVM_DUMP_METHOD void SymExpr::dump() const { dumpToStream(llvm::errs()); }
41
dumpToStreamImpl(raw_ostream & OS,const SymExpr * Sym)42 void BinarySymExpr::dumpToStreamImpl(raw_ostream &OS, const SymExpr *Sym) {
43 OS << '(';
44 Sym->dumpToStream(OS);
45 OS << ')';
46 }
47
dumpToStreamImpl(raw_ostream & OS,const llvm::APSInt & Value)48 void BinarySymExpr::dumpToStreamImpl(raw_ostream &OS,
49 const llvm::APSInt &Value) {
50 if (Value.isUnsigned())
51 OS << Value.getZExtValue();
52 else
53 OS << Value.getSExtValue();
54 if (Value.isUnsigned())
55 OS << 'U';
56 }
57
dumpToStreamImpl(raw_ostream & OS,BinaryOperator::Opcode Op)58 void BinarySymExpr::dumpToStreamImpl(raw_ostream &OS,
59 BinaryOperator::Opcode Op) {
60 OS << ' ' << BinaryOperator::getOpcodeStr(Op) << ' ';
61 }
62
dumpToStream(raw_ostream & os) const63 void SymbolCast::dumpToStream(raw_ostream &os) const {
64 os << '(' << ToTy << ") (";
65 Operand->dumpToStream(os);
66 os << ')';
67 }
68
dumpToStream(raw_ostream & os) const69 void UnarySymExpr::dumpToStream(raw_ostream &os) const {
70 os << UnaryOperator::getOpcodeStr(Op);
71 bool Binary = isa<BinarySymExpr>(Operand);
72 if (Binary)
73 os << '(';
74 Operand->dumpToStream(os);
75 if (Binary)
76 os << ')';
77 }
78
getStmt() const79 const Stmt *SymbolConjured::getStmt() const {
80 // Sometimes the CFG element is invalid, avoid dereferencing it.
81 if (Elem.getParent() == nullptr ||
82 Elem.getIndexInBlock() >= Elem.getParent()->size())
83 return nullptr;
84 switch (Elem->getKind()) {
85 case CFGElement::Initializer:
86 if (const auto *Init = Elem->castAs<CFGInitializer>().getInitializer()) {
87 return Init->getInit();
88 }
89 return nullptr;
90 case CFGElement::ScopeBegin:
91 return Elem->castAs<CFGScopeBegin>().getTriggerStmt();
92 case CFGElement::ScopeEnd:
93 return Elem->castAs<CFGScopeEnd>().getTriggerStmt();
94 case CFGElement::NewAllocator:
95 return Elem->castAs<CFGNewAllocator>().getAllocatorExpr();
96 case CFGElement::LifetimeEnds:
97 return Elem->castAs<CFGLifetimeEnds>().getTriggerStmt();
98 case CFGElement::LoopExit:
99 return Elem->castAs<CFGLoopExit>().getLoopStmt();
100 case CFGElement::Statement:
101 return Elem->castAs<CFGStmt>().getStmt();
102 case CFGElement::Constructor:
103 return Elem->castAs<CFGConstructor>().getStmt();
104 case CFGElement::CXXRecordTypedCall:
105 return Elem->castAs<CFGCXXRecordTypedCall>().getStmt();
106 case CFGElement::AutomaticObjectDtor:
107 return Elem->castAs<CFGAutomaticObjDtor>().getTriggerStmt();
108 case CFGElement::DeleteDtor:
109 return Elem->castAs<CFGDeleteDtor>().getDeleteExpr();
110 case CFGElement::BaseDtor:
111 return nullptr;
112 case CFGElement::MemberDtor:
113 return nullptr;
114 case CFGElement::TemporaryDtor:
115 return Elem->castAs<CFGTemporaryDtor>().getBindTemporaryExpr();
116 case CFGElement::CleanupFunction:
117 return nullptr;
118 }
119 return nullptr;
120 }
121
dumpToStream(raw_ostream & os) const122 void SymbolConjured::dumpToStream(raw_ostream &os) const {
123 os << getKindStr() << getSymbolID() << '{' << T << ", LC" << LCtx->getID();
124 if (auto *S = getStmt())
125 os << ", S" << S->getID(LCtx->getDecl()->getASTContext());
126 else
127 os << ", no stmt";
128 os << ", #" << Count << '}';
129 }
130
dumpToStream(raw_ostream & os) const131 void SymbolDerived::dumpToStream(raw_ostream &os) const {
132 os << getKindStr() << getSymbolID() << '{' << getParentSymbol() << ','
133 << getRegion() << '}';
134 }
135
dumpToStream(raw_ostream & os) const136 void SymbolExtent::dumpToStream(raw_ostream &os) const {
137 os << getKindStr() << getSymbolID() << '{' << getRegion() << '}';
138 }
139
dumpToStream(raw_ostream & os) const140 void SymbolMetadata::dumpToStream(raw_ostream &os) const {
141 os << getKindStr() << getSymbolID() << '{' << getRegion() << ',' << T << '}';
142 }
143
anchor()144 void SymbolData::anchor() {}
145
dumpToStream(raw_ostream & os) const146 void SymbolRegionValue::dumpToStream(raw_ostream &os) const {
147 os << getKindStr() << getSymbolID() << '<' << getType() << ' ' << R << '>';
148 }
149
operator ==(const symbol_iterator & X) const150 bool SymExpr::symbol_iterator::operator==(const symbol_iterator &X) const {
151 return itr == X.itr;
152 }
153
operator !=(const symbol_iterator & X) const154 bool SymExpr::symbol_iterator::operator!=(const symbol_iterator &X) const {
155 return itr != X.itr;
156 }
157
symbol_iterator(const SymExpr * SE)158 SymExpr::symbol_iterator::symbol_iterator(const SymExpr *SE) {
159 itr.push_back(SE);
160 }
161
operator ++()162 SymExpr::symbol_iterator &SymExpr::symbol_iterator::operator++() {
163 assert(!itr.empty() && "attempting to iterate on an 'end' iterator");
164 expand();
165 return *this;
166 }
167
operator *()168 SymbolRef SymExpr::symbol_iterator::operator*() {
169 assert(!itr.empty() && "attempting to dereference an 'end' iterator");
170 return itr.back();
171 }
172
expand()173 void SymExpr::symbol_iterator::expand() {
174 const SymExpr *SE = itr.pop_back_val();
175
176 switch (SE->getKind()) {
177 case SymExpr::SymbolRegionValueKind:
178 case SymExpr::SymbolConjuredKind:
179 case SymExpr::SymbolDerivedKind:
180 case SymExpr::SymbolExtentKind:
181 case SymExpr::SymbolMetadataKind:
182 return;
183 case SymExpr::SymbolCastKind:
184 itr.push_back(cast<SymbolCast>(SE)->getOperand());
185 return;
186 case SymExpr::UnarySymExprKind:
187 itr.push_back(cast<UnarySymExpr>(SE)->getOperand());
188 return;
189 case SymExpr::SymIntExprKind:
190 itr.push_back(cast<SymIntExpr>(SE)->getLHS());
191 return;
192 case SymExpr::IntSymExprKind:
193 itr.push_back(cast<IntSymExpr>(SE)->getRHS());
194 return;
195 case SymExpr::SymSymExprKind: {
196 const auto *x = cast<SymSymExpr>(SE);
197 itr.push_back(x->getLHS());
198 itr.push_back(x->getRHS());
199 return;
200 }
201 }
202 llvm_unreachable("unhandled expansion case");
203 }
204
getType() const205 QualType SymbolConjured::getType() const {
206 return T;
207 }
208
getType() const209 QualType SymbolDerived::getType() const {
210 return R->getValueType();
211 }
212
getType() const213 QualType SymbolExtent::getType() const {
214 ASTContext &Ctx = R->getMemRegionManager().getContext();
215 return Ctx.getSizeType();
216 }
217
getType() const218 QualType SymbolMetadata::getType() const {
219 return T;
220 }
221
getType() const222 QualType SymbolRegionValue::getType() const {
223 return R->getValueType();
224 }
225
canSymbolicate(QualType T)226 bool SymbolManager::canSymbolicate(QualType T) {
227 T = T.getCanonicalType();
228
229 if (Loc::isLocType(T))
230 return true;
231
232 if (T->isIntegralOrEnumerationType())
233 return true;
234
235 if (T->isRecordType() && !T->isUnionType())
236 return true;
237
238 return false;
239 }
240
addSymbolDependency(const SymbolRef Primary,const SymbolRef Dependent)241 void SymbolManager::addSymbolDependency(const SymbolRef Primary,
242 const SymbolRef Dependent) {
243 auto &dependencies = SymbolDependencies[Primary];
244 if (!dependencies) {
245 dependencies = std::make_unique<SymbolRefSmallVectorTy>();
246 }
247 dependencies->push_back(Dependent);
248 }
249
getDependentSymbols(const SymbolRef Primary)250 const SymbolRefSmallVectorTy *SymbolManager::getDependentSymbols(
251 const SymbolRef Primary) {
252 SymbolDependTy::const_iterator I = SymbolDependencies.find(Primary);
253 if (I == SymbolDependencies.end())
254 return nullptr;
255 return I->second.get();
256 }
257
markDependentsLive(SymbolRef sym)258 void SymbolReaper::markDependentsLive(SymbolRef sym) {
259 // Do not mark dependents more then once.
260 SymbolMapTy::iterator LI = TheLiving.find(sym);
261 assert(LI != TheLiving.end() && "The primary symbol is not live.");
262 if (LI->second == HaveMarkedDependents)
263 return;
264 LI->second = HaveMarkedDependents;
265
266 if (const SymbolRefSmallVectorTy *Deps = SymMgr.getDependentSymbols(sym)) {
267 for (const auto I : *Deps) {
268 if (TheLiving.contains(I))
269 continue;
270 markLive(I);
271 }
272 }
273 }
274
markLive(SymbolRef sym)275 void SymbolReaper::markLive(SymbolRef sym) {
276 TheLiving[sym] = NotProcessed;
277 markDependentsLive(sym);
278 }
279
markLive(const MemRegion * region)280 void SymbolReaper::markLive(const MemRegion *region) {
281 LiveRegionRoots.insert(region->getBaseRegion());
282 markElementIndicesLive(region);
283 }
284
markLazilyCopied(const clang::ento::MemRegion * region)285 void SymbolReaper::markLazilyCopied(const clang::ento::MemRegion *region) {
286 LazilyCopiedRegionRoots.insert(region->getBaseRegion());
287 }
288
markElementIndicesLive(const MemRegion * region)289 void SymbolReaper::markElementIndicesLive(const MemRegion *region) {
290 for (auto SR = dyn_cast<SubRegion>(region); SR;
291 SR = dyn_cast<SubRegion>(SR->getSuperRegion())) {
292 if (const auto ER = dyn_cast<ElementRegion>(SR)) {
293 SVal Idx = ER->getIndex();
294 for (SymbolRef Sym : Idx.symbols())
295 markLive(Sym);
296 }
297 }
298 }
299
markInUse(SymbolRef sym)300 void SymbolReaper::markInUse(SymbolRef sym) {
301 if (isa<SymbolMetadata>(sym))
302 MetadataInUse.insert(sym);
303 }
304
isLiveRegion(const MemRegion * MR)305 bool SymbolReaper::isLiveRegion(const MemRegion *MR) {
306 // TODO: For now, liveness of a memory region is equivalent to liveness of its
307 // base region. In fact we can do a bit better: say, if a particular FieldDecl
308 // is not used later in the path, we can diagnose a leak of a value within
309 // that field earlier than, say, the variable that contains the field dies.
310 MR = MR->getBaseRegion();
311 if (LiveRegionRoots.count(MR))
312 return true;
313
314 if (const auto *SR = dyn_cast<SymbolicRegion>(MR))
315 return isLive(SR->getSymbol());
316
317 if (const auto *VR = dyn_cast<VarRegion>(MR))
318 return isLive(VR, true);
319
320 // FIXME: This is a gross over-approximation. What we really need is a way to
321 // tell if anything still refers to this region. Unlike SymbolicRegions,
322 // AllocaRegions don't have associated symbols, though, so we don't actually
323 // have a way to track their liveness.
324 return isa<AllocaRegion, CXXThisRegion, MemSpaceRegion, CodeTextRegion>(MR);
325 }
326
isLazilyCopiedRegion(const MemRegion * MR) const327 bool SymbolReaper::isLazilyCopiedRegion(const MemRegion *MR) const {
328 // TODO: See comment in isLiveRegion.
329 return LazilyCopiedRegionRoots.count(MR->getBaseRegion());
330 }
331
isReadableRegion(const MemRegion * MR)332 bool SymbolReaper::isReadableRegion(const MemRegion *MR) {
333 return isLiveRegion(MR) || isLazilyCopiedRegion(MR);
334 }
335
isLive(SymbolRef sym)336 bool SymbolReaper::isLive(SymbolRef sym) {
337 if (TheLiving.count(sym)) {
338 markDependentsLive(sym);
339 return true;
340 }
341
342 bool KnownLive;
343
344 switch (sym->getKind()) {
345 case SymExpr::SymbolRegionValueKind:
346 KnownLive = isReadableRegion(cast<SymbolRegionValue>(sym)->getRegion());
347 break;
348 case SymExpr::SymbolConjuredKind:
349 KnownLive = false;
350 break;
351 case SymExpr::SymbolDerivedKind:
352 KnownLive = isLive(cast<SymbolDerived>(sym)->getParentSymbol());
353 break;
354 case SymExpr::SymbolExtentKind:
355 KnownLive = isLiveRegion(cast<SymbolExtent>(sym)->getRegion());
356 break;
357 case SymExpr::SymbolMetadataKind:
358 KnownLive = MetadataInUse.count(sym) &&
359 isLiveRegion(cast<SymbolMetadata>(sym)->getRegion());
360 if (KnownLive)
361 MetadataInUse.erase(sym);
362 break;
363 case SymExpr::SymIntExprKind:
364 KnownLive = isLive(cast<SymIntExpr>(sym)->getLHS());
365 break;
366 case SymExpr::IntSymExprKind:
367 KnownLive = isLive(cast<IntSymExpr>(sym)->getRHS());
368 break;
369 case SymExpr::SymSymExprKind:
370 KnownLive = isLive(cast<SymSymExpr>(sym)->getLHS()) &&
371 isLive(cast<SymSymExpr>(sym)->getRHS());
372 break;
373 case SymExpr::SymbolCastKind:
374 KnownLive = isLive(cast<SymbolCast>(sym)->getOperand());
375 break;
376 case SymExpr::UnarySymExprKind:
377 KnownLive = isLive(cast<UnarySymExpr>(sym)->getOperand());
378 break;
379 }
380
381 if (KnownLive)
382 markLive(sym);
383
384 return KnownLive;
385 }
386
387 bool
isLive(const Expr * ExprVal,const LocationContext * ELCtx) const388 SymbolReaper::isLive(const Expr *ExprVal, const LocationContext *ELCtx) const {
389 if (LCtx == nullptr)
390 return false;
391
392 if (LCtx != ELCtx) {
393 // If the reaper's location context is a parent of the expression's
394 // location context, then the expression value is now "out of scope".
395 if (LCtx->isParentOf(ELCtx))
396 return false;
397 return true;
398 }
399
400 // If no statement is provided, everything in this and parent contexts is
401 // live.
402 if (!Loc)
403 return true;
404
405 return LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, ExprVal);
406 }
407
isLive(const VarRegion * VR,bool includeStoreBindings) const408 bool SymbolReaper::isLive(const VarRegion *VR, bool includeStoreBindings) const{
409 const StackFrameContext *VarContext = VR->getStackFrame();
410
411 if (!VarContext)
412 return true;
413
414 if (!LCtx)
415 return false;
416 const StackFrameContext *CurrentContext = LCtx->getStackFrame();
417
418 if (VarContext == CurrentContext) {
419 // If no statement is provided, everything is live.
420 if (!Loc)
421 return true;
422
423 // Anonymous parameters of an inheriting constructor are live for the entire
424 // duration of the constructor.
425 if (isa<CXXInheritedCtorInitExpr>(Loc))
426 return true;
427
428 if (LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, VR->getDecl()))
429 return true;
430
431 if (!includeStoreBindings)
432 return false;
433
434 unsigned &cachedQuery =
435 const_cast<SymbolReaper *>(this)->includedRegionCache[VR];
436
437 if (cachedQuery) {
438 return cachedQuery == 1;
439 }
440
441 // Query the store to see if the region occurs in any live bindings.
442 if (Store store = reapedStore.getStore()) {
443 bool hasRegion =
444 reapedStore.getStoreManager().includedInBindings(store, VR);
445 cachedQuery = hasRegion ? 1 : 2;
446 return hasRegion;
447 }
448
449 return false;
450 }
451
452 return VarContext->isParentOf(CurrentContext);
453 }
454