1 /* Subroutines needed for unwinding stack frames for exception handling. */
2 /* Copyright (C) 1997-2023 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
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
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
29 #include "coretypes.h"
31 #include "libgcc_tm.h"
34 #define NO_BASE_OF_ENCODED_VALUE
35 #include "unwind-pe.h"
36 #include "unwind-dw2-fde.h"
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
45 typedef __UINTPTR_TYPE__ uintptr_type
;
47 #ifdef ATOMIC_FDE_FAST_PATH
48 #include "unwind-dw2-btree.h"
50 static struct btree registered_frames
;
51 static bool in_shutdown
;
54 release_registered_frames (void) __attribute__ ((destructor
));
56 release_registered_frames (void)
58 /* Release the b-tree and all frames. Frame releases that happen later are
60 btree_destroy (®istered_frames
);
65 get_pc_range (const struct object
*ob
, uintptr_type
*range
);
68 /* Without fast path frame deregistration must always succeed. */
69 static const int in_shutdown
= 0;
71 /* The unseen_objects list contains objects that have been registered
72 but not yet categorized in any way. The seen_objects list has had
73 its pc_begin and count fields initialized at minimum, and is sorted
74 by decreasing value of pc_begin. */
75 static struct object
*unseen_objects
;
76 static struct object
*seen_objects
;
79 #ifdef __GTHREAD_MUTEX_INIT
80 static __gthread_mutex_t object_mutex
= __GTHREAD_MUTEX_INIT
;
81 #define init_object_mutex_once()
83 #ifdef __GTHREAD_MUTEX_INIT_FUNCTION
84 static __gthread_mutex_t object_mutex
;
87 init_object_mutex (void)
89 __GTHREAD_MUTEX_INIT_FUNCTION (&object_mutex
);
93 init_object_mutex_once (void)
95 static __gthread_once_t once
= __GTHREAD_ONCE_INIT
;
96 __gthread_once (&once
, init_object_mutex
);
99 /* ??? Several targets include this file with stubbing parts of gthr.h
100 and expect no locking to be done. */
101 #define init_object_mutex_once()
102 static __gthread_mutex_t object_mutex
;
106 /* Called from crtbegin.o to register the unwind info for an object. */
109 __register_frame_info_bases (const void *begin
, struct object
*ob
,
110 void *tbase
, void *dbase
)
112 /* If .eh_frame is empty, don't register at all. */
113 if ((const uword
*) begin
== 0 || *(const uword
*) begin
== 0)
116 ob
->pc_begin
= (void *)-1;
119 ob
->u
.single
= begin
;
121 ob
->s
.b
.encoding
= DW_EH_PE_omit
;
122 #ifdef DWARF2_OBJECT_END_PTR_EXTENSION
126 #ifdef ATOMIC_FDE_FAST_PATH
127 // Register the frame in the b-tree
128 uintptr_type range
[2];
129 get_pc_range (ob
, range
);
130 btree_insert (®istered_frames
, range
[0], range
[1] - range
[0], ob
);
132 init_object_mutex_once ();
133 __gthread_mutex_lock (&object_mutex
);
135 ob
->next
= unseen_objects
;
138 __gthread_mutex_unlock (&object_mutex
);
143 __register_frame_info (const void *begin
, struct object
*ob
)
145 __register_frame_info_bases (begin
, ob
, 0, 0);
149 __register_frame (void *begin
)
153 /* If .eh_frame is empty, don't register at all. */
154 if (*(uword
*) begin
== 0)
157 ob
= malloc (sizeof (struct object
));
158 __register_frame_info (begin
, ob
);
161 /* Similar, but BEGIN is actually a pointer to a table of unwind entries
162 for different translation units. Called from the file generated by
166 __register_frame_info_table_bases (void *begin
, struct object
*ob
,
167 void *tbase
, void *dbase
)
169 ob
->pc_begin
= (void *)-1;
174 ob
->s
.b
.from_array
= 1;
175 ob
->s
.b
.encoding
= DW_EH_PE_omit
;
177 #ifdef ATOMIC_FDE_FAST_PATH
178 // Register the frame in the b-tree
179 uintptr_type range
[2];
180 get_pc_range (ob
, range
);
181 btree_insert (®istered_frames
, range
[0], range
[1] - range
[0], ob
);
183 init_object_mutex_once ();
184 __gthread_mutex_lock (&object_mutex
);
186 ob
->next
= unseen_objects
;
189 __gthread_mutex_unlock (&object_mutex
);
194 __register_frame_info_table (void *begin
, struct object
*ob
)
196 __register_frame_info_table_bases (begin
, ob
, 0, 0);
200 __register_frame_table (void *begin
)
202 struct object
*ob
= malloc (sizeof (struct object
));
203 __register_frame_info_table (begin
, ob
);
206 /* Called from crtbegin.o to deregister the unwind info for an object. */
207 /* ??? Glibc has for a while now exported __register_frame_info and
208 __deregister_frame_info. If we call __register_frame_info_bases
209 from crtbegin (wherein it is declared weak), and this object does
210 not get pulled from libgcc.a for other reasons, then the
211 invocation of __deregister_frame_info will be resolved from glibc.
212 Since the registration did not happen there, we'll die.
214 Therefore, declare a new deregistration entry point that does the
215 exact same thing, but will resolve to the same library as
216 implements __register_frame_info_bases. */
219 __deregister_frame_info_bases (const void *begin
)
221 struct object
*ob
= 0;
223 /* If .eh_frame is empty, we haven't registered. */
224 if ((const uword
*) begin
== 0 || *(const uword
*) begin
== 0)
227 #ifdef ATOMIC_FDE_FAST_PATH
228 // Find the corresponding PC range
229 struct object lookupob
;
232 lookupob
.u
.single
= begin
;
234 lookupob
.s
.b
.encoding
= DW_EH_PE_omit
;
235 #ifdef DWARF2_OBJECT_END_PTR_EXTENSION
236 lookupob
.fde_end
= NULL
;
238 uintptr_type range
[2];
239 get_pc_range (&lookupob
, range
);
242 ob
= btree_remove (®istered_frames
, range
[0]);
243 bool empty_table
= (range
[1] - range
[0]) == 0;
245 // Deallocate the sort array if any.
246 if (ob
&& ob
->s
.b
.sorted
)
251 init_object_mutex_once ();
252 __gthread_mutex_lock (&object_mutex
);
255 for (p
= &unseen_objects
; *p
; p
= &(*p
)->next
)
256 if ((*p
)->u
.single
== begin
)
263 for (p
= &seen_objects
; *p
; p
= &(*p
)->next
)
264 if ((*p
)->s
.b
.sorted
)
266 if ((*p
)->u
.sort
->orig_data
== begin
)
276 if ((*p
)->u
.single
== begin
)
285 __gthread_mutex_unlock (&object_mutex
);
286 const int empty_table
= 0; // The non-atomic path stores all tables.
289 // If we didn't find anything in the lookup data structures then they
290 // were either already destroyed or we tried to remove an empty range.
291 gcc_assert (in_shutdown
|| (empty_table
|| ob
));
296 __deregister_frame_info (const void *begin
)
298 return __deregister_frame_info_bases (begin
);
302 __deregister_frame (void *begin
)
304 /* If .eh_frame is empty, we haven't registered. */
305 if (*(uword
*) begin
!= 0)
306 free (__deregister_frame_info (begin
));
310 /* Like base_of_encoded_value, but take the base from a struct object
311 instead of an _Unwind_Context. */
314 base_from_object (unsigned char encoding
, const struct object
*ob
)
316 if (encoding
== DW_EH_PE_omit
)
319 switch (encoding
& 0x70)
321 case DW_EH_PE_absptr
:
323 case DW_EH_PE_aligned
:
326 case DW_EH_PE_textrel
:
327 return (_Unwind_Ptr
) ob
->tbase
;
328 case DW_EH_PE_datarel
:
329 return (_Unwind_Ptr
) ob
->dbase
;
335 /* Return the FDE pointer encoding from the CIE. */
336 /* ??? This is a subset of extract_cie_info from unwind-dw2.c. */
339 get_cie_encoding (const struct dwarf_cie
*cie
)
341 const unsigned char *aug
, *p
;
346 aug
= cie
->augmentation
;
347 p
= aug
+ strlen ((const char *)aug
) + 1; /* Skip the augmentation string. */
348 if (__builtin_expect (cie
->version
>= 4, 0))
350 if (p
[0] != sizeof (void *) || p
[1] != 0)
351 return DW_EH_PE_omit
; /* We are not prepared to handle unexpected
352 address sizes or segment selectors. */
353 p
+= 2; /* Skip address size and segment size. */
357 return DW_EH_PE_absptr
;
359 p
= read_uleb128 (p
, &utmp
); /* Skip code alignment. */
360 p
= read_sleb128 (p
, &stmp
); /* Skip data alignment. */
361 if (cie
->version
== 1) /* Skip return address column. */
364 p
= read_uleb128 (p
, &utmp
);
366 aug
++; /* Skip 'z' */
367 p
= read_uleb128 (p
, &utmp
); /* Skip augmentation length. */
370 /* This is what we're looking for. */
373 /* Personality encoding and pointer. */
374 else if (*aug
== 'P')
376 /* ??? Avoid dereferencing indirect pointers, since we're
377 faking the base address. Gotta keep DW_EH_PE_aligned
379 p
= read_encoded_value_with_base (*p
& 0x7F, 0, p
+ 1, &dummy
);
382 else if (*aug
== 'L')
384 /* aarch64 b-key pointer authentication. */
385 else if (*aug
== 'B')
387 /* Otherwise end of string, or unknown augmentation. */
389 return DW_EH_PE_absptr
;
395 get_fde_encoding (const struct dwarf_fde
*f
)
397 return get_cie_encoding (get_cie (f
));
401 /* Sorting an array of FDEs by address.
402 (Ideally we would have the linker sort the FDEs so we don't have to do
403 it at run time. But the linkers are not yet prepared for this.) */
405 /* Comparison routines. Three variants of increasing complexity. */
408 fde_unencoded_compare (struct object
*ob
__attribute__((unused
)),
409 const fde
*x
, const fde
*y
)
411 _Unwind_Ptr x_ptr
, y_ptr
;
412 memcpy (&x_ptr
, x
->pc_begin
, sizeof (_Unwind_Ptr
));
413 memcpy (&y_ptr
, y
->pc_begin
, sizeof (_Unwind_Ptr
));
423 fde_single_encoding_compare (struct object
*ob
, const fde
*x
, const fde
*y
)
425 _Unwind_Ptr base
, x_ptr
, y_ptr
;
427 base
= base_from_object (ob
->s
.b
.encoding
, ob
);
428 read_encoded_value_with_base (ob
->s
.b
.encoding
, base
, x
->pc_begin
, &x_ptr
);
429 read_encoded_value_with_base (ob
->s
.b
.encoding
, base
, y
->pc_begin
, &y_ptr
);
439 fde_mixed_encoding_compare (struct object
*ob
, const fde
*x
, const fde
*y
)
441 int x_encoding
, y_encoding
;
442 _Unwind_Ptr x_ptr
, y_ptr
;
444 x_encoding
= get_fde_encoding (x
);
445 read_encoded_value_with_base (x_encoding
, base_from_object (x_encoding
, ob
),
446 x
->pc_begin
, &x_ptr
);
448 y_encoding
= get_fde_encoding (y
);
449 read_encoded_value_with_base (y_encoding
, base_from_object (y_encoding
, ob
),
450 y
->pc_begin
, &y_ptr
);
459 typedef int (*fde_compare_t
) (struct object
*, const fde
*, const fde
*);
461 // The extractor functions compute the pointer values for a block of
462 // fdes. The block processing hides the call overhead.
465 fde_unencoded_extract (struct object
*ob
__attribute__ ((unused
)),
466 _Unwind_Ptr
*target
, const fde
**x
, int count
)
468 for (int index
= 0; index
< count
; ++index
)
469 memcpy (target
+ index
, x
[index
]->pc_begin
, sizeof (_Unwind_Ptr
));
473 fde_single_encoding_extract (struct object
*ob
, _Unwind_Ptr
*target
,
474 const fde
**x
, int count
)
478 base
= base_from_object (ob
->s
.b
.encoding
, ob
);
479 for (int index
= 0; index
< count
; ++index
)
480 read_encoded_value_with_base (ob
->s
.b
.encoding
, base
, x
[index
]->pc_begin
,
485 fde_mixed_encoding_extract (struct object
*ob
, _Unwind_Ptr
*target
,
486 const fde
**x
, int count
)
488 for (int index
= 0; index
< count
; ++index
)
490 int encoding
= get_fde_encoding (x
[index
]);
491 read_encoded_value_with_base (encoding
, base_from_object (encoding
, ob
),
492 x
[index
]->pc_begin
, target
+ index
);
496 typedef void (*fde_extractor_t
) (struct object
*, _Unwind_Ptr
*, const fde
**,
499 // Data is is sorted using radix sort if possible, using an temporary
500 // auxiliary data structure of the same size as the input. When running
501 // out of memory do in-place heap sort.
503 struct fde_accumulator
505 struct fde_vector
*linear
;
506 struct fde_vector
*aux
;
510 start_fde_sort (struct fde_accumulator
*accu
, size_t count
)
516 size
= sizeof (struct fde_vector
) + sizeof (const fde
*) * count
;
517 if ((accu
->linear
= malloc (size
)))
519 accu
->linear
->count
= 0;
520 if ((accu
->aux
= malloc (size
)))
521 accu
->aux
->count
= 0;
529 fde_insert (struct fde_accumulator
*accu
, const fde
*this_fde
)
532 accu
->linear
->array
[accu
->linear
->count
++] = this_fde
;
535 #define SWAP(x,y) do { const fde * tmp = x; x = y; y = tmp; } while (0)
537 /* Convert a semi-heap to a heap. A semi-heap is a heap except possibly
538 for the first (root) node; push it down to its rightful place. */
541 frame_downheap (struct object
*ob
, fde_compare_t fde_compare
, const fde
**a
,
546 for (i
= lo
, j
= 2*i
+1;
550 if (j
+1 < hi
&& fde_compare (ob
, a
[j
], a
[j
+1]) < 0)
553 if (fde_compare (ob
, a
[i
], a
[j
]) < 0)
563 /* This is O(n log(n)). BSD/OS defines heapsort in stdlib.h, so we must
564 use a name that does not conflict. */
567 frame_heapsort (struct object
*ob
, fde_compare_t fde_compare
,
568 struct fde_vector
*erratic
)
570 /* For a description of this algorithm, see:
571 Samuel P. Harbison, Guy L. Steele Jr.: C, a reference manual, 2nd ed.,
573 const fde
** a
= erratic
->array
;
574 /* A portion of the array is called a "heap" if for all i>=0:
575 If i and 2i+1 are valid indices, then a[i] >= a[2i+1].
576 If i and 2i+2 are valid indices, then a[i] >= a[2i+2]. */
577 size_t n
= erratic
->count
;
580 /* Expand our heap incrementally from the end of the array, heapifying
581 each resulting semi-heap as we go. After each step, a[m] is the top
583 for (m
= n
/2-1; m
>= 0; --m
)
584 frame_downheap (ob
, fde_compare
, a
, m
, n
);
586 /* Shrink our heap incrementally from the end of the array, first
587 swapping out the largest element a[0] and then re-heapifying the
588 resulting semi-heap. After each step, a[0..m) is a heap. */
589 for (m
= n
-1; m
>= 1; --m
)
592 frame_downheap (ob
, fde_compare
, a
, 0, m
);
597 // Radix sort data in V1 using V2 as aux memory. Runtime O(n).
599 fde_radixsort (struct object
*ob
, fde_extractor_t fde_extractor
,
600 struct fde_vector
*v1
, struct fde_vector
*v2
)
603 #define FANOUT (1 << FANOUTBITS)
604 #define BLOCKSIZE 128
605 const unsigned rounds
606 = (__CHAR_BIT__
* sizeof (_Unwind_Ptr
) + FANOUTBITS
- 1) / FANOUTBITS
;
607 const fde
**a1
= v1
->array
, **a2
= v2
->array
;
608 _Unwind_Ptr ptrs
[BLOCKSIZE
+ 1];
609 unsigned n
= v1
->count
;
610 for (unsigned round
= 0; round
!= rounds
; ++round
)
612 unsigned counts
[FANOUT
] = {0};
613 unsigned violations
= 0;
615 // Count the number of elements per bucket and check if we are already
617 _Unwind_Ptr last
= 0;
618 for (unsigned i
= 0; i
< n
;)
620 unsigned chunk
= ((n
- i
) <= BLOCKSIZE
) ? (n
- i
) : BLOCKSIZE
;
621 fde_extractor (ob
, ptrs
+ 1, a1
+ i
, chunk
);
623 for (unsigned j
= 0; j
< chunk
; ++j
)
625 unsigned b
= (ptrs
[j
+ 1] >> (round
* FANOUTBITS
)) & (FANOUT
- 1);
627 // Use summation instead of an if to eliminate branches.
628 violations
+= ptrs
[j
+ 1] < ptrs
[j
];
634 // Stop if we are already sorted.
637 // The sorted data is in a1 now.
642 // Compute the prefix sum.
644 for (unsigned i
= 0; i
!= FANOUT
; ++i
)
651 // Place all elements.
652 for (unsigned i
= 0; i
< n
;)
654 unsigned chunk
= ((n
- i
) <= BLOCKSIZE
) ? (n
- i
) : BLOCKSIZE
;
655 fde_extractor (ob
, ptrs
, a1
+ i
, chunk
);
656 for (unsigned j
= 0; j
< chunk
; ++j
)
658 unsigned b
= (ptrs
[j
] >> (round
* FANOUTBITS
)) & (FANOUT
- 1);
659 a2
[counts
[b
]++] = a1
[i
+ j
];
665 const fde
**tmp
= a1
;
673 // The data is in a2 now, move in place if needed.
675 memcpy (v1
->array
, a2
, sizeof (const fde
*) * n
);
679 end_fde_sort (struct object
*ob
, struct fde_accumulator
*accu
, size_t count
)
681 gcc_assert (!accu
->linear
|| accu
->linear
->count
== count
);
685 fde_extractor_t fde_extractor
;
686 if (ob
->s
.b
.mixed_encoding
)
687 fde_extractor
= fde_mixed_encoding_extract
;
688 else if (ob
->s
.b
.encoding
== DW_EH_PE_absptr
)
689 fde_extractor
= fde_unencoded_extract
;
691 fde_extractor
= fde_single_encoding_extract
;
693 fde_radixsort (ob
, fde_extractor
, accu
->linear
, accu
->aux
);
698 fde_compare_t fde_compare
;
699 if (ob
->s
.b
.mixed_encoding
)
700 fde_compare
= fde_mixed_encoding_compare
;
701 else if (ob
->s
.b
.encoding
== DW_EH_PE_absptr
)
702 fde_compare
= fde_unencoded_compare
;
704 fde_compare
= fde_single_encoding_compare
;
706 /* We've not managed to malloc an aux array,
707 so heap sort in the linear one. */
708 frame_heapsort (ob
, fde_compare
, accu
->linear
);
712 /* Inspect the fde array beginning at this_fde. This
713 function can be used either in query mode (RANGE is
714 not null, OB is const), or in update mode (RANGE is
715 null, OB is modified). In query mode the function computes
716 the range of PC values and stores it in RANGE. In
717 update mode it updates encoding, mixed_encoding, and pc_begin
718 for OB. Return the number of fdes encountered along the way. */
721 classify_object_over_fdes (struct object
*ob
, const fde
*this_fde
,
724 const struct dwarf_cie
*last_cie
= 0;
726 int encoding
= DW_EH_PE_absptr
;
727 _Unwind_Ptr base
= 0;
729 for (; ! last_fde (ob
, this_fde
); this_fde
= next_fde (this_fde
))
731 const struct dwarf_cie
*this_cie
;
732 _Unwind_Ptr mask
, pc_begin
;
735 if (this_fde
->CIE_delta
== 0)
738 /* Determine the encoding for this FDE. Note mixed encoded
739 objects for later. */
740 this_cie
= get_cie (this_fde
);
741 if (this_cie
!= last_cie
)
744 encoding
= get_cie_encoding (this_cie
);
745 if (encoding
== DW_EH_PE_omit
)
747 base
= base_from_object (encoding
, ob
);
750 if (ob
->s
.b
.encoding
== DW_EH_PE_omit
)
751 ob
->s
.b
.encoding
= encoding
;
752 else if (ob
->s
.b
.encoding
!= encoding
)
753 ob
->s
.b
.mixed_encoding
= 1;
757 const unsigned char *p
;
758 p
= read_encoded_value_with_base (encoding
, base
, this_fde
->pc_begin
,
761 /* Take care to ignore link-once functions that were removed.
762 In these cases, the function address will be NULL, but if
763 the encoding is smaller than a pointer a true NULL may not
764 be representable. Assume 0 in the representable bits is NULL. */
765 mask
= size_of_encoded_value (encoding
);
766 if (mask
< sizeof (void *))
767 mask
= (((_Unwind_Ptr
) 1) << (mask
<< 3)) - 1;
771 if ((pc_begin
& mask
) == 0)
777 _Unwind_Ptr pc_range
, pc_end
;
778 read_encoded_value_with_base (encoding
& 0x0F, 0, p
, &pc_range
);
779 pc_end
= pc_begin
+ pc_range
;
780 if ((!range
[0]) && (!range
[1]))
787 if (pc_begin
< range
[0])
789 if (pc_end
> range
[1])
795 if ((void *) pc_begin
< ob
->pc_begin
)
796 ob
->pc_begin
= (void *) pc_begin
;
804 add_fdes (struct object
*ob
, struct fde_accumulator
*accu
, const fde
*this_fde
)
806 const struct dwarf_cie
*last_cie
= 0;
807 int encoding
= ob
->s
.b
.encoding
;
808 _Unwind_Ptr base
= base_from_object (ob
->s
.b
.encoding
, ob
);
810 for (; ! last_fde (ob
, this_fde
); this_fde
= next_fde (this_fde
))
812 const struct dwarf_cie
*this_cie
;
815 if (this_fde
->CIE_delta
== 0)
818 if (ob
->s
.b
.mixed_encoding
)
820 /* Determine the encoding for this FDE. Note mixed encoded
821 objects for later. */
822 this_cie
= get_cie (this_fde
);
823 if (this_cie
!= last_cie
)
826 encoding
= get_cie_encoding (this_cie
);
827 base
= base_from_object (encoding
, ob
);
831 if (encoding
== DW_EH_PE_absptr
)
834 memcpy (&ptr
, this_fde
->pc_begin
, sizeof (_Unwind_Ptr
));
840 _Unwind_Ptr pc_begin
, mask
;
842 read_encoded_value_with_base (encoding
, base
, this_fde
->pc_begin
,
845 /* Take care to ignore link-once functions that were removed.
846 In these cases, the function address will be NULL, but if
847 the encoding is smaller than a pointer a true NULL may not
848 be representable. Assume 0 in the representable bits is NULL. */
849 mask
= size_of_encoded_value (encoding
);
850 if (mask
< sizeof (void *))
851 mask
= (((_Unwind_Ptr
) 1) << (mask
<< 3)) - 1;
855 if ((pc_begin
& mask
) == 0)
859 fde_insert (accu
, this_fde
);
863 /* Set up a sorted array of pointers to FDEs for a loaded object. We
864 count up the entries before allocating the array because it's likely to
865 be faster. We can be called multiple times, should we have failed to
866 allocate a sorted fde array on a previous occasion. */
869 init_object (struct object
* ob
)
871 struct fde_accumulator accu
;
874 count
= ob
->s
.b
.count
;
877 if (ob
->s
.b
.from_array
)
879 fde
**p
= ob
->u
.array
;
880 for (count
= 0; *p
; ++p
)
882 size_t cur_count
= classify_object_over_fdes (ob
, *p
, NULL
);
883 if (cur_count
== (size_t) -1)
890 count
= classify_object_over_fdes (ob
, ob
->u
.single
, NULL
);
891 if (count
== (size_t) -1)
893 static const fde terminator
;
896 ob
->s
.b
.encoding
= DW_EH_PE_omit
;
897 ob
->u
.single
= &terminator
;
902 /* The count field we have in the main struct object is somewhat
903 limited, but should suffice for virtually all cases. If the
904 counted value doesn't fit, re-write a zero. The worst that
905 happens is that we re-count next time -- admittedly non-trivial
906 in that this implies some 2M fdes, but at least we function. */
907 ob
->s
.b
.count
= count
;
908 if (ob
->s
.b
.count
!= count
)
912 if (!start_fde_sort (&accu
, count
))
915 if (ob
->s
.b
.from_array
)
918 for (p
= ob
->u
.array
; *p
; ++p
)
919 add_fdes (ob
, &accu
, *p
);
922 add_fdes (ob
, &accu
, ob
->u
.single
);
924 end_fde_sort (ob
, &accu
, count
);
926 /* Save the original fde pointer, since this is the key by which the
927 DSO will deregister the object. */
928 accu
.linear
->orig_data
= ob
->u
.single
;
929 ob
->u
.sort
= accu
.linear
;
931 #ifdef ATOMIC_FDE_FAST_PATH
932 // We must update the sorted bit with an atomic operation
936 __atomic_store (&(ob
->s
.b
), &(tmp
.s
.b
), __ATOMIC_RELEASE
);
942 #ifdef ATOMIC_FDE_FAST_PATH
943 /* Get the PC range for lookup */
945 get_pc_range (const struct object
*ob
, uintptr_type
*range
)
947 // It is safe to cast to non-const object* here as
948 // classify_object_over_fdes does not modify ob in query mode.
949 struct object
*ncob
= (struct object
*) (uintptr_type
) ob
;
950 range
[0] = range
[1] = 0;
953 classify_object_over_fdes (ncob
, ob
->u
.sort
->orig_data
, range
);
955 else if (ob
->s
.b
.from_array
)
957 fde
**p
= ob
->u
.array
;
959 classify_object_over_fdes (ncob
, *p
, range
);
963 classify_object_over_fdes (ncob
, ob
->u
.single
, range
);
968 /* A linear search through a set of FDEs for the given PC. This is
969 used when there was insufficient memory to allocate and sort an
973 linear_search_fdes (struct object
*ob
, const fde
*this_fde
, void *pc
)
975 const struct dwarf_cie
*last_cie
= 0;
976 int encoding
= ob
->s
.b
.encoding
;
977 _Unwind_Ptr base
= base_from_object (ob
->s
.b
.encoding
, ob
);
979 for (; ! last_fde (ob
, this_fde
); this_fde
= next_fde (this_fde
))
981 const struct dwarf_cie
*this_cie
;
982 _Unwind_Ptr pc_begin
, pc_range
;
985 if (this_fde
->CIE_delta
== 0)
988 if (ob
->s
.b
.mixed_encoding
)
990 /* Determine the encoding for this FDE. Note mixed encoded
991 objects for later. */
992 this_cie
= get_cie (this_fde
);
993 if (this_cie
!= last_cie
)
996 encoding
= get_cie_encoding (this_cie
);
997 base
= base_from_object (encoding
, ob
);
1001 if (encoding
== DW_EH_PE_absptr
)
1003 const _Unwind_Ptr
*pc_array
= (const _Unwind_Ptr
*) this_fde
->pc_begin
;
1004 pc_begin
= pc_array
[0];
1005 pc_range
= pc_array
[1];
1012 const unsigned char *p
;
1014 p
= read_encoded_value_with_base (encoding
, base
,
1015 this_fde
->pc_begin
, &pc_begin
);
1016 read_encoded_value_with_base (encoding
& 0x0F, 0, p
, &pc_range
);
1018 /* Take care to ignore link-once functions that were removed.
1019 In these cases, the function address will be NULL, but if
1020 the encoding is smaller than a pointer a true NULL may not
1021 be representable. Assume 0 in the representable bits is NULL. */
1022 mask
= size_of_encoded_value (encoding
);
1023 if (mask
< sizeof (void *))
1024 mask
= (((_Unwind_Ptr
) 1) << (mask
<< 3)) - 1;
1028 if ((pc_begin
& mask
) == 0)
1032 if ((_Unwind_Ptr
) pc
- pc_begin
< pc_range
)
1039 /* Binary search for an FDE containing the given PC. Here are three
1040 implementations of increasing complexity. */
1042 static inline const fde
*
1043 binary_search_unencoded_fdes (struct object
*ob
, void *pc
)
1045 struct fde_vector
*vec
= ob
->u
.sort
;
1048 for (lo
= 0, hi
= vec
->count
; lo
< hi
; )
1050 size_t i
= (lo
+ hi
) / 2;
1051 const fde
*const f
= vec
->array
[i
];
1054 memcpy (&pc_begin
, (const void * const *) f
->pc_begin
, sizeof (void *));
1055 memcpy (&pc_range
, (const uaddr
*) f
->pc_begin
+ 1, sizeof (uaddr
));
1059 else if (pc
>= pc_begin
+ pc_range
)
1068 static inline const fde
*
1069 binary_search_single_encoding_fdes (struct object
*ob
, void *pc
)
1071 struct fde_vector
*vec
= ob
->u
.sort
;
1072 int encoding
= ob
->s
.b
.encoding
;
1073 _Unwind_Ptr base
= base_from_object (encoding
, ob
);
1076 for (lo
= 0, hi
= vec
->count
; lo
< hi
; )
1078 size_t i
= (lo
+ hi
) / 2;
1079 const fde
*f
= vec
->array
[i
];
1080 _Unwind_Ptr pc_begin
, pc_range
;
1081 const unsigned char *p
;
1083 p
= read_encoded_value_with_base (encoding
, base
, f
->pc_begin
,
1085 read_encoded_value_with_base (encoding
& 0x0F, 0, p
, &pc_range
);
1087 if ((_Unwind_Ptr
) pc
< pc_begin
)
1089 else if ((_Unwind_Ptr
) pc
>= pc_begin
+ pc_range
)
1098 static inline const fde
*
1099 binary_search_mixed_encoding_fdes (struct object
*ob
, void *pc
)
1101 struct fde_vector
*vec
= ob
->u
.sort
;
1104 for (lo
= 0, hi
= vec
->count
; lo
< hi
; )
1106 size_t i
= (lo
+ hi
) / 2;
1107 const fde
*f
= vec
->array
[i
];
1108 _Unwind_Ptr pc_begin
, pc_range
;
1109 const unsigned char *p
;
1112 encoding
= get_fde_encoding (f
);
1113 p
= read_encoded_value_with_base (encoding
,
1114 base_from_object (encoding
, ob
),
1115 f
->pc_begin
, &pc_begin
);
1116 read_encoded_value_with_base (encoding
& 0x0F, 0, p
, &pc_range
);
1118 if ((_Unwind_Ptr
) pc
< pc_begin
)
1120 else if ((_Unwind_Ptr
) pc
>= pc_begin
+ pc_range
)
1130 search_object (struct object
* ob
, void *pc
)
1132 /* The fast path initializes objects eagerly to avoid locking.
1133 * On the slow path we initialize them now */
1134 #ifndef ATOMIC_FDE_FAST_PATH
1135 /* If the data hasn't been sorted, try to do this now. We may have
1136 more memory available than last time we tried. */
1137 if (! ob
->s
.b
.sorted
)
1141 /* Despite the above comment, the normal reason to get here is
1142 that we've not processed this object before. A quick range
1143 check is in order. */
1144 if (pc
< ob
->pc_begin
)
1151 if (ob
->s
.b
.mixed_encoding
)
1152 return binary_search_mixed_encoding_fdes (ob
, pc
);
1153 else if (ob
->s
.b
.encoding
== DW_EH_PE_absptr
)
1154 return binary_search_unencoded_fdes (ob
, pc
);
1156 return binary_search_single_encoding_fdes (ob
, pc
);
1160 /* Long slow laborious linear search, cos we've no memory. */
1161 if (ob
->s
.b
.from_array
)
1164 for (p
= ob
->u
.array
; *p
; p
++)
1166 const fde
*f
= linear_search_fdes (ob
, *p
, pc
);
1173 return linear_search_fdes (ob
, ob
->u
.single
, pc
);
1177 #ifdef ATOMIC_FDE_FAST_PATH
1179 // Check if the object was already initialized
1181 is_object_initialized (struct object
*ob
)
1183 // We have to use acquire atomics for the read, which
1184 // is a bit involved as we read from a bitfield
1186 __atomic_load (&(ob
->s
.b
), &(tmp
.s
.b
), __ATOMIC_ACQUIRE
);
1187 return tmp
.s
.b
.sorted
;
1193 _Unwind_Find_FDE (void *pc
, struct dwarf_eh_bases
*bases
)
1196 const fde
*f
= NULL
;
1198 #ifdef ATOMIC_FDE_FAST_PATH
1199 ob
= btree_lookup (®istered_frames
, (uintptr_type
) pc
);
1203 // Initialize the object lazily
1204 if (!is_object_initialized (ob
))
1206 // Check again under mutex
1207 init_object_mutex_once ();
1208 __gthread_mutex_lock (&object_mutex
);
1210 if (!ob
->s
.b
.sorted
)
1215 __gthread_mutex_unlock (&object_mutex
);
1218 f
= search_object (ob
, pc
);
1221 init_object_mutex_once ();
1222 __gthread_mutex_lock (&object_mutex
);
1224 /* Linear search through the classified objects, to find the one
1225 containing the pc. Note that pc_begin is sorted descending, and
1226 we expect objects to be non-overlapping. */
1227 for (ob
= seen_objects
; ob
; ob
= ob
->next
)
1228 if (pc
>= ob
->pc_begin
)
1230 f
= search_object (ob
, pc
);
1236 /* Classify and search the objects we've not yet processed. */
1237 while ((ob
= unseen_objects
))
1241 unseen_objects
= ob
->next
;
1242 f
= search_object (ob
, pc
);
1244 /* Insert the object into the classified list. */
1245 for (p
= &seen_objects
; *p
; p
= &(*p
)->next
)
1246 if ((*p
)->pc_begin
< ob
->pc_begin
)
1256 __gthread_mutex_unlock (&object_mutex
);
1264 bases
->tbase
= ob
->tbase
;
1265 bases
->dbase
= ob
->dbase
;
1267 encoding
= ob
->s
.b
.encoding
;
1268 if (ob
->s
.b
.mixed_encoding
)
1269 encoding
= get_fde_encoding (f
);
1270 read_encoded_value_with_base (encoding
, base_from_object (encoding
, ob
),
1271 f
->pc_begin
, &func
);
1272 bases
->func
= (void *) func
;