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 | |
32 | void SymExpr::anchor() {} |
33 | |
34 | StringRef SymbolConjured::getKindStr() const { return "conj_$"; } |
35 | StringRef SymbolDerived::getKindStr() const { return "derived_$"; } |
36 | StringRef SymbolExtent::getKindStr() const { return "extent_$"; } |
37 | StringRef SymbolMetadata::getKindStr() const { return "meta_$"; } |
38 | StringRef SymbolRegionValue::getKindStr() const { return "reg_$"; } |
39 | |
40 | LLVM_DUMP_METHOD void SymExpr::dump() const { dumpToStream(os&: llvm::errs()); } |
41 | |
42 | void BinarySymExpr::dumpToStreamImpl(raw_ostream &OS, const SymExpr *Sym) { |
43 | OS << '('; |
44 | Sym->dumpToStream(os&: OS); |
45 | OS << ')'; |
46 | } |
47 | |
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 | |
58 | void BinarySymExpr::dumpToStreamImpl(raw_ostream &OS, |
59 | BinaryOperator::Opcode Op) { |
60 | OS << ' ' << BinaryOperator::getOpcodeStr(Op) << ' '; |
61 | } |
62 | |
63 | void SymbolCast::dumpToStream(raw_ostream &os) const { |
64 | os << '(' << ToTy << ") ("; |
65 | Operand->dumpToStream(os); |
66 | os << ')'; |
67 | } |
68 | |
69 | void UnarySymExpr::dumpToStream(raw_ostream &os) const { |
70 | os << UnaryOperator::getOpcodeStr(Op); |
71 | bool Binary = isa<BinarySymExpr>(Val: Operand); |
72 | if (Binary) |
73 | os << '('; |
74 | Operand->dumpToStream(os); |
75 | if (Binary) |
76 | os << ')'; |
77 | } |
78 | |
79 | 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 | |
122 | 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(Context: LCtx->getDecl()->getASTContext()); |
126 | else |
127 | os << ", no stmt"; |
128 | os << ", #"<< Count << '}'; |
129 | } |
130 | |
131 | void SymbolDerived::dumpToStream(raw_ostream &os) const { |
132 | os << getKindStr() << getSymbolID() << '{' << getParentSymbol() << ',' |
133 | << getRegion() << '}'; |
134 | } |
135 | |
136 | void SymbolExtent::dumpToStream(raw_ostream &os) const { |
137 | os << getKindStr() << getSymbolID() << '{' << getRegion() << '}'; |
138 | } |
139 | |
140 | void SymbolMetadata::dumpToStream(raw_ostream &os) const { |
141 | os << getKindStr() << getSymbolID() << '{' << getRegion() << ',' << T << '}'; |
142 | } |
143 | |
144 | void SymbolData::anchor() {} |
145 | |
146 | void SymbolRegionValue::dumpToStream(raw_ostream &os) const { |
147 | os << getKindStr() << getSymbolID() << '<' << getType() << ' ' << R << '>'; |
148 | } |
149 | |
150 | bool SymExpr::symbol_iterator::operator==(const symbol_iterator &X) const { |
151 | return itr == X.itr; |
152 | } |
153 | |
154 | bool SymExpr::symbol_iterator::operator!=(const symbol_iterator &X) const { |
155 | return itr != X.itr; |
156 | } |
157 | |
158 | SymExpr::symbol_iterator::symbol_iterator(const SymExpr *SE) { |
159 | itr.push_back(Elt: SE); |
160 | } |
161 | |
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 | |
168 | SymbolRef SymExpr::symbol_iterator::operator*() { |
169 | assert(!itr.empty() && "attempting to dereference an 'end' iterator"); |
170 | return itr.back(); |
171 | } |
172 | |
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(Elt: cast<SymbolCast>(Val: SE)->getOperand()); |
185 | return; |
186 | case SymExpr::UnarySymExprKind: |
187 | itr.push_back(Elt: cast<UnarySymExpr>(Val: SE)->getOperand()); |
188 | return; |
189 | case SymExpr::SymIntExprKind: |
190 | itr.push_back(Elt: cast<SymIntExpr>(Val: SE)->getLHS()); |
191 | return; |
192 | case SymExpr::IntSymExprKind: |
193 | itr.push_back(Elt: cast<IntSymExpr>(Val: SE)->getRHS()); |
194 | return; |
195 | case SymExpr::SymSymExprKind: { |
196 | const auto *x = cast<SymSymExpr>(Val: SE); |
197 | itr.push_back(Elt: x->getLHS()); |
198 | itr.push_back(Elt: x->getRHS()); |
199 | return; |
200 | } |
201 | } |
202 | llvm_unreachable("unhandled expansion case"); |
203 | } |
204 | |
205 | QualType SymbolConjured::getType() const { |
206 | return T; |
207 | } |
208 | |
209 | QualType SymbolDerived::getType() const { |
210 | return R->getValueType(); |
211 | } |
212 | |
213 | QualType SymbolExtent::getType() const { |
214 | ASTContext &Ctx = R->getMemRegionManager().getContext(); |
215 | return Ctx.getSizeType(); |
216 | } |
217 | |
218 | QualType SymbolMetadata::getType() const { |
219 | return T; |
220 | } |
221 | |
222 | QualType SymbolRegionValue::getType() const { |
223 | return R->getValueType(); |
224 | } |
225 | |
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 | |
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(Elt: Dependent); |
248 | } |
249 | |
250 | const SymbolRefSmallVectorTy *SymbolManager::getDependentSymbols( |
251 | const SymbolRef Primary) { |
252 | SymbolDependTy::const_iterator I = SymbolDependencies.find(Val: Primary); |
253 | if (I == SymbolDependencies.end()) |
254 | return nullptr; |
255 | return I->second.get(); |
256 | } |
257 | |
258 | void SymbolReaper::markDependentsLive(SymbolRef sym) { |
259 | // Do not mark dependents more then once. |
260 | SymbolMapTy::iterator LI = TheLiving.find(Val: 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(Primary: sym)) { |
267 | for (const auto I : *Deps) { |
268 | if (TheLiving.contains(Val: I)) |
269 | continue; |
270 | markLive(sym: I); |
271 | } |
272 | } |
273 | } |
274 | |
275 | void SymbolReaper::markLive(SymbolRef sym) { |
276 | TheLiving[sym] = NotProcessed; |
277 | markDependentsLive(sym); |
278 | } |
279 | |
280 | void SymbolReaper::markLive(const MemRegion *region) { |
281 | LiveRegionRoots.insert(V: region->getBaseRegion()); |
282 | markElementIndicesLive(region); |
283 | } |
284 | |
285 | void SymbolReaper::markLazilyCopied(const clang::ento::MemRegion *region) { |
286 | LazilyCopiedRegionRoots.insert(V: region->getBaseRegion()); |
287 | } |
288 | |
289 | void SymbolReaper::markElementIndicesLive(const MemRegion *region) { |
290 | for (auto SR = dyn_cast<SubRegion>(Val: region); SR; |
291 | SR = dyn_cast<SubRegion>(Val: SR->getSuperRegion())) { |
292 | if (const auto ER = dyn_cast<ElementRegion>(Val: SR)) { |
293 | SVal Idx = ER->getIndex(); |
294 | for (SymbolRef Sym : Idx.symbols()) |
295 | markLive(sym: Sym); |
296 | } |
297 | } |
298 | } |
299 | |
300 | void SymbolReaper::markInUse(SymbolRef sym) { |
301 | if (isa<SymbolMetadata>(Val: sym)) |
302 | MetadataInUse.insert(V: sym); |
303 | } |
304 | |
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(V: MR)) |
312 | return true; |
313 | |
314 | if (const auto *SR = dyn_cast<SymbolicRegion>(Val: MR)) |
315 | return isLive(sym: SR->getSymbol()); |
316 | |
317 | if (const auto *VR = dyn_cast<VarRegion>(Val: MR)) |
318 | return isLive(VR, includeStoreBindings: 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>(Val: MR); |
325 | } |
326 | |
327 | bool SymbolReaper::isLazilyCopiedRegion(const MemRegion *MR) const { |
328 | // TODO: See comment in isLiveRegion. |
329 | return LazilyCopiedRegionRoots.count(V: MR->getBaseRegion()); |
330 | } |
331 | |
332 | bool SymbolReaper::isReadableRegion(const MemRegion *MR) { |
333 | return isLiveRegion(MR) || isLazilyCopiedRegion(MR); |
334 | } |
335 | |
336 | bool SymbolReaper::isLive(SymbolRef sym) { |
337 | if (TheLiving.count(Val: sym)) { |
338 | markDependentsLive(sym); |
339 | return true; |
340 | } |
341 | |
342 | bool KnownLive; |
343 | |
344 | switch (sym->getKind()) { |
345 | case SymExpr::SymbolRegionValueKind: |
346 | KnownLive = isReadableRegion(MR: cast<SymbolRegionValue>(Val: sym)->getRegion()); |
347 | break; |
348 | case SymExpr::SymbolConjuredKind: |
349 | KnownLive = false; |
350 | break; |
351 | case SymExpr::SymbolDerivedKind: |
352 | KnownLive = isLive(sym: cast<SymbolDerived>(Val: sym)->getParentSymbol()); |
353 | break; |
354 | case SymExpr::SymbolExtentKind: |
355 | KnownLive = isLiveRegion(MR: cast<SymbolExtent>(Val: sym)->getRegion()); |
356 | break; |
357 | case SymExpr::SymbolMetadataKind: |
358 | KnownLive = MetadataInUse.count(V: sym) && |
359 | isLiveRegion(MR: cast<SymbolMetadata>(Val: sym)->getRegion()); |
360 | if (KnownLive) |
361 | MetadataInUse.erase(V: sym); |
362 | break; |
363 | case SymExpr::SymIntExprKind: |
364 | KnownLive = isLive(sym: cast<SymIntExpr>(Val: sym)->getLHS()); |
365 | break; |
366 | case SymExpr::IntSymExprKind: |
367 | KnownLive = isLive(sym: cast<IntSymExpr>(Val: sym)->getRHS()); |
368 | break; |
369 | case SymExpr::SymSymExprKind: |
370 | KnownLive = isLive(sym: cast<SymSymExpr>(Val: sym)->getLHS()) && |
371 | isLive(sym: cast<SymSymExpr>(Val: sym)->getRHS()); |
372 | break; |
373 | case SymExpr::SymbolCastKind: |
374 | KnownLive = isLive(sym: cast<SymbolCast>(Val: sym)->getOperand()); |
375 | break; |
376 | case SymExpr::UnarySymExprKind: |
377 | KnownLive = isLive(sym: cast<UnarySymExpr>(Val: sym)->getOperand()); |
378 | break; |
379 | } |
380 | |
381 | if (KnownLive) |
382 | markLive(sym); |
383 | |
384 | return KnownLive; |
385 | } |
386 | |
387 | bool |
388 | 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(LC: 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, Val: ExprVal); |
406 | } |
407 | |
408 | 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>(Val: Loc)) |
426 | return true; |
427 | |
428 | if (LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(S: Loc, D: 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, region: VR); |
445 | cachedQuery = hasRegion ? 1 : 2; |
446 | return hasRegion; |
447 | } |
448 | |
449 | return false; |
450 | } |
451 | |
452 | return VarContext->isParentOf(LC: CurrentContext); |
453 | } |
454 |
Definitions
- anchor
- getKindStr
- getKindStr
- getKindStr
- getKindStr
- getKindStr
- dump
- dumpToStreamImpl
- dumpToStreamImpl
- dumpToStreamImpl
- dumpToStream
- dumpToStream
- getStmt
- dumpToStream
- dumpToStream
- dumpToStream
- dumpToStream
- anchor
- dumpToStream
- operator==
- operator!=
- symbol_iterator
- operator++
- operator*
- expand
- getType
- getType
- getType
- getType
- getType
- canSymbolicate
- addSymbolDependency
- getDependentSymbols
- markDependentsLive
- markLive
- markLive
- markLazilyCopied
- markElementIndicesLive
- markInUse
- isLiveRegion
- isLazilyCopiedRegion
- isReadableRegion
- isLive
- isLive
Improve your Profiling and Debugging skills
Find out more