[PATCH] objtool: Deal with relative jump tables correctly

[PATCH] 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 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 to the target of the relocation.
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 accurately, by applying an addend.

Given that the referenced symbols are 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.

Cc: Josh Poimboeuf <jpoimboe@kernel.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Signed-off-by: Ard Biesheuvel <ardb@kernel.org>
---
 tools/objtool/arch/x86/special.c |  8 --------
 tools/objtool/check.c            | 14 ++++++++++++--
 2 files changed, 12 insertions(+), 10 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..db5c5069473f 100644
--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -2111,13 +2111,15 @@ static int add_jump_table(struct objtool_file *file, struct instruction *insn,
 	 * instruction.
 	 */
 	for_each_reloc_from(table->sec, reloc) {
+		bool pcrel = reloc_type(reloc) == R_X86_64_PC32;
+		unsigned long addend = reloc_addend(reloc);
 
 		/* Check for the end of the table: */
 		if (reloc != table && reloc == next_table)
 			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 +2127,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;
 
-- 
2.47.0.rc0.187.ge670bccf7e-goog

Re: [PATCH] objtool: Deal with relative jump tables correctly

[Josh Poimboeuf]

On Tue, Oct 08, 2024 at 12:47:48AM +0200, Ard Biesheuvel wrote:
> -	/*
> -	 * 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;
> -

I'm not sure if this bug still exists on current GCC versions.  If so,
it will start reporting "unreachable instruction" warnings again and
we'll have to figure out a way to resolve that.

Otherwise the patch looks ok.

-- 
Josh

Re: [PATCH] objtool: Deal with relative jump tables correctly

[Ard Biesheuvel]

On Tue, 8 Oct 2024 at 19:42, Josh Poimboeuf <jpoimboe@kernel.org> wrote:
>
> On Tue, Oct 08, 2024 at 12:47:48AM +0200, Ard Biesheuvel wrote:
> > -     /*
> > -      * 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;
> > -
>
> I'm not sure if this bug still exists on current GCC versions.  If so,
> it will start reporting "unreachable instruction" warnings again and
> we'll have to figure out a way to resolve that.
>

Ah, I mistook this for a check against the first entry in the table,
but it is the reference *to* the table from the code.

So I'll just leave this alone.

> Otherwise the patch looks ok.
>

Thanks. I've added another tweak locally so validate_ibt_data_reloc()
uses the corrected offset as well, or I end up with !ENDBR warnings.
So with that in place, objtool can decipher the jump table if it
manages to recognize it as one.

However, there are pathological cases (see one below) where the LEA
that takes the address of the jump table is ridiculously far away from
the indirect jump, resulting in a warning like

vmlinux.o: warning: objtool: fdt_pmu_probe_pmu_dev.isra.0+0x229:
sibling call from callable instruction with modified stack frame


This is with GCC 14 (it is the only warning introduced by PIC codegen
in an allmodconfig build), and I suspect that this might happen with
non-PIC codegen too, right?

So how important is jump table support now that it is turned off in
most cases? And has there been any movement on compiler annotations?
If this is worth while, it is something I could look into: Kees and I
work very closely with both the GCC and the Clang folks, and have
contributed other features that are specific to the kernel.







ffffffff83203a40 <fdt_pmu_probe_pmu_dev.isra.0>:
3a40:  nopl   0x0(%rax,%rax,1)
3a45:  push   %r15
3a47:  push   %r14
3a49:  lea    0x597a98(%rip),%r14  <--- load of jump table address
3a50:  push   %r13
3a52:  mov    %rsi,%r13
3a55:  push   %r12
3a57:  lea    0x530(%r13),%r15
3a5e:  push   %rbp
3a5f:  push   %rbx
3a60:  mov    %rdi,%rbx
3a63:  sub    $0x10,%rsp
3a67:  mov    0x40(%rsp),%rdi
3a6c:  call   ffffffff81745c00 <__tsan_func_entry>
3a71:  call   ffffffff814ae4c0 <__sanitizer_cov_trace_pc>
3a76:  mov    %r15,%rdi
3a79:  call   ffffffff81747a00 <__tsan_read8>
3a7e:  mov    0x530(%r13),%rdi
3a85:  xor    %esi,%esi
3a87:  call   ffffffff82a25800 <of_get_next_child>
3a8c:  mov    %rax,%r12
3a8f:  call   ffffffff814ae4c0 <__sanitizer_cov_trace_pc>
3a94:  test   %r12,%r12
3a97:  je     ffffffff83203d55 <fdt_pmu_probe_pmu_dev.isra.0+0x315>
3a9d:  call   ffffffff814ae4c0 <__sanitizer_cov_trace_pc>
3aa2:  mov    %r12,%rdi
3aa5:  call   ffffffff82a26e00 <of_device_is_available>
3aaa:  xor    %edi,%edi
3aac:  mov    %eax,%ebp
3aae:  mov    %eax,%esi
3ab0:  call   ffffffff814ae740 <__sanitizer_cov_trace_const_cmp1>
3ab5:  test   %bpl,%bpl
3ab8:  je     ffffffff83203d31 <fdt_pmu_probe_pmu_dev.isra.0+0x2f1>
3abe:  call   ffffffff814ae4c0 <__sanitizer_cov_trace_pc>
3ac3:  lea    0x68e996(%rip),%rsi        # ffffffff83892460 <.LC29>
3aca:  mov    %r12,%rdi
3acd:  call   ffffffff82a26180 <of_device_is_compatible>
3ad2:  xor    %edi,%edi
3ad4:  mov    %eax,%ebp
3ad6:  mov    %eax,%esi
3ad8:  call   ffffffff814ae7c0 <__sanitizer_cov_trace_const_cmp4>
3add:  test   %ebp,%ebp
3adf:  je     ffffffff83203b03 <fdt_pmu_probe_pmu_dev.isra.0+0xc3>
3ae1:  call   ffffffff814ae4c0 <__sanitizer_cov_trace_pc>
3ae6:  mov    %rbx,%rdi
3ae9:  call   ffffffff81747a00 <__tsan_read8>
3aee:  mov    (%rbx),%rdi
3af1:  xor    %edx,%edx
3af3:  mov    %r12,%rsi
3af6:  call   ffffffff83203800 <fdt_get_pmu_hw_inf.isra.0>
3afb:  mov    %rax,%rbp
3afe:  jmp    ffffffff83203bd7 <fdt_pmu_probe_pmu_dev.isra.0+0x197>
3b03:  call   ffffffff814ae4c0 <__sanitizer_cov_trace_pc>
3b08:  lea    0x68e963(%rip),%rsi        # ffffffff83892472 <.LC30>
3b0f:  mov    %r12,%rdi
3b12:  call   ffffffff82a26180 <of_device_is_compatible>
3b17:  xor    %edi,%edi
3b19:  mov    %eax,%ebp
3b1b:  mov    %eax,%esi
3b1d:  call   ffffffff814ae7c0 <__sanitizer_cov_trace_const_cmp4>
3b22:  test   %ebp,%ebp
3b24:  je     ffffffff83203b4b <fdt_pmu_probe_pmu_dev.isra.0+0x10b>
3b26:  call   ffffffff814ae4c0 <__sanitizer_cov_trace_pc>
3b2b:  mov    %rbx,%rdi
3b2e:  call   ffffffff81747a00 <__tsan_read8>
3b33:  mov    (%rbx),%rdi
3b36:  mov    $0x1,%edx
3b3b:  mov    %r12,%rsi
3b3e:  call   ffffffff83203800 <fdt_get_pmu_hw_inf.isra.0>
3b43:  mov    %rax,%rbp
3b46:  jmp    ffffffff83203bd7 <fdt_pmu_probe_pmu_dev.isra.0+0x197>
3b4b:  call   ffffffff814ae4c0 <__sanitizer_cov_trace_pc>
3b50:  lea    0x68e92d(%rip),%rsi        # ffffffff83892484 <.LC31>
3b57:  mov    %r12,%rdi
3b5a:  call   ffffffff82a26180 <of_device_is_compatible>
3b5f:  xor    %edi,%edi
3b61:  mov    %eax,%ebp
3b63:  mov    %eax,%esi
3b65:  call   ffffffff814ae7c0 <__sanitizer_cov_trace_const_cmp4>
3b6a:  test   %ebp,%ebp
3b6c:  je     ffffffff83203b90 <fdt_pmu_probe_pmu_dev.isra.0+0x150>
3b6e:  call   ffffffff814ae4c0 <__sanitizer_cov_trace_pc>
3b73:  mov    %rbx,%rdi
3b76:  call   ffffffff81747a00 <__tsan_read8>
3b7b:  mov    (%rbx),%rdi
3b7e:  mov    $0x3,%edx
3b83:  mov    %r12,%rsi
3b86:  call   ffffffff83203800 <fdt_get_pmu_hw_inf.isra.0>
3b8b:  mov    %rax,%rbp
3b8e:  jmp    ffffffff83203bd7 <fdt_pmu_probe_pmu_dev.isra.0+0x197>
3b90:  call   ffffffff814ae4c0 <__sanitizer_cov_trace_pc>
3b95:  lea    0x68e8fa(%rip),%rsi        # ffffffff83892496 <.LC32>
3b9c:  mov    %r12,%rdi
3b9f:  call   ffffffff82a26180 <of_device_is_compatible>
3ba4:  xor    %edi,%edi
3ba6:  mov    %eax,%ebp
3ba8:  mov    %eax,%esi
3baa:  call   ffffffff814ae7c0 <__sanitizer_cov_trace_const_cmp4>
3baf:  test   %ebp,%ebp
3bb1:  je     ffffffff83203d31 <fdt_pmu_probe_pmu_dev.isra.0+0x2f1>
3bb7:  call   ffffffff814ae4c0 <__sanitizer_cov_trace_pc>
3bbc:  mov    %rbx,%rdi
3bbf:  call   ffffffff81747a00 <__tsan_read8>
3bc4:  mov    (%rbx),%rdi
3bc7:  mov    $0x4,%edx
3bcc:  mov    %r12,%rsi
3bcf:  call   ffffffff83203800 <fdt_get_pmu_hw_inf.isra.0>
3bd4:  mov    %rax,%rbp
3bd7:  call   ffffffff814ae4c0 <__sanitizer_cov_trace_pc>
3bdc:  test   %rbp,%rbp
3bdf:  je     ffffffff83203d31 <fdt_pmu_probe_pmu_dev.isra.0+0x2f1>
3be5:  call   ffffffff814ae4c0 <__sanitizer_cov_trace_pc>
3bea:  mov    %rbp,%rsi
3bed:  mov    %rbx,%rdi
3bf0:  call   ffffffff82a864c0 <xgene_pmu_dev_add>
3bf5:  xor    %edi,%edi
3bf7:  mov    %eax,%esi
3bf9:  mov    %eax,(%rsp)
3bfc:  call   ffffffff814ae7c0 <__sanitizer_cov_trace_const_cmp4>
3c01:  mov    (%rsp),%eax
3c04:  test   %eax,%eax
3c06:  je     ffffffff83203c25 <fdt_pmu_probe_pmu_dev.isra.0+0x1e5>
3c08:  call   ffffffff814ae4c0 <__sanitizer_cov_trace_pc>
3c0d:  mov    %rbx,%rdi
3c10:  call   ffffffff81747a00 <__tsan_read8>
3c15:  mov    (%rbx),%rdi
3c18:  mov    %rbp,%rsi
3c1b:  call   ffffffff8283d3c0 <devm_kfree>
3c20:  jmp    ffffffff83203d31 <fdt_pmu_probe_pmu_dev.isra.0+0x2f1>
3c25:  call   ffffffff814ae4c0 <__sanitizer_cov_trace_pc>
3c2a:  lea    0x20(%rbp),%rdi
3c2e:  call   ffffffff817474c0 <__tsan_read4>
3c33:  mov    0x20(%rbp),%eax
3c36:  lea    0x597923(%rip),%rsi
3c3d:  mov    %rax,%rdi
3c40:  mov    %eax,0xc(%rsp)
3c44:  mov    %rax,(%rsp)
3c48:  call   ffffffff814ae840 <__sanitizer_cov_trace_switch>
3c4d:  mov    0xc(%rsp),%edx
3c51:  cmp    $0x4,%edx
3c54:  ja     ffffffff83203d31 <fdt_pmu_probe_pmu_dev.isra.0+0x2f1>
3c5a:  mov    (%rsp),%rax
3c5e:  add    $0x8,%rbp
3c62:  movslq (%r14,%rax,4),%rax
3c66:  add    %r14,%rax
3c69:  jmp    *%rax
3c6b:  int3

Re: [PATCH] objtool: Deal with relative jump tables correctly

[Josh Poimboeuf]

[ Adding Jan and Jose for the jump table annotation discussion below ]

On Wed, Oct 09, 2024 at 05:18:36PM +0200, Ard Biesheuvel wrote:
> On Tue, 8 Oct 2024 at 19:42, Josh Poimboeuf <jpoimboe@kernel.org> wrote:
> >
> > On Tue, Oct 08, 2024 at 12:47:48AM +0200, Ard Biesheuvel wrote:
> > > -     /*
> > > -      * 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;
> > > -
> >
> > I'm not sure if this bug still exists on current GCC versions.  If so,
> > it will start reporting "unreachable instruction" warnings again and
> > we'll have to figure out a way to resolve that.
> >
> 
> Ah, I mistook this for a check against the first entry in the table,
> but it is the reference *to* the table from the code.
> 
> So I'll just leave this alone.

But then with -fpie, unreachable instructions would always be ignored,
which is not ideal as those warnings are actually very useful and often
point to bigger problems.

> Thanks. I've added another tweak locally so validate_ibt_data_reloc()
> uses the corrected offset as well, or I end up with !ENDBR warnings.
> So with that in place, objtool can decipher the jump table if it
> manages to recognize it as one.
> 
> However, there are pathological cases (see one below) where the LEA
> that takes the address of the jump table is ridiculously far away from
> the indirect jump, resulting in a warning like
> 
> vmlinux.o: warning: objtool: fdt_pmu_probe_pmu_dev.isra.0+0x229:
> sibling call from callable instruction with modified stack frame
> 
> 
> This is with GCC 14 (it is the only warning introduced by PIC codegen
> in an allmodconfig build), and I suspect that this might happen with
> non-PIC codegen too, right?
> 
> So how important is jump table support now that it is turned off in
> most cases?

For x86 I believe -fjump-tables is still a possibility in some configs,
so it still needs to work.  That said we may be behind on keeping up
with all the latest warnings.  Jump table detection has always been
whack-a-mole hacks.

And we'd want to support it for other arches as well.

> And has there been any movement on compiler annotations?
> If this is worth while, it is something I could look into: Kees and I
> work very closely with both the GCC and the Clang folks, and have
> contributed other features that are specific to the kernel.

I spoke with several people about this at GNU Cauldron last month and
there is definitely interest in helping out.  If you and Kees also want
to help out, that would be awesome.

Jan proposed an idea to apply a R_*_NONE relocation at the indirect
branch instruction which references the jump table address.  And then
emit a sized ELF symbol for each jump table entry.  That would be all we
need.

-- 
Josh

Re: [PATCH] objtool: Deal with relative jump tables correctly

[Josh Poimboeuf]

On Wed, Oct 09, 2024 at 10:16:52PM -0700, Josh Poimboeuf wrote:
> > And has there been any movement on compiler annotations?
> > If this is worth while, it is something I could look into: Kees and I
> > work very closely with both the GCC and the Clang folks, and have
> > contributed other features that are specific to the kernel.
> 
> I spoke with several people about this at GNU Cauldron last month and
> there is definitely interest in helping out.  If you and Kees also want
> to help out, that would be awesome.
> 
> Jan proposed an idea to apply a R_*_NONE relocation at the indirect
> branch instruction which references the jump table address.  And then
> emit a sized ELF symbol for each jump table entry.  That would be all we
> need.

While we're on the subject of objtool pain points, there's also the need
to have some kind of annotation for noreturn functions.  One suggestion
has been a GCC plugin (which could in theory also work for jump tables).

-- 
Josh