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