1 //===- Store.cpp - Interface for maps from Locations to Values ------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defined the types Store and StoreManager. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h" 14 #include "clang/AST/ASTContext.h" 15 #include "clang/AST/CXXInheritance.h" 16 #include "clang/AST/CharUnits.h" 17 #include "clang/AST/Decl.h" 18 #include "clang/AST/DeclCXX.h" 19 #include "clang/AST/DeclObjC.h" 20 #include "clang/AST/Expr.h" 21 #include "clang/AST/Type.h" 22 #include "clang/Basic/LLVM.h" 23 #include "clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h" 24 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" 25 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" 26 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 27 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h" 28 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" 29 #include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h" 30 #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h" 31 #include "llvm/ADT/APSInt.h" 32 #include "llvm/ADT/Optional.h" 33 #include "llvm/ADT/SmallVector.h" 34 #include "llvm/Support/Casting.h" 35 #include "llvm/Support/ErrorHandling.h" 36 #include <cassert> 37 #include <cstdint> 38 39 using namespace clang; 40 using namespace ento; 41 42 StoreManager::StoreManager(ProgramStateManager &stateMgr) 43 : svalBuilder(stateMgr.getSValBuilder()), StateMgr(stateMgr), 44 MRMgr(svalBuilder.getRegionManager()), Ctx(stateMgr.getContext()) {} 45 46 StoreRef StoreManager::enterStackFrame(Store OldStore, 47 const CallEvent &Call, 48 const StackFrameContext *LCtx) { 49 StoreRef Store = StoreRef(OldStore, *this); 50 51 SmallVector<CallEvent::FrameBindingTy, 16> InitialBindings; 52 Call.getInitialStackFrameContents(LCtx, InitialBindings); 53 54 for (const auto &I : InitialBindings) 55 Store = Bind(Store.getStore(), I.first.castAs<Loc>(), I.second); 56 57 return Store; 58 } 59 60 const ElementRegion *StoreManager::MakeElementRegion(const SubRegion *Base, 61 QualType EleTy, 62 uint64_t index) { 63 NonLoc idx = svalBuilder.makeArrayIndex(index); 64 return MRMgr.getElementRegion(EleTy, idx, Base, svalBuilder.getContext()); 65 } 66 67 const ElementRegion *StoreManager::GetElementZeroRegion(const SubRegion *R, 68 QualType T) { 69 NonLoc idx = svalBuilder.makeZeroArrayIndex(); 70 assert(!T.isNull()); 71 return MRMgr.getElementRegion(T, idx, R, Ctx); 72 } 73 74 Optional<const MemRegion *> StoreManager::castRegion(const MemRegion *R, 75 QualType CastToTy) { 76 ASTContext &Ctx = StateMgr.getContext(); 77 78 // Handle casts to Objective-C objects. 79 if (CastToTy->isObjCObjectPointerType()) 80 return R->StripCasts(); 81 82 if (CastToTy->isBlockPointerType()) { 83 // FIXME: We may need different solutions, depending on the symbol 84 // involved. Blocks can be casted to/from 'id', as they can be treated 85 // as Objective-C objects. This could possibly be handled by enhancing 86 // our reasoning of downcasts of symbolic objects. 87 if (isa<CodeTextRegion, SymbolicRegion>(R)) 88 return R; 89 90 // We don't know what to make of it. Return a NULL region, which 91 // will be interpreted as UnknownVal. 92 return None; 93 } 94 95 // Now assume we are casting from pointer to pointer. Other cases should 96 // already be handled. 97 QualType PointeeTy = CastToTy->getPointeeType(); 98 QualType CanonPointeeTy = Ctx.getCanonicalType(PointeeTy); 99 CanonPointeeTy = CanonPointeeTy.getLocalUnqualifiedType(); 100 101 // Handle casts to void*. We just pass the region through. 102 if (CanonPointeeTy == Ctx.VoidTy) 103 return R; 104 105 const auto IsSameRegionType = [&Ctx](const MemRegion *R, QualType OtherTy) { 106 if (const auto *TR = dyn_cast<TypedValueRegion>(R)) { 107 QualType ObjTy = Ctx.getCanonicalType(TR->getValueType()); 108 if (OtherTy == ObjTy.getLocalUnqualifiedType()) 109 return true; 110 } 111 return false; 112 }; 113 114 // Handle casts from compatible types. 115 if (R->isBoundable() && IsSameRegionType(R, CanonPointeeTy)) 116 return R; 117 118 // Process region cast according to the kind of the region being cast. 119 switch (R->getKind()) { 120 case MemRegion::CXXThisRegionKind: 121 case MemRegion::CodeSpaceRegionKind: 122 case MemRegion::StackLocalsSpaceRegionKind: 123 case MemRegion::StackArgumentsSpaceRegionKind: 124 case MemRegion::HeapSpaceRegionKind: 125 case MemRegion::UnknownSpaceRegionKind: 126 case MemRegion::StaticGlobalSpaceRegionKind: 127 case MemRegion::GlobalInternalSpaceRegionKind: 128 case MemRegion::GlobalSystemSpaceRegionKind: 129 case MemRegion::GlobalImmutableSpaceRegionKind: { 130 llvm_unreachable("Invalid region cast"); 131 } 132 133 case MemRegion::FunctionCodeRegionKind: 134 case MemRegion::BlockCodeRegionKind: 135 case MemRegion::BlockDataRegionKind: 136 case MemRegion::StringRegionKind: 137 // FIXME: Need to handle arbitrary downcasts. 138 case MemRegion::SymbolicRegionKind: 139 case MemRegion::AllocaRegionKind: 140 case MemRegion::CompoundLiteralRegionKind: 141 case MemRegion::FieldRegionKind: 142 case MemRegion::ObjCIvarRegionKind: 143 case MemRegion::ObjCStringRegionKind: 144 case MemRegion::NonParamVarRegionKind: 145 case MemRegion::ParamVarRegionKind: 146 case MemRegion::CXXTempObjectRegionKind: 147 case MemRegion::CXXBaseObjectRegionKind: 148 case MemRegion::CXXDerivedObjectRegionKind: 149 return MakeElementRegion(cast<SubRegion>(R), PointeeTy); 150 151 case MemRegion::ElementRegionKind: { 152 // If we are casting from an ElementRegion to another type, the 153 // algorithm is as follows: 154 // 155 // (1) Compute the "raw offset" of the ElementRegion from the 156 // base region. This is done by calling 'getAsRawOffset()'. 157 // 158 // (2a) If we get a 'RegionRawOffset' after calling 159 // 'getAsRawOffset()', determine if the absolute offset 160 // can be exactly divided into chunks of the size of the 161 // casted-pointee type. If so, create a new ElementRegion with 162 // the pointee-cast type as the new ElementType and the index 163 // being the offset divded by the chunk size. If not, create 164 // a new ElementRegion at offset 0 off the raw offset region. 165 // 166 // (2b) If we don't a get a 'RegionRawOffset' after calling 167 // 'getAsRawOffset()', it means that we are at offset 0. 168 // 169 // FIXME: Handle symbolic raw offsets. 170 171 const ElementRegion *elementR = cast<ElementRegion>(R); 172 const RegionRawOffset &rawOff = elementR->getAsArrayOffset(); 173 const MemRegion *baseR = rawOff.getRegion(); 174 175 // If we cannot compute a raw offset, throw up our hands and return 176 // a NULL MemRegion*. 177 if (!baseR) 178 return None; 179 180 CharUnits off = rawOff.getOffset(); 181 182 if (off.isZero()) { 183 // Edge case: we are at 0 bytes off the beginning of baseR. We check to 184 // see if the type we are casting to is the same as the type of the base 185 // region. If so, just return the base region. 186 if (IsSameRegionType(baseR, CanonPointeeTy)) 187 return baseR; 188 // Otherwise, create a new ElementRegion at offset 0. 189 return MakeElementRegion(cast<SubRegion>(baseR), PointeeTy); 190 } 191 192 // We have a non-zero offset from the base region. We want to determine 193 // if the offset can be evenly divided by sizeof(PointeeTy). If so, 194 // we create an ElementRegion whose index is that value. Otherwise, we 195 // create two ElementRegions, one that reflects a raw offset and the other 196 // that reflects the cast. 197 198 // Compute the index for the new ElementRegion. 199 int64_t newIndex = 0; 200 const MemRegion *newSuperR = nullptr; 201 202 // We can only compute sizeof(PointeeTy) if it is a complete type. 203 if (!PointeeTy->isIncompleteType()) { 204 // Compute the size in **bytes**. 205 CharUnits pointeeTySize = Ctx.getTypeSizeInChars(PointeeTy); 206 if (!pointeeTySize.isZero()) { 207 // Is the offset a multiple of the size? If so, we can layer the 208 // ElementRegion (with elementType == PointeeTy) directly on top of 209 // the base region. 210 if (off % pointeeTySize == 0) { 211 newIndex = off / pointeeTySize; 212 newSuperR = baseR; 213 } 214 } 215 } 216 217 if (!newSuperR) { 218 // Create an intermediate ElementRegion to represent the raw byte. 219 // This will be the super region of the final ElementRegion. 220 newSuperR = MakeElementRegion(cast<SubRegion>(baseR), Ctx.CharTy, 221 off.getQuantity()); 222 } 223 224 return MakeElementRegion(cast<SubRegion>(newSuperR), PointeeTy, newIndex); 225 } 226 } 227 228 llvm_unreachable("unreachable"); 229 } 230 231 static bool regionMatchesCXXRecordType(SVal V, QualType Ty) { 232 const MemRegion *MR = V.getAsRegion(); 233 if (!MR) 234 return true; 235 236 const auto *TVR = dyn_cast<TypedValueRegion>(MR); 237 if (!TVR) 238 return true; 239 240 const CXXRecordDecl *RD = TVR->getValueType()->getAsCXXRecordDecl(); 241 if (!RD) 242 return true; 243 244 const CXXRecordDecl *Expected = Ty->getPointeeCXXRecordDecl(); 245 if (!Expected) 246 Expected = Ty->getAsCXXRecordDecl(); 247 248 return Expected->getCanonicalDecl() == RD->getCanonicalDecl(); 249 } 250 251 SVal StoreManager::evalDerivedToBase(SVal Derived, const CastExpr *Cast) { 252 // Early return to avoid doing the wrong thing in the face of 253 // reinterpret_cast. 254 if (!regionMatchesCXXRecordType(Derived, Cast->getSubExpr()->getType())) 255 return UnknownVal(); 256 257 // Walk through the cast path to create nested CXXBaseRegions. 258 SVal Result = Derived; 259 for (CastExpr::path_const_iterator I = Cast->path_begin(), 260 E = Cast->path_end(); 261 I != E; ++I) { 262 Result = evalDerivedToBase(Result, (*I)->getType(), (*I)->isVirtual()); 263 } 264 return Result; 265 } 266 267 SVal StoreManager::evalDerivedToBase(SVal Derived, const CXXBasePath &Path) { 268 // Walk through the path to create nested CXXBaseRegions. 269 SVal Result = Derived; 270 for (const auto &I : Path) 271 Result = evalDerivedToBase(Result, I.Base->getType(), 272 I.Base->isVirtual()); 273 return Result; 274 } 275 276 SVal StoreManager::evalDerivedToBase(SVal Derived, QualType BaseType, 277 bool IsVirtual) { 278 const MemRegion *DerivedReg = Derived.getAsRegion(); 279 if (!DerivedReg) 280 return Derived; 281 282 const CXXRecordDecl *BaseDecl = BaseType->getPointeeCXXRecordDecl(); 283 if (!BaseDecl) 284 BaseDecl = BaseType->getAsCXXRecordDecl(); 285 assert(BaseDecl && "not a C++ object?"); 286 287 if (const auto *AlreadyDerivedReg = 288 dyn_cast<CXXDerivedObjectRegion>(DerivedReg)) { 289 if (const auto *SR = 290 dyn_cast<SymbolicRegion>(AlreadyDerivedReg->getSuperRegion())) 291 if (SR->getSymbol()->getType()->getPointeeCXXRecordDecl() == BaseDecl) 292 return loc::MemRegionVal(SR); 293 294 DerivedReg = AlreadyDerivedReg->getSuperRegion(); 295 } 296 297 const MemRegion *BaseReg = MRMgr.getCXXBaseObjectRegion( 298 BaseDecl, cast<SubRegion>(DerivedReg), IsVirtual); 299 300 return loc::MemRegionVal(BaseReg); 301 } 302 303 /// Returns the static type of the given region, if it represents a C++ class 304 /// object. 305 /// 306 /// This handles both fully-typed regions, where the dynamic type is known, and 307 /// symbolic regions, where the dynamic type is merely bounded (and even then, 308 /// only ostensibly!), but does not take advantage of any dynamic type info. 309 static const CXXRecordDecl *getCXXRecordType(const MemRegion *MR) { 310 if (const auto *TVR = dyn_cast<TypedValueRegion>(MR)) 311 return TVR->getValueType()->getAsCXXRecordDecl(); 312 if (const auto *SR = dyn_cast<SymbolicRegion>(MR)) 313 return SR->getSymbol()->getType()->getPointeeCXXRecordDecl(); 314 return nullptr; 315 } 316 317 Optional<SVal> StoreManager::evalBaseToDerived(SVal Base, QualType TargetType) { 318 const MemRegion *MR = Base.getAsRegion(); 319 if (!MR) 320 return UnknownVal(); 321 322 // Assume the derived class is a pointer or a reference to a CXX record. 323 TargetType = TargetType->getPointeeType(); 324 assert(!TargetType.isNull()); 325 const CXXRecordDecl *TargetClass = TargetType->getAsCXXRecordDecl(); 326 if (!TargetClass && !TargetType->isVoidType()) 327 return UnknownVal(); 328 329 // Drill down the CXXBaseObject chains, which represent upcasts (casts from 330 // derived to base). 331 while (const CXXRecordDecl *MRClass = getCXXRecordType(MR)) { 332 // If found the derived class, the cast succeeds. 333 if (MRClass == TargetClass) 334 return loc::MemRegionVal(MR); 335 336 // We skip over incomplete types. They must be the result of an earlier 337 // reinterpret_cast, as one can only dynamic_cast between types in the same 338 // class hierarchy. 339 if (!TargetType->isVoidType() && MRClass->hasDefinition()) { 340 // Static upcasts are marked as DerivedToBase casts by Sema, so this will 341 // only happen when multiple or virtual inheritance is involved. 342 CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/true, 343 /*DetectVirtual=*/false); 344 if (MRClass->isDerivedFrom(TargetClass, Paths)) 345 return evalDerivedToBase(loc::MemRegionVal(MR), Paths.front()); 346 } 347 348 if (const auto *BaseR = dyn_cast<CXXBaseObjectRegion>(MR)) { 349 // Drill down the chain to get the derived classes. 350 MR = BaseR->getSuperRegion(); 351 continue; 352 } 353 354 // If this is a cast to void*, return the region. 355 if (TargetType->isVoidType()) 356 return loc::MemRegionVal(MR); 357 358 // Strange use of reinterpret_cast can give us paths we don't reason 359 // about well, by putting in ElementRegions where we'd expect 360 // CXXBaseObjectRegions. If it's a valid reinterpret_cast (i.e. if the 361 // derived class has a zero offset from the base class), then it's safe 362 // to strip the cast; if it's invalid, -Wreinterpret-base-class should 363 // catch it. In the interest of performance, the analyzer will silently 364 // do the wrong thing in the invalid case (because offsets for subregions 365 // will be wrong). 366 const MemRegion *Uncasted = MR->StripCasts(/*IncludeBaseCasts=*/false); 367 if (Uncasted == MR) { 368 // We reached the bottom of the hierarchy and did not find the derived 369 // class. We must be casting the base to derived, so the cast should 370 // fail. 371 break; 372 } 373 374 MR = Uncasted; 375 } 376 377 // If we're casting a symbolic base pointer to a derived class, use 378 // CXXDerivedObjectRegion to represent the cast. If it's a pointer to an 379 // unrelated type, it must be a weird reinterpret_cast and we have to 380 // be fine with ElementRegion. TODO: Should we instead make 381 // Derived{TargetClass, Element{SourceClass, SR}}? 382 if (const auto *SR = dyn_cast<SymbolicRegion>(MR)) { 383 QualType T = SR->getSymbol()->getType(); 384 const CXXRecordDecl *SourceClass = T->getPointeeCXXRecordDecl(); 385 if (TargetClass && SourceClass && TargetClass->isDerivedFrom(SourceClass)) 386 return loc::MemRegionVal( 387 MRMgr.getCXXDerivedObjectRegion(TargetClass, SR)); 388 return loc::MemRegionVal(GetElementZeroRegion(SR, TargetType)); 389 } 390 391 // We failed if the region we ended up with has perfect type info. 392 if (isa<TypedValueRegion>(MR)) 393 return None; 394 395 return UnknownVal(); 396 } 397 398 SVal StoreManager::getLValueFieldOrIvar(const Decl *D, SVal Base) { 399 if (Base.isUnknownOrUndef()) 400 return Base; 401 402 Loc BaseL = Base.castAs<Loc>(); 403 const SubRegion* BaseR = nullptr; 404 405 switch (BaseL.getSubKind()) { 406 case loc::MemRegionValKind: 407 BaseR = cast<SubRegion>(BaseL.castAs<loc::MemRegionVal>().getRegion()); 408 break; 409 410 case loc::GotoLabelKind: 411 // These are anormal cases. Flag an undefined value. 412 return UndefinedVal(); 413 414 case loc::ConcreteIntKind: 415 // While these seem funny, this can happen through casts. 416 // FIXME: What we should return is the field offset, not base. For example, 417 // add the field offset to the integer value. That way things 418 // like this work properly: &(((struct foo *) 0xa)->f) 419 // However, that's not easy to fix without reducing our abilities 420 // to catch null pointer dereference. Eg., ((struct foo *)0x0)->f = 7 421 // is a null dereference even though we're dereferencing offset of f 422 // rather than null. Coming up with an approach that computes offsets 423 // over null pointers properly while still being able to catch null 424 // dereferences might be worth it. 425 return Base; 426 427 default: 428 llvm_unreachable("Unhandled Base."); 429 } 430 431 // NOTE: We must have this check first because ObjCIvarDecl is a subclass 432 // of FieldDecl. 433 if (const auto *ID = dyn_cast<ObjCIvarDecl>(D)) 434 return loc::MemRegionVal(MRMgr.getObjCIvarRegion(ID, BaseR)); 435 436 return loc::MemRegionVal(MRMgr.getFieldRegion(cast<FieldDecl>(D), BaseR)); 437 } 438 439 SVal StoreManager::getLValueIvar(const ObjCIvarDecl *decl, SVal base) { 440 return getLValueFieldOrIvar(decl, base); 441 } 442 443 SVal StoreManager::getLValueElement(QualType elementType, NonLoc Offset, 444 SVal Base) { 445 446 // Special case, if index is 0, return the same type as if 447 // this was not an array dereference. 448 if (Offset.isZeroConstant()) { 449 QualType BT = Base.getType(this->Ctx); 450 if (!BT.isNull() && !elementType.isNull()) { 451 QualType PointeeTy = BT->getPointeeType(); 452 if (!PointeeTy.isNull() && 453 PointeeTy.getCanonicalType() == elementType.getCanonicalType()) 454 return Base; 455 } 456 } 457 458 // If the base is an unknown or undefined value, just return it back. 459 // FIXME: For absolute pointer addresses, we just return that value back as 460 // well, although in reality we should return the offset added to that 461 // value. See also the similar FIXME in getLValueFieldOrIvar(). 462 if (Base.isUnknownOrUndef() || isa<loc::ConcreteInt>(Base)) 463 return Base; 464 465 if (isa<loc::GotoLabel>(Base)) 466 return UnknownVal(); 467 468 const SubRegion *BaseRegion = 469 Base.castAs<loc::MemRegionVal>().getRegionAs<SubRegion>(); 470 471 // Pointer of any type can be cast and used as array base. 472 const auto *ElemR = dyn_cast<ElementRegion>(BaseRegion); 473 474 // Convert the offset to the appropriate size and signedness. 475 Offset = svalBuilder.convertToArrayIndex(Offset).castAs<NonLoc>(); 476 477 if (!ElemR) { 478 // If the base region is not an ElementRegion, create one. 479 // This can happen in the following example: 480 // 481 // char *p = __builtin_alloc(10); 482 // p[1] = 8; 483 // 484 // Observe that 'p' binds to an AllocaRegion. 485 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, Offset, 486 BaseRegion, Ctx)); 487 } 488 489 SVal BaseIdx = ElemR->getIndex(); 490 491 if (!isa<nonloc::ConcreteInt>(BaseIdx)) 492 return UnknownVal(); 493 494 const llvm::APSInt &BaseIdxI = 495 BaseIdx.castAs<nonloc::ConcreteInt>().getValue(); 496 497 // Only allow non-integer offsets if the base region has no offset itself. 498 // FIXME: This is a somewhat arbitrary restriction. We should be using 499 // SValBuilder here to add the two offsets without checking their types. 500 if (!isa<nonloc::ConcreteInt>(Offset)) { 501 if (isa<ElementRegion>(BaseRegion->StripCasts())) 502 return UnknownVal(); 503 504 return loc::MemRegionVal(MRMgr.getElementRegion( 505 elementType, Offset, cast<SubRegion>(ElemR->getSuperRegion()), Ctx)); 506 } 507 508 const llvm::APSInt& OffI = Offset.castAs<nonloc::ConcreteInt>().getValue(); 509 assert(BaseIdxI.isSigned()); 510 511 // Compute the new index. 512 nonloc::ConcreteInt NewIdx(svalBuilder.getBasicValueFactory().getValue(BaseIdxI + 513 OffI)); 514 515 // Construct the new ElementRegion. 516 const SubRegion *ArrayR = cast<SubRegion>(ElemR->getSuperRegion()); 517 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, NewIdx, ArrayR, 518 Ctx)); 519 } 520 521 StoreManager::BindingsHandler::~BindingsHandler() = default; 522 523 bool StoreManager::FindUniqueBinding::HandleBinding(StoreManager& SMgr, 524 Store store, 525 const MemRegion* R, 526 SVal val) { 527 SymbolRef SymV = val.getAsLocSymbol(); 528 if (!SymV || SymV != Sym) 529 return true; 530 531 if (Binding) { 532 First = false; 533 return false; 534 } 535 else 536 Binding = R; 537 538 return true; 539 } 540