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