libdw/cfi.c

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