[RFC v5 44/57] objtool: arm64: Implement functions to add switch tables alternatives

[Julien Thierry <jthierry@redhat.com>]

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.

Signed-off-by: Raphael Gault <raphael.gault@arm.com>
[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@redhat.com>
---
 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)
-- 
2.21.0