blob: 35bcf945fb93d7a1421ce4d84350953d67a30ed1 [file] [log] [blame]
//== BasicStore.cpp - Basic map from Locations to Values --------*- C++ -*--==//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file defined the BasicStore and BasicStoreManager classes.
//
//===----------------------------------------------------------------------===//
#include "clang/AST/DeclCXX.h"
#include "clang/AST/ExprObjC.h"
#include "clang/Analysis/Analyses/LiveVariables.h"
#include "clang/Analysis/AnalysisContext.h"
#include "clang/StaticAnalyzer/PathSensitive/GRState.h"
#include "llvm/ADT/ImmutableMap.h"
using namespace clang;
using namespace ento;
typedef llvm::ImmutableMap<const MemRegion*,SVal> BindingsTy;
namespace {
class BasicStoreSubRegionMap : public SubRegionMap {
public:
BasicStoreSubRegionMap() {}
bool iterSubRegions(const MemRegion* R, Visitor& V) const {
return true; // Do nothing. No subregions.
}
};
class BasicStoreManager : public StoreManager {
BindingsTy::Factory VBFactory;
public:
BasicStoreManager(GRStateManager& mgr)
: StoreManager(mgr), VBFactory(mgr.getAllocator()) {}
~BasicStoreManager() {}
SubRegionMap *getSubRegionMap(Store store) {
return new BasicStoreSubRegionMap();
}
SVal Retrieve(Store store, Loc loc, QualType T = QualType());
Store InvalidateRegion(Store store, const MemRegion *R, const Expr *E,
unsigned Count, InvalidatedSymbols *IS);
Store InvalidateRegions(Store store, const MemRegion * const *Begin,
const MemRegion * const *End, const Expr *E,
unsigned Count, InvalidatedSymbols *IS,
bool invalidateGlobals, InvalidatedRegions *Regions);
Store scanForIvars(Stmt *B, const Decl* SelfDecl,
const MemRegion *SelfRegion, Store St);
Store Bind(Store St, Loc loc, SVal V);
Store Remove(Store St, Loc loc);
Store getInitialStore(const LocationContext *InitLoc);
Store BindCompoundLiteral(Store store, const CompoundLiteralExpr*,
const LocationContext*, SVal val) {
return store;
}
/// ArrayToPointer - Used by ExprEngine::VistCast to handle implicit
/// conversions between arrays and pointers.
SVal ArrayToPointer(Loc Array) { return Array; }
/// RemoveDeadBindings - Scans a BasicStore of 'state' for dead values.
/// It updatees the GRState object in place with the values removed.
Store RemoveDeadBindings(Store store, const StackFrameContext *LCtx,
SymbolReaper& SymReaper,
llvm::SmallVectorImpl<const MemRegion*>& RegionRoots);
void iterBindings(Store store, BindingsHandler& f);
Store BindDecl(Store store, const VarRegion *VR, SVal InitVal) {
return BindDeclInternal(store, VR, &InitVal);
}
Store BindDeclWithNoInit(Store store, const VarRegion *VR) {
return BindDeclInternal(store, VR, 0);
}
Store BindDeclInternal(Store store, const VarRegion *VR, SVal *InitVal);
static inline BindingsTy GetBindings(Store store) {
return BindingsTy(static_cast<const BindingsTy::TreeTy*>(store));
}
void print(Store store, llvm::raw_ostream& Out, const char* nl,
const char *sep);
private:
SVal LazyRetrieve(Store store, const TypedRegion *R);
};
} // end anonymous namespace
StoreManager* ento::CreateBasicStoreManager(GRStateManager& StMgr) {
return new BasicStoreManager(StMgr);
}
static bool isHigherOrderRawPtr(QualType T, ASTContext &C) {
bool foundPointer = false;
while (1) {
const PointerType *PT = T->getAs<PointerType>();
if (!PT) {
if (!foundPointer)
return false;
// intptr_t* or intptr_t**, etc?
if (T->isIntegerType() && C.getTypeSize(T) == C.getTypeSize(C.VoidPtrTy))
return true;
QualType X = C.getCanonicalType(T).getUnqualifiedType();
return X == C.VoidTy;
}
foundPointer = true;
T = PT->getPointeeType();
}
}
SVal BasicStoreManager::LazyRetrieve(Store store, const TypedRegion *R) {
const VarRegion *VR = dyn_cast<VarRegion>(R);
if (!VR)
return UnknownVal();
const VarDecl *VD = VR->getDecl();
QualType T = VD->getType();
// Only handle simple types that we can symbolicate.
if (!SymbolManager::canSymbolicate(T) || !T->isScalarType())
return UnknownVal();
// Globals and parameters start with symbolic values.
// Local variables initially are undefined.
// Non-static globals may have had their values reset by InvalidateRegions.
const MemSpaceRegion *MS = VR->getMemorySpace();
if (isa<NonStaticGlobalSpaceRegion>(MS)) {
BindingsTy B = GetBindings(store);
// FIXME: Copy-and-pasted from RegionStore.cpp.
if (BindingsTy::data_type *Val = B.lookup(MS)) {
if (SymbolRef parentSym = Val->getAsSymbol())
return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);
if (Val->isZeroConstant())
return svalBuilder.makeZeroVal(T);
if (Val->isUnknownOrUndef())
return *Val;
assert(0 && "Unknown default value.");
}
}
if (VR->hasGlobalsOrParametersStorage() ||
isa<UnknownSpaceRegion>(VR->getMemorySpace()))
return svalBuilder.getRegionValueSymbolVal(R);
return UndefinedVal();
}
SVal BasicStoreManager::Retrieve(Store store, Loc loc, QualType T) {
if (isa<UnknownVal>(loc))
return UnknownVal();
assert(!isa<UndefinedVal>(loc));
switch (loc.getSubKind()) {
case loc::MemRegionKind: {
const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion();
if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R) ||
isa<CXXThisRegion>(R)))
return UnknownVal();
BindingsTy B = GetBindings(store);
BindingsTy::data_type *Val = B.lookup(R);
const TypedRegion *TR = cast<TypedRegion>(R);
if (Val)
return CastRetrievedVal(*Val, TR, T);
SVal V = LazyRetrieve(store, TR);
return V.isUnknownOrUndef() ? V : CastRetrievedVal(V, TR, T);
}
case loc::ConcreteIntKind:
// Support direct accesses to memory. It's up to individual checkers
// to flag an error.
return UnknownVal();
default:
assert (false && "Invalid Loc.");
break;
}
return UnknownVal();
}
Store BasicStoreManager::Bind(Store store, Loc loc, SVal V) {
if (isa<loc::ConcreteInt>(loc))
return store;
const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion();
// Special case: a default symbol assigned to the NonStaticGlobalsSpaceRegion
// that is used to derive other symbols.
if (isa<NonStaticGlobalSpaceRegion>(R)) {
BindingsTy B = GetBindings(store);
return VBFactory.add(B, R, V).getRoot();
}
// Special case: handle store of pointer values (Loc) to pointers via
// a cast to intXX_t*, void*, etc. This is needed to handle
// OSCompareAndSwap32Barrier/OSCompareAndSwap64Barrier.
if (isa<Loc>(V) || isa<nonloc::LocAsInteger>(V))
if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
// FIXME: Should check for index 0.
QualType T = ER->getLocationType();
if (isHigherOrderRawPtr(T, Ctx))
R = ER->getSuperRegion();
}
if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R) || isa<CXXThisRegion>(R)))
return store;
const TypedRegion *TyR = cast<TypedRegion>(R);
// Do not bind to arrays. We need to explicitly check for this so that
// we do not encounter any weirdness of trying to load/store from arrays.
if (TyR->isBoundable() && TyR->getValueType()->isArrayType())
return store;
if (nonloc::LocAsInteger *X = dyn_cast<nonloc::LocAsInteger>(&V)) {
// Only convert 'V' to a location iff the underlying region type
// is a location as well.
// FIXME: We are allowing a store of an arbitrary location to
// a pointer. We may wish to flag a type error here if the types
// are incompatible. This may also cause lots of breakage
// elsewhere. Food for thought.
if (TyR->isBoundable() && Loc::IsLocType(TyR->getValueType()))
V = X->getLoc();
}
BindingsTy B = GetBindings(store);
return V.isUnknown()
? VBFactory.remove(B, R).getRoot()
: VBFactory.add(B, R, V).getRoot();
}
Store BasicStoreManager::Remove(Store store, Loc loc) {
switch (loc.getSubKind()) {
case loc::MemRegionKind: {
const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion();
if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R) ||
isa<CXXThisRegion>(R)))
return store;
return VBFactory.remove(GetBindings(store), R).getRoot();
}
default:
assert ("Remove for given Loc type not yet implemented.");
return store;
}
}
Store BasicStoreManager::RemoveDeadBindings(Store store,
const StackFrameContext *LCtx,
SymbolReaper& SymReaper,
llvm::SmallVectorImpl<const MemRegion*>& RegionRoots)
{
BindingsTy B = GetBindings(store);
typedef SVal::symbol_iterator symbol_iterator;
// Iterate over the variable bindings.
for (BindingsTy::iterator I=B.begin(), E=B.end(); I!=E ; ++I) {
if (const VarRegion *VR = dyn_cast<VarRegion>(I.getKey())) {
if (SymReaper.isLive(VR))
RegionRoots.push_back(VR);
else
continue;
}
else if (isa<ObjCIvarRegion>(I.getKey()) ||
isa<NonStaticGlobalSpaceRegion>(I.getKey()) ||
isa<CXXThisRegion>(I.getKey()))
RegionRoots.push_back(I.getKey());
else
continue;
// Mark the bindings in the data as live.
SVal X = I.getData();
for (symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end(); SI!=SE; ++SI)
SymReaper.markLive(*SI);
}
// Scan for live variables and live symbols.
llvm::SmallPtrSet<const MemRegion*, 10> Marked;
while (!RegionRoots.empty()) {
const MemRegion* MR = RegionRoots.back();
RegionRoots.pop_back();
while (MR) {
if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(MR)) {
SymReaper.markLive(SymR->getSymbol());
break;
}
else if (isa<VarRegion>(MR) || isa<ObjCIvarRegion>(MR) ||
isa<NonStaticGlobalSpaceRegion>(MR) || isa<CXXThisRegion>(MR)) {
if (Marked.count(MR))
break;
Marked.insert(MR);
SVal X = Retrieve(store, loc::MemRegionVal(MR));
// FIXME: We need to handle symbols nested in region definitions.
for (symbol_iterator SI=X.symbol_begin(),SE=X.symbol_end();SI!=SE;++SI)
SymReaper.markLive(*SI);
if (!isa<loc::MemRegionVal>(X))
break;
const loc::MemRegionVal& LVD = cast<loc::MemRegionVal>(X);
RegionRoots.push_back(LVD.getRegion());
break;
}
else if (const SubRegion* R = dyn_cast<SubRegion>(MR))
MR = R->getSuperRegion();
else
break;
}
}
// Remove dead variable bindings.
for (BindingsTy::iterator I=B.begin(), E=B.end(); I!=E ; ++I) {
const MemRegion* R = I.getKey();
if (!Marked.count(R)) {
store = Remove(store, svalBuilder.makeLoc(R));
SVal X = I.getData();
for (symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end(); SI!=SE; ++SI)
SymReaper.maybeDead(*SI);
}
}
return store;
}
Store BasicStoreManager::scanForIvars(Stmt *B, const Decl* SelfDecl,
const MemRegion *SelfRegion, Store St) {
for (Stmt::child_iterator CI=B->child_begin(), CE=B->child_end();
CI != CE; ++CI) {
if (!*CI)
continue;
// Check if the statement is an ivar reference. We only
// care about self.ivar.
if (ObjCIvarRefExpr *IV = dyn_cast<ObjCIvarRefExpr>(*CI)) {
const Expr *Base = IV->getBase()->IgnoreParenCasts();
if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Base)) {
if (DR->getDecl() == SelfDecl) {
const ObjCIvarRegion *IVR = MRMgr.getObjCIvarRegion(IV->getDecl(),
SelfRegion);
SVal X = svalBuilder.getRegionValueSymbolVal(IVR);
St = Bind(St, svalBuilder.makeLoc(IVR), X);
}
}
}
else
St = scanForIvars(*CI, SelfDecl, SelfRegion, St);
}
return St;
}
Store BasicStoreManager::getInitialStore(const LocationContext *InitLoc) {
// The LiveVariables information already has a compilation of all VarDecls
// used in the function. Iterate through this set, and "symbolicate"
// any VarDecl whose value originally comes from outside the function.
typedef LiveVariables::AnalysisDataTy LVDataTy;
LVDataTy& D = InitLoc->getLiveVariables()->getAnalysisData();
Store St = VBFactory.getEmptyMap().getRoot();
for (LVDataTy::decl_iterator I=D.begin_decl(), E=D.end_decl(); I != E; ++I) {
const NamedDecl* ND = I->first;
// Handle implicit parameters.
if (const ImplicitParamDecl* PD = dyn_cast<ImplicitParamDecl>(ND)) {
const Decl& CD = *InitLoc->getDecl();
if (const ObjCMethodDecl* MD = dyn_cast<ObjCMethodDecl>(&CD)) {
if (MD->getSelfDecl() == PD) {
// FIXME: Add type constraints (when they become available) to
// SelfRegion? (i.e., it implements MD->getClassInterface()).
const VarRegion *VR = MRMgr.getVarRegion(PD, InitLoc);
const MemRegion *SelfRegion =
svalBuilder.getRegionValueSymbolVal(VR).getAsRegion();
assert(SelfRegion);
St = Bind(St, svalBuilder.makeLoc(VR), loc::MemRegionVal(SelfRegion));
// Scan the method for ivar references. While this requires an
// entire AST scan, the cost should not be high in practice.
St = scanForIvars(MD->getBody(), PD, SelfRegion, St);
}
}
}
}
if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(InitLoc->getDecl())) {
// For C++ methods add symbolic region for 'this' in initial stack frame.
QualType ThisT = MD->getThisType(StateMgr.getContext());
MemRegionManager &RegMgr = svalBuilder.getRegionManager();
const CXXThisRegion *ThisR = RegMgr.getCXXThisRegion(ThisT, InitLoc);
SVal ThisV = svalBuilder.getRegionValueSymbolVal(ThisR);
St = Bind(St, svalBuilder.makeLoc(ThisR), ThisV);
}
return St;
}
Store BasicStoreManager::BindDeclInternal(Store store, const VarRegion* VR,
SVal* InitVal) {
BasicValueFactory& BasicVals = StateMgr.getBasicVals();
const VarDecl *VD = VR->getDecl();
// BasicStore does not model arrays and structs.
if (VD->getType()->isArrayType() || VD->getType()->isStructureOrClassType())
return store;
if (VD->hasGlobalStorage()) {
// Handle variables with global storage: extern, static, PrivateExtern.
// FIXME:: static variables may have an initializer, but the second time a
// function is called those values may not be current. Currently, a function
// will not be called more than once.
// Static global variables should not be visited here.
assert(!(VD->getStorageClass() == SC_Static &&
VD->isFileVarDecl()));
// Process static variables.
if (VD->getStorageClass() == SC_Static) {
// C99: 6.7.8 Initialization
// If an object that has static storage duration is not initialized
// explicitly, then:
// —if it has pointer type, it is initialized to a null pointer;
// —if it has arithmetic type, it is initialized to (positive or
// unsigned) zero;
if (!InitVal) {
QualType T = VD->getType();
if (Loc::IsLocType(T))
store = Bind(store, loc::MemRegionVal(VR),
loc::ConcreteInt(BasicVals.getValue(0, T)));
else if (T->isIntegerType() && T->isScalarType())
store = Bind(store, loc::MemRegionVal(VR),
nonloc::ConcreteInt(BasicVals.getValue(0, T)));
} else {
store = Bind(store, loc::MemRegionVal(VR), *InitVal);
}
}
} else {
// Process local scalar variables.
QualType T = VD->getType();
// BasicStore only supports scalars.
if ((T->isScalarType() || T->isReferenceType()) &&
svalBuilder.getSymbolManager().canSymbolicate(T)) {
SVal V = InitVal ? *InitVal : UndefinedVal();
store = Bind(store, loc::MemRegionVal(VR), V);
}
}
return store;
}
void BasicStoreManager::print(Store store, llvm::raw_ostream& Out,
const char* nl, const char *sep) {
BindingsTy B = GetBindings(store);
Out << "Variables:" << nl;
bool isFirst = true;
for (BindingsTy::iterator I=B.begin(), E=B.end(); I != E; ++I) {
if (isFirst)
isFirst = false;
else
Out << nl;
Out << ' ' << I.getKey() << " : " << I.getData();
}
}
void BasicStoreManager::iterBindings(Store store, BindingsHandler& f) {
BindingsTy B = GetBindings(store);
for (BindingsTy::iterator I=B.begin(), E=B.end(); I != E; ++I)
if (!f.HandleBinding(*this, store, I.getKey(), I.getData()))
return;
}
StoreManager::BindingsHandler::~BindingsHandler() {}
//===----------------------------------------------------------------------===//
// Binding invalidation.
//===----------------------------------------------------------------------===//
Store BasicStoreManager::InvalidateRegions(Store store,
const MemRegion * const *I,
const MemRegion * const *End,
const Expr *E, unsigned Count,
InvalidatedSymbols *IS,
bool invalidateGlobals,
InvalidatedRegions *Regions) {
if (invalidateGlobals) {
BindingsTy B = GetBindings(store);
for (BindingsTy::iterator I=B.begin(), End=B.end(); I != End; ++I) {
const MemRegion *R = I.getKey();
if (isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace()))
store = InvalidateRegion(store, R, E, Count, IS);
}
}
for ( ; I != End ; ++I) {
const MemRegion *R = *I;
// Don't invalidate globals twice.
if (invalidateGlobals) {
if (isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace()))
continue;
}
store = InvalidateRegion(store, *I, E, Count, IS);
if (Regions)
Regions->push_back(R);
}
// FIXME: This is copy-and-paste from RegionStore.cpp.
if (invalidateGlobals) {
// Bind the non-static globals memory space to a new symbol that we will
// use to derive the bindings for all non-static globals.
const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion();
SVal V =
svalBuilder.getConjuredSymbolVal(/* SymbolTag = */ (void*) GS, E,
/* symbol type, doesn't matter */ Ctx.IntTy,
Count);
store = Bind(store, loc::MemRegionVal(GS), V);
if (Regions)
Regions->push_back(GS);
}
return store;
}
Store BasicStoreManager::InvalidateRegion(Store store,
const MemRegion *R,
const Expr *E,
unsigned Count,
InvalidatedSymbols *IS) {
R = R->StripCasts();
if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R)))
return store;
if (IS) {
BindingsTy B = GetBindings(store);
if (BindingsTy::data_type *Val = B.lookup(R)) {
if (SymbolRef Sym = Val->getAsSymbol())
IS->insert(Sym);
}
}
QualType T = cast<TypedRegion>(R)->getValueType();
SVal V = svalBuilder.getConjuredSymbolVal(R, E, T, Count);
return Bind(store, loc::MemRegionVal(R), V);
}