OpenCores
URL https://opencores.org/ocsvn/openrisc_me/openrisc_me/trunk

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gdb-6.8/] [gdb/] [addrmap.c] - Blame information for rev 262

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 24 jeremybenn
/* addrmap.c --- implementation of address map data structure.
2
 
3
   Copyright (C) 2007, 2008 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
 
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
};
45
 
46
 
47
struct addrmap
48
{
49
  const struct addrmap_funcs *funcs;
50
};
51
 
52
 
53
void
54
addrmap_set_empty (struct addrmap *map,
55
                   CORE_ADDR start, CORE_ADDR end_inclusive,
56
                   void *obj)
57
{
58
  map->funcs->set_empty (map, start, end_inclusive, obj);
59
}
60
 
61
 
62
void *
63
addrmap_find (struct addrmap *map, CORE_ADDR addr)
64
{
65
  return map->funcs->find (map, addr);
66
}
67
 
68
 
69
struct addrmap *
70
addrmap_create_fixed (struct addrmap *original, struct obstack *obstack)
71
{
72
  return original->funcs->create_fixed (original, obstack);
73
}
74
 
75
 
76
/* Relocate all the addresses in MAP by OFFSET.  (This can be applied
77
   to either mutable or immutable maps.)  */
78
void
79
addrmap_relocate (struct addrmap *map, CORE_ADDR offset)
80
{
81
  map->funcs->relocate (map, offset);
82
}
83
 
84
 
85
 
86
/* Fixed address maps.  */
87
 
88
/* A transition: a point in an address map where the value changes.
89
   The map maps ADDR to VALUE, but if ADDR > 0, it maps ADDR-1 to
90
   something else.  */
91
struct addrmap_transition
92
{
93
  CORE_ADDR addr;
94
  void *value;
95
};
96
 
97
 
98
struct addrmap_fixed
99
{
100
  struct addrmap addrmap;
101
 
102
  /* The number of transitions in TRANSITIONS.  */
103
  size_t num_transitions;
104
 
105
  /* An array of transitions, sorted by address.  For every point in
106
     the map where either ADDR == 0 or ADDR is mapped to one value and
107
     ADDR - 1 is mapped to something different, we have an entry here
108
     containing ADDR and VALUE.  (Note that this means we always have
109
     an entry for address 0).  */
110
  struct addrmap_transition transitions[1];
111
};
112
 
113
 
114
static void
115
addrmap_fixed_set_empty (struct addrmap *this,
116
                   CORE_ADDR start, CORE_ADDR end_inclusive,
117
                   void *obj)
118
{
119
  internal_error (__FILE__, __LINE__,
120
                  "addrmap_fixed_set_empty: "
121
                  "fixed addrmaps can't be changed\n");
122
}
123
 
124
 
125
static void *
126
addrmap_fixed_find (struct addrmap *this, CORE_ADDR addr)
127
{
128
  struct addrmap_fixed *map = (struct addrmap_fixed *) this;
129
  struct addrmap_transition *bottom = &map->transitions[0];
130
  struct addrmap_transition *top = &map->transitions[map->num_transitions - 1];
131
 
132
  while (bottom < top)
133
    {
134
      /* This needs to round towards top, or else when top = bottom +
135
         1 (i.e., two entries are under consideration), then mid ==
136
         bottom, and then we may not narrow the range when (mid->addr
137
         < addr).  */
138
      struct addrmap_transition *mid = top - (top - bottom) / 2;
139
 
140
      if (mid->addr == addr)
141
        {
142
          bottom = mid;
143
          break;
144
        }
145
      else if (mid->addr < addr)
146
        /* We don't eliminate mid itself here, since each transition
147
           covers all subsequent addresses until the next.  This is why
148
           we must round up in computing the midpoint.  */
149
        bottom = mid;
150
      else
151
        top = mid - 1;
152
    }
153
 
154
  return bottom->value;
155
}
156
 
157
 
158
static struct addrmap *
159
addrmap_fixed_create_fixed (struct addrmap *this, struct obstack *obstack)
160
{
161
  internal_error (__FILE__, __LINE__,
162
                  _("addrmap_create_fixed is not implemented yet "
163
                    "for fixed addrmaps"));
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 const struct addrmap_funcs addrmap_fixed_funcs =
179
{
180
  addrmap_fixed_set_empty,
181
  addrmap_fixed_find,
182
  addrmap_fixed_create_fixed,
183
  addrmap_fixed_relocate
184
};
185
 
186
 
187
 
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 void
256
addrmap_splay_tree_remove (struct addrmap_mutable *map, CORE_ADDR addr)
257
{
258
  splay_tree_remove (map->tree, (splay_tree_key) &addr);
259
}
260
 
261
 
262
static CORE_ADDR
263
addrmap_node_key (splay_tree_node node)
264
{
265
  return * (CORE_ADDR *) node->key;
266
}
267
 
268
 
269
static void *
270
addrmap_node_value (splay_tree_node node)
271
{
272
  return (void *) node->value;
273
}
274
 
275
 
276
static void
277
addrmap_node_set_value (splay_tree_node node, void *value)
278
{
279
  node->value = (splay_tree_value) value;
280
}
281
 
282
 
283
static void
284
addrmap_splay_tree_insert (struct addrmap_mutable *map, CORE_ADDR key, void *value)
285
{
286
  splay_tree_insert (map->tree,
287
                     allocate_key (map, key),
288
                     (splay_tree_value) value);
289
}
290
 
291
 
292
/* Without changing the mapping of any address, ensure that there is a
293
   tree node at ADDR, even if it would represent a "transition" from
294
   one value to the same value.  */
295
static void
296
force_transition (struct addrmap_mutable *this, CORE_ADDR addr)
297
{
298
  splay_tree_node n
299
    = addrmap_splay_tree_lookup (this, addr);
300
 
301
  if (! n)
302
    {
303
      n = addrmap_splay_tree_predecessor (this, addr);
304
      addrmap_splay_tree_insert (this, addr,
305
                                 n ? addrmap_node_value (n) : NULL);
306
    }
307
}
308
 
309
 
310
static void
311
addrmap_mutable_set_empty (struct addrmap *this,
312
                           CORE_ADDR start, CORE_ADDR end_inclusive,
313
                           void *obj)
314
{
315
  struct addrmap_mutable *map = (struct addrmap_mutable *) this;
316
  splay_tree_node n, next;
317
  void *prior_value;
318
 
319
  /* If we're being asked to set all empty portions of the given
320
     address range to empty, then probably the caller is confused.
321
     (If that turns out to be useful in some cases, then we can change
322
     this to simply return, since overriding NULL with NULL is a
323
     no-op.)  */
324
  gdb_assert (obj);
325
 
326
  /* We take a two-pass approach, for simplicity.
327
     - Establish transitions where we think we might need them.
328
     - First pass: change all NULL regions to OBJ.
329
     - Second pass: remove any unnecessary transitions.  */
330
 
331
  /* Establish transitions at the start and end.  */
332
  force_transition (map, start);
333
  if (end_inclusive < CORE_ADDR_MAX)
334
    force_transition (map, end_inclusive + 1);
335
 
336
  /* Walk the area, changing all NULL regions to OBJ.  */
337
  for (n = addrmap_splay_tree_lookup (map, start), gdb_assert (n);
338
       n && addrmap_node_key (n) <= end_inclusive;
339
       n = addrmap_splay_tree_successor (map, addrmap_node_key (n)))
340
    {
341
      if (! addrmap_node_value (n))
342
        addrmap_node_set_value (n, obj);
343
    }
344
 
345
  /* Walk the area again, removing transitions from any value to
346
     itself.  Be sure to visit both the transitions we forced
347
     above.  */
348
  n = addrmap_splay_tree_predecessor (map, start);
349
  prior_value = n ? addrmap_node_value (n) : NULL;
350
  for (n = addrmap_splay_tree_lookup (map, start), gdb_assert (n);
351
       n && (end_inclusive == CORE_ADDR_MAX
352
             || addrmap_node_key (n) <= end_inclusive + 1);
353
       n = next)
354
    {
355
      next = addrmap_splay_tree_successor (map, addrmap_node_key (n));
356
      if (addrmap_node_value (n) == prior_value)
357
        addrmap_splay_tree_remove (map, addrmap_node_key (n));
358
      else
359
        prior_value = addrmap_node_value (n);
360
    }
361
}
362
 
363
 
364
static void *
365
addrmap_mutable_find (struct addrmap *this, CORE_ADDR addr)
366
{
367
  /* Not needed yet.  */
368
  internal_error (__FILE__, __LINE__,
369
                  _("addrmap_find is not implemented yet "
370
                    "for mutable addrmaps"));
371
}
372
 
373
 
374
/* A function to pass to splay_tree_foreach to count the number of nodes
375
   in the tree.  */
376
static int
377
splay_foreach_count (splay_tree_node n, void *closure)
378
{
379
  size_t *count = (size_t *) closure;
380
 
381
  (*count)++;
382
  return 0;
383
}
384
 
385
 
386
/* A function to pass to splay_tree_foreach to copy entries into a
387
   fixed address map.  */
388
static int
389
splay_foreach_copy (splay_tree_node n, void *closure)
390
{
391
  struct addrmap_fixed *fixed = (struct addrmap_fixed *) closure;
392
  struct addrmap_transition *t = &fixed->transitions[fixed->num_transitions];
393
 
394
  t->addr = addrmap_node_key (n);
395
  t->value = addrmap_node_value (n);
396
  fixed->num_transitions++;
397
 
398
  return 0;
399
}
400
 
401
 
402
static struct addrmap *
403
addrmap_mutable_create_fixed (struct addrmap *this, struct obstack *obstack)
404
{
405
  struct addrmap_mutable *mutable = (struct addrmap_mutable *) this;
406
  struct addrmap_fixed *fixed;
407
  size_t num_transitions;
408
 
409
  /* Count the number of transitions in the tree.  */
410
  num_transitions = 0;
411
  splay_tree_foreach (mutable->tree, splay_foreach_count, &num_transitions);
412
 
413
  /* Include an extra entry for the transition at zero (which fixed
414
     maps have, but mutable maps do not.)  */
415
  num_transitions++;
416
 
417
  fixed = obstack_alloc (obstack,
418
                         (sizeof (*fixed)
419
                          + (num_transitions
420
                             * sizeof (fixed->transitions[0]))));
421
  fixed->addrmap.funcs = &addrmap_fixed_funcs;
422
  fixed->num_transitions = 1;
423
  fixed->transitions[0].addr = 0;
424
  fixed->transitions[0].value = NULL;
425
 
426
  /* Copy all entries from the splay tree to the array, in order
427
     of increasing address.  */
428
  splay_tree_foreach (mutable->tree, splay_foreach_copy, fixed);
429
 
430
  /* We should have filled the array.  */
431
  gdb_assert (fixed->num_transitions == num_transitions);
432
 
433
  return (struct addrmap *) fixed;
434
}
435
 
436
 
437
static void
438
addrmap_mutable_relocate (struct addrmap *this, CORE_ADDR offset)
439
{
440
  /* Not needed yet.  */
441
  internal_error (__FILE__, __LINE__,
442
                  _("addrmap_relocate is not implemented yet "
443
                    "for mutable addrmaps"));
444
}
445
 
446
 
447
static const struct addrmap_funcs addrmap_mutable_funcs =
448
{
449
  addrmap_mutable_set_empty,
450
  addrmap_mutable_find,
451
  addrmap_mutable_create_fixed,
452
  addrmap_mutable_relocate
453
};
454
 
455
 
456
static void *
457
splay_obstack_alloc (int size, void *closure)
458
{
459
  struct addrmap_mutable *map = closure;
460
  splay_tree_node n;
461
 
462
  /* We should only be asked to allocate nodes and larger things.
463
     (If, at some point in the future, this is no longer true, we can
464
     just round up the size to sizeof (*n).)  */
465
  gdb_assert (size >= sizeof (*n));
466
 
467
  if (map->free_nodes)
468
    {
469
      n = map->free_nodes;
470
      map->free_nodes = n->right;
471
      return n;
472
    }
473
  else
474
    return obstack_alloc (map->obstack, size);
475
}
476
 
477
 
478
static void
479
splay_obstack_free (void *obj, void *closure)
480
{
481
  struct addrmap_mutable *map = closure;
482
  splay_tree_node n = obj;
483
 
484
  /* We've asserted in the allocation function that we only allocate
485
     nodes or larger things, so it should be safe to put whatever
486
     we get passed back on the free list.  */
487
  n->right = map->free_nodes;
488
  map->free_nodes = n;
489
}
490
 
491
 
492
/* Compare keys as CORE_ADDR * values.  */
493
static int
494
splay_compare_CORE_ADDR_ptr (splay_tree_key ak, splay_tree_key bk)
495
{
496
  CORE_ADDR a = * (CORE_ADDR *) ak;
497
  CORE_ADDR b = * (CORE_ADDR *) bk;
498
 
499
  /* We can't just return a-b here, because of over/underflow.  */
500
  if (a < b)
501
    return -1;
502
  else if (a == b)
503
    return 0;
504
  else
505
    return 1;
506
}
507
 
508
 
509
struct addrmap *
510
addrmap_create_mutable (struct obstack *obstack)
511
{
512
  struct addrmap_mutable *map = obstack_alloc (obstack, sizeof (*map));
513
 
514
  map->addrmap.funcs = &addrmap_mutable_funcs;
515
  map->obstack = obstack;
516
 
517
  /* splay_tree_new_with_allocator uses the provided allocation
518
     function to allocate the main splay_tree structure itself, so our
519
     free list has to be initialized before we create the tree.  */
520
  map->free_nodes = NULL;
521
 
522
  map->tree = splay_tree_new_with_allocator (splay_compare_CORE_ADDR_ptr,
523
                                             NULL, /* no delete key */
524
                                             NULL, /* no delete value */
525
                                             splay_obstack_alloc,
526
                                             splay_obstack_free,
527
                                             map);
528
 
529
  return (struct addrmap *) map;
530
}
531
 
532
 
533
 
534
/* Initialization.  */
535
 
536
void
537
_initialize_addrmap (void)
538
{
539
  /* Make sure splay trees can actually hold the values we want to
540
     store in them.  */
541
  gdb_assert (sizeof (splay_tree_key) >= sizeof (CORE_ADDR *));
542
  gdb_assert (sizeof (splay_tree_value) >= sizeof (void *));
543
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.