1 //== RegionStore.cpp - Field-sensitive store model --------------*- C++ -*--==// 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 a basic region store model. In this model, we do have field 10 // sensitivity. But we assume nothing about the heap shape. So recursive data 11 // structures are largely ignored. Basically we do 1-limiting analysis. 12 // Parameter pointers are assumed with no aliasing. Pointee objects of 13 // parameters are created lazily. 14 // 15 //===----------------------------------------------------------------------===// 16 17 #include "clang/AST/Attr.h" 18 #include "clang/AST/CharUnits.h" 19 #include "clang/ASTMatchers/ASTMatchFinder.h" 20 #include "clang/Analysis/Analyses/LiveVariables.h" 21 #include "clang/Analysis/AnalysisDeclContext.h" 22 #include "clang/Basic/JsonSupport.h" 23 #include "clang/Basic/TargetInfo.h" 24 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" 25 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" 26 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 27 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" 28 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 29 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 30 #include "llvm/ADT/ImmutableMap.h" 31 #include "llvm/ADT/Optional.h" 32 #include "llvm/Support/raw_ostream.h" 33 #include <utility> 34 35 using namespace clang; 36 using namespace ento; 37 38 //===----------------------------------------------------------------------===// 39 // Representation of binding keys. 40 //===----------------------------------------------------------------------===// 41 42 namespace { 43 class BindingKey { 44 public: 45 enum Kind { Default = 0x0, Direct = 0x1 }; 46 private: 47 enum { Symbolic = 0x2 }; 48 49 llvm::PointerIntPair<const MemRegion *, 2> P; 50 uint64_t Data; 51 52 /// Create a key for a binding to region \p r, which has a symbolic offset 53 /// from region \p Base. 54 explicit BindingKey(const SubRegion *r, const SubRegion *Base, Kind k) 55 : P(r, k | Symbolic), Data(reinterpret_cast<uintptr_t>(Base)) { 56 assert(r && Base && "Must have known regions."); 57 assert(getConcreteOffsetRegion() == Base && "Failed to store base region"); 58 } 59 60 /// Create a key for a binding at \p offset from base region \p r. 61 explicit BindingKey(const MemRegion *r, uint64_t offset, Kind k) 62 : P(r, k), Data(offset) { 63 assert(r && "Must have known regions."); 64 assert(getOffset() == offset && "Failed to store offset"); 65 assert((r == r->getBaseRegion() || 66 isa<ObjCIvarRegion, CXXDerivedObjectRegion>(r)) && 67 "Not a base"); 68 } 69 public: 70 71 bool isDirect() const { return P.getInt() & Direct; } 72 bool hasSymbolicOffset() const { return P.getInt() & Symbolic; } 73 74 const MemRegion *getRegion() const { return P.getPointer(); } 75 uint64_t getOffset() const { 76 assert(!hasSymbolicOffset()); 77 return Data; 78 } 79 80 const SubRegion *getConcreteOffsetRegion() const { 81 assert(hasSymbolicOffset()); 82 return reinterpret_cast<const SubRegion *>(static_cast<uintptr_t>(Data)); 83 } 84 85 const MemRegion *getBaseRegion() const { 86 if (hasSymbolicOffset()) 87 return getConcreteOffsetRegion()->getBaseRegion(); 88 return getRegion()->getBaseRegion(); 89 } 90 91 void Profile(llvm::FoldingSetNodeID& ID) const { 92 ID.AddPointer(P.getOpaqueValue()); 93 ID.AddInteger(Data); 94 } 95 96 static BindingKey Make(const MemRegion *R, Kind k); 97 98 bool operator<(const BindingKey &X) const { 99 if (P.getOpaqueValue() < X.P.getOpaqueValue()) 100 return true; 101 if (P.getOpaqueValue() > X.P.getOpaqueValue()) 102 return false; 103 return Data < X.Data; 104 } 105 106 bool operator==(const BindingKey &X) const { 107 return P.getOpaqueValue() == X.P.getOpaqueValue() && 108 Data == X.Data; 109 } 110 111 LLVM_DUMP_METHOD void dump() const; 112 }; 113 } // end anonymous namespace 114 115 BindingKey BindingKey::Make(const MemRegion *R, Kind k) { 116 const RegionOffset &RO = R->getAsOffset(); 117 if (RO.hasSymbolicOffset()) 118 return BindingKey(cast<SubRegion>(R), cast<SubRegion>(RO.getRegion()), k); 119 120 return BindingKey(RO.getRegion(), RO.getOffset(), k); 121 } 122 123 namespace llvm { 124 static inline raw_ostream &operator<<(raw_ostream &Out, BindingKey K) { 125 Out << "\"kind\": \"" << (K.isDirect() ? "Direct" : "Default") 126 << "\", \"offset\": "; 127 128 if (!K.hasSymbolicOffset()) 129 Out << K.getOffset(); 130 else 131 Out << "null"; 132 133 return Out; 134 } 135 136 } // namespace llvm 137 138 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 139 void BindingKey::dump() const { llvm::errs() << *this; } 140 #endif 141 142 //===----------------------------------------------------------------------===// 143 // Actual Store type. 144 //===----------------------------------------------------------------------===// 145 146 typedef llvm::ImmutableMap<BindingKey, SVal> ClusterBindings; 147 typedef llvm::ImmutableMapRef<BindingKey, SVal> ClusterBindingsRef; 148 typedef std::pair<BindingKey, SVal> BindingPair; 149 150 typedef llvm::ImmutableMap<const MemRegion *, ClusterBindings> 151 RegionBindings; 152 153 namespace { 154 class RegionBindingsRef : public llvm::ImmutableMapRef<const MemRegion *, 155 ClusterBindings> { 156 ClusterBindings::Factory *CBFactory; 157 158 // This flag indicates whether the current bindings are within the analysis 159 // that has started from main(). It affects how we perform loads from 160 // global variables that have initializers: if we have observed the 161 // program execution from the start and we know that these variables 162 // have not been overwritten yet, we can be sure that their initializers 163 // are still relevant. This flag never gets changed when the bindings are 164 // updated, so it could potentially be moved into RegionStoreManager 165 // (as if it's the same bindings but a different loading procedure) 166 // however that would have made the manager needlessly stateful. 167 bool IsMainAnalysis; 168 169 public: 170 typedef llvm::ImmutableMapRef<const MemRegion *, ClusterBindings> 171 ParentTy; 172 173 RegionBindingsRef(ClusterBindings::Factory &CBFactory, 174 const RegionBindings::TreeTy *T, 175 RegionBindings::TreeTy::Factory *F, 176 bool IsMainAnalysis) 177 : llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>(T, F), 178 CBFactory(&CBFactory), IsMainAnalysis(IsMainAnalysis) {} 179 180 RegionBindingsRef(const ParentTy &P, 181 ClusterBindings::Factory &CBFactory, 182 bool IsMainAnalysis) 183 : llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>(P), 184 CBFactory(&CBFactory), IsMainAnalysis(IsMainAnalysis) {} 185 186 RegionBindingsRef add(key_type_ref K, data_type_ref D) const { 187 return RegionBindingsRef(static_cast<const ParentTy *>(this)->add(K, D), 188 *CBFactory, IsMainAnalysis); 189 } 190 191 RegionBindingsRef remove(key_type_ref K) const { 192 return RegionBindingsRef(static_cast<const ParentTy *>(this)->remove(K), 193 *CBFactory, IsMainAnalysis); 194 } 195 196 RegionBindingsRef addBinding(BindingKey K, SVal V) const; 197 198 RegionBindingsRef addBinding(const MemRegion *R, 199 BindingKey::Kind k, SVal V) const; 200 201 const SVal *lookup(BindingKey K) const; 202 const SVal *lookup(const MemRegion *R, BindingKey::Kind k) const; 203 using llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>::lookup; 204 205 RegionBindingsRef removeBinding(BindingKey K); 206 207 RegionBindingsRef removeBinding(const MemRegion *R, 208 BindingKey::Kind k); 209 210 RegionBindingsRef removeBinding(const MemRegion *R) { 211 return removeBinding(R, BindingKey::Direct). 212 removeBinding(R, BindingKey::Default); 213 } 214 215 Optional<SVal> getDirectBinding(const MemRegion *R) const; 216 217 /// getDefaultBinding - Returns an SVal* representing an optional default 218 /// binding associated with a region and its subregions. 219 Optional<SVal> getDefaultBinding(const MemRegion *R) const; 220 221 /// Return the internal tree as a Store. 222 Store asStore() const { 223 llvm::PointerIntPair<Store, 1, bool> Ptr = { 224 asImmutableMap().getRootWithoutRetain(), IsMainAnalysis}; 225 return reinterpret_cast<Store>(Ptr.getOpaqueValue()); 226 } 227 228 bool isMainAnalysis() const { 229 return IsMainAnalysis; 230 } 231 232 void printJson(raw_ostream &Out, const char *NL = "\n", 233 unsigned int Space = 0, bool IsDot = false) const { 234 for (iterator I = begin(); I != end(); ++I) { 235 // TODO: We might need a .printJson for I.getKey() as well. 236 Indent(Out, Space, IsDot) 237 << "{ \"cluster\": \"" << I.getKey() << "\", \"pointer\": \"" 238 << (const void *)I.getKey() << "\", \"items\": [" << NL; 239 240 ++Space; 241 const ClusterBindings &CB = I.getData(); 242 for (ClusterBindings::iterator CI = CB.begin(); CI != CB.end(); ++CI) { 243 Indent(Out, Space, IsDot) << "{ " << CI.getKey() << ", \"value\": "; 244 CI.getData().printJson(Out, /*AddQuotes=*/true); 245 Out << " }"; 246 if (std::next(CI) != CB.end()) 247 Out << ','; 248 Out << NL; 249 } 250 251 --Space; 252 Indent(Out, Space, IsDot) << "]}"; 253 if (std::next(I) != end()) 254 Out << ','; 255 Out << NL; 256 } 257 } 258 259 LLVM_DUMP_METHOD void dump() const { printJson(llvm::errs()); } 260 }; 261 } // end anonymous namespace 262 263 typedef const RegionBindingsRef& RegionBindingsConstRef; 264 265 Optional<SVal> RegionBindingsRef::getDirectBinding(const MemRegion *R) const { 266 return Optional<SVal>::create(lookup(R, BindingKey::Direct)); 267 } 268 269 Optional<SVal> RegionBindingsRef::getDefaultBinding(const MemRegion *R) const { 270 return Optional<SVal>::create(lookup(R, BindingKey::Default)); 271 } 272 273 RegionBindingsRef RegionBindingsRef::addBinding(BindingKey K, SVal V) const { 274 const MemRegion *Base = K.getBaseRegion(); 275 276 const ClusterBindings *ExistingCluster = lookup(Base); 277 ClusterBindings Cluster = 278 (ExistingCluster ? *ExistingCluster : CBFactory->getEmptyMap()); 279 280 ClusterBindings NewCluster = CBFactory->add(Cluster, K, V); 281 return add(Base, NewCluster); 282 } 283 284 285 RegionBindingsRef RegionBindingsRef::addBinding(const MemRegion *R, 286 BindingKey::Kind k, 287 SVal V) const { 288 return addBinding(BindingKey::Make(R, k), V); 289 } 290 291 const SVal *RegionBindingsRef::lookup(BindingKey K) const { 292 const ClusterBindings *Cluster = lookup(K.getBaseRegion()); 293 if (!Cluster) 294 return nullptr; 295 return Cluster->lookup(K); 296 } 297 298 const SVal *RegionBindingsRef::lookup(const MemRegion *R, 299 BindingKey::Kind k) const { 300 return lookup(BindingKey::Make(R, k)); 301 } 302 303 RegionBindingsRef RegionBindingsRef::removeBinding(BindingKey K) { 304 const MemRegion *Base = K.getBaseRegion(); 305 const ClusterBindings *Cluster = lookup(Base); 306 if (!Cluster) 307 return *this; 308 309 ClusterBindings NewCluster = CBFactory->remove(*Cluster, K); 310 if (NewCluster.isEmpty()) 311 return remove(Base); 312 return add(Base, NewCluster); 313 } 314 315 RegionBindingsRef RegionBindingsRef::removeBinding(const MemRegion *R, 316 BindingKey::Kind k){ 317 return removeBinding(BindingKey::Make(R, k)); 318 } 319 320 //===----------------------------------------------------------------------===// 321 // Fine-grained control of RegionStoreManager. 322 //===----------------------------------------------------------------------===// 323 324 namespace { 325 struct minimal_features_tag {}; 326 struct maximal_features_tag {}; 327 328 class RegionStoreFeatures { 329 bool SupportsFields; 330 public: 331 RegionStoreFeatures(minimal_features_tag) : 332 SupportsFields(false) {} 333 334 RegionStoreFeatures(maximal_features_tag) : 335 SupportsFields(true) {} 336 337 void enableFields(bool t) { SupportsFields = t; } 338 339 bool supportsFields() const { return SupportsFields; } 340 }; 341 } 342 343 //===----------------------------------------------------------------------===// 344 // Main RegionStore logic. 345 //===----------------------------------------------------------------------===// 346 347 namespace { 348 class InvalidateRegionsWorker; 349 350 class RegionStoreManager : public StoreManager { 351 public: 352 const RegionStoreFeatures Features; 353 354 RegionBindings::Factory RBFactory; 355 mutable ClusterBindings::Factory CBFactory; 356 357 typedef std::vector<SVal> SValListTy; 358 private: 359 typedef llvm::DenseMap<const LazyCompoundValData *, 360 SValListTy> LazyBindingsMapTy; 361 LazyBindingsMapTy LazyBindingsMap; 362 363 /// The largest number of fields a struct can have and still be 364 /// considered "small". 365 /// 366 /// This is currently used to decide whether or not it is worth "forcing" a 367 /// LazyCompoundVal on bind. 368 /// 369 /// This is controlled by 'region-store-small-struct-limit' option. 370 /// To disable all small-struct-dependent behavior, set the option to "0". 371 unsigned SmallStructLimit; 372 373 /// A helper used to populate the work list with the given set of 374 /// regions. 375 void populateWorkList(InvalidateRegionsWorker &W, 376 ArrayRef<SVal> Values, 377 InvalidatedRegions *TopLevelRegions); 378 379 public: 380 RegionStoreManager(ProgramStateManager& mgr, const RegionStoreFeatures &f) 381 : StoreManager(mgr), Features(f), 382 RBFactory(mgr.getAllocator()), CBFactory(mgr.getAllocator()), 383 SmallStructLimit(0) { 384 ExprEngine &Eng = StateMgr.getOwningEngine(); 385 AnalyzerOptions &Options = Eng.getAnalysisManager().options; 386 SmallStructLimit = Options.RegionStoreSmallStructLimit; 387 } 388 389 390 /// setImplicitDefaultValue - Set the default binding for the provided 391 /// MemRegion to the value implicitly defined for compound literals when 392 /// the value is not specified. 393 RegionBindingsRef setImplicitDefaultValue(RegionBindingsConstRef B, 394 const MemRegion *R, QualType T); 395 396 /// ArrayToPointer - Emulates the "decay" of an array to a pointer 397 /// type. 'Array' represents the lvalue of the array being decayed 398 /// to a pointer, and the returned SVal represents the decayed 399 /// version of that lvalue (i.e., a pointer to the first element of 400 /// the array). This is called by ExprEngine when evaluating 401 /// casts from arrays to pointers. 402 SVal ArrayToPointer(Loc Array, QualType ElementTy) override; 403 404 /// Creates the Store that correctly represents memory contents before 405 /// the beginning of the analysis of the given top-level stack frame. 406 StoreRef getInitialStore(const LocationContext *InitLoc) override { 407 bool IsMainAnalysis = false; 408 if (const auto *FD = dyn_cast<FunctionDecl>(InitLoc->getDecl())) 409 IsMainAnalysis = FD->isMain() && !Ctx.getLangOpts().CPlusPlus; 410 return StoreRef(RegionBindingsRef( 411 RegionBindingsRef::ParentTy(RBFactory.getEmptyMap(), RBFactory), 412 CBFactory, IsMainAnalysis).asStore(), *this); 413 } 414 415 //===-------------------------------------------------------------------===// 416 // Binding values to regions. 417 //===-------------------------------------------------------------------===// 418 RegionBindingsRef invalidateGlobalRegion(MemRegion::Kind K, 419 const Expr *Ex, 420 unsigned Count, 421 const LocationContext *LCtx, 422 RegionBindingsRef B, 423 InvalidatedRegions *Invalidated); 424 425 StoreRef invalidateRegions(Store store, 426 ArrayRef<SVal> Values, 427 const Expr *E, unsigned Count, 428 const LocationContext *LCtx, 429 const CallEvent *Call, 430 InvalidatedSymbols &IS, 431 RegionAndSymbolInvalidationTraits &ITraits, 432 InvalidatedRegions *Invalidated, 433 InvalidatedRegions *InvalidatedTopLevel) override; 434 435 bool scanReachableSymbols(Store S, const MemRegion *R, 436 ScanReachableSymbols &Callbacks) override; 437 438 RegionBindingsRef removeSubRegionBindings(RegionBindingsConstRef B, 439 const SubRegion *R); 440 Optional<SVal> getConstantValFromConstArrayInitializer( 441 RegionBindingsConstRef B, const VarRegion *VR, const ElementRegion *R); 442 Optional<SVal> getSValFromInitListExpr(const InitListExpr *ILE, 443 uint64_t Offset, QualType ElemT); 444 445 public: // Part of public interface to class. 446 447 StoreRef Bind(Store store, Loc LV, SVal V) override { 448 return StoreRef(bind(getRegionBindings(store), LV, V).asStore(), *this); 449 } 450 451 RegionBindingsRef bind(RegionBindingsConstRef B, Loc LV, SVal V); 452 453 // BindDefaultInitial is only used to initialize a region with 454 // a default value. 455 StoreRef BindDefaultInitial(Store store, const MemRegion *R, 456 SVal V) override { 457 RegionBindingsRef B = getRegionBindings(store); 458 // Use other APIs when you have to wipe the region that was initialized 459 // earlier. 460 assert(!(B.getDefaultBinding(R) || B.getDirectBinding(R)) && 461 "Double initialization!"); 462 B = B.addBinding(BindingKey::Make(R, BindingKey::Default), V); 463 return StoreRef(B.asImmutableMap().getRootWithoutRetain(), *this); 464 } 465 466 // BindDefaultZero is used for zeroing constructors that may accidentally 467 // overwrite existing bindings. 468 StoreRef BindDefaultZero(Store store, const MemRegion *R) override { 469 // FIXME: The offsets of empty bases can be tricky because of 470 // of the so called "empty base class optimization". 471 // If a base class has been optimized out 472 // we should not try to create a binding, otherwise we should. 473 // Unfortunately, at the moment ASTRecordLayout doesn't expose 474 // the actual sizes of the empty bases 475 // and trying to infer them from offsets/alignments 476 // seems to be error-prone and non-trivial because of the trailing padding. 477 // As a temporary mitigation we don't create bindings for empty bases. 478 if (const auto *BR = dyn_cast<CXXBaseObjectRegion>(R)) 479 if (BR->getDecl()->isEmpty()) 480 return StoreRef(store, *this); 481 482 RegionBindingsRef B = getRegionBindings(store); 483 SVal V = svalBuilder.makeZeroVal(Ctx.CharTy); 484 B = removeSubRegionBindings(B, cast<SubRegion>(R)); 485 B = B.addBinding(BindingKey::Make(R, BindingKey::Default), V); 486 return StoreRef(B.asImmutableMap().getRootWithoutRetain(), *this); 487 } 488 489 /// Attempt to extract the fields of \p LCV and bind them to the struct region 490 /// \p R. 491 /// 492 /// This path is used when it seems advantageous to "force" loading the values 493 /// within a LazyCompoundVal to bind memberwise to the struct region, rather 494 /// than using a Default binding at the base of the entire region. This is a 495 /// heuristic attempting to avoid building long chains of LazyCompoundVals. 496 /// 497 /// \returns The updated store bindings, or \c None if binding non-lazily 498 /// would be too expensive. 499 Optional<RegionBindingsRef> tryBindSmallStruct(RegionBindingsConstRef B, 500 const TypedValueRegion *R, 501 const RecordDecl *RD, 502 nonloc::LazyCompoundVal LCV); 503 504 /// BindStruct - Bind a compound value to a structure. 505 RegionBindingsRef bindStruct(RegionBindingsConstRef B, 506 const TypedValueRegion* R, SVal V); 507 508 /// BindVector - Bind a compound value to a vector. 509 RegionBindingsRef bindVector(RegionBindingsConstRef B, 510 const TypedValueRegion* R, SVal V); 511 512 RegionBindingsRef bindArray(RegionBindingsConstRef B, 513 const TypedValueRegion* R, 514 SVal V); 515 516 /// Clears out all bindings in the given region and assigns a new value 517 /// as a Default binding. 518 RegionBindingsRef bindAggregate(RegionBindingsConstRef B, 519 const TypedRegion *R, 520 SVal DefaultVal); 521 522 /// Create a new store with the specified binding removed. 523 /// \param ST the original store, that is the basis for the new store. 524 /// \param L the location whose binding should be removed. 525 StoreRef killBinding(Store ST, Loc L) override; 526 527 void incrementReferenceCount(Store store) override { 528 getRegionBindings(store).manualRetain(); 529 } 530 531 /// If the StoreManager supports it, decrement the reference count of 532 /// the specified Store object. If the reference count hits 0, the memory 533 /// associated with the object is recycled. 534 void decrementReferenceCount(Store store) override { 535 getRegionBindings(store).manualRelease(); 536 } 537 538 bool includedInBindings(Store store, const MemRegion *region) const override; 539 540 /// Return the value bound to specified location in a given state. 541 /// 542 /// The high level logic for this method is this: 543 /// getBinding (L) 544 /// if L has binding 545 /// return L's binding 546 /// else if L is in killset 547 /// return unknown 548 /// else 549 /// if L is on stack or heap 550 /// return undefined 551 /// else 552 /// return symbolic 553 SVal getBinding(Store S, Loc L, QualType T) override { 554 return getBinding(getRegionBindings(S), L, T); 555 } 556 557 Optional<SVal> getDefaultBinding(Store S, const MemRegion *R) override { 558 RegionBindingsRef B = getRegionBindings(S); 559 // Default bindings are always applied over a base region so look up the 560 // base region's default binding, otherwise the lookup will fail when R 561 // is at an offset from R->getBaseRegion(). 562 return B.getDefaultBinding(R->getBaseRegion()); 563 } 564 565 SVal getBinding(RegionBindingsConstRef B, Loc L, QualType T = QualType()); 566 567 SVal getBindingForElement(RegionBindingsConstRef B, const ElementRegion *R); 568 569 SVal getBindingForField(RegionBindingsConstRef B, const FieldRegion *R); 570 571 SVal getBindingForObjCIvar(RegionBindingsConstRef B, const ObjCIvarRegion *R); 572 573 SVal getBindingForVar(RegionBindingsConstRef B, const VarRegion *R); 574 575 SVal getBindingForLazySymbol(const TypedValueRegion *R); 576 577 SVal getBindingForFieldOrElementCommon(RegionBindingsConstRef B, 578 const TypedValueRegion *R, 579 QualType Ty); 580 581 SVal getLazyBinding(const SubRegion *LazyBindingRegion, 582 RegionBindingsRef LazyBinding); 583 584 /// Get bindings for the values in a struct and return a CompoundVal, used 585 /// when doing struct copy: 586 /// struct s x, y; 587 /// x = y; 588 /// y's value is retrieved by this method. 589 SVal getBindingForStruct(RegionBindingsConstRef B, const TypedValueRegion *R); 590 SVal getBindingForArray(RegionBindingsConstRef B, const TypedValueRegion *R); 591 NonLoc createLazyBinding(RegionBindingsConstRef B, const TypedValueRegion *R); 592 593 /// Used to lazily generate derived symbols for bindings that are defined 594 /// implicitly by default bindings in a super region. 595 /// 596 /// Note that callers may need to specially handle LazyCompoundVals, which 597 /// are returned as is in case the caller needs to treat them differently. 598 Optional<SVal> getBindingForDerivedDefaultValue(RegionBindingsConstRef B, 599 const MemRegion *superR, 600 const TypedValueRegion *R, 601 QualType Ty); 602 603 /// Get the state and region whose binding this region \p R corresponds to. 604 /// 605 /// If there is no lazy binding for \p R, the returned value will have a null 606 /// \c second. Note that a null pointer can represents a valid Store. 607 std::pair<Store, const SubRegion *> 608 findLazyBinding(RegionBindingsConstRef B, const SubRegion *R, 609 const SubRegion *originalRegion); 610 611 /// Returns the cached set of interesting SVals contained within a lazy 612 /// binding. 613 /// 614 /// The precise value of "interesting" is determined for the purposes of 615 /// RegionStore's internal analysis. It must always contain all regions and 616 /// symbols, but may omit constants and other kinds of SVal. 617 const SValListTy &getInterestingValues(nonloc::LazyCompoundVal LCV); 618 619 //===------------------------------------------------------------------===// 620 // State pruning. 621 //===------------------------------------------------------------------===// 622 623 /// removeDeadBindings - Scans the RegionStore of 'state' for dead values. 624 /// It returns a new Store with these values removed. 625 StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx, 626 SymbolReaper& SymReaper) override; 627 628 //===------------------------------------------------------------------===// 629 // Utility methods. 630 //===------------------------------------------------------------------===// 631 632 RegionBindingsRef getRegionBindings(Store store) const { 633 llvm::PointerIntPair<Store, 1, bool> Ptr; 634 Ptr.setFromOpaqueValue(const_cast<void *>(store)); 635 return RegionBindingsRef( 636 CBFactory, 637 static_cast<const RegionBindings::TreeTy *>(Ptr.getPointer()), 638 RBFactory.getTreeFactory(), 639 Ptr.getInt()); 640 } 641 642 void printJson(raw_ostream &Out, Store S, const char *NL = "\n", 643 unsigned int Space = 0, bool IsDot = false) const override; 644 645 void iterBindings(Store store, BindingsHandler& f) override { 646 RegionBindingsRef B = getRegionBindings(store); 647 for (RegionBindingsRef::iterator I = B.begin(), E = B.end(); I != E; ++I) { 648 const ClusterBindings &Cluster = I.getData(); 649 for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); 650 CI != CE; ++CI) { 651 const BindingKey &K = CI.getKey(); 652 if (!K.isDirect()) 653 continue; 654 if (const SubRegion *R = dyn_cast<SubRegion>(K.getRegion())) { 655 // FIXME: Possibly incorporate the offset? 656 if (!f.HandleBinding(*this, store, R, CI.getData())) 657 return; 658 } 659 } 660 } 661 } 662 }; 663 664 } // end anonymous namespace 665 666 //===----------------------------------------------------------------------===// 667 // RegionStore creation. 668 //===----------------------------------------------------------------------===// 669 670 std::unique_ptr<StoreManager> 671 ento::CreateRegionStoreManager(ProgramStateManager &StMgr) { 672 RegionStoreFeatures F = maximal_features_tag(); 673 return std::make_unique<RegionStoreManager>(StMgr, F); 674 } 675 676 std::unique_ptr<StoreManager> 677 ento::CreateFieldsOnlyRegionStoreManager(ProgramStateManager &StMgr) { 678 RegionStoreFeatures F = minimal_features_tag(); 679 F.enableFields(true); 680 return std::make_unique<RegionStoreManager>(StMgr, F); 681 } 682 683 684 //===----------------------------------------------------------------------===// 685 // Region Cluster analysis. 686 //===----------------------------------------------------------------------===// 687 688 namespace { 689 /// Used to determine which global regions are automatically included in the 690 /// initial worklist of a ClusterAnalysis. 691 enum GlobalsFilterKind { 692 /// Don't include any global regions. 693 GFK_None, 694 /// Only include system globals. 695 GFK_SystemOnly, 696 /// Include all global regions. 697 GFK_All 698 }; 699 700 template <typename DERIVED> 701 class ClusterAnalysis { 702 protected: 703 typedef llvm::DenseMap<const MemRegion *, const ClusterBindings *> ClusterMap; 704 typedef const MemRegion * WorkListElement; 705 typedef SmallVector<WorkListElement, 10> WorkList; 706 707 llvm::SmallPtrSet<const ClusterBindings *, 16> Visited; 708 709 WorkList WL; 710 711 RegionStoreManager &RM; 712 ASTContext &Ctx; 713 SValBuilder &svalBuilder; 714 715 RegionBindingsRef B; 716 717 718 protected: 719 const ClusterBindings *getCluster(const MemRegion *R) { 720 return B.lookup(R); 721 } 722 723 /// Returns true if all clusters in the given memspace should be initially 724 /// included in the cluster analysis. Subclasses may provide their 725 /// own implementation. 726 bool includeEntireMemorySpace(const MemRegion *Base) { 727 return false; 728 } 729 730 public: 731 ClusterAnalysis(RegionStoreManager &rm, ProgramStateManager &StateMgr, 732 RegionBindingsRef b) 733 : RM(rm), Ctx(StateMgr.getContext()), 734 svalBuilder(StateMgr.getSValBuilder()), B(std::move(b)) {} 735 736 RegionBindingsRef getRegionBindings() const { return B; } 737 738 bool isVisited(const MemRegion *R) { 739 return Visited.count(getCluster(R)); 740 } 741 742 void GenerateClusters() { 743 // Scan the entire set of bindings and record the region clusters. 744 for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end(); 745 RI != RE; ++RI){ 746 const MemRegion *Base = RI.getKey(); 747 748 const ClusterBindings &Cluster = RI.getData(); 749 assert(!Cluster.isEmpty() && "Empty clusters should be removed"); 750 static_cast<DERIVED*>(this)->VisitAddedToCluster(Base, Cluster); 751 752 // If the base's memspace should be entirely invalidated, add the cluster 753 // to the workspace up front. 754 if (static_cast<DERIVED*>(this)->includeEntireMemorySpace(Base)) 755 AddToWorkList(WorkListElement(Base), &Cluster); 756 } 757 } 758 759 bool AddToWorkList(WorkListElement E, const ClusterBindings *C) { 760 if (C && !Visited.insert(C).second) 761 return false; 762 WL.push_back(E); 763 return true; 764 } 765 766 bool AddToWorkList(const MemRegion *R) { 767 return static_cast<DERIVED*>(this)->AddToWorkList(R); 768 } 769 770 void RunWorkList() { 771 while (!WL.empty()) { 772 WorkListElement E = WL.pop_back_val(); 773 const MemRegion *BaseR = E; 774 775 static_cast<DERIVED*>(this)->VisitCluster(BaseR, getCluster(BaseR)); 776 } 777 } 778 779 void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C) {} 780 void VisitCluster(const MemRegion *baseR, const ClusterBindings *C) {} 781 782 void VisitCluster(const MemRegion *BaseR, const ClusterBindings *C, 783 bool Flag) { 784 static_cast<DERIVED*>(this)->VisitCluster(BaseR, C); 785 } 786 }; 787 } 788 789 //===----------------------------------------------------------------------===// 790 // Binding invalidation. 791 //===----------------------------------------------------------------------===// 792 793 bool RegionStoreManager::scanReachableSymbols(Store S, const MemRegion *R, 794 ScanReachableSymbols &Callbacks) { 795 assert(R == R->getBaseRegion() && "Should only be called for base regions"); 796 RegionBindingsRef B = getRegionBindings(S); 797 const ClusterBindings *Cluster = B.lookup(R); 798 799 if (!Cluster) 800 return true; 801 802 for (ClusterBindings::iterator RI = Cluster->begin(), RE = Cluster->end(); 803 RI != RE; ++RI) { 804 if (!Callbacks.scan(RI.getData())) 805 return false; 806 } 807 808 return true; 809 } 810 811 static inline bool isUnionField(const FieldRegion *FR) { 812 return FR->getDecl()->getParent()->isUnion(); 813 } 814 815 typedef SmallVector<const FieldDecl *, 8> FieldVector; 816 817 static void getSymbolicOffsetFields(BindingKey K, FieldVector &Fields) { 818 assert(K.hasSymbolicOffset() && "Not implemented for concrete offset keys"); 819 820 const MemRegion *Base = K.getConcreteOffsetRegion(); 821 const MemRegion *R = K.getRegion(); 822 823 while (R != Base) { 824 if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) 825 if (!isUnionField(FR)) 826 Fields.push_back(FR->getDecl()); 827 828 R = cast<SubRegion>(R)->getSuperRegion(); 829 } 830 } 831 832 static bool isCompatibleWithFields(BindingKey K, const FieldVector &Fields) { 833 assert(K.hasSymbolicOffset() && "Not implemented for concrete offset keys"); 834 835 if (Fields.empty()) 836 return true; 837 838 FieldVector FieldsInBindingKey; 839 getSymbolicOffsetFields(K, FieldsInBindingKey); 840 841 ptrdiff_t Delta = FieldsInBindingKey.size() - Fields.size(); 842 if (Delta >= 0) 843 return std::equal(FieldsInBindingKey.begin() + Delta, 844 FieldsInBindingKey.end(), 845 Fields.begin()); 846 else 847 return std::equal(FieldsInBindingKey.begin(), FieldsInBindingKey.end(), 848 Fields.begin() - Delta); 849 } 850 851 /// Collects all bindings in \p Cluster that may refer to bindings within 852 /// \p Top. 853 /// 854 /// Each binding is a pair whose \c first is the key (a BindingKey) and whose 855 /// \c second is the value (an SVal). 856 /// 857 /// The \p IncludeAllDefaultBindings parameter specifies whether to include 858 /// default bindings that may extend beyond \p Top itself, e.g. if \p Top is 859 /// an aggregate within a larger aggregate with a default binding. 860 static void 861 collectSubRegionBindings(SmallVectorImpl<BindingPair> &Bindings, 862 SValBuilder &SVB, const ClusterBindings &Cluster, 863 const SubRegion *Top, BindingKey TopKey, 864 bool IncludeAllDefaultBindings) { 865 FieldVector FieldsInSymbolicSubregions; 866 if (TopKey.hasSymbolicOffset()) { 867 getSymbolicOffsetFields(TopKey, FieldsInSymbolicSubregions); 868 Top = TopKey.getConcreteOffsetRegion(); 869 TopKey = BindingKey::Make(Top, BindingKey::Default); 870 } 871 872 // Find the length (in bits) of the region being invalidated. 873 uint64_t Length = UINT64_MAX; 874 SVal Extent = Top->getMemRegionManager().getStaticSize(Top, SVB); 875 if (Optional<nonloc::ConcreteInt> ExtentCI = 876 Extent.getAs<nonloc::ConcreteInt>()) { 877 const llvm::APSInt &ExtentInt = ExtentCI->getValue(); 878 assert(ExtentInt.isNonNegative() || ExtentInt.isUnsigned()); 879 // Extents are in bytes but region offsets are in bits. Be careful! 880 Length = ExtentInt.getLimitedValue() * SVB.getContext().getCharWidth(); 881 } else if (const FieldRegion *FR = dyn_cast<FieldRegion>(Top)) { 882 if (FR->getDecl()->isBitField()) 883 Length = FR->getDecl()->getBitWidthValue(SVB.getContext()); 884 } 885 886 for (ClusterBindings::iterator I = Cluster.begin(), E = Cluster.end(); 887 I != E; ++I) { 888 BindingKey NextKey = I.getKey(); 889 if (NextKey.getRegion() == TopKey.getRegion()) { 890 // FIXME: This doesn't catch the case where we're really invalidating a 891 // region with a symbolic offset. Example: 892 // R: points[i].y 893 // Next: points[0].x 894 895 if (NextKey.getOffset() > TopKey.getOffset() && 896 NextKey.getOffset() - TopKey.getOffset() < Length) { 897 // Case 1: The next binding is inside the region we're invalidating. 898 // Include it. 899 Bindings.push_back(*I); 900 901 } else if (NextKey.getOffset() == TopKey.getOffset()) { 902 // Case 2: The next binding is at the same offset as the region we're 903 // invalidating. In this case, we need to leave default bindings alone, 904 // since they may be providing a default value for a regions beyond what 905 // we're invalidating. 906 // FIXME: This is probably incorrect; consider invalidating an outer 907 // struct whose first field is bound to a LazyCompoundVal. 908 if (IncludeAllDefaultBindings || NextKey.isDirect()) 909 Bindings.push_back(*I); 910 } 911 912 } else if (NextKey.hasSymbolicOffset()) { 913 const MemRegion *Base = NextKey.getConcreteOffsetRegion(); 914 if (Top->isSubRegionOf(Base) && Top != Base) { 915 // Case 3: The next key is symbolic and we just changed something within 916 // its concrete region. We don't know if the binding is still valid, so 917 // we'll be conservative and include it. 918 if (IncludeAllDefaultBindings || NextKey.isDirect()) 919 if (isCompatibleWithFields(NextKey, FieldsInSymbolicSubregions)) 920 Bindings.push_back(*I); 921 } else if (const SubRegion *BaseSR = dyn_cast<SubRegion>(Base)) { 922 // Case 4: The next key is symbolic, but we changed a known 923 // super-region. In this case the binding is certainly included. 924 if (BaseSR->isSubRegionOf(Top)) 925 if (isCompatibleWithFields(NextKey, FieldsInSymbolicSubregions)) 926 Bindings.push_back(*I); 927 } 928 } 929 } 930 } 931 932 static void 933 collectSubRegionBindings(SmallVectorImpl<BindingPair> &Bindings, 934 SValBuilder &SVB, const ClusterBindings &Cluster, 935 const SubRegion *Top, bool IncludeAllDefaultBindings) { 936 collectSubRegionBindings(Bindings, SVB, Cluster, Top, 937 BindingKey::Make(Top, BindingKey::Default), 938 IncludeAllDefaultBindings); 939 } 940 941 RegionBindingsRef 942 RegionStoreManager::removeSubRegionBindings(RegionBindingsConstRef B, 943 const SubRegion *Top) { 944 BindingKey TopKey = BindingKey::Make(Top, BindingKey::Default); 945 const MemRegion *ClusterHead = TopKey.getBaseRegion(); 946 947 if (Top == ClusterHead) { 948 // We can remove an entire cluster's bindings all in one go. 949 return B.remove(Top); 950 } 951 952 const ClusterBindings *Cluster = B.lookup(ClusterHead); 953 if (!Cluster) { 954 // If we're invalidating a region with a symbolic offset, we need to make 955 // sure we don't treat the base region as uninitialized anymore. 956 if (TopKey.hasSymbolicOffset()) { 957 const SubRegion *Concrete = TopKey.getConcreteOffsetRegion(); 958 return B.addBinding(Concrete, BindingKey::Default, UnknownVal()); 959 } 960 return B; 961 } 962 963 SmallVector<BindingPair, 32> Bindings; 964 collectSubRegionBindings(Bindings, svalBuilder, *Cluster, Top, TopKey, 965 /*IncludeAllDefaultBindings=*/false); 966 967 ClusterBindingsRef Result(*Cluster, CBFactory); 968 for (SmallVectorImpl<BindingPair>::const_iterator I = Bindings.begin(), 969 E = Bindings.end(); 970 I != E; ++I) 971 Result = Result.remove(I->first); 972 973 // If we're invalidating a region with a symbolic offset, we need to make sure 974 // we don't treat the base region as uninitialized anymore. 975 // FIXME: This isn't very precise; see the example in 976 // collectSubRegionBindings. 977 if (TopKey.hasSymbolicOffset()) { 978 const SubRegion *Concrete = TopKey.getConcreteOffsetRegion(); 979 Result = Result.add(BindingKey::Make(Concrete, BindingKey::Default), 980 UnknownVal()); 981 } 982 983 if (Result.isEmpty()) 984 return B.remove(ClusterHead); 985 return B.add(ClusterHead, Result.asImmutableMap()); 986 } 987 988 namespace { 989 class InvalidateRegionsWorker : public ClusterAnalysis<InvalidateRegionsWorker> 990 { 991 const Expr *Ex; 992 unsigned Count; 993 const LocationContext *LCtx; 994 InvalidatedSymbols &IS; 995 RegionAndSymbolInvalidationTraits &ITraits; 996 StoreManager::InvalidatedRegions *Regions; 997 GlobalsFilterKind GlobalsFilter; 998 public: 999 InvalidateRegionsWorker(RegionStoreManager &rm, 1000 ProgramStateManager &stateMgr, 1001 RegionBindingsRef b, 1002 const Expr *ex, unsigned count, 1003 const LocationContext *lctx, 1004 InvalidatedSymbols &is, 1005 RegionAndSymbolInvalidationTraits &ITraitsIn, 1006 StoreManager::InvalidatedRegions *r, 1007 GlobalsFilterKind GFK) 1008 : ClusterAnalysis<InvalidateRegionsWorker>(rm, stateMgr, b), 1009 Ex(ex), Count(count), LCtx(lctx), IS(is), ITraits(ITraitsIn), Regions(r), 1010 GlobalsFilter(GFK) {} 1011 1012 void VisitCluster(const MemRegion *baseR, const ClusterBindings *C); 1013 void VisitBinding(SVal V); 1014 1015 using ClusterAnalysis::AddToWorkList; 1016 1017 bool AddToWorkList(const MemRegion *R); 1018 1019 /// Returns true if all clusters in the memory space for \p Base should be 1020 /// be invalidated. 1021 bool includeEntireMemorySpace(const MemRegion *Base); 1022 1023 /// Returns true if the memory space of the given region is one of the global 1024 /// regions specially included at the start of invalidation. 1025 bool isInitiallyIncludedGlobalRegion(const MemRegion *R); 1026 }; 1027 } 1028 1029 bool InvalidateRegionsWorker::AddToWorkList(const MemRegion *R) { 1030 bool doNotInvalidateSuperRegion = ITraits.hasTrait( 1031 R, RegionAndSymbolInvalidationTraits::TK_DoNotInvalidateSuperRegion); 1032 const MemRegion *BaseR = doNotInvalidateSuperRegion ? R : R->getBaseRegion(); 1033 return AddToWorkList(WorkListElement(BaseR), getCluster(BaseR)); 1034 } 1035 1036 void InvalidateRegionsWorker::VisitBinding(SVal V) { 1037 // A symbol? Mark it touched by the invalidation. 1038 if (SymbolRef Sym = V.getAsSymbol()) 1039 IS.insert(Sym); 1040 1041 if (const MemRegion *R = V.getAsRegion()) { 1042 AddToWorkList(R); 1043 return; 1044 } 1045 1046 // Is it a LazyCompoundVal? All references get invalidated as well. 1047 if (Optional<nonloc::LazyCompoundVal> LCS = 1048 V.getAs<nonloc::LazyCompoundVal>()) { 1049 1050 const RegionStoreManager::SValListTy &Vals = RM.getInterestingValues(*LCS); 1051 1052 for (RegionStoreManager::SValListTy::const_iterator I = Vals.begin(), 1053 E = Vals.end(); 1054 I != E; ++I) 1055 VisitBinding(*I); 1056 1057 return; 1058 } 1059 } 1060 1061 void InvalidateRegionsWorker::VisitCluster(const MemRegion *baseR, 1062 const ClusterBindings *C) { 1063 1064 bool PreserveRegionsContents = 1065 ITraits.hasTrait(baseR, 1066 RegionAndSymbolInvalidationTraits::TK_PreserveContents); 1067 1068 if (C) { 1069 for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I) 1070 VisitBinding(I.getData()); 1071 1072 // Invalidate regions contents. 1073 if (!PreserveRegionsContents) 1074 B = B.remove(baseR); 1075 } 1076 1077 if (const auto *TO = dyn_cast<TypedValueRegion>(baseR)) { 1078 if (const auto *RD = TO->getValueType()->getAsCXXRecordDecl()) { 1079 1080 // Lambdas can affect all static local variables without explicitly 1081 // capturing those. 1082 // We invalidate all static locals referenced inside the lambda body. 1083 if (RD->isLambda() && RD->getLambdaCallOperator()->getBody()) { 1084 using namespace ast_matchers; 1085 1086 const char *DeclBind = "DeclBind"; 1087 StatementMatcher RefToStatic = stmt(hasDescendant(declRefExpr( 1088 to(varDecl(hasStaticStorageDuration()).bind(DeclBind))))); 1089 auto Matches = 1090 match(RefToStatic, *RD->getLambdaCallOperator()->getBody(), 1091 RD->getASTContext()); 1092 1093 for (BoundNodes &Match : Matches) { 1094 auto *VD = Match.getNodeAs<VarDecl>(DeclBind); 1095 const VarRegion *ToInvalidate = 1096 RM.getRegionManager().getVarRegion(VD, LCtx); 1097 AddToWorkList(ToInvalidate); 1098 } 1099 } 1100 } 1101 } 1102 1103 // BlockDataRegion? If so, invalidate captured variables that are passed 1104 // by reference. 1105 if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(baseR)) { 1106 for (BlockDataRegion::referenced_vars_iterator 1107 BI = BR->referenced_vars_begin(), BE = BR->referenced_vars_end() ; 1108 BI != BE; ++BI) { 1109 const VarRegion *VR = BI.getCapturedRegion(); 1110 const VarDecl *VD = VR->getDecl(); 1111 if (VD->hasAttr<BlocksAttr>() || !VD->hasLocalStorage()) { 1112 AddToWorkList(VR); 1113 } 1114 else if (Loc::isLocType(VR->getValueType())) { 1115 // Map the current bindings to a Store to retrieve the value 1116 // of the binding. If that binding itself is a region, we should 1117 // invalidate that region. This is because a block may capture 1118 // a pointer value, but the thing pointed by that pointer may 1119 // get invalidated. 1120 SVal V = RM.getBinding(B, loc::MemRegionVal(VR)); 1121 if (Optional<Loc> L = V.getAs<Loc>()) { 1122 if (const MemRegion *LR = L->getAsRegion()) 1123 AddToWorkList(LR); 1124 } 1125 } 1126 } 1127 return; 1128 } 1129 1130 // Symbolic region? 1131 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) 1132 IS.insert(SR->getSymbol()); 1133 1134 // Nothing else should be done in the case when we preserve regions context. 1135 if (PreserveRegionsContents) 1136 return; 1137 1138 // Otherwise, we have a normal data region. Record that we touched the region. 1139 if (Regions) 1140 Regions->push_back(baseR); 1141 1142 if (isa<AllocaRegion, SymbolicRegion>(baseR)) { 1143 // Invalidate the region by setting its default value to 1144 // conjured symbol. The type of the symbol is irrelevant. 1145 DefinedOrUnknownSVal V = 1146 svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, Ctx.IntTy, Count); 1147 B = B.addBinding(baseR, BindingKey::Default, V); 1148 return; 1149 } 1150 1151 if (!baseR->isBoundable()) 1152 return; 1153 1154 const TypedValueRegion *TR = cast<TypedValueRegion>(baseR); 1155 QualType T = TR->getValueType(); 1156 1157 if (isInitiallyIncludedGlobalRegion(baseR)) { 1158 // If the region is a global and we are invalidating all globals, 1159 // erasing the entry is good enough. This causes all globals to be lazily 1160 // symbolicated from the same base symbol. 1161 return; 1162 } 1163 1164 if (T->isRecordType()) { 1165 // Invalidate the region by setting its default value to 1166 // conjured symbol. The type of the symbol is irrelevant. 1167 DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, 1168 Ctx.IntTy, Count); 1169 B = B.addBinding(baseR, BindingKey::Default, V); 1170 return; 1171 } 1172 1173 if (const ArrayType *AT = Ctx.getAsArrayType(T)) { 1174 bool doNotInvalidateSuperRegion = ITraits.hasTrait( 1175 baseR, 1176 RegionAndSymbolInvalidationTraits::TK_DoNotInvalidateSuperRegion); 1177 1178 if (doNotInvalidateSuperRegion) { 1179 // We are not doing blank invalidation of the whole array region so we 1180 // have to manually invalidate each elements. 1181 Optional<uint64_t> NumElements; 1182 1183 // Compute lower and upper offsets for region within array. 1184 if (const ConstantArrayType *CAT = dyn_cast<ConstantArrayType>(AT)) 1185 NumElements = CAT->getSize().getZExtValue(); 1186 if (!NumElements) // We are not dealing with a constant size array 1187 goto conjure_default; 1188 QualType ElementTy = AT->getElementType(); 1189 uint64_t ElemSize = Ctx.getTypeSize(ElementTy); 1190 const RegionOffset &RO = baseR->getAsOffset(); 1191 const MemRegion *SuperR = baseR->getBaseRegion(); 1192 if (RO.hasSymbolicOffset()) { 1193 // If base region has a symbolic offset, 1194 // we revert to invalidating the super region. 1195 if (SuperR) 1196 AddToWorkList(SuperR); 1197 goto conjure_default; 1198 } 1199 1200 uint64_t LowerOffset = RO.getOffset(); 1201 uint64_t UpperOffset = LowerOffset + *NumElements * ElemSize; 1202 bool UpperOverflow = UpperOffset < LowerOffset; 1203 1204 // Invalidate regions which are within array boundaries, 1205 // or have a symbolic offset. 1206 if (!SuperR) 1207 goto conjure_default; 1208 1209 const ClusterBindings *C = B.lookup(SuperR); 1210 if (!C) 1211 goto conjure_default; 1212 1213 for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; 1214 ++I) { 1215 const BindingKey &BK = I.getKey(); 1216 Optional<uint64_t> ROffset = 1217 BK.hasSymbolicOffset() ? Optional<uint64_t>() : BK.getOffset(); 1218 1219 // Check offset is not symbolic and within array's boundaries. 1220 // Handles arrays of 0 elements and of 0-sized elements as well. 1221 if (!ROffset || 1222 ((*ROffset >= LowerOffset && *ROffset < UpperOffset) || 1223 (UpperOverflow && 1224 (*ROffset >= LowerOffset || *ROffset < UpperOffset)) || 1225 (LowerOffset == UpperOffset && *ROffset == LowerOffset))) { 1226 B = B.removeBinding(I.getKey()); 1227 // Bound symbolic regions need to be invalidated for dead symbol 1228 // detection. 1229 SVal V = I.getData(); 1230 const MemRegion *R = V.getAsRegion(); 1231 if (isa_and_nonnull<SymbolicRegion>(R)) 1232 VisitBinding(V); 1233 } 1234 } 1235 } 1236 conjure_default: 1237 // Set the default value of the array to conjured symbol. 1238 DefinedOrUnknownSVal V = 1239 svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, 1240 AT->getElementType(), Count); 1241 B = B.addBinding(baseR, BindingKey::Default, V); 1242 return; 1243 } 1244 1245 DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, 1246 T,Count); 1247 assert(SymbolManager::canSymbolicate(T) || V.isUnknown()); 1248 B = B.addBinding(baseR, BindingKey::Direct, V); 1249 } 1250 1251 bool InvalidateRegionsWorker::isInitiallyIncludedGlobalRegion( 1252 const MemRegion *R) { 1253 switch (GlobalsFilter) { 1254 case GFK_None: 1255 return false; 1256 case GFK_SystemOnly: 1257 return isa<GlobalSystemSpaceRegion>(R->getMemorySpace()); 1258 case GFK_All: 1259 return isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace()); 1260 } 1261 1262 llvm_unreachable("unknown globals filter"); 1263 } 1264 1265 bool InvalidateRegionsWorker::includeEntireMemorySpace(const MemRegion *Base) { 1266 if (isInitiallyIncludedGlobalRegion(Base)) 1267 return true; 1268 1269 const MemSpaceRegion *MemSpace = Base->getMemorySpace(); 1270 return ITraits.hasTrait(MemSpace, 1271 RegionAndSymbolInvalidationTraits::TK_EntireMemSpace); 1272 } 1273 1274 RegionBindingsRef 1275 RegionStoreManager::invalidateGlobalRegion(MemRegion::Kind K, 1276 const Expr *Ex, 1277 unsigned Count, 1278 const LocationContext *LCtx, 1279 RegionBindingsRef B, 1280 InvalidatedRegions *Invalidated) { 1281 // Bind the globals memory space to a new symbol that we will use to derive 1282 // the bindings for all globals. 1283 const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion(K); 1284 SVal V = svalBuilder.conjureSymbolVal(/* symbolTag = */ (const void*) GS, Ex, LCtx, 1285 /* type does not matter */ Ctx.IntTy, 1286 Count); 1287 1288 B = B.removeBinding(GS) 1289 .addBinding(BindingKey::Make(GS, BindingKey::Default), V); 1290 1291 // Even if there are no bindings in the global scope, we still need to 1292 // record that we touched it. 1293 if (Invalidated) 1294 Invalidated->push_back(GS); 1295 1296 return B; 1297 } 1298 1299 void RegionStoreManager::populateWorkList(InvalidateRegionsWorker &W, 1300 ArrayRef<SVal> Values, 1301 InvalidatedRegions *TopLevelRegions) { 1302 for (ArrayRef<SVal>::iterator I = Values.begin(), 1303 E = Values.end(); I != E; ++I) { 1304 SVal V = *I; 1305 if (Optional<nonloc::LazyCompoundVal> LCS = 1306 V.getAs<nonloc::LazyCompoundVal>()) { 1307 1308 const SValListTy &Vals = getInterestingValues(*LCS); 1309 1310 for (SValListTy::const_iterator I = Vals.begin(), 1311 E = Vals.end(); I != E; ++I) { 1312 // Note: the last argument is false here because these are 1313 // non-top-level regions. 1314 if (const MemRegion *R = (*I).getAsRegion()) 1315 W.AddToWorkList(R); 1316 } 1317 continue; 1318 } 1319 1320 if (const MemRegion *R = V.getAsRegion()) { 1321 if (TopLevelRegions) 1322 TopLevelRegions->push_back(R); 1323 W.AddToWorkList(R); 1324 continue; 1325 } 1326 } 1327 } 1328 1329 StoreRef 1330 RegionStoreManager::invalidateRegions(Store store, 1331 ArrayRef<SVal> Values, 1332 const Expr *Ex, unsigned Count, 1333 const LocationContext *LCtx, 1334 const CallEvent *Call, 1335 InvalidatedSymbols &IS, 1336 RegionAndSymbolInvalidationTraits &ITraits, 1337 InvalidatedRegions *TopLevelRegions, 1338 InvalidatedRegions *Invalidated) { 1339 GlobalsFilterKind GlobalsFilter; 1340 if (Call) { 1341 if (Call->isInSystemHeader()) 1342 GlobalsFilter = GFK_SystemOnly; 1343 else 1344 GlobalsFilter = GFK_All; 1345 } else { 1346 GlobalsFilter = GFK_None; 1347 } 1348 1349 RegionBindingsRef B = getRegionBindings(store); 1350 InvalidateRegionsWorker W(*this, StateMgr, B, Ex, Count, LCtx, IS, ITraits, 1351 Invalidated, GlobalsFilter); 1352 1353 // Scan the bindings and generate the clusters. 1354 W.GenerateClusters(); 1355 1356 // Add the regions to the worklist. 1357 populateWorkList(W, Values, TopLevelRegions); 1358 1359 W.RunWorkList(); 1360 1361 // Return the new bindings. 1362 B = W.getRegionBindings(); 1363 1364 // For calls, determine which global regions should be invalidated and 1365 // invalidate them. (Note that function-static and immutable globals are never 1366 // invalidated by this.) 1367 // TODO: This could possibly be more precise with modules. 1368 switch (GlobalsFilter) { 1369 case GFK_All: 1370 B = invalidateGlobalRegion(MemRegion::GlobalInternalSpaceRegionKind, 1371 Ex, Count, LCtx, B, Invalidated); 1372 LLVM_FALLTHROUGH; 1373 case GFK_SystemOnly: 1374 B = invalidateGlobalRegion(MemRegion::GlobalSystemSpaceRegionKind, 1375 Ex, Count, LCtx, B, Invalidated); 1376 LLVM_FALLTHROUGH; 1377 case GFK_None: 1378 break; 1379 } 1380 1381 return StoreRef(B.asStore(), *this); 1382 } 1383 1384 //===----------------------------------------------------------------------===// 1385 // Location and region casting. 1386 //===----------------------------------------------------------------------===// 1387 1388 /// ArrayToPointer - Emulates the "decay" of an array to a pointer 1389 /// type. 'Array' represents the lvalue of the array being decayed 1390 /// to a pointer, and the returned SVal represents the decayed 1391 /// version of that lvalue (i.e., a pointer to the first element of 1392 /// the array). This is called by ExprEngine when evaluating casts 1393 /// from arrays to pointers. 1394 SVal RegionStoreManager::ArrayToPointer(Loc Array, QualType T) { 1395 if (Array.getAs<loc::ConcreteInt>()) 1396 return Array; 1397 1398 if (!Array.getAs<loc::MemRegionVal>()) 1399 return UnknownVal(); 1400 1401 const SubRegion *R = 1402 cast<SubRegion>(Array.castAs<loc::MemRegionVal>().getRegion()); 1403 NonLoc ZeroIdx = svalBuilder.makeZeroArrayIndex(); 1404 return loc::MemRegionVal(MRMgr.getElementRegion(T, ZeroIdx, R, Ctx)); 1405 } 1406 1407 //===----------------------------------------------------------------------===// 1408 // Loading values from regions. 1409 //===----------------------------------------------------------------------===// 1410 1411 SVal RegionStoreManager::getBinding(RegionBindingsConstRef B, Loc L, QualType T) { 1412 assert(!L.getAs<UnknownVal>() && "location unknown"); 1413 assert(!L.getAs<UndefinedVal>() && "location undefined"); 1414 1415 // For access to concrete addresses, return UnknownVal. Checks 1416 // for null dereferences (and similar errors) are done by checkers, not 1417 // the Store. 1418 // FIXME: We can consider lazily symbolicating such memory, but we really 1419 // should defer this when we can reason easily about symbolicating arrays 1420 // of bytes. 1421 if (L.getAs<loc::ConcreteInt>()) { 1422 return UnknownVal(); 1423 } 1424 if (!L.getAs<loc::MemRegionVal>()) { 1425 return UnknownVal(); 1426 } 1427 1428 const MemRegion *MR = L.castAs<loc::MemRegionVal>().getRegion(); 1429 1430 if (isa<BlockDataRegion>(MR)) { 1431 return UnknownVal(); 1432 } 1433 1434 if (!isa<TypedValueRegion>(MR)) { 1435 if (T.isNull()) { 1436 if (const TypedRegion *TR = dyn_cast<TypedRegion>(MR)) 1437 T = TR->getLocationType()->getPointeeType(); 1438 else if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR)) 1439 T = SR->getSymbol()->getType()->getPointeeType(); 1440 } 1441 assert(!T.isNull() && "Unable to auto-detect binding type!"); 1442 assert(!T->isVoidType() && "Attempting to dereference a void pointer!"); 1443 MR = GetElementZeroRegion(cast<SubRegion>(MR), T); 1444 } else { 1445 T = cast<TypedValueRegion>(MR)->getValueType(); 1446 } 1447 1448 // FIXME: Perhaps this method should just take a 'const MemRegion*' argument 1449 // instead of 'Loc', and have the other Loc cases handled at a higher level. 1450 const TypedValueRegion *R = cast<TypedValueRegion>(MR); 1451 QualType RTy = R->getValueType(); 1452 1453 // FIXME: we do not yet model the parts of a complex type, so treat the 1454 // whole thing as "unknown". 1455 if (RTy->isAnyComplexType()) 1456 return UnknownVal(); 1457 1458 // FIXME: We should eventually handle funny addressing. e.g.: 1459 // 1460 // int x = ...; 1461 // int *p = &x; 1462 // char *q = (char*) p; 1463 // char c = *q; // returns the first byte of 'x'. 1464 // 1465 // Such funny addressing will occur due to layering of regions. 1466 if (RTy->isStructureOrClassType()) 1467 return getBindingForStruct(B, R); 1468 1469 // FIXME: Handle unions. 1470 if (RTy->isUnionType()) 1471 return createLazyBinding(B, R); 1472 1473 if (RTy->isArrayType()) { 1474 if (RTy->isConstantArrayType()) 1475 return getBindingForArray(B, R); 1476 else 1477 return UnknownVal(); 1478 } 1479 1480 // FIXME: handle Vector types. 1481 if (RTy->isVectorType()) 1482 return UnknownVal(); 1483 1484 if (const FieldRegion* FR = dyn_cast<FieldRegion>(R)) 1485 return svalBuilder.evalCast(getBindingForField(B, FR), T, QualType{}); 1486 1487 if (const ElementRegion* ER = dyn_cast<ElementRegion>(R)) { 1488 // FIXME: Here we actually perform an implicit conversion from the loaded 1489 // value to the element type. Eventually we want to compose these values 1490 // more intelligently. For example, an 'element' can encompass multiple 1491 // bound regions (e.g., several bound bytes), or could be a subset of 1492 // a larger value. 1493 return svalBuilder.evalCast(getBindingForElement(B, ER), T, QualType{}); 1494 } 1495 1496 if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R)) { 1497 // FIXME: Here we actually perform an implicit conversion from the loaded 1498 // value to the ivar type. What we should model is stores to ivars 1499 // that blow past the extent of the ivar. If the address of the ivar is 1500 // reinterpretted, it is possible we stored a different value that could 1501 // fit within the ivar. Either we need to cast these when storing them 1502 // or reinterpret them lazily (as we do here). 1503 return svalBuilder.evalCast(getBindingForObjCIvar(B, IVR), T, QualType{}); 1504 } 1505 1506 if (const VarRegion *VR = dyn_cast<VarRegion>(R)) { 1507 // FIXME: Here we actually perform an implicit conversion from the loaded 1508 // value to the variable type. What we should model is stores to variables 1509 // that blow past the extent of the variable. If the address of the 1510 // variable is reinterpretted, it is possible we stored a different value 1511 // that could fit within the variable. Either we need to cast these when 1512 // storing them or reinterpret them lazily (as we do here). 1513 return svalBuilder.evalCast(getBindingForVar(B, VR), T, QualType{}); 1514 } 1515 1516 const SVal *V = B.lookup(R, BindingKey::Direct); 1517 1518 // Check if the region has a binding. 1519 if (V) 1520 return *V; 1521 1522 // The location does not have a bound value. This means that it has 1523 // the value it had upon its creation and/or entry to the analyzed 1524 // function/method. These are either symbolic values or 'undefined'. 1525 if (R->hasStackNonParametersStorage()) { 1526 // All stack variables are considered to have undefined values 1527 // upon creation. All heap allocated blocks are considered to 1528 // have undefined values as well unless they are explicitly bound 1529 // to specific values. 1530 return UndefinedVal(); 1531 } 1532 1533 // All other values are symbolic. 1534 return svalBuilder.getRegionValueSymbolVal(R); 1535 } 1536 1537 static QualType getUnderlyingType(const SubRegion *R) { 1538 QualType RegionTy; 1539 if (const TypedValueRegion *TVR = dyn_cast<TypedValueRegion>(R)) 1540 RegionTy = TVR->getValueType(); 1541 1542 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) 1543 RegionTy = SR->getSymbol()->getType(); 1544 1545 return RegionTy; 1546 } 1547 1548 /// Checks to see if store \p B has a lazy binding for region \p R. 1549 /// 1550 /// If \p AllowSubregionBindings is \c false, a lazy binding will be rejected 1551 /// if there are additional bindings within \p R. 1552 /// 1553 /// Note that unlike RegionStoreManager::findLazyBinding, this will not search 1554 /// for lazy bindings for super-regions of \p R. 1555 static Optional<nonloc::LazyCompoundVal> 1556 getExistingLazyBinding(SValBuilder &SVB, RegionBindingsConstRef B, 1557 const SubRegion *R, bool AllowSubregionBindings) { 1558 Optional<SVal> V = B.getDefaultBinding(R); 1559 if (!V) 1560 return None; 1561 1562 Optional<nonloc::LazyCompoundVal> LCV = V->getAs<nonloc::LazyCompoundVal>(); 1563 if (!LCV) 1564 return None; 1565 1566 // If the LCV is for a subregion, the types might not match, and we shouldn't 1567 // reuse the binding. 1568 QualType RegionTy = getUnderlyingType(R); 1569 if (!RegionTy.isNull() && 1570 !RegionTy->isVoidPointerType()) { 1571 QualType SourceRegionTy = LCV->getRegion()->getValueType(); 1572 if (!SVB.getContext().hasSameUnqualifiedType(RegionTy, SourceRegionTy)) 1573 return None; 1574 } 1575 1576 if (!AllowSubregionBindings) { 1577 // If there are any other bindings within this region, we shouldn't reuse 1578 // the top-level binding. 1579 SmallVector<BindingPair, 16> Bindings; 1580 collectSubRegionBindings(Bindings, SVB, *B.lookup(R->getBaseRegion()), R, 1581 /*IncludeAllDefaultBindings=*/true); 1582 if (Bindings.size() > 1) 1583 return None; 1584 } 1585 1586 return *LCV; 1587 } 1588 1589 1590 std::pair<Store, const SubRegion *> 1591 RegionStoreManager::findLazyBinding(RegionBindingsConstRef B, 1592 const SubRegion *R, 1593 const SubRegion *originalRegion) { 1594 if (originalRegion != R) { 1595 if (Optional<nonloc::LazyCompoundVal> V = 1596 getExistingLazyBinding(svalBuilder, B, R, true)) 1597 return std::make_pair(V->getStore(), V->getRegion()); 1598 } 1599 1600 typedef std::pair<Store, const SubRegion *> StoreRegionPair; 1601 StoreRegionPair Result = StoreRegionPair(); 1602 1603 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) { 1604 Result = findLazyBinding(B, cast<SubRegion>(ER->getSuperRegion()), 1605 originalRegion); 1606 1607 if (Result.second) 1608 Result.second = MRMgr.getElementRegionWithSuper(ER, Result.second); 1609 1610 } else if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) { 1611 Result = findLazyBinding(B, cast<SubRegion>(FR->getSuperRegion()), 1612 originalRegion); 1613 1614 if (Result.second) 1615 Result.second = MRMgr.getFieldRegionWithSuper(FR, Result.second); 1616 1617 } else if (const CXXBaseObjectRegion *BaseReg = 1618 dyn_cast<CXXBaseObjectRegion>(R)) { 1619 // C++ base object region is another kind of region that we should blast 1620 // through to look for lazy compound value. It is like a field region. 1621 Result = findLazyBinding(B, cast<SubRegion>(BaseReg->getSuperRegion()), 1622 originalRegion); 1623 1624 if (Result.second) 1625 Result.second = MRMgr.getCXXBaseObjectRegionWithSuper(BaseReg, 1626 Result.second); 1627 } 1628 1629 return Result; 1630 } 1631 1632 Optional<SVal> RegionStoreManager::getConstantValFromConstArrayInitializer( 1633 RegionBindingsConstRef B, const VarRegion *VR, const ElementRegion *R) { 1634 assert(R && VR && "Regions should not be null"); 1635 1636 // Check if the containing array has an initialized value that we can trust. 1637 // We can trust a const value or a value of a global initializer in main(). 1638 const VarDecl *VD = VR->getDecl(); 1639 if (!VD->getType().isConstQualified() && 1640 !R->getElementType().isConstQualified() && 1641 (!B.isMainAnalysis() || !VD->hasGlobalStorage())) 1642 return None; 1643 1644 // Array's declaration should have an initializer. 1645 const Expr *Init = VD->getAnyInitializer(); 1646 if (!Init) 1647 return None; 1648 1649 // Array's declaration should have ConstantArrayType type, because only this 1650 // type contains an array extent. 1651 const ConstantArrayType *CAT = Ctx.getAsConstantArrayType(VD->getType()); 1652 if (!CAT) 1653 return None; 1654 1655 // Array should be one-dimensional. 1656 // TODO: Support multidimensional array. 1657 if (isa<ConstantArrayType>(CAT->getElementType())) // is multidimensional 1658 return None; 1659 1660 // Array's offset should be a concrete value. 1661 // Return Unknown value if symbolic index presented. 1662 // FIXME: We also need to take ElementRegions with symbolic 1663 // indexes into account. 1664 const auto OffsetVal = R->getIndex().getAs<nonloc::ConcreteInt>(); 1665 if (!OffsetVal.hasValue()) 1666 return UnknownVal(); 1667 1668 // Check offset for being out of bounds. 1669 // C++20 [expr.add] 7.6.6.4 (excerpt): 1670 // If P points to an array element i of an array object x with n 1671 // elements, where i < 0 or i > n, the behavior is undefined. 1672 // Dereferencing is not allowed on the "one past the last 1673 // element", when i == n. 1674 // Example: 1675 // const int arr[4] = {1, 2}; 1676 // const int *ptr = arr; 1677 // int x0 = ptr[0]; // 1 1678 // int x1 = ptr[1]; // 2 1679 // int x2 = ptr[2]; // 0 1680 // int x3 = ptr[3]; // 0 1681 // int x4 = ptr[4]; // UB 1682 // int x5 = ptr[-1]; // UB 1683 const llvm::APSInt &OffsetInt = OffsetVal->getValue(); 1684 const auto Offset = static_cast<uint64_t>(OffsetInt.getExtValue()); 1685 // Use `getZExtValue` because array extent can not be negative. 1686 const uint64_t Extent = CAT->getSize().getZExtValue(); 1687 // Check for `OffsetInt < 0` but NOT for `Offset < 0`, because `OffsetInt` 1688 // CAN be negative, but `Offset` can NOT, because `Offset` is an uint64_t. 1689 if (OffsetInt < 0 || Offset >= Extent) 1690 return UndefinedVal(); 1691 // From here `Offset` is in the bounds. 1692 1693 // Handle InitListExpr. 1694 if (const auto *ILE = dyn_cast<InitListExpr>(Init)) 1695 return getSValFromInitListExpr(ILE, Offset, R->getElementType()); 1696 1697 // FIXME: Handle StringLiteral. 1698 1699 // FIXME: Handle CompoundLiteralExpr. 1700 1701 return None; 1702 } 1703 1704 Optional<SVal> 1705 RegionStoreManager::getSValFromInitListExpr(const InitListExpr *ILE, 1706 uint64_t Offset, QualType ElemT) { 1707 assert(ILE && "InitListExpr should not be null"); 1708 1709 // C++20 [expr.add] 9.4.17.5 (excerpt): 1710 // i-th array element is value-initialized for each k < i ≤ n, 1711 // where k is an expression-list size and n is an array extent. 1712 if (Offset >= ILE->getNumInits()) 1713 return svalBuilder.makeZeroVal(ElemT); 1714 1715 // Return a constant value, if it is presented. 1716 // FIXME: Support other SVals. 1717 const Expr *E = ILE->getInit(Offset); 1718 return svalBuilder.getConstantVal(E); 1719 } 1720 1721 SVal RegionStoreManager::getBindingForElement(RegionBindingsConstRef B, 1722 const ElementRegion* R) { 1723 // Check if the region has a binding. 1724 if (const Optional<SVal> &V = B.getDirectBinding(R)) 1725 return *V; 1726 1727 const MemRegion* superR = R->getSuperRegion(); 1728 1729 // Check if the region is an element region of a string literal. 1730 if (const StringRegion *StrR = dyn_cast<StringRegion>(superR)) { 1731 // FIXME: Handle loads from strings where the literal is treated as 1732 // an integer, e.g., *((unsigned int*)"hello") 1733 QualType T = Ctx.getAsArrayType(StrR->getValueType())->getElementType(); 1734 if (!Ctx.hasSameUnqualifiedType(T, R->getElementType())) 1735 return UnknownVal(); 1736 1737 const StringLiteral *Str = StrR->getStringLiteral(); 1738 SVal Idx = R->getIndex(); 1739 if (Optional<nonloc::ConcreteInt> CI = Idx.getAs<nonloc::ConcreteInt>()) { 1740 int64_t i = CI->getValue().getSExtValue(); 1741 // Abort on string underrun. This can be possible by arbitrary 1742 // clients of getBindingForElement(). 1743 if (i < 0) 1744 return UndefinedVal(); 1745 int64_t length = Str->getLength(); 1746 // Technically, only i == length is guaranteed to be null. 1747 // However, such overflows should be caught before reaching this point; 1748 // the only time such an access would be made is if a string literal was 1749 // used to initialize a larger array. 1750 char c = (i >= length) ? '\0' : Str->getCodeUnit(i); 1751 return svalBuilder.makeIntVal(c, T); 1752 } 1753 } else if (const VarRegion *VR = dyn_cast<VarRegion>(superR)) { 1754 if (Optional<SVal> V = getConstantValFromConstArrayInitializer(B, VR, R)) 1755 return *V; 1756 } 1757 1758 // Check for loads from a code text region. For such loads, just give up. 1759 if (isa<CodeTextRegion>(superR)) 1760 return UnknownVal(); 1761 1762 // Handle the case where we are indexing into a larger scalar object. 1763 // For example, this handles: 1764 // int x = ... 1765 // char *y = &x; 1766 // return *y; 1767 // FIXME: This is a hack, and doesn't do anything really intelligent yet. 1768 const RegionRawOffset &O = R->getAsArrayOffset(); 1769 1770 // If we cannot reason about the offset, return an unknown value. 1771 if (!O.getRegion()) 1772 return UnknownVal(); 1773 1774 if (const TypedValueRegion *baseR = 1775 dyn_cast_or_null<TypedValueRegion>(O.getRegion())) { 1776 QualType baseT = baseR->getValueType(); 1777 if (baseT->isScalarType()) { 1778 QualType elemT = R->getElementType(); 1779 if (elemT->isScalarType()) { 1780 if (Ctx.getTypeSizeInChars(baseT) >= Ctx.getTypeSizeInChars(elemT)) { 1781 if (const Optional<SVal> &V = B.getDirectBinding(superR)) { 1782 if (SymbolRef parentSym = V->getAsSymbol()) 1783 return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); 1784 1785 if (V->isUnknownOrUndef()) 1786 return *V; 1787 // Other cases: give up. We are indexing into a larger object 1788 // that has some value, but we don't know how to handle that yet. 1789 return UnknownVal(); 1790 } 1791 } 1792 } 1793 } 1794 } 1795 return getBindingForFieldOrElementCommon(B, R, R->getElementType()); 1796 } 1797 1798 SVal RegionStoreManager::getBindingForField(RegionBindingsConstRef B, 1799 const FieldRegion* R) { 1800 1801 // Check if the region has a binding. 1802 if (const Optional<SVal> &V = B.getDirectBinding(R)) 1803 return *V; 1804 1805 // Is the field declared constant and has an in-class initializer? 1806 const FieldDecl *FD = R->getDecl(); 1807 QualType Ty = FD->getType(); 1808 if (Ty.isConstQualified()) 1809 if (const Expr *Init = FD->getInClassInitializer()) 1810 if (Optional<SVal> V = svalBuilder.getConstantVal(Init)) 1811 return *V; 1812 1813 // If the containing record was initialized, try to get its constant value. 1814 const MemRegion* superR = R->getSuperRegion(); 1815 if (const auto *VR = dyn_cast<VarRegion>(superR)) { 1816 const VarDecl *VD = VR->getDecl(); 1817 QualType RecordVarTy = VD->getType(); 1818 unsigned Index = FD->getFieldIndex(); 1819 // Either the record variable or the field has an initializer that we can 1820 // trust. We trust initializers of constants and, additionally, respect 1821 // initializers of globals when analyzing main(). 1822 if (RecordVarTy.isConstQualified() || Ty.isConstQualified() || 1823 (B.isMainAnalysis() && VD->hasGlobalStorage())) 1824 if (const Expr *Init = VD->getAnyInitializer()) 1825 if (const auto *InitList = dyn_cast<InitListExpr>(Init)) { 1826 if (Index < InitList->getNumInits()) { 1827 if (const Expr *FieldInit = InitList->getInit(Index)) 1828 if (Optional<SVal> V = svalBuilder.getConstantVal(FieldInit)) 1829 return *V; 1830 } else { 1831 return svalBuilder.makeZeroVal(Ty); 1832 } 1833 } 1834 } 1835 1836 return getBindingForFieldOrElementCommon(B, R, Ty); 1837 } 1838 1839 Optional<SVal> 1840 RegionStoreManager::getBindingForDerivedDefaultValue(RegionBindingsConstRef B, 1841 const MemRegion *superR, 1842 const TypedValueRegion *R, 1843 QualType Ty) { 1844 1845 if (const Optional<SVal> &D = B.getDefaultBinding(superR)) { 1846 const SVal &val = D.getValue(); 1847 if (SymbolRef parentSym = val.getAsSymbol()) 1848 return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); 1849 1850 if (val.isZeroConstant()) 1851 return svalBuilder.makeZeroVal(Ty); 1852 1853 if (val.isUnknownOrUndef()) 1854 return val; 1855 1856 // Lazy bindings are usually handled through getExistingLazyBinding(). 1857 // We should unify these two code paths at some point. 1858 if (val.getAs<nonloc::LazyCompoundVal>() || 1859 val.getAs<nonloc::CompoundVal>()) 1860 return val; 1861 1862 llvm_unreachable("Unknown default value"); 1863 } 1864 1865 return None; 1866 } 1867 1868 SVal RegionStoreManager::getLazyBinding(const SubRegion *LazyBindingRegion, 1869 RegionBindingsRef LazyBinding) { 1870 SVal Result; 1871 if (const ElementRegion *ER = dyn_cast<ElementRegion>(LazyBindingRegion)) 1872 Result = getBindingForElement(LazyBinding, ER); 1873 else 1874 Result = getBindingForField(LazyBinding, 1875 cast<FieldRegion>(LazyBindingRegion)); 1876 1877 // FIXME: This is a hack to deal with RegionStore's inability to distinguish a 1878 // default value for /part/ of an aggregate from a default value for the 1879 // /entire/ aggregate. The most common case of this is when struct Outer 1880 // has as its first member a struct Inner, which is copied in from a stack 1881 // variable. In this case, even if the Outer's default value is symbolic, 0, 1882 // or unknown, it gets overridden by the Inner's default value of undefined. 1883 // 1884 // This is a general problem -- if the Inner is zero-initialized, the Outer 1885 // will now look zero-initialized. The proper way to solve this is with a 1886 // new version of RegionStore that tracks the extent of a binding as well 1887 // as the offset. 1888 // 1889 // This hack only takes care of the undefined case because that can very 1890 // quickly result in a warning. 1891 if (Result.isUndef()) 1892 Result = UnknownVal(); 1893 1894 return Result; 1895 } 1896 1897 SVal 1898 RegionStoreManager::getBindingForFieldOrElementCommon(RegionBindingsConstRef B, 1899 const TypedValueRegion *R, 1900 QualType Ty) { 1901 1902 // At this point we have already checked in either getBindingForElement or 1903 // getBindingForField if 'R' has a direct binding. 1904 1905 // Lazy binding? 1906 Store lazyBindingStore = nullptr; 1907 const SubRegion *lazyBindingRegion = nullptr; 1908 std::tie(lazyBindingStore, lazyBindingRegion) = findLazyBinding(B, R, R); 1909 if (lazyBindingRegion) 1910 return getLazyBinding(lazyBindingRegion, 1911 getRegionBindings(lazyBindingStore)); 1912 1913 // Record whether or not we see a symbolic index. That can completely 1914 // be out of scope of our lookup. 1915 bool hasSymbolicIndex = false; 1916 1917 // FIXME: This is a hack to deal with RegionStore's inability to distinguish a 1918 // default value for /part/ of an aggregate from a default value for the 1919 // /entire/ aggregate. The most common case of this is when struct Outer 1920 // has as its first member a struct Inner, which is copied in from a stack 1921 // variable. In this case, even if the Outer's default value is symbolic, 0, 1922 // or unknown, it gets overridden by the Inner's default value of undefined. 1923 // 1924 // This is a general problem -- if the Inner is zero-initialized, the Outer 1925 // will now look zero-initialized. The proper way to solve this is with a 1926 // new version of RegionStore that tracks the extent of a binding as well 1927 // as the offset. 1928 // 1929 // This hack only takes care of the undefined case because that can very 1930 // quickly result in a warning. 1931 bool hasPartialLazyBinding = false; 1932 1933 const SubRegion *SR = R; 1934 while (SR) { 1935 const MemRegion *Base = SR->getSuperRegion(); 1936 if (Optional<SVal> D = getBindingForDerivedDefaultValue(B, Base, R, Ty)) { 1937 if (D->getAs<nonloc::LazyCompoundVal>()) { 1938 hasPartialLazyBinding = true; 1939 break; 1940 } 1941 1942 return *D; 1943 } 1944 1945 if (const ElementRegion *ER = dyn_cast<ElementRegion>(Base)) { 1946 NonLoc index = ER->getIndex(); 1947 if (!index.isConstant()) 1948 hasSymbolicIndex = true; 1949 } 1950 1951 // If our super region is a field or element itself, walk up the region 1952 // hierarchy to see if there is a default value installed in an ancestor. 1953 SR = dyn_cast<SubRegion>(Base); 1954 } 1955 1956 if (R->hasStackNonParametersStorage()) { 1957 if (isa<ElementRegion>(R)) { 1958 // Currently we don't reason specially about Clang-style vectors. Check 1959 // if superR is a vector and if so return Unknown. 1960 if (const TypedValueRegion *typedSuperR = 1961 dyn_cast<TypedValueRegion>(R->getSuperRegion())) { 1962 if (typedSuperR->getValueType()->isVectorType()) 1963 return UnknownVal(); 1964 } 1965 } 1966 1967 // FIXME: We also need to take ElementRegions with symbolic indexes into 1968 // account. This case handles both directly accessing an ElementRegion 1969 // with a symbolic offset, but also fields within an element with 1970 // a symbolic offset. 1971 if (hasSymbolicIndex) 1972 return UnknownVal(); 1973 1974 // Additionally allow introspection of a block's internal layout. 1975 if (!hasPartialLazyBinding && !isa<BlockDataRegion>(R->getBaseRegion())) 1976 return UndefinedVal(); 1977 } 1978 1979 // All other values are symbolic. 1980 return svalBuilder.getRegionValueSymbolVal(R); 1981 } 1982 1983 SVal RegionStoreManager::getBindingForObjCIvar(RegionBindingsConstRef B, 1984 const ObjCIvarRegion* R) { 1985 // Check if the region has a binding. 1986 if (const Optional<SVal> &V = B.getDirectBinding(R)) 1987 return *V; 1988 1989 const MemRegion *superR = R->getSuperRegion(); 1990 1991 // Check if the super region has a default binding. 1992 if (const Optional<SVal> &V = B.getDefaultBinding(superR)) { 1993 if (SymbolRef parentSym = V->getAsSymbol()) 1994 return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); 1995 1996 // Other cases: give up. 1997 return UnknownVal(); 1998 } 1999 2000 return getBindingForLazySymbol(R); 2001 } 2002 2003 SVal RegionStoreManager::getBindingForVar(RegionBindingsConstRef B, 2004 const VarRegion *R) { 2005 2006 // Check if the region has a binding. 2007 if (Optional<SVal> V = B.getDirectBinding(R)) 2008 return *V; 2009 2010 if (Optional<SVal> V = B.getDefaultBinding(R)) 2011 return *V; 2012 2013 // Lazily derive a value for the VarRegion. 2014 const VarDecl *VD = R->getDecl(); 2015 const MemSpaceRegion *MS = R->getMemorySpace(); 2016 2017 // Arguments are always symbolic. 2018 if (isa<StackArgumentsSpaceRegion>(MS)) 2019 return svalBuilder.getRegionValueSymbolVal(R); 2020 2021 // Is 'VD' declared constant? If so, retrieve the constant value. 2022 if (VD->getType().isConstQualified()) { 2023 if (const Expr *Init = VD->getAnyInitializer()) { 2024 if (Optional<SVal> V = svalBuilder.getConstantVal(Init)) 2025 return *V; 2026 2027 // If the variable is const qualified and has an initializer but 2028 // we couldn't evaluate initializer to a value, treat the value as 2029 // unknown. 2030 return UnknownVal(); 2031 } 2032 } 2033 2034 // This must come after the check for constants because closure-captured 2035 // constant variables may appear in UnknownSpaceRegion. 2036 if (isa<UnknownSpaceRegion>(MS)) 2037 return svalBuilder.getRegionValueSymbolVal(R); 2038 2039 if (isa<GlobalsSpaceRegion>(MS)) { 2040 QualType T = VD->getType(); 2041 2042 // If we're in main(), then global initializers have not become stale yet. 2043 if (B.isMainAnalysis()) 2044 if (const Expr *Init = VD->getAnyInitializer()) 2045 if (Optional<SVal> V = svalBuilder.getConstantVal(Init)) 2046 return *V; 2047 2048 // Function-scoped static variables are default-initialized to 0; if they 2049 // have an initializer, it would have been processed by now. 2050 // FIXME: This is only true when we're starting analysis from main(). 2051 // We're losing a lot of coverage here. 2052 if (isa<StaticGlobalSpaceRegion>(MS)) 2053 return svalBuilder.makeZeroVal(T); 2054 2055 if (Optional<SVal> V = getBindingForDerivedDefaultValue(B, MS, R, T)) { 2056 assert(!V->getAs<nonloc::LazyCompoundVal>()); 2057 return V.getValue(); 2058 } 2059 2060 return svalBuilder.getRegionValueSymbolVal(R); 2061 } 2062 2063 return UndefinedVal(); 2064 } 2065 2066 SVal RegionStoreManager::getBindingForLazySymbol(const TypedValueRegion *R) { 2067 // All other values are symbolic. 2068 return svalBuilder.getRegionValueSymbolVal(R); 2069 } 2070 2071 const RegionStoreManager::SValListTy & 2072 RegionStoreManager::getInterestingValues(nonloc::LazyCompoundVal LCV) { 2073 // First, check the cache. 2074 LazyBindingsMapTy::iterator I = LazyBindingsMap.find(LCV.getCVData()); 2075 if (I != LazyBindingsMap.end()) 2076 return I->second; 2077 2078 // If we don't have a list of values cached, start constructing it. 2079 SValListTy List; 2080 2081 const SubRegion *LazyR = LCV.getRegion(); 2082 RegionBindingsRef B = getRegionBindings(LCV.getStore()); 2083 2084 // If this region had /no/ bindings at the time, there are no interesting 2085 // values to return. 2086 const ClusterBindings *Cluster = B.lookup(LazyR->getBaseRegion()); 2087 if (!Cluster) 2088 return (LazyBindingsMap[LCV.getCVData()] = std::move(List)); 2089 2090 SmallVector<BindingPair, 32> Bindings; 2091 collectSubRegionBindings(Bindings, svalBuilder, *Cluster, LazyR, 2092 /*IncludeAllDefaultBindings=*/true); 2093 for (SmallVectorImpl<BindingPair>::const_iterator I = Bindings.begin(), 2094 E = Bindings.end(); 2095 I != E; ++I) { 2096 SVal V = I->second; 2097 if (V.isUnknownOrUndef() || V.isConstant()) 2098 continue; 2099 2100 if (Optional<nonloc::LazyCompoundVal> InnerLCV = 2101 V.getAs<nonloc::LazyCompoundVal>()) { 2102 const SValListTy &InnerList = getInterestingValues(*InnerLCV); 2103 List.insert(List.end(), InnerList.begin(), InnerList.end()); 2104 continue; 2105 } 2106 2107 List.push_back(V); 2108 } 2109 2110 return (LazyBindingsMap[LCV.getCVData()] = std::move(List)); 2111 } 2112 2113 NonLoc RegionStoreManager::createLazyBinding(RegionBindingsConstRef B, 2114 const TypedValueRegion *R) { 2115 if (Optional<nonloc::LazyCompoundVal> V = 2116 getExistingLazyBinding(svalBuilder, B, R, false)) 2117 return *V; 2118 2119 return svalBuilder.makeLazyCompoundVal(StoreRef(B.asStore(), *this), R); 2120 } 2121 2122 static bool isRecordEmpty(const RecordDecl *RD) { 2123 if (!RD->field_empty()) 2124 return false; 2125 if (const CXXRecordDecl *CRD = dyn_cast<CXXRecordDecl>(RD)) 2126 return CRD->getNumBases() == 0; 2127 return true; 2128 } 2129 2130 SVal RegionStoreManager::getBindingForStruct(RegionBindingsConstRef B, 2131 const TypedValueRegion *R) { 2132 const RecordDecl *RD = R->getValueType()->castAs<RecordType>()->getDecl(); 2133 if (!RD->getDefinition() || isRecordEmpty(RD)) 2134 return UnknownVal(); 2135 2136 return createLazyBinding(B, R); 2137 } 2138 2139 SVal RegionStoreManager::getBindingForArray(RegionBindingsConstRef B, 2140 const TypedValueRegion *R) { 2141 assert(Ctx.getAsConstantArrayType(R->getValueType()) && 2142 "Only constant array types can have compound bindings."); 2143 2144 return createLazyBinding(B, R); 2145 } 2146 2147 bool RegionStoreManager::includedInBindings(Store store, 2148 const MemRegion *region) const { 2149 RegionBindingsRef B = getRegionBindings(store); 2150 region = region->getBaseRegion(); 2151 2152 // Quick path: if the base is the head of a cluster, the region is live. 2153 if (B.lookup(region)) 2154 return true; 2155 2156 // Slow path: if the region is the VALUE of any binding, it is live. 2157 for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI) { 2158 const ClusterBindings &Cluster = RI.getData(); 2159 for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end(); 2160 CI != CE; ++CI) { 2161 const SVal &D = CI.getData(); 2162 if (const MemRegion *R = D.getAsRegion()) 2163 if (R->getBaseRegion() == region) 2164 return true; 2165 } 2166 } 2167 2168 return false; 2169 } 2170 2171 //===----------------------------------------------------------------------===// 2172 // Binding values to regions. 2173 //===----------------------------------------------------------------------===// 2174 2175 StoreRef RegionStoreManager::killBinding(Store ST, Loc L) { 2176 if (Optional<loc::MemRegionVal> LV = L.getAs<loc::MemRegionVal>()) 2177 if (const MemRegion* R = LV->getRegion()) 2178 return StoreRef(getRegionBindings(ST).removeBinding(R) 2179 .asImmutableMap() 2180 .getRootWithoutRetain(), 2181 *this); 2182 2183 return StoreRef(ST, *this); 2184 } 2185 2186 RegionBindingsRef 2187 RegionStoreManager::bind(RegionBindingsConstRef B, Loc L, SVal V) { 2188 if (L.getAs<loc::ConcreteInt>()) 2189 return B; 2190 2191 // If we get here, the location should be a region. 2192 const MemRegion *R = L.castAs<loc::MemRegionVal>().getRegion(); 2193 2194 // Check if the region is a struct region. 2195 if (const TypedValueRegion* TR = dyn_cast<TypedValueRegion>(R)) { 2196 QualType Ty = TR->getValueType(); 2197 if (Ty->isArrayType()) 2198 return bindArray(B, TR, V); 2199 if (Ty->isStructureOrClassType()) 2200 return bindStruct(B, TR, V); 2201 if (Ty->isVectorType()) 2202 return bindVector(B, TR, V); 2203 if (Ty->isUnionType()) 2204 return bindAggregate(B, TR, V); 2205 } 2206 2207 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) { 2208 // Binding directly to a symbolic region should be treated as binding 2209 // to element 0. 2210 QualType T = SR->getSymbol()->getType(); 2211 if (T->isAnyPointerType() || T->isReferenceType()) 2212 T = T->getPointeeType(); 2213 2214 R = GetElementZeroRegion(SR, T); 2215 } 2216 2217 assert((!isa<CXXThisRegion>(R) || !B.lookup(R)) && 2218 "'this' pointer is not an l-value and is not assignable"); 2219 2220 // Clear out bindings that may overlap with this binding. 2221 RegionBindingsRef NewB = removeSubRegionBindings(B, cast<SubRegion>(R)); 2222 return NewB.addBinding(BindingKey::Make(R, BindingKey::Direct), V); 2223 } 2224 2225 RegionBindingsRef 2226 RegionStoreManager::setImplicitDefaultValue(RegionBindingsConstRef B, 2227 const MemRegion *R, 2228 QualType T) { 2229 SVal V; 2230 2231 if (Loc::isLocType(T)) 2232 V = svalBuilder.makeNull(); 2233 else if (T->isIntegralOrEnumerationType()) 2234 V = svalBuilder.makeZeroVal(T); 2235 else if (T->isStructureOrClassType() || T->isArrayType()) { 2236 // Set the default value to a zero constant when it is a structure 2237 // or array. The type doesn't really matter. 2238 V = svalBuilder.makeZeroVal(Ctx.IntTy); 2239 } 2240 else { 2241 // We can't represent values of this type, but we still need to set a value 2242 // to record that the region has been initialized. 2243 // If this assertion ever fires, a new case should be added above -- we 2244 // should know how to default-initialize any value we can symbolicate. 2245 assert(!SymbolManager::canSymbolicate(T) && "This type is representable"); 2246 V = UnknownVal(); 2247 } 2248 2249 return B.addBinding(R, BindingKey::Default, V); 2250 } 2251 2252 RegionBindingsRef 2253 RegionStoreManager::bindArray(RegionBindingsConstRef B, 2254 const TypedValueRegion* R, 2255 SVal Init) { 2256 2257 const ArrayType *AT =cast<ArrayType>(Ctx.getCanonicalType(R->getValueType())); 2258 QualType ElementTy = AT->getElementType(); 2259 Optional<uint64_t> Size; 2260 2261 if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(AT)) 2262 Size = CAT->getSize().getZExtValue(); 2263 2264 // Check if the init expr is a literal. If so, bind the rvalue instead. 2265 // FIXME: It's not responsibility of the Store to transform this lvalue 2266 // to rvalue. ExprEngine or maybe even CFG should do this before binding. 2267 if (Optional<loc::MemRegionVal> MRV = Init.getAs<loc::MemRegionVal>()) { 2268 SVal V = getBinding(B.asStore(), *MRV, R->getValueType()); 2269 return bindAggregate(B, R, V); 2270 } 2271 2272 // Handle lazy compound values. 2273 if (Init.getAs<nonloc::LazyCompoundVal>()) 2274 return bindAggregate(B, R, Init); 2275 2276 if (Init.isUnknown()) 2277 return bindAggregate(B, R, UnknownVal()); 2278 2279 // Remaining case: explicit compound values. 2280 const nonloc::CompoundVal& CV = Init.castAs<nonloc::CompoundVal>(); 2281 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); 2282 uint64_t i = 0; 2283 2284 RegionBindingsRef NewB(B); 2285 2286 for (; Size.hasValue() ? i < Size.getValue() : true ; ++i, ++VI) { 2287 // The init list might be shorter than the array length. 2288 if (VI == VE) 2289 break; 2290 2291 const NonLoc &Idx = svalBuilder.makeArrayIndex(i); 2292 const ElementRegion *ER = MRMgr.getElementRegion(ElementTy, Idx, R, Ctx); 2293 2294 if (ElementTy->isStructureOrClassType()) 2295 NewB = bindStruct(NewB, ER, *VI); 2296 else if (ElementTy->isArrayType()) 2297 NewB = bindArray(NewB, ER, *VI); 2298 else 2299 NewB = bind(NewB, loc::MemRegionVal(ER), *VI); 2300 } 2301 2302 // If the init list is shorter than the array length (or the array has 2303 // variable length), set the array default value. Values that are already set 2304 // are not overwritten. 2305 if (!Size.hasValue() || i < Size.getValue()) 2306 NewB = setImplicitDefaultValue(NewB, R, ElementTy); 2307 2308 return NewB; 2309 } 2310 2311 RegionBindingsRef RegionStoreManager::bindVector(RegionBindingsConstRef B, 2312 const TypedValueRegion* R, 2313 SVal V) { 2314 QualType T = R->getValueType(); 2315 const VectorType *VT = T->castAs<VectorType>(); // Use castAs for typedefs. 2316 2317 // Handle lazy compound values and symbolic values. 2318 if (V.getAs<nonloc::LazyCompoundVal>() || V.getAs<nonloc::SymbolVal>()) 2319 return bindAggregate(B, R, V); 2320 2321 // We may get non-CompoundVal accidentally due to imprecise cast logic or 2322 // that we are binding symbolic struct value. Kill the field values, and if 2323 // the value is symbolic go and bind it as a "default" binding. 2324 if (!V.getAs<nonloc::CompoundVal>()) { 2325 return bindAggregate(B, R, UnknownVal()); 2326 } 2327 2328 QualType ElemType = VT->getElementType(); 2329 nonloc::CompoundVal CV = V.castAs<nonloc::CompoundVal>(); 2330 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); 2331 unsigned index = 0, numElements = VT->getNumElements(); 2332 RegionBindingsRef NewB(B); 2333 2334 for ( ; index != numElements ; ++index) { 2335 if (VI == VE) 2336 break; 2337 2338 NonLoc Idx = svalBuilder.makeArrayIndex(index); 2339 const ElementRegion *ER = MRMgr.getElementRegion(ElemType, Idx, R, Ctx); 2340 2341 if (ElemType->isArrayType()) 2342 NewB = bindArray(NewB, ER, *VI); 2343 else if (ElemType->isStructureOrClassType()) 2344 NewB = bindStruct(NewB, ER, *VI); 2345 else 2346 NewB = bind(NewB, loc::MemRegionVal(ER), *VI); 2347 } 2348 return NewB; 2349 } 2350 2351 Optional<RegionBindingsRef> 2352 RegionStoreManager::tryBindSmallStruct(RegionBindingsConstRef B, 2353 const TypedValueRegion *R, 2354 const RecordDecl *RD, 2355 nonloc::LazyCompoundVal LCV) { 2356 FieldVector Fields; 2357 2358 if (const CXXRecordDecl *Class = dyn_cast<CXXRecordDecl>(RD)) 2359 if (Class->getNumBases() != 0 || Class->getNumVBases() != 0) 2360 return None; 2361 2362 for (const auto *FD : RD->fields()) { 2363 if (FD->isUnnamedBitfield()) 2364 continue; 2365 2366 // If there are too many fields, or if any of the fields are aggregates, 2367 // just use the LCV as a default binding. 2368 if (Fields.size() == SmallStructLimit) 2369 return None; 2370 2371 QualType Ty = FD->getType(); 2372 if (!(Ty->isScalarType() || Ty->isReferenceType())) 2373 return None; 2374 2375 Fields.push_back(FD); 2376 } 2377 2378 RegionBindingsRef NewB = B; 2379 2380 for (FieldVector::iterator I = Fields.begin(), E = Fields.end(); I != E; ++I){ 2381 const FieldRegion *SourceFR = MRMgr.getFieldRegion(*I, LCV.getRegion()); 2382 SVal V = getBindingForField(getRegionBindings(LCV.getStore()), SourceFR); 2383 2384 const FieldRegion *DestFR = MRMgr.getFieldRegion(*I, R); 2385 NewB = bind(NewB, loc::MemRegionVal(DestFR), V); 2386 } 2387 2388 return NewB; 2389 } 2390 2391 RegionBindingsRef RegionStoreManager::bindStruct(RegionBindingsConstRef B, 2392 const TypedValueRegion* R, 2393 SVal V) { 2394 if (!Features.supportsFields()) 2395 return B; 2396 2397 QualType T = R->getValueType(); 2398 assert(T->isStructureOrClassType()); 2399 2400 const RecordType* RT = T->castAs<RecordType>(); 2401 const RecordDecl *RD = RT->getDecl(); 2402 2403 if (!RD->isCompleteDefinition()) 2404 return B; 2405 2406 // Handle lazy compound values and symbolic values. 2407 if (Optional<nonloc::LazyCompoundVal> LCV = 2408 V.getAs<nonloc::LazyCompoundVal>()) { 2409 if (Optional<RegionBindingsRef> NewB = tryBindSmallStruct(B, R, RD, *LCV)) 2410 return *NewB; 2411 return bindAggregate(B, R, V); 2412 } 2413 if (V.getAs<nonloc::SymbolVal>()) 2414 return bindAggregate(B, R, V); 2415 2416 // We may get non-CompoundVal accidentally due to imprecise cast logic or 2417 // that we are binding symbolic struct value. Kill the field values, and if 2418 // the value is symbolic go and bind it as a "default" binding. 2419 if (V.isUnknown() || !V.getAs<nonloc::CompoundVal>()) 2420 return bindAggregate(B, R, UnknownVal()); 2421 2422 // The raw CompoundVal is essentially a symbolic InitListExpr: an (immutable) 2423 // list of other values. It appears pretty much only when there's an actual 2424 // initializer list expression in the program, and the analyzer tries to 2425 // unwrap it as soon as possible. 2426 // This code is where such unwrap happens: when the compound value is put into 2427 // the object that it was supposed to initialize (it's an *initializer* list, 2428 // after all), instead of binding the whole value to the whole object, we bind 2429 // sub-values to sub-objects. Sub-values may themselves be compound values, 2430 // and in this case the procedure becomes recursive. 2431 // FIXME: The annoying part about compound values is that they don't carry 2432 // any sort of information about which value corresponds to which sub-object. 2433 // It's simply a list of values in the middle of nowhere; we expect to match 2434 // them to sub-objects, essentially, "by index": first value binds to 2435 // the first field, second value binds to the second field, etc. 2436 // It would have been much safer to organize non-lazy compound values as 2437 // a mapping from fields/bases to values. 2438 const nonloc::CompoundVal& CV = V.castAs<nonloc::CompoundVal>(); 2439 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end(); 2440 2441 RegionBindingsRef NewB(B); 2442 2443 // In C++17 aggregates may have base classes, handle those as well. 2444 // They appear before fields in the initializer list / compound value. 2445 if (const auto *CRD = dyn_cast<CXXRecordDecl>(RD)) { 2446 // If the object was constructed with a constructor, its value is a 2447 // LazyCompoundVal. If it's a raw CompoundVal, it means that we're 2448 // performing aggregate initialization. The only exception from this 2449 // rule is sending an Objective-C++ message that returns a C++ object 2450 // to a nil receiver; in this case the semantics is to return a 2451 // zero-initialized object even if it's a C++ object that doesn't have 2452 // this sort of constructor; the CompoundVal is empty in this case. 2453 assert((CRD->isAggregate() || (Ctx.getLangOpts().ObjC && VI == VE)) && 2454 "Non-aggregates are constructed with a constructor!"); 2455 2456 for (const auto &B : CRD->bases()) { 2457 // (Multiple inheritance is fine though.) 2458 assert(!B.isVirtual() && "Aggregates cannot have virtual base classes!"); 2459 2460 if (VI == VE) 2461 break; 2462 2463 QualType BTy = B.getType(); 2464 assert(BTy->isStructureOrClassType() && "Base classes must be classes!"); 2465 2466 const CXXRecordDecl *BRD = BTy->getAsCXXRecordDecl(); 2467 assert(BRD && "Base classes must be C++ classes!"); 2468 2469 const CXXBaseObjectRegion *BR = 2470 MRMgr.getCXXBaseObjectRegion(BRD, R, /*IsVirtual=*/false); 2471 2472 NewB = bindStruct(NewB, BR, *VI); 2473 2474 ++VI; 2475 } 2476 } 2477 2478 RecordDecl::field_iterator FI, FE; 2479 2480 for (FI = RD->field_begin(), FE = RD->field_end(); FI != FE; ++FI) { 2481 2482 if (VI == VE) 2483 break; 2484 2485 // Skip any unnamed bitfields to stay in sync with the initializers. 2486 if (FI->isUnnamedBitfield()) 2487 continue; 2488 2489 QualType FTy = FI->getType(); 2490 const FieldRegion* FR = MRMgr.getFieldRegion(*FI, R); 2491 2492 if (FTy->isArrayType()) 2493 NewB = bindArray(NewB, FR, *VI); 2494 else if (FTy->isStructureOrClassType()) 2495 NewB = bindStruct(NewB, FR, *VI); 2496 else 2497 NewB = bind(NewB, loc::MemRegionVal(FR), *VI); 2498 ++VI; 2499 } 2500 2501 // There may be fewer values in the initialize list than the fields of struct. 2502 if (FI != FE) { 2503 NewB = NewB.addBinding(R, BindingKey::Default, 2504 svalBuilder.makeIntVal(0, false)); 2505 } 2506 2507 return NewB; 2508 } 2509 2510 RegionBindingsRef 2511 RegionStoreManager::bindAggregate(RegionBindingsConstRef B, 2512 const TypedRegion *R, 2513 SVal Val) { 2514 // Remove the old bindings, using 'R' as the root of all regions 2515 // we will invalidate. Then add the new binding. 2516 return removeSubRegionBindings(B, R).addBinding(R, BindingKey::Default, Val); 2517 } 2518 2519 //===----------------------------------------------------------------------===// 2520 // State pruning. 2521 //===----------------------------------------------------------------------===// 2522 2523 namespace { 2524 class RemoveDeadBindingsWorker 2525 : public ClusterAnalysis<RemoveDeadBindingsWorker> { 2526 SmallVector<const SymbolicRegion *, 12> Postponed; 2527 SymbolReaper &SymReaper; 2528 const StackFrameContext *CurrentLCtx; 2529 2530 public: 2531 RemoveDeadBindingsWorker(RegionStoreManager &rm, 2532 ProgramStateManager &stateMgr, 2533 RegionBindingsRef b, SymbolReaper &symReaper, 2534 const StackFrameContext *LCtx) 2535 : ClusterAnalysis<RemoveDeadBindingsWorker>(rm, stateMgr, b), 2536 SymReaper(symReaper), CurrentLCtx(LCtx) {} 2537 2538 // Called by ClusterAnalysis. 2539 void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C); 2540 void VisitCluster(const MemRegion *baseR, const ClusterBindings *C); 2541 using ClusterAnalysis<RemoveDeadBindingsWorker>::VisitCluster; 2542 2543 using ClusterAnalysis::AddToWorkList; 2544 2545 bool AddToWorkList(const MemRegion *R); 2546 2547 bool UpdatePostponed(); 2548 void VisitBinding(SVal V); 2549 }; 2550 } 2551 2552 bool RemoveDeadBindingsWorker::AddToWorkList(const MemRegion *R) { 2553 const MemRegion *BaseR = R->getBaseRegion(); 2554 return AddToWorkList(WorkListElement(BaseR), getCluster(BaseR)); 2555 } 2556 2557 void RemoveDeadBindingsWorker::VisitAddedToCluster(const MemRegion *baseR, 2558 const ClusterBindings &C) { 2559 2560 if (const VarRegion *VR = dyn_cast<VarRegion>(baseR)) { 2561 if (SymReaper.isLive(VR)) 2562 AddToWorkList(baseR, &C); 2563 2564 return; 2565 } 2566 2567 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) { 2568 if (SymReaper.isLive(SR->getSymbol())) 2569 AddToWorkList(SR, &C); 2570 else 2571 Postponed.push_back(SR); 2572 2573 return; 2574 } 2575 2576 if (isa<NonStaticGlobalSpaceRegion>(baseR)) { 2577 AddToWorkList(baseR, &C); 2578 return; 2579 } 2580 2581 // CXXThisRegion in the current or parent location context is live. 2582 if (const CXXThisRegion *TR = dyn_cast<CXXThisRegion>(baseR)) { 2583 const auto *StackReg = 2584 cast<StackArgumentsSpaceRegion>(TR->getSuperRegion()); 2585 const StackFrameContext *RegCtx = StackReg->getStackFrame(); 2586 if (CurrentLCtx && 2587 (RegCtx == CurrentLCtx || RegCtx->isParentOf(CurrentLCtx))) 2588 AddToWorkList(TR, &C); 2589 } 2590 } 2591 2592 void RemoveDeadBindingsWorker::VisitCluster(const MemRegion *baseR, 2593 const ClusterBindings *C) { 2594 if (!C) 2595 return; 2596 2597 // Mark the symbol for any SymbolicRegion with live bindings as live itself. 2598 // This means we should continue to track that symbol. 2599 if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(baseR)) 2600 SymReaper.markLive(SymR->getSymbol()); 2601 2602 for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I) { 2603 // Element index of a binding key is live. 2604 SymReaper.markElementIndicesLive(I.getKey().getRegion()); 2605 2606 VisitBinding(I.getData()); 2607 } 2608 } 2609 2610 void RemoveDeadBindingsWorker::VisitBinding(SVal V) { 2611 // Is it a LazyCompoundVal? All referenced regions are live as well. 2612 if (Optional<nonloc::LazyCompoundVal> LCS = 2613 V.getAs<nonloc::LazyCompoundVal>()) { 2614 2615 const RegionStoreManager::SValListTy &Vals = RM.getInterestingValues(*LCS); 2616 2617 for (RegionStoreManager::SValListTy::const_iterator I = Vals.begin(), 2618 E = Vals.end(); 2619 I != E; ++I) 2620 VisitBinding(*I); 2621 2622 return; 2623 } 2624 2625 // If V is a region, then add it to the worklist. 2626 if (const MemRegion *R = V.getAsRegion()) { 2627 AddToWorkList(R); 2628 SymReaper.markLive(R); 2629 2630 // All regions captured by a block are also live. 2631 if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(R)) { 2632 BlockDataRegion::referenced_vars_iterator I = BR->referenced_vars_begin(), 2633 E = BR->referenced_vars_end(); 2634 for ( ; I != E; ++I) 2635 AddToWorkList(I.getCapturedRegion()); 2636 } 2637 } 2638 2639 2640 // Update the set of live symbols. 2641 for (auto SI = V.symbol_begin(), SE = V.symbol_end(); SI!=SE; ++SI) 2642 SymReaper.markLive(*SI); 2643 } 2644 2645 bool RemoveDeadBindingsWorker::UpdatePostponed() { 2646 // See if any postponed SymbolicRegions are actually live now, after 2647 // having done a scan. 2648 bool Changed = false; 2649 2650 for (auto I = Postponed.begin(), E = Postponed.end(); I != E; ++I) { 2651 if (const SymbolicRegion *SR = *I) { 2652 if (SymReaper.isLive(SR->getSymbol())) { 2653 Changed |= AddToWorkList(SR); 2654 *I = nullptr; 2655 } 2656 } 2657 } 2658 2659 return Changed; 2660 } 2661 2662 StoreRef RegionStoreManager::removeDeadBindings(Store store, 2663 const StackFrameContext *LCtx, 2664 SymbolReaper& SymReaper) { 2665 RegionBindingsRef B = getRegionBindings(store); 2666 RemoveDeadBindingsWorker W(*this, StateMgr, B, SymReaper, LCtx); 2667 W.GenerateClusters(); 2668 2669 // Enqueue the region roots onto the worklist. 2670 for (SymbolReaper::region_iterator I = SymReaper.region_begin(), 2671 E = SymReaper.region_end(); I != E; ++I) { 2672 W.AddToWorkList(*I); 2673 } 2674 2675 do W.RunWorkList(); while (W.UpdatePostponed()); 2676 2677 // We have now scanned the store, marking reachable regions and symbols 2678 // as live. We now remove all the regions that are dead from the store 2679 // as well as update DSymbols with the set symbols that are now dead. 2680 for (RegionBindingsRef::iterator I = B.begin(), E = B.end(); I != E; ++I) { 2681 const MemRegion *Base = I.getKey(); 2682 2683 // If the cluster has been visited, we know the region has been marked. 2684 // Otherwise, remove the dead entry. 2685 if (!W.isVisited(Base)) 2686 B = B.remove(Base); 2687 } 2688 2689 return StoreRef(B.asStore(), *this); 2690 } 2691 2692 //===----------------------------------------------------------------------===// 2693 // Utility methods. 2694 //===----------------------------------------------------------------------===// 2695 2696 void RegionStoreManager::printJson(raw_ostream &Out, Store S, const char *NL, 2697 unsigned int Space, bool IsDot) const { 2698 RegionBindingsRef Bindings = getRegionBindings(S); 2699 2700 Indent(Out, Space, IsDot) << "\"store\": "; 2701 2702 if (Bindings.isEmpty()) { 2703 Out << "null," << NL; 2704 return; 2705 } 2706 2707 Out << "{ \"pointer\": \"" << Bindings.asStore() << "\", \"items\": [" << NL; 2708 Bindings.printJson(Out, NL, Space + 1, IsDot); 2709 Indent(Out, Space, IsDot) << "]}," << NL; 2710 } 2711