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
32 using namespace clang;
33 using namespace ento;
34
anchor()35 void SymExpr::anchor() {}
36
dump() const37 LLVM_DUMP_METHOD void SymExpr::dump() const { dumpToStream(llvm::errs()); }
38
dumpToStreamImpl(raw_ostream & OS,const SymExpr * Sym)39 void BinarySymExpr::dumpToStreamImpl(raw_ostream &OS, const SymExpr *Sym) {
40 OS << '(';
41 Sym->dumpToStream(OS);
42 OS << ')';
43 }
44
dumpToStreamImpl(raw_ostream & OS,const llvm::APSInt & Value)45 void 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
dumpToStreamImpl(raw_ostream & OS,BinaryOperator::Opcode Op)55 void BinarySymExpr::dumpToStreamImpl(raw_ostream &OS,
56 BinaryOperator::Opcode Op) {
57 OS << ' ' << BinaryOperator::getOpcodeStr(Op) << ' ';
58 }
59
dumpToStream(raw_ostream & os) const60 void SymbolCast::dumpToStream(raw_ostream &os) const {
61 os << '(' << ToTy.getAsString() << ") (";
62 Operand->dumpToStream(os);
63 os << ')';
64 }
65
dumpToStream(raw_ostream & os) const66 void 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
dumpToStream(raw_ostream & os) const76 void SymbolDerived::dumpToStream(raw_ostream &os) const {
77 os << "derived_$" << getSymbolID() << '{'
78 << getParentSymbol() << ',' << getRegion() << '}';
79 }
80
dumpToStream(raw_ostream & os) const81 void SymbolExtent::dumpToStream(raw_ostream &os) const {
82 os << "extent_$" << getSymbolID() << '{' << getRegion() << '}';
83 }
84
dumpToStream(raw_ostream & os) const85 void SymbolMetadata::dumpToStream(raw_ostream &os) const {
86 os << "meta_$" << getSymbolID() << '{'
87 << getRegion() << ',' << T.getAsString() << '}';
88 }
89
anchor()90 void SymbolData::anchor() {}
91
dumpToStream(raw_ostream & os) const92 void SymbolRegionValue::dumpToStream(raw_ostream &os) const {
93 os << "reg_$" << getSymbolID()
94 << '<' << getType().getAsString() << ' ' << R << '>';
95 }
96
operator ==(const symbol_iterator & X) const97 bool SymExpr::symbol_iterator::operator==(const symbol_iterator &X) const {
98 return itr == X.itr;
99 }
100
operator !=(const symbol_iterator & X) const101 bool SymExpr::symbol_iterator::operator!=(const symbol_iterator &X) const {
102 return itr != X.itr;
103 }
104
symbol_iterator(const SymExpr * SE)105 SymExpr::symbol_iterator::symbol_iterator(const SymExpr *SE) {
106 itr.push_back(SE);
107 }
108
operator ++()109 SymExpr::symbol_iterator &SymExpr::symbol_iterator::operator++() {
110 assert(!itr.empty() && "attempting to iterate on an 'end' iterator");
111 expand();
112 return *this;
113 }
114
operator *()115 SymbolRef SymExpr::symbol_iterator::operator*() {
116 assert(!itr.empty() && "attempting to dereference an 'end' iterator");
117 return itr.back();
118 }
119
expand()120 void 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
149 const SymbolRegionValue*
getRegionValueSymbol(const TypedValueRegion * R)150 SymbolManager::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
conjureSymbol(const Stmt * E,const LocationContext * LCtx,QualType T,unsigned Count,const void * SymbolTag)165 const 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
184 const SymbolDerived*
getDerivedSymbol(SymbolRef parentSymbol,const TypedValueRegion * R)185 SymbolManager::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
201 const SymbolExtent*
getExtentSymbol(const SubRegion * R)202 SymbolManager::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
217 const SymbolMetadata *
getMetadataSymbol(const MemRegion * R,const Stmt * S,QualType T,const LocationContext * LCtx,unsigned Count,const void * SymbolTag)218 SymbolManager::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
235 const SymbolCast*
getCastSymbol(const SymExpr * Op,QualType From,QualType To)236 SymbolManager::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
getSymIntExpr(const SymExpr * lhs,BinaryOperator::Opcode op,const llvm::APSInt & v,QualType t)251 const 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
getIntSymExpr(const llvm::APSInt & lhs,BinaryOperator::Opcode op,const SymExpr * rhs,QualType t)269 const 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
getSymSymExpr(const SymExpr * lhs,BinaryOperator::Opcode op,const SymExpr * rhs,QualType t)287 const 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
getType() const305 QualType SymbolConjured::getType() const {
306 return T;
307 }
308
getType() const309 QualType SymbolDerived::getType() const {
310 return R->getValueType();
311 }
312
getType() const313 QualType SymbolExtent::getType() const {
314 ASTContext &Ctx = R->getMemRegionManager().getContext();
315 return Ctx.getSizeType();
316 }
317
getType() const318 QualType SymbolMetadata::getType() const {
319 return T;
320 }
321
getType() const322 QualType SymbolRegionValue::getType() const {
323 return R->getValueType();
324 }
325
canSymbolicate(QualType T)326 bool 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
addSymbolDependency(const SymbolRef Primary,const SymbolRef Dependent)341 void 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
getDependentSymbols(const SymbolRef Primary)350 const 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
markDependentsLive(SymbolRef sym)358 void 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
markLive(SymbolRef sym)375 void SymbolReaper::markLive(SymbolRef sym) {
376 TheLiving[sym] = NotProcessed;
377 markDependentsLive(sym);
378 }
379
markLive(const MemRegion * region)380 void SymbolReaper::markLive(const MemRegion *region) {
381 RegionRoots.insert(region->getBaseRegion());
382 markElementIndicesLive(region);
383 }
384
markElementIndicesLive(const MemRegion * region)385 void 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
markInUse(SymbolRef sym)396 void SymbolReaper::markInUse(SymbolRef sym) {
397 if (isa<SymbolMetadata>(sym))
398 MetadataInUse.insert(sym);
399 }
400
isLiveRegion(const MemRegion * MR)401 bool 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
isLive(SymbolRef sym)436 bool 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
484 bool
isLive(const Stmt * ExprVal,const LocationContext * ELCtx) const485 SymbolReaper::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
isLive(const VarRegion * VR,bool includeStoreBindings) const504 bool 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