[PATCH bpf-next 0/8] bpf: Fixes for may_goto, insn patching and iterator loops

[PATCH bpf-next 0/8] bpf: Fixes for may_goto, insn patching and iterator loops

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

Fixes for four bugs in may_goto, in patching of insns and in
convergence of iterator loops, each followed by its tests.

Patch 1: arch_bpf_timed_may_goto() on x86 computes the address of count
and timestamp as rbp + offset. The prog with private stack keeps its
stack in r9, so bpf_check_timed_may_goto() reads and writes the kernel
stack, where r0-r5 have just been saved.

Patch 3: [ST, ST, first insn] that inits may_goto count and
[nospec, insn] move the insn down inside its own patch.
bpf_adj_branches() doesn't look inside the patch, so a call, ld_imm64
of a func or a jump that points backward lands short of its target
by the number of insns in front of it.

Patch 5: may_goto is expanded into a conditional jump with off + 5,
off + 2 or off - 1 stored into 16 bits without a range check.
may_goto +32763 jumps backward when it expires.

Patch 7: states_equal() matches ids through idmap, so the loop is
assumed to converge at bpf_iter_*_next() when the iterator was
destroyed and created again since the old state. The prog that never
ends is accepted.

On x86-64 without the fixes may_goto_priv_stack, may_goto_far/32767,
may_goto_far/-32768, both new tests of verifier_may_goto_1, "nospec in
front of a call" (unpriv) and four "iter: remake ... jump to next"
tests fail. With the fixes they pass.

veristat on selftests, 5477 progs: no prog changes its verdict except
the new "iter: remake" ones. Patch 7 adds insns to 16 progs that
call bpf_iter_*_next() in a loop: 11010007 -> 11011495 insns in total,
test_copy_from_user_dynptr 342 -> 470 is the largest in percent.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>

Alexei Starovoitov (8):
  bpf, x86: Fix timed may_goto with private stack
  selftests/bpf: Add test for timed may_goto with private stack
  bpf: Adjust pc-relative insn copied into its own patch
  selftests/bpf: Add tests for pc-relative insn copied into its own
    patch
  bpf: Fix overflow of jump offset in may_goto expansion
  selftests/bpf: Add tests for may_goto with far target
  bpf: Don't converge a loop on an iterator that was created anew
  selftests/bpf: Add tests for iterator created anew in its loop

 arch/x86/net/bpf_jit_comp.c                   |  12 +
 arch/x86/net/bpf_timed_may_goto.S             |  10 +-
 kernel/bpf/fixups.c                           | 123 ++++--
 kernel/bpf/states.c                           |  14 +-
 .../selftests/bpf/prog_tests/may_goto_far.c   |  92 +++++
 .../bpf/prog_tests/may_goto_priv_stack.c      |  41 ++
 tools/testing/selftests/bpf/progs/iters.c     | 382 ++++++++++++++++++
 .../selftests/bpf/progs/may_goto_priv_stack.c |  52 +++
 .../selftests/bpf/progs/verifier_may_goto_1.c | 121 ++++++
 .../selftests/bpf/progs/verifier_unpriv.c     |  37 ++
 10 files changed, 848 insertions(+), 36 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/may_goto_far.c
 create mode 100644 tools/testing/selftests/bpf/prog_tests/may_goto_priv_stack.c
 create mode 100644 tools/testing/selftests/bpf/progs/may_goto_priv_stack.c


base-commit: 93df8ae3267f19bf0c1135d26a0e21145dd0ea1c
-- 
2.55.0

[PATCH bpf-next 1/8] bpf, x86: Fix timed may_goto with private stack

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

arch_bpf_timed_may_goto() computes the address of count and timestamp
as rbp + offset. When the prog uses private stack the JIT maps r10 to r9
and nothing is reserved under rbp, so bpf_check_timed_may_goto() reads
and writes the timestamp in the kernel stack, where
arch_bpf_timed_may_goto() has just saved r0-r5 or further down.
The following loop in fentry prog with r0-r5 set to zero:

  1: may_goto +2
     r6 += 1
     goto 1b

leaves r3 with ktime in it when the prog has 64 bytes of stack and
ends after 65535 iterations when it has 128.

Add the frame pointer to the offset in the JIT, where rbp vs r9 is
known, and pass the pointer in AX.

arm64 and powerpc JITs keep the address of private stack in BPF_REG_FP
and are not affected.

Fixes: 2fb761823ead ("bpf, x86: Add x86 JIT support for timed may_goto")
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 arch/x86/net/bpf_jit_comp.c       | 12 ++++++++++++
 arch/x86/net/bpf_timed_may_goto.S | 10 ++--------
 2 files changed, 14 insertions(+), 8 deletions(-)

diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
index e2e531dd1e0b..6c7a0578760e 100644
--- a/arch/x86/net/bpf_jit_comp.c
+++ b/arch/x86/net/bpf_jit_comp.c
@@ -2961,6 +2961,18 @@ static int do_jit(struct bpf_verifier_env *env, struct bpf_prog *bpf_prog, int *
 				ip += emit_kfunc_arg_moves(fm, outgoing_arg_base -
 							   outgoing_rsp, &prog);
 			}
+			if (func == (u8 *)arch_bpf_timed_may_goto) {
+				u32 fp = priv_frame_ptr ? X86_REG_R9 : BPF_REG_FP;
+
+				/*
+				 * AX has the offset of count and timestamp
+				 * in the stack. Turn it into a pointer.
+				 * add r10, rbp or add r10, r9
+				 */
+				maybe_emit_mod(&prog, BPF_REG_AX, fp, true);
+				EMIT2(0x01, add_2reg(0xC0, BPF_REG_AX, fp));
+				ip += 3;
+			}
 			if (priv_frame_ptr) {
 				push_r9(&prog);
 				ip += 2;
diff --git a/arch/x86/net/bpf_timed_may_goto.S b/arch/x86/net/bpf_timed_may_goto.S
index 54c690cae190..6c6e03f725a3 100644
--- a/arch/x86/net/bpf_timed_may_goto.S
+++ b/arch/x86/net/bpf_timed_may_goto.S
@@ -11,12 +11,6 @@
 SYM_FUNC_START(arch_bpf_timed_may_goto)
 	ANNOTATE_NOENDBR
 
-	/*
-	 * r10 passes us stack depth, load the pointer to count and timestamp
-	 * into r10 by adding it to BPF frame pointer.
-	 */
-	leaq (%rbp, %r10, 1), %r10
-
 	/* Setup frame. */
 	pushq %rbp
 	movq %rsp, %rbp
@@ -30,8 +24,8 @@ SYM_FUNC_START(arch_bpf_timed_may_goto)
 	pushq %r8
 
 	/*
-	 * r10 has the pointer to count and timestamp, pass it as first
-	 * argument.
+	 * r10 has the pointer to count and timestamp. JIT added the frame
+	 * pointer to the offset. Pass it as first argument.
 	 */
 	movq %r10, %rdi
 
-- 
2.55.0

[PATCH bpf-next 2/8] selftests/bpf: Add test for timed may_goto with private stack

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

Run fentry progs with 64 and 128 bytes of stack that loop until
may_goto expires. Check that r0-r5 are intact after the loop and that
it made more than 65535 iterations.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 .../bpf/prog_tests/may_goto_priv_stack.c      | 41 +++++++++++++++
 .../selftests/bpf/progs/may_goto_priv_stack.c | 52 +++++++++++++++++++
 2 files changed, 93 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/may_goto_priv_stack.c
 create mode 100644 tools/testing/selftests/bpf/progs/may_goto_priv_stack.c

diff --git a/tools/testing/selftests/bpf/prog_tests/may_goto_priv_stack.c b/tools/testing/selftests/bpf/prog_tests/may_goto_priv_stack.c
new file mode 100644
index 000000000000..4f8476d36250
--- /dev/null
+++ b/tools/testing/selftests/bpf/prog_tests/may_goto_priv_stack.c
@@ -0,0 +1,41 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <test_progs.h>
+#include "may_goto_priv_stack.skel.h"
+
+static void check_regs(__u64 *regs)
+{
+	int i;
+
+	for (i = 0; i < 6; i++)
+		ASSERT_EQ(regs[i], 0, "reg");
+	/* count is refreshed at least once when may_goto is timed */
+	ASSERT_GT(regs[6], 0xffff, "iterations");
+}
+
+void test_may_goto_priv_stack(void)
+{
+	LIBBPF_OPTS(bpf_test_run_opts, topts);
+	struct may_goto_priv_stack *skel;
+	int err;
+
+	skel = may_goto_priv_stack__open_and_load();
+	if (!ASSERT_OK_PTR(skel, "open_and_load"))
+		return;
+
+	err = may_goto_priv_stack__attach(skel);
+	if (!ASSERT_OK(err, "attach"))
+		goto out;
+
+	memset(skel->bss->regs_64, 0xff, sizeof(skel->bss->regs_64));
+	memset(skel->bss->regs_128, 0xff, sizeof(skel->bss->regs_128));
+
+	err = bpf_prog_test_run_opts(bpf_program__fd(skel->progs.priv_stack_64), &topts);
+	if (!ASSERT_OK(err, "test_run"))
+		goto out;
+
+	check_regs(skel->bss->regs_64);
+	check_regs(skel->bss->regs_128);
+out:
+	may_goto_priv_stack__destroy(skel);
+}
diff --git a/tools/testing/selftests/bpf/progs/may_goto_priv_stack.c b/tools/testing/selftests/bpf/progs/may_goto_priv_stack.c
new file mode 100644
index 000000000000..5c2aa0aa5055
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/may_goto_priv_stack.c
@@ -0,0 +1,52 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <linux/bpf.h>
+#include <bpf/bpf_helpers.h>
+#include "../../../include/linux/filter.h"
+#include "bpf_misc.h"
+
+/* r0-r5 after the loop and the number of iterations */
+__u64 regs_64[7];
+__u64 regs_128[7];
+
+/*
+ * fentry prog with 64 or more bytes of stack uses private stack.
+ * Loop until may_goto expires. r0-r5 should stay zero.
+ */
+#define TIMED_MAY_GOTO_PRIV_STACK(size, func)				\
+SEC("fentry/" #func)							\
+__naked void priv_stack_##size(void)					\
+{									\
+	asm volatile (							\
+	"r6 = 0;"							\
+	"*(u64 *)(r10 - " #size ") = r6;"				\
+	"r7 = %[regs] ll;"						\
+	"r0 = 0;"							\
+	"r1 = 0;"							\
+	"r2 = 0;"							\
+	"r3 = 0;"							\
+	"r4 = 0;"							\
+	"r5 = 0;"							\
+"1:"									\
+	".8byte %[may_goto];"						\
+	"r6 += 1;"							\
+	"goto 1b;"							\
+	"*(u64 *)(r7 + 0) = r0;"					\
+	"*(u64 *)(r7 + 8) = r1;"					\
+	"*(u64 *)(r7 + 16) = r2;"					\
+	"*(u64 *)(r7 + 24) = r3;"					\
+	"*(u64 *)(r7 + 32) = r4;"					\
+	"*(u64 *)(r7 + 40) = r5;"					\
+	"*(u64 *)(r7 + 48) = r6;"					\
+	"r0 = 0;"							\
+	"exit;"								\
+	:								\
+	: [regs]"i"(&regs_##size),					\
+	  __imm_insn(may_goto, BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, 2, 0)) \
+	: __clobber_all);						\
+}
+
+TIMED_MAY_GOTO_PRIV_STACK(64, bpf_fentry_test1)
+TIMED_MAY_GOTO_PRIV_STACK(128, bpf_fentry_test2)
+
+char _license[] SEC("license") = "GPL";
-- 
2.55.0

[PATCH bpf-next 3/8] bpf: Adjust pc-relative insn copied into its own patch

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

bpf_do_misc_fixups() inits may_goto count by patching the first insn
of a subprog with [ST, ST, first insn]. bpf_convert_ctx_accesses()
patches insn that needs a barrier with [nospec, insn].
bpf_adj_branches() doesn't adjust insns inside the patch, so when
the copy is a call, ld_imm64 of a func or a jump that points backward
its target is off by the number of insns in front of it:

  static int A(void)  { return 1; }
  static int A2(void) { return 2; }
  static int B(void)
  {
          int i, ret = A();

          for (i = 0; i < 10 && can_loop; i++)
                  ...
          return ret;
  }

When A is placed in front of B and may_goto is timed 'call A' becomes
call of A + 2. B returns 2 when A + 2 is the start of A2. Otherwise
the prog is rejected with "verifier bug: No program to jit at insn".

Add bpf_adj_moved_insn() and use it for both copies.

Fixes: 011832b97b31 ("bpf: Introduce may_goto instruction")
Fixes: d6f1c85f2253 ("bpf: Fall back to nospec for Spectre v1")
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 kernel/bpf/fixups.c | 55 +++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 53 insertions(+), 2 deletions(-)

diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c
index a5d335a47d26..ae9713d292df 100644
--- a/kernel/bpf/fixups.c
+++ b/kernel/bpf/fixups.c
@@ -383,6 +383,44 @@ struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 off,
 	return new_prog;
 }
 
+/*
+ * insn was moved down by delta insns inside its own patch. Operands relative
+ * to the pc that point in front of the old position did not move with it.
+ */
+static int bpf_adj_moved_insn(struct bpf_insn *insn, u32 delta)
+{
+	u8 class = BPF_CLASS(insn->code), op = BPF_OP(insn->code);
+	s64 off = insn->imm, off_min = S32_MIN;
+	bool is_imm = true;
+
+	if (bpf_pseudo_func(insn) || bpf_pseudo_call(insn)) {
+		/* subprog that started at the old position starts with the patch */
+		if (off >= 0)
+			return 0;
+	} else if ((class == BPF_JMP || class == BPF_JMP32) &&
+		   op != BPF_CALL && op != BPF_EXIT) {
+		if (insn->code != (BPF_JMP32 | BPF_JA)) {
+			off = insn->off;
+			off_min = S16_MIN;
+			is_imm = false;
+		}
+		/* jump to itself stays */
+		if (off >= -1)
+			return 0;
+	} else {
+		return 0;
+	}
+
+	off -= delta;
+	if (off < off_min)
+		return -ERANGE;
+	if (is_imm)
+		insn->imm = off;
+	else
+		insn->off = off;
+	return 0;
+}
+
 /*
  * For all jmp insns in a given 'prog' that point to 'tgt_idx' insn adjust the
  * jump offset by 'delta'.
@@ -905,7 +943,13 @@ int bpf_convert_ctx_accesses(struct bpf_verifier_env *env)
 			struct bpf_insn *patch = insn_buf;
 
 			*patch++ = BPF_ST_NOSPEC();
-			*patch++ = *insn;
+			*patch = *insn;
+			ret = bpf_adj_moved_insn(patch++, 1);
+			if (ret) {
+				verbose(env, "insn %d cannot be patched due to 16-bit range\n",
+					env->insn_aux_data[i + delta].orig_idx);
+				return ret;
+			}
 			cnt = patch - insn_buf;
 			new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
 			if (!new_prog)
@@ -2597,7 +2641,14 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 						     BPF_MAX_LOOPS);
 		}
 		/* Copy first actual insn to preserve it */
-		insn_buf[cnt++] = env->prog->insnsi[subprog_start];
+		insn_buf[cnt] = env->prog->insnsi[subprog_start];
+		ret = bpf_adj_moved_insn(&insn_buf[cnt], cnt);
+		if (ret) {
+			verbose(env, "insn %d cannot be patched due to 16-bit range\n",
+				env->insn_aux_data[subprog_start].orig_idx);
+			return ret;
+		}
+		cnt++;
 
 		new_prog = bpf_patch_insn_data(env, subprog_start, insn_buf, cnt);
 		if (!new_prog)
-- 
2.55.0

[PATCH bpf-next 4/8] selftests/bpf: Add tests for pc-relative insn copied into its own patch

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

Add tests for may_goto in a subprog that starts with a call or with
ld_imm64 of a func located in front of it, and for nospec inserted
in front of such call.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 .../selftests/bpf/progs/verifier_may_goto_1.c | 121 ++++++++++++++++++
 .../selftests/bpf/progs/verifier_unpriv.c     |  37 ++++++
 2 files changed, 158 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/verifier_may_goto_1.c b/tools/testing/selftests/bpf/progs/verifier_may_goto_1.c
index db7e30da234f..faf9eec0a63e 100644
--- a/tools/testing/selftests/bpf/progs/verifier_may_goto_1.c
+++ b/tools/testing/selftests/bpf/progs/verifier_may_goto_1.c
@@ -173,4 +173,125 @@ __naked void timed_may_goto_preserves_regs(void)
 	: __clobber_all);
 }
 
+__used __naked static void mg_ret1(void)
+{
+	asm volatile (
+	"r0 = 1;"
+	"exit;"
+	::: __clobber_all);
+}
+
+__used __naked static void mg_ret2(void)
+{
+	asm volatile (
+	"r0 = 2;"
+	"exit;"
+	::: __clobber_all);
+}
+
+__used __naked static void mg_call_first(void)
+{
+	asm volatile (
+	"call mg_ret1;"
+	"r1 = 0;"
+"1:"
+	".8byte %[may_goto];"
+	"r1 += 1;"
+	"if r1 < 10 goto 1b;"
+	"exit;"
+	:
+	: __imm_insn(may_goto, BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, 2, 0))
+	: __clobber_all);
+}
+
+/*
+ * mg_ret1 and mg_ret2 are placed in front of mg_call_first,
+ * so the offset of its call is negative.
+ */
+SEC("socket")
+__description("may_goto in subprog that starts with a call")
+__success
+__retval(1)
+__naked void may_goto_subprog_call_first(void)
+{
+	asm volatile (
+	"call mg_ret1;"
+	"call mg_ret2;"
+	"call mg_call_first;"
+	"exit;"
+	::: __clobber_all);
+}
+
+__used __naked static void mg_cb_stop(void)
+{
+	asm volatile (
+	"r0 = 1;"
+	"exit;"
+	::: __clobber_all);
+}
+
+__used __naked static void mg_cb_cont(void)
+{
+	asm volatile (
+	"r0 = 0;"
+	"exit;"
+	::: __clobber_all);
+}
+
+/* r1 is zero, but not a constant, so that bpf_loop() is not inlined */
+__used __naked static void mg_func_first(void)
+{
+	asm volatile (
+	"r2 = %[mg_cb_stop] ll;"
+	"r4 = r1;"
+	"r1 = 2;"
+	"r3 = 0;"
+	"call %[bpf_loop];"
+	"r1 = 0;"
+"1:"
+	".8byte %[may_goto];"
+	"r1 += 1;"
+	"if r1 < 10 goto 1b;"
+	"exit;"
+	:
+	: __imm_addr(mg_cb_stop),
+	  __imm(bpf_loop),
+	  __imm_insn(may_goto, BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, 2, 0))
+	: __clobber_all);
+}
+
+/*
+ * mg_cb_stop stops bpf_loop() after the first iteration,
+ * mg_cb_cont lets it do both.
+ */
+SEC("socket")
+__description("may_goto in subprog that starts with ld_imm64 of a func")
+__success
+__retval(1)
+__naked void may_goto_subprog_func_first(void)
+{
+	asm volatile (
+	"r1 = 1;"
+	"r2 = %[mg_cb_stop] ll;"
+	"r3 = 0;"
+	"r4 = 0;"
+	"call %[bpf_loop];"
+	"r1 = 1;"
+	"r2 = %[mg_cb_cont] ll;"
+	"r3 = 0;"
+	"r4 = 0;"
+	"call %[bpf_loop];"
+	"call %[bpf_ktime_get_ns];"
+	"r1 = r0;"
+	"r1 >>= 63;"
+	"call mg_func_first;"
+	"exit;"
+	:
+	: __imm_addr(mg_cb_stop),
+	  __imm_addr(mg_cb_cont),
+	  __imm(bpf_loop),
+	  __imm(bpf_ktime_get_ns)
+	: __clobber_all);
+}
+
 char _license[] SEC("license") = "GPL";
diff --git a/tools/testing/selftests/bpf/progs/verifier_unpriv.c b/tools/testing/selftests/bpf/progs/verifier_unpriv.c
index 3069e70fbcbd..a54b5a58b945 100644
--- a/tools/testing/selftests/bpf/progs/verifier_unpriv.c
+++ b/tools/testing/selftests/bpf/progs/verifier_unpriv.c
@@ -1035,4 +1035,41 @@ __naked void stack_write_nospec_slot_index(void)
 "	::: __clobber_all);
 }
 
+__noinline int nospec_global_func(int x)
+{
+	return x + 1;
+}
+
+__used __naked static void nospec_call_subprog(void)
+{
+	asm volatile ("					\
+	call %[bpf_get_prandom_u32];			\
+	r0 &= 0xff;					\
+	r1 = 0;						\
+	if r0 < 0x100 goto l0_%=;			\
+	/* executed only speculatively */		\
+	r1 = r10;					\
+l0_%=:	call nospec_global_func;			\
+	exit;						\
+"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
+/* nospec_global_func is placed in front of nospec_call_subprog */
+SEC("socket")
+__description("unpriv: nospec in front of a call")
+__success __success_unpriv
+__caps_unpriv(CAP_BPF)
+__retval(1)
+__naked void nospec_backward_call(void)
+{
+	asm volatile ("					\
+	r1 = 0;						\
+	call nospec_global_func;			\
+	call nospec_call_subprog;			\
+	exit;						\
+"	::: __clobber_all);
+}
+
 char _license[] SEC("license") = "GPL";
-- 
2.55.0

[PATCH bpf-next 5/8] bpf: Fix overflow of jump offset in may_goto expansion

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

may_goto is expanded into 'if AX == 0 goto off + 5' when it's timed,
off + 2 when it's not and off - 1 when it jumps backward. The sum is
stored into 16-bit off without a range check, so may_goto +32763
turns into:

  if r12 == 0x0 goto pc-32768

and the prog jumps backward when may_goto expires.

Emit 'if AX != 0 goto +1; gotol' when the offset doesn't fit and
compute the offset from the number of insns in the expansion.
JITs that don't support gotol will reject such prog.

Fixes: 011832b97b31 ("bpf: Introduce may_goto instruction")
Fixes: e723608bf428 ("bpf: Add verifier support for timed may_goto")
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 kernel/bpf/fixups.c | 68 +++++++++++++++++++++++++++++----------------
 1 file changed, 44 insertions(+), 24 deletions(-)

diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c
index ae9713d292df..e9c2d6c06218 100644
--- a/kernel/bpf/fixups.c
+++ b/kernel/bpf/fixups.c
@@ -1690,6 +1690,30 @@ static int add_hidden_subprog(struct bpf_verifier_env *env, struct bpf_insn *pat
 	return 0;
 }
 
+/*
+ * Expand may_goto: load the count from the stack, jump to the target of
+ * may_goto when it is zero, then the tail that updates the count.
+ * Use gotol when the target is too far for 16-bit offset of a conditional jump.
+ */
+static int may_goto_expand(struct bpf_insn *insn_buf, int off, int stack_off,
+			   const struct bpf_insn *tail, int tail_cnt)
+{
+	int cnt = 0;
+
+	/* Forward jump has to step over the tail */
+	off = off >= 0 ? off + tail_cnt : off - 1;
+
+	insn_buf[cnt++] = BPF_LDX_MEM(BPF_DW, BPF_REG_AX, BPF_REG_10, stack_off);
+	if (off == (s16)off) {
+		insn_buf[cnt++] = BPF_JMP_IMM(BPF_JEQ, BPF_REG_AX, 0, off);
+	} else {
+		insn_buf[cnt++] = BPF_JMP_IMM(BPF_JNE, BPF_REG_AX, 0, 1);
+		insn_buf[cnt++] = BPF_JMP32_A(off >= 0 ? off : off - 1);
+	}
+	memcpy(insn_buf + cnt, tail, tail_cnt * sizeof(*tail));
+	return cnt + tail_cnt;
+}
+
 /* Do various post-verification rewrites in a single program pass.
  * These rewrites simplify JIT and interpreter implementations.
  */
@@ -1967,6 +1991,18 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 
 		if (bpf_is_may_goto_insn(insn) && bpf_jit_supports_timed_may_goto()) {
 			int stack_off_cnt = -stack_depth - 16;
+			/*
+			 * AX is used as an argument to pass in stack_off_cnt
+			 * (to add to r10/fp), and also as the return value of
+			 * the call to arch_bpf_timed_may_goto.
+			 */
+			struct bpf_insn tail[] = {
+				BPF_ALU64_IMM(BPF_SUB, BPF_REG_AX, 1),
+				BPF_JMP_IMM(BPF_JNE, BPF_REG_AX, 0, 2),
+				BPF_MOV64_IMM(BPF_REG_AX, stack_off_cnt),
+				BPF_EMIT_CALL(arch_bpf_timed_may_goto),
+				BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_AX, stack_off_cnt),
+			};
 
 			/*
 			 * Two 8 byte slots, depth-16 stores the count, and
@@ -1983,22 +2019,8 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			 * after subtraction, rinse and repeat.
 			 */
 			stack_depth_extra = 16;
-			insn_buf[0] = BPF_LDX_MEM(BPF_DW, BPF_REG_AX, BPF_REG_10, stack_off_cnt);
-			if (insn->off >= 0)
-				insn_buf[1] = BPF_JMP_IMM(BPF_JEQ, BPF_REG_AX, 0, insn->off + 5);
-			else
-				insn_buf[1] = BPF_JMP_IMM(BPF_JEQ, BPF_REG_AX, 0, insn->off - 1);
-			insn_buf[2] = BPF_ALU64_IMM(BPF_SUB, BPF_REG_AX, 1);
-			insn_buf[3] = BPF_JMP_IMM(BPF_JNE, BPF_REG_AX, 0, 2);
-			/*
-			 * AX is used as an argument to pass in stack_off_cnt
-			 * (to add to r10/fp), and also as the return value of
-			 * the call to arch_bpf_timed_may_goto.
-			 */
-			insn_buf[4] = BPF_MOV64_IMM(BPF_REG_AX, stack_off_cnt);
-			insn_buf[5] = BPF_EMIT_CALL(arch_bpf_timed_may_goto);
-			insn_buf[6] = BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_AX, stack_off_cnt);
-			cnt = 7;
+			cnt = may_goto_expand(insn_buf, insn->off, stack_off_cnt,
+					      tail, ARRAY_SIZE(tail));
 
 			new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
 			if (!new_prog)
@@ -2010,16 +2032,14 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			goto next_insn;
 		} else if (bpf_is_may_goto_insn(insn)) {
 			int stack_off = -stack_depth - 8;
+			struct bpf_insn tail[] = {
+				BPF_ALU64_IMM(BPF_SUB, BPF_REG_AX, 1),
+				BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_AX, stack_off),
+			};
 
 			stack_depth_extra = 8;
-			insn_buf[0] = BPF_LDX_MEM(BPF_DW, BPF_REG_AX, BPF_REG_10, stack_off);
-			if (insn->off >= 0)
-				insn_buf[1] = BPF_JMP_IMM(BPF_JEQ, BPF_REG_AX, 0, insn->off + 2);
-			else
-				insn_buf[1] = BPF_JMP_IMM(BPF_JEQ, BPF_REG_AX, 0, insn->off - 1);
-			insn_buf[2] = BPF_ALU64_IMM(BPF_SUB, BPF_REG_AX, 1);
-			insn_buf[3] = BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_AX, stack_off);
-			cnt = 4;
+			cnt = may_goto_expand(insn_buf, insn->off, stack_off,
+					      tail, ARRAY_SIZE(tail));
 
 			new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
 			if (!new_prog)
-- 
2.55.0

[PATCH bpf-next 6/8] selftests/bpf: Add tests for may_goto with far target

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

Generate syscall progs with may_goto that jumps up to 32767 insns
forward and 32768 insns backward. The prog loops until may_goto expires
and returns 0 when it lands on the target.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 .../selftests/bpf/prog_tests/may_goto_far.c   | 92 +++++++++++++++++++
 1 file changed, 92 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/may_goto_far.c

diff --git a/tools/testing/selftests/bpf/prog_tests/may_goto_far.c b/tools/testing/selftests/bpf/prog_tests/may_goto_far.c
new file mode 100644
index 000000000000..8d0ff30bd068
--- /dev/null
+++ b/tools/testing/selftests/bpf/prog_tests/may_goto_far.c
@@ -0,0 +1,92 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <test_progs.h>
+#include <linux/filter.h>
+
+#define MAY_GOTO(off)	BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, off, 0)
+#define FILL_CNT	33000
+
+static struct bpf_insn *fill(struct bpf_insn *insn, int cnt, int reg)
+{
+	while (cnt--)
+		*insn++ = BPF_MOV64_REG(BPF_REG_0, reg);
+	return insn;
+}
+
+/*
+ * Syscall prog that loops until may_goto expires. Its target is 'off' insns
+ * away:
+ *
+ *	r6 = r7 = 0, but not a constant for the verifier
+ *	r8 = 2
+ *	r9 = 0
+ *	r0 = r8		x FILL_CNT or 1
+ * 1:	if r6 == r9 goto +1
+ *	exit
+ *	r6 = r8
+ *	r0 = r9		x N when off is negative
+ *	if r7 != r9 goto 3f
+ * 2:	may_goto off	(1b or 4f)
+ *	goto 2b
+ * 3:	r0 = r8		x N when off is positive
+ * 4:	exit
+ *
+ * The prog returns 0 when may_goto jumps to its target and 2 when
+ * it lands in one of 'r0 = r8' areas. There are no constants between
+ * may_goto and its target to keep the distance when constants are blinded.
+ */
+static void test_far(int off)
+{
+	LIBBPF_OPTS(bpf_prog_load_opts, opts, .prog_flags = BPF_F_SLEEPABLE);
+	LIBBPF_OPTS(bpf_test_run_opts, topts);
+	int front = off < 0 ? 1 : FILL_CNT;
+	int mid = off < 0 ? -off - 5 : 1;
+	int back = off < 0 ? FILL_CNT : off - 1;
+	struct bpf_insn *insns, *insn;
+	int fd, err;
+
+	insns = calloc(front + mid + back + 16, sizeof(*insns));
+	if (!ASSERT_OK_PTR(insns, "calloc"))
+		return;
+
+	insn = insns;
+	*insn++ = BPF_EMIT_CALL(BPF_FUNC_ktime_get_ns);
+	*insn++ = BPF_MOV64_REG(BPF_REG_6, BPF_REG_0);
+	*insn++ = BPF_ALU64_IMM(BPF_RSH, BPF_REG_6, 63);
+	*insn++ = BPF_MOV64_REG(BPF_REG_7, BPF_REG_0);
+	*insn++ = BPF_ALU64_IMM(BPF_RSH, BPF_REG_7, 63);
+	*insn++ = BPF_MOV64_IMM(BPF_REG_8, 2);
+	*insn++ = BPF_MOV64_IMM(BPF_REG_9, 0);
+	insn = fill(insn, front, BPF_REG_8);
+	*insn++ = BPF_JMP_REG(BPF_JEQ, BPF_REG_6, BPF_REG_9, 1);
+	*insn++ = BPF_EXIT_INSN();
+	*insn++ = BPF_MOV64_REG(BPF_REG_6, BPF_REG_8);
+	insn = fill(insn, mid, BPF_REG_9);
+	*insn++ = BPF_JMP_REG(BPF_JNE, BPF_REG_7, BPF_REG_9, 2);
+	*insn++ = MAY_GOTO(off);
+	*insn++ = BPF_JMP_A(-2);
+	insn = fill(insn, back, BPF_REG_8);
+	*insn++ = BPF_EXIT_INSN();
+
+	fd = bpf_prog_load(BPF_PROG_TYPE_SYSCALL, NULL, "GPL", insns, insn - insns, &opts);
+	free(insns);
+	if (!ASSERT_GE(fd, 0, "prog_load"))
+		return;
+
+	err = bpf_prog_test_run_opts(fd, &topts);
+	ASSERT_OK(err, "test_run");
+	ASSERT_EQ(topts.retval, 0, "retval");
+	close(fd);
+}
+
+void test_may_goto_far(void)
+{
+	if (test__start_subtest("32762"))
+		test_far(32762);
+	if (test__start_subtest("32767"))
+		test_far(32767);
+	if (test__start_subtest("-32767"))
+		test_far(-32767);
+	if (test__start_subtest("-32768"))
+		test_far(-32768);
+}
-- 
2.55.0

[PATCH bpf-next 7/8] bpf: Don't converge a loop on an iterator that was created anew

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

When the verifier reaches bpf_iter_*_next() in a state that is equal to
a state that is still being explored it concludes that the loop
converged, since an active iterator will be drained eventually.
states_equal() matches ids through idmap, so the same is concluded for
an iterator that was destroyed and created again since the old state:

  bpf_iter_num_new(&it, 0, 10);
  loop:
          if (bpf_ktime_get_ns())
                  goto remake;
  next:
          if (!bpf_iter_num_next(&it))
                  goto out;
          goto loop;
  remake:
          bpf_iter_num_destroy(&it);
          bpf_iter_num_new(&it, 0, 10);
          goto next;

Such prog is accepted when the call of bpf_iter_num_next() is the first
prune point after bpf_iter_num_new() and it never returns. Otherwise
it's rejected with "infinite loop detected".

Require the iterator to have the same id in both states.

Fixes: 06accc8779c1 ("bpf: add support for open-coded iterator loops")
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 kernel/bpf/states.c | 14 ++++++++++++--
 1 file changed, 12 insertions(+), 2 deletions(-)

diff --git a/kernel/bpf/states.c b/kernel/bpf/states.c
index c1fbb339329f..18bf7b660c2f 100644
--- a/kernel/bpf/states.c
+++ b/kernel/bpf/states.c
@@ -1335,8 +1335,9 @@ int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 			 */
 			if (is_iter_next_insn(env, insn_idx)) {
 				if (states_equal(env, &sl->state, cur, RANGE_WITHIN)) {
-					struct bpf_func_state *cur_frame, *iter_frame;
+					struct bpf_func_state *cur_frame, *iter_frame, *old_frame;
 					struct bpf_reg_state *iter_state, *iter_reg;
+					struct bpf_reg_state *old_iter;
 					int spi;
 
 					cur_frame = cur->frame[cur->curframe];
@@ -1351,7 +1352,16 @@ int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 					spi = bpf_get_spi(iter_reg->var_off.value);
 					iter_frame = bpf_func(env, iter_reg);
 					iter_state = &bpf_stack_slot(iter_frame, spi)->spilled_ptr;
-					if (iter_state->iter.state == BPF_ITER_STATE_ACTIVE) {
+					old_frame = sl->state.frame[iter_reg->frameno];
+					old_iter = &bpf_stack_slot(old_frame, spi)->spilled_ptr;
+					/*
+					 * states_equal() matches ids through idmap.
+					 * The loop converged only if it's the same
+					 * iterator. The one that was destroyed and
+					 * created again starts from the beginning.
+					 */
+					if (iter_state->iter.state == BPF_ITER_STATE_ACTIVE &&
+					    iter_state->id == old_iter->id) {
 						loop = true;
 						goto hit;
 					}
-- 
2.55.0

[PATCH bpf-next 8/8] selftests/bpf: Add tests for iterator created anew in its loop

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

Add progs that destroy and create the iterator inside its loop with
and without a prune point in front of bpf_iter_num_next(). All of them
should be rejected. Nested bpf_for() loops, where the inner iterator is
created in every iteration of the outer loop, should load.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 tools/testing/selftests/bpf/progs/iters.c | 382 ++++++++++++++++++++++
 1 file changed, 382 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/iters.c b/tools/testing/selftests/bpf/progs/iters.c
index 65d4c6e01f93..ae845ad747bf 100644
--- a/tools/testing/selftests/bpf/progs/iters.c
+++ b/tools/testing/selftests/bpf/progs/iters.c
@@ -2188,4 +2188,386 @@ __naked void loop_counter_precision_2nd_iter(void)
 	);
 }
 
+/*
+ * An iterator that is destroyed and created again inside its loop starts from
+ * the beginning and the loop never ends. In the first four progs the first
+ * prune point after bpf_iter_num_new() is the call of bpf_iter_num_next().
+ */
+SEC("socket")
+__description("iter: remake in the loop, jump to next")
+__failure __msg("infinite loop detected")
+__naked void iter_remake_jmp(void)
+{
+	asm volatile (
+	"r1 = r10;"
+	"r1 += -8;"
+	"r2 = 0;"
+	"r3 = 10;"
+	"call %[bpf_iter_num_new];"
+"1:"
+	"call %[bpf_ktime_get_ns];"
+	"if r0 != 0 goto 3f;"
+	"r1 = r10;"
+	"r1 += -8;"
+"2:"
+	"call %[bpf_iter_num_next];"
+	"if r0 != 0 goto 1b;"
+	"r1 = r10;"
+	"r1 += -8;"
+	"call %[bpf_iter_num_destroy];"
+	"r0 = 0;"
+	"exit;"
+"3:"
+	"r1 = r10;"
+	"r1 += -8;"
+	"call %[bpf_iter_num_destroy];"
+	"r1 = r10;"
+	"r1 += -8;"
+	"r2 = 0;"
+	"r3 = 10;"
+	"call %[bpf_iter_num_new];"
+	"r1 = r10;"
+	"r1 += -8;"
+	"goto 2b;"
+	:
+	: __imm(bpf_iter_num_new),
+	  __imm(bpf_iter_num_next),
+	  __imm(bpf_iter_num_destroy),
+	  __imm(bpf_ktime_get_ns)
+	: __clobber_all);
+}
+
+__used __naked static void iter_remake(void)
+{
+	asm volatile (
+	"r6 = r1;"
+	"call %[bpf_iter_num_destroy];"
+	"r1 = r6;"
+	"r2 = 0;"
+	"r3 = 10;"
+	"call %[bpf_iter_num_new];"
+	"r0 = 0;"
+	"exit;"
+	:
+	: __imm(bpf_iter_num_new),
+	  __imm(bpf_iter_num_destroy)
+	: __clobber_all);
+}
+
+SEC("socket")
+__description("iter: remake in a callee, jump to next")
+__failure __msg("infinite loop detected")
+__naked void iter_remake_callee_jmp(void)
+{
+	asm volatile (
+	"r1 = r10;"
+	"r1 += -8;"
+	"r2 = 0;"
+	"r3 = 10;"
+	"call %[bpf_iter_num_new];"
+"1:"
+	"call %[bpf_ktime_get_ns];"
+	"if r0 != 0 goto 3f;"
+	"r1 = r10;"
+	"r1 += -8;"
+"2:"
+	"call %[bpf_iter_num_next];"
+	"if r0 != 0 goto 1b;"
+	"r1 = r10;"
+	"r1 += -8;"
+	"call %[bpf_iter_num_destroy];"
+	"r0 = 0;"
+	"exit;"
+"3:"
+	"r1 = r10;"
+	"r1 += -8;"
+	"call iter_remake;"
+	"r1 = r10;"
+	"r1 += -8;"
+	"goto 2b;"
+	:
+	: __imm(bpf_iter_num_new),
+	  __imm(bpf_iter_num_next),
+	  __imm(bpf_iter_num_destroy),
+	  __imm(bpf_ktime_get_ns)
+	: __clobber_all);
+}
+
+SEC("socket")
+__description("iter: remake after next, jump to next")
+__failure __msg("infinite loop detected")
+__naked void iter_remake_after_next_jmp(void)
+{
+	asm volatile (
+	"r1 = r10;"
+	"r1 += -8;"
+	"r2 = 0;"
+	"r3 = 10;"
+	"call %[bpf_iter_num_new];"
+	"r1 = r10;"
+	"r1 += -8;"
+"1:"
+	"call %[bpf_iter_num_next];"
+	"if r0 == 0 goto 2f;"
+	"r1 = r10;"
+	"r1 += -8;"
+	"call %[bpf_iter_num_destroy];"
+	"r1 = r10;"
+	"r1 += -8;"
+	"r2 = 0;"
+	"r3 = 10;"
+	"call %[bpf_iter_num_new];"
+	"r1 = r10;"
+	"r1 += -8;"
+	"goto 1b;"
+"2:"
+	"r1 = r10;"
+	"r1 += -8;"
+	"call %[bpf_iter_num_destroy];"
+	"r0 = 0;"
+	"exit;"
+	:
+	: __imm(bpf_iter_num_new),
+	  __imm(bpf_iter_num_next),
+	  __imm(bpf_iter_num_destroy),
+	  __imm(bpf_ktime_get_ns)
+	: __clobber_all);
+}
+
+SEC("socket")
+__description("iter: two iterators, remake each after its next")
+__failure __msg("infinite loop detected")
+__naked void iter_remake_two_jmp(void)
+{
+	asm volatile (
+	"r1 = r10;"
+	"r1 += -8;"
+	"r2 = 0;"
+	"r3 = 10;"
+	"call %[bpf_iter_num_new];"
+	"r1 = r10;"
+	"r1 += -16;"
+	"r2 = 0;"
+	"r3 = 10;"
+	"call %[bpf_iter_num_new];"
+	"r1 = r10;"
+	"r1 += -8;"
+"1:"
+	"call %[bpf_iter_num_next];"
+	"if r0 == 0 goto 2f;"
+	"r1 = r10;"
+	"r1 += -8;"
+	"call %[bpf_iter_num_destroy];"
+	"r1 = r10;"
+	"r1 += -8;"
+	"r2 = 0;"
+	"r3 = 10;"
+	"call %[bpf_iter_num_new];"
+	"r1 = r10;"
+	"r1 += -16;"
+	"call %[bpf_iter_num_next];"
+	"if r0 == 0 goto 2f;"
+	"r1 = r10;"
+	"r1 += -16;"
+	"call %[bpf_iter_num_destroy];"
+	"r1 = r10;"
+	"r1 += -16;"
+	"r2 = 0;"
+	"r3 = 10;"
+	"call %[bpf_iter_num_new];"
+	"r1 = r10;"
+	"r1 += -8;"
+	"goto 1b;"
+"2:"
+	"r1 = r10;"
+	"r1 += -8;"
+	"call %[bpf_iter_num_destroy];"
+	"r1 = r10;"
+	"r1 += -16;"
+	"call %[bpf_iter_num_destroy];"
+	"r0 = 0;"
+	"exit;"
+	:
+	: __imm(bpf_iter_num_new),
+	  __imm(bpf_iter_num_next),
+	  __imm(bpf_iter_num_destroy),
+	  __imm(bpf_ktime_get_ns)
+	: __clobber_all);
+}
+
+/* Same loops with a prune point in front of bpf_iter_num_next() */
+SEC("socket")
+__description("iter: remake in the loop")
+__failure __msg("infinite loop detected")
+__flag(BPF_F_TEST_STATE_FREQ)
+__naked void iter_remake_inline(void)
+{
+	asm volatile (
+	"r1 = r10;"
+	"r1 += -8;"
+	"r2 = 0;"
+	"r3 = 10;"
+	"call %[bpf_iter_num_new];"
+"1:"
+	"call %[bpf_ktime_get_ns];"
+	"if r0 == 0 goto 2f;"
+	"r1 = r10;"
+	"r1 += -8;"
+	"call %[bpf_iter_num_destroy];"
+	"r1 = r10;"
+	"r1 += -8;"
+	"r2 = 0;"
+	"r3 = 10;"
+	"call %[bpf_iter_num_new];"
+"2:"
+	"r1 = r10;"
+	"r1 += -8;"
+	"call %[bpf_iter_num_next];"
+	"if r0 != 0 goto 1b;"
+	"r1 = r10;"
+	"r1 += -8;"
+	"call %[bpf_iter_num_destroy];"
+	"r0 = 0;"
+	"exit;"
+	:
+	: __imm(bpf_iter_num_new),
+	  __imm(bpf_iter_num_next),
+	  __imm(bpf_iter_num_destroy),
+	  __imm(bpf_ktime_get_ns)
+	: __clobber_all);
+}
+
+SEC("socket")
+__description("iter: remake in a callee")
+__failure __msg("infinite loop detected")
+__flag(BPF_F_TEST_STATE_FREQ)
+__naked void iter_remake_callee(void)
+{
+	asm volatile (
+	"r1 = r10;"
+	"r1 += -8;"
+	"r2 = 0;"
+	"r3 = 10;"
+	"call %[bpf_iter_num_new];"
+"1:"
+	"call %[bpf_ktime_get_ns];"
+	"if r0 == 0 goto 2f;"
+	"r1 = r10;"
+	"r1 += -8;"
+	"call iter_remake;"
+"2:"
+	"r1 = r10;"
+	"r1 += -8;"
+	"call %[bpf_iter_num_next];"
+	"if r0 != 0 goto 1b;"
+	"r1 = r10;"
+	"r1 += -8;"
+	"call %[bpf_iter_num_destroy];"
+	"r0 = 0;"
+	"exit;"
+	:
+	: __imm(bpf_iter_num_new),
+	  __imm(bpf_iter_num_next),
+	  __imm(bpf_iter_num_destroy),
+	  __imm(bpf_ktime_get_ns)
+	: __clobber_all);
+}
+
+SEC("socket")
+__description("iter: remake after next")
+__failure __msg("infinite loop detected")
+__flag(BPF_F_TEST_STATE_FREQ)
+__naked void iter_remake_after_next(void)
+{
+	asm volatile (
+	"r1 = r10;"
+	"r1 += -8;"
+	"r2 = 0;"
+	"r3 = 10;"
+	"call %[bpf_iter_num_new];"
+"1:"
+	"r1 = r10;"
+	"r1 += -8;"
+	"call %[bpf_iter_num_next];"
+	"if r0 == 0 goto 2f;"
+	"r1 = r10;"
+	"r1 += -8;"
+	"call %[bpf_iter_num_destroy];"
+	"r1 = r10;"
+	"r1 += -8;"
+	"r2 = 0;"
+	"r3 = 10;"
+	"call %[bpf_iter_num_new];"
+	"goto 1b;"
+"2:"
+	"r1 = r10;"
+	"r1 += -8;"
+	"call %[bpf_iter_num_destroy];"
+	"r0 = 0;"
+	"exit;"
+	:
+	: __imm(bpf_iter_num_new),
+	  __imm(bpf_iter_num_next),
+	  __imm(bpf_iter_num_destroy),
+	  __imm(bpf_ktime_get_ns)
+	: __clobber_all);
+}
+
+SEC("socket")
+__description("iter: remake when drained")
+__failure __msg("infinite loop detected")
+__flag(BPF_F_TEST_STATE_FREQ)
+__naked void iter_remake_drained(void)
+{
+	asm volatile (
+	"r1 = r10;"
+	"r1 += -8;"
+	"r2 = 0;"
+	"r3 = 10;"
+	"call %[bpf_iter_num_new];"
+"1:"
+	"call %[bpf_ktime_get_ns];"
+	"if r0 == 119 goto 2f;"
+	"r1 = r10;"
+	"r1 += -8;"
+	"call %[bpf_iter_num_next];"
+	"if r0 != 0 goto 1b;"
+	"r1 = r10;"
+	"r1 += -8;"
+	"call %[bpf_iter_num_destroy];"
+	"r1 = r10;"
+	"r1 += -8;"
+	"r2 = 0;"
+	"r3 = 10;"
+	"call %[bpf_iter_num_new];"
+	"goto 1b;"
+"2:"
+	"r1 = r10;"
+	"r1 += -8;"
+	"call %[bpf_iter_num_destroy];"
+	"r0 = 0;"
+	"exit;"
+	:
+	: __imm(bpf_iter_num_new),
+	  __imm(bpf_iter_num_next),
+	  __imm(bpf_iter_num_destroy),
+	  __imm(bpf_ktime_get_ns)
+	: __clobber_all);
+}
+
+/* The inner iterator is created in every iteration of the outer loop */
+SEC("socket")
+__description("iter: nested loops")
+__success __retval(12)
+int iter_nested_remake(void *ctx)
+{
+	int i, j, sum = 0;
+
+	bpf_for(i, 0, 3) {
+		bpf_for(j, 0, 4)
+			sum++;
+	}
+	return sum;
+}
+
 char _license[] SEC("license") = "GPL";
-- 
2.55.0

Re: [PATCH bpf-next 6/8] selftests/bpf: Add tests for may_goto with far target

[bot+bpf-ci]

[-- Attachment #1: Type: text/plain, Size: 4777 bytes --]

> diff --git a/tools/testing/selftests/bpf/prog_tests/may_goto_far.c b/tools/testing/selftests/bpf/prog_tests/may_goto_far.c
> new file mode 100644
> index 000000000000..8d0ff30bd068
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/prog_tests/may_goto_far.c
> @@ -0,0 +1,92 @@
> +// SPDX-License-Identifier: GPL-2.0
> +
> +#include <test_progs.h>
> +#include <linux/filter.h>
> +
> +#define MAY_GOTO(off)	BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, off, 0)
> +#define FILL_CNT	33000
> +
> +static struct bpf_insn *fill(struct bpf_insn *insn, int cnt, int reg)
> +{
> +	while (cnt--)
> +		*insn++ = BPF_MOV64_REG(BPF_REG_0, reg);
> +	return insn;
> +}
> +
> +/*
> + * Syscall prog that loops until may_goto expires. Its target is 'off' insns
> + * away:
> + *
> + *	r6 = r7 = 0, but not a constant for the verifier
> + *	r8 = 2
> + *	r9 = 0
> + *	r0 = r8		x FILL_CNT or 1
> + * 1:	if r6 == r9 goto +1
> + *	exit
> + *	r6 = r8
> + *	r0 = r9		x N when off is negative
> + *	if r7 != r9 goto 3f
> + * 2:	may_goto off	(1b or 4f)
> + *	goto 2b
> + * 3:	r0 = r8		x N when off is positive
> + * 4:	exit
> + *
> + * The prog returns 0 when may_goto jumps to its target and 2 when
> + * it lands in one of 'r0 = r8' areas. There are no constants between
> + * may_goto and its target to keep the distance when constants are blinded.
> + */
> +static void test_far(int off)
> +{
> +	LIBBPF_OPTS(bpf_prog_load_opts, opts, .prog_flags = BPF_F_SLEEPABLE);
> +	LIBBPF_OPTS(bpf_test_run_opts, topts);
> +	int front = off < 0 ? 1 : FILL_CNT;
> +	int mid = off < 0 ? -off - 5 : 1;
> +	int back = off < 0 ? FILL_CNT : off - 1;
> +	struct bpf_insn *insns, *insn;
> +	int fd, err;
> +
> +	insns = calloc(front + mid + back + 16, sizeof(*insns));
> +	if (!ASSERT_OK_PTR(insns, "calloc"))
> +		return;
> +
> +	insn = insns;
> +	*insn++ = BPF_EMIT_CALL(BPF_FUNC_ktime_get_ns);
> +	*insn++ = BPF_MOV64_REG(BPF_REG_6, BPF_REG_0);
> +	*insn++ = BPF_ALU64_IMM(BPF_RSH, BPF_REG_6, 63);
> +	*insn++ = BPF_MOV64_REG(BPF_REG_7, BPF_REG_0);
> +	*insn++ = BPF_ALU64_IMM(BPF_RSH, BPF_REG_7, 63);
> +	*insn++ = BPF_MOV64_IMM(BPF_REG_8, 2);
> +	*insn++ = BPF_MOV64_IMM(BPF_REG_9, 0);
> +	insn = fill(insn, front, BPF_REG_8);
> +	*insn++ = BPF_JMP_REG(BPF_JEQ, BPF_REG_6, BPF_REG_9, 1);
> +	*insn++ = BPF_EXIT_INSN();
> +	*insn++ = BPF_MOV64_REG(BPF_REG_6, BPF_REG_8);
> +	insn = fill(insn, mid, BPF_REG_9);
> +	*insn++ = BPF_JMP_REG(BPF_JNE, BPF_REG_7, BPF_REG_9, 2);
> +	*insn++ = MAY_GOTO(off);
> +	*insn++ = BPF_JMP_A(-2);
> +	insn = fill(insn, back, BPF_REG_8);
> +	*insn++ = BPF_EXIT_INSN();
> +
> +	fd = bpf_prog_load(BPF_PROG_TYPE_SYSCALL, NULL, "GPL", insns, insn - insns, &opts);
> +	free(insns);
> +	if (!ASSERT_GE(fd, 0, "prog_load"))
> +		return;
> +
> +	err = bpf_prog_test_run_opts(fd, &topts);
> +	ASSERT_OK(err, "test_run");
> +	ASSERT_EQ(topts.retval, 0, "retval");
> +	close(fd);
> +}
> +
> +void test_may_goto_far(void)
> +{
> +	if (test__start_subtest("32762"))
> +		test_far(32762);
> +	if (test__start_subtest("32767"))
> +		test_far(32767);
> +	if (test__start_subtest("-32767"))
> +		test_far(-32767);
> +	if (test__start_subtest("-32768"))
> +		test_far(-32768);
> +}

A subsystem pattern flags this as potentially concerning: this adds a
new standalone prog_tests file for one narrow variant of may_goto
behaviour, specifically testing targets far enough away that the
expansion in may_goto_expand() falls back to the 'if AX != 0 goto +1;
gotol' path.

General may_goto coverage already exists in
progs/verifier_may_goto_1.c, which is run by prog_tests/verifier.c.
That file includes runtime cases with __retval checks, including a
SEC("syscall") test. The pc-relative fix earlier in this series also
added its new may_goto cases to verifier_may_goto_1.c. Large
inline-asm programs are already an established pattern in the same
tree: progs/verifier_gotol.c uses '.rept 40000' for a far gotol, and
progs/verifier_call_large_imm.c uses '.rept 32765' and '.rept 32768'.

Could the four offsets (32762, 32767, -32767, -32768) be __naked
__retval(0) cases in verifier_may_goto_1.c instead of a new file?

One reason for a separate file might be that generating the program at
runtime from 'off' derives all four fill counts from one formula, while
the inline-asm form would need four hand-counted .rept programs and a
raw-encoded may_goto for each offset. However, it would be helpful to
understand if that convenience justifies the separate file, or if the
precedent of keeping related may_goto tests together in
verifier_may_goto_1.c takes priority.


---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/36073900100

Re: [PATCH bpf-next 6/8] selftests/bpf: Add tests for may_goto with far target

[Alexei Starovoitov]

On Fri, Sep 25, 2026 at 12:01 AM bot+bpf-ci@kernel.org <bot+bpf-ci@kernel.org> wrote:
>> +static void test_far(int off)
>> +{
>> +	LIBBPF_OPTS(bpf_prog_load_opts, opts, .prog_flags = BPF_F_SLEEPABLE);
>> +	LIBBPF_OPTS(bpf_test_run_opts, topts);
>> +	int front = off < 0 ? 1 : FILL_CNT;
>> +	int mid = off < 0 ? -off - 5 : 1;
>> +	int back = off < 0 ? FILL_CNT : off - 1;

[...]

> Could the four offsets (32762, 32767, -32767, -32768) be __naked
> __retval(0) cases in verifier_may_goto_1.c instead of a new file?

No. That's four progs of 66k insns each. 2 Mbyte of .rept in
verifier_may_goto_1.bpf.o and test_loader opens the whole object
again for every test in the file.
Here the fill counts are computed from 'off' at run time, like
bpf_fill_*() do in test_verifier.c.

Re: [PATCH bpf-next 0/8] bpf: Fixes for may_goto, insn patching and iterator loops

[Kumar Kartikeya Dwivedi]

On Fri Sep 25, 2026 at 1:31 AM CEST, Alexei Starovoitov wrote:
> From: Alexei Starovoitov <ast@kernel.org>
>
> Fixes for four bugs in may_goto, in patching of insns and in
> convergence of iterator loops, each followed by its tests.
>
> Patch 1: arch_bpf_timed_may_goto() on x86 computes the address of count
> and timestamp as rbp + offset. The prog with private stack keeps its
> stack in r9, so bpf_check_timed_may_goto() reads and writes the kernel
> stack, where r0-r5 have just been saved.
>
> Patch 3: [ST, ST, first insn] that inits may_goto count and
> [nospec, insn] move the insn down inside its own patch.
> bpf_adj_branches() doesn't look inside the patch, so a call, ld_imm64
> of a func or a jump that points backward lands short of its target
> by the number of insns in front of it.
>
> Patch 5: may_goto is expanded into a conditional jump with off + 5,
> off + 2 or off - 1 stored into 16 bits without a range check.
> may_goto +32763 jumps backward when it expires.
>
> Patch 7: states_equal() matches ids through idmap, so the loop is
> assumed to converge at bpf_iter_*_next() when the iterator was
> destroyed and created again since the old state. The prog that never
> ends is accepted.
>
> On x86-64 without the fixes may_goto_priv_stack, may_goto_far/32767,
> may_goto_far/-32768, both new tests of verifier_may_goto_1, "nospec in
> front of a call" (unpriv) and four "iter: remake ... jump to next"
> tests fail. With the fixes they pass.
>
> veristat on selftests, 5477 progs: no prog changes its verdict except
> the new "iter: remake" ones. Patch 7 adds insns to 16 progs that
> call bpf_iter_*_next() in a loop: 11010007 -> 11011495 insns in total,
> test_copy_from_user_dynptr 342 -> 470 is the largest in percent.
>
> Signed-off-by: Alexei Starovoitov <ast@kernel.org>
>

For the set:
Acked-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>

Re: [PATCH bpf-next 0/8] bpf: Fixes for may_goto, insn patching and iterator loops

[patchwork-bot+netdevbpf]

Hello:

This series was applied to bpf/bpf-next.git (master)
by Alexei Starovoitov <ast@kernel.org>:

On Thu, 24 Sep 2026 23:31:22 +0000 you wrote:
> From: Alexei Starovoitov <ast@kernel.org>
> 
> Fixes for four bugs in may_goto, in patching of insns and in
> convergence of iterator loops, each followed by its tests.
> 
> Patch 1: arch_bpf_timed_may_goto() on x86 computes the address of count
> and timestamp as rbp + offset. The prog with private stack keeps its
> stack in r9, so bpf_check_timed_may_goto() reads and writes the kernel
> stack, where r0-r5 have just been saved.
> 
> [...]

Here is the summary with links:
  - [bpf-next,1/8] bpf, x86: Fix timed may_goto with private stack
    https://git.kernel.org/bpf/bpf-next/c/bb83425b3cdc
  - [bpf-next,2/8] selftests/bpf: Add test for timed may_goto with private stack
    https://git.kernel.org/bpf/bpf-next/c/d17107a3051b
  - [bpf-next,3/8] bpf: Adjust pc-relative insn copied into its own patch
    https://git.kernel.org/bpf/bpf-next/c/67a3b916a7ae
  - [bpf-next,4/8] selftests/bpf: Add tests for pc-relative insn copied into its own patch
    https://git.kernel.org/bpf/bpf-next/c/913a5466dbfc
  - [bpf-next,5/8] bpf: Fix overflow of jump offset in may_goto expansion
    https://git.kernel.org/bpf/bpf-next/c/8a12a00f6c5d
  - [bpf-next,6/8] selftests/bpf: Add tests for may_goto with far target
    https://git.kernel.org/bpf/bpf-next/c/948c658c93de
  - [bpf-next,7/8] bpf: Don't converge a loop on an iterator that was created anew
    https://git.kernel.org/bpf/bpf-next/c/6f3ee3516305
  - [bpf-next,8/8] selftests/bpf: Add tests for iterator created anew in its loop
    https://git.kernel.org/bpf/bpf-next/c/36e238196ac5

You are awesome, thank you!
-- 
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html