Merge from mainline
[official-gcc.git] / gcc / unwind-dw2-fde.c
bloba06a5bed87b38345cedb82d56da8ab02080667b2
1 /* Subroutines needed for unwinding stack frames for exception handling. */
2 /* Copyright (C) 1997, 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
3 Contributed by Jason Merrill <jason@cygnus.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
12 In addition to the permissions in the GNU General Public License, the
13 Free Software Foundation gives you unlimited permission to link the
14 compiled version of this file into combinations with other programs,
15 and to distribute those combinations without any restriction coming
16 from the use of this file. (The General Public License restrictions
17 do apply in other respects; for example, they cover modification of
18 the file, and distribution when not linked into a combine
19 executable.)
21 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
22 WARRANTY; without even the implied warranty of MERCHANTABILITY or
23 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
24 for more details.
26 You should have received a copy of the GNU General Public License
27 along with GCC; see the file COPYING. If not, write to the Free
28 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
29 02111-1307, USA. */
31 #ifndef _Unwind_Find_FDE
32 #include "tconfig.h"
33 #include "tsystem.h"
34 #include "dwarf2.h"
35 #include "unwind.h"
36 #define NO_BASE_OF_ENCODED_VALUE
37 #include "unwind-pe.h"
38 #include "unwind-dw2-fde.h"
39 #include "gthr.h"
40 #endif
42 /* The unseen_objects list contains objects that have been registered
43 but not yet categorized in any way. The seen_objects list has had
44 it's pc_begin and count fields initialized at minimum, and is sorted
45 by decreasing value of pc_begin. */
46 static struct object *unseen_objects;
47 static struct object *seen_objects;
49 #ifdef __GTHREAD_MUTEX_INIT
50 static __gthread_mutex_t object_mutex = __GTHREAD_MUTEX_INIT;
51 #else
52 static __gthread_mutex_t object_mutex;
53 #endif
55 #ifdef __GTHREAD_MUTEX_INIT_FUNCTION
56 static void
57 init_object_mutex (void)
59 __GTHREAD_MUTEX_INIT_FUNCTION (&object_mutex);
62 static void
63 init_object_mutex_once (void)
65 static __gthread_once_t once = __GTHREAD_ONCE_INIT;
66 __gthread_once (&once, init_object_mutex);
68 #else
69 #define init_object_mutex_once()
70 #endif
72 /* Called from crtbegin.o to register the unwind info for an object. */
74 void
75 __register_frame_info_bases (void *begin, struct object *ob,
76 void *tbase, void *dbase)
78 /* If .eh_frame is empty, don't register at all. */
79 if (*(uword *) begin == 0)
80 return;
82 ob->pc_begin = (void *)-1;
83 ob->tbase = tbase;
84 ob->dbase = dbase;
85 ob->u.single = begin;
86 ob->s.i = 0;
87 ob->s.b.encoding = DW_EH_PE_omit;
89 init_object_mutex_once ();
90 __gthread_mutex_lock (&object_mutex);
92 ob->next = unseen_objects;
93 unseen_objects = ob;
95 __gthread_mutex_unlock (&object_mutex);
98 void
99 __register_frame_info (void *begin, struct object *ob)
101 __register_frame_info_bases (begin, ob, 0, 0);
104 void
105 __register_frame (void *begin)
107 struct object *ob;
109 /* If .eh_frame is empty, don't register at all. */
110 if (*(uword *) begin == 0)
111 return;
113 ob = (struct object *) malloc (sizeof (struct object));
114 __register_frame_info (begin, ob);
117 /* Similar, but BEGIN is actually a pointer to a table of unwind entries
118 for different translation units. Called from the file generated by
119 collect2. */
121 void
122 __register_frame_info_table_bases (void *begin, struct object *ob,
123 void *tbase, void *dbase)
125 ob->pc_begin = (void *)-1;
126 ob->tbase = tbase;
127 ob->dbase = dbase;
128 ob->u.array = begin;
129 ob->s.i = 0;
130 ob->s.b.from_array = 1;
131 ob->s.b.encoding = DW_EH_PE_omit;
133 init_object_mutex_once ();
134 __gthread_mutex_lock (&object_mutex);
136 ob->next = unseen_objects;
137 unseen_objects = ob;
139 __gthread_mutex_unlock (&object_mutex);
142 void
143 __register_frame_info_table (void *begin, struct object *ob)
145 __register_frame_info_table_bases (begin, ob, 0, 0);
148 void
149 __register_frame_table (void *begin)
151 struct object *ob = (struct object *) malloc (sizeof (struct object));
152 __register_frame_info_table (begin, ob);
155 /* Called from crtbegin.o to deregister the unwind info for an object. */
156 /* ??? Glibc has for a while now exported __register_frame_info and
157 __deregister_frame_info. If we call __register_frame_info_bases
158 from crtbegin (wherein it is declared weak), and this object does
159 not get pulled from libgcc.a for other reasons, then the
160 invocation of __deregister_frame_info will be resolved from glibc.
161 Since the registration did not happen there, we'll abort.
163 Therefore, declare a new deregistration entry point that does the
164 exact same thing, but will resolve to the same library as
165 implements __register_frame_info_bases. */
167 void *
168 __deregister_frame_info_bases (void *begin)
170 struct object **p;
171 struct object *ob = 0;
173 /* If .eh_frame is empty, we haven't registered. */
174 if (*(uword *) begin == 0)
175 return ob;
177 init_object_mutex_once ();
178 __gthread_mutex_lock (&object_mutex);
180 for (p = &unseen_objects; *p ; p = &(*p)->next)
181 if ((*p)->u.single == begin)
183 ob = *p;
184 *p = ob->next;
185 goto out;
188 for (p = &seen_objects; *p ; p = &(*p)->next)
189 if ((*p)->s.b.sorted)
191 if ((*p)->u.sort->orig_data == begin)
193 ob = *p;
194 *p = ob->next;
195 free (ob->u.sort);
196 goto out;
199 else
201 if ((*p)->u.single == begin)
203 ob = *p;
204 *p = ob->next;
205 goto out;
209 __gthread_mutex_unlock (&object_mutex);
210 abort ();
212 out:
213 __gthread_mutex_unlock (&object_mutex);
214 return (void *) ob;
217 void *
218 __deregister_frame_info (void *begin)
220 return __deregister_frame_info_bases (begin);
223 void
224 __deregister_frame (void *begin)
226 /* If .eh_frame is empty, we haven't registered. */
227 if (*(uword *) begin != 0)
228 free (__deregister_frame_info (begin));
232 /* Like base_of_encoded_value, but take the base from a struct object
233 instead of an _Unwind_Context. */
235 static _Unwind_Ptr
236 base_from_object (unsigned char encoding, struct object *ob)
238 if (encoding == DW_EH_PE_omit)
239 return 0;
241 switch (encoding & 0x70)
243 case DW_EH_PE_absptr:
244 case DW_EH_PE_pcrel:
245 case DW_EH_PE_aligned:
246 return 0;
248 case DW_EH_PE_textrel:
249 return (_Unwind_Ptr) ob->tbase;
250 case DW_EH_PE_datarel:
251 return (_Unwind_Ptr) ob->dbase;
253 abort ();
256 /* Return the FDE pointer encoding from the CIE. */
257 /* ??? This is a subset of extract_cie_info from unwind-dw2.c. */
259 static int
260 get_cie_encoding (struct dwarf_cie *cie)
262 const unsigned char *aug, *p;
263 _Unwind_Ptr dummy;
264 _Unwind_Word utmp;
265 _Unwind_Sword stmp;
267 aug = cie->augmentation;
268 if (aug[0] != 'z')
269 return DW_EH_PE_absptr;
271 p = aug + strlen (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 p++; /* Skip return address column. */
276 aug++; /* Skip 'z' */
277 p = read_uleb128 (p, &utmp); /* Skip augmentation length. */
278 while (1)
280 /* This is what we're looking for. */
281 if (*aug == 'R')
282 return *p;
283 /* Personality encoding and pointer. */
284 else if (*aug == 'P')
286 /* ??? Avoid dereferencing indirect pointers, since we're
287 faking the base address. Gotta keep DW_EH_PE_aligned
288 intact, however. */
289 p = read_encoded_value_with_base (*p & 0x7F, 0, p + 1, &dummy);
291 /* LSDA encoding. */
292 else if (*aug == 'L')
293 p++;
294 /* Otherwise end of string, or unknown augmentation. */
295 else
296 return DW_EH_PE_absptr;
297 aug++;
301 static inline int
302 get_fde_encoding (struct dwarf_fde *f)
304 return get_cie_encoding (get_cie (f));
308 /* Sorting an array of FDEs by address.
309 (Ideally we would have the linker sort the FDEs so we don't have to do
310 it at run time. But the linkers are not yet prepared for this.) */
312 /* Comparison routines. Three variants of increasing complexity. */
314 static int
315 fde_unencoded_compare (struct object *ob __attribute__((unused)),
316 fde *x, fde *y)
318 _Unwind_Ptr x_ptr = *(_Unwind_Ptr *) x->pc_begin;
319 _Unwind_Ptr y_ptr = *(_Unwind_Ptr *) y->pc_begin;
321 if (x_ptr > y_ptr)
322 return 1;
323 if (x_ptr < y_ptr)
324 return -1;
325 return 0;
328 static int
329 fde_single_encoding_compare (struct object *ob, fde *x, fde *y)
331 _Unwind_Ptr base, x_ptr, y_ptr;
333 base = base_from_object (ob->s.b.encoding, ob);
334 read_encoded_value_with_base (ob->s.b.encoding, base, x->pc_begin, &x_ptr);
335 read_encoded_value_with_base (ob->s.b.encoding, base, y->pc_begin, &y_ptr);
337 if (x_ptr > y_ptr)
338 return 1;
339 if (x_ptr < y_ptr)
340 return -1;
341 return 0;
344 static int
345 fde_mixed_encoding_compare (struct object *ob, fde *x, fde *y)
347 int x_encoding, y_encoding;
348 _Unwind_Ptr x_ptr, y_ptr;
350 x_encoding = get_fde_encoding (x);
351 read_encoded_value_with_base (x_encoding, base_from_object (x_encoding, ob),
352 x->pc_begin, &x_ptr);
354 y_encoding = get_fde_encoding (y);
355 read_encoded_value_with_base (y_encoding, base_from_object (y_encoding, ob),
356 y->pc_begin, &y_ptr);
358 if (x_ptr > y_ptr)
359 return 1;
360 if (x_ptr < y_ptr)
361 return -1;
362 return 0;
365 typedef int (*fde_compare_t) (struct object *, fde *, fde *);
368 /* This is a special mix of insertion sort and heap sort, optimized for
369 the data sets that actually occur. They look like
370 101 102 103 127 128 105 108 110 190 111 115 119 125 160 126 129 130.
371 I.e. a linearly increasing sequence (coming from functions in the text
372 section), with additionally a few unordered elements (coming from functions
373 in gnu_linkonce sections) whose values are higher than the values in the
374 surrounding linear sequence (but not necessarily higher than the values
375 at the end of the linear sequence!).
376 The worst-case total run time is O(N) + O(n log (n)), where N is the
377 total number of FDEs and n is the number of erratic ones. */
379 struct fde_accumulator
381 struct fde_vector *linear;
382 struct fde_vector *erratic;
385 static inline int
386 start_fde_sort (struct fde_accumulator *accu, size_t count)
388 size_t size;
389 if (! count)
390 return 0;
392 size = sizeof (struct fde_vector) + sizeof (fde *) * count;
393 if ((accu->linear = (struct fde_vector *) malloc (size)))
395 accu->linear->count = 0;
396 if ((accu->erratic = (struct fde_vector *) malloc (size)))
397 accu->erratic->count = 0;
398 return 1;
400 else
401 return 0;
404 static inline void
405 fde_insert (struct fde_accumulator *accu, fde *this_fde)
407 if (accu->linear)
408 accu->linear->array[accu->linear->count++] = this_fde;
411 /* Split LINEAR into a linear sequence with low values and an erratic
412 sequence with high values, put the linear one (of longest possible
413 length) into LINEAR and the erratic one into ERRATIC. This is O(N).
415 Because the longest linear sequence we are trying to locate within the
416 incoming LINEAR array can be interspersed with (high valued) erratic
417 entries. We construct a chain indicating the sequenced entries.
418 To avoid having to allocate this chain, we overlay it onto the space of
419 the ERRATIC array during construction. A final pass iterates over the
420 chain to determine what should be placed in the ERRATIC array, and
421 what is the linear sequence. This overlay is safe from aliasing. */
423 static inline void
424 fde_split (struct object *ob, fde_compare_t fde_compare,
425 struct fde_vector *linear, struct fde_vector *erratic)
427 static fde *marker;
428 size_t count = linear->count;
429 fde **chain_end = &marker;
430 size_t i, j, k;
432 /* This should optimize out, but it is wise to make sure this assumption
433 is correct. Should these have different sizes, we cannot cast between
434 them and the overlaying onto ERRATIC will not work. */
435 if (sizeof (fde *) != sizeof (fde **))
436 abort ();
438 for (i = 0; i < count; i++)
440 fde **probe;
442 for (probe = chain_end;
443 probe != &marker && fde_compare (ob, linear->array[i], *probe) < 0;
444 probe = chain_end)
446 chain_end = (fde **) erratic->array[probe - linear->array];
447 erratic->array[probe - linear->array] = NULL;
449 erratic->array[i] = (fde *) chain_end;
450 chain_end = &linear->array[i];
453 /* Each entry in LINEAR which is part of the linear sequence we have
454 discovered will correspond to a non-NULL entry in the chain we built in
455 the ERRATIC array. */
456 for (i = j = k = 0; i < count; i++)
457 if (erratic->array[i])
458 linear->array[j++] = linear->array[i];
459 else
460 erratic->array[k++] = linear->array[i];
461 linear->count = j;
462 erratic->count = k;
465 /* This is O(n log(n)). BSD/OS defines heapsort in stdlib.h, so we must
466 use a name that does not conflict. */
468 static void
469 frame_heapsort (struct object *ob, fde_compare_t fde_compare,
470 struct fde_vector *erratic)
472 /* For a description of this algorithm, see:
473 Samuel P. Harbison, Guy L. Steele Jr.: C, a reference manual, 2nd ed.,
474 p. 60-61. */
475 fde ** a = erratic->array;
476 /* A portion of the array is called a "heap" if for all i>=0:
477 If i and 2i+1 are valid indices, then a[i] >= a[2i+1].
478 If i and 2i+2 are valid indices, then a[i] >= a[2i+2]. */
479 #define SWAP(x,y) do { fde * tmp = x; x = y; y = tmp; } while (0)
480 size_t n = erratic->count;
481 size_t m = n;
482 size_t i;
484 while (m > 0)
486 /* Invariant: a[m..n-1] is a heap. */
487 m--;
488 for (i = m; 2*i+1 < n; )
490 if (2*i+2 < n
491 && fde_compare (ob, a[2*i+2], a[2*i+1]) > 0
492 && fde_compare (ob, a[2*i+2], a[i]) > 0)
494 SWAP (a[i], a[2*i+2]);
495 i = 2*i+2;
497 else if (fde_compare (ob, a[2*i+1], a[i]) > 0)
499 SWAP (a[i], a[2*i+1]);
500 i = 2*i+1;
502 else
503 break;
506 while (n > 1)
508 /* Invariant: a[0..n-1] is a heap. */
509 n--;
510 SWAP (a[0], a[n]);
511 for (i = 0; 2*i+1 < n; )
513 if (2*i+2 < n
514 && fde_compare (ob, a[2*i+2], a[2*i+1]) > 0
515 && fde_compare (ob, a[2*i+2], a[i]) > 0)
517 SWAP (a[i], a[2*i+2]);
518 i = 2*i+2;
520 else if (fde_compare (ob, a[2*i+1], a[i]) > 0)
522 SWAP (a[i], a[2*i+1]);
523 i = 2*i+1;
525 else
526 break;
529 #undef SWAP
532 /* Merge V1 and V2, both sorted, and put the result into V1. */
533 static inline void
534 fde_merge (struct object *ob, fde_compare_t fde_compare,
535 struct fde_vector *v1, struct fde_vector *v2)
537 size_t i1, i2;
538 fde * fde2;
540 i2 = v2->count;
541 if (i2 > 0)
543 i1 = v1->count;
546 i2--;
547 fde2 = v2->array[i2];
548 while (i1 > 0 && fde_compare (ob, v1->array[i1-1], fde2) > 0)
550 v1->array[i1+i2] = v1->array[i1-1];
551 i1--;
553 v1->array[i1+i2] = fde2;
555 while (i2 > 0);
556 v1->count += v2->count;
560 static inline void
561 end_fde_sort (struct object *ob, struct fde_accumulator *accu, size_t count)
563 fde_compare_t fde_compare;
565 if (accu->linear && accu->linear->count != count)
566 abort ();
568 if (ob->s.b.mixed_encoding)
569 fde_compare = fde_mixed_encoding_compare;
570 else if (ob->s.b.encoding == DW_EH_PE_absptr)
571 fde_compare = fde_unencoded_compare;
572 else
573 fde_compare = fde_single_encoding_compare;
575 if (accu->erratic)
577 fde_split (ob, fde_compare, accu->linear, accu->erratic);
578 if (accu->linear->count + accu->erratic->count != count)
579 abort ();
580 frame_heapsort (ob, fde_compare, accu->erratic);
581 fde_merge (ob, fde_compare, accu->linear, accu->erratic);
582 free (accu->erratic);
584 else
586 /* We've not managed to malloc an erratic array,
587 so heap sort in the linear one. */
588 frame_heapsort (ob, fde_compare, accu->linear);
593 /* Update encoding, mixed_encoding, and pc_begin for OB for the
594 fde array beginning at THIS_FDE. Return the number of fdes
595 encountered along the way. */
597 static size_t
598 classify_object_over_fdes (struct object *ob, fde *this_fde)
600 struct dwarf_cie *last_cie = 0;
601 size_t count = 0;
602 int encoding = DW_EH_PE_absptr;
603 _Unwind_Ptr base = 0;
605 for (; this_fde->length != 0; this_fde = next_fde (this_fde))
607 struct dwarf_cie *this_cie;
608 _Unwind_Ptr mask, pc_begin;
610 /* Skip CIEs. */
611 if (this_fde->CIE_delta == 0)
612 continue;
614 /* Determine the encoding for this FDE. Note mixed encoded
615 objects for later. */
616 this_cie = get_cie (this_fde);
617 if (this_cie != last_cie)
619 last_cie = this_cie;
620 encoding = get_cie_encoding (this_cie);
621 base = base_from_object (encoding, ob);
622 if (ob->s.b.encoding == DW_EH_PE_omit)
623 ob->s.b.encoding = encoding;
624 else if (ob->s.b.encoding != encoding)
625 ob->s.b.mixed_encoding = 1;
628 read_encoded_value_with_base (encoding, base, this_fde->pc_begin,
629 &pc_begin);
631 /* Take care to ignore link-once functions that were removed.
632 In these cases, the function address will be NULL, but if
633 the encoding is smaller than a pointer a true NULL may not
634 be representable. Assume 0 in the representable bits is NULL. */
635 mask = size_of_encoded_value (encoding);
636 if (mask < sizeof (void *))
637 mask = (1L << (mask << 3)) - 1;
638 else
639 mask = -1;
641 if ((pc_begin & mask) == 0)
642 continue;
644 count += 1;
645 if ((void *) pc_begin < ob->pc_begin)
646 ob->pc_begin = (void *) pc_begin;
649 return count;
652 static void
653 add_fdes (struct object *ob, struct fde_accumulator *accu, fde *this_fde)
655 struct dwarf_cie *last_cie = 0;
656 int encoding = ob->s.b.encoding;
657 _Unwind_Ptr base = base_from_object (ob->s.b.encoding, ob);
659 for (; this_fde->length != 0; this_fde = next_fde (this_fde))
661 struct dwarf_cie *this_cie;
663 /* Skip CIEs. */
664 if (this_fde->CIE_delta == 0)
665 continue;
667 if (ob->s.b.mixed_encoding)
669 /* Determine the encoding for this FDE. Note mixed encoded
670 objects for later. */
671 this_cie = get_cie (this_fde);
672 if (this_cie != last_cie)
674 last_cie = this_cie;
675 encoding = get_cie_encoding (this_cie);
676 base = base_from_object (encoding, ob);
680 if (encoding == DW_EH_PE_absptr)
682 if (*(_Unwind_Ptr *) this_fde->pc_begin == 0)
683 continue;
685 else
687 _Unwind_Ptr pc_begin, mask;
689 read_encoded_value_with_base (encoding, base, this_fde->pc_begin,
690 &pc_begin);
692 /* Take care to ignore link-once functions that were removed.
693 In these cases, the function address will be NULL, but if
694 the encoding is smaller than a pointer a true NULL may not
695 be representable. Assume 0 in the representable bits is NULL. */
696 mask = size_of_encoded_value (encoding);
697 if (mask < sizeof (void *))
698 mask = (1L << (mask << 3)) - 1;
699 else
700 mask = -1;
702 if ((pc_begin & mask) == 0)
703 continue;
706 fde_insert (accu, this_fde);
710 /* Set up a sorted array of pointers to FDEs for a loaded object. We
711 count up the entries before allocating the array because it's likely to
712 be faster. We can be called multiple times, should we have failed to
713 allocate a sorted fde array on a previous occasion. */
715 static inline void
716 init_object (struct object* ob)
718 struct fde_accumulator accu;
719 size_t count;
721 count = ob->s.b.count;
722 if (count == 0)
724 if (ob->s.b.from_array)
726 fde **p = ob->u.array;
727 for (count = 0; *p; ++p)
728 count += classify_object_over_fdes (ob, *p);
730 else
731 count = classify_object_over_fdes (ob, ob->u.single);
733 /* The count field we have in the main struct object is somewhat
734 limited, but should suffice for virtually all cases. If the
735 counted value doesn't fit, re-write a zero. The worst that
736 happens is that we re-count next time -- admittedly non-trivial
737 in that this implies some 2M fdes, but at least we function. */
738 ob->s.b.count = count;
739 if (ob->s.b.count != count)
740 ob->s.b.count = 0;
743 if (!start_fde_sort (&accu, count))
744 return;
746 if (ob->s.b.from_array)
748 fde **p;
749 for (p = ob->u.array; *p; ++p)
750 add_fdes (ob, &accu, *p);
752 else
753 add_fdes (ob, &accu, ob->u.single);
755 end_fde_sort (ob, &accu, count);
757 /* Save the original fde pointer, since this is the key by which the
758 DSO will deregister the object. */
759 accu.linear->orig_data = ob->u.single;
760 ob->u.sort = accu.linear;
762 ob->s.b.sorted = 1;
765 /* A linear search through a set of FDEs for the given PC. This is
766 used when there was insufficient memory to allocate and sort an
767 array. */
769 static fde *
770 linear_search_fdes (struct object *ob, fde *this_fde, void *pc)
772 struct dwarf_cie *last_cie = 0;
773 int encoding = ob->s.b.encoding;
774 _Unwind_Ptr base = base_from_object (ob->s.b.encoding, ob);
776 for (; this_fde->length != 0; this_fde = next_fde (this_fde))
778 struct dwarf_cie *this_cie;
779 _Unwind_Ptr pc_begin, pc_range;
781 /* Skip CIEs. */
782 if (this_fde->CIE_delta == 0)
783 continue;
785 if (ob->s.b.mixed_encoding)
787 /* Determine the encoding for this FDE. Note mixed encoded
788 objects for later. */
789 this_cie = get_cie (this_fde);
790 if (this_cie != last_cie)
792 last_cie = this_cie;
793 encoding = get_cie_encoding (this_cie);
794 base = base_from_object (encoding, ob);
798 if (encoding == DW_EH_PE_absptr)
800 pc_begin = ((_Unwind_Ptr *) this_fde->pc_begin)[0];
801 pc_range = ((_Unwind_Ptr *) this_fde->pc_begin)[1];
802 if (pc_begin == 0)
803 continue;
805 else
807 _Unwind_Ptr mask;
808 const char *p;
810 p = read_encoded_value_with_base (encoding, base,
811 this_fde->pc_begin, &pc_begin);
812 read_encoded_value_with_base (encoding & 0x0F, 0, p, &pc_range);
814 /* Take care to ignore link-once functions that were removed.
815 In these cases, the function address will be NULL, but if
816 the encoding is smaller than a pointer a true NULL may not
817 be representable. Assume 0 in the representable bits is NULL. */
818 mask = size_of_encoded_value (encoding);
819 if (mask < sizeof (void *))
820 mask = (1L << (mask << 3)) - 1;
821 else
822 mask = -1;
824 if ((pc_begin & mask) == 0)
825 continue;
828 if ((_Unwind_Ptr) pc - pc_begin < pc_range)
829 return this_fde;
832 return NULL;
835 /* Binary search for an FDE containing the given PC. Here are three
836 implementations of increasing complexity. */
838 static inline fde *
839 binary_search_unencoded_fdes (struct object *ob, void *pc)
841 struct fde_vector *vec = ob->u.sort;
842 size_t lo, hi;
844 for (lo = 0, hi = vec->count; lo < hi; )
846 size_t i = (lo + hi) / 2;
847 fde *f = vec->array[i];
848 void *pc_begin;
849 uaddr pc_range;
851 pc_begin = ((void **) f->pc_begin)[0];
852 pc_range = ((uaddr *) f->pc_begin)[1];
854 if (pc < pc_begin)
855 hi = i;
856 else if (pc >= pc_begin + pc_range)
857 lo = i + 1;
858 else
859 return f;
862 return NULL;
865 static inline fde *
866 binary_search_single_encoding_fdes (struct object *ob, void *pc)
868 struct fde_vector *vec = ob->u.sort;
869 int encoding = ob->s.b.encoding;
870 _Unwind_Ptr base = base_from_object (encoding, ob);
871 size_t lo, hi;
873 for (lo = 0, hi = vec->count; lo < hi; )
875 size_t i = (lo + hi) / 2;
876 fde *f = vec->array[i];
877 _Unwind_Ptr pc_begin, pc_range;
878 const char *p;
880 p = read_encoded_value_with_base (encoding, base, f->pc_begin,
881 &pc_begin);
882 read_encoded_value_with_base (encoding & 0x0F, 0, p, &pc_range);
884 if ((_Unwind_Ptr) pc < pc_begin)
885 hi = i;
886 else if ((_Unwind_Ptr) pc >= pc_begin + pc_range)
887 lo = i + 1;
888 else
889 return f;
892 return NULL;
895 static inline fde *
896 binary_search_mixed_encoding_fdes (struct object *ob, void *pc)
898 struct fde_vector *vec = ob->u.sort;
899 size_t lo, hi;
901 for (lo = 0, hi = vec->count; lo < hi; )
903 size_t i = (lo + hi) / 2;
904 fde *f = vec->array[i];
905 _Unwind_Ptr pc_begin, pc_range;
906 const char *p;
907 int encoding;
909 encoding = get_fde_encoding (f);
910 p = read_encoded_value_with_base (encoding,
911 base_from_object (encoding, ob),
912 f->pc_begin, &pc_begin);
913 read_encoded_value_with_base (encoding & 0x0F, 0, p, &pc_range);
915 if ((_Unwind_Ptr) pc < pc_begin)
916 hi = i;
917 else if ((_Unwind_Ptr) pc >= pc_begin + pc_range)
918 lo = i + 1;
919 else
920 return f;
923 return NULL;
926 static fde *
927 search_object (struct object* ob, void *pc)
929 /* If the data hasn't been sorted, try to do this now. We may have
930 more memory available than last time we tried. */
931 if (! ob->s.b.sorted)
933 init_object (ob);
935 /* Despite the above comment, the normal reason to get here is
936 that we've not processed this object before. A quick range
937 check is in order. */
938 if (pc < ob->pc_begin)
939 return NULL;
942 if (ob->s.b.sorted)
944 if (ob->s.b.mixed_encoding)
945 return binary_search_mixed_encoding_fdes (ob, pc);
946 else if (ob->s.b.encoding == DW_EH_PE_absptr)
947 return binary_search_unencoded_fdes (ob, pc);
948 else
949 return binary_search_single_encoding_fdes (ob, pc);
951 else
953 /* Long slow labourious linear search, cos we've no memory. */
954 if (ob->s.b.from_array)
956 fde **p;
957 for (p = ob->u.array; *p ; p++)
959 fde *f = linear_search_fdes (ob, *p, pc);
960 if (f)
961 return f;
963 return NULL;
965 else
966 return linear_search_fdes (ob, ob->u.single, pc);
970 fde *
971 _Unwind_Find_FDE (void *pc, struct dwarf_eh_bases *bases)
973 struct object *ob;
974 fde *f = NULL;
976 init_object_mutex_once ();
977 __gthread_mutex_lock (&object_mutex);
979 /* Linear search through the classified objects, to find the one
980 containing the pc. Note that pc_begin is sorted descending, and
981 we expect objects to be non-overlapping. */
982 for (ob = seen_objects; ob; ob = ob->next)
983 if (pc >= ob->pc_begin)
985 f = search_object (ob, pc);
986 if (f)
987 goto fini;
988 break;
991 /* Classify and search the objects we've not yet processed. */
992 while ((ob = unseen_objects))
994 struct object **p;
996 unseen_objects = ob->next;
997 f = search_object (ob, pc);
999 /* Insert the object into the classified list. */
1000 for (p = &seen_objects; *p ; p = &(*p)->next)
1001 if ((*p)->pc_begin < ob->pc_begin)
1002 break;
1003 ob->next = *p;
1004 *p = ob;
1006 if (f)
1007 goto fini;
1010 fini:
1011 __gthread_mutex_unlock (&object_mutex);
1013 if (f)
1015 int encoding;
1017 bases->tbase = ob->tbase;
1018 bases->dbase = ob->dbase;
1020 encoding = ob->s.b.encoding;
1021 if (ob->s.b.mixed_encoding)
1022 encoding = get_fde_encoding (f);
1023 read_encoded_value_with_base (encoding, base_from_object (encoding, ob),
1024 f->pc_begin, (_Unwind_Ptr *)&bases->func);
1027 return f;