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 bool
 205 addrmap_mutable::set_empty (CORE_ADDR start, CORE_ADDR end_inclusive,
 206                             void *obj)
 207 {
 208   bool full_range = true;
 209   splay_tree_node n, next;
 210   void *prior_value;
 211
 212   if (tree == nullptr)
 213     tree = splay_tree_new (splay_compare_CORE_ADDR_ptr, xfree_wrapper,
 214                            nullptr /* no delete value */);
 215
 216   /* If we're being asked to set all empty portions of the given
 217      address range to empty, then probably the caller is confused.
 218      (If that turns out to be useful in some cases, then we can change
 219      this to simply return, since overriding NULL with NULL is a
 220      no-op.)  */
 221   gdb_assert (obj);
 222
 223   /* We take a two-pass approach, for simplicity.
 224      - Establish transitions where we think we might need them.
 225      - First pass: change all NULL regions to OBJ.
 226      - Second pass: remove any unnecessary transitions.  */
 227
 228   /* Establish transitions at the start and end.  */
 229   force_transition (start);
 230   if (end_inclusive < CORE_ADDR_MAX)
 231     force_transition (end_inclusive + 1);
 232
 233   /* Walk the area, changing all NULL regions to OBJ.  */
 234   for (n = splay_tree_lookup (start), gdb_assert (n);
 235        n && addrmap_node_key (n) <= end_inclusive;
 236        n = splay_tree_successor (addrmap_node_key (n)))
 237     {
 238       if (addrmap_node_value (n))
 239         {
 240           /* Already mapped.  */
 241           full_range = false;
 242         }
 243       else
 244         addrmap_node_set_value (n, obj);
 245     }
 246
 247   /* Walk the area again, removing transitions from any value to
 248      itself.  Be sure to visit both the transitions we forced
 249      above.  */
 250   n = splay_tree_predecessor (start);
 251   prior_value = n ? addrmap_node_value (n) : NULL;
 252   for (n = splay_tree_lookup (start), gdb_assert (n);
 253        n && (end_inclusive == CORE_ADDR_MAX
 254              || addrmap_node_key (n) <= end_inclusive + 1);
 255        n = next)
 256     {
 257       next = splay_tree_successor (addrmap_node_key (n));
 258       if (addrmap_node_value (n) == prior_value)
 259         splay_tree_remove (addrmap_node_key (n));
 260       else
 261         prior_value = addrmap_node_value (n);
 262     }
 263
 264   return full_range;
 265 }
 266
 267
 268 void *
 269 addrmap_mutable::do_find (CORE_ADDR addr) const
 270 {
 271   if (tree == nullptr)
 272     return nullptr;
 273
 274   splay_tree_node n = splay_tree_lookup (addr);
 275   if (n != nullptr)
 276     {
 277       gdb_assert (addrmap_node_key (n) == addr);
 278       return addrmap_node_value (n);
 279     }
 280
 281   n = splay_tree_predecessor (addr);
 282   if (n != nullptr)
 283     {
 284       gdb_assert (addrmap_node_key (n) < addr);
 285       return addrmap_node_value (n);
 286     }
 287
 288   return nullptr;
 289 }
 290
 291
 292 addrmap_fixed::addrmap_fixed (struct obstack *obstack,
 293                               const addrmap_mutable *mut)
 294 {
 295   size_t transition_count = 0;
 296
 297   /* Count the number of transitions in the tree.  */
 298   mut->foreach ([&] (CORE_ADDR start, const void *obj)
 299     {
 300       ++transition_count;
 301       return 0;
 302     });
 303
 304   /* Include an extra entry for the transition at zero (which fixed
 305      maps have, but mutable maps do not.)  */
 306   transition_count++;
 307
 308   num_transitions = 1;
 309   transitions = XOBNEWVEC (obstack, struct addrmap_transition,
 310                            transition_count);
 311   transitions[0].addr = 0;
 312   transitions[0].value = NULL;
 313
 314   /* Copy all entries from the splay tree to the array, in order
 315      of increasing address.  */
 316   mut->foreach ([&] (CORE_ADDR start, const void *obj)
 317     {
 318       transitions[num_transitions].addr = start;
 319       transitions[num_transitions].value = const_cast<void *> (obj);
 320       ++num_transitions;
 321       return 0;
 322     });
 323
 324   /* We should have filled the array.  */
 325   gdb_assert (num_transitions == transition_count);
 326 }
 327
 328 /* This is a splay_tree_foreach_fn.  */
 329
 330 static int
 331 addrmap_mutable_foreach_worker (splay_tree_node node, void *data)
 332 {
 333   addrmap_foreach_fn *fn = (addrmap_foreach_fn *) data;
 334
 335   return (*fn) (addrmap_node_key (node), addrmap_node_value (node));
 336 }
 337
 338
 339 int
 340 addrmap_mutable::do_foreach (addrmap_foreach_fn fn) const
 341 {
 342   if (tree == nullptr)
 343     return 0;
 344   return splay_tree_foreach (tree, addrmap_mutable_foreach_worker, &fn);
 345 }
 346
 347
 348 void
 349 addrmap_mutable::clear ()
 350 {
 351   if (tree != nullptr)
 352     {
 353       splay_tree_delete (tree);
 354       tree = nullptr;
 355     }
 356 }
 357
 358
 359 /* See addrmap.h.  */
 360
 361 void
 362 addrmap_dump (struct addrmap *map, struct ui_file *outfile, void *payload,
 363               gdb::function_view<void (struct ui_file *outfile,
 364                                        CORE_ADDR start_addr,
 365                                        const void *value)> annotate_value)
 366 {
 367   /* True if the previously printed addrmap entry was for PAYLOAD.
 368      If so, we want to print the next one as well (since the next
 369      addrmap entry defines the end of the range).  */
 370   bool previous_matched = false;
 371
 372   auto callback = [&] (CORE_ADDR start_addr, const void *obj)
 373   {
 374     QUIT;
 375
 376     bool matches = payload == nullptr || payload == obj;
 377     const char *addr_str = nullptr;
 378     if (matches)
 379       addr_str = host_address_to_string (obj);
 380     else if (previous_matched)
 381       addr_str = "<ends here>";
 382
 383     if (matches || previous_matched)
 384       {
 385         gdb_printf (outfile, "  %s%s %s",
 386                     payload != nullptr ? "  " : "",
 387                     core_addr_to_string (start_addr),
 388                     addr_str);
 389         if (annotate_value != nullptr)
 390           annotate_value (outfile, start_addr, obj);
 391
 392         gdb_printf (outfile, "\n");
 393       }
 394
 395     previous_matched = matches;
 396
 397     return 0;
 398   };
 399
 400   map->foreach (callback);
 401 }
 402
 403 #if GDB_SELF_TEST
 404 namespace selftests {
 405
 406 /* Convert P to CORE_ADDR.  */
 407
 408 static CORE_ADDR
 409 core_addr (const void *p)
 410 {
 411   return (CORE_ADDR) (uintptr_t) p;
 412 }
 413
 414 /* Check that &ARRAY[LOW]..&ARRAY[HIGH] has VAL in MAP.  */
 415
 416 static void
 417 check_addrmap_find (const addrmap &map, const char *array, unsigned int low,
 418                     unsigned int high, const void *val)
 419 {
 420   for (unsigned int i = low; i <= high; ++i)
 421     SELF_CHECK (map.find (core_addr (&array[i])) == val);
 422 }
 423
 424 /* Entry point for addrmap unit tests.  */
 425
 426 static void
 427 test_addrmap ()
 428 {
 429   /* We'll verify using the addresses of the elements of this array.  */
 430   char array[20];
 431
 432   /* We'll verify using these values stored into the map.  */
 433   void *val1 = &array[1];
 434   void *val2 = &array[2];
 435
 436   /* Create mutable addrmap.  */
 437   auto_obstack temp_obstack;
 438   addrmap_mutable map;
 439
 440   /* Check initial state.  */
 441   check_addrmap_find (map, array, 0, 19, nullptr);
 442
 443   /* Insert address range into mutable addrmap.  */
 444   bool full_range_p
 445     = map.set_empty (core_addr (&array[10]), core_addr (&array[12]), val1);
 446   SELF_CHECK (full_range_p);
 447   check_addrmap_find (map, array, 0, 9, nullptr);
 448   check_addrmap_find (map, array, 10, 12, val1);
 449   check_addrmap_find (map, array, 13, 19, nullptr);
 450
 451   /* Create corresponding fixed addrmap.  */
 452   addrmap_fixed *map2
 453     = new (&temp_obstack) addrmap_fixed (&temp_obstack, &map);
 454   SELF_CHECK (map2 != nullptr);
 455   check_addrmap_find (*map2, array, 0, 9, nullptr);
 456   check_addrmap_find (*map2, array, 10, 12, val1);
 457   check_addrmap_find (*map2, array, 13, 19, nullptr);
 458
 459   /* Iterate over both addrmaps.  */
 460   auto callback = [&] (CORE_ADDR start_addr, void *obj)
 461     {
 462       if (start_addr == core_addr (nullptr))
 463         SELF_CHECK (obj == nullptr);
 464       else if (start_addr == core_addr (&array[10]))
 465         SELF_CHECK (obj == val1);
 466       else if (start_addr == core_addr (&array[13]))
 467         SELF_CHECK (obj == nullptr);
 468       else
 469         SELF_CHECK (false);
 470       return 0;
 471     };
 472   SELF_CHECK (map.foreach (callback) == 0);
 473   SELF_CHECK (map2->foreach (callback) == 0);
 474
 475   /* Relocate fixed addrmap.  */
 476   map2->relocate (1);
 477   check_addrmap_find (*map2, array, 0, 10, nullptr);
 478   check_addrmap_find (*map2, array, 11, 13, val1);
 479   check_addrmap_find (*map2, array, 14, 19, nullptr);
 480
 481   /* Insert partially overlapping address range into mutable addrmap.  */
 482   full_range_p
 483     = map.set_empty (core_addr (&array[11]), core_addr (&array[13]), val2);
 484   SELF_CHECK (!full_range_p);
 485   check_addrmap_find (map, array, 0, 9, nullptr);
 486   check_addrmap_find (map, array, 10, 12, val1);
 487   check_addrmap_find (map, array, 13, 13, val2);
 488   check_addrmap_find (map, array, 14, 19, nullptr);
 489 }
 490
 491 } /* namespace selftests */
 492 #endif /* GDB_SELF_TEST */
 493
 494 INIT_GDB_FILE (addrmap)
 495 {
 496 #if GDB_SELF_TEST
 497   selftests::register_test ("addrmap", selftests::test_addrmap);
 498 #endif /* GDB_SELF_TEST */
 499 }