gdb/addrmap.c

   1 /* addrmap.c --- implementation of address map data structure.
   2
   3    Copyright (C) 2007-2023 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 #include "defs.h"
  21 #include "gdbsupport/gdb_obstack.h"
  22 #include "addrmap.h"
  23 #include "gdbsupport/selftest.h"
  24
  25 /* Make sure splay trees can actually hold the values we want to
  26    store in them.  */
  27 gdb_static_assert (sizeof (splay_tree_key) >= sizeof (CORE_ADDR *));
  28 gdb_static_assert (sizeof (splay_tree_value) >= sizeof (void *));
  29
  30 \f
  31 /* Fixed address maps.  */
  32
  33 void
  34 addrmap_fixed::set_empty (CORE_ADDR start, CORE_ADDR end_inclusive,
  35                           void *obj)
  36 {
  37   internal_error ("addrmap_fixed_set_empty: "
  38                   "fixed addrmaps can't be changed\n");
  39 }
  40
  41
  42 void *
  43 addrmap_fixed::find (CORE_ADDR addr) const
  44 {
  45   const struct addrmap_transition *bottom = &transitions[0];
  46   const struct addrmap_transition *top = &transitions[num_transitions - 1];
  47
  48   while (bottom < top)
  49     {
  50       /* This needs to round towards top, or else when top = bottom +
  51          1 (i.e., two entries are under consideration), then mid ==
  52          bottom, and then we may not narrow the range when (mid->addr
  53          < addr).  */
  54       const addrmap_transition *mid = top - (top - bottom) / 2;
  55
  56       if (mid->addr == addr)
  57         {
  58           bottom = mid;
  59           break;
  60         }
  61       else if (mid->addr < addr)
  62         /* We don't eliminate mid itself here, since each transition
  63            covers all subsequent addresses until the next.  This is why
  64            we must round up in computing the midpoint.  */
  65         bottom = mid;
  66       else
  67         top = mid - 1;
  68     }
  69
  70   return bottom->value;
  71 }
  72
  73
  74 void
  75 addrmap_fixed::relocate (CORE_ADDR offset)
  76 {
  77   size_t i;
  78
  79   for (i = 0; i < num_transitions; i++)
  80     transitions[i].addr += offset;
  81 }
  82
  83
  84 int
  85 addrmap_fixed::foreach (addrmap_foreach_fn fn)
  86 {
  87   size_t i;
  88
  89   for (i = 0; i < num_transitions; i++)
  90     {
  91       int res = fn (transitions[i].addr, transitions[i].value);
  92
  93       if (res != 0)
  94         return res;
  95     }
  96
  97   return 0;
  98 }
  99
 100
 101 \f
 102 /* Mutable address maps.  */
 103
 104 /* Allocate a copy of CORE_ADDR.  */
 105 splay_tree_key
 106 addrmap_mutable::allocate_key (CORE_ADDR addr)
 107 {
 108   CORE_ADDR *key = XNEW (CORE_ADDR);
 109
 110   *key = addr;
 111   return (splay_tree_key) key;
 112 }
 113
 114
 115 /* Type-correct wrappers for splay tree access.  */
 116 splay_tree_node
 117 addrmap_mutable::splay_tree_lookup (CORE_ADDR addr) const
 118 {
 119   return ::splay_tree_lookup (tree, (splay_tree_key) &addr);
 120 }
 121
 122
 123 splay_tree_node
 124 addrmap_mutable::splay_tree_predecessor (CORE_ADDR addr) const
 125 {
 126   return ::splay_tree_predecessor (tree, (splay_tree_key) &addr);
 127 }
 128
 129
 130 splay_tree_node
 131 addrmap_mutable::splay_tree_successor (CORE_ADDR addr)
 132 {
 133   return ::splay_tree_successor (tree, (splay_tree_key) &addr);
 134 }
 135
 136
 137 void
 138 addrmap_mutable::splay_tree_remove (CORE_ADDR addr)
 139 {
 140   ::splay_tree_remove (tree, (splay_tree_key) &addr);
 141 }
 142
 143
 144 static CORE_ADDR
 145 addrmap_node_key (splay_tree_node node)
 146 {
 147   return * (CORE_ADDR *) node->key;
 148 }
 149
 150
 151 static void *
 152 addrmap_node_value (splay_tree_node node)
 153 {
 154   return (void *) node->value;
 155 }
 156
 157
 158 static void
 159 addrmap_node_set_value (splay_tree_node node, void *value)
 160 {
 161   node->value = (splay_tree_value) value;
 162 }
 163
 164
 165 void
 166 addrmap_mutable::splay_tree_insert (CORE_ADDR key, void *value)
 167 {
 168   ::splay_tree_insert (tree,
 169                        allocate_key (key),
 170                        (splay_tree_value) value);
 171 }
 172
 173
 174 /* Without changing the mapping of any address, ensure that there is a
 175    tree node at ADDR, even if it would represent a "transition" from
 176    one value to the same value.  */
 177 void
 178 addrmap_mutable::force_transition (CORE_ADDR addr)
 179 {
 180   splay_tree_node n = splay_tree_lookup (addr);
 181
 182   if (! n)
 183     {
 184       n = splay_tree_predecessor (addr);
 185       splay_tree_insert (addr, n ? addrmap_node_value (n) : NULL);
 186     }
 187 }
 188
 189
 190 void
 191 addrmap_mutable::set_empty (CORE_ADDR start, CORE_ADDR end_inclusive,
 192                             void *obj)
 193 {
 194   splay_tree_node n, next;
 195   void *prior_value;
 196
 197   /* If we're being asked to set all empty portions of the given
 198      address range to empty, then probably the caller is confused.
 199      (If that turns out to be useful in some cases, then we can change
 200      this to simply return, since overriding NULL with NULL is a
 201      no-op.)  */
 202   gdb_assert (obj);
 203
 204   /* We take a two-pass approach, for simplicity.
 205      - Establish transitions where we think we might need them.
 206      - First pass: change all NULL regions to OBJ.
 207      - Second pass: remove any unnecessary transitions.  */
 208
 209   /* Establish transitions at the start and end.  */
 210   force_transition (start);
 211   if (end_inclusive < CORE_ADDR_MAX)
 212     force_transition (end_inclusive + 1);
 213
 214   /* Walk the area, changing all NULL regions to OBJ.  */
 215   for (n = splay_tree_lookup (start), gdb_assert (n);
 216        n && addrmap_node_key (n) <= end_inclusive;
 217        n = splay_tree_successor (addrmap_node_key (n)))
 218     {
 219       if (! addrmap_node_value (n))
 220         addrmap_node_set_value (n, obj);
 221     }
 222
 223   /* Walk the area again, removing transitions from any value to
 224      itself.  Be sure to visit both the transitions we forced
 225      above.  */
 226   n = splay_tree_predecessor (start);
 227   prior_value = n ? addrmap_node_value (n) : NULL;
 228   for (n = splay_tree_lookup (start), gdb_assert (n);
 229        n && (end_inclusive == CORE_ADDR_MAX
 230              || addrmap_node_key (n) <= end_inclusive + 1);
 231        n = next)
 232     {
 233       next = splay_tree_successor (addrmap_node_key (n));
 234       if (addrmap_node_value (n) == prior_value)
 235         splay_tree_remove (addrmap_node_key (n));
 236       else
 237         prior_value = addrmap_node_value (n);
 238     }
 239 }
 240
 241
 242 void *
 243 addrmap_mutable::find (CORE_ADDR addr) const
 244 {
 245   splay_tree_node n = splay_tree_lookup (addr);
 246   if (n != nullptr)
 247     {
 248       gdb_assert (addrmap_node_key (n) == addr);
 249       return addrmap_node_value (n);
 250     }
 251
 252   n = splay_tree_predecessor (addr);
 253   if (n != nullptr)
 254     {
 255       gdb_assert (addrmap_node_key (n) < addr);
 256       return addrmap_node_value (n);
 257     }
 258
 259   return nullptr;
 260 }
 261
 262
 263 addrmap_fixed::addrmap_fixed (struct obstack *obstack, addrmap_mutable *mut)
 264 {
 265   size_t transition_count = 0;
 266
 267   /* Count the number of transitions in the tree.  */
 268   mut->foreach ([&] (CORE_ADDR start, void *obj)
 269     {
 270       ++transition_count;
 271       return 0;
 272     });
 273
 274   /* Include an extra entry for the transition at zero (which fixed
 275      maps have, but mutable maps do not.)  */
 276   transition_count++;
 277
 278   num_transitions = 1;
 279   transitions = XOBNEWVEC (obstack, struct addrmap_transition,
 280                            transition_count);
 281   transitions[0].addr = 0;
 282   transitions[0].value = NULL;
 283
 284   /* Copy all entries from the splay tree to the array, in order
 285      of increasing address.  */
 286   mut->foreach ([&] (CORE_ADDR start, void *obj)
 287     {
 288       transitions[num_transitions].addr = start;
 289       transitions[num_transitions].value = obj;
 290       ++num_transitions;
 291       return 0;
 292     });
 293
 294   /* We should have filled the array.  */
 295   gdb_assert (num_transitions == transition_count);
 296 }
 297
 298
 299 void
 300 addrmap_mutable::relocate (CORE_ADDR offset)
 301 {
 302   /* Not needed yet.  */
 303   internal_error (_("addrmap_relocate is not implemented yet "
 304                     "for mutable addrmaps"));
 305 }
 306
 307
 308 /* This is a splay_tree_foreach_fn.  */
 309
 310 static int
 311 addrmap_mutable_foreach_worker (splay_tree_node node, void *data)
 312 {
 313   addrmap_foreach_fn *fn = (addrmap_foreach_fn *) data;
 314
 315   return (*fn) (addrmap_node_key (node), addrmap_node_value (node));
 316 }
 317
 318
 319 int
 320 addrmap_mutable::foreach (addrmap_foreach_fn fn)
 321 {
 322   return splay_tree_foreach (tree, addrmap_mutable_foreach_worker, &fn);
 323 }
 324
 325
 326 /* Compare keys as CORE_ADDR * values.  */
 327 static int
 328 splay_compare_CORE_ADDR_ptr (splay_tree_key ak, splay_tree_key bk)
 329 {
 330   CORE_ADDR a = * (CORE_ADDR *) ak;
 331   CORE_ADDR b = * (CORE_ADDR *) bk;
 332
 333   /* We can't just return a-b here, because of over/underflow.  */
 334   if (a < b)
 335     return -1;
 336   else if (a == b)
 337     return 0;
 338   else
 339     return 1;
 340 }
 341
 342
 343 static void
 344 xfree_wrapper (splay_tree_key key)
 345 {
 346   xfree ((void *) key);
 347 }
 348
 349 addrmap_mutable::addrmap_mutable ()
 350   : tree (splay_tree_new (splay_compare_CORE_ADDR_ptr, xfree_wrapper,
 351                           nullptr /* no delete value */))
 352 {
 353 }
 354
 355 addrmap_mutable::~addrmap_mutable ()
 356 {
 357   splay_tree_delete (tree);
 358 }
 359
 360
 361 /* See addrmap.h.  */
 362
 363 void
 364 addrmap_dump (struct addrmap *map, struct ui_file *outfile, void *payload)
 365 {
 366   /* True if the previously printed addrmap entry was for PAYLOAD.
 367      If so, we want to print the next one as well (since the next
 368      addrmap entry defines the end of the range).  */
 369   bool previous_matched = false;
 370
 371   auto callback = [&] (CORE_ADDR start_addr, void *obj)
 372   {
 373     QUIT;
 374
 375     bool matches = payload == nullptr || payload == obj;
 376     const char *addr_str = nullptr;
 377     if (matches)
 378       addr_str = host_address_to_string (obj);
 379     else if (previous_matched)
 380       addr_str = "<ends here>";
 381
 382     if (matches || previous_matched)
 383       gdb_printf (outfile, "  %s%s %s\n",
 384                   payload != nullptr ? "  " : "",
 385                   core_addr_to_string (start_addr),
 386                   addr_str);
 387
 388     previous_matched = matches;
 389
 390     return 0;
 391   };
 392
 393   map->foreach (callback);
 394 }
 395
 396 #if GDB_SELF_TEST
 397 namespace selftests {
 398
 399 /* Convert P to CORE_ADDR.  */
 400
 401 static CORE_ADDR
 402 core_addr (void *p)
 403 {
 404   return (CORE_ADDR)(uintptr_t)p;
 405 }
 406
 407 /* Check that &ARRAY[LOW]..&ARRAY[HIGH] has VAL in MAP.  */
 408
 409 #define CHECK_ADDRMAP_FIND(MAP, ARRAY, LOW, HIGH, VAL)                  \
 410   do                                                                    \
 411     {                                                                   \
 412       for (unsigned i = LOW; i <= HIGH; ++i)                            \
 413         SELF_CHECK (MAP->find (core_addr (&ARRAY[i])) == VAL);          \
 414     }                                                                   \
 415   while (0)
 416
 417 /* Entry point for addrmap unit tests.  */
 418
 419 static void
 420 test_addrmap ()
 421 {
 422   /* We'll verify using the addresses of the elements of this array.  */
 423   char array[20];
 424
 425   /* We'll verify using these values stored into the map.  */
 426   void *val1 = &array[1];
 427   void *val2 = &array[2];
 428
 429   /* Create mutable addrmap.  */
 430   auto_obstack temp_obstack;
 431   std::unique_ptr<struct addrmap_mutable> map (new addrmap_mutable);
 432   SELF_CHECK (map != nullptr);
 433
 434   /* Check initial state.  */
 435   CHECK_ADDRMAP_FIND (map, array, 0, 19, nullptr);
 436
 437   /* Insert address range into mutable addrmap.  */
 438   map->set_empty (core_addr (&array[10]), core_addr (&array[12]), val1);
 439   CHECK_ADDRMAP_FIND (map, array, 0, 9, nullptr);
 440   CHECK_ADDRMAP_FIND (map, array, 10, 12, val1);
 441   CHECK_ADDRMAP_FIND (map, array, 13, 19, nullptr);
 442
 443   /* Create corresponding fixed addrmap.  */
 444   struct addrmap *map2
 445     = new (&temp_obstack) addrmap_fixed (&temp_obstack, map.get ());
 446   SELF_CHECK (map2 != nullptr);
 447   CHECK_ADDRMAP_FIND (map2, array, 0, 9, nullptr);
 448   CHECK_ADDRMAP_FIND (map2, array, 10, 12, val1);
 449   CHECK_ADDRMAP_FIND (map2, array, 13, 19, nullptr);
 450
 451   /* Iterate over both addrmaps.  */
 452   auto callback = [&] (CORE_ADDR start_addr, void *obj)
 453     {
 454       if (start_addr == core_addr (nullptr))
 455         SELF_CHECK (obj == nullptr);
 456       else if (start_addr == core_addr (&array[10]))
 457         SELF_CHECK (obj == val1);
 458       else if (start_addr == core_addr (&array[13]))
 459         SELF_CHECK (obj == nullptr);
 460       else
 461         SELF_CHECK (false);
 462       return 0;
 463     };
 464   SELF_CHECK (map->foreach (callback) == 0);
 465   SELF_CHECK (map2->foreach (callback) == 0);
 466
 467   /* Relocate fixed addrmap.  */
 468   map2->relocate (1);
 469   CHECK_ADDRMAP_FIND (map2, array, 0, 10, nullptr);
 470   CHECK_ADDRMAP_FIND (map2, array, 11, 13, val1);
 471   CHECK_ADDRMAP_FIND (map2, array, 14, 19, nullptr);
 472
 473   /* Insert partially overlapping address range into mutable addrmap.  */
 474   map->set_empty (core_addr (&array[11]), core_addr (&array[13]), val2);
 475   CHECK_ADDRMAP_FIND (map, array, 0, 9, nullptr);
 476   CHECK_ADDRMAP_FIND (map, array, 10, 12, val1);
 477   CHECK_ADDRMAP_FIND (map, array, 13, 13, val2);
 478   CHECK_ADDRMAP_FIND (map, array, 14, 19, nullptr);
 479 }
 480
 481 } // namespace selftests
 482 #endif /* GDB_SELF_TEST */
 483
 484 void _initialize_addrmap ();
 485 void
 486 _initialize_addrmap ()
 487 {
 488 #if GDB_SELF_TEST
 489   selftests::register_test ("addrmap", selftests::test_addrmap);
 490 #endif /* GDB_SELF_TEST */
 491 }