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 "dwarf_i.h"
  27 #include "libunwind_i.h"
  28 #include <stddef.h>
  29 #include <limits.h>
  30
  31 #define alloc_reg_state()       (mempool_alloc (&dwarf_reg_state_pool))
  32 #define free_reg_state(rs)      (mempool_free (&dwarf_reg_state_pool, rs))
  33
  34 #define DWARF_UNW_CACHE_SIZE(log_size)   (1 << log_size)
  35 #define DWARF_UNW_HASH_SIZE(log_size)    (1 << (log_size + 1))
  36
  37 static inline int
  38 read_regnum (unw_addr_space_t as, unw_accessors_t *a, unw_word_t *addr,
  39              unw_word_t *valp, void *arg)
  40 {
  41   int ret;
  42
  43   if ((ret = dwarf_read_uleb128 (as, a, addr, valp, arg)) < 0)
  44     return ret;
  45
  46   if (*valp >= DWARF_NUM_PRESERVED_REGS)
  47     {
  48       Debug (1, "Invalid register number %u\n", (unsigned int) *valp);
  49       return -UNW_EBADREG;
  50     }
  51   return 0;
  52 }
  53
  54 static inline void
  55 set_reg (dwarf_state_record_t *sr, unw_word_t regnum, dwarf_where_t where,
  56          unw_word_t val)
  57 {
  58   sr->rs_current.reg.where[regnum] = where;
  59   sr->rs_current.reg.val[regnum] = val;
  60 }
  61
  62 static inline int
  63 push_rstate_stack(dwarf_stackable_reg_state_t **rs_stack)
  64 {
  65   dwarf_stackable_reg_state_t *old_rs = *rs_stack;
  66   if (NULL == (*rs_stack = alloc_reg_state ()))
  67     {
  68       *rs_stack = old_rs;
  69       return -1;
  70     }
  71   (*rs_stack)->next = old_rs;
  72   return 0;
  73 }
  74
  75 static inline void
  76 pop_rstate_stack(dwarf_stackable_reg_state_t **rs_stack)
  77 {
  78   dwarf_stackable_reg_state_t *old_rs = *rs_stack;
  79   *rs_stack = old_rs->next;
  80   free_reg_state (old_rs);
  81 }
  82
  83 static inline void
  84 empty_rstate_stack(dwarf_stackable_reg_state_t **rs_stack)
  85 {
  86   while (*rs_stack)
  87     pop_rstate_stack(rs_stack);
  88 }
  89
  90 /* Run a CFI program to update the register state.  */
  91 static int
  92 run_cfi_program (struct dwarf_cursor *c, dwarf_state_record_t *sr,
  93                  unw_word_t *ip, unw_word_t end_ip,
  94                  unw_word_t *addr, unw_word_t end_addr,
  95                  dwarf_stackable_reg_state_t **rs_stack,
  96                  struct dwarf_cie_info *dci)
  97 {
  98   unw_addr_space_t as;
  99   void *arg;
 100
 101   if (c->pi.flags & UNW_PI_FLAG_DEBUG_FRAME)
 102     {
 103       /* .debug_frame CFI is stored in local address space.  */
 104       as = unw_local_addr_space;
 105       arg = NULL;
 106     }
 107   else
 108     {
 109       as = c->as;
 110       arg = c->as_arg;
 111     }
 112   unw_accessors_t *a = unw_get_accessors_int (as);
 113   int ret = 0;
 114
 115   while (*ip <= end_ip && *addr < end_addr && ret >= 0)
 116     {
 117       unw_word_t operand = 0, regnum, val, len;
 118       uint8_t u8, op;
 119       uint16_t u16;
 120       uint32_t u32;
 121
 122       if ((ret = dwarf_readu8 (as, a, addr, &op, arg)) < 0)
 123         break;
 124
 125       if (op & DWARF_CFA_OPCODE_MASK)
 126         {
 127           operand = op & DWARF_CFA_OPERAND_MASK;
 128           op &= ~DWARF_CFA_OPERAND_MASK;
 129         }
 130       switch ((dwarf_cfa_t) op)
 131         {
 132         case DW_CFA_advance_loc:
 133           *ip += operand * dci->code_align;
 134           Debug (15, "CFA_advance_loc to 0x%lx\n", (long) *ip);
 135           break;
 136
 137         case DW_CFA_advance_loc1:
 138           if ((ret = dwarf_readu8 (as, a, addr, &u8, arg)) < 0)
 139             break;
 140           *ip += u8 * dci->code_align;
 141           Debug (15, "CFA_advance_loc1 to 0x%lx\n", (long) *ip);
 142           break;
 143
 144         case DW_CFA_advance_loc2:
 145           if ((ret = dwarf_readu16 (as, a, addr, &u16, arg)) < 0)
 146             break;
 147           *ip += u16 * dci->code_align;
 148           Debug (15, "CFA_advance_loc2 to 0x%lx\n", (long) *ip);
 149           break;
 150
 151         case DW_CFA_advance_loc4:
 152           if ((ret = dwarf_readu32 (as, a, addr, &u32, arg)) < 0)
 153             break;
 154           *ip += u32 * dci->code_align;
 155           Debug (15, "CFA_advance_loc4 to 0x%lx\n", (long) *ip);
 156           break;
 157
 158         case DW_CFA_MIPS_advance_loc8:
 159 #ifdef UNW_TARGET_MIPS
 160           {
 161             uint64_t u64 = 0;
 162
 163             if ((ret = dwarf_readu64 (as, a, addr, &u64, arg)) < 0)
 164               break;
 165             *ip += u64 * dci->code_align;
 166             Debug (15, "CFA_MIPS_advance_loc8\n");
 167             break;
 168           }
 169 #else
 170           Debug (1, "DW_CFA_MIPS_advance_loc8 on non-MIPS target\n");
 171           ret = -UNW_EINVAL;
 172           break;
 173 #endif
 174
 175         case DW_CFA_offset:
 176           regnum = operand;
 177           if (regnum >= DWARF_NUM_PRESERVED_REGS)
 178             {
 179               Debug (1, "Invalid register number %u in DW_cfa_OFFSET\n",
 180                      (unsigned int) regnum);
 181               ret = -UNW_EBADREG;
 182               break;
 183             }
 184           if ((ret = dwarf_read_uleb128 (as, a, addr, &val, arg)) < 0)
 185             break;
 186           set_reg (sr, regnum, DWARF_WHERE_CFAREL, val * dci->data_align);
 187           Debug (15, "CFA_offset r%lu at cfa+0x%lx\n",
 188                  (long) regnum, (long) (val * dci->data_align));
 189           break;
 190
 191         case DW_CFA_offset_extended:
 192           if (((ret = read_regnum (as, a, addr, &regnum, arg)) < 0)
 193               || ((ret = dwarf_read_uleb128 (as, a, addr, &val, arg)) < 0))
 194             break;
 195           set_reg (sr, regnum, DWARF_WHERE_CFAREL, val * dci->data_align);
 196           Debug (15, "CFA_offset_extended r%lu at cf+0x%lx\n",
 197                  (long) regnum, (long) (val * dci->data_align));
 198           break;
 199
 200         case DW_CFA_offset_extended_sf:
 201           if (((ret = read_regnum (as, a, addr, &regnum, arg)) < 0)
 202               || ((ret = dwarf_read_sleb128 (as, a, addr, &val, arg)) < 0))
 203             break;
 204           set_reg (sr, regnum, DWARF_WHERE_CFAREL, val * dci->data_align);
 205           Debug (15, "CFA_offset_extended_sf r%lu at cf+0x%lx\n",
 206                  (long) regnum, (long) (val * dci->data_align));
 207           break;
 208
 209         case DW_CFA_restore:
 210           regnum = operand;
 211           if (regnum >= DWARF_NUM_PRESERVED_REGS)
 212             {
 213               Debug (1, "Invalid register number %u in DW_CFA_restore\n",
 214                      (unsigned int) regnum);
 215               ret = -UNW_EINVAL;
 216               break;
 217             }
 218           sr->rs_current.reg.where[regnum] = sr->rs_initial.reg.where[regnum];
 219           sr->rs_current.reg.val[regnum] = sr->rs_initial.reg.val[regnum];
 220           Debug (15, "CFA_restore r%lu\n", (long) regnum);
 221           break;
 222
 223         case DW_CFA_restore_extended:
 224           if ((ret = dwarf_read_uleb128 (as, a, addr, &regnum, arg)) < 0)
 225             break;
 226           if (regnum >= DWARF_NUM_PRESERVED_REGS)
 227             {
 228               Debug (1, "Invalid register number %u in "
 229                      "DW_CFA_restore_extended\n", (unsigned int) regnum);
 230               ret = -UNW_EINVAL;
 231               break;
 232             }
 233           sr->rs_current.reg.where[regnum] = sr->rs_initial.reg.where[regnum];
 234           sr->rs_current.reg.val[regnum] = sr->rs_initial.reg.val[regnum];
 235           Debug (15, "CFA_restore_extended r%lu\n", (long) regnum);
 236           break;
 237
 238         case DW_CFA_nop:
 239           break;
 240
 241         case DW_CFA_set_loc:
 242           if ((ret = dwarf_read_encoded_pointer (as, a, addr, dci->fde_encoding,
 243                                                  &c->pi, ip,
 244                                                  arg)) < 0)
 245             break;
 246           Debug (15, "CFA_set_loc to 0x%lx\n", (long) *ip);
 247           break;
 248
 249         case DW_CFA_undefined:
 250           if ((ret = read_regnum (as, a, addr, &regnum, arg)) < 0)
 251             break;
 252           set_reg (sr, regnum, DWARF_WHERE_UNDEF, 0);
 253           Debug (15, "CFA_undefined r%lu\n", (long) regnum);
 254           break;
 255
 256         case DW_CFA_same_value:
 257           if ((ret = read_regnum (as, a, addr, &regnum, arg)) < 0)
 258             break;
 259           set_reg (sr, regnum, DWARF_WHERE_SAME, 0);
 260           Debug (15, "CFA_same_value r%lu\n", (long) regnum);
 261           break;
 262
 263         case DW_CFA_register:
 264           if (((ret = read_regnum (as, a, addr, &regnum, arg)) < 0)
 265               || ((ret = dwarf_read_uleb128 (as, a, addr, &val, arg)) < 0))
 266             break;
 267           set_reg (sr, regnum, DWARF_WHERE_REG, val);
 268           Debug (15, "CFA_register r%lu to r%lu\n", (long) regnum, (long) val);
 269           break;
 270
 271         case DW_CFA_remember_state:
 272           if (push_rstate_stack(rs_stack) < 0)
 273             {
 274               Debug (1, "Out of memory in DW_CFA_remember_state\n");
 275               ret = -UNW_ENOMEM;
 276               break;
 277             }
 278           (*rs_stack)->state = sr->rs_current;
 279           Debug (15, "CFA_remember_state\n");
 280           break;
 281
 282         case DW_CFA_restore_state:
 283           if (!*rs_stack)
 284             {
 285               Debug (1, "register-state stack underflow\n");
 286               ret = -UNW_EINVAL;
 287               break;
 288             }
 289           sr->rs_current = (*rs_stack)->state;
 290           pop_rstate_stack(rs_stack);
 291           Debug (15, "CFA_restore_state\n");
 292           break;
 293
 294         case DW_CFA_def_cfa:
 295           if (((ret = read_regnum (as, a, addr, &regnum, arg)) < 0)
 296               || ((ret = dwarf_read_uleb128 (as, a, addr, &val, arg)) < 0))
 297             break;
 298           set_reg (sr, DWARF_CFA_REG_COLUMN, DWARF_WHERE_REG, regnum);
 299           set_reg (sr, DWARF_CFA_OFF_COLUMN, 0, val);   /* NOT factored! */
 300           Debug (15, "CFA_def_cfa r%lu+0x%lx\n", (long) regnum, (long) val);
 301           break;
 302
 303         case DW_CFA_def_cfa_sf:
 304           if (((ret = read_regnum (as, a, addr, &regnum, arg)) < 0)
 305               || ((ret = dwarf_read_sleb128 (as, a, addr, &val, arg)) < 0))
 306             break;
 307           set_reg (sr, DWARF_CFA_REG_COLUMN, DWARF_WHERE_REG, regnum);
 308           set_reg (sr, DWARF_CFA_OFF_COLUMN, 0,
 309                    val * dci->data_align);              /* factored! */
 310           Debug (15, "CFA_def_cfa_sf r%lu+0x%lx\n",
 311                  (long) regnum, (long) (val * dci->data_align));
 312           break;
 313
 314         case DW_CFA_def_cfa_register:
 315           if ((ret = read_regnum (as, a, addr, &regnum, arg)) < 0)
 316             break;
 317           set_reg (sr, DWARF_CFA_REG_COLUMN, DWARF_WHERE_REG, regnum);
 318           Debug (15, "CFA_def_cfa_register r%lu\n", (long) regnum);
 319           break;
 320
 321         case DW_CFA_def_cfa_offset:
 322           if ((ret = dwarf_read_uleb128 (as, a, addr, &val, arg)) < 0)
 323             break;
 324           set_reg (sr, DWARF_CFA_OFF_COLUMN, 0, val);   /* NOT factored! */
 325           Debug (15, "CFA_def_cfa_offset 0x%lx\n", (long) val);
 326           break;
 327
 328         case DW_CFA_def_cfa_offset_sf:
 329           if ((ret = dwarf_read_sleb128 (as, a, addr, &val, arg)) < 0)
 330             break;
 331           set_reg (sr, DWARF_CFA_OFF_COLUMN, 0,
 332                    val * dci->data_align);      /* factored! */
 333           Debug (15, "CFA_def_cfa_offset_sf 0x%lx\n",
 334                  (long) (val * dci->data_align));
 335           break;
 336
 337         case DW_CFA_def_cfa_expression:
 338           /* Save the address of the DW_FORM_block for later evaluation. */
 339           set_reg (sr, DWARF_CFA_REG_COLUMN, DWARF_WHERE_EXPR, *addr);
 340
 341           if ((ret = dwarf_read_uleb128 (as, a, addr, &len, arg)) < 0)
 342             break;
 343
 344           Debug (15, "CFA_def_cfa_expr @ 0x%lx [%lu bytes]\n",
 345                  (long) *addr, (long) len);
 346           *addr += len;
 347           break;
 348
 349         case DW_CFA_expression:
 350           if ((ret = read_regnum (as, a, addr, &regnum, arg)) < 0)
 351             break;
 352
 353           /* Save the address of the DW_FORM_block for later evaluation. */
 354           set_reg (sr, regnum, DWARF_WHERE_EXPR, *addr);
 355
 356           if ((ret = dwarf_read_uleb128 (as, a, addr, &len, arg)) < 0)
 357             break;
 358
 359           Debug (15, "CFA_expression r%lu @ 0x%lx [%lu bytes]\n",
 360                  (long) regnum, (long) addr, (long) len);
 361           *addr += len;
 362           break;
 363
 364         case DW_CFA_val_expression:
 365           if ((ret = read_regnum (as, a, addr, &regnum, arg)) < 0)
 366             break;
 367
 368           /* Save the address of the DW_FORM_block for later evaluation. */
 369           set_reg (sr, regnum, DWARF_WHERE_VAL_EXPR, *addr);
 370
 371           if ((ret = dwarf_read_uleb128 (as, a, addr, &len, arg)) < 0)
 372             break;
 373
 374           Debug (15, "CFA_val_expression r%lu @ 0x%lx [%lu bytes]\n",
 375                  (long) regnum, (long) addr, (long) len);
 376           *addr += len;
 377           break;
 378
 379         case DW_CFA_GNU_args_size:
 380           if ((ret = dwarf_read_uleb128 (as, a, addr, &val, arg)) < 0)
 381             break;
 382           sr->args_size = val;
 383           Debug (15, "CFA_GNU_args_size %lu\n", (long) val);
 384           break;
 385
 386         case DW_CFA_GNU_negative_offset_extended:
 387           /* A comment in GCC says that this is obsoleted by
 388              DW_CFA_offset_extended_sf, but that it's used by older
 389              PowerPC code.  */
 390           if (((ret = read_regnum (as, a, addr, &regnum, arg)) < 0)
 391               || ((ret = dwarf_read_uleb128 (as, a, addr, &val, arg)) < 0))
 392             break;
 393           set_reg (sr, regnum, DWARF_WHERE_CFAREL, -(val * dci->data_align));
 394           Debug (15, "CFA_GNU_negative_offset_extended cfa+0x%lx\n",
 395                  (long) -(val * dci->data_align));
 396           break;
 397
 398         case DW_CFA_GNU_window_save:
 399 #ifdef UNW_TARGET_SPARC
 400           /* This is a special CFA to handle all 16 windowed registers
 401              on SPARC.  */
 402           for (regnum = 16; regnum < 32; ++regnum)
 403             set_reg (sr, regnum, DWARF_WHERE_CFAREL,
 404                      (regnum - 16) * sizeof (unw_word_t));
 405           Debug (15, "CFA_GNU_window_save\n");
 406           break;
 407 #else
 408           /* FALL THROUGH */
 409 #endif
 410         case DW_CFA_lo_user:
 411         case DW_CFA_hi_user:
 412           Debug (1, "Unexpected CFA opcode 0x%x\n", op);
 413           ret = -UNW_EINVAL;
 414           break;
 415         }
 416     }
 417
 418   if (ret > 0)
 419     ret = 0;
 420   return ret;
 421 }
 422
 423 static int
 424 fetch_proc_info (struct dwarf_cursor *c, unw_word_t ip)
 425 {
 426   int ret, dynamic = 1;
 427
 428   /* The 'ip' can point either to the previous or next instruction
 429      depending on what type of frame we have: normal call or a place
 430      to resume execution (e.g. after signal frame).
 431
 432      For a normal call frame we need to back up so we point within the
 433      call itself; this is important because a) the call might be the
 434      very last instruction of the function and the edge of the FDE,
 435      and b) so that run_cfi_program() runs locations up to the call
 436      but not more.
 437
 438      For signal frame, we need to do the exact opposite and look
 439      up using the current 'ip' value.  That is where execution will
 440      continue, and it's important we get this right, as 'ip' could be
 441      right at the function entry and hence FDE edge, or at instruction
 442      that manipulates CFA (push/pop). */
 443   if (c->use_prev_instr)
 444     --ip;
 445
 446   memset (&c->pi, 0, sizeof (c->pi));
 447
 448   /* check dynamic info first --- it overrides everything else */
 449   ret = unwi_find_dynamic_proc_info (c->as, ip, &c->pi, 1,
 450                                      c->as_arg);
 451   if (ret == -UNW_ENOINFO)
 452     {
 453       dynamic = 0;
 454       if ((ret = tdep_find_proc_info (c, ip, 1)) < 0)
 455         return ret;
 456     }
 457
 458   if (c->pi.format != UNW_INFO_FORMAT_DYNAMIC
 459       && c->pi.format != UNW_INFO_FORMAT_TABLE
 460       && c->pi.format != UNW_INFO_FORMAT_REMOTE_TABLE)
 461     return -UNW_ENOINFO;
 462
 463   c->pi_valid = 1;
 464   c->pi_is_dynamic = dynamic;
 465
 466   /* Let system/machine-dependent code determine frame-specific attributes. */
 467   if (ret >= 0)
 468     tdep_fetch_frame (c, ip, 1);
 469
 470   return ret;
 471 }
 472
 473 static int
 474 parse_dynamic (struct dwarf_cursor *c, unw_word_t ip, dwarf_state_record_t *sr)
 475 {
 476   Debug (1, "Not yet implemented\n");
 477   return -UNW_ENOINFO;
 478 }
 479
 480 static inline void
 481 put_unwind_info (struct dwarf_cursor *c, unw_proc_info_t *pi)
 482 {
 483   if (c->pi_is_dynamic)
 484     unwi_put_dynamic_unwind_info (c->as, pi, c->as_arg);
 485   else if (pi->unwind_info && pi->format == UNW_INFO_FORMAT_TABLE)
 486     {
 487       mempool_free (&dwarf_cie_info_pool, pi->unwind_info);
 488       pi->unwind_info = NULL;
 489     }
 490   c->pi_valid = 0;
 491 }
 492
 493 static inline int
 494 setup_fde (struct dwarf_cursor *c, dwarf_state_record_t *sr)
 495 {
 496   int i, ret;
 497
 498   assert (c->pi_valid);
 499
 500   memset (sr, 0, sizeof (*sr));
 501   for (i = 0; i < DWARF_NUM_PRESERVED_REGS + 2; ++i)
 502     set_reg (sr, i, DWARF_WHERE_SAME, 0);
 503
 504   struct dwarf_cie_info *dci = c->pi.unwind_info;
 505   sr->rs_current.ret_addr_column  = dci->ret_addr_column;
 506   unw_word_t addr = dci->cie_instr_start;
 507   unw_word_t curr_ip = 0;
 508   dwarf_stackable_reg_state_t *rs_stack = NULL;
 509   ret = run_cfi_program (c, sr, &curr_ip, ~(unw_word_t) 0, &addr,
 510                          dci->cie_instr_end,
 511                          &rs_stack, dci);
 512   empty_rstate_stack(&rs_stack);
 513   if (ret < 0)
 514     return ret;
 515
 516   memcpy (&sr->rs_initial, &sr->rs_current, sizeof (sr->rs_initial));
 517   return 0;
 518 }
 519
 520 static inline int
 521 parse_fde (struct dwarf_cursor *c, unw_word_t ip, dwarf_state_record_t *sr)
 522 {
 523   int ret;
 524   struct dwarf_cie_info *dci = c->pi.unwind_info;
 525   unw_word_t addr = dci->fde_instr_start;
 526   unw_word_t curr_ip = c->pi.start_ip;
 527   dwarf_stackable_reg_state_t *rs_stack = NULL;
 528   /* Process up to current `ip` for signal frame and `ip - 1` for normal call frame
 529      See `c->use_prev_instr` use in `fetch_proc_info` for details. */
 530   ret = run_cfi_program (c, sr, &curr_ip, ip - c->use_prev_instr, &addr, dci->fde_instr_end,
 531                          &rs_stack, dci);
 532   empty_rstate_stack(&rs_stack);
 533   if (ret < 0)
 534     return ret;
 535
 536   return 0;
 537 }
 538
 539 HIDDEN int
 540 dwarf_flush_rs_cache (struct dwarf_rs_cache *cache)
 541 {
 542   int i;
 543
 544   if (cache->log_size == DWARF_DEFAULT_LOG_UNW_CACHE_SIZE
 545       || !cache->hash) {
 546     cache->hash = cache->default_hash;
 547     cache->buckets = cache->default_buckets;
 548     cache->links = cache->default_links;
 549     cache->log_size = DWARF_DEFAULT_LOG_UNW_CACHE_SIZE;
 550   } else {
 551     if (cache->hash && cache->hash != cache->default_hash)
 552       munmap(cache->hash, DWARF_UNW_HASH_SIZE(cache->prev_log_size)
 553                            * sizeof (cache->hash[0]));
 554     if (cache->buckets && cache->buckets != cache->default_buckets)
 555       munmap(cache->buckets, DWARF_UNW_CACHE_SIZE(cache->prev_log_size)
 556                               * sizeof (cache->buckets[0]));
 557     if (cache->links && cache->links != cache->default_links)
 558       munmap(cache->links, DWARF_UNW_CACHE_SIZE(cache->prev_log_size)
 559                               * sizeof (cache->links[0]));
 560     GET_MEMORY(cache->hash, DWARF_UNW_HASH_SIZE(cache->log_size)
 561                              * sizeof (cache->hash[0]));
 562     GET_MEMORY(cache->buckets, DWARF_UNW_CACHE_SIZE(cache->log_size)
 563                                 * sizeof (cache->buckets[0]));
 564     GET_MEMORY(cache->links, DWARF_UNW_CACHE_SIZE(cache->log_size)
 565                                 * sizeof (cache->links[0]));
 566     if (!cache->hash || !cache->buckets || !cache->links)
 567       {
 568         Debug (1, "Unable to allocate cache memory");
 569         return -UNW_ENOMEM;
 570       }
 571     cache->prev_log_size = cache->log_size;
 572   }
 573
 574   cache->rr_head = 0;
 575
 576   for (i = 0; i < DWARF_UNW_CACHE_SIZE(cache->log_size); ++i)
 577     {
 578       cache->links[i].coll_chain = -1;
 579       cache->links[i].ip = 0;
 580       cache->links[i].valid = 0;
 581     }
 582   for (i = 0; i< DWARF_UNW_HASH_SIZE(cache->log_size); ++i)
 583     cache->hash[i] = -1;
 584
 585   return 0;
 586 }
 587
 588 static inline struct dwarf_rs_cache *
 589 get_rs_cache (unw_addr_space_t as, intrmask_t *saved_maskp)
 590 {
 591   struct dwarf_rs_cache *cache = &as->global_cache;
 592   unw_caching_policy_t caching = as->caching_policy;
 593
 594   if (caching == UNW_CACHE_NONE)
 595     return NULL;
 596
 597 #if defined(HAVE___THREAD) && HAVE___THREAD
 598   if (likely (caching == UNW_CACHE_PER_THREAD))
 599     {
 600       static __thread struct dwarf_rs_cache tls_cache __attribute__((tls_model("initial-exec")));
 601       Debug (16, "using TLS cache\n");
 602       cache = &tls_cache;
 603     }
 604   else
 605 #else
 606   if (likely (caching == UNW_CACHE_GLOBAL))
 607 #endif
 608     {
 609       Debug (16, "acquiring lock\n");
 610       lock_acquire (&cache->lock, *saved_maskp);
 611     }
 612
 613   if ((atomic_read (&as->cache_generation) != atomic_read (&cache->generation))
 614        || !cache->hash)
 615     {
 616       /* cache_size is only set in the global_cache, copy it over before flushing */
 617       cache->log_size = as->global_cache.log_size;
 618       if (dwarf_flush_rs_cache (cache) < 0)
 619         return NULL;
 620       cache->generation = as->cache_generation;
 621     }
 622
 623   return cache;
 624 }
 625
 626 static inline void
 627 put_rs_cache (unw_addr_space_t as, struct dwarf_rs_cache *cache,
 628                   intrmask_t *saved_maskp)
 629 {
 630   assert (as->caching_policy != UNW_CACHE_NONE);
 631
 632   Debug (16, "unmasking signals/interrupts and releasing lock\n");
 633   if (likely (as->caching_policy == UNW_CACHE_GLOBAL))
 634     lock_release (&cache->lock, *saved_maskp);
 635 }
 636
 637 static inline unw_hash_index_t CONST_ATTR
 638 hash (unw_word_t ip, unsigned short log_size)
 639 {
 640   /* based on (sqrt(5)/2-1)*2^64 */
 641 # define magic  ((unw_word_t) 0x9e3779b97f4a7c16ULL)
 642
 643   return ip * magic >> ((sizeof(unw_word_t) * 8) - (log_size + 1));
 644 }
 645
 646 static inline long
 647 cache_match (struct dwarf_rs_cache *cache, unsigned short index, unw_word_t ip)
 648 {
 649   return (cache->links[index].valid && (ip == cache->links[index].ip));
 650 }
 651
 652 static dwarf_reg_state_t *
 653 rs_lookup (struct dwarf_rs_cache *cache, struct dwarf_cursor *c)
 654 {
 655   unsigned short index;
 656   unw_word_t ip = c->ip;
 657
 658   if (c->hint > 0)
 659     {
 660       index = c->hint - 1;
 661       if (cache_match (cache, index, ip))
 662         return &cache->buckets[index];
 663     }
 664
 665   for (index = cache->hash[hash (ip, cache->log_size)];
 666        index < DWARF_UNW_CACHE_SIZE(cache->log_size);
 667        index = cache->links[index].coll_chain)
 668     {
 669       if (cache_match (cache, index, ip))
 670         return &cache->buckets[index];
 671     }
 672   return NULL;
 673 }
 674
 675 static inline dwarf_reg_state_t *
 676 rs_new (struct dwarf_rs_cache *cache, struct dwarf_cursor * c)
 677 {
 678   unw_hash_index_t index;
 679   unsigned short head;
 680
 681   head = cache->rr_head;
 682   cache->rr_head = (head + 1) & (DWARF_UNW_CACHE_SIZE(cache->log_size) - 1);
 683
 684   /* remove the old rs from the hash table (if it's there): */
 685   if (cache->links[head].ip)
 686     {
 687       unsigned short *pindex;
 688       for (pindex = &cache->hash[hash (cache->links[head].ip, cache->log_size)];
 689            *pindex < DWARF_UNW_CACHE_SIZE(cache->log_size);
 690            pindex = &cache->links[*pindex].coll_chain)
 691         {
 692           if (*pindex == head)
 693             {
 694               *pindex = cache->links[*pindex].coll_chain;
 695               break;
 696             }
 697         }
 698     }
 699
 700   /* enter new rs in the hash table */
 701   index = hash (c->ip, cache->log_size);
 702   cache->links[head].coll_chain = cache->hash[index];
 703   cache->hash[index] = head;
 704
 705   cache->links[head].ip = c->ip;
 706   cache->links[head].valid = 1;
 707   cache->links[head].signal_frame = tdep_cache_frame(c);
 708   return cache->buckets + head;
 709 }
 710
 711 static int
 712 create_state_record_for (struct dwarf_cursor *c, dwarf_state_record_t *sr,
 713                          unw_word_t ip)
 714 {
 715   int ret;
 716   switch (c->pi.format)
 717     {
 718     case UNW_INFO_FORMAT_TABLE:
 719     case UNW_INFO_FORMAT_REMOTE_TABLE:
 720       if ((ret = setup_fde(c, sr)) < 0)
 721         return ret;
 722       ret = parse_fde (c, ip, sr);
 723       break;
 724
 725     case UNW_INFO_FORMAT_DYNAMIC:
 726       ret = parse_dynamic (c, ip, sr);
 727       break;
 728
 729     default:
 730       Debug (1, "Unexpected unwind-info format %d\n", c->pi.format);
 731       ret = -UNW_EINVAL;
 732     }
 733   return ret;
 734 }
 735
 736 static inline int
 737 eval_location_expr (struct dwarf_cursor *c, unw_addr_space_t as,
 738                     unw_accessors_t *a, unw_word_t addr,
 739                     dwarf_loc_t *locp, void *arg)
 740 {
 741   int ret, is_register;
 742   unw_word_t len, val;
 743
 744   /* read the length of the expression: */
 745   if ((ret = dwarf_read_uleb128 (as, a, &addr, &len, arg)) < 0)
 746     return ret;
 747
 748   /* evaluate the expression: */
 749   if ((ret = dwarf_eval_expr (c, &addr, len, &val, &is_register)) < 0)
 750     return ret;
 751
 752   if (is_register)
 753     *locp = DWARF_REG_LOC (c, dwarf_to_unw_regnum (val));
 754   else
 755     *locp = DWARF_MEM_LOC (c, val);
 756
 757   return 0;
 758 }
 759
 760 static int
 761 apply_reg_state (struct dwarf_cursor *c, struct dwarf_reg_state *rs)
 762 {
 763   unw_word_t regnum, addr, cfa, ip;
 764   unw_word_t prev_ip, prev_cfa;
 765   unw_addr_space_t as;
 766   dwarf_loc_t cfa_loc;
 767   unw_accessors_t *a;
 768   int i, ret;
 769   void *arg;
 770
 771   prev_ip = c->ip;
 772   prev_cfa = c->cfa;
 773
 774   as = c->as;
 775   arg = c->as_arg;
 776   a = unw_get_accessors_int (as);
 777
 778   /* Evaluate the CFA first, because it may be referred to by other
 779      expressions.  */
 780
 781   if (rs->reg.where[DWARF_CFA_REG_COLUMN] == DWARF_WHERE_REG)
 782     {
 783       /* CFA is equal to [reg] + offset: */
 784
 785       /* As a special-case, if the stack-pointer is the CFA and the
 786          stack-pointer wasn't saved, popping the CFA implicitly pops
 787          the stack-pointer as well.  */
 788       if ((rs->reg.val[DWARF_CFA_REG_COLUMN] == UNW_TDEP_SP)
 789           && (UNW_TDEP_SP < ARRAY_SIZE(rs->reg.val))
 790           && (rs->reg.where[UNW_TDEP_SP] == DWARF_WHERE_SAME))
 791           cfa = c->cfa;
 792       else
 793         {
 794           regnum = dwarf_to_unw_regnum (rs->reg.val[DWARF_CFA_REG_COLUMN]);
 795           if ((ret = unw_get_reg ((unw_cursor_t *) c, regnum, &cfa)) < 0)
 796             return ret;
 797         }
 798       cfa += rs->reg.val[DWARF_CFA_OFF_COLUMN];
 799     }
 800   else
 801     {
 802       /* CFA is equal to EXPR: */
 803
 804       assert (rs->reg.where[DWARF_CFA_REG_COLUMN] == DWARF_WHERE_EXPR);
 805
 806       addr = rs->reg.val[DWARF_CFA_REG_COLUMN];
 807       if ((ret = eval_location_expr (c, as, a, addr, &cfa_loc, arg)) < 0)
 808         return ret;
 809       /* the returned location better be a memory location... */
 810       if (DWARF_IS_REG_LOC (cfa_loc))
 811         return -UNW_EBADFRAME;
 812       cfa = DWARF_GET_LOC (cfa_loc);
 813     }
 814
 815   dwarf_loc_t new_loc[DWARF_NUM_PRESERVED_REGS];
 816   memcpy(new_loc, c->loc, sizeof(new_loc));
 817
 818   for (i = 0; i < DWARF_NUM_PRESERVED_REGS; ++i)
 819     {
 820       switch ((dwarf_where_t) rs->reg.where[i])
 821         {
 822         case DWARF_WHERE_UNDEF:
 823           new_loc[i] = DWARF_NULL_LOC;
 824           break;
 825
 826         case DWARF_WHERE_SAME:
 827           break;
 828
 829         case DWARF_WHERE_CFAREL:
 830           new_loc[i] = DWARF_MEM_LOC (c, cfa + rs->reg.val[i]);
 831           break;
 832
 833         case DWARF_WHERE_REG:
 834           new_loc[i] = DWARF_REG_LOC (c, dwarf_to_unw_regnum (rs->reg.val[i]));
 835           break;
 836
 837         case DWARF_WHERE_EXPR:
 838           addr = rs->reg.val[i];
 839           if ((ret = eval_location_expr (c, as, a, addr, new_loc + i, arg)) < 0)
 840             return ret;
 841           break;
 842
 843         case DWARF_WHERE_VAL_EXPR:
 844           addr = rs->reg.val[i];
 845           if ((ret = eval_location_expr (c, as, a, addr, new_loc + i, arg)) < 0)
 846             return ret;
 847           new_loc[i] = DWARF_VAL_LOC (c, DWARF_GET_LOC (new_loc[i]));
 848           break;
 849         }
 850     }
 851
 852   memcpy(c->loc, new_loc, sizeof(new_loc));
 853
 854   c->cfa = cfa;
 855   /* DWARF spec says undefined return address location means end of stack. */
 856   if (DWARF_IS_NULL_LOC (c->loc[rs->ret_addr_column]))
 857     {
 858       c->ip = 0;
 859       ret = 0;
 860     }
 861   else
 862   {
 863     ret = dwarf_get (c, c->loc[rs->ret_addr_column], &ip);
 864     if (ret < 0)
 865       return ret;
 866     c->ip = ip;
 867     ret = 1;
 868   }
 869
 870   /* XXX: check for ip to be code_aligned */
 871   if (c->ip == prev_ip && c->cfa == prev_cfa)
 872     {
 873       Dprintf ("%s: ip and cfa unchanged; stopping here (ip=0x%lx)\n",
 874                __FUNCTION__, (long) c->ip);
 875       return -UNW_EBADFRAME;
 876     }
 877
 878   if (c->stash_frames)
 879     tdep_stash_frame (c, rs);
 880
 881   return ret;
 882 }
 883
 884 /* Find the saved locations. */
 885 static int
 886 find_reg_state (struct dwarf_cursor *c, dwarf_state_record_t *sr)
 887 {
 888   dwarf_reg_state_t *rs;
 889   struct dwarf_rs_cache *cache;
 890   int ret = 0;
 891   intrmask_t saved_mask;
 892
 893   if ((cache = get_rs_cache(c->as, &saved_mask)) &&
 894       (rs = rs_lookup(cache, c)))
 895     {
 896       /* update hint; no locking needed: single-word writes are atomic */
 897       unsigned short index = rs - cache->buckets;
 898       c->use_prev_instr = ! cache->links[index].signal_frame;
 899       memcpy (&sr->rs_current, rs, sizeof (*rs));
 900     }
 901   else
 902     {
 903       ret = fetch_proc_info (c, c->ip);
 904       int next_use_prev_instr = c->use_prev_instr;
 905       if (ret >= 0)
 906         {
 907           /* Update use_prev_instr for the next frame. */
 908           assert(c->pi.unwind_info);
 909           struct dwarf_cie_info *dci = c->pi.unwind_info;
 910           next_use_prev_instr = ! dci->signal_frame;
 911           ret = create_state_record_for (c, sr, c->ip);
 912         }
 913       put_unwind_info (c, &c->pi);
 914       c->use_prev_instr = next_use_prev_instr;
 915
 916       if (cache && ret >= 0)
 917         {
 918           rs = rs_new (cache, c);
 919           cache->links[rs - cache->buckets].hint = 0;
 920           memcpy(rs, &sr->rs_current, sizeof(*rs));
 921         }
 922     }
 923
 924   unsigned short index = -1;
 925   if (cache)
 926     {
 927       put_rs_cache (c->as, cache, &saved_mask);
 928       if (rs)
 929         {
 930           index = rs - cache->buckets;
 931           c->hint = cache->links[index].hint;
 932           cache->links[c->prev_rs].hint = index + 1;
 933           c->prev_rs = index;
 934         }
 935     }
 936   if (ret < 0)
 937       return ret;
 938   if (cache)
 939     tdep_reuse_frame (c, cache->links[index].signal_frame);
 940   return 0;
 941 }
 942
 943 /* The function finds the saved locations and applies the register
 944    state as well. */
 945 HIDDEN int
 946 dwarf_step (struct dwarf_cursor *c)
 947 {
 948   int ret;
 949   dwarf_state_record_t sr;
 950   if ((ret = find_reg_state (c, &sr)) < 0)
 951     return ret;
 952   return apply_reg_state (c, &sr.rs_current);
 953 }
 954
 955 HIDDEN int
 956 dwarf_make_proc_info (struct dwarf_cursor *c)
 957 {
 958 #if 0
 959   if (c->as->caching_policy == UNW_CACHE_NONE
 960       || get_cached_proc_info (c) < 0)
 961 #endif
 962   /* Need to check if current frame contains
 963      args_size, and set cursor appropriately.  Only
 964      needed for unw_resume */
 965   dwarf_state_record_t sr;
 966   int ret;
 967
 968   /* Lookup it up the slow way... */
 969   ret = fetch_proc_info (c, c->ip);
 970   if (ret >= 0)
 971       ret = create_state_record_for (c, &sr, c->ip);
 972   put_unwind_info (c, &c->pi);
 973   if (ret < 0)
 974     return ret;
 975   c->args_size = sr.args_size;
 976
 977   return 0;
 978 }
 979
 980 static int
 981 dwarf_reg_states_dynamic_iterate(struct dwarf_cursor *c,
 982                                  unw_reg_states_callback cb,
 983                                  void *token)
 984 {
 985   Debug (1, "Not yet implemented\n");
 986   return -UNW_ENOINFO;
 987 }
 988
 989 static int
 990 dwarf_reg_states_table_iterate(struct dwarf_cursor *c,
 991                                unw_reg_states_callback cb,
 992                                void *token)
 993 {
 994   dwarf_state_record_t sr;
 995   int ret = setup_fde(c, &sr);
 996   struct dwarf_cie_info *dci = c->pi.unwind_info;
 997   unw_word_t addr = dci->fde_instr_start;
 998   unw_word_t curr_ip = c->pi.start_ip;
 999   dwarf_stackable_reg_state_t *rs_stack = NULL;
1000   while (ret >= 0 && curr_ip < c->pi.end_ip && addr < dci->fde_instr_end)
1001     {
1002       unw_word_t prev_ip = curr_ip;
1003       ret = run_cfi_program (c, &sr, &curr_ip, prev_ip, &addr, dci->fde_instr_end,
1004                              &rs_stack, dci);
1005       if (ret >= 0 && prev_ip < curr_ip)
1006         ret = cb(token, &sr.rs_current, sizeof(sr.rs_current), prev_ip, curr_ip);
1007     }
1008   empty_rstate_stack(&rs_stack);
1009 #if defined(NEED_LAST_IP)
1010   if (ret >= 0 && curr_ip < c->pi.last_ip)
1011     /* report the dead zone after the procedure ends */
1012     ret = cb(token, &sr.rs_current, sizeof(sr.rs_current), curr_ip, c->pi.last_ip);
1013 #else
1014   if (ret >= 0 && curr_ip < c->pi.end_ip)
1015     /* report for whatever is left before procedure end */
1016     ret = cb(token, &sr.rs_current, sizeof(sr.rs_current), curr_ip, c->pi.end_ip);
1017 #endif
1018   return ret;
1019 }
1020
1021 HIDDEN int
1022 dwarf_reg_states_iterate(struct dwarf_cursor *c,
1023                          unw_reg_states_callback cb,
1024                          void *token)
1025 {
1026   int ret = fetch_proc_info (c, c->ip);
1027   int next_use_prev_instr = c->use_prev_instr;
1028   if (ret >= 0)
1029     {
1030       /* Update use_prev_instr for the next frame. */
1031       assert(c->pi.unwind_info);
1032       struct dwarf_cie_info *dci = c->pi.unwind_info;
1033       next_use_prev_instr = ! dci->signal_frame;
1034       switch (c->pi.format)
1035         {
1036         case UNW_INFO_FORMAT_TABLE:
1037         case UNW_INFO_FORMAT_REMOTE_TABLE:
1038           ret = dwarf_reg_states_table_iterate(c, cb, token);
1039           break;
1040
1041         case UNW_INFO_FORMAT_DYNAMIC:
1042           ret = dwarf_reg_states_dynamic_iterate (c, cb, token);
1043           break;
1044
1045         default:
1046           Debug (1, "Unexpected unwind-info format %d\n", c->pi.format);
1047           ret = -UNW_EINVAL;
1048         }
1049     }
1050   put_unwind_info (c, &c->pi);
1051   c->use_prev_instr = next_use_prev_instr;
1052   return ret;
1053 }
1054
1055 HIDDEN int
1056 dwarf_apply_reg_state (struct dwarf_cursor *c, struct dwarf_reg_state *rs)
1057 {
1058   return apply_reg_state(c, rs);
1059 }