Back to index

glibc  2.9
unwind-dw2-fde.c
Go to the documentation of this file.
00001 /* Subroutines needed for unwinding stack frames for exception handling.  */
00002 /* Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2006, 2007
00003    Free Software Foundation, Inc.
00004    Contributed by Jason Merrill <jason@cygnus.com>.
00005 
00006    This file is part of the GNU C Library.
00007 
00008    The GNU C Library is free software; you can redistribute it and/or
00009    modify it under the terms of the GNU Lesser General Public
00010    License as published by the Free Software Foundation; either
00011    version 2.1 of the License, or (at your option) any later version.
00012 
00013    The GNU C Library is distributed in the hope that it will be useful,
00014    but WITHOUT ANY WARRANTY; without even the implied warranty of
00015    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00016    Lesser General Public License for more details.
00017 
00018    You should have received a copy of the GNU Lesser General Public
00019    License along with the GNU C Library; if not, write to the Free
00020    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
00021    02111-1307 USA.  */
00022 
00023 #ifdef _LIBC
00024 # include <shlib-compat.h>
00025 #endif
00026 
00027 #if !defined _LIBC || SHLIB_COMPAT (libc, GLIBC_2_0, GLIBC_2_2_5)
00028 
00029 #ifdef _LIBC
00030 #include <stdlib.h>
00031 #include <string.h>
00032 #include <bits/libc-lock.h>
00033 #include <dwarf2.h>
00034 #include <unwind.h>
00035 #define NO_BASE_OF_ENCODED_VALUE
00036 #include <unwind-pe.h>
00037 #include <unwind-dw2-fde.h>
00038 #else
00039 #ifndef _Unwind_Find_FDE
00040 #include "tconfig.h"
00041 #include "tsystem.h"
00042 #include "dwarf2.h"
00043 #include "unwind.h"
00044 #define NO_BASE_OF_ENCODED_VALUE
00045 #include "unwind-pe.h"
00046 #include "unwind-dw2-fde.h"
00047 #include "gthr.h"
00048 #endif
00049 #endif
00050 
00051 /* The unseen_objects list contains objects that have been registered
00052    but not yet categorized in any way.  The seen_objects list has had
00053    it's pc_begin and count fields initialized at minimum, and is sorted
00054    by decreasing value of pc_begin.  */
00055 static struct object *unseen_objects;
00056 static struct object *seen_objects;
00057 
00058 #ifdef _LIBC
00059 
00060 __libc_lock_define_initialized (static, object_mutex)
00061 #define init_object_mutex_once()
00062 #define __gthread_mutex_lock(m) __libc_lock_lock (*(m))
00063 #define __gthread_mutex_unlock(m) __libc_lock_unlock (*(m))
00064 
00065 void __register_frame_info_bases_internal (void *begin, struct object *ob,
00066                                       void *tbase, void *dbase);
00067 void __register_frame_info_table_bases_internal (void *begin,
00068                                            struct object *ob,
00069                                            void *tbase, void *dbase);
00070 void *__deregister_frame_info_bases_internal (void *begin);
00071 
00072 #else
00073 
00074 #ifdef __GTHREAD_MUTEX_INIT
00075 static __gthread_mutex_t object_mutex = __GTHREAD_MUTEX_INIT;
00076 #else
00077 static __gthread_mutex_t object_mutex;
00078 #endif
00079 
00080 #ifdef __GTHREAD_MUTEX_INIT_FUNCTION
00081 static void
00082 init_object_mutex (void)
00083 {
00084   __GTHREAD_MUTEX_INIT_FUNCTION (&object_mutex);
00085 }
00086 
00087 static void
00088 init_object_mutex_once (void)
00089 {
00090   static __gthread_once_t once = __GTHREAD_ONCE_INIT;
00091   __gthread_once (&once, init_object_mutex);
00092 }
00093 #else
00094 #define init_object_mutex_once()
00095 #endif
00096 
00097 #endif /* _LIBC */
00098 
00099 /* Called from crtbegin.o to register the unwind info for an object.  */
00100 
00101 void
00102 __register_frame_info_bases (void *begin, struct object *ob,
00103                           void *tbase, void *dbase)
00104 {
00105   /* If .eh_frame is empty, don't register at all.  */
00106   if (*(uword *) begin == 0)
00107     return;
00108 
00109   ob->pc_begin = (void *)-1;
00110   ob->tbase = tbase;
00111   ob->dbase = dbase;
00112   ob->u.single = begin;
00113   ob->s.i = 0;
00114   ob->s.b.encoding = DW_EH_PE_omit;
00115 #ifdef DWARF2_OBJECT_END_PTR_EXTENSION
00116   ob->fde_end = NULL;
00117 #endif
00118 
00119   init_object_mutex_once ();
00120   __gthread_mutex_lock (&object_mutex);
00121 
00122   ob->next = unseen_objects;
00123   unseen_objects = ob;
00124 
00125   __gthread_mutex_unlock (&object_mutex);
00126 }
00127 INTDEF(__register_frame_info_bases)
00128 
00129 void
00130 __register_frame_info (void *begin, struct object *ob)
00131 {
00132   INTUSE(__register_frame_info_bases) (begin, ob, 0, 0);
00133 }
00134 
00135 void
00136 __register_frame (void *begin)
00137 {
00138   struct object *ob;
00139 
00140   /* If .eh_frame is empty, don't register at all.  */
00141   if (*(uword *) begin == 0)
00142     return;
00143 
00144   ob = (struct object *) malloc (sizeof (struct object));
00145   INTUSE(__register_frame_info_bases) (begin, ob, 0, 0);
00146 }
00147 
00148 /* Similar, but BEGIN is actually a pointer to a table of unwind entries
00149    for different translation units.  Called from the file generated by
00150    collect2.  */
00151 
00152 void
00153 __register_frame_info_table_bases (void *begin, struct object *ob,
00154                                void *tbase, void *dbase)
00155 {
00156   ob->pc_begin = (void *)-1;
00157   ob->tbase = tbase;
00158   ob->dbase = dbase;
00159   ob->u.array = begin;
00160   ob->s.i = 0;
00161   ob->s.b.from_array = 1;
00162   ob->s.b.encoding = DW_EH_PE_omit;
00163 
00164   init_object_mutex_once ();
00165   __gthread_mutex_lock (&object_mutex);
00166 
00167   ob->next = unseen_objects;
00168   unseen_objects = ob;
00169 
00170   __gthread_mutex_unlock (&object_mutex);
00171 }
00172 INTDEF(__register_frame_info_table_bases)
00173 
00174 void
00175 __register_frame_info_table (void *begin, struct object *ob)
00176 {
00177   INTUSE(__register_frame_info_table_bases) (begin, ob, 0, 0);
00178 }
00179 
00180 void
00181 __register_frame_table (void *begin)
00182 {
00183   struct object *ob = (struct object *) malloc (sizeof (struct object));
00184   INTUSE(__register_frame_info_table_bases) (begin, ob, 0, 0);
00185 }
00186 
00187 /* Called from crtbegin.o to deregister the unwind info for an object.  */
00188 /* ??? Glibc has for a while now exported __register_frame_info and
00189    __deregister_frame_info.  If we call __register_frame_info_bases
00190    from crtbegin (wherein it is declared weak), and this object does
00191    not get pulled from libgcc.a for other reasons, then the
00192    invocation of __deregister_frame_info will be resolved from glibc.
00193    Since the registration did not happen there, we'll abort.
00194 
00195    Therefore, declare a new deregistration entry point that does the
00196    exact same thing, but will resolve to the same library as
00197    implements __register_frame_info_bases.  */
00198 
00199 void *
00200 __deregister_frame_info_bases (void *begin)
00201 {
00202   struct object **p;
00203   struct object *ob = 0;
00204 
00205   /* If .eh_frame is empty, we haven't registered.  */
00206   if (*(uword *) begin == 0)
00207     return ob;
00208 
00209   init_object_mutex_once ();
00210   __gthread_mutex_lock (&object_mutex);
00211 
00212   for (p = &unseen_objects; *p ; p = &(*p)->next)
00213     if ((*p)->u.single == begin)
00214       {
00215        ob = *p;
00216        *p = ob->next;
00217        goto out;
00218       }
00219 
00220   for (p = &seen_objects; *p ; p = &(*p)->next)
00221     if ((*p)->s.b.sorted)
00222       {
00223        if ((*p)->u.sort->orig_data == begin)
00224          {
00225            ob = *p;
00226            *p = ob->next;
00227            free (ob->u.sort);
00228            goto out;
00229          }
00230       }
00231     else
00232       {
00233        if ((*p)->u.single == begin)
00234          {
00235            ob = *p;
00236            *p = ob->next;
00237            goto out;
00238          }
00239       }
00240 
00241   __gthread_mutex_unlock (&object_mutex);
00242   abort ();
00243 
00244  out:
00245   __gthread_mutex_unlock (&object_mutex);
00246   return (void *) ob;
00247 }
00248 INTDEF(__deregister_frame_info_bases)
00249 
00250 void *
00251 __deregister_frame_info (void *begin)
00252 {
00253   return INTUSE(__deregister_frame_info_bases) (begin);
00254 }
00255 
00256 void
00257 __deregister_frame (void *begin)
00258 {
00259   /* If .eh_frame is empty, we haven't registered.  */
00260   if (*(uword *) begin != 0)
00261     free (INTUSE(__deregister_frame_info_bases) (begin));
00262 }
00263 
00264 
00265 /* Like base_of_encoded_value, but take the base from a struct object
00266    instead of an _Unwind_Context.  */
00267 
00268 static _Unwind_Ptr
00269 base_from_object (unsigned char encoding, struct object *ob)
00270 {
00271   if (encoding == DW_EH_PE_omit)
00272     return 0;
00273 
00274   switch (encoding & 0x70)
00275     {
00276     case DW_EH_PE_absptr:
00277     case DW_EH_PE_pcrel:
00278     case DW_EH_PE_aligned:
00279       return 0;
00280 
00281     case DW_EH_PE_textrel:
00282       return (_Unwind_Ptr) ob->tbase;
00283     case DW_EH_PE_datarel:
00284       return (_Unwind_Ptr) ob->dbase;
00285     }
00286   abort ();
00287 }
00288 
00289 /* Return the FDE pointer encoding from the CIE.  */
00290 /* ??? This is a subset of extract_cie_info from unwind-dw2.c.  */
00291 
00292 static int
00293 get_cie_encoding (struct dwarf_cie *cie)
00294 {
00295   const unsigned char *aug, *p;
00296   _Unwind_Ptr dummy;
00297   _Unwind_Word utmp;
00298   _Unwind_Sword stmp;
00299 
00300   aug = cie->augmentation;
00301   if (aug[0] != 'z')
00302     return DW_EH_PE_absptr;
00303 
00304   /* Skip the augmentation string.  */
00305   p = aug + strlen ((const char *) aug) + 1;
00306   p = read_uleb128 (p, &utmp);            /* Skip code alignment.  */
00307   p = read_sleb128 (p, &stmp);            /* Skip data alignment.  */
00308   p++;                             /* Skip return address column.  */
00309 
00310   aug++;                           /* Skip 'z' */
00311   p = read_uleb128 (p, &utmp);            /* Skip augmentation length.  */
00312   while (1)
00313     {
00314       /* This is what we're looking for.  */
00315       if (*aug == 'R')
00316        return *p;
00317       /* Personality encoding and pointer.  */
00318       else if (*aug == 'P')
00319        {
00320          /* ??? Avoid dereferencing indirect pointers, since we're
00321             faking the base address.  Gotta keep DW_EH_PE_aligned
00322             intact, however.  */
00323          p = read_encoded_value_with_base (*p & 0x7F, 0, p + 1, &dummy);
00324        }
00325       /* LSDA encoding.  */
00326       else if (*aug == 'L')
00327        p++;
00328       /* Otherwise end of string, or unknown augmentation.  */
00329       else
00330        return DW_EH_PE_absptr;
00331       aug++;
00332     }
00333 }
00334 
00335 static inline int
00336 get_fde_encoding (struct dwarf_fde *f)
00337 {
00338   return get_cie_encoding (get_cie (f));
00339 }
00340 
00341 
00342 /* Sorting an array of FDEs by address.
00343    (Ideally we would have the linker sort the FDEs so we don't have to do
00344    it at run time. But the linkers are not yet prepared for this.)  */
00345 
00346 /* Comparison routines.  Three variants of increasing complexity.  */
00347 
00348 static int
00349 fde_unencoded_compare (struct object *ob __attribute__((unused)),
00350                      fde *x, fde *y)
00351 {
00352   _Unwind_Ptr x_ptr = *(_Unwind_Ptr *) x->pc_begin;
00353   _Unwind_Ptr y_ptr = *(_Unwind_Ptr *) y->pc_begin;
00354 
00355   if (x_ptr > y_ptr)
00356     return 1;
00357   if (x_ptr < y_ptr)
00358     return -1;
00359   return 0;
00360 }
00361 
00362 static int
00363 fde_single_encoding_compare (struct object *ob, fde *x, fde *y)
00364 {
00365   _Unwind_Ptr base, x_ptr, y_ptr;
00366 
00367   base = base_from_object (ob->s.b.encoding, ob);
00368   read_encoded_value_with_base (ob->s.b.encoding, base, x->pc_begin, &x_ptr);
00369   read_encoded_value_with_base (ob->s.b.encoding, base, y->pc_begin, &y_ptr);
00370 
00371   if (x_ptr > y_ptr)
00372     return 1;
00373   if (x_ptr < y_ptr)
00374     return -1;
00375   return 0;
00376 }
00377 
00378 static int
00379 fde_mixed_encoding_compare (struct object *ob, fde *x, fde *y)
00380 {
00381   int x_encoding, y_encoding;
00382   _Unwind_Ptr x_ptr, y_ptr;
00383 
00384   x_encoding = get_fde_encoding (x);
00385   read_encoded_value_with_base (x_encoding, base_from_object (x_encoding, ob),
00386                             x->pc_begin, &x_ptr);
00387 
00388   y_encoding = get_fde_encoding (y);
00389   read_encoded_value_with_base (y_encoding, base_from_object (y_encoding, ob),
00390                             y->pc_begin, &y_ptr);
00391 
00392   if (x_ptr > y_ptr)
00393     return 1;
00394   if (x_ptr < y_ptr)
00395     return -1;
00396   return 0;
00397 }
00398 
00399 typedef int (*fde_compare_t) (struct object *, fde *, fde *);
00400 
00401 
00402 /* This is a special mix of insertion sort and heap sort, optimized for
00403    the data sets that actually occur. They look like
00404    101 102 103 127 128 105 108 110 190 111 115 119 125 160 126 129 130.
00405    I.e. a linearly increasing sequence (coming from functions in the text
00406    section), with additionally a few unordered elements (coming from functions
00407    in gnu_linkonce sections) whose values are higher than the values in the
00408    surrounding linear sequence (but not necessarily higher than the values
00409    at the end of the linear sequence!).
00410    The worst-case total run time is O(N) + O(n log (n)), where N is the
00411    total number of FDEs and n is the number of erratic ones.  */
00412 
00413 struct fde_accumulator
00414 {
00415   struct fde_vector *linear;
00416   struct fde_vector *erratic;
00417 };
00418 
00419 static int
00420 start_fde_sort (struct fde_accumulator *accu, size_t count)
00421 {
00422   size_t size;
00423   if (! count)
00424     return 0;
00425 
00426   size = sizeof (struct fde_vector) + sizeof (fde *) * count;
00427   if ((accu->linear = (struct fde_vector *) malloc (size)))
00428     {
00429       accu->linear->count = 0;
00430       if ((accu->erratic = (struct fde_vector *) malloc (size)))
00431        accu->erratic->count = 0;
00432       return 1;
00433     }
00434   else
00435     return 0;
00436 }
00437 
00438 static inline void
00439 fde_insert (struct fde_accumulator *accu, fde *this_fde)
00440 {
00441   if (accu->linear)
00442     accu->linear->array[accu->linear->count++] = this_fde;
00443 }
00444 
00445 /* Split LINEAR into a linear sequence with low values and an erratic
00446    sequence with high values, put the linear one (of longest possible
00447    length) into LINEAR and the erratic one into ERRATIC. This is O(N).
00448 
00449    Because the longest linear sequence we are trying to locate within the
00450    incoming LINEAR array can be interspersed with (high valued) erratic
00451    entries.  We construct a chain indicating the sequenced entries.
00452    To avoid having to allocate this chain, we overlay it onto the space of
00453    the ERRATIC array during construction.  A final pass iterates over the
00454    chain to determine what should be placed in the ERRATIC array, and
00455    what is the linear sequence.  This overlay is safe from aliasing.  */
00456 
00457 static void
00458 fde_split (struct object *ob, fde_compare_t fde_compare,
00459           struct fde_vector *linear, struct fde_vector *erratic)
00460 {
00461   static fde *marker;
00462   size_t count = linear->count;
00463   fde **chain_end = &marker;
00464   size_t i, j, k;
00465 
00466   /* This should optimize out, but it is wise to make sure this assumption
00467      is correct. Should these have different sizes, we cannot cast between
00468      them and the overlaying onto ERRATIC will not work.  */
00469   if (sizeof (fde *) != sizeof (fde **))
00470     abort ();
00471 
00472   for (i = 0; i < count; i++)
00473     {
00474       fde **probe;
00475 
00476       for (probe = chain_end;
00477           probe != &marker && fde_compare (ob, linear->array[i], *probe) < 0;
00478           probe = chain_end)
00479        {
00480          chain_end = (fde **) erratic->array[probe - linear->array];
00481          erratic->array[probe - linear->array] = NULL;
00482        }
00483       erratic->array[i] = (fde *) chain_end;
00484       chain_end = &linear->array[i];
00485     }
00486 
00487   /* Each entry in LINEAR which is part of the linear sequence we have
00488      discovered will correspond to a non-NULL entry in the chain we built in
00489      the ERRATIC array.  */
00490   for (i = j = k = 0; i < count; i++)
00491     if (erratic->array[i])
00492       linear->array[j++] = linear->array[i];
00493     else
00494       erratic->array[k++] = linear->array[i];
00495   linear->count = j;
00496   erratic->count = k;
00497 }
00498 
00499 /* This is O(n log(n)).  BSD/OS defines heapsort in stdlib.h, so we must
00500    use a name that does not conflict.  */
00501 
00502 static void
00503 frame_heapsort (struct object *ob, fde_compare_t fde_compare,
00504               struct fde_vector *erratic)
00505 {
00506   /* For a description of this algorithm, see:
00507      Samuel P. Harbison, Guy L. Steele Jr.: C, a reference manual, 2nd ed.,
00508      p. 60-61.  */
00509   fde ** a = erratic->array;
00510   /* A portion of the array is called a "heap" if for all i>=0:
00511      If i and 2i+1 are valid indices, then a[i] >= a[2i+1].
00512      If i and 2i+2 are valid indices, then a[i] >= a[2i+2].  */
00513 #define SWAP(x,y) do { fde * tmp = x; x = y; y = tmp; } while (0)
00514   size_t n = erratic->count;
00515   size_t m = n;
00516   size_t i;
00517 
00518   while (m > 0)
00519     {
00520       /* Invariant: a[m..n-1] is a heap.  */
00521       m--;
00522       for (i = m; 2*i+1 < n; )
00523        {
00524          if (2*i+2 < n
00525              && fde_compare (ob, a[2*i+2], a[2*i+1]) > 0
00526              && fde_compare (ob, a[2*i+2], a[i]) > 0)
00527            {
00528              SWAP (a[i], a[2*i+2]);
00529              i = 2*i+2;
00530            }
00531          else if (fde_compare (ob, a[2*i+1], a[i]) > 0)
00532            {
00533              SWAP (a[i], a[2*i+1]);
00534              i = 2*i+1;
00535            }
00536          else
00537            break;
00538        }
00539     }
00540   while (n > 1)
00541     {
00542       /* Invariant: a[0..n-1] is a heap.  */
00543       n--;
00544       SWAP (a[0], a[n]);
00545       for (i = 0; 2*i+1 < n; )
00546        {
00547          if (2*i+2 < n
00548              && fde_compare (ob, a[2*i+2], a[2*i+1]) > 0
00549              && fde_compare (ob, a[2*i+2], a[i]) > 0)
00550            {
00551              SWAP (a[i], a[2*i+2]);
00552              i = 2*i+2;
00553            }
00554          else if (fde_compare (ob, a[2*i+1], a[i]) > 0)
00555            {
00556              SWAP (a[i], a[2*i+1]);
00557              i = 2*i+1;
00558            }
00559          else
00560            break;
00561        }
00562     }
00563 #undef SWAP
00564 }
00565 
00566 /* Merge V1 and V2, both sorted, and put the result into V1.  */
00567 static void
00568 fde_merge (struct object *ob, fde_compare_t fde_compare,
00569           struct fde_vector *v1, struct fde_vector *v2)
00570 {
00571   size_t i1, i2;
00572   fde * fde2;
00573 
00574   i2 = v2->count;
00575   if (i2 > 0)
00576     {
00577       i1 = v1->count;
00578       do
00579        {
00580          i2--;
00581          fde2 = v2->array[i2];
00582          while (i1 > 0 && fde_compare (ob, v1->array[i1-1], fde2) > 0)
00583            {
00584              v1->array[i1+i2] = v1->array[i1-1];
00585              i1--;
00586            }
00587          v1->array[i1+i2] = fde2;
00588        }
00589       while (i2 > 0);
00590       v1->count += v2->count;
00591     }
00592 }
00593 
00594 static void
00595 end_fde_sort (struct object *ob, struct fde_accumulator *accu, size_t count)
00596 {
00597   fde_compare_t fde_compare;
00598 
00599   if (accu->linear->count != count)
00600     abort ();
00601 
00602   if (ob->s.b.mixed_encoding)
00603     fde_compare = fde_mixed_encoding_compare;
00604   else if (ob->s.b.encoding == DW_EH_PE_absptr)
00605     fde_compare = fde_unencoded_compare;
00606   else
00607     fde_compare = fde_single_encoding_compare;
00608 
00609   if (accu->erratic)
00610     {
00611       fde_split (ob, fde_compare, accu->linear, accu->erratic);
00612       if (accu->linear->count + accu->erratic->count != count)
00613        abort ();
00614       frame_heapsort (ob, fde_compare, accu->erratic);
00615       fde_merge (ob, fde_compare, accu->linear, accu->erratic);
00616       free (accu->erratic);
00617     }
00618   else
00619     {
00620       /* We've not managed to malloc an erratic array,
00621         so heap sort in the linear one.  */
00622       frame_heapsort (ob, fde_compare, accu->linear);
00623     }
00624 }
00625 
00626 
00627 /* Update encoding, mixed_encoding, and pc_begin for OB for the
00628    fde array beginning at THIS_FDE.  Return the number of fdes
00629    encountered along the way.  */
00630 
00631 static size_t
00632 classify_object_over_fdes (struct object *ob, fde *this_fde)
00633 {
00634   struct dwarf_cie *last_cie = 0;
00635   size_t count = 0;
00636   int encoding = DW_EH_PE_absptr;
00637   _Unwind_Ptr base = 0;
00638 
00639   for (; ! last_fde (ob, this_fde); this_fde = next_fde (this_fde))
00640     {
00641       struct dwarf_cie *this_cie;
00642       _Unwind_Ptr mask, pc_begin;
00643 
00644       /* Skip CIEs.  */
00645       if (this_fde->CIE_delta == 0)
00646        continue;
00647 
00648       /* Determine the encoding for this FDE.  Note mixed encoded
00649         objects for later.  */
00650       this_cie = get_cie (this_fde);
00651       if (this_cie != last_cie)
00652        {
00653          last_cie = this_cie;
00654          encoding = get_cie_encoding (this_cie);
00655          base = base_from_object (encoding, ob);
00656          if (ob->s.b.encoding == DW_EH_PE_omit)
00657            ob->s.b.encoding = encoding;
00658          else if (ob->s.b.encoding != encoding)
00659            ob->s.b.mixed_encoding = 1;
00660        }
00661 
00662       read_encoded_value_with_base (encoding, base, this_fde->pc_begin,
00663                                 &pc_begin);
00664 
00665       /* Take care to ignore link-once functions that were removed.
00666         In these cases, the function address will be NULL, but if
00667         the encoding is smaller than a pointer a true NULL may not
00668         be representable.  Assume 0 in the representable bits is NULL.  */
00669       mask = size_of_encoded_value (encoding);
00670       if (mask < sizeof (void *))
00671        mask = (1L << (mask << 3)) - 1;
00672       else
00673        mask = -1;
00674 
00675       if ((pc_begin & mask) == 0)
00676        continue;
00677 
00678       count += 1;
00679       if ((void *) pc_begin < ob->pc_begin)
00680        ob->pc_begin = (void *) pc_begin;
00681     }
00682 
00683   return count;
00684 }
00685 
00686 static void
00687 add_fdes (struct object *ob, struct fde_accumulator *accu, fde *this_fde)
00688 {
00689   struct dwarf_cie *last_cie = 0;
00690   int encoding = ob->s.b.encoding;
00691   _Unwind_Ptr base = base_from_object (ob->s.b.encoding, ob);
00692 
00693   for (; ! last_fde (ob, this_fde); this_fde = next_fde (this_fde))
00694     {
00695       struct dwarf_cie *this_cie;
00696 
00697       /* Skip CIEs.  */
00698       if (this_fde->CIE_delta == 0)
00699        continue;
00700 
00701       if (ob->s.b.mixed_encoding)
00702        {
00703          /* Determine the encoding for this FDE.  Note mixed encoded
00704             objects for later.  */
00705          this_cie = get_cie (this_fde);
00706          if (this_cie != last_cie)
00707            {
00708              last_cie = this_cie;
00709              encoding = get_cie_encoding (this_cie);
00710              base = base_from_object (encoding, ob);
00711            }
00712        }
00713 
00714       if (encoding == DW_EH_PE_absptr)
00715        {
00716          if (*(_Unwind_Ptr *) this_fde->pc_begin == 0)
00717            continue;
00718        }
00719       else
00720        {
00721          _Unwind_Ptr pc_begin, mask;
00722 
00723          read_encoded_value_with_base (encoding, base, this_fde->pc_begin,
00724                                    &pc_begin);
00725 
00726          /* Take care to ignore link-once functions that were removed.
00727             In these cases, the function address will be NULL, but if
00728             the encoding is smaller than a pointer a true NULL may not
00729             be representable.  Assume 0 in the representable bits is NULL.  */
00730          mask = size_of_encoded_value (encoding);
00731          if (mask < sizeof (void *))
00732            mask = (1L << (mask << 3)) - 1;
00733          else
00734            mask = -1;
00735 
00736          if ((pc_begin & mask) == 0)
00737            continue;
00738        }
00739 
00740       fde_insert (accu, this_fde);
00741     }
00742 }
00743 
00744 /* Set up a sorted array of pointers to FDEs for a loaded object.  We
00745    count up the entries before allocating the array because it's likely to
00746    be faster.  We can be called multiple times, should we have failed to
00747    allocate a sorted fde array on a previous occasion.  */
00748 
00749 static void
00750 init_object (struct object* ob)
00751 {
00752   struct fde_accumulator accu;
00753   size_t count;
00754 
00755   count = ob->s.b.count;
00756   if (count == 0)
00757     {
00758       if (ob->s.b.from_array)
00759        {
00760          fde **p = ob->u.array;
00761          for (count = 0; *p; ++p)
00762            count += classify_object_over_fdes (ob, *p);
00763        }
00764       else
00765        count = classify_object_over_fdes (ob, ob->u.single);
00766 
00767       /* The count field we have in the main struct object is somewhat
00768         limited, but should suffice for virtually all cases.  If the
00769         counted value doesn't fit, re-write a zero.  The worst that
00770         happens is that we re-count next time -- admittedly non-trivial
00771         in that this implies some 2M fdes, but at least we function.  */
00772       ob->s.b.count = count;
00773       if (ob->s.b.count != count)
00774        ob->s.b.count = 0;
00775     }
00776 
00777   if (!start_fde_sort (&accu, count))
00778     return;
00779 
00780   if (ob->s.b.from_array)
00781     {
00782       fde **p;
00783       for (p = ob->u.array; *p; ++p)
00784        add_fdes (ob, &accu, *p);
00785     }
00786   else
00787     add_fdes (ob, &accu, ob->u.single);
00788 
00789   end_fde_sort (ob, &accu, count);
00790 
00791   /* Save the original fde pointer, since this is the key by which the
00792      DSO will deregister the object.  */
00793   accu.linear->orig_data = ob->u.single;
00794   ob->u.sort = accu.linear;
00795 
00796   ob->s.b.sorted = 1;
00797 }
00798 
00799 /* A linear search through a set of FDEs for the given PC.  This is
00800    used when there was insufficient memory to allocate and sort an
00801    array.  */
00802 
00803 static fde *
00804 linear_search_fdes (struct object *ob, fde *this_fde, void *pc)
00805 {
00806   struct dwarf_cie *last_cie = 0;
00807   int encoding = ob->s.b.encoding;
00808   _Unwind_Ptr base = base_from_object (ob->s.b.encoding, ob);
00809 
00810   for (; ! last_fde (ob, this_fde); this_fde = next_fde (this_fde))
00811     {
00812       struct dwarf_cie *this_cie;
00813       _Unwind_Ptr pc_begin, pc_range;
00814 
00815       /* Skip CIEs.  */
00816       if (this_fde->CIE_delta == 0)
00817        continue;
00818 
00819       if (ob->s.b.mixed_encoding)
00820        {
00821          /* Determine the encoding for this FDE.  Note mixed encoded
00822             objects for later.  */
00823          this_cie = get_cie (this_fde);
00824          if (this_cie != last_cie)
00825            {
00826              last_cie = this_cie;
00827              encoding = get_cie_encoding (this_cie);
00828              base = base_from_object (encoding, ob);
00829            }
00830        }
00831 
00832       if (encoding == DW_EH_PE_absptr)
00833        {
00834          pc_begin = ((_Unwind_Ptr *) this_fde->pc_begin)[0];
00835          pc_range = ((_Unwind_Ptr *) this_fde->pc_begin)[1];
00836          if (pc_begin == 0)
00837            continue;
00838        }
00839       else
00840        {
00841          _Unwind_Ptr mask;
00842          const unsigned char *p;
00843 
00844          p = read_encoded_value_with_base (encoding, base,
00845                                        this_fde->pc_begin, &pc_begin);
00846          read_encoded_value_with_base (encoding & 0x0F, 0, p, &pc_range);
00847 
00848          /* Take care to ignore link-once functions that were removed.
00849             In these cases, the function address will be NULL, but if
00850             the encoding is smaller than a pointer a true NULL may not
00851             be representable.  Assume 0 in the representable bits is NULL.  */
00852          mask = size_of_encoded_value (encoding);
00853          if (mask < sizeof (void *))
00854            mask = (1L << (mask << 3)) - 1;
00855          else
00856            mask = -1;
00857 
00858          if ((pc_begin & mask) == 0)
00859            continue;
00860        }
00861 
00862       if ((_Unwind_Ptr) pc - pc_begin < pc_range)
00863        return this_fde;
00864     }
00865 
00866   return NULL;
00867 }
00868 
00869 /* Binary search for an FDE containing the given PC.  Here are three
00870    implementations of increasing complexity.  */
00871 
00872 static fde *
00873 binary_search_unencoded_fdes (struct object *ob, void *pc)
00874 {
00875   struct fde_vector *vec = ob->u.sort;
00876   size_t lo, hi;
00877 
00878   for (lo = 0, hi = vec->count; lo < hi; )
00879     {
00880       size_t i = (lo + hi) / 2;
00881       fde *f = vec->array[i];
00882       void *pc_begin;
00883       uaddr pc_range;
00884 
00885       pc_begin = ((void **) f->pc_begin)[0];
00886       pc_range = ((uaddr *) f->pc_begin)[1];
00887 
00888       if (pc < pc_begin)
00889        hi = i;
00890       else if (pc >= pc_begin + pc_range)
00891        lo = i + 1;
00892       else
00893        return f;
00894     }
00895 
00896   return NULL;
00897 }
00898 
00899 static fde *
00900 binary_search_single_encoding_fdes (struct object *ob, void *pc)
00901 {
00902   struct fde_vector *vec = ob->u.sort;
00903   int encoding = ob->s.b.encoding;
00904   _Unwind_Ptr base = base_from_object (encoding, ob);
00905   size_t lo, hi;
00906 
00907   for (lo = 0, hi = vec->count; lo < hi; )
00908     {
00909       size_t i = (lo + hi) / 2;
00910       fde *f = vec->array[i];
00911       _Unwind_Ptr pc_begin, pc_range;
00912       const unsigned char *p;
00913 
00914       p = read_encoded_value_with_base (encoding, base, f->pc_begin,
00915                                    &pc_begin);
00916       read_encoded_value_with_base (encoding & 0x0F, 0, p, &pc_range);
00917 
00918       if ((_Unwind_Ptr) pc < pc_begin)
00919        hi = i;
00920       else if ((_Unwind_Ptr) pc >= pc_begin + pc_range)
00921        lo = i + 1;
00922       else
00923        return f;
00924     }
00925 
00926   return NULL;
00927 }
00928 
00929 static fde *
00930 binary_search_mixed_encoding_fdes (struct object *ob, void *pc)
00931 {
00932   struct fde_vector *vec = ob->u.sort;
00933   size_t lo, hi;
00934 
00935   for (lo = 0, hi = vec->count; lo < hi; )
00936     {
00937       size_t i = (lo + hi) / 2;
00938       fde *f = vec->array[i];
00939       _Unwind_Ptr pc_begin, pc_range;
00940       const unsigned char *p;
00941       int encoding;
00942 
00943       encoding = get_fde_encoding (f);
00944       p = read_encoded_value_with_base (encoding,
00945                                    base_from_object (encoding, ob),
00946                                    f->pc_begin, &pc_begin);
00947       read_encoded_value_with_base (encoding & 0x0F, 0, p, &pc_range);
00948 
00949       if ((_Unwind_Ptr) pc < pc_begin)
00950        hi = i;
00951       else if ((_Unwind_Ptr) pc >= pc_begin + pc_range)
00952        lo = i + 1;
00953       else
00954        return f;
00955     }
00956 
00957   return NULL;
00958 }
00959 
00960 static fde *
00961 search_object (struct object* ob, void *pc)
00962 {
00963   /* If the data hasn't been sorted, try to do this now.  We may have
00964      more memory available than last time we tried.  */
00965   if (! ob->s.b.sorted)
00966     {
00967       init_object (ob);
00968 
00969       /* Despite the above comment, the normal reason to get here is
00970         that we've not processed this object before.  A quick range
00971         check is in order.  */
00972       if (pc < ob->pc_begin)
00973        return NULL;
00974     }
00975 
00976   if (ob->s.b.sorted)
00977     {
00978       if (ob->s.b.mixed_encoding)
00979        return binary_search_mixed_encoding_fdes (ob, pc);
00980       else if (ob->s.b.encoding == DW_EH_PE_absptr)
00981        return binary_search_unencoded_fdes (ob, pc);
00982       else
00983        return binary_search_single_encoding_fdes (ob, pc);
00984     }
00985   else
00986     {
00987       /* Long slow labourious linear search, cos we've no memory.  */
00988       if (ob->s.b.from_array)
00989        {
00990          fde **p;
00991          for (p = ob->u.array; *p ; p++)
00992            {
00993              fde *f = linear_search_fdes (ob, *p, pc);
00994              if (f)
00995               return f;
00996            }
00997          return NULL;
00998        }
00999       else
01000        return linear_search_fdes (ob, ob->u.single, pc);
01001     }
01002 }
01003 
01004 fde *
01005 _Unwind_Find_FDE (void *pc, struct dwarf_eh_bases *bases)
01006 {
01007   struct object *ob;
01008   fde *f = NULL;
01009 
01010   init_object_mutex_once ();
01011   __gthread_mutex_lock (&object_mutex);
01012 
01013   /* Linear search through the classified objects, to find the one
01014      containing the pc.  Note that pc_begin is sorted descending, and
01015      we expect objects to be non-overlapping.  */
01016   for (ob = seen_objects; ob; ob = ob->next)
01017     if (pc >= ob->pc_begin)
01018       {
01019        f = search_object (ob, pc);
01020        if (f)
01021          goto fini;
01022        break;
01023       }
01024 
01025   /* Classify and search the objects we've not yet processed.  */
01026   while ((ob = unseen_objects))
01027     {
01028       struct object **p;
01029 
01030       unseen_objects = ob->next;
01031       f = search_object (ob, pc);
01032 
01033       /* Insert the object into the classified list.  */
01034       for (p = &seen_objects; *p ; p = &(*p)->next)
01035        if ((*p)->pc_begin < ob->pc_begin)
01036          break;
01037       ob->next = *p;
01038       *p = ob;
01039 
01040       if (f)
01041        goto fini;
01042     }
01043 
01044  fini:
01045   __gthread_mutex_unlock (&object_mutex);
01046 
01047   if (f)
01048     {
01049       int encoding;
01050       _Unwind_Ptr func;
01051 
01052       bases->tbase = ob->tbase;
01053       bases->dbase = ob->dbase;
01054 
01055       encoding = ob->s.b.encoding;
01056       if (ob->s.b.mixed_encoding)
01057        encoding = get_fde_encoding (f);
01058       read_encoded_value_with_base (encoding, base_from_object (encoding, ob),
01059                                 f->pc_begin, &func);
01060       bases->func = (void *) func;
01061     }
01062 
01063   return f;
01064 }
01065 
01066 #endif