1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
|
//=== FlatStore.cpp - Flat region-based store model -------------*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
#include "clang/StaticAnalyzer/Core/PathSensitive/GRState.h"
#include "llvm/ADT/ImmutableIntervalMap.h"
#include "llvm/Support/ErrorHandling.h"
using namespace clang;
using namespace ento;
using llvm::Interval;
// The actual store type.
typedef llvm::ImmutableIntervalMap<SVal> BindingVal;
typedef llvm::ImmutableMap<const MemRegion *, BindingVal> RegionBindings;
namespace {
class FlatStoreManager : public StoreManager {
RegionBindings::Factory RBFactory;
BindingVal::Factory BVFactory;
public:
FlatStoreManager(GRStateManager &mgr)
: StoreManager(mgr),
RBFactory(mgr.getAllocator()),
BVFactory(mgr.getAllocator()) {}
SVal Retrieve(Store store, Loc L, QualType T);
StoreRef Bind(Store store, Loc L, SVal val);
StoreRef Remove(Store St, Loc L);
StoreRef BindCompoundLiteral(Store store, const CompoundLiteralExpr* cl,
const LocationContext *LC, SVal v);
StoreRef getInitialStore(const LocationContext *InitLoc) {
return StoreRef(RBFactory.getEmptyMap().getRoot(), *this);
}
SubRegionMap *getSubRegionMap(Store store) {
return 0;
}
SVal ArrayToPointer(Loc Array);
StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx,
SymbolReaper& SymReaper,
llvm::SmallVectorImpl<const MemRegion*>& RegionRoots){
return StoreRef(store, *this);
}
StoreRef BindDecl(Store store, const VarRegion *VR, SVal initVal);
StoreRef BindDeclWithNoInit(Store store, const VarRegion *VR);
typedef llvm::DenseSet<SymbolRef> InvalidatedSymbols;
StoreRef invalidateRegions(Store store, const MemRegion * const *I,
const MemRegion * const *E, const Expr *Ex,
unsigned Count, InvalidatedSymbols *IS,
bool invalidateGlobals,
InvalidatedRegions *Regions);
void print(Store store, llvm::raw_ostream& Out, const char* nl,
const char *sep);
void iterBindings(Store store, BindingsHandler& f);
private:
static RegionBindings getRegionBindings(Store store) {
return RegionBindings(static_cast<const RegionBindings::TreeTy*>(store));
}
class RegionInterval {
public:
const MemRegion *R;
Interval I;
RegionInterval(const MemRegion *r, int64_t s, int64_t e) : R(r), I(s, e){}
};
RegionInterval RegionToInterval(const MemRegion *R);
SVal RetrieveRegionWithNoBinding(const MemRegion *R, QualType T);
};
} // end anonymous namespace
StoreManager *ento::CreateFlatStoreManager(GRStateManager &StMgr) {
return new FlatStoreManager(StMgr);
}
SVal FlatStoreManager::Retrieve(Store store, Loc L, QualType T) {
// For access to concrete addresses, return UnknownVal. Checks
// for null dereferences (and similar errors) are done by checkers, not
// the Store.
// FIXME: We can consider lazily symbolicating such memory, but we really
// should defer this when we can reason easily about symbolicating arrays
// of bytes.
if (isa<loc::ConcreteInt>(L)) {
return UnknownVal();
}
if (!isa<loc::MemRegionVal>(L)) {
return UnknownVal();
}
const MemRegion *R = cast<loc::MemRegionVal>(L).getRegion();
RegionInterval RI = RegionToInterval(R);
// FIXME: FlatStore should handle regions with unknown intervals.
if (!RI.R)
return UnknownVal();
RegionBindings B = getRegionBindings(store);
const BindingVal *BV = B.lookup(RI.R);
if (BV) {
const SVal *V = BVFactory.lookup(*BV, RI.I);
if (V)
return *V;
else
return RetrieveRegionWithNoBinding(R, T);
}
return RetrieveRegionWithNoBinding(R, T);
}
SVal FlatStoreManager::RetrieveRegionWithNoBinding(const MemRegion *R,
QualType T) {
if (R->hasStackNonParametersStorage())
return UndefinedVal();
else
return svalBuilder.getRegionValueSymbolVal(cast<TypedRegion>(R));
}
StoreRef FlatStoreManager::Bind(Store store, Loc L, SVal val) {
const MemRegion *R = cast<loc::MemRegionVal>(L).getRegion();
RegionBindings B = getRegionBindings(store);
const BindingVal *V = B.lookup(R);
BindingVal BV = BVFactory.getEmptyMap();
if (V)
BV = *V;
RegionInterval RI = RegionToInterval(R);
// FIXME: FlatStore should handle regions with unknown intervals.
if (!RI.R)
return StoreRef(B.getRoot(), *this);
BV = BVFactory.add(BV, RI.I, val);
B = RBFactory.add(B, RI.R, BV);
return StoreRef(B.getRoot(), *this);
}
StoreRef FlatStoreManager::Remove(Store store, Loc L) {
return StoreRef(store, *this);
}
StoreRef FlatStoreManager::BindCompoundLiteral(Store store,
const CompoundLiteralExpr* cl,
const LocationContext *LC,
SVal v) {
return StoreRef(store, *this);
}
SVal FlatStoreManager::ArrayToPointer(Loc Array) {
return Array;
}
StoreRef FlatStoreManager::BindDecl(Store store, const VarRegion *VR,
SVal initVal) {
return Bind(store, svalBuilder.makeLoc(VR), initVal);
}
StoreRef FlatStoreManager::BindDeclWithNoInit(Store store, const VarRegion *VR){
return StoreRef(store, *this);
}
StoreRef FlatStoreManager::invalidateRegions(Store store,
const MemRegion * const *I,
const MemRegion * const *E,
const Expr *Ex, unsigned Count,
InvalidatedSymbols *IS,
bool invalidateGlobals,
InvalidatedRegions *Regions) {
assert(false && "Not implemented");
return StoreRef(store, *this);
}
void FlatStoreManager::print(Store store, llvm::raw_ostream& Out,
const char* nl, const char *sep) {
}
void FlatStoreManager::iterBindings(Store store, BindingsHandler& f) {
}
FlatStoreManager::RegionInterval
FlatStoreManager::RegionToInterval(const MemRegion *R) {
switch (R->getKind()) {
case MemRegion::VarRegionKind: {
QualType T = cast<VarRegion>(R)->getValueType();
int64_t Size = Ctx.getTypeSize(T);
return RegionInterval(R, 0, Size-1);
}
case MemRegion::ElementRegionKind:
case MemRegion::FieldRegionKind: {
RegionOffset Offset = R->getAsOffset();
// We cannot compute offset for all regions, for example, elements
// with symbolic offsets.
if (!Offset.getRegion())
return RegionInterval(0, 0, 0);
int64_t Start = Offset.getOffset();
int64_t Size = Ctx.getTypeSize(cast<TypedRegion>(R)->getValueType());
return RegionInterval(Offset.getRegion(), Start, Start+Size);
}
default:
llvm_unreachable("Region kind unhandled.");
return RegionInterval(0, 0, 0);
}
}
|
