gcc/unwind-dw2-fde.c

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