gdb/addrmap.c

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