]>
Commit | Line | Data |
---|---|---|
801e3a5b JB |
1 | /* addrmap.c --- implementation of address map data structure. |
2 | ||
1d506c26 | 3 | Copyright (C) 2007-2024 Free Software Foundation, Inc. |
801e3a5b JB |
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 | |
2fff4d11 | 9 | the Free Software Foundation; either version 3 of the License, or |
801e3a5b JB |
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 | |
2fff4d11 | 18 | along with this program. If not, see <http://www.gnu.org/licenses/>. */ |
801e3a5b JB |
19 | |
20 | #include "defs.h" | |
bf31fd38 | 21 | #include "gdbsupport/gdb_obstack.h" |
4de283e4 | 22 | #include "addrmap.h" |
6a7ee001 | 23 | #include "gdbsupport/selftest.h" |
801e3a5b | 24 | |
90421c56 SM |
25 | /* Make sure splay trees can actually hold the values we want to |
26 | store in them. */ | |
69f6730d TT |
27 | static_assert (sizeof (splay_tree_key) >= sizeof (CORE_ADDR *)); |
28 | static_assert (sizeof (splay_tree_value) >= sizeof (void *)); | |
90421c56 | 29 | |
801e3a5b JB |
30 | \f |
31 | /* Fixed address maps. */ | |
32 | ||
a692aa3f TT |
33 | void |
34 | addrmap_fixed::set_empty (CORE_ADDR start, CORE_ADDR end_inclusive, | |
35 | void *obj) | |
801e3a5b | 36 | { |
f34652de | 37 | internal_error ("addrmap_fixed_set_empty: " |
dda83cd7 | 38 | "fixed addrmaps can't be changed\n"); |
801e3a5b JB |
39 | } |
40 | ||
41 | ||
a692aa3f | 42 | void * |
5867ab87 | 43 | addrmap_fixed::do_find (CORE_ADDR addr) const |
801e3a5b | 44 | { |
a692aa3f TT |
45 | const struct addrmap_transition *bottom = &transitions[0]; |
46 | const struct addrmap_transition *top = &transitions[num_transitions - 1]; | |
801e3a5b JB |
47 | |
48 | while (bottom < top) | |
49 | { | |
50 | /* This needs to round towards top, or else when top = bottom + | |
dda83cd7 SM |
51 | 1 (i.e., two entries are under consideration), then mid == |
52 | bottom, and then we may not narrow the range when (mid->addr | |
53 | < addr). */ | |
bad9471a | 54 | const addrmap_transition *mid = top - (top - bottom) / 2; |
801e3a5b JB |
55 | |
56 | if (mid->addr == addr) | |
dda83cd7 SM |
57 | { |
58 | bottom = mid; | |
59 | break; | |
60 | } | |
801e3a5b | 61 | else if (mid->addr < addr) |
dda83cd7 SM |
62 | /* We don't eliminate mid itself here, since each transition |
63 | covers all subsequent addresses until the next. This is why | |
64 | we must round up in computing the midpoint. */ | |
65 | bottom = mid; | |
801e3a5b | 66 | else |
dda83cd7 | 67 | top = mid - 1; |
801e3a5b JB |
68 | } |
69 | ||
70 | return bottom->value; | |
71 | } | |
72 | ||
73 | ||
a692aa3f TT |
74 | void |
75 | addrmap_fixed::relocate (CORE_ADDR offset) | |
801e3a5b | 76 | { |
801e3a5b JB |
77 | size_t i; |
78 | ||
a692aa3f TT |
79 | for (i = 0; i < num_transitions; i++) |
80 | transitions[i].addr += offset; | |
801e3a5b JB |
81 | } |
82 | ||
83 | ||
a692aa3f | 84 | int |
5867ab87 | 85 | addrmap_fixed::do_foreach (addrmap_foreach_fn fn) const |
855c153f | 86 | { |
855c153f DE |
87 | size_t i; |
88 | ||
a692aa3f | 89 | for (i = 0; i < num_transitions; i++) |
855c153f | 90 | { |
a692aa3f | 91 | int res = fn (transitions[i].addr, transitions[i].value); |
855c153f DE |
92 | |
93 | if (res != 0) | |
94 | return res; | |
95 | } | |
96 | ||
97 | return 0; | |
98 | } | |
99 | ||
100 | ||
801e3a5b JB |
101 | \f |
102 | /* Mutable address maps. */ | |
103 | ||
93b527ef | 104 | /* Allocate a copy of CORE_ADDR. */ |
9d45ec63 TT |
105 | splay_tree_key |
106 | addrmap_mutable::allocate_key (CORE_ADDR addr) | |
801e3a5b | 107 | { |
93b527ef | 108 | CORE_ADDR *key = XNEW (CORE_ADDR); |
801e3a5b | 109 | |
5b4ee69b | 110 | *key = addr; |
801e3a5b JB |
111 | return (splay_tree_key) key; |
112 | } | |
113 | ||
114 | ||
115 | /* Type-correct wrappers for splay tree access. */ | |
9d45ec63 TT |
116 | splay_tree_node |
117 | addrmap_mutable::splay_tree_lookup (CORE_ADDR addr) const | |
801e3a5b | 118 | { |
9d45ec63 | 119 | return ::splay_tree_lookup (tree, (splay_tree_key) &addr); |
801e3a5b JB |
120 | } |
121 | ||
122 | ||
9d45ec63 TT |
123 | splay_tree_node |
124 | addrmap_mutable::splay_tree_predecessor (CORE_ADDR addr) const | |
801e3a5b | 125 | { |
9d45ec63 | 126 | return ::splay_tree_predecessor (tree, (splay_tree_key) &addr); |
801e3a5b JB |
127 | } |
128 | ||
129 | ||
9d45ec63 TT |
130 | splay_tree_node |
131 | addrmap_mutable::splay_tree_successor (CORE_ADDR addr) | |
801e3a5b | 132 | { |
9d45ec63 | 133 | return ::splay_tree_successor (tree, (splay_tree_key) &addr); |
801e3a5b JB |
134 | } |
135 | ||
136 | ||
9d45ec63 TT |
137 | void |
138 | addrmap_mutable::splay_tree_remove (CORE_ADDR addr) | |
cb446409 | 139 | { |
9d45ec63 | 140 | ::splay_tree_remove (tree, (splay_tree_key) &addr); |
cb446409 JB |
141 | } |
142 | ||
143 | ||
801e3a5b JB |
144 | static CORE_ADDR |
145 | addrmap_node_key (splay_tree_node node) | |
146 | { | |
147 | return * (CORE_ADDR *) node->key; | |
148 | } | |
149 | ||
150 | ||
151 | static void * | |
152 | addrmap_node_value (splay_tree_node node) | |
153 | { | |
154 | return (void *) node->value; | |
155 | } | |
156 | ||
157 | ||
158 | static void | |
159 | addrmap_node_set_value (splay_tree_node node, void *value) | |
160 | { | |
161 | node->value = (splay_tree_value) value; | |
162 | } | |
163 | ||
164 | ||
9d45ec63 TT |
165 | void |
166 | addrmap_mutable::splay_tree_insert (CORE_ADDR key, void *value) | |
801e3a5b | 167 | { |
9d45ec63 TT |
168 | ::splay_tree_insert (tree, |
169 | allocate_key (key), | |
170 | (splay_tree_value) value); | |
801e3a5b JB |
171 | } |
172 | ||
173 | ||
174 | /* Without changing the mapping of any address, ensure that there is a | |
175 | tree node at ADDR, even if it would represent a "transition" from | |
176 | one value to the same value. */ | |
9d45ec63 TT |
177 | void |
178 | addrmap_mutable::force_transition (CORE_ADDR addr) | |
801e3a5b | 179 | { |
9d45ec63 | 180 | splay_tree_node n = splay_tree_lookup (addr); |
801e3a5b JB |
181 | |
182 | if (! n) | |
183 | { | |
9d45ec63 TT |
184 | n = splay_tree_predecessor (addr); |
185 | splay_tree_insert (addr, n ? addrmap_node_value (n) : NULL); | |
801e3a5b JB |
186 | } |
187 | } | |
188 | ||
189 | ||
a692aa3f TT |
190 | void |
191 | addrmap_mutable::set_empty (CORE_ADDR start, CORE_ADDR end_inclusive, | |
192 | void *obj) | |
801e3a5b | 193 | { |
801e3a5b JB |
194 | splay_tree_node n, next; |
195 | void *prior_value; | |
196 | ||
197 | /* If we're being asked to set all empty portions of the given | |
198 | address range to empty, then probably the caller is confused. | |
199 | (If that turns out to be useful in some cases, then we can change | |
200 | this to simply return, since overriding NULL with NULL is a | |
201 | no-op.) */ | |
202 | gdb_assert (obj); | |
203 | ||
204 | /* We take a two-pass approach, for simplicity. | |
205 | - Establish transitions where we think we might need them. | |
206 | - First pass: change all NULL regions to OBJ. | |
207 | - Second pass: remove any unnecessary transitions. */ | |
208 | ||
209 | /* Establish transitions at the start and end. */ | |
9d45ec63 | 210 | force_transition (start); |
801e3a5b | 211 | if (end_inclusive < CORE_ADDR_MAX) |
9d45ec63 | 212 | force_transition (end_inclusive + 1); |
801e3a5b JB |
213 | |
214 | /* Walk the area, changing all NULL regions to OBJ. */ | |
9d45ec63 | 215 | for (n = splay_tree_lookup (start), gdb_assert (n); |
801e3a5b | 216 | n && addrmap_node_key (n) <= end_inclusive; |
9d45ec63 | 217 | n = splay_tree_successor (addrmap_node_key (n))) |
801e3a5b JB |
218 | { |
219 | if (! addrmap_node_value (n)) | |
dda83cd7 | 220 | addrmap_node_set_value (n, obj); |
801e3a5b JB |
221 | } |
222 | ||
223 | /* Walk the area again, removing transitions from any value to | |
224 | itself. Be sure to visit both the transitions we forced | |
225 | above. */ | |
9d45ec63 | 226 | n = splay_tree_predecessor (start); |
801e3a5b | 227 | prior_value = n ? addrmap_node_value (n) : NULL; |
9d45ec63 | 228 | for (n = splay_tree_lookup (start), gdb_assert (n); |
801e3a5b | 229 | n && (end_inclusive == CORE_ADDR_MAX |
dda83cd7 | 230 | || addrmap_node_key (n) <= end_inclusive + 1); |
801e3a5b JB |
231 | n = next) |
232 | { | |
9d45ec63 | 233 | next = splay_tree_successor (addrmap_node_key (n)); |
801e3a5b | 234 | if (addrmap_node_value (n) == prior_value) |
9d45ec63 | 235 | splay_tree_remove (addrmap_node_key (n)); |
801e3a5b | 236 | else |
dda83cd7 | 237 | prior_value = addrmap_node_value (n); |
801e3a5b JB |
238 | } |
239 | } | |
240 | ||
241 | ||
a692aa3f | 242 | void * |
5867ab87 | 243 | addrmap_mutable::do_find (CORE_ADDR addr) const |
801e3a5b | 244 | { |
9d45ec63 | 245 | splay_tree_node n = splay_tree_lookup (addr); |
6a7ee001 TV |
246 | if (n != nullptr) |
247 | { | |
248 | gdb_assert (addrmap_node_key (n) == addr); | |
249 | return addrmap_node_value (n); | |
250 | } | |
251 | ||
9d45ec63 | 252 | n = splay_tree_predecessor (addr); |
6a7ee001 TV |
253 | if (n != nullptr) |
254 | { | |
255 | gdb_assert (addrmap_node_key (n) < addr); | |
256 | return addrmap_node_value (n); | |
257 | } | |
258 | ||
259 | return nullptr; | |
801e3a5b JB |
260 | } |
261 | ||
262 | ||
5427f03f | 263 | addrmap_fixed::addrmap_fixed (struct obstack *obstack, addrmap_mutable *mut) |
801e3a5b | 264 | { |
5427f03f | 265 | size_t transition_count = 0; |
801e3a5b JB |
266 | |
267 | /* Count the number of transitions in the tree. */ | |
769520b7 | 268 | mut->foreach ([&] (CORE_ADDR start, void *obj) |
5427f03f TT |
269 | { |
270 | ++transition_count; | |
271 | return 0; | |
272 | }); | |
801e3a5b JB |
273 | |
274 | /* Include an extra entry for the transition at zero (which fixed | |
275 | maps have, but mutable maps do not.) */ | |
5427f03f | 276 | transition_count++; |
801e3a5b | 277 | |
5427f03f TT |
278 | num_transitions = 1; |
279 | transitions = XOBNEWVEC (obstack, struct addrmap_transition, | |
280 | transition_count); | |
281 | transitions[0].addr = 0; | |
282 | transitions[0].value = NULL; | |
801e3a5b JB |
283 | |
284 | /* Copy all entries from the splay tree to the array, in order | |
285 | of increasing address. */ | |
769520b7 | 286 | mut->foreach ([&] (CORE_ADDR start, void *obj) |
5427f03f TT |
287 | { |
288 | transitions[num_transitions].addr = start; | |
289 | transitions[num_transitions].value = obj; | |
290 | ++num_transitions; | |
291 | return 0; | |
292 | }); | |
801e3a5b JB |
293 | |
294 | /* We should have filled the array. */ | |
5427f03f TT |
295 | gdb_assert (num_transitions == transition_count); |
296 | } | |
297 | ||
801e3a5b | 298 | |
a692aa3f TT |
299 | void |
300 | addrmap_mutable::relocate (CORE_ADDR offset) | |
801e3a5b JB |
301 | { |
302 | /* Not needed yet. */ | |
f34652de | 303 | internal_error (_("addrmap_relocate is not implemented yet " |
dda83cd7 | 304 | "for mutable addrmaps")); |
801e3a5b JB |
305 | } |
306 | ||
307 | ||
855c153f DE |
308 | /* This is a splay_tree_foreach_fn. */ |
309 | ||
310 | static int | |
311 | addrmap_mutable_foreach_worker (splay_tree_node node, void *data) | |
312 | { | |
50a6759f | 313 | addrmap_foreach_fn *fn = (addrmap_foreach_fn *) data; |
855c153f | 314 | |
50a6759f | 315 | return (*fn) (addrmap_node_key (node), addrmap_node_value (node)); |
855c153f DE |
316 | } |
317 | ||
318 | ||
a692aa3f | 319 | int |
5867ab87 | 320 | addrmap_mutable::do_foreach (addrmap_foreach_fn fn) const |
855c153f | 321 | { |
a692aa3f | 322 | return splay_tree_foreach (tree, addrmap_mutable_foreach_worker, &fn); |
855c153f DE |
323 | } |
324 | ||
325 | ||
801e3a5b JB |
326 | /* Compare keys as CORE_ADDR * values. */ |
327 | static int | |
328 | splay_compare_CORE_ADDR_ptr (splay_tree_key ak, splay_tree_key bk) | |
329 | { | |
330 | CORE_ADDR a = * (CORE_ADDR *) ak; | |
331 | CORE_ADDR b = * (CORE_ADDR *) bk; | |
332 | ||
333 | /* We can't just return a-b here, because of over/underflow. */ | |
334 | if (a < b) | |
335 | return -1; | |
336 | else if (a == b) | |
337 | return 0; | |
338 | else | |
339 | return 1; | |
340 | } | |
341 | ||
342 | ||
93b527ef TT |
343 | static void |
344 | xfree_wrapper (splay_tree_key key) | |
345 | { | |
346 | xfree ((void *) key); | |
347 | } | |
348 | ||
349 | addrmap_mutable::addrmap_mutable () | |
350 | : tree (splay_tree_new (splay_compare_CORE_ADDR_ptr, xfree_wrapper, | |
351 | nullptr /* no delete value */)) | |
352 | { | |
353 | } | |
354 | ||
355 | addrmap_mutable::~addrmap_mutable () | |
801e3a5b | 356 | { |
93b527ef | 357 | splay_tree_delete (tree); |
9d45ec63 | 358 | } |
801e3a5b | 359 | |
801e3a5b | 360 | |
192786c7 TT |
361 | /* See addrmap.h. */ |
362 | ||
363 | void | |
364 | addrmap_dump (struct addrmap *map, struct ui_file *outfile, void *payload) | |
365 | { | |
366 | /* True if the previously printed addrmap entry was for PAYLOAD. | |
367 | If so, we want to print the next one as well (since the next | |
368 | addrmap entry defines the end of the range). */ | |
369 | bool previous_matched = false; | |
370 | ||
5867ab87 | 371 | auto callback = [&] (CORE_ADDR start_addr, const void *obj) |
192786c7 TT |
372 | { |
373 | QUIT; | |
374 | ||
375 | bool matches = payload == nullptr || payload == obj; | |
376 | const char *addr_str = nullptr; | |
377 | if (matches) | |
378 | addr_str = host_address_to_string (obj); | |
379 | else if (previous_matched) | |
380 | addr_str = "<ends here>"; | |
381 | ||
382 | if (matches || previous_matched) | |
6cb06a8c TT |
383 | gdb_printf (outfile, " %s%s %s\n", |
384 | payload != nullptr ? " " : "", | |
385 | core_addr_to_string (start_addr), | |
386 | addr_str); | |
192786c7 TT |
387 | |
388 | previous_matched = matches; | |
389 | ||
390 | return 0; | |
391 | }; | |
392 | ||
769520b7 | 393 | map->foreach (callback); |
192786c7 TT |
394 | } |
395 | ||
6a7ee001 TV |
396 | #if GDB_SELF_TEST |
397 | namespace selftests { | |
398 | ||
399 | /* Convert P to CORE_ADDR. */ | |
400 | ||
401 | static CORE_ADDR | |
402 | core_addr (void *p) | |
403 | { | |
404 | return (CORE_ADDR)(uintptr_t)p; | |
405 | } | |
406 | ||
407 | /* Check that &ARRAY[LOW]..&ARRAY[HIGH] has VAL in MAP. */ | |
408 | ||
409 | #define CHECK_ADDRMAP_FIND(MAP, ARRAY, LOW, HIGH, VAL) \ | |
410 | do \ | |
411 | { \ | |
412 | for (unsigned i = LOW; i <= HIGH; ++i) \ | |
769520b7 | 413 | SELF_CHECK (MAP->find (core_addr (&ARRAY[i])) == VAL); \ |
6a7ee001 TV |
414 | } \ |
415 | while (0) | |
416 | ||
6a7ee001 TV |
417 | /* Entry point for addrmap unit tests. */ |
418 | ||
419 | static void | |
420 | test_addrmap () | |
421 | { | |
5b3ef0a5 TV |
422 | /* We'll verify using the addresses of the elements of this array. */ |
423 | char array[20]; | |
424 | ||
425 | /* We'll verify using these values stored into the map. */ | |
426 | void *val1 = &array[1]; | |
427 | void *val2 = &array[2]; | |
6a7ee001 TV |
428 | |
429 | /* Create mutable addrmap. */ | |
aa095373 | 430 | auto_obstack temp_obstack; |
6b62451a | 431 | auto map = std::make_unique<struct addrmap_mutable> (); |
6a7ee001 TV |
432 | SELF_CHECK (map != nullptr); |
433 | ||
434 | /* Check initial state. */ | |
435 | CHECK_ADDRMAP_FIND (map, array, 0, 19, nullptr); | |
436 | ||
437 | /* Insert address range into mutable addrmap. */ | |
769520b7 | 438 | map->set_empty (core_addr (&array[10]), core_addr (&array[12]), val1); |
6a7ee001 TV |
439 | CHECK_ADDRMAP_FIND (map, array, 0, 9, nullptr); |
440 | CHECK_ADDRMAP_FIND (map, array, 10, 12, val1); | |
441 | CHECK_ADDRMAP_FIND (map, array, 13, 19, nullptr); | |
442 | ||
443 | /* Create corresponding fixed addrmap. */ | |
d89120e9 | 444 | struct addrmap *map2 |
aa095373 | 445 | = new (&temp_obstack) addrmap_fixed (&temp_obstack, map.get ()); |
6a7ee001 TV |
446 | SELF_CHECK (map2 != nullptr); |
447 | CHECK_ADDRMAP_FIND (map2, array, 0, 9, nullptr); | |
448 | CHECK_ADDRMAP_FIND (map2, array, 10, 12, val1); | |
449 | CHECK_ADDRMAP_FIND (map2, array, 13, 19, nullptr); | |
450 | ||
451 | /* Iterate over both addrmaps. */ | |
5b3ef0a5 TV |
452 | auto callback = [&] (CORE_ADDR start_addr, void *obj) |
453 | { | |
454 | if (start_addr == core_addr (nullptr)) | |
455 | SELF_CHECK (obj == nullptr); | |
456 | else if (start_addr == core_addr (&array[10])) | |
457 | SELF_CHECK (obj == val1); | |
458 | else if (start_addr == core_addr (&array[13])) | |
459 | SELF_CHECK (obj == nullptr); | |
460 | else | |
461 | SELF_CHECK (false); | |
462 | return 0; | |
463 | }; | |
769520b7 TT |
464 | SELF_CHECK (map->foreach (callback) == 0); |
465 | SELF_CHECK (map2->foreach (callback) == 0); | |
6a7ee001 TV |
466 | |
467 | /* Relocate fixed addrmap. */ | |
769520b7 | 468 | map2->relocate (1); |
6a7ee001 TV |
469 | CHECK_ADDRMAP_FIND (map2, array, 0, 10, nullptr); |
470 | CHECK_ADDRMAP_FIND (map2, array, 11, 13, val1); | |
471 | CHECK_ADDRMAP_FIND (map2, array, 14, 19, nullptr); | |
472 | ||
473 | /* Insert partially overlapping address range into mutable addrmap. */ | |
769520b7 | 474 | map->set_empty (core_addr (&array[11]), core_addr (&array[13]), val2); |
6a7ee001 TV |
475 | CHECK_ADDRMAP_FIND (map, array, 0, 9, nullptr); |
476 | CHECK_ADDRMAP_FIND (map, array, 10, 12, val1); | |
477 | CHECK_ADDRMAP_FIND (map, array, 13, 13, val2); | |
478 | CHECK_ADDRMAP_FIND (map, array, 14, 19, nullptr); | |
6a7ee001 TV |
479 | } |
480 | ||
481 | } // namespace selftests | |
fd986183 | 482 | #endif /* GDB_SELF_TEST */ |
6a7ee001 TV |
483 | |
484 | void _initialize_addrmap (); | |
485 | void | |
486 | _initialize_addrmap () | |
487 | { | |
fd986183 | 488 | #if GDB_SELF_TEST |
6a7ee001 | 489 | selftests::register_test ("addrmap", selftests::test_addrmap); |
6a7ee001 | 490 | #endif /* GDB_SELF_TEST */ |
fd986183 | 491 | } |