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