gdb/addrmap.c

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