aboutsummaryrefslogtreecommitdiff
path: root/gdb/addrmap.c
diff options
context:
space:
mode:
authorJim Blandy <jimb@codesourcery.com>2007-12-04 23:43:57 +0000
committerJim Blandy <jimb@codesourcery.com>2007-12-04 23:43:57 +0000
commit801e3a5b5681c44b2fec1b392dddec386870647c (patch)
treefc5540169fef73f5721542765234f47023c7763d /gdb/addrmap.c
parentc420411fe81ad583b2154fd9338fd0076761d99d (diff)
downloadgdb-801e3a5b5681c44b2fec1b392dddec386870647c.zip
gdb-801e3a5b5681c44b2fec1b392dddec386870647c.tar.gz
gdb-801e3a5b5681c44b2fec1b392dddec386870647c.tar.bz2
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.
Diffstat (limited to 'gdb/addrmap.c')
-rw-r--r--gdb/addrmap.c532
1 files changed, 532 insertions, 0 deletions
diff --git a/gdb/addrmap.c b/gdb/addrmap.c
new file mode 100644
index 0000000..fd800cf
--- /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 <stdlib.h>
+
+#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 *));
+}