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 2 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, write to the Free Software
  19    Foundation, Inc., 51 Franklin Street, Fifth Floor,
  20    Boston, MA 02110-1301, USA.  */
  21
  22 #include "defs.h"
  23
  24 #include <stdlib.h>
  25
  26 #include "splay-tree.h"
  27 #include "gdb_obstack.h"
  28 #include "addrmap.h"
  29 #include "gdb_assert.h"
  30
  31
  32 \f
  33 /* The "abstract class".  */
  34
  35 /* Functions implementing the addrmap functions for a particular
  36    implementation.  */
  37 struct addrmap_funcs
  38 {
  39   void (*set_empty) (struct addrmap *this,
  40                      CORE_ADDR start, CORE_ADDR end_inclusive,
  41                      void *obj);
  42   void *(*find) (struct addrmap *this, CORE_ADDR addr);
  43   struct addrmap *(*create_fixed) (struct addrmap *this,
  44                                    struct obstack *obstack);
  45   void (*relocate) (struct addrmap *this, CORE_ADDR offset);
  46 };
  47
  48
  49 struct addrmap
  50 {
  51   struct addrmap_funcs *funcs;
  52 };
  53
  54
  55 void
  56 addrmap_set_empty (struct addrmap *map,
  57                    CORE_ADDR start, CORE_ADDR end_inclusive,
  58                    void *obj)
  59 {
  60   map->funcs->set_empty (map, start, end_inclusive, obj);
  61 }
  62
  63
  64 void *
  65 addrmap_find (struct addrmap *map, CORE_ADDR addr)
  66 {
  67   return map->funcs->find (map, addr);
  68 }
  69
  70
  71 struct addrmap *
  72 addrmap_create_fixed (struct addrmap *original, struct obstack *obstack)
  73 {
  74   return original->funcs->create_fixed (original, obstack);
  75 }
  76
  77
  78 /* Relocate all the addresses in MAP by OFFSET.  (This can be applied
  79    to either mutable or immutable maps.)  */
  80 void
  81 addrmap_relocate (struct addrmap *map, CORE_ADDR offset)
  82 {
  83   map->funcs->relocate (map, offset);
  84 }
  85
  86
  87 \f
  88 /* Fixed address maps.  */
  89
  90 /* A transition: a point in an address map where the value changes.
  91    The map maps ADDR to VALUE, but if ADDR > 0, it maps ADDR-1 to
  92    something else.  */
  93 struct addrmap_transition
  94 {
  95   CORE_ADDR addr;
  96   void *value;
  97 };
  98
  99
 100 struct addrmap_fixed
 101 {
 102   struct addrmap addrmap;
 103
 104   /* The number of transitions in TRANSITIONS.  */
 105   size_t num_transitions;
 106
 107   /* An array of transitions, sorted by address.  For every point in
 108      the map where either ADDR == 0 or ADDR is mapped to one value and
 109      ADDR - 1 is mapped to something different, we have an entry here
 110      containing ADDR and VALUE.  (Note that this means we always have
 111      an entry for address 0).  */
 112   struct addrmap_transition transitions[1];
 113 };
 114
 115
 116 static void
 117 addrmap_fixed_set_empty (struct addrmap *this,
 118                    CORE_ADDR start, CORE_ADDR end_inclusive,
 119                    void *obj)
 120 {
 121   internal_error (__FILE__, __LINE__,
 122                   "addrmap_fixed_set_empty: "
 123                   "fixed addrmaps can't be changed\n");
 124 }
 125
 126
 127 static void *
 128 addrmap_fixed_find (struct addrmap *this, CORE_ADDR addr)
 129 {
 130   struct addrmap_fixed *map = (struct addrmap_fixed *) this;
 131   struct addrmap_transition *bottom = &map->transitions[0];
 132   struct addrmap_transition *top = &map->transitions[map->num_transitions - 1];
 133
 134   while (bottom < top)
 135     {
 136       /* This needs to round towards top, or else when top = bottom +
 137          1 (i.e., two entries are under consideration), then mid ==
 138          bottom, and then we may not narrow the range when (mid->addr
 139          < addr).  */
 140       struct addrmap_transition *mid = top - (top - bottom) / 2;
 141
 142       if (mid->addr == addr)
 143         {
 144           bottom = mid;
 145           break;
 146         }
 147       else if (mid->addr < addr)
 148         /* We don't eliminate mid itself here, since each transition
 149            covers all subsequent addresses until the next.  This is why
 150            we must round up in computing the midpoint.  */
 151         bottom = mid;
 152       else
 153         top = mid - 1;
 154     }
 155
 156   return bottom->value;
 157 }
 158
 159
 160 static struct addrmap *
 161 addrmap_fixed_create_fixed (struct addrmap *this, struct obstack *obstack)
 162 {
 163   abort ();
 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 struct addrmap_funcs addrmap_fixed_funcs =
 179 {
 180   .set_empty    = addrmap_fixed_set_empty,
 181   .find         = addrmap_fixed_find,
 182   .create_fixed = addrmap_fixed_create_fixed,
 183   .relocate     = 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   abort ();
 362 }
 363
 364
 365 /* A function to pass to splay_tree_foreach to count the number of nodes
 366    in the tree.  */
 367 static int
 368 splay_foreach_count (splay_tree_node n, void *closure)
 369 {
 370   size_t *count = (size_t *) closure;
 371
 372   (*count)++;
 373   return 0;
 374 }
 375
 376
 377 /* A function to pass to splay_tree_foreach to copy entries into a
 378    fixed address map.  */
 379 static int
 380 splay_foreach_copy (splay_tree_node n, void *closure)
 381 {
 382   struct addrmap_fixed *fixed = (struct addrmap_fixed *) closure;
 383   struct addrmap_transition *t = &fixed->transitions[fixed->num_transitions];
 384
 385   t->addr = addrmap_node_key (n);
 386   t->value = addrmap_node_value (n);
 387   fixed->num_transitions++;
 388
 389   return 0;
 390 }
 391
 392
 393 static struct addrmap *
 394 addrmap_mutable_create_fixed (struct addrmap *this, struct obstack *obstack)
 395 {
 396   struct addrmap_mutable *mutable = (struct addrmap_mutable *) this;
 397   struct addrmap_fixed *fixed;
 398   size_t num_transitions;
 399
 400   /* Count the number of transitions in the tree.  */
 401   num_transitions = 0;
 402   splay_tree_foreach (mutable->tree, splay_foreach_count, &num_transitions);
 403
 404   /* Include an extra entry for the transition at zero (which fixed
 405      maps have, but mutable maps do not.)  */
 406   num_transitions++;
 407
 408   fixed = obstack_alloc (obstack,
 409                          (sizeof (*fixed)
 410                           + (num_transitions
 411                              * sizeof (fixed->transitions[0]))));
 412   fixed->addrmap.funcs = &addrmap_fixed_funcs;
 413   fixed->num_transitions = 1;
 414   fixed->transitions[0].addr = 0;
 415   fixed->transitions[0].value = NULL;
 416
 417   /* Copy all entries from the splay tree to the array, in order
 418      of increasing address.  */
 419   splay_tree_foreach (mutable->tree, splay_foreach_copy, fixed);
 420
 421   /* We should have filled the array.  */
 422   gdb_assert (fixed->num_transitions == num_transitions);
 423
 424   return (struct addrmap *) fixed;
 425 }
 426
 427
 428 static void
 429 addrmap_mutable_relocate (struct addrmap *this, CORE_ADDR offset)
 430 {
 431   /* Not needed yet.  */
 432   abort ();
 433 }
 434
 435
 436 static struct addrmap_funcs addrmap_mutable_funcs =
 437 {
 438   .set_empty    = addrmap_mutable_set_empty,
 439   .find         = addrmap_mutable_find,
 440   .create_fixed = addrmap_mutable_create_fixed,
 441   .relocate     = addrmap_mutable_relocate
 442 };
 443
 444
 445 static void *
 446 splay_obstack_alloc (int size, void *closure)
 447 {
 448   struct addrmap_mutable *map = closure;
 449   splay_tree_node n;
 450
 451   /* We should only be asked to allocate nodes and larger things.
 452      (If, at some point in the future, this is no longer true, we can
 453      just round up the size to sizeof (*n).)  */
 454   gdb_assert (size >= sizeof (*n));
 455
 456   if (map->free_nodes)
 457     {
 458       n = map->free_nodes;
 459       map->free_nodes = n->right;
 460       return n;
 461     }
 462   else
 463     return obstack_alloc (map->obstack, size);
 464 }
 465
 466
 467 static void
 468 splay_obstack_free (void *obj, void *closure)
 469 {
 470   struct addrmap_mutable *map = closure;
 471   splay_tree_node n = obj;
 472
 473   /* We've asserted in the allocation function that we only allocate
 474      nodes or larger things, so it should be safe to put whatever
 475      we get passed back on the free list.  */
 476   n->right = map->free_nodes;
 477   map->free_nodes = n;
 478 }
 479
 480
 481 /* Compare keys as CORE_ADDR * values.  */
 482 static int
 483 splay_compare_CORE_ADDR_ptr (splay_tree_key ak, splay_tree_key bk)
 484 {
 485   CORE_ADDR a = * (CORE_ADDR *) ak;
 486   CORE_ADDR b = * (CORE_ADDR *) bk;
 487
 488   /* We can't just return a-b here, because of over/underflow.  */
 489   if (a < b)
 490     return -1;
 491   else if (a == b)
 492     return 0;
 493   else
 494     return 1;
 495 }
 496
 497
 498 struct addrmap *
 499 addrmap_create_mutable (struct obstack *obstack)
 500 {
 501   struct addrmap_mutable *map = obstack_alloc (obstack, sizeof (*map));
 502
 503   map->addrmap.funcs = &addrmap_mutable_funcs;
 504   map->obstack = obstack;
 505
 506   /* splay_tree_new_with_allocator uses the provided allocation
 507      function to allocate the main splay_tree structure itself, so our
 508      free list has to be initialized before we create the tree.  */
 509   map->free_nodes = NULL;
 510
 511   map->tree = splay_tree_new_with_allocator (splay_compare_CORE_ADDR_ptr,
 512                                              NULL, /* no delete key */
 513                                              NULL, /* no delete value */
 514                                              splay_obstack_alloc,
 515                                              splay_obstack_free,
 516                                              map);
 517
 518   return (struct addrmap *) map;
 519 }
 520
 521
 522 \f
 523 /* Initialization.  */
 524
 525 void
 526 _initialize_addrmap (void)
 527 {
 528   /* Make sure splay trees can actually hold the values we want to
 529      store in them.  */
 530   gdb_assert (sizeof (splay_tree_key) >= sizeof (CORE_ADDR *));
 531   gdb_assert (sizeof (splay_tree_value) >= sizeof (void *));
 532 }