gcc/frame.c

   1 /* Subroutines needed for unwinding stack frames for exception handling.  */
   2 /* Compile this one with gcc.  */
   3 /* Copyright (C) 1997 Free Software Foundation, Inc.
   4    Contributed by Jason Merrill <jason@cygnus.com>.
   5
   6 This file is part of GNU CC.
   7
   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)
  11 any later version.
  12
  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.
  17
  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.  */
  22
  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.  */
  29
  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
  32    do not apply.  */
  33
  34 #include "tconfig.h"
  35 #include "defaults.h"
  36
  37 #ifdef DWARF2_UNWIND_INFO
  38 #include "dwarf2.h"
  39 #include "frame.h"
  40 #include <stddef.h>
  41
  42 /* Don't use `fancy_abort' here even if config.h says to use it.  */
  43 #ifdef abort
  44 #undef abort
  45 #endif
  46
  47 /* Some types used by the DWARF 2 spec.  */
  48
  49 typedef unsigned int uword __attribute__ ((mode (SI)));
  50 typedef unsigned int uaddr __attribute__ ((mode (pointer)));
  51 typedef int saddr __attribute__ ((mode (pointer)));
  52 typedef unsigned char ubyte;
  53
  54 /* The first few fields of a CIE.  The CIE_id field is 0xffffffff for a CIE,
  55    to distinguish it from a valid FDE.  FDEs are aligned to an addressing
  56    unit boundary, but the fields within are unaligned.  */
  57
  58 struct dwarf_cie {
  59   uword length;
  60   uaddr CIE_id;
  61   ubyte version;
  62   char augmentation[0];
  63 } __attribute__ ((packed, aligned (__alignof__ (void *))));
  64
  65 /* The first few fields of an FDE.  */
  66
  67 struct dwarf_fde {
  68   uword length;
  69   struct dwarf_cie* CIE_pointer;
  70   void* pc_begin;
  71   uaddr pc_range;
  72 } __attribute__ ((packed, aligned (__alignof__ (void *))));
  73
  74 typedef struct dwarf_fde fde;
  75
  76 /* The representation for an "object" to be searched for frame unwind info.
  77    For targets with named sections, one object is an executable or shared
  78    library; for other targets, one object is one translation unit.  */
  79
  80 struct object {
  81   void *pc_begin;
  82   void *pc_end;
  83   fde *fde_begin;
  84   fde ** fde_array;
  85   size_t count;
  86   struct object *next;
  87 };
  88
  89 static struct object *objects;
  90
  91 /* The information we care about from a CIE.  */
  92
  93 struct cie_info {
  94   char *augmentation;
  95   int code_align;
  96   int data_align;
  97   unsigned ra_regno;
  98 };
  99
 100 /* The current unwind state, plus a saved copy for DW_CFA_remember_state.  */
 101
 102 struct frame_state_internal
 103 {
 104   struct frame_state s;
 105   struct frame_state_internal *saved_state;
 106 };
 107 \f
 108 /* Decode the unsigned LEB128 constant at BUF into the variable pointed to
 109    by R, and return the new value of BUF.  */
 110
 111 static void *
 112 decode_uleb128 (unsigned char *buf, unsigned *r)
 113 {
 114   unsigned shift = 0;
 115   unsigned result = 0;
 116
 117   while (1)
 118     {
 119       unsigned byte = *buf++;
 120       result |= (byte & 0x7f) << shift;
 121       if ((byte & 0x80) == 0)
 122         break;
 123       shift += 7;
 124     }
 125   *r = result;
 126   return buf;
 127 }
 128
 129 /* Decode the signed LEB128 constant at BUF into the variable pointed to
 130    by R, and return the new value of BUF.  */
 131
 132 static void *
 133 decode_sleb128 (unsigned char *buf, int *r)
 134 {
 135   unsigned shift = 0;
 136   unsigned result = 0;
 137   unsigned byte;
 138
 139   while (1)
 140     {
 141       byte = *buf++;
 142       result |= (byte & 0x7f) << shift;
 143       shift += 7;
 144       if ((byte & 0x80) == 0)
 145         break;
 146     }
 147   if (shift < (sizeof (*r) * 8) && (byte & 0x40) != 0)
 148     result |= - (1 << shift);
 149
 150   *r = result;
 151   return buf;
 152 }
 153
 154 /* Read unaligned data from the instruction buffer.  */
 155
 156 union unaligned {
 157   void *p;
 158   unsigned b2 __attribute__ ((mode (HI)));
 159   unsigned b4 __attribute__ ((mode (SI)));
 160   unsigned b8 __attribute__ ((mode (DI)));
 161 } __attribute__ ((packed));
 162 static inline void *
 163 read_pointer (void *p)
 164 { union unaligned *up = p; return up->p; }
 165 static inline unsigned
 166 read_1byte (void *p)
 167 { return *(unsigned char *)p; }
 168 static inline unsigned
 169 read_2byte (void *p)
 170 { union unaligned *up = p; return up->b2; }
 171 static inline unsigned
 172 read_4byte (void *p)
 173 { union unaligned *up = p; return up->b4; }
 174 static inline unsigned long
 175 read_8byte (void *p)
 176 { union unaligned *up = p; return up->b8; }
 177 \f
 178 /* Ordering function for FDEs.  Functions can't overlap, so we just compare
 179    their starting addresses.  */
 180
 181 static inline saddr
 182 fde_compare (fde *x, fde *y)
 183 {
 184   return (saddr)x->pc_begin - (saddr)y->pc_begin;
 185 }
 186
 187 /* Return the address of the FDE after P.  */
 188
 189 static inline fde *
 190 next_fde (fde *p)
 191 {
 192   return (fde *)(((char *)p) + p->length + sizeof (p->length));
 193 }
 194
 195 /* One iteration of an insertion sort, for adding new FDEs to the array.
 196    Usually the new FDE will go in at the end, so we can expect close to
 197    O(n) performance.  If this turns out to be overly optimistic, we can have
 198    the linker sort the FDEs so we don't have to do it at run time.  */
 199
 200 static void
 201 fde_insert (fde **array, size_t i, fde *this_fde)
 202 {
 203   array[i] = this_fde;
 204
 205   for (; i > 0 && fde_compare (array[i], array[i-1]) < 0; --i)
 206     {
 207       this_fde = array[i];
 208       array[i] = array[i-1];
 209       array[i-1] = this_fde;
 210     }
 211 }
 212
 213 static size_t
 214 count_fdes (fde *this_fde)
 215 {
 216   size_t count;
 217
 218   for (count = 0; this_fde->length != 0; this_fde = next_fde (this_fde))
 219     {
 220       /* Skip CIEs.  */
 221       if ((uaddr)(this_fde->CIE_pointer) == (uaddr)-1)
 222         continue;
 223
 224       ++count;
 225     }
 226
 227   return count;
 228 }
 229
 230 static void
 231 add_fdes (fde *this_fde, fde **array, size_t *i_ptr,
 232           void **beg_ptr, void **end_ptr)
 233 {
 234   size_t i = *i_ptr;
 235   void *pc_begin = *beg_ptr;
 236   void *pc_end = *end_ptr;
 237
 238   for (; this_fde->length != 0; this_fde = next_fde (this_fde))
 239     {
 240       /* Skip CIEs.  */
 241       if ((uaddr)(this_fde->CIE_pointer) == (uaddr)-1)
 242         continue;
 243
 244       fde_insert (array, i++, this_fde);
 245
 246       if (this_fde->pc_begin < pc_begin)
 247         pc_begin = this_fde->pc_begin;
 248       if (this_fde->pc_begin + this_fde->pc_range > pc_end)
 249         pc_end = this_fde->pc_begin + this_fde->pc_range;
 250     }
 251
 252   *i_ptr = i;
 253   *beg_ptr = pc_begin;
 254   *end_ptr = pc_end;
 255 }
 256
 257 /* Set up a sorted array of pointers to FDEs for a loaded object.  We
 258    count up the entries before allocating the array because it's likely to
 259    be faster.  */
 260
 261 static void
 262 frame_init (struct object* ob)
 263 {
 264   fde *this_fde;
 265   size_t count;
 266   fde **array;
 267   void *pc_begin, *pc_end;
 268
 269   if (ob->fde_array)
 270     {
 271       fde **p = ob->fde_array;
 272       for (count = 0; *p; ++p)
 273         count += count_fdes (*p);
 274     }
 275   else
 276     count = count_fdes (ob->fde_begin);
 277
 278   ob->count = count;
 279   array = (fde **) malloc (sizeof (fde *) * count);
 280
 281   pc_begin = (void*)(uaddr)-1;
 282   pc_end = 0;
 283   count = 0;
 284
 285   if (ob->fde_array)
 286     {
 287       fde **p = ob->fde_array;
 288       for (; *p; ++p)
 289         add_fdes (*p, array, &count, &pc_begin, &pc_end);
 290     }
 291   else
 292     add_fdes (ob->fde_begin, array, &count, &pc_begin, &pc_end);
 293
 294   ob->fde_array = array;
 295   ob->pc_begin = pc_begin;
 296   ob->pc_end = pc_end;
 297 }
 298
 299 /* Return a pointer to the FDE for the function containing PC.  */
 300
 301 static fde *
 302 find_fde (void *pc)
 303 {
 304   struct object *ob;
 305   size_t lo, hi;
 306
 307   for (ob = objects; ob; ob = ob->next)
 308     {
 309       if (ob->pc_begin == 0)
 310         frame_init (ob);
 311       if (pc >= ob->pc_begin && pc < ob->pc_end)
 312         break;
 313     }
 314
 315   if (ob == 0)
 316     return 0;
 317
 318   /* Standard binary search algorithm.  */
 319   for (lo = 0, hi = ob->count; lo < hi; )
 320     {
 321       size_t i = (lo + hi) / 2;
 322       fde *f = ob->fde_array[i];
 323
 324       if (pc < f->pc_begin)
 325         hi = i;
 326       else if (pc > f->pc_begin + f->pc_range)
 327         lo = i + 1;
 328       else
 329         return f;
 330     }
 331
 332   return 0;
 333 }
 334 \f
 335 /* Extract any interesting information from the CIE for the translation
 336    unit F belongs to.  */
 337
 338 static void *
 339 extract_cie_info (fde *f, struct cie_info *c)
 340 {
 341   void *p;
 342   int i;
 343
 344   c->augmentation = f->CIE_pointer->augmentation;
 345
 346   if (strcmp (c->augmentation, "") != 0
 347       && strcmp (c->augmentation, "e") != 0
 348       && c->augmentation[0] != 'z')
 349     return 0;
 350
 351   p = c->augmentation + strlen (c->augmentation) + 1;
 352
 353   p = decode_uleb128 (p, &c->code_align);
 354   p = decode_sleb128 (p, &c->data_align);
 355   c->ra_regno = *(unsigned char *)p++;
 356
 357   /* If the augmentation starts with 'z', we now see the length of the
 358      augmentation fields.  */
 359   if (c->augmentation[0] == 'z')
 360     {
 361       p = decode_uleb128 (p, &i);
 362       p += i;
 363     }
 364
 365   return p;
 366 }
 367
 368 /* Decode one instruction's worth of of DWARF 2 call frame information.
 369    Used by __frame_state_for.  Takes pointers P to the instruction to
 370    decode, STATE to the current register unwind information, INFO to the
 371    current CIE information, and PC to the current PC value.  Returns a
 372    pointer to the next instruction.  */
 373
 374 static void *
 375 execute_cfa_insn (void *p, struct frame_state_internal *state,
 376                   struct cie_info *info, void **pc)
 377 {
 378   unsigned insn = *(unsigned char *)p++;
 379   unsigned reg;
 380   int offset;
 381
 382   if (insn & DW_CFA_advance_loc)
 383     *pc += ((insn & 0x3f) * info->code_align);
 384   else if (insn & DW_CFA_offset)
 385     {
 386       reg = (insn & 0x3f);
 387       p = decode_uleb128 (p, &offset);
 388       offset *= info->data_align;
 389       state->s.saved[reg] = REG_SAVED_OFFSET;
 390       state->s.reg_or_offset[reg] = offset;
 391     }
 392   else if (insn & DW_CFA_restore)
 393     {
 394       reg = (insn & 0x3f);
 395       state->s.saved[reg] = REG_UNSAVED;
 396     }
 397   else switch (insn)
 398     {
 399     case DW_CFA_set_loc:
 400       *pc = read_pointer (p);
 401       p += sizeof (void *);
 402       break;
 403     case DW_CFA_advance_loc1:
 404       *pc += read_1byte (p);
 405       p += 1;
 406       break;
 407     case DW_CFA_advance_loc2:
 408       *pc += read_2byte (p);
 409       p += 2;
 410       break;
 411     case DW_CFA_advance_loc4:
 412       *pc += read_4byte (p);
 413       p += 4;
 414       break;
 415
 416     case DW_CFA_offset_extended:
 417       p = decode_uleb128 (p, &reg);
 418       p = decode_uleb128 (p, &offset);
 419       offset *= info->data_align;
 420       state->s.saved[reg] = REG_SAVED_OFFSET;
 421       state->s.reg_or_offset[reg] = offset;
 422       break;
 423     case DW_CFA_restore_extended:
 424       p = decode_uleb128 (p, &reg);
 425       state->s.saved[reg] = REG_UNSAVED;
 426       break;
 427
 428     case DW_CFA_undefined:
 429     case DW_CFA_same_value:
 430     case DW_CFA_nop:
 431       break;
 432
 433     case DW_CFA_register:
 434       {
 435         unsigned reg2;
 436         p = decode_uleb128 (p, &reg);
 437         p = decode_uleb128 (p, &reg2);
 438         state->s.saved[reg] = REG_SAVED_REG;
 439         state->s.reg_or_offset[reg] = reg2;
 440       }
 441       break;
 442
 443     case DW_CFA_def_cfa:
 444       p = decode_uleb128 (p, &reg);
 445       p = decode_uleb128 (p, &offset);
 446       state->s.cfa_reg = reg;
 447       state->s.cfa_offset = offset;
 448       break;
 449     case DW_CFA_def_cfa_register:
 450       p = decode_uleb128 (p, &reg);
 451       state->s.cfa_reg = reg;
 452       break;
 453     case DW_CFA_def_cfa_offset:
 454       p = decode_uleb128 (p, &offset);
 455       state->s.cfa_offset = offset;
 456       break;
 457
 458     case DW_CFA_remember_state:
 459       {
 460         struct frame_state_internal *save =
 461           (struct frame_state_internal *)
 462           malloc (sizeof (struct frame_state_internal));
 463         memcpy (save, state, sizeof (struct frame_state_internal));
 464         state->saved_state = save;
 465       }
 466       break;
 467     case DW_CFA_restore_state:
 468       {
 469         struct frame_state_internal *save = state->saved_state;
 470         memcpy (state, save, sizeof (struct frame_state_internal));
 471         free (save);
 472       }
 473       break;
 474
 475       /* FIXME: Hardcoded for SPARC register window configuration.  */
 476     case DW_CFA_GNU_window_save:
 477       for (reg = 16; reg < 32; ++reg)
 478         {
 479           state->s.saved[reg] = REG_SAVED_OFFSET;
 480           state->s.reg_or_offset[reg] = (reg - 16) * sizeof (void *);
 481         }
 482       break;
 483
 484     case DW_CFA_GNU_args_size:
 485       p = decode_uleb128 (p, &offset);
 486       state->s.args_size = offset;
 487       break;
 488
 489     default:
 490       abort ();
 491     }
 492   return p;
 493 }
 494 \f
 495 /* Called from crtbegin.o to register the unwind info for an object.  */
 496
 497 void
 498 __register_frame (void *begin)
 499 {
 500   struct object *ob = (struct object *) malloc (sizeof (struct object));
 501
 502   ob->fde_begin = begin;
 503
 504   ob->pc_begin = ob->pc_end = 0;
 505   ob->fde_array = 0;
 506   ob->count = 0;
 507
 508   ob->next = objects;
 509   objects = ob;
 510 }
 511
 512 /* Similar, but BEGIN is actually a pointer to a table of unwind entries
 513    for different translation units.  Called from the file generated by
 514    collect2.  */
 515
 516 void
 517 __register_frame_table (void *begin)
 518 {
 519   struct object *ob = (struct object *) malloc (sizeof (struct object));
 520
 521   ob->fde_begin = begin;
 522   ob->fde_array = begin;
 523
 524   ob->pc_begin = ob->pc_end = 0;
 525   ob->count = 0;
 526
 527   ob->next = objects;
 528   objects = ob;
 529 }
 530
 531 /* Called from crtend.o to deregister the unwind info for an object.  */
 532
 533 void
 534 __deregister_frame (void *begin)
 535 {
 536   struct object **p = &objects;
 537
 538   while (*p)
 539     {
 540       if ((*p)->fde_begin == begin)
 541         {
 542           struct object *ob = *p;
 543           *p = (*p)->next;
 544
 545           /* If we've run init_frame for this object, free the FDE array.  */
 546           if (ob->pc_begin)
 547             free (ob->fde_array);
 548           free (ob);
 549
 550           return;
 551         }
 552       p = &((*p)->next);
 553     }
 554   abort ();
 555 }
 556
 557 /* Called from __throw to find the registers to restore for a given
 558    PC_TARGET.  The caller should allocate a local variable of `struct
 559    frame_state' (declared in frame.h) and pass its address to STATE_IN.  */
 560
 561 struct frame_state *
 562 __frame_state_for (void *pc_target, struct frame_state *state_in)
 563 {
 564   fde *f;
 565   void *insn, *end, *pc;
 566   struct cie_info info;
 567   struct frame_state_internal state;
 568
 569   f = find_fde (pc_target);
 570   if (f == 0)
 571     return 0;
 572
 573   insn = extract_cie_info (f, &info);
 574   if (insn == 0)
 575     return 0;
 576
 577   memset (&state, 0, sizeof (state));
 578   state.s.retaddr_column = info.ra_regno;
 579
 580   /* First decode all the insns in the CIE.  */
 581   end = next_fde ((fde*) f->CIE_pointer);
 582   while (insn < end)
 583     insn = execute_cfa_insn (insn, &state, &info, 0);
 584
 585   insn = ((fde *)f) + 1;
 586
 587   if (info.augmentation[0] == 'z')
 588     {
 589       int i;
 590       insn = decode_uleb128 (insn, &i);
 591       insn += i;
 592     }
 593   else if (strcmp (info.augmentation, "e") == 0)
 594     {
 595       state.s.eh_ptr = read_pointer (insn);
 596       insn += sizeof (void *);
 597     }
 598
 599   /* Then the insns in the FDE up to our target PC.  */
 600   end = next_fde (f);
 601   pc = f->pc_begin;
 602   while (insn < end && pc < pc_target)
 603     insn = execute_cfa_insn (insn, &state, &info, &pc);
 604
 605   memcpy (state_in, &state.s, sizeof (state.s));
 606   return state_in;
 607 }
 608 #endif /* DWARF2_UNWIND_INFO */