/* addrmap.c --- implementation of address map data structure.
- Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
+ Copyright (C) 2007-2022 Free Software Foundation, Inc.
This file is part of GDB.
along with this program. If not, see <http://www.gnu.org/licenses/>. */
#include "defs.h"
-
-#include <stdlib.h>
-
#include "splay-tree.h"
-#include "gdb_obstack.h"
+#include "gdbsupport/gdb_obstack.h"
#include "addrmap.h"
-#include "gdb_assert.h"
+#include "gdbsupport/selftest.h"
+/* Make sure splay trees can actually hold the values we want to
+ store in them. */
+gdb_static_assert (sizeof (splay_tree_key) >= sizeof (CORE_ADDR *));
+gdb_static_assert (sizeof (splay_tree_value) >= sizeof (void *));
\f
/* The "abstract class". */
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);
+ void (*set_empty) (struct addrmap *self,
+ CORE_ADDR start, CORE_ADDR end_inclusive,
+ void *obj);
+ void *(*find) (struct addrmap *self, CORE_ADDR addr);
+ struct addrmap *(*create_fixed) (struct addrmap *self,
+ struct obstack *obstack);
+ void (*relocate) (struct addrmap *self, CORE_ADDR offset);
+ int (*foreach) (struct addrmap *self, addrmap_foreach_fn fn);
};
void
addrmap_set_empty (struct addrmap *map,
- CORE_ADDR start, CORE_ADDR end_inclusive,
- void *obj)
+ CORE_ADDR start, CORE_ADDR end_inclusive,
+ void *obj)
{
map->funcs->set_empty (map, start, end_inclusive, obj);
}
}
+int
+addrmap_foreach (struct addrmap *map, addrmap_foreach_fn fn)
+{
+ return map->funcs->foreach (map, fn);
+}
\f
/* Fixed address maps. */
static void
-addrmap_fixed_set_empty (struct addrmap *this,
- CORE_ADDR start, CORE_ADDR end_inclusive,
- void *obj)
+addrmap_fixed_set_empty (struct addrmap *self,
+ CORE_ADDR start, CORE_ADDR end_inclusive,
+ void *obj)
{
internal_error (__FILE__, __LINE__,
- "addrmap_fixed_set_empty: "
- "fixed addrmaps can't be changed\n");
+ "addrmap_fixed_set_empty: "
+ "fixed addrmaps can't be changed\n");
}
static void *
-addrmap_fixed_find (struct addrmap *this, CORE_ADDR addr)
+addrmap_fixed_find (struct addrmap *self, CORE_ADDR addr)
{
- struct addrmap_fixed *map = (struct addrmap_fixed *) this;
+ struct addrmap_fixed *map = (struct addrmap_fixed *) self;
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). */
+ 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;
- }
+ {
+ 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;
+ /* 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;
+ top = mid - 1;
}
return bottom->value;
static struct addrmap *
-addrmap_fixed_create_fixed (struct addrmap *this, struct obstack *obstack)
+addrmap_fixed_create_fixed (struct addrmap *self, struct obstack *obstack)
{
internal_error (__FILE__, __LINE__,
- _("addrmap_create_fixed is not implemented yet "
- "for fixed addrmaps"));
+ _("addrmap_create_fixed is not implemented yet "
+ "for fixed addrmaps"));
}
static void
-addrmap_fixed_relocate (struct addrmap *this, CORE_ADDR offset)
+addrmap_fixed_relocate (struct addrmap *self, CORE_ADDR offset)
{
- struct addrmap_fixed *map = (struct addrmap_fixed *) this;
+ struct addrmap_fixed *map = (struct addrmap_fixed *) self;
size_t i;
for (i = 0; i < map->num_transitions; i++)
}
+static int
+addrmap_fixed_foreach (struct addrmap *self, addrmap_foreach_fn fn)
+{
+ struct addrmap_fixed *map = (struct addrmap_fixed *) self;
+ size_t i;
+
+ for (i = 0; i < map->num_transitions; i++)
+ {
+ int res = fn (map->transitions[i].addr, map->transitions[i].value);
+
+ if (res != 0)
+ return res;
+ }
+
+ return 0;
+}
+
+
static const struct addrmap_funcs addrmap_fixed_funcs =
{
addrmap_fixed_set_empty,
addrmap_fixed_find,
addrmap_fixed_create_fixed,
- addrmap_fixed_relocate
+ addrmap_fixed_relocate,
+ addrmap_fixed_foreach
};
static splay_tree_key
allocate_key (struct addrmap_mutable *map, CORE_ADDR addr)
{
- CORE_ADDR *key = obstack_alloc (map->obstack, sizeof (*key));
- *key = addr;
+ CORE_ADDR *key = XOBNEW (map->obstack, CORE_ADDR);
+ *key = addr;
return (splay_tree_key) key;
}
static void
-addrmap_splay_tree_insert (struct addrmap_mutable *map, CORE_ADDR key, void *value)
+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);
+ allocate_key (map, key),
+ (splay_tree_value) value);
}
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)
+force_transition (struct addrmap_mutable *self, CORE_ADDR addr)
{
splay_tree_node n
- = addrmap_splay_tree_lookup (this, addr);
+ = addrmap_splay_tree_lookup (self, addr);
if (! n)
{
- n = addrmap_splay_tree_predecessor (this, addr);
- addrmap_splay_tree_insert (this, addr,
- n ? addrmap_node_value (n) : NULL);
+ n = addrmap_splay_tree_predecessor (self, addr);
+ addrmap_splay_tree_insert (self, 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)
+addrmap_mutable_set_empty (struct addrmap *self,
+ CORE_ADDR start, CORE_ADDR end_inclusive,
+ void *obj)
{
- struct addrmap_mutable *map = (struct addrmap_mutable *) this;
+ struct addrmap_mutable *map = (struct addrmap_mutable *) self;
splay_tree_node n, next;
void *prior_value;
n = addrmap_splay_tree_successor (map, addrmap_node_key (n)))
{
if (! addrmap_node_value (n))
- addrmap_node_set_value (n, obj);
+ addrmap_node_set_value (n, obj);
}
/* Walk the area again, removing transitions from any value to
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);
+ || 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)
- addrmap_splay_tree_remove (map, addrmap_node_key (n));
+ addrmap_splay_tree_remove (map, addrmap_node_key (n));
else
- prior_value = addrmap_node_value (n);
+ prior_value = addrmap_node_value (n);
}
}
static void *
-addrmap_mutable_find (struct addrmap *this, CORE_ADDR addr)
+addrmap_mutable_find (struct addrmap *self, CORE_ADDR addr)
{
- /* Not needed yet. */
- internal_error (__FILE__, __LINE__,
- _("addrmap_find is not implemented yet "
- "for mutable addrmaps"));
+ struct addrmap_mutable *map = (struct addrmap_mutable *) self;
+ splay_tree_node n = addrmap_splay_tree_lookup (map, addr);
+ if (n != nullptr)
+ {
+ gdb_assert (addrmap_node_key (n) == addr);
+ return addrmap_node_value (n);
+ }
+
+ n = addrmap_splay_tree_predecessor (map, addr);
+ if (n != nullptr)
+ {
+ gdb_assert (addrmap_node_key (n) < addr);
+ return addrmap_node_value (n);
+ }
+
+ return nullptr;
}
static struct addrmap *
-addrmap_mutable_create_fixed (struct addrmap *this, struct obstack *obstack)
+addrmap_mutable_create_fixed (struct addrmap *self, struct obstack *obstack)
{
- struct addrmap_mutable *mutable = (struct addrmap_mutable *) this;
+ struct addrmap_mutable *mutable_obj = (struct addrmap_mutable *) self;
struct addrmap_fixed *fixed;
size_t num_transitions;
+ size_t alloc_len;
/* Count the number of transitions in the tree. */
num_transitions = 0;
- splay_tree_foreach (mutable->tree, splay_foreach_count, &num_transitions);
+ splay_tree_foreach (mutable_obj->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]))));
+ alloc_len = sizeof (*fixed)
+ + (num_transitions * sizeof (fixed->transitions[0]));
+ fixed = (struct addrmap_fixed *) obstack_alloc (obstack, alloc_len);
fixed->addrmap.funcs = &addrmap_fixed_funcs;
fixed->num_transitions = 1;
fixed->transitions[0].addr = 0;
/* Copy all entries from the splay tree to the array, in order
of increasing address. */
- splay_tree_foreach (mutable->tree, splay_foreach_copy, fixed);
+ splay_tree_foreach (mutable_obj->tree, splay_foreach_copy, fixed);
/* We should have filled the array. */
gdb_assert (fixed->num_transitions == num_transitions);
static void
-addrmap_mutable_relocate (struct addrmap *this, CORE_ADDR offset)
+addrmap_mutable_relocate (struct addrmap *self, CORE_ADDR offset)
{
/* Not needed yet. */
internal_error (__FILE__, __LINE__,
- _("addrmap_relocate is not implemented yet "
- "for mutable addrmaps"));
+ _("addrmap_relocate is not implemented yet "
+ "for mutable addrmaps"));
+}
+
+
+/* This is a splay_tree_foreach_fn. */
+
+static int
+addrmap_mutable_foreach_worker (splay_tree_node node, void *data)
+{
+ addrmap_foreach_fn *fn = (addrmap_foreach_fn *) data;
+
+ return (*fn) (addrmap_node_key (node), addrmap_node_value (node));
+}
+
+
+static int
+addrmap_mutable_foreach (struct addrmap *self, addrmap_foreach_fn fn)
+{
+ struct addrmap_mutable *mutable_obj = (struct addrmap_mutable *) self;
+
+ return splay_tree_foreach (mutable_obj->tree, addrmap_mutable_foreach_worker,
+ &fn);
}
addrmap_mutable_set_empty,
addrmap_mutable_find,
addrmap_mutable_create_fixed,
- addrmap_mutable_relocate
+ addrmap_mutable_relocate,
+ addrmap_mutable_foreach
};
static void *
splay_obstack_alloc (int size, void *closure)
{
- struct addrmap_mutable *map = closure;
+ struct addrmap_mutable *map = (struct addrmap_mutable *) closure;
splay_tree_node n;
/* We should only be asked to allocate nodes and larger things.
static void
splay_obstack_free (void *obj, void *closure)
{
- struct addrmap_mutable *map = closure;
- splay_tree_node n = obj;
+ struct addrmap_mutable *map = (struct addrmap_mutable *) closure;
+ splay_tree_node n = (splay_tree_node) obj;
/* We've asserted in the allocation function that we only allocate
nodes or larger things, so it should be safe to put whatever
struct addrmap *
addrmap_create_mutable (struct obstack *obstack)
{
- struct addrmap_mutable *map = obstack_alloc (obstack, sizeof (*map));
+ struct addrmap_mutable *map = XOBNEW (obstack, struct addrmap_mutable);
map->addrmap.funcs = &addrmap_mutable_funcs;
map->obstack = obstack;
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);
+ NULL, /* no delete key */
+ NULL, /* no delete value */
+ splay_obstack_alloc,
+ splay_obstack_free,
+ map);
return (struct addrmap *) map;
}
+/* See addrmap.h. */
-\f
-/* Initialization. */
+void
+addrmap_dump (struct addrmap *map, struct ui_file *outfile, void *payload)
+{
+ /* True if the previously printed addrmap entry was for PAYLOAD.
+ If so, we want to print the next one as well (since the next
+ addrmap entry defines the end of the range). */
+ bool previous_matched = false;
+
+ auto callback = [&] (CORE_ADDR start_addr, void *obj)
+ {
+ QUIT;
+
+ bool matches = payload == nullptr || payload == obj;
+ const char *addr_str = nullptr;
+ if (matches)
+ addr_str = host_address_to_string (obj);
+ else if (previous_matched)
+ addr_str = "<ends here>";
+
+ if (matches || previous_matched)
+ fprintf_filtered (outfile, " %s%s %s\n",
+ payload != nullptr ? " " : "",
+ core_addr_to_string (start_addr),
+ addr_str);
+
+ previous_matched = matches;
+
+ return 0;
+ };
+
+ addrmap_foreach (map, callback);
+}
+
+#if GDB_SELF_TEST
+namespace selftests {
+
+/* Convert P to CORE_ADDR. */
+
+static CORE_ADDR
+core_addr (void *p)
+{
+ return (CORE_ADDR)(uintptr_t)p;
+}
+
+/* Check that &ARRAY[LOW]..&ARRAY[HIGH] has VAL in MAP. */
+
+#define CHECK_ADDRMAP_FIND(MAP, ARRAY, LOW, HIGH, VAL) \
+ do \
+ { \
+ for (unsigned i = LOW; i <= HIGH; ++i) \
+ SELF_CHECK (addrmap_find (MAP, core_addr (&ARRAY[i])) == VAL); \
+ } \
+ while (0)
+
+/* Entry point for addrmap unit tests. */
+
+static void
+test_addrmap ()
+{
+ /* We'll verify using the addresses of the elements of this array. */
+ char array[20];
+
+ /* We'll verify using these values stored into the map. */
+ void *val1 = &array[1];
+ void *val2 = &array[2];
+
+ /* Create mutable addrmap. */
+ struct obstack temp_obstack;
+ obstack_init (&temp_obstack);
+ struct addrmap *map = addrmap_create_mutable (&temp_obstack);
+ SELF_CHECK (map != nullptr);
+
+ /* Check initial state. */
+ CHECK_ADDRMAP_FIND (map, array, 0, 19, nullptr);
+
+ /* Insert address range into mutable addrmap. */
+ addrmap_set_empty (map, core_addr (&array[10]), core_addr (&array[12]),
+ val1);
+ CHECK_ADDRMAP_FIND (map, array, 0, 9, nullptr);
+ CHECK_ADDRMAP_FIND (map, array, 10, 12, val1);
+ CHECK_ADDRMAP_FIND (map, array, 13, 19, nullptr);
+
+ /* Create corresponding fixed addrmap. */
+ struct addrmap *map2 = addrmap_create_fixed (map, &temp_obstack);
+ SELF_CHECK (map2 != nullptr);
+ CHECK_ADDRMAP_FIND (map2, array, 0, 9, nullptr);
+ CHECK_ADDRMAP_FIND (map2, array, 10, 12, val1);
+ CHECK_ADDRMAP_FIND (map2, array, 13, 19, nullptr);
+
+ /* Iterate over both addrmaps. */
+ auto callback = [&] (CORE_ADDR start_addr, void *obj)
+ {
+ if (start_addr == core_addr (nullptr))
+ SELF_CHECK (obj == nullptr);
+ else if (start_addr == core_addr (&array[10]))
+ SELF_CHECK (obj == val1);
+ else if (start_addr == core_addr (&array[13]))
+ SELF_CHECK (obj == nullptr);
+ else
+ SELF_CHECK (false);
+ return 0;
+ };
+ SELF_CHECK (addrmap_foreach (map, callback) == 0);
+ SELF_CHECK (addrmap_foreach (map2, callback) == 0);
+
+ /* Relocate fixed addrmap. */
+ addrmap_relocate (map2, 1);
+ CHECK_ADDRMAP_FIND (map2, array, 0, 10, nullptr);
+ CHECK_ADDRMAP_FIND (map2, array, 11, 13, val1);
+ CHECK_ADDRMAP_FIND (map2, array, 14, 19, nullptr);
+
+ /* Insert partially overlapping address range into mutable addrmap. */
+ addrmap_set_empty (map, core_addr (&array[11]), core_addr (&array[13]),
+ val2);
+ CHECK_ADDRMAP_FIND (map, array, 0, 9, nullptr);
+ CHECK_ADDRMAP_FIND (map, array, 10, 12, val1);
+ CHECK_ADDRMAP_FIND (map, array, 13, 13, val2);
+ CHECK_ADDRMAP_FIND (map, array, 14, 19, nullptr);
+
+ /* Cleanup. */
+ obstack_free (&temp_obstack, NULL);
+}
-/* Provide a prototype to silence -Wmissing-prototypes. */
-extern initialize_file_ftype _initialize_addrmap;
+} // namespace selftests
+#endif /* GDB_SELF_TEST */
+void _initialize_addrmap ();
void
-_initialize_addrmap (void)
+_initialize_addrmap ()
{
- /* 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 *));
+#if GDB_SELF_TEST
+ selftests::register_test ("addrmap", selftests::test_addrmap);
+#endif /* GDB_SELF_TEST */
}