bpf, x64: Fix a jit convergence issue
Subsystems (5)
Yonghong Song
reviewerPATCH v2 1/2 bpf, x64: Fix a jit convergence issue
Daniel Hodges reported a jit error when playing with a sched-ext program. The error message is:
unexpected jmp_cond padding: -4 bytes
But further investigation shows the error is actual due to failed convergence. The following are some analysis:
...
pass4, final_proglen=4391:
...
20e: 48 85 ff test rdi,rdi
211: 74 7d je 0x290
213: 48 8b 77 00 mov rsi,QWORD PTR [rdi+0x0]
...
289: 48 85 ff test rdi,rdi
28c: 74 17 je 0x2a5
28e: e9 7f ff ff ff jmp 0x212
293: bf 03 00 00 00 mov edi,0x3Note that insn at 0x211 is 2-byte cond jump insn for offset 0x7d (-125) and insn at 0x28e is 5-byte jmp insn with offset -129.
pass5, final_proglen=4392:
...
20e: 48 85 ff test rdi,rdi
211: 0f 84 80 00 00 00 je 0x297
217: 48 8b 77 00 mov rsi,QWORD PTR [rdi+0x0]
...
28d: 48 85 ff test rdi,rdi
290: 74 1a je 0x2ac
292: eb 84 jmp 0x218
294: bf 03 00 00 00 mov edi,0x3Note that insn at 0x211 is 6-byte cond jump insn now since its offset becomes 0x80 based on previous round (0x293 - 0x213 = 0x80). At the same time, insn at 0x292 is a 2-byte insn since its offset is -124.
pass6 will repeat the same code as in pass4. pass7 will repeat the same code as in pass5, and so on. This will prevent eventual convergence.
Passes 1-14 are with padding = 0. At pass15, padding is 1 and related insn looks like:
211: 0f 84 80 00 00 00 je 0x297
217: 48 8b 77 00 mov rsi,QWORD PTR [rdi+0x0] ...
24d: 48 85 d2 test rdx,rdx
The similar code in pass14:
211: 74 7d je 0x290
213: 48 8b 77 00 mov rsi,QWORD PTR [rdi+0x0]
...
249: 48 85 d2 test rdx,rdx
24c: 74 21 je 0x26f
24e: 48 01 f7 add rdi,rsi
...Before generating the following insn,
250: 74 21 je 0x273
"padding = 1" enables some checking to ensure nops is either 0 or 4 where
#define INSN_SZ_DIFF (((addrs[i] - addrs[i - 1]) - (prog - temp))) nops = INSN_SZ_DIFF - 2
In this specific case,
addrs[i] = 0x24e // from pass14 addrs[i-1] = 0x24d // from pass15
prog - temp = 3 // from 'test rdx,rdx' in pass15
so
nops = -4
and this triggers the failure.
To fix the issue, we need to break cycles of je <-> jmp. For example, in the above case, we have
211: 74 7d je 0x290
the offset is 0x7d. If 2-byte je insn is generated only if the offset is less than 0x7d (<= 0x7c), the cycle can be break and we can achieve the convergence.
I did some study on other cases like je <-> je, jmp <-> je and jmp <-> jmp which may cause cycles. Those cases are not from actual reproducible cases since it is pretty hard to construct a test case for them. the results show that the offset <= 0x7b (0x7b = 123) should be enough to cover all cases. This patch added a new helper to generate 8-bit cond/uncond jmp insns only if the offset range is [-128, 123].
--- arch/x86/net/bpf_jit_comp.c | 55 +++++++++++++++++++++++++++++++++++-- 1 file changed, 53 insertions(+), 2 deletions(-)
arch/x86/net/bpf_jit_comp.c +53 -2
@@ -64,6 +64,57 @@ static bool is_imm8(int value)return value <=127 && value >=-128 ; } +/* +* Let us limit the positive offset to be <= 124. +* This is to ensure eventual jit convergence For the following patterns: +* ... +* pass4, final_proglen=4391: +* ... +* 20e: 48 85 ff test rdi,rdi +* 211: 74 7d je 0x290 +* 213: 48 8b 77 00 mov rsi,QWORD PTR [rdi+0x0] +* ... +* 289: 48 85 ff test rdi,rdi +* 28c: 74 17 je 0x2a5 +* 28e: e9 7f ff ff ff jmp 0x212 +* 293: bf 03 00 00 00 mov edi,0x3 +* Note that insn at 0x211 is 2-byte cond jump insn for offset 0x7d (-125) +* and insn at 0x28e is 5-byte jmp insn with offset -129. +* +* pass5, final_proglen=4392: +* ... +* 20e: 48 85 ff test rdi,rdi +* 211: 0f 84 80 00 00 00 je 0x297 +* 217: 48 8b 77 00 mov rsi,QWORD PTR [rdi+0x0] +* ... +* 28d: 48 85 ff test rdi,rdi +* 290: 74 1a je 0x2ac +* 292: eb 84 jmp 0x218 +* 294: bf 03 00 00 00 mov edi,0x3 +* Note that insn at 0x211 is 6-byte cond jump insn now since its offset +* becomes 0x80 based on previous round (0x293 - 0x213 = 0x80). +* At the same time, insn at 0x292 is a 2-byte insn since its offset is +* -124. +* +* pass6 will repeat the same code as in pass4 and this will prevent +* eventual convergence. +* +* To fix this issue, we need to break je (2->6 bytes) <-> jmp (5->2 bytes) +* cycle in the above. In the above example that we found je offset <= 0x7c +* should work. +* +* For other cases, je <-> je needs offset <= 0x7b to avoid no convergence +* issue. For jmp <-> je and jmp <-> jmp cases, jmp offset <= 0x7c should +* avoid no convergence issue. +* +* Overall, let us limit the positive offset for 8bit cond/uncond jmp insn +* to mamximum 123 (0x7b). This way, the jit pass can eventually converge. +*/ +static bool is_imm8_jmp_offset (int value) +{ +return value <=123 && value >=-128 ; +} +static bool is_simm32 (s64 value) {return value == (s64 )(s32 )value;
@@ -2231,7 +2282,7 @@ st: if (is_imm8(insn->off))return -EFAULT ; } jmp_offset = addrs[i + insn->off] - addrs[i]; -if (is_imm8 (jmp_offset)) { +if (is_imm8_jmp_offset (jmp_offset)) {if (jmp_padding) {/* To keep the jmp_offset valid, the extra bytes are * padded before the jump insn, so we subtract the
@@ -2313,7 +2364,7 @@ st: if (is_imm8(insn->off))break ; } emit_jmp: -if (is_imm8 (jmp_offset)) { +if (is_imm8_jmp_offset (jmp_offset)) {if (jmp_padding) {/* To avoid breaking jmp_offset, the extra bytes * are padded before the actual jmp insn, so
Signature · 1 line
2.43.5
Yonghong Song
reviewerPATCH v2 2/2 selftests/bpf: Add a selftest for x86 jit convergence issues
The core part of the selftest, i.e., the je <-> jmp cycle, mimics the original sched-ext bpf program. The test will fail without the previous patch.
I tried to create some cases for other potential cycles (je <-> je, jmp <-> je and jmp <-> jmp) with similar pattern to the test in this patch, but failed. So this patch only contains one test for je <-> jmp cycle.
--- .../selftests/bpf/prog_tests/verifier.c | 2 + .../bpf/progs/verifier_jit_convergence.c | 128 ++++++++++++++++++ 2 files changed, 130 insertions(+) create mode 100644 tools/testing/selftests/bpf/progs/verifier_jit_convergence.c
tools/testing/selftests/bpf/prog_tests/verifier.c +2 -0
@@ -39,6 +39,7 @@#include "verifier_int_ptr.skel.h" #include "verifier_iterating_callbacks.skel.h" #include "verifier_jeq_infer_not_null.skel.h" +#include "verifier_jit_convergence.skel.h" #include "verifier_ld_ind.skel.h" #include "verifier_ldsx.skel.h" #include "verifier_leak_ptr.skel.h"
@@ -163,6 +164,7 @@ void test_verifier_helper_value_access(void) { RUN(verifier_helper_value_accessvoid test_verifier_int_ptr (void ) {RUN (verifier_int_ptr); }void test_verifier_iterating_callbacks (void ) {RUN (verifier_iterating_callbacks); }void test_verifier_jeq_infer_not_null (void ) {RUN (verifier_jeq_infer_not_null); } +void test_verifier_jit_convergence (void ) {RUN (verifier_jit_convergence); }void test_verifier_ld_ind (void ) {RUN (verifier_ld_ind); }void test_verifier_ldsx (void ) {RUN (verifier_ldsx); }void test_verifier_leak_ptr (void ) {RUN (verifier_leak_ptr); }
tools/testing/selftests/bpf/progs/verifier_jit_convergence.c new file +128 -0
128 lines not on this page · raw message
Signature · 1 line
2.43.5
Re: [PATCH bpf-next v2 2/2] selftests/bpf: Add a selftest for x86 jit convergence issues
tools/testing/selftests/bpf/progs/verifier_jit_convergence.c line 8
Quoted 6 lines · Yonghong Song
tools/testing/selftests/bpf/progs/verifier_jit_convergence.c new file +5
-0+#include <linux/bpf.h> +#include <bpf/bpf_helpers.h> +#include "bpf_misc.h" + +#if defined(__TARGET_ARCH_x86)
Does our test framework need this ifdef and dummy_test below? There is __arch_x86_64 below.
Isn't it enough?
Quoted 4 lines
tools/testing/selftests/bpf/progs/verifier_jit_convergence.c new file +4
-0+SEC("socket") +__description("bpf_jit_convergence je <-> jmp") +__success __retval(0) +__arch_x86_64
Yonghong Song
reviewerRe: [PATCH bpf-next v2 2/2] selftests/bpf: Add a selftest for x86 jit convergence issues
Quoted 9 lines · Alexei Starovoitov
tools/testing/selftests/bpf/progs/verifier_jit_convergence.c line 8
Quoted 5 lines · Yonghong Song
tools/testing/selftests/bpf/progs/verifier_jit_convergence.c new file +5
-0+#include <linux/bpf.h> +#include <bpf/bpf_helpers.h> +#include "bpf_misc.h" + +#if defined(__TARGET_ARCH_x86)Does our test framework need this ifdef and
dummy_testbelow? There is__arch_x86_64below.
Isn't it enough?
It should be enough. Other arch should be correct although they do not have convergence issue.
Let me remove above "#if defined(__TARGET_ARCH_x86)" and do a test again to ensure everything is okay.
Quoted 5 lines
Quoted 5 lines
tools/testing/selftests/bpf/progs/verifier_jit_convergence.c new file +4
-0+SEC("socket") +__description("bpf_jit_convergence je <-> jmp") +__success __retval(0) +__arch_x86_64
arch/x86/net/bpf_jit_comp.c static bool is_imm8(int value) · line 68
Quoted 12 lines · Yonghong Song
arch/x86/net/bpf_jit_comp.c +2
-0@@ -64,6 +64,57 @@ static bool is_imm8(int value)return value <=127 && value >=-128 ; } +/* +* Let us limit the positive offset to be <= 124.
I think the comment will read better if the above says "<= 123", since that's the final outcome.
124 above is a bit confusing.
I can tweak while applying if you agree.
arch/x86/net/bpf_jit_comp.c static bool is_imm8(int value) · line 111
Quoted 1 line
arch/x86/net/bpf_jit_comp.c +1
-0+* to mamximum 123 (0x7b). This way, the jit pass can eventually converge.
Can fix this typo too.
Yonghong Song
reviewerQuoted 10 lines · Alexei Starovoitov
Quoted 9 lines · Yonghong Song
arch/x86/net/bpf_jit_comp.c +0
-0@@ -64,6 +64,57 @@ static bool is_imm8(int value)return value <=127 && value >=-128 ; }
Quoted 6 lines
arch/x86/net/bpf_jit_comp.c static bool is_imm8(int value) · line 68
Quoted 2 lines
arch/x86/net/bpf_jit_comp.c +2
-0+/* +* Let us limit the positive offset to be <= 124. I think the comment will read better if the above says "<= 123", since that's the final outcome.
124 above is a bit confusing.
I can tweak while applying if you agree.
Correct. Let us do "<= 123".
Quoted 3 lines
arch/x86/net/bpf_jit_comp.c static bool is_imm8(int value) · line 111
Quoted 2 lines
arch/x86/net/bpf_jit_comp.c +1
-0+* to mamximum 123 (0x7b). This way, the jit pass can eventually converge. Can fix this typo too.
Sounds good.
Since I need to change test in the second patch (enabling tests for arm64/s390), let me send v3 to address all comments.