sysdeps/generic/unwind-dw2-fde.c

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