src/dwarf/Gparser.c

   1 /* libunwind - a platform-independent unwind library
   2    Copyright (c) 2003, 2005 Hewlett-Packard Development Company, L.P.
   3         Contributed by David Mosberger-Tang <davidm@hpl.hp.com>
   4
   5 This file is part of libunwind.
   6
   7 Permission is hereby granted, free of charge, to any person obtaining
   8 a copy of this software and associated documentation files (the
   9 "Software"), to deal in the Software without restriction, including
  10 without limitation the rights to use, copy, modify, merge, publish,
  11 distribute, sublicense, and/or sell copies of the Software, and to
  12 permit persons to whom the Software is furnished to do so, subject to
  13 the following conditions:
  14
  15 The above copyright notice and this permission notice shall be
  16 included in all copies or substantial portions of the Software.
  17
  18 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  19 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  20 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  21 NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  22 LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  23 OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  24 WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.  */
  25
  26 #include <stddef.h>
  27 #include "dwarf_i.h"
  28 #include "libunwind_i.h"
  29
  30 #define alloc_reg_state()       (mempool_alloc (&dwarf_reg_state_pool))
  31 #define free_reg_state(rs)      (mempool_free (&dwarf_reg_state_pool, rs))
  32
  33 static inline int
  34 read_regnum (unw_addr_space_t as, unw_accessors_t *a, unw_word_t *addr,
  35              unw_word_t *valp, void *arg)
  36 {
  37   int ret;
  38
  39   if ((ret = dwarf_read_uleb128 (as, a, addr, valp, arg)) < 0)
  40     return ret;
  41
  42   if (*valp >= DWARF_NUM_PRESERVED_REGS)
  43     {
  44       Debug (1, "Invalid register number %u\n", (unsigned int) *valp);
  45       return -UNW_EBADREG;
  46     }
  47   return 0;
  48 }
  49
  50 static inline void
  51 set_reg (dwarf_state_record_t *sr, unw_word_t regnum, dwarf_where_t where,
  52          unw_word_t val)
  53 {
  54   sr->rs_current.reg[regnum].where = where;
  55   sr->rs_current.reg[regnum].val = val;
  56 }
  57
  58 /* Run a CFI program to update the register state.  */
  59 static int
  60 run_cfi_program (struct dwarf_cursor *c, dwarf_state_record_t *sr,
  61                  unw_word_t ip, unw_word_t *addr, unw_word_t end_addr,
  62                  struct dwarf_cie_info *dci)
  63 {
  64   unw_word_t curr_ip, operand = 0, regnum, val, len, fde_encoding;
  65   dwarf_reg_state_t *rs_stack = NULL, *new_rs, *old_rs;
  66   unw_addr_space_t as;
  67   unw_accessors_t *a;
  68   uint8_t u8, op;
  69   uint16_t u16;
  70   uint32_t u32;
  71   void *arg;
  72   int ret;
  73
  74   as = c->as;
  75   arg = c->as_arg;
  76   if (c->pi.flags & UNW_PI_FLAG_DEBUG_FRAME)
  77     {
  78       /* .debug_frame CFI is stored in local address space.  */
  79       as = unw_local_addr_space;
  80       arg = NULL;
  81     }
  82   a = unw_get_accessors (as);
  83   curr_ip = c->pi.start_ip;
  84
  85   /* Process everything up to and including the current 'ip',
  86      including all the DW_CFA_advance_loc instructions.  See
  87      'c->use_prev_instr' use in 'fetch_proc_info' for details. */
  88   while (curr_ip <= ip && *addr < end_addr)
  89     {
  90       if ((ret = dwarf_readu8 (as, a, addr, &op, arg)) < 0)
  91         return ret;
  92
  93       if (op & DWARF_CFA_OPCODE_MASK)
  94         {
  95           operand = op & DWARF_CFA_OPERAND_MASK;
  96           op &= ~DWARF_CFA_OPERAND_MASK;
  97         }
  98       switch ((dwarf_cfa_t) op)
  99         {
 100         case DW_CFA_advance_loc:
 101           curr_ip += operand * dci->code_align;
 102           Debug (15, "CFA_advance_loc to 0x%lx\n", (long) curr_ip);
 103           break;
 104
 105         case DW_CFA_advance_loc1:
 106           if ((ret = dwarf_readu8 (as, a, addr, &u8, arg)) < 0)
 107             goto fail;
 108           curr_ip += u8 * dci->code_align;
 109           Debug (15, "CFA_advance_loc1 to 0x%lx\n", (long) curr_ip);
 110           break;
 111
 112         case DW_CFA_advance_loc2:
 113           if ((ret = dwarf_readu16 (as, a, addr, &u16, arg)) < 0)
 114             goto fail;
 115           curr_ip += u16 * dci->code_align;
 116           Debug (15, "CFA_advance_loc2 to 0x%lx\n", (long) curr_ip);
 117           break;
 118
 119         case DW_CFA_advance_loc4:
 120           if ((ret = dwarf_readu32 (as, a, addr, &u32, arg)) < 0)
 121             goto fail;
 122           curr_ip += u32 * dci->code_align;
 123           Debug (15, "CFA_advance_loc4 to 0x%lx\n", (long) curr_ip);
 124           break;
 125
 126         case DW_CFA_MIPS_advance_loc8:
 127 #ifdef UNW_TARGET_MIPS
 128           {
 129             uint64_t u64;
 130
 131             if ((ret = dwarf_readu64 (as, a, addr, &u64, arg)) < 0)
 132               goto fail;
 133             curr_ip += u64 * dci->code_align;
 134             Debug (15, "CFA_MIPS_advance_loc8\n");
 135             break;
 136           }
 137 #else
 138           Debug (1, "DW_CFA_MIPS_advance_loc8 on non-MIPS target\n");
 139           ret = -UNW_EINVAL;
 140           goto fail;
 141 #endif
 142
 143         case DW_CFA_offset:
 144           regnum = operand;
 145           if (regnum >= DWARF_NUM_PRESERVED_REGS)
 146             {
 147               Debug (1, "Invalid register number %u in DW_cfa_OFFSET\n",
 148                      (unsigned int) regnum);
 149               ret = -UNW_EBADREG;
 150               goto fail;
 151             }
 152           if ((ret = dwarf_read_uleb128 (as, a, addr, &val, arg)) < 0)
 153             goto fail;
 154           set_reg (sr, regnum, DWARF_WHERE_CFAREL, val * dci->data_align);
 155           Debug (15, "CFA_offset r%lu at cfa+0x%lx\n",
 156                  (long) regnum, (long) (val * dci->data_align));
 157           break;
 158
 159         case DW_CFA_offset_extended:
 160           if (((ret = read_regnum (as, a, addr, &regnum, arg)) < 0)
 161               || ((ret = dwarf_read_uleb128 (as, a, addr, &val, arg)) < 0))
 162             goto fail;
 163           set_reg (sr, regnum, DWARF_WHERE_CFAREL, val * dci->data_align);
 164           Debug (15, "CFA_offset_extended r%lu at cf+0x%lx\n",
 165                  (long) regnum, (long) (val * dci->data_align));
 166           break;
 167
 168         case DW_CFA_offset_extended_sf:
 169           if (((ret = read_regnum (as, a, addr, &regnum, arg)) < 0)
 170               || ((ret = dwarf_read_sleb128 (as, a, addr, &val, arg)) < 0))
 171             goto fail;
 172           set_reg (sr, regnum, DWARF_WHERE_CFAREL, val * dci->data_align);
 173           Debug (15, "CFA_offset_extended_sf r%lu at cf+0x%lx\n",
 174                  (long) regnum, (long) (val * dci->data_align));
 175           break;
 176
 177         case DW_CFA_restore:
 178           regnum = operand;
 179           if (regnum >= DWARF_NUM_PRESERVED_REGS)
 180             {
 181               Debug (1, "Invalid register number %u in DW_CFA_restore\n",
 182                      (unsigned int) regnum);
 183               ret = -UNW_EINVAL;
 184               goto fail;
 185             }
 186           sr->rs_current.reg[regnum] = sr->rs_initial.reg[regnum];
 187           Debug (15, "CFA_restore r%lu\n", (long) regnum);
 188           break;
 189
 190         case DW_CFA_restore_extended:
 191           if ((ret = dwarf_read_uleb128 (as, a, addr, &regnum, arg)) < 0)
 192             goto fail;
 193           if (regnum >= DWARF_NUM_PRESERVED_REGS)
 194             {
 195               Debug (1, "Invalid register number %u in "
 196                      "DW_CFA_restore_extended\n", (unsigned int) regnum);
 197               ret = -UNW_EINVAL;
 198               goto fail;
 199             }
 200           sr->rs_current.reg[regnum] = sr->rs_initial.reg[regnum];
 201           Debug (15, "CFA_restore_extended r%lu\n", (long) regnum);
 202           break;
 203
 204         case DW_CFA_nop:
 205           break;
 206
 207         case DW_CFA_set_loc:
 208           fde_encoding = dci->fde_encoding;
 209           if ((ret = dwarf_read_encoded_pointer (as, a, addr, fde_encoding,
 210                                                  &c->pi, &curr_ip,
 211                                                  arg)) < 0)
 212             goto fail;
 213           Debug (15, "CFA_set_loc to 0x%lx\n", (long) curr_ip);
 214           break;
 215
 216         case DW_CFA_undefined:
 217           if ((ret = read_regnum (as, a, addr, &regnum, arg)) < 0)
 218             goto fail;
 219           set_reg (sr, regnum, DWARF_WHERE_UNDEF, 0);
 220           Debug (15, "CFA_undefined r%lu\n", (long) regnum);
 221           break;
 222
 223         case DW_CFA_same_value:
 224           if ((ret = read_regnum (as, a, addr, &regnum, arg)) < 0)
 225             goto fail;
 226           set_reg (sr, regnum, DWARF_WHERE_SAME, 0);
 227           Debug (15, "CFA_same_value r%lu\n", (long) regnum);
 228           break;
 229
 230         case DW_CFA_register:
 231           if (((ret = read_regnum (as, a, addr, &regnum, arg)) < 0)
 232               || ((ret = dwarf_read_uleb128 (as, a, addr, &val, arg)) < 0))
 233             goto fail;
 234           set_reg (sr, regnum, DWARF_WHERE_REG, val);
 235           Debug (15, "CFA_register r%lu to r%lu\n", (long) regnum, (long) val);
 236           break;
 237
 238         case DW_CFA_remember_state:
 239           new_rs = alloc_reg_state ();
 240           if (!new_rs)
 241             {
 242               Debug (1, "Out of memory in DW_CFA_remember_state\n");
 243               ret = -UNW_ENOMEM;
 244               goto fail;
 245             }
 246
 247           memcpy (new_rs->reg, sr->rs_current.reg, sizeof (new_rs->reg));
 248           new_rs->next = rs_stack;
 249           rs_stack = new_rs;
 250           Debug (15, "CFA_remember_state\n");
 251           break;
 252
 253         case DW_CFA_restore_state:
 254           if (!rs_stack)
 255             {
 256               Debug (1, "register-state stack underflow\n");
 257               ret = -UNW_EINVAL;
 258               goto fail;
 259             }
 260           memcpy (&sr->rs_current.reg, &rs_stack->reg, sizeof (rs_stack->reg));
 261           old_rs = rs_stack;
 262           rs_stack = rs_stack->next;
 263           free_reg_state (old_rs);
 264           Debug (15, "CFA_restore_state\n");
 265           break;
 266
 267         case DW_CFA_def_cfa:
 268           if (((ret = read_regnum (as, a, addr, &regnum, arg)) < 0)
 269               || ((ret = dwarf_read_uleb128 (as, a, addr, &val, arg)) < 0))
 270             goto fail;
 271           set_reg (sr, DWARF_CFA_REG_COLUMN, DWARF_WHERE_REG, regnum);
 272           set_reg (sr, DWARF_CFA_OFF_COLUMN, 0, val);   /* NOT factored! */
 273           Debug (15, "CFA_def_cfa r%lu+0x%lx\n", (long) regnum, (long) val);
 274           break;
 275
 276         case DW_CFA_def_cfa_sf:
 277           if (((ret = read_regnum (as, a, addr, &regnum, arg)) < 0)
 278               || ((ret = dwarf_read_sleb128 (as, a, addr, &val, arg)) < 0))
 279             goto fail;
 280           set_reg (sr, DWARF_CFA_REG_COLUMN, DWARF_WHERE_REG, regnum);
 281           set_reg (sr, DWARF_CFA_OFF_COLUMN, 0,
 282                    val * dci->data_align);              /* factored! */
 283           Debug (15, "CFA_def_cfa_sf r%lu+0x%lx\n",
 284                  (long) regnum, (long) (val * dci->data_align));
 285           break;
 286
 287         case DW_CFA_def_cfa_register:
 288           if ((ret = read_regnum (as, a, addr, &regnum, arg)) < 0)
 289             goto fail;
 290           set_reg (sr, DWARF_CFA_REG_COLUMN, DWARF_WHERE_REG, regnum);
 291           Debug (15, "CFA_def_cfa_register r%lu\n", (long) regnum);
 292           break;
 293
 294         case DW_CFA_def_cfa_offset:
 295           if ((ret = dwarf_read_uleb128 (as, a, addr, &val, arg)) < 0)
 296             goto fail;
 297           set_reg (sr, DWARF_CFA_OFF_COLUMN, 0, val);   /* NOT factored! */
 298           Debug (15, "CFA_def_cfa_offset 0x%lx\n", (long) val);
 299           break;
 300
 301         case DW_CFA_def_cfa_offset_sf:
 302           if ((ret = dwarf_read_sleb128 (as, a, addr, &val, arg)) < 0)
 303             goto fail;
 304           set_reg (sr, DWARF_CFA_OFF_COLUMN, 0,
 305                    val * dci->data_align);      /* factored! */
 306           Debug (15, "CFA_def_cfa_offset_sf 0x%lx\n",
 307                  (long) (val * dci->data_align));
 308           break;
 309
 310         case DW_CFA_def_cfa_expression:
 311           /* Save the address of the DW_FORM_block for later evaluation. */
 312           set_reg (sr, DWARF_CFA_REG_COLUMN, DWARF_WHERE_EXPR, *addr);
 313
 314           if ((ret = dwarf_read_uleb128 (as, a, addr, &len, arg)) < 0)
 315             goto fail;
 316
 317           Debug (15, "CFA_def_cfa_expr @ 0x%lx [%lu bytes]\n",
 318                  (long) *addr, (long) len);
 319           *addr += len;
 320           break;
 321
 322         case DW_CFA_expression:
 323           if ((ret = read_regnum (as, a, addr, &regnum, arg)) < 0)
 324             goto fail;
 325
 326           /* Save the address of the DW_FORM_block for later evaluation. */
 327           set_reg (sr, regnum, DWARF_WHERE_EXPR, *addr);
 328
 329           if ((ret = dwarf_read_uleb128 (as, a, addr, &len, arg)) < 0)
 330             goto fail;
 331
 332           Debug (15, "CFA_expression r%lu @ 0x%lx [%lu bytes]\n",
 333                  (long) regnum, (long) addr, (long) len);
 334           *addr += len;
 335           break;
 336
 337         case DW_CFA_val_expression:
 338           if ((ret = read_regnum (as, a, addr, &regnum, arg)) < 0)
 339             goto fail;
 340
 341           /* Save the address of the DW_FORM_block for later evaluation. */
 342           set_reg (sr, regnum, DWARF_WHERE_VAL_EXPR, *addr);
 343
 344           if ((ret = dwarf_read_uleb128 (as, a, addr, &len, arg)) < 0)
 345             goto fail;
 346
 347           Debug (15, "CFA_val_expression r%lu @ 0x%lx [%lu bytes]\n",
 348                  (long) regnum, (long) addr, (long) len);
 349           *addr += len;
 350           break;
 351
 352         case DW_CFA_GNU_args_size:
 353           if ((ret = dwarf_read_uleb128 (as, a, addr, &val, arg)) < 0)
 354             goto fail;
 355           sr->args_size = val;
 356           Debug (15, "CFA_GNU_args_size %lu\n", (long) val);
 357           break;
 358
 359         case DW_CFA_GNU_negative_offset_extended:
 360           /* A comment in GCC says that this is obsoleted by
 361              DW_CFA_offset_extended_sf, but that it's used by older
 362              PowerPC code.  */
 363           if (((ret = read_regnum (as, a, addr, &regnum, arg)) < 0)
 364               || ((ret = dwarf_read_uleb128 (as, a, addr, &val, arg)) < 0))
 365             goto fail;
 366           set_reg (sr, regnum, DWARF_WHERE_CFAREL, -(val * dci->data_align));
 367           Debug (15, "CFA_GNU_negative_offset_extended cfa+0x%lx\n",
 368                  (long) -(val * dci->data_align));
 369           break;
 370
 371         case DW_CFA_GNU_window_save:
 372 #ifdef UNW_TARGET_SPARC
 373           /* This is a special CFA to handle all 16 windowed registers
 374              on SPARC.  */
 375           for (regnum = 16; regnum < 32; ++regnum)
 376             set_reg (sr, regnum, DWARF_WHERE_CFAREL,
 377                      (regnum - 16) * sizeof (unw_word_t));
 378           Debug (15, "CFA_GNU_window_save\n");
 379           break;
 380 #else
 381           /* FALL THROUGH */
 382 #endif
 383         case DW_CFA_lo_user:
 384         case DW_CFA_hi_user:
 385           Debug (1, "Unexpected CFA opcode 0x%x\n", op);
 386           ret = -UNW_EINVAL;
 387           goto fail;
 388         }
 389     }
 390   ret = 0;
 391
 392  fail:
 393   /* Free the register-state stack, if not empty already.  */
 394   while (rs_stack)
 395     {
 396       old_rs = rs_stack;
 397       rs_stack = rs_stack->next;
 398       free_reg_state (old_rs);
 399     }
 400   return ret;
 401 }
 402
 403 static int
 404 fetch_proc_info (struct dwarf_cursor *c, unw_word_t ip, int need_unwind_info)
 405 {
 406   int ret, dynamic = 1;
 407
 408   /* The 'ip' can point either to the previous or next instruction
 409      depending on what type of frame we have: normal call or a place
 410      to resume execution (e.g. after signal frame).
 411
 412      For a normal call frame we need to back up so we point within the
 413      call itself; this is important because a) the call might be the
 414      very last instruction of the function and the edge of the FDE,
 415      and b) so that run_cfi_program() runs locations up to the call
 416      but not more.
 417
 418      For execution resume, we need to do the exact opposite and look
 419      up using the current 'ip' value.  That is where execution will
 420      continue, and it's important we get this right, as 'ip' could be
 421      right at the function entry and hence FDE edge, or at instruction
 422      that manipulates CFA (push/pop). */
 423   if (c->use_prev_instr)
 424     --ip;
 425
 426   if (c->pi_valid && !need_unwind_info)
 427     return 0;
 428
 429   memset (&c->pi, 0, sizeof (c->pi));
 430
 431   /* check dynamic info first --- it overrides everything else */
 432   ret = unwi_find_dynamic_proc_info (c->as, ip, &c->pi, need_unwind_info,
 433                                      c->as_arg);
 434   if (ret == -UNW_ENOINFO)
 435     {
 436       dynamic = 0;
 437       if ((ret = tdep_find_proc_info (c, ip, need_unwind_info)) < 0)
 438         return ret;
 439     }
 440
 441   if (c->pi.format != UNW_INFO_FORMAT_DYNAMIC
 442       && c->pi.format != UNW_INFO_FORMAT_TABLE
 443       && c->pi.format != UNW_INFO_FORMAT_REMOTE_TABLE)
 444     return -UNW_ENOINFO;
 445
 446   c->pi_valid = 1;
 447   c->pi_is_dynamic = dynamic;
 448
 449   /* Let system/machine-dependent code determine frame-specific attributes. */
 450   if (ret >= 0)
 451     tdep_fetch_frame (c, ip, need_unwind_info);
 452
 453   /* Update use_prev_instr for the next frame. */
 454   if (need_unwind_info)
 455   {
 456     assert(c->pi.unwind_info);
 457     struct dwarf_cie_info *dci = c->pi.unwind_info;
 458     c->use_prev_instr = ! dci->signal_frame;
 459   }
 460
 461   return ret;
 462 }
 463
 464 static int
 465 parse_dynamic (struct dwarf_cursor *c, unw_word_t ip, dwarf_state_record_t *sr)
 466 {
 467   Debug (1, "Not yet implemented\n");
 468 #if 0
 469   /* Don't forget to set the ret_addr_column!  */
 470   c->ret_addr_column = XXX;
 471 #endif
 472   return -UNW_ENOINFO;
 473 }
 474
 475 static inline void
 476 put_unwind_info (struct dwarf_cursor *c, unw_proc_info_t *pi)
 477 {
 478   if (c->pi_is_dynamic)
 479     unwi_put_dynamic_unwind_info (c->as, pi, c->as_arg);
 480   else if (pi->unwind_info && pi->format == UNW_INFO_FORMAT_TABLE)
 481     {
 482       mempool_free (&dwarf_cie_info_pool, pi->unwind_info);
 483       pi->unwind_info = NULL;
 484     }
 485 }
 486
 487 static inline int
 488 parse_fde (struct dwarf_cursor *c, unw_word_t ip, dwarf_state_record_t *sr)
 489 {
 490   struct dwarf_cie_info *dci;
 491   unw_word_t addr;
 492   int ret;
 493
 494   dci = c->pi.unwind_info;
 495   c->ret_addr_column = dci->ret_addr_column;
 496
 497   addr = dci->cie_instr_start;
 498   if ((ret = run_cfi_program (c, sr, ~(unw_word_t) 0, &addr,
 499                               dci->cie_instr_end, dci)) < 0)
 500     return ret;
 501
 502   memcpy (&sr->rs_initial, &sr->rs_current, sizeof (sr->rs_initial));
 503
 504   addr = dci->fde_instr_start;
 505   if ((ret = run_cfi_program (c, sr, ip, &addr, dci->fde_instr_end, dci)) < 0)
 506     return ret;
 507
 508   return 0;
 509 }
 510
 511 static inline void
 512 flush_rs_cache (struct dwarf_rs_cache *cache)
 513 {
 514   int i;
 515
 516   cache->lru_head = DWARF_UNW_CACHE_SIZE - 1;
 517   cache->lru_tail = 0;
 518
 519   for (i = 0; i < DWARF_UNW_CACHE_SIZE; ++i)
 520     {
 521       if (i > 0)
 522         cache->buckets[i].lru_chain = (i - 1);
 523       cache->buckets[i].coll_chain = -1;
 524       cache->buckets[i].ip = 0;
 525       cache->buckets[i].valid = 0;
 526     }
 527   for (i = 0; i<DWARF_UNW_HASH_SIZE; ++i)
 528     cache->hash[i] = -1;
 529 }
 530
 531 static inline struct dwarf_rs_cache *
 532 get_rs_cache (unw_addr_space_t as, intrmask_t *saved_maskp)
 533 {
 534   struct dwarf_rs_cache *cache = &as->global_cache;
 535   unw_caching_policy_t caching = as->caching_policy;
 536
 537   if (caching == UNW_CACHE_NONE)
 538     return NULL;
 539
 540   if (likely (caching == UNW_CACHE_GLOBAL))
 541     {
 542       Debug (16, "acquiring lock\n");
 543       lock_acquire (&cache->lock, *saved_maskp);
 544     }
 545
 546   if (atomic_read (&as->cache_generation) != atomic_read (&cache->generation))
 547     {
 548       flush_rs_cache (cache);
 549       cache->generation = as->cache_generation;
 550     }
 551
 552   return cache;
 553 }
 554
 555 static inline void
 556 put_rs_cache (unw_addr_space_t as, struct dwarf_rs_cache *cache,
 557                   intrmask_t *saved_maskp)
 558 {
 559   assert (as->caching_policy != UNW_CACHE_NONE);
 560
 561   Debug (16, "unmasking signals/interrupts and releasing lock\n");
 562   if (likely (as->caching_policy == UNW_CACHE_GLOBAL))
 563     lock_release (&cache->lock, *saved_maskp);
 564 }
 565
 566 static inline unw_hash_index_t CONST_ATTR
 567 hash (unw_word_t ip)
 568 {
 569   /* based on (sqrt(5)/2-1)*2^64 */
 570 # define magic  ((unw_word_t) 0x9e3779b97f4a7c16ULL)
 571
 572   return ip * magic >> ((sizeof(unw_word_t) * 8) - DWARF_LOG_UNW_HASH_SIZE);
 573 }
 574
 575 static inline long
 576 cache_match (dwarf_reg_state_t *rs, unw_word_t ip)
 577 {
 578   if (rs->valid && (ip == rs->ip))
 579     return 1;
 580   return 0;
 581 }
 582
 583 static dwarf_reg_state_t *
 584 rs_lookup (struct dwarf_rs_cache *cache, struct dwarf_cursor *c)
 585 {
 586   dwarf_reg_state_t *rs = cache->buckets + c->hint;
 587   unsigned short index;
 588   unw_word_t ip;
 589
 590   ip = c->ip;
 591
 592   if (cache_match (rs, ip))
 593     return rs;
 594
 595   index = cache->hash[hash (ip)];
 596   if (index >= DWARF_UNW_CACHE_SIZE)
 597     return NULL;
 598
 599   rs = cache->buckets + index;
 600   while (1)
 601     {
 602       if (cache_match (rs, ip))
 603         {
 604           /* update hint; no locking needed: single-word writes are atomic */
 605           c->hint = cache->buckets[c->prev_rs].hint =
 606             (rs - cache->buckets);
 607           return rs;
 608         }
 609       if (rs->coll_chain >= DWARF_UNW_HASH_SIZE)
 610         return NULL;
 611       rs = cache->buckets + rs->coll_chain;
 612     }
 613 }
 614
 615 static inline dwarf_reg_state_t *
 616 rs_new (struct dwarf_rs_cache *cache, struct dwarf_cursor * c)
 617 {
 618   dwarf_reg_state_t *rs, *prev, *tmp;
 619   unw_hash_index_t index;
 620   unsigned short head;
 621
 622   head = cache->lru_head;
 623   rs = cache->buckets + head;
 624   cache->lru_head = rs->lru_chain;
 625
 626   /* re-insert rs at the tail of the LRU chain: */
 627   cache->buckets[cache->lru_tail].lru_chain = head;
 628   cache->lru_tail = head;
 629
 630   /* remove the old rs from the hash table (if it's there): */
 631   if (rs->ip)
 632     {
 633       index = hash (rs->ip);
 634       tmp = cache->buckets + cache->hash[index];
 635       prev = NULL;
 636       while (1)
 637         {
 638           if (tmp == rs)
 639             {
 640               if (prev)
 641                 prev->coll_chain = tmp->coll_chain;
 642               else
 643                 cache->hash[index] = tmp->coll_chain;
 644               break;
 645             }
 646           else
 647             prev = tmp;
 648           if (tmp->coll_chain >= DWARF_UNW_CACHE_SIZE)
 649             /* old rs wasn't in the hash-table */
 650             break;
 651           tmp = cache->buckets + tmp->coll_chain;
 652         }
 653     }
 654
 655   /* enter new rs in the hash table */
 656   index = hash (c->ip);
 657   rs->coll_chain = cache->hash[index];
 658   cache->hash[index] = rs - cache->buckets;
 659
 660   rs->hint = 0;
 661   rs->ip = c->ip;
 662   rs->valid = 1;
 663   rs->ret_addr_column = c->ret_addr_column;
 664   rs->signal_frame = 0;
 665   tdep_cache_frame (c, rs);
 666
 667   return rs;
 668 }
 669
 670 static int
 671 create_state_record_for (struct dwarf_cursor *c, dwarf_state_record_t *sr,
 672                          unw_word_t ip)
 673 {
 674   int i, ret;
 675
 676   assert (c->pi_valid);
 677
 678   memset (sr, 0, sizeof (*sr));
 679   for (i = 0; i < DWARF_NUM_PRESERVED_REGS + 2; ++i)
 680     set_reg (sr, i, DWARF_WHERE_SAME, 0);
 681
 682   switch (c->pi.format)
 683     {
 684     case UNW_INFO_FORMAT_TABLE:
 685     case UNW_INFO_FORMAT_REMOTE_TABLE:
 686       ret = parse_fde (c, ip, sr);
 687       break;
 688
 689     case UNW_INFO_FORMAT_DYNAMIC:
 690       ret = parse_dynamic (c, ip, sr);
 691       break;
 692
 693     default:
 694       Debug (1, "Unexpected unwind-info format %d\n", c->pi.format);
 695       ret = -UNW_EINVAL;
 696     }
 697   return ret;
 698 }
 699
 700 static inline int
 701 eval_location_expr (struct dwarf_cursor *c, unw_addr_space_t as,
 702                     unw_accessors_t *a, unw_word_t addr,
 703                     dwarf_loc_t *locp, void *arg)
 704 {
 705   int ret, is_register;
 706   unw_word_t len, val;
 707
 708   /* read the length of the expression: */
 709   if ((ret = dwarf_read_uleb128 (as, a, &addr, &len, arg)) < 0)
 710     return ret;
 711
 712   /* evaluate the expression: */
 713   if ((ret = dwarf_eval_expr (c, &addr, len, &val, &is_register)) < 0)
 714     return ret;
 715
 716   if (is_register)
 717     *locp = DWARF_REG_LOC (c, dwarf_to_unw_regnum (val));
 718   else
 719     *locp = DWARF_MEM_LOC (c, val);
 720
 721   return 0;
 722 }
 723
 724 static int
 725 apply_reg_state (struct dwarf_cursor *c, struct dwarf_reg_state *rs)
 726 {
 727   unw_word_t regnum, addr, cfa, ip;
 728   unw_word_t prev_ip, prev_cfa;
 729   unw_addr_space_t as;
 730   dwarf_loc_t cfa_loc;
 731   unw_accessors_t *a;
 732   int i, ret;
 733   void *arg;
 734
 735   prev_ip = c->ip;
 736   prev_cfa = c->cfa;
 737
 738   as = c->as;
 739   arg = c->as_arg;
 740   a = unw_get_accessors (as);
 741
 742   /* Evaluate the CFA first, because it may be referred to by other
 743      expressions.  */
 744
 745   if (rs->reg[DWARF_CFA_REG_COLUMN].where == DWARF_WHERE_REG)
 746     {
 747       /* CFA is equal to [reg] + offset: */
 748
 749       /* As a special-case, if the stack-pointer is the CFA and the
 750          stack-pointer wasn't saved, popping the CFA implicitly pops
 751          the stack-pointer as well.  */
 752       if ((rs->reg[DWARF_CFA_REG_COLUMN].val == UNW_TDEP_SP)
 753           && (UNW_TDEP_SP < ARRAY_SIZE(rs->reg))
 754           && (rs->reg[UNW_TDEP_SP].where == DWARF_WHERE_SAME))
 755           cfa = c->cfa;
 756       else
 757         {
 758           regnum = dwarf_to_unw_regnum (rs->reg[DWARF_CFA_REG_COLUMN].val);
 759           if ((ret = unw_get_reg ((unw_cursor_t *) c, regnum, &cfa)) < 0)
 760             return ret;
 761         }
 762       cfa += rs->reg[DWARF_CFA_OFF_COLUMN].val;
 763     }
 764   else
 765     {
 766       /* CFA is equal to EXPR: */
 767
 768       assert (rs->reg[DWARF_CFA_REG_COLUMN].where == DWARF_WHERE_EXPR);
 769
 770       addr = rs->reg[DWARF_CFA_REG_COLUMN].val;
 771       if ((ret = eval_location_expr (c, as, a, addr, &cfa_loc, arg)) < 0)
 772         return ret;
 773       /* the returned location better be a memory location... */
 774       if (DWARF_IS_REG_LOC (cfa_loc))
 775         return -UNW_EBADFRAME;
 776       cfa = DWARF_GET_LOC (cfa_loc);
 777     }
 778
 779   for (i = 0; i < DWARF_NUM_PRESERVED_REGS; ++i)
 780     {
 781       switch ((dwarf_where_t) rs->reg[i].where)
 782         {
 783         case DWARF_WHERE_UNDEF:
 784           c->loc[i] = DWARF_NULL_LOC;
 785           break;
 786
 787         case DWARF_WHERE_SAME:
 788           break;
 789
 790         case DWARF_WHERE_CFAREL:
 791           c->loc[i] = DWARF_MEM_LOC (c, cfa + rs->reg[i].val);
 792           break;
 793
 794         case DWARF_WHERE_REG:
 795           c->loc[i] = DWARF_REG_LOC (c, dwarf_to_unw_regnum (rs->reg[i].val));
 796           break;
 797
 798         case DWARF_WHERE_EXPR:
 799           addr = rs->reg[i].val;
 800           if ((ret = eval_location_expr (c, as, a, addr, c->loc + i, arg)) < 0)
 801             return ret;
 802           break;
 803
 804         case DWARF_WHERE_VAL_EXPR:
 805           addr = rs->reg[i].val;
 806           if ((ret = eval_location_expr (c, as, a, addr, c->loc + i, arg)) < 0)
 807             return ret;
 808           c->loc[i] = DWARF_VAL_LOC (c, DWARF_GET_LOC (c->loc[i]));
 809           break;
 810         }
 811     }
 812
 813   c->cfa = cfa;
 814   /* DWARF spec says undefined return address location means end of stack. */
 815   if (DWARF_IS_NULL_LOC (c->loc[c->ret_addr_column]))
 816     c->ip = 0;
 817   else
 818   {
 819     ret = dwarf_get (c, c->loc[c->ret_addr_column], &ip);
 820     if (ret < 0)
 821       return ret;
 822     c->ip = ip;
 823   }
 824
 825   /* XXX: check for ip to be code_aligned */
 826   if (c->ip == prev_ip && c->cfa == prev_cfa)
 827     {
 828       Dprintf ("%s: ip and cfa unchanged; stopping here (ip=0x%lx)\n",
 829                __FUNCTION__, (long) c->ip);
 830       return -UNW_EBADFRAME;
 831     }
 832
 833   if (c->stash_frames)
 834     tdep_stash_frame (c, rs);
 835
 836   return 0;
 837 }
 838
 839 static int
 840 uncached_dwarf_find_save_locs (struct dwarf_cursor *c)
 841 {
 842   dwarf_state_record_t sr;
 843   int ret;
 844
 845   if ((ret = fetch_proc_info (c, c->ip, 1)) < 0)
 846     {
 847       put_unwind_info (c, &c->pi);
 848       return ret;
 849     }
 850
 851   if ((ret = create_state_record_for (c, &sr, c->ip)) < 0)
 852     return ret;
 853
 854   if ((ret = apply_reg_state (c, &sr.rs_current)) < 0)
 855     return ret;
 856
 857   put_unwind_info (c, &c->pi);
 858   return 0;
 859 }
 860
 861 /* The function finds the saved locations and applies the register
 862    state as well. */
 863 HIDDEN int
 864 dwarf_find_save_locs (struct dwarf_cursor *c)
 865 {
 866   dwarf_state_record_t sr;
 867   dwarf_reg_state_t *rs, rs_copy;
 868   struct dwarf_rs_cache *cache;
 869   int ret = 0;
 870   intrmask_t saved_mask;
 871
 872   if (c->as->caching_policy == UNW_CACHE_NONE)
 873     return uncached_dwarf_find_save_locs (c);
 874
 875   cache = get_rs_cache(c->as, &saved_mask);
 876   rs = rs_lookup(cache, c);
 877
 878   if (rs)
 879     {
 880       c->ret_addr_column = rs->ret_addr_column;
 881       c->use_prev_instr = ! rs->signal_frame;
 882     }
 883   else
 884     {
 885       if ((ret = fetch_proc_info (c, c->ip, 1)) < 0 ||
 886           (ret = create_state_record_for (c, &sr, c->ip)) < 0)
 887         {
 888           put_rs_cache (c->as, cache, &saved_mask);
 889           put_unwind_info (c, &c->pi);
 890           return ret;
 891         }
 892
 893       rs = rs_new (cache, c);
 894       memcpy(rs, &sr.rs_current, offsetof(struct dwarf_reg_state, ip));
 895       cache->buckets[c->prev_rs].hint = rs - cache->buckets;
 896
 897       c->hint = rs->hint;
 898       c->prev_rs = rs - cache->buckets;
 899
 900       put_unwind_info (c, &c->pi);
 901     }
 902
 903   memcpy (&rs_copy, rs, sizeof (rs_copy));
 904   put_rs_cache (c->as, cache, &saved_mask);
 905
 906   tdep_reuse_frame (c, &rs_copy);
 907   if ((ret = apply_reg_state (c, &rs_copy)) < 0)
 908     return ret;
 909
 910   return 0;
 911 }
 912
 913 /* The proc-info must be valid for IP before this routine can be
 914    called.  */
 915 HIDDEN int
 916 dwarf_create_state_record (struct dwarf_cursor *c, dwarf_state_record_t *sr)
 917 {
 918   return create_state_record_for (c, sr, c->ip);
 919 }
 920
 921 HIDDEN int
 922 dwarf_make_proc_info (struct dwarf_cursor *c)
 923 {
 924 #if 0
 925   if (c->as->caching_policy == UNW_CACHE_NONE
 926       || get_cached_proc_info (c) < 0)
 927 #endif
 928     /* Lookup it up the slow way... */
 929     return fetch_proc_info (c, c->ip, 0);
 930   return 0;
 931 }