Store.cpp revision 249423
183098Smp//== Store.cpp - Interface for maps from Locations to Values ----*- C++ -*--==// 283098Smp// 383098Smp// The LLVM Compiler Infrastructure 483098Smp// 583098Smp// This file is distributed under the University of Illinois Open Source 683098Smp// License. See LICENSE.TXT for details. 783098Smp// 883098Smp//===----------------------------------------------------------------------===// 983098Smp// 1083098Smp// This file defined the types Store and StoreManager. 1183098Smp// 1283098Smp//===----------------------------------------------------------------------===// 1383098Smp 1483098Smp#include "clang/StaticAnalyzer/Core/PathSensitive/Store.h" 1583098Smp#include "clang/AST/CXXInheritance.h" 1683098Smp#include "clang/AST/CharUnits.h" 1783098Smp#include "clang/AST/DeclObjC.h" 1883098Smp#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" 1983098Smp#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 2083098Smp 2183098Smpusing namespace clang; 2283098Smpusing namespace ento; 2383098Smp 2483098SmpStoreManager::StoreManager(ProgramStateManager &stateMgr) 2583098Smp : svalBuilder(stateMgr.getSValBuilder()), StateMgr(stateMgr), 2683098Smp MRMgr(svalBuilder.getRegionManager()), Ctx(stateMgr.getContext()) {} 2783098Smp 2883098SmpStoreRef StoreManager::enterStackFrame(Store OldStore, 2983098Smp const CallEvent &Call, 3083098Smp const StackFrameContext *LCtx) { 3183098Smp StoreRef Store = StoreRef(OldStore, *this); 3283098Smp 3383098Smp SmallVector<CallEvent::FrameBindingTy, 16> InitialBindings; 3483098Smp Call.getInitialStackFrameContents(LCtx, InitialBindings); 3583098Smp 3683098Smp for (CallEvent::BindingsTy::iterator I = InitialBindings.begin(), 3783098Smp E = InitialBindings.end(); 3883098Smp I != E; ++I) { 3983098Smp Store = Bind(Store.getStore(), I->first, I->second); 4083098Smp } 4183098Smp 4283098Smp return Store; 4383098Smp} 4483098Smp 4583098Smpconst MemRegion *StoreManager::MakeElementRegion(const MemRegion *Base, 4683098Smp QualType EleTy, uint64_t index) { 4783098Smp NonLoc idx = svalBuilder.makeArrayIndex(index); 4883098Smp return MRMgr.getElementRegion(EleTy, idx, Base, svalBuilder.getContext()); 4983098Smp} 5083098Smp 5183098Smp// FIXME: Merge with the implementation of the same method in MemRegion.cpp 5283098Smpstatic bool IsCompleteType(ASTContext &Ctx, QualType Ty) { 5383098Smp if (const RecordType *RT = Ty->getAs<RecordType>()) { 5483098Smp const RecordDecl *D = RT->getDecl(); 5583098Smp if (!D->getDefinition()) 5683098Smp return false; 5783098Smp } 5883098Smp 5983098Smp return true; 6083098Smp} 6183098Smp 6283098SmpStoreRef StoreManager::BindDefault(Store store, const MemRegion *R, SVal V) { 6383098Smp return StoreRef(store, *this); 6483098Smp} 6583098Smp 6683098Smpconst ElementRegion *StoreManager::GetElementZeroRegion(const MemRegion *R, 6783098Smp QualType T) { 6883098Smp NonLoc idx = svalBuilder.makeZeroArrayIndex(); 6983098Smp assert(!T.isNull()); 7083098Smp return MRMgr.getElementRegion(T, idx, R, Ctx); 7183098Smp} 7283098Smp 7383098Smpconst MemRegion *StoreManager::castRegion(const MemRegion *R, QualType CastToTy) { 7483098Smp 7583098Smp ASTContext &Ctx = StateMgr.getContext(); 7683098Smp 7783098Smp // Handle casts to Objective-C objects. 7883098Smp if (CastToTy->isObjCObjectPointerType()) 7983098Smp return R->StripCasts(); 8083098Smp 8183098Smp if (CastToTy->isBlockPointerType()) { 8283098Smp // FIXME: We may need different solutions, depending on the symbol 8383098Smp // involved. Blocks can be casted to/from 'id', as they can be treated 8483098Smp // as Objective-C objects. This could possibly be handled by enhancing 8583098Smp // our reasoning of downcasts of symbolic objects. 8683098Smp if (isa<CodeTextRegion>(R) || isa<SymbolicRegion>(R)) 8783098Smp return R; 8883098Smp 8983098Smp // We don't know what to make of it. Return a NULL region, which 9083098Smp // will be interpretted as UnknownVal. 9183098Smp return NULL; 9283098Smp } 9383098Smp 9483098Smp // Now assume we are casting from pointer to pointer. Other cases should 9583098Smp // already be handled. 9683098Smp QualType PointeeTy = CastToTy->getPointeeType(); 9783098Smp QualType CanonPointeeTy = Ctx.getCanonicalType(PointeeTy); 9883098Smp 9983098Smp // Handle casts to void*. We just pass the region through. 10083098Smp if (CanonPointeeTy.getLocalUnqualifiedType() == Ctx.VoidTy) 10183098Smp return R; 10283098Smp 10383098Smp // Handle casts from compatible types. 10483098Smp if (R->isBoundable()) 10583098Smp if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) { 10683098Smp QualType ObjTy = Ctx.getCanonicalType(TR->getValueType()); 10783098Smp if (CanonPointeeTy == ObjTy) 10883098Smp return R; 10983098Smp } 11083098Smp 11183098Smp // Process region cast according to the kind of the region being cast. 11283098Smp switch (R->getKind()) { 11383098Smp case MemRegion::CXXThisRegionKind: 11483098Smp case MemRegion::GenericMemSpaceRegionKind: 11583098Smp case MemRegion::StackLocalsSpaceRegionKind: 11683098Smp case MemRegion::StackArgumentsSpaceRegionKind: 11783098Smp case MemRegion::HeapSpaceRegionKind: 11883098Smp case MemRegion::UnknownSpaceRegionKind: 11983098Smp case MemRegion::StaticGlobalSpaceRegionKind: 12083098Smp case MemRegion::GlobalInternalSpaceRegionKind: 12183098Smp case MemRegion::GlobalSystemSpaceRegionKind: 12283098Smp case MemRegion::GlobalImmutableSpaceRegionKind: { 12383098Smp llvm_unreachable("Invalid region cast"); 12483098Smp } 12583098Smp 12683098Smp case MemRegion::FunctionTextRegionKind: 12783098Smp case MemRegion::BlockTextRegionKind: 12883098Smp case MemRegion::BlockDataRegionKind: 12983098Smp case MemRegion::StringRegionKind: 13083098Smp // FIXME: Need to handle arbitrary downcasts. 13183098Smp case MemRegion::SymbolicRegionKind: 13283098Smp case MemRegion::AllocaRegionKind: 13383098Smp case MemRegion::CompoundLiteralRegionKind: 13483098Smp case MemRegion::FieldRegionKind: 13583098Smp case MemRegion::ObjCIvarRegionKind: 13683098Smp case MemRegion::ObjCStringRegionKind: 13783098Smp case MemRegion::VarRegionKind: 13883098Smp case MemRegion::CXXTempObjectRegionKind: 13983098Smp case MemRegion::CXXBaseObjectRegionKind: 14083098Smp 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 226static 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 246SVal 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 262SVal 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 273SVal 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 292SVal 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. 355SVal 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 376SVal 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 411SVal StoreManager::getLValueIvar(const ObjCIvarDecl *decl, SVal base) { 412 return getLValueFieldOrIvar(decl, base); 413} 414 415SVal 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 480StoreManager::BindingsHandler::~BindingsHandler() {} 481 482bool 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