gcc/analyzer/region-model.h

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