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_GNU_args_size:
 338           if ((ret = dwarf_read_uleb128 (as, a, addr, &val, arg)) < 0)
 339             goto fail;
 340           sr->args_size = val;
 341           Debug (15, "CFA_GNU_args_size %lu\n", (long) val);
 342           break;
 343
 344         case DW_CFA_GNU_negative_offset_extended:
 345           /* A comment in GCC says that this is obsoleted by
 346              DW_CFA_offset_extended_sf, but that it's used by older
 347              PowerPC code.  */
 348           if (((ret = read_regnum (as, a, addr, &regnum, arg)) < 0)
 349               || ((ret = dwarf_read_uleb128 (as, a, addr, &val, arg)) < 0))
 350             goto fail;
 351           set_reg (sr, regnum, DWARF_WHERE_CFAREL, -(val * dci->data_align));
 352           Debug (15, "CFA_GNU_negative_offset_extended cfa+0x%lx\n",
 353                  (long) -(val * dci->data_align));
 354           break;
 355
 356         case DW_CFA_GNU_window_save:
 357 #ifdef UNW_TARGET_SPARC
 358           /* This is a special CFA to handle all 16 windowed registers
 359              on SPARC.  */
 360           for (regnum = 16; regnum < 32; ++regnum)
 361             set_reg (sr, regnum, DWARF_WHERE_CFAREL,
 362                      (regnum - 16) * sizeof (unw_word_t));
 363           Debug (15, "CFA_GNU_window_save\n");
 364           break;
 365 #else
 366           /* FALL THROUGH */
 367 #endif
 368         case DW_CFA_lo_user:
 369         case DW_CFA_hi_user:
 370           Debug (1, "Unexpected CFA opcode 0x%x\n", op);
 371           ret = -UNW_EINVAL;
 372           goto fail;
 373         }
 374     }
 375   ret = 0;
 376
 377  fail:
 378   /* Free the register-state stack, if not empty already.  */
 379   while (rs_stack)
 380     {
 381       old_rs = rs_stack;
 382       rs_stack = rs_stack->next;
 383       free_reg_state (old_rs);
 384     }
 385   return ret;
 386 }
 387
 388 static int
 389 fetch_proc_info (struct dwarf_cursor *c, unw_word_t ip, int need_unwind_info)
 390 {
 391   int ret, dynamic = 1;
 392
 393   /* The 'ip' can point either to the previous or next instruction
 394      depending on what type of frame we have: normal call or a place
 395      to resume execution (e.g. after signal frame).
 396
 397      For a normal call frame we need to back up so we point within the
 398      call itself; this is important because a) the call might be the
 399      very last instruction of the function and the edge of the FDE,
 400      and b) so that run_cfi_program() runs locations up to the call
 401      but not more.
 402
 403      For execution resume, we need to do the exact opposite and look
 404      up using the current 'ip' value.  That is where execution will
 405      continue, and it's important we get this right, as 'ip' could be
 406      right at the function entry and hence FDE edge, or at instruction
 407      that manipulates CFA (push/pop). */
 408   if (c->use_prev_instr)
 409     --ip;
 410
 411   if (c->pi_valid && !need_unwind_info)
 412     return 0;
 413
 414   memset (&c->pi, 0, sizeof (c->pi));
 415
 416   /* check dynamic info first --- it overrides everything else */
 417   ret = unwi_find_dynamic_proc_info (c->as, ip, &c->pi, need_unwind_info,
 418                                      c->as_arg);
 419   if (ret == -UNW_ENOINFO)
 420     {
 421       dynamic = 0;
 422       if ((ret = tdep_find_proc_info (c, ip, need_unwind_info)) < 0)
 423         return ret;
 424     }
 425
 426   if (c->pi.format != UNW_INFO_FORMAT_DYNAMIC
 427       && c->pi.format != UNW_INFO_FORMAT_TABLE
 428       && c->pi.format != UNW_INFO_FORMAT_REMOTE_TABLE)
 429     return -UNW_ENOINFO;
 430
 431   c->pi_valid = 1;
 432   c->pi_is_dynamic = dynamic;
 433
 434   /* Let system/machine-dependent code determine frame-specific attributes. */
 435   if (ret >= 0)
 436     tdep_fetch_frame (c, ip, need_unwind_info);
 437
 438   /* Update use_prev_instr for the next frame. */
 439   if (need_unwind_info)
 440   {
 441     assert(c->pi.unwind_info);
 442     struct dwarf_cie_info *dci = c->pi.unwind_info;
 443     c->use_prev_instr = ! dci->signal_frame;
 444   }
 445
 446   return ret;
 447 }
 448
 449 static int
 450 parse_dynamic (struct dwarf_cursor *c, unw_word_t ip, dwarf_state_record_t *sr)
 451 {
 452   Debug (1, "Not yet implemented\n");
 453 #if 0
 454   /* Don't forget to set the ret_addr_column!  */
 455   c->ret_addr_column = XXX;
 456 #endif
 457   return -UNW_ENOINFO;
 458 }
 459
 460 static inline void
 461 put_unwind_info (struct dwarf_cursor *c, unw_proc_info_t *pi)
 462 {
 463   if (!c->pi_valid)
 464     return;
 465
 466   if (c->pi_is_dynamic)
 467     unwi_put_dynamic_unwind_info (c->as, pi, c->as_arg);
 468   else if (pi->unwind_info)
 469     {
 470       mempool_free (&dwarf_cie_info_pool, pi->unwind_info);
 471       pi->unwind_info = NULL;
 472     }
 473 }
 474
 475 static inline int
 476 parse_fde (struct dwarf_cursor *c, unw_word_t ip, dwarf_state_record_t *sr)
 477 {
 478   struct dwarf_cie_info *dci;
 479   unw_word_t addr;
 480   int ret;
 481
 482   dci = c->pi.unwind_info;
 483   c->ret_addr_column = dci->ret_addr_column;
 484
 485   addr = dci->cie_instr_start;
 486   if ((ret = run_cfi_program (c, sr, ~(unw_word_t) 0, &addr,
 487                               dci->cie_instr_end, dci)) < 0)
 488     return ret;
 489
 490   memcpy (&sr->rs_initial, &sr->rs_current, sizeof (sr->rs_initial));
 491
 492   addr = dci->fde_instr_start;
 493   if ((ret = run_cfi_program (c, sr, ip, &addr, dci->fde_instr_end, dci)) < 0)
 494     return ret;
 495
 496   return 0;
 497 }
 498
 499 static inline void
 500 flush_rs_cache (struct dwarf_rs_cache *cache)
 501 {
 502   int i;
 503
 504   cache->lru_head = DWARF_UNW_CACHE_SIZE - 1;
 505   cache->lru_tail = 0;
 506
 507   for (i = 0; i < DWARF_UNW_CACHE_SIZE; ++i)
 508     {
 509       if (i > 0)
 510         cache->buckets[i].lru_chain = (i - 1);
 511       cache->buckets[i].coll_chain = -1;
 512       cache->buckets[i].ip = 0;
 513       cache->buckets[i].valid = 0;
 514     }
 515   for (i = 0; i<DWARF_UNW_HASH_SIZE; ++i)
 516     cache->hash[i] = -1;
 517 }
 518
 519 static inline struct dwarf_rs_cache *
 520 get_rs_cache (unw_addr_space_t as, intrmask_t *saved_maskp)
 521 {
 522   struct dwarf_rs_cache *cache = &as->global_cache;
 523   unw_caching_policy_t caching = as->caching_policy;
 524
 525   if (caching == UNW_CACHE_NONE)
 526     return NULL;
 527
 528   if (likely (caching == UNW_CACHE_GLOBAL))
 529     {
 530       Debug (16, "acquiring lock\n");
 531       lock_acquire (&cache->lock, *saved_maskp);
 532     }
 533
 534   if (atomic_read (&as->cache_generation) != atomic_read (&cache->generation))
 535     {
 536       flush_rs_cache (cache);
 537       cache->generation = as->cache_generation;
 538     }
 539
 540   return cache;
 541 }
 542
 543 static inline void
 544 put_rs_cache (unw_addr_space_t as, struct dwarf_rs_cache *cache,
 545                   intrmask_t *saved_maskp)
 546 {
 547   assert (as->caching_policy != UNW_CACHE_NONE);
 548
 549   Debug (16, "unmasking signals/interrupts and releasing lock\n");
 550   if (likely (as->caching_policy == UNW_CACHE_GLOBAL))
 551     lock_release (&cache->lock, *saved_maskp);
 552 }
 553
 554 static inline unw_hash_index_t CONST_ATTR
 555 hash (unw_word_t ip)
 556 {
 557   /* based on (sqrt(5)/2-1)*2^64 */
 558 # define magic  ((unw_word_t) 0x9e3779b97f4a7c16ULL)
 559
 560   return ip * magic >> ((sizeof(unw_word_t) * 8) - DWARF_LOG_UNW_HASH_SIZE);
 561 }
 562
 563 static inline long
 564 cache_match (dwarf_reg_state_t *rs, unw_word_t ip)
 565 {
 566   if (rs->valid && (ip == rs->ip))
 567     return 1;
 568   return 0;
 569 }
 570
 571 static dwarf_reg_state_t *
 572 rs_lookup (struct dwarf_rs_cache *cache, struct dwarf_cursor *c)
 573 {
 574   dwarf_reg_state_t *rs = cache->buckets + c->hint;
 575   unsigned short index;
 576   unw_word_t ip;
 577
 578   ip = c->ip;
 579
 580   if (cache_match (rs, ip))
 581     return rs;
 582
 583   index = cache->hash[hash (ip)];
 584   if (index >= DWARF_UNW_CACHE_SIZE)
 585     return NULL;
 586
 587   rs = cache->buckets + index;
 588   while (1)
 589     {
 590       if (cache_match (rs, ip))
 591         {
 592           /* update hint; no locking needed: single-word writes are atomic */
 593           c->hint = cache->buckets[c->prev_rs].hint =
 594             (rs - cache->buckets);
 595           return rs;
 596         }
 597       if (rs->coll_chain >= DWARF_UNW_HASH_SIZE)
 598         return NULL;
 599       rs = cache->buckets + rs->coll_chain;
 600     }
 601 }
 602
 603 static inline dwarf_reg_state_t *
 604 rs_new (struct dwarf_rs_cache *cache, struct dwarf_cursor * c)
 605 {
 606   dwarf_reg_state_t *rs, *prev, *tmp;
 607   unw_hash_index_t index;
 608   unsigned short head;
 609
 610   head = cache->lru_head;
 611   rs = cache->buckets + head;
 612   cache->lru_head = rs->lru_chain;
 613
 614   /* re-insert rs at the tail of the LRU chain: */
 615   cache->buckets[cache->lru_tail].lru_chain = head;
 616   cache->lru_tail = head;
 617
 618   /* remove the old rs from the hash table (if it's there): */
 619   if (rs->ip)
 620     {
 621       index = hash (rs->ip);
 622       tmp = cache->buckets + cache->hash[index];
 623       prev = NULL;
 624       while (1)
 625         {
 626           if (tmp == rs)
 627             {
 628               if (prev)
 629                 prev->coll_chain = tmp->coll_chain;
 630               else
 631                 cache->hash[index] = tmp->coll_chain;
 632               break;
 633             }
 634           else
 635             prev = tmp;
 636           if (tmp->coll_chain >= DWARF_UNW_CACHE_SIZE)
 637             /* old rs wasn't in the hash-table */
 638             break;
 639           tmp = cache->buckets + tmp->coll_chain;
 640         }
 641     }
 642
 643   /* enter new rs in the hash table */
 644   index = hash (c->ip);
 645   rs->coll_chain = cache->hash[index];
 646   cache->hash[index] = rs - cache->buckets;
 647
 648   rs->hint = 0;
 649   rs->ip = c->ip;
 650   rs->valid = 1;
 651   rs->ret_addr_column = c->ret_addr_column;
 652   rs->signal_frame = 0;
 653   tdep_cache_frame (c, rs);
 654
 655   return rs;
 656 }
 657
 658 static int
 659 create_state_record_for (struct dwarf_cursor *c, dwarf_state_record_t *sr,
 660                          unw_word_t ip)
 661 {
 662   int i, ret;
 663
 664   assert (c->pi_valid);
 665
 666   memset (sr, 0, sizeof (*sr));
 667   for (i = 0; i < DWARF_NUM_PRESERVED_REGS + 2; ++i)
 668     set_reg (sr, i, DWARF_WHERE_SAME, 0);
 669
 670   switch (c->pi.format)
 671     {
 672     case UNW_INFO_FORMAT_TABLE:
 673     case UNW_INFO_FORMAT_REMOTE_TABLE:
 674       ret = parse_fde (c, ip, sr);
 675       break;
 676
 677     case UNW_INFO_FORMAT_DYNAMIC:
 678       ret = parse_dynamic (c, ip, sr);
 679       break;
 680
 681     default:
 682       Debug (1, "Unexpected unwind-info format %d\n", c->pi.format);
 683       ret = -UNW_EINVAL;
 684     }
 685   return ret;
 686 }
 687
 688 static inline int
 689 eval_location_expr (struct dwarf_cursor *c, unw_addr_space_t as,
 690                     unw_accessors_t *a, unw_word_t addr,
 691                     dwarf_loc_t *locp, void *arg)
 692 {
 693   int ret, is_register;
 694   unw_word_t len, val;
 695
 696   /* read the length of the expression: */
 697   if ((ret = dwarf_read_uleb128 (as, a, &addr, &len, arg)) < 0)
 698     return ret;
 699
 700   /* evaluate the expression: */
 701   if ((ret = dwarf_eval_expr (c, &addr, len, &val, &is_register)) < 0)
 702     return ret;
 703
 704   if (is_register)
 705     *locp = DWARF_REG_LOC (c, dwarf_to_unw_regnum (val));
 706   else
 707     *locp = DWARF_MEM_LOC (c, val);
 708
 709   return 0;
 710 }
 711
 712 static int
 713 apply_reg_state (struct dwarf_cursor *c, struct dwarf_reg_state *rs)
 714 {
 715   unw_word_t regnum, addr, cfa, ip;
 716   unw_word_t prev_ip, prev_cfa;
 717   unw_addr_space_t as;
 718   dwarf_loc_t cfa_loc;
 719   unw_accessors_t *a;
 720   int i, ret;
 721   void *arg;
 722
 723   prev_ip = c->ip;
 724   prev_cfa = c->cfa;
 725
 726   as = c->as;
 727   arg = c->as_arg;
 728   a = unw_get_accessors (as);
 729
 730   /* Evaluate the CFA first, because it may be referred to by other
 731      expressions.  */
 732
 733   if (rs->reg[DWARF_CFA_REG_COLUMN].where == DWARF_WHERE_REG)
 734     {
 735       /* CFA is equal to [reg] + offset: */
 736
 737       /* As a special-case, if the stack-pointer is the CFA and the
 738          stack-pointer wasn't saved, popping the CFA implicitly pops
 739          the stack-pointer as well.  */
 740       if ((rs->reg[DWARF_CFA_REG_COLUMN].val == UNW_TDEP_SP)
 741           && (UNW_TDEP_SP < ARRAY_SIZE(rs->reg))
 742           && (rs->reg[UNW_TDEP_SP].where == DWARF_WHERE_SAME))
 743           cfa = c->cfa;
 744       else
 745         {
 746           regnum = dwarf_to_unw_regnum (rs->reg[DWARF_CFA_REG_COLUMN].val);
 747           if ((ret = unw_get_reg ((unw_cursor_t *) c, regnum, &cfa)) < 0)
 748             return ret;
 749         }
 750       cfa += rs->reg[DWARF_CFA_OFF_COLUMN].val;
 751     }
 752   else
 753     {
 754       /* CFA is equal to EXPR: */
 755
 756       assert (rs->reg[DWARF_CFA_REG_COLUMN].where == DWARF_WHERE_EXPR);
 757
 758       addr = rs->reg[DWARF_CFA_REG_COLUMN].val;
 759       if ((ret = eval_location_expr (c, as, a, addr, &cfa_loc, arg)) < 0)
 760         return ret;
 761       /* the returned location better be a memory location... */
 762       if (DWARF_IS_REG_LOC (cfa_loc))
 763         return -UNW_EBADFRAME;
 764       cfa = DWARF_GET_LOC (cfa_loc);
 765     }
 766
 767   for (i = 0; i < DWARF_NUM_PRESERVED_REGS; ++i)
 768     {
 769       switch ((dwarf_where_t) rs->reg[i].where)
 770         {
 771         case DWARF_WHERE_UNDEF:
 772           c->loc[i] = DWARF_NULL_LOC;
 773           break;
 774
 775         case DWARF_WHERE_SAME:
 776           break;
 777
 778         case DWARF_WHERE_CFAREL:
 779           c->loc[i] = DWARF_MEM_LOC (c, cfa + rs->reg[i].val);
 780           break;
 781
 782         case DWARF_WHERE_REG:
 783           c->loc[i] = DWARF_REG_LOC (c, dwarf_to_unw_regnum (rs->reg[i].val));
 784           break;
 785
 786         case DWARF_WHERE_EXPR:
 787           addr = rs->reg[i].val;
 788           if ((ret = eval_location_expr (c, as, a, addr, c->loc + i, arg)) < 0)
 789             return ret;
 790           break;
 791         }
 792     }
 793
 794   c->cfa = cfa;
 795   /* DWARF spec says undefined return address location means end of stack. */
 796   if (DWARF_IS_NULL_LOC (c->loc[c->ret_addr_column]))
 797     c->ip = 0;
 798   else
 799   {
 800     ret = dwarf_get (c, c->loc[c->ret_addr_column], &ip);
 801     if (ret < 0)
 802       return ret;
 803     c->ip = ip;
 804   }
 805
 806   /* XXX: check for ip to be code_aligned */
 807   if (c->ip == prev_ip && c->cfa == prev_cfa)
 808     {
 809       Dprintf ("%s: ip and cfa unchanged; stopping here (ip=0x%lx)\n",
 810                __FUNCTION__, (long) c->ip);
 811       return -UNW_EBADFRAME;
 812     }
 813
 814   if (c->stash_frames)
 815     tdep_stash_frame (c, rs);
 816
 817   return 0;
 818 }
 819
 820 static int
 821 uncached_dwarf_find_save_locs (struct dwarf_cursor *c)
 822 {
 823   dwarf_state_record_t sr;
 824   int ret;
 825
 826   if ((ret = fetch_proc_info (c, c->ip, 1)) < 0)
 827     return ret;
 828
 829   if ((ret = create_state_record_for (c, &sr, c->ip)) < 0)
 830     return ret;
 831
 832   if ((ret = apply_reg_state (c, &sr.rs_current)) < 0)
 833     return ret;
 834
 835   put_unwind_info (c, &c->pi);
 836   return 0;
 837 }
 838
 839 /* The function finds the saved locations and applies the register
 840    state as well. */
 841 HIDDEN int
 842 dwarf_find_save_locs (struct dwarf_cursor *c)
 843 {
 844   dwarf_state_record_t sr;
 845   dwarf_reg_state_t *rs, rs_copy;
 846   struct dwarf_rs_cache *cache;
 847   int ret = 0;
 848   intrmask_t saved_mask;
 849
 850   if (c->as->caching_policy == UNW_CACHE_NONE)
 851     return uncached_dwarf_find_save_locs (c);
 852
 853   cache = get_rs_cache(c->as, &saved_mask);
 854   rs = rs_lookup(cache, c);
 855
 856   if (rs)
 857     {
 858       c->ret_addr_column = rs->ret_addr_column;
 859       c->use_prev_instr = ! rs->signal_frame;
 860     }
 861   else
 862     {
 863       if ((ret = fetch_proc_info (c, c->ip, 1)) < 0 ||
 864           (ret = create_state_record_for (c, &sr, c->ip)) < 0)
 865         {
 866           put_rs_cache (c->as, cache, &saved_mask);
 867           return ret;
 868         }
 869
 870       rs = rs_new (cache, c);
 871       memcpy(rs, &sr.rs_current, offsetof(struct dwarf_reg_state, ip));
 872       cache->buckets[c->prev_rs].hint = rs - cache->buckets;
 873
 874       c->hint = rs->hint;
 875       c->prev_rs = rs - cache->buckets;
 876
 877       put_unwind_info (c, &c->pi);
 878     }
 879
 880   memcpy (&rs_copy, rs, sizeof (rs_copy));
 881   put_rs_cache (c->as, cache, &saved_mask);
 882
 883   tdep_reuse_frame (c, &rs_copy);
 884   if ((ret = apply_reg_state (c, &rs_copy)) < 0)
 885     return ret;
 886
 887   return 0;
 888 }
 889
 890 /* The proc-info must be valid for IP before this routine can be
 891    called.  */
 892 HIDDEN int
 893 dwarf_create_state_record (struct dwarf_cursor *c, dwarf_state_record_t *sr)
 894 {
 895   return create_state_record_for (c, sr, c->ip);
 896 }
 897
 898 HIDDEN int
 899 dwarf_make_proc_info (struct dwarf_cursor *c)
 900 {
 901 #if 0
 902   if (c->as->caching_policy == UNW_CACHE_NONE
 903       || get_cached_proc_info (c) < 0)
 904 #endif
 905     /* Lookup it up the slow way... */
 906     return fetch_proc_info (c, c->ip, 0);
 907   return 0;
 908 }