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