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]);
244 init_object_mutex_once ();
245 __gthread_mutex_lock (&object_mutex
);
248 for (p
= &unseen_objects
; *p
; p
= &(*p
)->next
)
249 if ((*p
)->u
.single
== begin
)
256 for (p
= &seen_objects
; *p
; p
= &(*p
)->next
)
257 if ((*p
)->s
.b
.sorted
)
259 if ((*p
)->u
.sort
->orig_data
== begin
)
269 if ((*p
)->u
.single
== begin
)
278 __gthread_mutex_unlock (&object_mutex
);
281 gcc_assert (in_shutdown
|| ob
);
286 __deregister_frame_info (const void *begin
)
288 return __deregister_frame_info_bases (begin
);
292 __deregister_frame (void *begin
)
294 /* If .eh_frame is empty, we haven't registered. */
295 if (*(uword
*) begin
!= 0)
296 free (__deregister_frame_info (begin
));
300 /* Like base_of_encoded_value, but take the base from a struct object
301 instead of an _Unwind_Context. */
304 base_from_object (unsigned char encoding
, const struct object
*ob
)
306 if (encoding
== DW_EH_PE_omit
)
309 switch (encoding
& 0x70)
311 case DW_EH_PE_absptr
:
313 case DW_EH_PE_aligned
:
316 case DW_EH_PE_textrel
:
317 return (_Unwind_Ptr
) ob
->tbase
;
318 case DW_EH_PE_datarel
:
319 return (_Unwind_Ptr
) ob
->dbase
;
325 /* Return the FDE pointer encoding from the CIE. */
326 /* ??? This is a subset of extract_cie_info from unwind-dw2.c. */
329 get_cie_encoding (const struct dwarf_cie
*cie
)
331 const unsigned char *aug
, *p
;
336 aug
= cie
->augmentation
;
337 p
= aug
+ strlen ((const char *)aug
) + 1; /* Skip the augmentation string. */
338 if (__builtin_expect (cie
->version
>= 4, 0))
340 if (p
[0] != sizeof (void *) || p
[1] != 0)
341 return DW_EH_PE_omit
; /* We are not prepared to handle unexpected
342 address sizes or segment selectors. */
343 p
+= 2; /* Skip address size and segment size. */
347 return DW_EH_PE_absptr
;
349 p
= read_uleb128 (p
, &utmp
); /* Skip code alignment. */
350 p
= read_sleb128 (p
, &stmp
); /* Skip data alignment. */
351 if (cie
->version
== 1) /* Skip return address column. */
354 p
= read_uleb128 (p
, &utmp
);
356 aug
++; /* Skip 'z' */
357 p
= read_uleb128 (p
, &utmp
); /* Skip augmentation length. */
360 /* This is what we're looking for. */
363 /* Personality encoding and pointer. */
364 else if (*aug
== 'P')
366 /* ??? Avoid dereferencing indirect pointers, since we're
367 faking the base address. Gotta keep DW_EH_PE_aligned
369 p
= read_encoded_value_with_base (*p
& 0x7F, 0, p
+ 1, &dummy
);
372 else if (*aug
== 'L')
374 /* aarch64 b-key pointer authentication. */
375 else if (*aug
== 'B')
377 /* Otherwise end of string, or unknown augmentation. */
379 return DW_EH_PE_absptr
;
385 get_fde_encoding (const struct dwarf_fde
*f
)
387 return get_cie_encoding (get_cie (f
));
391 /* Sorting an array of FDEs by address.
392 (Ideally we would have the linker sort the FDEs so we don't have to do
393 it at run time. But the linkers are not yet prepared for this.) */
395 /* Comparison routines. Three variants of increasing complexity. */
398 fde_unencoded_compare (struct object
*ob
__attribute__((unused
)),
399 const fde
*x
, const fde
*y
)
401 _Unwind_Ptr x_ptr
, y_ptr
;
402 memcpy (&x_ptr
, x
->pc_begin
, sizeof (_Unwind_Ptr
));
403 memcpy (&y_ptr
, y
->pc_begin
, sizeof (_Unwind_Ptr
));
413 fde_single_encoding_compare (struct object
*ob
, const fde
*x
, const fde
*y
)
415 _Unwind_Ptr base
, x_ptr
, y_ptr
;
417 base
= base_from_object (ob
->s
.b
.encoding
, ob
);
418 read_encoded_value_with_base (ob
->s
.b
.encoding
, base
, x
->pc_begin
, &x_ptr
);
419 read_encoded_value_with_base (ob
->s
.b
.encoding
, base
, y
->pc_begin
, &y_ptr
);
429 fde_mixed_encoding_compare (struct object
*ob
, const fde
*x
, const fde
*y
)
431 int x_encoding
, y_encoding
;
432 _Unwind_Ptr x_ptr
, y_ptr
;
434 x_encoding
= get_fde_encoding (x
);
435 read_encoded_value_with_base (x_encoding
, base_from_object (x_encoding
, ob
),
436 x
->pc_begin
, &x_ptr
);
438 y_encoding
= get_fde_encoding (y
);
439 read_encoded_value_with_base (y_encoding
, base_from_object (y_encoding
, ob
),
440 y
->pc_begin
, &y_ptr
);
449 typedef int (*fde_compare_t
) (struct object
*, const fde
*, const fde
*);
451 // The extractor functions compute the pointer values for a block of
452 // fdes. The block processing hides the call overhead.
455 fde_unencoded_extract (struct object
*ob
__attribute__ ((unused
)),
456 _Unwind_Ptr
*target
, const fde
**x
, int count
)
458 for (int index
= 0; index
< count
; ++index
)
459 memcpy (target
+ index
, x
[index
]->pc_begin
, sizeof (_Unwind_Ptr
));
463 fde_single_encoding_extract (struct object
*ob
, _Unwind_Ptr
*target
,
464 const fde
**x
, int count
)
468 base
= base_from_object (ob
->s
.b
.encoding
, ob
);
469 for (int index
= 0; index
< count
; ++index
)
470 read_encoded_value_with_base (ob
->s
.b
.encoding
, base
, x
[index
]->pc_begin
,
475 fde_mixed_encoding_extract (struct object
*ob
, _Unwind_Ptr
*target
,
476 const fde
**x
, int count
)
478 for (int index
= 0; index
< count
; ++index
)
480 int encoding
= get_fde_encoding (x
[index
]);
481 read_encoded_value_with_base (encoding
, base_from_object (encoding
, ob
),
482 x
[index
]->pc_begin
, target
+ index
);
486 typedef void (*fde_extractor_t
) (struct object
*, _Unwind_Ptr
*, const fde
**,
489 // Data is is sorted using radix sort if possible, using an temporary
490 // auxiliary data structure of the same size as the input. When running
491 // out of memory do in-place heap sort.
493 struct fde_accumulator
495 struct fde_vector
*linear
;
496 struct fde_vector
*aux
;
500 start_fde_sort (struct fde_accumulator
*accu
, size_t count
)
506 size
= sizeof (struct fde_vector
) + sizeof (const fde
*) * count
;
507 if ((accu
->linear
= malloc (size
)))
509 accu
->linear
->count
= 0;
510 if ((accu
->aux
= malloc (size
)))
511 accu
->aux
->count
= 0;
519 fde_insert (struct fde_accumulator
*accu
, const fde
*this_fde
)
522 accu
->linear
->array
[accu
->linear
->count
++] = this_fde
;
525 #define SWAP(x,y) do { const fde * tmp = x; x = y; y = tmp; } while (0)
527 /* Convert a semi-heap to a heap. A semi-heap is a heap except possibly
528 for the first (root) node; push it down to its rightful place. */
531 frame_downheap (struct object
*ob
, fde_compare_t fde_compare
, const fde
**a
,
536 for (i
= lo
, j
= 2*i
+1;
540 if (j
+1 < hi
&& fde_compare (ob
, a
[j
], a
[j
+1]) < 0)
543 if (fde_compare (ob
, a
[i
], a
[j
]) < 0)
553 /* This is O(n log(n)). BSD/OS defines heapsort in stdlib.h, so we must
554 use a name that does not conflict. */
557 frame_heapsort (struct object
*ob
, fde_compare_t fde_compare
,
558 struct fde_vector
*erratic
)
560 /* For a description of this algorithm, see:
561 Samuel P. Harbison, Guy L. Steele Jr.: C, a reference manual, 2nd ed.,
563 const fde
** a
= erratic
->array
;
564 /* A portion of the array is called a "heap" if for all i>=0:
565 If i and 2i+1 are valid indices, then a[i] >= a[2i+1].
566 If i and 2i+2 are valid indices, then a[i] >= a[2i+2]. */
567 size_t n
= erratic
->count
;
570 /* Expand our heap incrementally from the end of the array, heapifying
571 each resulting semi-heap as we go. After each step, a[m] is the top
573 for (m
= n
/2-1; m
>= 0; --m
)
574 frame_downheap (ob
, fde_compare
, a
, m
, n
);
576 /* Shrink our heap incrementally from the end of the array, first
577 swapping out the largest element a[0] and then re-heapifying the
578 resulting semi-heap. After each step, a[0..m) is a heap. */
579 for (m
= n
-1; m
>= 1; --m
)
582 frame_downheap (ob
, fde_compare
, a
, 0, m
);
587 // Radix sort data in V1 using V2 as aux memory. Runtime O(n).
589 fde_radixsort (struct object
*ob
, fde_extractor_t fde_extractor
,
590 struct fde_vector
*v1
, struct fde_vector
*v2
)
593 #define FANOUT (1 << FANOUTBITS)
594 #define BLOCKSIZE 128
595 const unsigned rounds
596 = (__CHAR_BIT__
* sizeof (_Unwind_Ptr
) + FANOUTBITS
- 1) / FANOUTBITS
;
597 const fde
**a1
= v1
->array
, **a2
= v2
->array
;
598 _Unwind_Ptr ptrs
[BLOCKSIZE
+ 1];
599 unsigned n
= v1
->count
;
600 for (unsigned round
= 0; round
!= rounds
; ++round
)
602 unsigned counts
[FANOUT
] = {0};
603 unsigned violations
= 0;
605 // Count the number of elements per bucket and check if we are already
607 _Unwind_Ptr last
= 0;
608 for (unsigned i
= 0; i
< n
;)
610 unsigned chunk
= ((n
- i
) <= BLOCKSIZE
) ? (n
- i
) : BLOCKSIZE
;
611 fde_extractor (ob
, ptrs
+ 1, a1
+ i
, chunk
);
613 for (unsigned j
= 0; j
< chunk
; ++j
)
615 unsigned b
= (ptrs
[j
+ 1] >> (round
* FANOUTBITS
)) & (FANOUT
- 1);
617 // Use summation instead of an if to eliminate branches.
618 violations
+= ptrs
[j
+ 1] < ptrs
[j
];
624 // Stop if we are already sorted.
627 // The sorted data is in a1 now.
632 // Compute the prefix sum.
634 for (unsigned i
= 0; i
!= FANOUT
; ++i
)
641 // Place all elements.
642 for (unsigned i
= 0; i
< n
;)
644 unsigned chunk
= ((n
- i
) <= BLOCKSIZE
) ? (n
- i
) : BLOCKSIZE
;
645 fde_extractor (ob
, ptrs
, a1
+ i
, chunk
);
646 for (unsigned j
= 0; j
< chunk
; ++j
)
648 unsigned b
= (ptrs
[j
] >> (round
* FANOUTBITS
)) & (FANOUT
- 1);
649 a2
[counts
[b
]++] = a1
[i
+ j
];
655 const fde
**tmp
= a1
;
663 // The data is in a2 now, move in place if needed.
665 memcpy (v1
->array
, a2
, sizeof (const fde
*) * n
);
669 end_fde_sort (struct object
*ob
, struct fde_accumulator
*accu
, size_t count
)
671 gcc_assert (!accu
->linear
|| accu
->linear
->count
== count
);
675 fde_extractor_t fde_extractor
;
676 if (ob
->s
.b
.mixed_encoding
)
677 fde_extractor
= fde_mixed_encoding_extract
;
678 else if (ob
->s
.b
.encoding
== DW_EH_PE_absptr
)
679 fde_extractor
= fde_unencoded_extract
;
681 fde_extractor
= fde_single_encoding_extract
;
683 fde_radixsort (ob
, fde_extractor
, accu
->linear
, accu
->aux
);
688 fde_compare_t fde_compare
;
689 if (ob
->s
.b
.mixed_encoding
)
690 fde_compare
= fde_mixed_encoding_compare
;
691 else if (ob
->s
.b
.encoding
== DW_EH_PE_absptr
)
692 fde_compare
= fde_unencoded_compare
;
694 fde_compare
= fde_single_encoding_compare
;
696 /* We've not managed to malloc an aux array,
697 so heap sort in the linear one. */
698 frame_heapsort (ob
, fde_compare
, accu
->linear
);
702 /* Inspect the fde array beginning at this_fde. This
703 function can be used either in query mode (RANGE is
704 not null, OB is const), or in update mode (RANGE is
705 null, OB is modified). In query mode the function computes
706 the range of PC values and stores it in RANGE. In
707 update mode it updates encoding, mixed_encoding, and pc_begin
708 for OB. Return the number of fdes encountered along the way. */
711 classify_object_over_fdes (struct object
*ob
, const fde
*this_fde
,
714 const struct dwarf_cie
*last_cie
= 0;
716 int encoding
= DW_EH_PE_absptr
;
717 _Unwind_Ptr base
= 0;
719 for (; ! last_fde (ob
, this_fde
); this_fde
= next_fde (this_fde
))
721 const struct dwarf_cie
*this_cie
;
722 _Unwind_Ptr mask
, pc_begin
;
725 if (this_fde
->CIE_delta
== 0)
728 /* Determine the encoding for this FDE. Note mixed encoded
729 objects for later. */
730 this_cie
= get_cie (this_fde
);
731 if (this_cie
!= last_cie
)
734 encoding
= get_cie_encoding (this_cie
);
735 if (encoding
== DW_EH_PE_omit
)
737 base
= base_from_object (encoding
, ob
);
740 if (ob
->s
.b
.encoding
== DW_EH_PE_omit
)
741 ob
->s
.b
.encoding
= encoding
;
742 else if (ob
->s
.b
.encoding
!= encoding
)
743 ob
->s
.b
.mixed_encoding
= 1;
747 const unsigned char *p
;
748 p
= read_encoded_value_with_base (encoding
, base
, this_fde
->pc_begin
,
751 /* Take care to ignore link-once functions that were removed.
752 In these cases, the function address will be NULL, but if
753 the encoding is smaller than a pointer a true NULL may not
754 be representable. Assume 0 in the representable bits is NULL. */
755 mask
= size_of_encoded_value (encoding
);
756 if (mask
< sizeof (void *))
757 mask
= (((_Unwind_Ptr
) 1) << (mask
<< 3)) - 1;
761 if ((pc_begin
& mask
) == 0)
767 _Unwind_Ptr pc_range
, pc_end
;
768 read_encoded_value_with_base (encoding
& 0x0F, 0, p
, &pc_range
);
769 pc_end
= pc_begin
+ pc_range
;
770 if ((!range
[0]) && (!range
[1]))
777 if (pc_begin
< range
[0])
779 if (pc_end
> range
[1])
785 if ((void *) pc_begin
< ob
->pc_begin
)
786 ob
->pc_begin
= (void *) pc_begin
;
794 add_fdes (struct object
*ob
, struct fde_accumulator
*accu
, const fde
*this_fde
)
796 const struct dwarf_cie
*last_cie
= 0;
797 int encoding
= ob
->s
.b
.encoding
;
798 _Unwind_Ptr base
= base_from_object (ob
->s
.b
.encoding
, ob
);
800 for (; ! last_fde (ob
, this_fde
); this_fde
= next_fde (this_fde
))
802 const struct dwarf_cie
*this_cie
;
805 if (this_fde
->CIE_delta
== 0)
808 if (ob
->s
.b
.mixed_encoding
)
810 /* Determine the encoding for this FDE. Note mixed encoded
811 objects for later. */
812 this_cie
= get_cie (this_fde
);
813 if (this_cie
!= last_cie
)
816 encoding
= get_cie_encoding (this_cie
);
817 base
= base_from_object (encoding
, ob
);
821 if (encoding
== DW_EH_PE_absptr
)
824 memcpy (&ptr
, this_fde
->pc_begin
, sizeof (_Unwind_Ptr
));
830 _Unwind_Ptr pc_begin
, mask
;
832 read_encoded_value_with_base (encoding
, base
, this_fde
->pc_begin
,
835 /* Take care to ignore link-once functions that were removed.
836 In these cases, the function address will be NULL, but if
837 the encoding is smaller than a pointer a true NULL may not
838 be representable. Assume 0 in the representable bits is NULL. */
839 mask
= size_of_encoded_value (encoding
);
840 if (mask
< sizeof (void *))
841 mask
= (((_Unwind_Ptr
) 1) << (mask
<< 3)) - 1;
845 if ((pc_begin
& mask
) == 0)
849 fde_insert (accu
, this_fde
);
853 /* Set up a sorted array of pointers to FDEs for a loaded object. We
854 count up the entries before allocating the array because it's likely to
855 be faster. We can be called multiple times, should we have failed to
856 allocate a sorted fde array on a previous occasion. */
859 init_object (struct object
* ob
)
861 struct fde_accumulator accu
;
864 count
= ob
->s
.b
.count
;
867 if (ob
->s
.b
.from_array
)
869 fde
**p
= ob
->u
.array
;
870 for (count
= 0; *p
; ++p
)
872 size_t cur_count
= classify_object_over_fdes (ob
, *p
, NULL
);
873 if (cur_count
== (size_t) -1)
880 count
= classify_object_over_fdes (ob
, ob
->u
.single
, NULL
);
881 if (count
== (size_t) -1)
883 static const fde terminator
;
886 ob
->s
.b
.encoding
= DW_EH_PE_omit
;
887 ob
->u
.single
= &terminator
;
892 /* The count field we have in the main struct object is somewhat
893 limited, but should suffice for virtually all cases. If the
894 counted value doesn't fit, re-write a zero. The worst that
895 happens is that we re-count next time -- admittedly non-trivial
896 in that this implies some 2M fdes, but at least we function. */
897 ob
->s
.b
.count
= count
;
898 if (ob
->s
.b
.count
!= count
)
902 if (!start_fde_sort (&accu
, count
))
905 if (ob
->s
.b
.from_array
)
908 for (p
= ob
->u
.array
; *p
; ++p
)
909 add_fdes (ob
, &accu
, *p
);
912 add_fdes (ob
, &accu
, ob
->u
.single
);
914 end_fde_sort (ob
, &accu
, count
);
916 /* Save the original fde pointer, since this is the key by which the
917 DSO will deregister the object. */
918 accu
.linear
->orig_data
= ob
->u
.single
;
919 ob
->u
.sort
= accu
.linear
;
921 #ifdef ATOMIC_FDE_FAST_PATH
922 // We must update the sorted bit with an atomic operation
926 __atomic_store (&(ob
->s
.b
), &(tmp
.s
.b
), __ATOMIC_RELEASE
);
932 #ifdef ATOMIC_FDE_FAST_PATH
933 /* Get the PC range for lookup */
935 get_pc_range (const struct object
*ob
, uintptr_type
*range
)
937 // It is safe to cast to non-const object* here as
938 // classify_object_over_fdes does not modify ob in query mode.
939 struct object
*ncob
= (struct object
*) (uintptr_type
) ob
;
940 range
[0] = range
[1] = 0;
943 classify_object_over_fdes (ncob
, ob
->u
.sort
->orig_data
, range
);
945 else if (ob
->s
.b
.from_array
)
947 fde
**p
= ob
->u
.array
;
949 classify_object_over_fdes (ncob
, *p
, range
);
953 classify_object_over_fdes (ncob
, ob
->u
.single
, range
);
958 /* A linear search through a set of FDEs for the given PC. This is
959 used when there was insufficient memory to allocate and sort an
963 linear_search_fdes (struct object
*ob
, const fde
*this_fde
, void *pc
)
965 const struct dwarf_cie
*last_cie
= 0;
966 int encoding
= ob
->s
.b
.encoding
;
967 _Unwind_Ptr base
= base_from_object (ob
->s
.b
.encoding
, ob
);
969 for (; ! last_fde (ob
, this_fde
); this_fde
= next_fde (this_fde
))
971 const struct dwarf_cie
*this_cie
;
972 _Unwind_Ptr pc_begin
, pc_range
;
975 if (this_fde
->CIE_delta
== 0)
978 if (ob
->s
.b
.mixed_encoding
)
980 /* Determine the encoding for this FDE. Note mixed encoded
981 objects for later. */
982 this_cie
= get_cie (this_fde
);
983 if (this_cie
!= last_cie
)
986 encoding
= get_cie_encoding (this_cie
);
987 base
= base_from_object (encoding
, ob
);
991 if (encoding
== DW_EH_PE_absptr
)
993 const _Unwind_Ptr
*pc_array
= (const _Unwind_Ptr
*) this_fde
->pc_begin
;
994 pc_begin
= pc_array
[0];
995 pc_range
= pc_array
[1];
1002 const unsigned char *p
;
1004 p
= read_encoded_value_with_base (encoding
, base
,
1005 this_fde
->pc_begin
, &pc_begin
);
1006 read_encoded_value_with_base (encoding
& 0x0F, 0, p
, &pc_range
);
1008 /* Take care to ignore link-once functions that were removed.
1009 In these cases, the function address will be NULL, but if
1010 the encoding is smaller than a pointer a true NULL may not
1011 be representable. Assume 0 in the representable bits is NULL. */
1012 mask
= size_of_encoded_value (encoding
);
1013 if (mask
< sizeof (void *))
1014 mask
= (((_Unwind_Ptr
) 1) << (mask
<< 3)) - 1;
1018 if ((pc_begin
& mask
) == 0)
1022 if ((_Unwind_Ptr
) pc
- pc_begin
< pc_range
)
1029 /* Binary search for an FDE containing the given PC. Here are three
1030 implementations of increasing complexity. */
1032 static inline const fde
*
1033 binary_search_unencoded_fdes (struct object
*ob
, void *pc
)
1035 struct fde_vector
*vec
= ob
->u
.sort
;
1038 for (lo
= 0, hi
= vec
->count
; lo
< hi
; )
1040 size_t i
= (lo
+ hi
) / 2;
1041 const fde
*const f
= vec
->array
[i
];
1044 memcpy (&pc_begin
, (const void * const *) f
->pc_begin
, sizeof (void *));
1045 memcpy (&pc_range
, (const uaddr
*) f
->pc_begin
+ 1, sizeof (uaddr
));
1049 else if (pc
>= pc_begin
+ pc_range
)
1058 static inline const fde
*
1059 binary_search_single_encoding_fdes (struct object
*ob
, void *pc
)
1061 struct fde_vector
*vec
= ob
->u
.sort
;
1062 int encoding
= ob
->s
.b
.encoding
;
1063 _Unwind_Ptr base
= base_from_object (encoding
, ob
);
1066 for (lo
= 0, hi
= vec
->count
; lo
< hi
; )
1068 size_t i
= (lo
+ hi
) / 2;
1069 const fde
*f
= vec
->array
[i
];
1070 _Unwind_Ptr pc_begin
, pc_range
;
1071 const unsigned char *p
;
1073 p
= read_encoded_value_with_base (encoding
, base
, f
->pc_begin
,
1075 read_encoded_value_with_base (encoding
& 0x0F, 0, p
, &pc_range
);
1077 if ((_Unwind_Ptr
) pc
< pc_begin
)
1079 else if ((_Unwind_Ptr
) pc
>= pc_begin
+ pc_range
)
1088 static inline const fde
*
1089 binary_search_mixed_encoding_fdes (struct object
*ob
, void *pc
)
1091 struct fde_vector
*vec
= ob
->u
.sort
;
1094 for (lo
= 0, hi
= vec
->count
; lo
< hi
; )
1096 size_t i
= (lo
+ hi
) / 2;
1097 const fde
*f
= vec
->array
[i
];
1098 _Unwind_Ptr pc_begin
, pc_range
;
1099 const unsigned char *p
;
1102 encoding
= get_fde_encoding (f
);
1103 p
= read_encoded_value_with_base (encoding
,
1104 base_from_object (encoding
, ob
),
1105 f
->pc_begin
, &pc_begin
);
1106 read_encoded_value_with_base (encoding
& 0x0F, 0, p
, &pc_range
);
1108 if ((_Unwind_Ptr
) pc
< pc_begin
)
1110 else if ((_Unwind_Ptr
) pc
>= pc_begin
+ pc_range
)
1120 search_object (struct object
* ob
, void *pc
)
1122 /* The fast path initializes objects eagerly to avoid locking.
1123 * On the slow path we initialize them now */
1124 #ifndef ATOMIC_FDE_FAST_PATH
1125 /* If the data hasn't been sorted, try to do this now. We may have
1126 more memory available than last time we tried. */
1127 if (! ob
->s
.b
.sorted
)
1131 /* Despite the above comment, the normal reason to get here is
1132 that we've not processed this object before. A quick range
1133 check is in order. */
1134 if (pc
< ob
->pc_begin
)
1141 if (ob
->s
.b
.mixed_encoding
)
1142 return binary_search_mixed_encoding_fdes (ob
, pc
);
1143 else if (ob
->s
.b
.encoding
== DW_EH_PE_absptr
)
1144 return binary_search_unencoded_fdes (ob
, pc
);
1146 return binary_search_single_encoding_fdes (ob
, pc
);
1150 /* Long slow laborious linear search, cos we've no memory. */
1151 if (ob
->s
.b
.from_array
)
1154 for (p
= ob
->u
.array
; *p
; p
++)
1156 const fde
*f
= linear_search_fdes (ob
, *p
, pc
);
1163 return linear_search_fdes (ob
, ob
->u
.single
, pc
);
1167 #ifdef ATOMIC_FDE_FAST_PATH
1169 // Check if the object was already initialized
1171 is_object_initialized (struct object
*ob
)
1173 // We have to use acquire atomics for the read, which
1174 // is a bit involved as we read from a bitfield
1176 __atomic_load (&(ob
->s
.b
), &(tmp
.s
.b
), __ATOMIC_ACQUIRE
);
1177 return tmp
.s
.b
.sorted
;
1183 _Unwind_Find_FDE (void *pc
, struct dwarf_eh_bases
*bases
)
1186 const fde
*f
= NULL
;
1188 #ifdef ATOMIC_FDE_FAST_PATH
1189 ob
= btree_lookup (®istered_frames
, (uintptr_type
) pc
);
1193 // Initialize the object lazily
1194 if (!is_object_initialized (ob
))
1196 // Check again under mutex
1197 init_object_mutex_once ();
1198 __gthread_mutex_lock (&object_mutex
);
1200 if (!ob
->s
.b
.sorted
)
1205 __gthread_mutex_unlock (&object_mutex
);
1208 f
= search_object (ob
, pc
);
1211 init_object_mutex_once ();
1212 __gthread_mutex_lock (&object_mutex
);
1214 /* Linear search through the classified objects, to find the one
1215 containing the pc. Note that pc_begin is sorted descending, and
1216 we expect objects to be non-overlapping. */
1217 for (ob
= seen_objects
; ob
; ob
= ob
->next
)
1218 if (pc
>= ob
->pc_begin
)
1220 f
= search_object (ob
, pc
);
1226 /* Classify and search the objects we've not yet processed. */
1227 while ((ob
= unseen_objects
))
1231 unseen_objects
= ob
->next
;
1232 f
= search_object (ob
, pc
);
1234 /* Insert the object into the classified list. */
1235 for (p
= &seen_objects
; *p
; p
= &(*p
)->next
)
1236 if ((*p
)->pc_begin
< ob
->pc_begin
)
1246 __gthread_mutex_unlock (&object_mutex
);
1254 bases
->tbase
= ob
->tbase
;
1255 bases
->dbase
= ob
->dbase
;
1257 encoding
= ob
->s
.b
.encoding
;
1258 if (ob
->s
.b
.mixed_encoding
)
1259 encoding
= get_fde_encoding (f
);
1260 read_encoded_value_with_base (encoding
, base_from_object (encoding
, ob
),
1261 f
->pc_begin
, &func
);
1262 bases
->func
= (void *) func
;