gdb/addrmap.c - gdb

Global variables defined

Data types defined

Functions defined

Source code

  1. /* addrmap.c --- implementation of address map data structure.

  3.    Copyright (C) 2007-2015 Free Software Foundation, Inc.

  5.    This file is part of GDB.

  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.

  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.

  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/>.  */

  20. #include "defs.h"
  21. #include "splay-tree.h"
  22. #include "gdb_obstack.h"
  23. #include "addrmap.h"


  26. /* The "abstract class".  */

  28. /* Functions implementing the addrmap functions for a particular
  29.    implementation.  */
  30. ‌struct addrmap_funcs
  31. {
  32.   void (*set_empty) (struct addrmap *this,
  33.                      CORE_ADDR start, CORE_ADDR end_inclusive,
  34.                      void *obj);
  35.   void *(*find) (struct addrmap *this, CORE_ADDR addr);
  36.   struct addrmap *(*create_fixed) (struct addrmap *this,
  37.                                    struct obstack *obstack);
  38.   void (*relocate) (struct addrmap *this, CORE_ADDR offset);
  39.   int (*foreach) (struct addrmap *this, addrmap_foreach_fn fn, void *data);
  40. };


  43. ‌struct addrmap
  44. {
  45.   const struct addrmap_funcs *funcs;
  46. };


  49. void
  50. ‌addrmap_set_empty (struct addrmap *map,
  51.                    CORE_ADDR start, CORE_ADDR end_inclusive,
  52.                    void *obj)
  53. {
  54.   map->funcs->set_empty (map, start, end_inclusive, obj);
  55. }


  58. void *
  59. ‌addrmap_find (struct addrmap *map, CORE_ADDR addr)
  60. {
  61.   return map->funcs->find (map, addr);
  62. }


  65. struct addrmap *
  66. ‌addrmap_create_fixed (struct addrmap *original, struct obstack *obstack)
  67. {
  68.   return original->funcs->create_fixed (original, obstack);
  69. }


  72. /* Relocate all the addresses in MAP by OFFSET.  (This can be applied
  73.    to either mutable or immutable maps.)  */
  74. void
  75. ‌addrmap_relocate (struct addrmap *map, CORE_ADDR offset)
  76. {
  77.   map->funcs->relocate (map, offset);
  78. }


  81. int
  82. ‌addrmap_foreach (struct addrmap *map, addrmap_foreach_fn fn, void *data)
  83. {
  84.   return map->funcs->foreach (map, fn, data);
  85. }

  87. /* Fixed address maps.  */

  89. /* A transition: a point in an address map where the value changes.
  90.    The map maps ADDR to VALUE, but if ADDR > 0, it maps ADDR-1 to
  91.    something else.  */
  92. ‌struct addrmap_transition
  93. {
  94.   CORE_ADDR addr;
  95.   void *value;
  96. };


  99. ‌struct addrmap_fixed
  100. {
  101.   struct addrmap addrmap;

  103.   /* The number of transitions in TRANSITIONS.  */
  104.   size_t num_transitions;

  106.   /* An array of transitions, sorted by address.  For every point in
  107.      the map where either ADDR == 0 or ADDR is mapped to one value and
  108.      ADDR - 1 is mapped to something different, we have an entry here
  109.      containing ADDR and VALUE.  (Note that this means we always have
  110.      an entry for address 0).  */
  111.   struct addrmap_transition transitions[1];
  112. };


  115. static void
  116. ‌addrmap_fixed_set_empty (struct addrmap *this,
  117.                    CORE_ADDR start, CORE_ADDR end_inclusive,
  118.                    void *obj)
  119. {
  120.   internal_error (__FILE__, __LINE__,
  121.                   "addrmap_fixed_set_empty: "
  122.                   "fixed addrmaps can't be changed\n");
  123. }


  126. static void *
  127. ‌addrmap_fixed_find (struct addrmap *this, CORE_ADDR addr)
  128. {
  129.   struct addrmap_fixed *map = (struct addrmap_fixed *) this;
  130.   struct addrmap_transition *bottom = &map->transitions[0];
  131.   struct addrmap_transition *top = &map->transitions[map->num_transitions - 1];

  133.   while (bottom < top)
  134.     {
  135.       /* This needs to round towards top, or else when top = bottom +
  136.          1 (i.e., two entries are under consideration), then mid ==
  137.          bottom, and then we may not narrow the range when (mid->addr
  138.          < addr).  */
  139.       struct addrmap_transition *mid = top - (top - bottom) / 2;

  141.       if (mid->addr == addr)
  142.         {
  143.           bottom = mid;
  144.           break;
  145.         }
  146.       else if (mid->addr < addr)
  147.         /* We don't eliminate mid itself here, since each transition
  148.            covers all subsequent addresses until the next.  This is why
  149.            we must round up in computing the midpoint.  */
  150.         bottom = mid;
  151.       else
  152.         top = mid - 1;
  153.     }

  155.   return bottom->value;
  156. }


  159. static struct addrmap *
  160. ‌addrmap_fixed_create_fixed (struct addrmap *this, struct obstack *obstack)
  161. {
  162.   internal_error (__FILE__, __LINE__,
  163.                   _("addrmap_create_fixed is not implemented yet "
  164.                     "for fixed addrmaps"));
  165. }


  168. static void
  169. ‌addrmap_fixed_relocate (struct addrmap *this, CORE_ADDR offset)
  170. {
  171.   struct addrmap_fixed *map = (struct addrmap_fixed *) this;
  172.   size_t i;

  174.   for (i = 0; i < map->num_transitions; i++)
  175.     map->transitions[i].addr += offset;
  176. }


  179. static int
  180. ‌addrmap_fixed_foreach (struct addrmap *this, addrmap_foreach_fn fn,
  181.                        void *data)
  182. {
  183.   struct addrmap_fixed *map = (struct addrmap_fixed *) this;
  184.   size_t i;

  186.   for (i = 0; i < map->num_transitions; i++)
  187.     {
  188.       int res = fn (data, map->transitions[i].addr, map->transitions[i].value);

  190.       if (res != 0)
  191.         return res;
  192.     }

  194.   return 0;
  195. }


  198. ‌static const struct addrmap_funcs addrmap_fixed_funcs =
  199. {
  200.   addrmap_fixed_set_empty,
  201.   addrmap_fixed_find,
  202.   addrmap_fixed_create_fixed,
  203.   addrmap_fixed_relocate,
  204.   addrmap_fixed_foreach
  205. };



  209. /* Mutable address maps.  */

  211. ‌struct addrmap_mutable
  212. {
  213.   struct addrmap addrmap;

  215.   /* The obstack to use for allocations for this map.  */
  216.   struct obstack *obstack;

  218.   /* A splay tree, with a node for each transition; there is a
  219.      transition at address T if T-1 and T map to different objects.

  221.      Any addresses below the first node map to NULL.  (Unlike
  222.      fixed maps, we have no entry at (CORE_ADDR) 0; it doesn't
  223.      simplify enough.)

  225.      The last region is assumed to end at CORE_ADDR_MAX.

  227.      Since we can't know whether CORE_ADDR is larger or smaller than
  228.      splay_tree_key (unsigned long) --- I think both are possible,
  229.      given all combinations of 32- and 64-bit hosts and targets ---
  230.      our keys are pointers to CORE_ADDR values.  Since the splay tree
  231.      library doesn't pass any closure pointer to the key free
  232.      function, we can't keep a freelist for keys.  Since mutable
  233.      addrmaps are only used temporarily right now, we just leak keys
  234.      from deleted nodes; they'll be freed when the obstack is freed.  */
  235.   splay_tree tree;

  237.   /* A freelist for splay tree nodes, allocated on obstack, and
  238.      chained together by their 'right' pointers.  */
  239.   splay_tree_node free_nodes;
  240. };


  243. /* Allocate a copy of CORE_ADDR in MAP's obstack.  */
  244. static splay_tree_key
  245. ‌allocate_key (struct addrmap_mutable *map, CORE_ADDR addr)
  246. {
  247.   CORE_ADDR *key = obstack_alloc (map->obstack, sizeof (*key));

  249.   *key = addr;
  250.   return (splay_tree_key) key;
  251. }


  254. /* Type-correct wrappers for splay tree access.  */
  255. static splay_tree_node
  256. ‌addrmap_splay_tree_lookup (struct addrmap_mutable *map, CORE_ADDR addr)
  257. {
  258.   return splay_tree_lookup (map->tree, (splay_tree_key) &addr);
  259. }


  262. static splay_tree_node
  263. ‌addrmap_splay_tree_predecessor (struct addrmap_mutable *map, CORE_ADDR addr)
  264. {
  265.   return splay_tree_predecessor (map->tree, (splay_tree_key) &addr);
  266. }


  269. static splay_tree_node
  270. ‌addrmap_splay_tree_successor (struct addrmap_mutable *map, CORE_ADDR addr)
  271. {
  272.   return splay_tree_successor (map->tree, (splay_tree_key) &addr);
  273. }


  276. static void
  277. ‌addrmap_splay_tree_remove (struct addrmap_mutable *map, CORE_ADDR addr)
  278. {
  279.   splay_tree_remove (map->tree, (splay_tree_key) &addr);
  280. }


  283. static CORE_ADDR
  284. ‌addrmap_node_key (splay_tree_node node)
  285. {
  286.   return * (CORE_ADDR *) node->key;
  287. }


  290. static void *
  291. ‌addrmap_node_value (splay_tree_node node)
  292. {
  293.   return (void *) node->value;
  294. }


  297. static void
  298. ‌addrmap_node_set_value (splay_tree_node node, void *value)
  299. {
  300.   node->value = (splay_tree_value) value;
  301. }


  304. static void
  305. ‌addrmap_splay_tree_insert (struct addrmap_mutable *map,
  306.                            CORE_ADDR key, void *value)
  307. {
  308.   splay_tree_insert (map->tree,
  309.                      allocate_key (map, key),
  310.                      (splay_tree_value) value);
  311. }


  314. /* Without changing the mapping of any address, ensure that there is a
  315.    tree node at ADDR, even if it would represent a "transition" from
  316.    one value to the same value.  */
  317. static void
  318. ‌force_transition (struct addrmap_mutable *this, CORE_ADDR addr)
  319. {
  320.   splay_tree_node n
  321.     = addrmap_splay_tree_lookup (this, addr);

  323.   if (! n)
  324.     {
  325.       n = addrmap_splay_tree_predecessor (this, addr);
  326.       addrmap_splay_tree_insert (this, addr,
  327.                                  n ? addrmap_node_value (n) : NULL);
  328.     }
  329. }


  332. static void
  333. ‌addrmap_mutable_set_empty (struct addrmap *this,
  334.                            CORE_ADDR start, CORE_ADDR end_inclusive,
  335.                            void *obj)
  336. {
  337.   struct addrmap_mutable *map = (struct addrmap_mutable *) this;
  338.   splay_tree_node n, next;
  339.   void *prior_value;

  341.   /* If we're being asked to set all empty portions of the given
  342.      address range to empty, then probably the caller is confused.
  343.      (If that turns out to be useful in some cases, then we can change
  344.      this to simply return, since overriding NULL with NULL is a
  345.      no-op.)  */
  346.   gdb_assert (obj);

  348.   /* We take a two-pass approach, for simplicity.
  349.      - Establish transitions where we think we might need them.
  350.      - First pass: change all NULL regions to OBJ.
  351.      - Second pass: remove any unnecessary transitions.  */

  353.   /* Establish transitions at the start and end.  */
  354.   force_transition (map, start);
  355.   if (end_inclusive < CORE_ADDR_MAX)
  356.     force_transition (map, end_inclusive + 1);

  358.   /* Walk the area, changing all NULL regions to OBJ.  */
  359.   for (n = addrmap_splay_tree_lookup (map, start), gdb_assert (n);
  360.        n && addrmap_node_key (n) <= end_inclusive;
  361.        n = addrmap_splay_tree_successor (map, addrmap_node_key (n)))
  362.     {
  363.       if (! addrmap_node_value (n))
  364.         addrmap_node_set_value (n, obj);
  365.     }

  367.   /* Walk the area again, removing transitions from any value to
  368.      itself.  Be sure to visit both the transitions we forced
  369.      above.  */
  370.   n = addrmap_splay_tree_predecessor (map, start);
  371.   prior_value = n ? addrmap_node_value (n) : NULL;
  372.   for (n = addrmap_splay_tree_lookup (map, start), gdb_assert (n);
  373.        n && (end_inclusive == CORE_ADDR_MAX
  374.              || addrmap_node_key (n) <= end_inclusive + 1);
  375.        n = next)
  376.     {
  377.       next = addrmap_splay_tree_successor (map, addrmap_node_key (n));
  378.       if (addrmap_node_value (n) == prior_value)
  379.         addrmap_splay_tree_remove (map, addrmap_node_key (n));
  380.       else
  381.         prior_value = addrmap_node_value (n);
  382.     }
  383. }


  386. static void *
  387. ‌addrmap_mutable_find (struct addrmap *this, CORE_ADDR addr)
  388. {
  389.   /* Not needed yet.  */
  390.   internal_error (__FILE__, __LINE__,
  391.                   _("addrmap_find is not implemented yet "
  392.                     "for mutable addrmaps"));
  393. }


  396. /* A function to pass to splay_tree_foreach to count the number of nodes
  397.    in the tree.  */
  398. static int
  399. ‌splay_foreach_count (splay_tree_node n, void *closure)
  400. {
  401.   size_t *count = (size_t *) closure;

  403.   (*count)++;
  404.   return 0;
  405. }


  408. /* A function to pass to splay_tree_foreach to copy entries into a
  409.    fixed address map.  */
  410. static int
  411. ‌splay_foreach_copy (splay_tree_node n, void *closure)
  412. {
  413.   struct addrmap_fixed *fixed = (struct addrmap_fixed *) closure;
  414.   struct addrmap_transition *t = &fixed->transitions[fixed->num_transitions];

  416.   t->addr = addrmap_node_key (n);
  417.   t->value = addrmap_node_value (n);
  418.   fixed->num_transitions++;

  420.   return 0;
  421. }


  424. static struct addrmap *
  425. ‌addrmap_mutable_create_fixed (struct addrmap *this, struct obstack *obstack)
  426. {
  427.   struct addrmap_mutable *mutable = (struct addrmap_mutable *) this;
  428.   struct addrmap_fixed *fixed;
  429.   size_t num_transitions;

  431.   /* Count the number of transitions in the tree.  */
  432.   num_transitions = 0;
  433.   splay_tree_foreach (mutable->tree, splay_foreach_count, &num_transitions);

  435.   /* Include an extra entry for the transition at zero (which fixed
  436.      maps have, but mutable maps do not.)  */
  437.   num_transitions++;

  439.   fixed = obstack_alloc (obstack,
  440.                          (sizeof (*fixed)
  441.                           + (num_transitions
  442.                              * sizeof (fixed->transitions[0]))));
  443.   fixed->addrmap.funcs = &addrmap_fixed_funcs;
  444.   fixed->num_transitions = 1;
  445.   fixed->transitions[0].addr = 0;
  446.   fixed->transitions[0].value = NULL;

  448.   /* Copy all entries from the splay tree to the array, in order
  449.      of increasing address.  */
  450.   splay_tree_foreach (mutable->tree, splay_foreach_copy, fixed);

  452.   /* We should have filled the array.  */
  453.   gdb_assert (fixed->num_transitions == num_transitions);

  455.   return (struct addrmap *) fixed;
  456. }


  459. static void
  460. ‌addrmap_mutable_relocate (struct addrmap *this, CORE_ADDR offset)
  461. {
  462.   /* Not needed yet.  */
  463.   internal_error (__FILE__, __LINE__,
  464.                   _("addrmap_relocate is not implemented yet "
  465.                     "for mutable addrmaps"));
  466. }


  469. /* Struct to map addrmap's foreach function to splay_tree's version.  */
  470. ‌struct mutable_foreach_data
  471. {
  472.   addrmap_foreach_fn fn;
  473.   void *data;
  474. };


  477. /* This is a splay_tree_foreach_fn.  */

  479. static int
  480. ‌addrmap_mutable_foreach_worker (splay_tree_node node, void *data)
  481. {
  482.   struct mutable_foreach_data *foreach_data = data;

  484.   return foreach_data->fn (foreach_data->data,
  485.                            addrmap_node_key (node),
  486.                            addrmap_node_value (node));
  487. }


  490. static int
  491. ‌addrmap_mutable_foreach (struct addrmap *this, addrmap_foreach_fn fn,
  492.                          void *data)
  493. {
  494.   struct addrmap_mutable *mutable = (struct addrmap_mutable *) this;
  495.   struct mutable_foreach_data foreach_data;

  497.   foreach_data.fn = fn;
  498.   foreach_data.data = data;
  499.   return splay_tree_foreach (mutable->tree, addrmap_mutable_foreach_worker,
  500.                              &foreach_data);
  501. }


  504. ‌static const struct addrmap_funcs addrmap_mutable_funcs =
  505. {
  506.   addrmap_mutable_set_empty,
  507.   addrmap_mutable_find,
  508.   addrmap_mutable_create_fixed,
  509.   addrmap_mutable_relocate,
  510.   addrmap_mutable_foreach
  511. };


  514. static void *
  515. ‌splay_obstack_alloc (int size, void *closure)
  516. {
  517.   struct addrmap_mutable *map = closure;
  518.   splay_tree_node n;

  520.   /* We should only be asked to allocate nodes and larger things.
  521.      (If, at some point in the future, this is no longer true, we can
  522.      just round up the size to sizeof (*n).)  */
  523.   gdb_assert (size >= sizeof (*n));

  525.   if (map->free_nodes)
  526.     {
  527.       n = map->free_nodes;
  528.       map->free_nodes = n->right;
  529.       return n;
  530.     }
  531.   else
  532.     return obstack_alloc (map->obstack, size);
  533. }


  536. static void
  537. ‌splay_obstack_free (void *obj, void *closure)
  538. {
  539.   struct addrmap_mutable *map = closure;
  540.   splay_tree_node n = obj;

  542.   /* We've asserted in the allocation function that we only allocate
  543.      nodes or larger things, so it should be safe to put whatever
  544.      we get passed back on the free list.  */
  545.   n->right = map->free_nodes;
  546.   map->free_nodes = n;
  547. }


  550. /* Compare keys as CORE_ADDR * values.  */
  551. static int
  552. ‌splay_compare_CORE_ADDR_ptr (splay_tree_key ak, splay_tree_key bk)
  553. {
  554.   CORE_ADDR a = * (CORE_ADDR *) ak;
  555.   CORE_ADDR b = * (CORE_ADDR *) bk;

  557.   /* We can't just return a-b here, because of over/underflow.  */
  558.   if (a < b)
  559.     return -1;
  560.   else if (a == b)
  561.     return 0;
  562.   else
  563.     return 1;
  564. }


  567. struct addrmap *
  568. ‌addrmap_create_mutable (struct obstack *obstack)
  569. {
  570.   struct addrmap_mutable *map = obstack_alloc (obstack, sizeof (*map));

  572.   map->addrmap.funcs = &addrmap_mutable_funcs;
  573.   map->obstack = obstack;

  575.   /* splay_tree_new_with_allocator uses the provided allocation
  576.      function to allocate the main splay_tree structure itself, so our
  577.      free list has to be initialized before we create the tree.  */
  578.   map->free_nodes = NULL;

  580.   map->tree = splay_tree_new_with_allocator (splay_compare_CORE_ADDR_ptr,
  581.                                              NULL, /* no delete key */
  582.                                              NULL, /* no delete value */
  583.                                              splay_obstack_alloc,
  584.                                              splay_obstack_free,
  585.                                              map);

  587.   return (struct addrmap *) map;
  588. }



  592. /* Initialization.  */

  594. /* Provide a prototype to silence -Wmissing-prototypes.  */
  595. extern initialize_file_ftype _initialize_addrmap;

  597. void
  598. ‌_initialize_addrmap (void)
  599. {
  600.   /* Make sure splay trees can actually hold the values we want to
  601.      store in them.  */
  602.   gdb_assert (sizeof (splay_tree_key) >= sizeof (CORE_ADDR *));
  603.   gdb_assert (sizeof (splay_tree_value) >= sizeof (void *));
  604. }