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