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