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