x86: bpf unwinder fixes

Objtool previously ignored ___bpf_prog_run() because it didn't understand the jump table. This resulted in the ORC unwinder not being able to unwind through non-JIT BPF code.

Now that objtool knows how to read jump tables, remove the whitelist and annotate the jump table so objtool can recognize it.

Also add an additional "const" to the jump table definition to clarify that the text pointers are constant. Otherwise GCC sets the section writable flag and the assembler spits out warnings.

Fixes d15d356887e7 ("perf/x86: Make perf callchains work without CONFIG_FRAME_POINTER")

Reported-by Song Liu <[email protected]>

Signed-off-by Josh Poimboeuf <[email protected]>

Commit-ID:  b22cf36c189f31883ad0238a69ccf82aa1f3b16b
Gitweb:     https://git.kernel.org/tip/b22cf36c189f31883ad0238a69ccf82aa1f3b16b
Author:     Josh Poimboeuf <[email protected]>
AuthorDate: Thu, 27 Jun 2019 20:50:47 -0500
Committer:  Thomas Gleixner <[email protected]>
CommitDate: Sat, 29 Jun 2019 07:55:14 +0200

bpf: Fix ORC unwinding in non-JIT BPF code

Objtool previously ignored ___bpf_prog_run() because it didn't understand the jump table. This resulted in the ORC unwinder not being able to unwind through non-JIT BPF code.

Now that objtool knows how to read jump tables, remove the whitelist and annotate the jump table so objtool can recognize it.

Also add an additional "const" to the jump table definition to clarify that the text pointers are constant. Otherwise GCC sets the section writable flag and the assembler spits out warnings.

Fixes d15d356887e7 ("perf/x86: Make perf callchains work without CONFIG_FRAME_POINTER")

Reported-by Song Liu <[email protected]>

Signed-off-by Josh Poimboeuf <[email protected]>

Signed-off-by Thomas Gleixner <[email protected]>

Acked-by Alexei Starovoitov <[email protected]>

Cc Peter Zijlstra <[email protected]>

Cc Kairui Song <[email protected]>

Cc Steven Rostedt <[email protected]>

Cc Borislav Petkov <[email protected]>

Cc Daniel Borkmann <[email protected]>

Link https://lkml.kernel.org/r/881939122b88f32be4c374d248c09d7527a87e35.1561685471.git.jpoimboe@redhat.com open here

---
 kernel/bpf/core.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

Quoted 32 lines · tip-bot for Josh Poimboeuf

Commit-ID:  b22cf36c189f31883ad0238a69ccf82aa1f3b16b
Gitweb:     https://git.kernel.org/tip/b22cf36c189f31883ad0238a69ccf82aa1f3b16b
Author:     Josh Poimboeuf <[email protected]>
AuthorDate: Thu, 27 Jun 2019 20:50:47 -0500
Committer:  Thomas Gleixner <[email protected]>
CommitDate: Sat, 29 Jun 2019 07:55:14 +0200

bpf: Fix ORC unwinding in non-JIT BPF code

Objtool previously ignored ___bpf_prog_run() because it didn't understand the jump table. This resulted in the ORC unwinder not being able to unwind through non-JIT BPF code.

Now that objtool knows how to read jump tables, remove the whitelist and annotate the jump table so objtool can recognize it.

Also add an additional "const" to the jump table definition to clarify that the text pointers are constant. Otherwise GCC sets the section writable flag and the assembler spits out warnings.

Fixes d15d356887e7 ("perf/x86: Make perf callchains work without CONFIG_FRAME_POINTER")

Reported-by Song Liu <[email protected]>

Signed-off-by Josh Poimboeuf <[email protected]>

Signed-off-by Thomas Gleixner <[email protected]>

Acked-by Alexei Starovoitov <[email protected]>

Cc Peter Zijlstra <[email protected]>

Cc Kairui Song <[email protected]>

Cc Steven Rostedt <[email protected]>

Cc Borislav Petkov <[email protected]>

Cc Daniel Borkmann <[email protected]>

Link https://lkml.kernel.org/r/881939122b88f32be4c374d248c09d7527a87e35.1561685471.git.jpoimboe@redhat.com open here

Quoted 3 lines

---
 kernel/bpf/core.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

Hm, I get this new build warning on x86-64 defconfig-ish kernels plus these enabled:

CONFIG_BPF=y
CONFIG_BPF_JIT=y

kernel/bpf/core.o: warning: objtool: ___bpf_prog_run()+0x8da: sibling call from callable instruction with modified stack frame

Quoted 3 lines · Ingo Molnar

Hm, I get this new build warning on x86-64 defconfig-ish kernels plus these enabled:

Quoted 4 lines

CONFIG_BPF=y
CONFIG_BPF_JIT=y

kernel/bpf/core.o: warning: objtool: ___bpf_prog_run()+0x8da: sibling call from callable instruction with modified stack frame

I assume you have CONFIG_RETPOLINE disabled? For some reason that causes GCC to add 166 indirect jumps to that function, which is giving objtool trouble. Looking into it.

Quoted 4 lines · Josh Poimboeuf

Quoted 3 lines · Ingo Molnar

Hm, I get this new build warning on x86-64 defconfig-ish kernels plus these enabled:

Quoted 8 lines

Quoted 4 lines

CONFIG_BPF=y
CONFIG_BPF_JIT=y

kernel/bpf/core.o: warning: objtool: ___bpf_prog_run()+0x8da: sibling call from callable instruction with modified stack frame

I assume you have CONFIG_RETPOLINE disabled? For some reason that causes GCC to add 166 indirect jumps to that function, which is giving objtool trouble. Looking into it.

Alexei, do you have any objections to setting -fno-gcse for ___bpf_prog_run()? Either for the function or the file? Doing so seems to be recommended by the GCC manual for computed gotos. It would also "fix" one of the issues. More details below.

Details:

With CONFIG_RETPOLINE=n, there are a couple of GCC optimizations in ___bpf_prog_run() which objtool is having trouble with.

1)

The function has:

        select_insn:
                goto *jumptable[insn->code];

And then a bunch of "goto select_insn" statements.

GCC is basically replacing

        select_insn:
                jmp *jumptable(,%rax,8)
                ...
        ALU64_ADD_X:
                ...
                jmp select_insn
        ALU_ADD_X:
                ...
                jmp select_insn

with

        select_insn:
                jmp *jumptable(, %rax, 8)
                ...
        ALU64_ADD_X:
                ...
                jmp *jumptable(, %rax, 8)
        ALU_ADD_X:
                ...
                jmp *jumptable(, %rax, 8)

It does that 166 times.

For some reason, it doesn't do the optimization with retpolines enabled.

Objtool has never seen multiple indirect jump sites which use the same jump table. This is relatively trivial to fix (I already have a working patch).

2)

After doing the first optimization, GCC then does another one which is a little trickier. It replaces:

        select_insn:
                jmp *jumptable(, %rax, 8)
                ...
        ALU64_ADD_X:
                ...
                jmp *jumptable(, %rax, 8)
        ALU_ADD_X:
                ...
                jmp *jumptable(, %rax, 8)

with

        select_insn:
                mov jumptable, %r12
                jmp *(%r12, %rax, 8)
                ...
        ALU64_ADD_X:
                ...
                jmp *(%r12, %rax, 8)
        ALU_ADD_X:
                ...
                jmp *(%r12, %rax, 8)

The problem is that it only moves the jumptable address into %r12 once, for the entire function, then it goes through multiple recursive indirect jumps which rely on that %r12 value. But objtool isn't yet smart enough to be able to track the value across multiple recursive indirect jumps through the jump table.

After some digging I found that the quick and easy fix is to disable -fgcse. In fact, this seems to be recommended by the GCC manual, for code like this:

-fgcse
Perform a global common subexpression elimination pass. This pass also performs global constant and copy propagation.

Note: When compiling a program using computed gotos, a GCC extension, you may get better run-time performance if you disable the global common subexpression elimination pass by adding -fno-gcse to the command line.

Enabled at levels -O2, -O3, -Os.

This code indeed relies extensively on computed gotos. I don't know *why* disabling this optimization would improve performance. In fact I really don't see how it could make much of a difference either way.

Anyway, using -fno-gcse makes optimization #2 go away and makes objtool happy, with only a fix for #1 needed.

If -fno-gcse isn't an option, we might be able to fix objtool by using the "first_jump_src" thing which Peter added, improving it such that it also takes table jumps into account.

Quoted 53 lines

2)

After doing the first optimization, GCC then does another one which is a little trickier. It replaces:

        select_insn:
                jmp *jumptable(, %rax, 8)
                ...
        ALU64_ADD_X:
                ...
                jmp *jumptable(, %rax, 8)
        ALU_ADD_X:
                ...
                jmp *jumptable(, %rax, 8)

with

        select_insn:
                mov jumptable, %r12
                jmp *(%r12, %rax, 8)
                ...
        ALU64_ADD_X:
                ...
                jmp *(%r12, %rax, 8)
        ALU_ADD_X:
                ...
                jmp *(%r12, %rax, 8)

The problem is that it only moves the jumptable address into %r12 once, for the entire function, then it goes through multiple recursive indirect jumps which rely on that %r12 value. But objtool isn't yet smart enough to be able to track the value across multiple recursive indirect jumps through the jump table.

After some digging I found that the quick and easy fix is to disable -fgcse. In fact, this seems to be recommended by the GCC manual, for code like this:

-fgcse
Perform a global common subexpression elimination pass. This pass also performs global constant and copy propagation.

Note: When compiling a program using computed gotos, a GCC extension, you may get better run-time performance if you disable the global common subexpression elimination pass by adding -fno-gcse to the command line.

Enabled at levels -O2, -O3, -Os.

This code indeed relies extensively on computed gotos. I don't know *why* disabling this optimization would improve performance. In fact I really don't see how it could make much of a difference either way.

Quoted 6 lines

Anyway, using -fno-gcse makes optimization #2 go away and makes objtool happy, with only a fix for #1 needed.

If -fno-gcse isn't an option, we might be able to fix objtool by using the "first_jump_src" thing which Peter added, improving it such that it also takes table jumps into account.

Sorry for delay. I'm mostly offgrid until next week.
As far as -fno-gcse.. I don't mind as long as it doesn't hurt performance. Which I suspect it will :(
All these indirect gotos are there for performance.
Single indirect goto and a bunch of jmp select_insn
are way slower, since there is only one instruction
for cpu branch predictor to work with.
When every insn is followed by "jmp *jumptable"
there is more room for cpu to speculate.
It's been long time, but when I wrote it the difference between all indirect goto vs single indirect goto was almost 2x.

Quoted 60 lines · Alexei Starovoitov

Quoted 53 lines

2)

After doing the first optimization, GCC then does another one which is a little trickier. It replaces:

        select_insn:
                jmp *jumptable(, %rax, 8)
                ...
        ALU64_ADD_X:
                ...
                jmp *jumptable(, %rax, 8)
        ALU_ADD_X:
                ...
                jmp *jumptable(, %rax, 8)

with

        select_insn:
                mov jumptable, %r12
                jmp *(%r12, %rax, 8)
                ...
        ALU64_ADD_X:
                ...
                jmp *(%r12, %rax, 8)
        ALU_ADD_X:
                ...
                jmp *(%r12, %rax, 8)

The problem is that it only moves the jumptable address into %r12 once, for the entire function, then it goes through multiple recursive indirect jumps which rely on that %r12 value. But objtool isn't yet smart enough to be able to track the value across multiple recursive indirect jumps through the jump table.

After some digging I found that the quick and easy fix is to disable -fgcse. In fact, this seems to be recommended by the GCC manual, for code like this:

-fgcse
Perform a global common subexpression elimination pass. This pass also performs global constant and copy propagation.

Note: When compiling a program using computed gotos, a GCC extension, you may get better run-time performance if you disable the global common subexpression elimination pass by adding -fno-gcse to the command line.

Enabled at levels -O2, -O3, -Os.

This code indeed relies extensively on computed gotos. I don't know *why* disabling this optimization would improve performance. In fact I really don't see how it could make much of a difference either way.

Quoted 6 lines

Anyway, using -fno-gcse makes optimization #2 go away and makes objtool happy, with only a fix for #1 needed.

If -fno-gcse isn't an option, we might be able to fix objtool by using the "first_jump_src" thing which Peter added, improving it such that it also takes table jumps into account.

Quoted 11 lines

Sorry for delay. I'm mostly offgrid until next week.
As far as -fno-gcse.. I don't mind as long as it doesn't hurt performance. Which I suspect it will :(
All these indirect gotos are there for performance.
Single indirect goto and a bunch of jmp select_insn
are way slower, since there is only one instruction
for cpu branch predictor to work with.
When every insn is followed by "jmp *jumptable"
there is more room for cpu to speculate.
It's been long time, but when I wrote it the difference between all indirect goto vs single indirect goto was almost 2x.

Just to clarify, -fno-gcse doesn't get rid of any of the indirect jumps. It still has 166 indirect jumps. It just gets rid of the second optimization, where the jumptable address is placed in a register.

If you have a benchmark which is relatively easy to use, I could try to run some tests.

Quoted 12 lines

Quoted 11 lines

Sorry for delay. I'm mostly offgrid until next week.
As far as -fno-gcse.. I don't mind as long as it doesn't hurt performance. Which I suspect it will :(
All these indirect gotos are there for performance.
Single indirect goto and a bunch of jmp select_insn
are way slower, since there is only one instruction
for cpu branch predictor to work with.
When every insn is followed by "jmp *jumptable"
there is more room for cpu to speculate.
It's been long time, but when I wrote it the difference between all indirect goto vs single indirect goto was almost 2x.

Quoted 3 lines

Just to clarify, -fno-gcse doesn't get rid of any of the indirect jumps. It still has 166 indirect jumps. It just gets rid of the second optimization, where the jumptable address is placed in a register.

what about other functions in core.c ?
May be it's easier to teach objtool to recognize that pattern?

Quoted 2 lines

If you have a benchmark which is relatively easy to use, I could try to run some tests.

modprobe test_bpf
selftests/bpf/test_progs
both print runtime.
Some of test_progs have high run-to-run variations though.

Quoted 12 lines · Alexei Starovoitov

Quoted 12 lines

Quoted 11 lines

Sorry for delay. I'm mostly offgrid until next week.
As far as -fno-gcse.. I don't mind as long as it doesn't hurt performance. Which I suspect it will :(
All these indirect gotos are there for performance.
Single indirect goto and a bunch of jmp select_insn
are way slower, since there is only one instruction
for cpu branch predictor to work with.
When every insn is followed by "jmp *jumptable"
there is more room for cpu to speculate.
It's been long time, but when I wrote it the difference between all indirect goto vs single indirect goto was almost 2x.

Quoted 6 lines

Quoted 3 lines

Just to clarify, -fno-gcse doesn't get rid of any of the indirect jumps. It still has 166 indirect jumps. It just gets rid of the second optimization, where the jumptable address is placed in a register.

what about other functions in core.c ?
May be it's easier to teach objtool to recognize that pattern?

The GCC man page actually recommends using -fno-gcse for computed goto code, for better performance. So if that's actually true, then it would be win-win because objtool wouldn't need a change for it.

Otherwise I can teach objtool to recognize the new pattern.

Quoted 3 lines

Quoted 2 lines

If you have a benchmark which is relatively easy to use, I could try to run some tests.

Quoted 4 lines

modprobe test_bpf
selftests/bpf/test_progs
both print runtime.
Some of test_progs have high run-to-run variations though.

Thanks, I'll give it a shot.

Quoted 6 lines

Quoted 5 lines

modprobe test_bpf
selftests/bpf/test_progs
both print runtime.
Some of test_progs have high run-to-run variations though.

Quoted 1 line

Thanks, I'll give it a shot.

I modprobed test_bpf with JIT disabled.

Before: 2.493018s
After:  2.523572s

So it looks like it's either no change, or slightly slower.

total time is hard to compare. Could you compare few tests? like two that are called "tcpdump *"

I think small regression is ok.
Folks that care about performance should be using JIT.

Quoted 6 lines · Alexei Starovoitov

total time is hard to compare. Could you compare few tests? like two that are called "tcpdump *"

I think small regression is ok.
Folks that care about performance should be using JIT.

I did each test 20 times and computed the averages:

"tcpdump port 22":
default: 0.00743175s
-fno-gcse: 0.00709920s (~4.5% speedup)

"tcpdump complex":
default: 0.00876715s
-fno-gcse: 0.00854895s (~2.5% speedup)

So there does seem to be a small performance gain by disabling this optimization.

We could change it for the whole file, by adjusting CFLAGS_core.o in the BPF makefile, or we could change it for the function only with something like the below patch.

Thoughts?

include/linux/compiler-gcc.h +2 -0

index e8579412ad21..d7ee4c6bad48 100644
@@ -170,3 +170,5 @@
 #else
 #define __diag_GCC_8(s)
 #endif
+
+#define __no_fgcse __attribute__((optimize("-fno-gcse")))

include/linux/compiler_types.h +4 -0

index 095d55c3834d..599c27b56c29 100644
@@ -189,6 +189,10 @@ struct ftrace_likely_data {
 #define asm_volatile_goto(x...) asm goto(x)
 #endif
 
+#ifndef __no_fgcse
+# define __no_fgcse
+#endif
+
 /* Are two types/vars the same type (ignoring qualifiers)? */
 #define __same_type(a, b) __builtin_types_compatible_p(typeof(a), typeof(b))
 

kernel/bpf/core.c +0 -0

index 7e98f36a14e2..8191a7db2777 100644

Quoted 15 lines · Josh Poimboeuf

Quoted 6 lines · Alexei Starovoitov

total time is hard to compare. Could you compare few tests? like two that are called "tcpdump *"

I think small regression is ok.
Folks that care about performance should be using JIT.

I did each test 20 times and computed the averages:

"tcpdump port 22":
default: 0.00743175s
-fno-gcse: 0.00709920s (~4.5% speedup)

Quoted 6 lines

"tcpdump complex":
default: 0.00876715s
-fno-gcse: 0.00854895s (~2.5% speedup)

So there does seem to be a small performance gain by disabling this optimization.

great. thanks for checking.

Quoted 36 lines

We could change it for the whole file, by adjusting CFLAGS_core.o in the BPF makefile, or we could change it for the function only with something like the below patch.

Thoughts?

include/linux/compiler-gcc.h +2 -0

index e8579412ad21..d7ee4c6bad48 100644
@@ -170,3 +170,5 @@
 #else
 #define __diag_GCC_8(s)
 #endif
+
+#define __no_fgcse __attribute__((optimize("-fno-gcse")))

include/linux/compiler_types.h +4 -0

index 095d55c3834d..599c27b56c29 100644
@@ -189,6 +189,10 @@ struct ftrace_likely_data {
 #define asm_volatile_goto(x...) asm goto(x)
 #endif
 
+#ifndef __no_fgcse
+# define __no_fgcse
+#endif
+
 /* Are two types/vars the same type (ignoring qualifiers)? */
 #define __same_type(a, b) __builtin_types_compatible_p(typeof(a), typeof(b))
 

kernel/bpf/core.c +0 -0

index 7e98f36a14e2..8191a7db2777 100644

kernel/bpf/core.c bool bpf_opcode_in_insntable(u8 code) · line 1298

Quoted 5 lines

kernel/bpf/core.c +1 -1

@@ -1295,7 +1295,7 @@ bool bpf_opcode_in_insntable(u8 code)
  *
  * Decode and execute eBPF instructions.
  */
-static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn, u64 *stack)
+static u64 __no_fgcse ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn, u64 *stack)

I prefer per-function flag.
If you want to route it via tip:

Acked-by Alexei Starovoitov <[email protected]>

or Daniel can take it into bpf tree while I'm traveling.

Quoted 56 lines · Alexei Starovoitov

Quoted 15 lines · Josh Poimboeuf

Quoted 6 lines · Alexei Starovoitov

total time is hard to compare. Could you compare few tests? like two that are called "tcpdump *"

I think small regression is ok.
Folks that care about performance should be using JIT.

I did each test 20 times and computed the averages:

"tcpdump port 22":
default: 0.00743175s
-fno-gcse: 0.00709920s (~4.5% speedup)

Quoted 6 lines

"tcpdump complex":
default: 0.00876715s
-fno-gcse: 0.00854895s (~2.5% speedup)

So there does seem to be a small performance gain by disabling this optimization.

great. thanks for checking.

Quoted 31 lines

We could change it for the whole file, by adjusting CFLAGS_core.o in the BPF makefile, or we could change it for the function only with something like the below patch.

Thoughts?

include/linux/compiler-gcc.h +2 -0

index e8579412ad21..d7ee4c6bad48 100644
@@ -170,3 +170,5 @@
 #else
 #define __diag_GCC_8(s)
 #endif
+
+#define __no_fgcse __attribute__((optimize("-fno-gcse")))

include/linux/compiler_types.h +4 -0

index 095d55c3834d..599c27b56c29 100644
@@ -189,6 +189,10 @@ struct ftrace_likely_data {
 #define asm_volatile_goto(x...) asm goto(x)
 #endif
 
+#ifndef __no_fgcse
+# define __no_fgcse
+#endif
+
 /* Are two types/vars the same type (ignoring qualifiers)? */
 #define __same_type(a, b) __builtin_types_compatible_p(typeof(a), typeof(b))
 

Quoted 4 lines

Quoted 4 lines

kernel/bpf/core.c +0 -0

index 7e98f36a14e2..8191a7db2777 100644

Quoted 8 lines

kernel/bpf/core.c bool bpf_opcode_in_insntable(u8 code) · line 1298

Quoted 6 lines

kernel/bpf/core.c +1 -1

@@ -1295,7 +1295,7 @@ bool bpf_opcode_in_insntable(u8 code)
  *
  * Decode and execute eBPF instructions.
  */
-static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn, u64 *stack)
+static u64 __no_fgcse ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn, u64 *stack)

I prefer per-function flag.

Quoted 4 lines

If you want to route it via tip:

Acked-by Alexei Starovoitov <[email protected]>

or Daniel can take it into bpf tree while I'm traveling.

Thanks! I''ll probably send it through the tip tree, along with an objtool fix for the other optimization.