diff options
author | obrien <obrien@FreeBSD.org> | 1999-08-26 09:30:50 +0000 |
---|---|---|
committer | obrien <obrien@FreeBSD.org> | 1999-08-26 09:30:50 +0000 |
commit | 0bedf4fb30066e5e1d4342a1d3914dae7d37cba7 (patch) | |
tree | 68d8110b41afd0ebbf39167b1a4918eea667a7c5 /contrib/gcc/frame.c | |
parent | d4db5fb866b7ad5216abd5047774a3973b9901a9 (diff) | |
download | FreeBSD-src-0bedf4fb30066e5e1d4342a1d3914dae7d37cba7.zip FreeBSD-src-0bedf4fb30066e5e1d4342a1d3914dae7d37cba7.tar.gz |
Virgin import of gcc from EGCS 1.1.2
Diffstat (limited to 'contrib/gcc/frame.c')
-rw-r--r-- | contrib/gcc/frame.c | 815 |
1 files changed, 815 insertions, 0 deletions
diff --git a/contrib/gcc/frame.c b/contrib/gcc/frame.c new file mode 100644 index 0000000..4b62759 --- /dev/null +++ b/contrib/gcc/frame.c @@ -0,0 +1,815 @@ +/* Subroutines needed for unwinding stack frames for exception handling. */ +/* Compile this one with gcc. */ +/* Copyright (C) 1997 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. + +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. */ + +/* As a special exception, if you link this library with other files, + some of which are compiled with GCC, to produce an executable, + this library does not by itself cause the resulting executable + to be covered by the GNU General Public License. + This exception does not however invalidate any other reasons why + the executable file might be covered by the GNU General Public License. */ + +/* It is incorrect to include config.h here, because this file is being + compiled for the target, and hence definitions concerning only the host + do not apply. */ + +#include "tconfig.h" + +/* We disable this when inhibit_libc, so that gcc can still be built without + needing header files first. */ +/* ??? This is not a good solution, since prototypes may be required in + some cases for correct code. See also libgcc2.c. */ +#ifndef inhibit_libc +/* fixproto guarantees these system headers exist. */ +#include <stdlib.h> +#include <unistd.h> +#endif + +#include "defaults.h" + +#ifdef DWARF2_UNWIND_INFO +#include "gansidecl.h" +#include "dwarf2.h" +#include <stddef.h> +#include "frame.h" +#include "gthr.h" + +#ifdef __GTHREAD_MUTEX_INIT +static __gthread_mutex_t object_mutex = __GTHREAD_MUTEX_INIT; +#else +static __gthread_mutex_t object_mutex; +#endif + +/* Don't use `fancy_abort' here even if config.h says to use it. */ +#ifdef abort +#undef abort +#endif + +/* Some types used by the DWARF 2 spec. */ + +typedef int sword __attribute__ ((mode (SI))); +typedef unsigned int uword __attribute__ ((mode (SI))); +typedef unsigned int uaddr __attribute__ ((mode (pointer))); +typedef int saddr __attribute__ ((mode (pointer))); +typedef unsigned char ubyte; + +/* The first few fields of a CIE. The CIE_id field is 0 for a CIE, + to distinguish it from a valid FDE. FDEs are aligned to an addressing + unit boundary, but the fields within are unaligned. */ + +struct dwarf_cie { + uword length; + sword CIE_id; + ubyte version; + char augmentation[0]; +} __attribute__ ((packed, aligned (__alignof__ (void *)))); + +/* The first few fields of an FDE. */ + +struct dwarf_fde { + uword length; + sword CIE_delta; + void* pc_begin; + uaddr pc_range; +} __attribute__ ((packed, aligned (__alignof__ (void *)))); + +typedef struct dwarf_fde fde; + +/* Objects to be searched for frame unwind info. */ + +static struct object *objects; + +/* The information we care about from a CIE. */ + +struct cie_info { + char *augmentation; + void *eh_ptr; + int code_align; + int data_align; + unsigned ra_regno; +}; + +/* The current unwind state, plus a saved copy for DW_CFA_remember_state. */ + +struct frame_state_internal +{ + struct frame_state s; + struct frame_state_internal *saved_state; +}; + +/* Decode the unsigned LEB128 constant at BUF into the variable pointed to + by R, and return the new value of BUF. */ + +static void * +decode_uleb128 (unsigned char *buf, unsigned *r) +{ + unsigned shift = 0; + unsigned result = 0; + + while (1) + { + unsigned byte = *buf++; + result |= (byte & 0x7f) << shift; + if ((byte & 0x80) == 0) + break; + shift += 7; + } + *r = result; + return buf; +} + +/* Decode the signed LEB128 constant at BUF into the variable pointed to + by R, and return the new value of BUF. */ + +static void * +decode_sleb128 (unsigned char *buf, int *r) +{ + unsigned shift = 0; + unsigned result = 0; + unsigned byte; + + while (1) + { + byte = *buf++; + result |= (byte & 0x7f) << shift; + shift += 7; + if ((byte & 0x80) == 0) + break; + } + if (shift < (sizeof (*r) * 8) && (byte & 0x40) != 0) + result |= - (1 << shift); + + *r = result; + return buf; +} + +/* Read unaligned data from the instruction buffer. */ + +union unaligned { + void *p; + unsigned b2 __attribute__ ((mode (HI))); + unsigned b4 __attribute__ ((mode (SI))); + unsigned b8 __attribute__ ((mode (DI))); +} __attribute__ ((packed)); +static inline void * +read_pointer (void *p) +{ union unaligned *up = p; return up->p; } +static inline unsigned +read_1byte (void *p) +{ return *(unsigned char *)p; } +static inline unsigned +read_2byte (void *p) +{ union unaligned *up = p; return up->b2; } +static inline unsigned +read_4byte (void *p) +{ union unaligned *up = p; return up->b4; } +static inline unsigned long +read_8byte (void *p) +{ union unaligned *up = p; return up->b8; } + +/* Ordering function for FDEs. Functions can't overlap, so we just compare + their starting addresses. */ + +static inline saddr +fde_compare (fde *x, fde *y) +{ + return (saddr)x->pc_begin - (saddr)y->pc_begin; +} + +/* Return the address of the FDE after P. */ + +static inline fde * +next_fde (fde *p) +{ + return (fde *)(((char *)p) + p->length + sizeof (p->length)); +} + +/* 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 void +start_fde_sort (fde_accumulator *accu, size_t count) +{ + accu->linear.array = (fde **) malloc (sizeof (fde *) * count); + accu->erratic.array = (fde **) malloc (sizeof (fde *) * count); + accu->linear.count = 0; + accu->erratic.count = 0; +} + +static inline void +fde_insert (fde_accumulator *accu, fde *this_fde) +{ + 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). */ +static inline void +fde_split (fde_vector *linear, fde_vector *erratic) +{ + size_t count = linear->count; + size_t linear_max = (size_t) -1; + size_t previous_max[count]; + size_t i, j; + + for (i = 0; i < count; i++) + { + for (j = linear_max; + j != (size_t) -1 + && fde_compare (linear->array[i], linear->array[j]) < 0; + j = previous_max[j]) + { + erratic->array[erratic->count++] = linear->array[j]; + linear->array[j] = (fde *) NULL; + } + previous_max[i] = j; + linear_max = i; + } + + for (i = 0, j = 0; i < count; i++) + if (linear->array[i] != (fde *) NULL) + linear->array[j++] = linear->array[i]; + linear->count = j; +} + +/* 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.count != count) + abort (); + 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); + 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 linked once FDE entries. */ + if (this_fde->CIE_delta == 0 || this_fde->pc_begin == 0) + continue; + + ++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; +} + +/* 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. */ + +static void +frame_init (struct object* ob) +{ + size_t count; + fde_accumulator accu; + void *pc_begin, *pc_end; + + 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; + + start_fde_sort (&accu, count); + 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); + + ob->fde_array = end_fde_sort (&accu, count); + ob->pc_begin = pc_begin; + ob->pc_end = pc_end; +} + +/* Return a pointer to the FDE for the function containing PC. */ + +static fde * +find_fde (void *pc) +{ + struct object *ob; + size_t lo, hi; + + __gthread_mutex_lock (&object_mutex); + + 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; + } + + __gthread_mutex_unlock (&object_mutex); + + if (ob == 0) + return 0; + + /* 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; + } + + return 0; +} + +static inline struct dwarf_cie * +get_cie (fde *f) +{ + return ((void *)&f->CIE_delta) - f->CIE_delta; +} + +/* Extract any interesting information from the CIE for the translation + unit F belongs to. */ + +static void * +extract_cie_info (fde *f, struct cie_info *c) +{ + void *p; + int i; + + c->augmentation = get_cie (f)->augmentation; + + if (strcmp (c->augmentation, "") != 0 + && strcmp (c->augmentation, "eh") != 0 + && c->augmentation[0] != 'z') + return 0; + + p = c->augmentation + strlen (c->augmentation) + 1; + + if (strcmp (c->augmentation, "eh") == 0) + { + c->eh_ptr = read_pointer (p); + p += sizeof (void *); + } + else + c->eh_ptr = 0; + + p = decode_uleb128 (p, &c->code_align); + p = decode_sleb128 (p, &c->data_align); + c->ra_regno = *(unsigned char *)p++; + + /* If the augmentation starts with 'z', we now see the length of the + augmentation fields. */ + if (c->augmentation[0] == 'z') + { + p = decode_uleb128 (p, &i); + p += i; + } + + return p; +} + +/* Decode one instruction's worth of DWARF 2 call frame information. + Used by __frame_state_for. Takes pointers P to the instruction to + decode, STATE to the current register unwind information, INFO to the + current CIE information, and PC to the current PC value. Returns a + pointer to the next instruction. */ + +static void * +execute_cfa_insn (void *p, struct frame_state_internal *state, + struct cie_info *info, void **pc) +{ + unsigned insn = *(unsigned char *)p++; + unsigned reg; + int offset; + + if (insn & DW_CFA_advance_loc) + *pc += ((insn & 0x3f) * info->code_align); + else if (insn & DW_CFA_offset) + { + reg = (insn & 0x3f); + p = decode_uleb128 (p, &offset); + offset *= info->data_align; + state->s.saved[reg] = REG_SAVED_OFFSET; + state->s.reg_or_offset[reg] = offset; + } + else if (insn & DW_CFA_restore) + { + reg = (insn & 0x3f); + state->s.saved[reg] = REG_UNSAVED; + } + else switch (insn) + { + case DW_CFA_set_loc: + *pc = read_pointer (p); + p += sizeof (void *); + break; + case DW_CFA_advance_loc1: + *pc += read_1byte (p); + p += 1; + break; + case DW_CFA_advance_loc2: + *pc += read_2byte (p); + p += 2; + break; + case DW_CFA_advance_loc4: + *pc += read_4byte (p); + p += 4; + break; + + case DW_CFA_offset_extended: + p = decode_uleb128 (p, ®); + p = decode_uleb128 (p, &offset); + offset *= info->data_align; + state->s.saved[reg] = REG_SAVED_OFFSET; + state->s.reg_or_offset[reg] = offset; + break; + case DW_CFA_restore_extended: + p = decode_uleb128 (p, ®); + state->s.saved[reg] = REG_UNSAVED; + break; + + case DW_CFA_undefined: + case DW_CFA_same_value: + case DW_CFA_nop: + break; + + case DW_CFA_register: + { + unsigned reg2; + p = decode_uleb128 (p, ®); + p = decode_uleb128 (p, ®2); + state->s.saved[reg] = REG_SAVED_REG; + state->s.reg_or_offset[reg] = reg2; + } + break; + + case DW_CFA_def_cfa: + p = decode_uleb128 (p, ®); + p = decode_uleb128 (p, &offset); + state->s.cfa_reg = reg; + state->s.cfa_offset = offset; + break; + case DW_CFA_def_cfa_register: + p = decode_uleb128 (p, ®); + state->s.cfa_reg = reg; + break; + case DW_CFA_def_cfa_offset: + p = decode_uleb128 (p, &offset); + state->s.cfa_offset = offset; + break; + + case DW_CFA_remember_state: + { + struct frame_state_internal *save = + (struct frame_state_internal *) + malloc (sizeof (struct frame_state_internal)); + memcpy (save, state, sizeof (struct frame_state_internal)); + state->saved_state = save; + } + break; + case DW_CFA_restore_state: + { + struct frame_state_internal *save = state->saved_state; + memcpy (state, save, sizeof (struct frame_state_internal)); + free (save); + } + break; + + /* FIXME: Hardcoded for SPARC register window configuration. */ + case DW_CFA_GNU_window_save: + for (reg = 16; reg < 32; ++reg) + { + state->s.saved[reg] = REG_SAVED_OFFSET; + state->s.reg_or_offset[reg] = (reg - 16) * sizeof (void *); + } + break; + + case DW_CFA_GNU_args_size: + p = decode_uleb128 (p, &offset); + state->s.args_size = offset; + break; + + default: + abort (); + } + return p; +} + +/* Called from crtbegin.o to register the unwind info for an object. */ + +void +__register_frame_info (void *begin, struct object *ob) +{ + ob->fde_begin = begin; + + ob->pc_begin = ob->pc_end = 0; + ob->fde_array = 0; + ob->count = 0; + + __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->fde_begin = begin; + ob->fde_array = begin; + + ob->pc_begin = ob->pc_end = 0; + ob->count = 0; + + __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; + + __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->pc_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)); +} + +/* Called from __throw to find the registers to restore for a given + PC_TARGET. The caller should allocate a local variable of `struct + frame_state' (declared in frame.h) and pass its address to STATE_IN. */ + +struct frame_state * +__frame_state_for (void *pc_target, struct frame_state *state_in) +{ + fde *f; + void *insn, *end, *pc; + struct cie_info info; + struct frame_state_internal state; + + f = find_fde (pc_target); + if (f == 0) + return 0; + + insn = extract_cie_info (f, &info); + if (insn == 0) + return 0; + + memset (&state, 0, sizeof (state)); + state.s.retaddr_column = info.ra_regno; + state.s.eh_ptr = info.eh_ptr; + + /* First decode all the insns in the CIE. */ + end = next_fde ((fde*) get_cie (f)); + while (insn < end) + insn = execute_cfa_insn (insn, &state, &info, 0); + + insn = ((fde *)f) + 1; + + if (info.augmentation[0] == 'z') + { + int i; + insn = decode_uleb128 (insn, &i); + insn += i; + } + + /* Then the insns in the FDE up to our target PC. */ + end = next_fde (f); + pc = f->pc_begin; + while (insn < end && pc <= pc_target) + insn = execute_cfa_insn (insn, &state, &info, &pc); + + memcpy (state_in, &state.s, sizeof (state.s)); + return state_in; +} +#endif /* DWARF2_UNWIND_INFO */ |