Predator
[unstable] git snapshot
Main Page
Related Pages
Namespaces
Data Structures
Files
File List
Globals
symstate.hh
Go to the documentation of this file.
1
/*
2
* Copyright (C) 2009-2010 Kamil Dudka <kdudka@redhat.com>
3
*
4
* This file is part of predator.
5
*
6
* predator is free software: you can redistribute it and/or modify
7
* it under the terms of the GNU General Public License as published by
8
* the Free Software Foundation, either version 3 of the License, or
9
* any later version.
10
*
11
* predator is distributed in the hope that it will be useful,
12
* but WITHOUT ANY WARRANTY; without even the implied warranty of
13
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14
* GNU General Public License for more details.
15
*
16
* You should have received a copy of the GNU General Public License
17
* along with predator. If not, see <http://www.gnu.org/licenses/>.
18
*/
19
20
#ifndef H_GUARD_SYM_STATE_H
21
#define H_GUARD_SYM_STATE_H
22
23
/**
24
* @file symstate.hh
25
* @todo update dox
26
*/
27
28
#include <set>
29
#include <vector>
30
31
#include "
join_status.hh
"
32
#include "
symheap.hh
"
33
34
namespace
CodeStorage {
35
class
Block;
36
}
37
38
class
SymState
{
39
private
:
40
typedef
std::vector<SymHeap *>
TList
;
41
42
public
:
43
typedef
TList::const_iterator
const_iterator
;
44
typedef
TList::iterator
iterator
;
45
46
public
:
47
SymState
() { }
48
virtual
~SymState
();
49
50
SymState
(
const
SymState
&);
51
SymState
&
operator=
(
const
SymState
&);
52
53
virtual
void
clear
();
54
55
virtual
void
swap
(
SymState
&other) {
56
heaps_
.swap(other.
heaps_
);
57
}
58
59
/**
60
* look for the given symbolic heap, return its index if found, -1
61
* otherwise
62
*/
63
virtual
int
lookup
(
const
SymHeap
&heap)
const
= 0;
64
65
/// insert given SymHeap object into the state
66
virtual
bool
insert
(
const
SymHeap
&sh,
bool
allowThreeWay =
true
);
67
68
/// return count of object stored in the container
69
size_t
size
()
const
{
return
heaps_
.size(); }
70
71
/// return nth SymHeap object, 0 <= nth < size()
72
const
SymHeap
&
operator[]
(
int
nth)
const
{
73
return
*
heaps_
[nth];
74
}
75
76
/// return STL-like iterator to go through the container
77
const_iterator
begin
()
const
{
return
heaps_
.begin(); }
78
79
/// return STL-like iterator to go through the container
80
const_iterator
end
()
const
{
return
heaps_
.end(); }
81
82
/// @copydoc begin() const
83
iterator
begin
() {
return
heaps_
.begin(); }
84
85
/// @copydoc begin() const
86
iterator
end
() {
return
heaps_
.end(); }
87
88
protected
:
89
/// insert @b new SymHeap that @ must be guaranteed to be not yet in
90
virtual
void
insertNew
(
const
SymHeap
&sh);
91
92
virtual
void
eraseExisting
(
int
nth) {
93
delete
heaps_
[nth];
94
heaps_
.erase(
heaps_
.begin() + nth);
95
}
96
97
virtual
void
swapExisting
(
int
nth,
SymHeap
&sh) {
98
SymHeap
&existing = *
heaps_
.at(nth);
99
existing.
swap
(sh);
100
}
101
102
virtual
void
rotateExisting
(
int
idxA,
int
idxB);
103
104
void
updateTraceOf
(
int
idx,
Trace::Node
*tr,
EJoinStatus
status);
105
106
/// lookup/insert optimization in SymCallCache implementation
107
friend
class
PerFncCache
;
108
109
private
:
110
TList
heaps_
;
111
};
112
113
class
SymHeapList
:
public
SymState
{
114
public
:
115
SymHeapList
() { }
116
117
SymHeapList
(
const
SymState
&ref):
118
// safe to slice the base, as we have no data anyway
119
SymState
(ref)
120
{
121
}
122
123
SymHeapList
&
operator=
(
const
SymState
&ref) {
124
// safe to slice the base, as we have no data anyway
125
*
static_cast<
SymState
*
>
(
this
) = ref;
126
127
return
*
this
;
128
}
129
130
virtual
int
lookup
(
const
SymHeap
&)
const
{
131
return
/* not found */
-1;
132
}
133
};
134
135
/**
136
* symbolic state represented as a union of SymHeap objects (aka disjuncts)
137
*
138
* During the symbolic execution (see SymExec) we keep such a state per each
139
* basic block of the function just being processed. The result of a
140
* symbolically executed function is then the SymState taken from the basic
141
* block containing CL_INSN_RET as soon as the fix-point calculation has
142
* terminated.
143
*/
144
class
SymHeapUnion
:
public
SymState
{
145
public
:
146
virtual
int
lookup
(
const
SymHeap
&sh)
const
;
147
};
148
149
class
SymStateWithJoin
:
public
SymHeapUnion
{
150
public
:
151
virtual
bool
insert
(
const
SymHeap
&sh,
bool
allowThreeWay =
true
);
152
153
private
:
154
void
packState
(
unsigned
idx,
bool
allowThreeWay);
155
};
156
157
/**
158
* Extension of SymStateWithJoin, which distinguishes among already processed
159
* symbolic heaps and symbolic heaps scheduled for processing. Newly inserted
160
* symbolic heaps are always marked as scheduled. They can be marked as done
161
* later, using the setDone() method.
162
*/
163
class
SymStateMarked
:
public
SymStateWithJoin
{
164
public
:
165
SymStateMarked
():
166
cntPending_
(0)
167
{
168
}
169
170
/// import of SymState rewrites the base and invalidates all flags
171
SymStateMarked
&
operator=
(
const
SymState
&huni) {
172
static_cast<
SymState
&
>
(*this) = huni;
173
done_
.clear();
174
done_
.resize(huni.
size
(),
false
);
175
cntPending_
= huni.
size
();
176
return
*
this
;
177
}
178
179
virtual
void
clear
() {
180
SymStateWithJoin::clear
();
181
done_
.clear();
182
cntPending_
= 0;
183
}
184
185
/// @attention always reinitializes the markers
186
virtual
void
swap
(
SymState
&);
187
188
/// return count of heaps pending for execution
189
int
cntPending
()
const
{
190
return
cntPending_
;
191
}
192
193
protected
:
194
virtual
void
insertNew
(
const
SymHeap
&sh) {
195
SymStateWithJoin::insertNew
(sh);
196
197
// schedule the just inserted SymHeap for processing
198
done_
.push_back(
false
);
199
++
cntPending_
;
200
}
201
202
virtual
void
eraseExisting
(
int
nth) {
203
SymStateWithJoin::eraseExisting
(nth);
204
205
if
(!
done_
[nth])
206
--
cntPending_
;
207
208
done_
.erase(
done_
.begin() + nth);
209
}
210
211
virtual
void
swapExisting
(
int
nth,
SymHeap
&sh) {
212
SymStateWithJoin::swapExisting
(nth, sh);
213
214
if
(!
done_
.at(nth))
215
return
;
216
217
// an already processed heap has been generalized, we need to
218
// schedule it for precessing once again
219
done_
[nth] =
false
;
220
++
cntPending_
;
221
}
222
223
virtual
void
rotateExisting
(
int
idxA,
int
idxB);
224
225
friend
class
SymStateMap
;
226
227
public
:
228
/// check if the nth symbolic heap has been already processed
229
bool
isDone
(
int
nth)
const
{
230
return
done_
.at(nth);
231
}
232
233
/// mark the nth symbolic heap as processed
234
void
setDone
(
int
nth) {
235
if
(!
done_
.at(nth))
236
--
cntPending_
;
237
238
done_
[nth] =
true
;
239
}
240
241
private
:
242
typedef
std::vector<bool>
TDone
;
243
244
TDone
done_
;
245
int
cntPending_
;
246
};
247
248
class
IPendingCountProvider
{
249
public
:
250
virtual
~IPendingCountProvider
() { }
251
252
/// return count of heaps pending for execution in the specified blcok
253
virtual
int
cntPending
(
const
CodeStorage::Block
*)
const
= 0;
254
};
255
256
/**
257
* higher-level container that maintains a SymStateMarked object per each basic
258
* block. It's used by SymExecEngine and PathTracer classes.
259
*/
260
class
SymStateMap
:
public
IPendingCountProvider
{
261
public
:
262
typedef
std::vector<const CodeStorage::Block *>
TContBlock
;
263
264
SymStateMap
();
265
virtual
~SymStateMap
();
266
267
/// state lookup, basically equal to std::map semantic
268
SymStateMarked
&
operator[]
(
const
CodeStorage::Block
*);
269
270
/**
271
* managed insertion of the state that keeps track of the relation among
272
* source and destination basic blocks
273
* @param dst @b destination basic block (where the insertion occurs)
274
* @param sh an instance of symbolic heap that should be inserted
275
* @param allowThreeWay if true, three-way join is allowed
276
*/
277
bool
insert
(
const
CodeStorage::Block
*dst,
278
const
SymHeap
&sh,
279
bool
allowThreeWay =
true
);
280
281
/// true if the specified block has ever joined/entailed any given state
282
bool
anyReuseHappened
(
const
CodeStorage::Block
*)
const
;
283
284
virtual
int
cntPending
(
const
CodeStorage::Block
*)
const
;
285
286
private
:
287
/// object copying is @b not allowed
288
SymStateMap
(
const
SymStateMap
&);
289
290
/// object copying is @b not allowed
291
SymStateMap
&
operator=
(
const
SymStateMap
&);
292
293
private
:
294
struct
Private;
295
Private *
d
;
296
};
297
298
class
IStatsProvider
{
299
public
:
300
virtual
~IStatsProvider
() { }
301
virtual
void
printStats
()
const
= 0;
302
};
303
304
class
BlockScheduler
:
public
IStatsProvider
{
305
public
:
306
typedef
const
CodeStorage::Block
*
TBlock
;
307
typedef
std::set<TBlock>
TBlockSet
;
308
typedef
std::vector<TBlock>
TBlockList
;
309
310
public
:
311
BlockScheduler
(
const
IPendingCountProvider
&);
312
BlockScheduler
(
const
BlockScheduler
&);
313
~BlockScheduler
();
314
315
const
TBlockSet
&
todo
()
const
;
316
317
TBlockList
done
()
const
;
318
319
unsigned
cntWaiting
()
const
;
320
321
bool
schedule
(
TBlock
bb);
322
323
bool
getNext
(
TBlock
*dst);
324
325
virtual
void
printStats
()
const
;
326
327
private
:
328
// not implemented
329
BlockScheduler
&
operator=
(
const
BlockScheduler
&);
330
331
struct
Private;
332
Private *
d
;
333
};
334
335
#endif
/* H_GUARD_SYM_STATE_H */
Generated on Mon Nov 9 2015 14:51:59 for Predator by
1.8.1.2