GDB (xrefs)
Loading...
Searching...
No Matches
addrmap.c
Go to the documentation of this file.
1/* addrmap.c --- implementation of address map data structure.
2
3 Copyright (C) 2007-2023 Free Software Foundation, Inc.
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
9 the Free Software Foundation; either version 3 of the License, or
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
18 along with this program. If not, see <http://www.gnu.org/licenses/>. */
19
20#include "defs.h"
21#include "gdbsupport/gdb_obstack.h"
22#include "addrmap.h"
23#include "gdbsupport/selftest.h"
24
25/* Make sure splay trees can actually hold the values we want to
26 store in them. */
27gdb_static_assert (sizeof (splay_tree_key) >= sizeof (CORE_ADDR *));
28gdb_static_assert (sizeof (splay_tree_value) >= sizeof (void *));
29
30
31/* Fixed address maps. */
32
33void
34addrmap_fixed::set_empty (CORE_ADDR start, CORE_ADDR end_inclusive,
35 void *obj)
36{
37 internal_error ("addrmap_fixed_set_empty: "
38 "fixed addrmaps can't be changed\n");
39}
40
41
42void *
43addrmap_fixed::do_find (CORE_ADDR addr) const
44{
45 const struct addrmap_transition *bottom = &transitions[0];
46 const struct addrmap_transition *top = &transitions[num_transitions - 1];
47
48 while (bottom < top)
49 {
50 /* This needs to round towards top, or else when top = bottom +
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). */
54 const addrmap_transition *mid = top - (top - bottom) / 2;
55
56 if (mid->addr == addr)
57 {
58 bottom = mid;
59 break;
60 }
61 else if (mid->addr < addr)
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;
66 else
67 top = mid - 1;
68 }
69
70 return bottom->value;
71}
72
73
74void
75addrmap_fixed::relocate (CORE_ADDR offset)
76{
77 size_t i;
78
79 for (i = 0; i < num_transitions; i++)
80 transitions[i].addr += offset;
81}
82
83
84int
86{
87 size_t i;
88
89 for (i = 0; i < num_transitions; i++)
90 {
91 int res = fn (transitions[i].addr, transitions[i].value);
92
93 if (res != 0)
94 return res;
95 }
96
97 return 0;
98}
99
100
101
102/* Mutable address maps. */
103
104/* Allocate a copy of CORE_ADDR. */
105splay_tree_key
107{
108 CORE_ADDR *key = XNEW (CORE_ADDR);
109
110 *key = addr;
111 return (splay_tree_key) key;
112}
113
114
115/* Type-correct wrappers for splay tree access. */
116splay_tree_node
118{
119 return ::splay_tree_lookup (tree, (splay_tree_key) &addr);
120}
121
122
123splay_tree_node
125{
126 return ::splay_tree_predecessor (tree, (splay_tree_key) &addr);
127}
128
129
130splay_tree_node
132{
133 return ::splay_tree_successor (tree, (splay_tree_key) &addr);
134}
135
136
137void
139{
140 ::splay_tree_remove (tree, (splay_tree_key) &addr);
141}
142
143
144static CORE_ADDR
145addrmap_node_key (splay_tree_node node)
146{
147 return * (CORE_ADDR *) node->key;
148}
149
150
151static void *
152addrmap_node_value (splay_tree_node node)
153{
154 return (void *) node->value;
155}
156
157
158static void
159addrmap_node_set_value (splay_tree_node node, void *value)
160{
161 node->value = (splay_tree_value) value;
162}
163
164
165void
167{
169 allocate_key (key),
170 (splay_tree_value) value);
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. */
177void
179{
180 splay_tree_node n = splay_tree_lookup (addr);
181
182 if (! n)
183 {
184 n = splay_tree_predecessor (addr);
185 splay_tree_insert (addr, n ? addrmap_node_value (n) : NULL);
186 }
187}
188
189
190void
191addrmap_mutable::set_empty (CORE_ADDR start, CORE_ADDR end_inclusive,
192 void *obj)
193{
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. */
210 force_transition (start);
211 if (end_inclusive < CORE_ADDR_MAX)
212 force_transition (end_inclusive + 1);
213
214 /* Walk the area, changing all NULL regions to OBJ. */
215 for (n = splay_tree_lookup (start), gdb_assert (n);
216 n && addrmap_node_key (n) <= end_inclusive;
218 {
219 if (! addrmap_node_value (n))
220 addrmap_node_set_value (n, obj);
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. */
226 n = splay_tree_predecessor (start);
227 prior_value = n ? addrmap_node_value (n) : NULL;
228 for (n = splay_tree_lookup (start), gdb_assert (n);
229 n && (end_inclusive == CORE_ADDR_MAX
230 || addrmap_node_key (n) <= end_inclusive + 1);
231 n = next)
232 {
234 if (addrmap_node_value (n) == prior_value)
236 else
237 prior_value = addrmap_node_value (n);
238 }
239}
240
241
242void *
243addrmap_mutable::do_find (CORE_ADDR addr) const
244{
245 splay_tree_node n = splay_tree_lookup (addr);
246 if (n != nullptr)
247 {
248 gdb_assert (addrmap_node_key (n) == addr);
249 return addrmap_node_value (n);
250 }
251
252 n = splay_tree_predecessor (addr);
253 if (n != nullptr)
254 {
255 gdb_assert (addrmap_node_key (n) < addr);
256 return addrmap_node_value (n);
257 }
258
259 return nullptr;
260}
261
262
263addrmap_fixed::addrmap_fixed (struct obstack *obstack, addrmap_mutable *mut)
264{
265 size_t transition_count = 0;
266
267 /* Count the number of transitions in the tree. */
268 mut->foreach ([&] (CORE_ADDR start, void *obj)
269 {
270 ++transition_count;
271 return 0;
272 });
273
274 /* Include an extra entry for the transition at zero (which fixed
275 maps have, but mutable maps do not.) */
276 transition_count++;
277
278 num_transitions = 1;
279 transitions = XOBNEWVEC (obstack, struct addrmap_transition,
280 transition_count);
281 transitions[0].addr = 0;
282 transitions[0].value = NULL;
283
284 /* Copy all entries from the splay tree to the array, in order
285 of increasing address. */
286 mut->foreach ([&] (CORE_ADDR start, void *obj)
287 {
291 return 0;
292 });
293
294 /* We should have filled the array. */
295 gdb_assert (num_transitions == transition_count);
296}
297
298
299void
301{
302 /* Not needed yet. */
303 internal_error (_("addrmap_relocate is not implemented yet "
304 "for mutable addrmaps"));
305}
306
307
308/* This is a splay_tree_foreach_fn. */
309
310static int
311addrmap_mutable_foreach_worker (splay_tree_node node, void *data)
312{
314
315 return (*fn) (addrmap_node_key (node), addrmap_node_value (node));
316}
317
318
319int
321{
322 return splay_tree_foreach (tree, addrmap_mutable_foreach_worker, &fn);
323}
324
325
326/* Compare keys as CORE_ADDR * values. */
327static int
328splay_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
343static void
344xfree_wrapper (splay_tree_key key)
345{
346 xfree ((void *) key);
347}
348
350 : tree (splay_tree_new (splay_compare_CORE_ADDR_ptr, xfree_wrapper,
351 nullptr /* no delete value */))
352{
353}
354
356{
357 splay_tree_delete (tree);
358}
359
360
361/* See addrmap.h. */
362
363void
364addrmap_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
371 auto callback = [&] (CORE_ADDR start_addr, const void *obj)
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)
383 gdb_printf (outfile, " %s%s %s\n",
384 payload != nullptr ? " " : "",
385 core_addr_to_string (start_addr),
386 addr_str);
387
388 previous_matched = matches;
389
390 return 0;
391 };
392
393 map->foreach (callback);
394}
395
396#if GDB_SELF_TEST
397namespace selftests {
398
399/* Convert P to CORE_ADDR. */
400
401static CORE_ADDR
402core_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) \
413 SELF_CHECK (MAP->find (core_addr (&ARRAY[i])) == VAL); \
414 } \
415 while (0)
416
417/* Entry point for addrmap unit tests. */
418
419static void
420test_addrmap ()
421{
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];
428
429 /* Create mutable addrmap. */
430 auto_obstack temp_obstack;
431 auto map = gdb::make_unique<struct addrmap_mutable> ();
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. */
438 map->set_empty (core_addr (&array[10]), core_addr (&array[12]), val1);
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. */
444 struct addrmap *map2
445 = new (&temp_obstack) addrmap_fixed (&temp_obstack, map.get ());
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. */
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 };
464 SELF_CHECK (map->foreach (callback) == 0);
465 SELF_CHECK (map2->foreach (callback) == 0);
466
467 /* Relocate fixed addrmap. */
468 map2->relocate (1);
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. */
474 map->set_empty (core_addr (&array[11]), core_addr (&array[13]), val2);
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);
479}
480
481} // namespace selftests
482#endif /* GDB_SELF_TEST */
483
484void _initialize_addrmap ();
485void
487{
488#if GDB_SELF_TEST
489 selftests::register_test ("addrmap", selftests::test_addrmap);
490#endif /* GDB_SELF_TEST */
491}
void xfree(void *)
static CORE_ADDR addrmap_node_key(splay_tree_node node)
Definition addrmap.c:145
void _initialize_addrmap()
Definition addrmap.c:486
static void * addrmap_node_value(splay_tree_node node)
Definition addrmap.c:152
gdb_static_assert(sizeof(splay_tree_key) >=sizeof(CORE_ADDR *))
static int splay_compare_CORE_ADDR_ptr(splay_tree_key ak, splay_tree_key bk)
Definition addrmap.c:328
static void xfree_wrapper(splay_tree_key key)
Definition addrmap.c:344
void addrmap_dump(struct addrmap *map, struct ui_file *outfile, void *payload)
Definition addrmap.c:364
static void addrmap_node_set_value(splay_tree_node node, void *value)
Definition addrmap.c:159
static int addrmap_mutable_foreach_worker(splay_tree_node node, void *data)
Definition addrmap.c:311
gdb::function_view< int(CORE_ADDR start_addr, void *obj)> addrmap_foreach_fn
Definition addrmap.h:39
#define QUIT
Definition defs.h:187
size_t num_transitions
Definition addrmap.h:146
void relocate(CORE_ADDR offset) override
Definition addrmap.c:75
struct addrmap_transition * transitions
Definition addrmap.h:153
int do_foreach(addrmap_foreach_fn fn) const override
Definition addrmap.c:85
void * do_find(CORE_ADDR addr) const override
Definition addrmap.c:43
void set_empty(CORE_ADDR start, CORE_ADDR end_inclusive, void *obj) override
Definition addrmap.c:34
addrmap_fixed(struct obstack *obstack, addrmap_mutable *mut)
Definition addrmap.c:263
void splay_tree_remove(CORE_ADDR addr)
Definition addrmap.c:138
splay_tree tree
Definition addrmap.h:191
void force_transition(CORE_ADDR addr)
Definition addrmap.c:178
splay_tree_node splay_tree_lookup(CORE_ADDR addr) const
Definition addrmap.c:117
int do_foreach(addrmap_foreach_fn fn) const override
Definition addrmap.c:320
void * do_find(CORE_ADDR addr) const override
Definition addrmap.c:243
void splay_tree_insert(CORE_ADDR key, void *value)
Definition addrmap.c:166
void relocate(CORE_ADDR offset) override
Definition addrmap.c:300
splay_tree_key allocate_key(CORE_ADDR addr)
Definition addrmap.c:106
splay_tree_node splay_tree_successor(CORE_ADDR addr)
Definition addrmap.c:131
void set_empty(CORE_ADDR start, CORE_ADDR end_inclusive, void *obj) override
Definition addrmap.c:191
splay_tree_node splay_tree_predecessor(CORE_ADDR addr) const
Definition addrmap.c:124
int foreach(addrmap_foreach_const_fn fn) const
Definition addrmap.h:102
virtual void relocate(CORE_ADDR offset)=0
Definition value.h:130
void gdb_printf(struct ui_file *stream, const char *format,...)
Definition utils.c:1886
#define nullptr
Definition x86-cpuid.h:28