gdb/addrmap.h

   1 /* addrmap.h --- interface to address map data structure.
   2
   3    Copyright (C) 2007-2024 Free Software Foundation, Inc.
   4
   5    This file is part of GDB.
   6
   7    This program is free software; you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 3 of the License, or
  10    (at your option) any later version.
  11
  12    This program is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  19
  20 #ifndef ADDRMAP_H
  21 #define ADDRMAP_H
  22
  23 #include "gdbsupport/function-view.h"
  24 #include "gdbsupport/gdb_obstack.h"
  25 #include "splay-tree.h"
  26
  27 /* An address map is essentially a table mapping CORE_ADDRs onto GDB
  28    data structures, like blocks, symtabs, partial symtabs, and so on.
  29    An address map uses memory proportional to the number of
  30    transitions in the map, where a CORE_ADDR N is mapped to one
  31    object, and N+1 is mapped to a different object.
  32
  33    Address maps come in two flavors: fixed, and mutable.  Mutable
  34    address maps consume more memory, but can be changed and extended.
  35    A fixed address map, once constructed (from a mutable address map),
  36    can't be edited.  */
  37
  38 /* The type of a function used to iterate over the map.
  39    OBJ is NULL for unmapped regions.  */
  40 using addrmap_foreach_fn
  41   = gdb::function_view<int (CORE_ADDR start_addr, void *obj)>;
  42 using addrmap_foreach_const_fn
  43   = gdb::function_view<int (CORE_ADDR start_addr, const void *obj)>;
  44
  45 /* The base class for addrmaps.  */
  46 struct addrmap
  47 {
  48   /* Return the object associated with ADDR in MAP.  */
  49   const void *find (CORE_ADDR addr) const
  50   { return this->do_find (addr); }
  51
  52   void *find (CORE_ADDR addr)
  53   { return this->do_find (addr); }
  54
  55   /* Relocate all the addresses in MAP by OFFSET.  (This can be applied
  56      to either mutable or immutable maps.)  */
  57   virtual void relocate (CORE_ADDR offset) = 0;
  58
  59   /* Call FN for every address in MAP, following an in-order traversal.
  60      If FN ever returns a non-zero value, the iteration ceases
  61      immediately, and the value is returned.  Otherwise, this function
  62      returns 0.  */
  63   int foreach (addrmap_foreach_const_fn fn) const
  64   { return this->do_foreach (fn); }
  65
  66   int foreach (addrmap_foreach_fn fn)
  67   { return this->do_foreach (fn); }
  68
  69
  70 protected:
  71   ~addrmap () = default;
  72
  73 private:
  74   /* Worker for find, implemented by sub-classes.  */
  75   virtual void *do_find (CORE_ADDR addr) const = 0;
  76
  77   /* Worker for foreach, implemented by sub-classes.  */
  78   virtual int do_foreach (addrmap_foreach_fn fn) const = 0;
  79 };
  80
  81 struct addrmap_mutable;
  82
  83 /* Fixed address maps.  */
  84 struct addrmap_fixed final : public addrmap,
  85                              public allocate_on_obstack<addrmap_fixed>
  86 {
  87 public:
  88
  89   addrmap_fixed (struct obstack *obstack, const addrmap_mutable *mut);
  90   DISABLE_COPY_AND_ASSIGN (addrmap_fixed);
  91
  92   /* It's fine to use the default move operators, because this addrmap
  93      does not own the storage for the elements.  */
  94   addrmap_fixed (addrmap_fixed &&other) = default;
  95   addrmap_fixed &operator= (addrmap_fixed &&) = default;
  96
  97   void relocate (CORE_ADDR offset) override;
  98
  99 private:
 100   void *do_find (CORE_ADDR addr) const override;
 101   int do_foreach (addrmap_foreach_fn fn) const override;
 102
 103   /* A transition: a point in an address map where the value changes.
 104      The map maps ADDR to VALUE, but if ADDR > 0, it maps ADDR-1 to
 105      something else.  */
 106   struct addrmap_transition
 107   {
 108     CORE_ADDR addr;
 109     void *value;
 110   };
 111
 112   /* The number of transitions in TRANSITIONS.  */
 113   size_t num_transitions;
 114
 115   /* An array of transitions, sorted by address.  For every point in
 116      the map where either ADDR == 0 or ADDR is mapped to one value and
 117      ADDR - 1 is mapped to something different, we have an entry here
 118      containing ADDR and VALUE.  (Note that this means we always have
 119      an entry for address 0).  */
 120   struct addrmap_transition *transitions;
 121 };
 122
 123 /* Mutable address maps.  */
 124
 125 struct addrmap_mutable final : public addrmap
 126 {
 127 public:
 128
 129   addrmap_mutable ();
 130   ~addrmap_mutable ();
 131   DISABLE_COPY_AND_ASSIGN (addrmap_mutable);
 132
 133   addrmap_mutable (addrmap_mutable &&other)
 134     : tree (other.tree)
 135   {
 136     other.tree = nullptr;
 137   }
 138
 139   addrmap_mutable &operator= (addrmap_mutable &&other)
 140   {
 141     std::swap (tree, other.tree);
 142     return *this;
 143   }
 144
 145   /* In the mutable address map MAP, associate the addresses from START
 146      to END_INCLUSIVE that are currently associated with NULL with OBJ
 147      instead.  Addresses mapped to an object other than NULL are left
 148      unchanged.
 149
 150      As the name suggests, END_INCLUSIVE is also mapped to OBJ.  This
 151      convention is unusual, but it allows callers to accurately specify
 152      ranges that abut the top of the address space, and ranges that
 153      cover the entire address space.
 154
 155      This operation seems a bit complicated for a primitive: if it's
 156      needed, why not just have a simpler primitive operation that sets a
 157      range to a value, wiping out whatever was there before, and then
 158      let the caller construct more complicated operations from that,
 159      along with some others for traversal?
 160
 161      It turns out this is the mutation operation we want to use all the
 162      time, at least for now.  Our immediate use for address maps is to
 163      represent lexical blocks whose address ranges are not contiguous.
 164      We walk the tree of lexical blocks present in the debug info, and
 165      only create 'struct block' objects after we've traversed all a
 166      block's children.  If a lexical block declares no local variables
 167      (and isn't the lexical block for a function's body), we omit it
 168      from GDB's data structures entirely.
 169
 170      However, this means that we don't decide to create a block (and
 171      thus record it in the address map) until after we've traversed its
 172      children.  If we do decide to create the block, we do so at a time
 173      when all its children have already been recorded in the map.  So
 174      this operation --- change only those addresses left unset --- is
 175      actually the operation we want to use every time.
 176
 177      It seems simpler to let the code which operates on the
 178      representation directly deal with the hair of implementing these
 179      semantics than to provide an interface which allows it to be
 180      implemented efficiently, but doesn't reveal too much of the
 181      representation.  */
 182   void set_empty (CORE_ADDR start, CORE_ADDR end_inclusive,
 183                   void *obj);
 184   void relocate (CORE_ADDR offset) override;
 185
 186 private:
 187   void *do_find (CORE_ADDR addr) const override;
 188   int do_foreach (addrmap_foreach_fn fn) const override;
 189
 190   /* A splay tree, with a node for each transition; there is a
 191      transition at address T if T-1 and T map to different objects.
 192
 193      Any addresses below the first node map to NULL.  (Unlike
 194      fixed maps, we have no entry at (CORE_ADDR) 0; it doesn't
 195      simplify enough.)
 196
 197      The last region is assumed to end at CORE_ADDR_MAX.
 198
 199      Since we can't know whether CORE_ADDR is larger or smaller than
 200      splay_tree_key (unsigned long) --- I think both are possible,
 201      given all combinations of 32- and 64-bit hosts and targets ---
 202      our keys are pointers to CORE_ADDR values.  Since the splay tree
 203      library doesn't pass any closure pointer to the key free
 204      function, we can't keep a freelist for keys.  Since mutable
 205      addrmaps are only used temporarily right now, we just leak keys
 206      from deleted nodes; they'll be freed when the obstack is freed.  */
 207   splay_tree tree;
 208
 209   /* Various helper methods.  */
 210   splay_tree_key allocate_key (CORE_ADDR addr);
 211   void force_transition (CORE_ADDR addr);
 212   splay_tree_node splay_tree_lookup (CORE_ADDR addr) const;
 213   splay_tree_node splay_tree_predecessor (CORE_ADDR addr) const;
 214   splay_tree_node splay_tree_successor (CORE_ADDR addr);
 215   void splay_tree_remove (CORE_ADDR addr);
 216   void splay_tree_insert (CORE_ADDR key, void *value);
 217 };
 218
 219
 220 /* Dump the addrmap to OUTFILE.  If PAYLOAD is non-NULL, only dump any
 221    components that map to PAYLOAD.  (If PAYLOAD is NULL, the entire
 222    map is dumped.)  If ANNOTATE_VALUE is non-nullptr, call it for each
 223    value.  */
 224
 225 void addrmap_dump (struct addrmap *map, struct ui_file *outfile,
 226                    void *payload,
 227                    gdb::function_view<void (struct ui_file *outfile,
 228                                             const void *value)>
 229                      annotate_value = nullptr);
 230
 231 #endif /* ADDRMAP_H */