[PATCH bpf-next 0/2] bpf: Fix x86 JIT stopping before jumps converge

[PATCH bpf-next 0/2] bpf: Fix x86 JIT stopping before jumps converge

[Mykyta Yatsenko]

The x86 JIT stops its sizing passes once two passes give the same image
length. A backward jump can grow while other jumps shrink, so the length
may repeat with jump sizes still changing. The final pass then emits code
of a different size than was sized, hits "bpf_jit: fatal error" and the
program fails to load with -ENOTSUPP.

Patch 1 stops the passes only when no insn moved.
Patch 2 adds a selftest which fails to load without the fix.

This was hit in CI by cgroup_tcp_skb with the unpublished branch
inversion series, whose layout change happened to trigger it.

Signed-off-by: Mykyta Yatsenko <yatsenko@meta.com>
---
Mykyta Yatsenko (2):
      bpf: Stop JIT passes only when no insn moves
      selftests/bpf: Test JIT jumps which change at a repeated image length

 arch/x86/net/bpf_jit_comp.c                        | 25 +++++++---
 tools/testing/selftests/bpf/prog_tests/jit_insns.c | 57 ++++++++++++++++++++++
 2 files changed, 75 insertions(+), 7 deletions(-)
---
base-commit: 59d77affc1dc56c992308038e68d7041abef1b8d
change-id: 20261021-jit_size_fix-da316b8d492c

Best regards,
--  
Mykyta Yatsenko <yatsenko@meta.com>

[PATCH bpf-next 1/2] bpf: Stop JIT passes only when no insn moves

[Mykyta Yatsenko]

From: Mykyta Yatsenko <yatsenko@meta.com>

A backward jump is sized from its target's current-pass address and its
own previous-pass address, so it can grow while other jumps shrink. Two
passes may then give the same image length with jumps still changing,
and the image pass fails with "bpf_jit: fatal error".

Signed-off-by: Mykyta Yatsenko <yatsenko@meta.com>
---
 arch/x86/net/bpf_jit_comp.c | 25 ++++++++++++++++++-------
 1 file changed, 18 insertions(+), 7 deletions(-)

diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
index 6a2fe3d0039d..b483cde866d9 100644
--- a/arch/x86/net/bpf_jit_comp.c
+++ b/arch/x86/net/bpf_jit_comp.c
@@ -355,6 +355,9 @@ struct jit_context {
 	 */
 	int tail_call_direct_label;
 	int tail_call_indirect_label;
+
+	/* Set when a pass moves the end of any insn */
+	bool addrs_changed;
 };
 
 /* Maximum number of bytes emitted while JITing one eBPF insn */
@@ -2574,6 +2577,13 @@ static int emit_unwind_ret_addr(u8 **pprog, u8 *ip)
 	return 0;
 }
 
+static void set_insn_end(struct jit_context *ctx, int *insn_end, int end)
+{
+	if (*insn_end != end)
+		ctx->addrs_changed = true;
+	*insn_end = end;
+}
+
 static int do_jit(struct bpf_verifier_env *env, struct bpf_prog *bpf_prog, int *addrs, u8 *image,
 		  u8 *rw_image, int oldproglen, struct jit_context *ctx, bool jmp_padding)
 {
@@ -2702,7 +2712,8 @@ static int do_jit(struct bpf_verifier_env *env, struct bpf_prog *bpf_prog, int *
 	if (rw_image)
 		memcpy(rw_image + proglen, temp, ilen);
 	proglen += ilen;
-	addrs[0] = proglen;
+	ctx->addrs_changed = false;
+	set_insn_end(ctx, addrs, proglen);
 	prog = temp;
 
 	for (i = 1; i <= insn_cnt; i++, insn++) {
@@ -3930,7 +3941,7 @@ static int do_jit(struct bpf_verifier_env *env, struct bpf_prog *bpf_prog, int *
 			memcpy(rw_image + proglen, temp, ilen);
 		}
 		proglen += ilen;
-		addrs[i] = proglen;
+		set_insn_end(ctx, addrs + i, proglen);
 		prog = temp;
 	}
 
@@ -4977,10 +4988,10 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_verifier_env *env, struct bpf_pr
 skip_init_addrs:
 
 	/*
-	 * JITed image shrinks with every pass and the loop iterates
-	 * until the image stops shrinking. Very large BPF programs
-	 * may converge on the last pass. In such case do one more
-	 * pass to emit the final image.
+	 * JITed image usually shrinks with every pass, but individual
+	 * jumps can grow, so the loop iterates until no insn moves.
+	 * Very large BPF programs may converge on the last pass. In
+	 * such case do one more pass to emit the final image.
 	 */
 	for (pass = 0; pass < MAX_PASSES || image; pass++) {
 		if (!padding && pass >= PADDING_PASSES)
@@ -5010,7 +5021,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_verifier_env *env, struct bpf_pr
 			}
 			break;
 		}
-		if (proglen == oldproglen) {
+		if (!ctx.addrs_changed) {
 			/*
 			 * The number of entries in extable is the number of BPF_LDX
 			 * insns that access kernel memory via "pointer to BTF type".

-- 
2.53.0-Meta

[PATCH bpf-next 2/2] selftests/bpf: Test JIT jumps which change at a repeated image length

[Mykyta Yatsenko]

From: Mykyta Yatsenko <yatsenko@meta.com>

Cover the case where two JIT passes give the same image length while
jumps still change size, which used to fail with -ENOTSUPP on x86-64.

Signed-off-by: Mykyta Yatsenko <yatsenko@meta.com>
---
 tools/testing/selftests/bpf/prog_tests/jit_insns.c | 57 ++++++++++++++++++++++
 1 file changed, 57 insertions(+)

diff --git a/tools/testing/selftests/bpf/prog_tests/jit_insns.c b/tools/testing/selftests/bpf/prog_tests/jit_insns.c
index dabefdb8a353..1abfe6161bb9 100644
--- a/tools/testing/selftests/bpf/prog_tests/jit_insns.c
+++ b/tools/testing/selftests/bpf/prog_tests/jit_insns.c
@@ -2881,6 +2881,61 @@ static void test_convergence(void)
 	}
 }
 
+/*
+ * On x86-64 a backward jump grows here while others shrink, so two passes
+ * give the same image length with jumps still changing. The fillers are 7
+ * and 2 bytes of native code, jumps are never taken.
+ */
+static void test_same_len_not_converged(void)
+{
+	struct bpf_insn insns[] = {
+		BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, IN0),
+		BPF_LDX_MEM(BPF_DW, BPF_REG_4, BPF_REG_1, IN1),
+		BPF_JMP_IMM(BPF_JA, 0, 0, 1),
+		BPF_JMP_IMM(BPF_JA, 0, 0, 29),
+		BPF_JMP32_REG(BPF_JEQ, BPF_REG_0, BPF_REG_4, 20),
+		BPF_JMP32_REG(BPF_JEQ, BPF_REG_0, BPF_REG_4, -3),
+		BPF_JMP32_REG(BPF_JEQ, BPF_REG_0, BPF_REG_4, 22),
+		BPF_JMP32_REG(BPF_JEQ, BPF_REG_0, BPF_REG_4, 2),
+		BPF_MOV32_IMM(BPF_REG_2, 0),
+		BPF_JMP32_REG(BPF_JEQ, BPF_REG_0, BPF_REG_4, 23),
+		BPF_MOV64_IMM(BPF_REG_2, -1),
+		BPF_MOV64_IMM(BPF_REG_2, -1),
+		BPF_MOV64_IMM(BPF_REG_2, -1),
+		BPF_MOV64_IMM(BPF_REG_2, -1),
+		BPF_MOV64_IMM(BPF_REG_2, -1),
+		BPF_MOV64_IMM(BPF_REG_2, -1),
+		BPF_MOV64_IMM(BPF_REG_2, -1),
+		BPF_MOV64_IMM(BPF_REG_2, -1),
+		BPF_MOV64_IMM(BPF_REG_2, -1),
+		BPF_MOV64_IMM(BPF_REG_2, -1),
+		BPF_MOV64_IMM(BPF_REG_2, -1),
+		BPF_MOV64_IMM(BPF_REG_2, -1),
+		BPF_MOV64_IMM(BPF_REG_2, -1),
+		BPF_MOV32_IMM(BPF_REG_2, 0),
+		BPF_JMP_IMM(BPF_JA, 0, 0, -22),
+		BPF_MOV64_IMM(BPF_REG_2, -1),
+		BPF_MOV32_IMM(BPF_REG_2, 0),
+		BPF_MOV32_IMM(BPF_REG_2, 0),
+		BPF_JMP32_REG(BPF_JEQ, BPF_REG_0, BPF_REG_4, 3),
+		BPF_MOV32_IMM(BPF_REG_2, 0),
+		BPF_JMP32_REG(BPF_JEQ, BPF_REG_0, BPF_REG_4, 2),
+		BPF_JMP_IMM(BPF_JA, 0, 0, -22),
+		BPF_MOV32_IMM(BPF_REG_2, 0),
+		BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 10),
+		BPF_STX_MEM(BPF_DW, BPF_REG_1, BPF_REG_0, RES),
+		BPF_MOV64_IMM(BPF_REG_0, 0),
+		BPF_EXIT_INSN(),
+	};
+	int fd;
+
+	fd = load_prog(insns, ARRAY_SIZE(insns), "same len not converged");
+	if (fd < 0)
+		return;
+	prog_run(fd, 1, 2, 11, "same len not converged");
+	close(fd);
+}
+
 /*
  * Calls into a subprogram with all five arguments, which clobbers a subset
  * of r6-r9 and uses the deepest stack slot the budget leaves, directly or
@@ -3087,6 +3142,8 @@ void test_jit_insns(void)
 		test_max_jmp();
 	if (test__start_subtest("convergence"))
 		test_convergence();
+	if (test__start_subtest("same_len_not_converged"))
+		test_same_len_not_converged();
 	if (test__start_subtest("calls"))
 		test_calls();
 	if (test__start_subtest("helper_calls"))

-- 
2.53.0-Meta

Re: [PATCH bpf-next 1/2] bpf: Stop JIT passes only when no insn moves

[Alexei Starovoitov]

On Wed, Oct 21, 2026 at 07:21 AM Mykyta Yatsenko <mykyta.yatsenko5@gmail.com> wrote:
> A backward jump is sized from its target's current-pass address and its
> own previous-pass address, so it can grow while other jumps shrink. Two
> passes may then give the same image length with jumps still changing,
> and the image pass fails with "bpf_jit: fatal error".

can we fix the sizing of the backward jump instead ?

It's the third time it bites us.
commit 1612a981b766 ("bpf, x64: fix JIT emission for dead code")
special cased ja -1 and
commit c8831bdbfbab ("bpf, x64: Fix a jit convergence issue")
limited imm8 to 123 because of it.
With this patch jumps still grow, and the one that grows in a padding
pass still ends in "unexpected jmp_cond padding: -4 bytes".

do_jit() knows how far the current pass moved insn i. With that taken
into account a backward jump is sized by the insns it jumps over, the
same way as a forward one. Insn sizes start at 64 and only go down, so
the image shrinks with every pass like the comment in
bpf_int_jit_compile() says, and proglen == oldproglen means that
nothing moved.
Then no need for addrs_changed, for the ja -1 special case and
for is_imm8_jmp_offset().

Something like this (compile tested only):

diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
index 6a2fe3d..c20d7d3 100644
--- a/arch/x86/net/bpf_jit_comp.c
+++ b/arch/x86/net/bpf_jit_comp.c
@@ -97,56 +97,6 @@ static bool is_imm8(int value)
 	return value <= 127 && value >= -128;
 }

-/*
- * Let us limit the positive offset to be <= 123.
- * 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 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 maximum 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;
@@ -2298,6 +2248,17 @@ static void emit_priv_frame_ptr(u8 **pprog, void __percpu *priv_frame_ptr)

 #define INSN_SZ_DIFF (((addrs[i] - addrs[i - 1]) - (prog - temp)))

+/*
+ * addrs[] below i are from this pass, addrs[i] and above are from the previous
+ * one. 'moved' is how far this pass moved the start of insn i. With it a jump
+ * in either direction is sized by the insns it jumps over. All insns start at
+ * 64 bytes, so none of them ever grows and the image shrinks with every pass.
+ */
+static int jmp_distance(const int *addrs, int i, int off, int moved)
+{
+	return addrs[i + off] - addrs[i] + (off < 0 ? moved : 0);
+}
+
 #define __LOAD_TCC_PTR(off)			\
 	emit_ldx(&prog, BPF_DW, BPF_REG_0, BPF_REG_FP, off)
 /* mov rax, qword ptr [rbp - rounded_stack_depth - 16] */
@@ -2588,7 +2549,7 @@ static int do_jit(struct bpf_verifier_env *env, struct bpf_prog *bpf_prog, int *
 	u64 arena_vm_start = 0, user_vm_start = 0;
 	void __percpu *priv_stack_ptr;
 	int i, excnt = 0;
-	int ilen, proglen = 0;
+	int ilen, moved, proglen = 0;
 	u8 *ip, *prog = temp;
 	u32 stack_depth;
 	int callee_saved_size;
@@ -2702,6 +2663,7 @@ static int do_jit(struct bpf_verifier_env *env, struct bpf_prog *bpf_prog, int *
 	if (rw_image)
 		memcpy(rw_image + proglen, temp, ilen);
 	proglen += ilen;
+	moved = addrs[0] - proglen;
 	addrs[0] = proglen;
 	prog = temp;

@@ -3747,8 +3709,8 @@ emit_cond_jmp:		/* Convert BPF opcode to x86 */
 			default: /* to silence GCC warning */
 				return -EFAULT;
 			}
-			jmp_offset = addrs[i + insn->off] - addrs[i];
-			if (is_imm8_jmp_offset(jmp_offset)) {
+			jmp_offset = jmp_distance(addrs, i, insn->off, moved);
+			if (is_imm8(jmp_offset)) {
 				if (jmp_padding) {
 					/* To keep the jmp_offset valid, the extra bytes are
 					 * padded before the jump insn, so we subtract the
@@ -3788,23 +3750,10 @@ emit_cond_jmp:		/* Convert BPF opcode to x86 */
 			break;
 		case BPF_JMP | BPF_JA:
 		case BPF_JMP32 | BPF_JA:
-			if (BPF_CLASS(insn->code) == BPF_JMP) {
-				if (insn->off == -1)
-					/* -1 jmp instructions will always jump
-					 * backwards two bytes. Explicitly handling
-					 * this case avoids wasting too many passes
-					 * when there are long sequences of replaced
-					 * dead code.
-					 */
-					jmp_offset = -2;
-				else
-					jmp_offset = addrs[i + insn->off] - addrs[i];
-			} else {
-				if (insn->imm == -1)
-					jmp_offset = -2;
-				else
-					jmp_offset = addrs[i + insn->imm] - addrs[i];
-			}
+			if (BPF_CLASS(insn->code) == BPF_JMP)
+				jmp_offset = jmp_distance(addrs, i, insn->off, moved);
+			else
+				jmp_offset = jmp_distance(addrs, i, insn->imm, moved);

 			if (!jmp_offset) {
 				/*
@@ -3833,7 +3782,7 @@ emit_cond_jmp:		/* Convert BPF opcode to x86 */
 				break;
 			}
 emit_jmp:
-			if (is_imm8_jmp_offset(jmp_offset)) {
+			if (is_imm8(jmp_offset)) {
 				if (jmp_padding) {
 					/* To avoid breaking jmp_offset, the extra bytes
 					 * are padded before the actual jmp insn, so
@@ -3869,7 +3818,7 @@ emit_jmp:
 			    emit_unwind_ret_addr(&prog, ip))
 				return -EINVAL;
 			if (seen_exit) {
-				jmp_offset = ctx->cleanup_addr - addrs[i];
+				jmp_offset = ctx->cleanup_addr - addrs[i] + moved;
 				goto emit_jmp;
 			}
 			seen_exit = true;
@@ -3930,6 +3879,7 @@ emit_jmp:
 			memcpy(rw_image + proglen, temp, ilen);
 		}
 		proglen += ilen;
+		moved = addrs[i] - proglen;
 		addrs[i] = proglen;
 		prog = temp;
 	}

pw-bot: cr

Re: [PATCH bpf-next 1/2] bpf: Stop JIT passes only when no insn moves

[Mykyta Yatsenko]

On 10/21/26 11:15 PM, Alexei Starovoitov wrote:
> On Wed, Oct 21, 2026 at 07:21 AM Mykyta Yatsenko <mykyta.yatsenko5@gmail.com> wrote:
>> A backward jump is sized from its target's current-pass address and its
>> own previous-pass address, so it can grow while other jumps shrink. Two
>> passes may then give the same image length with jumps still changing,
>> and the image pass fails with "bpf_jit: fatal error".
> 
> can we fix the sizing of the backward jump instead ?
> 
> It's the third time it bites us.
> commit 1612a981b766 ("bpf, x64: fix JIT emission for dead code")
> special cased ja -1 and
> commit c8831bdbfbab ("bpf, x64: Fix a jit convergence issue")
> limited imm8 to 123 because of it.
> With this patch jumps still grow, and the one that grows in a padding
> pass still ends in "unexpected jmp_cond padding: -4 bytes".
> 
> do_jit() knows how far the current pass moved insn i. With that taken
> into account a backward jump is sized by the insns it jumps over, the
> same way as a forward one. Insn sizes start at 64 and only go down, so
> the image shrinks with every pass like the comment in
> bpf_int_jit_compile() says, and proglen == oldproglen means that
> nothing moved.
> Then no need for addrs_changed, for the ja -1 special case and
> for is_imm8_jmp_offset().
> 
> Something like this (compile tested only):

I'll send v2. Thanks for the suggestion.

> pw-bot: cr