Line data Source code
1 : /* Classes for modeling the state of memory.
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 : #ifndef GCC_ANALYZER_REGION_MODEL_H
22 : #define GCC_ANALYZER_REGION_MODEL_H
23 :
24 : /* Implementation of the region-based ternary model described in:
25 : "A Memory Model for Static Analysis of C Programs"
26 : (Zhongxing Xu, Ted Kremenek, and Jian Zhang)
27 : http://lcs.ios.ac.cn/~xuzb/canalyze/memmodel.pdf */
28 :
29 : #include "bitmap.h"
30 : #include "stringpool.h"
31 : #include "attribs.h" // for rdwr_map
32 : #include "selftest.h"
33 : #include "analyzer/svalue.h"
34 : #include "analyzer/region.h"
35 : #include "analyzer/known-function-manager.h"
36 : #include "analyzer/region-model-manager.h"
37 : #include "analyzer/pending-diagnostic.h"
38 : #include "analyzer/diagnostic-manager.h"
39 : #include "text-art/widget.h"
40 : #include "text-art/dump.h"
41 :
42 : using namespace ana;
43 :
44 : namespace inchash
45 : {
46 : extern void add_path_var (path_var pv, hash &hstate);
47 : } // namespace inchash
48 :
49 : namespace ana {
50 :
51 : template <typename T>
52 781679 : class one_way_id_map
53 : {
54 : public:
55 : one_way_id_map (int num_ids);
56 : void put (T src, T dst);
57 : T get_dst_for_src (T src) const;
58 : void dump_to_pp (pretty_printer *pp) const;
59 : void dump () const;
60 : void update (T *) const;
61 :
62 : private:
63 : auto_vec<T> m_src_to_dst;
64 : };
65 :
66 : /* class one_way_id_map. */
67 :
68 : /* one_way_id_map's ctor, which populates the map with dummy null values. */
69 :
70 : template <typename T>
71 781679 : inline one_way_id_map<T>::one_way_id_map (int num_svalues)
72 781679 : : m_src_to_dst (num_svalues)
73 : {
74 3104377 : for (int i = 0; i < num_svalues; i++)
75 2322698 : m_src_to_dst.quick_push (T::null ());
76 781679 : }
77 :
78 : /* Record that SRC is to be mapped to DST. */
79 :
80 : template <typename T>
81 : inline void
82 2295493 : one_way_id_map<T>::put (T src, T dst)
83 : {
84 2295493 : m_src_to_dst[src.as_int ()] = dst;
85 : }
86 :
87 : /* Get the new value for SRC within the map. */
88 :
89 : template <typename T>
90 : inline T
91 3079525 : one_way_id_map<T>::get_dst_for_src (T src) const
92 : {
93 3079525 : if (src.null_p ())
94 0 : return src;
95 3079525 : return m_src_to_dst[src.as_int ()];
96 : }
97 :
98 : /* Dump this map to PP. */
99 :
100 : template <typename T>
101 : inline void
102 0 : one_way_id_map<T>::dump_to_pp (pretty_printer *pp) const
103 : {
104 0 : pp_string (pp, "src to dst: {");
105 : unsigned i;
106 : T *dst;
107 0 : FOR_EACH_VEC_ELT (m_src_to_dst, i, dst)
108 : {
109 0 : if (i > 0)
110 0 : pp_string (pp, ", ");
111 0 : T src (T::from_int (i));
112 0 : src.print (pp);
113 0 : pp_string (pp, " -> ");
114 0 : dst->print (pp);
115 : }
116 0 : pp_string (pp, "}");
117 0 : pp_newline (pp);
118 0 : }
119 :
120 : /* Dump this map to stderr. */
121 :
122 : template <typename T>
123 : DEBUG_FUNCTION inline void
124 0 : one_way_id_map<T>::dump () const
125 : {
126 0 : pretty_printer pp;
127 0 : pp.set_output_stream (stderr);
128 0 : dump_to_pp (&pp);
129 0 : pp_flush (&pp);
130 0 : }
131 :
132 : /* Update *ID from the old value to its new value in this map. */
133 :
134 : template <typename T>
135 : inline void
136 3079525 : one_way_id_map<T>::update (T *id) const
137 : {
138 1544705 : *id = get_dst_for_src (*id);
139 : }
140 :
141 : /* A mapping from region to svalue for use when tracking state. */
142 :
143 2915893 : class region_to_value_map
144 : {
145 : public:
146 : typedef hash_map<const region *, const svalue *> hash_map_t;
147 : typedef hash_map_t::iterator iterator;
148 :
149 195403 : region_to_value_map () : m_hash_map () {}
150 2720490 : region_to_value_map (const region_to_value_map &other)
151 2720490 : : m_hash_map (other.m_hash_map) {}
152 : region_to_value_map &operator= (const region_to_value_map &other);
153 :
154 : bool operator== (const region_to_value_map &other) const;
155 425546 : bool operator!= (const region_to_value_map &other) const
156 : {
157 425546 : return !(*this == other);
158 : }
159 :
160 534250 : iterator begin () const { return m_hash_map.begin (); }
161 534250 : iterator end () const { return m_hash_map.end (); }
162 :
163 238426 : const svalue * const *get (const region *reg) const
164 : {
165 238426 : return const_cast <hash_map_t &> (m_hash_map).get (reg);
166 : }
167 21561 : void put (const region *reg, const svalue *sval)
168 : {
169 21561 : m_hash_map.put (reg, sval);
170 : }
171 49678 : void remove (const region *reg)
172 : {
173 49678 : m_hash_map.remove (reg);
174 : }
175 :
176 720 : bool is_empty () const { return m_hash_map.is_empty (); }
177 :
178 : void dump_to_logger (logger &) const;
179 :
180 : std::unique_ptr<json::object> to_json () const;
181 :
182 : std::unique_ptr<text_art::tree_widget>
183 : make_dump_widget (symbolic::node_dump_state &nds) const;
184 :
185 : bool can_merge_with_p (const region_to_value_map &other,
186 : region_to_value_map *out) const;
187 :
188 : void purge_state_involving (const symbolic::node &node);
189 :
190 : private:
191 : hash_map_t m_hash_map;
192 : };
193 :
194 : /* Various operations delete information from a region_model.
195 :
196 : This struct tracks how many of each kind of entity were purged (e.g.
197 : for selftests, and for debugging). */
198 :
199 : struct purge_stats
200 : {
201 : purge_stats ()
202 : : m_num_svalues (0),
203 : m_num_regions (0),
204 : m_num_equiv_classes (0),
205 : m_num_constraints (0),
206 : m_num_bounded_ranges_constraints (0),
207 : m_num_client_items (0)
208 : {}
209 :
210 : int m_num_svalues;
211 : int m_num_regions;
212 : int m_num_equiv_classes;
213 : int m_num_constraints;
214 : int m_num_bounded_ranges_constraints;
215 : int m_num_client_items;
216 : };
217 :
218 : /* A base class for visiting regions and svalues, with do-nothing
219 : base implementations of the per-subclass vfuncs. */
220 :
221 11565 : class visitor
222 : {
223 : public:
224 0 : virtual void visit_pointer_svalue (const pointer_svalue *) {}
225 0 : virtual void visit_constant_svalue (const constant_svalue *) {}
226 3443 : virtual void visit_unknown_svalue (const unknown_svalue *) {}
227 0 : virtual void visit_poisoned_svalue (const poisoned_svalue *) {}
228 0 : virtual void visit_setjmp_svalue (const setjmp_svalue *) {}
229 0 : virtual void visit_initial_svalue (const initial_svalue *) {}
230 496 : virtual void visit_unaryop_svalue (const unaryop_svalue *) {}
231 869 : virtual void visit_binop_svalue (const binop_svalue *) {}
232 333 : virtual void visit_svalue_from_bit_vector (const svalue_from_bit_vector *) {}
233 0 : virtual void visit_unmergeable_svalue (const unmergeable_svalue *) {}
234 15 : virtual void visit_placeholder_svalue (const placeholder_svalue *) {}
235 24 : virtual void visit_widening_svalue (const widening_svalue *) {}
236 0 : virtual void visit_asm_output_svalue (const asm_output_svalue *) {}
237 0 : virtual void visit_const_fn_result_svalue (const const_fn_result_svalue *) {}
238 :
239 5097 : virtual void visit_region (const region *) {}
240 : };
241 :
242 : struct append_regions_cb_data;
243 :
244 : // TODO: should this be a new kind of symbolic::node ?
245 :
246 : /* Roughly equivalent to a struct __cxa_exception, except we store a std::vector
247 : rather than a linked list. */
248 :
249 : struct exception_node
250 : {
251 5883 : exception_node (const svalue *exception_sval,
252 : const svalue *typeinfo_sval,
253 : const svalue *destructor_sval)
254 5883 : : m_exception_sval (exception_sval),
255 5883 : m_typeinfo_sval (typeinfo_sval),
256 5883 : m_destructor_sval (destructor_sval)
257 : {
258 : }
259 :
260 : bool operator== (const exception_node &other) const;
261 :
262 : void dump_to_logger (logger &) const;
263 : void dump () const;
264 :
265 : std::unique_ptr<json::object> to_json () const;
266 :
267 : std::unique_ptr<text_art::tree_widget>
268 : make_dump_widget (symbolic::node_dump_state &nds) const;
269 :
270 : tree maybe_get_type () const;
271 :
272 : void add_to_reachable_regions (reachable_regions &) const;
273 :
274 : const svalue *m_exception_sval;
275 : const svalue *m_typeinfo_sval;
276 : const svalue *m_destructor_sval;
277 : };
278 :
279 : /* A region_model encapsulates a representation of the state of memory, with
280 : a tree of regions, along with their associated values.
281 : The representation is graph-like because values can be pointers to
282 : regions.
283 : It also stores:
284 : - a constraint_manager, capturing relationships between the values, and
285 : - dynamic extents, mapping dynamically-allocated regions to svalues (their
286 : capacities). */
287 :
288 : class region_model
289 : {
290 : public:
291 : typedef region_to_value_map dynamic_extents_t;
292 :
293 : region_model (symbolic::node_manager &node_mgr);
294 : region_model (const region_model &other);
295 : ~region_model ();
296 : region_model &operator= (const region_model &other);
297 :
298 : bool operator== (const region_model &other) const;
299 28 : bool operator!= (const region_model &other) const
300 : {
301 28 : return !(*this == other);
302 : }
303 :
304 : hashval_t hash () const;
305 :
306 : void print (pretty_printer *pp) const;
307 :
308 : void dump_to_logger (logger &) const;
309 : void dump_to_pp (pretty_printer *pp) const;
310 : void dump () const;
311 :
312 : std::unique_ptr<json::object> to_json () const;
313 :
314 : std::unique_ptr<text_art::tree_widget>
315 : make_dump_widget (symbolic::node_dump_state &nds) const;
316 :
317 : void validate () const;
318 :
319 : void canonicalize ();
320 : bool canonicalized_p () const;
321 :
322 : void
323 : on_stmt_pre (const gimple *stmt,
324 : bool *out_unknown_side_effects,
325 : region_model_context *ctxt);
326 :
327 : void on_assignment (const gassign *stmt, region_model_context *ctxt);
328 : const svalue *get_gassign_result (const gassign *assign,
329 : region_model_context *ctxt);
330 : void on_asm_stmt (const gasm *asm_stmt, region_model_context *ctxt);
331 : bool on_call_pre (const gcall &stmt, region_model_context *ctxt);
332 : void on_call_post (const gcall &stmt,
333 : bool unknown_side_effects,
334 : region_model_context *ctxt);
335 :
336 : void purge_state_involving (const symbolic::node &node,
337 : region_model_context *ctxt);
338 :
339 : void impl_deallocation_call (const call_details &cd);
340 :
341 : const svalue *maybe_get_copy_bounds (const region *src_reg,
342 : const svalue *num_bytes_sval);
343 : void update_for_int_cst_return (const call_details &cd,
344 : int retval,
345 : bool unmergeable);
346 : void update_for_zero_return (const call_details &cd,
347 : bool unmergeable);
348 : void update_for_null_return (const call_details &cd,
349 : bool unmergeable);
350 : void update_for_nonzero_return (const call_details &cd);
351 :
352 : void handle_unrecognized_call (const gcall &call,
353 : region_model_context *ctxt);
354 : void get_reachable_svalues (value_set *out,
355 : const svalue *extra_sval,
356 : const uncertainty_t *uncertainty);
357 :
358 : void on_return (const greturn *stmt, region_model_context *ctxt);
359 : void on_setjmp (const gcall &stmt,
360 : const exploded_node &enode,
361 : const superedge &sedge,
362 : region_model_context *ctxt);
363 : void on_longjmp (const gcall &longjmp_call, const gcall &setjmp_call,
364 : int setjmp_stack_depth, region_model_context *ctxt);
365 :
366 : void update_for_gcall (const gcall &call_stmt,
367 : region_model_context *ctxt,
368 : function *callee = nullptr);
369 :
370 : void update_for_return_gcall (const gcall &call_stmt,
371 : region_model_context *ctxt);
372 :
373 : const region *push_frame (const function &fun,
374 : const gcall *call_stmt,
375 : const vec<const svalue *> *arg_sids,
376 : region_model_context *ctxt);
377 11390665 : const frame_region *get_current_frame () const { return m_current_frame; }
378 : const function *get_current_function () const;
379 : void pop_frame (tree result_lvalue,
380 : const svalue **out_result,
381 : region_model_context *ctxt,
382 : const gcall *call_stmt,
383 : bool eval_return_svalue = true);
384 : int get_stack_depth () const;
385 : const frame_region *get_frame_at_index (int index) const;
386 :
387 : const region *get_lvalue (path_var pv, region_model_context *ctxt) const;
388 : const region *get_lvalue (tree expr, region_model_context *ctxt) const;
389 : const svalue *get_rvalue (path_var pv, region_model_context *ctxt) const;
390 : const svalue *get_rvalue (tree expr, region_model_context *ctxt) const;
391 :
392 : const region *deref_rvalue (const svalue *ptr_sval, tree ptr_tree,
393 : region_model_context *ctxt,
394 : bool add_nonnull_constraint = true) const;
395 :
396 : const svalue *get_rvalue_for_bits (tree type,
397 : const region *reg,
398 : const bit_range &bits,
399 : region_model_context *ctxt) const;
400 :
401 : void set_value (const region *lhs_reg, const svalue *rhs_sval,
402 : region_model_context *ctxt);
403 : void set_value (tree lhs, tree rhs, region_model_context *ctxt);
404 : void clobber_region (const region *reg);
405 : void purge_region (const region *reg);
406 : void zero_fill_region (const region *reg,
407 : region_model_context *ctxt);
408 :
409 : void
410 : write_bytes (symbolic::pointer dest_sym_ptr,
411 : const symbolic::bit_vector &bytes,
412 : region_model_context *ctxt);
413 :
414 : const symbolic::bit_vector &
415 : read_bytes (symbolic::pointer src_sym_ptr,
416 : tree src_ptr_expr,
417 : const symbolic_byte_size &num_bytes,
418 : region_model_context *ctxt) const;
419 :
420 : void
421 : copy_bytes (symbolic::pointer dest_sym_ptr,
422 : symbolic::pointer src_sym_ptr,
423 : tree src_ptr_expr,
424 : const symbolic_byte_size &num_bytes,
425 : region_model_context *ctxt);
426 :
427 : void
428 : mark_region_as_unknown (const region *reg,
429 : uncertainty_t *uncertainty);
430 : void
431 : mark_region_as_conjured (const region &base_reg,
432 : const gimple &stmt,
433 : region_model_context *ctxt);
434 :
435 : tristate eval_condition (const svalue *lhs,
436 : enum tree_code op,
437 : const svalue *rhs) const;
438 : tristate compare_initial_and_pointer (const initial_svalue *init,
439 : const symbolic::pointer &ptr) const;
440 : tristate symbolic_greater_than (const binop_svalue *a,
441 : const svalue *b) const;
442 : tristate structural_equality (const svalue *a, const svalue *b) const;
443 : tristate eval_condition (tree lhs,
444 : enum tree_code op,
445 : tree rhs,
446 : region_model_context *ctxt) const;
447 : bool add_constraint (tree lhs, enum tree_code op, tree rhs,
448 : region_model_context *ctxt);
449 : bool add_constraint (tree lhs, enum tree_code op, tree rhs,
450 : region_model_context *ctxt,
451 : std::unique_ptr<rejected_constraint> *out);
452 :
453 : const region *
454 : get_or_create_region_for_heap_alloc (const svalue *size_in_bytes,
455 : region_model_context *ctxt,
456 : bool update_state_machine = false,
457 : const call_details *cd = nullptr);
458 :
459 : const region *create_region_for_alloca (const svalue *size_in_bytes,
460 : region_model_context *ctxt);
461 : void get_referenced_base_regions (auto_bitmap &out_ids) const;
462 :
463 : tree get_representative_tree (const svalue *sval,
464 : logger *logger = nullptr) const;
465 : tree get_representative_tree (const region *reg,
466 : logger *logger = nullptr) const;
467 : path_var
468 : get_representative_path_var (const svalue *sval,
469 : value_set *visited,
470 : logger *logger) const;
471 : path_var
472 : get_representative_path_var (const region *reg,
473 : value_set *visited,
474 : logger *logger) const;
475 :
476 : const region *
477 : maybe_get_region_for_mem_range (const symbolic::memory_range &mem_range,
478 : tree type,
479 : logger *logger = nullptr) const;
480 :
481 : /* For selftests. */
482 474710 : constraint_manager *get_constraints ()
483 : {
484 474710 : return m_constraints;
485 : }
486 :
487 913131 : store *get_store () { return &m_store; }
488 229620 : const store *get_store () const { return &m_store; }
489 :
490 : const dynamic_extents_t &
491 45893 : get_dynamic_extents () const
492 : {
493 45893 : return m_dynamic_extents;
494 : }
495 : const svalue *get_dynamic_extents (const region *reg) const;
496 : void set_dynamic_extents (const region *reg,
497 : const svalue *size_in_bytes,
498 : region_model_context *ctxt);
499 : void unset_dynamic_extents (const region *reg);
500 :
501 32 : symbolic::node_manager &get_node_manager () const { return m_node_mgr; }
502 700680 : region_model_manager *get_manager () const { return m_mgr; }
503 : bounded_ranges_manager *get_range_manager () const
504 : {
505 : return get_manager ()->get_range_manager ();
506 : }
507 :
508 : void unbind_region_and_descendents (const region *reg,
509 : enum poison_kind pkind);
510 :
511 : bool can_merge_with_p (const region_model &other_model,
512 : const program_point &point,
513 : region_model *out_model,
514 : const extrinsic_state *ext_state = nullptr,
515 : const program_state *state_a = nullptr,
516 : const program_state *state_b = nullptr) const;
517 :
518 : tree get_fndecl_for_call (const gcall &call,
519 : region_model_context *ctxt);
520 : tree get_fndecl_for_virtual_call (const_tree fn_ptr,
521 : region_model_context *ctxt);
522 :
523 : tree get_vtable_from_obj (tree obj, tree obj_type, region_model_manager *mgr,
524 : region_model_context *ctxt,
525 : unsigned HOST_WIDE_INT *out = nullptr) const;
526 :
527 : void get_regions_for_current_frame (auto_vec<const decl_region *> *out) const;
528 : static void append_regions_cb (const region *base_reg,
529 : struct append_regions_cb_data *data);
530 :
531 : const svalue *get_store_value (const region *reg,
532 : region_model_context *ctxt) const;
533 :
534 : const symbolic::bit_vector &
535 : get_store_bits (const symbolic::memory_range &mem_range,
536 : region_model_context *ctxt) const;
537 :
538 : const symbolic::bit_contents &
539 : get_bit_contents (const region &base_reg) const;
540 :
541 : void
542 : set_bit_contents_raw (const region &base_reg,
543 : const symbolic::bit_contents &new_bc);
544 :
545 : const svalue *scan_for_null_terminator (const region *reg,
546 : tree expr,
547 : const symbolic::bit_vector **out_bv,
548 : region_model_context *ctxt) const;
549 : const svalue *scan_for_null_terminator_1 (const region *reg,
550 : tree expr,
551 : const symbolic::bit_vector **out_bv,
552 : region_model_context *ctxt) const;
553 :
554 : void
555 : write_to_memory_offset (const symbolic::memory_offset &mem_offset,
556 : const symbolic::bit_vector &bv,
557 : region_model_context *ctxt);
558 :
559 : bool region_exists_p (const region *reg) const;
560 :
561 : void loop_replay_fixup (const region_model *dst_state);
562 :
563 : const svalue *get_capacity (const region *reg) const;
564 :
565 : const symbolic::scalar<integer_with_unit<units::byte>> &
566 : get_capacity_as_scalar (const region *reg) const;
567 :
568 : bool replay_call_summary (call_summary_replay &r,
569 : const region_model &summary);
570 :
571 : void maybe_complain_about_infoleak (const region *dst_reg,
572 : const svalue *copied_sval,
573 : const region *src_reg,
574 : region_model_context *ctxt);
575 :
576 : void set_errno (const call_details &cd);
577 :
578 : /* Implemented in sm-fd.cc */
579 : void mark_as_valid_fd (const svalue *sval, region_model_context *ctxt);
580 :
581 : /* Implemented in sm-malloc.cc */
582 : void on_realloc_with_move (const call_details &cd,
583 : const svalue *old_ptr_sval,
584 : const svalue *new_ptr_sval);
585 :
586 : /* Implemented in sm-malloc.cc. */
587 : void
588 : transition_ptr_sval_non_null (region_model_context *ctxt,
589 : const svalue *new_ptr_sval);
590 :
591 : /* Implemented in sm-taint.cc. */
592 : void mark_as_tainted (const svalue *sval,
593 : region_model_context *ctxt);
594 :
595 : bool add_constraint (const svalue *lhs,
596 : enum tree_code op,
597 : const svalue *rhs,
598 : region_model_context *ctxt);
599 :
600 : const svalue *check_for_poison (const svalue *sval,
601 : tree expr,
602 : const region *src_region,
603 : region_model_context *ctxt) const;
604 :
605 : void
606 : check_bytes_for_poison (const symbolic::bit_vector &bv,
607 : symbolic::pointer sym_ptr,
608 : tree sym_ptr_expr,
609 : region_model_context *ctxt) const;
610 :
611 : void check_region_for_write (const region *dest_reg,
612 : const svalue *sval_hint,
613 : region_model_context *ctxt) const;
614 :
615 : const svalue *
616 : check_for_null_terminated_string_arg (const call_details &cd,
617 : unsigned idx) const;
618 : const svalue *
619 : check_for_null_terminated_string_arg (const call_details &cd,
620 : unsigned idx,
621 : bool include_terminator,
622 : const symbolic::bit_vector **out_bv) const;
623 :
624 : const builtin_known_function *
625 : get_builtin_kf (const gcall &call,
626 : region_model_context *ctxt = nullptr) const;
627 :
628 : bool called_from_main_p () const;
629 :
630 : baseline_state
631 : get_baseline_state () const;
632 :
633 5967 : void push_thrown_exception (const exception_node &node)
634 : {
635 5967 : m_thrown_exceptions_stack.push_back (node);
636 : }
637 649 : const exception_node *get_current_thrown_exception () const
638 : {
639 649 : if (m_thrown_exceptions_stack.empty ())
640 : return nullptr;
641 646 : return &m_thrown_exceptions_stack.back ();
642 : }
643 349 : exception_node pop_thrown_exception ()
644 : {
645 349 : gcc_assert (!m_thrown_exceptions_stack.empty ());
646 349 : const exception_node retval = m_thrown_exceptions_stack.back ();
647 349 : m_thrown_exceptions_stack.pop_back ();
648 349 : return retval;
649 : }
650 :
651 349 : void push_caught_exception (const exception_node &node)
652 : {
653 349 : m_caught_exceptions_stack.push_back (node);
654 : }
655 198 : const exception_node *get_current_caught_exception () const
656 : {
657 198 : if (m_caught_exceptions_stack.empty ())
658 : return nullptr;
659 150 : return &m_caught_exceptions_stack.back ();
660 : }
661 233 : exception_node pop_caught_exception ()
662 : {
663 233 : gcc_assert (!m_caught_exceptions_stack.empty ());
664 233 : const exception_node retval = m_caught_exceptions_stack.back ();
665 233 : m_caught_exceptions_stack.pop_back ();
666 233 : return retval;
667 : }
668 :
669 : bool
670 287978 : bits_live_p (const symbolic::bit_vector_from_ubc &bv_from_ubc) const
671 : {
672 287978 : return m_store.bits_live_p (bv_from_ubc, *this);
673 : }
674 :
675 : private:
676 : const region *get_lvalue_1 (path_var pv, region_model_context *ctxt) const;
677 : const svalue *get_rvalue_1 (path_var pv, region_model_context *ctxt) const;
678 :
679 : path_var
680 : get_representative_path_var_1 (const svalue *sval,
681 : value_set *visited,
682 : logger *logger) const;
683 : path_var
684 : get_representative_path_var_1 (const region *reg,
685 : value_set *visited,
686 : logger *logger) const;
687 :
688 : const known_function *get_known_function (tree fndecl,
689 : const call_details &cd) const;
690 : const known_function *get_known_function (enum internal_fn) const;
691 :
692 : const region *
693 : maybe_get_subregion_for_symbolic_bit_range (const region ®,
694 : tree type,
695 : symbolic_bit_range bit_range) const;
696 : const region *
697 : maybe_get_subregion_for_concrete_bit_range (const region ®,
698 : tree desired_type,
699 : concrete_bit_range bit_range) const;
700 : const region *
701 : maybe_get_subregion_for_symbolic_bit_range_in_array (const region &array_reg,
702 : tree desired_type,
703 : symbolic_bit_range bit_range) const;
704 : const region *
705 : maybe_get_subregion_for_symbolic_bit_range_in_record (const region &record_reg,
706 : tree desired_type,
707 : symbolic_bit_range bit_range) const;
708 :
709 : bool add_constraints_from_binop (const svalue *outer_lhs,
710 : enum tree_code outer_op,
711 : const svalue *outer_rhs,
712 : bool *out,
713 : region_model_context *ctxt);
714 :
715 : void poison_any_pointers_to_descendents (const region *reg,
716 : enum poison_kind pkind);
717 :
718 : void on_top_level_param (tree param,
719 : bool nonnull,
720 : region_model_context *ctxt);
721 :
722 : const svalue *get_initial_value_for_global (const region *reg) const;
723 :
724 : const region * get_region_for_poisoned_expr (tree expr) const;
725 :
726 : const svalue *
727 : complain_about_poison (const svalue *sval,
728 : tree expr,
729 : const region *src_region,
730 : region_model_context *ctxt,
731 : enum poison_kind pkind) const;
732 :
733 : void check_dynamic_size_for_taint (enum memory_space mem_space,
734 : const svalue *size_in_bytes,
735 : region_model_context *ctxt) const;
736 : void check_dynamic_size_for_floats (const svalue *size_in_bytes,
737 : region_model_context *ctxt) const;
738 :
739 : void check_memory_range_for_taint (const symbolic::memory_range &mem_range,
740 : enum access_direction dir,
741 : region_model_context *ctxt) const;
742 : void check_region_for_taint (const region *reg,
743 : enum access_direction,
744 : region_model_context *ctxt) const;
745 :
746 : void check_for_writable_region (const region* dest_reg,
747 : region_model_context *ctxt) const;
748 :
749 : bool
750 : check_memory_range_access (const symbolic::memory_range &mem_range,
751 : enum access_direction dir,
752 : const svalue *sval_hint,
753 : region_model_context *ctxt) const;
754 :
755 : bool check_region_access (const region *reg,
756 : enum access_direction dir,
757 : const svalue *sval_hint,
758 : region_model_context *ctxt) const;
759 :
760 : void check_region_size (const region *lhs_reg, const svalue *rhs_sval,
761 : region_model_context *ctxt) const;
762 :
763 : /* Implemented in bounds-checking.cc */
764 : bool
765 : check_memory_range_bounds (const symbolic::memory_range &mem_range,
766 : enum access_direction dir,
767 : const svalue *sval_hint,
768 : region_model_context *ctxt) const;
769 :
770 : bool check_symbolic_bounds (const symbolic::memory_range &attempted_range,
771 : const svalue *capacity,
772 : enum access_direction dir,
773 : const svalue *sval_hint,
774 : region_model_context *ctxt) const;
775 : bool check_region_bounds (const region *reg, enum access_direction dir,
776 : const svalue *sval_hint,
777 : region_model_context *ctxt) const;
778 :
779 : void check_call_args (const call_details &cd) const;
780 : void check_call_format_attr (const call_details &cd,
781 : tree format_attr) const;
782 : void check_function_attr_access (const gcall &call,
783 : tree callee_fndecl,
784 : region_model_context *ctxt,
785 : rdwr_map &rdwr_idx) const;
786 : void check_function_attr_null_terminated_string_arg (const gcall &call,
787 : tree callee_fndecl,
788 : region_model_context *ctxt,
789 : rdwr_map &rdwr_idx);
790 : void check_one_function_attr_null_terminated_string_arg (const gcall &call,
791 : tree callee_fndecl,
792 : region_model_context *ctxt,
793 : rdwr_map &rdwr_idx,
794 : tree attr);
795 : void check_function_attrs (const gcall &call,
796 : tree callee_fndecl,
797 : region_model_context *ctxt);
798 :
799 : void check_for_throw_inside_call (const gcall &call,
800 : tree fndecl,
801 : region_model_context *ctxt);
802 :
803 : const svalue *
804 : canonicalize_svalue_for_constraint (const svalue *sval) const;
805 :
806 : bool
807 : can_recurse_eval_condition_p (const unaryop_svalue *unary_op) const;
808 :
809 : /* Storing this here to avoid passing it around everywhere. */
810 : symbolic::node_manager &m_node_mgr;
811 :
812 : // TODO: eliminate this copy (kept here to minimize churn)
813 : region_model_manager *const m_mgr;
814 :
815 : store m_store;
816 :
817 : constraint_manager *m_constraints; // TODO: embed, rather than dynalloc?
818 :
819 : const frame_region *m_current_frame;
820 :
821 : std::vector<exception_node> m_thrown_exceptions_stack;
822 : std::vector<exception_node> m_caught_exceptions_stack;
823 :
824 : /* Map from base region to size in bytes, for tracking the sizes of
825 : dynamically-allocated regions.
826 : This is part of the region_model rather than the region to allow for
827 : memory regions to be resized (e.g. by realloc). */
828 : dynamic_extents_t m_dynamic_extents;
829 : };
830 :
831 : /* Some region_model activity could lead to warnings (e.g. attempts to use an
832 : uninitialized value). This abstract base class encapsulates an interface
833 : for the region model to use when emitting such warnings.
834 :
835 : Having this as an abstract base class allows us to support the various
836 : operations needed by program_state in the analyzer within region_model,
837 : whilst keeping them somewhat modularized. */
838 :
839 1274943 : class region_model_context
840 : {
841 : public:
842 : bool
843 : warn (std::unique_ptr<pending_diagnostic> d,
844 : std::unique_ptr<pending_location::fixer_for_epath> ploc_fixer = nullptr);
845 :
846 : /* Hook for determining where diagnostics are to currently be emitted. */
847 : virtual pending_location
848 : get_pending_location_for_diag () const = 0;
849 :
850 : /* Hook for clients to store pending diagnostics.
851 : Return true if the diagnostic was stored, or false if it was deleted. */
852 : virtual bool
853 : warn_at (std::unique_ptr<pending_diagnostic> d,
854 : pending_location &&ploc) = 0;
855 :
856 : /* Hook for clients to add a note to the last previously stored
857 : pending diagnostic. */
858 : virtual void add_note (std::unique_ptr<pending_note> pn) = 0;
859 :
860 : /* Hook for clients to add an event to the last previously stored
861 : pending diagnostic. */
862 : virtual void add_event (std::unique_ptr<checker_event> event) = 0;
863 :
864 : /* Hook for clients to be notified when an SVAL that was reachable
865 : in a previous state is no longer live, so that clients can emit warnings
866 : about leaks. */
867 : virtual void on_svalue_leak (const svalue *sval) = 0;
868 :
869 : /* Hook for clients to be notified when the set of explicitly live
870 : svalues changes, so that they can purge state relating to dead
871 : svalues and report leaks. */
872 : virtual void on_liveness_change (symbolic::liveness_context &liveness_ctxt) = 0;
873 :
874 : virtual logger *get_logger () = 0;
875 :
876 : /* Hook for clients to be notified when the condition
877 : "LHS OP RHS" is added to the region model.
878 : This exists so that state machines can detect tests on edges,
879 : and use them to trigger sm-state transitions (e.g. transitions due
880 : to ptrs becoming known to be NULL or non-NULL, rather than just
881 : "unchecked") */
882 : virtual void on_condition (const svalue *lhs,
883 : enum tree_code op,
884 : const svalue *rhs) = 0;
885 :
886 : /* Hook for clients to be notified when the condition that
887 : SVAL is within RANGES is added to the region model.
888 : Similar to on_condition, but for use when handling switch statements.
889 : RANGES is non-empty. */
890 : virtual void on_bounded_ranges (const svalue &sval,
891 : const bounded_ranges &ranges) = 0;
892 :
893 : /* Hook for clients to be notified when a frame is popped from the stack. */
894 : virtual void on_pop_frame (const frame_region *) = 0;
895 :
896 : /* Hooks for clients to be notified when an unknown change happens
897 : to VAL (in response to a call to an unknown function). */
898 : virtual void on_unknown_change (const symbolic::value_node &val,
899 : bool is_mutable) = 0;
900 :
901 : /* Hooks for clients to be notified when a phi node is handled,
902 : where RHS is the pertinent argument. */
903 : virtual void on_phi (const gphi *phi, tree rhs) = 0;
904 :
905 : /* Hooks for clients to be notified when the region model doesn't
906 : know how to handle the tree code of T at LOC. */
907 : virtual void on_unexpected_tree_code (tree t,
908 : const dump_location_t &loc) = 0;
909 :
910 : /* Hook for clients to be notified when a function_decl escapes. */
911 : virtual void on_escaped_function (tree fndecl) = 0;
912 :
913 : virtual uncertainty_t *get_uncertainty () = 0;
914 :
915 : /* Hook for clients to purge state involving NODE. */
916 : virtual void purge_state_involving (const symbolic::node &node) = 0;
917 :
918 : /* Hook for clients to split state with a non-standard path. */
919 : virtual void bifurcate (std::unique_ptr<custom_edge_info> info) = 0;
920 :
921 : /* Hook for clients to terminate the standard path. */
922 : virtual void terminate_path () = 0;
923 :
924 : virtual const extrinsic_state *get_ext_state () const = 0;
925 :
926 : /* Hook for clients to access the a specific state machine in
927 : any underlying program_state. */
928 : virtual bool
929 : get_state_map_by_name (const char *name,
930 : sm_state_map **out_smap,
931 : const state_machine **out_sm,
932 : unsigned *out_sm_idx,
933 : std::unique_ptr<sm_context> *out_sm_context) = 0;
934 :
935 : /* Precanned ways for clients to access specific state machines. */
936 647 : bool get_fd_map (sm_state_map **out_smap,
937 : const state_machine **out_sm,
938 : unsigned *out_sm_idx,
939 : std::unique_ptr<sm_context> *out_sm_context)
940 : {
941 647 : return get_state_map_by_name ("file-descriptor", out_smap, out_sm,
942 : out_sm_idx, out_sm_context);
943 : }
944 257 : bool get_malloc_map (sm_state_map **out_smap,
945 : const state_machine **out_sm,
946 : unsigned *out_sm_idx)
947 : {
948 257 : return get_state_map_by_name ("malloc", out_smap, out_sm, out_sm_idx,
949 : nullptr);
950 : }
951 669285 : bool get_taint_map (sm_state_map **out_smap,
952 : const state_machine **out_sm,
953 : unsigned *out_sm_idx)
954 : {
955 669285 : return get_state_map_by_name ("taint", out_smap, out_sm, out_sm_idx,
956 : nullptr);
957 : }
958 :
959 : bool possibly_tainted_p (const svalue *sval);
960 :
961 : /* Get the current statement, if any. */
962 : virtual const gimple *get_stmt () const = 0;
963 :
964 : virtual const exploded_graph *get_eg () const = 0;
965 :
966 : virtual const program_state *get_state () const = 0;
967 :
968 : /* Hooks for detecting infinite loops. */
969 : virtual void maybe_did_work () = 0;
970 : virtual bool checking_for_infinite_loop_p () const = 0;
971 : virtual void on_unusable_in_infinite_loop () = 0;
972 : };
973 :
974 : /* A "do nothing" subclass of region_model_context. */
975 :
976 24471 : class noop_region_model_context : public region_model_context
977 : {
978 : public:
979 : pending_location
980 749 : get_pending_location_for_diag () const override
981 : {
982 749 : return pending_location ();
983 : }
984 : bool
985 745 : warn_at (std::unique_ptr<pending_diagnostic>,
986 : pending_location &&) override
987 : {
988 745 : return false;
989 : }
990 : void add_note (std::unique_ptr<pending_note>) override;
991 : void add_event (std::unique_ptr<checker_event>) override;
992 0 : void on_svalue_leak (const svalue *) override {}
993 0 : void on_liveness_change (symbolic::liveness_context &) override {}
994 73513 : logger *get_logger () override { return nullptr; }
995 44 : void on_condition (const svalue *lhs ATTRIBUTE_UNUSED,
996 : enum tree_code op ATTRIBUTE_UNUSED,
997 : const svalue *rhs ATTRIBUTE_UNUSED) override
998 : {
999 44 : }
1000 63 : void on_bounded_ranges (const svalue &,
1001 : const bounded_ranges &) override
1002 : {
1003 63 : }
1004 297 : void on_pop_frame (const frame_region *) override {}
1005 1296 : void on_unknown_change (const symbolic::value_node &val ATTRIBUTE_UNUSED,
1006 : bool is_mutable ATTRIBUTE_UNUSED) override
1007 : {
1008 1296 : }
1009 0 : void on_phi (const gphi *phi ATTRIBUTE_UNUSED,
1010 : tree rhs ATTRIBUTE_UNUSED) override
1011 : {
1012 0 : }
1013 0 : void on_unexpected_tree_code (tree, const dump_location_t &) override {}
1014 :
1015 0 : void on_escaped_function (tree) override {}
1016 :
1017 12276 : uncertainty_t *get_uncertainty () override { return nullptr; }
1018 :
1019 1861 : void purge_state_involving (const symbolic::node &) override {}
1020 :
1021 : void bifurcate (std::unique_ptr<custom_edge_info> info) override;
1022 : void terminate_path () override;
1023 :
1024 14420 : const extrinsic_state *get_ext_state () const override { return nullptr; }
1025 :
1026 36863 : bool get_state_map_by_name (const char *,
1027 : sm_state_map **,
1028 : const state_machine **,
1029 : unsigned *,
1030 : std::unique_ptr<sm_context> *) override
1031 : {
1032 36863 : return false;
1033 : }
1034 :
1035 12356 : const gimple *get_stmt () const override { return nullptr; }
1036 0 : const exploded_graph *get_eg () const override { return nullptr; }
1037 0 : const program_state *get_state () const override { return nullptr; }
1038 :
1039 746 : void maybe_did_work () override {}
1040 44 : bool checking_for_infinite_loop_p () const override { return false; }
1041 0 : void on_unusable_in_infinite_loop () override {}
1042 : };
1043 :
1044 : /* A subclass of region_model_context for determining if operations fail
1045 : e.g. "can we generate a region for the lvalue of EXPR?". */
1046 :
1047 : class tentative_region_model_context : public noop_region_model_context
1048 : {
1049 : public:
1050 : tentative_region_model_context () : m_num_unexpected_codes (0) {}
1051 :
1052 0 : void on_unexpected_tree_code (tree, const dump_location_t &)
1053 : final override
1054 : {
1055 0 : m_num_unexpected_codes++;
1056 0 : }
1057 :
1058 : bool had_errors_p () const { return m_num_unexpected_codes > 0; }
1059 :
1060 : private:
1061 : int m_num_unexpected_codes;
1062 : };
1063 :
1064 : /* Subclass of region_model_context that wraps another context, allowing
1065 : for extra code to be added to the various hooks. */
1066 :
1067 : class region_model_context_decorator : public region_model_context
1068 : {
1069 : public:
1070 : pending_location
1071 233 : get_pending_location_for_diag () const override
1072 : {
1073 233 : if (m_inner)
1074 227 : return m_inner->get_pending_location_for_diag ();
1075 : else
1076 6 : return pending_location ();
1077 : }
1078 :
1079 : bool
1080 9 : warn_at (std::unique_ptr<pending_diagnostic> d,
1081 : pending_location &&ploc) override
1082 : {
1083 9 : if (m_inner)
1084 9 : return m_inner->warn_at (std::move (d), std::move (ploc));
1085 : else
1086 : return false;
1087 : }
1088 :
1089 222 : void add_note (std::unique_ptr<pending_note> pn) override
1090 : {
1091 222 : if (m_inner)
1092 222 : m_inner->add_note (std::move (pn));
1093 222 : }
1094 : void add_event (std::unique_ptr<checker_event> event) override;
1095 :
1096 0 : void on_svalue_leak (const svalue *sval) override
1097 : {
1098 0 : if (m_inner)
1099 0 : m_inner->on_svalue_leak (sval);
1100 0 : }
1101 :
1102 0 : void on_liveness_change (symbolic::liveness_context &liveness_ctxt) override
1103 : {
1104 0 : if (m_inner)
1105 0 : m_inner->on_liveness_change (liveness_ctxt);
1106 0 : }
1107 :
1108 34877 : logger *get_logger () override
1109 : {
1110 34877 : if (m_inner)
1111 25369 : return m_inner->get_logger ();
1112 : else
1113 : return nullptr;
1114 : }
1115 :
1116 0 : void on_condition (const svalue *lhs,
1117 : enum tree_code op,
1118 : const svalue *rhs) override
1119 : {
1120 0 : if (m_inner)
1121 0 : m_inner->on_condition (lhs, op, rhs);
1122 0 : }
1123 :
1124 0 : void on_bounded_ranges (const svalue &sval,
1125 : const bounded_ranges &ranges) override
1126 : {
1127 0 : if (m_inner)
1128 0 : m_inner->on_bounded_ranges (sval, ranges);
1129 0 : }
1130 :
1131 0 : void on_pop_frame (const frame_region *frame_reg) override
1132 : {
1133 0 : if (m_inner)
1134 0 : m_inner->on_pop_frame (frame_reg);
1135 0 : }
1136 :
1137 0 : void on_unknown_change (const symbolic::value_node &val,
1138 : bool is_mutable) override
1139 : {
1140 0 : if (m_inner)
1141 0 : m_inner->on_unknown_change (val, is_mutable);
1142 0 : }
1143 :
1144 0 : void on_phi (const gphi *phi, tree rhs) override
1145 : {
1146 0 : if (m_inner)
1147 0 : m_inner->on_phi (phi, rhs);
1148 0 : }
1149 :
1150 0 : void on_unexpected_tree_code (tree t,
1151 : const dump_location_t &loc) override
1152 : {
1153 0 : if (m_inner)
1154 0 : m_inner->on_unexpected_tree_code (t, loc);
1155 0 : }
1156 :
1157 0 : void on_escaped_function (tree fndecl) override
1158 : {
1159 0 : if (m_inner)
1160 0 : m_inner->on_escaped_function (fndecl);
1161 0 : }
1162 :
1163 5773 : uncertainty_t *get_uncertainty () override
1164 : {
1165 5773 : if (m_inner)
1166 4487 : return m_inner->get_uncertainty ();
1167 : else
1168 : return nullptr;
1169 : }
1170 :
1171 0 : void purge_state_involving (const symbolic::node &node) override
1172 : {
1173 0 : if (m_inner)
1174 0 : m_inner->purge_state_involving (node);
1175 0 : }
1176 :
1177 0 : void bifurcate (std::unique_ptr<custom_edge_info> info) override
1178 : {
1179 0 : if (m_inner)
1180 0 : m_inner->bifurcate (std::move (info));
1181 0 : }
1182 :
1183 0 : void terminate_path () override
1184 : {
1185 0 : if (m_inner)
1186 0 : m_inner->terminate_path ();
1187 0 : }
1188 :
1189 7810 : const extrinsic_state *get_ext_state () const override
1190 : {
1191 7810 : if (m_inner)
1192 7810 : return m_inner->get_ext_state ();
1193 : else
1194 : return nullptr;
1195 : }
1196 :
1197 10372 : bool get_state_map_by_name (const char *name,
1198 : sm_state_map **out_smap,
1199 : const state_machine **out_sm,
1200 : unsigned *out_sm_idx,
1201 : std::unique_ptr<sm_context> *out_sm_context)
1202 : override
1203 : {
1204 10372 : if (m_inner)
1205 8044 : return m_inner->get_state_map_by_name (name, out_smap, out_sm, out_sm_idx,
1206 8044 : out_sm_context);
1207 : else
1208 : return false;
1209 : }
1210 :
1211 101 : const gimple *get_stmt () const override
1212 : {
1213 101 : if (m_inner)
1214 101 : return m_inner->get_stmt ();
1215 : else
1216 : return nullptr;
1217 : }
1218 :
1219 0 : const exploded_graph *get_eg () const override
1220 : {
1221 0 : if (m_inner)
1222 0 : return m_inner->get_eg ();
1223 : else
1224 : return nullptr;
1225 : }
1226 :
1227 0 : const program_state *get_state () const override
1228 : {
1229 0 : if (m_inner)
1230 0 : return m_inner->get_state ();
1231 : else
1232 : return nullptr;
1233 : }
1234 :
1235 0 : void maybe_did_work () override
1236 : {
1237 0 : if (m_inner)
1238 0 : m_inner->maybe_did_work ();
1239 0 : }
1240 :
1241 0 : bool checking_for_infinite_loop_p () const override
1242 : {
1243 0 : if (m_inner)
1244 0 : return m_inner->checking_for_infinite_loop_p ();
1245 : return false;
1246 : }
1247 0 : void on_unusable_in_infinite_loop () override
1248 : {
1249 0 : if (m_inner)
1250 0 : m_inner->on_unusable_in_infinite_loop ();
1251 0 : }
1252 :
1253 : protected:
1254 12885 : region_model_context_decorator (region_model_context *inner)
1255 5773 : : m_inner (inner)
1256 : {
1257 : }
1258 :
1259 : region_model_context *m_inner;
1260 : };
1261 :
1262 : /* Subclass of region_model_context_decorator with a hook for adding
1263 : notes/events when saving diagnostics. */
1264 :
1265 : class annotating_context : public region_model_context_decorator
1266 : {
1267 : public:
1268 : bool
1269 224 : warn_at (std::unique_ptr<pending_diagnostic> d,
1270 : pending_location &&ploc) override
1271 : {
1272 224 : if (m_inner)
1273 218 : if (m_inner->warn_at (std::move (d), std::move (ploc)))
1274 : {
1275 214 : add_annotations ();
1276 214 : return true;
1277 : }
1278 : return false;
1279 : }
1280 :
1281 : /* Hook to add new event(s)/note(s) */
1282 : virtual void add_annotations () = 0;
1283 :
1284 : protected:
1285 7112 : annotating_context (region_model_context *inner)
1286 7112 : : region_model_context_decorator (inner)
1287 : {
1288 : }
1289 : };
1290 :
1291 : /* A bundle of data for use when attempting to merge two region_model
1292 : instances to make a third. */
1293 :
1294 63282 : struct model_merger
1295 : {
1296 63282 : model_merger (const region_model *model_a,
1297 : const region_model *model_b,
1298 : const program_point &point,
1299 : region_model *merged_model,
1300 : const extrinsic_state *ext_state,
1301 : const program_state *state_a,
1302 : const program_state *state_b)
1303 63282 : : m_model_a (model_a), m_model_b (model_b),
1304 63282 : m_point (point),
1305 63282 : m_merged_model (merged_model),
1306 63282 : m_ext_state (ext_state),
1307 63282 : m_state_a (state_a), m_state_b (state_b)
1308 : {
1309 : }
1310 :
1311 : void dump_to_logger (logger &) const;
1312 : void dump () const;
1313 :
1314 : region_model_manager *get_manager () const
1315 : {
1316 : return m_model_a->get_manager ();
1317 : }
1318 :
1319 : bool mergeable_svalue_p (const svalue *) const;
1320 : bool mergeable_bit_vector_p (const symbolic::bit_vector &) const;
1321 :
1322 2629 : const supernode *get_supernode () const
1323 : {
1324 2629 : return m_point.get_supernode ();
1325 : }
1326 :
1327 : void on_widening_reuse (const widening_svalue *widening_sval);
1328 :
1329 : const region_model *m_model_a;
1330 : const region_model *m_model_b;
1331 : const program_point &m_point;
1332 : region_model *m_merged_model;
1333 :
1334 : const extrinsic_state *m_ext_state;
1335 : const program_state *m_state_a;
1336 : const program_state *m_state_b;
1337 :
1338 : hash_set<const svalue *> m_svals_changing_meaning;
1339 : };
1340 :
1341 : /* A record that can (optionally) be written out when
1342 : region_model::add_constraint fails. */
1343 :
1344 : class rejected_constraint
1345 : {
1346 : public:
1347 : virtual ~rejected_constraint () {}
1348 : virtual void dump_to_pp (pretty_printer *pp) const = 0;
1349 : virtual std::unique_ptr<json::object> to_json () const = 0;
1350 :
1351 0 : const region_model &get_model () const { return m_model; }
1352 :
1353 : protected:
1354 1624 : rejected_constraint (const region_model &model)
1355 1611 : : m_model (model)
1356 : {}
1357 :
1358 : std::unique_ptr<json::object>
1359 : make_base_json (const char *kind) const;
1360 :
1361 : region_model m_model;
1362 : };
1363 :
1364 : class rejected_op_constraint : public rejected_constraint
1365 : {
1366 : public:
1367 1612 : rejected_op_constraint (const region_model &model,
1368 : const svalue *lhs, enum tree_code op, const svalue *rhs)
1369 : : rejected_constraint (model),
1370 1612 : m_lhs (lhs), m_op (op), m_rhs (rhs)
1371 : {}
1372 :
1373 : void dump_to_pp (pretty_printer *pp) const final override;
1374 : std::unique_ptr<json::object> to_json () const final override;
1375 :
1376 : const svalue *m_lhs;
1377 : enum tree_code m_op;
1378 : const svalue *m_rhs;
1379 : };
1380 :
1381 : class rejected_default_case : public rejected_constraint
1382 : {
1383 : public:
1384 0 : rejected_default_case (const region_model &model)
1385 0 : : rejected_constraint (model)
1386 : {}
1387 :
1388 : void dump_to_pp (pretty_printer *pp) const final override;
1389 : std::unique_ptr<json::object> to_json () const final override;
1390 : };
1391 :
1392 : class rejected_ranges_constraint : public rejected_constraint
1393 : {
1394 : public:
1395 12 : rejected_ranges_constraint (const region_model &model,
1396 : tree expr, const bounded_ranges *ranges)
1397 : : rejected_constraint (model),
1398 12 : m_expr (expr), m_ranges (ranges)
1399 : {}
1400 :
1401 : void dump_to_pp (pretty_printer *pp) const final override;
1402 : std::unique_ptr<json::object> to_json () const final override;
1403 :
1404 : private:
1405 : tree m_expr;
1406 : const bounded_ranges *m_ranges;
1407 : };
1408 :
1409 : /* A bundle of state. */
1410 :
1411 : class engine
1412 : {
1413 : public:
1414 : engine (symbolic::node_manager &node_mgr,
1415 : const supergraph *sg = nullptr);
1416 289258 : const supergraph *get_supergraph () { return m_sg; }
1417 :
1418 : symbolic::node_manager &
1419 184905 : get_node_manager ()
1420 : {
1421 138973 : return m_node_mgr;
1422 : }
1423 :
1424 : region_model_manager *
1425 7490553 : get_model_manager ()
1426 : {
1427 7490515 : return &m_node_mgr.get_region_model_manager ();
1428 : }
1429 :
1430 3611 : known_function_manager *get_known_function_manager ()
1431 : {
1432 3611 : return get_model_manager ()->get_known_function_manager ();
1433 : }
1434 :
1435 : void log_stats (logger *logger) const;
1436 :
1437 : private:
1438 : symbolic::node_manager &m_node_mgr;
1439 : const supergraph *m_sg;
1440 : };
1441 :
1442 : /* Factory functions for various diagnostics. */
1443 :
1444 : extern std::unique_ptr<pending_diagnostic>
1445 : make_poisoned_value_diagnostic (tree expr, enum poison_kind pkind,
1446 : const region *src_region,
1447 : tree check_expr);
1448 :
1449 : extern std::unique_ptr<pending_diagnostic>
1450 : make_shift_count_negative_diagnostic (const gassign *assign,
1451 : tree count_cst,
1452 : const region *src_region);
1453 :
1454 : extern std::unique_ptr<pending_diagnostic>
1455 : make_shift_count_overflow_diagnostic (const gassign *assign,
1456 : int operand_precision,
1457 : tree count_cst,
1458 : const region *src_region);
1459 :
1460 : extern std::unique_ptr<pending_diagnostic>
1461 : make_write_to_const_diagnostic (const region *dest_reg, tree decl);
1462 :
1463 : extern std::unique_ptr<pending_diagnostic>
1464 : make_write_to_string_literal_diagnostic (const region *reg);
1465 :
1466 5468 : struct poison_finder : public symbolic::node_visitor
1467 : {
1468 5546 : poison_finder ()
1469 5546 : : m_found_poison (false)
1470 : {
1471 : }
1472 :
1473 : bool
1474 : visit_svalue (const svalue &sval) final override;
1475 :
1476 : bool
1477 : visit_bit_vector (const symbolic::bit_vector &bv) final override;
1478 :
1479 : bool m_found_poison;
1480 : enum poison_kind m_pkind;
1481 : };
1482 :
1483 : } // namespace ana
1484 :
1485 : extern void debug (const region_model &rmodel);
1486 :
1487 : namespace ana {
1488 :
1489 : #if CHECKING_P
1490 :
1491 : namespace selftest {
1492 :
1493 : using namespace ::selftest;
1494 :
1495 : /* An implementation of region_model_context for use in selftests, which
1496 : stores any pending_diagnostic instances passed to it. */
1497 :
1498 224 : class test_region_model_context : public noop_region_model_context
1499 : {
1500 : public:
1501 : bool
1502 4 : warn_at (std::unique_ptr<pending_diagnostic> d,
1503 : pending_location &&) final override
1504 : {
1505 4 : m_diagnostics.safe_push (d.release ());
1506 4 : return true;
1507 : }
1508 :
1509 4 : unsigned get_num_diagnostics () const { return m_diagnostics.length (); }
1510 :
1511 0 : void on_unexpected_tree_code (tree t, const dump_location_t &)
1512 : final override
1513 : {
1514 0 : internal_error ("unhandled tree code: %qs",
1515 0 : get_tree_code_name (TREE_CODE (t)));
1516 : }
1517 :
1518 : private:
1519 : /* Implicitly delete any diagnostics in the dtor. */
1520 : auto_delete_vec<pending_diagnostic> m_diagnostics;
1521 : };
1522 :
1523 : /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1524 : Verify that MODEL remains satisfiable. */
1525 :
1526 : #define ADD_SAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1527 : SELFTEST_BEGIN_STMT \
1528 : bool sat = (MODEL).add_constraint (LHS, OP, RHS, nullptr); \
1529 : ASSERT_TRUE (sat); \
1530 : SELFTEST_END_STMT
1531 :
1532 : /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1533 : Verify that the result is not satisfiable. */
1534 :
1535 : #define ADD_UNSAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1536 : SELFTEST_BEGIN_STMT \
1537 : bool sat = (MODEL).add_constraint (LHS, OP, RHS, nullptr); \
1538 : ASSERT_FALSE (sat); \
1539 : SELFTEST_END_STMT
1540 :
1541 : /* Implementation detail of the ASSERT_CONDITION_* macros. */
1542 :
1543 : void assert_condition (const location &loc,
1544 : region_model &model,
1545 : const svalue *lhs, tree_code op, const svalue *rhs,
1546 : tristate expected);
1547 :
1548 : void assert_condition (const location &loc,
1549 : region_model &model,
1550 : tree lhs, tree_code op, tree rhs,
1551 : tristate expected);
1552 :
1553 : /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1554 : as "true". */
1555 :
1556 : #define ASSERT_CONDITION_TRUE(REGION_MODEL, LHS, OP, RHS) \
1557 : SELFTEST_BEGIN_STMT \
1558 : assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1559 : tristate (tristate::TS_TRUE)); \
1560 : SELFTEST_END_STMT
1561 :
1562 : /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1563 : as "false". */
1564 :
1565 : #define ASSERT_CONDITION_FALSE(REGION_MODEL, LHS, OP, RHS) \
1566 : SELFTEST_BEGIN_STMT \
1567 : assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1568 : tristate (tristate::TS_FALSE)); \
1569 : SELFTEST_END_STMT
1570 :
1571 : /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1572 : as "unknown". */
1573 :
1574 : #define ASSERT_CONDITION_UNKNOWN(REGION_MODEL, LHS, OP, RHS) \
1575 : SELFTEST_BEGIN_STMT \
1576 : assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1577 : tristate (tristate::TS_UNKNOWN)); \
1578 : SELFTEST_END_STMT
1579 :
1580 : } /* end of namespace selftest. */
1581 :
1582 : #endif /* #if CHECKING_P */
1583 :
1584 : } // namespace ana
1585 :
1586 : #endif /* GCC_ANALYZER_REGION_MODEL_H */
|