contrib/gcc-5.0/libgcc/unwind-dw2-fde.c

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