[RFC V3 10/18] objtool: arm64: Implement functions to add switch tables alternatives

[Raphael Gault <raphael.gault@arm.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 .objtool_data section.

Signed-off-by: Raphael Gault <raphael.gault@arm.com>
---
 tools/objtool/arch/arm64/arch_special.c       | 142 +++++++++++++++++-
 tools/objtool/arch/arm64/decode.c             |   2 +-
 .../objtool/arch/arm64/include/arch_special.h |  10 ++
 .../objtool/arch/arm64/include/insn_decode.h  |   3 +-
 tools/objtool/check.c                         |   8 +-
 tools/objtool/check.h                         |   2 +
 6 files changed, 157 insertions(+), 10 deletions(-)

diff --git a/tools/objtool/arch/arm64/arch_special.c b/tools/objtool/arch/arm64/arch_special.c
index a0f7066994b5..33f30876d339 100644
--- a/tools/objtool/arch/arm64/arch_special.c
+++ b/tools/objtool/arch/arm64/arch_special.c
@@ -12,8 +12,13 @@
  * You should have received a copy of the GNU General Public License
  * along with this program; if not, see <http://www.gnu.org/licenses/>.
  */
+
+#include <stdlib.h>
+#include <string.h>
+
 #include "../../special.h"
 #include "arch_special.h"
+#include "bit_operations.h"
 
 void arch_force_alt_path(unsigned short feature,
 			 bool uaccess,
@@ -21,9 +26,141 @@ void arch_force_alt_path(unsigned short feature,
 {
 }
 
+static u32 next_offset(u8 *table, u8 entry_size)
+{
+	switch (entry_size) {
+	case 1:
+		return table[0];
+	case 2:
+		return *(u16 *)(table);
+	default:
+		return *(u32 *)(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, u32 offset)
+{
+	struct instruction *new_insn;
+	struct alternative *alt;
+	offset = base + 4 * offset;
+	new_insn = calloc(1, sizeof(*new_insn));
+
+	if (new_insn == NULL) {
+		WARN("allocation failure, can't add jump alternative");
+		return -1;
+	}
+
+	memcpy(new_insn, insn, sizeof(*insn));
+	alt = calloc(1, sizeof(*alt));
+
+	if (new_insn == NULL) {
+		WARN("allocation failure, can't add jump alternative");
+		return -1;
+	}
+
+	new_insn->type = INSN_JUMP_UNCONDITIONAL;
+	new_insn->immediate = offset;
+	INIT_LIST_HEAD(&new_insn->alts);
+	new_insn->jump_dest = find_insn(file, insn->sec, offset);
+	alt->insn = new_insn;
+	alt->skip_orig = true;
+	list_add_tail(&alt->list, &insn->alts);
+	list_add_tail(&new_insn->list, &file->insn_list);
+	return 0;
+}
+
 int arch_add_switch_table(struct objtool_file *file, struct instruction *insn,
-			    struct rela *table, struct rela *next_table)
+			  struct rela *table, struct rela *next_table)
 {
+	struct rela *objtool_data_rela = NULL;
+	struct switch_table_info *swt_info = NULL;
+	struct section *objtool_data = find_section_by_name(file->elf, ".objtool_data");
+	struct section *rodata_sec = find_section_by_name(file->elf, ".rodata");
+	struct section *branch_sec = NULL;
+	u8 *switch_table = NULL;
+	u64 base_offset = 0;
+	struct instruction *pre_jump_insn;
+	u32 sec_size = 0;
+	u32 entry_size = 0;
+	u32 offset = 0;
+	u32 i, j;
+
+	if (objtool_data == NULL)
+		return 0;
+
+	/*
+	 * 1. Using rela, Identify entry for the switch table
+	 * 2. Retrieve base offset
+	 * 3. Retrieve branch instruction
+	 * 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
+	 */
+	sec_size = objtool_data->sh.sh_size;
+	for (i = 0, swt_info = (void *)objtool_data->data->d_buf;
+	     i < sec_size / sizeof(struct switch_table_info);
+	     i++, swt_info++) {
+		offset = i * sizeof(struct switch_table_info);
+		objtool_data_rela = find_rela_by_dest_range(objtool_data, offset,
+							    sizeof(u64));
+		/* retrieving the objtool data of the switch table we need */
+		if (objtool_data_rela == NULL ||
+		    table->sym->sec != objtool_data_rela->sym->sec ||
+		    table->addend != objtool_data_rela->addend)
+			continue;
+
+		/* retrieving switch table content */
+		switch_table = (u8 *)(rodata_sec->data->d_buf + table->addend);
+
+		/* 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));
+
+		/*
+		 * iterating over the pre-jumps instruction in order to
+		 * retrieve switch base offset.
+		 */
+		while (pre_jump_insn != NULL &&
+		       pre_jump_insn->offset <= insn->offset) {
+			if (pre_jump_insn->stack_op.src.reg == ADR_SOURCE) {
+				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 (j = 0; j < swt_info->nb_entries; j++) {
+					if (add_possible_branch(file, insn,
+								base_offset,
+								next_offset(switch_table, entry_size))) {
+						return -1;
+					}
+					switch_table += entry_size;
+				}
+			}
+			pre_jump_insn = next_insn_same_sec(file, pre_jump_insn);
+		}
+	}
 	return 0;
 }
 
@@ -32,6 +169,5 @@ struct rela *arch_find_switch_table(struct objtool_file *file,
 				    struct section *rodata_sec,
 				    unsigned long table_offset)
 {
-	file->ignore_unreachables = true;
-	return NULL;
+	return text_rela;
 }
diff --git a/tools/objtool/arch/arm64/decode.c b/tools/objtool/arch/arm64/decode.c
index a40338a895f5..44ab2299bc0f 100644
--- a/tools/objtool/arch/arm64/decode.c
+++ b/tools/objtool/arch/arm64/decode.c
@@ -613,7 +613,7 @@ int arm_decode_except_gen(u32 instr, unsigned char *type,
 		return 0;
 	case INSN_BRK:
 		if (imm16 == 0x800)
-			*type = INSN_BUG;
+			*type = INSN_NOP;
 		else if (imm16 == 0x100 || imm16 >= 0x900)
 			*type = INSN_CONTEXT_SWITCH;
 		else
diff --git a/tools/objtool/arch/arm64/include/arch_special.h b/tools/objtool/arch/arm64/include/arch_special.h
index 185103be8a51..cba432fed80f 100644
--- a/tools/objtool/arch/arm64/include/arch_special.h
+++ b/tools/objtool/arch/arm64/include/arch_special.h
@@ -15,6 +15,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
@@ -30,6 +32,14 @@
 #define ALT_ORIG_LEN_OFFSET	10
 #define ALT_NEW_LEN_OFFSET	11
 
+#define ADR_SOURCE	255
+
+struct switch_table_info {
+	u64 switch_table_label;
+	u64 nb_entries;
+	u64 offset_unsigned;
+} __attribute__((__packed__));
+
 static inline bool arch_should_ignore_feature(unsigned short feature)
 {
 	return false;
diff --git a/tools/objtool/arch/arm64/include/insn_decode.h b/tools/objtool/arch/arm64/include/insn_decode.h
index a01d76306749..65b6efecd68f 100644
--- a/tools/objtool/arch/arm64/include/insn_decode.h
+++ b/tools/objtool/arch/arm64/include/insn_decode.h
@@ -18,6 +18,7 @@
 #define _ARM_INSN_DECODE_H
 
 #include "../../../arch.h"
+#include "arch_special.h"
 
 #define INSN_RESERVED	0b0000
 #define INSN_UNALLOC_1	0b0001
@@ -58,8 +59,6 @@
 #define COMPOSED_INSN_REGS_NUM	2
 #define INSN_COMPOSED	1
 
-#define ADR_SOURCE	-1
-
 typedef int (*arm_decode_class)(u32 instr, unsigned char *type,
 				unsigned long *immediate, struct stack_op *op);
 
diff --git a/tools/objtool/check.c b/tools/objtool/check.c
index ce1165ce448a..fce8ad7ab001 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);
 
@@ -942,7 +942,7 @@ static struct rela *find_switch_table(struct objtool_file *file,
 				      struct symbol *func,
 				      struct instruction *insn)
 {
-	struct rela *text_rela, *rodata_rela;
+	struct rela *text_rela;
 	struct instruction *orig_insn = insn;
 	struct section *rodata_sec;
 	unsigned long table_offset;
@@ -1840,7 +1840,7 @@ static int validate_sibling_call(struct instruction *insn, struct insn_state *st
 {
 	if (arch_is_insn_sibling_call(insn) && has_modified_stack_frame(state)) {
 		WARN_FUNC("sibling call from callable instruction with modified stack frame",
-				insn->sec, insn->offset);
+			  insn->sec, insn->offset);
 		return 1;
 	}
 
diff --git a/tools/objtool/check.h b/tools/objtool/check.h
index 80e7a96525af..5acfd4b2951c 100644
--- a/tools/objtool/check.h
+++ b/tools/objtool/check.h
@@ -64,6 +64,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.17.1