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