gdb/addrmap.c

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