#ifndef _Unwind_Find_FDE
#include "tconfig.h"
#include "tsystem.h"
#include "coretypes.h"
#include "tm.h"
#include "dwarf2.h"
#include "unwind.h"
#define NO_BASE_OF_ENCODED_VALUE
#include "unwind-pe.h"
#include "unwind-dw2-fde.h"
#include "gthr.h"
#endif
static struct object *unseen_objects;
static struct object *seen_objects;
#ifdef __GTHREAD_MUTEX_INIT
static __gthread_mutex_t object_mutex = __GTHREAD_MUTEX_INIT;
#else
static __gthread_mutex_t object_mutex;
#endif
#ifdef __GTHREAD_MUTEX_INIT_FUNCTION
static void
init_object_mutex (void)
{
__GTHREAD_MUTEX_INIT_FUNCTION (&object_mutex);
}
static void
init_object_mutex_once (void)
{
static __gthread_once_t once = __GTHREAD_ONCE_INIT;
__gthread_once (&once, init_object_mutex);
}
#else
#define init_object_mutex_once()
#endif
void
__register_frame_info_bases (const void *begin, struct object *ob,
void *tbase, void *dbase)
{
if ((uword *) begin == 0 || *(uword *) begin == 0)
return;
ob->pc_begin = (void *)-1;
ob->tbase = tbase;
ob->dbase = dbase;
ob->u.single = begin;
ob->s.i = 0;
ob->s.b.encoding = DW_EH_PE_omit;
#ifdef DWARF2_OBJECT_END_PTR_EXTENSION
ob->fde_end = NULL;
#endif
init_object_mutex_once ();
__gthread_mutex_lock (&object_mutex);
ob->next = unseen_objects;
unseen_objects = ob;
__gthread_mutex_unlock (&object_mutex);
}
void
__register_frame_info (const void *begin, struct object *ob)
{
__register_frame_info_bases (begin, ob, 0, 0);
}
void
__register_frame (void *begin)
{
struct object *ob;
if (*(uword *) begin == 0)
return;
ob = malloc (sizeof (struct object));
__register_frame_info (begin, ob);
}
void
__register_frame_info_table_bases (void *begin, struct object *ob,
void *tbase, void *dbase)
{
ob->pc_begin = (void *)-1;
ob->tbase = tbase;
ob->dbase = dbase;
ob->u.array = begin;
ob->s.i = 0;
ob->s.b.from_array = 1;
ob->s.b.encoding = DW_EH_PE_omit;
init_object_mutex_once ();
__gthread_mutex_lock (&object_mutex);
ob->next = unseen_objects;
unseen_objects = ob;
__gthread_mutex_unlock (&object_mutex);
}
void
__register_frame_info_table (void *begin, struct object *ob)
{
__register_frame_info_table_bases (begin, ob, 0, 0);
}
void
__register_frame_table (void *begin)
{
struct object *ob = malloc (sizeof (struct object));
__register_frame_info_table (begin, ob);
}
void *
__deregister_frame_info_bases (const void *begin)
{
struct object **p;
struct object *ob = 0;
if ((uword *) begin == 0 || *(uword *) begin == 0)
return ob;
init_object_mutex_once ();
__gthread_mutex_lock (&object_mutex);
for (p = &unseen_objects; *p ; p = &(*p)->next)
if ((*p)->u.single == begin)
{
ob = *p;
*p = ob->next;
goto out;
}
for (p = &seen_objects; *p ; p = &(*p)->next)
if ((*p)->s.b.sorted)
{
if ((*p)->u.sort->orig_data == begin)
{
ob = *p;
*p = ob->next;
free (ob->u.sort);
goto out;
}
}
else
{
if ((*p)->u.single == begin)
{
ob = *p;
*p = ob->next;
goto out;
}
}
out:
__gthread_mutex_unlock (&object_mutex);
gcc_assert (ob);
return (void *) ob;
}
void *
__deregister_frame_info (const void *begin)
{
return __deregister_frame_info_bases (begin);
}
void
__deregister_frame (void *begin)
{
if (*(uword *) begin != 0)
free (__deregister_frame_info (begin));
}
static _Unwind_Ptr
base_from_object (unsigned char encoding, struct object *ob)
{
if (encoding == DW_EH_PE_omit)
return 0;
switch (encoding & 0x70)
{
case DW_EH_PE_absptr:
case DW_EH_PE_pcrel:
case DW_EH_PE_aligned:
return 0;
case DW_EH_PE_textrel:
return (_Unwind_Ptr) ob->tbase;
case DW_EH_PE_datarel:
return (_Unwind_Ptr) ob->dbase;
default:
gcc_unreachable ();
}
}
static int
get_cie_encoding (const struct dwarf_cie *cie)
{
const unsigned char *aug, *p;
_Unwind_Ptr dummy;
_Unwind_Word utmp;
_Unwind_Sword stmp;
aug = cie->augmentation;
if (aug[0] != 'z')
return DW_EH_PE_absptr;
p = aug + strlen ((const char *)aug) + 1;
p = read_uleb128 (p, &utmp);
p = read_sleb128 (p, &stmp);
if (cie->version == 1)
p++;
else
p = read_uleb128 (p, &utmp);
aug++;
p = read_uleb128 (p, &utmp);
while (1)
{
if (*aug == 'R')
return *p;
else if (*aug == 'P')
{
p = read_encoded_value_with_base (*p & 0x7F, 0, p + 1, &dummy);
}
else if (*aug == 'L')
p++;
else
return DW_EH_PE_absptr;
aug++;
}
}
static inline int
get_fde_encoding (const struct dwarf_fde *f)
{
return get_cie_encoding (get_cie (f));
}
static int
fde_unencoded_compare (struct object *ob __attribute__((unused)),
const fde *x, const fde *y)
{
_Unwind_Ptr x_ptr = *(_Unwind_Ptr *) x->pc_begin;
_Unwind_Ptr y_ptr = *(_Unwind_Ptr *) y->pc_begin;
if (x_ptr > y_ptr)
return 1;
if (x_ptr < y_ptr)
return -1;
return 0;
}
static int
fde_single_encoding_compare (struct object *ob, const fde *x, const fde *y)
{
_Unwind_Ptr base, x_ptr, y_ptr;
base = base_from_object (ob->s.b.encoding, ob);
read_encoded_value_with_base (ob->s.b.encoding, base, x->pc_begin, &x_ptr);
read_encoded_value_with_base (ob->s.b.encoding, base, y->pc_begin, &y_ptr);
if (x_ptr > y_ptr)
return 1;
if (x_ptr < y_ptr)
return -1;
return 0;
}
static int
fde_mixed_encoding_compare (struct object *ob, const fde *x, const fde *y)
{
int x_encoding, y_encoding;
_Unwind_Ptr x_ptr, y_ptr;
x_encoding = get_fde_encoding (x);
read_encoded_value_with_base (x_encoding, base_from_object (x_encoding, ob),
x->pc_begin, &x_ptr);
y_encoding = get_fde_encoding (y);
read_encoded_value_with_base (y_encoding, base_from_object (y_encoding, ob),
y->pc_begin, &y_ptr);
if (x_ptr > y_ptr)
return 1;
if (x_ptr < y_ptr)
return -1;
return 0;
}
typedef int (*fde_compare_t) (struct object *, const fde *, const fde *);
struct fde_accumulator
{
struct fde_vector *linear;
struct fde_vector *erratic;
};
static inline int
start_fde_sort (struct fde_accumulator *accu, size_t count)
{
size_t size;
if (! count)
return 0;
size = sizeof (struct fde_vector) + sizeof (const fde *) * count;
if ((accu->linear = malloc (size)))
{
accu->linear->count = 0;
if ((accu->erratic = malloc (size)))
accu->erratic->count = 0;
return 1;
}
else
return 0;
}
static inline void
fde_insert (struct fde_accumulator *accu, const fde *this_fde)
{
if (accu->linear)
accu->linear->array[accu->linear->count++] = this_fde;
}
static inline void
fde_split (struct object *ob, fde_compare_t fde_compare,
struct fde_vector *linear, struct fde_vector *erratic)
{
static const fde *marker;
size_t count = linear->count;
const fde **chain_end = ▮
size_t i, j, k;
gcc_assert (sizeof (const fde *) == sizeof (const fde **));
for (i = 0; i < count; i++)
{
const fde **probe;
for (probe = chain_end;
probe != &marker && fde_compare (ob, linear->array[i], *probe) < 0;
probe = chain_end)
{
chain_end = (const fde **) erratic->array[probe - linear->array];
erratic->array[probe - linear->array] = NULL;
}
erratic->array[i] = (const fde *) chain_end;
chain_end = &linear->array[i];
}
for (i = j = k = 0; i < count; i++)
if (erratic->array[i])
linear->array[j++] = linear->array[i];
else
erratic->array[k++] = linear->array[i];
linear->count = j;
erratic->count = k;
}
#define SWAP(x,y) do { const fde * tmp = x; x = y; y = tmp; } while (0)
static void
frame_downheap (struct object *ob, fde_compare_t fde_compare, const fde **a,
int lo, int hi)
{
int i, j;
for (i = lo, j = 2*i+1;
j < hi;
j = 2*i+1)
{
if (j+1 < hi && fde_compare (ob, a[j], a[j+1]) < 0)
++j;
if (fde_compare (ob, a[i], a[j]) < 0)
{
SWAP (a[i], a[j]);
i = j;
}
else
break;
}
}
static void
frame_heapsort (struct object *ob, fde_compare_t fde_compare,
struct fde_vector *erratic)
{
const fde ** a = erratic->array;
size_t n = erratic->count;
int m;
for (m = n/2-1; m >= 0; --m)
frame_downheap (ob, fde_compare, a, m, n);
for (m = n-1; m >= 1; --m)
{
SWAP (a[0], a[m]);
frame_downheap (ob, fde_compare, a, 0, m);
}
#undef SWAP
}
static inline void
fde_merge (struct object *ob, fde_compare_t fde_compare,
struct fde_vector *v1, struct fde_vector *v2)
{
size_t i1, i2;
const fde * fde2;
i2 = v2->count;
if (i2 > 0)
{
i1 = v1->count;
do
{
i2--;
fde2 = v2->array[i2];
while (i1 > 0 && fde_compare (ob, v1->array[i1-1], fde2) > 0)
{
v1->array[i1+i2] = v1->array[i1-1];
i1--;
}
v1->array[i1+i2] = fde2;
}
while (i2 > 0);
v1->count += v2->count;
}
}
static inline void
end_fde_sort (struct object *ob, struct fde_accumulator *accu, size_t count)
{
fde_compare_t fde_compare;
gcc_assert (!accu->linear || accu->linear->count == count);
if (ob->s.b.mixed_encoding)
fde_compare = fde_mixed_encoding_compare;
else if (ob->s.b.encoding == DW_EH_PE_absptr)
fde_compare = fde_unencoded_compare;
else
fde_compare = fde_single_encoding_compare;
if (accu->erratic)
{
fde_split (ob, fde_compare, accu->linear, accu->erratic);
gcc_assert (accu->linear->count + accu->erratic->count == count);
frame_heapsort (ob, fde_compare, accu->erratic);
fde_merge (ob, fde_compare, accu->linear, accu->erratic);
free (accu->erratic);
}
else
{
frame_heapsort (ob, fde_compare, accu->linear);
}
}
static size_t
classify_object_over_fdes (struct object *ob, const fde *this_fde)
{
const struct dwarf_cie *last_cie = 0;
size_t count = 0;
int encoding = DW_EH_PE_absptr;
_Unwind_Ptr base = 0;
for (; ! last_fde (ob, this_fde); this_fde = next_fde (this_fde))
{
const struct dwarf_cie *this_cie;
_Unwind_Ptr mask, pc_begin;
if (this_fde->CIE_delta == 0)
continue;
this_cie = get_cie (this_fde);
if (this_cie != last_cie)
{
last_cie = this_cie;
encoding = get_cie_encoding (this_cie);
base = base_from_object (encoding, ob);
if (ob->s.b.encoding == DW_EH_PE_omit)
ob->s.b.encoding = encoding;
else if (ob->s.b.encoding != encoding)
ob->s.b.mixed_encoding = 1;
}
read_encoded_value_with_base (encoding, base, this_fde->pc_begin,
&pc_begin);
mask = size_of_encoded_value (encoding);
if (mask < sizeof (void *))
mask = (1L << (mask << 3)) - 1;
else
mask = -1;
if ((pc_begin & mask) == 0)
continue;
count += 1;
if ((void *) pc_begin < ob->pc_begin)
ob->pc_begin = (void *) pc_begin;
}
return count;
}
static void
add_fdes (struct object *ob, struct fde_accumulator *accu, const fde *this_fde)
{
const struct dwarf_cie *last_cie = 0;
int encoding = ob->s.b.encoding;
_Unwind_Ptr base = base_from_object (ob->s.b.encoding, ob);
for (; ! last_fde (ob, this_fde); this_fde = next_fde (this_fde))
{
const struct dwarf_cie *this_cie;
if (this_fde->CIE_delta == 0)
continue;
if (ob->s.b.mixed_encoding)
{
this_cie = get_cie (this_fde);
if (this_cie != last_cie)
{
last_cie = this_cie;
encoding = get_cie_encoding (this_cie);
base = base_from_object (encoding, ob);
}
}
if (encoding == DW_EH_PE_absptr)
{
if (*(_Unwind_Ptr *) this_fde->pc_begin == 0)
continue;
}
else
{
_Unwind_Ptr pc_begin, mask;
read_encoded_value_with_base (encoding, base, this_fde->pc_begin,
&pc_begin);
mask = size_of_encoded_value (encoding);
if (mask < sizeof (void *))
mask = (1L << (mask << 3)) - 1;
else
mask = -1;
if ((pc_begin & mask) == 0)
continue;
}
fde_insert (accu, this_fde);
}
}
static inline void
init_object (struct object* ob)
{
struct fde_accumulator accu;
size_t count;
count = ob->s.b.count;
if (count == 0)
{
if (ob->s.b.from_array)
{
fde **p = ob->u.array;
for (count = 0; *p; ++p)
count += classify_object_over_fdes (ob, *p);
}
else
count = classify_object_over_fdes (ob, ob->u.single);
ob->s.b.count = count;
if (ob->s.b.count != count)
ob->s.b.count = 0;
}
if (!start_fde_sort (&accu, count))
return;
if (ob->s.b.from_array)
{
fde **p;
for (p = ob->u.array; *p; ++p)
add_fdes (ob, &accu, *p);
}
else
add_fdes (ob, &accu, ob->u.single);
end_fde_sort (ob, &accu, count);
accu.linear->orig_data = ob->u.single;
ob->u.sort = accu.linear;
ob->s.b.sorted = 1;
}
static const fde *
linear_search_fdes (struct object *ob, const fde *this_fde, void *pc)
{
const struct dwarf_cie *last_cie = 0;
int encoding = ob->s.b.encoding;
_Unwind_Ptr base = base_from_object (ob->s.b.encoding, ob);
for (; ! last_fde (ob, this_fde); this_fde = next_fde (this_fde))
{
const struct dwarf_cie *this_cie;
_Unwind_Ptr pc_begin, pc_range;
if (this_fde->CIE_delta == 0)
continue;
if (ob->s.b.mixed_encoding)
{
this_cie = get_cie (this_fde);
if (this_cie != last_cie)
{
last_cie = this_cie;
encoding = get_cie_encoding (this_cie);
base = base_from_object (encoding, ob);
}
}
if (encoding == DW_EH_PE_absptr)
{
pc_begin = ((_Unwind_Ptr *) this_fde->pc_begin)[0];
pc_range = ((_Unwind_Ptr *) this_fde->pc_begin)[1];
if (pc_begin == 0)
continue;
}
else
{
_Unwind_Ptr mask;
const unsigned char *p;
p = read_encoded_value_with_base (encoding, base,
this_fde->pc_begin, &pc_begin);
read_encoded_value_with_base (encoding & 0x0F, 0, p, &pc_range);
mask = size_of_encoded_value (encoding);
if (mask < sizeof (void *))
mask = (1L << (mask << 3)) - 1;
else
mask = -1;
if ((pc_begin & mask) == 0)
continue;
}
if ((_Unwind_Ptr) pc - pc_begin < pc_range)
return this_fde;
}
return NULL;
}
static inline const fde *
binary_search_unencoded_fdes (struct object *ob, void *pc)
{
struct fde_vector *vec = ob->u.sort;
size_t lo, hi;
for (lo = 0, hi = vec->count; lo < hi; )
{
size_t i = (lo + hi) / 2;
const fde *f = vec->array[i];
void *pc_begin;
uaddr pc_range;
pc_begin = ((void **) f->pc_begin)[0];
pc_range = ((uaddr *) f->pc_begin)[1];
if (pc < pc_begin)
hi = i;
else if (pc >= pc_begin + pc_range)
lo = i + 1;
else
return f;
}
return NULL;
}
static inline const fde *
binary_search_single_encoding_fdes (struct object *ob, void *pc)
{
struct fde_vector *vec = ob->u.sort;
int encoding = ob->s.b.encoding;
_Unwind_Ptr base = base_from_object (encoding, ob);
size_t lo, hi;
for (lo = 0, hi = vec->count; lo < hi; )
{
size_t i = (lo + hi) / 2;
const fde *f = vec->array[i];
_Unwind_Ptr pc_begin, pc_range;
const unsigned char *p;
p = read_encoded_value_with_base (encoding, base, f->pc_begin,
&pc_begin);
read_encoded_value_with_base (encoding & 0x0F, 0, p, &pc_range);
if ((_Unwind_Ptr) pc < pc_begin)
hi = i;
else if ((_Unwind_Ptr) pc >= pc_begin + pc_range)
lo = i + 1;
else
return f;
}
return NULL;
}
static inline const fde *
binary_search_mixed_encoding_fdes (struct object *ob, void *pc)
{
struct fde_vector *vec = ob->u.sort;
size_t lo, hi;
for (lo = 0, hi = vec->count; lo < hi; )
{
size_t i = (lo + hi) / 2;
const fde *f = vec->array[i];
_Unwind_Ptr pc_begin, pc_range;
const unsigned char *p;
int encoding;
encoding = get_fde_encoding (f);
p = read_encoded_value_with_base (encoding,
base_from_object (encoding, ob),
f->pc_begin, &pc_begin);
read_encoded_value_with_base (encoding & 0x0F, 0, p, &pc_range);
if ((_Unwind_Ptr) pc < pc_begin)
hi = i;
else if ((_Unwind_Ptr) pc >= pc_begin + pc_range)
lo = i + 1;
else
return f;
}
return NULL;
}
static const fde *
search_object (struct object* ob, void *pc)
{
if (! ob->s.b.sorted)
{
init_object (ob);
if (pc < ob->pc_begin)
return NULL;
}
if (ob->s.b.sorted)
{
if (ob->s.b.mixed_encoding)
return binary_search_mixed_encoding_fdes (ob, pc);
else if (ob->s.b.encoding == DW_EH_PE_absptr)
return binary_search_unencoded_fdes (ob, pc);
else
return binary_search_single_encoding_fdes (ob, pc);
}
else
{
if (ob->s.b.from_array)
{
fde **p;
for (p = ob->u.array; *p ; p++)
{
const fde *f = linear_search_fdes (ob, *p, pc);
if (f)
return f;
}
return NULL;
}
else
return linear_search_fdes (ob, ob->u.single, pc);
}
}
const fde *
_Unwind_Find_FDE (void *pc, struct dwarf_eh_bases *bases)
{
struct object *ob;
const fde *f = NULL;
init_object_mutex_once ();
__gthread_mutex_lock (&object_mutex);
for (ob = seen_objects; ob; ob = ob->next)
if (pc >= ob->pc_begin)
{
f = search_object (ob, pc);
if (f)
goto fini;
break;
}
while ((ob = unseen_objects))
{
struct object **p;
unseen_objects = ob->next;
f = search_object (ob, pc);
for (p = &seen_objects; *p ; p = &(*p)->next)
if ((*p)->pc_begin < ob->pc_begin)
break;
ob->next = *p;
*p = ob;
if (f)
goto fini;
}
fini:
__gthread_mutex_unlock (&object_mutex);
if (f)
{
int encoding;
_Unwind_Ptr func;
bases->tbase = ob->tbase;
bases->dbase = ob->dbase;
encoding = ob->s.b.encoding;
if (ob->s.b.mixed_encoding)
encoding = get_fde_encoding (f);
read_encoded_value_with_base (encoding, base_from_object (encoding, ob),
f->pc_begin, &func);
bases->func = (void *) func;
}
return f;
}