gcc/unwind-dw2-fde.c

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