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