gcc/unwind-dw2-fde.c

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