1 //== Store.cpp - Interface for maps from Locations to Values ----*- C++ -*--==// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file defined the types Store and StoreManager. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h" 15 #include "clang/AST/CXXInheritance.h" 16 #include "clang/AST/CharUnits.h" 17 #include "clang/AST/DeclObjC.h" 18 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" 19 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 20 21 using namespace clang; 22 using namespace ento; 23 24 StoreManager::StoreManager(ProgramStateManager &stateMgr) 25 : svalBuilder(stateMgr.getSValBuilder()), StateMgr(stateMgr), 26 MRMgr(svalBuilder.getRegionManager()), Ctx(stateMgr.getContext()) {} 27 28 StoreRef StoreManager::enterStackFrame(Store OldStore, 29 const CallEvent &Call, 30 const StackFrameContext *LCtx) { 31 StoreRef Store = StoreRef(OldStore, *this); 32 33 SmallVector<CallEvent::FrameBindingTy, 16> InitialBindings; 34 Call.getInitialStackFrameContents(LCtx, InitialBindings); 35 36 for (CallEvent::BindingsTy::iterator I = InitialBindings.begin(), 37 E = InitialBindings.end(); 38 I != E; ++I) { 39 Store = Bind(Store.getStore(), I->first, I->second); 40 } 41 42 return Store; 43 } 44 45 const MemRegion *StoreManager::MakeElementRegion(const MemRegion *Base, 46 QualType EleTy, uint64_t index) { 47 NonLoc idx = svalBuilder.makeArrayIndex(index); 48 return MRMgr.getElementRegion(EleTy, idx, Base, svalBuilder.getContext()); 49 } 50 51 // FIXME: Merge with the implementation of the same method in MemRegion.cpp 52 static bool IsCompleteType(ASTContext &Ctx, QualType Ty) { 53 if (const RecordType *RT = Ty->getAs<RecordType>()) { 54 const RecordDecl *D = RT->getDecl(); 55 if (!D->getDefinition()) 56 return false; 57 } 58 59 return true; 60 } 61 62 StoreRef StoreManager::BindDefault(Store store, const MemRegion *R, SVal V) { 63 return StoreRef(store, *this); 64 } 65 66 const ElementRegion *StoreManager::GetElementZeroRegion(const MemRegion *R, 67 QualType T) { 68 NonLoc idx = svalBuilder.makeZeroArrayIndex(); 69 assert(!T.isNull()); 70 return MRMgr.getElementRegion(T, idx, R, Ctx); 71 } 72 73 const MemRegion *StoreManager::castRegion(const MemRegion *R, QualType CastToTy) { 74 75 ASTContext &Ctx = StateMgr.getContext(); 76 77 // Handle casts to Objective-C objects. 78 if (CastToTy->isObjCObjectPointerType()) 79 return R->StripCasts(); 80 81 if (CastToTy->isBlockPointerType()) { 82 // FIXME: We may need different solutions, depending on the symbol 83 // involved. Blocks can be casted to/from 'id', as they can be treated 84 // as Objective-C objects. This could possibly be handled by enhancing 85 // our reasoning of downcasts of symbolic objects. 86 if (isa<CodeTextRegion>(R) || isa<SymbolicRegion>(R)) 87 return R; 88 89 // We don't know what to make of it. Return a NULL region, which 90 // will be interpretted as UnknownVal. 91 return NULL; 92 } 93 94 // Now assume we are casting from pointer to pointer. Other cases should 95 // already be handled. 96 QualType PointeeTy = CastToTy->getPointeeType(); 97 QualType CanonPointeeTy = Ctx.getCanonicalType(PointeeTy); 98 99 // Handle casts to void*. We just pass the region through. 100 if (CanonPointeeTy.getLocalUnqualifiedType() == Ctx.VoidTy) 101 return R; 102 103 // Handle casts from compatible types. 104 if (R->isBoundable()) 105 if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) { 106 QualType ObjTy = Ctx.getCanonicalType(TR->getValueType()); 107 if (CanonPointeeTy == ObjTy) 108 return R; 109 } 110 111 // Process region cast according to the kind of the region being cast. 112 switch (R->getKind()) { 113 case MemRegion::CXXThisRegionKind: 114 case MemRegion::GenericMemSpaceRegionKind: 115 case MemRegion::StackLocalsSpaceRegionKind: 116 case MemRegion::StackArgumentsSpaceRegionKind: 117 case MemRegion::HeapSpaceRegionKind: 118 case MemRegion::UnknownSpaceRegionKind: 119 case MemRegion::StaticGlobalSpaceRegionKind: 120 case MemRegion::GlobalInternalSpaceRegionKind: 121 case MemRegion::GlobalSystemSpaceRegionKind: 122 case MemRegion::GlobalImmutableSpaceRegionKind: { 123 llvm_unreachable("Invalid region cast"); 124 } 125 126 case MemRegion::FunctionTextRegionKind: 127 case MemRegion::BlockTextRegionKind: 128 case MemRegion::BlockDataRegionKind: 129 case MemRegion::StringRegionKind: 130 // FIXME: Need to handle arbitrary downcasts. 131 case MemRegion::SymbolicRegionKind: 132 case MemRegion::AllocaRegionKind: 133 case MemRegion::CompoundLiteralRegionKind: 134 case MemRegion::FieldRegionKind: 135 case MemRegion::ObjCIvarRegionKind: 136 case MemRegion::ObjCStringRegionKind: 137 case MemRegion::VarRegionKind: 138 case MemRegion::CXXTempObjectRegionKind: 139 case MemRegion::CXXBaseObjectRegionKind: 140 return MakeElementRegion(R, PointeeTy); 141 142 case MemRegion::ElementRegionKind: { 143 // If we are casting from an ElementRegion to another type, the 144 // algorithm is as follows: 145 // 146 // (1) Compute the "raw offset" of the ElementRegion from the 147 // base region. This is done by calling 'getAsRawOffset()'. 148 // 149 // (2a) If we get a 'RegionRawOffset' after calling 150 // 'getAsRawOffset()', determine if the absolute offset 151 // can be exactly divided into chunks of the size of the 152 // casted-pointee type. If so, create a new ElementRegion with 153 // the pointee-cast type as the new ElementType and the index 154 // being the offset divded by the chunk size. If not, create 155 // a new ElementRegion at offset 0 off the raw offset region. 156 // 157 // (2b) If we don't a get a 'RegionRawOffset' after calling 158 // 'getAsRawOffset()', it means that we are at offset 0. 159 // 160 // FIXME: Handle symbolic raw offsets. 161 162 const ElementRegion *elementR = cast<ElementRegion>(R); 163 const RegionRawOffset &rawOff = elementR->getAsArrayOffset(); 164 const MemRegion *baseR = rawOff.getRegion(); 165 166 // If we cannot compute a raw offset, throw up our hands and return 167 // a NULL MemRegion*. 168 if (!baseR) 169 return NULL; 170 171 CharUnits off = rawOff.getOffset(); 172 173 if (off.isZero()) { 174 // Edge case: we are at 0 bytes off the beginning of baseR. We 175 // check to see if type we are casting to is the same as the base 176 // region. If so, just return the base region. 177 if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(baseR)) { 178 QualType ObjTy = Ctx.getCanonicalType(TR->getValueType()); 179 QualType CanonPointeeTy = Ctx.getCanonicalType(PointeeTy); 180 if (CanonPointeeTy == ObjTy) 181 return baseR; 182 } 183 184 // Otherwise, create a new ElementRegion at offset 0. 185 return MakeElementRegion(baseR, PointeeTy); 186 } 187 188 // We have a non-zero offset from the base region. We want to determine 189 // if the offset can be evenly divided by sizeof(PointeeTy). If so, 190 // we create an ElementRegion whose index is that value. Otherwise, we 191 // create two ElementRegions, one that reflects a raw offset and the other 192 // that reflects the cast. 193 194 // Compute the index for the new ElementRegion. 195 int64_t newIndex = 0; 196 const MemRegion *newSuperR = 0; 197 198 // We can only compute sizeof(PointeeTy) if it is a complete type. 199 if (IsCompleteType(Ctx, PointeeTy)) { 200 // Compute the size in **bytes**. 201 CharUnits pointeeTySize = Ctx.getTypeSizeInChars(PointeeTy); 202 if (!pointeeTySize.isZero()) { 203 // Is the offset a multiple of the size? If so, we can layer the 204 // ElementRegion (with elementType == PointeeTy) directly on top of 205 // the base region. 206 if (off % pointeeTySize == 0) { 207 newIndex = off / pointeeTySize; 208 newSuperR = baseR; 209 } 210 } 211 } 212 213 if (!newSuperR) { 214 // Create an intermediate ElementRegion to represent the raw byte. 215 // This will be the super region of the final ElementRegion. 216 newSuperR = MakeElementRegion(baseR, Ctx.CharTy, off.getQuantity()); 217 } 218 219 return MakeElementRegion(newSuperR, PointeeTy, newIndex); 220 } 221 } 222 223 llvm_unreachable("unreachable"); 224 } 225 226 static bool regionMatchesCXXRecordType(SVal V, QualType Ty) { 227 const MemRegion *MR = V.getAsRegion(); 228 if (!MR) 229 return true; 230 231 const TypedValueRegion *TVR = dyn_cast<TypedValueRegion>(MR); 232 if (!TVR) 233 return true; 234 235 const CXXRecordDecl *RD = TVR->getValueType()->getAsCXXRecordDecl(); 236 if (!RD) 237 return true; 238 239 const CXXRecordDecl *Expected = Ty->getPointeeCXXRecordDecl(); 240 if (!Expected) 241 Expected = Ty->getAsCXXRecordDecl(); 242 243 return Expected->getCanonicalDecl() == RD->getCanonicalDecl(); 244 } 245 246 SVal StoreManager::evalDerivedToBase(SVal Derived, const CastExpr *Cast) { 247 // Sanity check to avoid doing the wrong thing in the face of 248 // reinterpret_cast. 249 if (!regionMatchesCXXRecordType(Derived, Cast->getSubExpr()->getType())) 250 return UnknownVal(); 251 252 // Walk through the cast path to create nested CXXBaseRegions. 253 SVal Result = Derived; 254 for (CastExpr::path_const_iterator I = Cast->path_begin(), 255 E = Cast->path_end(); 256 I != E; ++I) { 257 Result = evalDerivedToBase(Result, (*I)->getType(), (*I)->isVirtual()); 258 } 259 return Result; 260 } 261 262 SVal StoreManager::evalDerivedToBase(SVal Derived, const CXXBasePath &Path) { 263 // Walk through the path to create nested CXXBaseRegions. 264 SVal Result = Derived; 265 for (CXXBasePath::const_iterator I = Path.begin(), E = Path.end(); 266 I != E; ++I) { 267 Result = evalDerivedToBase(Result, I->Base->getType(), 268 I->Base->isVirtual()); 269 } 270 return Result; 271 } 272 273 SVal StoreManager::evalDerivedToBase(SVal Derived, QualType BaseType, 274 bool IsVirtual) { 275 Optional<loc::MemRegionVal> DerivedRegVal = 276 Derived.getAs<loc::MemRegionVal>(); 277 if (!DerivedRegVal) 278 return Derived; 279 280 const CXXRecordDecl *BaseDecl = BaseType->getPointeeCXXRecordDecl(); 281 if (!BaseDecl) 282 BaseDecl = BaseType->getAsCXXRecordDecl(); 283 assert(BaseDecl && "not a C++ object?"); 284 285 const MemRegion *BaseReg = 286 MRMgr.getCXXBaseObjectRegion(BaseDecl, DerivedRegVal->getRegion(), 287 IsVirtual); 288 289 return loc::MemRegionVal(BaseReg); 290 } 291 292 SVal StoreManager::evalDynamicCast(SVal Base, QualType DerivedType, 293 bool &Failed) { 294 Failed = false; 295 296 Optional<loc::MemRegionVal> BaseRegVal = Base.getAs<loc::MemRegionVal>(); 297 if (!BaseRegVal) 298 return UnknownVal(); 299 const MemRegion *BaseRegion = BaseRegVal->stripCasts(/*StripBases=*/false); 300 301 // Assume the derived class is a pointer or a reference to a CXX record. 302 DerivedType = DerivedType->getPointeeType(); 303 assert(!DerivedType.isNull()); 304 const CXXRecordDecl *DerivedDecl = DerivedType->getAsCXXRecordDecl(); 305 if (!DerivedDecl && !DerivedType->isVoidType()) 306 return UnknownVal(); 307 308 // Drill down the CXXBaseObject chains, which represent upcasts (casts from 309 // derived to base). 310 const MemRegion *SR = BaseRegion; 311 while (const TypedRegion *TSR = dyn_cast_or_null<TypedRegion>(SR)) { 312 QualType BaseType = TSR->getLocationType()->getPointeeType(); 313 assert(!BaseType.isNull()); 314 const CXXRecordDecl *SRDecl = BaseType->getAsCXXRecordDecl(); 315 if (!SRDecl) 316 return UnknownVal(); 317 318 // If found the derived class, the cast succeeds. 319 if (SRDecl == DerivedDecl) 320 return loc::MemRegionVal(TSR); 321 322 if (!DerivedType->isVoidType()) { 323 // Static upcasts are marked as DerivedToBase casts by Sema, so this will 324 // only happen when multiple or virtual inheritance is involved. 325 CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/true, 326 /*DetectVirtual=*/false); 327 if (SRDecl->isDerivedFrom(DerivedDecl, Paths)) 328 return evalDerivedToBase(loc::MemRegionVal(TSR), Paths.front()); 329 } 330 331 if (const CXXBaseObjectRegion *R = dyn_cast<CXXBaseObjectRegion>(TSR)) 332 // Drill down the chain to get the derived classes. 333 SR = R->getSuperRegion(); 334 else { 335 // We reached the bottom of the hierarchy. 336 337 // If this is a cast to void*, return the region. 338 if (DerivedType->isVoidType()) 339 return loc::MemRegionVal(TSR); 340 341 // We did not find the derived class. We we must be casting the base to 342 // derived, so the cast should fail. 343 Failed = true; 344 return UnknownVal(); 345 } 346 } 347 348 return UnknownVal(); 349 } 350 351 352 /// CastRetrievedVal - Used by subclasses of StoreManager to implement 353 /// implicit casts that arise from loads from regions that are reinterpreted 354 /// as another region. 355 SVal StoreManager::CastRetrievedVal(SVal V, const TypedValueRegion *R, 356 QualType castTy, bool performTestOnly) { 357 358 if (castTy.isNull() || V.isUnknownOrUndef()) 359 return V; 360 361 ASTContext &Ctx = svalBuilder.getContext(); 362 363 if (performTestOnly) { 364 // Automatically translate references to pointers. 365 QualType T = R->getValueType(); 366 if (const ReferenceType *RT = T->getAs<ReferenceType>()) 367 T = Ctx.getPointerType(RT->getPointeeType()); 368 369 assert(svalBuilder.getContext().hasSameUnqualifiedType(castTy, T)); 370 return V; 371 } 372 373 return svalBuilder.dispatchCast(V, castTy); 374 } 375 376 SVal StoreManager::getLValueFieldOrIvar(const Decl *D, SVal Base) { 377 if (Base.isUnknownOrUndef()) 378 return Base; 379 380 Loc BaseL = Base.castAs<Loc>(); 381 const MemRegion* BaseR = 0; 382 383 switch (BaseL.getSubKind()) { 384 case loc::MemRegionKind: 385 BaseR = BaseL.castAs<loc::MemRegionVal>().getRegion(); 386 break; 387 388 case loc::GotoLabelKind: 389 // These are anormal cases. Flag an undefined value. 390 return UndefinedVal(); 391 392 case loc::ConcreteIntKind: 393 // While these seem funny, this can happen through casts. 394 // FIXME: What we should return is the field offset. For example, 395 // add the field offset to the integer value. That way funny things 396 // like this work properly: &(((struct foo *) 0xa)->f) 397 return Base; 398 399 default: 400 llvm_unreachable("Unhandled Base."); 401 } 402 403 // NOTE: We must have this check first because ObjCIvarDecl is a subclass 404 // of FieldDecl. 405 if (const ObjCIvarDecl *ID = dyn_cast<ObjCIvarDecl>(D)) 406 return loc::MemRegionVal(MRMgr.getObjCIvarRegion(ID, BaseR)); 407 408 return loc::MemRegionVal(MRMgr.getFieldRegion(cast<FieldDecl>(D), BaseR)); 409 } 410 411 SVal StoreManager::getLValueIvar(const ObjCIvarDecl *decl, SVal base) { 412 return getLValueFieldOrIvar(decl, base); 413 } 414 415 SVal StoreManager::getLValueElement(QualType elementType, NonLoc Offset, 416 SVal Base) { 417 418 // If the base is an unknown or undefined value, just return it back. 419 // FIXME: For absolute pointer addresses, we just return that value back as 420 // well, although in reality we should return the offset added to that 421 // value. 422 if (Base.isUnknownOrUndef() || Base.getAs<loc::ConcreteInt>()) 423 return Base; 424 425 const MemRegion* BaseRegion = Base.castAs<loc::MemRegionVal>().getRegion(); 426 427 // Pointer of any type can be cast and used as array base. 428 const ElementRegion *ElemR = dyn_cast<ElementRegion>(BaseRegion); 429 430 // Convert the offset to the appropriate size and signedness. 431 Offset = svalBuilder.convertToArrayIndex(Offset).castAs<NonLoc>(); 432 433 if (!ElemR) { 434 // 435 // If the base region is not an ElementRegion, create one. 436 // This can happen in the following example: 437 // 438 // char *p = __builtin_alloc(10); 439 // p[1] = 8; 440 // 441 // Observe that 'p' binds to an AllocaRegion. 442 // 443 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, Offset, 444 BaseRegion, Ctx)); 445 } 446 447 SVal BaseIdx = ElemR->getIndex(); 448 449 if (!BaseIdx.getAs<nonloc::ConcreteInt>()) 450 return UnknownVal(); 451 452 const llvm::APSInt &BaseIdxI = 453 BaseIdx.castAs<nonloc::ConcreteInt>().getValue(); 454 455 // Only allow non-integer offsets if the base region has no offset itself. 456 // FIXME: This is a somewhat arbitrary restriction. We should be using 457 // SValBuilder here to add the two offsets without checking their types. 458 if (!Offset.getAs<nonloc::ConcreteInt>()) { 459 if (isa<ElementRegion>(BaseRegion->StripCasts())) 460 return UnknownVal(); 461 462 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, Offset, 463 ElemR->getSuperRegion(), 464 Ctx)); 465 } 466 467 const llvm::APSInt& OffI = Offset.castAs<nonloc::ConcreteInt>().getValue(); 468 assert(BaseIdxI.isSigned()); 469 470 // Compute the new index. 471 nonloc::ConcreteInt NewIdx(svalBuilder.getBasicValueFactory().getValue(BaseIdxI + 472 OffI)); 473 474 // Construct the new ElementRegion. 475 const MemRegion *ArrayR = ElemR->getSuperRegion(); 476 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, NewIdx, ArrayR, 477 Ctx)); 478 } 479 480 StoreManager::BindingsHandler::~BindingsHandler() {} 481 482 bool StoreManager::FindUniqueBinding::HandleBinding(StoreManager& SMgr, 483 Store store, 484 const MemRegion* R, 485 SVal val) { 486 SymbolRef SymV = val.getAsLocSymbol(); 487 if (!SymV || SymV != Sym) 488 return true; 489 490 if (Binding) { 491 First = false; 492 return false; 493 } 494 else 495 Binding = R; 496 497 return true; 498 } 499