libdw/cfi.c

   1 /* CFI program execution.
   2    Copyright (C) 2009-2010 Red Hat, Inc.
   3    This file is part of elfutils.
   4
   5    This file is free software; you can redistribute it and/or modify
   6    it under the terms of either
   7
   8      * the GNU Lesser General Public License as published by the Free
   9        Software Foundation; either version 3 of the License, or (at
  10        your option) any later version
  11
  12    or
  13
  14      * the GNU General Public License as published by the Free
  15        Software Foundation; either version 2 of the License, or (at
  16        your option) any later version
  17
  18    or both in parallel, as here.
  19
  20    elfutils is distributed in the hope that it will be useful, but
  21    WITHOUT ANY WARRANTY; without even the implied warranty of
  22    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  23    General Public License for more details.
  24
  25    You should have received copies of the GNU General Public License and
  26    the GNU Lesser General Public License along with this program.  If
  27    not, see <http://www.gnu.org/licenses/>.  */
  28
  29 #ifdef HAVE_CONFIG_H
  30 # include <config.h>
  31 #endif
  32
  33 #include <dwarf.h>
  34 #include "../libebl/libebl.h"
  35 #include "cfi.h"
  36 #include "memory-access.h"
  37 #include "encoded-value.h"
  38 #include "system.h"
  39 #include <assert.h>
  40 #include <stdlib.h>
  41 #include <string.h>
  42
  43 #define CFI_PRIMARY_MAX 0x3f
  44
  45 static Dwarf_Frame *
  46 duplicate_frame_state (const Dwarf_Frame *original,
  47                        Dwarf_Frame *prev)
  48 {
  49   size_t size = offsetof (Dwarf_Frame, regs[original->nregs]);
  50   Dwarf_Frame *copy = malloc (size);
  51   if (likely (copy != NULL))
  52     {
  53       memcpy (copy, original, size);
  54       copy->prev = prev;
  55     }
  56   return copy;
  57 }
  58
  59 /* Returns a DWARF_E_* error code, usually NOERROR or INVALID_CFI.
  60    Frees *STATE on failure.  */
  61 static int
  62 execute_cfi (Dwarf_CFI *cache,
  63              const struct dwarf_cie *cie,
  64              Dwarf_Frame **state,
  65              const uint8_t *program, const uint8_t *const end, bool abi_cfi,
  66              Dwarf_Addr loc, Dwarf_Addr find_pc)
  67 {
  68   /* The caller should not give us anything out of range.  */
  69   assert (loc <= find_pc);
  70
  71   int result = DWARF_E_NOERROR;
  72
  73 #define cfi_assert(ok) do {                                                   \
  74     if (likely (ok)) break;                                                   \
  75     result = DWARF_E_INVALID_CFI;                                             \
  76     goto out;                                                                 \
  77   } while (0)
  78
  79   Dwarf_Frame *fs = *state;
  80   inline bool enough_registers (Dwarf_Word reg)
  81     {
  82       if (fs->nregs <= reg)
  83         {
  84           size_t size = offsetof (Dwarf_Frame, regs[reg + 1]);
  85           Dwarf_Frame *bigger = realloc (fs, size);
  86           if (unlikely (bigger == NULL))
  87             {
  88               result = DWARF_E_NOMEM;
  89               return false;
  90             }
  91           else
  92             {
  93               eu_static_assert (reg_unspecified == 0);
  94               memset (bigger->regs + bigger->nregs, 0,
  95                       (reg + 1 - bigger->nregs) * sizeof bigger->regs[0]);
  96               bigger->nregs = reg + 1;
  97               fs = bigger;
  98             }
  99         }
 100       return true;
 101     }
 102
 103   inline void require_cfa_offset (void)
 104   {
 105     if (unlikely (fs->cfa_rule != cfa_offset))
 106       fs->cfa_rule = cfa_invalid;
 107   }
 108
 109 #define register_rule(regno, r_rule, r_value) do {      \
 110     if (unlikely (! enough_registers (regno)))          \
 111       goto out;                                         \
 112     fs->regs[regno].rule = reg_##r_rule;                \
 113     fs->regs[regno].value = (r_value);                  \
 114   } while (0)
 115
 116   while (program < end)
 117     {
 118       uint8_t opcode = *program++;
 119       Dwarf_Word regno;
 120       Dwarf_Word offset;
 121       Dwarf_Word sf_offset;
 122       Dwarf_Word operand = opcode & CFI_PRIMARY_MAX;
 123       switch (opcode)
 124         {
 125           /* These cases move LOC, i.e. "create a new table row".  */
 126
 127         case DW_CFA_advance_loc1:
 128           operand = *program++;
 129         case DW_CFA_advance_loc + 0 ... DW_CFA_advance_loc + CFI_PRIMARY_MAX:
 130         advance_loc:
 131           loc += operand * cie->code_alignment_factor;
 132           break;
 133
 134         case DW_CFA_advance_loc2:
 135           operand = read_2ubyte_unaligned_inc (cache, program);
 136           goto advance_loc;
 137         case DW_CFA_advance_loc4:
 138           operand = read_4ubyte_unaligned_inc (cache, program);
 139           goto advance_loc;
 140         case DW_CFA_MIPS_advance_loc8:
 141           operand = read_8ubyte_unaligned_inc (cache, program);
 142           goto advance_loc;
 143
 144         case DW_CFA_set_loc:
 145           if (likely (!read_encoded_value (cache, cie->fde_encoding,
 146                                            &program, &loc)))
 147             break;
 148           result = INTUSE(dwarf_errno) ();
 149           goto out;
 150
 151           /* Now all following cases affect this row, but do not touch LOC.
 152              These cases end with 'continue'.  We only get out of the
 153              switch block for the row-copying (LOC-moving) cases above.  */
 154
 155         case DW_CFA_def_cfa:
 156           get_uleb128 (operand, program);
 157           get_uleb128 (offset, program);
 158         def_cfa:
 159           fs->cfa_rule = cfa_offset;
 160           fs->cfa_val_reg = operand;
 161           fs->cfa_val_offset = offset;
 162           /* Prime the rest of the Dwarf_Op so dwarf_frame_cfa can use it.  */
 163           fs->cfa_data.offset.atom = DW_OP_bregx;
 164           fs->cfa_data.offset.offset = 0;
 165           continue;
 166
 167         case DW_CFA_def_cfa_register:
 168           get_uleb128 (regno, program);
 169           require_cfa_offset ();
 170           fs->cfa_val_reg = regno;
 171           continue;
 172
 173         case DW_CFA_def_cfa_sf:
 174           get_uleb128 (operand, program);
 175           get_sleb128 (sf_offset, program);
 176           offset = sf_offset * cie->data_alignment_factor;
 177           goto def_cfa;
 178
 179         case DW_CFA_def_cfa_offset:
 180           get_uleb128 (offset, program);
 181         def_cfa_offset:
 182           require_cfa_offset ();
 183           fs->cfa_val_offset = offset;
 184           continue;
 185
 186         case DW_CFA_def_cfa_offset_sf:
 187           get_sleb128 (sf_offset, program);
 188           offset = sf_offset * cie->data_alignment_factor;
 189           goto def_cfa_offset;
 190
 191         case DW_CFA_def_cfa_expression:
 192           /* DW_FORM_block is a ULEB128 length followed by that many bytes.  */
 193           get_uleb128 (operand, program);
 194           cfi_assert (operand <= (Dwarf_Word) (end - program));
 195           fs->cfa_rule = cfa_expr;
 196           fs->cfa_data.expr.data = (unsigned char *) program;
 197           fs->cfa_data.expr.length = operand;
 198           program += operand;
 199           continue;
 200
 201         case DW_CFA_undefined:
 202           get_uleb128 (regno, program);
 203           register_rule (regno, undefined, 0);
 204           continue;
 205
 206         case DW_CFA_same_value:
 207           get_uleb128 (regno, program);
 208           register_rule (regno, same_value, 0);
 209           continue;
 210
 211         case DW_CFA_offset_extended:
 212           get_uleb128 (operand, program);
 213         case DW_CFA_offset + 0 ... DW_CFA_offset + CFI_PRIMARY_MAX:
 214           get_uleb128 (offset, program);
 215           offset *= cie->data_alignment_factor;
 216         offset_extended:
 217           register_rule (operand, offset, offset);
 218           continue;
 219
 220         case DW_CFA_offset_extended_sf:
 221           get_uleb128 (operand, program);
 222           get_sleb128 (sf_offset, program);
 223         offset_extended_sf:
 224           offset = sf_offset * cie->data_alignment_factor;
 225           goto offset_extended;
 226
 227         case DW_CFA_GNU_negative_offset_extended:
 228           /* GNU extension obsoleted by DW_CFA_offset_extended_sf.  */
 229           get_uleb128 (operand, program);
 230           get_uleb128 (offset, program);
 231           sf_offset = -offset;
 232           goto offset_extended_sf;
 233
 234         case DW_CFA_val_offset:
 235           get_uleb128 (operand, program);
 236           get_uleb128 (offset, program);
 237           offset *= cie->data_alignment_factor;
 238         val_offset:
 239           register_rule (operand, val_offset, offset);
 240           continue;
 241
 242         case DW_CFA_val_offset_sf:
 243           get_uleb128 (operand, program);
 244           get_sleb128 (sf_offset, program);
 245           offset = sf_offset * cie->data_alignment_factor;
 246           goto val_offset;
 247
 248         case DW_CFA_register:
 249           get_uleb128 (regno, program);
 250           get_uleb128 (operand, program);
 251           register_rule (regno, register, operand);
 252           continue;
 253
 254         case DW_CFA_expression:
 255           /* Expression rule relies on section data, abi_cfi cannot use it.  */
 256           assert (! abi_cfi);
 257           get_uleb128 (regno, program);
 258           offset = program - (const uint8_t *) cache->data->d.d_buf;
 259           /* DW_FORM_block is a ULEB128 length followed by that many bytes.  */
 260           get_uleb128 (operand, program);
 261           cfi_assert (operand <= (Dwarf_Word) (end - program));
 262           program += operand;
 263           register_rule (regno, expression, offset);
 264           continue;
 265
 266         case DW_CFA_val_expression:
 267           /* Expression rule relies on section data, abi_cfi cannot use it.  */
 268           assert (! abi_cfi);
 269           get_uleb128 (regno, program);
 270           /* DW_FORM_block is a ULEB128 length followed by that many bytes.  */
 271           offset = program - (const uint8_t *) cache->data->d.d_buf;
 272           get_uleb128 (operand, program);
 273           cfi_assert (operand <= (Dwarf_Word) (end - program));
 274           program += operand;
 275           register_rule (regno, val_expression, offset);
 276           continue;
 277
 278         case DW_CFA_restore_extended:
 279           get_uleb128 (operand, program);
 280         case DW_CFA_restore + 0 ... DW_CFA_restore + CFI_PRIMARY_MAX:
 281
 282           if (unlikely (abi_cfi) && likely (opcode == DW_CFA_restore))
 283             {
 284               /* Special case hack to give backend abi_cfi a shorthand.  */
 285               cache->default_same_value = true;
 286               continue;
 287             }
 288
 289           /* This can't be used in the CIE's own initial instructions.  */
 290           cfi_assert (cie->initial_state != NULL);
 291
 292           /* Restore the CIE's initial rule for this register.  */
 293           if (unlikely (! enough_registers (operand)))
 294             goto out;
 295           if (cie->initial_state->nregs > operand)
 296             fs->regs[operand] = cie->initial_state->regs[operand];
 297           else
 298             fs->regs[operand].rule = reg_unspecified;
 299           continue;
 300
 301         case DW_CFA_remember_state:
 302           {
 303             /* Duplicate the state and chain the copy on.  */
 304             Dwarf_Frame *copy = duplicate_frame_state (fs, fs);
 305             if (unlikely (copy == NULL))
 306               {
 307                 result = DWARF_E_NOMEM;
 308                 goto out;
 309               }
 310             fs = copy;
 311             continue;
 312           }
 313
 314         case DW_CFA_restore_state:
 315           {
 316             /* Pop the current state off and use the old one instead.  */
 317             Dwarf_Frame *prev = fs->prev;
 318             cfi_assert (prev != NULL);
 319             free (fs);
 320             fs = prev;
 321             continue;
 322           }
 323
 324         case DW_CFA_nop:
 325           continue;
 326
 327         case DW_CFA_GNU_window_save:
 328           /* This is magic shorthand used only by SPARC.  It's equivalent
 329              to a bunch of DW_CFA_register and DW_CFA_offset operations.  */
 330           if (unlikely (! enough_registers (31)))
 331             goto out;
 332           for (regno = 8; regno < 16; ++regno)
 333             {
 334               /* Find each %oN in %iN.  */
 335               fs->regs[regno].rule = reg_register;
 336               fs->regs[regno].value = regno + 16;
 337             }
 338           unsigned int address_size = (cache->e_ident[EI_CLASS] == ELFCLASS32
 339                                        ? 4 : 8);
 340           for (; regno < 32; ++regno)
 341             {
 342               /* Find %l0..%l7 and %i0..%i7 in a block at the CFA.  */
 343               fs->regs[regno].rule = reg_offset;
 344               fs->regs[regno].value = (regno - 16) * address_size;
 345             }
 346           continue;
 347
 348         case DW_CFA_GNU_args_size:
 349           /* XXX is this useful for anything? */
 350           get_uleb128 (operand, program);
 351           continue;
 352
 353         default:
 354           cfi_assert (false);
 355           continue;
 356         }
 357
 358       /* We get here only for the cases that have just moved LOC.  */
 359       cfi_assert (cie->initial_state != NULL);
 360       if (find_pc >= loc)
 361         /* This advance has not yet reached FIND_PC.  */
 362         fs->start = loc;
 363       else
 364         {
 365           /* We have just advanced past the address we're looking for.
 366              The state currently described is what we want to see.  */
 367           fs->end = loc;
 368           break;
 369         }
 370     }
 371
 372   /* "The end of the instruction stream can be thought of as a
 373      DW_CFA_set_loc (initial_location + address_range) instruction."
 374      (DWARF 3.0 Section 6.4.3)
 375
 376      When we fall off the end of the program without an advance_loc/set_loc
 377      that put us past FIND_PC, the final state left by the FDE program
 378      applies to this address (the caller ensured it was inside the FDE).
 379      This address (FDE->end) is already in FS->end as set by the caller.  */
 380
 381 #undef register_rule
 382 #undef cfi_assert
 383
 384  out:
 385
 386   /* Pop any remembered states left on the stack.  */
 387   while (fs->prev != NULL)
 388     {
 389       Dwarf_Frame *prev = fs->prev;
 390       fs->prev = prev->prev;
 391       free (prev);
 392     }
 393
 394   if (likely (result == DWARF_E_NOERROR))
 395     *state = fs;
 396   else
 397     free (fs);
 398
 399   return result;
 400 }
 401
 402 static int
 403 cie_cache_initial_state (Dwarf_CFI *cache, struct dwarf_cie *cie)
 404 {
 405   int result = DWARF_E_NOERROR;
 406
 407   if (likely (cie->initial_state != NULL))
 408     return result;
 409
 410   /* This CIE has not been used before.  Play out its initial
 411      instructions and cache the initial state that results.
 412      First we'll let the backend fill in the default initial
 413      state for this machine's ABI.  */
 414
 415   Dwarf_CIE abi_info = { DW_CIE_ID_64, NULL, NULL, 1, 1, -1, "", NULL, 0, 0 };
 416
 417   /* Make sure we have a backend handle cached.  */
 418   if (unlikely (cache->ebl == NULL))
 419     {
 420       cache->ebl = ebl_openbackend (cache->data->s->elf);
 421       if (unlikely (cache->ebl == NULL))
 422         cache->ebl = (void *) -1l;
 423     }
 424
 425   /* Fetch the ABI's default CFI program.  */
 426   if (likely (cache->ebl != (void *) -1l)
 427       && unlikely (ebl_abi_cfi (cache->ebl, &abi_info) < 0))
 428     return DWARF_E_UNKNOWN_ERROR;
 429
 430   Dwarf_Frame *cie_fs = calloc (1, sizeof (Dwarf_Frame));
 431   if (unlikely (cie_fs == NULL))
 432     return DWARF_E_NOMEM;
 433
 434   /* If the default state of any register is not "undefined"
 435      (i.e. call-clobbered), then the backend supplies instructions
 436      for the standard initial state.  */
 437   if (abi_info.initial_instructions_end > abi_info.initial_instructions)
 438     {
 439       /* Dummy CIE for backend's instructions.  */
 440       struct dwarf_cie abi_cie =
 441         {
 442           .code_alignment_factor = abi_info.code_alignment_factor,
 443           .data_alignment_factor = abi_info.data_alignment_factor,
 444         };
 445       result = execute_cfi (cache, &abi_cie, &cie_fs,
 446                             abi_info.initial_instructions,
 447                             abi_info.initial_instructions_end, true,
 448                             0, (Dwarf_Addr) -1l);
 449     }
 450
 451   /* Now run the CIE's initial instructions.  */
 452   if (cie->initial_instructions_end > cie->initial_instructions
 453       && likely (result == DWARF_E_NOERROR))
 454     result = execute_cfi (cache, cie, &cie_fs,
 455                           cie->initial_instructions,
 456                           cie->initial_instructions_end, false,
 457                           0, (Dwarf_Addr) -1l);
 458
 459   if (likely (result == DWARF_E_NOERROR))
 460     {
 461       /* Now we have the initial state of things that all
 462          FDEs using this CIE will start from.  */
 463       cie_fs->cache = cache;
 464       cie->initial_state = cie_fs;
 465     }
 466
 467   return result;
 468 }
 469
 470 int
 471 internal_function
 472 __libdw_frame_at_address (Dwarf_CFI *cache, struct dwarf_fde *fde,
 473                           Dwarf_Addr address, Dwarf_Frame **frame)
 474 {
 475   int result = cie_cache_initial_state (cache, fde->cie);
 476   if (likely (result == DWARF_E_NOERROR))
 477     {
 478       Dwarf_Frame *fs = duplicate_frame_state (fde->cie->initial_state, NULL);
 479       if (unlikely (fs == NULL))
 480         return DWARF_E_NOMEM;
 481
 482       fs->fde = fde;
 483       fs->start = fde->start;
 484       fs->end = fde->end;
 485
 486       result = execute_cfi (cache, fde->cie, &fs,
 487                             fde->instructions, fde->instructions_end, false,
 488                             fde->start, address);
 489       if (likely (result == DWARF_E_NOERROR))
 490         *frame = fs;
 491     }
 492   return result;
 493 }