Line data Source code
1 : /* Classes for modeling the state of memory.
2 : Copyright (C) 2020-2026 Free Software Foundation, Inc.
3 : Contributed by David Malcolm <dmalcolm@redhat.com>.
4 :
5 : This file is part of GCC.
6 :
7 : GCC is free software; you can redistribute it and/or modify it
8 : under the terms of the GNU General Public License as published by
9 : the Free Software Foundation; either version 3, or (at your option)
10 : any later version.
11 :
12 : GCC is distributed in the hope that it will be useful, but
13 : WITHOUT ANY WARRANTY; without even the implied warranty of
14 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 : General Public License for more details.
16 :
17 : You should have received a copy of the GNU General Public License
18 : along with GCC; see the file COPYING3. If not see
19 : <http://www.gnu.org/licenses/>. */
20 :
21 : #ifndef GCC_ANALYZER_STORE_H
22 : #define GCC_ANALYZER_STORE_H
23 :
24 : #include "text-art/tree-widget.h"
25 : #include "analyzer/complexity.h"
26 : #include "analyzer/concrete-ranges.h"
27 : #include "analyzer/symbolic-ranges.h"
28 : #include "analyzer/symbolic-bit-contents.h"
29 : #include "analyzer/symbolic-memory-ranges.h"
30 :
31 : /* Implementation of the region-based ternary model described in:
32 : "A Memory Model for Static Analysis of C Programs"
33 : (Zhongxing Xu, Ted Kremenek, and Jian Zhang)
34 : http://lcs.ios.ac.cn/~xuzb/canalyze/memmodel.pdf */
35 :
36 : /* Binding clusters
37 : ================
38 :
39 : The store models memory as a collection of "clusters", where regions
40 : are partitioned into clusters via their base region.
41 :
42 : For example, given:
43 : int a, b, c;
44 : struct coord { double x; double y; } verts[3];
45 : then "verts[0].y" and "verts[1].x" both have "verts" as their base region.
46 : Each of a, b, c, and verts will have their own clusters, so that we
47 : know that writes to e.g. "verts[1].x".don't affect e.g. "a".
48 :
49 : For each cluster that's been touched by the user's code we track an
50 : immutable bit_contents instance, updating it to point to a different
51 : bit_contents instance after each change.
52 :
53 : Handling symbolic regions requires us to handle aliasing.
54 :
55 : In the example above, each of a, b, c and verts are non-symbolic
56 : base regions and so their clusters are "concrete clusters", whereas given:
57 : struct coord *p, *q;
58 : then "*p" and "*q" are symbolic base regions, and thus "*p" and "*q"
59 : have "symbolic clusters".
60 :
61 : In the above, "verts[i].x" will have a symbolic *binding* within a
62 : concrete cluster for "verts", whereas "*p" is a symbolic *cluster*.
63 :
64 : Writes to concrete clusters can't affect other concrete clusters,
65 : but can affect symbolic clusters; e.g. after:
66 : verts[0].x = 42;
67 : we bind 42 in the cluster for "verts", but the clusters for "b" and "c"
68 : can't be affected. Any symbolic clusters for *p and for *q can be
69 : affected, *p and *q could alias "verts".
70 :
71 : Writes to a symbolic cluster can affect other clusters, both
72 : concrete and symbolic; e.g. after:
73 : p->x = 17;
74 : we bind 17 within the cluster for "*p". The concrete clusters for a, b,
75 : c, and verts could be affected, depending on whether *p aliases them.
76 : Similarly, the symbolic cluster to *q could be affected.
77 :
78 :
79 : Tracking the state within a binding cluster
80 : ===========================================
81 :
82 : Reads and writes to memory are handled as reading and writing bits to
83 : a cluster, where the memory ranges relative to the start of the cluster
84 : can be either fully concrete, or be symbolic (with a symbolic start offset
85 : and/or size).
86 :
87 : Consider this example (taken from
88 : gcc/testsuite/c-c++-common/analyzer/symbolic-1.c, adding calls to
89 : __analyzer_dump (); at the pertinent places):
90 :
91 : char arr[1024];
92 : arr[2] = a; (1)
93 : arr[3] = b; (2)
94 : After (1) and (2), we have this state:
95 : | program_state
96 : | ╰─ Region Model
97 : | ├─ Current Frame: frame: ‘test_1’@1
98 : | ╰─ Store
99 : | ├─ m_called_unknown_fn: false
100 : | ╰─ frame: ‘test_1’@1
101 : | ╰─ arr:
102 : | ╰─ (616): concrete bit overlay
103 : | ├─ concrete ranges
104 : | │ ├─ [byte 2]: (605): bit_vector_from_svalue[size: 1 byte]
105 : | │ │ ╰─ m_sval: (604): ‘char’: initial_svalue
106 : | │ │ ├─ value_range: {[irange] char VARYING}
107 : | │ │ ╰─ m_reg: (601): ‘char’: decl_region(‘a_48(D)’)
108 : | │ │ ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
109 : | │ │ ╰─ parent: (1): stack region
110 : | │ │ ╰─ parent: (0): root region
111 : | │ ╰─ [byte 3]: (613): bit_vector_from_svalue[size: 1 byte]
112 : | │ ╰─ m_sval: (612): ‘char’: initial_svalue
113 : | │ ├─ value_range: {[irange] char VARYING}
114 : | │ ╰─ m_reg: (611): ‘char’: decl_region(‘b_50(D)’)
115 : | │ ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
116 : | │ ╰─ {as above; descendents: 3, depth: 3}
117 : | ╰─ baseline: (7): uninitialized contents
118 : The cluster for "arr" has a concrete_bit_overlay for its contents,
119 : with bytes 2 and 3 bound to bit_vectors for the target encoding
120 : of svalues for the initial values of "a" and "b" respectively. This
121 : is overlaid on top of the baseline "uninitialized" everywhere else, so
122 : that attempting to query e.g. arr[4] will return "uninitialized".
123 :
124 : "a" and "b" are each in their own clusters, with no explicit
125 : bindings, and thus have their "implicit contents": in this case
126 : concrete_bit_overlay instances bound at [0..sizeof(int)) to the bit
127 : vectors for the initial_svalue of "a" and "b" respectively.
128 :
129 : arr[3] = c; (3)
130 : After (3), the contents of the cluster for "arr" has been replaced by
131 : a new concrete_bit_overlay instance, the same as the previous one,
132 : but with byte 3 now bound to a bit vector for the
133 : initial_svalue for "c":
134 : | program_state
135 : | ╰─ Region Model
136 : | ├─ Current Frame: frame: ‘test_1’@1
137 : | ╰─ Store
138 : | ├─ m_called_unknown_fn: false
139 : | ╰─ frame: ‘test_1’@1
140 : | ╰─ arr:
141 : | ╰─ (648): concrete bit overlay
142 : | ├─ concrete ranges
143 : | │ ├─ [byte 2]: (605): bit_vector_from_svalue[size: 1 byte]
144 : | │ │ ╰─ m_sval: (604): ‘char’: initial_svalue
145 : | │ │ ├─ value_range: {[irange] char VARYING}
146 : | │ │ ╰─ m_reg: (601): ‘char’: decl_region(‘a_48(D)’)
147 : | │ │ ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
148 : | │ │ ╰─ parent: (1): stack region
149 : | │ │ ╰─ parent: (0): root region
150 : | │ ╰─ [byte 3]: (645): bit_vector_from_svalue[size: 1 byte]
151 : | │ ╰─ m_sval: (644): ‘char’: initial_svalue
152 : | │ ├─ value_range: {[irange] char VARYING}
153 : | │ ╰─ m_reg: (643): ‘char’: decl_region(‘c_55(D)’)
154 : | │ ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
155 : | │ ╰─ {as above; descendents: 3, depth: 3}
156 : | ╰─ baseline: (7): uninitialized contents
157 : Note that the concrete_bit_overlay (and other bit_contents instances)
158 : are immutable and pure-functional - when a cluster is written to, we
159 : update the cluster's m_contents to point to a different bit_contents.
160 :
161 : arr[i] = d; (4)
162 : After the write to the symbolic array index at (4), the cluster for
163 : "arr" no longer uses the concrete_bit_overlay and instead points to
164 : a symbolic_bit_overlay, where the bytes at element [i] are bound to
165 : the bit_vector fot the initial value of "d":
166 : | program_state
167 : | ╰─ Region Model
168 : | ├─ Current Frame: frame: ‘test_1’@1
169 : | ╰─ Store
170 : | ├─ m_called_unknown_fn: false
171 : | ╰─ frame: ‘test_1’@1
172 : | ╰─ arr:
173 : | ╰─ (670): symbolic bit overlay
174 : | ├─ symbolic ranges
175 : | │ ├─ symbolic range
176 : | │ │ ├─ start offset: (571): bits_from_bytes_scalar
177 : | │ │ │ ╰─ (570): scalar_from_svalue<bytes>
178 : | │ │ │ ╰─ (565): ‘int’: initial_svalue
179 : | │ │ │ ├─ value_range: {[irange] int VARYING}
180 : | │ │ │ ╰─ m_reg: (564): ‘int’: decl_region(‘i_61(D)’)
181 : | │ │ │ ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
182 : | │ │ │ ╰─ parent: (1): stack region
183 : | │ │ │ ╰─ parent: (0): root region
184 : | │ │ ╰─ size: (11): concrete_scalar<bits>: 8
185 : | │ ╰─ (657): bit_vector_from_svalue[size: 1 byte]
186 : | │ ╰─ m_sval: (656): ‘char’: initial_svalue
187 : | │ ├─ value_range: {[irange] char VARYING}
188 : | │ ╰─ m_reg: (655): ‘char’: decl_region(‘d_62(D)’)
189 : | │ ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
190 : | │ ╰─ {as above; descendents: 3, depth: 3}
191 : | ╰─ baseline: (669): untracked_bit_contents
192 : | ╰─ maybe live values
193 : | ├─ (605): bit_vector_from_svalue[size: 1 byte]
194 : | │ ╰─ m_sval: (604): ‘char’: initial_svalue
195 : | │ ├─ value_range: {[irange] char VARYING}
196 : | │ ╰─ m_reg: (601): ‘char’: decl_region(‘a_48(D)’)
197 : | │ ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
198 : | │ ╰─ {as above; descendents: 3, depth: 3}
199 : | ╰─ (645): bit_vector_from_svalue[size: 1 byte]
200 : | ╰─ m_sval: (644): ‘char’: initial_svalue
201 : | ├─ value_range: {[irange] char VARYING}
202 : | ╰─ m_reg: (643): ‘char’: decl_region(‘c_55(D)’)
203 : | ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
204 : | ╰─ {as above; descendents: 3, depth: 3}
205 : We also set the baseline for this overlay to an untracked_bit_contents
206 : instance. This indicates that we've given up on tracking the contents
207 : of "arr" at other locations (reads will return "unknown", rather than
208 : "uninitialized"). The untracked_bit_contents has a set of values that
209 : are "maybe live", capturing that the initial values of "a" and "c" may
210 : still be live within "arr" (to avoid leak false +ves), since we don't
211 : know if i == 3 or 4.
212 :
213 : Note how the IDs of the "maybe live values" nodes below match those
214 : within the concrete_bit_overlay above: the symbolic::node instances
215 : persist through the analysis.
216 :
217 : arr[j] = e; (5)
218 : After (5), the user's code has written to a possibly-different
219 : symbolic index within "arr", so we have a new symbolic_bit_overlay,
220 : binding the byte at [j] to the bit vector for the initial value of "e",
221 : and the "maybe live values" has gained the value that was at [i], since
222 : we don't know whether j == i (or j == 3, or j == 4):
223 : | program_state
224 : | ╰─ Region Model
225 : | ├─ Current Frame: frame: ‘test_1’@1
226 : | ╰─ Store
227 : | ├─ m_called_unknown_fn: false
228 : | ╰─ frame: ‘test_1’@1
229 : | ╰─ arr:
230 : | ╰─ (685): symbolic bit overlay
231 : | ├─ symbolic ranges
232 : | │ ├─ symbolic range
233 : | │ │ ├─ start offset: (590): bits_from_bytes_scalar
234 : | │ │ │ ╰─ (589): scalar_from_svalue<bytes>
235 : | │ │ │ ╰─ (584): ‘int’: initial_svalue
236 : | │ │ │ ├─ value_range: {[irange] int VARYING}
237 : | │ │ │ ╰─ m_reg: (583): ‘int’: decl_region(‘j_68(D)’)
238 : | │ │ │ ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
239 : | │ │ │ ╰─ parent: (1): stack region
240 : | │ │ │ ╰─ parent: (0): root region
241 : | │ │ ╰─ size: (11): concrete_scalar<bits>: 8
242 : | │ ╰─ (676): bit_vector_from_svalue[size: 1 byte]
243 : | │ ╰─ m_sval: (675): ‘char’: initial_svalue
244 : | │ ├─ value_range: {[irange] char VARYING}
245 : | │ ╰─ m_reg: (674): ‘char’: decl_region(‘e_69(D)’)
246 : | │ ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
247 : | │ ╰─ {as above; descendents: 3, depth: 3}
248 : | ╰─ baseline: (684): untracked_bit_contents
249 : | ╰─ maybe live values
250 : | ├─ (605): bit_vector_from_svalue[size: 1 byte]
251 : | │ ╰─ m_sval: (604): ‘char’: initial_svalue
252 : | │ ├─ value_range: {[irange] char VARYING}
253 : | │ ╰─ m_reg: (601): ‘char’: decl_region(‘a_48(D)’)
254 : | │ ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
255 : | │ ╰─ {as above; descendents: 3, depth: 3}
256 : | ├─ (645): bit_vector_from_svalue[size: 1 byte]
257 : | │ ╰─ m_sval: (644): ‘char’: initial_svalue
258 : | │ ├─ value_range: {[irange] char VARYING}
259 : | │ ╰─ m_reg: (643): ‘char’: decl_region(‘c_55(D)’)
260 : | │ ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
261 : | │ ╰─ {as above; descendents: 3, depth: 3}
262 : | ╰─ (657): bit_vector_from_svalue[size: 1 byte]
263 : | ╰─ m_sval: (656): ‘char’: initial_svalue
264 : | ├─ value_range: {[irange] char VARYING}
265 : | ╰─ m_reg: (655): ‘char’: decl_region(‘d_62(D)’)
266 : | ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
267 : | ╰─ {as above; descendents: 3, depth: 3}
268 :
269 : arr[3] = f; (6)
270 : After (6), we have a concrete_bit_overlay again, this, with a binding
271 : at byte [3], where the baseline is an untracked_bit_contents, with all
272 : the various other values we're written into "arr" as "maybe live":
273 : | program_state
274 : | ╰─ Region Model
275 : | ├─ Current Frame: frame: ‘test_1’@1
276 : | ╰─ Store
277 : | ├─ m_called_unknown_fn: false
278 : | ╰─ frame: ‘test_1’@1
279 : | ╰─ arr:
280 : | ╰─ (691): concrete bit overlay
281 : | ├─ concrete ranges
282 : | │ ╰─ [byte 3]: (688): bit_vector_from_svalue[size: 1 byte]
283 : | │ ╰─ m_sval: (687): ‘char’: initial_svalue
284 : | │ ├─ value_range: {[irange] char VARYING}
285 : | │ ╰─ m_reg: (686): ‘char’: decl_region(‘f_74(D)’)
286 : | │ ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
287 : | │ ╰─ parent: (1): stack region
288 : | │ ╰─ parent: (0): root region
289 : | ╰─ baseline: (690): untracked_bit_contents
290 : | ╰─ maybe live values
291 : | ├─ (605): bit_vector_from_svalue[size: 1 byte]
292 : | │ ╰─ m_sval: (604): ‘char’: initial_svalue
293 : | │ ├─ value_range: {[irange] char VARYING}
294 : | │ ╰─ m_reg: (601): ‘char’: decl_region(‘a_48(D)’)
295 : | │ ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
296 : | │ ╰─ {as above; descendents: 3, depth: 3}
297 : | ├─ (645): bit_vector_from_svalue[size: 1 byte]
298 : | │ ╰─ m_sval: (644): ‘char’: initial_svalue
299 : | │ ├─ value_range: {[irange] char VARYING}
300 : | │ ╰─ m_reg: (643): ‘char’: decl_region(‘c_55(D)’)
301 : | │ ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
302 : | │ ╰─ {as above; descendents: 3, depth: 3}
303 : | ├─ (657): bit_vector_from_svalue[size: 1 byte]
304 : | │ ╰─ m_sval: (656): ‘char’: initial_svalue
305 : | │ ├─ value_range: {[irange] char VARYING}
306 : | │ ╰─ m_reg: (655): ‘char’: decl_region(‘d_62(D)’)
307 : | │ ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
308 : | │ ╰─ {as above; descendents: 3, depth: 3}
309 : | ╰─ (676): bit_vector_from_svalue[size: 1 byte]
310 : | ╰─ m_sval: (675): ‘char’: initial_svalue
311 : | ├─ value_range: {[irange] char VARYING}
312 : | ╰─ m_reg: (674): ‘char’: decl_region(‘e_69(D)’)
313 : | ╰─ parent: (522): frame_region(‘test_1’, index: 0, depth: 1)
314 : | ╰─ {as above; descendents: 3, depth: 3}
315 : */
316 :
317 :
318 : namespace ana {
319 :
320 : /* A class for keeping track of aspects of a program_state that we don't
321 : know about, to avoid false positives about leaks.
322 :
323 : Consider:
324 :
325 : p->field = malloc (1024);
326 : q->field = NULL;
327 :
328 : where we don't know whether or not p and q point to the same memory,
329 : and:
330 :
331 : p->field = malloc (1024);
332 : unknown_fn (p);
333 :
334 : In both cases, the svalue for the address of the allocated buffer
335 : goes from being bound to p->field to not having anything explicitly bound
336 : to it.
337 :
338 : Given that we conservatively discard bindings due to possible aliasing or
339 : calls to unknown function, the store loses references to svalues,
340 : but these svalues could still be live. We don't want to warn about
341 : them leaking - they're effectively in a "maybe live" state.
342 :
343 : This "maybe live" information is somewhat transient.
344 :
345 : We don't want to store this "maybe live" information in the program_state,
346 : region_model, or store, since we don't want to bloat these objects (and
347 : potentially bloat the exploded_graph with more nodes).
348 : However, we can't store it in the region_model_context, as these context
349 : objects sometimes don't last long enough to be around when comparing the
350 : old vs the new state.
351 :
352 : This class is a way to track a set of such svalues, so that we can
353 : temporarily capture that they are in a "maybe live" state whilst
354 : comparing old and new states. */
355 :
356 956689 : class uncertainty_t
357 : {
358 : public:
359 : typedef hash_set<const symbolic::value_node *>::iterator iterator;
360 :
361 : void on_maybe_bound_value (const symbolic::value_node &val);
362 : void on_mutable_value_at_unknown_call (const symbolic::value_node &val);
363 :
364 : bool unknown_sm_state_p (const svalue *sval);
365 :
366 : void add_bit_contents (const symbolic::bit_contents &bc);
367 :
368 : void dump () const;
369 : void dump_to_logger (logger &) const;
370 :
371 : std::unique_ptr<text_art::tree_widget>
372 : make_dump_widget (symbolic::node_dump_state &nds) const;
373 :
374 383020 : iterator begin_maybe_bound_svals () const
375 : {
376 383020 : return m_maybe_bound_vals.begin ();
377 : }
378 410211 : iterator end_maybe_bound_svals () const
379 : {
380 410211 : return m_maybe_bound_vals.end ();
381 : }
382 :
383 : private:
384 :
385 : /* Values that might or might not still be bound. */
386 : hash_set<const symbolic::value_node *> m_maybe_bound_vals;
387 :
388 : /* Values that have mutable sm-state at unknown calls. */
389 : hash_set<const symbolic::value_node *> m_mutable_at_unknown_call_vals;
390 : };
391 :
392 : class byte_range;
393 :
394 : // TODO: eliminate this in favor of concrete_bit_range:
395 : /* A concrete range of bits. */
396 :
397 : struct bit_range
398 : {
399 146 : bit_range (bit_offset_t start_bit_offset, bit_size_t size_in_bits)
400 194 : : m_start_bit_offset (start_bit_offset),
401 178 : m_size_in_bits (size_in_bits)
402 : {}
403 :
404 : void dump_to_pp (pretty_printer *pp) const;
405 : void dump () const;
406 :
407 : std::unique_ptr<json::object> to_json () const;
408 :
409 0 : bool empty_p () const
410 : {
411 0 : return m_size_in_bits == 0;
412 : }
413 :
414 354 : bit_offset_t get_start_bit_offset () const
415 : {
416 186 : return m_start_bit_offset;
417 : }
418 8 : bit_offset_t get_next_bit_offset () const
419 : {
420 104 : return m_start_bit_offset + m_size_in_bits;
421 : }
422 0 : bit_offset_t get_last_bit_offset () const
423 : {
424 0 : gcc_assert (!empty_p ());
425 0 : return get_next_bit_offset () - 1;
426 : }
427 :
428 0 : bool contains_p (bit_offset_t offset) const
429 : {
430 0 : return (offset >= get_start_bit_offset ()
431 0 : && offset < get_next_bit_offset ());
432 : }
433 :
434 : bool contains_p (const bit_range &other, bit_range *out) const;
435 :
436 : bool operator== (const bit_range &other) const
437 : {
438 : return (m_start_bit_offset == other.m_start_bit_offset
439 : && m_size_in_bits == other.m_size_in_bits);
440 : }
441 :
442 88 : bool intersects_p (const bit_range &other) const
443 : {
444 88 : return (get_start_bit_offset () < other.get_next_bit_offset ()
445 160 : && other.get_start_bit_offset () < get_next_bit_offset ());
446 : }
447 : bool intersects_p (const bit_range &other,
448 : bit_size_t *out_num_overlap_bits) const;
449 : bool intersects_p (const bit_range &other,
450 : bit_range *out_this,
451 : bit_range *out_other) const;
452 :
453 : bool exceeds_p (const bit_range &other,
454 : bit_range *out_overhanging_bit_range) const;
455 :
456 : bool falls_short_of_p (bit_offset_t offset,
457 : bit_range *out_fall_short_bits) const;
458 :
459 : static int cmp (const bit_range &br1, const bit_range &br2);
460 :
461 : bit_range operator- (bit_offset_t offset) const;
462 :
463 : bool as_byte_range (byte_range *out) const;
464 :
465 : bool
466 : operator< (const bit_range &other) const
467 : {
468 : if (m_start_bit_offset < other.m_start_bit_offset)
469 : return true;
470 : if (m_start_bit_offset > other.m_start_bit_offset)
471 : return false;
472 : return (m_size_in_bits < other.m_size_in_bits);
473 : }
474 :
475 : hashval_t hash () const
476 : {
477 : inchash::hash hstate;
478 : hstate.add_wide_int (m_start_bit_offset);
479 : hstate.add_wide_int (m_size_in_bits);
480 : return hstate.end ();
481 : }
482 :
483 : bit_offset_t m_start_bit_offset;
484 : bit_size_t m_size_in_bits;
485 : };
486 :
487 : inline concrete::range<integer_with_unit<units::bit>>
488 130 : convert_from_bit_range (bit_range old_bits)
489 : {
490 130 : return concrete::range<integer_with_unit<units::bit>>
491 260 : (convert_from_bit_offset_t (old_bits.get_start_bit_offset ()),
492 260 : convert_from_bit_size_t (old_bits.m_size_in_bits));
493 : }
494 :
495 : inline bit_range
496 : convert_to_bit_range (concrete::range<integer_with_unit<units::bit>> new_bits)
497 : {
498 : return bit_range
499 : (convert_to_bit_offset_t (new_bits.get_start_offset ()),
500 : convert_to_bit_size_t (new_bits.get_size ()));
501 : }
502 :
503 : // TODO: eliminate this in favor of concrete_byte_range:
504 : /* A concrete range of bytes. */
505 :
506 : struct byte_range
507 : {
508 0 : byte_range (byte_offset_t start_byte_offset, byte_size_t size_in_bytes)
509 0 : : m_start_byte_offset (start_byte_offset),
510 0 : m_size_in_bytes (size_in_bytes)
511 : {}
512 :
513 : void dump_to_pp (pretty_printer *pp) const;
514 : void dump () const;
515 :
516 : std::unique_ptr<json::object> to_json () const;
517 :
518 0 : bool empty_p () const
519 : {
520 0 : return m_size_in_bytes == 0;
521 : }
522 :
523 0 : bool contains_p (byte_offset_t offset) const
524 : {
525 0 : return (offset >= get_start_byte_offset ()
526 0 : && offset < get_next_byte_offset ());
527 : }
528 : bool contains_p (const byte_range &other, byte_range *out) const;
529 :
530 : bool operator== (const byte_range &other) const
531 : {
532 : return (m_start_byte_offset == other.m_start_byte_offset
533 : && m_size_in_bytes == other.m_size_in_bytes);
534 : }
535 :
536 0 : byte_offset_t get_start_byte_offset () const
537 : {
538 0 : return m_start_byte_offset;
539 : }
540 0 : byte_offset_t get_next_byte_offset () const
541 : {
542 0 : return m_start_byte_offset + m_size_in_bytes;
543 : }
544 0 : byte_offset_t get_last_byte_offset () const
545 : {
546 0 : gcc_assert (!empty_p ());
547 0 : return m_start_byte_offset + m_size_in_bytes - 1;
548 : }
549 :
550 : bit_range as_bit_range () const
551 : {
552 : return bit_range (m_start_byte_offset * BITS_PER_UNIT,
553 : m_size_in_bytes * BITS_PER_UNIT);
554 : }
555 :
556 : bit_offset_t get_start_bit_offset () const
557 : {
558 : return m_start_byte_offset * BITS_PER_UNIT;
559 : }
560 : bit_offset_t get_next_bit_offset () const
561 : {
562 : return get_next_byte_offset () * BITS_PER_UNIT;
563 : }
564 : bit_size_t get_size_in_bits () const
565 : {
566 : return m_size_in_bytes * BITS_PER_UNIT;
567 : }
568 :
569 : static int cmp (const byte_range &br1, const byte_range &br2);
570 :
571 : byte_offset_t m_start_byte_offset;
572 : byte_size_t m_size_in_bytes;
573 : };
574 :
575 : /* All of the bindings within a store for regions that share the same
576 : base region.
577 :
578 : Invariants:
579 : - the region must be a base region
580 : - region->tracked_p () must be true
581 : - region->symbolic_for_unknown_ptr_p () must be false (we must not be
582 : dereferencing an UNKNOWN ptr). */
583 :
584 : class binding_cluster
585 : {
586 : public:
587 : friend class store;
588 :
589 : binding_cluster (symbolic::node_manager &node_mgr,
590 : const region *base_region,
591 : const symbolic::bit_contents &contents);
592 : binding_cluster (const binding_cluster &other);
593 : binding_cluster& operator=(const binding_cluster &other);
594 :
595 : bool operator== (const binding_cluster &other) const;
596 1908648 : bool operator!= (const binding_cluster &other) const
597 : {
598 1908648 : return !(*this == other);
599 : }
600 :
601 : hashval_t hash () const;
602 :
603 : bool symbolic_p () const;
604 :
605 172 : const region *get_base_region () const { return m_base_region; }
606 :
607 : void dump () const;
608 :
609 : void validate () const;
610 :
611 : std::unique_ptr<json::object> to_json () const;
612 :
613 : std::unique_ptr<text_art::tree_widget>
614 : make_dump_widget (symbolic::node_dump_state &nds) const;
615 :
616 : const symbolic::bit_vector &
617 : get_bits (symbolic_bit_range bit_range) const;
618 :
619 : void
620 : set_bits (symbolic_bit_range bit_range,
621 : const symbolic::bit_vector &bits,
622 : uncertainty_t *uncertainty);
623 :
624 : const symbolic::bit_contents &
625 10897 : get_bit_contents () const { return *m_contents; }
626 :
627 : void
628 6467 : set_bit_contents (const symbolic::bit_contents &bc)
629 : {
630 6467 : m_contents = &bc;
631 : }
632 :
633 : void mark_as_untracked (symbolic::node_manager &node_mgr,
634 : uncertainty_t *uncertainty,
635 : value_set *maybe_live_values);
636 : void purge_state_involving (const symbolic::node &node);
637 :
638 : iter_result
639 : for_each_value (iter_result (*cb) (const symbolic::value_node &val,
640 : void *user_data),
641 : void *user_data) const;
642 :
643 : static bool can_merge_p (const binding_cluster *cluster_a,
644 : const binding_cluster *cluster_b,
645 : binding_cluster *out_cluster,
646 : store *out_store,
647 : model_merger *merger);
648 : void make_unknown_relative_to (const binding_cluster *other_cluster,
649 : store *out_store,
650 : baseline_state bs);
651 :
652 : void mark_as_escaped ();
653 : void on_unknown_fncall (const gcall &call,
654 : const conjured_purge &p);
655 : void
656 : mark_region_as_conjured (const gimple &stmt,
657 : const conjured_purge &p);
658 :
659 : void on_asm (const gasm *stmt,
660 : const conjured_purge &p);
661 :
662 : bool escaped_p () const;
663 120862 : bool touched_p () const { return m_touched; }
664 :
665 : bool redundant_p (const store &store_,
666 : baseline_state bs) const;
667 :
668 : void get_representative_path_vars (const region_model *model,
669 : value_set *visited,
670 : const region *base_reg,
671 : const svalue *sval,
672 : logger *logger,
673 : auto_vec<path_var> *out_pvs) const;
674 :
675 : void
676 : poison_any_pointers_to_descendents (const region *reg,
677 : enum poison_kind pkind);
678 :
679 : bool
680 : bits_live_p (const symbolic::bit_vector_from_ubc &bv_from_ubc) const;
681 :
682 : private:
683 : symbolic::node_manager &m_node_mgr;
684 :
685 : const region *m_base_region;
686 :
687 : const symbolic::bit_contents *m_contents;
688 :
689 : /* Has a pointer to this cluster "escaped" into a part of the program
690 : we don't know about (via a call to a function with an unknown body,
691 : or by being passed in as a pointer param of a "top-level" function call).
692 : Such regions could be overwritten when other such functions are called,
693 : even if the region is no longer reachable by pointers that we are
694 : tracking. */
695 : bool m_escaped;
696 :
697 : /* Has this cluster been written to via a symbolic binding?
698 : If so, then we don't know anything about unbound subregions,
699 : so we can't use initial_svalue, treat them as uninitialized, or
700 : inherit values from a parent region. */
701 : bool m_touched;
702 : };
703 :
704 : /* The mapping from regions to svalues.
705 : This is actually expressed by subdividing into clusters, to better
706 : handle aliasing. */
707 :
708 : class store
709 : {
710 : public:
711 : typedef hash_map <const region *, binding_cluster *> cluster_map_t;
712 :
713 : store (symbolic::node_manager &node_mgr);
714 : store (const store &other);
715 : ~store ();
716 :
717 : store &operator= (const store &other);
718 :
719 : bool operator== (const store &other) const;
720 437680 : bool operator!= (const store &other) const
721 : {
722 437680 : return !(*this == other);
723 : }
724 :
725 : hashval_t hash () const;
726 :
727 : void dump () const;
728 : void summarize_to_pp (pretty_printer *pp, bool simple) const;
729 :
730 : void validate () const;
731 :
732 : std::unique_ptr<json::object> to_json () const;
733 :
734 : std::unique_ptr<text_art::tree_widget>
735 : make_dump_widget (symbolic::node_dump_state &nds) const;
736 :
737 : const symbolic::bit_vector &
738 : get_bits (const symbolic::memory_range &mem_range,
739 : baseline_state bs) const;
740 :
741 : const symbolic::bit_contents &
742 : get_bit_contents (const region &base_reg,
743 : baseline_state bs) const;
744 :
745 0 : bool called_unknown_fn_p () const { return m_called_unknown_fn; }
746 :
747 : void
748 : set_bits (const region *lhs_reg,
749 : const symbolic::bit_vector &bv,
750 : uncertainty_t *uncertainty,
751 : const region_model &model);
752 :
753 : void
754 : set_bits (const symbolic::memory_range &mem_range,
755 : const symbolic::bit_vector &bv,
756 : uncertainty_t *uncertainty,
757 : const region_model &model);
758 :
759 : void
760 : set_bit_contents_raw (const region &base_reg,
761 : const symbolic::bit_contents &bc,
762 : const region_model &model);
763 :
764 : void clobber_region (const region *reg,
765 : baseline_state bs,
766 : region_model_manager &rmm);
767 : void purge_region (const region *reg);
768 : void mark_region_as_unknown (const region *reg,
769 : baseline_state bs,
770 : uncertainty_t *uncertainty,
771 : const region_model &model);
772 : void purge_state_involving (const symbolic::node &node);
773 :
774 : const binding_cluster *get_cluster (const region *base_reg) const;
775 : binding_cluster *get_cluster (const region *base_reg);
776 : binding_cluster *
777 : get_or_create_cluster (const region *base_reg,
778 : baseline_state bs);
779 : void purge_cluster (const region *base_reg);
780 :
781 : template <typename T>
782 1276187 : void for_each_cluster (void (*cb) (const region *base_reg, T user_data),
783 : T user_data) const
784 : {
785 1276187 : for (cluster_map_t::iterator iter = m_cluster_map.begin ();
786 8430736 : iter != m_cluster_map.end (); ++iter)
787 7154549 : cb ((*iter).first, user_data);
788 1276187 : }
789 :
790 : static bool can_merge_p (const store *store_a, const store *store_b,
791 : store *out_store,
792 : model_merger *merger);
793 :
794 : void mark_as_escaped (const region *base_reg,
795 : baseline_state bs);
796 : void on_unknown_fncall (const gcall &call,
797 : const conjured_purge &p);
798 : void
799 : mark_region_as_conjured (const region &base_reg,
800 : baseline_state bs,
801 : const gimple &stmt,
802 : const conjured_purge &p);
803 :
804 : bool escaped_p (const region *reg) const;
805 :
806 : void get_representative_path_vars (const region_model *model,
807 : value_set *visited,
808 : const svalue *sval,
809 : logger *logger,
810 : auto_vec<path_var> *out_pvs) const;
811 :
812 988442 : cluster_map_t::iterator begin () const { return m_cluster_map.begin (); }
813 6296164 : cluster_map_t::iterator end () const { return m_cluster_map.end (); }
814 :
815 : tristate eval_alias (const region *base_reg_a,
816 : const region *base_reg_b,
817 : const region_model &model) const;
818 :
819 : void canonicalize ();
820 : void loop_replay_fixup (const store *other_store,
821 : baseline_state bs,
822 : region_model_manager *mgr);
823 :
824 : bool replay_call_summary (call_summary_replay &r,
825 : const store &summary);
826 : bool replay_call_summary_cluster (call_summary_replay &r,
827 : const store &summary,
828 : const region *base_reg);
829 : bool
830 : replay_call_summary_bit_contents (call_summary_replay &r,
831 : const store &summary,
832 : const region &summary_base_reg,
833 : const region &caller_dest_reg,
834 : const symbolic::bit_contents &caller_bc);
835 :
836 : void on_maybe_live_values (const value_set &maybe_live_values,
837 : baseline_state bs);
838 :
839 : bool
840 : bits_live_p (const symbolic::bit_vector_from_ubc &bv_from_ubc,
841 : const region_model &model) const;
842 :
843 : const symbolic::bit_contents &
844 : get_implicit_contents (const region &base_reg,
845 : baseline_state bs) const;
846 :
847 : private:
848 : const symbolic::bit_contents &
849 : get_baseline_contents (const region &base_reg,
850 : baseline_state bs) const;
851 :
852 : tristate eval_alias_1 (const region *base_reg_a,
853 : const region *base_reg_b,
854 : const region_model &model) const;
855 :
856 : symbolic::node_manager &m_node_mgr;
857 :
858 : cluster_map_t m_cluster_map;
859 :
860 : /* If this is true, then unknown code has been called since the beginning
861 : of some path reaching this point in the analysis. All externally
862 : visible non-readonly global variables that aren't currently modelled by
863 : the store are affected by this flag: they are implicitly either all in their
864 : "initial state" (m_called_unknown_fn==false), or all in unknown state
865 : (m_called_unknown_fn==true).
866 :
867 : This is to avoid having to mark (and thus explicitly track)
868 : every global when an unknown function is called; instead, they
869 : can be tracked implicitly. */
870 : bool m_called_unknown_fn;
871 : };
872 :
873 : } // namespace ana
874 :
875 : #endif /* GCC_ANALYZER_STORE_H */
|