gdb/addrmap.c

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