1 /* addrmap.c --- implementation of address map data structure. 2 3 Copyright (C) 2007-2013 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 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 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 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 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 } 610