gdb/addrmap.h

   1 /* addrmap.h --- interface to address map data structure.
   2
   3    Copyright (C) 2007-2022 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 "splay-tree.h"
  24 #include "gdbsupport/function-view.h"
  25
  26 /* An address map is essentially a table mapping CORE_ADDRs onto GDB
  27    data structures, like blocks, symtabs, partial symtabs, and so on.
  28    An address map uses memory proportional to the number of
  29    transitions in the map, where a CORE_ADDR N is mapped to one
  30    object, and N+1 is mapped to a different object.
  31
  32    Address maps come in two flavors: fixed, and mutable.  Mutable
  33    address maps consume more memory, but can be changed and extended.
  34    A fixed address map, once constructed (from a mutable address map),
  35    can't be edited.  */
  36
  37 /* The type of a function used to iterate over the map.
  38    OBJ is NULL for unmapped regions.  */
  39 typedef gdb::function_view<int (CORE_ADDR start_addr, void *obj)>
  40      addrmap_foreach_fn;
  41
  42 /* The base class for addrmaps.  */
  43 struct addrmap
  44 {
  45   virtual ~addrmap () = default;
  46
  47   /* In the mutable address map MAP, associate the addresses from START
  48      to END_INCLUSIVE that are currently associated with NULL with OBJ
  49      instead.  Addresses mapped to an object other than NULL are left
  50      unchanged.
  51
  52      As the name suggests, END_INCLUSIVE is also mapped to OBJ.  This
  53      convention is unusual, but it allows callers to accurately specify
  54      ranges that abut the top of the address space, and ranges that
  55      cover the entire address space.
  56
  57      This operation seems a bit complicated for a primitive: if it's
  58      needed, why not just have a simpler primitive operation that sets a
  59      range to a value, wiping out whatever was there before, and then
  60      let the caller construct more complicated operations from that,
  61      along with some others for traversal?
  62
  63      It turns out this is the mutation operation we want to use all the
  64      time, at least for now.  Our immediate use for address maps is to
  65      represent lexical blocks whose address ranges are not contiguous.
  66      We walk the tree of lexical blocks present in the debug info, and
  67      only create 'struct block' objects after we've traversed all a
  68      block's children.  If a lexical block declares no local variables
  69      (and isn't the lexical block for a function's body), we omit it
  70      from GDB's data structures entirely.
  71
  72      However, this means that we don't decide to create a block (and
  73      thus record it in the address map) until after we've traversed its
  74      children.  If we do decide to create the block, we do so at a time
  75      when all its children have already been recorded in the map.  So
  76      this operation --- change only those addresses left unset --- is
  77      actually the operation we want to use every time.
  78
  79      It seems simpler to let the code which operates on the
  80      representation directly deal with the hair of implementing these
  81      semantics than to provide an interface which allows it to be
  82      implemented efficiently, but doesn't reveal too much of the
  83      representation.  */
  84   virtual void set_empty (CORE_ADDR start, CORE_ADDR end_inclusive,
  85                           void *obj) = 0;
  86
  87   /* Return the object associated with ADDR in MAP.  */
  88   virtual void *find (CORE_ADDR addr) const = 0;
  89
  90   /* Relocate all the addresses in MAP by OFFSET.  (This can be applied
  91      to either mutable or immutable maps.)  */
  92   virtual void relocate (CORE_ADDR offset) = 0;
  93
  94   /* Call FN for every address in MAP, following an in-order traversal.
  95      If FN ever returns a non-zero value, the iteration ceases
  96      immediately, and the value is returned.  Otherwise, this function
  97      returns 0.  */
  98   virtual int foreach (addrmap_foreach_fn fn) = 0;
  99 };
 100
 101 struct addrmap_mutable;
 102
 103 /* Fixed address maps.  */
 104 struct addrmap_fixed : public addrmap,
 105                        public allocate_on_obstack
 106 {
 107 public:
 108
 109   addrmap_fixed (struct obstack *obstack, addrmap_mutable *mut);
 110   DISABLE_COPY_AND_ASSIGN (addrmap_fixed);
 111
 112   void set_empty (CORE_ADDR start, CORE_ADDR end_inclusive,
 113                   void *obj) override;
 114   void *find (CORE_ADDR addr) const override;
 115   void relocate (CORE_ADDR offset) override;
 116   int foreach (addrmap_foreach_fn fn) override;
 117
 118 private:
 119
 120   /* A transition: a point in an address map where the value changes.
 121      The map maps ADDR to VALUE, but if ADDR > 0, it maps ADDR-1 to
 122      something else.  */
 123   struct addrmap_transition
 124   {
 125     CORE_ADDR addr;
 126     void *value;
 127   };
 128
 129   /* The number of transitions in TRANSITIONS.  */
 130   size_t num_transitions;
 131
 132   /* An array of transitions, sorted by address.  For every point in
 133      the map where either ADDR == 0 or ADDR is mapped to one value and
 134      ADDR - 1 is mapped to something different, we have an entry here
 135      containing ADDR and VALUE.  (Note that this means we always have
 136      an entry for address 0).  */
 137   struct addrmap_transition *transitions;
 138 };
 139
 140 /* Mutable address maps.  */
 141
 142 struct addrmap_mutable : public addrmap
 143 {
 144 public:
 145
 146   addrmap_mutable ();
 147   ~addrmap_mutable ();
 148   DISABLE_COPY_AND_ASSIGN (addrmap_mutable);
 149
 150   void set_empty (CORE_ADDR start, CORE_ADDR end_inclusive,
 151                   void *obj) override;
 152   void *find (CORE_ADDR addr) const override;
 153   void relocate (CORE_ADDR offset) override;
 154   int foreach (addrmap_foreach_fn fn) override;
 155
 156 private:
 157
 158   /* A splay tree, with a node for each transition; there is a
 159      transition at address T if T-1 and T map to different objects.
 160
 161      Any addresses below the first node map to NULL.  (Unlike
 162      fixed maps, we have no entry at (CORE_ADDR) 0; it doesn't
 163      simplify enough.)
 164
 165      The last region is assumed to end at CORE_ADDR_MAX.
 166
 167      Since we can't know whether CORE_ADDR is larger or smaller than
 168      splay_tree_key (unsigned long) --- I think both are possible,
 169      given all combinations of 32- and 64-bit hosts and targets ---
 170      our keys are pointers to CORE_ADDR values.  Since the splay tree
 171      library doesn't pass any closure pointer to the key free
 172      function, we can't keep a freelist for keys.  Since mutable
 173      addrmaps are only used temporarily right now, we just leak keys
 174      from deleted nodes; they'll be freed when the obstack is freed.  */
 175   splay_tree tree;
 176
 177   /* Various helper methods.  */
 178   splay_tree_key allocate_key (CORE_ADDR addr);
 179   void force_transition (CORE_ADDR addr);
 180   splay_tree_node splay_tree_lookup (CORE_ADDR addr) const;
 181   splay_tree_node splay_tree_predecessor (CORE_ADDR addr) const;
 182   splay_tree_node splay_tree_successor (CORE_ADDR addr);
 183   void splay_tree_remove (CORE_ADDR addr);
 184   void splay_tree_insert (CORE_ADDR key, void *value);
 185 };
 186
 187
 188 /* Dump the addrmap to OUTFILE.  If PAYLOAD is non-NULL, only dump any
 189    components that map to PAYLOAD.  (If PAYLOAD is NULL, the entire
 190    map is dumped.)  */
 191 void addrmap_dump (struct addrmap *map, struct ui_file *outfile,
 192                    void *payload);
 193
 194 #endif /* ADDRMAP_H */