gcc/analyzer/region-model.h

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