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, CORE_ADDR key, void *value)
 311 {
 312   splay_tree_insert (map->tree,
 313                      allocate_key (map, key),
 314                      (splay_tree_value) value);
 315 }
 316
 317
 318 /* Without changing the mapping of any address, ensure that there is a
 319    tree node at ADDR, even if it would represent a "transition" from
 320    one value to the same value.  */
 321 static void
 322 force_transition (struct addrmap_mutable *this, CORE_ADDR addr)
 323 {
 324   splay_tree_node n
 325     = addrmap_splay_tree_lookup (this, addr);
 326
 327   if (! n)
 328     {
 329       n = addrmap_splay_tree_predecessor (this, addr);
 330       addrmap_splay_tree_insert (this, addr,
 331                                  n ? addrmap_node_value (n) : NULL);
 332     }
 333 }
 334
 335
 336 static void
 337 addrmap_mutable_set_empty (struct addrmap *this,
 338                            CORE_ADDR start, CORE_ADDR end_inclusive,
 339                            void *obj)
 340 {
 341   struct addrmap_mutable *map = (struct addrmap_mutable *) this;
 342   splay_tree_node n, next;
 343   void *prior_value;
 344
 345   /* If we're being asked to set all empty portions of the given
 346      address range to empty, then probably the caller is confused.
 347      (If that turns out to be useful in some cases, then we can change
 348      this to simply return, since overriding NULL with NULL is a
 349      no-op.)  */
 350   gdb_assert (obj);
 351
 352   /* We take a two-pass approach, for simplicity.
 353      - Establish transitions where we think we might need them.
 354      - First pass: change all NULL regions to OBJ.
 355      - Second pass: remove any unnecessary transitions.  */
 356
 357   /* Establish transitions at the start and end.  */
 358   force_transition (map, start);
 359   if (end_inclusive < CORE_ADDR_MAX)
 360     force_transition (map, end_inclusive + 1);
 361
 362   /* Walk the area, changing all NULL regions to OBJ.  */
 363   for (n = addrmap_splay_tree_lookup (map, start), gdb_assert (n);
 364        n && addrmap_node_key (n) <= end_inclusive;
 365        n = addrmap_splay_tree_successor (map, addrmap_node_key (n)))
 366     {
 367       if (! addrmap_node_value (n))
 368         addrmap_node_set_value (n, obj);
 369     }
 370
 371   /* Walk the area again, removing transitions from any value to
 372      itself.  Be sure to visit both the transitions we forced
 373      above.  */
 374   n = addrmap_splay_tree_predecessor (map, start);
 375   prior_value = n ? addrmap_node_value (n) : NULL;
 376   for (n = addrmap_splay_tree_lookup (map, start), gdb_assert (n);
 377        n && (end_inclusive == CORE_ADDR_MAX
 378              || addrmap_node_key (n) <= end_inclusive + 1);
 379        n = next)
 380     {
 381       next = addrmap_splay_tree_successor (map, addrmap_node_key (n));
 382       if (addrmap_node_value (n) == prior_value)
 383         addrmap_splay_tree_remove (map, addrmap_node_key (n));
 384       else
 385         prior_value = addrmap_node_value (n);
 386     }
 387 }
 388
 389
 390 static void *
 391 addrmap_mutable_find (struct addrmap *this, CORE_ADDR addr)
 392 {
 393   /* Not needed yet.  */
 394   internal_error (__FILE__, __LINE__,
 395                   _("addrmap_find is not implemented yet "
 396                     "for mutable addrmaps"));
 397 }
 398
 399
 400 /* A function to pass to splay_tree_foreach to count the number of nodes
 401    in the tree.  */
 402 static int
 403 splay_foreach_count (splay_tree_node n, void *closure)
 404 {
 405   size_t *count = (size_t *) closure;
 406
 407   (*count)++;
 408   return 0;
 409 }
 410
 411
 412 /* A function to pass to splay_tree_foreach to copy entries into a
 413    fixed address map.  */
 414 static int
 415 splay_foreach_copy (splay_tree_node n, void *closure)
 416 {
 417   struct addrmap_fixed *fixed = (struct addrmap_fixed *) closure;
 418   struct addrmap_transition *t = &fixed->transitions[fixed->num_transitions];
 419
 420   t->addr = addrmap_node_key (n);
 421   t->value = addrmap_node_value (n);
 422   fixed->num_transitions++;
 423
 424   return 0;
 425 }
 426
 427
 428 static struct addrmap *
 429 addrmap_mutable_create_fixed (struct addrmap *this, struct obstack *obstack)
 430 {
 431   struct addrmap_mutable *mutable = (struct addrmap_mutable *) this;
 432   struct addrmap_fixed *fixed;
 433   size_t num_transitions;
 434
 435   /* Count the number of transitions in the tree.  */
 436   num_transitions = 0;
 437   splay_tree_foreach (mutable->tree, splay_foreach_count, &num_transitions);
 438
 439   /* Include an extra entry for the transition at zero (which fixed
 440      maps have, but mutable maps do not.)  */
 441   num_transitions++;
 442
 443   fixed = obstack_alloc (obstack,
 444                          (sizeof (*fixed)
 445                           + (num_transitions
 446                              * sizeof (fixed->transitions[0]))));
 447   fixed->addrmap.funcs = &addrmap_fixed_funcs;
 448   fixed->num_transitions = 1;
 449   fixed->transitions[0].addr = 0;
 450   fixed->transitions[0].value = NULL;
 451
 452   /* Copy all entries from the splay tree to the array, in order
 453      of increasing address.  */
 454   splay_tree_foreach (mutable->tree, splay_foreach_copy, fixed);
 455
 456   /* We should have filled the array.  */
 457   gdb_assert (fixed->num_transitions == num_transitions);
 458
 459   return (struct addrmap *) fixed;
 460 }
 461
 462
 463 static void
 464 addrmap_mutable_relocate (struct addrmap *this, CORE_ADDR offset)
 465 {
 466   /* Not needed yet.  */
 467   internal_error (__FILE__, __LINE__,
 468                   _("addrmap_relocate is not implemented yet "
 469                     "for mutable addrmaps"));
 470 }
 471
 472
 473 /* Struct to map addrmap's foreach function to splay_tree's version.  */
 474 struct mutable_foreach_data
 475 {
 476   addrmap_foreach_fn fn;
 477   void *data;
 478 };
 479
 480
 481 /* This is a splay_tree_foreach_fn.  */
 482
 483 static int
 484 addrmap_mutable_foreach_worker (splay_tree_node node, void *data)
 485 {
 486   struct mutable_foreach_data *foreach_data = data;
 487
 488   return foreach_data->fn (foreach_data->data,
 489                            addrmap_node_key (node),
 490                            addrmap_node_value (node));
 491 }
 492
 493
 494 static int
 495 addrmap_mutable_foreach (struct addrmap *this, addrmap_foreach_fn fn,
 496                          void *data)
 497 {
 498   struct addrmap_mutable *mutable = (struct addrmap_mutable *) this;
 499   struct mutable_foreach_data foreach_data;
 500
 501   foreach_data.fn = fn;
 502   foreach_data.data = data;
 503   return splay_tree_foreach (mutable->tree, addrmap_mutable_foreach_worker,
 504                              &foreach_data);
 505 }
 506
 507
 508 static const struct addrmap_funcs addrmap_mutable_funcs =
 509 {
 510   addrmap_mutable_set_empty,
 511   addrmap_mutable_find,
 512   addrmap_mutable_create_fixed,
 513   addrmap_mutable_relocate,
 514   addrmap_mutable_foreach
 515 };
 516
 517
 518 static void *
 519 splay_obstack_alloc (int size, void *closure)
 520 {
 521   struct addrmap_mutable *map = closure;
 522   splay_tree_node n;
 523
 524   /* We should only be asked to allocate nodes and larger things.
 525      (If, at some point in the future, this is no longer true, we can
 526      just round up the size to sizeof (*n).)  */
 527   gdb_assert (size >= sizeof (*n));
 528
 529   if (map->free_nodes)
 530     {
 531       n = map->free_nodes;
 532       map->free_nodes = n->right;
 533       return n;
 534     }
 535   else
 536     return obstack_alloc (map->obstack, size);
 537 }
 538
 539
 540 static void
 541 splay_obstack_free (void *obj, void *closure)
 542 {
 543   struct addrmap_mutable *map = closure;
 544   splay_tree_node n = obj;
 545
 546   /* We've asserted in the allocation function that we only allocate
 547      nodes or larger things, so it should be safe to put whatever
 548      we get passed back on the free list.  */
 549   n->right = map->free_nodes;
 550   map->free_nodes = n;
 551 }
 552
 553
 554 /* Compare keys as CORE_ADDR * values.  */
 555 static int
 556 splay_compare_CORE_ADDR_ptr (splay_tree_key ak, splay_tree_key bk)
 557 {
 558   CORE_ADDR a = * (CORE_ADDR *) ak;
 559   CORE_ADDR b = * (CORE_ADDR *) bk;
 560
 561   /* We can't just return a-b here, because of over/underflow.  */
 562   if (a < b)
 563     return -1;
 564   else if (a == b)
 565     return 0;
 566   else
 567     return 1;
 568 }
 569
 570
 571 struct addrmap *
 572 addrmap_create_mutable (struct obstack *obstack)
 573 {
 574   struct addrmap_mutable *map = obstack_alloc (obstack, sizeof (*map));
 575
 576   map->addrmap.funcs = &addrmap_mutable_funcs;
 577   map->obstack = obstack;
 578
 579   /* splay_tree_new_with_allocator uses the provided allocation
 580      function to allocate the main splay_tree structure itself, so our
 581      free list has to be initialized before we create the tree.  */
 582   map->free_nodes = NULL;
 583
 584   map->tree = splay_tree_new_with_allocator (splay_compare_CORE_ADDR_ptr,
 585                                              NULL, /* no delete key */
 586                                              NULL, /* no delete value */
 587                                              splay_obstack_alloc,
 588                                              splay_obstack_free,
 589                                              map);
 590
 591   return (struct addrmap *) map;
 592 }
 593
 594
 595 \f
 596 /* Initialization.  */
 597
 598 /* Provide a prototype to silence -Wmissing-prototypes.  */
 599 extern initialize_file_ftype _initialize_addrmap;
 600
 601 void
 602 _initialize_addrmap (void)
 603 {
 604   /* Make sure splay trees can actually hold the values we want to
 605      store in them.  */
 606   gdb_assert (sizeof (splay_tree_key) >= sizeof (CORE_ADDR *));
 607   gdb_assert (sizeof (splay_tree_value) >= sizeof (void *));
 608 }