1 /* addrmap.c --- implementation of address map data structure.
3 Copyright (C) 2007-2014 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 "splay-tree.h"
22 #include "gdb_obstack.h"
24 #include "gdb_assert.h"
28 /* The "abstract class". */
30 /* Functions implementing the addrmap functions for a particular
34 void (*set_empty
) (struct addrmap
*this,
35 CORE_ADDR start
, CORE_ADDR end_inclusive
,
37 void *(*find
) (struct addrmap
*this, CORE_ADDR addr
);
38 struct addrmap
*(*create_fixed
) (struct addrmap
*this,
39 struct obstack
*obstack
);
40 void (*relocate
) (struct addrmap
*this, CORE_ADDR offset
);
41 int (*foreach
) (struct addrmap
*this, addrmap_foreach_fn fn
, void *data
);
47 const struct addrmap_funcs
*funcs
;
52 addrmap_set_empty (struct addrmap
*map
,
53 CORE_ADDR start
, CORE_ADDR end_inclusive
,
56 map
->funcs
->set_empty (map
, start
, end_inclusive
, obj
);
61 addrmap_find (struct addrmap
*map
, CORE_ADDR addr
)
63 return map
->funcs
->find (map
, addr
);
68 addrmap_create_fixed (struct addrmap
*original
, struct obstack
*obstack
)
70 return original
->funcs
->create_fixed (original
, obstack
);
74 /* Relocate all the addresses in MAP by OFFSET. (This can be applied
75 to either mutable or immutable maps.) */
77 addrmap_relocate (struct addrmap
*map
, CORE_ADDR offset
)
79 map
->funcs
->relocate (map
, offset
);
84 addrmap_foreach (struct addrmap
*map
, addrmap_foreach_fn fn
, void *data
)
86 return map
->funcs
->foreach (map
, fn
, data
);
89 /* Fixed address maps. */
91 /* A transition: a point in an address map where the value changes.
92 The map maps ADDR to VALUE, but if ADDR > 0, it maps ADDR-1 to
94 struct addrmap_transition
103 struct addrmap addrmap
;
105 /* The number of transitions in TRANSITIONS. */
106 size_t num_transitions
;
108 /* An array of transitions, sorted by address. For every point in
109 the map where either ADDR == 0 or ADDR is mapped to one value and
110 ADDR - 1 is mapped to something different, we have an entry here
111 containing ADDR and VALUE. (Note that this means we always have
112 an entry for address 0). */
113 struct addrmap_transition transitions
[1];
118 addrmap_fixed_set_empty (struct addrmap
*this,
119 CORE_ADDR start
, CORE_ADDR end_inclusive
,
122 internal_error (__FILE__
, __LINE__
,
123 "addrmap_fixed_set_empty: "
124 "fixed addrmaps can't be changed\n");
129 addrmap_fixed_find (struct addrmap
*this, CORE_ADDR addr
)
131 struct addrmap_fixed
*map
= (struct addrmap_fixed
*) this;
132 struct addrmap_transition
*bottom
= &map
->transitions
[0];
133 struct addrmap_transition
*top
= &map
->transitions
[map
->num_transitions
- 1];
137 /* This needs to round towards top, or else when top = bottom +
138 1 (i.e., two entries are under consideration), then mid ==
139 bottom, and then we may not narrow the range when (mid->addr
141 struct addrmap_transition
*mid
= top
- (top
- bottom
) / 2;
143 if (mid
->addr
== addr
)
148 else if (mid
->addr
< addr
)
149 /* We don't eliminate mid itself here, since each transition
150 covers all subsequent addresses until the next. This is why
151 we must round up in computing the midpoint. */
157 return bottom
->value
;
161 static struct addrmap
*
162 addrmap_fixed_create_fixed (struct addrmap
*this, struct obstack
*obstack
)
164 internal_error (__FILE__
, __LINE__
,
165 _("addrmap_create_fixed is not implemented yet "
166 "for fixed addrmaps"));
171 addrmap_fixed_relocate (struct addrmap
*this, CORE_ADDR offset
)
173 struct addrmap_fixed
*map
= (struct addrmap_fixed
*) this;
176 for (i
= 0; i
< map
->num_transitions
; i
++)
177 map
->transitions
[i
].addr
+= offset
;
182 addrmap_fixed_foreach (struct addrmap
*this, addrmap_foreach_fn fn
,
185 struct addrmap_fixed
*map
= (struct addrmap_fixed
*) this;
188 for (i
= 0; i
< map
->num_transitions
; i
++)
190 int res
= fn (data
, map
->transitions
[i
].addr
, map
->transitions
[i
].value
);
200 static const struct addrmap_funcs addrmap_fixed_funcs
=
202 addrmap_fixed_set_empty
,
204 addrmap_fixed_create_fixed
,
205 addrmap_fixed_relocate
,
206 addrmap_fixed_foreach
211 /* Mutable address maps. */
213 struct addrmap_mutable
215 struct addrmap addrmap
;
217 /* The obstack to use for allocations for this map. */
218 struct obstack
*obstack
;
220 /* A splay tree, with a node for each transition; there is a
221 transition at address T if T-1 and T map to different objects.
223 Any addresses below the first node map to NULL. (Unlike
224 fixed maps, we have no entry at (CORE_ADDR) 0; it doesn't
227 The last region is assumed to end at CORE_ADDR_MAX.
229 Since we can't know whether CORE_ADDR is larger or smaller than
230 splay_tree_key (unsigned long) --- I think both are possible,
231 given all combinations of 32- and 64-bit hosts and targets ---
232 our keys are pointers to CORE_ADDR values. Since the splay tree
233 library doesn't pass any closure pointer to the key free
234 function, we can't keep a freelist for keys. Since mutable
235 addrmaps are only used temporarily right now, we just leak keys
236 from deleted nodes; they'll be freed when the obstack is freed. */
239 /* A freelist for splay tree nodes, allocated on obstack, and
240 chained together by their 'right' pointers. */
241 splay_tree_node free_nodes
;
245 /* Allocate a copy of CORE_ADDR in MAP's obstack. */
246 static splay_tree_key
247 allocate_key (struct addrmap_mutable
*map
, CORE_ADDR addr
)
249 CORE_ADDR
*key
= obstack_alloc (map
->obstack
, sizeof (*key
));
252 return (splay_tree_key
) key
;
256 /* Type-correct wrappers for splay tree access. */
257 static splay_tree_node
258 addrmap_splay_tree_lookup (struct addrmap_mutable
*map
, CORE_ADDR addr
)
260 return splay_tree_lookup (map
->tree
, (splay_tree_key
) &addr
);
264 static splay_tree_node
265 addrmap_splay_tree_predecessor (struct addrmap_mutable
*map
, CORE_ADDR addr
)
267 return splay_tree_predecessor (map
->tree
, (splay_tree_key
) &addr
);
271 static splay_tree_node
272 addrmap_splay_tree_successor (struct addrmap_mutable
*map
, CORE_ADDR addr
)
274 return splay_tree_successor (map
->tree
, (splay_tree_key
) &addr
);
279 addrmap_splay_tree_remove (struct addrmap_mutable
*map
, CORE_ADDR addr
)
281 splay_tree_remove (map
->tree
, (splay_tree_key
) &addr
);
286 addrmap_node_key (splay_tree_node node
)
288 return * (CORE_ADDR
*) node
->key
;
293 addrmap_node_value (splay_tree_node node
)
295 return (void *) node
->value
;
300 addrmap_node_set_value (splay_tree_node node
, void *value
)
302 node
->value
= (splay_tree_value
) value
;
307 addrmap_splay_tree_insert (struct addrmap_mutable
*map
,
308 CORE_ADDR key
, void *value
)
310 splay_tree_insert (map
->tree
,
311 allocate_key (map
, key
),
312 (splay_tree_value
) value
);
316 /* Without changing the mapping of any address, ensure that there is a
317 tree node at ADDR, even if it would represent a "transition" from
318 one value to the same value. */
320 force_transition (struct addrmap_mutable
*this, CORE_ADDR addr
)
323 = addrmap_splay_tree_lookup (this, addr
);
327 n
= addrmap_splay_tree_predecessor (this, addr
);
328 addrmap_splay_tree_insert (this, addr
,
329 n
? addrmap_node_value (n
) : NULL
);
335 addrmap_mutable_set_empty (struct addrmap
*this,
336 CORE_ADDR start
, CORE_ADDR end_inclusive
,
339 struct addrmap_mutable
*map
= (struct addrmap_mutable
*) this;
340 splay_tree_node n
, next
;
343 /* If we're being asked to set all empty portions of the given
344 address range to empty, then probably the caller is confused.
345 (If that turns out to be useful in some cases, then we can change
346 this to simply return, since overriding NULL with NULL is a
350 /* We take a two-pass approach, for simplicity.
351 - Establish transitions where we think we might need them.
352 - First pass: change all NULL regions to OBJ.
353 - Second pass: remove any unnecessary transitions. */
355 /* Establish transitions at the start and end. */
356 force_transition (map
, start
);
357 if (end_inclusive
< CORE_ADDR_MAX
)
358 force_transition (map
, end_inclusive
+ 1);
360 /* Walk the area, changing all NULL regions to OBJ. */
361 for (n
= addrmap_splay_tree_lookup (map
, start
), gdb_assert (n
);
362 n
&& addrmap_node_key (n
) <= end_inclusive
;
363 n
= addrmap_splay_tree_successor (map
, addrmap_node_key (n
)))
365 if (! addrmap_node_value (n
))
366 addrmap_node_set_value (n
, obj
);
369 /* Walk the area again, removing transitions from any value to
370 itself. Be sure to visit both the transitions we forced
372 n
= addrmap_splay_tree_predecessor (map
, start
);
373 prior_value
= n
? addrmap_node_value (n
) : NULL
;
374 for (n
= addrmap_splay_tree_lookup (map
, start
), gdb_assert (n
);
375 n
&& (end_inclusive
== CORE_ADDR_MAX
376 || addrmap_node_key (n
) <= end_inclusive
+ 1);
379 next
= addrmap_splay_tree_successor (map
, addrmap_node_key (n
));
380 if (addrmap_node_value (n
) == prior_value
)
381 addrmap_splay_tree_remove (map
, addrmap_node_key (n
));
383 prior_value
= addrmap_node_value (n
);
389 addrmap_mutable_find (struct addrmap
*this, CORE_ADDR addr
)
391 /* Not needed yet. */
392 internal_error (__FILE__
, __LINE__
,
393 _("addrmap_find is not implemented yet "
394 "for mutable addrmaps"));
398 /* A function to pass to splay_tree_foreach to count the number of nodes
401 splay_foreach_count (splay_tree_node n
, void *closure
)
403 size_t *count
= (size_t *) closure
;
410 /* A function to pass to splay_tree_foreach to copy entries into a
411 fixed address map. */
413 splay_foreach_copy (splay_tree_node n
, void *closure
)
415 struct addrmap_fixed
*fixed
= (struct addrmap_fixed
*) closure
;
416 struct addrmap_transition
*t
= &fixed
->transitions
[fixed
->num_transitions
];
418 t
->addr
= addrmap_node_key (n
);
419 t
->value
= addrmap_node_value (n
);
420 fixed
->num_transitions
++;
426 static struct addrmap
*
427 addrmap_mutable_create_fixed (struct addrmap
*this, struct obstack
*obstack
)
429 struct addrmap_mutable
*mutable = (struct addrmap_mutable
*) this;
430 struct addrmap_fixed
*fixed
;
431 size_t num_transitions
;
433 /* Count the number of transitions in the tree. */
435 splay_tree_foreach (mutable->tree
, splay_foreach_count
, &num_transitions
);
437 /* Include an extra entry for the transition at zero (which fixed
438 maps have, but mutable maps do not.) */
441 fixed
= obstack_alloc (obstack
,
444 * sizeof (fixed
->transitions
[0]))));
445 fixed
->addrmap
.funcs
= &addrmap_fixed_funcs
;
446 fixed
->num_transitions
= 1;
447 fixed
->transitions
[0].addr
= 0;
448 fixed
->transitions
[0].value
= NULL
;
450 /* Copy all entries from the splay tree to the array, in order
451 of increasing address. */
452 splay_tree_foreach (mutable->tree
, splay_foreach_copy
, fixed
);
454 /* We should have filled the array. */
455 gdb_assert (fixed
->num_transitions
== num_transitions
);
457 return (struct addrmap
*) fixed
;
462 addrmap_mutable_relocate (struct addrmap
*this, CORE_ADDR offset
)
464 /* Not needed yet. */
465 internal_error (__FILE__
, __LINE__
,
466 _("addrmap_relocate is not implemented yet "
467 "for mutable addrmaps"));
471 /* Struct to map addrmap's foreach function to splay_tree's version. */
472 struct mutable_foreach_data
474 addrmap_foreach_fn fn
;
479 /* This is a splay_tree_foreach_fn. */
482 addrmap_mutable_foreach_worker (splay_tree_node node
, void *data
)
484 struct mutable_foreach_data
*foreach_data
= data
;
486 return foreach_data
->fn (foreach_data
->data
,
487 addrmap_node_key (node
),
488 addrmap_node_value (node
));
493 addrmap_mutable_foreach (struct addrmap
*this, addrmap_foreach_fn fn
,
496 struct addrmap_mutable
*mutable = (struct addrmap_mutable
*) this;
497 struct mutable_foreach_data foreach_data
;
499 foreach_data
.fn
= fn
;
500 foreach_data
.data
= data
;
501 return splay_tree_foreach (mutable->tree
, addrmap_mutable_foreach_worker
,
506 static const struct addrmap_funcs addrmap_mutable_funcs
=
508 addrmap_mutable_set_empty
,
509 addrmap_mutable_find
,
510 addrmap_mutable_create_fixed
,
511 addrmap_mutable_relocate
,
512 addrmap_mutable_foreach
517 splay_obstack_alloc (int size
, void *closure
)
519 struct addrmap_mutable
*map
= closure
;
522 /* We should only be asked to allocate nodes and larger things.
523 (If, at some point in the future, this is no longer true, we can
524 just round up the size to sizeof (*n).) */
525 gdb_assert (size
>= sizeof (*n
));
530 map
->free_nodes
= n
->right
;
534 return obstack_alloc (map
->obstack
, size
);
539 splay_obstack_free (void *obj
, void *closure
)
541 struct addrmap_mutable
*map
= closure
;
542 splay_tree_node n
= obj
;
544 /* We've asserted in the allocation function that we only allocate
545 nodes or larger things, so it should be safe to put whatever
546 we get passed back on the free list. */
547 n
->right
= map
->free_nodes
;
552 /* Compare keys as CORE_ADDR * values. */
554 splay_compare_CORE_ADDR_ptr (splay_tree_key ak
, splay_tree_key bk
)
556 CORE_ADDR a
= * (CORE_ADDR
*) ak
;
557 CORE_ADDR b
= * (CORE_ADDR
*) bk
;
559 /* We can't just return a-b here, because of over/underflow. */
570 addrmap_create_mutable (struct obstack
*obstack
)
572 struct addrmap_mutable
*map
= obstack_alloc (obstack
, sizeof (*map
));
574 map
->addrmap
.funcs
= &addrmap_mutable_funcs
;
575 map
->obstack
= obstack
;
577 /* splay_tree_new_with_allocator uses the provided allocation
578 function to allocate the main splay_tree structure itself, so our
579 free list has to be initialized before we create the tree. */
580 map
->free_nodes
= NULL
;
582 map
->tree
= splay_tree_new_with_allocator (splay_compare_CORE_ADDR_ptr
,
583 NULL
, /* no delete key */
584 NULL
, /* no delete value */
589 return (struct addrmap
*) map
;
594 /* Initialization. */
596 /* Provide a prototype to silence -Wmissing-prototypes. */
597 extern initialize_file_ftype _initialize_addrmap
;
600 _initialize_addrmap (void)
602 /* Make sure splay trees can actually hold the values we want to
604 gdb_assert (sizeof (splay_tree_key
) >= sizeof (CORE_ADDR
*));
605 gdb_assert (sizeof (splay_tree_value
) >= sizeof (void *));