gdb/addrmap.c

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