GDB (xrefs)
/tmp/gdb-7.10/gdb/addrmap.c
Go to the documentation of this file.
1 /* addrmap.c --- implementation of address map data structure.
2 
3  Copyright (C) 2007-2015 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 
26 /* The "abstract class". */
27 
28 /* Functions implementing the addrmap functions for a particular
29  implementation. */
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
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
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 
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. */
93 {
95  void *value;
96 };
97 
98 
100 {
101  struct addrmap addrmap;
102 
103  /* The number of transitions in 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). */
112 };
113 
114 
115 static void
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 *
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
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
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 {
205 };
206 
207 
208 
209 /* Mutable address maps. */
210 
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
246 {
247  CORE_ADDR *key = obstack_alloc (map->obstack, sizeof (*key));
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
257 {
258  return splay_tree_lookup (map->tree, (splay_tree_key) &addr);
259 }
260 
261 
262 static splay_tree_node
264 {
265  return splay_tree_predecessor (map->tree, (splay_tree_key) &addr);
266 }
267 
268 
269 static splay_tree_node
271 {
272  return splay_tree_successor (map->tree, (splay_tree_key) &addr);
273 }
274 
275 
276 static void
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
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
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
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;
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  {
378  if (addrmap_node_value (n) == prior_value)
380  else
381  prior_value = addrmap_node_value (n);
382  }
383 }
384 
385 
386 static void *
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 
431  /* Count the number of transitions in the tree. */
432  num_transitions = 0;
433  splay_tree_foreach (mutable_obj->tree, splay_foreach_count, &num_transitions);
434 
435  /* Include an extra entry for the transition at zero (which fixed
436  maps have, but mutable maps do not.) */
437  num_transitions++;
438 
439  fixed = obstack_alloc (obstack,
440  (sizeof (*fixed)
441  + (num_transitions
442  * sizeof (fixed->transitions[0]))));
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
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. */
471 {
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 = data;
483 
484  return foreach_data->fn (foreach_data->data,
485  addrmap_node_key (node),
486  addrmap_node_value (node));
487 }
488 
489 
490 static int
492  void *data)
493 {
494  struct addrmap_mutable *mutable_obj = (struct addrmap_mutable *) self;
495  struct mutable_foreach_data foreach_data;
496 
497  foreach_data.fn = fn;
498  foreach_data.data = data;
499  return splay_tree_foreach (mutable_obj->tree, addrmap_mutable_foreach_worker,
500  &foreach_data);
501 }
502 
503 
504 static const struct addrmap_funcs addrmap_mutable_funcs =
505 {
511 };
512 
513 
514 static void *
515 splay_obstack_alloc (int size, void *closure)
516 {
517  struct addrmap_mutable *map = closure;
518  splay_tree_node n;
519 
520  /* We should only be asked to allocate nodes and larger things.
521  (If, at some point in the future, this is no longer true, we can
522  just round up the size to sizeof (*n).) */
523  gdb_assert (size >= sizeof (*n));
524 
525  if (map->free_nodes)
526  {
527  n = map->free_nodes;
528  map->free_nodes = n->right;
529  return n;
530  }
531  else
532  return obstack_alloc (map->obstack, size);
533 }
534 
535 
536 static void
537 splay_obstack_free (void *obj, void *closure)
538 {
539  struct addrmap_mutable *map = closure;
540  splay_tree_node n = obj;
541 
542  /* We've asserted in the allocation function that we only allocate
543  nodes or larger things, so it should be safe to put whatever
544  we get passed back on the free list. */
545  n->right = map->free_nodes;
546  map->free_nodes = n;
547 }
548 
549 
550 /* Compare keys as CORE_ADDR * values. */
551 static int
552 splay_compare_CORE_ADDR_ptr (splay_tree_key ak, splay_tree_key bk)
553 {
554  CORE_ADDR a = * (CORE_ADDR *) ak;
555  CORE_ADDR b = * (CORE_ADDR *) bk;
556 
557  /* We can't just return a-b here, because of over/underflow. */
558  if (a < b)
559  return -1;
560  else if (a == b)
561  return 0;
562  else
563  return 1;
564 }
565 
566 
567 struct addrmap *
568 addrmap_create_mutable (struct obstack *obstack)
569 {
570  struct addrmap_mutable *map = obstack_alloc (obstack, sizeof (*map));
571 
573  map->obstack = obstack;
574 
575  /* splay_tree_new_with_allocator uses the provided allocation
576  function to allocate the main splay_tree structure itself, so our
577  free list has to be initialized before we create the tree. */
578  map->free_nodes = NULL;
579 
580  map->tree = splay_tree_new_with_allocator (splay_compare_CORE_ADDR_ptr,
581  NULL, /* no delete key */
582  NULL, /* no delete value */
585  map);
586 
587  return (struct addrmap *) map;
588 }
589 
590 
591 
592 /* Initialization. */
593 
594 /* Provide a prototype to silence -Wmissing-prototypes. */
596 
597 void
599 {
600  /* Make sure splay trees can actually hold the values we want to
601  store in them. */
602  gdb_assert (sizeof (splay_tree_key) >= sizeof (CORE_ADDR *));
603  gdb_assert (sizeof (splay_tree_value) >= sizeof (void *));
604 }
static const struct addrmap_funcs addrmap_mutable_funcs
Definition: addrmap.c:504
struct obstack * obstack
Definition: addrmap.c:216
static void addrmap_node_set_value(splay_tree_node node, void *value)
Definition: addrmap.c:298
bfd_vma CORE_ADDR
Definition: common-types.h:41
void *(* find)(struct addrmap *self, CORE_ADDR addr)
Definition: addrmap.c:35
addrmap_foreach_fn fn
Definition: addrmap.c:472
void internal_error(const char *file, int line, const char *fmt,...)
Definition: errors.c:50
void(* relocate)(struct addrmap *self, CORE_ADDR offset)
Definition: addrmap.c:38
static void addrmap_mutable_relocate(struct addrmap *self, CORE_ADDR offset)
Definition: addrmap.c:460
int addrmap_foreach(struct addrmap *map, addrmap_foreach_fn fn, void *data)
Definition: addrmap.c:82
static void splay_obstack_free(void *obj, void *closure)
Definition: addrmap.c:537
#define _(String)
Definition: gdb_locale.h:40
int(* addrmap_foreach_fn)(void *data, CORE_ADDR start_addr, void *obj)
Definition: addrmap.h:96
static void force_transition(struct addrmap_mutable *self, CORE_ADDR addr)
Definition: addrmap.c:318
static CORE_ADDR addrmap_node_key(splay_tree_node node)
Definition: addrmap.c:284
struct addrmap addrmap
Definition: addrmap.c:101
const struct addrmap_funcs * funcs
Definition: addrmap.c:45
static int splay_foreach_copy(splay_tree_node n, void *closure)
Definition: addrmap.c:411
static int splay_foreach_count(splay_tree_node n, void *closure)
Definition: addrmap.c:399
void initialize_file_ftype(void)
Definition: defs.h:281
#define CORE_ADDR_MAX
Definition: common-types.h:59
void(* set_empty)(struct addrmap *self, CORE_ADDR start, CORE_ADDR end_inclusive, void *obj)
Definition: addrmap.c:32
static void * addrmap_fixed_find(struct addrmap *self, CORE_ADDR addr)
Definition: addrmap.c:127
static void * addrmap_node_value(splay_tree_node node)
Definition: addrmap.c:291
static splay_tree_node addrmap_splay_tree_lookup(struct addrmap_mutable *map, CORE_ADDR addr)
Definition: addrmap.c:256
size_t num_transitions
Definition: addrmap.c:104
struct addrmap * addrmap_create_mutable(struct obstack *obstack)
Definition: addrmap.c:568
splay_tree_node free_nodes
Definition: addrmap.c:239
static int addrmap_fixed_foreach(struct addrmap *self, addrmap_foreach_fn fn, void *data)
Definition: addrmap.c:180
CORE_ADDR addr
Definition: addrmap.c:94
#define gdb_assert(expr)
Definition: gdb_assert.h:33
void addrmap_set_empty(struct addrmap *map, CORE_ADDR start, CORE_ADDR end_inclusive, void *obj)
Definition: addrmap.c:50
struct addrmap addrmap
Definition: addrmap.c:213
static void * addrmap_mutable_find(struct addrmap *self, CORE_ADDR addr)
Definition: addrmap.c:387
static struct addrmap * addrmap_mutable_create_fixed(struct addrmap *self, struct obstack *obstack)
Definition: addrmap.c:425
Definition: value.c:172
static int addrmap_mutable_foreach(struct addrmap *self, addrmap_foreach_fn fn, void *data)
Definition: addrmap.c:491
static const struct addrmap_funcs addrmap_fixed_funcs
Definition: addrmap.c:198
int(* foreach)(struct addrmap *self, addrmap_foreach_fn fn, void *data)
Definition: addrmap.c:39
static void addrmap_splay_tree_remove(struct addrmap_mutable *map, CORE_ADDR addr)
Definition: addrmap.c:277
const char const char int
Definition: command.h:229
static splay_tree_node addrmap_splay_tree_predecessor(struct addrmap_mutable *map, CORE_ADDR addr)
Definition: addrmap.c:263
static int splay_compare_CORE_ADDR_ptr(splay_tree_key ak, splay_tree_key bk)
Definition: addrmap.c:552
static struct addrmap * addrmap_fixed_create_fixed(struct addrmap *self, struct obstack *obstack)
Definition: addrmap.c:160
static void addrmap_fixed_relocate(struct addrmap *self, CORE_ADDR offset)
Definition: addrmap.c:169
static void addrmap_mutable_set_empty(struct addrmap *self, CORE_ADDR start, CORE_ADDR end_inclusive, void *obj)
Definition: addrmap.c:333
int offset
Definition: agent.c:65
struct addrmap *(* create_fixed)(struct addrmap *self, struct obstack *obstack)
Definition: addrmap.c:36
struct addrmap * addrmap_create_fixed(struct addrmap *original, struct obstack *obstack)
Definition: addrmap.c:66
static splay_tree_node addrmap_splay_tree_successor(struct addrmap_mutable *map, CORE_ADDR addr)
Definition: addrmap.c:270
void addrmap_relocate(struct addrmap *map, CORE_ADDR offset)
Definition: addrmap.c:75
static int addrmap_mutable_foreach_worker(splay_tree_node node, void *data)
Definition: addrmap.c:480
static void * splay_obstack_alloc(int size, void *closure)
Definition: addrmap.c:515
void * addrmap_find(struct addrmap *map, CORE_ADDR addr)
Definition: addrmap.c:59
static void addrmap_fixed_set_empty(struct addrmap *self, CORE_ADDR start, CORE_ADDR end_inclusive, void *obj)
Definition: addrmap.c:116
initialize_file_ftype _initialize_addrmap
struct addrmap_transition transitions[1]
Definition: addrmap.c:111
size_t size
Definition: go32-nat.c:242
splay_tree tree
Definition: addrmap.c:235
static splay_tree_key allocate_key(struct addrmap_mutable *map, CORE_ADDR addr)
Definition: addrmap.c:245
static void addrmap_splay_tree_insert(struct addrmap_mutable *map, CORE_ADDR key, void *value)
Definition: addrmap.c:305