gdb/addrmap.c

   1 /* addrmap.c --- implementation of address map data structure.
   2
   3    Copyright (C) 2007-2021 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 "splay-tree.h"
  22 #include "gdb_obstack.h"
  23 #include "addrmap.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 /* The "abstract class".  */
  32
  33 /* Functions implementing the addrmap functions for a particular
  34    implementation.  */
  35 struct addrmap_funcs
  36 {
  37   void (*set_empty) (struct addrmap *self,
  38                      CORE_ADDR start, CORE_ADDR end_inclusive,
  39                      void *obj);
  40   void *(*find) (struct addrmap *self, CORE_ADDR addr);
  41   struct addrmap *(*create_fixed) (struct addrmap *self,
  42                                    struct obstack *obstack);
  43   void (*relocate) (struct addrmap *self, CORE_ADDR offset);
  44   int (*foreach) (struct addrmap *self, addrmap_foreach_fn fn);
  45 };
  46
  47
  48 struct addrmap
  49 {
  50   const struct addrmap_funcs *funcs;
  51 };
  52
  53
  54 void
  55 addrmap_set_empty (struct addrmap *map,
  56                    CORE_ADDR start, CORE_ADDR end_inclusive,
  57                    void *obj)
  58 {
  59   map->funcs->set_empty (map, start, end_inclusive, obj);
  60 }
  61
  62
  63 void *
  64 addrmap_find (struct addrmap *map, CORE_ADDR addr)
  65 {
  66   return map->funcs->find (map, addr);
  67 }
  68
  69
  70 struct addrmap *
  71 addrmap_create_fixed (struct addrmap *original, struct obstack *obstack)
  72 {
  73   return original->funcs->create_fixed (original, obstack);
  74 }
  75
  76
  77 /* Relocate all the addresses in MAP by OFFSET.  (This can be applied
  78    to either mutable or immutable maps.)  */
  79 void
  80 addrmap_relocate (struct addrmap *map, CORE_ADDR offset)
  81 {
  82   map->funcs->relocate (map, offset);
  83 }
  84
  85
  86 int
  87 addrmap_foreach (struct addrmap *map, addrmap_foreach_fn fn)
  88 {
  89   return map->funcs->foreach (map, fn);
  90 }
  91 \f
  92 /* Fixed address maps.  */
  93
  94 /* A transition: a point in an address map where the value changes.
  95    The map maps ADDR to VALUE, but if ADDR > 0, it maps ADDR-1 to
  96    something else.  */
  97 struct addrmap_transition
  98 {
  99   CORE_ADDR addr;
 100   void *value;
 101 };
 102
 103
 104 struct addrmap_fixed
 105 {
 106   struct addrmap addrmap;
 107
 108   /* The number of transitions in TRANSITIONS.  */
 109   size_t num_transitions;
 110
 111   /* An array of transitions, sorted by address.  For every point in
 112      the map where either ADDR == 0 or ADDR is mapped to one value and
 113      ADDR - 1 is mapped to something different, we have an entry here
 114      containing ADDR and VALUE.  (Note that this means we always have
 115      an entry for address 0).  */
 116   struct addrmap_transition transitions[1];
 117 };
 118
 119
 120 static void
 121 addrmap_fixed_set_empty (struct addrmap *self,
 122                    CORE_ADDR start, CORE_ADDR end_inclusive,
 123                    void *obj)
 124 {
 125   internal_error (__FILE__, __LINE__,
 126                   "addrmap_fixed_set_empty: "
 127                   "fixed addrmaps can't be changed\n");
 128 }
 129
 130
 131 static void *
 132 addrmap_fixed_find (struct addrmap *self, CORE_ADDR addr)
 133 {
 134   struct addrmap_fixed *map = (struct addrmap_fixed *) self;
 135   struct addrmap_transition *bottom = &map->transitions[0];
 136   struct addrmap_transition *top = &map->transitions[map->num_transitions - 1];
 137
 138   while (bottom < top)
 139     {
 140       /* This needs to round towards top, or else when top = bottom +
 141          1 (i.e., two entries are under consideration), then mid ==
 142          bottom, and then we may not narrow the range when (mid->addr
 143          < addr).  */
 144       struct addrmap_transition *mid = top - (top - bottom) / 2;
 145
 146       if (mid->addr == addr)
 147         {
 148           bottom = mid;
 149           break;
 150         }
 151       else if (mid->addr < addr)
 152         /* We don't eliminate mid itself here, since each transition
 153            covers all subsequent addresses until the next.  This is why
 154            we must round up in computing the midpoint.  */
 155         bottom = mid;
 156       else
 157         top = mid - 1;
 158     }
 159
 160   return bottom->value;
 161 }
 162
 163
 164 static struct addrmap *
 165 addrmap_fixed_create_fixed (struct addrmap *self, struct obstack *obstack)
 166 {
 167   internal_error (__FILE__, __LINE__,
 168                   _("addrmap_create_fixed is not implemented yet "
 169                     "for fixed addrmaps"));
 170 }
 171
 172
 173 static void
 174 addrmap_fixed_relocate (struct addrmap *self, CORE_ADDR offset)
 175 {
 176   struct addrmap_fixed *map = (struct addrmap_fixed *) self;
 177   size_t i;
 178
 179   for (i = 0; i < map->num_transitions; i++)
 180     map->transitions[i].addr += offset;
 181 }
 182
 183
 184 static int
 185 addrmap_fixed_foreach (struct addrmap *self, addrmap_foreach_fn fn)
 186 {
 187   struct addrmap_fixed *map = (struct addrmap_fixed *) self;
 188   size_t i;
 189
 190   for (i = 0; i < map->num_transitions; i++)
 191     {
 192       int res = fn (map->transitions[i].addr, map->transitions[i].value);
 193
 194       if (res != 0)
 195         return res;
 196     }
 197
 198   return 0;
 199 }
 200
 201
 202 static const struct addrmap_funcs addrmap_fixed_funcs =
 203 {
 204   addrmap_fixed_set_empty,
 205   addrmap_fixed_find,
 206   addrmap_fixed_create_fixed,
 207   addrmap_fixed_relocate,
 208   addrmap_fixed_foreach
 209 };
 210
 211
 212 \f
 213 /* Mutable address maps.  */
 214
 215 struct addrmap_mutable
 216 {
 217   struct addrmap addrmap;
 218
 219   /* The obstack to use for allocations for this map.  */
 220   struct obstack *obstack;
 221
 222   /* A splay tree, with a node for each transition; there is a
 223      transition at address T if T-1 and T map to different objects.
 224
 225      Any addresses below the first node map to NULL.  (Unlike
 226      fixed maps, we have no entry at (CORE_ADDR) 0; it doesn't
 227      simplify enough.)
 228
 229      The last region is assumed to end at CORE_ADDR_MAX.
 230
 231      Since we can't know whether CORE_ADDR is larger or smaller than
 232      splay_tree_key (unsigned long) --- I think both are possible,
 233      given all combinations of 32- and 64-bit hosts and targets ---
 234      our keys are pointers to CORE_ADDR values.  Since the splay tree
 235      library doesn't pass any closure pointer to the key free
 236      function, we can't keep a freelist for keys.  Since mutable
 237      addrmaps are only used temporarily right now, we just leak keys
 238      from deleted nodes; they'll be freed when the obstack is freed.  */
 239   splay_tree tree;
 240
 241   /* A freelist for splay tree nodes, allocated on obstack, and
 242      chained together by their 'right' pointers.  */
 243   splay_tree_node free_nodes;
 244 };
 245
 246
 247 /* Allocate a copy of CORE_ADDR in MAP's obstack.  */
 248 static splay_tree_key
 249 allocate_key (struct addrmap_mutable *map, CORE_ADDR addr)
 250 {
 251   CORE_ADDR *key = XOBNEW (map->obstack, CORE_ADDR);
 252
 253   *key = addr;
 254   return (splay_tree_key) key;
 255 }
 256
 257
 258 /* Type-correct wrappers for splay tree access.  */
 259 static splay_tree_node
 260 addrmap_splay_tree_lookup (struct addrmap_mutable *map, CORE_ADDR addr)
 261 {
 262   return splay_tree_lookup (map->tree, (splay_tree_key) &addr);
 263 }
 264
 265
 266 static splay_tree_node
 267 addrmap_splay_tree_predecessor (struct addrmap_mutable *map, CORE_ADDR addr)
 268 {
 269   return splay_tree_predecessor (map->tree, (splay_tree_key) &addr);
 270 }
 271
 272
 273 static splay_tree_node
 274 addrmap_splay_tree_successor (struct addrmap_mutable *map, CORE_ADDR addr)
 275 {
 276   return splay_tree_successor (map->tree, (splay_tree_key) &addr);
 277 }
 278
 279
 280 static void
 281 addrmap_splay_tree_remove (struct addrmap_mutable *map, CORE_ADDR addr)
 282 {
 283   splay_tree_remove (map->tree, (splay_tree_key) &addr);
 284 }
 285
 286
 287 static CORE_ADDR
 288 addrmap_node_key (splay_tree_node node)
 289 {
 290   return * (CORE_ADDR *) node->key;
 291 }
 292
 293
 294 static void *
 295 addrmap_node_value (splay_tree_node node)
 296 {
 297   return (void *) node->value;
 298 }
 299
 300
 301 static void
 302 addrmap_node_set_value (splay_tree_node node, void *value)
 303 {
 304   node->value = (splay_tree_value) value;
 305 }
 306
 307
 308 static void
 309 addrmap_splay_tree_insert (struct addrmap_mutable *map,
 310                            CORE_ADDR key, void *value)
 311 {
 312   splay_tree_insert (map->tree,
 313                      allocate_key (map, key),
 314                      (splay_tree_value) value);
 315 }
 316
 317
 318 /* Without changing the mapping of any address, ensure that there is a
 319    tree node at ADDR, even if it would represent a "transition" from
 320    one value to the same value.  */
 321 static void
 322 force_transition (struct addrmap_mutable *self, CORE_ADDR addr)
 323 {
 324   splay_tree_node n
 325     = addrmap_splay_tree_lookup (self, addr);
 326
 327   if (! n)
 328     {
 329       n = addrmap_splay_tree_predecessor (self, addr);
 330       addrmap_splay_tree_insert (self, addr,
 331                                  n ? addrmap_node_value (n) : NULL);
 332     }
 333 }
 334
 335
 336 static void
 337 addrmap_mutable_set_empty (struct addrmap *self,
 338                            CORE_ADDR start, CORE_ADDR end_inclusive,
 339                            void *obj)
 340 {
 341   struct addrmap_mutable *map = (struct addrmap_mutable *) self;
 342   splay_tree_node n, next;
 343   void *prior_value;
 344
 345   /* If we're being asked to set all empty portions of the given
 346      address range to empty, then probably the caller is confused.
 347      (If that turns out to be useful in some cases, then we can change
 348      this to simply return, since overriding NULL with NULL is a
 349      no-op.)  */
 350   gdb_assert (obj);
 351
 352   /* We take a two-pass approach, for simplicity.
 353      - Establish transitions where we think we might need them.
 354      - First pass: change all NULL regions to OBJ.
 355      - Second pass: remove any unnecessary transitions.  */
 356
 357   /* Establish transitions at the start and end.  */
 358   force_transition (map, start);
 359   if (end_inclusive < CORE_ADDR_MAX)
 360     force_transition (map, end_inclusive + 1);
 361
 362   /* Walk the area, changing all NULL regions to OBJ.  */
 363   for (n = addrmap_splay_tree_lookup (map, start), gdb_assert (n);
 364        n && addrmap_node_key (n) <= end_inclusive;
 365        n = addrmap_splay_tree_successor (map, addrmap_node_key (n)))
 366     {
 367       if (! addrmap_node_value (n))
 368         addrmap_node_set_value (n, obj);
 369     }
 370
 371   /* Walk the area again, removing transitions from any value to
 372      itself.  Be sure to visit both the transitions we forced
 373      above.  */
 374   n = addrmap_splay_tree_predecessor (map, start);
 375   prior_value = n ? addrmap_node_value (n) : NULL;
 376   for (n = addrmap_splay_tree_lookup (map, start), gdb_assert (n);
 377        n && (end_inclusive == CORE_ADDR_MAX
 378              || addrmap_node_key (n) <= end_inclusive + 1);
 379        n = next)
 380     {
 381       next = addrmap_splay_tree_successor (map, addrmap_node_key (n));
 382       if (addrmap_node_value (n) == prior_value)
 383         addrmap_splay_tree_remove (map, addrmap_node_key (n));
 384       else
 385         prior_value = addrmap_node_value (n);
 386     }
 387 }
 388
 389
 390 static void *
 391 addrmap_mutable_find (struct addrmap *self, CORE_ADDR addr)
 392 {
 393   /* Not needed yet.  */
 394   internal_error (__FILE__, __LINE__,
 395                   _("addrmap_find is not implemented yet "
 396                     "for mutable addrmaps"));
 397 }
 398
 399
 400 /* A function to pass to splay_tree_foreach to count the number of nodes
 401    in the tree.  */
 402 static int
 403 splay_foreach_count (splay_tree_node n, void *closure)
 404 {
 405   size_t *count = (size_t *) closure;
 406
 407   (*count)++;
 408   return 0;
 409 }
 410
 411
 412 /* A function to pass to splay_tree_foreach to copy entries into a
 413    fixed address map.  */
 414 static int
 415 splay_foreach_copy (splay_tree_node n, void *closure)
 416 {
 417   struct addrmap_fixed *fixed = (struct addrmap_fixed *) closure;
 418   struct addrmap_transition *t = &fixed->transitions[fixed->num_transitions];
 419
 420   t->addr = addrmap_node_key (n);
 421   t->value = addrmap_node_value (n);
 422   fixed->num_transitions++;
 423
 424   return 0;
 425 }
 426
 427
 428 static struct addrmap *
 429 addrmap_mutable_create_fixed (struct addrmap *self, struct obstack *obstack)
 430 {
 431   struct addrmap_mutable *mutable_obj = (struct addrmap_mutable *) self;
 432   struct addrmap_fixed *fixed;
 433   size_t num_transitions;
 434   size_t alloc_len;
 435
 436   /* Count the number of transitions in the tree.  */
 437   num_transitions = 0;
 438   splay_tree_foreach (mutable_obj->tree, splay_foreach_count, &num_transitions);
 439
 440   /* Include an extra entry for the transition at zero (which fixed
 441      maps have, but mutable maps do not.)  */
 442   num_transitions++;
 443
 444   alloc_len = sizeof (*fixed)
 445               + (num_transitions * sizeof (fixed->transitions[0]));
 446   fixed = (struct addrmap_fixed *) obstack_alloc (obstack, alloc_len);
 447   fixed->addrmap.funcs = &addrmap_fixed_funcs;
 448   fixed->num_transitions = 1;
 449   fixed->transitions[0].addr = 0;
 450   fixed->transitions[0].value = NULL;
 451
 452   /* Copy all entries from the splay tree to the array, in order
 453      of increasing address.  */
 454   splay_tree_foreach (mutable_obj->tree, splay_foreach_copy, fixed);
 455
 456   /* We should have filled the array.  */
 457   gdb_assert (fixed->num_transitions == num_transitions);
 458
 459   return (struct addrmap *) fixed;
 460 }
 461
 462
 463 static void
 464 addrmap_mutable_relocate (struct addrmap *self, CORE_ADDR offset)
 465 {
 466   /* Not needed yet.  */
 467   internal_error (__FILE__, __LINE__,
 468                   _("addrmap_relocate is not implemented yet "
 469                     "for mutable addrmaps"));
 470 }
 471
 472
 473 /* This is a splay_tree_foreach_fn.  */
 474
 475 static int
 476 addrmap_mutable_foreach_worker (splay_tree_node node, void *data)
 477 {
 478   addrmap_foreach_fn *fn = (addrmap_foreach_fn *) data;
 479
 480   return (*fn) (addrmap_node_key (node), addrmap_node_value (node));
 481 }
 482
 483
 484 static int
 485 addrmap_mutable_foreach (struct addrmap *self, addrmap_foreach_fn fn)
 486 {
 487   struct addrmap_mutable *mutable_obj = (struct addrmap_mutable *) self;
 488
 489   return splay_tree_foreach (mutable_obj->tree, addrmap_mutable_foreach_worker,
 490                              &fn);
 491 }
 492
 493
 494 static const struct addrmap_funcs addrmap_mutable_funcs =
 495 {
 496   addrmap_mutable_set_empty,
 497   addrmap_mutable_find,
 498   addrmap_mutable_create_fixed,
 499   addrmap_mutable_relocate,
 500   addrmap_mutable_foreach
 501 };
 502
 503
 504 static void *
 505 splay_obstack_alloc (int size, void *closure)
 506 {
 507   struct addrmap_mutable *map = (struct addrmap_mutable *) closure;
 508   splay_tree_node n;
 509
 510   /* We should only be asked to allocate nodes and larger things.
 511      (If, at some point in the future, this is no longer true, we can
 512      just round up the size to sizeof (*n).)  */
 513   gdb_assert (size >= sizeof (*n));
 514
 515   if (map->free_nodes)
 516     {
 517       n = map->free_nodes;
 518       map->free_nodes = n->right;
 519       return n;
 520     }
 521   else
 522     return obstack_alloc (map->obstack, size);
 523 }
 524
 525
 526 static void
 527 splay_obstack_free (void *obj, void *closure)
 528 {
 529   struct addrmap_mutable *map = (struct addrmap_mutable *) closure;
 530   splay_tree_node n = (splay_tree_node) obj;
 531
 532   /* We've asserted in the allocation function that we only allocate
 533      nodes or larger things, so it should be safe to put whatever
 534      we get passed back on the free list.  */
 535   n->right = map->free_nodes;
 536   map->free_nodes = n;
 537 }
 538
 539
 540 /* Compare keys as CORE_ADDR * values.  */
 541 static int
 542 splay_compare_CORE_ADDR_ptr (splay_tree_key ak, splay_tree_key bk)
 543 {
 544   CORE_ADDR a = * (CORE_ADDR *) ak;
 545   CORE_ADDR b = * (CORE_ADDR *) bk;
 546
 547   /* We can't just return a-b here, because of over/underflow.  */
 548   if (a < b)
 549     return -1;
 550   else if (a == b)
 551     return 0;
 552   else
 553     return 1;
 554 }
 555
 556
 557 struct addrmap *
 558 addrmap_create_mutable (struct obstack *obstack)
 559 {
 560   struct addrmap_mutable *map = XOBNEW (obstack, struct addrmap_mutable);
 561
 562   map->addrmap.funcs = &addrmap_mutable_funcs;
 563   map->obstack = obstack;
 564
 565   /* splay_tree_new_with_allocator uses the provided allocation
 566      function to allocate the main splay_tree structure itself, so our
 567      free list has to be initialized before we create the tree.  */
 568   map->free_nodes = NULL;
 569
 570   map->tree = splay_tree_new_with_allocator (splay_compare_CORE_ADDR_ptr,
 571                                              NULL, /* no delete key */
 572                                              NULL, /* no delete value */
 573                                              splay_obstack_alloc,
 574                                              splay_obstack_free,
 575                                              map);
 576
 577   return (struct addrmap *) map;
 578 }