gdb/addrmap.c

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