[PATCH v2 0/5] Improve objtool jump table handling

[PATCH v2 0/5] Improve objtool jump table handling

[Ard Biesheuvel]

From: Ard Biesheuvel <ardb@kernel.org>

Jump table handling has faded into the background a little due to the
fact that jump tables are [currently] disabled when enabling retpoline
mitigations and/or IBT on x86.

However, this is likely to come back and bite us later, so it still
needs to be addressed. Given the difficulty in identifying jump tables
from .rodata references and indirect jump instructions that often have
no obvious correlation, it would be better to do this in the compiler.

This series implements [on the objtool side] the suggestion made at GNU
Cauldron this year to annotate the indirect jump with a R_X86_64_NONE
relocation that refers to the jump table, and ensure that it is covered
by a STT_OBJECT symbol whose size accurately reflects the size of the
jump table.

This can be wired up in objtool with minimal effort. The only
complication is that indirect jumps may be direct jumps in disguise, if
they target retpoline thunks. This will result in more than one
relocation attached to the same instruction, which needs careful
handling in objtool.

Other than that, changes are rather straight-forward.

Patches #4 and #5 update the CRC32C driver, which has a jump table
implemented in assembler, to a) use a relative jump table, for
compatibility with linking in PIE mode (#4) and b) make the jump table
more difficult to identify by objtool's existing heuristics, but provide
the annotation so it can found nonetheless.

This series is labeled as v2 because patch #1 was sent out before.

Changes since v1:
- tweak logic in patch #1 to ensure that all jump table entries are
  covered by the same type of relocation
- use the corrected addend when validating IBT targets
- add patches #2 - #5

Cc: Josh Poimboeuf <jpoimboe@kernel.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Jan Beulich <jbeulich@suse.com>
Cc: "Jose E. Marchesi" <jemarch@gnu.org>
Cc: Kees Cook <kees@kernel.org>

Ard Biesheuvel (5):
  objtool: Deal with relative jump tables correctly
  objtool: Allow arch code to discover jump table size
  objtool: Add support for annotated jump tables
  crypto: x86/crc32c - Use idiomatic relative jump table
  crypto: x86/crc32c - Tweak jump table to validate objtool logic

 arch/x86/crypto/crc32c-pcl-intel-asm_64.S | 40 +++++++-----
 tools/objtool/arch/loongarch/special.c    |  3 +-
 tools/objtool/arch/powerpc/special.c      |  3 +-
 tools/objtool/arch/x86/special.c          | 43 ++++++++-----
 tools/objtool/check.c                     | 65 +++++++++++++++-----
 tools/objtool/include/objtool/check.h     |  5 +-
 tools/objtool/include/objtool/elf.h       |  6 ++
 tools/objtool/include/objtool/special.h   |  3 +-
 8 files changed, 117 insertions(+), 51 deletions(-)

-- 
2.47.0.rc0.187.ge670bccf7e-goog

[PATCH v2 1/5] objtool: Deal with relative jump tables correctly

[Ard Biesheuvel]

From: Ard Biesheuvel <ardb@kernel.org>

Relative jump tables contain entries that carry the offset between the
target of the jump and the start of the jump table. This permits the use
of the PIC idiom of

    leaq    jump_table(%rip), %tbl
    movslq  (%tbl,%idx,4), %offset
    addq    %offset, %tbl
    jmp     *%tbl

The jump table entries are decorated with PC32 relocations, which record
the offset of the referenced symbol relative to the target of the
relocation, which is the individual entry in the table.  This means that
only the first entry produces the correct value directly; the subsequent
ones need to be corrected to produce the offset relative to the start of
the table, by applying an addend.

Given that the referenced symbols are anonymous, and thus already
expressed in terms of sections and addends, e.g., .text+0x5df9, the
correction is incorporated into the existing addend. The upshot of this
is that chasing the reference to find the target instruction needs to
take this second addend into account as well.

Signed-off-by: Ard Biesheuvel <ardb@kernel.org>
---
 tools/objtool/arch/x86/special.c    |  8 -------
 tools/objtool/check.c               | 24 +++++++++++++++++---
 tools/objtool/include/objtool/elf.h |  6 +++++
 3 files changed, 27 insertions(+), 11 deletions(-)

diff --git a/tools/objtool/arch/x86/special.c b/tools/objtool/arch/x86/special.c
index 4ea0f9815fda..415e4d035e53 100644
--- a/tools/objtool/arch/x86/special.c
+++ b/tools/objtool/arch/x86/special.c
@@ -150,13 +150,5 @@ struct reloc *arch_find_switch_table(struct objtool_file *file,
 	if (!rodata_reloc)
 		return NULL;
 
-	/*
-	 * Use of RIP-relative switch jumps is quite rare, and
-	 * indicates a rare GCC quirk/bug which can leave dead
-	 * code behind.
-	 */
-	if (reloc_type(text_reloc) == R_X86_64_PC32)
-		file->ignore_unreachables = true;
-
 	return rodata_reloc;
 }
diff --git a/tools/objtool/check.c b/tools/objtool/check.c
index 3cb3e9b5ad0b..7f7981a93535 100644
--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -2101,6 +2101,8 @@ static int add_jump_table(struct objtool_file *file, struct instruction *insn,
 {
 	struct symbol *pfunc = insn_func(insn)->pfunc;
 	struct reloc *table = insn_jump_table(insn);
+	unsigned int rtype = reloc_type(table);
+	bool pcrel = rtype == R_X86_64_PC32;
 	struct instruction *dest_insn;
 	unsigned int prev_offset = 0;
 	struct reloc *reloc = table;
@@ -2111,13 +2113,18 @@ static int add_jump_table(struct objtool_file *file, struct instruction *insn,
 	 * instruction.
 	 */
 	for_each_reloc_from(table->sec, reloc) {
+		unsigned long addend = reloc_addend(reloc);
 
 		/* Check for the end of the table: */
 		if (reloc != table && reloc == next_table)
 			break;
 
+		/* Each entry in the jump table should use the same relocation type */
+		if (reloc_type(reloc) != rtype)
+			break;
+
 		/* Make sure the table entries are consecutive: */
-		if (prev_offset && reloc_offset(reloc) != prev_offset + 8)
+		if (prev_offset && reloc_offset(reloc) != prev_offset + (pcrel ? 4 : 8))
 			break;
 
 		/* Detect function pointers from contiguous objects: */
@@ -2125,7 +2132,15 @@ static int add_jump_table(struct objtool_file *file, struct instruction *insn,
 		    reloc_addend(reloc) == pfunc->offset)
 			break;
 
-		dest_insn = find_insn(file, reloc->sym->sec, reloc_addend(reloc));
+		/*
+		 * Place-relative jump tables carry offsets relative to the
+		 * start of the jump table, not to the entry itself. So correct
+		 * the addend for the location of the entry in the table.
+		 */
+		if (pcrel)
+			addend -= reloc_offset(reloc) - reloc_offset(table);
+
+		dest_insn = find_insn(file, reloc->sym->sec, addend);
 		if (!dest_insn)
 			break;
 
@@ -2133,6 +2148,9 @@ static int add_jump_table(struct objtool_file *file, struct instruction *insn,
 		if (!insn_func(dest_insn) || insn_func(dest_insn)->pfunc != pfunc)
 			break;
 
+		if (pcrel)
+			reloc->sym_offset = addend;
+
 		alt = malloc(sizeof(*alt));
 		if (!alt) {
 			WARN("malloc failed");
@@ -4536,7 +4554,7 @@ static int validate_ibt_data_reloc(struct objtool_file *file,
 	struct instruction *dest;
 
 	dest = find_insn(file, reloc->sym->sec,
-			 reloc->sym->offset + reloc_addend(reloc));
+			 reloc->sym->offset + reloc_sym_offset(reloc));
 	if (!dest)
 		return 0;
 
diff --git a/tools/objtool/include/objtool/elf.h b/tools/objtool/include/objtool/elf.h
index d7e815c2fd15..f4a6307f4c08 100644
--- a/tools/objtool/include/objtool/elf.h
+++ b/tools/objtool/include/objtool/elf.h
@@ -78,6 +78,7 @@ struct reloc {
 	struct section *sec;
 	struct symbol *sym;
 	struct reloc *sym_next_reloc;
+	s64 sym_offset;
 };
 
 struct elf {
@@ -251,6 +252,11 @@ static inline s64 reloc_addend(struct reloc *reloc)
 	return __get_reloc_field(reloc, r_addend);
 }
 
+static inline s64 reloc_sym_offset(struct reloc *reloc)
+{
+	return reloc->sym_offset ?: reloc_addend(reloc);
+}
+
 static inline void set_reloc_addend(struct elf *elf, struct reloc *reloc, s64 addend)
 {
 	__set_reloc_field(reloc, r_addend, addend);
-- 
2.47.0.rc0.187.ge670bccf7e-goog

Re: [PATCH v2 1/5] objtool: Deal with relative jump tables correctly

[Peter Zijlstra]

On Thu, Oct 10, 2024 at 02:28:03PM +0200, Ard Biesheuvel wrote:
> diff --git a/tools/objtool/check.c b/tools/objtool/check.c
> index 3cb3e9b5ad0b..7f7981a93535 100644
> --- a/tools/objtool/check.c
> +++ b/tools/objtool/check.c
> @@ -2101,6 +2101,8 @@ static int add_jump_table(struct objtool_file *file, struct instruction *insn,
>  {
>  	struct symbol *pfunc = insn_func(insn)->pfunc;
>  	struct reloc *table = insn_jump_table(insn);
> +	unsigned int rtype = reloc_type(table);
> +	bool pcrel = rtype == R_X86_64_PC32;

R_DATA32 or R_TEXT32 please, the budding cross arch stuff has their own
names for all that.

Re: [PATCH v2 1/5] objtool: Deal with relative jump tables correctly

[Ard Biesheuvel]

On Thu, 10 Oct 2024 at 15:26, Peter Zijlstra <peterz@infradead.org> wrote:
>
> On Thu, Oct 10, 2024 at 02:28:03PM +0200, Ard Biesheuvel wrote:
> > diff --git a/tools/objtool/check.c b/tools/objtool/check.c
> > index 3cb3e9b5ad0b..7f7981a93535 100644
> > --- a/tools/objtool/check.c
> > +++ b/tools/objtool/check.c
> > @@ -2101,6 +2101,8 @@ static int add_jump_table(struct objtool_file *file, struct instruction *insn,
> >  {
> >       struct symbol *pfunc = insn_func(insn)->pfunc;
> >       struct reloc *table = insn_jump_table(insn);
> > +     unsigned int rtype = reloc_type(table);
> > +     bool pcrel = rtype == R_X86_64_PC32;
>
> R_DATA32 or R_TEXT32 please, the budding cross arch stuff has their own
> names for all that.
>

#define R_DATA32        R_X86_64_PC32
#define R_DATA64        R_X86_64_PC32
#define R_TEXT32        R_X86_64_PC32
#define R_TEXT64        R_X86_64_PC32

Clear as mud.

I'd guess we need the '64' variant here, but I'm not sure which one to
use for a .rodata relocation pointing to .text. Any hints?

Re: [PATCH v2 1/5] objtool: Deal with relative jump tables correctly

[Peter Zijlstra]

On Thu, Oct 10, 2024 at 03:59:43PM +0200, Ard Biesheuvel wrote:
> On Thu, 10 Oct 2024 at 15:26, Peter Zijlstra <peterz@infradead.org> wrote:
> >
> > On Thu, Oct 10, 2024 at 02:28:03PM +0200, Ard Biesheuvel wrote:
> > > diff --git a/tools/objtool/check.c b/tools/objtool/check.c
> > > index 3cb3e9b5ad0b..7f7981a93535 100644
> > > --- a/tools/objtool/check.c
> > > +++ b/tools/objtool/check.c
> > > @@ -2101,6 +2101,8 @@ static int add_jump_table(struct objtool_file *file, struct instruction *insn,
> > >  {
> > >       struct symbol *pfunc = insn_func(insn)->pfunc;
> > >       struct reloc *table = insn_jump_table(insn);
> > > +     unsigned int rtype = reloc_type(table);
> > > +     bool pcrel = rtype == R_X86_64_PC32;
> >
> > R_DATA32 or R_TEXT32 please, the budding cross arch stuff has their own
> > names for all that.
> >
> 
> #define R_DATA32        R_X86_64_PC32
> #define R_DATA64        R_X86_64_PC32
> #define R_TEXT32        R_X86_64_PC32
> #define R_TEXT64        R_X86_64_PC32
> 
> Clear as mud.
> 
> I'd guess we need the '64' variant here, but I'm not sure which one to
> use for a .rodata relocation pointing to .text. Any hints?

Josh? do R_{DATA,TEXT}64 want to be _PC64 ?

Re: [PATCH v2 1/5] objtool: Deal with relative jump tables correctly

[Josh Poimboeuf]

On Thu, Oct 10, 2024 at 04:07:45PM +0200, Peter Zijlstra wrote:
> On Thu, Oct 10, 2024 at 03:59:43PM +0200, Ard Biesheuvel wrote:
> > On Thu, 10 Oct 2024 at 15:26, Peter Zijlstra <peterz@infradead.org> wrote:
> > >
> > > On Thu, Oct 10, 2024 at 02:28:03PM +0200, Ard Biesheuvel wrote:
> > > > diff --git a/tools/objtool/check.c b/tools/objtool/check.c
> > > > index 3cb3e9b5ad0b..7f7981a93535 100644
> > > > --- a/tools/objtool/check.c
> > > > +++ b/tools/objtool/check.c
> > > > @@ -2101,6 +2101,8 @@ static int add_jump_table(struct objtool_file *file, struct instruction *insn,
> > > >  {
> > > >       struct symbol *pfunc = insn_func(insn)->pfunc;
> > > >       struct reloc *table = insn_jump_table(insn);
> > > > +     unsigned int rtype = reloc_type(table);
> > > > +     bool pcrel = rtype == R_X86_64_PC32;
> > >
> > > R_DATA32 or R_TEXT32 please, the budding cross arch stuff has their own
> > > names for all that.
> > >
> > 
> > #define R_DATA32        R_X86_64_PC32
> > #define R_DATA64        R_X86_64_PC32
> > #define R_TEXT32        R_X86_64_PC32
> > #define R_TEXT64        R_X86_64_PC32
> > 
> > Clear as mud.

Yep... :-/

> > 
> > I'd guess we need the '64' variant here, but I'm not sure which one to
> > use for a .rodata relocation pointing to .text. Any hints?

This should be R_TEXT64.

> Josh? do R_{DATA,TEXT}64 want to be _PC64 ?

Actually, R_{DATA,TEXT}32 should be R_386_PC32.

-- 
Josh

[PATCH v2 2/5] objtool: Allow arch code to discover jump table size

[Ard Biesheuvel]

From: Ard Biesheuvel <ardb@kernel.org>

In preparation for adding support for annotated jump tables, where
ELF relocations and symbols are used to describe the locations of jump
tables in the executable, refactor the jump table discovery logic so the
table size can be returned from arch_find_switch_table().

Signed-off-by: Ard Biesheuvel <ardb@kernel.org>
---
 tools/objtool/arch/loongarch/special.c  |  3 +-
 tools/objtool/arch/powerpc/special.c    |  3 +-
 tools/objtool/arch/x86/special.c        |  4 ++-
 tools/objtool/check.c                   | 31 +++++++++++++-------
 tools/objtool/include/objtool/check.h   |  5 +++-
 tools/objtool/include/objtool/special.h |  3 +-
 6 files changed, 33 insertions(+), 16 deletions(-)

diff --git a/tools/objtool/arch/loongarch/special.c b/tools/objtool/arch/loongarch/special.c
index 9bba1e9318e0..87230ed570fd 100644
--- a/tools/objtool/arch/loongarch/special.c
+++ b/tools/objtool/arch/loongarch/special.c
@@ -9,7 +9,8 @@ bool arch_support_alt_relocation(struct special_alt *special_alt,
 }
 
 struct reloc *arch_find_switch_table(struct objtool_file *file,
-				     struct instruction *insn)
+				     struct instruction *insn,
+				     unsigned long *table_size)
 {
 	return NULL;
 }
diff --git a/tools/objtool/arch/powerpc/special.c b/tools/objtool/arch/powerpc/special.c
index d33868147196..51610689abf7 100644
--- a/tools/objtool/arch/powerpc/special.c
+++ b/tools/objtool/arch/powerpc/special.c
@@ -13,7 +13,8 @@ bool arch_support_alt_relocation(struct special_alt *special_alt,
 }
 
 struct reloc *arch_find_switch_table(struct objtool_file *file,
-				    struct instruction *insn)
+				     struct instruction *insn,
+				     unsigned long *table_size)
 {
 	exit(-1);
 }
diff --git a/tools/objtool/arch/x86/special.c b/tools/objtool/arch/x86/special.c
index 415e4d035e53..f8fb67636384 100644
--- a/tools/objtool/arch/x86/special.c
+++ b/tools/objtool/arch/x86/special.c
@@ -109,7 +109,8 @@ bool arch_support_alt_relocation(struct special_alt *special_alt,
  *    NOTE: MITIGATION_RETPOLINE made it harder still to decode dynamic jumps.
  */
 struct reloc *arch_find_switch_table(struct objtool_file *file,
-				    struct instruction *insn)
+				     struct instruction *insn,
+				     unsigned long *table_size)
 {
 	struct reloc  *text_reloc, *rodata_reloc;
 	struct section *table_sec;
@@ -150,5 +151,6 @@ struct reloc *arch_find_switch_table(struct objtool_file *file,
 	if (!rodata_reloc)
 		return NULL;
 
+	*table_size = 0;
 	return rodata_reloc;
 }
diff --git a/tools/objtool/check.c b/tools/objtool/check.c
index 7f7981a93535..5f711ac5b43d 100644
--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -150,6 +150,15 @@ static inline struct reloc *insn_jump_table(struct instruction *insn)
 	return NULL;
 }
 
+static inline unsigned long insn_jump_table_size(struct instruction *insn)
+{
+	if (insn->type == INSN_JUMP_DYNAMIC ||
+	    insn->type == INSN_CALL_DYNAMIC)
+		return insn->_jump_table_size;
+
+	return 0;
+}
+
 static bool is_jump_table_jump(struct instruction *insn)
 {
 	struct alt_group *alt_group = insn->alt_group;
@@ -2099,6 +2108,7 @@ static int add_special_section_alts(struct objtool_file *file)
 static int add_jump_table(struct objtool_file *file, struct instruction *insn,
 			  struct reloc *next_table)
 {
+	unsigned long table_size = insn_jump_table_size(insn);
 	struct symbol *pfunc = insn_func(insn)->pfunc;
 	struct reloc *table = insn_jump_table(insn);
 	unsigned int rtype = reloc_type(table);
@@ -2116,6 +2126,8 @@ static int add_jump_table(struct objtool_file *file, struct instruction *insn,
 		unsigned long addend = reloc_addend(reloc);
 
 		/* Check for the end of the table: */
+		if (table_size && reloc_offset(reloc) - reloc_offset(table) >= table_size)
+			break;
 		if (reloc != table && reloc == next_table)
 			break;
 
@@ -2175,12 +2187,12 @@ static int add_jump_table(struct objtool_file *file, struct instruction *insn,
  * find_jump_table() - Given a dynamic jump, find the switch jump table
  * associated with it.
  */
-static struct reloc *find_jump_table(struct objtool_file *file,
-				      struct symbol *func,
-				      struct instruction *insn)
+static void find_jump_table(struct objtool_file *file, struct symbol *func,
+			    struct instruction *insn)
 {
 	struct reloc *table_reloc;
 	struct instruction *dest_insn, *orig_insn = insn;
+	unsigned long table_size;
 
 	/*
 	 * Backward search using the @first_jump_src links, these help avoid
@@ -2201,17 +2213,17 @@ static struct reloc *find_jump_table(struct objtool_file *file,
 		     insn->jump_dest->offset > orig_insn->offset))
 		    break;
 
-		table_reloc = arch_find_switch_table(file, insn);
+		table_reloc = arch_find_switch_table(file, insn, &table_size);
 		if (!table_reloc)
 			continue;
 		dest_insn = find_insn(file, table_reloc->sym->sec, reloc_addend(table_reloc));
 		if (!dest_insn || !insn_func(dest_insn) || insn_func(dest_insn)->pfunc != func)
 			continue;
 
-		return table_reloc;
+		orig_insn->_jump_table = table_reloc;
+		orig_insn->_jump_table_size = table_size;
+		break;
 	}
-
-	return NULL;
 }
 
 /*
@@ -2222,7 +2234,6 @@ static void mark_func_jump_tables(struct objtool_file *file,
 				    struct symbol *func)
 {
 	struct instruction *insn, *last = NULL;
-	struct reloc *reloc;
 
 	func_for_each_insn(file, func, insn) {
 		if (!last)
@@ -2245,9 +2256,7 @@ static void mark_func_jump_tables(struct objtool_file *file,
 		if (insn->type != INSN_JUMP_DYNAMIC)
 			continue;
 
-		reloc = find_jump_table(file, func, insn);
-		if (reloc)
-			insn->_jump_table = reloc;
+		find_jump_table(file, func, insn);
 	}
 }
 
diff --git a/tools/objtool/include/objtool/check.h b/tools/objtool/include/objtool/check.h
index daa46f1f0965..e1cd13cd28a3 100644
--- a/tools/objtool/include/objtool/check.h
+++ b/tools/objtool/include/objtool/check.h
@@ -71,7 +71,10 @@ struct instruction {
 	struct instruction *first_jump_src;
 	union {
 		struct symbol *_call_dest;
-		struct reloc *_jump_table;
+		struct {
+			struct reloc *_jump_table;
+			unsigned long _jump_table_size;
+		};
 	};
 	struct alternative *alts;
 	struct symbol *sym;
diff --git a/tools/objtool/include/objtool/special.h b/tools/objtool/include/objtool/special.h
index 89ee12b1a138..e049679bb17b 100644
--- a/tools/objtool/include/objtool/special.h
+++ b/tools/objtool/include/objtool/special.h
@@ -38,5 +38,6 @@ bool arch_support_alt_relocation(struct special_alt *special_alt,
 				 struct instruction *insn,
 				 struct reloc *reloc);
 struct reloc *arch_find_switch_table(struct objtool_file *file,
-				    struct instruction *insn);
+				     struct instruction *insn,
+				     unsigned long *table_size);
 #endif /* _SPECIAL_H */
-- 
2.47.0.rc0.187.ge670bccf7e-goog

Re: [PATCH v2 2/5] objtool: Allow arch code to discover jump table size

[Josh Poimboeuf]

On Thu, Oct 10, 2024 at 02:28:04PM +0200, Ard Biesheuvel wrote:
> @@ -2222,7 +2234,6 @@ static void mark_func_jump_tables(struct objtool_file *file,
>  				    struct symbol *func)
>  {
>  	struct instruction *insn, *last = NULL;
> -	struct reloc *reloc;
>  
>  	func_for_each_insn(file, func, insn) {
>  		if (!last)
> @@ -2245,9 +2256,7 @@ static void mark_func_jump_tables(struct objtool_file *file,
>  		if (insn->type != INSN_JUMP_DYNAMIC)
>  			continue;
>  
> -		reloc = find_jump_table(file, func, insn);
> -		if (reloc)
> -			insn->_jump_table = reloc;
> +		find_jump_table(file, func, insn);

Can we detect the annotation here, and if it exists, pivot to a separate
generic implementation which skips all the arch-specific code and hacks?

That way we could keep the "ugly" separate, and also have all arches
supported by default.

-- 
Josh

Re: [PATCH v2 2/5] objtool: Allow arch code to discover jump table size

[Ard Biesheuvel]

On Thu, 10 Oct 2024 at 21:52, Josh Poimboeuf <jpoimboe@kernel.org> wrote:
>
> On Thu, Oct 10, 2024 at 02:28:04PM +0200, Ard Biesheuvel wrote:
> > @@ -2222,7 +2234,6 @@ static void mark_func_jump_tables(struct objtool_file *file,
> >                                   struct symbol *func)
> >  {
> >       struct instruction *insn, *last = NULL;
> > -     struct reloc *reloc;
> >
> >       func_for_each_insn(file, func, insn) {
> >               if (!last)
> > @@ -2245,9 +2256,7 @@ static void mark_func_jump_tables(struct objtool_file *file,
> >               if (insn->type != INSN_JUMP_DYNAMIC)
> >                       continue;
> >
> > -             reloc = find_jump_table(file, func, insn);
> > -             if (reloc)
> > -                     insn->_jump_table = reloc;
> > +             find_jump_table(file, func, insn);
>
> Can we detect the annotation here, and if it exists, pivot to a separate
> generic implementation which skips all the arch-specific code and hacks?
>
> That way we could keep the "ugly" separate, and also have all arches
> supported by default.
>

I had a stab at this, and while the code changes are a bit intrusive,
the end result is much better for it (IMHO).

In the end, the logic in arch_find_switch_table() is mostly generic
anyway, but it is the code traversal in check.c that is the "ugly". So
I moved lots of things around. I'll send that out before signing off
today.

[PATCH v2 3/5] objtool: Add support for annotated jump tables

[Ard Biesheuvel]

From: Ard Biesheuvel <ardb@kernel.org>

Add logic to follow R_X86_64_NONE relocations attached to indirect
jumps, which are emitted to annotate jump tables, which are otherwise
difficult to spot reliably.

If an ELF symbol is associated with the jump table, its size is taken as
the size of the jump table, and subsequently used to limit the traversal
of the table and validate its jump destinations.

One complicating factor is that indirect jumps may actually be direct
jumps to retpoline thunks, and therefore already have a relocation
associated with it. Accommodate these by ignoring R_*_NONE relocations
in insn_reloc(), so that the existing code does not get confused by
them.

E.g.,

  8c:   48 63 7c 85 00          movslq 0x0(%rbp,%rax,4),%rdi
  91:   48 01 ef                add    %rbp,%rdi
  94:   e9 00 00 00 00          jmp    99 <crc_pcl+0x89>
            94: R_X86_64_NONE       .rodata+0x400
            95: R_X86_64_PLT32      __x86_indirect_thunk_rdi-0x4

Signed-off-by: Ard Biesheuvel <ardb@kernel.org>
---
 tools/objtool/arch/x86/special.c | 33 ++++++++++++++++----
 tools/objtool/check.c            | 10 ++++--
 2 files changed, 35 insertions(+), 8 deletions(-)

diff --git a/tools/objtool/arch/x86/special.c b/tools/objtool/arch/x86/special.c
index f8fb67636384..67c20623d7f7 100644
--- a/tools/objtool/arch/x86/special.c
+++ b/tools/objtool/arch/x86/special.c
@@ -115,30 +115,51 @@ struct reloc *arch_find_switch_table(struct objtool_file *file,
 	struct reloc  *text_reloc, *rodata_reloc;
 	struct section *table_sec;
 	unsigned long table_offset;
+	struct symbol *sym;
 
 	/* look for a relocation which references .rodata */
 	text_reloc = find_reloc_by_dest_range(file->elf, insn->sec,
 					      insn->offset, insn->len);
-	if (!text_reloc || text_reloc->sym->type != STT_SECTION ||
-	    !text_reloc->sym->sec->rodata)
+	if (!text_reloc || !text_reloc->sym->sec->rodata)
 		return NULL;
 
-	table_offset = reloc_addend(text_reloc);
+	/*
+	 * If the indirect jump instruction itself is annotated with a
+	 * R_X86_64_NONE relocation, it should point to the jump table
+	 * in .rodata. In this case, the ELF symbol will give us the
+	 * size of the table. Ignore other occurrences of R_X86_64_NONE.
+	 */
+	if (reloc_type(text_reloc) == R_X86_64_NONE &&
+	    insn->type != INSN_JUMP_DYNAMIC)
+		return NULL;
+
+	table_offset = text_reloc->sym->offset + reloc_addend(text_reloc);
 	table_sec = text_reloc->sym->sec;
 
 	if (reloc_type(text_reloc) == R_X86_64_PC32)
 		table_offset += 4;
 
+	switch (text_reloc->sym->type) {
+	case STT_OBJECT:
+		sym = text_reloc->sym;
+		break;
+	case  STT_SECTION:
+		sym = find_symbol_containing(table_sec, table_offset);
+		break;
+	default:
+		return NULL;
+	}
+
 	/*
 	 * Make sure the .rodata address isn't associated with a
-	 * symbol.  GCC jump tables are anonymous data.
+	 * symbol. Unannotated GCC jump tables are anonymous data.
 	 *
 	 * Also support C jump tables which are in the same format as
 	 * switch jump tables.  For objtool to recognize them, they
 	 * need to be placed in the C_JUMP_TABLE_SECTION section.  They
 	 * have symbols associated with them.
 	 */
-	if (find_symbol_containing(table_sec, table_offset) &&
+	if (reloc_type(text_reloc) != R_X86_64_NONE && sym &&
 	    strcmp(table_sec->name, C_JUMP_TABLE_SECTION))
 		return NULL;
 
@@ -151,6 +172,6 @@ struct reloc *arch_find_switch_table(struct objtool_file *file,
 	if (!rodata_reloc)
 		return NULL;
 
-	*table_size = 0;
+	*table_size = sym ? sym->len : 0;
 	return rodata_reloc;
 }
diff --git a/tools/objtool/check.c b/tools/objtool/check.c
index 5f711ac5b43d..6521c82880f0 100644
--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -1386,6 +1386,8 @@ __weak const char *arch_nop_fentry_call(int len)
 
 static struct reloc *insn_reloc(struct objtool_file *file, struct instruction *insn)
 {
+	unsigned long offset = insn->offset;
+	unsigned int len = insn->len;
 	struct reloc *reloc;
 
 	if (insn->no_reloc)
@@ -1394,8 +1396,12 @@ static struct reloc *insn_reloc(struct objtool_file *file, struct instruction *i
 	if (!file)
 		return NULL;
 
-	reloc = find_reloc_by_dest_range(file->elf, insn->sec,
-					 insn->offset, insn->len);
+	do {
+		/* Skip any R_*_NONE relocations */
+		reloc = find_reloc_by_dest_range(file->elf, insn->sec,
+						 offset++, len--);
+	} while (len && reloc && reloc_type(reloc) == 0);
+
 	if (!reloc) {
 		insn->no_reloc = 1;
 		return NULL;
-- 
2.47.0.rc0.187.ge670bccf7e-goog

Re: [PATCH v2 3/5] objtool: Add support for annotated jump tables

[Josh Poimboeuf]

On Thu, Oct 10, 2024 at 02:28:05PM +0200, Ard Biesheuvel wrote:
> @@ -1394,8 +1396,12 @@ static struct reloc *insn_reloc(struct objtool_file *file, struct instruction *i
>  	if (!file)
>  		return NULL;
>  
> -	reloc = find_reloc_by_dest_range(file->elf, insn->sec,
> -					 insn->offset, insn->len);
> +	do {
> +		/* Skip any R_*_NONE relocations */
> +		reloc = find_reloc_by_dest_range(file->elf, insn->sec,
> +						 offset++, len--);
> +	} while (len && reloc && reloc_type(reloc) == 0);

s/0/R_NONE/

-- 
Josh

Re: [PATCH v2 3/5] objtool: Add support for annotated jump tables

[Josh Poimboeuf]

On Thu, Oct 10, 2024 at 02:28:05PM +0200, Ard Biesheuvel wrote:
> +++ b/tools/objtool/arch/x86/special.c
> @@ -115,30 +115,51 @@ struct reloc *arch_find_switch_table(struct objtool_file *file,
>  	struct reloc  *text_reloc, *rodata_reloc;
>  	struct section *table_sec;
>  	unsigned long table_offset;
> +	struct symbol *sym;
>  
>  	/* look for a relocation which references .rodata */
>  	text_reloc = find_reloc_by_dest_range(file->elf, insn->sec,
>  					      insn->offset, insn->len);

Hm, we can probably put insn_reloc() in check.h and use that here to
take advantage of its caching for the no_reloc case.

> +	switch (text_reloc->sym->type) {
> +	case STT_OBJECT:
> +		sym = text_reloc->sym;
> +		break;
> +	case  STT_SECTION:
	     ^
	     extra whitespace

-- 
Josh

Re: [PATCH v2 3/5] objtool: Add support for annotated jump tables

[Ard Biesheuvel]

On Thu, 10 Oct 2024 at 22:15, Josh Poimboeuf <jpoimboe@kernel.org> wrote:
>
> On Thu, Oct 10, 2024 at 02:28:05PM +0200, Ard Biesheuvel wrote:
> > +++ b/tools/objtool/arch/x86/special.c
> > @@ -115,30 +115,51 @@ struct reloc *arch_find_switch_table(struct objtool_file *file,
> >       struct reloc  *text_reloc, *rodata_reloc;
> >       struct section *table_sec;
> >       unsigned long table_offset;
> > +     struct symbol *sym;
> >
> >       /* look for a relocation which references .rodata */
> >       text_reloc = find_reloc_by_dest_range(file->elf, insn->sec,
> >                                             insn->offset, insn->len);
>
> Hm, we can probably put insn_reloc() in check.h and use that here to
> take advantage of its caching for the no_reloc case.
>

insn_reloc() filters out R_*_NONE relocations, for the reasons pointed
out in the commit log.

Re: [PATCH v2 3/5] objtool: Add support for annotated jump tables

[Josh Poimboeuf]

On Fri, Oct 11, 2024 at 08:29:48AM +0200, Ard Biesheuvel wrote:
> On Thu, 10 Oct 2024 at 22:15, Josh Poimboeuf <jpoimboe@kernel.org> wrote:
> >
> > On Thu, Oct 10, 2024 at 02:28:05PM +0200, Ard Biesheuvel wrote:
> > > +++ b/tools/objtool/arch/x86/special.c
> > > @@ -115,30 +115,51 @@ struct reloc *arch_find_switch_table(struct objtool_file *file,
> > >       struct reloc  *text_reloc, *rodata_reloc;
> > >       struct section *table_sec;
> > >       unsigned long table_offset;
> > > +     struct symbol *sym;
> > >
> > >       /* look for a relocation which references .rodata */
> > >       text_reloc = find_reloc_by_dest_range(file->elf, insn->sec,
> > >                                             insn->offset, insn->len);
> >
> > Hm, we can probably put insn_reloc() in check.h and use that here to
> > take advantage of its caching for the no_reloc case.
> >
> 
> insn_reloc() filters out R_*_NONE relocations, for the reasons pointed
> out in the commit log.

True, unless this becomes the fallback code for the generic "no
annotations" case as I suggested elsewhere.

Regardless we should be sure to write and read insn->no_reloc where we
can to minimize duplicate reloc lookups.

-- 
Josh

[PATCH v2 4/5] crypto: x86/crc32c - Use idiomatic relative jump table

[Ard Biesheuvel]

From: Ard Biesheuvel <ardb@kernel.org>

The original crc32c code used a place-relative jump table but with a
slightly awkward use of two separate symbols. To help objtool, this was
replaced with a bog-standard position dependent jump table call, which
was subsequently tweaked to use a RIP-relative reference to the table,
but still populate it with absolute 64-bit references.

Given that objtool will need to be taught about the jump table idiom
that compilers use when running with -fpie enabled, let's update the
jump table in the crc32c code once again to use this standard idiom,
where the jump table carries 32-bit references relative to the start of
the table, and the destination address can be obtained by adding the
two.

Signed-off-by: Ard Biesheuvel <ardb@kernel.org>
---
 arch/x86/crypto/crc32c-pcl-intel-asm_64.S | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/arch/x86/crypto/crc32c-pcl-intel-asm_64.S b/arch/x86/crypto/crc32c-pcl-intel-asm_64.S
index bbcff1fb78cb..45b005935194 100644
--- a/arch/x86/crypto/crc32c-pcl-intel-asm_64.S
+++ b/arch/x86/crypto/crc32c-pcl-intel-asm_64.S
@@ -53,7 +53,7 @@
 .endm
 
 .macro JMPTBL_ENTRY i
-.quad .Lcrc_\i
+.long .Lcrc_\i - jump_table
 .endm
 
 .macro JNC_LESS_THAN j
@@ -169,7 +169,8 @@ SYM_FUNC_START(crc_pcl)
 
 	## branch into array
 	leaq	jump_table(%rip), %bufp
-	mov	(%bufp,%rax,8), %bufp
+	movslq	(%bufp,%rax,4), len
+	addq	len, %bufp
 	JMP_NOSPEC bufp
 
 	################################################################
-- 
2.47.0.rc0.187.ge670bccf7e-goog

[PATCH v2 5/5] crypto: x86/crc32c - Tweak jump table to validate objtool logic

[Ard Biesheuvel]

From: Ard Biesheuvel <ardb@kernel.org>

Tweak the jump table so
- the address is taken far way from its use
- its offset from the start of .rodata is != 0x0
- its type is STT_OBJECT and its size is set to the size of the actual
  table
- the indirect jump is annotated with a R_X86_64_NONE relocation
  pointing to the jump table

Signed-off-by: Ard Biesheuvel <ardb@kernel.org>
---
 arch/x86/crypto/crc32c-pcl-intel-asm_64.S | 39 +++++++++++---------
 1 file changed, 22 insertions(+), 17 deletions(-)

diff --git a/arch/x86/crypto/crc32c-pcl-intel-asm_64.S b/arch/x86/crypto/crc32c-pcl-intel-asm_64.S
index 45b005935194..ba1cca66875b 100644
--- a/arch/x86/crypto/crc32c-pcl-intel-asm_64.S
+++ b/arch/x86/crypto/crc32c-pcl-intel-asm_64.S
@@ -93,10 +93,13 @@ SYM_FUNC_START(crc_pcl)
 #define    crc1		%r9
 #define    crc2		%r10
 
+	pushq	%rbp
 	pushq   %rbx
 	pushq   %rdi
 	pushq   %rsi
 
+	leaq	jump_table(%rip), %rbp
+
 	## Move crc_init for Linux to a different
 	mov     crc_init_arg, crc_init
 
@@ -168,9 +171,9 @@ SYM_FUNC_START(crc_pcl)
 	xor     crc2, crc2
 
 	## branch into array
-	leaq	jump_table(%rip), %bufp
-	movslq	(%bufp,%rax,4), len
-	addq	len, %bufp
+	movslq	(%rbp,%rax,4), %bufp
+	addq	%rbp, %bufp
+	.reloc	., R_X86_64_NONE, jump_table
 	JMP_NOSPEC bufp
 
 	################################################################
@@ -310,24 +313,11 @@ LABEL less_than_ %j			# less_than_j: Length should be in
 	popq    %rsi
 	popq    %rdi
 	popq    %rbx
+	popq    %rbp
         RET
 SYM_FUNC_END(crc_pcl)
 
 .section	.rodata, "a", @progbits
-        ################################################################
-        ## jump table        Table is 129 entries x 2 bytes each
-        ################################################################
-.align 4
-jump_table:
-	i=0
-.rept 129
-.altmacro
-JMPTBL_ENTRY %i
-.noaltmacro
-	i=i+1
-.endr
-
-
 	################################################################
 	## PCLMULQDQ tables
 	## Table is 128 entries x 2 words (8 bytes) each
@@ -462,3 +452,18 @@ K_table:
 	.long 0x45cddf4e, 0xe0ac139e
 	.long 0xacfa3103, 0x6c23e841
 	.long 0xa51b6135, 0x170076fa
+
+        ################################################################
+        ## jump table        Table is 129 entries x 2 bytes each
+        ################################################################
+.align 4
+jump_table:
+	i=0
+.rept 129
+.altmacro
+JMPTBL_ENTRY %i
+.noaltmacro
+	i=i+1
+.endr
+.size	jump_table, . - jump_table
+.type	jump_table, @object
-- 
2.47.0.rc0.187.ge670bccf7e-goog

Re: [PATCH v2 5/5] crypto: x86/crc32c - Tweak jump table to validate objtool logic

[Josh Poimboeuf]

On Thu, Oct 10, 2024 at 02:28:07PM +0200, Ard Biesheuvel wrote:
> From: Ard Biesheuvel <ardb@kernel.org>
> 
> Tweak the jump table so
> - the address is taken far way from its use
> - its offset from the start of .rodata is != 0x0
> - its type is STT_OBJECT and its size is set to the size of the actual
>   table
> - the indirect jump is annotated with a R_X86_64_NONE relocation
>   pointing to the jump table
> 
> Signed-off-by: Ard Biesheuvel <ardb@kernel.org>

This needs more "why", I assume the goals are to add the annotations +
confuse objtool if it doesn't read them properly?

-- 
Josh

Re: [PATCH v2 5/5] crypto: x86/crc32c - Tweak jump table to validate objtool logic

[Ard Biesheuvel]

On Thu, 10 Oct 2024 at 22:34, Josh Poimboeuf <jpoimboe@kernel.org> wrote:
>
> On Thu, Oct 10, 2024 at 02:28:07PM +0200, Ard Biesheuvel wrote:
> > From: Ard Biesheuvel <ardb@kernel.org>
> >
> > Tweak the jump table so
> > - the address is taken far way from its use
> > - its offset from the start of .rodata is != 0x0
> > - its type is STT_OBJECT and its size is set to the size of the actual
> >   table
> > - the indirect jump is annotated with a R_X86_64_NONE relocation
> >   pointing to the jump table
> >
> > Signed-off-by: Ard Biesheuvel <ardb@kernel.org>
>
> This needs more "why", I assume the goals are to add the annotations +
> confuse objtool if it doesn't read them properly?
>

As presented, this is just a vehicle to test the other changes in the
series. That is why I split it off from the previous one.

Whether or not we want this code in the tree is up for debate, but I
guess it could be useful as a canary for objtool, given that most
configs now disable jump tables entirely.

Re: [PATCH v2 5/5] crypto: x86/crc32c - Tweak jump table to validate objtool logic

[Josh Poimboeuf]

On Fri, Oct 11, 2024 at 08:32:33AM +0200, Ard Biesheuvel wrote:
> On Thu, 10 Oct 2024 at 22:34, Josh Poimboeuf <jpoimboe@kernel.org> wrote:
> >
> > On Thu, Oct 10, 2024 at 02:28:07PM +0200, Ard Biesheuvel wrote:
> > > From: Ard Biesheuvel <ardb@kernel.org>
> > >
> > > Tweak the jump table so
> > > - the address is taken far way from its use
> > > - its offset from the start of .rodata is != 0x0
> > > - its type is STT_OBJECT and its size is set to the size of the actual
> > >   table
> > > - the indirect jump is annotated with a R_X86_64_NONE relocation
> > >   pointing to the jump table
> > >
> > > Signed-off-by: Ard Biesheuvel <ardb@kernel.org>
> >
> > This needs more "why", I assume the goals are to add the annotations +
> > confuse objtool if it doesn't read them properly?
> >
> 
> As presented, this is just a vehicle to test the other changes in the
> series. That is why I split it off from the previous one.
> 
> Whether or not we want this code in the tree is up for debate, but I
> guess it could be useful as a canary for objtool, given that most
> configs now disable jump tables entirely.

The annotations are definitely needed since that's the future of jump
table handling.

The rest of the changes aren't worth the effort IMO.  In general we
don't compromise code quality to make objtool happy.

And "unit test for deprecated jump table detection" is even less of a
justification than would be something like "objtool can't otherwise
follow the code".

-- 
Josh

Re: [PATCH v2 5/5] crypto: x86/crc32c - Tweak jump table to validate objtool logic

[Ard Biesheuvel]

On Fri, 11 Oct 2024 at 18:05, Josh Poimboeuf <jpoimboe@kernel.org> wrote:
>
> On Fri, Oct 11, 2024 at 08:32:33AM +0200, Ard Biesheuvel wrote:
> > On Thu, 10 Oct 2024 at 22:34, Josh Poimboeuf <jpoimboe@kernel.org> wrote:
> > >
> > > On Thu, Oct 10, 2024 at 02:28:07PM +0200, Ard Biesheuvel wrote:
> > > > From: Ard Biesheuvel <ardb@kernel.org>
> > > >
> > > > Tweak the jump table so
> > > > - the address is taken far way from its use
> > > > - its offset from the start of .rodata is != 0x0
> > > > - its type is STT_OBJECT and its size is set to the size of the actual
> > > >   table
> > > > - the indirect jump is annotated with a R_X86_64_NONE relocation
> > > >   pointing to the jump table
> > > >
> > > > Signed-off-by: Ard Biesheuvel <ardb@kernel.org>
> > >
> > > This needs more "why", I assume the goals are to add the annotations +
> > > confuse objtool if it doesn't read them properly?
> > >
> >
> > As presented, this is just a vehicle to test the other changes in the
> > series. That is why I split it off from the previous one.
> >
> > Whether or not we want this code in the tree is up for debate, but I
> > guess it could be useful as a canary for objtool, given that most
> > configs now disable jump tables entirely.
>
> The annotations are definitely needed since that's the future of jump
> table handling.
>

Yeah, I'll split those off

> The rest of the changes aren't worth the effort IMO.  In general we
> don't compromise code quality to make objtool happy.
>
> And "unit test for deprecated jump table detection" is even less of a
> justification than would be something like "objtool can't otherwise
> follow the code".
>

No, quite the opposite - the changes will confuse objtool and so it
will only work correctly if the annotation is provided. That was the
point of this patch, but as I said, I never intended those changes to
be merged.

Re: [PATCH v2 0/5] Improve objtool jump table handling

[Ard Biesheuvel]

On Thu, 10 Oct 2024 at 14:28, Ard Biesheuvel <ardb+git@google.com> wrote:
>
> From: Ard Biesheuvel <ardb@kernel.org>
>
> Jump table handling has faded into the background a little due to the
> fact that jump tables are [currently] disabled when enabling retpoline
> mitigations and/or IBT on x86.
>
> However, this is likely to come back and bite us later, so it still
> needs to be addressed. Given the difficulty in identifying jump tables
> from .rodata references and indirect jump instructions that often have
> no obvious correlation, it would be better to do this in the compiler.
>
> This series implements [on the objtool side] the suggestion made at GNU
> Cauldron this year to annotate the indirect jump with a R_X86_64_NONE
> relocation that refers to the jump table, and ensure that it is covered
> by a STT_OBJECT symbol whose size accurately reflects the size of the
> jump table.
>

For the adventurous, I have a branch [0] that implements the first
part of this in Clang.

Getting the jump table emitted as a STT_OBJECT with a proper size
shouldn't be too hard either, but I'll look into that later.


[0] https://github.com/ardbiesheuvel/llvm-project/tree/jump-table-annotations

Re: [PATCH v2 0/5] Improve objtool jump table handling

[Josh Poimboeuf]

On Thu, Oct 10, 2024 at 07:50:17PM +0200, Ard Biesheuvel wrote:
> On Thu, 10 Oct 2024 at 14:28, Ard Biesheuvel <ardb+git@google.com> wrote:
> >
> > From: Ard Biesheuvel <ardb@kernel.org>
> >
> > Jump table handling has faded into the background a little due to the
> > fact that jump tables are [currently] disabled when enabling retpoline
> > mitigations and/or IBT on x86.
> >
> > However, this is likely to come back and bite us later, so it still
> > needs to be addressed. Given the difficulty in identifying jump tables
> > from .rodata references and indirect jump instructions that often have
> > no obvious correlation, it would be better to do this in the compiler.
> >
> > This series implements [on the objtool side] the suggestion made at GNU
> > Cauldron this year to annotate the indirect jump with a R_X86_64_NONE
> > relocation that refers to the jump table, and ensure that it is covered
> > by a STT_OBJECT symbol whose size accurately reflects the size of the
> > jump table.
> >
> 
> For the adventurous, I have a branch [0] that implements the first
> part of this in Clang.
> 
> Getting the jump table emitted as a STT_OBJECT with a proper size
> shouldn't be too hard either, but I'll look into that later.
> 
> 
> [0] https://github.com/ardbiesheuvel/llvm-project/tree/jump-table-annotations

That was fast!  This is good stuff, thank you for working on this.

-- 
Josh