gcc/unwind-dw2-fde.c

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