Commit | Line | Data |
---|---|---|
801e3a5b JB |
1 | /* addrmap.c --- implementation of address map data structure. |
2 | ||
3 | Copyright (C) 2007 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 2 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, write to the Free Software | |
19 | Foundation, Inc., 51 Franklin Street, Fifth Floor, | |
20 | Boston, MA 02110-1301, USA. */ | |
21 | ||
22 | #include "defs.h" | |
23 | ||
24 | #include <stdlib.h> | |
25 | ||
26 | #include "splay-tree.h" | |
27 | #include "gdb_obstack.h" | |
28 | #include "addrmap.h" | |
29 | #include "gdb_assert.h" | |
30 | ||
31 | ||
32 | \f | |
33 | /* The "abstract class". */ | |
34 | ||
35 | /* Functions implementing the addrmap functions for a particular | |
36 | implementation. */ | |
37 | struct addrmap_funcs | |
38 | { | |
39 | void (*set_empty) (struct addrmap *this, | |
40 | CORE_ADDR start, CORE_ADDR end_inclusive, | |
41 | void *obj); | |
42 | void *(*find) (struct addrmap *this, CORE_ADDR addr); | |
43 | struct addrmap *(*create_fixed) (struct addrmap *this, | |
44 | struct obstack *obstack); | |
45 | void (*relocate) (struct addrmap *this, CORE_ADDR offset); | |
46 | }; | |
47 | ||
48 | ||
49 | struct addrmap | |
50 | { | |
51 | struct addrmap_funcs *funcs; | |
52 | }; | |
53 | ||
54 | ||
55 | void | |
56 | addrmap_set_empty (struct addrmap *map, | |
57 | CORE_ADDR start, CORE_ADDR end_inclusive, | |
58 | void *obj) | |
59 | { | |
60 | map->funcs->set_empty (map, start, end_inclusive, obj); | |
61 | } | |
62 | ||
63 | ||
64 | void * | |
65 | addrmap_find (struct addrmap *map, CORE_ADDR addr) | |
66 | { | |
67 | return map->funcs->find (map, addr); | |
68 | } | |
69 | ||
70 | ||
71 | struct addrmap * | |
72 | addrmap_create_fixed (struct addrmap *original, struct obstack *obstack) | |
73 | { | |
74 | return original->funcs->create_fixed (original, obstack); | |
75 | } | |
76 | ||
77 | ||
78 | /* Relocate all the addresses in MAP by OFFSET. (This can be applied | |
79 | to either mutable or immutable maps.) */ | |
80 | void | |
81 | addrmap_relocate (struct addrmap *map, CORE_ADDR offset) | |
82 | { | |
83 | map->funcs->relocate (map, offset); | |
84 | } | |
85 | ||
86 | ||
87 | \f | |
88 | /* Fixed address maps. */ | |
89 | ||
90 | /* A transition: a point in an address map where the value changes. | |
91 | The map maps ADDR to VALUE, but if ADDR > 0, it maps ADDR-1 to | |
92 | something else. */ | |
93 | struct addrmap_transition | |
94 | { | |
95 | CORE_ADDR addr; | |
96 | void *value; | |
97 | }; | |
98 | ||
99 | ||
100 | struct addrmap_fixed | |
101 | { | |
102 | struct addrmap addrmap; | |
103 | ||
104 | /* The number of transitions in TRANSITIONS. */ | |
105 | size_t num_transitions; | |
106 | ||
107 | /* An array of transitions, sorted by address. For every point in | |
108 | the map where either ADDR == 0 or ADDR is mapped to one value and | |
109 | ADDR - 1 is mapped to something different, we have an entry here | |
110 | containing ADDR and VALUE. (Note that this means we always have | |
111 | an entry for address 0). */ | |
112 | struct addrmap_transition transitions[1]; | |
113 | }; | |
114 | ||
115 | ||
116 | static void | |
117 | addrmap_fixed_set_empty (struct addrmap *this, | |
118 | CORE_ADDR start, CORE_ADDR end_inclusive, | |
119 | void *obj) | |
120 | { | |
121 | internal_error (__FILE__, __LINE__, | |
122 | "addrmap_fixed_set_empty: " | |
123 | "fixed addrmaps can't be changed\n"); | |
124 | } | |
125 | ||
126 | ||
127 | static void * | |
128 | addrmap_fixed_find (struct addrmap *this, CORE_ADDR addr) | |
129 | { | |
130 | struct addrmap_fixed *map = (struct addrmap_fixed *) this; | |
131 | struct addrmap_transition *bottom = &map->transitions[0]; | |
132 | struct addrmap_transition *top = &map->transitions[map->num_transitions - 1]; | |
133 | ||
134 | while (bottom < top) | |
135 | { | |
136 | /* This needs to round towards top, or else when top = bottom + | |
137 | 1 (i.e., two entries are under consideration), then mid == | |
138 | bottom, and then we may not narrow the range when (mid->addr | |
139 | < addr). */ | |
140 | struct addrmap_transition *mid = top - (top - bottom) / 2; | |
141 | ||
142 | if (mid->addr == addr) | |
143 | { | |
144 | bottom = mid; | |
145 | break; | |
146 | } | |
147 | else if (mid->addr < addr) | |
148 | /* We don't eliminate mid itself here, since each transition | |
149 | covers all subsequent addresses until the next. This is why | |
150 | we must round up in computing the midpoint. */ | |
151 | bottom = mid; | |
152 | else | |
153 | top = mid - 1; | |
154 | } | |
155 | ||
156 | return bottom->value; | |
157 | } | |
158 | ||
159 | ||
160 | static struct addrmap * | |
161 | addrmap_fixed_create_fixed (struct addrmap *this, struct obstack *obstack) | |
162 | { | |
163 | abort (); | |
164 | } | |
165 | ||
166 | ||
167 | static void | |
168 | addrmap_fixed_relocate (struct addrmap *this, CORE_ADDR offset) | |
169 | { | |
170 | struct addrmap_fixed *map = (struct addrmap_fixed *) this; | |
171 | size_t i; | |
172 | ||
173 | for (i = 0; i < map->num_transitions; i++) | |
174 | map->transitions[i].addr += offset; | |
175 | } | |
176 | ||
177 | ||
178 | static struct addrmap_funcs addrmap_fixed_funcs = | |
179 | { | |
180 | .set_empty = addrmap_fixed_set_empty, | |
181 | .find = addrmap_fixed_find, | |
182 | .create_fixed = addrmap_fixed_create_fixed, | |
183 | .relocate = addrmap_fixed_relocate | |
184 | }; | |
185 | ||
186 | ||
187 | \f | |
188 | /* Mutable address maps. */ | |
189 | ||
190 | struct addrmap_mutable | |
191 | { | |
192 | struct addrmap addrmap; | |
193 | ||
194 | /* The obstack to use for allocations for this map. */ | |
195 | struct obstack *obstack; | |
196 | ||
197 | /* A splay tree, with a node for each transition; there is a | |
198 | transition at address T if T-1 and T map to different objects. | |
199 | ||
200 | Any addresses below the first node map to NULL. (Unlike | |
201 | fixed maps, we have no entry at (CORE_ADDR) 0; it doesn't | |
202 | simplify enough.) | |
203 | ||
204 | The last region is assumed to end at CORE_ADDR_MAX. | |
205 | ||
206 | Since we can't know whether CORE_ADDR is larger or smaller than | |
207 | splay_tree_key (unsigned long) --- I think both are possible, | |
208 | given all combinations of 32- and 64-bit hosts and targets --- | |
209 | our keys are pointers to CORE_ADDR values. Since the splay tree | |
210 | library doesn't pass any closure pointer to the key free | |
211 | function, we can't keep a freelist for keys. Since mutable | |
212 | addrmaps are only used temporarily right now, we just leak keys | |
213 | from deleted nodes; they'll be freed when the obstack is freed. */ | |
214 | splay_tree tree; | |
215 | ||
216 | /* A freelist for splay tree nodes, allocated on obstack, and | |
217 | chained together by their 'right' pointers. */ | |
218 | splay_tree_node free_nodes; | |
219 | }; | |
220 | ||
221 | ||
222 | /* Allocate a copy of CORE_ADDR in MAP's obstack. */ | |
223 | static splay_tree_key | |
224 | allocate_key (struct addrmap_mutable *map, CORE_ADDR addr) | |
225 | { | |
226 | CORE_ADDR *key = obstack_alloc (map->obstack, sizeof (*key)); | |
227 | *key = addr; | |
228 | ||
229 | return (splay_tree_key) key; | |
230 | } | |
231 | ||
232 | ||
233 | /* Type-correct wrappers for splay tree access. */ | |
234 | static splay_tree_node | |
235 | addrmap_splay_tree_lookup (struct addrmap_mutable *map, CORE_ADDR addr) | |
236 | { | |
237 | return splay_tree_lookup (map->tree, (splay_tree_key) &addr); | |
238 | } | |
239 | ||
240 | ||
241 | static splay_tree_node | |
242 | addrmap_splay_tree_predecessor (struct addrmap_mutable *map, CORE_ADDR addr) | |
243 | { | |
244 | return splay_tree_predecessor (map->tree, (splay_tree_key) &addr); | |
245 | } | |
246 | ||
247 | ||
248 | static splay_tree_node | |
249 | addrmap_splay_tree_successor (struct addrmap_mutable *map, CORE_ADDR addr) | |
250 | { | |
251 | return splay_tree_successor (map->tree, (splay_tree_key) &addr); | |
252 | } | |
253 | ||
254 | ||
255 | static CORE_ADDR | |
256 | addrmap_node_key (splay_tree_node node) | |
257 | { | |
258 | return * (CORE_ADDR *) node->key; | |
259 | } | |
260 | ||
261 | ||
262 | static void * | |
263 | addrmap_node_value (splay_tree_node node) | |
264 | { | |
265 | return (void *) node->value; | |
266 | } | |
267 | ||
268 | ||
269 | static void | |
270 | addrmap_node_set_value (splay_tree_node node, void *value) | |
271 | { | |
272 | node->value = (splay_tree_value) value; | |
273 | } | |
274 | ||
275 | ||
276 | static void | |
277 | addrmap_splay_tree_insert (struct addrmap_mutable *map, CORE_ADDR key, void *value) | |
278 | { | |
279 | splay_tree_insert (map->tree, | |
280 | allocate_key (map, key), | |
281 | (splay_tree_value) value); | |
282 | } | |
283 | ||
284 | ||
285 | /* Without changing the mapping of any address, ensure that there is a | |
286 | tree node at ADDR, even if it would represent a "transition" from | |
287 | one value to the same value. */ | |
288 | static void | |
289 | force_transition (struct addrmap_mutable *this, CORE_ADDR addr) | |
290 | { | |
291 | splay_tree_node n | |
292 | = addrmap_splay_tree_lookup (this, addr); | |
293 | ||
294 | if (! n) | |
295 | { | |
296 | n = addrmap_splay_tree_predecessor (this, addr); | |
297 | addrmap_splay_tree_insert (this, addr, | |
298 | n ? addrmap_node_value (n) : NULL); | |
299 | } | |
300 | } | |
301 | ||
302 | ||
303 | static void | |
304 | addrmap_mutable_set_empty (struct addrmap *this, | |
305 | CORE_ADDR start, CORE_ADDR end_inclusive, | |
306 | void *obj) | |
307 | { | |
308 | struct addrmap_mutable *map = (struct addrmap_mutable *) this; | |
309 | splay_tree_node n, next; | |
310 | void *prior_value; | |
311 | ||
312 | /* If we're being asked to set all empty portions of the given | |
313 | address range to empty, then probably the caller is confused. | |
314 | (If that turns out to be useful in some cases, then we can change | |
315 | this to simply return, since overriding NULL with NULL is a | |
316 | no-op.) */ | |
317 | gdb_assert (obj); | |
318 | ||
319 | /* We take a two-pass approach, for simplicity. | |
320 | - Establish transitions where we think we might need them. | |
321 | - First pass: change all NULL regions to OBJ. | |
322 | - Second pass: remove any unnecessary transitions. */ | |
323 | ||
324 | /* Establish transitions at the start and end. */ | |
325 | force_transition (map, start); | |
326 | if (end_inclusive < CORE_ADDR_MAX) | |
327 | force_transition (map, end_inclusive + 1); | |
328 | ||
329 | /* Walk the area, changing all NULL regions to OBJ. */ | |
330 | for (n = addrmap_splay_tree_lookup (map, start), gdb_assert (n); | |
331 | n && addrmap_node_key (n) <= end_inclusive; | |
332 | n = addrmap_splay_tree_successor (map, addrmap_node_key (n))) | |
333 | { | |
334 | if (! addrmap_node_value (n)) | |
335 | addrmap_node_set_value (n, obj); | |
336 | } | |
337 | ||
338 | /* Walk the area again, removing transitions from any value to | |
339 | itself. Be sure to visit both the transitions we forced | |
340 | above. */ | |
341 | n = addrmap_splay_tree_predecessor (map, start); | |
342 | prior_value = n ? addrmap_node_value (n) : NULL; | |
343 | for (n = addrmap_splay_tree_lookup (map, start), gdb_assert (n); | |
344 | n && (end_inclusive == CORE_ADDR_MAX | |
345 | || addrmap_node_key (n) <= end_inclusive + 1); | |
346 | n = next) | |
347 | { | |
348 | next = addrmap_splay_tree_successor (map, addrmap_node_key (n)); | |
349 | if (addrmap_node_value (n) == prior_value) | |
350 | splay_tree_remove (map->tree, addrmap_node_key (n)); | |
351 | else | |
352 | prior_value = addrmap_node_value (n); | |
353 | } | |
354 | } | |
355 | ||
356 | ||
357 | static void * | |
358 | addrmap_mutable_find (struct addrmap *this, CORE_ADDR addr) | |
359 | { | |
360 | /* Not needed yet. */ | |
361 | abort (); | |
362 | } | |
363 | ||
364 | ||
365 | /* A function to pass to splay_tree_foreach to count the number of nodes | |
366 | in the tree. */ | |
367 | static int | |
368 | splay_foreach_count (splay_tree_node n, void *closure) | |
369 | { | |
370 | size_t *count = (size_t *) closure; | |
371 | ||
372 | (*count)++; | |
373 | return 0; | |
374 | } | |
375 | ||
376 | ||
377 | /* A function to pass to splay_tree_foreach to copy entries into a | |
378 | fixed address map. */ | |
379 | static int | |
380 | splay_foreach_copy (splay_tree_node n, void *closure) | |
381 | { | |
382 | struct addrmap_fixed *fixed = (struct addrmap_fixed *) closure; | |
383 | struct addrmap_transition *t = &fixed->transitions[fixed->num_transitions]; | |
384 | ||
385 | t->addr = addrmap_node_key (n); | |
386 | t->value = addrmap_node_value (n); | |
387 | fixed->num_transitions++; | |
388 | ||
389 | return 0; | |
390 | } | |
391 | ||
392 | ||
393 | static struct addrmap * | |
394 | addrmap_mutable_create_fixed (struct addrmap *this, struct obstack *obstack) | |
395 | { | |
396 | struct addrmap_mutable *mutable = (struct addrmap_mutable *) this; | |
397 | struct addrmap_fixed *fixed; | |
398 | size_t num_transitions; | |
399 | ||
400 | /* Count the number of transitions in the tree. */ | |
401 | num_transitions = 0; | |
402 | splay_tree_foreach (mutable->tree, splay_foreach_count, &num_transitions); | |
403 | ||
404 | /* Include an extra entry for the transition at zero (which fixed | |
405 | maps have, but mutable maps do not.) */ | |
406 | num_transitions++; | |
407 | ||
408 | fixed = obstack_alloc (obstack, | |
409 | (sizeof (*fixed) | |
410 | + (num_transitions | |
411 | * sizeof (fixed->transitions[0])))); | |
412 | fixed->addrmap.funcs = &addrmap_fixed_funcs; | |
413 | fixed->num_transitions = 1; | |
414 | fixed->transitions[0].addr = 0; | |
415 | fixed->transitions[0].value = NULL; | |
416 | ||
417 | /* Copy all entries from the splay tree to the array, in order | |
418 | of increasing address. */ | |
419 | splay_tree_foreach (mutable->tree, splay_foreach_copy, fixed); | |
420 | ||
421 | /* We should have filled the array. */ | |
422 | gdb_assert (fixed->num_transitions == num_transitions); | |
423 | ||
424 | return (struct addrmap *) fixed; | |
425 | } | |
426 | ||
427 | ||
428 | static void | |
429 | addrmap_mutable_relocate (struct addrmap *this, CORE_ADDR offset) | |
430 | { | |
431 | /* Not needed yet. */ | |
432 | abort (); | |
433 | } | |
434 | ||
435 | ||
436 | static struct addrmap_funcs addrmap_mutable_funcs = | |
437 | { | |
438 | .set_empty = addrmap_mutable_set_empty, | |
439 | .find = addrmap_mutable_find, | |
440 | .create_fixed = addrmap_mutable_create_fixed, | |
441 | .relocate = addrmap_mutable_relocate | |
442 | }; | |
443 | ||
444 | ||
445 | static void * | |
446 | splay_obstack_alloc (int size, void *closure) | |
447 | { | |
448 | struct addrmap_mutable *map = closure; | |
449 | splay_tree_node n; | |
450 | ||
451 | /* We should only be asked to allocate nodes and larger things. | |
452 | (If, at some point in the future, this is no longer true, we can | |
453 | just round up the size to sizeof (*n).) */ | |
454 | gdb_assert (size >= sizeof (*n)); | |
455 | ||
456 | if (map->free_nodes) | |
457 | { | |
458 | n = map->free_nodes; | |
459 | map->free_nodes = n->right; | |
460 | return n; | |
461 | } | |
462 | else | |
463 | return obstack_alloc (map->obstack, size); | |
464 | } | |
465 | ||
466 | ||
467 | static void | |
468 | splay_obstack_free (void *obj, void *closure) | |
469 | { | |
470 | struct addrmap_mutable *map = closure; | |
471 | splay_tree_node n = obj; | |
472 | ||
473 | /* We've asserted in the allocation function that we only allocate | |
474 | nodes or larger things, so it should be safe to put whatever | |
475 | we get passed back on the free list. */ | |
476 | n->right = map->free_nodes; | |
477 | map->free_nodes = n; | |
478 | } | |
479 | ||
480 | ||
481 | /* Compare keys as CORE_ADDR * values. */ | |
482 | static int | |
483 | splay_compare_CORE_ADDR_ptr (splay_tree_key ak, splay_tree_key bk) | |
484 | { | |
485 | CORE_ADDR a = * (CORE_ADDR *) ak; | |
486 | CORE_ADDR b = * (CORE_ADDR *) bk; | |
487 | ||
488 | /* We can't just return a-b here, because of over/underflow. */ | |
489 | if (a < b) | |
490 | return -1; | |
491 | else if (a == b) | |
492 | return 0; | |
493 | else | |
494 | return 1; | |
495 | } | |
496 | ||
497 | ||
498 | struct addrmap * | |
499 | addrmap_create_mutable (struct obstack *obstack) | |
500 | { | |
501 | struct addrmap_mutable *map = obstack_alloc (obstack, sizeof (*map)); | |
502 | ||
503 | map->addrmap.funcs = &addrmap_mutable_funcs; | |
504 | map->obstack = obstack; | |
505 | ||
506 | /* splay_tree_new_with_allocator uses the provided allocation | |
507 | function to allocate the main splay_tree structure itself, so our | |
508 | free list has to be initialized before we create the tree. */ | |
509 | map->free_nodes = NULL; | |
510 | ||
511 | map->tree = splay_tree_new_with_allocator (splay_compare_CORE_ADDR_ptr, | |
512 | NULL, /* no delete key */ | |
513 | NULL, /* no delete value */ | |
514 | splay_obstack_alloc, | |
515 | splay_obstack_free, | |
516 | map); | |
517 | ||
518 | return (struct addrmap *) map; | |
519 | } | |
520 | ||
521 | ||
522 | \f | |
523 | /* Initialization. */ | |
524 | ||
525 | void | |
526 | _initialize_addrmap (void) | |
527 | { | |
528 | /* Make sure splay trees can actually hold the values we want to | |
529 | store in them. */ | |
530 | gdb_assert (sizeof (splay_tree_key) >= sizeof (CORE_ADDR *)); | |
531 | gdb_assert (sizeof (splay_tree_value) >= sizeof (void *)); | |
532 | } |