Store.cpp revision ada0d224fcff5ff07c9dd846379592f92ccf5ee7
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 21using namespace clang; 22using namespace ento; 23 24StoreManager::StoreManager(ProgramStateManager &stateMgr) 25 : svalBuilder(stateMgr.getSValBuilder()), StateMgr(stateMgr), 26 MRMgr(svalBuilder.getRegionManager()), Ctx(stateMgr.getContext()) {} 27 28StoreRef 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 45const 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 52static 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 62StoreRef StoreManager::BindDefault(Store store, const MemRegion *R, SVal V) { 63 return StoreRef(store, *this); 64} 65 66const 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 73const 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 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()); 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 } 269 return Result; 270} 271 272SVal StoreManager::evalDerivedToBase(SVal Derived, QualType BaseType) { 273 loc::MemRegionVal *DerivedRegVal = dyn_cast<loc::MemRegionVal>(&Derived); 274 if (!DerivedRegVal) 275 return Derived; 276 277 const CXXRecordDecl *BaseDecl = BaseType->getPointeeCXXRecordDecl(); 278 if (!BaseDecl) 279 BaseDecl = BaseType->getAsCXXRecordDecl(); 280 assert(BaseDecl && "not a C++ object?"); 281 282 const MemRegion *BaseReg = 283 MRMgr.getCXXBaseObjectRegion(BaseDecl, DerivedRegVal->getRegion()); 284 285 return loc::MemRegionVal(BaseReg); 286} 287 288SVal StoreManager::evalDynamicCast(SVal Base, QualType DerivedType, 289 bool &Failed) { 290 Failed = false; 291 292 loc::MemRegionVal *BaseRegVal = dyn_cast<loc::MemRegionVal>(&Base); 293 if (!BaseRegVal) 294 return UnknownVal(); 295 const MemRegion *BaseRegion = BaseRegVal->stripCasts(/*StripBases=*/false); 296 297 // Assume the derived class is a pointer or a reference to a CXX record. 298 DerivedType = DerivedType->getPointeeType(); 299 assert(!DerivedType.isNull()); 300 const CXXRecordDecl *DerivedDecl = DerivedType->getAsCXXRecordDecl(); 301 if (!DerivedDecl && !DerivedType->isVoidType()) 302 return UnknownVal(); 303 304 // Drill down the CXXBaseObject chains, which represent upcasts (casts from 305 // derived to base). 306 const MemRegion *SR = BaseRegion; 307 while (const TypedRegion *TSR = dyn_cast_or_null<TypedRegion>(SR)) { 308 QualType BaseType = TSR->getLocationType()->getPointeeType(); 309 assert(!BaseType.isNull()); 310 const CXXRecordDecl *SRDecl = BaseType->getAsCXXRecordDecl(); 311 if (!SRDecl) 312 return UnknownVal(); 313 314 // If found the derived class, the cast succeeds. 315 if (SRDecl == DerivedDecl) 316 return loc::MemRegionVal(TSR); 317 318 if (!DerivedType->isVoidType()) { 319 // Static upcasts are marked as DerivedToBase casts by Sema, so this will 320 // only happen when multiple or virtual inheritance is involved. 321 CXXBasePaths Paths(/*FindAmbiguities=*/false, /*RecordPaths=*/true, 322 /*DetectVirtual=*/false); 323 if (SRDecl->isDerivedFrom(DerivedDecl, Paths)) 324 return evalDerivedToBase(loc::MemRegionVal(TSR), Paths.front()); 325 } 326 327 if (const CXXBaseObjectRegion *R = dyn_cast<CXXBaseObjectRegion>(TSR)) 328 // Drill down the chain to get the derived classes. 329 SR = R->getSuperRegion(); 330 else { 331 // We reached the bottom of the hierarchy. 332 333 // If this is a cast to void*, return the region. 334 if (DerivedType->isVoidType()) 335 return loc::MemRegionVal(TSR); 336 337 // We did not find the derived class. We we must be casting the base to 338 // derived, so the cast should fail. 339 Failed = true; 340 return UnknownVal(); 341 } 342 } 343 344 return UnknownVal(); 345} 346 347 348/// CastRetrievedVal - Used by subclasses of StoreManager to implement 349/// implicit casts that arise from loads from regions that are reinterpreted 350/// as another region. 351SVal StoreManager::CastRetrievedVal(SVal V, const TypedValueRegion *R, 352 QualType castTy, bool performTestOnly) { 353 354 if (castTy.isNull() || V.isUnknownOrUndef()) 355 return V; 356 357 ASTContext &Ctx = svalBuilder.getContext(); 358 359 if (performTestOnly) { 360 // Automatically translate references to pointers. 361 QualType T = R->getValueType(); 362 if (const ReferenceType *RT = T->getAs<ReferenceType>()) 363 T = Ctx.getPointerType(RT->getPointeeType()); 364 365 assert(svalBuilder.getContext().hasSameUnqualifiedType(castTy, T)); 366 return V; 367 } 368 369 return svalBuilder.dispatchCast(V, castTy); 370} 371 372SVal StoreManager::getLValueFieldOrIvar(const Decl *D, SVal Base) { 373 if (Base.isUnknownOrUndef()) 374 return Base; 375 376 Loc BaseL = cast<Loc>(Base); 377 const MemRegion* BaseR = 0; 378 379 switch (BaseL.getSubKind()) { 380 case loc::MemRegionKind: 381 BaseR = cast<loc::MemRegionVal>(BaseL).getRegion(); 382 break; 383 384 case loc::GotoLabelKind: 385 // These are anormal cases. Flag an undefined value. 386 return UndefinedVal(); 387 388 case loc::ConcreteIntKind: 389 // While these seem funny, this can happen through casts. 390 // FIXME: What we should return is the field offset. For example, 391 // add the field offset to the integer value. That way funny things 392 // like this work properly: &(((struct foo *) 0xa)->f) 393 return Base; 394 395 default: 396 llvm_unreachable("Unhandled Base."); 397 } 398 399 // NOTE: We must have this check first because ObjCIvarDecl is a subclass 400 // of FieldDecl. 401 if (const ObjCIvarDecl *ID = dyn_cast<ObjCIvarDecl>(D)) 402 return loc::MemRegionVal(MRMgr.getObjCIvarRegion(ID, BaseR)); 403 404 return loc::MemRegionVal(MRMgr.getFieldRegion(cast<FieldDecl>(D), BaseR)); 405} 406 407SVal StoreManager::getLValueIvar(const ObjCIvarDecl *decl, SVal base) { 408 return getLValueFieldOrIvar(decl, base); 409} 410 411SVal StoreManager::getLValueElement(QualType elementType, NonLoc Offset, 412 SVal Base) { 413 414 // If the base is an unknown or undefined value, just return it back. 415 // FIXME: For absolute pointer addresses, we just return that value back as 416 // well, although in reality we should return the offset added to that 417 // value. 418 if (Base.isUnknownOrUndef() || isa<loc::ConcreteInt>(Base)) 419 return Base; 420 421 const MemRegion* BaseRegion = cast<loc::MemRegionVal>(Base).getRegion(); 422 423 // Pointer of any type can be cast and used as array base. 424 const ElementRegion *ElemR = dyn_cast<ElementRegion>(BaseRegion); 425 426 // Convert the offset to the appropriate size and signedness. 427 Offset = cast<NonLoc>(svalBuilder.convertToArrayIndex(Offset)); 428 429 if (!ElemR) { 430 // 431 // If the base region is not an ElementRegion, create one. 432 // This can happen in the following example: 433 // 434 // char *p = __builtin_alloc(10); 435 // p[1] = 8; 436 // 437 // Observe that 'p' binds to an AllocaRegion. 438 // 439 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, Offset, 440 BaseRegion, Ctx)); 441 } 442 443 SVal BaseIdx = ElemR->getIndex(); 444 445 if (!isa<nonloc::ConcreteInt>(BaseIdx)) 446 return UnknownVal(); 447 448 const llvm::APSInt& BaseIdxI = cast<nonloc::ConcreteInt>(BaseIdx).getValue(); 449 450 // Only allow non-integer offsets if the base region has no offset itself. 451 // FIXME: This is a somewhat arbitrary restriction. We should be using 452 // SValBuilder here to add the two offsets without checking their types. 453 if (!isa<nonloc::ConcreteInt>(Offset)) { 454 if (isa<ElementRegion>(BaseRegion->StripCasts())) 455 return UnknownVal(); 456 457 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, Offset, 458 ElemR->getSuperRegion(), 459 Ctx)); 460 } 461 462 const llvm::APSInt& OffI = cast<nonloc::ConcreteInt>(Offset).getValue(); 463 assert(BaseIdxI.isSigned()); 464 465 // Compute the new index. 466 nonloc::ConcreteInt NewIdx(svalBuilder.getBasicValueFactory().getValue(BaseIdxI + 467 OffI)); 468 469 // Construct the new ElementRegion. 470 const MemRegion *ArrayR = ElemR->getSuperRegion(); 471 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, NewIdx, ArrayR, 472 Ctx)); 473} 474 475StoreManager::BindingsHandler::~BindingsHandler() {} 476 477bool StoreManager::FindUniqueBinding::HandleBinding(StoreManager& SMgr, 478 Store store, 479 const MemRegion* R, 480 SVal val) { 481 SymbolRef SymV = val.getAsLocSymbol(); 482 if (!SymV || SymV != Sym) 483 return true; 484 485 if (Binding) { 486 First = false; 487 return false; 488 } 489 else 490 Binding = R; 491 492 return true; 493} 494