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

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.5.1/] [gcc/] [unwind-dw2-fde.c] - Blame information for rev 328

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

Line No. Rev Author Line
1 280 jeremybenn
/* Subroutines needed for unwinding stack frames for exception handling.  */
2
/* Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2008,
3
   2009  Free Software Foundation, Inc.
4
   Contributed by Jason Merrill <jason@cygnus.com>.
5
 
6
This file is part of GCC.
7
 
8
GCC is free software; you can redistribute it and/or modify it under
9
the terms of the GNU General Public License as published by the Free
10
Software Foundation; either version 3, or (at your option) any later
11
version.
12
 
13
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14
WARRANTY; without even the implied warranty of MERCHANTABILITY or
15
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16
for more details.
17
 
18
Under Section 7 of GPL version 3, you are granted additional
19
permissions described in the GCC Runtime Library Exception, version
20
3.1, as published by the Free Software Foundation.
21
 
22
You should have received a copy of the GNU General Public License and
23
a copy of the GCC Runtime Library Exception along with this program;
24
see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
25
<http://www.gnu.org/licenses/>.  */
26
 
27
#ifndef _Unwind_Find_FDE
28
#include "tconfig.h"
29
#include "tsystem.h"
30
#include "coretypes.h"
31
#include "tm.h"
32
#include "dwarf2.h"
33
#include "unwind.h"
34
#define NO_BASE_OF_ENCODED_VALUE
35
#include "unwind-pe.h"
36
#include "unwind-dw2-fde.h"
37
#include "gthr.h"
38
#endif
39
 
40
/* The unseen_objects list contains objects that have been registered
41
   but not yet categorized in any way.  The seen_objects list has had
42
   its pc_begin and count fields initialized at minimum, and is sorted
43
   by decreasing value of pc_begin.  */
44
static struct object *unseen_objects;
45
static struct object *seen_objects;
46
 
47
#ifdef __GTHREAD_MUTEX_INIT
48
static __gthread_mutex_t object_mutex = __GTHREAD_MUTEX_INIT;
49
#else
50
static __gthread_mutex_t object_mutex;
51
#endif
52
 
53
#ifdef __GTHREAD_MUTEX_INIT_FUNCTION
54
static void
55
init_object_mutex (void)
56
{
57
  __GTHREAD_MUTEX_INIT_FUNCTION (&object_mutex);
58
}
59
 
60
static void
61
init_object_mutex_once (void)
62
{
63
  static __gthread_once_t once = __GTHREAD_ONCE_INIT;
64
  __gthread_once (&once, init_object_mutex);
65
}
66
#else
67
#define init_object_mutex_once()
68
#endif
69
 
70
/* Called from crtbegin.o to register the unwind info for an object.  */
71
 
72
void
73
__register_frame_info_bases (const void *begin, struct object *ob,
74
                             void *tbase, void *dbase)
75
{
76
  /* If .eh_frame is empty, don't register at all.  */
77
  if ((const uword *) begin == 0 || *(const uword *) begin == 0)
78
    return;
79
 
80
  ob->pc_begin = (void *)-1;
81
  ob->tbase = tbase;
82
  ob->dbase = dbase;
83
  ob->u.single = begin;
84
  ob->s.i = 0;
85
  ob->s.b.encoding = DW_EH_PE_omit;
86
#ifdef DWARF2_OBJECT_END_PTR_EXTENSION
87
  ob->fde_end = NULL;
88
#endif
89
 
90
  init_object_mutex_once ();
91
  __gthread_mutex_lock (&object_mutex);
92
 
93
  ob->next = unseen_objects;
94
  unseen_objects = ob;
95
 
96
  __gthread_mutex_unlock (&object_mutex);
97
}
98
 
99
void
100
__register_frame_info (const void *begin, struct object *ob)
101
{
102
  __register_frame_info_bases (begin, ob, 0, 0);
103
}
104
 
105
void
106
__register_frame (void *begin)
107
{
108
  struct object *ob;
109
 
110
  /* If .eh_frame is empty, don't register at all.  */
111
  if (*(uword *) begin == 0)
112
    return;
113
 
114
  ob = malloc (sizeof (struct object));
115
  __register_frame_info (begin, ob);
116
}
117
 
118
/* Similar, but BEGIN is actually a pointer to a table of unwind entries
119
   for different translation units.  Called from the file generated by
120
   collect2.  */
121
 
122
void
123
__register_frame_info_table_bases (void *begin, struct object *ob,
124
                                   void *tbase, void *dbase)
125
{
126
  ob->pc_begin = (void *)-1;
127
  ob->tbase = tbase;
128
  ob->dbase = dbase;
129
  ob->u.array = begin;
130
  ob->s.i = 0;
131
  ob->s.b.from_array = 1;
132
  ob->s.b.encoding = DW_EH_PE_omit;
133
 
134
  init_object_mutex_once ();
135
  __gthread_mutex_lock (&object_mutex);
136
 
137
  ob->next = unseen_objects;
138
  unseen_objects = ob;
139
 
140
  __gthread_mutex_unlock (&object_mutex);
141
}
142
 
143
void
144
__register_frame_info_table (void *begin, struct object *ob)
145
{
146
  __register_frame_info_table_bases (begin, ob, 0, 0);
147
}
148
 
149
void
150
__register_frame_table (void *begin)
151
{
152
  struct object *ob = malloc (sizeof (struct object));
153
  __register_frame_info_table (begin, ob);
154
}
155
 
156
/* Called from crtbegin.o to deregister the unwind info for an object.  */
157
/* ??? Glibc has for a while now exported __register_frame_info and
158
   __deregister_frame_info.  If we call __register_frame_info_bases
159
   from crtbegin (wherein it is declared weak), and this object does
160
   not get pulled from libgcc.a for other reasons, then the
161
   invocation of __deregister_frame_info will be resolved from glibc.
162
   Since the registration did not happen there, we'll die.
163
 
164
   Therefore, declare a new deregistration entry point that does the
165
   exact same thing, but will resolve to the same library as
166
   implements __register_frame_info_bases.  */
167
 
168
void *
169
__deregister_frame_info_bases (const void *begin)
170
{
171
  struct object **p;
172
  struct object *ob = 0;
173
 
174
  /* If .eh_frame is empty, we haven't registered.  */
175
  if ((const uword *) begin == 0 || *(const uword *) begin == 0)
176
    return ob;
177
 
178
  init_object_mutex_once ();
179
  __gthread_mutex_lock (&object_mutex);
180
 
181
  for (p = &unseen_objects; *p ; p = &(*p)->next)
182
    if ((*p)->u.single == begin)
183
      {
184
        ob = *p;
185
        *p = ob->next;
186
        goto out;
187
      }
188
 
189
  for (p = &seen_objects; *p ; p = &(*p)->next)
190
    if ((*p)->s.b.sorted)
191
      {
192
        if ((*p)->u.sort->orig_data == begin)
193
          {
194
            ob = *p;
195
            *p = ob->next;
196
            free (ob->u.sort);
197
            goto out;
198
          }
199
      }
200
    else
201
      {
202
        if ((*p)->u.single == begin)
203
          {
204
            ob = *p;
205
            *p = ob->next;
206
            goto out;
207
          }
208
      }
209
 
210
 out:
211
  __gthread_mutex_unlock (&object_mutex);
212
  gcc_assert (ob);
213
  return (void *) ob;
214
}
215
 
216
void *
217
__deregister_frame_info (const void *begin)
218
{
219
  return __deregister_frame_info_bases (begin);
220
}
221
 
222
void
223
__deregister_frame (void *begin)
224
{
225
  /* If .eh_frame is empty, we haven't registered.  */
226
  if (*(uword *) begin != 0)
227
    free (__deregister_frame_info (begin));
228
}
229
 
230
 
231
/* Like base_of_encoded_value, but take the base from a struct object
232
   instead of an _Unwind_Context.  */
233
 
234
static _Unwind_Ptr
235
base_from_object (unsigned char encoding, struct object *ob)
236
{
237
  if (encoding == DW_EH_PE_omit)
238
    return 0;
239
 
240
  switch (encoding & 0x70)
241
    {
242
    case DW_EH_PE_absptr:
243
    case DW_EH_PE_pcrel:
244
    case DW_EH_PE_aligned:
245
      return 0;
246
 
247
    case DW_EH_PE_textrel:
248
      return (_Unwind_Ptr) ob->tbase;
249
    case DW_EH_PE_datarel:
250
      return (_Unwind_Ptr) ob->dbase;
251
    default:
252
      gcc_unreachable ();
253
    }
254
}
255
 
256
/* Return the FDE pointer encoding from the CIE.  */
257
/* ??? This is a subset of extract_cie_info from unwind-dw2.c.  */
258
 
259
static int
260
get_cie_encoding (const struct dwarf_cie *cie)
261
{
262
  const unsigned char *aug, *p;
263
  _Unwind_Ptr dummy;
264
  _uleb128_t utmp;
265
  _sleb128_t stmp;
266
 
267
  aug = cie->augmentation;
268
  if (aug[0] != 'z')
269
    return DW_EH_PE_absptr;
270
 
271
  p = aug + strlen ((const char *)aug) + 1; /* Skip the augmentation string.  */
272
  p = read_uleb128 (p, &utmp);          /* Skip code alignment.  */
273
  p = read_sleb128 (p, &stmp);          /* Skip data alignment.  */
274
  if (cie->version == 1)                /* Skip return address column.  */
275
    p++;
276
  else
277
    p = read_uleb128 (p, &utmp);
278
 
279
  aug++;                                /* Skip 'z' */
280
  p = read_uleb128 (p, &utmp);          /* Skip augmentation length.  */
281
  while (1)
282
    {
283
      /* This is what we're looking for.  */
284
      if (*aug == 'R')
285
        return *p;
286
      /* Personality encoding and pointer.  */
287
      else if (*aug == 'P')
288
        {
289
          /* ??? Avoid dereferencing indirect pointers, since we're
290
             faking the base address.  Gotta keep DW_EH_PE_aligned
291
             intact, however.  */
292
          p = read_encoded_value_with_base (*p & 0x7F, 0, p + 1, &dummy);
293
        }
294
      /* LSDA encoding.  */
295
      else if (*aug == 'L')
296
        p++;
297
      /* Otherwise end of string, or unknown augmentation.  */
298
      else
299
        return DW_EH_PE_absptr;
300
      aug++;
301
    }
302
}
303
 
304
static inline int
305
get_fde_encoding (const struct dwarf_fde *f)
306
{
307
  return get_cie_encoding (get_cie (f));
308
}
309
 
310
 
311
/* Sorting an array of FDEs by address.
312
   (Ideally we would have the linker sort the FDEs so we don't have to do
313
   it at run time. But the linkers are not yet prepared for this.)  */
314
 
315
/* Comparison routines.  Three variants of increasing complexity.  */
316
 
317
static int
318
fde_unencoded_compare (struct object *ob __attribute__((unused)),
319
                       const fde *x, const fde *y)
320
{
321
  _Unwind_Ptr x_ptr, y_ptr;
322
  memcpy (&x_ptr, x->pc_begin, sizeof (_Unwind_Ptr));
323
  memcpy (&y_ptr, y->pc_begin, sizeof (_Unwind_Ptr));
324
 
325
  if (x_ptr > y_ptr)
326
    return 1;
327
  if (x_ptr < y_ptr)
328
    return -1;
329
  return 0;
330
}
331
 
332
static int
333
fde_single_encoding_compare (struct object *ob, const fde *x, const fde *y)
334
{
335
  _Unwind_Ptr base, x_ptr, y_ptr;
336
 
337
  base = base_from_object (ob->s.b.encoding, ob);
338
  read_encoded_value_with_base (ob->s.b.encoding, base, x->pc_begin, &x_ptr);
339
  read_encoded_value_with_base (ob->s.b.encoding, base, y->pc_begin, &y_ptr);
340
 
341
  if (x_ptr > y_ptr)
342
    return 1;
343
  if (x_ptr < y_ptr)
344
    return -1;
345
  return 0;
346
}
347
 
348
static int
349
fde_mixed_encoding_compare (struct object *ob, const fde *x, const fde *y)
350
{
351
  int x_encoding, y_encoding;
352
  _Unwind_Ptr x_ptr, y_ptr;
353
 
354
  x_encoding = get_fde_encoding (x);
355
  read_encoded_value_with_base (x_encoding, base_from_object (x_encoding, ob),
356
                                x->pc_begin, &x_ptr);
357
 
358
  y_encoding = get_fde_encoding (y);
359
  read_encoded_value_with_base (y_encoding, base_from_object (y_encoding, ob),
360
                                y->pc_begin, &y_ptr);
361
 
362
  if (x_ptr > y_ptr)
363
    return 1;
364
  if (x_ptr < y_ptr)
365
    return -1;
366
  return 0;
367
}
368
 
369
typedef int (*fde_compare_t) (struct object *, const fde *, const fde *);
370
 
371
 
372
/* This is a special mix of insertion sort and heap sort, optimized for
373
   the data sets that actually occur. They look like
374
   101 102 103 127 128 105 108 110 190 111 115 119 125 160 126 129 130.
375
   I.e. a linearly increasing sequence (coming from functions in the text
376
   section), with additionally a few unordered elements (coming from functions
377
   in gnu_linkonce sections) whose values are higher than the values in the
378
   surrounding linear sequence (but not necessarily higher than the values
379
   at the end of the linear sequence!).
380
   The worst-case total run time is O(N) + O(n log (n)), where N is the
381
   total number of FDEs and n is the number of erratic ones.  */
382
 
383
struct fde_accumulator
384
{
385
  struct fde_vector *linear;
386
  struct fde_vector *erratic;
387
};
388
 
389
static inline int
390
start_fde_sort (struct fde_accumulator *accu, size_t count)
391
{
392
  size_t size;
393
  if (! count)
394
    return 0;
395
 
396
  size = sizeof (struct fde_vector) + sizeof (const fde *) * count;
397
  if ((accu->linear = malloc (size)))
398
    {
399
      accu->linear->count = 0;
400
      if ((accu->erratic = malloc (size)))
401
        accu->erratic->count = 0;
402
      return 1;
403
    }
404
  else
405
    return 0;
406
}
407
 
408
static inline void
409
fde_insert (struct fde_accumulator *accu, const fde *this_fde)
410
{
411
  if (accu->linear)
412
    accu->linear->array[accu->linear->count++] = this_fde;
413
}
414
 
415
/* Split LINEAR into a linear sequence with low values and an erratic
416
   sequence with high values, put the linear one (of longest possible
417
   length) into LINEAR and the erratic one into ERRATIC. This is O(N).
418
 
419
   Because the longest linear sequence we are trying to locate within the
420
   incoming LINEAR array can be interspersed with (high valued) erratic
421
   entries.  We construct a chain indicating the sequenced entries.
422
   To avoid having to allocate this chain, we overlay it onto the space of
423
   the ERRATIC array during construction.  A final pass iterates over the
424
   chain to determine what should be placed in the ERRATIC array, and
425
   what is the linear sequence.  This overlay is safe from aliasing.  */
426
 
427
static inline void
428
fde_split (struct object *ob, fde_compare_t fde_compare,
429
           struct fde_vector *linear, struct fde_vector *erratic)
430
{
431
  static const fde *marker;
432
  size_t count = linear->count;
433
  const fde *const *chain_end = &marker;
434
  size_t i, j, k;
435
 
436
  /* This should optimize out, but it is wise to make sure this assumption
437
     is correct. Should these have different sizes, we cannot cast between
438
     them and the overlaying onto ERRATIC will not work.  */
439
  gcc_assert (sizeof (const fde *) == sizeof (const fde **));
440
 
441
  for (i = 0; i < count; i++)
442
    {
443
      const fde *const *probe;
444
 
445
      for (probe = chain_end;
446
           probe != &marker && fde_compare (ob, linear->array[i], *probe) < 0;
447
           probe = chain_end)
448
        {
449
          chain_end = (const fde *const*) erratic->array[probe - linear->array];
450
          erratic->array[probe - linear->array] = NULL;
451
        }
452
      erratic->array[i] = (const fde *) chain_end;
453
      chain_end = &linear->array[i];
454
    }
455
 
456
  /* Each entry in LINEAR which is part of the linear sequence we have
457
     discovered will correspond to a non-NULL entry in the chain we built in
458
     the ERRATIC array.  */
459
  for (i = j = k = 0; i < count; i++)
460
    if (erratic->array[i])
461
      linear->array[j++] = linear->array[i];
462
    else
463
      erratic->array[k++] = linear->array[i];
464
  linear->count = j;
465
  erratic->count = k;
466
}
467
 
468
#define SWAP(x,y) do { const fde * tmp = x; x = y; y = tmp; } while (0)
469
 
470
/* Convert a semi-heap to a heap.  A semi-heap is a heap except possibly
471
   for the first (root) node; push it down to its rightful place.  */
472
 
473
static void
474
frame_downheap (struct object *ob, fde_compare_t fde_compare, const fde **a,
475
                int lo, int hi)
476
{
477
  int i, j;
478
 
479
  for (i = lo, j = 2*i+1;
480
       j < hi;
481
       j = 2*i+1)
482
    {
483
      if (j+1 < hi && fde_compare (ob, a[j], a[j+1]) < 0)
484
        ++j;
485
 
486
      if (fde_compare (ob, a[i], a[j]) < 0)
487
        {
488
          SWAP (a[i], a[j]);
489
          i = j;
490
        }
491
      else
492
        break;
493
    }
494
}
495
 
496
/* This is O(n log(n)).  BSD/OS defines heapsort in stdlib.h, so we must
497
   use a name that does not conflict.  */
498
 
499
static void
500
frame_heapsort (struct object *ob, fde_compare_t fde_compare,
501
                struct fde_vector *erratic)
502
{
503
  /* For a description of this algorithm, see:
504
     Samuel P. Harbison, Guy L. Steele Jr.: C, a reference manual, 2nd ed.,
505
     p. 60-61.  */
506
  const fde ** a = erratic->array;
507
  /* A portion of the array is called a "heap" if for all i>=0:
508
     If i and 2i+1 are valid indices, then a[i] >= a[2i+1].
509
     If i and 2i+2 are valid indices, then a[i] >= a[2i+2].  */
510
  size_t n = erratic->count;
511
  int m;
512
 
513
  /* Expand our heap incrementally from the end of the array, heapifying
514
     each resulting semi-heap as we go.  After each step, a[m] is the top
515
     of a heap.  */
516
  for (m = n/2-1; m >= 0; --m)
517
    frame_downheap (ob, fde_compare, a, m, n);
518
 
519
  /* Shrink our heap incrementally from the end of the array, first
520
     swapping out the largest element a[0] and then re-heapifying the
521
     resulting semi-heap.  After each step, a[0..m) is a heap.  */
522
  for (m = n-1; m >= 1; --m)
523
    {
524
      SWAP (a[0], a[m]);
525
      frame_downheap (ob, fde_compare, a, 0, m);
526
    }
527
#undef SWAP
528
}
529
 
530
/* Merge V1 and V2, both sorted, and put the result into V1.  */
531
static inline void
532
fde_merge (struct object *ob, fde_compare_t fde_compare,
533
           struct fde_vector *v1, struct fde_vector *v2)
534
{
535
  size_t i1, i2;
536
  const fde * fde2;
537
 
538
  i2 = v2->count;
539
  if (i2 > 0)
540
    {
541
      i1 = v1->count;
542
      do
543
        {
544
          i2--;
545
          fde2 = v2->array[i2];
546
          while (i1 > 0 && fde_compare (ob, v1->array[i1-1], fde2) > 0)
547
            {
548
              v1->array[i1+i2] = v1->array[i1-1];
549
              i1--;
550
            }
551
          v1->array[i1+i2] = fde2;
552
        }
553
      while (i2 > 0);
554
      v1->count += v2->count;
555
    }
556
}
557
 
558
static inline void
559
end_fde_sort (struct object *ob, struct fde_accumulator *accu, size_t count)
560
{
561
  fde_compare_t fde_compare;
562
 
563
  gcc_assert (!accu->linear || accu->linear->count == count);
564
 
565
  if (ob->s.b.mixed_encoding)
566
    fde_compare = fde_mixed_encoding_compare;
567
  else if (ob->s.b.encoding == DW_EH_PE_absptr)
568
    fde_compare = fde_unencoded_compare;
569
  else
570
    fde_compare = fde_single_encoding_compare;
571
 
572
  if (accu->erratic)
573
    {
574
      fde_split (ob, fde_compare, accu->linear, accu->erratic);
575
      gcc_assert (accu->linear->count + accu->erratic->count == count);
576
      frame_heapsort (ob, fde_compare, accu->erratic);
577
      fde_merge (ob, fde_compare, accu->linear, accu->erratic);
578
      free (accu->erratic);
579
    }
580
  else
581
    {
582
      /* We've not managed to malloc an erratic array,
583
         so heap sort in the linear one.  */
584
      frame_heapsort (ob, fde_compare, accu->linear);
585
    }
586
}
587
 
588
 
589
/* Update encoding, mixed_encoding, and pc_begin for OB for the
590
   fde array beginning at THIS_FDE.  Return the number of fdes
591
   encountered along the way.  */
592
 
593
static size_t
594
classify_object_over_fdes (struct object *ob, const fde *this_fde)
595
{
596
  const struct dwarf_cie *last_cie = 0;
597
  size_t count = 0;
598
  int encoding = DW_EH_PE_absptr;
599
  _Unwind_Ptr base = 0;
600
 
601
  for (; ! last_fde (ob, this_fde); this_fde = next_fde (this_fde))
602
    {
603
      const struct dwarf_cie *this_cie;
604
      _Unwind_Ptr mask, pc_begin;
605
 
606
      /* Skip CIEs.  */
607
      if (this_fde->CIE_delta == 0)
608
        continue;
609
 
610
      /* Determine the encoding for this FDE.  Note mixed encoded
611
         objects for later.  */
612
      this_cie = get_cie (this_fde);
613
      if (this_cie != last_cie)
614
        {
615
          last_cie = this_cie;
616
          encoding = get_cie_encoding (this_cie);
617
          base = base_from_object (encoding, ob);
618
          if (ob->s.b.encoding == DW_EH_PE_omit)
619
            ob->s.b.encoding = encoding;
620
          else if (ob->s.b.encoding != encoding)
621
            ob->s.b.mixed_encoding = 1;
622
        }
623
 
624
      read_encoded_value_with_base (encoding, base, this_fde->pc_begin,
625
                                    &pc_begin);
626
 
627
      /* Take care to ignore link-once functions that were removed.
628
         In these cases, the function address will be NULL, but if
629
         the encoding is smaller than a pointer a true NULL may not
630
         be representable.  Assume 0 in the representable bits is NULL.  */
631
      mask = size_of_encoded_value (encoding);
632
      if (mask < sizeof (void *))
633
        mask = (((_Unwind_Ptr) 1) << (mask << 3)) - 1;
634
      else
635
        mask = -1;
636
 
637
      if ((pc_begin & mask) == 0)
638
        continue;
639
 
640
      count += 1;
641
      if ((void *) pc_begin < ob->pc_begin)
642
        ob->pc_begin = (void *) pc_begin;
643
    }
644
 
645
  return count;
646
}
647
 
648
static void
649
add_fdes (struct object *ob, struct fde_accumulator *accu, const fde *this_fde)
650
{
651
  const struct dwarf_cie *last_cie = 0;
652
  int encoding = ob->s.b.encoding;
653
  _Unwind_Ptr base = base_from_object (ob->s.b.encoding, ob);
654
 
655
  for (; ! last_fde (ob, this_fde); this_fde = next_fde (this_fde))
656
    {
657
      const struct dwarf_cie *this_cie;
658
 
659
      /* Skip CIEs.  */
660
      if (this_fde->CIE_delta == 0)
661
        continue;
662
 
663
      if (ob->s.b.mixed_encoding)
664
        {
665
          /* Determine the encoding for this FDE.  Note mixed encoded
666
             objects for later.  */
667
          this_cie = get_cie (this_fde);
668
          if (this_cie != last_cie)
669
            {
670
              last_cie = this_cie;
671
              encoding = get_cie_encoding (this_cie);
672
              base = base_from_object (encoding, ob);
673
            }
674
        }
675
 
676
      if (encoding == DW_EH_PE_absptr)
677
        {
678
          _Unwind_Ptr ptr;
679
          memcpy (&ptr, this_fde->pc_begin, sizeof (_Unwind_Ptr));
680
          if (ptr == 0)
681
            continue;
682
        }
683
      else
684
        {
685
          _Unwind_Ptr pc_begin, mask;
686
 
687
          read_encoded_value_with_base (encoding, base, this_fde->pc_begin,
688
                                        &pc_begin);
689
 
690
          /* Take care to ignore link-once functions that were removed.
691
             In these cases, the function address will be NULL, but if
692
             the encoding is smaller than a pointer a true NULL may not
693
             be representable.  Assume 0 in the representable bits is NULL.  */
694
          mask = size_of_encoded_value (encoding);
695
          if (mask < sizeof (void *))
696
            mask = (((_Unwind_Ptr) 1) << (mask << 3)) - 1;
697
          else
698
            mask = -1;
699
 
700
          if ((pc_begin & mask) == 0)
701
            continue;
702
        }
703
 
704
      fde_insert (accu, this_fde);
705
    }
706
}
707
 
708
/* Set up a sorted array of pointers to FDEs for a loaded object.  We
709
   count up the entries before allocating the array because it's likely to
710
   be faster.  We can be called multiple times, should we have failed to
711
   allocate a sorted fde array on a previous occasion.  */
712
 
713
static inline void
714
init_object (struct object* ob)
715
{
716
  struct fde_accumulator accu;
717
  size_t count;
718
 
719
  count = ob->s.b.count;
720
  if (count == 0)
721
    {
722
      if (ob->s.b.from_array)
723
        {
724
          fde **p = ob->u.array;
725
          for (count = 0; *p; ++p)
726
            count += classify_object_over_fdes (ob, *p);
727
        }
728
      else
729
        count = classify_object_over_fdes (ob, ob->u.single);
730
 
731
      /* The count field we have in the main struct object is somewhat
732
         limited, but should suffice for virtually all cases.  If the
733
         counted value doesn't fit, re-write a zero.  The worst that
734
         happens is that we re-count next time -- admittedly non-trivial
735
         in that this implies some 2M fdes, but at least we function.  */
736
      ob->s.b.count = count;
737
      if (ob->s.b.count != count)
738
        ob->s.b.count = 0;
739
    }
740
 
741
  if (!start_fde_sort (&accu, count))
742
    return;
743
 
744
  if (ob->s.b.from_array)
745
    {
746
      fde **p;
747
      for (p = ob->u.array; *p; ++p)
748
        add_fdes (ob, &accu, *p);
749
    }
750
  else
751
    add_fdes (ob, &accu, ob->u.single);
752
 
753
  end_fde_sort (ob, &accu, count);
754
 
755
  /* Save the original fde pointer, since this is the key by which the
756
     DSO will deregister the object.  */
757
  accu.linear->orig_data = ob->u.single;
758
  ob->u.sort = accu.linear;
759
 
760
  ob->s.b.sorted = 1;
761
}
762
 
763
/* A linear search through a set of FDEs for the given PC.  This is
764
   used when there was insufficient memory to allocate and sort an
765
   array.  */
766
 
767
static const fde *
768
linear_search_fdes (struct object *ob, const fde *this_fde, void *pc)
769
{
770
  const struct dwarf_cie *last_cie = 0;
771
  int encoding = ob->s.b.encoding;
772
  _Unwind_Ptr base = base_from_object (ob->s.b.encoding, ob);
773
 
774
  for (; ! last_fde (ob, this_fde); this_fde = next_fde (this_fde))
775
    {
776
      const struct dwarf_cie *this_cie;
777
      _Unwind_Ptr pc_begin, pc_range;
778
 
779
      /* Skip CIEs.  */
780
      if (this_fde->CIE_delta == 0)
781
        continue;
782
 
783
      if (ob->s.b.mixed_encoding)
784
        {
785
          /* Determine the encoding for this FDE.  Note mixed encoded
786
             objects for later.  */
787
          this_cie = get_cie (this_fde);
788
          if (this_cie != last_cie)
789
            {
790
              last_cie = this_cie;
791
              encoding = get_cie_encoding (this_cie);
792
              base = base_from_object (encoding, ob);
793
            }
794
        }
795
 
796
      if (encoding == DW_EH_PE_absptr)
797
        {
798
          const _Unwind_Ptr *pc_array = (const _Unwind_Ptr *) this_fde->pc_begin;
799
          pc_begin = pc_array[0];
800
          pc_range = pc_array[1];
801
          if (pc_begin == 0)
802
            continue;
803
        }
804
      else
805
        {
806
          _Unwind_Ptr mask;
807
          const unsigned char *p;
808
 
809
          p = read_encoded_value_with_base (encoding, base,
810
                                            this_fde->pc_begin, &pc_begin);
811
          read_encoded_value_with_base (encoding & 0x0F, 0, p, &pc_range);
812
 
813
          /* Take care to ignore link-once functions that were removed.
814
             In these cases, the function address will be NULL, but if
815
             the encoding is smaller than a pointer a true NULL may not
816
             be representable.  Assume 0 in the representable bits is NULL.  */
817
          mask = size_of_encoded_value (encoding);
818
          if (mask < sizeof (void *))
819
            mask = (((_Unwind_Ptr) 1) << (mask << 3)) - 1;
820
          else
821
            mask = -1;
822
 
823
          if ((pc_begin & mask) == 0)
824
            continue;
825
        }
826
 
827
      if ((_Unwind_Ptr) pc - pc_begin < pc_range)
828
        return this_fde;
829
    }
830
 
831
  return NULL;
832
}
833
 
834
/* Binary search for an FDE containing the given PC.  Here are three
835
   implementations of increasing complexity.  */
836
 
837
static inline const fde *
838
binary_search_unencoded_fdes (struct object *ob, void *pc)
839
{
840
  struct fde_vector *vec = ob->u.sort;
841
  size_t lo, hi;
842
 
843
  for (lo = 0, hi = vec->count; lo < hi; )
844
    {
845
      size_t i = (lo + hi) / 2;
846
      const fde *const f = vec->array[i];
847
      void *pc_begin;
848
      uaddr pc_range;
849
      memcpy (&pc_begin, (const void * const *) f->pc_begin, sizeof (void *));
850
      memcpy (&pc_range, (const uaddr *) f->pc_begin + 1, sizeof (uaddr));
851
 
852
      if (pc < pc_begin)
853
        hi = i;
854
      else if (pc >= pc_begin + pc_range)
855
        lo = i + 1;
856
      else
857
        return f;
858
    }
859
 
860
  return NULL;
861
}
862
 
863
static inline const fde *
864
binary_search_single_encoding_fdes (struct object *ob, void *pc)
865
{
866
  struct fde_vector *vec = ob->u.sort;
867
  int encoding = ob->s.b.encoding;
868
  _Unwind_Ptr base = base_from_object (encoding, ob);
869
  size_t lo, hi;
870
 
871
  for (lo = 0, hi = vec->count; lo < hi; )
872
    {
873
      size_t i = (lo + hi) / 2;
874
      const fde *f = vec->array[i];
875
      _Unwind_Ptr pc_begin, pc_range;
876
      const unsigned char *p;
877
 
878
      p = read_encoded_value_with_base (encoding, base, f->pc_begin,
879
                                        &pc_begin);
880
      read_encoded_value_with_base (encoding & 0x0F, 0, p, &pc_range);
881
 
882
      if ((_Unwind_Ptr) pc < pc_begin)
883
        hi = i;
884
      else if ((_Unwind_Ptr) pc >= pc_begin + pc_range)
885
        lo = i + 1;
886
      else
887
        return f;
888
    }
889
 
890
  return NULL;
891
}
892
 
893
static inline const fde *
894
binary_search_mixed_encoding_fdes (struct object *ob, void *pc)
895
{
896
  struct fde_vector *vec = ob->u.sort;
897
  size_t lo, hi;
898
 
899
  for (lo = 0, hi = vec->count; lo < hi; )
900
    {
901
      size_t i = (lo + hi) / 2;
902
      const fde *f = vec->array[i];
903
      _Unwind_Ptr pc_begin, pc_range;
904
      const unsigned char *p;
905
      int encoding;
906
 
907
      encoding = get_fde_encoding (f);
908
      p = read_encoded_value_with_base (encoding,
909
                                        base_from_object (encoding, ob),
910
                                        f->pc_begin, &pc_begin);
911
      read_encoded_value_with_base (encoding & 0x0F, 0, p, &pc_range);
912
 
913
      if ((_Unwind_Ptr) pc < pc_begin)
914
        hi = i;
915
      else if ((_Unwind_Ptr) pc >= pc_begin + pc_range)
916
        lo = i + 1;
917
      else
918
        return f;
919
    }
920
 
921
  return NULL;
922
}
923
 
924
static const fde *
925
search_object (struct object* ob, void *pc)
926
{
927
  /* If the data hasn't been sorted, try to do this now.  We may have
928
     more memory available than last time we tried.  */
929
  if (! ob->s.b.sorted)
930
    {
931
      init_object (ob);
932
 
933
      /* Despite the above comment, the normal reason to get here is
934
         that we've not processed this object before.  A quick range
935
         check is in order.  */
936
      if (pc < ob->pc_begin)
937
        return NULL;
938
    }
939
 
940
  if (ob->s.b.sorted)
941
    {
942
      if (ob->s.b.mixed_encoding)
943
        return binary_search_mixed_encoding_fdes (ob, pc);
944
      else if (ob->s.b.encoding == DW_EH_PE_absptr)
945
        return binary_search_unencoded_fdes (ob, pc);
946
      else
947
        return binary_search_single_encoding_fdes (ob, pc);
948
    }
949
  else
950
    {
951
      /* Long slow laborious linear search, cos we've no memory.  */
952
      if (ob->s.b.from_array)
953
        {
954
          fde **p;
955
          for (p = ob->u.array; *p ; p++)
956
            {
957
              const fde *f = linear_search_fdes (ob, *p, pc);
958
              if (f)
959
                return f;
960
            }
961
          return NULL;
962
        }
963
      else
964
        return linear_search_fdes (ob, ob->u.single, pc);
965
    }
966
}
967
 
968
const fde *
969
_Unwind_Find_FDE (void *pc, struct dwarf_eh_bases *bases)
970
{
971
  struct object *ob;
972
  const fde *f = NULL;
973
 
974
  init_object_mutex_once ();
975
  __gthread_mutex_lock (&object_mutex);
976
 
977
  /* Linear search through the classified objects, to find the one
978
     containing the pc.  Note that pc_begin is sorted descending, and
979
     we expect objects to be non-overlapping.  */
980
  for (ob = seen_objects; ob; ob = ob->next)
981
    if (pc >= ob->pc_begin)
982
      {
983
        f = search_object (ob, pc);
984
        if (f)
985
          goto fini;
986
        break;
987
      }
988
 
989
  /* Classify and search the objects we've not yet processed.  */
990
  while ((ob = unseen_objects))
991
    {
992
      struct object **p;
993
 
994
      unseen_objects = ob->next;
995
      f = search_object (ob, pc);
996
 
997
      /* Insert the object into the classified list.  */
998
      for (p = &seen_objects; *p ; p = &(*p)->next)
999
        if ((*p)->pc_begin < ob->pc_begin)
1000
          break;
1001
      ob->next = *p;
1002
      *p = ob;
1003
 
1004
      if (f)
1005
        goto fini;
1006
    }
1007
 
1008
 fini:
1009
  __gthread_mutex_unlock (&object_mutex);
1010
 
1011
  if (f)
1012
    {
1013
      int encoding;
1014
      _Unwind_Ptr func;
1015
 
1016
      bases->tbase = ob->tbase;
1017
      bases->dbase = ob->dbase;
1018
 
1019
      encoding = ob->s.b.encoding;
1020
      if (ob->s.b.mixed_encoding)
1021
        encoding = get_fde_encoding (f);
1022
      read_encoded_value_with_base (encoding, base_from_object (encoding, ob),
1023
                                    f->pc_begin, &func);
1024
      bases->func = (void *) func;
1025
    }
1026
 
1027
  return f;
1028
}

powered by: WebSVN 2.1.0

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