From cd55174880a4b218d9a7c12310c8ec066fe54155 Mon Sep 17 00:00:00 2001 From: Jim Blandy Date: Tue, 4 Dec 2007 23:43:57 +0000 Subject: Support lexical blocks and function bodies that occupy non-contiguous address ranges. * addrmap.c, addrmap.h: New files. * block.h (struct addrmap): New forward declaration. (struct blockvector): New member, 'map'. (BLOCKVECTOR_MAP): New accessor macro. * block.c: #include "addrmap.h" (blockvector_for_pc_sect): If the blockvector we've found has an address map, use it instead of searching the blocks. * buildsym.c: #include "addrmap.h" (pending_addrmap_obstack, pending_addrmap_interesting): New static variables. (really_free_pendings): If we have a pending addrmap, free it too. (record_block_range): New function. (make_blockvector): If we have an interesting pending addrmap, record it in the new blockvector. (start_symtab, buildsym_init): Assert that there is no pending addrmap now; we should have cleaned up any addrmaps we'd built previously. (end_symtab): If there is a pending addrmap left over that didn't get included in the blockvector, free it. * buildsym.h (struct addrmap): New forward declaration. (record_block_range): New prototype. * objfiles.c: #include "addrmap.h". (objfile_relocate): Relocate the blockvector's address map, if present. * dwarf2read.c (dwarf2_record_block_ranges): New function. (read_func_scope, read_lexical_block_scope): Call it. * Makefile.in (SFILES): Add addrmap.c. (addrmap_h): New header dependency variable. (COMMON_OBS): Add addrmap.o. (addrmap.o): New rule.l (block.o, objfiles.o, buildsym.o): Depend on $(addrmap_h). * block.c (blockvector_for_pc, blockvector_for_pc_sect): Return a pointer to the block, not its index in the blockvector. (block_for_pc_sect): Use the returned block, instead of looking it up ourselves. * block.h (blockvector_for_pc, blockvector_for_pc_sect): Update declarations. * breakpoint.c (resolve_sal_pc): Use returned block, instead of looking it up ourselves. * stack.c (print_frame_label_vars): Disable function, which depends on the block's index. * buildsym.c (finish_block): Return the block we've built. * buildsym.h (finish_block): Update prototype. * defs.h (CORE_ADDR_MAX): New constant. --- gdb/addrmap.c | 532 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 532 insertions(+) create mode 100644 gdb/addrmap.c (limited to 'gdb/addrmap.c') diff --git a/gdb/addrmap.c b/gdb/addrmap.c new file mode 100644 index 00000000000..fd800cfddba --- /dev/null +++ b/gdb/addrmap.c @@ -0,0 +1,532 @@ +/* addrmap.c --- implementation of address map data structure. + + Copyright (C) 2007 Free Software Foundation, Inc. + + This file is part of GDB. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 51 Franklin Street, Fifth Floor, + Boston, MA 02110-1301, USA. */ + +#include "defs.h" + +#include + +#include "splay-tree.h" +#include "gdb_obstack.h" +#include "addrmap.h" +#include "gdb_assert.h" + + + +/* The "abstract class". */ + +/* Functions implementing the addrmap functions for a particular + implementation. */ +struct addrmap_funcs +{ + void (*set_empty) (struct addrmap *this, + CORE_ADDR start, CORE_ADDR end_inclusive, + void *obj); + void *(*find) (struct addrmap *this, CORE_ADDR addr); + struct addrmap *(*create_fixed) (struct addrmap *this, + struct obstack *obstack); + void (*relocate) (struct addrmap *this, CORE_ADDR offset); +}; + + +struct addrmap +{ + struct addrmap_funcs *funcs; +}; + + +void +addrmap_set_empty (struct addrmap *map, + CORE_ADDR start, CORE_ADDR end_inclusive, + void *obj) +{ + map->funcs->set_empty (map, start, end_inclusive, obj); +} + + +void * +addrmap_find (struct addrmap *map, CORE_ADDR addr) +{ + return map->funcs->find (map, addr); +} + + +struct addrmap * +addrmap_create_fixed (struct addrmap *original, struct obstack *obstack) +{ + return original->funcs->create_fixed (original, obstack); +} + + +/* Relocate all the addresses in MAP by OFFSET. (This can be applied + to either mutable or immutable maps.) */ +void +addrmap_relocate (struct addrmap *map, CORE_ADDR offset) +{ + map->funcs->relocate (map, offset); +} + + + +/* Fixed address maps. */ + +/* A transition: a point in an address map where the value changes. + The map maps ADDR to VALUE, but if ADDR > 0, it maps ADDR-1 to + something else. */ +struct addrmap_transition +{ + CORE_ADDR addr; + void *value; +}; + + +struct addrmap_fixed +{ + struct addrmap addrmap; + + /* The number of transitions in TRANSITIONS. */ + size_t num_transitions; + + /* An array of transitions, sorted by address. For every point in + the map where either ADDR == 0 or ADDR is mapped to one value and + ADDR - 1 is mapped to something different, we have an entry here + containing ADDR and VALUE. (Note that this means we always have + an entry for address 0). */ + struct addrmap_transition transitions[1]; +}; + + +static void +addrmap_fixed_set_empty (struct addrmap *this, + CORE_ADDR start, CORE_ADDR end_inclusive, + void *obj) +{ + internal_error (__FILE__, __LINE__, + "addrmap_fixed_set_empty: " + "fixed addrmaps can't be changed\n"); +} + + +static void * +addrmap_fixed_find (struct addrmap *this, CORE_ADDR addr) +{ + struct addrmap_fixed *map = (struct addrmap_fixed *) this; + struct addrmap_transition *bottom = &map->transitions[0]; + struct addrmap_transition *top = &map->transitions[map->num_transitions - 1]; + + while (bottom < top) + { + /* This needs to round towards top, or else when top = bottom + + 1 (i.e., two entries are under consideration), then mid == + bottom, and then we may not narrow the range when (mid->addr + < addr). */ + struct addrmap_transition *mid = top - (top - bottom) / 2; + + if (mid->addr == addr) + { + bottom = mid; + break; + } + else if (mid->addr < addr) + /* We don't eliminate mid itself here, since each transition + covers all subsequent addresses until the next. This is why + we must round up in computing the midpoint. */ + bottom = mid; + else + top = mid - 1; + } + + return bottom->value; +} + + +static struct addrmap * +addrmap_fixed_create_fixed (struct addrmap *this, struct obstack *obstack) +{ + abort (); +} + + +static void +addrmap_fixed_relocate (struct addrmap *this, CORE_ADDR offset) +{ + struct addrmap_fixed *map = (struct addrmap_fixed *) this; + size_t i; + + for (i = 0; i < map->num_transitions; i++) + map->transitions[i].addr += offset; +} + + +static struct addrmap_funcs addrmap_fixed_funcs = +{ + .set_empty = addrmap_fixed_set_empty, + .find = addrmap_fixed_find, + .create_fixed = addrmap_fixed_create_fixed, + .relocate = addrmap_fixed_relocate +}; + + + +/* Mutable address maps. */ + +struct addrmap_mutable +{ + struct addrmap addrmap; + + /* The obstack to use for allocations for this map. */ + struct obstack *obstack; + + /* A splay tree, with a node for each transition; there is a + transition at address T if T-1 and T map to different objects. + + Any addresses below the first node map to NULL. (Unlike + fixed maps, we have no entry at (CORE_ADDR) 0; it doesn't + simplify enough.) + + The last region is assumed to end at CORE_ADDR_MAX. + + Since we can't know whether CORE_ADDR is larger or smaller than + splay_tree_key (unsigned long) --- I think both are possible, + given all combinations of 32- and 64-bit hosts and targets --- + our keys are pointers to CORE_ADDR values. Since the splay tree + library doesn't pass any closure pointer to the key free + function, we can't keep a freelist for keys. Since mutable + addrmaps are only used temporarily right now, we just leak keys + from deleted nodes; they'll be freed when the obstack is freed. */ + splay_tree tree; + + /* A freelist for splay tree nodes, allocated on obstack, and + chained together by their 'right' pointers. */ + splay_tree_node free_nodes; +}; + + +/* Allocate a copy of CORE_ADDR in MAP's obstack. */ +static splay_tree_key +allocate_key (struct addrmap_mutable *map, CORE_ADDR addr) +{ + CORE_ADDR *key = obstack_alloc (map->obstack, sizeof (*key)); + *key = addr; + + return (splay_tree_key) key; +} + + +/* Type-correct wrappers for splay tree access. */ +static splay_tree_node +addrmap_splay_tree_lookup (struct addrmap_mutable *map, CORE_ADDR addr) +{ + return splay_tree_lookup (map->tree, (splay_tree_key) &addr); +} + + +static splay_tree_node +addrmap_splay_tree_predecessor (struct addrmap_mutable *map, CORE_ADDR addr) +{ + return splay_tree_predecessor (map->tree, (splay_tree_key) &addr); +} + + +static splay_tree_node +addrmap_splay_tree_successor (struct addrmap_mutable *map, CORE_ADDR addr) +{ + return splay_tree_successor (map->tree, (splay_tree_key) &addr); +} + + +static CORE_ADDR +addrmap_node_key (splay_tree_node node) +{ + return * (CORE_ADDR *) node->key; +} + + +static void * +addrmap_node_value (splay_tree_node node) +{ + return (void *) node->value; +} + + +static void +addrmap_node_set_value (splay_tree_node node, void *value) +{ + node->value = (splay_tree_value) value; +} + + +static void +addrmap_splay_tree_insert (struct addrmap_mutable *map, CORE_ADDR key, void *value) +{ + splay_tree_insert (map->tree, + allocate_key (map, key), + (splay_tree_value) value); +} + + +/* Without changing the mapping of any address, ensure that there is a + tree node at ADDR, even if it would represent a "transition" from + one value to the same value. */ +static void +force_transition (struct addrmap_mutable *this, CORE_ADDR addr) +{ + splay_tree_node n + = addrmap_splay_tree_lookup (this, addr); + + if (! n) + { + n = addrmap_splay_tree_predecessor (this, addr); + addrmap_splay_tree_insert (this, addr, + n ? addrmap_node_value (n) : NULL); + } +} + + +static void +addrmap_mutable_set_empty (struct addrmap *this, + CORE_ADDR start, CORE_ADDR end_inclusive, + void *obj) +{ + struct addrmap_mutable *map = (struct addrmap_mutable *) this; + splay_tree_node n, next; + void *prior_value; + + /* If we're being asked to set all empty portions of the given + address range to empty, then probably the caller is confused. + (If that turns out to be useful in some cases, then we can change + this to simply return, since overriding NULL with NULL is a + no-op.) */ + gdb_assert (obj); + + /* We take a two-pass approach, for simplicity. + - Establish transitions where we think we might need them. + - First pass: change all NULL regions to OBJ. + - Second pass: remove any unnecessary transitions. */ + + /* Establish transitions at the start and end. */ + force_transition (map, start); + if (end_inclusive < CORE_ADDR_MAX) + force_transition (map, end_inclusive + 1); + + /* Walk the area, changing all NULL regions to OBJ. */ + for (n = addrmap_splay_tree_lookup (map, start), gdb_assert (n); + n && addrmap_node_key (n) <= end_inclusive; + n = addrmap_splay_tree_successor (map, addrmap_node_key (n))) + { + if (! addrmap_node_value (n)) + addrmap_node_set_value (n, obj); + } + + /* Walk the area again, removing transitions from any value to + itself. Be sure to visit both the transitions we forced + above. */ + n = addrmap_splay_tree_predecessor (map, start); + prior_value = n ? addrmap_node_value (n) : NULL; + for (n = addrmap_splay_tree_lookup (map, start), gdb_assert (n); + n && (end_inclusive == CORE_ADDR_MAX + || addrmap_node_key (n) <= end_inclusive + 1); + n = next) + { + next = addrmap_splay_tree_successor (map, addrmap_node_key (n)); + if (addrmap_node_value (n) == prior_value) + splay_tree_remove (map->tree, addrmap_node_key (n)); + else + prior_value = addrmap_node_value (n); + } +} + + +static void * +addrmap_mutable_find (struct addrmap *this, CORE_ADDR addr) +{ + /* Not needed yet. */ + abort (); +} + + +/* A function to pass to splay_tree_foreach to count the number of nodes + in the tree. */ +static int +splay_foreach_count (splay_tree_node n, void *closure) +{ + size_t *count = (size_t *) closure; + + (*count)++; + return 0; +} + + +/* A function to pass to splay_tree_foreach to copy entries into a + fixed address map. */ +static int +splay_foreach_copy (splay_tree_node n, void *closure) +{ + struct addrmap_fixed *fixed = (struct addrmap_fixed *) closure; + struct addrmap_transition *t = &fixed->transitions[fixed->num_transitions]; + + t->addr = addrmap_node_key (n); + t->value = addrmap_node_value (n); + fixed->num_transitions++; + + return 0; +} + + +static struct addrmap * +addrmap_mutable_create_fixed (struct addrmap *this, struct obstack *obstack) +{ + struct addrmap_mutable *mutable = (struct addrmap_mutable *) this; + struct addrmap_fixed *fixed; + size_t num_transitions; + + /* Count the number of transitions in the tree. */ + num_transitions = 0; + splay_tree_foreach (mutable->tree, splay_foreach_count, &num_transitions); + + /* Include an extra entry for the transition at zero (which fixed + maps have, but mutable maps do not.) */ + num_transitions++; + + fixed = obstack_alloc (obstack, + (sizeof (*fixed) + + (num_transitions + * sizeof (fixed->transitions[0])))); + fixed->addrmap.funcs = &addrmap_fixed_funcs; + fixed->num_transitions = 1; + fixed->transitions[0].addr = 0; + fixed->transitions[0].value = NULL; + + /* Copy all entries from the splay tree to the array, in order + of increasing address. */ + splay_tree_foreach (mutable->tree, splay_foreach_copy, fixed); + + /* We should have filled the array. */ + gdb_assert (fixed->num_transitions == num_transitions); + + return (struct addrmap *) fixed; +} + + +static void +addrmap_mutable_relocate (struct addrmap *this, CORE_ADDR offset) +{ + /* Not needed yet. */ + abort (); +} + + +static struct addrmap_funcs addrmap_mutable_funcs = +{ + .set_empty = addrmap_mutable_set_empty, + .find = addrmap_mutable_find, + .create_fixed = addrmap_mutable_create_fixed, + .relocate = addrmap_mutable_relocate +}; + + +static void * +splay_obstack_alloc (int size, void *closure) +{ + struct addrmap_mutable *map = closure; + splay_tree_node n; + + /* We should only be asked to allocate nodes and larger things. + (If, at some point in the future, this is no longer true, we can + just round up the size to sizeof (*n).) */ + gdb_assert (size >= sizeof (*n)); + + if (map->free_nodes) + { + n = map->free_nodes; + map->free_nodes = n->right; + return n; + } + else + return obstack_alloc (map->obstack, size); +} + + +static void +splay_obstack_free (void *obj, void *closure) +{ + struct addrmap_mutable *map = closure; + splay_tree_node n = obj; + + /* We've asserted in the allocation function that we only allocate + nodes or larger things, so it should be safe to put whatever + we get passed back on the free list. */ + n->right = map->free_nodes; + map->free_nodes = n; +} + + +/* Compare keys as CORE_ADDR * values. */ +static int +splay_compare_CORE_ADDR_ptr (splay_tree_key ak, splay_tree_key bk) +{ + CORE_ADDR a = * (CORE_ADDR *) ak; + CORE_ADDR b = * (CORE_ADDR *) bk; + + /* We can't just return a-b here, because of over/underflow. */ + if (a < b) + return -1; + else if (a == b) + return 0; + else + return 1; +} + + +struct addrmap * +addrmap_create_mutable (struct obstack *obstack) +{ + struct addrmap_mutable *map = obstack_alloc (obstack, sizeof (*map)); + + map->addrmap.funcs = &addrmap_mutable_funcs; + map->obstack = obstack; + + /* splay_tree_new_with_allocator uses the provided allocation + function to allocate the main splay_tree structure itself, so our + free list has to be initialized before we create the tree. */ + map->free_nodes = NULL; + + map->tree = splay_tree_new_with_allocator (splay_compare_CORE_ADDR_ptr, + NULL, /* no delete key */ + NULL, /* no delete value */ + splay_obstack_alloc, + splay_obstack_free, + map); + + return (struct addrmap *) map; +} + + + +/* Initialization. */ + +void +_initialize_addrmap (void) +{ + /* Make sure splay trees can actually hold the values we want to + store in them. */ + gdb_assert (sizeof (splay_tree_key) >= sizeof (CORE_ADDR *)); + gdb_assert (sizeof (splay_tree_value) >= sizeof (void *)); +} -- cgit v1.2.1