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