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>(R) || isa<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 100 // Handle casts to void*. We just pass the region through. 101 if (CanonPointeeTy.getLocalUnqualifiedType() == Ctx.VoidTy) 102 return R; 103 104 // Handle casts from compatible types. 105 if (R->isBoundable()) 106 if (const auto *TR = dyn_cast<TypedValueRegion>(R)) { 107 QualType ObjTy = Ctx.getCanonicalType(TR->getValueType()); 108 if (CanonPointeeTy == ObjTy) 109 return R; 110 } 111 112 // Process region cast according to the kind of the region being cast. 113 switch (R->getKind()) { 114 case MemRegion::CXXThisRegionKind: 115 case MemRegion::CodeSpaceRegionKind: 116 case MemRegion::StackLocalsSpaceRegionKind: 117 case MemRegion::StackArgumentsSpaceRegionKind: 118 case MemRegion::HeapSpaceRegionKind: 119 case MemRegion::UnknownSpaceRegionKind: 120 case MemRegion::StaticGlobalSpaceRegionKind: 121 case MemRegion::GlobalInternalSpaceRegionKind: 122 case MemRegion::GlobalSystemSpaceRegionKind: 123 case MemRegion::GlobalImmutableSpaceRegionKind: { 124 llvm_unreachable("Invalid region cast"); 125 } 126 127 case MemRegion::FunctionCodeRegionKind: 128 case MemRegion::BlockCodeRegionKind: 129 case MemRegion::BlockDataRegionKind: 130 case MemRegion::StringRegionKind: 131 // FIXME: Need to handle arbitrary downcasts. 132 case MemRegion::SymbolicRegionKind: 133 case MemRegion::AllocaRegionKind: 134 case MemRegion::CompoundLiteralRegionKind: 135 case MemRegion::FieldRegionKind: 136 case MemRegion::ObjCIvarRegionKind: 137 case MemRegion::ObjCStringRegionKind: 138 case MemRegion::NonParamVarRegionKind: 139 case MemRegion::ParamVarRegionKind: 140 case MemRegion::CXXTempObjectRegionKind: 141 case MemRegion::CXXBaseObjectRegionKind: 142 case MemRegion::CXXDerivedObjectRegionKind: 143 return MakeElementRegion(cast<SubRegion>(R), PointeeTy); 144 145 case MemRegion::ElementRegionKind: { 146 // If we are casting from an ElementRegion to another type, the 147 // algorithm is as follows: 148 // 149 // (1) Compute the "raw offset" of the ElementRegion from the 150 // base region. This is done by calling 'getAsRawOffset()'. 151 // 152 // (2a) If we get a 'RegionRawOffset' after calling 153 // 'getAsRawOffset()', determine if the absolute offset 154 // can be exactly divided into chunks of the size of the 155 // casted-pointee type. If so, create a new ElementRegion with 156 // the pointee-cast type as the new ElementType and the index 157 // being the offset divded by the chunk size. If not, create 158 // a new ElementRegion at offset 0 off the raw offset region. 159 // 160 // (2b) If we don't a get a 'RegionRawOffset' after calling 161 // 'getAsRawOffset()', it means that we are at offset 0. 162 // 163 // FIXME: Handle symbolic raw offsets. 164 165 const ElementRegion *elementR = cast<ElementRegion>(R); 166 const RegionRawOffset &rawOff = elementR->getAsArrayOffset(); 167 const MemRegion *baseR = rawOff.getRegion(); 168 169 // If we cannot compute a raw offset, throw up our hands and return 170 // a NULL MemRegion*. 171 if (!baseR) 172 return None; 173 174 CharUnits off = rawOff.getOffset(); 175 176 if (off.isZero()) { 177 // Edge case: we are at 0 bytes off the beginning of baseR. We 178 // check to see if type we are casting to is the same as the base 179 // region. If so, just return the base region. 180 if (const auto *TR = dyn_cast<TypedValueRegion>(baseR)) { 181 QualType ObjTy = Ctx.getCanonicalType(TR->getValueType()); 182 QualType CanonPointeeTy = Ctx.getCanonicalType(PointeeTy); 183 if (CanonPointeeTy == ObjTy) 184 return baseR; 185 } 186 187 // Otherwise, create a new ElementRegion at offset 0. 188 return MakeElementRegion(cast<SubRegion>(baseR), PointeeTy); 189 } 190 191 // We have a non-zero offset from the base region. We want to determine 192 // if the offset can be evenly divided by sizeof(PointeeTy). If so, 193 // we create an ElementRegion whose index is that value. Otherwise, we 194 // create two ElementRegions, one that reflects a raw offset and the other 195 // that reflects the cast. 196 197 // Compute the index for the new ElementRegion. 198 int64_t newIndex = 0; 199 const MemRegion *newSuperR = nullptr; 200 201 // We can only compute sizeof(PointeeTy) if it is a complete type. 202 if (!PointeeTy->isIncompleteType()) { 203 // Compute the size in **bytes**. 204 CharUnits pointeeTySize = Ctx.getTypeSizeInChars(PointeeTy); 205 if (!pointeeTySize.isZero()) { 206 // Is the offset a multiple of the size? If so, we can layer the 207 // ElementRegion (with elementType == PointeeTy) directly on top of 208 // the base region. 209 if (off % pointeeTySize == 0) { 210 newIndex = off / pointeeTySize; 211 newSuperR = baseR; 212 } 213 } 214 } 215 216 if (!newSuperR) { 217 // Create an intermediate ElementRegion to represent the raw byte. 218 // This will be the super region of the final ElementRegion. 219 newSuperR = MakeElementRegion(cast<SubRegion>(baseR), Ctx.CharTy, 220 off.getQuantity()); 221 } 222 223 return MakeElementRegion(cast<SubRegion>(newSuperR), PointeeTy, newIndex); 224 } 225 } 226 227 llvm_unreachable("unreachable"); 228 } 229 230 static bool regionMatchesCXXRecordType(SVal V, QualType Ty) { 231 const MemRegion *MR = V.getAsRegion(); 232 if (!MR) 233 return true; 234 235 const auto *TVR = dyn_cast<TypedValueRegion>(MR); 236 if (!TVR) 237 return true; 238 239 const CXXRecordDecl *RD = TVR->getValueType()->getAsCXXRecordDecl(); 240 if (!RD) 241 return true; 242 243 const CXXRecordDecl *Expected = Ty->getPointeeCXXRecordDecl(); 244 if (!Expected) 245 Expected = Ty->getAsCXXRecordDecl(); 246 247 return Expected->getCanonicalDecl() == RD->getCanonicalDecl(); 248 } 249 250 SVal StoreManager::evalDerivedToBase(SVal Derived, const CastExpr *Cast) { 251 // Sanity check to avoid doing the wrong thing in the face of 252 // reinterpret_cast. 253 if (!regionMatchesCXXRecordType(Derived, Cast->getSubExpr()->getType())) 254 return UnknownVal(); 255 256 // Walk through the cast path to create nested CXXBaseRegions. 257 SVal Result = Derived; 258 for (CastExpr::path_const_iterator I = Cast->path_begin(), 259 E = Cast->path_end(); 260 I != E; ++I) { 261 Result = evalDerivedToBase(Result, (*I)->getType(), (*I)->isVirtual()); 262 } 263 return Result; 264 } 265 266 SVal StoreManager::evalDerivedToBase(SVal Derived, const CXXBasePath &Path) { 267 // Walk through the path to create nested CXXBaseRegions. 268 SVal Result = Derived; 269 for (const auto &I : Path) 270 Result = evalDerivedToBase(Result, I.Base->getType(), 271 I.Base->isVirtual()); 272 return Result; 273 } 274 275 SVal StoreManager::evalDerivedToBase(SVal Derived, QualType BaseType, 276 bool IsVirtual) { 277 const MemRegion *DerivedReg = Derived.getAsRegion(); 278 if (!DerivedReg) 279 return Derived; 280 281 const CXXRecordDecl *BaseDecl = BaseType->getPointeeCXXRecordDecl(); 282 if (!BaseDecl) 283 BaseDecl = BaseType->getAsCXXRecordDecl(); 284 assert(BaseDecl && "not a C++ object?"); 285 286 if (const auto *AlreadyDerivedReg = 287 dyn_cast<CXXDerivedObjectRegion>(DerivedReg)) { 288 if (const auto *SR = 289 dyn_cast<SymbolicRegion>(AlreadyDerivedReg->getSuperRegion())) 290 if (SR->getSymbol()->getType()->getPointeeCXXRecordDecl() == BaseDecl) 291 return loc::MemRegionVal(SR); 292 293 DerivedReg = AlreadyDerivedReg->getSuperRegion(); 294 } 295 296 const MemRegion *BaseReg = MRMgr.getCXXBaseObjectRegion( 297 BaseDecl, cast<SubRegion>(DerivedReg), IsVirtual); 298 299 return loc::MemRegionVal(BaseReg); 300 } 301 302 /// Returns the static type of the given region, if it represents a C++ class 303 /// object. 304 /// 305 /// This handles both fully-typed regions, where the dynamic type is known, and 306 /// symbolic regions, where the dynamic type is merely bounded (and even then, 307 /// only ostensibly!), but does not take advantage of any dynamic type info. 308 static const CXXRecordDecl *getCXXRecordType(const MemRegion *MR) { 309 if (const auto *TVR = dyn_cast<TypedValueRegion>(MR)) 310 return TVR->getValueType()->getAsCXXRecordDecl(); 311 if (const auto *SR = dyn_cast<SymbolicRegion>(MR)) 312 return SR->getSymbol()->getType()->getPointeeCXXRecordDecl(); 313 return nullptr; 314 } 315 316 SVal StoreManager::attemptDownCast(SVal Base, QualType TargetType, 317 bool &Failed) { 318 Failed = false; 319 320 const MemRegion *MR = Base.getAsRegion(); 321 if (!MR) 322 return UnknownVal(); 323 324 // Assume the derived class is a pointer or a reference to a CXX record. 325 TargetType = TargetType->getPointeeType(); 326 assert(!TargetType.isNull()); 327 const CXXRecordDecl *TargetClass = TargetType->getAsCXXRecordDecl(); 328 if (!TargetClass && !TargetType->isVoidType()) 329 return UnknownVal(); 330 331 // Drill down the CXXBaseObject chains, which represent upcasts (casts from 332 // derived to base). 333 while (const CXXRecordDecl *MRClass = getCXXRecordType(MR)) { 334 // If found the derived class, the cast succeeds. 335 if (MRClass == TargetClass) 336 return loc::MemRegionVal(MR); 337 338 // We skip over incomplete types. They must be the result of an earlier 339 // reinterpret_cast, as one can only dynamic_cast between types in the same 340 // class hierarchy. 341 if (!TargetType->isVoidType() && MRClass->hasDefinition()) { 342 // Static upcasts are marked as DerivedToBase casts by Sema, so this will 343 // only happen when multiple or virtual inheritance is involved. 344 CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/true, 345 /*DetectVirtual=*/false); 346 if (MRClass->isDerivedFrom(TargetClass, Paths)) 347 return evalDerivedToBase(loc::MemRegionVal(MR), Paths.front()); 348 } 349 350 if (const auto *BaseR = dyn_cast<CXXBaseObjectRegion>(MR)) { 351 // Drill down the chain to get the derived classes. 352 MR = BaseR->getSuperRegion(); 353 continue; 354 } 355 356 // If this is a cast to void*, return the region. 357 if (TargetType->isVoidType()) 358 return loc::MemRegionVal(MR); 359 360 // Strange use of reinterpret_cast can give us paths we don't reason 361 // about well, by putting in ElementRegions where we'd expect 362 // CXXBaseObjectRegions. If it's a valid reinterpret_cast (i.e. if the 363 // derived class has a zero offset from the base class), then it's safe 364 // to strip the cast; if it's invalid, -Wreinterpret-base-class should 365 // catch it. In the interest of performance, the analyzer will silently 366 // do the wrong thing in the invalid case (because offsets for subregions 367 // will be wrong). 368 const MemRegion *Uncasted = MR->StripCasts(/*IncludeBaseCasts=*/false); 369 if (Uncasted == MR) { 370 // We reached the bottom of the hierarchy and did not find the derived 371 // class. We must be casting the base to derived, so the cast should 372 // fail. 373 break; 374 } 375 376 MR = Uncasted; 377 } 378 379 // If we're casting a symbolic base pointer to a derived class, use 380 // CXXDerivedObjectRegion to represent the cast. If it's a pointer to an 381 // unrelated type, it must be a weird reinterpret_cast and we have to 382 // be fine with ElementRegion. TODO: Should we instead make 383 // Derived{TargetClass, Element{SourceClass, SR}}? 384 if (const auto *SR = dyn_cast<SymbolicRegion>(MR)) { 385 QualType T = SR->getSymbol()->getType(); 386 const CXXRecordDecl *SourceClass = T->getPointeeCXXRecordDecl(); 387 if (TargetClass && SourceClass && TargetClass->isDerivedFrom(SourceClass)) 388 return loc::MemRegionVal( 389 MRMgr.getCXXDerivedObjectRegion(TargetClass, SR)); 390 return loc::MemRegionVal(GetElementZeroRegion(SR, TargetType)); 391 } 392 393 // We failed if the region we ended up with has perfect type info. 394 Failed = isa<TypedValueRegion>(MR); 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 // If the base is an unknown or undefined value, just return it back. 446 // FIXME: For absolute pointer addresses, we just return that value back as 447 // well, although in reality we should return the offset added to that 448 // value. See also the similar FIXME in getLValueFieldOrIvar(). 449 if (Base.isUnknownOrUndef() || Base.getAs<loc::ConcreteInt>()) 450 return Base; 451 452 if (Base.getAs<loc::GotoLabel>()) 453 return UnknownVal(); 454 455 const SubRegion *BaseRegion = 456 Base.castAs<loc::MemRegionVal>().getRegionAs<SubRegion>(); 457 458 // Pointer of any type can be cast and used as array base. 459 const auto *ElemR = dyn_cast<ElementRegion>(BaseRegion); 460 461 // Convert the offset to the appropriate size and signedness. 462 Offset = svalBuilder.convertToArrayIndex(Offset).castAs<NonLoc>(); 463 464 if (!ElemR) { 465 // If the base region is not an ElementRegion, create one. 466 // This can happen in the following example: 467 // 468 // char *p = __builtin_alloc(10); 469 // p[1] = 8; 470 // 471 // Observe that 'p' binds to an AllocaRegion. 472 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, Offset, 473 BaseRegion, Ctx)); 474 } 475 476 SVal BaseIdx = ElemR->getIndex(); 477 478 if (!BaseIdx.getAs<nonloc::ConcreteInt>()) 479 return UnknownVal(); 480 481 const llvm::APSInt &BaseIdxI = 482 BaseIdx.castAs<nonloc::ConcreteInt>().getValue(); 483 484 // Only allow non-integer offsets if the base region has no offset itself. 485 // FIXME: This is a somewhat arbitrary restriction. We should be using 486 // SValBuilder here to add the two offsets without checking their types. 487 if (!Offset.getAs<nonloc::ConcreteInt>()) { 488 if (isa<ElementRegion>(BaseRegion->StripCasts())) 489 return UnknownVal(); 490 491 return loc::MemRegionVal(MRMgr.getElementRegion( 492 elementType, Offset, cast<SubRegion>(ElemR->getSuperRegion()), Ctx)); 493 } 494 495 const llvm::APSInt& OffI = Offset.castAs<nonloc::ConcreteInt>().getValue(); 496 assert(BaseIdxI.isSigned()); 497 498 // Compute the new index. 499 nonloc::ConcreteInt NewIdx(svalBuilder.getBasicValueFactory().getValue(BaseIdxI + 500 OffI)); 501 502 // Construct the new ElementRegion. 503 const SubRegion *ArrayR = cast<SubRegion>(ElemR->getSuperRegion()); 504 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, NewIdx, ArrayR, 505 Ctx)); 506 } 507 508 StoreManager::BindingsHandler::~BindingsHandler() = default; 509 510 bool StoreManager::FindUniqueBinding::HandleBinding(StoreManager& SMgr, 511 Store store, 512 const MemRegion* R, 513 SVal val) { 514 SymbolRef SymV = val.getAsLocSymbol(); 515 if (!SymV || SymV != Sym) 516 return true; 517 518 if (Binding) { 519 First = false; 520 return false; 521 } 522 else 523 Binding = R; 524 525 return true; 526 } 527