gdb/addrmap.c

   1 /* addrmap.c --- implementation of address map data structure.
   2
   3    Copyright (C) 2007 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 CORE_ADDR
 256 addrmap_node_key (splay_tree_node node)
 257 {
 258   return * (CORE_ADDR *) node->key;
 259 }
 260
 261
 262 static void *
 263 addrmap_node_value (splay_tree_node node)
 264 {
 265   return (void *) node->value;
 266 }
 267
 268
 269 static void
 270 addrmap_node_set_value (splay_tree_node node, void *value)
 271 {
 272   node->value = (splay_tree_value) value;
 273 }
 274
 275
 276 static void
 277 addrmap_splay_tree_insert (struct addrmap_mutable *map, CORE_ADDR key, void *value)
 278 {
 279   splay_tree_insert (map->tree,
 280                      allocate_key (map, key),
 281                      (splay_tree_value) value);
 282 }
 283
 284
 285 /* Without changing the mapping of any address, ensure that there is a
 286    tree node at ADDR, even if it would represent a "transition" from
 287    one value to the same value.  */
 288 static void
 289 force_transition (struct addrmap_mutable *this, CORE_ADDR addr)
 290 {
 291   splay_tree_node n
 292     = addrmap_splay_tree_lookup (this, addr);
 293
 294   if (! n)
 295     {
 296       n = addrmap_splay_tree_predecessor (this, addr);
 297       addrmap_splay_tree_insert (this, addr,
 298                                  n ? addrmap_node_value (n) : NULL);
 299     }
 300 }
 301
 302
 303 static void
 304 addrmap_mutable_set_empty (struct addrmap *this,
 305                            CORE_ADDR start, CORE_ADDR end_inclusive,
 306                            void *obj)
 307 {
 308   struct addrmap_mutable *map = (struct addrmap_mutable *) this;
 309   splay_tree_node n, next;
 310   void *prior_value;
 311
 312   /* If we're being asked to set all empty portions of the given
 313      address range to empty, then probably the caller is confused.
 314      (If that turns out to be useful in some cases, then we can change
 315      this to simply return, since overriding NULL with NULL is a
 316      no-op.)  */
 317   gdb_assert (obj);
 318
 319   /* We take a two-pass approach, for simplicity.
 320      - Establish transitions where we think we might need them.
 321      - First pass: change all NULL regions to OBJ.
 322      - Second pass: remove any unnecessary transitions.  */
 323
 324   /* Establish transitions at the start and end.  */
 325   force_transition (map, start);
 326   if (end_inclusive < CORE_ADDR_MAX)
 327     force_transition (map, end_inclusive + 1);
 328
 329   /* Walk the area, changing all NULL regions to OBJ.  */
 330   for (n = addrmap_splay_tree_lookup (map, start), gdb_assert (n);
 331        n && addrmap_node_key (n) <= end_inclusive;
 332        n = addrmap_splay_tree_successor (map, addrmap_node_key (n)))
 333     {
 334       if (! addrmap_node_value (n))
 335         addrmap_node_set_value (n, obj);
 336     }
 337
 338   /* Walk the area again, removing transitions from any value to
 339      itself.  Be sure to visit both the transitions we forced
 340      above.  */
 341   n = addrmap_splay_tree_predecessor (map, start);
 342   prior_value = n ? addrmap_node_value (n) : NULL;
 343   for (n = addrmap_splay_tree_lookup (map, start), gdb_assert (n);
 344        n && (end_inclusive == CORE_ADDR_MAX
 345              || addrmap_node_key (n) <= end_inclusive + 1);
 346        n = next)
 347     {
 348       next = addrmap_splay_tree_successor (map, addrmap_node_key (n));
 349       if (addrmap_node_value (n) == prior_value)
 350         splay_tree_remove (map->tree, addrmap_node_key (n));
 351       else
 352         prior_value = addrmap_node_value (n);
 353     }
 354 }
 355
 356
 357 static void *
 358 addrmap_mutable_find (struct addrmap *this, CORE_ADDR addr)
 359 {
 360   /* Not needed yet.  */
 361   internal_error (__FILE__, __LINE__,
 362                   _("addrmap_find is not implemented yet "
 363                     "for mutable addrmaps"));
 364 }
 365
 366
 367 /* A function to pass to splay_tree_foreach to count the number of nodes
 368    in the tree.  */
 369 static int
 370 splay_foreach_count (splay_tree_node n, void *closure)
 371 {
 372   size_t *count = (size_t *) closure;
 373
 374   (*count)++;
 375   return 0;
 376 }
 377
 378
 379 /* A function to pass to splay_tree_foreach to copy entries into a
 380    fixed address map.  */
 381 static int
 382 splay_foreach_copy (splay_tree_node n, void *closure)
 383 {
 384   struct addrmap_fixed *fixed = (struct addrmap_fixed *) closure;
 385   struct addrmap_transition *t = &fixed->transitions[fixed->num_transitions];
 386
 387   t->addr = addrmap_node_key (n);
 388   t->value = addrmap_node_value (n);
 389   fixed->num_transitions++;
 390
 391   return 0;
 392 }
 393
 394
 395 static struct addrmap *
 396 addrmap_mutable_create_fixed (struct addrmap *this, struct obstack *obstack)
 397 {
 398   struct addrmap_mutable *mutable = (struct addrmap_mutable *) this;
 399   struct addrmap_fixed *fixed;
 400   size_t num_transitions;
 401
 402   /* Count the number of transitions in the tree.  */
 403   num_transitions = 0;
 404   splay_tree_foreach (mutable->tree, splay_foreach_count, &num_transitions);
 405
 406   /* Include an extra entry for the transition at zero (which fixed
 407      maps have, but mutable maps do not.)  */
 408   num_transitions++;
 409
 410   fixed = obstack_alloc (obstack,
 411                          (sizeof (*fixed)
 412                           + (num_transitions
 413                              * sizeof (fixed->transitions[0]))));
 414   fixed->addrmap.funcs = &addrmap_fixed_funcs;
 415   fixed->num_transitions = 1;
 416   fixed->transitions[0].addr = 0;
 417   fixed->transitions[0].value = NULL;
 418
 419   /* Copy all entries from the splay tree to the array, in order
 420      of increasing address.  */
 421   splay_tree_foreach (mutable->tree, splay_foreach_copy, fixed);
 422
 423   /* We should have filled the array.  */
 424   gdb_assert (fixed->num_transitions == num_transitions);
 425
 426   return (struct addrmap *) fixed;
 427 }
 428
 429
 430 static void
 431 addrmap_mutable_relocate (struct addrmap *this, CORE_ADDR offset)
 432 {
 433   /* Not needed yet.  */
 434   internal_error (__FILE__, __LINE__,
 435                   _("addrmap_relocate is not implemented yet "
 436                     "for mutable addrmaps"));
 437 }
 438
 439
 440 static const struct addrmap_funcs addrmap_mutable_funcs =
 441 {
 442   addrmap_mutable_set_empty,
 443   addrmap_mutable_find,
 444   addrmap_mutable_create_fixed,
 445   addrmap_mutable_relocate
 446 };
 447
 448
 449 static void *
 450 splay_obstack_alloc (int size, void *closure)
 451 {
 452   struct addrmap_mutable *map = closure;
 453   splay_tree_node n;
 454
 455   /* We should only be asked to allocate nodes and larger things.
 456      (If, at some point in the future, this is no longer true, we can
 457      just round up the size to sizeof (*n).)  */
 458   gdb_assert (size >= sizeof (*n));
 459
 460   if (map->free_nodes)
 461     {
 462       n = map->free_nodes;
 463       map->free_nodes = n->right;
 464       return n;
 465     }
 466   else
 467     return obstack_alloc (map->obstack, size);
 468 }
 469
 470
 471 static void
 472 splay_obstack_free (void *obj, void *closure)
 473 {
 474   struct addrmap_mutable *map = closure;
 475   splay_tree_node n = obj;
 476
 477   /* We've asserted in the allocation function that we only allocate
 478      nodes or larger things, so it should be safe to put whatever
 479      we get passed back on the free list.  */
 480   n->right = map->free_nodes;
 481   map->free_nodes = n;
 482 }
 483
 484
 485 /* Compare keys as CORE_ADDR * values.  */
 486 static int
 487 splay_compare_CORE_ADDR_ptr (splay_tree_key ak, splay_tree_key bk)
 488 {
 489   CORE_ADDR a = * (CORE_ADDR *) ak;
 490   CORE_ADDR b = * (CORE_ADDR *) bk;
 491
 492   /* We can't just return a-b here, because of over/underflow.  */
 493   if (a < b)
 494     return -1;
 495   else if (a == b)
 496     return 0;
 497   else
 498     return 1;
 499 }
 500
 501
 502 struct addrmap *
 503 addrmap_create_mutable (struct obstack *obstack)
 504 {
 505   struct addrmap_mutable *map = obstack_alloc (obstack, sizeof (*map));
 506
 507   map->addrmap.funcs = &addrmap_mutable_funcs;
 508   map->obstack = obstack;
 509
 510   /* splay_tree_new_with_allocator uses the provided allocation
 511      function to allocate the main splay_tree structure itself, so our
 512      free list has to be initialized before we create the tree.  */
 513   map->free_nodes = NULL;
 514
 515   map->tree = splay_tree_new_with_allocator (splay_compare_CORE_ADDR_ptr,
 516                                              NULL, /* no delete key */
 517                                              NULL, /* no delete value */
 518                                              splay_obstack_alloc,
 519                                              splay_obstack_free,
 520                                              map);
 521
 522   return (struct addrmap *) map;
 523 }
 524
 525
 526 \f
 527 /* Initialization.  */
 528
 529 void
 530 _initialize_addrmap (void)
 531 {
 532   /* Make sure splay trees can actually hold the values we want to
 533      store in them.  */
 534   gdb_assert (sizeof (splay_tree_key) >= sizeof (CORE_ADDR *));
 535   gdb_assert (sizeof (splay_tree_value) >= sizeof (void *));
 536 }