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