diff options
Diffstat (limited to 'gcc/unwind-dw2-fde.c')
| -rw-r--r-- | gcc/unwind-dw2-fde.c | 542 |
1 files changed, 542 insertions, 0 deletions
diff --git a/gcc/unwind-dw2-fde.c b/gcc/unwind-dw2-fde.c new file mode 100644 index 0000000..6f450c5 --- /dev/null +++ b/gcc/unwind-dw2-fde.c @@ -0,0 +1,542 @@ +/* Subroutines needed for unwinding stack frames for exception handling. */ +/* Copyright (C) 1997, 1998, 1999, 2000, 2001 Free Software Foundation, Inc. + Contributed by Jason Merrill <jason@cygnus.com>. + +This file is part of GNU CC. + +GNU CC is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +In addition to the permissions in the GNU General Public License, the +Free Software Foundation gives you unlimited permission to link the +compiled version of this file into combinations with other programs, +and to distribute those combinations without any restriction coming +from the use of this file. (The General Public License restrictions +do apply in other respects; for example, they cover modification of +the file, and distribution when not linked into a combine +executable.) + +GNU CC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU CC; see the file COPYING. If not, write to +the Free Software Foundation, 59 Temple Place - Suite 330, +Boston, MA 02111-1307, USA. */ + +#include "tconfig.h" +#include "tsystem.h" +#include "unwind-dw2-fde.h" +#include "gthr.h" + +static struct object *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 + +/* Called from crtbegin.o to register the unwind info for an object. */ + +void +__register_frame_info (void *begin, struct object *ob) +{ + ob->pc_begin = ob->pc_end = 0; + ob->fde_begin = begin; + ob->fde_array = 0; + ob->count = 0; + + init_object_mutex_once (); + __gthread_mutex_lock (&object_mutex); + + ob->next = objects; + objects = ob; + + __gthread_mutex_unlock (&object_mutex); +} + +void +__register_frame (void *begin) +{ + struct object *ob = (struct object *) malloc (sizeof (struct object)); + __register_frame_info (begin, ob); +} + +/* Similar, but BEGIN is actually a pointer to a table of unwind entries + for different translation units. Called from the file generated by + collect2. */ + +void +__register_frame_info_table (void *begin, struct object *ob) +{ + ob->pc_begin = ob->pc_end = 0; + ob->fde_begin = begin; + ob->fde_array = begin; + ob->count = 0; + + init_object_mutex_once (); + __gthread_mutex_lock (&object_mutex); + + ob->next = objects; + objects = ob; + + __gthread_mutex_unlock (&object_mutex); +} + +void +__register_frame_table (void *begin) +{ + struct object *ob = (struct object *) malloc (sizeof (struct object)); + __register_frame_info_table (begin, ob); +} + +/* Called from crtbegin.o to deregister the unwind info for an object. */ + +void * +__deregister_frame_info (void *begin) +{ + struct object **p; + + init_object_mutex_once (); + __gthread_mutex_lock (&object_mutex); + + p = &objects; + while (*p) + { + if ((*p)->fde_begin == begin) + { + struct object *ob = *p; + *p = (*p)->next; + + /* If we've run init_frame for this object, free the FDE array. */ + if (ob->fde_array && ob->fde_array != begin) + free (ob->fde_array); + + __gthread_mutex_unlock (&object_mutex); + return (void *) ob; + } + p = &((*p)->next); + } + + __gthread_mutex_unlock (&object_mutex); + abort (); +} + +void +__deregister_frame (void *begin) +{ + free (__deregister_frame_info (begin)); +} + + +/* Sorting an array of FDEs by address. + (Ideally we would have the linker sort the FDEs so we don't have to do + it at run time. But the linkers are not yet prepared for this.) */ + +/* This is a special mix of insertion sort and heap sort, optimized for + the data sets that actually occur. They look like + 101 102 103 127 128 105 108 110 190 111 115 119 125 160 126 129 130. + I.e. a linearly increasing sequence (coming from functions in the text + section), with additionally a few unordered elements (coming from functions + in gnu_linkonce sections) whose values are higher than the values in the + surrounding linear sequence (but not necessarily higher than the values + at the end of the linear sequence!). + The worst-case total run time is O(N) + O(n log (n)), where N is the + total number of FDEs and n is the number of erratic ones. */ + +typedef struct fde_vector +{ + fde **array; + size_t count; +} fde_vector; + +typedef struct fde_accumulator +{ + fde_vector linear; + fde_vector erratic; +} fde_accumulator; + +static inline saddr +fde_compare (fde *x, fde *y) +{ + return (saddr)x->pc_begin - (saddr)y->pc_begin; +} + +static inline int +start_fde_sort (fde_accumulator *accu, size_t count) +{ + accu->linear.array = count ? (fde **) malloc (sizeof (fde *) * count) : NULL; + accu->erratic.array = accu->linear.array ? + (fde **) malloc (sizeof (fde *) * count) : NULL; + accu->linear.count = 0; + accu->erratic.count = 0; + + return accu->linear.array != NULL; +} + +static inline void +fde_insert (fde_accumulator *accu, fde *this_fde) +{ + if (accu->linear.array) + accu->linear.array[accu->linear.count++] = this_fde; +} + +/* Split LINEAR into a linear sequence with low values and an erratic + sequence with high values, put the linear one (of longest possible + length) into LINEAR and the erratic one into ERRATIC. This is O(N). + + Because the longest linear sequence we are trying to locate within the + incoming LINEAR array can be interspersed with (high valued) erratic + entries. We construct a chain indicating the sequenced entries. + To avoid having to allocate this chain, we overlay it onto the space of + the ERRATIC array during construction. A final pass iterates over the + chain to determine what should be placed in the ERRATIC array, and + what is the linear sequence. This overlay is safe from aliasing. */ +static inline void +fde_split (fde_vector *linear, fde_vector *erratic) +{ + static fde *marker; + size_t count = linear->count; + fde **chain_end = ▮ + size_t i, j, k; + + /* This should optimize out, but it is wise to make sure this assumption + is correct. Should these have different sizes, we cannot cast between + them and the overlaying onto ERRATIC will not work. */ + if (sizeof (fde *) != sizeof (fde **)) + abort (); + + for (i = 0; i < count; i++) + { + fde **probe; + + for (probe = chain_end; + probe != &marker && fde_compare (linear->array[i], *probe) < 0; + probe = chain_end) + { + chain_end = (fde **)erratic->array[probe - linear->array]; + erratic->array[probe - linear->array] = NULL; + } + erratic->array[i] = (fde *)chain_end; + chain_end = &linear->array[i]; + } + + /* Each entry in LINEAR which is part of the linear sequence we have + discovered will correspond to a non-NULL entry in the chain we built in + the ERRATIC array. */ + 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; +} + +/* This is O(n log(n)). BSD/OS defines heapsort in stdlib.h, so we must + use a name that does not conflict. */ +static inline void +frame_heapsort (fde_vector *erratic) +{ + /* For a description of this algorithm, see: + Samuel P. Harbison, Guy L. Steele Jr.: C, a reference manual, 2nd ed., + p. 60-61. */ + fde ** a = erratic->array; + /* A portion of the array is called a "heap" if for all i>=0: + If i and 2i+1 are valid indices, then a[i] >= a[2i+1]. + If i and 2i+2 are valid indices, then a[i] >= a[2i+2]. */ +#define SWAP(x,y) do { fde * tmp = x; x = y; y = tmp; } while (0) + size_t n = erratic->count; + size_t m = n; + size_t i; + + while (m > 0) + { + /* Invariant: a[m..n-1] is a heap. */ + m--; + for (i = m; 2*i+1 < n; ) + { + if (2*i+2 < n + && fde_compare (a[2*i+2], a[2*i+1]) > 0 + && fde_compare (a[2*i+2], a[i]) > 0) + { + SWAP (a[i], a[2*i+2]); + i = 2*i+2; + } + else if (fde_compare (a[2*i+1], a[i]) > 0) + { + SWAP (a[i], a[2*i+1]); + i = 2*i+1; + } + else + break; + } + } + while (n > 1) + { + /* Invariant: a[0..n-1] is a heap. */ + n--; + SWAP (a[0], a[n]); + for (i = 0; 2*i+1 < n; ) + { + if (2*i+2 < n + && fde_compare (a[2*i+2], a[2*i+1]) > 0 + && fde_compare (a[2*i+2], a[i]) > 0) + { + SWAP (a[i], a[2*i+2]); + i = 2*i+2; + } + else if (fde_compare (a[2*i+1], a[i]) > 0) + { + SWAP (a[i], a[2*i+1]); + i = 2*i+1; + } + else + break; + } + } +#undef SWAP +} + +/* Merge V1 and V2, both sorted, and put the result into V1. */ +static void +fde_merge (fde_vector *v1, const fde_vector *v2) +{ + size_t i1, i2; + fde * fde2; + + i2 = v2->count; + if (i2 > 0) + { + i1 = v1->count; + do { + i2--; + fde2 = v2->array[i2]; + while (i1 > 0 && fde_compare (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 fde ** +end_fde_sort (fde_accumulator *accu, size_t count) +{ + if (accu->linear.array && accu->linear.count != count) + abort (); + + if (accu->erratic.array) + { + fde_split (&accu->linear, &accu->erratic); + if (accu->linear.count + accu->erratic.count != count) + abort (); + frame_heapsort (&accu->erratic); + fde_merge (&accu->linear, &accu->erratic); + free (accu->erratic.array); + } + else + { + /* We've not managed to malloc an erratic array, so heap sort in the + linear one. */ + frame_heapsort (&accu->linear); + } + return accu->linear.array; +} + + +static size_t +count_fdes (fde *this_fde) +{ + size_t count; + + for (count = 0; this_fde->length != 0; this_fde = next_fde (this_fde)) + /* Skip CIEs and omitted link-once FDE entries. */ + if (this_fde->CIE_delta != 0 && this_fde->pc_begin != 0) + ++count; + + return count; +} + +static void +add_fdes (fde *this_fde, fde_accumulator *accu, void **beg_ptr, void **end_ptr) +{ + void *pc_begin = *beg_ptr; + void *pc_end = *end_ptr; + + for (; this_fde->length != 0; this_fde = next_fde (this_fde)) + { + /* Skip CIEs and linked once FDE entries. */ + if (this_fde->CIE_delta == 0 || this_fde->pc_begin == 0) + continue; + + fde_insert (accu, this_fde); + + if (this_fde->pc_begin < pc_begin) + pc_begin = this_fde->pc_begin; + if (this_fde->pc_begin + this_fde->pc_range > pc_end) + pc_end = this_fde->pc_begin + this_fde->pc_range; + } + + *beg_ptr = pc_begin; + *end_ptr = pc_end; +} + +static fde * +search_fdes (fde *this_fde, void *pc) +{ + for (; this_fde->length != 0; this_fde = next_fde (this_fde)) + { + /* Skip CIEs and linked once FDE entries. */ + if (this_fde->CIE_delta == 0 || this_fde->pc_begin == 0) + continue; + + if ((uaddr)((char *)pc - (char *)this_fde->pc_begin) < this_fde->pc_range) + return this_fde; + } + return NULL; +} + +/* Set up a sorted array of pointers to FDEs for a loaded object. We + count up the entries before allocating the array because it's likely to + be faster. We can be called multiple times, should we have failed to + allocate a sorted fde array on a previous occasion. */ + +static void +frame_init (struct object* ob) +{ + size_t count; + fde_accumulator accu; + void *pc_begin, *pc_end; + fde **array; + + if (ob->pc_begin) + count = ob->count; + else if (ob->fde_array) + { + fde **p = ob->fde_array; + for (count = 0; *p; ++p) + count += count_fdes (*p); + } + else + count = count_fdes (ob->fde_begin); + ob->count = count; + + if (!start_fde_sort (&accu, count) && ob->pc_begin) + return; + + pc_begin = (void*)(uaddr)-1; + pc_end = 0; + + if (ob->fde_array) + { + fde **p = ob->fde_array; + for (; *p; ++p) + add_fdes (*p, &accu, &pc_begin, &pc_end); + } + else + add_fdes (ob->fde_begin, &accu, &pc_begin, &pc_end); + array = end_fde_sort (&accu, count); + if (array) + ob->fde_array = array; + ob->pc_begin = pc_begin; + ob->pc_end = pc_end; +} + +fde * +_Unwind_Find_FDE (void *pc, struct dwarf_eh_bases *bases) +{ + struct object *ob; + size_t lo, hi; + + init_object_mutex_once (); + __gthread_mutex_lock (&object_mutex); + + /* Linear search through the objects, to find the one containing the pc. */ + for (ob = objects; ob; ob = ob->next) + { + if (ob->pc_begin == 0) + frame_init (ob); + if (pc >= ob->pc_begin && pc < ob->pc_end) + break; + } + + if (ob == 0) + { + __gthread_mutex_unlock (&object_mutex); + return 0; + } + + if (!ob->fde_array || (void *)ob->fde_array == (void *)ob->fde_begin) + frame_init (ob); + + if (ob->fde_array && (void *)ob->fde_array != (void *)ob->fde_begin) + { + __gthread_mutex_unlock (&object_mutex); + + /* Standard binary search algorithm. */ + for (lo = 0, hi = ob->count; lo < hi; ) + { + size_t i = (lo + hi) / 2; + fde *f = ob->fde_array[i]; + + if (pc < f->pc_begin) + hi = i; + else if (pc >= f->pc_begin + f->pc_range) + lo = i + 1; + else + return f; + } + } + else + { + /* Long slow labourious linear search, cos we've no memory. */ + fde *f; + + if (ob->fde_array) + { + fde **p = ob->fde_array; + + do + { + f = search_fdes (*p, pc); + if (f) + break; + p++; + } + while (*p); + } + else + f = search_fdes (ob->fde_begin, pc); + + __gthread_mutex_unlock (&object_mutex); + return f; + } + + return 0; +} |