Line data Source code
1 : /* Classes for representing the state of interest at a given path of analysis.
2 : Copyright (C) 2019-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 : #include "analyzer/common.h"
22 :
23 : #include "sbitmap.h"
24 : #include "ordered-hash-map.h"
25 : #include "selftest.h"
26 : #include "cfg.h"
27 : #include "gimple-iterator.h"
28 : #include "cgraph.h"
29 : #include "digraph.h"
30 : #include "diagnostics/event-id.h"
31 : #include "diagnostics/state-graphs.h"
32 : #include "graphviz.h"
33 :
34 : #include "text-art/tree-widget.h"
35 : #include "text-art/dump.h"
36 :
37 : #include "analyzer/analyzer-logging.h"
38 : #include "analyzer/sm.h"
39 : #include "analyzer/call-string.h"
40 : #include "analyzer/program-point.h"
41 : #include "analyzer/store.h"
42 : #include "analyzer/region-model.h"
43 : #include "analyzer/program-state.h"
44 : #include "analyzer/constraint-manager.h"
45 : #include "analyzer/pending-diagnostic.h"
46 : #include "analyzer/diagnostic-manager.h"
47 : #include "analyzer/supergraph.h"
48 : #include "analyzer/program-state.h"
49 : #include "analyzer/exploded-graph.h"
50 : #include "analyzer/state-purge.h"
51 : #include "analyzer/call-summary.h"
52 : #include "analyzer/analyzer-selftests.h"
53 : #include "analyzer/ana-state-to-diagnostic-state.h"
54 : #include "analyzer/liveness-context.h"
55 :
56 : #if ENABLE_ANALYZER
57 :
58 : namespace ana {
59 :
60 : /* class extrinsic_state. */
61 :
62 : std::unique_ptr<text_art::tree_widget>
63 0 : extrinsic_state::make_dump_widget (symbolic::node_dump_state &nds) const
64 : {
65 0 : using text_art::tree_widget;
66 0 : std::unique_ptr<tree_widget> w
67 0 : (tree_widget::from_fmt (nds, nullptr, "Extrinsic State"));
68 0 : unsigned i = 0;
69 0 : for (auto &checker : m_checkers)
70 : {
71 0 : std::unique_ptr<tree_widget> cw
72 : (tree_widget::from_fmt (nds, nullptr, "m_checkers[%i]: %qs\n",
73 0 : ++i, checker->get_name ()));
74 0 : w->add_child (std::move (cw));
75 0 : }
76 0 : return w;
77 : }
78 :
79 : /* Return a new json::object of the form
80 : {"checkers" : array of objects, one for each state_machine}. */
81 :
82 : std::unique_ptr<json::object>
83 1 : extrinsic_state::to_json () const
84 : {
85 1 : auto ext_state_obj = std::make_unique<json::object> ();
86 :
87 1 : {
88 1 : auto checkers_arr = std::make_unique<json::array> ();
89 8 : for (auto &sm : m_checkers)
90 7 : checkers_arr->append (sm->to_json ());
91 1 : ext_state_obj->set ("checkers", std::move (checkers_arr));
92 1 : }
93 :
94 1 : return ext_state_obj;
95 : }
96 :
97 : /* Get the region_model_manager for this extrinsic_state. */
98 :
99 : region_model_manager *
100 7476658 : extrinsic_state::get_model_manager () const
101 : {
102 7476658 : if (m_engine)
103 7476658 : return m_engine->get_model_manager ();
104 : else
105 : return nullptr; /* for selftests. */
106 : }
107 :
108 : symbolic::node_manager &
109 45932 : extrinsic_state::get_node_manager () const
110 : {
111 45932 : gcc_assert (m_engine);
112 45932 : return m_engine->get_node_manager ();
113 : }
114 :
115 : /* Try to find a state machine named NAME.
116 : If found, return true and write its index to *OUT.
117 : Otherwise return false. */
118 :
119 : bool
120 627557 : extrinsic_state::get_sm_idx_by_name (const char *name, unsigned *out) const
121 : {
122 2507781 : for (size_t i = 0; i < m_checkers.size (); ++i)
123 2507310 : if (0 == strcmp (name, m_checkers[i]->get_name ()))
124 : {
125 : /* Found NAME. */
126 627086 : *out = i;
127 627086 : return true;
128 : }
129 :
130 : /* NAME not found. */
131 : return false;
132 : }
133 :
134 : /* struct sm_state_map::entry_t. */
135 :
136 : int
137 65946 : sm_state_map::entry_t::cmp (const entry_t &entry_a, const entry_t &entry_b)
138 : {
139 65946 : gcc_assert (entry_a.m_state);
140 65946 : gcc_assert (entry_b.m_state);
141 65946 : if (int cmp_state = ((int)entry_a.m_state->get_id ()
142 65946 : - (int)entry_b.m_state->get_id ()))
143 : return cmp_state;
144 59640 : if (entry_a.m_origin && entry_b.m_origin)
145 0 : return svalue::cmp_ptr (entry_a.m_origin, entry_b.m_origin);
146 59640 : if (entry_a.m_origin)
147 : return 1;
148 59640 : if (entry_b.m_origin)
149 0 : return -1;
150 : return 0;
151 : }
152 :
153 : /* class sm_state_map. */
154 :
155 : /* sm_state_map's ctor. */
156 :
157 1040587 : sm_state_map::sm_state_map (const state_machine &sm)
158 1040587 : : m_sm (sm), m_map (), m_global_state (sm.get_start_state ())
159 : {
160 1040587 : }
161 :
162 : /* Clone the sm_state_map. */
163 :
164 : sm_state_map *
165 12578289 : sm_state_map::clone () const
166 : {
167 12578289 : return new sm_state_map (*this);
168 : }
169 :
170 : /* Print this sm_state_map to PP.
171 : If MODEL is non-NULL, print representative tree values where
172 : available. */
173 :
174 : void
175 0 : sm_state_map::print (const region_model *model,
176 : bool simple, bool multiline,
177 : pretty_printer *pp) const
178 : {
179 0 : bool first = true;
180 0 : if (!multiline)
181 0 : pp_string (pp, "{");
182 0 : if (m_global_state != m_sm.get_start_state ())
183 : {
184 0 : if (multiline)
185 0 : pp_string (pp, " ");
186 0 : pp_string (pp, "global: ");
187 0 : m_global_state->dump_to_pp (pp);
188 0 : if (multiline)
189 0 : pp_newline (pp);
190 : first = false;
191 : }
192 0 : auto_vec <const svalue *> keys (m_map.elements ());
193 0 : for (map_t::iterator iter = m_map.begin ();
194 0 : iter != m_map.end ();
195 0 : ++iter)
196 0 : keys.quick_push ((*iter).first);
197 0 : keys.qsort (svalue::cmp_ptr_ptr);
198 0 : unsigned i;
199 0 : const svalue *sval;
200 0 : FOR_EACH_VEC_ELT (keys, i, sval)
201 : {
202 0 : if (multiline)
203 0 : pp_string (pp, " ");
204 0 : else if (!first)
205 0 : pp_string (pp, ", ");
206 0 : first = false;
207 0 : if (!flag_dump_noaddr)
208 : {
209 0 : pp_pointer (pp, sval);
210 0 : pp_string (pp, ": ");
211 : }
212 0 : sval->dump_to_pp (pp, simple);
213 :
214 0 : entry_t e = *const_cast <map_t &> (m_map).get (sval);
215 0 : pp_string (pp, ": ");
216 0 : e.m_state->dump_to_pp (pp);
217 0 : if (model)
218 0 : if (tree rep = model->get_representative_tree (sval))
219 : {
220 0 : pp_string (pp, " (");
221 0 : dump_quoted_tree (pp, rep);
222 0 : pp_character (pp, ')');
223 : }
224 0 : if (e.m_origin)
225 : {
226 0 : pp_string (pp, " (origin: ");
227 0 : if (!flag_dump_noaddr)
228 : {
229 0 : pp_pointer (pp, e.m_origin);
230 0 : pp_string (pp, ": ");
231 : }
232 0 : e.m_origin->dump_to_pp (pp, simple);
233 0 : if (model)
234 0 : if (tree rep = model->get_representative_tree (e.m_origin))
235 : {
236 0 : pp_string (pp, " (");
237 0 : dump_quoted_tree (pp, rep);
238 0 : pp_character (pp, ')');
239 : }
240 0 : pp_string (pp, ")");
241 : }
242 0 : if (multiline)
243 0 : pp_newline (pp);
244 : }
245 0 : if (!multiline)
246 0 : pp_string (pp, "}");
247 : // TODO: m_map_ubc_to_state
248 0 : }
249 :
250 : /* Dump this object to stderr. */
251 :
252 : DEBUG_FUNCTION void
253 0 : sm_state_map::dump (bool simple) const
254 : {
255 0 : tree_dump_pretty_printer pp (stderr);
256 0 : print (nullptr, simple, true, &pp);
257 0 : pp_newline (&pp);
258 0 : }
259 :
260 : /* Return a new json::object of the form
261 : {"global" : (optional) value for global state,
262 : SVAL_DESC : value for state}. */
263 :
264 : std::unique_ptr<json::object>
265 9 : sm_state_map::to_json () const
266 : {
267 9 : auto map_obj = std::make_unique<json::object> ();
268 :
269 9 : if (m_global_state != m_sm.get_start_state ())
270 0 : map_obj->set ("global", m_global_state->to_json ());
271 9 : for (map_t::iterator iter = m_map.begin ();
272 18 : iter != m_map.end ();
273 9 : ++iter)
274 : {
275 9 : const svalue *sval = (*iter).first;
276 9 : entry_t e = (*iter).second;
277 :
278 9 : label_text sval_desc = sval->get_desc ();
279 9 : map_obj->set (sval_desc.get (), e.m_state->to_json ());
280 :
281 : /* This doesn't yet JSONify e.m_origin. */
282 9 : }
283 : // TODO: m_map_ubc_to_state
284 9 : return map_obj;
285 : }
286 :
287 : /* Make a text_art::tree_widget describing this sm_state_map,
288 : using MODEL if non-null to describe svalues. */
289 :
290 : std::unique_ptr<text_art::tree_widget>
291 70 : sm_state_map::make_dump_widget (symbolic::node_dump_state &nds,
292 : const region_model *) const
293 : {
294 70 : using text_art::styled_string;
295 70 : using text_art::tree_widget;
296 70 : std::unique_ptr<tree_widget> state_widget
297 : (tree_widget::from_fmt (nds, nullptr,
298 70 : "%qs state machine", m_sm.get_name ()));
299 :
300 70 : if (m_global_state != m_sm.get_start_state ())
301 : {
302 0 : pretty_printer the_pp;
303 0 : pretty_printer * const pp = &the_pp;
304 0 : pp_format_decoder (pp) = default_tree_printer;
305 0 : pp_string (pp, "Global State: ");
306 0 : m_global_state->dump_to_pp (pp);
307 0 : state_widget->add_child (tree_widget::make (nds, pp));
308 0 : }
309 :
310 70 : auto_vec <const svalue *> keys (m_map.elements ());
311 70 : for (map_t::iterator iter = m_map.begin ();
312 140 : iter != m_map.end ();
313 70 : ++iter)
314 70 : keys.quick_push ((*iter).first);
315 70 : keys.qsort (svalue::cmp_ptr_ptr);
316 70 : unsigned i;
317 70 : const svalue *sval;
318 210 : FOR_EACH_VEC_ELT (keys, i, sval)
319 : {
320 70 : entry_t e = *const_cast <map_t &> (m_map).get (sval);
321 :
322 70 : pretty_printer pp;
323 70 : pp_format_decoder (&pp) = default_tree_printer;
324 70 : e.m_state->dump_to_pp (&pp);
325 70 : std::unique_ptr<tree_widget> per_key_widget
326 70 : = tree_widget::make (nds, &pp);
327 140 : per_key_widget->add_child (sval->make_dump_widget (nds));
328 140 : state_widget->add_child (std::move (per_key_widget));
329 70 : }
330 70 : for (auto iter : m_map_ubc_to_state)
331 : {
332 0 : auto *ubc = iter.first;
333 0 : auto state = iter.second;
334 0 : pretty_printer pp;
335 0 : pp_format_decoder (&pp) = default_tree_printer;
336 0 : state->dump_to_pp (&pp);
337 0 : std::unique_ptr<tree_widget> per_key_widget
338 0 : = tree_widget::make (nds, &pp);
339 0 : per_key_widget->add_child (ubc->make_dump_widget (nds));
340 0 : state_widget->add_child (std::move (per_key_widget));
341 0 : }
342 :
343 70 : return state_widget;
344 70 : }
345 :
346 : DEBUG_FUNCTION void
347 0 : sm_state_map::dump () const
348 : {
349 0 : symbolic::dump_node_tree_to_stderr<sm_state_map> (*this);
350 0 : }
351 :
352 : /* Return true if no states have been set within this map
353 : (all expressions are for the start state). */
354 :
355 : bool
356 5112 : sm_state_map::is_empty_p () const
357 : {
358 5112 : return (m_map.elements () == 0
359 5029 : && m_global_state == m_sm.get_start_state ()
360 10141 : && m_map_ubc_to_state.empty ());
361 : }
362 :
363 : /* Generate a hash value for this sm_state_map. */
364 :
365 : hashval_t
366 3927018 : sm_state_map::hash () const
367 : {
368 3927018 : hashval_t result = 0;
369 :
370 : /* Accumulate the result by xoring a hash for each slot, so that the
371 : result doesn't depend on the ordering of the slots in the map. */
372 :
373 3927018 : for (map_t::iterator iter = m_map.begin ();
374 4380799 : iter != m_map.end ();
375 453781 : ++iter)
376 : {
377 453781 : inchash::hash hstate;
378 453781 : hstate.add_ptr ((*iter).first);
379 453781 : entry_t e = (*iter).second;
380 453781 : hstate.add_int (e.m_state->get_id ());
381 453781 : hstate.add_ptr (e.m_origin);
382 453781 : result ^= hstate.end ();
383 : }
384 3927018 : result ^= m_global_state->get_id ();
385 :
386 3927018 : return result;
387 : }
388 :
389 : /* Equality operator for sm_state_map. */
390 :
391 : bool
392 579147 : sm_state_map::operator== (const sm_state_map &other) const
393 : {
394 579147 : if (m_global_state != other.m_global_state)
395 : return false;
396 :
397 578120 : if (m_map.elements () != other.m_map.elements ())
398 : return false;
399 :
400 521090 : for (map_t::iterator iter = m_map.begin ();
401 591586 : iter != m_map.end ();
402 70496 : ++iter)
403 : {
404 81611 : const svalue *sval = (*iter).first;
405 81611 : entry_t e = (*iter).second;
406 81611 : entry_t *other_slot = const_cast <map_t &> (other.m_map).get (sval);
407 81611 : if (other_slot == nullptr)
408 11115 : return false;
409 152107 : if (e != *other_slot)
410 : return false;
411 : }
412 :
413 509975 : if (m_map_ubc_to_state != other.m_map_ubc_to_state)
414 : return false;
415 :
416 509797 : gcc_checking_assert (hash () == other.hash ());
417 :
418 : return true;
419 : }
420 :
421 : state_machine::state_t
422 129124 : sm_state_map::
423 : get_any_inherited_state_of_bit_vector (const symbolic::bit_vector &bv,
424 : const extrinsic_state &ext_state,
425 : region_model_manager &rmm) const
426 : {
427 130222 : switch (bv.get_kind ())
428 : {
429 0 : default:
430 0 : gcc_unreachable ();
431 :
432 : case symbolic::bit_vector::kind::concat:
433 : break;
434 : case symbolic::bit_vector::kind::conjured:
435 : break;
436 1098 : case symbolic::bit_vector::kind::cropped:
437 1098 : {
438 1098 : auto &cropped_bv
439 : = static_cast<const symbolic::cropped_bit_vector &> (bv);
440 1098 : auto &inner_bv = cropped_bv.get_uncropped_bit_vector ();
441 1098 : return get_any_inherited_state_of_bit_vector (inner_bv, ext_state, rmm);
442 : }
443 : break;
444 : case symbolic::bit_vector::kind::empty:
445 : break;
446 : case symbolic::bit_vector::kind::named_test:
447 : break;
448 : case symbolic::bit_vector::kind::poisoned:
449 : break;
450 : case symbolic::bit_vector::kind::repeated:
451 : break;
452 1008 : case symbolic::bit_vector::kind::svalue:
453 1008 : {
454 1008 : auto &from_sval
455 : = static_cast<const symbolic::bit_vector_from_svalue &> (bv);
456 1008 : auto &sval = from_sval.get_svalue ();
457 1008 : return get_state (&sval, ext_state);
458 : }
459 67777 : break;
460 67777 : case symbolic::bit_vector::kind::from_ubc:
461 67777 : {
462 67777 : auto &from_ubc
463 : = static_cast<const symbolic::bit_vector_from_ubc &> (bv);
464 67777 : auto &ubc = from_ubc.get_bit_contents ();
465 67777 : auto iter = m_map_ubc_to_state.find (&ubc);
466 67777 : if (iter != m_map_ubc_to_state.end ())
467 739 : return iter->second;
468 67038 : if (auto *conjured_bc = ubc.dyn_cast_conjured_bit_contents ())
469 : {
470 11005 : auto *id_reg = conjured_bc->get_id_region ();
471 11005 : const svalue *id_reg_ptr = rmm.get_ptr_svalue (NULL_TREE, id_reg);
472 11005 : state_machine::state_t parent_state
473 11005 : = get_state (id_reg_ptr, ext_state);
474 11005 : if (parent_state)
475 : return parent_state;
476 : }
477 56033 : if (auto *baseline_bc = ubc.dyn_cast_baseline_bit_contents ())
478 : {
479 56033 : auto &bkey = baseline_bc->get_baseline_key ();
480 56033 : const region *reg = bkey.m_base_reg;
481 56033 : const svalue *reg_ptr = rmm.get_ptr_svalue (NULL_TREE, reg);
482 56033 : state_machine::state_t parent_state
483 56033 : = get_state (reg_ptr, ext_state);
484 56033 : if (parent_state)
485 : return parent_state;
486 : }
487 : }
488 : break;
489 : case symbolic::bit_vector::kind::tristate:
490 : break;
491 : }
492 :
493 : return nullptr;
494 : }
495 :
496 : /* Get the state of SVAL within this object.
497 : States default to the start state. */
498 :
499 : state_machine::state_t
500 4431731 : sm_state_map::get_state (const svalue *sval,
501 : const extrinsic_state &ext_state) const
502 : {
503 4431731 : gcc_assert (sval);
504 :
505 4431731 : sval = canonicalize_svalue (sval, ext_state);
506 :
507 8863462 : if (entry_t *slot
508 4431731 : = const_cast <map_t &> (m_map).get (sval))
509 352618 : return slot->m_state;
510 :
511 : /* SVAL has no explicit sm-state.
512 : If this sm allows for state inheritance, then SVAL might have implicit
513 : sm-state inherited via a parent.
514 : For example INIT_VAL(foo.field) might inherit taintedness state from
515 : INIT_VAL(foo). */
516 4079113 : if (m_sm.inherited_state_p ())
517 1488112 : if (region_model_manager *mgr = ext_state.get_model_manager ())
518 : {
519 1488112 : if (const initial_svalue *init_sval = sval->dyn_cast_initial_svalue ())
520 : {
521 163397 : const region *reg = init_sval->get_region ();
522 : /* Try recursing upwards (up to the base region for the
523 : cluster). */
524 163397 : if (!reg->base_region_p ())
525 0 : if (const region *parent_reg = reg->get_parent_region ())
526 : {
527 0 : const svalue *parent_init_sval
528 0 : = mgr->get_or_create_initial_value (parent_reg);
529 0 : state_machine::state_t parent_state
530 0 : = get_state (parent_init_sval, ext_state);
531 0 : if (parent_state)
532 : return parent_state;
533 : }
534 : }
535 1488112 : if (auto *from_bv = sval->dyn_cast_svalue_from_bit_vector ())
536 129124 : if (auto state
537 : = get_any_inherited_state_of_bit_vector
538 129124 : (from_bv->get_bit_vector (),
539 : ext_state,
540 : *mgr))
541 : return state;
542 : }
543 :
544 8020656 : if (state_machine::state_t state
545 4010328 : = m_sm.alt_get_inherited_state (*this, sval, ext_state))
546 : return state;
547 :
548 3841160 : return m_sm.get_default_state (sval);
549 : }
550 :
551 : /* Get the "origin" svalue for any state of SVAL. */
552 :
553 : const svalue *
554 12 : sm_state_map::get_origin (const svalue *sval,
555 : const extrinsic_state &ext_state) const
556 : {
557 12 : gcc_assert (sval);
558 :
559 12 : sval = canonicalize_svalue (sval, ext_state);
560 :
561 12 : entry_t *slot
562 12 : = const_cast <map_t &> (m_map).get (sval);
563 12 : if (slot)
564 12 : return slot->m_origin;
565 : else
566 : return nullptr;
567 : }
568 :
569 : /* Set the state of SID within MODEL to STATE, recording that
570 : the state came from ORIGIN. */
571 :
572 : void
573 36360 : sm_state_map::set_state (region_model *model,
574 : const svalue *sval,
575 : state_machine::state_t state,
576 : const svalue *origin,
577 : const extrinsic_state &ext_state)
578 : {
579 36360 : if (model == nullptr)
580 : return;
581 :
582 : /* Reject attempts to set state on UNKNOWN/POISONED. */
583 36360 : if (!sval->can_have_associated_state_p ())
584 : return;
585 :
586 32994 : equiv_class &ec = model->get_constraints ()->get_equiv_class (sval);
587 32994 : if (!set_state (ec, state, origin, ext_state))
588 : return;
589 : }
590 :
591 : /* Set the state of EC to STATE, recording that the state came from
592 : ORIGIN.
593 : Return true if any states of svalue_ids within EC changed. */
594 :
595 : bool
596 32994 : sm_state_map::set_state (const equiv_class &ec,
597 : state_machine::state_t state,
598 : const svalue *origin,
599 : const extrinsic_state &ext_state)
600 : {
601 32994 : bool any_changed = false;
602 133732 : for (const svalue *sval : ec.m_vars)
603 34750 : any_changed |= impl_set_state (sval, state, origin, ext_state);
604 32994 : return any_changed;
605 : }
606 :
607 : /* Set state of SVAL to STATE, bypassing equivalence classes.
608 : Return true if the state changed. */
609 :
610 : bool
611 99911 : sm_state_map::impl_set_state (const svalue *sval,
612 : state_machine::state_t state,
613 : const svalue *origin,
614 : const extrinsic_state &ext_state)
615 : {
616 99911 : sval = canonicalize_svalue (sval, ext_state);
617 :
618 99911 : if (get_state (sval, ext_state) == state)
619 : return false;
620 :
621 84737 : gcc_assert (sval->can_have_associated_state_p ());
622 :
623 : /* Special-case state 0 as the default value. */
624 84737 : if (state == 0)
625 : {
626 823 : if (m_map.get (sval))
627 819 : m_map.remove (sval);
628 : return true;
629 : }
630 83914 : gcc_assert (sval);
631 83914 : m_map.put (sval, entry_t (state, origin));
632 :
633 : /* Update m_map_ubc_to_state. */
634 83914 : if (m_sm.inherited_state_p ())
635 21543 : if (auto *from_bv = sval->dyn_cast_svalue_from_bit_vector ())
636 297 : if (auto *from_ubc
637 297 : = from_bv->get_bit_vector ().dyn_cast_bit_vector_from_ubc ())
638 290 : m_map_ubc_to_state[&from_ubc->get_bit_contents ()] = state;
639 :
640 : return true;
641 : }
642 :
643 : /* Clear any state for SVAL from this state map. */
644 :
645 : void
646 2864 : sm_state_map::clear_any_state (const svalue *sval)
647 : {
648 2864 : m_map.remove (sval);
649 : // TODO: what about m_map_ubc_to_state?
650 2864 : }
651 :
652 : /* Clear all per-svalue state within this state map. */
653 :
654 : void
655 7963 : sm_state_map::clear_all_per_svalue_state ()
656 : {
657 7963 : m_map.empty ();
658 7963 : m_map_ubc_to_state.clear ();
659 7963 : }
660 :
661 : /* Set the "global" state within this state map to STATE. */
662 :
663 : void
664 108310 : sm_state_map::set_global_state (state_machine::state_t state)
665 : {
666 108310 : m_global_state = state;
667 108310 : }
668 :
669 : /* Get the "global" state within this state map. */
670 :
671 : state_machine::state_t
672 974964 : sm_state_map::get_global_state () const
673 : {
674 974964 : return m_global_state;
675 : }
676 :
677 : /* Purge any state for SVAL.
678 : If !SM::can_purge_p, then report the state as leaking,
679 : using CTXT. */
680 :
681 : void
682 173542 : sm_state_map::on_svalue_leak (const svalue *sval,
683 : impl_region_model_context *ctxt)
684 : {
685 173542 : if (state_machine::state_t state = get_state (sval, ctxt->m_ext_state))
686 : {
687 173542 : if (m_sm.can_purge_p (state))
688 173069 : m_map.remove (sval);
689 : else
690 473 : ctxt->on_state_leak (m_sm, sval, state);
691 : }
692 173542 : }
693 :
694 : /* Purge any state for svalues that aren't live with respect to
695 : LIVENESS_CTXT. */
696 :
697 : void
698 3034126 : sm_state_map::on_liveness_change (symbolic::liveness_context &liveness_ctxt,
699 : const extrinsic_state &ext_state,
700 : impl_region_model_context *ctxt)
701 : {
702 3034126 : symbolic::node_set<svalue> svals_to_unset;
703 3034126 : uncertainty_t *uncertainty = ctxt->get_uncertainty ();
704 :
705 3034126 : auto_vec<const svalue *> leaked_svals (m_map.elements ());
706 3430178 : for (map_t::iterator iter = m_map.begin ();
707 3430178 : iter != m_map.end ();
708 396052 : ++iter)
709 : {
710 396052 : const svalue *iter_sval = (*iter).first;
711 396052 : if (!liveness_ctxt.node_live_p (*iter_sval))
712 : {
713 20028 : svals_to_unset.insert (iter_sval);
714 20028 : entry_t e = (*iter).second;
715 20028 : if (!m_sm.can_purge_p (e.m_state))
716 778 : leaked_svals.quick_push (iter_sval);
717 : }
718 396052 : if (uncertainty)
719 352256 : if (uncertainty->unknown_sm_state_p (iter_sval))
720 399 : svals_to_unset.insert (iter_sval);
721 : }
722 :
723 3034126 : leaked_svals.qsort (svalue::cmp_ptr_ptr);
724 :
725 3034126 : unsigned i;
726 3034126 : const svalue *sval;
727 3261071 : FOR_EACH_VEC_ELT (leaked_svals, i, sval)
728 : {
729 778 : entry_t e = *m_map.get (sval);
730 778 : ctxt->on_state_leak (m_sm, sval, e.m_state);
731 : }
732 :
733 3034126 : sm_state_map old_sm_map = *this;
734 :
735 3034126 : for (auto iter = svals_to_unset.begin ();
736 3054553 : iter != svals_to_unset.end (); ++iter)
737 20427 : m_map.remove (*iter);
738 :
739 : /* For state machines like "taint" where states can be
740 : alt-inherited from other svalues, ensure that state purging doesn't
741 : make us lose sm-state.
742 :
743 : Consider e.g.:
744 :
745 : make_tainted(foo);
746 : if (foo.field > 128)
747 : return;
748 : arr[foo.field].f1 = v1;
749 :
750 : where the last line is:
751 :
752 : (A): _t1 = foo.field;
753 : (B): _t2 = _t1 * sizeof(arr[0]);
754 : (C): [arr + _t2].f1 = val;
755 :
756 : At (A), foo is 'tainted' and foo.field is 'has_ub'.
757 : After (B), foo.field's value (in _t1) is no longer directly
758 : within LIVE_SVALUES, so with state purging enabled, we would
759 : erroneously purge the "has_ub" state from the svalue.
760 :
761 : Given that _t2's value's state comes from _t1's value's state,
762 : we need to preserve that information.
763 :
764 : Hence for all svalues that have had their explicit sm-state unset,
765 : having their sm-state being unset, determine if doing so has changed
766 : their effective state, and if so, explicitly set their state.
767 :
768 : For example, in the above, unsetting the "has_ub" for _t1's value means
769 : that _t2's effective value changes from "has_ub" (from alt-inherited
770 : from _t1's value) to "tainted" (inherited from "foo"'s value).
771 :
772 : For such cases, preserve the effective state by explicitly setting the
773 : new state. In the above example, this means explicitly setting _t2's
774 : value to the value ("has_ub") it was previously alt-inheriting from _t1's
775 : value. */
776 3034126 : if (m_sm.has_alt_get_inherited_state_p ())
777 : {
778 433376 : auto_vec<const svalue *> svalues_needing_state;
779 450896 : for (auto unset_sval : svals_to_unset)
780 : {
781 17520 : const state_machine::state_t old_state
782 17520 : = old_sm_map.get_state (unset_sval, ext_state);
783 17520 : const state_machine::state_t new_state
784 17520 : = get_state (unset_sval, ext_state);
785 17520 : if (new_state != old_state)
786 17449 : svalues_needing_state.safe_push (unset_sval);
787 : }
788 469467 : for (auto sval : svalues_needing_state)
789 : {
790 17449 : const state_machine::state_t old_state
791 17449 : = old_sm_map.get_state (sval, ext_state);
792 17449 : impl_set_state (sval, old_state, nullptr, ext_state);
793 : }
794 433376 : }
795 3034126 : }
796 :
797 : /* Purge state from VAL (in response to a call to an unknown function). */
798 :
799 : void
800 206220 : sm_state_map::on_unknown_change (const symbolic::value_node &val,
801 : bool is_mutable,
802 : const extrinsic_state &ext_state)
803 : {
804 206220 : symbolic::node_set<svalue> svals_to_unset;
805 :
806 206220 : if (auto *sval = val.dyn_cast_svalue ())
807 : {
808 159446 : sval = canonicalize_svalue (sval, ext_state);
809 :
810 179557 : for (map_t::iterator iter = m_map.begin ();
811 339003 : iter != m_map.end ();
812 20111 : ++iter)
813 : {
814 20111 : const svalue *key = (*iter).first;
815 20111 : entry_t e = (*iter).second;
816 : /* We only want to purge state for some states when things
817 : are mutable. For example, in sm-malloc.cc, an on-stack ptr
818 : doesn't stop being stack-allocated when passed to an unknown fn. */
819 20111 : if (!m_sm.reset_when_passed_to_unknown_fn_p (e.m_state, is_mutable))
820 8930 : continue;
821 11181 : if (key == sval)
822 773 : svals_to_unset.add (key);
823 : /* If we have INIT_VAL(BASE_REG), then unset any INIT_VAL(REG)
824 : for REG within BASE_REG. */
825 11181 : if (const initial_svalue *init_sval = sval->dyn_cast_initial_svalue ())
826 2590 : if (const initial_svalue *init_key = key->dyn_cast_initial_svalue ())
827 : {
828 978 : const region *changed_reg = init_sval->get_region ();
829 978 : const region *changed_key = init_key->get_region ();
830 978 : if (changed_key->get_base_region () == changed_reg)
831 200 : svals_to_unset.add (key);
832 : }
833 : }
834 : }
835 46774 : else if (auto *bv = val.dyn_cast_bit_vector ())
836 : {
837 56396 : for (map_t::iterator iter = m_map.begin ();
838 103170 : iter != m_map.end ();
839 9622 : ++iter)
840 : {
841 9622 : const svalue *key = (*iter).first;
842 9622 : entry_t e = (*iter).second;
843 : /* We only want to purge state for some states when things
844 : are mutable. For example, in sm-malloc.cc, an on-stack ptr
845 : doesn't stop being stack-allocated when passed to an unknown fn. */
846 9622 : if (!m_sm.reset_when_passed_to_unknown_fn_p (e.m_state, is_mutable))
847 5260 : continue;
848 4362 : if (auto *sval_from_bv = key->dyn_cast_svalue_from_bit_vector ())
849 209 : if (&sval_from_bv->get_bit_vector () == bv)
850 33 : svals_to_unset.add (key);
851 : }
852 : }
853 : else
854 0 : gcc_unreachable ();
855 :
856 207026 : for (auto iter = svals_to_unset.begin ();
857 207026 : iter != svals_to_unset.end (); ++iter)
858 806 : impl_set_state (*iter, (state_machine::state_t)0, nullptr, ext_state);
859 206220 : }
860 :
861 : /* Purge state for things involving NODE.
862 : For use when NODE changes meaning, at the def_stmt on an SSA_NAME. */
863 :
864 : void
865 81662 : sm_state_map::purge_state_involving (const symbolic::node &node,
866 : const extrinsic_state &ext_state)
867 : {
868 81662 : symbolic::node_set<svalue> svals_to_unset;
869 :
870 90962 : for (map_t::iterator iter = m_map.begin ();
871 90962 : iter != m_map.end ();
872 9300 : ++iter)
873 : {
874 9300 : const svalue *key = (*iter).first;
875 9300 : entry_t e = (*iter).second;
876 9300 : if (!m_sm.can_purge_p (e.m_state))
877 3659 : continue;
878 5641 : if (key->involves_p (node))
879 9 : svals_to_unset.add (key);
880 : }
881 :
882 81671 : for (auto iter = svals_to_unset.begin ();
883 81671 : iter != svals_to_unset.end (); ++iter)
884 9 : impl_set_state (*iter, (state_machine::state_t)0, nullptr, ext_state);
885 81662 : }
886 :
887 : /* Comparator for imposing an order on sm_state_map instances. */
888 :
889 : int
890 346306 : sm_state_map::cmp (const sm_state_map &smap_a, const sm_state_map &smap_b)
891 : {
892 346306 : if (int cmp_count = smap_a.elements () - smap_b.elements ())
893 : return cmp_count;
894 :
895 296928 : auto_vec <const svalue *> keys_a (smap_a.elements ());
896 296928 : for (map_t::iterator iter = smap_a.begin ();
897 370462 : iter != smap_a.end ();
898 73534 : ++iter)
899 73534 : keys_a.quick_push ((*iter).first);
900 296928 : keys_a.qsort (svalue::cmp_ptr_ptr);
901 :
902 296928 : auto_vec <const svalue *> keys_b (smap_b.elements ());
903 296928 : for (map_t::iterator iter = smap_b.begin ();
904 370462 : iter != smap_b.end ();
905 73534 : ++iter)
906 73534 : keys_b.quick_push ((*iter).first);
907 296928 : keys_b.qsort (svalue::cmp_ptr_ptr);
908 :
909 296928 : unsigned i;
910 296928 : const svalue *sval_a;
911 394126 : FOR_EACH_VEC_ELT (keys_a, i, sval_a)
912 : {
913 69473 : const svalue *sval_b = keys_b[i];
914 69473 : if (int cmp_sval = svalue::cmp_ptr (sval_a, sval_b))
915 9833 : return cmp_sval;
916 65946 : const entry_t *e_a = const_cast <map_t &> (smap_a.m_map).get (sval_a);
917 65946 : const entry_t *e_b = const_cast <map_t &> (smap_b.m_map).get (sval_b);
918 65946 : if (int cmp_entry = entry_t::cmp (*e_a, *e_b))
919 : return cmp_entry;
920 : }
921 :
922 : // TODO: m_map_ubc_to_state
923 :
924 : return 0;
925 296928 : }
926 :
927 : /* Canonicalize SVAL before getting/setting it within the map.
928 : Convert all NULL pointers to (void *) to avoid state explosions
929 : involving all of the various (foo *)NULL vs (bar *)NULL. */
930 :
931 : const svalue *
932 5975649 : sm_state_map::canonicalize_svalue (const svalue *sval,
933 : const extrinsic_state &ext_state)
934 : {
935 5975649 : if (!sval)
936 : return nullptr;
937 :
938 5973230 : region_model_manager *mgr = ext_state.get_model_manager ();
939 5973230 : if (!mgr)
940 : return sval;
941 :
942 5973230 : if (sval->get_type () && POINTER_TYPE_P (sval->get_type ()))
943 : {
944 3046539 : if (tree cst = sval->maybe_get_constant ())
945 63382 : if (zerop (cst))
946 62934 : return mgr->get_or_create_constant_svalue (null_pointer_node);
947 : }
948 :
949 : /* Strip types from symbolic pointers. */
950 5910296 : if (auto *sym_ptr = sval->maybe_get_symbolic_pointer ())
951 1694008 : return mgr->get_ptr_svalue (ptr_type_node, *sym_ptr);
952 :
953 : /* Strip types from svalue_from_bit_vector. */
954 4216288 : if (auto *from_bv = sval->dyn_cast_svalue_from_bit_vector ())
955 662843 : return mgr->get_svalue_from_bit_vector (NULL_TREE,
956 662843 : from_bv->get_bit_vector ());
957 :
958 : return sval;
959 : }
960 :
961 : /* Attempt to merge this state map with OTHER, writing the result
962 : into *OUT.
963 : Return true if the merger was possible, false otherwise.
964 :
965 : Normally, only identical state maps can be merged, so that
966 : differences between state maps lead to different enodes
967 :
968 : However some state machines may support merging states to
969 : allow for discarding of less important states, and thus avoid
970 : blow-up of the exploded graph. */
971 :
972 : bool
973 527107 : sm_state_map::can_merge_with_p (const sm_state_map &other,
974 : const state_machine &sm,
975 : const extrinsic_state &ext_state,
976 : sm_state_map **out) const
977 : {
978 : /* If identical, then they merge trivially, with a copy. */
979 527107 : if (*this == other)
980 : {
981 458643 : delete *out;
982 458643 : *out = clone ();
983 458643 : return true;
984 : }
985 :
986 68464 : delete *out;
987 68464 : *out = new sm_state_map (sm);
988 :
989 : /* Otherwise, attempt to merge element by element. */
990 :
991 : /* Try to merge global state. */
992 136928 : if (state_machine::state_t merged_global_state
993 69343 : = sm.maybe_get_merged_state (get_global_state (),
994 : other.get_global_state ()))
995 67585 : (*out)->set_global_state (merged_global_state);
996 : else
997 : return false;
998 :
999 : /* Try to merge state each svalue's state (for the union
1000 : of svalues represented by each smap).
1001 : Ignore the origin information. */
1002 67585 : hash_set<const svalue *> svals;
1003 216897 : for (auto kv : *this)
1004 149312 : svals.add (kv.first);
1005 188554 : for (auto kv : other)
1006 120969 : svals.add (kv.first);
1007 114430 : for (auto sval : svals)
1008 : {
1009 106758 : state_machine::state_t this_state = get_state (sval, ext_state);
1010 106758 : state_machine::state_t other_state = other.get_state (sval, ext_state);
1011 106758 : if (state_machine::state_t merged_state
1012 106758 : = sm.maybe_get_merged_state (this_state, other_state))
1013 46845 : (*out)->impl_set_state (sval, merged_state, nullptr, ext_state);
1014 : else
1015 59913 : return false;
1016 : }
1017 :
1018 : // TODO: m_map_ubc_to_state
1019 :
1020 : /* Successfully merged all elements. */
1021 7672 : return true;
1022 67585 : }
1023 :
1024 : void
1025 11185725 : sm_state_map::validate (const extrinsic_state &ext_state) const
1026 : {
1027 12436363 : for (auto iter : m_map)
1028 : {
1029 1250638 : const svalue *key = iter.first;
1030 1250638 : state_machine::state_t state = iter.second.m_state;
1031 1250638 : const svalue *origin = iter.second.m_origin;
1032 :
1033 1250638 : gcc_assert (canonicalize_svalue (key, ext_state) == key);
1034 1250638 : if (origin)
1035 0 : gcc_assert (canonicalize_svalue (origin, ext_state) == origin);
1036 : }
1037 11185725 : }
1038 :
1039 : /* class program_state. */
1040 :
1041 : /* program_state's ctor. */
1042 :
1043 138945 : program_state::program_state (const extrinsic_state &ext_state)
1044 138945 : : m_region_model (nullptr),
1045 138945 : m_checker_states (ext_state.get_num_checkers ()),
1046 138945 : m_valid (true)
1047 : {
1048 138945 : engine *eng = ext_state.get_engine ();
1049 138945 : auto &node_mgr = eng->get_node_manager ();
1050 138945 : m_region_model = new region_model (node_mgr);
1051 138945 : const int num_states = ext_state.get_num_checkers ();
1052 1111036 : for (int i = 0; i < num_states; i++)
1053 : {
1054 972091 : sm_state_map *sm = new sm_state_map (ext_state.get_sm (i));
1055 972091 : m_checker_states.quick_push (sm);
1056 : }
1057 138945 : }
1058 :
1059 : /* Attempt to use R to replay SUMMARY into this object.
1060 : Return true if it is possible. */
1061 :
1062 : bool
1063 2898 : sm_state_map::replay_call_summary (call_summary_replay &r,
1064 : const sm_state_map &summary)
1065 : {
1066 3200 : for (auto kv : summary.m_map)
1067 : {
1068 302 : const svalue *summary_sval = kv.first;
1069 302 : const svalue *caller_sval = r.convert_svalue_from_summary (summary_sval);
1070 370 : if (!caller_sval)
1071 108 : continue;
1072 234 : caller_sval = canonicalize_svalue (caller_sval, r.get_ext_state ());
1073 234 : if (!caller_sval->can_have_associated_state_p ())
1074 40 : continue;
1075 194 : const svalue *summary_origin = kv.second.m_origin;
1076 194 : const svalue *caller_origin
1077 : = (summary_origin
1078 194 : ? r.convert_svalue_from_summary (summary_origin)
1079 : : nullptr);
1080 : // caller_origin can be nullptr.
1081 194 : m_map.put (caller_sval, entry_t (kv.second.m_state, caller_origin));
1082 : }
1083 2898 : m_global_state = summary.m_global_state;
1084 2898 : return true;
1085 : }
1086 :
1087 : /* program_state's copy ctor. */
1088 :
1089 1723569 : program_state::program_state (const program_state &other)
1090 1723569 : : m_region_model (new region_model (*other.m_region_model)),
1091 3447138 : m_checker_states (other.m_checker_states.length ()),
1092 1723569 : m_valid (true)
1093 : {
1094 1723569 : int i;
1095 1723569 : sm_state_map *smap;
1096 13777054 : FOR_EACH_VEC_ELT (other.m_checker_states, i, smap)
1097 12053485 : m_checker_states.quick_push (smap->clone ());
1098 1723569 : }
1099 :
1100 : /* program_state's assignment operator. */
1101 :
1102 : program_state&
1103 9464 : program_state::operator= (const program_state &other)
1104 : {
1105 9464 : delete m_region_model;
1106 9464 : m_region_model = new region_model (*other.m_region_model);
1107 :
1108 9464 : int i;
1109 9464 : sm_state_map *smap;
1110 75625 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
1111 66161 : delete smap;
1112 9464 : m_checker_states.truncate (0);
1113 28392 : gcc_assert (m_checker_states.space (other.m_checker_states.length ()));
1114 :
1115 75625 : FOR_EACH_VEC_ELT (other.m_checker_states, i, smap)
1116 66161 : m_checker_states.quick_push (smap->clone ());
1117 :
1118 9464 : m_valid = other.m_valid;
1119 :
1120 9464 : return *this;
1121 : }
1122 :
1123 : /* Move constructor for program_state (when building with C++11). */
1124 793385 : program_state::program_state (program_state &&other)
1125 793385 : : m_region_model (other.m_region_model),
1126 1586770 : m_checker_states (other.m_checker_states.length ())
1127 : {
1128 793385 : other.m_region_model = nullptr;
1129 :
1130 793385 : int i;
1131 793385 : sm_state_map *smap;
1132 7134977 : FOR_EACH_VEC_ELT (other.m_checker_states, i, smap)
1133 5548207 : m_checker_states.quick_push (smap);
1134 793385 : other.m_checker_states.truncate (0);
1135 :
1136 793385 : m_valid = other.m_valid;
1137 793385 : }
1138 :
1139 : /* Move assignment for program_state. */
1140 :
1141 : program_state&
1142 25306 : program_state::operator= (program_state &&other)
1143 : {
1144 25306 : if (this == &other)
1145 : return *this;
1146 :
1147 25306 : delete m_region_model;
1148 25306 : m_region_model = other.m_region_model;
1149 25306 : other.m_region_model = nullptr;
1150 :
1151 25306 : int i;
1152 25306 : sm_state_map *smap;
1153 227754 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
1154 177142 : delete smap;
1155 25306 : m_checker_states.truncate (0);
1156 75918 : gcc_assert (m_checker_states.space (other.m_checker_states.length ()));
1157 227754 : FOR_EACH_VEC_ELT (other.m_checker_states, i, smap)
1158 177142 : m_checker_states.quick_push (smap);
1159 25306 : other.m_checker_states.truncate (0);
1160 :
1161 25306 : m_valid = other.m_valid;
1162 :
1163 25306 : return *this;
1164 : }
1165 :
1166 : /* program_state's dtor. */
1167 :
1168 2655899 : program_state::~program_state ()
1169 : {
1170 2655899 : delete m_region_model;
1171 2655899 : }
1172 :
1173 : /* Generate a hash value for this program_state. */
1174 :
1175 : hashval_t
1176 415735 : program_state::hash () const
1177 : {
1178 415735 : hashval_t result = m_region_model->hash ();
1179 :
1180 415735 : int i;
1181 415735 : sm_state_map *smap;
1182 3738854 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
1183 2907384 : result ^= smap->hash ();
1184 415735 : return result;
1185 : }
1186 :
1187 : /* Equality operator for program_state.
1188 : All parts of the program_state (region model, checker states) must
1189 : equal their counterparts in OTHER for the two program_states to be
1190 : considered equal. */
1191 :
1192 : bool
1193 66199 : program_state::operator== (const program_state &other) const
1194 : {
1195 66199 : if (!(*m_region_model == *other.m_region_model))
1196 : return false;
1197 :
1198 : int i;
1199 : sm_state_map *smap;
1200 59149 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
1201 52020 : if (!(*smap == *other.m_checker_states[i]))
1202 : return false;
1203 :
1204 7129 : gcc_checking_assert (hash () == other.hash ());
1205 :
1206 : return true;
1207 : }
1208 :
1209 : /* Dump a tree-like representation of this state to stderr. */
1210 :
1211 : DEBUG_FUNCTION void
1212 0 : program_state::dump () const
1213 : {
1214 0 : symbolic::dump_node_tree_to_stderr<program_state> (*this);
1215 0 : }
1216 :
1217 : /* Dump a tree-like representation of this state to LOG. */
1218 :
1219 : void
1220 713 : program_state::dump_to_logger (logger &log, const char *label) const
1221 : {
1222 713 : symbolic::dump_node_tree_to_logger<program_state> (*this, log, label);
1223 713 : }
1224 :
1225 : /* Return a new json::object of the form
1226 : {"store" : object for store,
1227 : "constraints" : object for constraint_manager,
1228 : "curr_frame" : (optional) str for current frame,
1229 : "checkers" : { STATE_NAME : object per sm_state_map },
1230 : "valid" : true/false}. */
1231 :
1232 : std::unique_ptr<json::object>
1233 15 : program_state::to_json (const extrinsic_state &ext_state) const
1234 : {
1235 15 : auto state_obj = std::make_unique<json::object> ();
1236 :
1237 15 : state_obj->set ("store", m_region_model->get_store ()->to_json ());
1238 15 : state_obj->set ("constraints",
1239 15 : m_region_model->get_constraints ()->to_json ());
1240 15 : if (m_region_model->get_current_frame ())
1241 14 : state_obj->set ("curr_frame",
1242 14 : m_region_model->get_current_frame ()->to_json ());
1243 :
1244 : /* Provide m_checker_states as an object, using names as keys. */
1245 15 : {
1246 15 : auto checkers_obj = std::make_unique<json::object> ();
1247 :
1248 15 : int i;
1249 15 : sm_state_map *smap;
1250 135 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
1251 105 : if (!smap->is_empty_p ())
1252 9 : checkers_obj->set (ext_state.get_name (i), smap->to_json ());
1253 :
1254 15 : state_obj->set ("checkers", std::move (checkers_obj));
1255 15 : }
1256 :
1257 15 : state_obj->set_bool ("valid", m_valid);
1258 :
1259 15 : return state_obj;
1260 : }
1261 :
1262 :
1263 : std::unique_ptr<text_art::tree_widget>
1264 713 : program_state::make_dump_widget (symbolic::node_dump_state &nds,
1265 : const char *label) const
1266 : {
1267 713 : if (!label)
1268 338 : label = "program_state";
1269 :
1270 713 : using text_art::tree_widget;
1271 713 : std::unique_ptr<tree_widget> state_widget
1272 713 : (tree_widget::from_fmt (nds, nullptr, "%s", label));
1273 :
1274 1426 : state_widget->add_child (m_region_model->make_dump_widget (nds));
1275 :
1276 : /* Add nodes for any sm_state_maps with state. */
1277 713 : {
1278 713 : int i;
1279 713 : sm_state_map *smap;
1280 5704 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
1281 4991 : if (!smap->is_empty_p ())
1282 140 : state_widget->add_child (smap->make_dump_widget (nds, m_region_model));
1283 : }
1284 :
1285 713 : return state_widget;
1286 : }
1287 :
1288 : void
1289 0 : program_state::dump_dot (const extrinsic_state &ext_state) const
1290 : {
1291 0 : auto state_graph = make_diagnostic_state_graph (ext_state);
1292 :
1293 0 : gcc_assert (global_dc);
1294 0 : auto logical_loc_mgr = global_dc->get_logical_location_manager ();
1295 0 : gcc_assert (logical_loc_mgr);
1296 :
1297 0 : auto graph = diagnostics::state_graphs::make_dot_graph (*state_graph,
1298 0 : *logical_loc_mgr);
1299 :
1300 0 : pretty_printer pp;
1301 0 : dot::writer w (pp);
1302 0 : graph->print (w);
1303 0 : pp_flush (&pp);
1304 0 : }
1305 :
1306 : /* Update this program_state to reflect a top-level call to FUN.
1307 : The params will have initial_svalues. */
1308 :
1309 : void
1310 11520 : program_state::push_frame (const extrinsic_state &ext_state ATTRIBUTE_UNUSED,
1311 : const function &fun)
1312 : {
1313 11520 : m_region_model->push_frame (fun, nullptr, nullptr, nullptr);
1314 11520 : }
1315 :
1316 : /* Get the current function of this state. */
1317 :
1318 : const function *
1319 22 : program_state::get_current_function () const
1320 : {
1321 22 : return m_region_model->get_current_function ();
1322 : }
1323 :
1324 : /* Generate a simpler version of THIS, discarding state that's no longer
1325 : relevant at POINT.
1326 : The idea is that we're more likely to be able to consolidate
1327 : multiple (point, state) into single exploded_nodes if we discard
1328 : irrelevant state (e.g. at the end of functions). */
1329 :
1330 : program_state
1331 376171 : program_state::prune_for_point (exploded_graph &eg,
1332 : const program_point &point,
1333 : exploded_node *enode_for_diag,
1334 : uncertainty_t *uncertainty) const
1335 : {
1336 376171 : logger * const logger = eg.get_logger ();
1337 376171 : LOG_SCOPE (logger);
1338 :
1339 376171 : function *fun = point.get_function ();
1340 372598 : if (!fun)
1341 3573 : return *this;
1342 :
1343 372598 : program_state new_state (*this);
1344 :
1345 372598 : const state_purge_map *pm = eg.get_purge_map ();
1346 372598 : if (pm)
1347 : {
1348 372136 : unsigned num_ssas_purged = 0;
1349 372136 : unsigned num_decls_purged = 0;
1350 372136 : auto_vec<const decl_region *> regs;
1351 372136 : new_state.m_region_model->get_regions_for_current_frame (®s);
1352 372136 : regs.qsort (region::cmp_ptr_ptr);
1353 372136 : unsigned i;
1354 372136 : const decl_region *reg;
1355 1285993 : FOR_EACH_VEC_ELT (regs, i, reg)
1356 : {
1357 913857 : const tree node = reg->get_decl ();
1358 913857 : if (TREE_CODE (node) == SSA_NAME)
1359 : {
1360 785839 : const tree ssa_name = node;
1361 785839 : const state_purge_per_ssa_name &per_ssa
1362 785839 : = pm->get_data_for_ssa_name (node);
1363 785839 : if (!per_ssa.needed_at_supernode_p (point.get_supernode ()))
1364 : {
1365 : /* Don't purge bindings of SSA names to svalues
1366 : that have unpurgable sm-state, so that leaks are
1367 : reported at the end of the function, rather than
1368 : at the last place that such an SSA name is referred to.
1369 :
1370 : But do purge them for temporaries (when SSA_NAME_VAR is
1371 : NULL), so that we report for cases where a leak happens when
1372 : a variable is overwritten with another value, so that the leak
1373 : is reported at the point of overwrite, rather than having
1374 : temporaries keep the value reachable until the frame is
1375 : popped. */
1376 191202 : const svalue *sval
1377 191202 : = new_state.m_region_model->get_store_value (reg, nullptr);
1378 191202 : if (!new_state.can_purge_p (eg.get_ext_state (), sval)
1379 216529 : && SSA_NAME_VAR (ssa_name))
1380 : {
1381 : /* (currently only state maps can keep things
1382 : alive). */
1383 19430 : if (logger)
1384 0 : logger->log ("not purging binding for %qE"
1385 : " (used by state map)", ssa_name);
1386 19430 : continue;
1387 : }
1388 :
1389 171772 : new_state.m_region_model->purge_region (reg);
1390 171772 : num_ssas_purged++;
1391 : }
1392 : }
1393 : else
1394 : {
1395 128018 : const tree decl = node;
1396 128018 : gcc_assert (TREE_CODE (node) == VAR_DECL
1397 : || TREE_CODE (node) == PARM_DECL
1398 : || TREE_CODE (node) == RESULT_DECL);
1399 256036 : if (const state_purge_per_decl *per_decl
1400 128018 : = pm->get_any_data_for_decl (decl))
1401 102050 : if (!per_decl->needed_at_supernode_p (point.get_supernode ()))
1402 : {
1403 : /* Don't purge bindings of decls if there are svalues
1404 : that have unpurgable sm-state within the decl's cluster,
1405 : so that leaks are reported at the end of the function,
1406 : rather than at the last place that such a decl is
1407 : referred to. */
1408 1957 : if (!new_state.can_purge_base_region_p (eg.get_ext_state (),
1409 : reg))
1410 : {
1411 : /* (currently only state maps can keep things
1412 : alive). */
1413 620 : if (logger)
1414 0 : logger->log ("not purging binding for %qE"
1415 : " (value in binding used by state map)",
1416 : decl);
1417 620 : continue;
1418 : }
1419 :
1420 1337 : new_state.m_region_model->purge_region (reg);
1421 1337 : num_decls_purged++;
1422 : }
1423 : }
1424 : }
1425 :
1426 372136 : if (num_ssas_purged > 0 || num_decls_purged > 0)
1427 : {
1428 143107 : if (logger)
1429 : {
1430 49 : logger->log ("num_ssas_purged: %i", num_ssas_purged);
1431 49 : logger->log ("num_decl_purged: %i", num_decls_purged);
1432 : }
1433 143107 : impl_region_model_context ctxt (eg, enode_for_diag,
1434 : this,
1435 : &new_state,
1436 : uncertainty,
1437 143107 : nullptr);
1438 143107 : detect_leaks (*this, new_state, nullptr, eg.get_ext_state (), &ctxt);
1439 143107 : }
1440 372136 : }
1441 :
1442 372598 : new_state.m_region_model->canonicalize ();
1443 :
1444 372598 : return new_state;
1445 376171 : }
1446 :
1447 : /* Return true if there are no unpurgeable bindings within BASE_REG. */
1448 :
1449 : bool
1450 1957 : program_state::can_purge_base_region_p (const extrinsic_state &ext_state,
1451 : const region *base_reg) const
1452 : {
1453 1957 : binding_cluster *cluster
1454 1957 : = m_region_model->get_store ()->get_cluster (base_reg);
1455 1957 : if (!cluster)
1456 : return true;
1457 :
1458 1957 : symbolic::node_set<symbolic::value_node> bound_value_nodes;
1459 1957 : cluster->for_each_value ([](const symbolic::value_node &val,
1460 : void *user_data) -> iter_result
1461 : {
1462 : auto *bound_value_nodes
1463 : = static_cast <symbolic::node_set<symbolic::value_node> *> (user_data);
1464 : bound_value_nodes->add (&val);
1465 : return iter_result::keep_going;
1466 : }, &bound_value_nodes);
1467 :
1468 1957 : if (bound_value_nodes.empty ())
1469 : return true;
1470 :
1471 1907 : auto &bv_mgr
1472 1907 : = ext_state.get_node_manager ().get_bit_vector_manager ();
1473 :
1474 1907 : int i;
1475 1907 : sm_state_map *smap;
1476 12876 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
1477 19726 : for (auto iter : *smap)
1478 : {
1479 1702 : const svalue *sval = iter.first;
1480 1702 : sm_state_map::entry_t e = iter.second;
1481 1702 : if (!ext_state.get_sm (i).can_purge_p (e.m_state))
1482 : {
1483 1022 : if (bound_value_nodes.contains (sval))
1484 620 : return false;
1485 :
1486 1022 : if (auto *as_bv = bv_mgr.maybe_get_bit_vector_from_svalue (*sval))
1487 : {
1488 1022 : if (bound_value_nodes.contains (as_bv))
1489 : return false;
1490 : }
1491 : }
1492 : }
1493 :
1494 : return true;
1495 1957 : }
1496 :
1497 : /* Get a representative tree to use for describing SVAL. */
1498 :
1499 : tree
1500 0 : program_state::get_representative_tree (const svalue *sval) const
1501 : {
1502 0 : gcc_assert (m_region_model);
1503 0 : return m_region_model->get_representative_tree (sval);
1504 : }
1505 :
1506 : /* Attempt to merge this state with OTHER, both at POINT.
1507 : Write the result to *OUT.
1508 : If the states were merged successfully, return true. */
1509 :
1510 : bool
1511 123822 : program_state::can_merge_with_p (const program_state &other,
1512 : const extrinsic_state &ext_state,
1513 : const program_point &point,
1514 : program_state *out) const
1515 : {
1516 123822 : gcc_assert (out);
1517 123822 : gcc_assert (m_region_model);
1518 :
1519 : /* Attempt to merge the sm-states. */
1520 : int i;
1521 : sm_state_map *smap;
1522 590137 : FOR_EACH_VEC_ELT (out->m_checker_states, i, smap)
1523 1054214 : if (!m_checker_states[i]->can_merge_with_p (*other.m_checker_states[i],
1524 : ext_state.get_sm (i),
1525 : ext_state,
1526 527107 : &out->m_checker_states[i]))
1527 : return false;
1528 :
1529 : /* Attempt to merge the region_models. */
1530 63030 : if (!m_region_model->can_merge_with_p (*other.m_region_model,
1531 : point,
1532 : out->m_region_model,
1533 : &ext_state,
1534 : this, &other))
1535 : return false;
1536 :
1537 37496 : out->m_region_model->canonicalize ();
1538 :
1539 37496 : return true;
1540 : }
1541 :
1542 : /* Assert that this object is valid. */
1543 :
1544 : void
1545 1599565 : program_state::validate (const extrinsic_state &ext_state) const
1546 : {
1547 : /* Skip this in a release build. */
1548 : #if !CHECKING_P
1549 : return;
1550 : #endif
1551 :
1552 3199130 : gcc_assert (m_checker_states.length () == ext_state.get_num_checkers ());
1553 1599565 : m_region_model->validate ();
1554 :
1555 1599565 : int i;
1556 1599565 : sm_state_map *smap;
1557 14384855 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
1558 11185725 : m_checker_states[i]->validate (ext_state);
1559 1599565 : }
1560 :
1561 : static void
1562 256 : log_set_of_values (logger *logger, const char *name,
1563 : const value_set &set)
1564 : {
1565 256 : logger->log ("%s", name);
1566 256 : logger->inc_indent ();
1567 256 : auto_vec<const symbolic::value_node *> val_vec (set.size ());
1568 256 : for (value_set::iterator iter = set.begin ();
1569 2000 : iter != set.end (); ++iter)
1570 1744 : val_vec.quick_push (*iter);
1571 256 : val_vec.qsort (svalue::cmp_ptr_ptr);
1572 256 : unsigned i;
1573 256 : const symbolic::value_node *val;
1574 2000 : FOR_EACH_VEC_ELT (val_vec, i, val)
1575 1744 : val->dump_to_logger (*logger);
1576 256 : logger->dec_indent ();
1577 256 : }
1578 :
1579 : // class symbolic::liveness_context
1580 :
1581 : namespace symbolic {
1582 :
1583 1532107 : liveness_context::liveness_context (const value_set &known_live_values,
1584 : const region_model &model)
1585 1532107 : : m_model (model)
1586 : {
1587 6141607 : for (auto iter : known_live_values)
1588 4609500 : set_known_liveness_for_node (*iter, true);
1589 1532107 : }
1590 :
1591 : bool
1592 5162038 : liveness_context::node_live_p (const symbolic::value_node &n)
1593 : {
1594 : /* Do we already know the liveness of N? */
1595 5162038 : auto iter = m_known_liveness.find (&n);
1596 5162038 : if (iter != m_known_liveness.end ())
1597 3693927 : return iter->second;
1598 :
1599 : /* Otherwise, determine if SVAL is implicitly live due to being made of
1600 : other live svalues. */
1601 1468111 : bool implicitly_live = n.implicitly_live_p (*this);
1602 1468111 : set_known_liveness_for_node (n, implicitly_live);
1603 1468111 : return implicitly_live;
1604 : }
1605 :
1606 : bool
1607 287978 : liveness_context::bits_live_p (const bit_vector_from_ubc &bv_from_ubc)
1608 : {
1609 287978 : return m_model.bits_live_p (bv_from_ubc);
1610 : }
1611 :
1612 : /* Consider any pointer to base_reg in LIVENESS_CTXT as keeping it live, so
1613 : that different (X*)ptr and (Y*)ptr are effectively the same from
1614 : a liveness perspective. */
1615 :
1616 : bool
1617 184983 : liveness_context::known_live_ptr_to_base_region_p (const region &base_reg) const
1618 : {
1619 184983 : auto iter = m_known_base_regions.find (&base_reg);
1620 184983 : if (iter != m_known_base_regions.end ())
1621 147021 : return true;
1622 :
1623 : return false;
1624 : }
1625 :
1626 : void
1627 6077611 : liveness_context::set_known_liveness_for_node (const symbolic::value_node &n,
1628 : bool is_live)
1629 : {
1630 6077611 : m_known_liveness.insert ({&n, is_live});
1631 :
1632 : /* Consider any pointer to a base region as keeping that region live, so
1633 : that different (X*)ptr and (Y*)ptr are effectively the same from
1634 : a liveness perspective. */
1635 6077611 : if (is_live)
1636 5911638 : if (auto *sval = n.dyn_cast_svalue ())
1637 3729206 : if (auto *sym_ptr = sval->maybe_get_symbolic_pointer ())
1638 531300 : m_known_base_regions.insert (&sym_ptr->get_base_region ());
1639 6077611 : }
1640 :
1641 : void
1642 0 : liveness_context::dump_to_pp (pretty_printer *pp) const
1643 : {
1644 0 : text_art::theme *theme = global_dc->get_diagram_theme ();
1645 0 : symbolic::dump_node_tree_to_pp<liveness_context>
1646 0 : (*this, theme, pp,
1647 : true /* show_ids */,
1648 : true /* elide_repeated_nodes */);
1649 0 : }
1650 :
1651 : std::unique_ptr<text_art::tree_widget>
1652 0 : liveness_context::make_dump_widget (symbolic::node_dump_state &nds) const
1653 : {
1654 0 : using text_art::tree_widget;
1655 0 : std::unique_ptr<tree_widget> widget
1656 0 : = tree_widget::from_fmt (nds, nullptr, "impl_liveness_context");
1657 0 : for (auto iter : m_known_liveness)
1658 : {
1659 0 : const symbolic::value_node *node = iter.first;
1660 0 : bool liveness = iter.second;
1661 0 : const char *prefix = liveness ? "live" : "dead";
1662 0 : widget->add_child (node->make_dump_widget (nds, prefix));
1663 : }
1664 0 : for (auto iter : m_known_base_regions)
1665 0 : widget->add_child (iter->make_dump_widget (nds, "known region"));
1666 0 : widget->add_child (m_model.make_dump_widget (nds));
1667 0 : return widget;
1668 : }
1669 :
1670 : } // namespace ana::symbolic
1671 :
1672 : /* Compare the sets of svalues reachable from each of SRC_STATE and DEST_STATE.
1673 : For all svalues that are reachable in SRC_STATE and are not live in
1674 : DEST_STATE (whether explicitly reachable in DEST_STATE, or implicitly live
1675 : based on the former set), call CTXT->on_svalue_leak for them.
1676 :
1677 : Call on_liveness_change on both the CTXT and on the DEST_STATE's
1678 : constraint_manager, purging dead svalues from sm-state and from
1679 : constraints, respectively.
1680 :
1681 : This function should be called at each fine-grained state change, not
1682 : just at exploded edges. */
1683 :
1684 : void
1685 433757 : program_state::detect_leaks (const program_state &src_state,
1686 : const program_state &dest_state,
1687 : const svalue *extra_sval,
1688 : const extrinsic_state &ext_state,
1689 : region_model_context *ctxt)
1690 : {
1691 433757 : logger *logger = ext_state.get_logger ();
1692 433757 : LOG_SCOPE (logger);
1693 433757 : const uncertainty_t *uncertainty = ctxt->get_uncertainty ();
1694 433757 : if (logger)
1695 : {
1696 128 : src_state.dump_to_logger (*logger, "src_state");
1697 128 : dest_state.dump_to_logger (*logger, "dest_state");
1698 128 : if (extra_sval)
1699 : {
1700 1 : logger->log ("extra_sval:");
1701 1 : extra_sval->dump_to_logger (*logger);
1702 : }
1703 128 : if (uncertainty)
1704 114 : uncertainty->dump_to_logger (*logger);
1705 : }
1706 :
1707 : /* Get svalues reachable from each of src_state and dest_state.
1708 : Get svalues *known* to be reachable in src_state.
1709 : Pass in uncertainty for dest_state so that we additionally get svalues that
1710 : *might* still be reachable in dst_state. */
1711 433757 : value_set known_src_svalues;
1712 433757 : src_state.m_region_model->get_reachable_svalues (&known_src_svalues,
1713 : nullptr, nullptr);
1714 433757 : value_set maybe_dest_svalues;
1715 433757 : dest_state.m_region_model->get_reachable_svalues (&maybe_dest_svalues,
1716 : extra_sval, uncertainty);
1717 :
1718 433757 : if (logger)
1719 : {
1720 128 : log_set_of_values (logger, "src_state known reachable values:",
1721 : known_src_svalues);
1722 128 : log_set_of_values (logger, "dest_state maybe reachable values:",
1723 : maybe_dest_svalues);
1724 : }
1725 :
1726 433757 : symbolic::liveness_context dest_liveness (maybe_dest_svalues,
1727 433757 : *dest_state.m_region_model);
1728 :
1729 433757 : auto_vec <const svalue *> dead_svals (known_src_svalues.size ());
1730 5065923 : for (value_set::iterator iter = known_src_svalues.begin ();
1731 5065923 : iter != known_src_svalues.end (); ++iter)
1732 4632166 : if (auto *sval = (*iter)->dyn_cast_svalue ())
1733 : {
1734 : /* For each sval reachable from SRC_STATE, determine if it is
1735 : live in DEST_STATE: either explicitly reachable, implicitly
1736 : live based on the set of explicitly reachable svalues,
1737 : or possibly reachable as recorded in uncertainty.
1738 : Record those that have ceased to be live i.e. were known
1739 : to be live, and are now not known to be even possibly-live. */
1740 2647080 : if (!dest_liveness.node_live_p (*sval))
1741 24808 : dead_svals.quick_push (sval);
1742 : }
1743 :
1744 : /* Call CTXT->on_svalue_leak on all svals in SRC_STATE that have ceased
1745 : to be live, sorting them first to ensure deterministic behavior. */
1746 433757 : dead_svals.qsort (svalue::cmp_ptr_ptr);
1747 433757 : unsigned i;
1748 433757 : const svalue *sval;
1749 458565 : FOR_EACH_VEC_ELT (dead_svals, i, sval)
1750 24808 : ctxt->on_svalue_leak (sval);
1751 :
1752 : /* Purge dead svals from sm-state. */
1753 433757 : ctxt->on_liveness_change (dest_liveness);
1754 :
1755 : /* Purge dead svals from constraints. */
1756 433757 : dest_state.m_region_model->get_constraints ()->on_liveness_change
1757 433757 : (dest_liveness);
1758 :
1759 : /* Purge dead heap-allocated regions from dynamic extents. */
1760 1218477 : for (const svalue *sval : dead_svals)
1761 24808 : if (auto *sym_ptr = sval->maybe_get_symbolic_pointer ())
1762 : {
1763 14099 : const region ® = sym_ptr->get_base_region ();
1764 14099 : if (reg.get_kind () == RK_HEAP_ALLOCATED)
1765 6920 : dest_state.m_region_model->unset_dynamic_extents (®);
1766 : }
1767 433757 : }
1768 :
1769 : /* Attempt to use R to replay SUMMARY into this object.
1770 : Return true if it is possible. */
1771 :
1772 : bool
1773 635 : program_state::replay_call_summary (call_summary_replay &r,
1774 : const program_state &summary)
1775 : {
1776 635 : if (!m_region_model->replay_call_summary (r, *summary.m_region_model))
1777 : return false;
1778 :
1779 3312 : for (unsigned sm_idx = 0; sm_idx < m_checker_states.length (); sm_idx++)
1780 : {
1781 2898 : const sm_state_map *summary_sm_map = summary.m_checker_states[sm_idx];
1782 2898 : m_checker_states[sm_idx]->replay_call_summary (r, *summary_sm_map);
1783 : }
1784 :
1785 414 : if (!summary.m_valid)
1786 0 : m_valid = false;
1787 :
1788 : return true;
1789 : }
1790 :
1791 : /* Handle calls to "__analyzer_dump_state". */
1792 :
1793 : void
1794 377 : program_state::impl_call_analyzer_dump_state (const gcall &call,
1795 : const extrinsic_state &ext_state,
1796 : region_model_context *ctxt)
1797 : {
1798 377 : call_details cd (call, m_region_model, ctxt);
1799 377 : const char *sm_name = cd.get_arg_string_literal (0);
1800 377 : if (!sm_name)
1801 : {
1802 4 : error_at (call.location, "cannot determine state machine");
1803 12 : return;
1804 : }
1805 373 : unsigned sm_idx;
1806 373 : if (!ext_state.get_sm_idx_by_name (sm_name, &sm_idx))
1807 : {
1808 4 : error_at (call.location, "unrecognized state machine %qs", sm_name);
1809 4 : return;
1810 : }
1811 369 : const sm_state_map *smap = m_checker_states[sm_idx];
1812 :
1813 369 : const svalue *sval = cd.get_arg_svalue (1);
1814 :
1815 : /* Strip off cast to int (due to variadic args). */
1816 369 : if (const svalue *cast = sval->maybe_undo_cast ())
1817 30 : sval = cast;
1818 :
1819 369 : state_machine::state_t state = smap->get_state (sval, ext_state);
1820 369 : warning_at (call.location, 0, "state: %qs", state->get_name ());
1821 : }
1822 :
1823 : #if CHECKING_P
1824 :
1825 : namespace selftest {
1826 :
1827 : /* Tests for sm_state_map. */
1828 :
1829 : static void
1830 4 : test_sm_state_map ()
1831 : {
1832 4 : tree x = build_global_decl ("x", integer_type_node);
1833 4 : tree y = build_global_decl ("y", integer_type_node);
1834 4 : tree z = build_global_decl ("z", integer_type_node);
1835 :
1836 4 : std::unique_ptr<state_machine> sm = make_malloc_state_machine (nullptr);
1837 4 : state_machine::state_t start = sm->get_start_state ();
1838 4 : std::vector<std::unique_ptr<state_machine>> checkers;
1839 4 : const state_machine &borrowed_sm = *sm.get ();
1840 4 : checkers.push_back (std::move (sm));
1841 4 : symbolic::node_manager node_mgr;
1842 4 : engine eng (node_mgr);
1843 4 : extrinsic_state ext_state (std::move (checkers), &eng);
1844 :
1845 : /* Test setting states on svalue_id instances directly. */
1846 4 : {
1847 4 : const state_machine::state test_state_42 ("test state 42", 42);
1848 4 : const state_machine::state_t TEST_STATE_42 = &test_state_42;
1849 4 : region_model model (node_mgr);
1850 4 : const svalue *x_sval = model.get_rvalue (x, nullptr);
1851 4 : const svalue *y_sval = model.get_rvalue (y, nullptr);
1852 4 : const svalue *z_sval = model.get_rvalue (z, nullptr);
1853 :
1854 4 : sm_state_map map (borrowed_sm);
1855 4 : ASSERT_TRUE (map.is_empty_p ());
1856 4 : ASSERT_EQ (map.get_state (x_sval, ext_state), start);
1857 :
1858 4 : map.impl_set_state (x_sval, TEST_STATE_42, z_sval, ext_state);
1859 4 : ASSERT_EQ (map.get_state (x_sval, ext_state), TEST_STATE_42);
1860 4 : ASSERT_EQ (map.get_origin (x_sval, ext_state), z_sval);
1861 4 : ASSERT_EQ (map.get_state (y_sval, ext_state), start);
1862 4 : ASSERT_FALSE (map.is_empty_p ());
1863 :
1864 4 : map.impl_set_state (y_sval, 0, z_sval, ext_state);
1865 4 : ASSERT_EQ (map.get_state (y_sval, ext_state), start);
1866 :
1867 4 : map.impl_set_state (x_sval, 0, z_sval, ext_state);
1868 4 : ASSERT_EQ (map.get_state (x_sval, ext_state), start);
1869 4 : ASSERT_TRUE (map.is_empty_p ());
1870 4 : }
1871 :
1872 4 : const state_machine::state test_state_5 ("test state 5", 5);
1873 4 : const state_machine::state_t TEST_STATE_5 = &test_state_5;
1874 :
1875 : /* Test setting states via equivalence classes. */
1876 4 : {
1877 4 : region_model model (node_mgr);
1878 4 : const svalue *x_sval = model.get_rvalue (x, nullptr);
1879 4 : const svalue *y_sval = model.get_rvalue (y, nullptr);
1880 4 : const svalue *z_sval = model.get_rvalue (z, nullptr);
1881 :
1882 4 : sm_state_map map (borrowed_sm);
1883 4 : ASSERT_TRUE (map.is_empty_p ());
1884 4 : ASSERT_EQ (map.get_state (x_sval, ext_state), start);
1885 4 : ASSERT_EQ (map.get_state (y_sval, ext_state), start);
1886 :
1887 4 : model.add_constraint (x, EQ_EXPR, y, nullptr);
1888 :
1889 : /* Setting x to a state should also update y, as they
1890 : are in the same equivalence class. */
1891 4 : map.set_state (&model, x_sval, TEST_STATE_5, z_sval, ext_state);
1892 4 : ASSERT_EQ (map.get_state (x_sval, ext_state), TEST_STATE_5);
1893 4 : ASSERT_EQ (map.get_state (y_sval, ext_state), TEST_STATE_5);
1894 4 : ASSERT_EQ (map.get_origin (x_sval, ext_state), z_sval);
1895 4 : ASSERT_EQ (map.get_origin (y_sval, ext_state), z_sval);
1896 4 : }
1897 :
1898 : /* Test equality and hashing. */
1899 4 : {
1900 4 : region_model model (node_mgr);
1901 4 : const svalue *y_sval = model.get_rvalue (y, nullptr);
1902 4 : const svalue *z_sval = model.get_rvalue (z, nullptr);
1903 :
1904 4 : sm_state_map map0 (borrowed_sm);
1905 4 : sm_state_map map1 (borrowed_sm);
1906 4 : sm_state_map map2 (borrowed_sm);
1907 :
1908 4 : ASSERT_EQ (map0.hash (), map1.hash ());
1909 4 : ASSERT_EQ (map0, map1);
1910 :
1911 4 : map1.impl_set_state (y_sval, TEST_STATE_5, z_sval, ext_state);
1912 4 : ASSERT_NE (map0.hash (), map1.hash ());
1913 4 : ASSERT_NE (map0, map1);
1914 :
1915 : /* Make the same change to map2. */
1916 4 : map2.impl_set_state (y_sval, TEST_STATE_5, z_sval, ext_state);
1917 4 : ASSERT_EQ (map1.hash (), map2.hash ());
1918 4 : ASSERT_EQ (map1, map2);
1919 4 : }
1920 :
1921 : /* Equality and hashing shouldn't depend on ordering. */
1922 4 : {
1923 4 : const state_machine::state test_state_2 ("test state 2", 2);
1924 4 : const state_machine::state_t TEST_STATE_2 = &test_state_2;
1925 4 : const state_machine::state test_state_3 ("test state 3", 3);
1926 4 : const state_machine::state_t TEST_STATE_3 = &test_state_3;
1927 4 : sm_state_map map0 (borrowed_sm);
1928 4 : sm_state_map map1 (borrowed_sm);
1929 4 : sm_state_map map2 (borrowed_sm);
1930 :
1931 4 : ASSERT_EQ (map0.hash (), map1.hash ());
1932 4 : ASSERT_EQ (map0, map1);
1933 :
1934 4 : region_model model (node_mgr);
1935 4 : const svalue *x_sval = model.get_rvalue (x, nullptr);
1936 4 : const svalue *y_sval = model.get_rvalue (y, nullptr);
1937 4 : const svalue *z_sval = model.get_rvalue (z, nullptr);
1938 :
1939 4 : map1.impl_set_state (x_sval, TEST_STATE_2, nullptr, ext_state);
1940 4 : map1.impl_set_state (y_sval, TEST_STATE_3, nullptr, ext_state);
1941 4 : map1.impl_set_state (z_sval, TEST_STATE_2, nullptr, ext_state);
1942 :
1943 4 : map2.impl_set_state (z_sval, TEST_STATE_2, nullptr, ext_state);
1944 4 : map2.impl_set_state (y_sval, TEST_STATE_3, nullptr, ext_state);
1945 4 : map2.impl_set_state (x_sval, TEST_STATE_2, nullptr, ext_state);
1946 :
1947 4 : ASSERT_EQ (map1.hash (), map2.hash ());
1948 4 : ASSERT_EQ (map1, map2);
1949 4 : }
1950 :
1951 : // TODO: coverage for purging
1952 4 : }
1953 :
1954 : /* Check program_state works as expected. */
1955 :
1956 : static void
1957 4 : test_program_state_1 ()
1958 : {
1959 : /* Create a program_state for a global ptr "p" that has
1960 : malloc sm-state, pointing to a region on the heap. */
1961 4 : tree p = build_global_decl ("p", ptr_type_node);
1962 :
1963 4 : std::unique_ptr<state_machine> sm = make_malloc_state_machine (nullptr);
1964 4 : const state_machine::state_t UNCHECKED_STATE
1965 4 : = sm->get_state_by_name ("unchecked");
1966 :
1967 4 : symbolic::node_manager node_mgr;
1968 4 : auto &mgr = node_mgr.get_region_model_manager ();
1969 4 : engine eng (node_mgr);
1970 4 : extrinsic_state ext_state (std::move (sm), &eng);
1971 4 : program_state s (ext_state);
1972 4 : region_model *model = s.m_region_model;
1973 4 : const svalue *size_in_bytes
1974 4 : = mgr.get_or_create_unknown_svalue (size_type_node);
1975 4 : const region *new_reg
1976 4 : = model->get_or_create_region_for_heap_alloc (size_in_bytes, nullptr);
1977 4 : const svalue *ptr_sval = mgr.get_ptr_svalue (ptr_type_node, new_reg);
1978 4 : model->set_value (model->get_lvalue (p, nullptr),
1979 : ptr_sval, nullptr);
1980 4 : sm_state_map *smap = s.m_checker_states[0];
1981 :
1982 4 : smap->impl_set_state (ptr_sval, UNCHECKED_STATE, nullptr, ext_state);
1983 4 : ASSERT_EQ (smap->get_state (ptr_sval, ext_state), UNCHECKED_STATE);
1984 4 : }
1985 :
1986 : /* Check that program_state works for string literals. */
1987 :
1988 : static void
1989 4 : test_program_state_2 ()
1990 : {
1991 : /* Create a program_state for a global ptr "p" that points to
1992 : a string constant. */
1993 4 : tree p = build_global_decl ("p", ptr_type_node);
1994 :
1995 4 : tree string_cst_ptr = build_string_literal (4, "foo");
1996 :
1997 4 : std::vector<std::unique_ptr<state_machine>> checkers;
1998 4 : symbolic::node_manager node_mgr;
1999 4 : engine eng (node_mgr);
2000 4 : extrinsic_state ext_state (std::move (checkers), &eng);
2001 :
2002 4 : program_state s (ext_state);
2003 4 : region_model *model = s.m_region_model;
2004 4 : const region *p_reg = model->get_lvalue (p, nullptr);
2005 4 : const svalue *str_sval = model->get_rvalue (string_cst_ptr, nullptr);
2006 4 : model->set_value (p_reg, str_sval, nullptr);
2007 4 : }
2008 :
2009 : /* Verify that program_states with identical sm-state can be merged,
2010 : and that the merged program_state preserves the sm-state. */
2011 :
2012 : static void
2013 4 : test_program_state_merging ()
2014 : {
2015 : /* Create a program_state for a global ptr "p" that has
2016 : malloc sm-state, pointing to a region on the heap. */
2017 4 : tree p = build_global_decl ("p", ptr_type_node);
2018 :
2019 4 : symbolic::node_manager node_mgr;
2020 4 : auto &mgr = node_mgr.get_region_model_manager ();
2021 4 : engine eng (node_mgr);
2022 4 : program_point point (program_point::origin (mgr));
2023 4 : extrinsic_state ext_state (make_malloc_state_machine (nullptr),
2024 4 : &eng);
2025 :
2026 4 : program_state s0 (ext_state);
2027 4 : uncertainty_t uncertainty;
2028 4 : impl_region_model_context ctxt (&s0, ext_state, &uncertainty);
2029 :
2030 4 : region_model *model0 = s0.m_region_model;
2031 4 : const svalue *size_in_bytes
2032 4 : = mgr.get_or_create_unknown_svalue (size_type_node);
2033 4 : const region *new_reg
2034 4 : = model0->get_or_create_region_for_heap_alloc (size_in_bytes, nullptr);
2035 4 : const svalue *ptr_sval = mgr.get_ptr_svalue (ptr_type_node, new_reg);
2036 4 : model0->set_value (model0->get_lvalue (p, &ctxt),
2037 : ptr_sval, &ctxt);
2038 4 : sm_state_map *smap = s0.m_checker_states[0];
2039 4 : const state_machine::state test_state ("test state", 0);
2040 4 : const state_machine::state_t TEST_STATE = &test_state;
2041 4 : smap->impl_set_state (ptr_sval, TEST_STATE, nullptr, ext_state);
2042 4 : ASSERT_EQ (smap->get_state (ptr_sval, ext_state), TEST_STATE);
2043 :
2044 4 : model0->canonicalize ();
2045 :
2046 : /* Verify that canonicalization preserves sm-state. */
2047 4 : ASSERT_EQ (smap->get_state (model0->get_rvalue (p, nullptr), ext_state),
2048 : TEST_STATE);
2049 :
2050 : /* Make a copy of the program_state. */
2051 4 : program_state s1 (s0);
2052 4 : ASSERT_EQ (s0, s1);
2053 :
2054 : /* We have two identical states with "p" pointing to a heap region
2055 : with the given sm-state.
2056 : They ought to be mergeable, preserving the sm-state. */
2057 4 : program_state merged (ext_state);
2058 4 : ASSERT_TRUE (s0.can_merge_with_p (s1, ext_state, point, &merged));
2059 4 : merged.validate (ext_state);
2060 :
2061 : /* Verify that the merged state has the sm-state for "p". */
2062 4 : region_model *merged_model = merged.m_region_model;
2063 4 : sm_state_map *merged_smap = merged.m_checker_states[0];
2064 4 : ASSERT_EQ (merged_smap->get_state (merged_model->get_rvalue (p, nullptr),
2065 : ext_state),
2066 : TEST_STATE);
2067 :
2068 : /* Try canonicalizing. */
2069 4 : merged.m_region_model->canonicalize ();
2070 4 : merged.validate (ext_state);
2071 :
2072 : /* Verify that the merged state still has the sm-state for "p". */
2073 4 : ASSERT_EQ (merged_smap->get_state (merged_model->get_rvalue (p, nullptr),
2074 : ext_state),
2075 : TEST_STATE);
2076 :
2077 : /* After canonicalization, we ought to have equality with the inputs. */
2078 4 : ASSERT_EQ (s0, merged);
2079 8 : }
2080 :
2081 : /* Verify that program_states with different global-state in an sm-state
2082 : can't be merged. */
2083 :
2084 : static void
2085 4 : test_program_state_merging_2 ()
2086 : {
2087 4 : symbolic::node_manager node_mgr;
2088 4 : auto &mgr = node_mgr.get_region_model_manager ();
2089 4 : engine eng (node_mgr);
2090 4 : program_point point (program_point::origin (mgr));
2091 4 : extrinsic_state ext_state (make_signal_state_machine (nullptr), &eng);
2092 :
2093 4 : const state_machine::state test_state_0 ("test state 0", 0);
2094 4 : const state_machine::state test_state_1 ("test state 1", 1);
2095 4 : const state_machine::state_t TEST_STATE_0 = &test_state_0;
2096 4 : const state_machine::state_t TEST_STATE_1 = &test_state_1;
2097 :
2098 4 : program_state s0 (ext_state);
2099 4 : {
2100 4 : sm_state_map *smap0 = s0.m_checker_states[0];
2101 4 : smap0->set_global_state (TEST_STATE_0);
2102 4 : ASSERT_EQ (smap0->get_global_state (), TEST_STATE_0);
2103 : }
2104 :
2105 4 : program_state s1 (ext_state);
2106 4 : {
2107 4 : sm_state_map *smap1 = s1.m_checker_states[0];
2108 4 : smap1->set_global_state (TEST_STATE_1);
2109 4 : ASSERT_EQ (smap1->get_global_state (), TEST_STATE_1);
2110 : }
2111 :
2112 4 : ASSERT_NE (s0, s1);
2113 :
2114 : /* They ought to not be mergeable. */
2115 4 : program_state merged (ext_state);
2116 4 : ASSERT_FALSE (s0.can_merge_with_p (s1, ext_state, point, &merged));
2117 4 : }
2118 :
2119 : /* Run all of the selftests within this file. */
2120 :
2121 : void
2122 4 : analyzer_program_state_cc_tests ()
2123 : {
2124 4 : test_sm_state_map ();
2125 4 : test_program_state_1 ();
2126 4 : test_program_state_2 ();
2127 4 : test_program_state_merging ();
2128 4 : test_program_state_merging_2 ();
2129 4 : }
2130 :
2131 : } // namespace selftest
2132 :
2133 : #endif /* CHECKING_P */
2134 :
2135 : } // namespace ana
2136 :
2137 : #endif /* #if ENABLE_ANALYZER */
|