OSDN Git Service

gcc
[pf3gnuchains/gcc-fork.git] / gcc / unwind-dw2-fde.c
1 /* 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 "elf/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 \f
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 \f
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 \f
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 = (1L << (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 = (1L << (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 = (1L << (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 }