gcc/unwind-dw2-fde.c

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