1 /* Subroutines needed for unwinding stack frames for exception handling. */
2 /* Compile this one with gcc. */
3 /* Copyright (C) 1997, 1998, 1999, 2000 Free Software Foundation, Inc.
4 Contributed by Jason Merrill <jason@cygnus.com>.
6 This file is part of GNU CC.
8 GNU CC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
13 GNU CC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GNU CC; see the file COPYING. If not, write to
20 the Free Software Foundation, 59 Temple Place - Suite 330,
21 Boston, MA 02111-1307, USA. */
23 /* As a special exception, if you link this library with other files,
24 some of which are compiled with GCC, to produce an executable,
25 this library does not by itself cause the resulting executable
26 to be covered by the GNU General Public License.
27 This exception does not however invalidate any other reasons why
28 the executable file might be covered by the GNU General Public License. */
30 /* It is incorrect to include config.h here, because this file is being
31 compiled for the target, and hence definitions concerning only the host
39 #ifdef DWARF2_UNWIND_INFO
44 #ifdef __GTHREAD_MUTEX_INIT
45 static __gthread_mutex_t object_mutex = __GTHREAD_MUTEX_INIT;
47 static __gthread_mutex_t object_mutex;
50 /* Don't use `fancy_abort' here even if config.h says to use it. */
55 /* Some types used by the DWARF 2 spec. */
57 typedef int sword __attribute__ ((mode (SI)));
58 typedef unsigned int uword __attribute__ ((mode (SI)));
59 typedef unsigned int uaddr __attribute__ ((mode (pointer)));
60 typedef int saddr __attribute__ ((mode (pointer)));
61 typedef unsigned char ubyte;
64 CIE - Common Information Element
65 FDE - Frame Descriptor Element
67 There is one per function, and it describes where the function code
68 is located, and what the register lifetimes and stack layout are
71 The data structures are defined in the DWARF specfication, although
72 not in a very readable way (see LITERATURE).
74 Every time an exception is thrown, the code needs to locate the FDE
75 for the current function, and starts to look for exception regions
76 from that FDE. This works in a two-level search:
77 a) in a linear search, find the shared image (i.e. DLL) containing
79 b) using the FDE table for that shared object, locate the FDE using
80 binary search (which requires the sorting). */
82 /* The first few fields of a CIE. The CIE_id field is 0 for a CIE,
83 to distinguish it from a valid FDE. FDEs are aligned to an addressing
84 unit boundary, but the fields within are unaligned. */
91 } __attribute__ ((packed, aligned (__alignof__ (void *))));
93 /* The first few fields of an FDE. */
100 } __attribute__ ((packed, aligned (__alignof__ (void *))));
102 typedef struct dwarf_fde fde;
104 /* Objects to be searched for frame unwind info. */
106 static struct object *objects;
108 /* The information we care about from a CIE. */
118 /* The current unwind state, plus a saved copy for DW_CFA_remember_state. */
120 struct frame_state_internal
122 struct frame_state s;
123 struct frame_state_internal *saved_state;
126 /* This is undefined below if we need it to be an actual function. */
127 #define init_object_mutex_once()
130 #ifdef __GTHREAD_MUTEX_INIT_FUNCTION
132 /* Helper for init_object_mutex_once. */
135 init_object_mutex (void)
137 __GTHREAD_MUTEX_INIT_FUNCTION (&object_mutex);
140 /* Call this to arrange to initialize the object mutex. */
142 #undef init_object_mutex_once
144 init_object_mutex_once (void)
146 static __gthread_once_t once = __GTHREAD_ONCE_INIT;
147 __gthread_once (&once, init_object_mutex);
150 #endif /* __GTHREAD_MUTEX_INIT_FUNCTION */
151 #endif /* __GTHREADS */
153 /* Decode the unsigned LEB128 constant at BUF into the variable pointed to
154 by R, and return the new value of BUF. */
157 decode_uleb128 (unsigned char *buf, unsigned *r)
164 unsigned byte = *buf++;
165 result |= (byte & 0x7f) << shift;
166 if ((byte & 0x80) == 0)
174 /* Decode the signed LEB128 constant at BUF into the variable pointed to
175 by R, and return the new value of BUF. */
178 decode_sleb128 (unsigned char *buf, int *r)
187 result |= (byte & 0x7f) << shift;
189 if ((byte & 0x80) == 0)
192 if (shift < (sizeof (*r) * 8) && (byte & 0x40) != 0)
193 result |= - (1 << shift);
199 /* Read unaligned data from the instruction buffer. */
203 unsigned b2 __attribute__ ((mode (HI)));
204 unsigned b4 __attribute__ ((mode (SI)));
205 unsigned b8 __attribute__ ((mode (DI)));
206 } __attribute__ ((packed));
208 read_pointer (void *p)
209 { union unaligned *up = p; return up->p; }
210 static inline unsigned
212 { return *(unsigned char *)p; }
213 static inline unsigned
215 { union unaligned *up = p; return up->b2; }
216 static inline unsigned
218 { union unaligned *up = p; return up->b4; }
219 static inline unsigned long
221 { union unaligned *up = p; return up->b8; }
223 /* Ordering function for FDEs. Functions can't overlap, so we just compare
224 their starting addresses. */
227 fde_compare (fde *x, fde *y)
229 return (saddr)x->pc_begin - (saddr)y->pc_begin;
232 /* Return the address of the FDE after P. */
237 return (fde *)(((char *)p) + p->length + sizeof (p->length));
240 /* Sorting an array of FDEs by address.
241 (Ideally we would have the linker sort the FDEs so we don't have to do
242 it at run time. But the linkers are not yet prepared for this.) */
244 /* This is a special mix of insertion sort and heap sort, optimized for
245 the data sets that actually occur. They look like
246 101 102 103 127 128 105 108 110 190 111 115 119 125 160 126 129 130.
247 I.e. a linearly increasing sequence (coming from functions in the text
248 section), with additionally a few unordered elements (coming from functions
249 in gnu_linkonce sections) whose values are higher than the values in the
250 surrounding linear sequence (but not necessarily higher than the values
251 at the end of the linear sequence!).
252 The worst-case total run time is O(N) + O(n log (n)), where N is the
253 total number of FDEs and n is the number of erratic ones. */
255 typedef struct fde_vector
261 typedef struct fde_accumulator
268 start_fde_sort (fde_accumulator *accu, size_t count)
270 accu->linear.array = (fde **) malloc (sizeof (fde *) * count);
271 accu->erratic.array = accu->linear.array ?
272 (fde **) malloc (sizeof (fde *) * count) : NULL;
273 accu->linear.count = 0;
274 accu->erratic.count = 0;
276 return accu->linear.array != NULL;
280 fde_insert (fde_accumulator *accu, fde *this_fde)
282 if (accu->linear.array)
283 accu->linear.array[accu->linear.count++] = this_fde;
286 /* Split LINEAR into a linear sequence with low values and an erratic
287 sequence with high values, put the linear one (of longest possible
288 length) into LINEAR and the erratic one into ERRATIC. This is O(N).
290 Because the longest linear sequence we are trying to locate within the
291 incoming LINEAR array can be interspersed with (high valued) erratic
292 entries. We construct a chain indicating the sequenced entries.
293 To avoid having to allocate this chain, we overlay it onto the space of
294 the ERRATIC array during construction. A final pass iterates over the
295 chain to determine what should be placed in the ERRATIC array, and
296 what is the linear sequence. This overlay is safe from aliasing. */
298 fde_split (fde_vector *linear, fde_vector *erratic)
301 size_t count = linear->count;
302 fde **chain_end = ▮
305 /* This should optimize out, but it is wise to make sure this assumption
306 is correct. Should these have different sizes, we cannot cast between
307 them and the overlaying onto ERRATIC will not work. */
308 if (sizeof (fde *) != sizeof (fde **))
311 for (i = 0; i < count; i++)
315 for (probe = chain_end;
316 probe != &marker && fde_compare (linear->array[i], *probe) < 0;
319 chain_end = (fde **)erratic->array[probe - linear->array];
320 erratic->array[probe - linear->array] = NULL;
322 erratic->array[i] = (fde *)chain_end;
323 chain_end = &linear->array[i];
326 /* Each entry in LINEAR which is part of the linear sequence we have
327 discovered will correspond to a non-NULL entry in the chain we built in
328 the ERRATIC array. */
329 for (i = j = k = 0; i < count; i++)
330 if (erratic->array[i])
331 linear->array[j++] = linear->array[i];
333 erratic->array[k++] = linear->array[i];
338 /* This is O(n log(n)). BSD/OS defines heapsort in stdlib.h, so we must
339 use a name that does not conflict. */
341 frame_heapsort (fde_vector *erratic)
343 /* For a description of this algorithm, see:
344 Samuel P. Harbison, Guy L. Steele Jr.: C, a reference manual, 2nd ed.,
346 fde ** a = erratic->array;
347 /* A portion of the array is called a "heap" if for all i>=0:
348 If i and 2i+1 are valid indices, then a[i] >= a[2i+1].
349 If i and 2i+2 are valid indices, then a[i] >= a[2i+2]. */
350 #define SWAP(x,y) do { fde * tmp = x; x = y; y = tmp; } while (0)
351 size_t n = erratic->count;
357 /* Invariant: a[m..n-1] is a heap. */
359 for (i = m; 2*i+1 < n; )
362 && fde_compare (a[2*i+2], a[2*i+1]) > 0
363 && fde_compare (a[2*i+2], a[i]) > 0)
365 SWAP (a[i], a[2*i+2]);
368 else if (fde_compare (a[2*i+1], a[i]) > 0)
370 SWAP (a[i], a[2*i+1]);
379 /* Invariant: a[0..n-1] is a heap. */
382 for (i = 0; 2*i+1 < n; )
385 && fde_compare (a[2*i+2], a[2*i+1]) > 0
386 && fde_compare (a[2*i+2], a[i]) > 0)
388 SWAP (a[i], a[2*i+2]);
391 else if (fde_compare (a[2*i+1], a[i]) > 0)
393 SWAP (a[i], a[2*i+1]);
403 /* Merge V1 and V2, both sorted, and put the result into V1. */
405 fde_merge (fde_vector *v1, const fde_vector *v2)
416 fde2 = v2->array[i2];
417 while (i1 > 0 && fde_compare (v1->array[i1-1], fde2) > 0)
419 v1->array[i1+i2] = v1->array[i1-1];
422 v1->array[i1+i2] = fde2;
424 v1->count += v2->count;
429 end_fde_sort (fde_accumulator *accu, size_t count)
431 if (accu->linear.array && accu->linear.count != count)
434 if (accu->erratic.array)
436 fde_split (&accu->linear, &accu->erratic);
437 if (accu->linear.count + accu->erratic.count != count)
439 frame_heapsort (&accu->erratic);
440 fde_merge (&accu->linear, &accu->erratic);
441 if (accu->erratic.array)
442 free (accu->erratic.array);
446 /* We've not managed to malloc an erratic array, so heap sort in the
448 frame_heapsort (&accu->linear);
450 return accu->linear.array;
454 count_fdes (fde *this_fde)
458 for (count = 0; this_fde->length != 0; this_fde = next_fde (this_fde))
460 /* Skip CIEs and linked once FDE entries. */
461 if (this_fde->CIE_delta == 0 || this_fde->pc_begin == 0)
471 add_fdes (fde *this_fde, fde_accumulator *accu, void **beg_ptr, void **end_ptr)
473 void *pc_begin = *beg_ptr;
474 void *pc_end = *end_ptr;
476 for (; this_fde->length != 0; this_fde = next_fde (this_fde))
478 /* Skip CIEs and linked once FDE entries. */
479 if (this_fde->CIE_delta == 0 || this_fde->pc_begin == 0)
482 fde_insert (accu, this_fde);
484 if (this_fde->pc_begin < pc_begin)
485 pc_begin = this_fde->pc_begin;
486 if (this_fde->pc_begin + this_fde->pc_range > pc_end)
487 pc_end = this_fde->pc_begin + this_fde->pc_range;
494 /* search this fde table for the one containing the pc */
496 search_fdes (fde *this_fde, void *pc)
498 for (; this_fde->length != 0; this_fde = next_fde (this_fde))
500 /* Skip CIEs and linked once FDE entries. */
501 if (this_fde->CIE_delta == 0 || this_fde->pc_begin == 0)
504 if ((uaddr)((char *)pc - (char *)this_fde->pc_begin) < this_fde->pc_range)
510 /* Set up a sorted array of pointers to FDEs for a loaded object. We
511 count up the entries before allocating the array because it's likely to
512 be faster. We can be called multiple times, should we have failed to
513 allocate a sorted fde array on a previous occasion. */
516 frame_init (struct object* ob)
519 fde_accumulator accu;
520 void *pc_begin, *pc_end;
525 else if (ob->fde_array)
527 fde **p = ob->fde_array;
528 for (count = 0; *p; ++p)
529 count += count_fdes (*p);
532 count = count_fdes (ob->fde_begin);
535 if (!start_fde_sort (&accu, count) && ob->pc_begin)
538 pc_begin = (void*)(uaddr)-1;
543 fde **p = ob->fde_array;
545 add_fdes (*p, &accu, &pc_begin, &pc_end);
548 add_fdes (ob->fde_begin, &accu, &pc_begin, &pc_end);
550 array = end_fde_sort (&accu, count);
552 ob->fde_array = array;
553 ob->pc_begin = pc_begin;
557 /* Return a pointer to the FDE for the function containing PC. */
565 init_object_mutex_once ();
566 __gthread_mutex_lock (&object_mutex);
568 /* Linear search through the objects, to find the one containing the pc. */
569 for (ob = objects; ob; ob = ob->next)
571 if (ob->pc_begin == 0)
573 if (pc >= ob->pc_begin && pc < ob->pc_end)
579 __gthread_mutex_unlock (&object_mutex);
583 if (!ob->fde_array || (void *)ob->fde_array == (void *)ob->fde_begin)
586 if (ob->fde_array && (void *)ob->fde_array != (void *)ob->fde_begin)
588 __gthread_mutex_unlock (&object_mutex);
590 /* Standard binary search algorithm. */
591 for (lo = 0, hi = ob->count; lo < hi; )
593 size_t i = (lo + hi) / 2;
594 fde *f = ob->fde_array[i];
596 if (pc < f->pc_begin)
598 else if (pc >= f->pc_begin + f->pc_range)
606 /* Long slow labourious linear search, cos we've no memory. */
611 fde **p = ob->fde_array;
615 f = search_fdes (*p, pc);
623 f = search_fdes (ob->fde_begin, pc);
624 __gthread_mutex_unlock (&object_mutex);
630 static inline struct dwarf_cie *
633 return ((void *)&f->CIE_delta) - f->CIE_delta;
636 /* Extract any interesting information from the CIE for the translation
637 unit F belongs to. */
640 extract_cie_info (fde *f, struct cie_info *c)
645 c->augmentation = get_cie (f)->augmentation;
647 if (strcmp (c->augmentation, "") != 0
648 && strcmp (c->augmentation, "eh") != 0
649 && c->augmentation[0] != 'z')
652 p = c->augmentation + strlen (c->augmentation) + 1;
654 if (strcmp (c->augmentation, "eh") == 0)
656 c->eh_ptr = read_pointer (p);
657 p += sizeof (void *);
662 p = decode_uleb128 (p, &c->code_align);
663 p = decode_sleb128 (p, &c->data_align);
664 c->ra_regno = *(unsigned char *)p++;
666 /* If the augmentation starts with 'z', we now see the length of the
667 augmentation fields. */
668 if (c->augmentation[0] == 'z')
670 p = decode_uleb128 (p, &i);
677 /* Decode one instruction's worth of DWARF 2 call frame information.
678 Used by __frame_state_for. Takes pointers P to the instruction to
679 decode, STATE to the current register unwind information, INFO to the
680 current CIE information, and PC to the current PC value. Returns a
681 pointer to the next instruction. */
684 execute_cfa_insn (void *p, struct frame_state_internal *state,
685 struct cie_info *info, void **pc)
687 unsigned insn = *(unsigned char *)p++;
691 if (insn & DW_CFA_advance_loc)
692 *pc += ((insn & 0x3f) * info->code_align);
693 else if (insn & DW_CFA_offset)
696 p = decode_uleb128 (p, &offset);
697 offset *= info->data_align;
698 state->s.saved[reg] = REG_SAVED_OFFSET;
699 state->s.reg_or_offset[reg] = offset;
701 else if (insn & DW_CFA_restore)
704 state->s.saved[reg] = REG_UNSAVED;
709 *pc = read_pointer (p);
710 p += sizeof (void *);
712 case DW_CFA_advance_loc1:
713 *pc += read_1byte (p);
716 case DW_CFA_advance_loc2:
717 *pc += read_2byte (p);
720 case DW_CFA_advance_loc4:
721 *pc += read_4byte (p);
725 case DW_CFA_offset_extended:
726 p = decode_uleb128 (p, ®);
727 p = decode_uleb128 (p, &offset);
728 offset *= info->data_align;
729 state->s.saved[reg] = REG_SAVED_OFFSET;
730 state->s.reg_or_offset[reg] = offset;
732 case DW_CFA_restore_extended:
733 p = decode_uleb128 (p, ®);
734 state->s.saved[reg] = REG_UNSAVED;
737 case DW_CFA_undefined:
738 case DW_CFA_same_value:
742 case DW_CFA_register:
745 p = decode_uleb128 (p, ®);
746 p = decode_uleb128 (p, ®2);
747 state->s.saved[reg] = REG_SAVED_REG;
748 state->s.reg_or_offset[reg] = reg2;
753 p = decode_uleb128 (p, ®);
754 p = decode_uleb128 (p, &offset);
755 state->s.cfa_reg = reg;
756 state->s.cfa_offset = offset;
758 case DW_CFA_def_cfa_register:
759 p = decode_uleb128 (p, ®);
760 state->s.cfa_reg = reg;
762 case DW_CFA_def_cfa_offset:
763 p = decode_uleb128 (p, &offset);
764 state->s.cfa_offset = offset;
767 case DW_CFA_remember_state:
769 struct frame_state_internal *save =
770 (struct frame_state_internal *)
771 malloc (sizeof (struct frame_state_internal));
772 memcpy (save, state, sizeof (struct frame_state_internal));
773 state->saved_state = save;
776 case DW_CFA_restore_state:
778 struct frame_state_internal *save = state->saved_state;
779 memcpy (state, save, sizeof (struct frame_state_internal));
784 /* FIXME: Hardcoded for SPARC register window configuration. */
785 case DW_CFA_GNU_window_save:
786 for (reg = 16; reg < 32; ++reg)
788 state->s.saved[reg] = REG_SAVED_OFFSET;
789 state->s.reg_or_offset[reg] = (reg - 16) * sizeof (void *);
793 case DW_CFA_GNU_args_size:
794 p = decode_uleb128 (p, &offset);
795 state->s.args_size = offset;
798 case DW_CFA_GNU_negative_offset_extended:
799 p = decode_uleb128 (p, ®);
800 p = decode_uleb128 (p, &offset);
801 offset *= info->data_align;
802 state->s.saved[reg] = REG_SAVED_OFFSET;
803 state->s.reg_or_offset[reg] = -offset;
812 /* Called from crtbegin.o to register the unwind info for an object. */
815 __register_frame_info (void *begin, struct object *ob)
817 ob->fde_begin = begin;
819 ob->pc_begin = ob->pc_end = 0;
823 init_object_mutex_once ();
824 __gthread_mutex_lock (&object_mutex);
829 __gthread_mutex_unlock (&object_mutex);
833 __register_frame (void *begin)
835 struct object *ob = (struct object *) malloc (sizeof (struct object));
836 __register_frame_info (begin, ob);
839 /* Similar, but BEGIN is actually a pointer to a table of unwind entries
840 for different translation units. Called from the file generated by
844 __register_frame_info_table (void *begin, struct object *ob)
846 ob->fde_begin = begin;
847 ob->fde_array = begin;
849 ob->pc_begin = ob->pc_end = 0;
852 init_object_mutex_once ();
853 __gthread_mutex_lock (&object_mutex);
858 __gthread_mutex_unlock (&object_mutex);
862 __register_frame_table (void *begin)
864 struct object *ob = (struct object *) malloc (sizeof (struct object));
865 __register_frame_info_table (begin, ob);
868 /* Called from crtbegin.o to deregister the unwind info for an object. */
871 __deregister_frame_info (void *begin)
875 init_object_mutex_once ();
876 __gthread_mutex_lock (&object_mutex);
881 if ((*p)->fde_begin == begin)
883 struct object *ob = *p;
886 /* If we've run init_frame for this object, free the FDE array. */
887 if (ob->fde_array && ob->fde_array != begin)
888 free (ob->fde_array);
890 __gthread_mutex_unlock (&object_mutex);
896 __gthread_mutex_unlock (&object_mutex);
901 __deregister_frame (void *begin)
903 free (__deregister_frame_info (begin));
906 /* Called from __throw to find the registers to restore for a given
907 PC_TARGET. The caller should allocate a local variable of `struct
908 frame_state' (declared in frame.h) and pass its address to STATE_IN. */
911 __frame_state_for (void *pc_target, struct frame_state *state_in)
914 void *insn, *end, *pc;
915 struct cie_info info;
916 struct frame_state_internal state;
918 f = find_fde (pc_target);
922 insn = extract_cie_info (f, &info);
926 memset (&state, 0, sizeof (state));
927 state.s.retaddr_column = info.ra_regno;
928 state.s.eh_ptr = info.eh_ptr;
930 /* First decode all the insns in the CIE. */
931 end = next_fde ((fde*) get_cie (f));
933 insn = execute_cfa_insn (insn, &state, &info, 0);
935 insn = ((fde *)f) + 1;
937 if (info.augmentation[0] == 'z')
940 insn = decode_uleb128 (insn, &i);
944 /* Then the insns in the FDE up to our target PC. */
947 while (insn < end && pc <= pc_target)
948 insn = execute_cfa_insn (insn, &state, &info, &pc);
950 memcpy (state_in, &state.s, sizeof (state.s));
953 #endif /* DWARF2_UNWIND_INFO */