1 /* addrmap.c --- implementation of address map data structure.
3 Copyright (C) 2007-2024 Free Software Foundation, Inc.
5 This file is part of GDB.
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.
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.
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/>. */
21 #include "gdbsupport/gdb_obstack.h"
23 #include "gdbsupport/selftest.h"
25 /* Make sure splay trees can actually hold the values we want to
27 static_assert (sizeof (splay_tree_key
) >= sizeof (CORE_ADDR
*));
28 static_assert (sizeof (splay_tree_value
) >= sizeof (void *));
31 /* Fixed address maps. */
34 addrmap_fixed::do_find (CORE_ADDR addr
) const
36 const struct addrmap_transition
*bottom
= &transitions
[0];
37 const struct addrmap_transition
*top
= &transitions
[num_transitions
- 1];
41 /* This needs to round towards top, or else when top = bottom +
42 1 (i.e., two entries are under consideration), then mid ==
43 bottom, and then we may not narrow the range when (mid->addr
45 const addrmap_transition
*mid
= top
- (top
- bottom
) / 2;
47 if (mid
->addr
== addr
)
52 else if (mid
->addr
< addr
)
53 /* We don't eliminate mid itself here, since each transition
54 covers all subsequent addresses until the next. This is why
55 we must round up in computing the midpoint. */
66 addrmap_fixed::relocate (CORE_ADDR offset
)
70 for (i
= 0; i
< num_transitions
; i
++)
71 transitions
[i
].addr
+= offset
;
76 addrmap_fixed::do_foreach (addrmap_foreach_fn fn
) const
80 for (i
= 0; i
< num_transitions
; i
++)
82 int res
= fn (transitions
[i
].addr
, transitions
[i
].value
);
93 /* Mutable address maps. */
95 /* Allocate a copy of CORE_ADDR. */
97 addrmap_mutable::allocate_key (CORE_ADDR addr
)
99 CORE_ADDR
*key
= XNEW (CORE_ADDR
);
102 return (splay_tree_key
) key
;
106 /* Type-correct wrappers for splay tree access. */
108 addrmap_mutable::splay_tree_lookup (CORE_ADDR addr
) const
110 return ::splay_tree_lookup (tree
, (splay_tree_key
) &addr
);
115 addrmap_mutable::splay_tree_predecessor (CORE_ADDR addr
) const
117 return ::splay_tree_predecessor (tree
, (splay_tree_key
) &addr
);
122 addrmap_mutable::splay_tree_successor (CORE_ADDR addr
)
124 return ::splay_tree_successor (tree
, (splay_tree_key
) &addr
);
129 addrmap_mutable::splay_tree_remove (CORE_ADDR addr
)
131 ::splay_tree_remove (tree
, (splay_tree_key
) &addr
);
136 addrmap_node_key (splay_tree_node node
)
138 return * (CORE_ADDR
*) node
->key
;
143 addrmap_node_value (splay_tree_node node
)
145 return (void *) node
->value
;
150 addrmap_node_set_value (splay_tree_node node
, void *value
)
152 node
->value
= (splay_tree_value
) value
;
157 addrmap_mutable::splay_tree_insert (CORE_ADDR key
, void *value
)
159 ::splay_tree_insert (tree
,
161 (splay_tree_value
) value
);
165 /* Without changing the mapping of any address, ensure that there is a
166 tree node at ADDR, even if it would represent a "transition" from
167 one value to the same value. */
169 addrmap_mutable::force_transition (CORE_ADDR addr
)
171 splay_tree_node n
= splay_tree_lookup (addr
);
175 n
= splay_tree_predecessor (addr
);
176 splay_tree_insert (addr
, n
? addrmap_node_value (n
) : NULL
);
182 addrmap_mutable::set_empty (CORE_ADDR start
, CORE_ADDR end_inclusive
,
185 splay_tree_node n
, next
;
188 /* If we're being asked to set all empty portions of the given
189 address range to empty, then probably the caller is confused.
190 (If that turns out to be useful in some cases, then we can change
191 this to simply return, since overriding NULL with NULL is a
195 /* We take a two-pass approach, for simplicity.
196 - Establish transitions where we think we might need them.
197 - First pass: change all NULL regions to OBJ.
198 - Second pass: remove any unnecessary transitions. */
200 /* Establish transitions at the start and end. */
201 force_transition (start
);
202 if (end_inclusive
< CORE_ADDR_MAX
)
203 force_transition (end_inclusive
+ 1);
205 /* Walk the area, changing all NULL regions to OBJ. */
206 for (n
= splay_tree_lookup (start
), gdb_assert (n
);
207 n
&& addrmap_node_key (n
) <= end_inclusive
;
208 n
= splay_tree_successor (addrmap_node_key (n
)))
210 if (! addrmap_node_value (n
))
211 addrmap_node_set_value (n
, obj
);
214 /* Walk the area again, removing transitions from any value to
215 itself. Be sure to visit both the transitions we forced
217 n
= splay_tree_predecessor (start
);
218 prior_value
= n
? addrmap_node_value (n
) : NULL
;
219 for (n
= splay_tree_lookup (start
), gdb_assert (n
);
220 n
&& (end_inclusive
== CORE_ADDR_MAX
221 || addrmap_node_key (n
) <= end_inclusive
+ 1);
224 next
= splay_tree_successor (addrmap_node_key (n
));
225 if (addrmap_node_value (n
) == prior_value
)
226 splay_tree_remove (addrmap_node_key (n
));
228 prior_value
= addrmap_node_value (n
);
234 addrmap_mutable::do_find (CORE_ADDR addr
) const
236 splay_tree_node n
= splay_tree_lookup (addr
);
239 gdb_assert (addrmap_node_key (n
) == addr
);
240 return addrmap_node_value (n
);
243 n
= splay_tree_predecessor (addr
);
246 gdb_assert (addrmap_node_key (n
) < addr
);
247 return addrmap_node_value (n
);
254 addrmap_fixed::addrmap_fixed (struct obstack
*obstack
, addrmap_mutable
*mut
)
256 size_t transition_count
= 0;
258 /* Count the number of transitions in the tree. */
259 mut
->foreach ([&] (CORE_ADDR start
, void *obj
)
265 /* Include an extra entry for the transition at zero (which fixed
266 maps have, but mutable maps do not.) */
270 transitions
= XOBNEWVEC (obstack
, struct addrmap_transition
,
272 transitions
[0].addr
= 0;
273 transitions
[0].value
= NULL
;
275 /* Copy all entries from the splay tree to the array, in order
276 of increasing address. */
277 mut
->foreach ([&] (CORE_ADDR start
, void *obj
)
279 transitions
[num_transitions
].addr
= start
;
280 transitions
[num_transitions
].value
= obj
;
285 /* We should have filled the array. */
286 gdb_assert (num_transitions
== transition_count
);
291 addrmap_mutable::relocate (CORE_ADDR offset
)
293 /* Not needed yet. */
294 internal_error (_("addrmap_relocate is not implemented yet "
295 "for mutable addrmaps"));
299 /* This is a splay_tree_foreach_fn. */
302 addrmap_mutable_foreach_worker (splay_tree_node node
, void *data
)
304 addrmap_foreach_fn
*fn
= (addrmap_foreach_fn
*) data
;
306 return (*fn
) (addrmap_node_key (node
), addrmap_node_value (node
));
311 addrmap_mutable::do_foreach (addrmap_foreach_fn fn
) const
313 return splay_tree_foreach (tree
, addrmap_mutable_foreach_worker
, &fn
);
317 /* Compare keys as CORE_ADDR * values. */
319 splay_compare_CORE_ADDR_ptr (splay_tree_key ak
, splay_tree_key bk
)
321 CORE_ADDR a
= * (CORE_ADDR
*) ak
;
322 CORE_ADDR b
= * (CORE_ADDR
*) bk
;
324 /* We can't just return a-b here, because of over/underflow. */
335 xfree_wrapper (splay_tree_key key
)
337 xfree ((void *) key
);
340 addrmap_mutable::addrmap_mutable ()
341 : tree (splay_tree_new (splay_compare_CORE_ADDR_ptr
, xfree_wrapper
,
342 nullptr /* no delete value */))
346 addrmap_mutable::~addrmap_mutable ()
348 splay_tree_delete (tree
);
355 addrmap_dump (struct addrmap
*map
, struct ui_file
*outfile
, void *payload
)
357 /* True if the previously printed addrmap entry was for PAYLOAD.
358 If so, we want to print the next one as well (since the next
359 addrmap entry defines the end of the range). */
360 bool previous_matched
= false;
362 auto callback
= [&] (CORE_ADDR start_addr
, const void *obj
)
366 bool matches
= payload
== nullptr || payload
== obj
;
367 const char *addr_str
= nullptr;
369 addr_str
= host_address_to_string (obj
);
370 else if (previous_matched
)
371 addr_str
= "<ends here>";
373 if (matches
|| previous_matched
)
374 gdb_printf (outfile
, " %s%s %s\n",
375 payload
!= nullptr ? " " : "",
376 core_addr_to_string (start_addr
),
379 previous_matched
= matches
;
384 map
->foreach (callback
);
388 namespace selftests
{
390 /* Convert P to CORE_ADDR. */
395 return (CORE_ADDR
)(uintptr_t)p
;
398 /* Check that &ARRAY[LOW]..&ARRAY[HIGH] has VAL in MAP. */
400 #define CHECK_ADDRMAP_FIND(MAP, ARRAY, LOW, HIGH, VAL) \
403 for (unsigned i = LOW; i <= HIGH; ++i) \
404 SELF_CHECK (MAP->find (core_addr (&ARRAY[i])) == VAL); \
408 /* Entry point for addrmap unit tests. */
413 /* We'll verify using the addresses of the elements of this array. */
416 /* We'll verify using these values stored into the map. */
417 void *val1
= &array
[1];
418 void *val2
= &array
[2];
420 /* Create mutable addrmap. */
421 auto_obstack temp_obstack
;
422 auto map
= std::make_unique
<struct addrmap_mutable
> ();
423 SELF_CHECK (map
!= nullptr);
425 /* Check initial state. */
426 CHECK_ADDRMAP_FIND (map
, array
, 0, 19, nullptr);
428 /* Insert address range into mutable addrmap. */
429 map
->set_empty (core_addr (&array
[10]), core_addr (&array
[12]), val1
);
430 CHECK_ADDRMAP_FIND (map
, array
, 0, 9, nullptr);
431 CHECK_ADDRMAP_FIND (map
, array
, 10, 12, val1
);
432 CHECK_ADDRMAP_FIND (map
, array
, 13, 19, nullptr);
434 /* Create corresponding fixed addrmap. */
436 = new (&temp_obstack
) addrmap_fixed (&temp_obstack
, map
.get ());
437 SELF_CHECK (map2
!= nullptr);
438 CHECK_ADDRMAP_FIND (map2
, array
, 0, 9, nullptr);
439 CHECK_ADDRMAP_FIND (map2
, array
, 10, 12, val1
);
440 CHECK_ADDRMAP_FIND (map2
, array
, 13, 19, nullptr);
442 /* Iterate over both addrmaps. */
443 auto callback
= [&] (CORE_ADDR start_addr
, void *obj
)
445 if (start_addr
== core_addr (nullptr))
446 SELF_CHECK (obj
== nullptr);
447 else if (start_addr
== core_addr (&array
[10]))
448 SELF_CHECK (obj
== val1
);
449 else if (start_addr
== core_addr (&array
[13]))
450 SELF_CHECK (obj
== nullptr);
455 SELF_CHECK (map
->foreach (callback
) == 0);
456 SELF_CHECK (map2
->foreach (callback
) == 0);
458 /* Relocate fixed addrmap. */
460 CHECK_ADDRMAP_FIND (map2
, array
, 0, 10, nullptr);
461 CHECK_ADDRMAP_FIND (map2
, array
, 11, 13, val1
);
462 CHECK_ADDRMAP_FIND (map2
, array
, 14, 19, nullptr);
464 /* Insert partially overlapping address range into mutable addrmap. */
465 map
->set_empty (core_addr (&array
[11]), core_addr (&array
[13]), val2
);
466 CHECK_ADDRMAP_FIND (map
, array
, 0, 9, nullptr);
467 CHECK_ADDRMAP_FIND (map
, array
, 10, 12, val1
);
468 CHECK_ADDRMAP_FIND (map
, array
, 13, 13, val2
);
469 CHECK_ADDRMAP_FIND (map
, array
, 14, 19, nullptr);
472 } // namespace selftests
473 #endif /* GDB_SELF_TEST */
475 void _initialize_addrmap ();
477 _initialize_addrmap ()
480 selftests::register_test ("addrmap", selftests::test_addrmap
);
481 #endif /* GDB_SELF_TEST */