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         i2--;
 546         fde2 = v2->array[i2];
 547         while (i1 > 0 && fde_compare (ob, v1->array[i1-1], fde2) > 0)
 548           {
 549             v1->array[i1+i2] = v1->array[i1-1];
 550             i1--;
 551           }
 552         v1->array[i1+i2] = fde2;
 553       } while (i2 > 0);
 554       v1->count += v2->count;
 555     }
 556 }
 557
 558 static inline void
 559 end_fde_sort (struct object *ob, struct fde_accumulator *accu, size_t count)
 560 {
 561   fde_compare_t fde_compare;
 562
 563   if (accu->linear && accu->linear->count != count)
 564     abort ();
 565
 566   if (ob->s.b.mixed_encoding)
 567     fde_compare = fde_mixed_encoding_compare;
 568   else if (ob->s.b.encoding == DW_EH_PE_absptr)
 569     fde_compare = fde_unencoded_compare;
 570   else
 571     fde_compare = fde_single_encoding_compare;
 572
 573   if (accu->erratic)
 574     {
 575       fde_split (ob, fde_compare, accu->linear, accu->erratic);
 576       if (accu->linear->count + accu->erratic->count != count)
 577         abort ();
 578       frame_heapsort (ob, fde_compare, accu->erratic);
 579       fde_merge (ob, fde_compare, accu->linear, accu->erratic);
 580       free (accu->erratic);
 581     }
 582   else
 583     {
 584       /* We've not managed to malloc an erratic array,
 585          so heap sort in the linear one.  */
 586       frame_heapsort (ob, fde_compare, accu->linear);
 587     }
 588 }
 589
 590 \f
 591 /* Update encoding, mixed_encoding, and pc_begin for OB for the
 592    fde array beginning at THIS_FDE.  Return the number of fdes
 593    encountered along the way.  */
 594
 595 static size_t
 596 classify_object_over_fdes (struct object *ob, fde *this_fde)
 597 {
 598   struct dwarf_cie *last_cie = 0;
 599   size_t count = 0;
 600   int encoding = DW_EH_PE_absptr;
 601   _Unwind_Ptr base = 0;
 602
 603   for (; this_fde->length != 0; this_fde = next_fde (this_fde))
 604     {
 605       struct dwarf_cie *this_cie;
 606       _Unwind_Ptr mask, pc_begin;
 607
 608       /* Skip CIEs.  */
 609       if (this_fde->CIE_delta == 0)
 610         continue;
 611
 612       /* Determine the encoding for this FDE.  Note mixed encoded
 613          objects for later.  */
 614       this_cie = get_cie (this_fde);
 615       if (this_cie != last_cie)
 616         {
 617           last_cie = this_cie;
 618           encoding = get_cie_encoding (this_cie);
 619           base = base_from_object (encoding, ob);
 620           if (ob->s.b.encoding == DW_EH_PE_omit)
 621             ob->s.b.encoding = encoding;
 622           else if (ob->s.b.encoding != encoding)
 623             ob->s.b.mixed_encoding = 1;
 624         }
 625
 626       read_encoded_value_with_base (encoding, base, this_fde->pc_begin,
 627                                     &pc_begin);
 628
 629       /* Take care to ignore link-once functions that were removed.
 630          In these cases, the function address will be NULL, but if
 631          the encoding is smaller than a pointer a true NULL may not
 632          be representable.  Assume 0 in the representable bits is NULL.  */
 633       mask = size_of_encoded_value (encoding);
 634       if (mask < sizeof (void *))
 635         mask = (1L << (mask << 3)) - 1;
 636       else
 637         mask = -1;
 638
 639       if ((pc_begin & mask) == 0)
 640         continue;
 641
 642       count += 1;
 643       if ((void *)pc_begin < ob->pc_begin)
 644         ob->pc_begin = (void *)pc_begin;
 645     }
 646
 647   return count;
 648 }
 649
 650 static void
 651 add_fdes (struct object *ob, struct fde_accumulator *accu, fde *this_fde)
 652 {
 653   struct dwarf_cie *last_cie = 0;
 654   int encoding = ob->s.b.encoding;
 655   _Unwind_Ptr base = base_from_object (ob->s.b.encoding, ob);
 656
 657   for (; this_fde->length != 0; this_fde = next_fde (this_fde))
 658     {
 659       struct dwarf_cie *this_cie;
 660
 661       /* Skip CIEs.  */
 662       if (this_fde->CIE_delta == 0)
 663         continue;
 664
 665       if (ob->s.b.mixed_encoding)
 666         {
 667           /* Determine the encoding for this FDE.  Note mixed encoded
 668              objects for later.  */
 669           this_cie = get_cie (this_fde);
 670           if (this_cie != last_cie)
 671             {
 672               last_cie = this_cie;
 673               encoding = get_cie_encoding (this_cie);
 674               base = base_from_object (encoding, ob);
 675             }
 676         }
 677
 678       if (encoding == DW_EH_PE_absptr)
 679         {
 680           if (*(_Unwind_Ptr *)this_fde->pc_begin == 0)
 681             continue;
 682         }
 683       else
 684         {
 685           _Unwind_Ptr pc_begin, mask;
 686
 687           read_encoded_value_with_base (encoding, base, this_fde->pc_begin,
 688                                         &pc_begin);
 689
 690           /* Take care to ignore link-once functions that were removed.
 691              In these cases, the function address will be NULL, but if
 692              the encoding is smaller than a pointer a true NULL may not
 693              be representable.  Assume 0 in the representable bits is NULL.  */
 694           mask = size_of_encoded_value (encoding);
 695           if (mask < sizeof (void *))
 696             mask = (1L << (mask << 3)) - 1;
 697           else
 698             mask = -1;
 699
 700           if ((pc_begin & mask) == 0)
 701             continue;
 702         }
 703
 704       fde_insert (accu, this_fde);
 705     }
 706 }
 707
 708 /* Set up a sorted array of pointers to FDEs for a loaded object.  We
 709    count up the entries before allocating the array because it's likely to
 710    be faster.  We can be called multiple times, should we have failed to
 711    allocate a sorted fde array on a previous occasion.  */
 712
 713 static inline void
 714 init_object (struct object* ob)
 715 {
 716   struct fde_accumulator accu;
 717   size_t count;
 718
 719   count = ob->s.b.count;
 720   if (count == 0)
 721     {
 722       if (ob->s.b.from_array)
 723         {
 724           fde **p = ob->u.array;
 725           for (count = 0; *p; ++p)
 726             count += classify_object_over_fdes (ob, *p);
 727         }
 728       else
 729         count = classify_object_over_fdes (ob, ob->u.single);
 730
 731       /* The count field we have in the main struct object is somewhat
 732          limited, but should suffice for virtually all cases.  If the
 733          counted value doesn't fit, re-write a zero.  The worst that
 734          happens is that we re-count next time -- admittedly non-trivial
 735          in that this implies some 2M fdes, but at least we function.  */
 736       ob->s.b.count = count;
 737       if (ob->s.b.count != count)
 738         ob->s.b.count = 0;
 739     }
 740
 741   if (!start_fde_sort (&accu, count))
 742     return;
 743
 744   if (ob->s.b.from_array)
 745     {
 746       fde **p;
 747       for (p = ob->u.array; *p; ++p)
 748         add_fdes (ob, &accu, *p);
 749     }
 750   else
 751     add_fdes (ob, &accu, ob->u.single);
 752
 753   end_fde_sort (ob, &accu, count);
 754
 755   /* Save the original fde pointer, since this is the key by which the
 756      DSO will deregister the object.  */
 757   accu.linear->orig_data = ob->u.single;
 758   ob->u.sort = accu.linear;
 759
 760   ob->s.b.sorted = 1;
 761 }
 762
 763 /* A linear search through a set of FDEs for the given PC.  This is
 764    used when there was insufficient memory to allocate and sort an
 765    array.  */
 766
 767 static fde *
 768 linear_search_fdes (struct object *ob, fde *this_fde, void *pc)
 769 {
 770   struct dwarf_cie *last_cie = 0;
 771   int encoding = ob->s.b.encoding;
 772   _Unwind_Ptr base = base_from_object (ob->s.b.encoding, ob);
 773
 774   for (; this_fde->length != 0; this_fde = next_fde (this_fde))
 775     {
 776       struct dwarf_cie *this_cie;
 777       _Unwind_Ptr pc_begin, pc_range;
 778
 779       /* Skip CIEs.  */
 780       if (this_fde->CIE_delta == 0)
 781         continue;
 782
 783       if (ob->s.b.mixed_encoding)
 784         {
 785           /* Determine the encoding for this FDE.  Note mixed encoded
 786              objects for later.  */
 787           this_cie = get_cie (this_fde);
 788           if (this_cie != last_cie)
 789             {
 790               last_cie = this_cie;
 791               encoding = get_cie_encoding (this_cie);
 792               base = base_from_object (encoding, ob);
 793             }
 794         }
 795
 796       if (encoding == DW_EH_PE_absptr)
 797         {
 798           pc_begin = ((_Unwind_Ptr *)this_fde->pc_begin)[0];
 799           pc_range = ((_Unwind_Ptr *)this_fde->pc_begin)[1];
 800           if (pc_begin == 0)
 801             continue;
 802         }
 803       else
 804         {
 805           _Unwind_Ptr mask;
 806           const char *p;
 807
 808           p = read_encoded_value_with_base (encoding, base,
 809                                             this_fde->pc_begin, &pc_begin);
 810           read_encoded_value_with_base (encoding & 0x0F, 0, p, &pc_range);
 811
 812           /* Take care to ignore link-once functions that were removed.
 813              In these cases, the function address will be NULL, but if
 814              the encoding is smaller than a pointer a true NULL may not
 815              be representable.  Assume 0 in the representable bits is NULL.  */
 816           mask = size_of_encoded_value (encoding);
 817           if (mask < sizeof (void *))
 818             mask = (1L << (mask << 3)) - 1;
 819           else
 820             mask = -1;
 821
 822           if ((pc_begin & mask) == 0)
 823             continue;
 824         }
 825
 826       if ((_Unwind_Ptr)pc - pc_begin < pc_range)
 827         return this_fde;
 828     }
 829
 830   return NULL;
 831 }
 832
 833 /* Binary search for an FDE containing the given PC.  Here are three
 834    implementations of increasing complexity.  */
 835
 836 static inline fde *
 837 binary_search_unencoded_fdes (struct object *ob, void *pc)
 838 {
 839   struct fde_vector *vec = ob->u.sort;
 840   size_t lo, hi;
 841
 842   for (lo = 0, hi = vec->count; lo < hi; )
 843     {
 844       size_t i = (lo + hi) / 2;
 845       fde *f = vec->array[i];
 846       void *pc_begin;
 847       uaddr pc_range;
 848
 849       pc_begin = ((void **)f->pc_begin)[0];
 850       pc_range = ((uaddr *)f->pc_begin)[1];
 851
 852       if (pc < pc_begin)
 853         hi = i;
 854       else if (pc >= pc_begin + pc_range)
 855         lo = i + 1;
 856       else
 857         return f;
 858     }
 859
 860   return NULL;
 861 }
 862
 863 static inline fde *
 864 binary_search_single_encoding_fdes (struct object *ob, void *pc)
 865 {
 866   struct fde_vector *vec = ob->u.sort;
 867   int encoding = ob->s.b.encoding;
 868   _Unwind_Ptr base = base_from_object (encoding, ob);
 869   size_t lo, hi;
 870
 871   for (lo = 0, hi = vec->count; lo < hi; )
 872     {
 873       size_t i = (lo + hi) / 2;
 874       fde *f = vec->array[i];
 875       _Unwind_Ptr pc_begin, pc_range;
 876       const char *p;
 877
 878       p = read_encoded_value_with_base (encoding, base, f->pc_begin,
 879                                         &pc_begin);
 880       read_encoded_value_with_base (encoding & 0x0F, 0, p, &pc_range);
 881
 882       if ((_Unwind_Ptr)pc < pc_begin)
 883         hi = i;
 884       else if ((_Unwind_Ptr)pc >= pc_begin + pc_range)
 885         lo = i + 1;
 886       else
 887         return f;
 888     }
 889
 890   return NULL;
 891 }
 892
 893 static inline fde *
 894 binary_search_mixed_encoding_fdes (struct object *ob, void *pc)
 895 {
 896   struct fde_vector *vec = ob->u.sort;
 897   size_t lo, hi;
 898
 899   for (lo = 0, hi = vec->count; lo < hi; )
 900     {
 901       size_t i = (lo + hi) / 2;
 902       fde *f = vec->array[i];
 903       _Unwind_Ptr pc_begin, pc_range;
 904       const char *p;
 905       int encoding;
 906
 907       encoding = get_fde_encoding (f);
 908       p = read_encoded_value_with_base (encoding,
 909                                         base_from_object (encoding, ob),
 910                                         f->pc_begin, &pc_begin);
 911       read_encoded_value_with_base (encoding & 0x0F, 0, p, &pc_range);
 912
 913       if ((_Unwind_Ptr)pc < pc_begin)
 914         hi = i;
 915       else if ((_Unwind_Ptr)pc >= pc_begin + pc_range)
 916         lo = i + 1;
 917       else
 918         return f;
 919     }
 920
 921   return NULL;
 922 }
 923
 924 static fde *
 925 search_object (struct object* ob, void *pc)
 926 {
 927   /* If the data hasn't been sorted, try to do this now.  We may have
 928      more memory available than last time we tried.  */
 929   if (! ob->s.b.sorted)
 930     {
 931       init_object (ob);
 932
 933       /* Despite the above comment, the normal reason to get here is
 934          that we've not processed this object before.  A quick range
 935          check is in order.  */
 936       if (pc < ob->pc_begin)
 937         return NULL;
 938     }
 939
 940   if (ob->s.b.sorted)
 941     {
 942       if (ob->s.b.mixed_encoding)
 943         return binary_search_mixed_encoding_fdes (ob, pc);
 944       else if (ob->s.b.encoding == DW_EH_PE_absptr)
 945         return binary_search_unencoded_fdes (ob, pc);
 946       else
 947         return binary_search_single_encoding_fdes (ob, pc);
 948     }
 949   else
 950     {
 951       /* Long slow labourious linear search, cos we've no memory.  */
 952       if (ob->s.b.from_array)
 953         {
 954           fde **p;
 955           for (p = ob->u.array; *p ; p++)
 956             {
 957               fde *f = linear_search_fdes (ob, *p, pc);
 958               if (f)
 959                 return f;
 960             }
 961           return NULL;
 962         }
 963       else
 964         return linear_search_fdes (ob, ob->u.single, pc);
 965     }
 966 }
 967
 968 fde *
 969 _Unwind_Find_FDE (void *pc, struct dwarf_eh_bases *bases)
 970 {
 971   struct object *ob;
 972   fde *f = NULL;
 973
 974   init_object_mutex_once ();
 975   __gthread_mutex_lock (&object_mutex);
 976
 977   /* Linear search through the classified objects, to find the one
 978      containing the pc.  Note that pc_begin is sorted descending, and
 979      we expect objects to be non-overlapping.  */
 980   for (ob = seen_objects; ob; ob = ob->next)
 981     if (pc >= ob->pc_begin)
 982       {
 983         f = search_object (ob, pc);
 984         if (f)
 985           goto fini;
 986         break;
 987       }
 988
 989   /* Classify and search the objects we've not yet processed.  */
 990   while ((ob = unseen_objects))
 991     {
 992       struct object **p;
 993
 994       unseen_objects = ob->next;
 995       f = search_object (ob, pc);
 996
 997       /* Insert the object into the classified list.  */
 998       for (p = &seen_objects; *p ; p = &(*p)->next)
 999         if ((*p)->pc_begin < ob->pc_begin)
1000           break;
1001       ob->next = *p;
1002       *p = ob;
1003
1004       if (f)
1005         goto fini;
1006     }
1007
1008  fini:
1009   __gthread_mutex_unlock (&object_mutex);
1010
1011   if (f)
1012     {
1013       int encoding;
1014
1015       bases->tbase = ob->tbase;
1016       bases->dbase = ob->dbase;
1017
1018       encoding = ob->s.b.encoding;
1019       if (ob->s.b.mixed_encoding)
1020         encoding = get_fde_encoding (f);
1021       read_encoded_value_with_base (encoding, base_from_object (encoding, ob),
1022                                     f->pc_begin, (_Unwind_Ptr *)&bases->func);
1023     }
1024
1025   return f;
1026 }