Store.cpp revision ef15831780b705475e7b237ac16418e9b53cb7a6
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/StaticAnalyzer/Core/PathSensitive/CallEvent.h" 16#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 17#include "clang/AST/CharUnits.h" 18#include "clang/AST/DeclObjC.h" 19 20using namespace clang; 21using namespace ento; 22 23StoreManager::StoreManager(ProgramStateManager &stateMgr) 24 : svalBuilder(stateMgr.getSValBuilder()), StateMgr(stateMgr), 25 MRMgr(svalBuilder.getRegionManager()), Ctx(stateMgr.getContext()) {} 26 27StoreRef StoreManager::enterStackFrame(Store OldStore, 28 const CallEvent &Call, 29 const StackFrameContext *LCtx) { 30 StoreRef Store = StoreRef(OldStore, *this); 31 32 SmallVector<CallEvent::FrameBindingTy, 16> InitialBindings; 33 Call.getInitialStackFrameContents(LCtx, InitialBindings); 34 35 for (CallEvent::BindingsTy::iterator I = InitialBindings.begin(), 36 E = InitialBindings.end(); 37 I != E; ++I) { 38 Store = Bind(Store.getStore(), I->first, I->second); 39 } 40 41 return Store; 42} 43 44const MemRegion *StoreManager::MakeElementRegion(const MemRegion *Base, 45 QualType EleTy, uint64_t index) { 46 NonLoc idx = svalBuilder.makeArrayIndex(index); 47 return MRMgr.getElementRegion(EleTy, idx, Base, svalBuilder.getContext()); 48} 49 50// FIXME: Merge with the implementation of the same method in MemRegion.cpp 51static bool IsCompleteType(ASTContext &Ctx, QualType Ty) { 52 if (const RecordType *RT = Ty->getAs<RecordType>()) { 53 const RecordDecl *D = RT->getDecl(); 54 if (!D->getDefinition()) 55 return false; 56 } 57 58 return true; 59} 60 61StoreRef StoreManager::BindDefault(Store store, const MemRegion *R, SVal V) { 62 return StoreRef(store, *this); 63} 64 65const ElementRegion *StoreManager::GetElementZeroRegion(const MemRegion *R, 66 QualType T) { 67 NonLoc idx = svalBuilder.makeZeroArrayIndex(); 68 assert(!T.isNull()); 69 return MRMgr.getElementRegion(T, idx, R, Ctx); 70} 71 72const MemRegion *StoreManager::castRegion(const MemRegion *R, QualType CastToTy) { 73 74 ASTContext &Ctx = StateMgr.getContext(); 75 76 // Handle casts to Objective-C objects. 77 if (CastToTy->isObjCObjectPointerType()) 78 return R->StripCasts(); 79 80 if (CastToTy->isBlockPointerType()) { 81 // FIXME: We may need different solutions, depending on the symbol 82 // involved. Blocks can be casted to/from 'id', as they can be treated 83 // as Objective-C objects. This could possibly be handled by enhancing 84 // our reasoning of downcasts of symbolic objects. 85 if (isa<CodeTextRegion>(R) || isa<SymbolicRegion>(R)) 86 return R; 87 88 // We don't know what to make of it. Return a NULL region, which 89 // will be interpretted as UnknownVal. 90 return NULL; 91 } 92 93 // Now assume we are casting from pointer to pointer. Other cases should 94 // already be handled. 95 QualType PointeeTy = CastToTy->getPointeeType(); 96 QualType CanonPointeeTy = Ctx.getCanonicalType(PointeeTy); 97 98 // Handle casts to void*. We just pass the region through. 99 if (CanonPointeeTy.getLocalUnqualifiedType() == Ctx.VoidTy) 100 return R; 101 102 // Handle casts from compatible types. 103 if (R->isBoundable()) 104 if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) { 105 QualType ObjTy = Ctx.getCanonicalType(TR->getValueType()); 106 if (CanonPointeeTy == ObjTy) 107 return R; 108 } 109 110 // Process region cast according to the kind of the region being cast. 111 switch (R->getKind()) { 112 case MemRegion::CXXThisRegionKind: 113 case MemRegion::GenericMemSpaceRegionKind: 114 case MemRegion::StackLocalsSpaceRegionKind: 115 case MemRegion::StackArgumentsSpaceRegionKind: 116 case MemRegion::HeapSpaceRegionKind: 117 case MemRegion::UnknownSpaceRegionKind: 118 case MemRegion::StaticGlobalSpaceRegionKind: 119 case MemRegion::GlobalInternalSpaceRegionKind: 120 case MemRegion::GlobalSystemSpaceRegionKind: 121 case MemRegion::GlobalImmutableSpaceRegionKind: { 122 llvm_unreachable("Invalid region cast"); 123 } 124 125 case MemRegion::FunctionTextRegionKind: 126 case MemRegion::BlockTextRegionKind: 127 case MemRegion::BlockDataRegionKind: 128 case MemRegion::StringRegionKind: 129 // FIXME: Need to handle arbitrary downcasts. 130 case MemRegion::SymbolicRegionKind: 131 case MemRegion::AllocaRegionKind: 132 case MemRegion::CompoundLiteralRegionKind: 133 case MemRegion::FieldRegionKind: 134 case MemRegion::ObjCIvarRegionKind: 135 case MemRegion::ObjCStringRegionKind: 136 case MemRegion::VarRegionKind: 137 case MemRegion::CXXTempObjectRegionKind: 138 case MemRegion::CXXBaseObjectRegionKind: 139 return MakeElementRegion(R, PointeeTy); 140 141 case MemRegion::ElementRegionKind: { 142 // If we are casting from an ElementRegion to another type, the 143 // algorithm is as follows: 144 // 145 // (1) Compute the "raw offset" of the ElementRegion from the 146 // base region. This is done by calling 'getAsRawOffset()'. 147 // 148 // (2a) If we get a 'RegionRawOffset' after calling 149 // 'getAsRawOffset()', determine if the absolute offset 150 // can be exactly divided into chunks of the size of the 151 // casted-pointee type. If so, create a new ElementRegion with 152 // the pointee-cast type as the new ElementType and the index 153 // being the offset divded by the chunk size. If not, create 154 // a new ElementRegion at offset 0 off the raw offset region. 155 // 156 // (2b) If we don't a get a 'RegionRawOffset' after calling 157 // 'getAsRawOffset()', it means that we are at offset 0. 158 // 159 // FIXME: Handle symbolic raw offsets. 160 161 const ElementRegion *elementR = cast<ElementRegion>(R); 162 const RegionRawOffset &rawOff = elementR->getAsArrayOffset(); 163 const MemRegion *baseR = rawOff.getRegion(); 164 165 // If we cannot compute a raw offset, throw up our hands and return 166 // a NULL MemRegion*. 167 if (!baseR) 168 return NULL; 169 170 CharUnits off = rawOff.getOffset(); 171 172 if (off.isZero()) { 173 // Edge case: we are at 0 bytes off the beginning of baseR. We 174 // check to see if type we are casting to is the same as the base 175 // region. If so, just return the base region. 176 if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(baseR)) { 177 QualType ObjTy = Ctx.getCanonicalType(TR->getValueType()); 178 QualType CanonPointeeTy = Ctx.getCanonicalType(PointeeTy); 179 if (CanonPointeeTy == ObjTy) 180 return baseR; 181 } 182 183 // Otherwise, create a new ElementRegion at offset 0. 184 return MakeElementRegion(baseR, PointeeTy); 185 } 186 187 // We have a non-zero offset from the base region. We want to determine 188 // if the offset can be evenly divided by sizeof(PointeeTy). If so, 189 // we create an ElementRegion whose index is that value. Otherwise, we 190 // create two ElementRegions, one that reflects a raw offset and the other 191 // that reflects the cast. 192 193 // Compute the index for the new ElementRegion. 194 int64_t newIndex = 0; 195 const MemRegion *newSuperR = 0; 196 197 // We can only compute sizeof(PointeeTy) if it is a complete type. 198 if (IsCompleteType(Ctx, PointeeTy)) { 199 // Compute the size in **bytes**. 200 CharUnits pointeeTySize = Ctx.getTypeSizeInChars(PointeeTy); 201 if (!pointeeTySize.isZero()) { 202 // Is the offset a multiple of the size? If so, we can layer the 203 // ElementRegion (with elementType == PointeeTy) directly on top of 204 // the base region. 205 if (off % pointeeTySize == 0) { 206 newIndex = off / pointeeTySize; 207 newSuperR = baseR; 208 } 209 } 210 } 211 212 if (!newSuperR) { 213 // Create an intermediate ElementRegion to represent the raw byte. 214 // This will be the super region of the final ElementRegion. 215 newSuperR = MakeElementRegion(baseR, Ctx.CharTy, off.getQuantity()); 216 } 217 218 return MakeElementRegion(newSuperR, PointeeTy, newIndex); 219 } 220 } 221 222 llvm_unreachable("unreachable"); 223} 224 225 226/// CastRetrievedVal - Used by subclasses of StoreManager to implement 227/// implicit casts that arise from loads from regions that are reinterpreted 228/// as another region. 229SVal StoreManager::CastRetrievedVal(SVal V, const TypedValueRegion *R, 230 QualType castTy, bool performTestOnly) { 231 232 if (castTy.isNull() || V.isUnknownOrUndef()) 233 return V; 234 235 ASTContext &Ctx = svalBuilder.getContext(); 236 237 if (performTestOnly) { 238 // Automatically translate references to pointers. 239 QualType T = R->getValueType(); 240 if (const ReferenceType *RT = T->getAs<ReferenceType>()) 241 T = Ctx.getPointerType(RT->getPointeeType()); 242 243 assert(svalBuilder.getContext().hasSameUnqualifiedType(castTy, T)); 244 return V; 245 } 246 247 return svalBuilder.dispatchCast(V, castTy); 248} 249 250SVal StoreManager::getLValueFieldOrIvar(const Decl *D, SVal Base) { 251 if (Base.isUnknownOrUndef()) 252 return Base; 253 254 Loc BaseL = cast<Loc>(Base); 255 const MemRegion* BaseR = 0; 256 257 switch (BaseL.getSubKind()) { 258 case loc::MemRegionKind: 259 BaseR = cast<loc::MemRegionVal>(BaseL).getRegion(); 260 break; 261 262 case loc::GotoLabelKind: 263 // These are anormal cases. Flag an undefined value. 264 return UndefinedVal(); 265 266 case loc::ConcreteIntKind: 267 // While these seem funny, this can happen through casts. 268 // FIXME: What we should return is the field offset. For example, 269 // add the field offset to the integer value. That way funny things 270 // like this work properly: &(((struct foo *) 0xa)->f) 271 return Base; 272 273 default: 274 llvm_unreachable("Unhandled Base."); 275 } 276 277 // NOTE: We must have this check first because ObjCIvarDecl is a subclass 278 // of FieldDecl. 279 if (const ObjCIvarDecl *ID = dyn_cast<ObjCIvarDecl>(D)) 280 return loc::MemRegionVal(MRMgr.getObjCIvarRegion(ID, BaseR)); 281 282 return loc::MemRegionVal(MRMgr.getFieldRegion(cast<FieldDecl>(D), BaseR)); 283} 284 285SVal StoreManager::getLValueIvar(const ObjCIvarDecl *decl, SVal base) { 286 return getLValueFieldOrIvar(decl, base); 287} 288 289SVal StoreManager::getLValueElement(QualType elementType, NonLoc Offset, 290 SVal Base) { 291 292 // If the base is an unknown or undefined value, just return it back. 293 // FIXME: For absolute pointer addresses, we just return that value back as 294 // well, although in reality we should return the offset added to that 295 // value. 296 if (Base.isUnknownOrUndef() || isa<loc::ConcreteInt>(Base)) 297 return Base; 298 299 const MemRegion* BaseRegion = cast<loc::MemRegionVal>(Base).getRegion(); 300 301 // Pointer of any type can be cast and used as array base. 302 const ElementRegion *ElemR = dyn_cast<ElementRegion>(BaseRegion); 303 304 // Convert the offset to the appropriate size and signedness. 305 Offset = cast<NonLoc>(svalBuilder.convertToArrayIndex(Offset)); 306 307 if (!ElemR) { 308 // 309 // If the base region is not an ElementRegion, create one. 310 // This can happen in the following example: 311 // 312 // char *p = __builtin_alloc(10); 313 // p[1] = 8; 314 // 315 // Observe that 'p' binds to an AllocaRegion. 316 // 317 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, Offset, 318 BaseRegion, Ctx)); 319 } 320 321 SVal BaseIdx = ElemR->getIndex(); 322 323 if (!isa<nonloc::ConcreteInt>(BaseIdx)) 324 return UnknownVal(); 325 326 const llvm::APSInt& BaseIdxI = cast<nonloc::ConcreteInt>(BaseIdx).getValue(); 327 328 // Only allow non-integer offsets if the base region has no offset itself. 329 // FIXME: This is a somewhat arbitrary restriction. We should be using 330 // SValBuilder here to add the two offsets without checking their types. 331 if (!isa<nonloc::ConcreteInt>(Offset)) { 332 if (isa<ElementRegion>(BaseRegion->StripCasts())) 333 return UnknownVal(); 334 335 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, Offset, 336 ElemR->getSuperRegion(), 337 Ctx)); 338 } 339 340 const llvm::APSInt& OffI = cast<nonloc::ConcreteInt>(Offset).getValue(); 341 assert(BaseIdxI.isSigned()); 342 343 // Compute the new index. 344 nonloc::ConcreteInt NewIdx(svalBuilder.getBasicValueFactory().getValue(BaseIdxI + 345 OffI)); 346 347 // Construct the new ElementRegion. 348 const MemRegion *ArrayR = ElemR->getSuperRegion(); 349 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, NewIdx, ArrayR, 350 Ctx)); 351} 352 353StoreManager::BindingsHandler::~BindingsHandler() {} 354 355bool StoreManager::FindUniqueBinding::HandleBinding(StoreManager& SMgr, 356 Store store, 357 const MemRegion* R, 358 SVal val) { 359 SymbolRef SymV = val.getAsLocSymbol(); 360 if (!SymV || SymV != Sym) 361 return true; 362 363 if (Binding) { 364 First = false; 365 return false; 366 } 367 else 368 Binding = R; 369 370 return true; 371} 372 373void SubRegionMap::anchor() { } 374void SubRegionMap::Visitor::anchor() { } 375