Daily bump.
[official-gcc.git] / libgcc / unwind-dw2-fde.c
blob5d2213c3f88f3a496da74a6fea0b41046c9bd941
1 /* Subroutines needed for unwinding stack frames for exception handling. */
2 /* Copyright (C) 1997-2021 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 3, or (at your option) any later
10 version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
17 Under Section 7 of GPL version 3, you are granted additional
18 permissions described in the GCC Runtime Library Exception, version
19 3.1, as published by the Free Software Foundation.
21 You should have received a copy of the GNU General Public License and
22 a copy of the GCC Runtime Library Exception along with this program;
23 see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 <http://www.gnu.org/licenses/>. */
26 #ifndef _Unwind_Find_FDE
27 #include "tconfig.h"
28 #include "tsystem.h"
29 #include "coretypes.h"
30 #include "tm.h"
31 #include "libgcc_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 #else
39 #if (defined(__GTHREAD_MUTEX_INIT) || defined(__GTHREAD_MUTEX_INIT_FUNCTION)) \
40 && defined(__GCC_HAVE_SYNC_COMPARE_AND_SWAP_4)
41 #define ATOMIC_FDE_FAST_PATH 1
42 #endif
43 #endif
45 /* The unseen_objects list contains objects that have been registered
46 but not yet categorized in any way. The seen_objects list has had
47 its pc_begin and count fields initialized at minimum, and is sorted
48 by decreasing value of pc_begin. */
49 static struct object *unseen_objects;
50 static struct object *seen_objects;
51 #ifdef ATOMIC_FDE_FAST_PATH
52 static int any_objects_registered;
53 #endif
55 #ifdef __GTHREAD_MUTEX_INIT
56 static __gthread_mutex_t object_mutex = __GTHREAD_MUTEX_INIT;
57 #define init_object_mutex_once()
58 #else
59 #ifdef __GTHREAD_MUTEX_INIT_FUNCTION
60 static __gthread_mutex_t object_mutex;
62 static void
63 init_object_mutex (void)
65 __GTHREAD_MUTEX_INIT_FUNCTION (&object_mutex);
68 static void
69 init_object_mutex_once (void)
71 static __gthread_once_t once = __GTHREAD_ONCE_INIT;
72 __gthread_once (&once, init_object_mutex);
74 #else
75 /* ??? Several targets include this file with stubbing parts of gthr.h
76 and expect no locking to be done. */
77 #define init_object_mutex_once()
78 static __gthread_mutex_t object_mutex;
79 #endif
80 #endif
82 /* Called from crtbegin.o to register the unwind info for an object. */
84 void
85 __register_frame_info_bases (const void *begin, struct object *ob,
86 void *tbase, void *dbase)
88 /* If .eh_frame is empty, don't register at all. */
89 if ((const uword *) begin == 0 || *(const uword *) begin == 0)
90 return;
92 ob->pc_begin = (void *)-1;
93 ob->tbase = tbase;
94 ob->dbase = dbase;
95 ob->u.single = begin;
96 ob->s.i = 0;
97 ob->s.b.encoding = DW_EH_PE_omit;
98 #ifdef DWARF2_OBJECT_END_PTR_EXTENSION
99 ob->fde_end = NULL;
100 #endif
102 init_object_mutex_once ();
103 __gthread_mutex_lock (&object_mutex);
105 ob->next = unseen_objects;
106 unseen_objects = ob;
107 #ifdef ATOMIC_FDE_FAST_PATH
108 /* Set flag that at least one library has registered FDEs.
109 Use relaxed MO here, it is up to the app to ensure that the library
110 loading/initialization happens-before using that library in other
111 threads (in particular unwinding with that library's functions
112 appearing in the backtraces). Calling that library's functions
113 without waiting for the library to initialize would be racy. */
114 if (!any_objects_registered)
115 __atomic_store_n (&any_objects_registered, 1, __ATOMIC_RELAXED);
116 #endif
118 __gthread_mutex_unlock (&object_mutex);
121 void
122 __register_frame_info (const void *begin, struct object *ob)
124 __register_frame_info_bases (begin, ob, 0, 0);
127 void
128 __register_frame (void *begin)
130 struct object *ob;
132 /* If .eh_frame is empty, don't register at all. */
133 if (*(uword *) begin == 0)
134 return;
136 ob = malloc (sizeof (struct object));
137 __register_frame_info (begin, ob);
140 /* Similar, but BEGIN is actually a pointer to a table of unwind entries
141 for different translation units. Called from the file generated by
142 collect2. */
144 void
145 __register_frame_info_table_bases (void *begin, struct object *ob,
146 void *tbase, void *dbase)
148 ob->pc_begin = (void *)-1;
149 ob->tbase = tbase;
150 ob->dbase = dbase;
151 ob->u.array = begin;
152 ob->s.i = 0;
153 ob->s.b.from_array = 1;
154 ob->s.b.encoding = DW_EH_PE_omit;
156 init_object_mutex_once ();
157 __gthread_mutex_lock (&object_mutex);
159 ob->next = unseen_objects;
160 unseen_objects = ob;
161 #ifdef ATOMIC_FDE_FAST_PATH
162 /* Set flag that at least one library has registered FDEs.
163 Use relaxed MO here, it is up to the app to ensure that the library
164 loading/initialization happens-before using that library in other
165 threads (in particular unwinding with that library's functions
166 appearing in the backtraces). Calling that library's functions
167 without waiting for the library to initialize would be racy. */
168 if (!any_objects_registered)
169 __atomic_store_n (&any_objects_registered, 1, __ATOMIC_RELAXED);
170 #endif
172 __gthread_mutex_unlock (&object_mutex);
175 void
176 __register_frame_info_table (void *begin, struct object *ob)
178 __register_frame_info_table_bases (begin, ob, 0, 0);
181 void
182 __register_frame_table (void *begin)
184 struct object *ob = malloc (sizeof (struct object));
185 __register_frame_info_table (begin, ob);
188 /* Called from crtbegin.o to deregister the unwind info for an object. */
189 /* ??? Glibc has for a while now exported __register_frame_info and
190 __deregister_frame_info. If we call __register_frame_info_bases
191 from crtbegin (wherein it is declared weak), and this object does
192 not get pulled from libgcc.a for other reasons, then the
193 invocation of __deregister_frame_info will be resolved from glibc.
194 Since the registration did not happen there, we'll die.
196 Therefore, declare a new deregistration entry point that does the
197 exact same thing, but will resolve to the same library as
198 implements __register_frame_info_bases. */
200 void *
201 __deregister_frame_info_bases (const void *begin)
203 struct object **p;
204 struct object *ob = 0;
206 /* If .eh_frame is empty, we haven't registered. */
207 if ((const uword *) begin == 0 || *(const uword *) begin == 0)
208 return ob;
210 init_object_mutex_once ();
211 __gthread_mutex_lock (&object_mutex);
213 for (p = &unseen_objects; *p ; p = &(*p)->next)
214 if ((*p)->u.single == begin)
216 ob = *p;
217 *p = ob->next;
218 goto out;
221 for (p = &seen_objects; *p ; p = &(*p)->next)
222 if ((*p)->s.b.sorted)
224 if ((*p)->u.sort->orig_data == begin)
226 ob = *p;
227 *p = ob->next;
228 free (ob->u.sort);
229 goto out;
232 else
234 if ((*p)->u.single == begin)
236 ob = *p;
237 *p = ob->next;
238 goto out;
242 out:
243 __gthread_mutex_unlock (&object_mutex);
244 gcc_assert (ob);
245 return (void *) ob;
248 void *
249 __deregister_frame_info (const void *begin)
251 return __deregister_frame_info_bases (begin);
254 void
255 __deregister_frame (void *begin)
257 /* If .eh_frame is empty, we haven't registered. */
258 if (*(uword *) begin != 0)
259 free (__deregister_frame_info (begin));
263 /* Like base_of_encoded_value, but take the base from a struct object
264 instead of an _Unwind_Context. */
266 static _Unwind_Ptr
267 base_from_object (unsigned char encoding, struct object *ob)
269 if (encoding == DW_EH_PE_omit)
270 return 0;
272 switch (encoding & 0x70)
274 case DW_EH_PE_absptr:
275 case DW_EH_PE_pcrel:
276 case DW_EH_PE_aligned:
277 return 0;
279 case DW_EH_PE_textrel:
280 return (_Unwind_Ptr) ob->tbase;
281 case DW_EH_PE_datarel:
282 return (_Unwind_Ptr) ob->dbase;
283 default:
284 gcc_unreachable ();
288 /* Return the FDE pointer encoding from the CIE. */
289 /* ??? This is a subset of extract_cie_info from unwind-dw2.c. */
291 static int
292 get_cie_encoding (const struct dwarf_cie *cie)
294 const unsigned char *aug, *p;
295 _Unwind_Ptr dummy;
296 _uleb128_t utmp;
297 _sleb128_t stmp;
299 aug = cie->augmentation;
300 p = aug + strlen ((const char *)aug) + 1; /* Skip the augmentation string. */
301 if (__builtin_expect (cie->version >= 4, 0))
303 if (p[0] != sizeof (void *) || p[1] != 0)
304 return DW_EH_PE_omit; /* We are not prepared to handle unexpected
305 address sizes or segment selectors. */
306 p += 2; /* Skip address size and segment size. */
309 if (aug[0] != 'z')
310 return DW_EH_PE_absptr;
312 p = read_uleb128 (p, &utmp); /* Skip code alignment. */
313 p = read_sleb128 (p, &stmp); /* Skip data alignment. */
314 if (cie->version == 1) /* Skip return address column. */
315 p++;
316 else
317 p = read_uleb128 (p, &utmp);
319 aug++; /* Skip 'z' */
320 p = read_uleb128 (p, &utmp); /* Skip augmentation length. */
321 while (1)
323 /* This is what we're looking for. */
324 if (*aug == 'R')
325 return *p;
326 /* Personality encoding and pointer. */
327 else if (*aug == 'P')
329 /* ??? Avoid dereferencing indirect pointers, since we're
330 faking the base address. Gotta keep DW_EH_PE_aligned
331 intact, however. */
332 p = read_encoded_value_with_base (*p & 0x7F, 0, p + 1, &dummy);
334 /* LSDA encoding. */
335 else if (*aug == 'L')
336 p++;
337 /* aarch64 b-key pointer authentication. */
338 else if (*aug == 'B')
339 p++;
340 /* Otherwise end of string, or unknown augmentation. */
341 else
342 return DW_EH_PE_absptr;
343 aug++;
347 static inline int
348 get_fde_encoding (const struct dwarf_fde *f)
350 return get_cie_encoding (get_cie (f));
354 /* Sorting an array of FDEs by address.
355 (Ideally we would have the linker sort the FDEs so we don't have to do
356 it at run time. But the linkers are not yet prepared for this.) */
358 /* Comparison routines. Three variants of increasing complexity. */
360 static int
361 fde_unencoded_compare (struct object *ob __attribute__((unused)),
362 const fde *x, const fde *y)
364 _Unwind_Ptr x_ptr, y_ptr;
365 memcpy (&x_ptr, x->pc_begin, sizeof (_Unwind_Ptr));
366 memcpy (&y_ptr, y->pc_begin, sizeof (_Unwind_Ptr));
368 if (x_ptr > y_ptr)
369 return 1;
370 if (x_ptr < y_ptr)
371 return -1;
372 return 0;
375 static int
376 fde_single_encoding_compare (struct object *ob, const fde *x, const fde *y)
378 _Unwind_Ptr base, x_ptr, y_ptr;
380 base = base_from_object (ob->s.b.encoding, ob);
381 read_encoded_value_with_base (ob->s.b.encoding, base, x->pc_begin, &x_ptr);
382 read_encoded_value_with_base (ob->s.b.encoding, base, y->pc_begin, &y_ptr);
384 if (x_ptr > y_ptr)
385 return 1;
386 if (x_ptr < y_ptr)
387 return -1;
388 return 0;
391 static int
392 fde_mixed_encoding_compare (struct object *ob, const fde *x, const fde *y)
394 int x_encoding, y_encoding;
395 _Unwind_Ptr x_ptr, y_ptr;
397 x_encoding = get_fde_encoding (x);
398 read_encoded_value_with_base (x_encoding, base_from_object (x_encoding, ob),
399 x->pc_begin, &x_ptr);
401 y_encoding = get_fde_encoding (y);
402 read_encoded_value_with_base (y_encoding, base_from_object (y_encoding, ob),
403 y->pc_begin, &y_ptr);
405 if (x_ptr > y_ptr)
406 return 1;
407 if (x_ptr < y_ptr)
408 return -1;
409 return 0;
412 typedef int (*fde_compare_t) (struct object *, const fde *, const fde *);
415 /* This is a special mix of insertion sort and heap sort, optimized for
416 the data sets that actually occur. They look like
417 101 102 103 127 128 105 108 110 190 111 115 119 125 160 126 129 130.
418 I.e. a linearly increasing sequence (coming from functions in the text
419 section), with additionally a few unordered elements (coming from functions
420 in gnu_linkonce sections) whose values are higher than the values in the
421 surrounding linear sequence (but not necessarily higher than the values
422 at the end of the linear sequence!).
423 The worst-case total run time is O(N) + O(n log (n)), where N is the
424 total number of FDEs and n is the number of erratic ones. */
426 struct fde_accumulator
428 struct fde_vector *linear;
429 struct fde_vector *erratic;
432 static inline int
433 start_fde_sort (struct fde_accumulator *accu, size_t count)
435 size_t size;
436 if (! count)
437 return 0;
439 size = sizeof (struct fde_vector) + sizeof (const fde *) * count;
440 if ((accu->linear = malloc (size)))
442 accu->linear->count = 0;
443 if ((accu->erratic = malloc (size)))
444 accu->erratic->count = 0;
445 return 1;
447 else
448 return 0;
451 static inline void
452 fde_insert (struct fde_accumulator *accu, const fde *this_fde)
454 if (accu->linear)
455 accu->linear->array[accu->linear->count++] = this_fde;
458 /* Split LINEAR into a linear sequence with low values and an erratic
459 sequence with high values, put the linear one (of longest possible
460 length) into LINEAR and the erratic one into ERRATIC. This is O(N).
462 Because the longest linear sequence we are trying to locate within the
463 incoming LINEAR array can be interspersed with (high valued) erratic
464 entries. We construct a chain indicating the sequenced entries.
465 To avoid having to allocate this chain, we overlay it onto the space of
466 the ERRATIC array during construction. A final pass iterates over the
467 chain to determine what should be placed in the ERRATIC array, and
468 what is the linear sequence. This overlay is safe from aliasing. */
470 static inline void
471 fde_split (struct object *ob, fde_compare_t fde_compare,
472 struct fde_vector *linear, struct fde_vector *erratic)
474 static const fde *marker;
475 size_t count = linear->count;
476 const fde *const *chain_end = &marker;
477 size_t i, j, k;
479 /* This should optimize out, but it is wise to make sure this assumption
480 is correct. Should these have different sizes, we cannot cast between
481 them and the overlaying onto ERRATIC will not work. */
482 gcc_assert (sizeof (const fde *) == sizeof (const fde **));
484 for (i = 0; i < count; i++)
486 const fde *const *probe;
488 for (probe = chain_end;
489 probe != &marker && fde_compare (ob, linear->array[i], *probe) < 0;
490 probe = chain_end)
492 chain_end = (const fde *const*) erratic->array[probe - linear->array];
493 erratic->array[probe - linear->array] = NULL;
495 erratic->array[i] = (const fde *) chain_end;
496 chain_end = &linear->array[i];
499 /* Each entry in LINEAR which is part of the linear sequence we have
500 discovered will correspond to a non-NULL entry in the chain we built in
501 the ERRATIC array. */
502 for (i = j = k = 0; i < count; i++)
503 if (erratic->array[i])
504 linear->array[j++] = linear->array[i];
505 else
506 erratic->array[k++] = linear->array[i];
507 linear->count = j;
508 erratic->count = k;
511 #define SWAP(x,y) do { const fde * tmp = x; x = y; y = tmp; } while (0)
513 /* Convert a semi-heap to a heap. A semi-heap is a heap except possibly
514 for the first (root) node; push it down to its rightful place. */
516 static void
517 frame_downheap (struct object *ob, fde_compare_t fde_compare, const fde **a,
518 int lo, int hi)
520 int i, j;
522 for (i = lo, j = 2*i+1;
523 j < hi;
524 j = 2*i+1)
526 if (j+1 < hi && fde_compare (ob, a[j], a[j+1]) < 0)
527 ++j;
529 if (fde_compare (ob, a[i], a[j]) < 0)
531 SWAP (a[i], a[j]);
532 i = j;
534 else
535 break;
539 /* This is O(n log(n)). BSD/OS defines heapsort in stdlib.h, so we must
540 use a name that does not conflict. */
542 static void
543 frame_heapsort (struct object *ob, fde_compare_t fde_compare,
544 struct fde_vector *erratic)
546 /* For a description of this algorithm, see:
547 Samuel P. Harbison, Guy L. Steele Jr.: C, a reference manual, 2nd ed.,
548 p. 60-61. */
549 const fde ** a = erratic->array;
550 /* A portion of the array is called a "heap" if for all i>=0:
551 If i and 2i+1 are valid indices, then a[i] >= a[2i+1].
552 If i and 2i+2 are valid indices, then a[i] >= a[2i+2]. */
553 size_t n = erratic->count;
554 int m;
556 /* Expand our heap incrementally from the end of the array, heapifying
557 each resulting semi-heap as we go. After each step, a[m] is the top
558 of a heap. */
559 for (m = n/2-1; m >= 0; --m)
560 frame_downheap (ob, fde_compare, a, m, n);
562 /* Shrink our heap incrementally from the end of the array, first
563 swapping out the largest element a[0] and then re-heapifying the
564 resulting semi-heap. After each step, a[0..m) is a heap. */
565 for (m = n-1; m >= 1; --m)
567 SWAP (a[0], a[m]);
568 frame_downheap (ob, fde_compare, a, 0, m);
570 #undef SWAP
573 /* Merge V1 and V2, both sorted, and put the result into V1. */
574 static inline void
575 fde_merge (struct object *ob, fde_compare_t fde_compare,
576 struct fde_vector *v1, struct fde_vector *v2)
578 size_t i1, i2;
579 const fde * fde2;
581 i2 = v2->count;
582 if (i2 > 0)
584 i1 = v1->count;
587 i2--;
588 fde2 = v2->array[i2];
589 while (i1 > 0 && fde_compare (ob, v1->array[i1-1], fde2) > 0)
591 v1->array[i1+i2] = v1->array[i1-1];
592 i1--;
594 v1->array[i1+i2] = fde2;
596 while (i2 > 0);
597 v1->count += v2->count;
601 static inline void
602 end_fde_sort (struct object *ob, struct fde_accumulator *accu, size_t count)
604 fde_compare_t fde_compare;
606 gcc_assert (!accu->linear || accu->linear->count == count);
608 if (ob->s.b.mixed_encoding)
609 fde_compare = fde_mixed_encoding_compare;
610 else if (ob->s.b.encoding == DW_EH_PE_absptr)
611 fde_compare = fde_unencoded_compare;
612 else
613 fde_compare = fde_single_encoding_compare;
615 if (accu->erratic)
617 fde_split (ob, fde_compare, accu->linear, accu->erratic);
618 gcc_assert (accu->linear->count + accu->erratic->count == count);
619 frame_heapsort (ob, fde_compare, accu->erratic);
620 fde_merge (ob, fde_compare, accu->linear, accu->erratic);
621 free (accu->erratic);
623 else
625 /* We've not managed to malloc an erratic array,
626 so heap sort in the linear one. */
627 frame_heapsort (ob, fde_compare, accu->linear);
632 /* Update encoding, mixed_encoding, and pc_begin for OB for the
633 fde array beginning at THIS_FDE. Return the number of fdes
634 encountered along the way. */
636 static size_t
637 classify_object_over_fdes (struct object *ob, const fde *this_fde)
639 const struct dwarf_cie *last_cie = 0;
640 size_t count = 0;
641 int encoding = DW_EH_PE_absptr;
642 _Unwind_Ptr base = 0;
644 for (; ! last_fde (ob, this_fde); this_fde = next_fde (this_fde))
646 const struct dwarf_cie *this_cie;
647 _Unwind_Ptr mask, pc_begin;
649 /* Skip CIEs. */
650 if (this_fde->CIE_delta == 0)
651 continue;
653 /* Determine the encoding for this FDE. Note mixed encoded
654 objects for later. */
655 this_cie = get_cie (this_fde);
656 if (this_cie != last_cie)
658 last_cie = this_cie;
659 encoding = get_cie_encoding (this_cie);
660 if (encoding == DW_EH_PE_omit)
661 return -1;
662 base = base_from_object (encoding, ob);
663 if (ob->s.b.encoding == DW_EH_PE_omit)
664 ob->s.b.encoding = encoding;
665 else if (ob->s.b.encoding != encoding)
666 ob->s.b.mixed_encoding = 1;
669 read_encoded_value_with_base (encoding, base, this_fde->pc_begin,
670 &pc_begin);
672 /* Take care to ignore link-once functions that were removed.
673 In these cases, the function address will be NULL, but if
674 the encoding is smaller than a pointer a true NULL may not
675 be representable. Assume 0 in the representable bits is NULL. */
676 mask = size_of_encoded_value (encoding);
677 if (mask < sizeof (void *))
678 mask = (((_Unwind_Ptr) 1) << (mask << 3)) - 1;
679 else
680 mask = -1;
682 if ((pc_begin & mask) == 0)
683 continue;
685 count += 1;
686 if ((void *) pc_begin < ob->pc_begin)
687 ob->pc_begin = (void *) pc_begin;
690 return count;
693 static void
694 add_fdes (struct object *ob, struct fde_accumulator *accu, const fde *this_fde)
696 const struct dwarf_cie *last_cie = 0;
697 int encoding = ob->s.b.encoding;
698 _Unwind_Ptr base = base_from_object (ob->s.b.encoding, ob);
700 for (; ! last_fde (ob, this_fde); this_fde = next_fde (this_fde))
702 const struct dwarf_cie *this_cie;
704 /* Skip CIEs. */
705 if (this_fde->CIE_delta == 0)
706 continue;
708 if (ob->s.b.mixed_encoding)
710 /* Determine the encoding for this FDE. Note mixed encoded
711 objects for later. */
712 this_cie = get_cie (this_fde);
713 if (this_cie != last_cie)
715 last_cie = this_cie;
716 encoding = get_cie_encoding (this_cie);
717 base = base_from_object (encoding, ob);
721 if (encoding == DW_EH_PE_absptr)
723 _Unwind_Ptr ptr;
724 memcpy (&ptr, this_fde->pc_begin, sizeof (_Unwind_Ptr));
725 if (ptr == 0)
726 continue;
728 else
730 _Unwind_Ptr pc_begin, mask;
732 read_encoded_value_with_base (encoding, base, this_fde->pc_begin,
733 &pc_begin);
735 /* Take care to ignore link-once functions that were removed.
736 In these cases, the function address will be NULL, but if
737 the encoding is smaller than a pointer a true NULL may not
738 be representable. Assume 0 in the representable bits is NULL. */
739 mask = size_of_encoded_value (encoding);
740 if (mask < sizeof (void *))
741 mask = (((_Unwind_Ptr) 1) << (mask << 3)) - 1;
742 else
743 mask = -1;
745 if ((pc_begin & mask) == 0)
746 continue;
749 fde_insert (accu, this_fde);
753 /* Set up a sorted array of pointers to FDEs for a loaded object. We
754 count up the entries before allocating the array because it's likely to
755 be faster. We can be called multiple times, should we have failed to
756 allocate a sorted fde array on a previous occasion. */
758 static inline void
759 init_object (struct object* ob)
761 struct fde_accumulator accu;
762 size_t count;
764 count = ob->s.b.count;
765 if (count == 0)
767 if (ob->s.b.from_array)
769 fde **p = ob->u.array;
770 for (count = 0; *p; ++p)
772 size_t cur_count = classify_object_over_fdes (ob, *p);
773 if (cur_count == (size_t) -1)
774 goto unhandled_fdes;
775 count += cur_count;
778 else
780 count = classify_object_over_fdes (ob, ob->u.single);
781 if (count == (size_t) -1)
783 static const fde terminator;
784 unhandled_fdes:
785 ob->s.i = 0;
786 ob->s.b.encoding = DW_EH_PE_omit;
787 ob->u.single = &terminator;
788 return;
792 /* The count field we have in the main struct object is somewhat
793 limited, but should suffice for virtually all cases. If the
794 counted value doesn't fit, re-write a zero. The worst that
795 happens is that we re-count next time -- admittedly non-trivial
796 in that this implies some 2M fdes, but at least we function. */
797 ob->s.b.count = count;
798 if (ob->s.b.count != count)
799 ob->s.b.count = 0;
802 if (!start_fde_sort (&accu, count))
803 return;
805 if (ob->s.b.from_array)
807 fde **p;
808 for (p = ob->u.array; *p; ++p)
809 add_fdes (ob, &accu, *p);
811 else
812 add_fdes (ob, &accu, ob->u.single);
814 end_fde_sort (ob, &accu, count);
816 /* Save the original fde pointer, since this is the key by which the
817 DSO will deregister the object. */
818 accu.linear->orig_data = ob->u.single;
819 ob->u.sort = accu.linear;
821 ob->s.b.sorted = 1;
824 /* A linear search through a set of FDEs for the given PC. This is
825 used when there was insufficient memory to allocate and sort an
826 array. */
828 static const fde *
829 linear_search_fdes (struct object *ob, const fde *this_fde, void *pc)
831 const struct dwarf_cie *last_cie = 0;
832 int encoding = ob->s.b.encoding;
833 _Unwind_Ptr base = base_from_object (ob->s.b.encoding, ob);
835 for (; ! last_fde (ob, this_fde); this_fde = next_fde (this_fde))
837 const struct dwarf_cie *this_cie;
838 _Unwind_Ptr pc_begin, pc_range;
840 /* Skip CIEs. */
841 if (this_fde->CIE_delta == 0)
842 continue;
844 if (ob->s.b.mixed_encoding)
846 /* Determine the encoding for this FDE. Note mixed encoded
847 objects for later. */
848 this_cie = get_cie (this_fde);
849 if (this_cie != last_cie)
851 last_cie = this_cie;
852 encoding = get_cie_encoding (this_cie);
853 base = base_from_object (encoding, ob);
857 if (encoding == DW_EH_PE_absptr)
859 const _Unwind_Ptr *pc_array = (const _Unwind_Ptr *) this_fde->pc_begin;
860 pc_begin = pc_array[0];
861 pc_range = pc_array[1];
862 if (pc_begin == 0)
863 continue;
865 else
867 _Unwind_Ptr mask;
868 const unsigned char *p;
870 p = read_encoded_value_with_base (encoding, base,
871 this_fde->pc_begin, &pc_begin);
872 read_encoded_value_with_base (encoding & 0x0F, 0, p, &pc_range);
874 /* Take care to ignore link-once functions that were removed.
875 In these cases, the function address will be NULL, but if
876 the encoding is smaller than a pointer a true NULL may not
877 be representable. Assume 0 in the representable bits is NULL. */
878 mask = size_of_encoded_value (encoding);
879 if (mask < sizeof (void *))
880 mask = (((_Unwind_Ptr) 1) << (mask << 3)) - 1;
881 else
882 mask = -1;
884 if ((pc_begin & mask) == 0)
885 continue;
888 if ((_Unwind_Ptr) pc - pc_begin < pc_range)
889 return this_fde;
892 return NULL;
895 /* Binary search for an FDE containing the given PC. Here are three
896 implementations of increasing complexity. */
898 static inline const fde *
899 binary_search_unencoded_fdes (struct object *ob, void *pc)
901 struct fde_vector *vec = ob->u.sort;
902 size_t lo, hi;
904 for (lo = 0, hi = vec->count; lo < hi; )
906 size_t i = (lo + hi) / 2;
907 const fde *const f = vec->array[i];
908 void *pc_begin;
909 uaddr pc_range;
910 memcpy (&pc_begin, (const void * const *) f->pc_begin, sizeof (void *));
911 memcpy (&pc_range, (const uaddr *) f->pc_begin + 1, sizeof (uaddr));
913 if (pc < pc_begin)
914 hi = i;
915 else if (pc >= pc_begin + pc_range)
916 lo = i + 1;
917 else
918 return f;
921 return NULL;
924 static inline const fde *
925 binary_search_single_encoding_fdes (struct object *ob, void *pc)
927 struct fde_vector *vec = ob->u.sort;
928 int encoding = ob->s.b.encoding;
929 _Unwind_Ptr base = base_from_object (encoding, ob);
930 size_t lo, hi;
932 for (lo = 0, hi = vec->count; lo < hi; )
934 size_t i = (lo + hi) / 2;
935 const fde *f = vec->array[i];
936 _Unwind_Ptr pc_begin, pc_range;
937 const unsigned char *p;
939 p = read_encoded_value_with_base (encoding, base, f->pc_begin,
940 &pc_begin);
941 read_encoded_value_with_base (encoding & 0x0F, 0, p, &pc_range);
943 if ((_Unwind_Ptr) pc < pc_begin)
944 hi = i;
945 else if ((_Unwind_Ptr) pc >= pc_begin + pc_range)
946 lo = i + 1;
947 else
948 return f;
951 return NULL;
954 static inline const fde *
955 binary_search_mixed_encoding_fdes (struct object *ob, void *pc)
957 struct fde_vector *vec = ob->u.sort;
958 size_t lo, hi;
960 for (lo = 0, hi = vec->count; lo < hi; )
962 size_t i = (lo + hi) / 2;
963 const fde *f = vec->array[i];
964 _Unwind_Ptr pc_begin, pc_range;
965 const unsigned char *p;
966 int encoding;
968 encoding = get_fde_encoding (f);
969 p = read_encoded_value_with_base (encoding,
970 base_from_object (encoding, ob),
971 f->pc_begin, &pc_begin);
972 read_encoded_value_with_base (encoding & 0x0F, 0, p, &pc_range);
974 if ((_Unwind_Ptr) pc < pc_begin)
975 hi = i;
976 else if ((_Unwind_Ptr) pc >= pc_begin + pc_range)
977 lo = i + 1;
978 else
979 return f;
982 return NULL;
985 static const fde *
986 search_object (struct object* ob, void *pc)
988 /* If the data hasn't been sorted, try to do this now. We may have
989 more memory available than last time we tried. */
990 if (! ob->s.b.sorted)
992 init_object (ob);
994 /* Despite the above comment, the normal reason to get here is
995 that we've not processed this object before. A quick range
996 check is in order. */
997 if (pc < ob->pc_begin)
998 return NULL;
1001 if (ob->s.b.sorted)
1003 if (ob->s.b.mixed_encoding)
1004 return binary_search_mixed_encoding_fdes (ob, pc);
1005 else if (ob->s.b.encoding == DW_EH_PE_absptr)
1006 return binary_search_unencoded_fdes (ob, pc);
1007 else
1008 return binary_search_single_encoding_fdes (ob, pc);
1010 else
1012 /* Long slow laborious linear search, cos we've no memory. */
1013 if (ob->s.b.from_array)
1015 fde **p;
1016 for (p = ob->u.array; *p ; p++)
1018 const fde *f = linear_search_fdes (ob, *p, pc);
1019 if (f)
1020 return f;
1022 return NULL;
1024 else
1025 return linear_search_fdes (ob, ob->u.single, pc);
1029 const fde *
1030 _Unwind_Find_FDE (void *pc, struct dwarf_eh_bases *bases)
1032 struct object *ob;
1033 const fde *f = NULL;
1035 #ifdef ATOMIC_FDE_FAST_PATH
1036 /* For targets where unwind info is usually not registered through these
1037 APIs anymore, avoid taking a global lock.
1038 Use relaxed MO here, it is up to the app to ensure that the library
1039 loading/initialization happens-before using that library in other
1040 threads (in particular unwinding with that library's functions
1041 appearing in the backtraces). Calling that library's functions
1042 without waiting for the library to initialize would be racy. */
1043 if (__builtin_expect (!__atomic_load_n (&any_objects_registered,
1044 __ATOMIC_RELAXED), 1))
1045 return NULL;
1046 #endif
1048 init_object_mutex_once ();
1049 __gthread_mutex_lock (&object_mutex);
1051 /* Linear search through the classified objects, to find the one
1052 containing the pc. Note that pc_begin is sorted descending, and
1053 we expect objects to be non-overlapping. */
1054 for (ob = seen_objects; ob; ob = ob->next)
1055 if (pc >= ob->pc_begin)
1057 f = search_object (ob, pc);
1058 if (f)
1059 goto fini;
1060 break;
1063 /* Classify and search the objects we've not yet processed. */
1064 while ((ob = unseen_objects))
1066 struct object **p;
1068 unseen_objects = ob->next;
1069 f = search_object (ob, pc);
1071 /* Insert the object into the classified list. */
1072 for (p = &seen_objects; *p ; p = &(*p)->next)
1073 if ((*p)->pc_begin < ob->pc_begin)
1074 break;
1075 ob->next = *p;
1076 *p = ob;
1078 if (f)
1079 goto fini;
1082 fini:
1083 __gthread_mutex_unlock (&object_mutex);
1085 if (f)
1087 int encoding;
1088 _Unwind_Ptr func;
1090 bases->tbase = ob->tbase;
1091 bases->dbase = ob->dbase;
1093 encoding = ob->s.b.encoding;
1094 if (ob->s.b.mixed_encoding)
1095 encoding = get_fde_encoding (f);
1096 read_encoded_value_with_base (encoding, base_from_object (encoding, ob),
1097 f->pc_begin, &func);
1098 bases->func = (void *) func;
1101 return f;