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