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   void impl_call_errno_location (const call_details &cd);
 353   bool impl_call_error (const call_details &cd, unsigned min_args,
 354                         bool *out_terminate_path);
 355   void impl_call_fgets (const call_details &cd);
 356   void impl_call_fread (const call_details &cd);
 357   void impl_call_free (const call_details &cd);
 358   void impl_call_malloc (const call_details &cd);
 359   void impl_call_memcpy (const call_details &cd);
 360   void impl_call_memset (const call_details &cd);
 361   void impl_call_pipe (const call_details &cd);
 362   void impl_call_putenv (const call_details &cd);
 363   void impl_call_realloc (const call_details &cd);
 364   void impl_call_strchr (const call_details &cd);
 365   void impl_call_strcpy (const call_details &cd);
 366   void impl_call_strlen (const call_details &cd);
 367   void impl_call_operator_new (const call_details &cd);
 368   void impl_call_operator_delete (const call_details &cd);
 369   void impl_deallocation_call (const call_details &cd);
 370
 371   /* Implemented in varargs.cc.  */
 372   void impl_call_va_start (const call_details &cd);
 373   void impl_call_va_copy (const call_details &cd);
 374   void impl_call_va_arg (const call_details &cd);
 375   void impl_call_va_end (const call_details &cd);
 376
 377   const svalue *maybe_get_copy_bounds (const region *src_reg,
 378                                        const svalue *num_bytes_sval);
 379   void update_for_int_cst_return (const call_details &cd,
 380                                   int retval,
 381                                   bool unmergeable);
 382   void update_for_zero_return (const call_details &cd,
 383                                bool unmergeable);
 384   void update_for_nonzero_return (const call_details &cd);
 385
 386   void handle_unrecognized_call (const gcall *call,
 387                                  region_model_context *ctxt);
 388   void get_reachable_svalues (svalue_set *out,
 389                               const svalue *extra_sval,
 390                               const uncertainty_t *uncertainty);
 391
 392   void on_return (const greturn *stmt, region_model_context *ctxt);
 393   void on_setjmp (const gcall *stmt, const exploded_node *enode,
 394                   region_model_context *ctxt);
 395   void on_longjmp (const gcall *longjmp_call, const gcall *setjmp_call,
 396                    int setjmp_stack_depth, region_model_context *ctxt);
 397
 398   void update_for_phis (const supernode *snode,
 399                         const cfg_superedge *last_cfg_superedge,
 400                         region_model_context *ctxt);
 401
 402   void handle_phi (const gphi *phi, tree lhs, tree rhs,
 403                    const region_model &old_state,
 404                    region_model_context *ctxt);
 405
 406   bool maybe_update_for_edge (const superedge &edge,
 407                               const gimple *last_stmt,
 408                               region_model_context *ctxt,
 409                               rejected_constraint **out);
 410
 411   void update_for_gcall (const gcall *call_stmt,
 412                          region_model_context *ctxt,
 413                          function *callee = NULL);
 414
 415   void update_for_return_gcall (const gcall *call_stmt,
 416                                 region_model_context *ctxt);
 417
 418   const region *push_frame (function *fun, const vec<const svalue *> *arg_sids,
 419                             region_model_context *ctxt);
 420   const frame_region *get_current_frame () const { return m_current_frame; }
 421   function * get_current_function () const;
 422   void pop_frame (tree result_lvalue,
 423                   const svalue **out_result,
 424                   region_model_context *ctxt);
 425   int get_stack_depth () const;
 426   const frame_region *get_frame_at_index (int index) const;
 427
 428   const region *get_lvalue (path_var pv, region_model_context *ctxt) const;
 429   const region *get_lvalue (tree expr, region_model_context *ctxt) const;
 430   const svalue *get_rvalue (path_var pv, region_model_context *ctxt) const;
 431   const svalue *get_rvalue (tree expr, region_model_context *ctxt) const;
 432
 433   const region *deref_rvalue (const svalue *ptr_sval, tree ptr_tree,
 434                                region_model_context *ctxt) const;
 435
 436   const svalue *get_rvalue_for_bits (tree type,
 437                                      const region *reg,
 438                                      const bit_range &bits,
 439                                      region_model_context *ctxt) const;
 440
 441   void set_value (const region *lhs_reg, const svalue *rhs_sval,
 442                   region_model_context *ctxt);
 443   void set_value (tree lhs, tree rhs, region_model_context *ctxt);
 444   void clobber_region (const region *reg);
 445   void purge_region (const region *reg);
 446   void fill_region (const region *reg, const svalue *sval);
 447   void zero_fill_region (const region *reg);
 448   void mark_region_as_unknown (const region *reg, uncertainty_t *uncertainty);
 449
 450   tristate eval_condition (const svalue *lhs,
 451                            enum tree_code op,
 452                            const svalue *rhs) const;
 453   tristate eval_condition_without_cm (const svalue *lhs,
 454                                       enum tree_code op,
 455                                       const svalue *rhs) const;
 456   tristate compare_initial_and_pointer (const initial_svalue *init,
 457                                         const region_svalue *ptr) const;
 458   tristate symbolic_greater_than (const binop_svalue *a,
 459                                   const svalue *b) const;
 460   tristate structural_equality (const svalue *a, const svalue *b) const;
 461   tristate eval_condition (tree lhs,
 462                            enum tree_code op,
 463                            tree rhs,
 464                            region_model_context *ctxt);
 465   bool add_constraint (tree lhs, enum tree_code op, tree rhs,
 466                        region_model_context *ctxt);
 467   bool add_constraint (tree lhs, enum tree_code op, tree rhs,
 468                        region_model_context *ctxt,
 469                        rejected_constraint **out);
 470
 471   const region *create_region_for_heap_alloc (const svalue *size_in_bytes,
 472                                               region_model_context *ctxt);
 473   const region *create_region_for_alloca (const svalue *size_in_bytes,
 474                                           region_model_context *ctxt);
 475
 476   tree get_representative_tree (const svalue *sval) const;
 477   tree get_representative_tree (const region *reg) const;
 478   path_var
 479   get_representative_path_var (const svalue *sval,
 480                                svalue_set *visited) const;
 481   path_var
 482   get_representative_path_var (const region *reg,
 483                                svalue_set *visited) const;
 484
 485   /* For selftests.  */
 486   constraint_manager *get_constraints ()
 487   {
 488     return m_constraints;
 489   }
 490
 491   store *get_store () { return &m_store; }
 492   const store *get_store () const { return &m_store; }
 493
 494   const dynamic_extents_t &
 495   get_dynamic_extents () const
 496   {
 497     return m_dynamic_extents;
 498   }
 499   const svalue *get_dynamic_extents (const region *reg) const;
 500   void set_dynamic_extents (const region *reg,
 501                             const svalue *size_in_bytes,
 502                             region_model_context *ctxt);
 503   void unset_dynamic_extents (const region *reg);
 504
 505   region_model_manager *get_manager () const { return m_mgr; }
 506   bounded_ranges_manager *get_range_manager () const
 507   {
 508     return m_mgr->get_range_manager ();
 509   }
 510
 511   void unbind_region_and_descendents (const region *reg,
 512                                       enum poison_kind pkind);
 513
 514   bool can_merge_with_p (const region_model &other_model,
 515                          const program_point &point,
 516                          region_model *out_model,
 517                          const extrinsic_state *ext_state = NULL,
 518                          const program_state *state_a = NULL,
 519                          const program_state *state_b = NULL) const;
 520
 521   tree get_fndecl_for_call (const gcall *call,
 522                             region_model_context *ctxt);
 523
 524   void get_regions_for_current_frame (auto_vec<const decl_region *> *out) const;
 525   static void append_regions_cb (const region *base_reg,
 526                                  struct append_regions_cb_data *data);
 527
 528   const svalue *get_store_value (const region *reg,
 529                                  region_model_context *ctxt) const;
 530
 531   bool region_exists_p (const region *reg) const;
 532
 533   void loop_replay_fixup (const region_model *dst_state);
 534
 535   const svalue *get_capacity (const region *reg) const;
 536
 537   const svalue *get_string_size (const svalue *sval) const;
 538   const svalue *get_string_size (const region *reg) const;
 539
 540   bool replay_call_summary (call_summary_replay &r,
 541                             const region_model &summary);
 542
 543   void maybe_complain_about_infoleak (const region *dst_reg,
 544                                       const svalue *copied_sval,
 545                                       const region *src_reg,
 546                                       region_model_context *ctxt);
 547
 548   void set_errno (const call_details &cd);
 549
 550   /* Implemented in sm-fd.cc  */
 551   void mark_as_valid_fd (const svalue *sval, region_model_context *ctxt);
 552
 553   /* Implemented in sm-malloc.cc  */
 554   void on_realloc_with_move (const call_details &cd,
 555                              const svalue *old_ptr_sval,
 556                              const svalue *new_ptr_sval);
 557
 558   /* Implemented in sm-taint.cc.  */
 559   void mark_as_tainted (const svalue *sval,
 560                         region_model_context *ctxt);
 561
 562  private:
 563   const region *get_lvalue_1 (path_var pv, region_model_context *ctxt) const;
 564   const svalue *get_rvalue_1 (path_var pv, region_model_context *ctxt) const;
 565
 566   path_var
 567   get_representative_path_var_1 (const svalue *sval,
 568                                  svalue_set *visited) const;
 569   path_var
 570   get_representative_path_var_1 (const region *reg,
 571                                  svalue_set *visited) const;
 572
 573   const known_function *get_known_function (tree fndecl) const;
 574
 575   bool add_constraint (const svalue *lhs,
 576                        enum tree_code op,
 577                        const svalue *rhs,
 578                        region_model_context *ctxt);
 579   bool add_constraints_from_binop (const svalue *outer_lhs,
 580                                    enum tree_code outer_op,
 581                                    const svalue *outer_rhs,
 582                                    bool *out,
 583                                    region_model_context *ctxt);
 584
 585   void update_for_call_superedge (const call_superedge &call_edge,
 586                                   region_model_context *ctxt);
 587   void update_for_return_superedge (const return_superedge &return_edge,
 588                                     region_model_context *ctxt);
 589   bool apply_constraints_for_gcond (const cfg_superedge &edge,
 590                                     const gcond *cond_stmt,
 591                                     region_model_context *ctxt,
 592                                     rejected_constraint **out);
 593   bool apply_constraints_for_gswitch (const switch_cfg_superedge &edge,
 594                                       const gswitch *switch_stmt,
 595                                       region_model_context *ctxt,
 596                                       rejected_constraint **out);
 597   bool apply_constraints_for_exception (const gimple *last_stmt,
 598                                         region_model_context *ctxt,
 599                                         rejected_constraint **out);
 600
 601   int poison_any_pointers_to_descendents (const region *reg,
 602                                           enum poison_kind pkind);
 603
 604   void on_top_level_param (tree param, region_model_context *ctxt);
 605
 606   bool called_from_main_p () const;
 607   const svalue *get_initial_value_for_global (const region *reg) const;
 608
 609   const svalue *check_for_poison (const svalue *sval,
 610                                   tree expr,
 611                                   region_model_context *ctxt) const;
 612   const region * get_region_for_poisoned_expr (tree expr) const;
 613
 614   void check_dynamic_size_for_taint (enum memory_space mem_space,
 615                                      const svalue *size_in_bytes,
 616                                      region_model_context *ctxt) const;
 617   void check_dynamic_size_for_floats (const svalue *size_in_bytes,
 618                                       region_model_context *ctxt) const;
 619
 620   void check_region_for_taint (const region *reg,
 621                                enum access_direction dir,
 622                                region_model_context *ctxt) const;
 623
 624   void check_for_writable_region (const region* dest_reg,
 625                                   region_model_context *ctxt) const;
 626   void check_region_access (const region *reg,
 627                             enum access_direction dir,
 628                             region_model_context *ctxt) const;
 629   void check_region_for_write (const region *dest_reg,
 630                                region_model_context *ctxt) const;
 631   void check_region_for_read (const region *src_reg,
 632                               region_model_context *ctxt) const;
 633   void check_region_size (const region *lhs_reg, const svalue *rhs_sval,
 634                           region_model_context *ctxt) const;
 635   void check_symbolic_bounds (const region *base_reg,
 636                               const svalue *sym_byte_offset,
 637                               const svalue *num_bytes_sval,
 638                               const svalue *capacity,
 639                               enum access_direction dir,
 640                               region_model_context *ctxt) const;
 641   void check_region_bounds (const region *reg, enum access_direction dir,
 642                             region_model_context *ctxt) const;
 643
 644   void check_call_args (const call_details &cd) const;
 645   void check_external_function_for_access_attr (const gcall *call,
 646                                                 tree callee_fndecl,
 647                                                 region_model_context *ctxt) const;
 648
 649   /* Storing this here to avoid passing it around everywhere.  */
 650   region_model_manager *const m_mgr;
 651
 652   store m_store;
 653
 654   constraint_manager *m_constraints; // TODO: embed, rather than dynalloc?
 655
 656   const frame_region *m_current_frame;
 657
 658   /* Map from base region to size in bytes, for tracking the sizes of
 659      dynamically-allocated regions.
 660      This is part of the region_model rather than the region to allow for
 661      memory regions to be resized (e.g. by realloc).  */
 662   dynamic_extents_t m_dynamic_extents;
 663 };
 664
 665 /* Some region_model activity could lead to warnings (e.g. attempts to use an
 666    uninitialized value).  This abstract base class encapsulates an interface
 667    for the region model to use when emitting such warnings.
 668
 669    Having this as an abstract base class allows us to support the various
 670    operations needed by program_state in the analyzer within region_model,
 671    whilst keeping them somewhat modularized.  */
 672
 673 class region_model_context
 674 {
 675  public:
 676   /* Hook for clients to store pending diagnostics.
 677      Return true if the diagnostic was stored, or false if it was deleted.  */
 678   virtual bool warn (std::unique_ptr<pending_diagnostic> d) = 0;
 679
 680   /* Hook for clients to add a note to the last previously stored
 681      pending diagnostic.  */
 682   virtual void add_note (std::unique_ptr<pending_note> pn) = 0;
 683
 684   /* Hook for clients to be notified when an SVAL that was reachable
 685      in a previous state is no longer live, so that clients can emit warnings
 686      about leaks.  */
 687   virtual void on_svalue_leak (const svalue *sval) = 0;
 688
 689   /* Hook for clients to be notified when the set of explicitly live
 690      svalues changes, so that they can purge state relating to dead
 691      svalues.  */
 692   virtual void on_liveness_change (const svalue_set &live_svalues,
 693                                    const region_model *model) = 0;
 694
 695   virtual logger *get_logger () = 0;
 696
 697   /* Hook for clients to be notified when the condition
 698      "LHS OP RHS" is added to the region model.
 699      This exists so that state machines can detect tests on edges,
 700      and use them to trigger sm-state transitions (e.g. transitions due
 701      to ptrs becoming known to be NULL or non-NULL, rather than just
 702      "unchecked") */
 703   virtual void on_condition (const svalue *lhs,
 704                              enum tree_code op,
 705                              const svalue *rhs) = 0;
 706
 707   /* Hook for clients to be notified when the condition that
 708      SVAL is within RANGES is added to the region model.
 709      Similar to on_condition, but for use when handling switch statements.
 710      RANGES is non-empty.  */
 711   virtual void on_bounded_ranges (const svalue &sval,
 712                                   const bounded_ranges &ranges) = 0;
 713
 714   /* Hooks for clients to be notified when an unknown change happens
 715      to SVAL (in response to a call to an unknown function).  */
 716   virtual void on_unknown_change (const svalue *sval, bool is_mutable) = 0;
 717
 718   /* Hooks for clients to be notified when a phi node is handled,
 719      where RHS is the pertinent argument.  */
 720   virtual void on_phi (const gphi *phi, tree rhs) = 0;
 721
 722   /* Hooks for clients to be notified when the region model doesn't
 723      know how to handle the tree code of T at LOC.  */
 724   virtual void on_unexpected_tree_code (tree t,
 725                                         const dump_location_t &loc) = 0;
 726
 727   /* Hook for clients to be notified when a function_decl escapes.  */
 728   virtual void on_escaped_function (tree fndecl) = 0;
 729
 730   virtual uncertainty_t *get_uncertainty () = 0;
 731
 732   /* Hook for clients to purge state involving SVAL.  */
 733   virtual void purge_state_involving (const svalue *sval) = 0;
 734
 735   /* Hook for clients to split state with a non-standard path.  */
 736   virtual void bifurcate (std::unique_ptr<custom_edge_info> info) = 0;
 737
 738   /* Hook for clients to terminate the standard path.  */
 739   virtual void terminate_path () = 0;
 740
 741   virtual const extrinsic_state *get_ext_state () const = 0;
 742
 743   /* Hook for clients to access the a specific state machine in
 744      any underlying program_state.  */
 745   virtual bool get_state_map_by_name (const char *name,
 746                                       sm_state_map **out_smap,
 747                                       const state_machine **out_sm,
 748                                       unsigned *out_sm_idx) = 0;
 749
 750   /* Precanned ways for clients to access specific state machines.  */
 751   bool get_fd_map (sm_state_map **out_smap,
 752                    const state_machine **out_sm,
 753                    unsigned *out_sm_idx)
 754   {
 755     return get_state_map_by_name ("file-descriptor", out_smap, out_sm,
 756                                   out_sm_idx);
 757   }
 758   bool get_malloc_map (sm_state_map **out_smap,
 759                        const state_machine **out_sm,
 760                        unsigned *out_sm_idx)
 761   {
 762     return get_state_map_by_name ("malloc", out_smap, out_sm, out_sm_idx);
 763   }
 764   bool get_taint_map (sm_state_map **out_smap,
 765                       const state_machine **out_sm,
 766                       unsigned *out_sm_idx)
 767   {
 768     return get_state_map_by_name ("taint", out_smap, out_sm, out_sm_idx);
 769   }
 770
 771   /* Get the current statement, if any.  */
 772   virtual const gimple *get_stmt () const = 0;
 773 };
 774
 775 /* A "do nothing" subclass of region_model_context.  */
 776
 777 class noop_region_model_context : public region_model_context
 778 {
 779 public:
 780   bool warn (std::unique_ptr<pending_diagnostic>) override { return false; }
 781   void add_note (std::unique_ptr<pending_note>) override;
 782   void on_svalue_leak (const svalue *) override {}
 783   void on_liveness_change (const svalue_set &,
 784                            const region_model *) override {}
 785   logger *get_logger () override { return NULL; }
 786   void on_condition (const svalue *lhs ATTRIBUTE_UNUSED,
 787                      enum tree_code op ATTRIBUTE_UNUSED,
 788                      const svalue *rhs ATTRIBUTE_UNUSED) override
 789   {
 790   }
 791   void on_bounded_ranges (const svalue &,
 792                           const bounded_ranges &) override
 793   {
 794   }
 795   void on_unknown_change (const svalue *sval ATTRIBUTE_UNUSED,
 796                           bool is_mutable ATTRIBUTE_UNUSED) override
 797   {
 798   }
 799   void on_phi (const gphi *phi ATTRIBUTE_UNUSED,
 800                tree rhs ATTRIBUTE_UNUSED) override
 801   {
 802   }
 803   void on_unexpected_tree_code (tree, const dump_location_t &) override {}
 804
 805   void on_escaped_function (tree) override {}
 806
 807   uncertainty_t *get_uncertainty () override { return NULL; }
 808
 809   void purge_state_involving (const svalue *sval ATTRIBUTE_UNUSED) override {}
 810
 811   void bifurcate (std::unique_ptr<custom_edge_info> info) override;
 812   void terminate_path () override;
 813
 814   const extrinsic_state *get_ext_state () const override { return NULL; }
 815
 816   bool get_state_map_by_name (const char *,
 817                               sm_state_map **,
 818                               const state_machine **,
 819                               unsigned *) override
 820   {
 821     return false;
 822   }
 823
 824   const gimple *get_stmt () const override { return NULL; }
 825 };
 826
 827 /* A subclass of region_model_context for determining if operations fail
 828    e.g. "can we generate a region for the lvalue of EXPR?".  */
 829
 830 class tentative_region_model_context : public noop_region_model_context
 831 {
 832 public:
 833   tentative_region_model_context () : m_num_unexpected_codes (0) {}
 834
 835   void on_unexpected_tree_code (tree, const dump_location_t &)
 836     final override
 837   {
 838     m_num_unexpected_codes++;
 839   }
 840
 841   bool had_errors_p () const { return m_num_unexpected_codes > 0; }
 842
 843 private:
 844   int m_num_unexpected_codes;
 845 };
 846
 847 /* Subclass of region_model_context that wraps another context, allowing
 848    for extra code to be added to the various hooks.  */
 849
 850 class region_model_context_decorator : public region_model_context
 851 {
 852  public:
 853   bool warn (std::unique_ptr<pending_diagnostic> d) override
 854   {
 855     return m_inner->warn (std::move (d));
 856   }
 857
 858   void add_note (std::unique_ptr<pending_note> pn) override
 859   {
 860     m_inner->add_note (std::move (pn));
 861   }
 862
 863   void on_svalue_leak (const svalue *sval) override
 864   {
 865     m_inner->on_svalue_leak (sval);
 866   }
 867
 868   void on_liveness_change (const svalue_set &live_svalues,
 869                            const region_model *model) override
 870   {
 871     m_inner->on_liveness_change (live_svalues, model);
 872   }
 873
 874   logger *get_logger () override
 875   {
 876     return m_inner->get_logger ();
 877   }
 878
 879   void on_condition (const svalue *lhs,
 880                      enum tree_code op,
 881                      const svalue *rhs) override
 882   {
 883     m_inner->on_condition (lhs, op, rhs);
 884   }
 885
 886   void on_bounded_ranges (const svalue &sval,
 887                           const bounded_ranges &ranges) override
 888   {
 889     m_inner->on_bounded_ranges (sval, ranges);
 890   }
 891
 892   void on_unknown_change (const svalue *sval, bool is_mutable) override
 893   {
 894     m_inner->on_unknown_change (sval, is_mutable);
 895   }
 896
 897   void on_phi (const gphi *phi, tree rhs) override
 898   {
 899     m_inner->on_phi (phi, rhs);
 900   }
 901
 902   void on_unexpected_tree_code (tree t,
 903                                 const dump_location_t &loc) override
 904   {
 905     m_inner->on_unexpected_tree_code (t, loc);
 906   }
 907
 908   void on_escaped_function (tree fndecl) override
 909   {
 910     m_inner->on_escaped_function (fndecl);
 911   }
 912
 913   uncertainty_t *get_uncertainty () override
 914   {
 915     return m_inner->get_uncertainty ();
 916   }
 917
 918   void purge_state_involving (const svalue *sval) override
 919   {
 920     m_inner->purge_state_involving (sval);
 921   }
 922
 923   void bifurcate (std::unique_ptr<custom_edge_info> info) override
 924   {
 925     m_inner->bifurcate (std::move (info));
 926   }
 927
 928   void terminate_path () override
 929   {
 930     m_inner->terminate_path ();
 931   }
 932
 933   const extrinsic_state *get_ext_state () const override
 934   {
 935     return m_inner->get_ext_state ();
 936   }
 937
 938   bool get_state_map_by_name (const char *name,
 939                               sm_state_map **out_smap,
 940                               const state_machine **out_sm,
 941                               unsigned *out_sm_idx) override
 942   {
 943     return m_inner->get_state_map_by_name (name, out_smap, out_sm, out_sm_idx);
 944   }
 945
 946   const gimple *get_stmt () const override
 947   {
 948     return m_inner->get_stmt ();
 949   }
 950
 951 protected:
 952   region_model_context_decorator (region_model_context *inner)
 953   : m_inner (inner)
 954   {
 955     gcc_assert (m_inner);
 956   }
 957
 958   region_model_context *m_inner;
 959 };
 960
 961 /* Subclass of region_model_context_decorator that adds a note
 962    when saving diagnostics.  */
 963
 964 class note_adding_context : public region_model_context_decorator
 965 {
 966 public:
 967   bool warn (std::unique_ptr<pending_diagnostic> d) override
 968   {
 969     if (m_inner->warn (std::move (d)))
 970       {
 971         add_note (make_note ());
 972         return true;
 973       }
 974     else
 975       return false;
 976   }
 977
 978   /* Hook to make the new note.  */
 979   virtual std::unique_ptr<pending_note> make_note () = 0;
 980
 981 protected:
 982   note_adding_context (region_model_context *inner)
 983   : region_model_context_decorator (inner)
 984   {
 985   }
 986 };
 987
 988 /* A bundle of data for use when attempting to merge two region_model
 989    instances to make a third.  */
 990
 991 struct model_merger
 992 {
 993   model_merger (const region_model *model_a,
 994                 const region_model *model_b,
 995                 const program_point &point,
 996                 region_model *merged_model,
 997                 const extrinsic_state *ext_state,
 998                 const program_state *state_a,
 999                 const program_state *state_b)
1000   : m_model_a (model_a), m_model_b (model_b),
1001     m_point (point),
1002     m_merged_model (merged_model),
1003     m_ext_state (ext_state),
1004     m_state_a (state_a), m_state_b (state_b)
1005   {
1006   }
1007
1008   void dump_to_pp (pretty_printer *pp, bool simple) const;
1009   void dump (FILE *fp, bool simple) const;
1010   void dump (bool simple) const;
1011
1012   region_model_manager *get_manager () const
1013   {
1014     return m_model_a->get_manager ();
1015   }
1016
1017   bool mergeable_svalue_p (const svalue *) const;
1018   const function_point &get_function_point () const
1019   {
1020     return m_point.get_function_point ();
1021   }
1022
1023   const region_model *m_model_a;
1024   const region_model *m_model_b;
1025   const program_point &m_point;
1026   region_model *m_merged_model;
1027
1028   const extrinsic_state *m_ext_state;
1029   const program_state *m_state_a;
1030   const program_state *m_state_b;
1031 };
1032
1033 /* A record that can (optionally) be written out when
1034    region_model::add_constraint fails.  */
1035
1036 class rejected_constraint
1037 {
1038 public:
1039   virtual ~rejected_constraint () {}
1040   virtual void dump_to_pp (pretty_printer *pp) const = 0;
1041
1042   const region_model &get_model () const { return m_model; }
1043
1044 protected:
1045   rejected_constraint (const region_model &model)
1046   : m_model (model)
1047   {}
1048
1049   region_model m_model;
1050 };
1051
1052 class rejected_op_constraint : public rejected_constraint
1053 {
1054 public:
1055   rejected_op_constraint (const region_model &model,
1056                           tree lhs, enum tree_code op, tree rhs)
1057   : rejected_constraint (model),
1058     m_lhs (lhs), m_op (op), m_rhs (rhs)
1059   {}
1060
1061   void dump_to_pp (pretty_printer *pp) const final override;
1062
1063   tree m_lhs;
1064   enum tree_code m_op;
1065   tree m_rhs;
1066 };
1067
1068 class rejected_ranges_constraint : public rejected_constraint
1069 {
1070 public:
1071   rejected_ranges_constraint (const region_model &model,
1072                               tree expr, const bounded_ranges *ranges)
1073   : rejected_constraint (model),
1074     m_expr (expr), m_ranges (ranges)
1075   {}
1076
1077   void dump_to_pp (pretty_printer *pp) const final override;
1078
1079 private:
1080   tree m_expr;
1081   const bounded_ranges *m_ranges;
1082 };
1083
1084 /* A bundle of state.  */
1085
1086 class engine
1087 {
1088 public:
1089   engine (const supergraph *sg = NULL, logger *logger = NULL);
1090   const supergraph *get_supergraph () { return m_sg; }
1091   region_model_manager *get_model_manager () { return &m_mgr; }
1092   known_function_manager *get_known_function_manager ()
1093   {
1094     return m_mgr.get_known_function_manager ();
1095   }
1096
1097   void log_stats (logger *logger) const;
1098
1099 private:
1100   const supergraph *m_sg;
1101   region_model_manager m_mgr;
1102 };
1103
1104 } // namespace ana
1105
1106 extern void debug (const region_model &rmodel);
1107
1108 namespace ana {
1109
1110 #if CHECKING_P
1111
1112 namespace selftest {
1113
1114 using namespace ::selftest;
1115
1116 /* An implementation of region_model_context for use in selftests, which
1117    stores any pending_diagnostic instances passed to it.  */
1118
1119 class test_region_model_context : public noop_region_model_context
1120 {
1121 public:
1122   bool warn (std::unique_ptr<pending_diagnostic> d) final override
1123   {
1124     m_diagnostics.safe_push (d.release ());
1125     return true;
1126   }
1127
1128   unsigned get_num_diagnostics () const { return m_diagnostics.length (); }
1129
1130   void on_unexpected_tree_code (tree t, const dump_location_t &)
1131     final override
1132   {
1133     internal_error ("unhandled tree code: %qs",
1134                     get_tree_code_name (TREE_CODE (t)));
1135   }
1136
1137 private:
1138   /* Implicitly delete any diagnostics in the dtor.  */
1139   auto_delete_vec<pending_diagnostic> m_diagnostics;
1140 };
1141
1142 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1143    Verify that MODEL remains satisfiable.  */
1144
1145 #define ADD_SAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
1146   SELFTEST_BEGIN_STMT                                   \
1147     bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL);     \
1148     ASSERT_TRUE (sat);                                  \
1149   SELFTEST_END_STMT
1150
1151 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
1152    Verify that the result is not satisfiable.  */
1153
1154 #define ADD_UNSAT_CONSTRAINT(MODEL, LHS, OP, RHS)       \
1155   SELFTEST_BEGIN_STMT                                   \
1156     bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL);     \
1157     ASSERT_FALSE (sat);                         \
1158   SELFTEST_END_STMT
1159
1160 /* Implementation detail of the ASSERT_CONDITION_* macros.  */
1161
1162 void assert_condition (const location &loc,
1163                        region_model &model,
1164                        const svalue *lhs, tree_code op, const svalue *rhs,
1165                        tristate expected);
1166
1167 void assert_condition (const location &loc,
1168                        region_model &model,
1169                        tree lhs, tree_code op, tree rhs,
1170                        tristate expected);
1171
1172 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1173    as "true".  */
1174
1175 #define ASSERT_CONDITION_TRUE(REGION_MODEL, LHS, OP, RHS) \
1176   SELFTEST_BEGIN_STMT                                                   \
1177   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
1178                     tristate (tristate::TS_TRUE));              \
1179   SELFTEST_END_STMT
1180
1181 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1182    as "false".  */
1183
1184 #define ASSERT_CONDITION_FALSE(REGION_MODEL, LHS, OP, RHS) \
1185   SELFTEST_BEGIN_STMT                                                   \
1186   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
1187                     tristate (tristate::TS_FALSE));             \
1188   SELFTEST_END_STMT
1189
1190 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
1191    as "unknown".  */
1192
1193 #define ASSERT_CONDITION_UNKNOWN(REGION_MODEL, LHS, OP, RHS) \
1194   SELFTEST_BEGIN_STMT                                                   \
1195   assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,      \
1196                     tristate (tristate::TS_UNKNOWN));           \
1197   SELFTEST_END_STMT
1198
1199 } /* end of namespace selftest.  */
1200
1201 #endif /* #if CHECKING_P */
1202
1203 } // namespace ana
1204
1205 #endif /* GCC_ANALYZER_REGION_MODEL_H */