Predator
[unstable] git snapshot
Main Page
Related Pages
Namespaces
Data Structures
Files
File List
Globals
symheap.hh
Go to the documentation of this file.
1
/*
2
* Copyright (C) 2009-2011 Kamil Dudka <kdudka@redhat.com>
3
* Copyright (C) 2010 Petr Peringer, FIT
4
*
5
* This file is part of predator.
6
*
7
* predator is free software: you can redistribute it and/or modify
8
* it under the terms of the GNU General Public License as published by
9
* the Free Software Foundation, either version 3 of the License, or
10
* any later version.
11
*
12
* predator is distributed in the hope that it will be useful,
13
* but WITHOUT ANY WARRANTY; without even the implied warranty of
14
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15
* GNU General Public License for more details.
16
*
17
* You should have received a copy of the GNU General Public License
18
* along with predator. If not, see <http://www.gnu.org/licenses/>.
19
*/
20
21
#ifndef H_GUARD_SYM_HEAP_H
22
#define H_GUARD_SYM_HEAP_H
23
24
/**
25
* @file symheap.hh
26
* SymHeap - the elementary representation of the state of program memory
27
*/
28
29
#include "
config.h
"
30
31
#include "
intrange.hh
"
32
#include "
symid.hh
"
33
#include "
util.hh
"
34
35
#include <
cl/code_listener.h
>
36
37
#include <map>
// for TValMap
38
#include <set>
// for TCVarSet
39
#include <string>
40
#include <vector>
// for many types
41
42
class
SymBackTrace
;
43
44
/// classification of kind of origins a value may come from
45
enum
EValueOrigin
{
46
VO_INVALID
,
///< reserved for signalling error states
47
VO_ASSIGNED
,
///< known result of an operation
48
VO_UNKNOWN
,
///< value was abstracted out and guessed later on
49
VO_REINTERPRET
,
///< a result of unsupported data reinterpretation
50
VO_DEREF_FAILED
,
///< a result of invalid dereference
51
VO_STACK
,
///< untouched contents of stack
52
VO_HEAP
///< untouched contents of heap
53
};
54
55
/// true for VO_HEAP and VO_STACK
56
bool
isUninitialized
(
EValueOrigin
);
57
58
/// classification of kind of objects a value may point to
59
enum
EValueTarget
{
60
VT_INVALID
,
///< completely invalid target
61
VT_UNKNOWN
,
///< arbitrary target
62
VT_COMPOSITE
,
///< value of a composite field (not a pointer to!)
63
VT_CUSTOM
,
///< non-pointer data, classified by ECustomValue
64
VT_OBJECT
,
///< target is a (possibly invalid) object
65
66
// TODO: drop this?
67
VT_RANGE
///< an offset value where offset is given by range
68
};
69
70
/// TODO: drop this!
71
bool
isAnyDataArea
(
EValueTarget
);
72
73
/// classification of the storage class for objects
74
enum
EStorageClass
{
75
SC_INVALID
,
///< reserved for signalling error states
76
SC_UNKNOWN
,
///< no assumptions, the object may be even shared
77
SC_STATIC
,
///< safely allocated in static data if not a 0+ obj
78
SC_ON_HEAP
,
///< safely allocated on heap except for 0+ objects
79
SC_ON_STACK
///< safely allocated on stack except for 0+ objects
80
};
81
82
/// true for SC_ON_HEAP
83
bool
isOnHeap
(
EStorageClass
);
84
85
/// true for SC_STATIC and SC_ON_STACK
86
bool
isProgramVar
(
EStorageClass
);
87
88
/// classification of the target of an address (a.k.a. target specifier)
89
enum
ETargetSpecifier
{
90
TS_INVALID
,
///< reserved for signalling error states
91
TS_REGION
,
///< the only allowed TS for addresses of regions
92
TS_FIRST
,
///< target is the first node of an abstract object
93
TS_LAST
,
///< target is the last node of an abstract object
94
TS_ALL
///< target is any node of an abstract object
95
};
96
97
/// enumeration of custom values, such as integer literals, or code pointers
98
enum
ECustomValue
{
99
CV_INVALID
,
///< reserved for signalling error states
100
CV_FNC
,
///< code pointer
101
CV_INT_RANGE
,
///< a closed interval over integral domain
102
CV_REAL
,
///< floating-point number
103
CV_STRING
///< string literal
104
};
105
106
union
CustomValueData
{
107
int
uid
;
///< unique ID as assigned by Code Listener
108
double
fpn
;
///< floating-point number
109
std::string *
str
;
///< string literal
110
IR::Range
rng
;
///< closed interval over integral domain
111
};
112
113
/// representation of a custom value, such as integer literal, or code pointer
114
class
CustomValue
{
115
public
:
116
// cppcheck-suppress uninitVar
117
CustomValue
():
118
code_
(
CV_INVALID
)
119
{
120
}
121
122
~CustomValue
();
123
CustomValue
(
const
CustomValue
&);
124
CustomValue
&
operator=
(
const
CustomValue
&);
125
126
explicit
CustomValue
(
int
uid
):
127
code_
(
CV_FNC
)
128
{
129
data_
.
uid
=
uid
;
130
}
131
132
explicit
CustomValue
(
const
IR::Range
&
rng
):
133
code_
(
CV_INT_RANGE
)
134
{
135
data_
.
rng
=
rng
;
136
}
137
138
explicit
CustomValue
(
const
double
fpn
):
139
code_
(
CV_REAL
)
140
{
141
data_
.
fpn
=
fpn
;
142
}
143
144
explicit
CustomValue
(
const
char
*
str
):
145
code_
(
CV_STRING
)
146
{
147
data_
.
str
=
new
std::string(str);
148
}
149
150
/// custom value classification
151
ECustomValue
code
()
const
{
152
return
code_
;
153
}
154
155
/// unique ID as assigned by Code Listener (only for CV_FNC)
156
int
uid
()
const
;
157
158
/// closed interval over integral domain (only for CV_INT_RANGE)
159
IR::Range
&
rng
();
160
161
/// closed interval over integral domain (only for CV_INT_RANGE)
162
const
IR::Range
&
rng
()
const
{
163
return
const_cast<
CustomValue
*
>
(
this
)->
rng
();
164
}
165
166
/// floating-point number (only for CV_REAL)
167
double
fpn
()
const
;
168
169
/// string literal (only for CV_STRING)
170
const
std::string &
str
()
const
;
171
172
private
:
173
friend
bool
operator==
(
const
CustomValue
&,
const
CustomValue
&);
174
175
ECustomValue
code_
;
176
CustomValueData
data_
;
177
};
178
179
bool
operator==
(
const
CustomValue
&a,
const
CustomValue
&b);
180
181
inline
bool
operator!=
(
const
CustomValue
&a,
const
CustomValue
&b)
182
{
183
return
!
operator==
(a, b);
184
}
185
186
namespace
CodeStorage {
187
struct
Storage;
188
}
189
190
namespace
Trace {
191
class
Node;
192
}
193
194
/// a type used for integral offsets (changing this is known to cause problems)
195
typedef
IR::TInt
TOffset
;
196
197
/// a type used for block sizes (do not set this to anything else than TOffset)
198
typedef
IR::TInt
TSizeOf
;
199
200
/// a type used for block size ranges (do not try to change this one either)
201
typedef
IR::Range
TSizeRange
;
202
203
/// a container to store offsets to
204
typedef
std::vector<TOffset>
TOffList
;
205
206
/// container used to store value IDs to
207
typedef
std::vector<TValId>
TValList
;
208
209
/// container used to store object IDs to
210
typedef
std::vector<TObjId>
TObjList
;
211
212
/// container used to store value IDs to
213
typedef
std::set<TValId>
TValSet
;
214
215
/// container used to store object IDs to
216
typedef
std::set<TObjId>
TObjSet
;
217
218
/// a type used for (injective) value IDs mapping
219
typedef
std::map<TValId, TValId>
TValMap
;
220
221
/// a type used for (injective) object IDs mapping
222
typedef
std::map<TObjId, TObjId>
TObjMap
;
223
224
/// a type used for type-info
225
typedef
const
struct
cl_type
*
TObjType
;
226
227
/// a class of type (structure, pointer, union, ...)
228
typedef
enum
cl_type_e
TObjCode
;
229
230
/// a reference to CodeStorage::Storage instance describing the analyzed code
231
typedef
const
CodeStorage::Storage
&
TStorRef
;
232
233
/// a type used for prototype level (0 means not a prototype)
234
typedef
short
TProtoLevel
;
235
236
/**
237
* bundles static identification of a variable with its instance number
238
*
239
* In order to enable call recursion, we need to distinguish among various
240
* instances of the same automatic variable in case a function is called
241
* recursively.
242
*/
243
struct
CVar
{
244
/// static identification of a variable
245
int
uid
;
246
247
/// zero for global/static variables, instance number 1..n otherwise
248
int
inst
;
249
250
CVar
():
251
uid
(-1),
252
inst
(-1)
253
{
254
}
255
256
CVar
(
int
uid_,
int
inst_):
257
uid
(uid_),
258
inst
(inst_)
259
{
260
}
261
};
262
263
inline
bool
operator==
(
const
CVar
&a,
const
CVar
&b)
264
{
265
if
(a.
uid
!= b.
uid
)
266
return
false
;
267
268
if
(-1 == a.
uid
)
269
// do not match .inst when a.uid == -1 == b.uid
270
return
true
;
271
272
return
a.
inst
== b.
inst
;
273
}
274
275
inline
bool
operator!=
(
const
CVar
&a,
const
CVar
&b)
276
{
277
return
!
operator==
(a, b);
278
}
279
280
/// bundles static identification of a function with its call instance number
281
struct
CallInst
{
282
int
uid
;
///< uid of the function
283
int
inst
;
///< how many instances of the fnc we have on the stack
284
285
CallInst
():
286
uid
(-1),
287
inst
(-1)
288
{
289
}
290
291
CallInst
(
const
SymBackTrace
*);
292
293
CallInst
(
int
uid_,
int
inst_):
294
uid
(uid_),
295
inst
(inst_)
296
{
297
}
298
};
299
300
inline
bool
operator==
(
const
CallInst
&a,
const
CallInst
&b)
301
{
302
return
(a.
uid
== b.
uid
)
303
&& (a.
inst
== b.
inst
);
304
}
305
306
inline
bool
operator!=
(
const
CallInst
&a,
const
CallInst
&b)
307
{
308
return
!
operator==
(a, b);
309
}
310
311
/**
312
* lexicographical comparison of CallInst objects
313
* @note we need it in order to place the objects into ordered containers
314
*/
315
inline
bool
operator<
(
const
CallInst
&a,
const
CallInst
&b)
316
{
317
// first compare uid
318
RETURN_IF_COMPARED
(a, b, uid);
319
320
// then compare inst
321
return
a.
inst
< b.
inst
;
322
}
323
324
/// a list of _program_ variables
325
typedef
std::vector<CVar>
TCVarList
;
326
327
/// a set of _program_ variables
328
typedef
std::set<CVar>
TCVarSet
;
329
330
/// only uninitialized or nullified blocks; generic arrays and strings need more
331
struct
UniformBlock
{
332
TOffset
off
;
///< relative placement of the block wrt. the root
333
TSizeOf
size
;
///< size of the block in bytes
334
TValId
tplValue
;
///< value you need to clone on object instantiation
335
};
336
337
/// a container used to return list of uniform blocks
338
typedef
std::map<TOffset, UniformBlock>
TUniBlockMap
;
339
340
/**
341
* lexicographical comparison of CVar objects
342
* @note we need it in order to place the objects into ordered containers
343
*/
344
inline
bool
operator<
(
const
CVar
&a,
const
CVar
&b)
345
{
346
// first compare uid
347
RETURN_IF_COMPARED
(a, b, uid);
348
349
// then compare inst
350
return
a.
inst
< b.
inst
;
351
}
352
353
class
FldList
;
354
class
SymHeap
;
355
356
/// SymHeapCore - the elementary representation of the state of program memory
357
class
SymHeapCore
{
358
public
:
359
/// create an empty symbolic heap
360
SymHeapCore
(
TStorRef
,
Trace::Node
*);
361
362
/// destruction of the symbolic heap invalidates all IDs of its entities
363
virtual
~SymHeapCore
();
364
365
/// relatively cheap operation as long as SH_COPY_ON_WRITE is enabled
366
SymHeapCore
(
const
SymHeapCore
&);
367
368
/// relatively cheap operation as long as SH_COPY_ON_WRITE is enabled
369
SymHeapCore
&
operator=
(
const
SymHeapCore
&);
370
371
/// exchange the contents with the other heap (works in constant time)
372
virtual
void
swap
(
SymHeapCore
&);
373
374
/// each symbolic heap is associated with a CodeStorage model of code
375
TStorRef
stor
()
const
{
return
stor_
; }
376
377
/// each symbolic heap is associated with a trace graph node
378
Trace::Node
*
traceNode
()
const
;
379
380
/// update the current trace graph node that the heap is associated with
381
void
traceUpdate
(
Trace::Node
*);
382
383
/// the last assigned ID of a heap entity (not necessarily still valid)
384
unsigned
lastId
()
const
;
385
386
public
:
387
/**
388
* collect all objects having the given value inside
389
* @param dst reference to a container to store the result to
390
* @param val ID of the value to look for
391
* @param liveOnly if true, exclude objects that are no longer alive
392
* @note The operation may return from 0 to n objects.
393
*/
394
void
usedBy
(
FldList
&dst,
TValId
val,
bool
liveOnly =
false
)
const
;
395
396
/// return how many objects have the value inside
397
unsigned
usedByCount
(
TValId
val)
const
;
398
399
/// return all objects that point at/inside the given object
400
void
pointedBy
(
FldList
&dst,
TObjId
)
const
;
401
402
/// return how many objects point at/inside the given object
403
unsigned
pointedByCount
(
TObjId
)
const
;
404
405
/// write an uninitialized or nullified block of memory
406
void
writeUniformBlock
(
407
TObjId
obj,
408
const
UniformBlock
&ub,
409
TValSet
*killedPtrs = 0);
410
411
/// copy 'size' bytes of raw memory from 'src' to 'dst'
412
void
copyBlockOfRawMemory
(
413
TValId
dst,
414
TValId
src,
415
TSizeOf
size,
416
TValSet
*killedPtrs = 0);
417
418
public
:
419
/// define an explicit Neq predicate
420
void
addNeq
(
TValId
v1,
TValId
v2);
421
422
/// remove an explicit Neq predicate if defined
423
void
delNeq
(
TValId
v1,
TValId
v2);
424
425
/// true if there is an @b explicit Neq relation over the given values
426
bool
chkNeq
(
TValId
v1,
TValId
v2)
const
;
427
428
/// collect values connect with the given value via an extra predicate
429
void
gatherRelatedValues
(
TValList
&dst,
TValId
val)
const
;
430
431
/// transfer as many as possible extra heap predicates from this to dst
432
void
copyRelevantPreds
(
SymHeapCore
&dst,
const
TValMap
&valMap)
const
;
433
434
/// true if all Neq predicates can be mapped to Neq predicates in ref
435
bool
matchPreds
(
436
const
SymHeapCore
&ref,
437
const
TValMap
&valMap,
438
bool
nonZeroOnly =
false
)
439
const
;
440
441
public
:
442
/// translate the given address by the given offset
443
TValId
valByOffset
(
TValId
,
TOffset
offset);
444
445
/// create (or recycle) a VT_RANGE value at the given allocated address
446
TValId
valByRange
(
TValId
at,
IR::Range
range);
447
448
/// translate the given value by the given offset
449
TValId
valShift
(
TValId
valToShift,
TValId
shiftBy);
450
451
/// classify the object the given value points to
452
EValueTarget
valTarget
(
TValId
)
const
;
453
454
/// classify where the given value originates from
455
EValueOrigin
valOrigin
(
TValId
)
const
;
456
457
/// return the target specifier of the given address
458
ETargetSpecifier
targetSpec
(
TValId
addr)
const
;
459
460
/// return the object that the given address points to
461
TObjId
objByAddr
(
TValId
addr)
const
;
462
463
/// classify the storage class of the given object
464
EStorageClass
objStorClass
(
TObjId
)
const
;
465
466
/// return size (in bytes) of the given object
467
TSizeRange
objSize
(
TObjId
)
const
;
468
469
/// target address at the given object with target specifier and offset
470
TValId
addrOfTarget
(
TObjId
,
ETargetSpecifier
,
TOffset
off = 0);
471
472
private
:
473
/// experimental implementation helper of rejoinObj(), do not use!
474
void
rewriteTargetOfBase
(
TValId
addr,
TObjId
target);
475
friend
void
redirectAddrs
(
SymHeap
&,
TObjId
,
TObjId
);
476
477
public
:
478
/// return the address of the root which the given value is binded to
479
TValId
valRoot
(
TValId
)
const
;
480
481
/// return the relative placement from the root
482
TOffset
valOffset
(
TValId
)
const
;
483
484
/// return the offset range associated with the given VT_RANGE value
485
IR::Range
valOffsetRange
(
TValId
)
const
;
486
487
/// narrow down the offset range of the given VT_RANGE value
488
void
valRestrictRange
(
TValId
,
IR::Range
win);
489
490
/// difference between two pointers (makes sense only for shared roots)
491
TValId
diffPointers
(
TValId
v1,
TValId
v2);
492
493
/// return count of bytes (including NULL) we can safely read as string
494
TSizeRange
valSizeOfString
(
TValId
)
const
;
495
496
/// return the region corresponding to the given program variable
497
TObjId
regionByVar
(
CVar
,
bool
createIfNeeded);
498
499
/// clone the given object, including the outgoing has-value edges
500
virtual
TObjId
objClone
(
TObjId
);
501
502
public
:
503
/// replace all occurrences of val by replaceBy
504
virtual
void
valReplace
(
TValId
val,
TValId
replaceBy);
505
506
/// return the list of objects satisfying the given filtering predicate
507
void
gatherObjects
(
TObjList
&dst,
bool
(*)(
EStorageClass
) = 0)
const
;
508
509
/// list of live fields (including ptrs) inside the given object
510
void
gatherLiveFields
(
FldList
&dst,
TObjId
)
const
;
511
512
/// list of uninitialized and nullified uniform blocks of the given obj
513
void
gatherUniformBlocks
(
TUniBlockMap
&dst,
TObjId
)
const
;
514
515
/// experimental optimization of joinUniBlocksCore()
516
bool
findCoveringUniBlocks
(
517
TUniBlockMap
*pCovered,
518
TObjId
root,
519
UniformBlock
block)
520
const
;
521
522
/// return program variable that the given object maps to
523
CVar
cVarByObject
(
TObjId
)
const
;
524
525
/**
526
* composite object given by val (applicable only on VT_COMPOSITE vals)
527
* @todo should we operate on FldHandle instead?
528
*/
529
TFldId
valGetComposite
(
TValId
val)
const
;
530
531
public
:
532
/// allocate a chunk of stack of known size from the select call stack
533
TObjId
stackAlloc
(
const
TSizeRange
&size,
const
CallInst
&from);
534
535
/// return true if the given object was allocated by stackAlloc()
536
bool
isAnonStackObj
(
TObjId
,
CallInst
*pFrom = 0);
537
538
/// clear the list of anonymous stack objects of the given call instance
539
void
clearAnonStackObjects
(
TObjList
&dst,
const
CallInst
&of);
540
541
/// allocate a chunk of heap of known size
542
TObjId
heapAlloc
(
const
TSizeRange
&size);
543
544
/// return true if the given object can be still accessed safely
545
bool
isValid
(
TObjId
)
const
;
546
547
/// invalidate the given object
548
virtual
void
objInvalidate
(
TObjId
);
549
550
/// update the estimated type-info of the given object
551
void
objSetEstimatedType
(
TObjId
obj, TObjType clt);
552
553
/// return the estimated type-info of the given object
554
TObjType
objEstimatedType
(
TObjId
obj)
const
;
555
556
/// create a @b generic value, otherwise use addrOfTarget()
557
TValId
valCreate
(
EValueTarget
code,
EValueOrigin
origin);
558
559
/// wrap a custom value, such as integer literal, or code pointer
560
TValId
valWrapCustom
(
CustomValue
data
);
561
562
/// unwrap a custom value, such as integer literal, or code pointer
563
const
CustomValue
&
valUnwrapCustom
(
TValId
)
const
;
564
565
public
:
566
/// prototype level of the given object (0 means not a prototype)
567
TProtoLevel
objProtoLevel
(
TObjId
)
const
;
568
569
/// set prototype level of the given boject (0 means not a prototype)
570
void
objSetProtoLevel
(
TObjId
obj,
TProtoLevel
level);
571
572
protected
:
573
/// return a @b data pointer inside the given object at the given offset
574
TFldId
ptrLookup
(
TObjId
obj,
TOffset
off);
575
576
/// return a field of the specified type at the specified offset in obj
577
TFldId
fldLookup
(
TObjId
obj,
TOffset
off, TObjType clt);
578
579
/// increment the external reference count of the given object
580
void
fldEnter
(
TFldId
);
581
582
/// decrement the external reference count (may trigger its destruction)
583
void
fldLeave
(
TFldId
);
584
585
/// FldHandle takes care of external reference count
586
friend
class
FldHandle
;
587
friend
class
PtrHandle
;
588
589
protected
:
590
// these should be accessed indirectly via FldHandle
591
TValId
valueOf
(
TFldId
fld);
592
TValId
placedAt
(
TFldId
fld);
593
TObjId
objByField
(
TFldId
fld)
const
;
594
TOffset
fieldOffset
(
TFldId
fld)
const
;
595
TObjType
fieldType
(
TFldId
fld)
const
;
596
void
setValOfField
(
TFldId
fld,
TValId
val,
TValSet
*killedPtrs = 0);
597
598
protected
:
599
TStorRef
stor_
;
600
601
private
:
602
struct
Private;
603
Private *
d
;
604
};
605
606
class
FldHandle
{
607
public
:
608
FldHandle
():
609
sh_
(0),
610
id_
(
FLD_INVALID
)
611
{
612
}
613
614
FldHandle
(
SymHeapCore
&
sh
,
TObjId
obj
, TObjType clt,
TOffset
off = 0):
615
sh_
(&sh),
616
id_
(sh.fldLookup(obj, off, clt))
617
{
618
if
(0 <
id_
)
619
sh_
->
fldEnter
(
id_
);
620
}
621
622
explicit
FldHandle
(
const
TFldId
special):
623
sh_
(0),
624
id_
(special)
625
{
626
CL_BREAK_IF
(0 < special);
627
}
628
629
FldHandle
(
const
FldHandle
&tpl):
630
sh_
(tpl.
sh_
),
631
id_
(tpl.
id_
)
632
{
633
if
(0 <
id_
)
634
sh_
->
fldEnter
(
id_
);
635
}
636
637
FldHandle
(
SymHeapCore
&
sh
,
const
FldHandle
&tpl):
638
sh_
(&sh),
639
id_
(tpl.
id_
)
640
{
641
if
(0 <
id_
)
642
sh_
->
fldEnter
(
id_
);
643
}
644
645
~FldHandle
() {
646
if
(0 <
id_
)
647
sh_
->
fldLeave
(
id_
);
648
}
649
650
FldHandle
&
operator=
(
const
FldHandle
&tpl) {
651
if
(0 <
id_
)
652
sh_
->
fldLeave
(
id_
);
653
654
sh_
= tpl.
sh_
;
655
id_
= tpl.
id_
;
656
if
(0 <
id_
)
657
sh_
->
fldEnter
(
id_
);
658
659
return
*
this
;
660
}
661
662
public
:
663
/// return the SymHeapCore instance associated with this handle
664
SymHeapCore
*
sh
()
const
{
return
sh_
; }
665
666
/// return raw field ID inside this handle (used mainly internally)
667
TFldId
fieldId
()
const
{
return
id_
; }
668
669
/// true if the given handle is valid (does not imply field validity)
670
bool
isValidHandle
()
const
{
return
(0 <
id_
); }
671
672
/// return the object that the field is part of
673
TObjId
obj
()
const
{
return
sh_
->
objByField
(
id_
); }
674
675
/// return the offset at which the field is placed within the object
676
TOffset
offset
()
const
{
return
sh_
->
fieldOffset
(
id_
); }
677
678
/// return the value inside the field (may trigger its initialization)
679
TValId
value
()
const
{
return
sh_
->
valueOf
(
id_
); }
680
681
/// return the address of the field (may trigger address instantiation)
682
TValId
placedAt
()
const
{
return
sh_
->
placedAt
(
id_
); }
683
684
/// static type-info of the given object (return 0 if not available)
685
TObjType
type
()
const
{
686
return
(this->
isValidHandle
())
687
?
sh_
->
fieldType
(
id_
)
688
: 0;
689
}
690
691
/// assign the given value, caller is responsible for garbage collecting
692
void
setValue
(
const
TValId
val,
TValSet
*killedPtrs = 0)
const
{
693
sh_
->
setValOfField
(
id_
, val, killedPtrs);
694
}
695
696
protected
:
697
FldHandle
(
SymHeapCore
&
sh
,
TFldId
id
):
698
sh_
(&sh),
699
id_
(id)
700
{
701
if
(0 <
id_
)
702
sh_
->
fldEnter
(
id_
);
703
}
704
705
friend
class
SymHeapCore
;
706
707
// TODO: remove this
708
friend
class
SymProc
;
709
710
// TODO: remove this
711
friend
const
char
*
valNullLabel
(
const
SymHeapCore
&,
TFldId
);
712
713
protected
:
714
SymHeapCore
*
sh_
;
715
TFldId
id_
;
716
};
717
718
/// this allows to insert FldHandle instances into std::set
719
inline
bool
operator<
(
const
FldHandle
&a,
const
FldHandle
&b)
720
{
721
// first compare heap addresses
722
RETURN_IF_COMPARED
(a, b,
sh
());
723
724
// then compare field IDs
725
return
(a.
fieldId
() < b.
fieldId
());
726
}
727
728
inline
bool
operator==
(
const
FldHandle
&a,
const
FldHandle
&b)
729
{
730
return
(a.
sh
() == b.
sh
())
731
&& (a.
fieldId
() == b.
fieldId
());
732
}
733
734
inline
bool
operator!=
(
const
FldHandle
&a,
const
FldHandle
&b)
735
{
736
return
!
operator==
(a, b);
737
}
738
739
class
PtrHandle
:
public
FldHandle
{
740
public
:
741
PtrHandle
(
SymHeapCore
&
sh
,
const
TObjId
obj
,
const
TOffset
off = 0):
742
FldHandle
(sh, sh.ptrLookup(obj, off))
743
{
744
if
(0 <
id_
)
745
sh_
->
fldEnter
(
id_
);
746
}
747
};
748
749
/// ugly, but typedefs do not support partial declarations
750
class
FldList
:
public
std::vector<FldHandle> { };
751
752
/// set of object handles
753
typedef
std::set<FldHandle>
TFldSet
;
754
755
/// a type used for minimal segment length (0+, 1+, ...)
756
typedef
short
TMinLen
;
757
758
/// enumeration of abstract object (although OK_REGION is not abstract)
759
enum
EObjKind
{
760
OK_REGION
= 0,
///< concrete object (not a segment)
761
OK_SLS
,
///< singly-linked list segment
762
OK_DLS
,
///< doubly-linked list segment
763
OK_OBJ_OR_NULL
,
///< 0..1 object, assume NULL if not allocated
764
OK_SEE_THROUGH
,
///< 0..1 object, see through if not allocated
765
OK_SEE_THROUGH_2N
///< OK_SEE_THROUGH with two next pointers
766
};
767
768
inline
bool
isMayExistObj
(
const
enum
EObjKind
kind)
769
{
770
switch
(kind) {
771
case
OK_OBJ_OR_NULL
:
772
case
OK_SEE_THROUGH
:
773
case
OK_SEE_THROUGH_2N
:
774
return
true
;
775
776
default
:
777
return
false
;
778
}
779
}
780
781
/// tuple of binding offsets assigned to abstract objects
782
struct
BindingOff
{
783
TOffset
head
;
///< target offset
784
TOffset
next
;
///< offset of the 'next' or 'r' pointer
785
TOffset
prev
;
///< offset of the 'prev' or 'l' pointer
786
787
BindingOff
():
788
head
(0),
789
next
(0),
790
prev
(0)
791
{
792
}
793
794
BindingOff
(
EObjKind
kind):
795
head
(-1),
796
next
(-1),
797
prev
(-1)
798
{
799
CL_BREAK_IF
(
OK_OBJ_OR_NULL
!= kind);
800
(void) kind;
801
}
802
};
803
804
/// point-wise comparison of BindingOff
805
inline
bool
operator==
(
const
BindingOff
&off1,
const
BindingOff
&off2)
806
{
807
return
off1.
head
== off2.
head
808
&& off1.
next
== off2.
next
809
&& off1.
prev
== off2.
prev
;
810
}
811
812
/// point-wise comparison of BindingOff
813
inline
bool
operator!=
(
const
BindingOff
&off1,
const
BindingOff
&off2)
814
{
815
return
!
operator==
(off1, off2);
816
}
817
818
/// lexicographical comparison of BindingOff, need for std::map
819
inline
bool
operator<
(
const
BindingOff
&off1,
const
BindingOff
&off2)
820
{
821
RETURN_IF_COMPARED
(off1, off2, next);
822
RETURN_IF_COMPARED
(off1, off2, prev);
823
return
(off1.
head
< off2.
head
);
824
}
825
826
/// extension of SymHeapCore dealing with abstract objects (list segments etc.)
827
class
SymHeap
:
public
SymHeapCore
{
828
public
:
829
/// create an empty symbolic heap
830
SymHeap
(
TStorRef
,
Trace::Node
*);
831
832
/// destruction of the symbolic heap invalidates all IDs of its entities
833
virtual
~SymHeap
();
834
835
/// relatively cheap operation as long as SH_COPY_ON_WRITE is enabled
836
SymHeap
(
const
SymHeap
&);
837
838
/// relatively cheap operation as long as SH_COPY_ON_WRITE is enabled
839
SymHeap
&
operator=
(
const
SymHeap
&);
840
841
virtual
void
swap
(
SymHeapCore
&);
842
843
public
:
844
/// kind of object (region, SLS, DLS, ...)
845
EObjKind
objKind
(
TObjId
)
const
;
846
847
/// tuple of binding offsets (next, prev, ...)
848
const
BindingOff
&
segBinding
(
TObjId
seg)
const
;
849
850
/// set properties of an abstract object, set abstract if not already
851
void
objSetAbstract
(
852
TObjId
seg,
853
EObjKind
kind,
854
const
BindingOff
&off);
855
856
/// set the given abstract object to be a concrete object (drops props)
857
void
objSetConcrete
(
TObjId
);
858
859
/// read the minimal segment length of the given abstract object
860
TMinLen
segMinLength
(
TObjId
seg)
const
;
861
862
/// assign the minimal segment length of the given abstract object
863
void
segSetMinLength
(
TObjId
seg, TMinLen len);
864
865
public
:
866
// just overrides (inherits the dox)
867
virtual
void
objInvalidate
(
TObjId
);
868
virtual
TObjId
objClone
(
TObjId
);
869
870
private
:
871
struct
Private;
872
Private *
d
;
873
};
874
875
/// enable/disable built-in self-checks (takes effect only in debug build)
876
void
enableProtectedMode
(
bool
enable);
877
878
/// temporarily disable protected mode of SymHeap in a debug build
879
class
ProtectionIntrusion
{
880
public
:
881
ProtectionIntrusion
() {
882
enableProtectedMode
(
false
);
883
}
884
885
~ProtectionIntrusion
() {
886
enableProtectedMode
(
true
);
887
}
888
};
889
890
#endif
/* H_GUARD_SYM_HEAP_H */
Generated on Mon Nov 9 2015 14:51:59 for Predator by
1.8.1.2