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
anchor()36 void SymExpr::anchor() {}
37
getKindStr() const38 StringRef SymbolConjured::getKindStr() const { return "conj_$"; }
getKindStr() const39 StringRef SymbolDerived::getKindStr() const { return "derived_$"; }
getKindStr() const40 StringRef SymbolExtent::getKindStr() const { return "extent_$"; }
getKindStr() const41 StringRef SymbolMetadata::getKindStr() const { return "meta_$"; }
getKindStr() const42 StringRef SymbolRegionValue::getKindStr() const { return "reg_$"; }
43
dump() const44 LLVM_DUMP_METHOD void SymExpr::dump() const { dumpToStream(llvm::errs()); }
45
dumpToStreamImpl(raw_ostream & OS,const SymExpr * Sym)46 void BinarySymExpr::dumpToStreamImpl(raw_ostream &OS, const SymExpr *Sym) {
47 OS << '(';
48 Sym->dumpToStream(OS);
49 OS << ')';
50 }
51
dumpToStreamImpl(raw_ostream & OS,const llvm::APSInt & Value)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
dumpToStreamImpl(raw_ostream & OS,BinaryOperator::Opcode Op)62 void BinarySymExpr::dumpToStreamImpl(raw_ostream &OS,
63 BinaryOperator::Opcode Op) {
64 OS << ' ' << BinaryOperator::getOpcodeStr(Op) << ' ';
65 }
66
dumpToStream(raw_ostream & os) const67 void SymbolCast::dumpToStream(raw_ostream &os) const {
68 os << '(' << ToTy.getAsString() << ") (";
69 Operand->dumpToStream(os);
70 os << ')';
71 }
72
dumpToStream(raw_ostream & os) const73 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
dumpToStream(raw_ostream & os) const83 void SymbolDerived::dumpToStream(raw_ostream &os) const {
84 os << getKindStr() << getSymbolID() << '{' << getParentSymbol() << ','
85 << getRegion() << '}';
86 }
87
dumpToStream(raw_ostream & os) const88 void SymbolExtent::dumpToStream(raw_ostream &os) const {
89 os << getKindStr() << getSymbolID() << '{' << getRegion() << '}';
90 }
91
dumpToStream(raw_ostream & os) const92 void SymbolMetadata::dumpToStream(raw_ostream &os) const {
93 os << getKindStr() << getSymbolID() << '{' << getRegion() << ','
94 << T.getAsString() << '}';
95 }
96
anchor()97 void SymbolData::anchor() {}
98
dumpToStream(raw_ostream & os) const99 void SymbolRegionValue::dumpToStream(raw_ostream &os) const {
100 os << getKindStr() << getSymbolID() << '<' << getType().getAsString() << ' '
101 << R << '>';
102 }
103
operator ==(const symbol_iterator & X) const104 bool SymExpr::symbol_iterator::operator==(const symbol_iterator &X) const {
105 return itr == X.itr;
106 }
107
operator !=(const symbol_iterator & X) const108 bool SymExpr::symbol_iterator::operator!=(const symbol_iterator &X) const {
109 return itr != X.itr;
110 }
111
symbol_iterator(const SymExpr * SE)112 SymExpr::symbol_iterator::symbol_iterator(const SymExpr *SE) {
113 itr.push_back(SE);
114 }
115
operator ++()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
operator *()122 SymbolRef SymExpr::symbol_iterator::operator*() {
123 assert(!itr.empty() && "attempting to dereference an 'end' iterator");
124 return itr.back();
125 }
126
expand()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*
getRegionValueSymbol(const TypedValueRegion * R)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
conjureSymbol(const Stmt * E,const LocationContext * LCtx,QualType T,unsigned Count,const void * SymbolTag)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*
getDerivedSymbol(SymbolRef parentSymbol,const TypedValueRegion * R)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*
getExtentSymbol(const SubRegion * R)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 *
getMetadataSymbol(const MemRegion * R,const Stmt * S,QualType T,const LocationContext * LCtx,unsigned Count,const void * SymbolTag)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*
getCastSymbol(const SymExpr * Op,QualType From,QualType To)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
getSymIntExpr(const SymExpr * lhs,BinaryOperator::Opcode op,const llvm::APSInt & v,QualType t)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
getIntSymExpr(const llvm::APSInt & lhs,BinaryOperator::Opcode op,const SymExpr * rhs,QualType t)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
getSymSymExpr(const SymExpr * lhs,BinaryOperator::Opcode op,const SymExpr * rhs,QualType t)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
getType() const312 QualType SymbolConjured::getType() const {
313 return T;
314 }
315
getType() const316 QualType SymbolDerived::getType() const {
317 return R->getValueType();
318 }
319
getType() const320 QualType SymbolExtent::getType() const {
321 ASTContext &Ctx = R->getMemRegionManager().getContext();
322 return Ctx.getSizeType();
323 }
324
getType() const325 QualType SymbolMetadata::getType() const {
326 return T;
327 }
328
getType() const329 QualType SymbolRegionValue::getType() const {
330 return R->getValueType();
331 }
332
canSymbolicate(QualType T)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
addSymbolDependency(const SymbolRef Primary,const SymbolRef Dependent)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
getDependentSymbols(const SymbolRef Primary)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
markDependentsLive(SymbolRef sym)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
markLive(SymbolRef sym)382 void SymbolReaper::markLive(SymbolRef sym) {
383 TheLiving[sym] = NotProcessed;
384 markDependentsLive(sym);
385 }
386
markLive(const MemRegion * region)387 void SymbolReaper::markLive(const MemRegion *region) {
388 RegionRoots.insert(region->getBaseRegion());
389 markElementIndicesLive(region);
390 }
391
markElementIndicesLive(const MemRegion * region)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
markInUse(SymbolRef sym)403 void SymbolReaper::markInUse(SymbolRef sym) {
404 if (isa<SymbolMetadata>(sym))
405 MetadataInUse.insert(sym);
406 }
407
isLiveRegion(const MemRegion * MR)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 if (isa<AllocaRegion>(MR))
429 return true;
430
431 if (isa<CXXThisRegion>(MR))
432 return true;
433
434 if (isa<MemSpaceRegion>(MR))
435 return true;
436
437 if (isa<CodeTextRegion>(MR))
438 return true;
439
440 return false;
441 }
442
isLive(SymbolRef sym)443 bool SymbolReaper::isLive(SymbolRef sym) {
444 if (TheLiving.count(sym)) {
445 markDependentsLive(sym);
446 return true;
447 }
448
449 bool KnownLive;
450
451 switch (sym->getKind()) {
452 case SymExpr::SymbolRegionValueKind:
453 KnownLive = isLiveRegion(cast<SymbolRegionValue>(sym)->getRegion());
454 break;
455 case SymExpr::SymbolConjuredKind:
456 KnownLive = false;
457 break;
458 case SymExpr::SymbolDerivedKind:
459 KnownLive = isLive(cast<SymbolDerived>(sym)->getParentSymbol());
460 break;
461 case SymExpr::SymbolExtentKind:
462 KnownLive = isLiveRegion(cast<SymbolExtent>(sym)->getRegion());
463 break;
464 case SymExpr::SymbolMetadataKind:
465 KnownLive = MetadataInUse.count(sym) &&
466 isLiveRegion(cast<SymbolMetadata>(sym)->getRegion());
467 if (KnownLive)
468 MetadataInUse.erase(sym);
469 break;
470 case SymExpr::SymIntExprKind:
471 KnownLive = isLive(cast<SymIntExpr>(sym)->getLHS());
472 break;
473 case SymExpr::IntSymExprKind:
474 KnownLive = isLive(cast<IntSymExpr>(sym)->getRHS());
475 break;
476 case SymExpr::SymSymExprKind:
477 KnownLive = isLive(cast<SymSymExpr>(sym)->getLHS()) &&
478 isLive(cast<SymSymExpr>(sym)->getRHS());
479 break;
480 case SymExpr::SymbolCastKind:
481 KnownLive = isLive(cast<SymbolCast>(sym)->getOperand());
482 break;
483 }
484
485 if (KnownLive)
486 markLive(sym);
487
488 return KnownLive;
489 }
490
491 bool
isLive(const Expr * ExprVal,const LocationContext * ELCtx) const492 SymbolReaper::isLive(const Expr *ExprVal, const LocationContext *ELCtx) const {
493 if (LCtx == nullptr)
494 return false;
495
496 if (LCtx != ELCtx) {
497 // If the reaper's location context is a parent of the expression's
498 // location context, then the expression value is now "out of scope".
499 if (LCtx->isParentOf(ELCtx))
500 return false;
501 return true;
502 }
503
504 // If no statement is provided, everything in this and parent contexts is
505 // live.
506 if (!Loc)
507 return true;
508
509 return LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, ExprVal);
510 }
511
isLive(const VarRegion * VR,bool includeStoreBindings) const512 bool SymbolReaper::isLive(const VarRegion *VR, bool includeStoreBindings) const{
513 const StackFrameContext *VarContext = VR->getStackFrame();
514
515 if (!VarContext)
516 return true;
517
518 if (!LCtx)
519 return false;
520 const StackFrameContext *CurrentContext = LCtx->getStackFrame();
521
522 if (VarContext == CurrentContext) {
523 // If no statement is provided, everything is live.
524 if (!Loc)
525 return true;
526
527 // Anonymous parameters of an inheriting constructor are live for the entire
528 // duration of the constructor.
529 if (isa<CXXInheritedCtorInitExpr>(Loc))
530 return true;
531
532 if (LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, VR->getDecl()))
533 return true;
534
535 if (!includeStoreBindings)
536 return false;
537
538 unsigned &cachedQuery =
539 const_cast<SymbolReaper *>(this)->includedRegionCache[VR];
540
541 if (cachedQuery) {
542 return cachedQuery == 1;
543 }
544
545 // Query the store to see if the region occurs in any live bindings.
546 if (Store store = reapedStore.getStore()) {
547 bool hasRegion =
548 reapedStore.getStoreManager().includedInBindings(store, VR);
549 cachedQuery = hasRegion ? 1 : 2;
550 return hasRegion;
551 }
552
553 return false;
554 }
555
556 return VarContext->isParentOf(CurrentContext);
557 }
558