Re: [RFC v5 44/57] objtool: arm64: Implement functions to add switch tables alternatives
From: Julien Thierry
Date: Fri Jan 17 2020 - 03:28:59 EST
Hi RaphaÃl,
On 1/15/20 4:37 PM, Raphael Gault wrote:
Hi Julien,
On 1/9/20 4:02 PM, Julien Thierry wrote:
This patch implements the functions required to identify and add as
alternatives all the possible destinations of the switch table.
This implementation relies on the new plugin introduced previously which
records information about the switch-table in a
.discard.switch_table_information section.
I think you forgot to update the name of the section with respect to
what was done in the previous patch (.discard.switch_table_info instead
of .discard.switch_table_information).
Oops, you are correct. Thanks for spotting this. I'll update the commit.
Thanks,
Signed-off-by: Raphael Gault <raphael.gault@xxxxxxx>
[J.T.: Update arch implementation to new prototypes,
ÂÂÂÂÂÂÂ Update switch table information section name,
ÂÂÂÂÂÂÂ Do some clean up,
ÂÂÂÂÂÂÂ Use the offset sign information,
ÂÂÂÂÂÂÂ Use the newly added rela to find the corresponding jump
instruction]
Signed-off-by: Julien Thierry <jthierry@xxxxxxxxxx>
---
 tools/objtool/arch/arm64/arch_special.c | 251 +++++++++++++++++-
 .../objtool/arch/arm64/include/arch_special.h | 2 +
 tools/objtool/check.c | 4 +-
 tools/objtool/check.h | 2 +
 4 files changed, 255 insertions(+), 4 deletions(-)
diff --git a/tools/objtool/arch/arm64/arch_special.c
b/tools/objtool/arch/arm64/arch_special.c
index 5239489c9c57..a15f6697dc74 100644
--- a/tools/objtool/arch/arm64/arch_special.c
+++ b/tools/objtool/arch/arm64/arch_special.c
@@ -1,15 +1,262 @@
 // SPDX-License-Identifier: GPL-2.0-or-later
+#include <stdlib.h>
+#include <string.h>
+
 #include "../../special.h"
+#include "../../warn.h"
+#include "arch_special.h"
+#include "bit_operations.h"
+#include "insn_decode.h"
+
+/*
+ * The arm64_switch_table_detection_plugin generate an array of elements
+ * described by the following structure.
+ * Each jump table found in the compilation unit is associated with
one of
+ * entries of the array.
+ */
+struct switch_table_info {
+ÂÂÂ u64 switch_table_ref; // Relocation target referencing the
beginning of the jump table
+ÂÂÂ u64 dyn_jump_ref; // Relocation target referencing the set of
instructions setting up the jump to the table
+ÂÂÂ u64 nb_entries;
+ÂÂÂ u64 offset_unsigned;
+} __attribute__((__packed__));
+
+static bool insn_is_adr_pcrel(struct instruction *insn)
+{
+ÂÂÂ u32 opcode = *(u32 *)(insn->sec->data->d_buf + insn->offset);
+
+ÂÂÂ return ((opcode >> 24) & 0x1f) == 0x10;
+}
+
+static s64 next_offset(void *table, u8 entry_size, bool is_signed)
+{
+ÂÂÂ if (!is_signed) {
+ÂÂÂÂÂÂÂ switch (entry_size) {
+ÂÂÂÂÂÂÂ case 1:
+ÂÂÂÂÂÂÂÂÂÂÂ return *(u8 *)(table);
+ÂÂÂÂÂÂÂ case 2:
+ÂÂÂÂÂÂÂÂÂÂÂ return *(u16 *)(table);
+ÂÂÂÂÂÂÂ default:
+ÂÂÂÂÂÂÂÂÂÂÂ return *(u32 *)(table);
+ÂÂÂÂÂÂÂ }
+ÂÂÂ } else {
+ÂÂÂÂÂÂÂ switch (entry_size) {
+ÂÂÂÂÂÂÂ case 1:
+ÂÂÂÂÂÂÂÂÂÂÂ return *(s8 *)(table);
+ÂÂÂÂÂÂÂ case 2:
+ÂÂÂÂÂÂÂÂÂÂÂ return *(s16 *)(table);
+ÂÂÂÂÂÂÂ default:
+ÂÂÂÂÂÂÂÂÂÂÂ return *(s32 *)(table);
+ÂÂÂÂÂÂÂ }
+ÂÂÂ }
+}
+
+static u32 get_table_entry_size(u32 insn)
+{
+ÂÂÂ unsigned char size = (insn >> 30) & ONES(2);
+
+ÂÂÂ switch (size) {
+ÂÂÂ case 0:
+ÂÂÂÂÂÂÂ return 1;
+ÂÂÂ case 1:
+ÂÂÂÂÂÂÂ return 2;
+ÂÂÂ default:
+ÂÂÂÂÂÂÂ return 4;
+ÂÂÂ }
+}
+
+static int add_possible_branch(struct objtool_file *file,
+ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ struct instruction *insn,
+ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ u32 base, s64 offset)
+{
+ÂÂÂ struct instruction *dest_insn;
+ÂÂÂ struct alternative *alt;
+
+ÂÂÂ offset = base + 4 * offset;
+
+ÂÂÂ dest_insn = find_insn(file, insn->sec, offset);
+ÂÂÂ if (!dest_insn)
+ÂÂÂÂÂÂÂ return 0;
+
+ÂÂÂ alt = calloc(1, sizeof(*alt));
+ÂÂÂ if (!alt) {
+ÂÂÂÂÂÂÂ WARN("allocation failure, can't add jump alternative");
+ÂÂÂÂÂÂÂ return -1;
+ÂÂÂ }
+
+ÂÂÂ alt->insn = dest_insn;
+ÂÂÂ alt->skip_orig = true;
+ÂÂÂ list_add_tail(&alt->list, &insn->alts);
+ÂÂÂ return 0;
+}
+
+static struct switch_table_info *get_swt_info(struct section
*swt_info_sec,
+ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ struct instruction *insn)
+{
+ÂÂÂ u64 *table_ref;
+
+ÂÂÂ if (!insn->jump_table) {
+ÂÂÂÂÂÂÂ WARN("no jump table available for %s+0x%lx",
+ÂÂÂÂÂÂÂÂÂÂÂÂ insn->sec->name, insn->offset);
+ÂÂÂÂÂÂÂ return NULL;
+ÂÂÂ }
+ÂÂÂ table_ref = (void *)(swt_info_sec->data->d_buf +
+ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ insn->jump_table->offset);
+ÂÂÂ return container_of(table_ref, struct switch_table_info,
+ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ switch_table_ref);
+}
+
+static int add_arm64_jump_table_dests(struct objtool_file *file,
+ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ struct instruction *insn)
+{
+ÂÂÂ struct switch_table_info *swt_info;
+ÂÂÂ struct section *objtool_data;
+ÂÂÂ struct section *rodata_sec;
+ÂÂÂ struct section *branch_sec;
+ÂÂÂ struct instruction *pre_jump_insn;
+ÂÂÂ u8 *switch_table;
+ÂÂÂ u32 entry_size;
+
+ÂÂÂ objtool_data = find_section_by_name(file->elf,
+ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ ".discard.switch_table_info");
+ÂÂÂ if (!objtool_data)
+ÂÂÂÂÂÂÂ return 0;
+
+ÂÂÂ /*
+ÂÂÂÂ * 1. Identify entry for the switch table
+ÂÂÂÂ * 2. Retrieve branch instruction
+ÂÂÂÂ * 3. Retrieve base offset
+ÂÂÂÂ * 3. For all entries in switch table:
+ÂÂÂÂ *ÂÂÂÂ 3.1. Compute new offset
+ÂÂÂÂ *ÂÂÂÂ 3.2. Create alternative instruction
+ÂÂÂÂ *ÂÂÂÂ 3.3. Add alt_instr to insn->alts list
+ÂÂÂÂ */
+ÂÂÂ swt_info = get_swt_info(objtool_data, insn);
+
+ÂÂÂ /* retrieving pre jump instruction (ldr) */
+ÂÂÂ branch_sec = insn->sec;
+ÂÂÂ pre_jump_insn = find_insn(file, branch_sec,
+ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ insn->offset - 3 * sizeof(u32));
+ÂÂÂ entry_size = get_table_entry_size(*(u32 *)(branch_sec->data->d_buf +
+ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ pre_jump_insn->offset));
+
+ÂÂÂ /* retrieving switch table content */
+ÂÂÂ rodata_sec = find_section_by_name(file->elf, ".rodata");
+ÂÂÂ switch_table = (u8 *)(rodata_sec->data->d_buf +
+ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ insn->jump_table->addend);
+
+ÂÂÂ /*
+ÂÂÂÂ * iterating over the pre-jumps instruction in order to
+ÂÂÂÂ * retrieve switch base offset.
+ÂÂÂÂ */
+ÂÂÂ while (pre_jump_insn && pre_jump_insn->offset <= insn->offset) {
+ÂÂÂÂÂÂÂ if (insn_is_adr_pcrel(pre_jump_insn)) {
+ÂÂÂÂÂÂÂÂÂÂÂ u64 base_offset;
+ÂÂÂÂÂÂÂÂÂÂÂ int i;
+
+ÂÂÂÂÂÂÂÂÂÂÂ base_offset = pre_jump_insn->offset +
+ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ pre_jump_insn->immediate;
+
+ÂÂÂÂÂÂÂÂÂÂÂ /*
+ÂÂÂÂÂÂÂÂÂÂÂÂ * Once we have the switch table entry size
+ÂÂÂÂÂÂÂÂÂÂÂÂ * we add every possible destination using
+ÂÂÂÂÂÂÂÂÂÂÂÂ * alternatives of the original branch
+ÂÂÂÂÂÂÂÂÂÂÂÂ * instruction
+ÂÂÂÂÂÂÂÂÂÂÂÂ */
+ÂÂÂÂÂÂÂÂÂÂÂ for (i = 0; i < swt_info->nb_entries; i++) {
+ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ s64 table_offset = next_offset(switch_table,
+ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ entry_size,
+ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ !swt_info->offset_unsigned);
+
+ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ if (add_possible_branch(file, insn,
+ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ base_offset,
+ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ table_offset)) {
+ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ return -1;
+ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ }
+ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ switch_table += entry_size;
+ÂÂÂÂÂÂÂÂÂÂÂ }
+ÂÂÂÂÂÂÂÂÂÂÂ break;
+ÂÂÂÂÂÂÂ }
+ÂÂÂÂÂÂÂ pre_jump_insn = next_insn_same_sec(file, pre_jump_insn);
+ÂÂÂ }
+
+ÂÂÂ return 0;
+}
 int arch_add_jump_table_dests(struct objtool_file *file,
ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ struct instruction *insn)
 {
-ÂÂÂ return 0;
+ÂÂÂ return add_arm64_jump_table_dests(file, insn);
 }
+static struct rela *find_swt_info_jump_rela(struct section
*swt_info_sec,
+ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ u32 index)
+{
+ÂÂÂ u32 rela_offset;
+
+ÂÂÂ rela_offset = index * sizeof(struct switch_table_info) +
+ÂÂÂÂÂÂÂÂÂÂÂÂÂ offsetof(struct switch_table_info, dyn_jump_ref);
+ÂÂÂ return find_rela_by_dest(swt_info_sec, rela_offset);
+}
+
+static struct rela *find_swt_info_table_rela(struct section
*swt_info_sec,
+ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ u32 index)
+{
+ÂÂÂ u32 rela_offset;
+
+ÂÂÂ rela_offset = index * sizeof(struct switch_table_info) +
+ÂÂÂÂÂÂÂÂÂÂÂÂÂ offsetof(struct switch_table_info, switch_table_ref);
+ÂÂÂ return find_rela_by_dest(swt_info_sec, rela_offset);
+}
+
+/*
+ * Aarch64 jump tables are just arrays of offsets (of varying
size/signess)
+ * representing the potential destination from a base address loaded
by an adr
+ * instruction.
+ *
+ * Aarch64 branches to jump tables are composed of multiple
instructions:
+ *
+ *ÂÂÂÂ ldr<?>Â x_offset, [x_offsets_table, x_index, ...]
+ *ÂÂÂÂ adrÂÂÂÂ x_dest_base, <addr>
+ *ÂÂÂÂ addÂÂÂÂ x_dest, x_target_base, x_offset, ...
+ *ÂÂÂÂ brÂÂÂÂÂ x_dest
+ *
+ * The arm64_switch_table_detection_plugin will make the connection
between
+ * the instruction setting x_offsets_table (dyn_jump_ref) and the actual
+ * table of offsets (switch_table_ref)
+ */
 struct rela *arch_find_switch_table(struct objtool_file *file,
ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ struct instruction *insn)
 {
-ÂÂÂ return NULL;
+ÂÂÂ struct section *objtool_data;
+ÂÂÂ struct rela *res = NULL;
+ÂÂÂ u32 nb_swt_entries = 0;
+ÂÂÂ u32 i;
+
+ÂÂÂ objtool_data = find_section_by_name(file->elf,
+ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ ".discard.switch_table_info");
+ÂÂÂ if (objtool_data)
+ÂÂÂÂÂÂÂ nb_swt_entries = objtool_data->sh.sh_size /
+ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ sizeof(struct switch_table_info);
+
+ÂÂÂ for (i = 0; i < nb_swt_entries; i++) {
+ÂÂÂÂÂÂÂ struct rela *info_rela;
+
+ÂÂÂÂÂÂÂ info_rela = find_swt_info_jump_rela(objtool_data, i);
+ÂÂÂÂÂÂÂ if (info_rela && info_rela->sym->sec == insn->sec &&
+ÂÂÂÂÂÂÂÂÂÂÂ info_rela->addend == insn->offset) {
+ÂÂÂÂÂÂÂÂÂÂÂ if (res) {
+ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ WARN_FUNC("duplicate objtool_data rela",
+ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ info_rela->sec, info_rela->offset);
+ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ continue;
+ÂÂÂÂÂÂÂÂÂÂÂ }
+ÂÂÂÂÂÂÂÂÂÂÂ res = find_swt_info_table_rela(objtool_data, i);
+ÂÂÂÂÂÂÂÂÂÂÂ if (!res)
+ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ WARN_FUNC("missing relocation in objtool data",
+ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ info_rela->sec, info_rela->offset);
+ÂÂÂÂÂÂÂ }
+ÂÂÂ }
+
+ÂÂÂ return res;
 }
diff --git a/tools/objtool/arch/arm64/include/arch_special.h
b/tools/objtool/arch/arm64/include/arch_special.h
index a82a9b3e51df..b96bcee308cf 100644
--- a/tools/objtool/arch/arm64/include/arch_special.h
+++ b/tools/objtool/arch/arm64/include/arch_special.h
@@ -3,6 +3,8 @@
 #ifndef _ARM64_ARCH_SPECIAL_H
 #define _ARM64_ARCH_SPECIAL_H
+#include <linux/types.h>
+
 #define EX_ENTRY_SIZE 8
 #define EX_ORIG_OFFSET 0
 #define EX_NEW_OFFSET 4
diff --git a/tools/objtool/check.c b/tools/objtool/check.c
index e0c6bda261c8..80ea5bbd36ab 100644
--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -33,8 +33,8 @@ struct instruction *find_insn(struct objtool_file
*file,
ÂÂÂÂÂ return NULL;
 }
-static struct instruction *next_insn_same_sec(struct objtool_file *file,
-ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ struct instruction *insn)
+struct instruction *next_insn_same_sec(struct objtool_file *file,
+ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ struct instruction *insn)
 {
ÂÂÂÂÂ struct instruction *next = list_next_entry(insn, list);
diff --git a/tools/objtool/check.h b/tools/objtool/check.h
index 91adec42782c..15165d04d9cb 100644
--- a/tools/objtool/check.h
+++ b/tools/objtool/check.h
@@ -66,6 +66,8 @@ int check(const char *objname, bool orc);
 struct instruction *find_insn(struct objtool_file *file,
ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ struct section *sec, unsigned long offset);
+struct instruction *next_insn_same_sec(struct objtool_file *file,
+ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ struct instruction *insn);
 #define for_each_insn(file, insn) \
ÂÂÂÂÂ list_for_each_entry(insn, &file->insn_list, list)
Cheers,
--
Julien Thierry