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