gcc/analyzer/region-model.h

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