1/* Classes for modeling the state of memory.
2 Copyright (C) 2019-2024 Free Software Foundation, Inc.
3 Contributed by David Malcolm <dmalcolm@redhat.com>.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it
8under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful, but
13WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along 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
39using namespace ana;
40
41namespace inchash
42{
43 extern void add_path_var (path_var pv, hash &hstate);
44} // namespace inchash
45
46namespace ana {
47
48template <typename T>
49class one_way_id_map
50{
51 public:
52 one_way_id_map (int num_ids);
53 void put (T src, T dst);
54 T get_dst_for_src (T src) const;
55 void dump_to_pp (pretty_printer *pp) const;
56 void dump () const;
57 void update (T *) const;
58
59 private:
60 auto_vec<T> m_src_to_dst;
61 };
62
63/* class one_way_id_map. */
64
65/* one_way_id_map's ctor, which populates the map with dummy null values. */
66
67template <typename T>
68inline one_way_id_map<T>::one_way_id_map (int num_svalues)
69: m_src_to_dst (num_svalues)
70{
71 for (int i = 0; i < num_svalues; i++)
72 m_src_to_dst.quick_push (T::null ());
73}
74
75/* Record that SRC is to be mapped to DST. */
76
77template <typename T>
78inline void
79one_way_id_map<T>::put (T src, T dst)
80{
81 m_src_to_dst[src.as_int ()] = dst;
82}
83
84/* Get the new value for SRC within the map. */
85
86template <typename T>
87inline T
88one_way_id_map<T>::get_dst_for_src (T src) const
89{
90 if (src.null_p ())
91 return src;
92 return m_src_to_dst[src.as_int ()];
93}
94
95/* Dump this map to PP. */
96
97template <typename T>
98inline void
99one_way_id_map<T>::dump_to_pp (pretty_printer *pp) const
100{
101 pp_string (pp, "src to dst: {");
102 unsigned i;
103 T *dst;
104 FOR_EACH_VEC_ELT (m_src_to_dst, i, dst)
105 {
106 if (i > 0)
107 pp_string (pp, ", ");
108 T src (T::from_int (i));
109 src.print (pp);
110 pp_string (pp, " -> ");
111 dst->print (pp);
112 }
113 pp_string (pp, "}");
114 pp_newline (pp);
115}
116
117/* Dump this map to stderr. */
118
119template <typename T>
120DEBUG_FUNCTION inline void
121one_way_id_map<T>::dump () const
122{
123 pretty_printer pp;
124 pp.buffer->stream = stderr;
125 dump_to_pp (pp: &pp);
126 pp_flush (&pp);
127}
128
129/* Update *ID from the old value to its new value in this map. */
130
131template <typename T>
132inline void
133one_way_id_map<T>::update (T *id) const
134{
135 *id = get_dst_for_src (src: *id);
136}
137
138/* A mapping from region to svalue for use when tracking state. */
139
140class region_to_value_map
141{
142public:
143 typedef hash_map<const region *, const svalue *> hash_map_t;
144 typedef hash_map_t::iterator iterator;
145
146 region_to_value_map () : m_hash_map () {}
147 region_to_value_map (const region_to_value_map &other)
148 : m_hash_map (other.m_hash_map) {}
149 region_to_value_map &operator= (const region_to_value_map &other);
150
151 bool operator== (const region_to_value_map &other) const;
152 bool operator!= (const region_to_value_map &other) const
153 {
154 return !(*this == other);
155 }
156
157 iterator begin () const { return m_hash_map.begin (); }
158 iterator end () const { return m_hash_map.end (); }
159
160 const svalue * const *get (const region *reg) const
161 {
162 return const_cast <hash_map_t &> (m_hash_map).get (k: reg);
163 }
164 void put (const region *reg, const svalue *sval)
165 {
166 m_hash_map.put (k: reg, v: sval);
167 }
168 void remove (const region *reg)
169 {
170 m_hash_map.remove (k: reg);
171 }
172
173 bool is_empty () const { return m_hash_map.is_empty (); }
174
175 void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
176 void dump (bool simple) const;
177
178 json::object *to_json () const;
179
180 bool can_merge_with_p (const region_to_value_map &other,
181 region_to_value_map *out) const;
182
183 void purge_state_involving (const svalue *sval);
184
185private:
186 hash_map_t m_hash_map;
187};
188
189/* Various operations delete information from a region_model.
190
191 This struct tracks how many of each kind of entity were purged (e.g.
192 for selftests, and for debugging). */
193
194struct purge_stats
195{
196 purge_stats ()
197 : m_num_svalues (0),
198 m_num_regions (0),
199 m_num_equiv_classes (0),
200 m_num_constraints (0),
201 m_num_bounded_ranges_constraints (0),
202 m_num_client_items (0)
203 {}
204
205 int m_num_svalues;
206 int m_num_regions;
207 int m_num_equiv_classes;
208 int m_num_constraints;
209 int m_num_bounded_ranges_constraints;
210 int m_num_client_items;
211};
212
213/* A base class for visiting regions and svalues, with do-nothing
214 base implementations of the per-subclass vfuncs. */
215
216class visitor
217{
218public:
219 virtual void visit_region_svalue (const region_svalue *) {}
220 virtual void visit_constant_svalue (const constant_svalue *) {}
221 virtual void visit_unknown_svalue (const unknown_svalue *) {}
222 virtual void visit_poisoned_svalue (const poisoned_svalue *) {}
223 virtual void visit_setjmp_svalue (const setjmp_svalue *) {}
224 virtual void visit_initial_svalue (const initial_svalue *) {}
225 virtual void visit_unaryop_svalue (const unaryop_svalue *) {}
226 virtual void visit_binop_svalue (const binop_svalue *) {}
227 virtual void visit_sub_svalue (const sub_svalue *) {}
228 virtual void visit_repeated_svalue (const repeated_svalue *) {}
229 virtual void visit_bits_within_svalue (const bits_within_svalue *) {}
230 virtual void visit_unmergeable_svalue (const unmergeable_svalue *) {}
231 virtual void visit_placeholder_svalue (const placeholder_svalue *) {}
232 virtual void visit_widening_svalue (const widening_svalue *) {}
233 virtual void visit_compound_svalue (const compound_svalue *) {}
234 virtual void visit_conjured_svalue (const conjured_svalue *) {}
235 virtual void visit_asm_output_svalue (const asm_output_svalue *) {}
236 virtual void visit_const_fn_result_svalue (const const_fn_result_svalue *) {}
237
238 virtual void visit_region (const region *) {}
239};
240
241struct append_regions_cb_data;
242
243typedef void (*pop_frame_callback) (const region_model *model,
244 const region_model *prev_model,
245 const svalue *retval,
246 region_model_context *ctxt);
247
248/* A region_model encapsulates a representation of the state of memory, with
249 a tree of regions, along with their associated values.
250 The representation is graph-like because values can be pointers to
251 regions.
252 It also stores:
253 - a constraint_manager, capturing relationships between the values, and
254 - dynamic extents, mapping dynamically-allocated regions to svalues (their
255 capacities). */
256
257class region_model
258{
259 public:
260 typedef region_to_value_map dynamic_extents_t;
261
262 region_model (region_model_manager *mgr);
263 region_model (const region_model &other);
264 ~region_model ();
265 region_model &operator= (const region_model &other);
266
267 bool operator== (const region_model &other) const;
268 bool operator!= (const region_model &other) const
269 {
270 return !(*this == other);
271 }
272
273 hashval_t hash () const;
274
275 void print (pretty_printer *pp) const;
276
277 void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
278 void dump (FILE *fp, bool simple, bool multiline) const;
279 void dump (bool simple) const;
280
281 void debug () const;
282
283 json::object *to_json () const;
284
285 void validate () const;
286
287 void canonicalize ();
288 bool canonicalized_p () const;
289
290 void
291 on_stmt_pre (const gimple *stmt,
292 bool *out_unknown_side_effects,
293 region_model_context *ctxt);
294
295 void on_assignment (const gassign *stmt, region_model_context *ctxt);
296 const svalue *get_gassign_result (const gassign *assign,
297 region_model_context *ctxt);
298 void on_asm_stmt (const gasm *asm_stmt, region_model_context *ctxt);
299 bool on_call_pre (const gcall *stmt, region_model_context *ctxt);
300 void on_call_post (const gcall *stmt,
301 bool unknown_side_effects,
302 region_model_context *ctxt);
303
304 void purge_state_involving (const svalue *sval, region_model_context *ctxt);
305
306 void impl_deallocation_call (const call_details &cd);
307
308 const svalue *maybe_get_copy_bounds (const region *src_reg,
309 const svalue *num_bytes_sval);
310 void update_for_int_cst_return (const call_details &cd,
311 int retval,
312 bool unmergeable);
313 void update_for_zero_return (const call_details &cd,
314 bool unmergeable);
315 void update_for_nonzero_return (const call_details &cd);
316
317 void handle_unrecognized_call (const gcall *call,
318 region_model_context *ctxt);
319 void get_reachable_svalues (svalue_set *out,
320 const svalue *extra_sval,
321 const uncertainty_t *uncertainty);
322
323 void on_return (const greturn *stmt, region_model_context *ctxt);
324 void on_setjmp (const gcall *stmt, const exploded_node *enode,
325 region_model_context *ctxt);
326 void on_longjmp (const gcall *longjmp_call, const gcall *setjmp_call,
327 int setjmp_stack_depth, region_model_context *ctxt);
328
329 void update_for_phis (const supernode *snode,
330 const cfg_superedge *last_cfg_superedge,
331 region_model_context *ctxt);
332
333 void handle_phi (const gphi *phi, tree lhs, tree rhs,
334 const region_model &old_state,
335 hash_set<const svalue *> &svals_changing_meaning,
336 region_model_context *ctxt);
337
338 bool maybe_update_for_edge (const superedge &edge,
339 const gimple *last_stmt,
340 region_model_context *ctxt,
341 std::unique_ptr<rejected_constraint> *out);
342
343 void update_for_gcall (const gcall *call_stmt,
344 region_model_context *ctxt,
345 function *callee = NULL);
346
347 void update_for_return_gcall (const gcall *call_stmt,
348 region_model_context *ctxt);
349
350 const region *push_frame (const function &fun, const vec<const svalue *> *arg_sids,
351 region_model_context *ctxt);
352 const frame_region *get_current_frame () const { return m_current_frame; }
353 const function *get_current_function () const;
354 void pop_frame (tree result_lvalue,
355 const svalue **out_result,
356 region_model_context *ctxt,
357 bool eval_return_svalue = true);
358 int get_stack_depth () const;
359 const frame_region *get_frame_at_index (int index) const;
360
361 const region *get_lvalue (path_var pv, region_model_context *ctxt) const;
362 const region *get_lvalue (tree expr, region_model_context *ctxt) const;
363 const svalue *get_rvalue (path_var pv, region_model_context *ctxt) const;
364 const svalue *get_rvalue (tree expr, region_model_context *ctxt) const;
365
366 const region *deref_rvalue (const svalue *ptr_sval, tree ptr_tree,
367 region_model_context *ctxt,
368 bool add_nonnull_constraint = true) const;
369
370 const svalue *get_rvalue_for_bits (tree type,
371 const region *reg,
372 const bit_range &bits,
373 region_model_context *ctxt) const;
374
375 void set_value (const region *lhs_reg, const svalue *rhs_sval,
376 region_model_context *ctxt);
377 void set_value (tree lhs, tree rhs, region_model_context *ctxt);
378 void clobber_region (const region *reg);
379 void purge_region (const region *reg);
380 void fill_region (const region *reg,
381 const svalue *sval,
382 region_model_context *ctxt);
383 void zero_fill_region (const region *reg,
384 region_model_context *ctxt);
385 void write_bytes (const region *dest_reg,
386 const svalue *num_bytes_sval,
387 const svalue *sval,
388 region_model_context *ctxt);
389 const svalue *read_bytes (const region *src_reg,
390 tree src_ptr_expr,
391 const svalue *num_bytes_sval,
392 region_model_context *ctxt) const;
393 void copy_bytes (const region *dest_reg,
394 const region *src_reg,
395 tree src_ptr_expr,
396 const svalue *num_bytes_sval,
397 region_model_context *ctxt);
398 void mark_region_as_unknown (const region *reg, uncertainty_t *uncertainty);
399
400 tristate eval_condition (const svalue *lhs,
401 enum tree_code op,
402 const svalue *rhs) const;
403 tristate compare_initial_and_pointer (const initial_svalue *init,
404 const region_svalue *ptr) const;
405 tristate symbolic_greater_than (const binop_svalue *a,
406 const svalue *b) const;
407 tristate structural_equality (const svalue *a, const svalue *b) const;
408 tristate eval_condition (tree lhs,
409 enum tree_code op,
410 tree rhs,
411 region_model_context *ctxt) const;
412 bool add_constraint (tree lhs, enum tree_code op, tree rhs,
413 region_model_context *ctxt);
414 bool add_constraint (tree lhs, enum tree_code op, tree rhs,
415 region_model_context *ctxt,
416 std::unique_ptr<rejected_constraint> *out);
417
418 const region *
419 get_or_create_region_for_heap_alloc (const svalue *size_in_bytes,
420 region_model_context *ctxt,
421 bool update_state_machine = false,
422 const call_details *cd = nullptr);
423
424 const region *create_region_for_alloca (const svalue *size_in_bytes,
425 region_model_context *ctxt);
426 void get_referenced_base_regions (auto_bitmap &out_ids) const;
427
428 tree get_representative_tree (const svalue *sval) const;
429 tree get_representative_tree (const region *reg) const;
430 path_var
431 get_representative_path_var (const svalue *sval,
432 svalue_set *visited) const;
433 path_var
434 get_representative_path_var (const region *reg,
435 svalue_set *visited) const;
436
437 /* For selftests. */
438 constraint_manager *get_constraints ()
439 {
440 return m_constraints;
441 }
442
443 store *get_store () { return &m_store; }
444 const store *get_store () const { return &m_store; }
445
446 const dynamic_extents_t &
447 get_dynamic_extents () const
448 {
449 return m_dynamic_extents;
450 }
451 const svalue *get_dynamic_extents (const region *reg) const;
452 void set_dynamic_extents (const region *reg,
453 const svalue *size_in_bytes,
454 region_model_context *ctxt);
455 void unset_dynamic_extents (const region *reg);
456
457 region_model_manager *get_manager () const { return m_mgr; }
458 bounded_ranges_manager *get_range_manager () const
459 {
460 return m_mgr->get_range_manager ();
461 }
462
463 void unbind_region_and_descendents (const region *reg,
464 enum poison_kind pkind);
465
466 bool can_merge_with_p (const region_model &other_model,
467 const program_point &point,
468 region_model *out_model,
469 const extrinsic_state *ext_state = NULL,
470 const program_state *state_a = NULL,
471 const program_state *state_b = NULL) const;
472
473 tree get_fndecl_for_call (const gcall *call,
474 region_model_context *ctxt);
475
476 void get_regions_for_current_frame (auto_vec<const decl_region *> *out) const;
477 static void append_regions_cb (const region *base_reg,
478 struct append_regions_cb_data *data);
479
480 const svalue *get_store_value (const region *reg,
481 region_model_context *ctxt) const;
482 const svalue *get_store_bytes (const region *base_reg,
483 const byte_range &bytes,
484 region_model_context *ctxt) const;
485 const svalue *scan_for_null_terminator (const region *reg,
486 tree expr,
487 const svalue **out_sval,
488 region_model_context *ctxt) const;
489 const svalue *scan_for_null_terminator_1 (const region *reg,
490 tree expr,
491 const svalue **out_sval,
492 region_model_context *ctxt) const;
493
494 bool region_exists_p (const region *reg) const;
495
496 void loop_replay_fixup (const region_model *dst_state);
497
498 const svalue *get_capacity (const region *reg) const;
499
500 bool replay_call_summary (call_summary_replay &r,
501 const region_model &summary);
502
503 void maybe_complain_about_infoleak (const region *dst_reg,
504 const svalue *copied_sval,
505 const region *src_reg,
506 region_model_context *ctxt);
507
508 void set_errno (const call_details &cd);
509
510 /* Implemented in sm-fd.cc */
511 void mark_as_valid_fd (const svalue *sval, region_model_context *ctxt);
512
513 /* Implemented in sm-malloc.cc */
514 void on_realloc_with_move (const call_details &cd,
515 const svalue *old_ptr_sval,
516 const svalue *new_ptr_sval);
517
518 /* Implemented in sm-malloc.cc. */
519 void
520 transition_ptr_sval_non_null (region_model_context *ctxt,
521 const svalue *new_ptr_sval);
522
523 /* Implemented in sm-taint.cc. */
524 void mark_as_tainted (const svalue *sval,
525 region_model_context *ctxt);
526
527 bool add_constraint (const svalue *lhs,
528 enum tree_code op,
529 const svalue *rhs,
530 region_model_context *ctxt);
531
532 const svalue *check_for_poison (const svalue *sval,
533 tree expr,
534 const region *src_region,
535 region_model_context *ctxt) const;
536
537 void check_region_for_write (const region *dest_reg,
538 const svalue *sval_hint,
539 region_model_context *ctxt) const;
540
541 const svalue *
542 check_for_null_terminated_string_arg (const call_details &cd,
543 unsigned idx) const;
544 const svalue *
545 check_for_null_terminated_string_arg (const call_details &cd,
546 unsigned idx,
547 bool include_terminator,
548 const svalue **out_sval) const;
549
550 const builtin_known_function *
551 get_builtin_kf (const gcall *call,
552 region_model_context *ctxt = NULL) const;
553
554 static void
555 register_pop_frame_callback (const pop_frame_callback &callback)
556 {
557 pop_frame_callbacks.safe_push (obj: callback);
558 }
559
560 static void
561 notify_on_pop_frame (const region_model *model,
562 const region_model *prev_model,
563 const svalue *retval,
564 region_model_context *ctxt)
565 {
566 for (auto &callback : pop_frame_callbacks)
567 callback (model, prev_model, retval, ctxt);
568 }
569
570 bool called_from_main_p () const;
571
572private:
573 const region *get_lvalue_1 (path_var pv, region_model_context *ctxt) const;
574 const svalue *get_rvalue_1 (path_var pv, region_model_context *ctxt) const;
575
576 path_var
577 get_representative_path_var_1 (const svalue *sval,
578 svalue_set *visited) const;
579 path_var
580 get_representative_path_var_1 (const region *reg,
581 svalue_set *visited) const;
582
583 const known_function *get_known_function (tree fndecl,
584 const call_details &cd) const;
585 const known_function *get_known_function (enum internal_fn) const;
586
587 bool add_constraints_from_binop (const svalue *outer_lhs,
588 enum tree_code outer_op,
589 const svalue *outer_rhs,
590 bool *out,
591 region_model_context *ctxt);
592
593 void update_for_call_superedge (const call_superedge &call_edge,
594 region_model_context *ctxt);
595 void update_for_return_superedge (const return_superedge &return_edge,
596 region_model_context *ctxt);
597 bool apply_constraints_for_gcond (const cfg_superedge &edge,
598 const gcond *cond_stmt,
599 region_model_context *ctxt,
600 std::unique_ptr<rejected_constraint> *out);
601 bool apply_constraints_for_gswitch (const switch_cfg_superedge &edge,
602 const gswitch *switch_stmt,
603 region_model_context *ctxt,
604 std::unique_ptr<rejected_constraint> *out);
605 bool apply_constraints_for_ggoto (const cfg_superedge &edge,
606 const ggoto *goto_stmt,
607 region_model_context *ctxt);
608 bool apply_constraints_for_exception (const gimple *last_stmt,
609 region_model_context *ctxt,
610 std::unique_ptr<rejected_constraint> *out);
611
612 int poison_any_pointers_to_descendents (const region *reg,
613 enum poison_kind pkind);
614
615 void on_top_level_param (tree param,
616 bool nonnull,
617 region_model_context *ctxt);
618
619 const svalue *get_initial_value_for_global (const region *reg) const;
620
621 const region * get_region_for_poisoned_expr (tree expr) const;
622
623 void check_dynamic_size_for_taint (enum memory_space mem_space,
624 const svalue *size_in_bytes,
625 region_model_context *ctxt) const;
626 void check_dynamic_size_for_floats (const svalue *size_in_bytes,
627 region_model_context *ctxt) const;
628
629 void check_region_for_taint (const region *reg,
630 enum access_direction dir,
631 region_model_context *ctxt) const;
632
633 void check_for_writable_region (const region* dest_reg,
634 region_model_context *ctxt) const;
635 bool check_region_access (const region *reg,
636 enum access_direction dir,
637 const svalue *sval_hint,
638 region_model_context *ctxt) const;
639 bool check_region_for_read (const region *src_reg,
640 region_model_context *ctxt) const;
641 void check_region_size (const region *lhs_reg, const svalue *rhs_sval,
642 region_model_context *ctxt) const;
643
644 /* Implemented in bounds-checking.cc */
645 bool check_symbolic_bounds (const region *base_reg,
646 const svalue *sym_byte_offset,
647 const svalue *num_bytes_sval,
648 const svalue *capacity,
649 enum access_direction dir,
650 const svalue *sval_hint,
651 region_model_context *ctxt) const;
652 bool check_region_bounds (const region *reg, enum access_direction dir,
653 const svalue *sval_hint,
654 region_model_context *ctxt) const;
655
656 void check_call_args (const call_details &cd) const;
657 void check_call_format_attr (const call_details &cd,
658 tree format_attr) const;
659 void check_function_attr_access (const gcall *call,
660 tree callee_fndecl,
661 region_model_context *ctxt,
662 rdwr_map &rdwr_idx) const;
663 void check_function_attr_null_terminated_string_arg (const gcall *call,
664 tree callee_fndecl,
665 region_model_context *ctxt,
666 rdwr_map &rdwr_idx);
667 void check_one_function_attr_null_terminated_string_arg (const gcall *call,
668 tree callee_fndecl,
669 region_model_context *ctxt,
670 rdwr_map &rdwr_idx,
671 tree attr);
672 void check_function_attrs (const gcall *call,
673 tree callee_fndecl,
674 region_model_context *ctxt);
675
676 static auto_vec<pop_frame_callback> pop_frame_callbacks;
677 /* Storing this here to avoid passing it around everywhere. */
678 region_model_manager *const m_mgr;
679
680 store m_store;
681
682 constraint_manager *m_constraints; // TODO: embed, rather than dynalloc?
683
684 const frame_region *m_current_frame;
685
686 /* Map from base region to size in bytes, for tracking the sizes of
687 dynamically-allocated regions.
688 This is part of the region_model rather than the region to allow for
689 memory regions to be resized (e.g. by realloc). */
690 dynamic_extents_t m_dynamic_extents;
691};
692
693/* Some region_model activity could lead to warnings (e.g. attempts to use an
694 uninitialized value). This abstract base class encapsulates an interface
695 for the region model to use when emitting such warnings.
696
697 Having this as an abstract base class allows us to support the various
698 operations needed by program_state in the analyzer within region_model,
699 whilst keeping them somewhat modularized. */
700
701class region_model_context
702{
703 public:
704 /* Hook for clients to store pending diagnostics.
705 Return true if the diagnostic was stored, or false if it was deleted.
706 Optionally provide a custom stmt_finder. */
707 virtual bool warn (std::unique_ptr<pending_diagnostic> d,
708 const stmt_finder *custom_finder = NULL) = 0;
709
710 /* Hook for clients to add a note to the last previously stored
711 pending diagnostic. */
712 virtual void add_note (std::unique_ptr<pending_note> pn) = 0;
713
714 /* Hook for clients to add an event to the last previously stored
715 pending diagnostic. */
716 virtual void add_event (std::unique_ptr<checker_event> event) = 0;
717
718 /* Hook for clients to be notified when an SVAL that was reachable
719 in a previous state is no longer live, so that clients can emit warnings
720 about leaks. */
721 virtual void on_svalue_leak (const svalue *sval) = 0;
722
723 /* Hook for clients to be notified when the set of explicitly live
724 svalues changes, so that they can purge state relating to dead
725 svalues. */
726 virtual void on_liveness_change (const svalue_set &live_svalues,
727 const region_model *model) = 0;
728
729 virtual logger *get_logger () = 0;
730
731 /* Hook for clients to be notified when the condition
732 "LHS OP RHS" is added to the region model.
733 This exists so that state machines can detect tests on edges,
734 and use them to trigger sm-state transitions (e.g. transitions due
735 to ptrs becoming known to be NULL or non-NULL, rather than just
736 "unchecked") */
737 virtual void on_condition (const svalue *lhs,
738 enum tree_code op,
739 const svalue *rhs) = 0;
740
741 /* Hook for clients to be notified when the condition that
742 SVAL is within RANGES is added to the region model.
743 Similar to on_condition, but for use when handling switch statements.
744 RANGES is non-empty. */
745 virtual void on_bounded_ranges (const svalue &sval,
746 const bounded_ranges &ranges) = 0;
747
748 /* Hook for clients to be notified when a frame is popped from the stack. */
749 virtual void on_pop_frame (const frame_region *) = 0;
750
751 /* Hooks for clients to be notified when an unknown change happens
752 to SVAL (in response to a call to an unknown function). */
753 virtual void on_unknown_change (const svalue *sval, bool is_mutable) = 0;
754
755 /* Hooks for clients to be notified when a phi node is handled,
756 where RHS is the pertinent argument. */
757 virtual void on_phi (const gphi *phi, tree rhs) = 0;
758
759 /* Hooks for clients to be notified when the region model doesn't
760 know how to handle the tree code of T at LOC. */
761 virtual void on_unexpected_tree_code (tree t,
762 const dump_location_t &loc) = 0;
763
764 /* Hook for clients to be notified when a function_decl escapes. */
765 virtual void on_escaped_function (tree fndecl) = 0;
766
767 virtual uncertainty_t *get_uncertainty () = 0;
768
769 /* Hook for clients to purge state involving SVAL. */
770 virtual void purge_state_involving (const svalue *sval) = 0;
771
772 /* Hook for clients to split state with a non-standard path. */
773 virtual void bifurcate (std::unique_ptr<custom_edge_info> info) = 0;
774
775 /* Hook for clients to terminate the standard path. */
776 virtual void terminate_path () = 0;
777
778 virtual const extrinsic_state *get_ext_state () const = 0;
779
780 /* Hook for clients to access the a specific state machine in
781 any underlying program_state. */
782 virtual bool
783 get_state_map_by_name (const char *name,
784 sm_state_map **out_smap,
785 const state_machine **out_sm,
786 unsigned *out_sm_idx,
787 std::unique_ptr<sm_context> *out_sm_context) = 0;
788
789 /* Precanned ways for clients to access specific state machines. */
790 bool get_fd_map (sm_state_map **out_smap,
791 const state_machine **out_sm,
792 unsigned *out_sm_idx,
793 std::unique_ptr<sm_context> *out_sm_context)
794 {
795 return get_state_map_by_name (name: "file-descriptor", out_smap, out_sm,
796 out_sm_idx, out_sm_context);
797 }
798 bool get_malloc_map (sm_state_map **out_smap,
799 const state_machine **out_sm,
800 unsigned *out_sm_idx)
801 {
802 return get_state_map_by_name (name: "malloc", out_smap, out_sm, out_sm_idx, NULL);
803 }
804 bool get_taint_map (sm_state_map **out_smap,
805 const state_machine **out_sm,
806 unsigned *out_sm_idx)
807 {
808 return get_state_map_by_name (name: "taint", out_smap, out_sm, out_sm_idx, NULL);
809 }
810
811 bool possibly_tainted_p (const svalue *sval);
812
813 /* Get the current statement, if any. */
814 virtual const gimple *get_stmt () const = 0;
815
816 virtual const exploded_graph *get_eg () const = 0;
817
818 /* Hooks for detecting infinite loops. */
819 virtual void maybe_did_work () = 0;
820 virtual bool checking_for_infinite_loop_p () const = 0;
821 virtual void on_unusable_in_infinite_loop () = 0;
822};
823
824/* A "do nothing" subclass of region_model_context. */
825
826class noop_region_model_context : public region_model_context
827{
828public:
829 bool warn (std::unique_ptr<pending_diagnostic>,
830 const stmt_finder *) override { return false; }
831 void add_note (std::unique_ptr<pending_note>) override;
832 void add_event (std::unique_ptr<checker_event>) override;
833 void on_svalue_leak (const svalue *) override {}
834 void on_liveness_change (const svalue_set &,
835 const region_model *) override {}
836 logger *get_logger () override { return NULL; }
837 void on_condition (const svalue *lhs ATTRIBUTE_UNUSED,
838 enum tree_code op ATTRIBUTE_UNUSED,
839 const svalue *rhs ATTRIBUTE_UNUSED) override
840 {
841 }
842 void on_bounded_ranges (const svalue &,
843 const bounded_ranges &) override
844 {
845 }
846 void on_pop_frame (const frame_region *) override {}
847 void on_unknown_change (const svalue *sval ATTRIBUTE_UNUSED,
848 bool is_mutable ATTRIBUTE_UNUSED) override
849 {
850 }
851 void on_phi (const gphi *phi ATTRIBUTE_UNUSED,
852 tree rhs ATTRIBUTE_UNUSED) override
853 {
854 }
855 void on_unexpected_tree_code (tree, const dump_location_t &) override {}
856
857 void on_escaped_function (tree) override {}
858
859 uncertainty_t *get_uncertainty () override { return NULL; }
860
861 void purge_state_involving (const svalue *sval ATTRIBUTE_UNUSED) override {}
862
863 void bifurcate (std::unique_ptr<custom_edge_info> info) override;
864 void terminate_path () override;
865
866 const extrinsic_state *get_ext_state () const override { return NULL; }
867
868 bool get_state_map_by_name (const char *,
869 sm_state_map **,
870 const state_machine **,
871 unsigned *,
872 std::unique_ptr<sm_context> *) override
873 {
874 return false;
875 }
876
877 const gimple *get_stmt () const override { return NULL; }
878 const exploded_graph *get_eg () const override { return NULL; }
879 void maybe_did_work () override {}
880 bool checking_for_infinite_loop_p () const override { return false; }
881 void on_unusable_in_infinite_loop () override {}
882};
883
884/* A subclass of region_model_context for determining if operations fail
885 e.g. "can we generate a region for the lvalue of EXPR?". */
886
887class tentative_region_model_context : public noop_region_model_context
888{
889public:
890 tentative_region_model_context () : m_num_unexpected_codes (0) {}
891
892 void on_unexpected_tree_code (tree, const dump_location_t &)
893 final override
894 {
895 m_num_unexpected_codes++;
896 }
897
898 bool had_errors_p () const { return m_num_unexpected_codes > 0; }
899
900private:
901 int m_num_unexpected_codes;
902};
903
904/* Subclass of region_model_context that wraps another context, allowing
905 for extra code to be added to the various hooks. */
906
907class region_model_context_decorator : public region_model_context
908{
909 public:
910 bool warn (std::unique_ptr<pending_diagnostic> d,
911 const stmt_finder *custom_finder) override
912 {
913 if (m_inner)
914 return m_inner->warn (d: std::move (d), custom_finder);
915 else
916 return false;
917 }
918
919 void add_note (std::unique_ptr<pending_note> pn) override
920 {
921 if (m_inner)
922 m_inner->add_note (pn: std::move (pn));
923 }
924 void add_event (std::unique_ptr<checker_event> event) override;
925
926 void on_svalue_leak (const svalue *sval) override
927 {
928 if (m_inner)
929 m_inner->on_svalue_leak (sval);
930 }
931
932 void on_liveness_change (const svalue_set &live_svalues,
933 const region_model *model) override
934 {
935 if (m_inner)
936 m_inner->on_liveness_change (live_svalues, model);
937 }
938
939 logger *get_logger () override
940 {
941 if (m_inner)
942 return m_inner->get_logger ();
943 else
944 return nullptr;
945 }
946
947 void on_condition (const svalue *lhs,
948 enum tree_code op,
949 const svalue *rhs) override
950 {
951 if (m_inner)
952 m_inner->on_condition (lhs, op, rhs);
953 }
954
955 void on_bounded_ranges (const svalue &sval,
956 const bounded_ranges &ranges) override
957 {
958 if (m_inner)
959 m_inner->on_bounded_ranges (sval, ranges);
960 }
961
962 void on_pop_frame (const frame_region *frame_reg) override
963 {
964 if (m_inner)
965 m_inner->on_pop_frame (frame_reg);
966 }
967
968 void on_unknown_change (const svalue *sval, bool is_mutable) override
969 {
970 if (m_inner)
971 m_inner->on_unknown_change (sval, is_mutable);
972 }
973
974 void on_phi (const gphi *phi, tree rhs) override
975 {
976 if (m_inner)
977 m_inner->on_phi (phi, rhs);
978 }
979
980 void on_unexpected_tree_code (tree t,
981 const dump_location_t &loc) override
982 {
983 if (m_inner)
984 m_inner->on_unexpected_tree_code (t, loc);
985 }
986
987 void on_escaped_function (tree fndecl) override
988 {
989 if (m_inner)
990 m_inner->on_escaped_function (fndecl);
991 }
992
993 uncertainty_t *get_uncertainty () override
994 {
995 if (m_inner)
996 return m_inner->get_uncertainty ();
997 else
998 return nullptr;
999 }
1000
1001 void purge_state_involving (const svalue *sval) override
1002 {
1003 if (m_inner)
1004 m_inner->purge_state_involving (sval);
1005 }
1006
1007 void bifurcate (std::unique_ptr<custom_edge_info> info) override
1008 {
1009 if (m_inner)
1010 m_inner->bifurcate (info: std::move (info));
1011 }
1012
1013 void terminate_path () override
1014 {
1015 if (m_inner)
1016 m_inner->terminate_path ();
1017 }
1018
1019 const extrinsic_state *get_ext_state () const override
1020 {
1021 if (m_inner)
1022 return m_inner->get_ext_state ();
1023 else
1024 return nullptr;
1025 }
1026
1027 bool get_state_map_by_name (const char *name,
1028 sm_state_map **out_smap,
1029 const state_machine **out_sm,
1030 unsigned *out_sm_idx,
1031 std::unique_ptr<sm_context> *out_sm_context)
1032 override
1033 {
1034 if (m_inner)
1035 return m_inner->get_state_map_by_name (name, out_smap, out_sm, out_sm_idx,
1036 out_sm_context);
1037 else
1038 return false;
1039 }
1040
1041 const gimple *get_stmt () const override
1042 {
1043 if (m_inner)
1044 return m_inner->get_stmt ();
1045 else
1046 return nullptr;
1047 }
1048
1049 const exploded_graph *get_eg () const override
1050 {
1051 if (m_inner)
1052 return m_inner->get_eg ();
1053 else
1054 return nullptr;
1055 }
1056
1057 void maybe_did_work () override
1058 {
1059 if (m_inner)
1060 m_inner->maybe_did_work ();
1061 }
1062
1063 bool checking_for_infinite_loop_p () const override
1064 {
1065 if (m_inner)
1066 return m_inner->checking_for_infinite_loop_p ();
1067 return false;
1068 }
1069 void on_unusable_in_infinite_loop () override
1070 {
1071 if (m_inner)
1072 m_inner->on_unusable_in_infinite_loop ();
1073 }
1074
1075protected:
1076 region_model_context_decorator (region_model_context *inner)
1077 : m_inner (inner)
1078 {
1079 }
1080
1081 region_model_context *m_inner;
1082};
1083
1084/* Subclass of region_model_context_decorator with a hook for adding
1085 notes/events when saving diagnostics. */
1086
1087class annotating_context : public region_model_context_decorator
1088{
1089public:
1090 bool warn (std::unique_ptr<pending_diagnostic> d,
1091 const stmt_finder *custom_finder) override
1092 {
1093 if (m_inner)
1094 if (m_inner->warn (d: std::move (d), custom_finder))
1095 {
1096 add_annotations ();
1097 return true;
1098 }
1099 return false;
1100 }
1101
1102 /* Hook to add new event(s)/note(s) */
1103 virtual void add_annotations () = 0;
1104
1105protected:
1106 annotating_context (region_model_context *inner)
1107 : region_model_context_decorator (inner)
1108 {
1109 }
1110};
1111
1112/* A bundle of data for use when attempting to merge two region_model
1113 instances to make a third. */
1114
1115struct model_merger
1116{
1117 model_merger (const region_model *model_a,
1118 const region_model *model_b,
1119 const program_point &point,
1120 region_model *merged_model,
1121 const extrinsic_state *ext_state,
1122 const program_state *state_a,
1123 const program_state *state_b)
1124 : m_model_a (model_a), m_model_b (model_b),
1125 m_point (point),
1126 m_merged_model (merged_model),
1127 m_ext_state (ext_state),
1128 m_state_a (state_a), m_state_b (state_b)
1129 {
1130 }
1131
1132 void dump_to_pp (pretty_printer *pp, bool simple) const;
1133 void dump (FILE *fp, bool simple) const;
1134 void dump (bool simple) const;
1135
1136 region_model_manager *get_manager () const
1137 {
1138 return m_model_a->get_manager ();
1139 }
1140
1141 bool mergeable_svalue_p (const svalue *) const;
1142 const function_point &get_function_point () const
1143 {
1144 return m_point.get_function_point ();
1145 }
1146
1147 void on_widening_reuse (const widening_svalue *widening_sval);
1148
1149 const region_model *m_model_a;
1150 const region_model *m_model_b;
1151 const program_point &m_point;
1152 region_model *m_merged_model;
1153
1154 const extrinsic_state *m_ext_state;
1155 const program_state *m_state_a;
1156 const program_state *m_state_b;
1157
1158 hash_set<const svalue *> m_svals_changing_meaning;
1159};
1160
1161/* A record that can (optionally) be written out when
1162 region_model::add_constraint fails. */
1163
1164class rejected_constraint
1165{
1166public:
1167 virtual ~rejected_constraint () {}
1168 virtual void dump_to_pp (pretty_printer *pp) const = 0;
1169
1170 const region_model &get_model () const { return m_model; }
1171
1172protected:
1173 rejected_constraint (const region_model &model)
1174 : m_model (model)
1175 {}
1176
1177 region_model m_model;
1178};
1179
1180class rejected_op_constraint : public rejected_constraint
1181{
1182public:
1183 rejected_op_constraint (const region_model &model,
1184 tree lhs, enum tree_code op, tree rhs)
1185 : rejected_constraint (model),
1186 m_lhs (lhs), m_op (op), m_rhs (rhs)
1187 {}
1188
1189 void dump_to_pp (pretty_printer *pp) const final override;
1190
1191 tree m_lhs;
1192 enum tree_code m_op;
1193 tree m_rhs;
1194};
1195
1196class rejected_default_case : public rejected_constraint
1197{
1198public:
1199 rejected_default_case (const region_model &model)
1200 : rejected_constraint (model)
1201 {}
1202
1203 void dump_to_pp (pretty_printer *pp) const final override;
1204};
1205
1206class rejected_ranges_constraint : public rejected_constraint
1207{
1208public:
1209 rejected_ranges_constraint (const region_model &model,
1210 tree expr, const bounded_ranges *ranges)
1211 : rejected_constraint (model),
1212 m_expr (expr), m_ranges (ranges)
1213 {}
1214
1215 void dump_to_pp (pretty_printer *pp) const final override;
1216
1217private:
1218 tree m_expr;
1219 const bounded_ranges *m_ranges;
1220};
1221
1222/* A bundle of state. */
1223
1224class engine
1225{
1226public:
1227 engine (const supergraph *sg = NULL, logger *logger = NULL);
1228 const supergraph *get_supergraph () { return m_sg; }
1229 region_model_manager *get_model_manager () { return &m_mgr; }
1230 known_function_manager *get_known_function_manager ()
1231 {
1232 return m_mgr.get_known_function_manager ();
1233 }
1234
1235 void log_stats (logger *logger) const;
1236
1237private:
1238 const supergraph *m_sg;
1239 region_model_manager m_mgr;
1240};
1241
1242} // namespace ana
1243
1244extern void debug (const region_model &rmodel);
1245
1246namespace ana {
1247
1248#if CHECKING_P
1249
1250namespace selftest {
1251
1252using namespace ::selftest;
1253
1254/* An implementation of region_model_context for use in selftests, which
1255 stores any pending_diagnostic instances passed to it. */
1256
1257class test_region_model_context : public noop_region_model_context
1258{
1259public:
1260 bool warn (std::unique_ptr<pending_diagnostic> d,
1261 const stmt_finder *) final override
1262 {
1263 m_diagnostics.safe_push (obj: d.release ());
1264 return true;
1265 }
1266
1267 unsigned get_num_diagnostics () const { return m_diagnostics.length (); }
1268
1269 void on_unexpected_tree_code (tree t, const dump_location_t &)
1270 final override
1271 {
1272 internal_error ("unhandled tree code: %qs",
1273 get_tree_code_name (TREE_CODE (t)));
1274 }
1275
1276private:
1277 /* Implicitly delete any diagnostics in the dtor. */
1278 auto_delete_vec<pending_diagnostic> m_diagnostics;
1279};
1280
1281/* Attempt to add the constraint (LHS OP RHS) to MODEL.
1282 Verify that MODEL remains satisfiable. */
1283
1284#define ADD_SAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1285 SELFTEST_BEGIN_STMT \
1286 bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL); \
1287 ASSERT_TRUE (sat); \
1288 SELFTEST_END_STMT
1289
1290/* Attempt to add the constraint (LHS OP RHS) to MODEL.
1291 Verify that the result is not satisfiable. */
1292
1293#define ADD_UNSAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1294 SELFTEST_BEGIN_STMT \
1295 bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL); \
1296 ASSERT_FALSE (sat); \
1297 SELFTEST_END_STMT
1298
1299/* Implementation detail of the ASSERT_CONDITION_* macros. */
1300
1301void assert_condition (const location &loc,
1302 region_model &model,
1303 const svalue *lhs, tree_code op, const svalue *rhs,
1304 tristate expected);
1305
1306void assert_condition (const location &loc,
1307 region_model &model,
1308 tree lhs, tree_code op, tree rhs,
1309 tristate expected);
1310
1311/* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1312 as "true". */
1313
1314#define ASSERT_CONDITION_TRUE(REGION_MODEL, LHS, OP, RHS) \
1315 SELFTEST_BEGIN_STMT \
1316 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1317 tristate (tristate::TS_TRUE)); \
1318 SELFTEST_END_STMT
1319
1320/* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1321 as "false". */
1322
1323#define ASSERT_CONDITION_FALSE(REGION_MODEL, LHS, OP, RHS) \
1324 SELFTEST_BEGIN_STMT \
1325 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1326 tristate (tristate::TS_FALSE)); \
1327 SELFTEST_END_STMT
1328
1329/* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1330 as "unknown". */
1331
1332#define ASSERT_CONDITION_UNKNOWN(REGION_MODEL, LHS, OP, RHS) \
1333 SELFTEST_BEGIN_STMT \
1334 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
1335 tristate (tristate::TS_UNKNOWN)); \
1336 SELFTEST_END_STMT
1337
1338} /* end of namespace selftest. */
1339
1340#endif /* #if CHECKING_P */
1341
1342} // namespace ana
1343
1344#endif /* GCC_ANALYZER_REGION_MODEL_H */
1345

source code of gcc/analyzer/region-model.h