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