Squashed 'third_party/elfutils/' content from commit 555e15e
Change-Id: I61cde98949e47e5c8c09c33260de17f30921be79
git-subtree-dir: third_party/elfutils
git-subtree-split: 555e15ebe8bf1eb33d00747173cfc80cc65648a4
diff --git a/libdw/cfi.c b/libdw/cfi.c
new file mode 100644
index 0000000..341e055
--- /dev/null
+++ b/libdw/cfi.c
@@ -0,0 +1,518 @@
+/* CFI program execution.
+ Copyright (C) 2009-2010, 2014, 2015 Red Hat, Inc.
+ This file is part of elfutils.
+
+ This file is free software; you can redistribute it and/or modify
+ it under the terms of either
+
+ * the GNU Lesser General Public License as published by the Free
+ Software Foundation; either version 3 of the License, or (at
+ your option) any later version
+
+ or
+
+ * the GNU General Public License as published by the Free
+ Software Foundation; either version 2 of the License, or (at
+ your option) any later version
+
+ or both in parallel, as here.
+
+ elfutils is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received copies of the GNU General Public License and
+ the GNU Lesser General Public License along with this program. If
+ not, see <http://www.gnu.org/licenses/>. */
+
+#ifdef HAVE_CONFIG_H
+# include <config.h>
+#endif
+
+#include <dwarf.h>
+#include "../libebl/libebl.h"
+#include "cfi.h"
+#include "memory-access.h"
+#include "encoded-value.h"
+#include "system.h"
+#include <assert.h>
+#include <stdlib.h>
+#include <string.h>
+
+#define CFI_PRIMARY_MAX 0x3f
+
+static Dwarf_Frame *
+duplicate_frame_state (const Dwarf_Frame *original,
+ Dwarf_Frame *prev)
+{
+ size_t size = offsetof (Dwarf_Frame, regs[original->nregs]);
+ Dwarf_Frame *copy = malloc (size);
+ if (likely (copy != NULL))
+ {
+ memcpy (copy, original, size);
+ copy->prev = prev;
+ }
+ return copy;
+}
+
+static inline bool
+enough_registers (Dwarf_Word reg, Dwarf_Frame **pfs, int *result)
+{
+ /* Don't allow insanely large register numbers. 268435456 registers
+ should be enough for anybody. And very large values might overflow
+ the array size and offsetof calculations below. */
+ if (unlikely (reg >= INT32_MAX / sizeof ((*pfs)->regs[0])))
+ {
+ *result = DWARF_E_INVALID_CFI;
+ return false;
+ }
+
+ if ((*pfs)->nregs <= reg)
+ {
+ size_t size = offsetof (Dwarf_Frame, regs[reg + 1]);
+ Dwarf_Frame *bigger = realloc (*pfs, size);
+ if (unlikely (bigger == NULL))
+ {
+ *result = DWARF_E_NOMEM;
+ return false;
+ }
+ else
+ {
+ eu_static_assert (reg_unspecified == 0);
+ memset (bigger->regs + bigger->nregs, 0,
+ (reg + 1 - bigger->nregs) * sizeof bigger->regs[0]);
+ bigger->nregs = reg + 1;
+ *pfs = bigger;
+ }
+ }
+ return true;
+}
+
+static inline void
+require_cfa_offset (Dwarf_Frame *fs)
+{
+ if (unlikely (fs->cfa_rule != cfa_offset))
+ fs->cfa_rule = cfa_invalid;
+}
+
+/* Returns a DWARF_E_* error code, usually NOERROR or INVALID_CFI.
+ Frees *STATE on failure. */
+static int
+execute_cfi (Dwarf_CFI *cache,
+ const struct dwarf_cie *cie,
+ Dwarf_Frame **state,
+ const uint8_t *program, const uint8_t *const end, bool abi_cfi,
+ Dwarf_Addr loc, Dwarf_Addr find_pc)
+{
+ /* The caller should not give us anything out of range. */
+ assert (loc <= find_pc);
+
+ int result = DWARF_E_NOERROR;
+
+#define cfi_assert(ok) do { \
+ if (likely (ok)) break; \
+ result = DWARF_E_INVALID_CFI; \
+ goto out; \
+ } while (0)
+
+ Dwarf_Frame *fs = *state;
+
+#define register_rule(regno, r_rule, r_value) do { \
+ if (unlikely (! enough_registers (regno, &fs, &result))) \
+ goto out; \
+ fs->regs[regno].rule = reg_##r_rule; \
+ fs->regs[regno].value = (r_value); \
+ } while (0)
+
+ while (program < end)
+ {
+ uint8_t opcode = *program++;
+ Dwarf_Word regno;
+ Dwarf_Word offset;
+ Dwarf_Word sf_offset;
+ Dwarf_Word operand = opcode & CFI_PRIMARY_MAX;
+ switch (opcode)
+ {
+ /* These cases move LOC, i.e. "create a new table row". */
+
+ case DW_CFA_advance_loc1:
+ operand = *program++;
+ FALLTHROUGH;
+ case DW_CFA_advance_loc + 0 ... DW_CFA_advance_loc + CFI_PRIMARY_MAX:
+ advance_loc:
+ loc += operand * cie->code_alignment_factor;
+ break;
+
+ case DW_CFA_advance_loc2:
+ cfi_assert (program + 2 <= end);
+ operand = read_2ubyte_unaligned_inc (cache, program);
+ goto advance_loc;
+ case DW_CFA_advance_loc4:
+ cfi_assert (program + 4 <= end);
+ operand = read_4ubyte_unaligned_inc (cache, program);
+ goto advance_loc;
+ case DW_CFA_MIPS_advance_loc8:
+ cfi_assert (program + 8 <= end);
+ operand = read_8ubyte_unaligned_inc (cache, program);
+ goto advance_loc;
+
+ case DW_CFA_set_loc:
+ if (likely (!read_encoded_value (cache, cie->fde_encoding,
+ &program, &loc)))
+ break;
+ result = INTUSE(dwarf_errno) ();
+ goto out;
+
+ /* Now all following cases affect this row, but do not touch LOC.
+ These cases end with 'continue'. We only get out of the
+ switch block for the row-copying (LOC-moving) cases above. */
+
+ case DW_CFA_def_cfa:
+ get_uleb128 (operand, program, end);
+ cfi_assert (program < end);
+ get_uleb128 (offset, program, end);
+ def_cfa:
+ fs->cfa_rule = cfa_offset;
+ fs->cfa_val_reg = operand;
+ fs->cfa_val_offset = offset;
+ /* Prime the rest of the Dwarf_Op so dwarf_frame_cfa can use it. */
+ fs->cfa_data.offset.atom = DW_OP_bregx;
+ fs->cfa_data.offset.offset = 0;
+ continue;
+
+ case DW_CFA_def_cfa_register:
+ get_uleb128 (regno, program, end);
+ require_cfa_offset (fs);
+ fs->cfa_val_reg = regno;
+ continue;
+
+ case DW_CFA_def_cfa_sf:
+ get_uleb128 (operand, program, end);
+ cfi_assert (program < end);
+ get_sleb128 (sf_offset, program, end);
+ offset = sf_offset * cie->data_alignment_factor;
+ goto def_cfa;
+
+ case DW_CFA_def_cfa_offset:
+ get_uleb128 (offset, program, end);
+ def_cfa_offset:
+ require_cfa_offset (fs);
+ fs->cfa_val_offset = offset;
+ continue;
+
+ case DW_CFA_def_cfa_offset_sf:
+ get_sleb128 (sf_offset, program, end);
+ offset = sf_offset * cie->data_alignment_factor;
+ goto def_cfa_offset;
+
+ case DW_CFA_def_cfa_expression:
+ /* DW_FORM_block is a ULEB128 length followed by that many bytes. */
+ get_uleb128 (operand, program, end);
+ cfi_assert (operand <= (Dwarf_Word) (end - program));
+ fs->cfa_rule = cfa_expr;
+ fs->cfa_data.expr.data = (unsigned char *) program;
+ fs->cfa_data.expr.length = operand;
+ program += operand;
+ continue;
+
+ case DW_CFA_undefined:
+ get_uleb128 (regno, program, end);
+ register_rule (regno, undefined, 0);
+ continue;
+
+ case DW_CFA_same_value:
+ get_uleb128 (regno, program, end);
+ register_rule (regno, same_value, 0);
+ continue;
+
+ case DW_CFA_offset_extended:
+ get_uleb128 (operand, program, end);
+ cfi_assert (program < end);
+ case DW_CFA_offset + 0 ... DW_CFA_offset + CFI_PRIMARY_MAX:
+ get_uleb128 (offset, program, end);
+ offset *= cie->data_alignment_factor;
+ offset_extended:
+ register_rule (operand, offset, offset);
+ continue;
+
+ case DW_CFA_offset_extended_sf:
+ get_uleb128 (operand, program, end);
+ get_sleb128 (sf_offset, program, end);
+ offset_extended_sf:
+ offset = sf_offset * cie->data_alignment_factor;
+ goto offset_extended;
+
+ case DW_CFA_GNU_negative_offset_extended:
+ /* GNU extension obsoleted by DW_CFA_offset_extended_sf. */
+ get_uleb128 (operand, program, end);
+ cfi_assert (program < end);
+ get_uleb128 (offset, program, end);
+ sf_offset = -offset;
+ goto offset_extended_sf;
+
+ case DW_CFA_val_offset:
+ get_uleb128 (operand, program, end);
+ cfi_assert (program < end);
+ get_uleb128 (offset, program, end);
+ offset *= cie->data_alignment_factor;
+ val_offset:
+ register_rule (operand, val_offset, offset);
+ continue;
+
+ case DW_CFA_val_offset_sf:
+ get_uleb128 (operand, program, end);
+ cfi_assert (program < end);
+ get_sleb128 (sf_offset, program, end);
+ offset = sf_offset * cie->data_alignment_factor;
+ goto val_offset;
+
+ case DW_CFA_register:
+ get_uleb128 (regno, program, end);
+ cfi_assert (program < end);
+ get_uleb128 (operand, program, end);
+ register_rule (regno, register, operand);
+ continue;
+
+ case DW_CFA_expression:
+ /* Expression rule relies on section data, abi_cfi cannot use it. */
+ assert (! abi_cfi);
+ get_uleb128 (regno, program, end);
+ offset = program - (const uint8_t *) cache->data->d.d_buf;
+ /* DW_FORM_block is a ULEB128 length followed by that many bytes. */
+ cfi_assert (program < end);
+ get_uleb128 (operand, program, end);
+ cfi_assert (operand <= (Dwarf_Word) (end - program));
+ program += operand;
+ register_rule (regno, expression, offset);
+ continue;
+
+ case DW_CFA_val_expression:
+ /* Expression rule relies on section data, abi_cfi cannot use it. */
+ assert (! abi_cfi);
+ get_uleb128 (regno, program, end);
+ /* DW_FORM_block is a ULEB128 length followed by that many bytes. */
+ offset = program - (const uint8_t *) cache->data->d.d_buf;
+ get_uleb128 (operand, program, end);
+ cfi_assert (operand <= (Dwarf_Word) (end - program));
+ program += operand;
+ register_rule (regno, val_expression, offset);
+ continue;
+
+ case DW_CFA_restore_extended:
+ get_uleb128 (operand, program, end);
+ FALLTHROUGH;
+ case DW_CFA_restore + 0 ... DW_CFA_restore + CFI_PRIMARY_MAX:
+
+ if (unlikely (abi_cfi) && likely (opcode == DW_CFA_restore))
+ {
+ /* Special case hack to give backend abi_cfi a shorthand. */
+ cache->default_same_value = true;
+ continue;
+ }
+
+ /* This can't be used in the CIE's own initial instructions. */
+ cfi_assert (cie->initial_state != NULL);
+
+ /* Restore the CIE's initial rule for this register. */
+ if (unlikely (! enough_registers (operand, &fs, &result)))
+ goto out;
+ if (cie->initial_state->nregs > operand)
+ fs->regs[operand] = cie->initial_state->regs[operand];
+ else
+ fs->regs[operand].rule = reg_unspecified;
+ continue;
+
+ case DW_CFA_remember_state:
+ {
+ /* Duplicate the state and chain the copy on. */
+ Dwarf_Frame *copy = duplicate_frame_state (fs, fs);
+ if (unlikely (copy == NULL))
+ {
+ result = DWARF_E_NOMEM;
+ goto out;
+ }
+ fs = copy;
+ continue;
+ }
+
+ case DW_CFA_restore_state:
+ {
+ /* Pop the current state off and use the old one instead. */
+ Dwarf_Frame *prev = fs->prev;
+ cfi_assert (prev != NULL);
+ free (fs);
+ fs = prev;
+ continue;
+ }
+
+ case DW_CFA_nop:
+ continue;
+
+ case DW_CFA_GNU_window_save:
+ /* This is magic shorthand used only by SPARC. It's equivalent
+ to a bunch of DW_CFA_register and DW_CFA_offset operations. */
+ if (unlikely (! enough_registers (31, &fs, &result)))
+ goto out;
+ for (regno = 8; regno < 16; ++regno)
+ {
+ /* Find each %oN in %iN. */
+ fs->regs[regno].rule = reg_register;
+ fs->regs[regno].value = regno + 16;
+ }
+ unsigned int address_size = (cache->e_ident[EI_CLASS] == ELFCLASS32
+ ? 4 : 8);
+ for (; regno < 32; ++regno)
+ {
+ /* Find %l0..%l7 and %i0..%i7 in a block at the CFA. */
+ fs->regs[regno].rule = reg_offset;
+ fs->regs[regno].value = (regno - 16) * address_size;
+ }
+ continue;
+
+ case DW_CFA_GNU_args_size:
+ /* XXX is this useful for anything? */
+ get_uleb128 (operand, program, end);
+ continue;
+
+ default:
+ cfi_assert (false);
+ continue;
+ }
+
+ /* We get here only for the cases that have just moved LOC. */
+ cfi_assert (cie->initial_state != NULL);
+ if (find_pc >= loc)
+ /* This advance has not yet reached FIND_PC. */
+ fs->start = loc;
+ else
+ {
+ /* We have just advanced past the address we're looking for.
+ The state currently described is what we want to see. */
+ fs->end = loc;
+ break;
+ }
+ }
+
+ /* "The end of the instruction stream can be thought of as a
+ DW_CFA_set_loc (initial_location + address_range) instruction."
+ (DWARF 3.0 Section 6.4.3)
+
+ When we fall off the end of the program without an advance_loc/set_loc
+ that put us past FIND_PC, the final state left by the FDE program
+ applies to this address (the caller ensured it was inside the FDE).
+ This address (FDE->end) is already in FS->end as set by the caller. */
+
+#undef register_rule
+#undef cfi_assert
+
+ out:
+
+ /* Pop any remembered states left on the stack. */
+ while (fs->prev != NULL)
+ {
+ Dwarf_Frame *prev = fs->prev;
+ fs->prev = prev->prev;
+ free (prev);
+ }
+
+ if (likely (result == DWARF_E_NOERROR))
+ *state = fs;
+ else
+ free (fs);
+
+ return result;
+}
+
+static int
+cie_cache_initial_state (Dwarf_CFI *cache, struct dwarf_cie *cie)
+{
+ int result = DWARF_E_NOERROR;
+
+ if (likely (cie->initial_state != NULL))
+ return result;
+
+ /* This CIE has not been used before. Play out its initial
+ instructions and cache the initial state that results.
+ First we'll let the backend fill in the default initial
+ state for this machine's ABI. */
+
+ Dwarf_CIE abi_info = { DW_CIE_ID_64, NULL, NULL, 1, 1, -1, "", NULL, 0, 0 };
+
+ /* Make sure we have a backend handle cached. */
+ if (unlikely (cache->ebl == NULL))
+ {
+ cache->ebl = ebl_openbackend (cache->data->s->elf);
+ if (unlikely (cache->ebl == NULL))
+ cache->ebl = (void *) -1l;
+ }
+
+ /* Fetch the ABI's default CFI program. */
+ if (likely (cache->ebl != (void *) -1l)
+ && unlikely (ebl_abi_cfi (cache->ebl, &abi_info) < 0))
+ return DWARF_E_UNKNOWN_ERROR;
+
+ Dwarf_Frame *cie_fs = calloc (1, sizeof (Dwarf_Frame));
+ if (unlikely (cie_fs == NULL))
+ return DWARF_E_NOMEM;
+
+ /* If the default state of any register is not "undefined"
+ (i.e. call-clobbered), then the backend supplies instructions
+ for the standard initial state. */
+ if (abi_info.initial_instructions_end > abi_info.initial_instructions)
+ {
+ /* Dummy CIE for backend's instructions. */
+ struct dwarf_cie abi_cie =
+ {
+ .code_alignment_factor = abi_info.code_alignment_factor,
+ .data_alignment_factor = abi_info.data_alignment_factor,
+ };
+ result = execute_cfi (cache, &abi_cie, &cie_fs,
+ abi_info.initial_instructions,
+ abi_info.initial_instructions_end, true,
+ 0, (Dwarf_Addr) -1l);
+ }
+
+ /* Now run the CIE's initial instructions. */
+ if (cie->initial_instructions_end > cie->initial_instructions
+ && likely (result == DWARF_E_NOERROR))
+ result = execute_cfi (cache, cie, &cie_fs,
+ cie->initial_instructions,
+ cie->initial_instructions_end, false,
+ 0, (Dwarf_Addr) -1l);
+
+ if (likely (result == DWARF_E_NOERROR))
+ {
+ /* Now we have the initial state of things that all
+ FDEs using this CIE will start from. */
+ cie_fs->cache = cache;
+ cie->initial_state = cie_fs;
+ }
+
+ return result;
+}
+
+int
+internal_function
+__libdw_frame_at_address (Dwarf_CFI *cache, struct dwarf_fde *fde,
+ Dwarf_Addr address, Dwarf_Frame **frame)
+{
+ int result = cie_cache_initial_state (cache, fde->cie);
+ if (likely (result == DWARF_E_NOERROR))
+ {
+ Dwarf_Frame *fs = duplicate_frame_state (fde->cie->initial_state, NULL);
+ if (unlikely (fs == NULL))
+ return DWARF_E_NOMEM;
+
+ fs->fde = fde;
+ fs->start = fde->start;
+ fs->end = fde->end;
+
+ result = execute_cfi (cache, fde->cie, &fs,
+ fde->instructions, fde->instructions_end, false,
+ fde->start, address);
+ if (likely (result == DWARF_E_NOERROR))
+ *frame = fs;
+ }
+ return result;
+}