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