gdb/addrmap.c

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