[PATCH bpf v2 0/9] bpf: One may_goto time slice per prog invocation

[PATCH bpf v2 0/9] bpf: One may_goto time slice per prog invocation

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

may_goto stops a loop that the verifier cannot bound: after 250 ms the loop
must exit. The count and the timestamp are in the stack frame of the
function that contains the loop. So the limit is for one call of a subprog,
not for one invocation of a prog. Loops that nest across calls multiply it,
and 9 insns lock up a cpu:

  main:                 sub:
  1: call sub           1: may_goto 2f
     may_goto 2f           goto 1b
     goto 1b            2: r0 = 0
  2: r0 = 1                exit
     exit

This series uses one count and one timestamp for all may_goto of a prog, in
per-cpu memory of the prog. The main prog sets them in its first insns.
When the time is up each loop ends at its next may_goto, in any function.

There is nothing in the stack frame any more, and nothing at the entry or
at an exit of a subprog. The C code of may_goto, helpers, kfuncs and
trampolines do not change. The callers of async callbacks save and restore
count and timestamp.

 - Patch 1: the interpreter can run a prog with the timed form of may_goto.
   Then the kernel crashes. This fix does not depend on the other patches.
 - Patches 2-4 change three selftests that rely on a time slice for each
   frame.
 - Patch 5 adds per-cpu insns to the JIT of s390. It is the only JIT with
   timed may_goto that doesn't have them.
 - Patch 6 passes a pointer to arch_bpf_timed_may_goto() in place of an
   offset in the stack frame. It removes code from six archs.
 - Patch 7 is the change.
 - Patch 8 ends bpf_loop() and bpf_for_each_map_elem() when the time is up.
 - Patch 9 has the tests.

What changes for a prog:
 - The 250 ms are for all loops of an invocation, not for each frame.
 - When the time is up, a function that is called after that makes no
   iteration. Today each call has a new time slice.

Count and timestamp are per-cpu, so a second invocation of the same prog on
the same cpu shares them with the first one. The error is on the long side:
the first one gets more time. None is stopped before it is 250 ms old.

All progs with may_goto get different code: 56 of 493 progs of scx, none of
Cilium. The series adds 1.8% to their JITed code, and they use 25% less
stack. On x86-64 (Zen 5) a call of a function with may_goto is cheaper than
before, and an iteration of an empty loop costs 0.09 nsec more.

Tested on x86-64: test_progs, test_progs-no_alu32, test_progs-cpuv4,
test_progs-bpf_gcc and test_verifier have no new failure. The same is true
for test_progs with KASAN, and for test_progs and test_verifier with
mitigations on. On arm64 the new tests pass in QEMU. On s390 test_progs did
not run: progs for the per-cpu insn and for may_goto pass in QEMU. riscv,
loongarch and powerpc are compile tested only.

v1 was patches 7 and 8 of [1]. I dropped them from v2 of that series [2].
v1 -> v2:
 - v1 also had a count in per-cpu memory. A subprog took it at its entry
   and gave it back at each exit. The insns at the exit changed R2, which
   is a part of a 16-byte return value (Ihor). Now each may_goto uses the
   per-cpu count, and there are no insns at the entry and at exits.
 - Each read of the clock walked the stack to find the prog. Now may_goto
   has the address.
 - Add patches 1-6 and 8.

[1] https://lore.kernel.org/bpf/20261026025943.404450-1-alexei.starovoitov@gmail.com/
[2] https://lore.kernel.org/bpf/20261027190314.1440199-1-alexei.starovoitov@gmail.com/

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

Alexei Starovoitov (9):
  bpf: Emit timed may_goto for JITed progs only
  selftests/bpf: Don't cast a pointer to .bss in arena_htab_asm
  selftests/bpf: Give the first loop of cond_break5 an end
  selftests/bpf: End the loop of parallel_test_bitmap after 50 ms
  s390/bpf: Support internal-only MOV instruction to resolve per-CPU
    addrs
  bpf: Pass a pointer to arch_bpf_timed_may_goto()
  bpf: One may_goto time slice per prog invocation
  bpf: End bpf_loop() when the time of may_goto is up
  selftests/bpf: Test one may_goto time slice per prog invocation

 arch/arm64/net/bpf_timed_may_goto.S           |  12 +-
 arch/loongarch/net/bpf_timed_may_goto.S       |  10 +-
 arch/powerpc/net/bpf_timed_may_goto.S         |   9 +-
 arch/riscv/net/bpf_timed_may_goto.S           |  10 +-
 arch/s390/net/bpf_jit_comp.c                  |  22 +-
 arch/s390/net/bpf_timed_may_goto.S            |   8 +-
 arch/x86/net/bpf_jit_comp.c                   |  12 -
 arch/x86/net/bpf_timed_may_goto.S             |   5 +-
 include/linux/bpf.h                           |   2 +
 include/linux/bpf_verifier.h                  |   4 +
 include/linux/filter.h                        |   8 +
 kernel/bpf/core.c                             |  33 +
 kernel/bpf/fixups.c                           | 149 ++-
 kernel/bpf/helpers.c                          |  19 +-
 kernel/bpf/verifier.c                         |   7 +
 .../selftests/test_parallel_bitmap.bpf.c      |  10 +
 .../selftests/bpf/prog_tests/may_goto_far.c   |  24 +-
 .../selftests/bpf/prog_tests/timed_may_goto.c | 195 ++++
 .../testing/selftests/bpf/progs/arena_htab.c  |   2 -
 .../selftests/bpf/progs/timed_may_goto.c      | 898 ++++++++++++++++++
 .../selftests/bpf/progs/timed_may_goto_ext.c  |  23 +
 .../selftests/bpf/progs/timed_may_goto_user.c | 311 ++++++
 .../bpf/progs/verifier_bpf_fastcall.c         |  72 +-
 .../bpf/progs/verifier_iterating_callbacks.c  |   6 +-
 .../selftests/bpf/progs/verifier_may_goto_1.c |  32 +-
 25 files changed, 1734 insertions(+), 149 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/timed_may_goto.c
 create mode 100644 tools/testing/selftests/bpf/progs/timed_may_goto.c
 create mode 100644 tools/testing/selftests/bpf/progs/timed_may_goto_ext.c
 create mode 100644 tools/testing/selftests/bpf/progs/timed_may_goto_user.c


base-commit: d89e1d186ec9271bf78e62771779e9fc03bf0fc3
-- 
2.55.0

[PATCH bpf v2 1/9] bpf: Emit timed may_goto for JITed progs only

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

The timed form of may_goto calls arch_bpf_timed_may_goto(). This function
takes its argument and returns its result in BPF_REG_AX, in a register of
the cpu. Only JITed code can call it.

The verifier emits the timed form when the arch has a JIT that supports it.
It does not look at the prog. With CONFIG_BPF_JIT_ALWAYS_ON=n the
interpreter can run such a prog: the JIT is off, or it fails. The
interpreter calls the function like a helper. The function takes what the C
code left in that register for a pointer, and bpf_check_timed_may_goto()
reads and writes through it.

Emit the timed form only when the prog asks for a JIT, and make the JIT
mandatory for such a prog. All other progs get the form that counts down
from BPF_MAX_LOOPS.

One test of verifier_may_goto_1 shows the insns of the timed form. Load it
only when progs are JITed.

Fixes: e723608bf428 ("bpf: Add verifier support for timed may_goto")
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 kernel/bpf/fixups.c                                     | 9 ++++++---
 tools/testing/selftests/bpf/progs/verifier_may_goto_1.c | 1 +
 2 files changed, 7 insertions(+), 3 deletions(-)

diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c
index 41bc37e205e0..bb6b57f5e144 100644
--- a/kernel/bpf/fixups.c
+++ b/kernel/bpf/fixups.c
@@ -1823,6 +1823,8 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 	struct bpf_subprog_info *subprogs = env->subprog_info;
 	u16 stack_depth = subprogs[cur_subprog].stack_depth;
 	u16 stack_depth_extra = 0;
+	/* arch_bpf_timed_may_goto() takes and returns AX in a cpu register: for JITs only */
+	bool timed_may_goto = prog->jit_requested && bpf_jit_supports_timed_may_goto();
 
 	if (env->seen_exception && !env->exception_callback_subprog) {
 		struct bpf_insn *patch = insn_buf;
@@ -2078,7 +2080,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			goto next_insn;
 		}
 
-		if (bpf_is_may_goto_insn(insn) && bpf_jit_supports_timed_may_goto()) {
+		if (bpf_is_may_goto_insn(insn) && timed_may_goto) {
 			int stack_off_cnt = -stack_depth - 16;
 			/*
 			 * AX is used as an argument to pass in stack_off_cnt
@@ -2108,6 +2110,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			 * after subtraction, rinse and repeat.
 			 */
 			stack_depth_extra = 16;
+			prog->jit_required = 1;
 			cnt = may_goto_expand(insn_buf, insn->off, stack_off_cnt,
 					      tail, ARRAY_SIZE(tail));
 
@@ -2730,7 +2733,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 
 	env->prog->aux->stack_depth = subprogs[0].stack_depth;
 	for (i = 0; i < env->subprog_cnt; i++) {
-		int delta = bpf_jit_supports_timed_may_goto() ? 2 : 1;
+		int delta = timed_may_goto ? 2 : 1;
 		int subprog_start = subprogs[i].start;
 		int stack_slots = subprogs[i].stack_extra / 8;
 		int slots = delta, cnt = 0;
@@ -2744,7 +2747,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 		}
 
 		stack_depth = subprogs[i].stack_depth;
-		if (bpf_jit_supports_timed_may_goto()) {
+		if (timed_may_goto) {
 			insn_buf[cnt++] = BPF_ST_MEM(BPF_DW, BPF_REG_FP, -stack_depth,
 						     BPF_MAX_TIMED_LOOPS);
 			insn_buf[cnt++] = BPF_ST_MEM(BPF_DW, BPF_REG_FP, -stack_depth + 8, 0);
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 faf9eec0a63e..c19b0522df61 100644
--- a/tools/testing/selftests/bpf/progs/verifier_may_goto_1.c
+++ b/tools/testing/selftests/bpf/progs/verifier_may_goto_1.c
@@ -82,6 +82,7 @@ __naked void may_goto_batch_1(void)
 
 SEC("raw_tp")
 __description("may_goto batch with offsets 2/0")
+__load_if_JITed()
 __arch_x86_64
 __arch_s390x
 __arch_arm64
-- 
2.55.0

[PATCH bpf v2 2/9] selftests/bpf: Don't cast a pointer to .bss in arena_htab_asm

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

arena_htab_asm is arena_htab.c with BPF_ARENA_FORCE_ASM. In this variant
__arena has no address space, so arr1 is in .bss, and cast_kern() is a real
insn. cast_kern(arr) turns the pointer to .bss into an offset in the arena.
Each of the 100000 stores to arr[i] faults, and the fault handler of the
arena skips it.

Remove the cast. In the other variant it is a nop. The prog takes 67 ms in
place of 950 ms on a kernel with lockdep.

With one time slice for all may_goto of a prog, may_goto stops the loops of
the old prog after 250 ms. The test does not see that, because it looks at
the first keys only.

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

diff --git a/tools/testing/selftests/bpf/progs/arena_htab.c b/tools/testing/selftests/bpf/progs/arena_htab.c
index 81eaa94afeb0..80cc14bb1c0f 100644
--- a/tools/testing/selftests/bpf/progs/arena_htab.c
+++ b/tools/testing/selftests/bpf/progs/arena_htab.c
@@ -34,8 +34,6 @@ int arena_htab_llvm(void *ctx)
 	cast_kern(htab);
 	htab_init(htab);
 
-	cast_kern(arr);
-
 	/* first run. No old elems in the table */
 	for (i = zero; i < 100000 && can_loop; i++) {
 		htab_update_elem(htab, i, i);
-- 
2.55.0

[PATCH bpf v2 3/9] selftests/bpf: Give the first loop of cond_break5 an end

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

The main prog of cond_break5 spins until may_goto stops the loop. Then it
calls a subprog and expects that the loop of the subprog makes iterations.
This is true only while each stack frame has a time slice of its own.

Stop the first loop after 100 iterations. The test still makes sure that
may_goto works in the main prog and in a subprog of one prog.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 .../selftests/bpf/progs/verifier_iterating_callbacks.c      | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

diff --git a/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
index 1fbcc5228306..4dd98acc6436 100644
--- a/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
+++ b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
@@ -553,7 +553,11 @@ int cond_break5(const void *ctx)
 {
 	int cnt1 = zero, cnt2;
 
-	for (;;) {
+	/*
+	 * There is one time slice for all may_goto of the prog. When it's used up a function that
+	 * is called after that makes no iteration. So this loop has an end.
+	 */
+	for (; cnt1 < 100;) {
 		cond_break;
 		cnt1++;
 	}
-- 
2.55.0

[PATCH bpf v2 4/9] selftests/bpf: End the loop of parallel_test_bitmap after 50 ms

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

The two progs of parallel_test_bitmap change bits of the same words in a
loop of 10000000 iterations with can_loop. The loop goes on until may_goto
stops it. The functions that it calls retry a cmpxchg that fails:

  do {
          ...
          actual = cmpxchg(&bmp->bits[idx], old, new);
          if (actual == old)
                  return true;
  } while (can_loop);
  return false;

The retry is always possible only while each stack frame has a time slice
of its own. With one time slice for all may_goto of a prog, a function that
is called after the time is up makes no iteration. The bit does not change,
and the test fails with -EINVAL, in 53 of 900 runs.

Leave the loop after 50 ms.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 .../bpf/libarena/selftests/test_parallel_bitmap.bpf.c  | 10 ++++++++++
 1 file changed, 10 insertions(+)

diff --git a/tools/testing/selftests/bpf/libarena/selftests/test_parallel_bitmap.bpf.c b/tools/testing/selftests/bpf/libarena/selftests/test_parallel_bitmap.bpf.c
index ea1fac95b461..017add229bef 100644
--- a/tools/testing/selftests/bpf/libarena/selftests/test_parallel_bitmap.bpf.c
+++ b/tools/testing/selftests/bpf/libarena/selftests/test_parallel_bitmap.bpf.c
@@ -11,6 +11,7 @@
 #define TEST_BITMAP_BITS	(2 * BITS_PER_LONG_LONG)
 #define TEST_BITMAP_SYNC_SPINS	BPF_MAX_LOOPS
 #define TEST_BITMAP_ITERS	10 * 1000 * 1000
+#define TEST_BITMAP_NSEC	(50 * 1000 * 1000)
 
 static struct arena_bitmap __arena *bitmap;
 static volatile u64 started;
@@ -129,6 +130,7 @@ static int bitmap_test_common_single(int parity)
 
 static int bitmap_test_common(int parity)
 {
+	u64 start;
 	int ret;
 	u32 i;
 
@@ -138,6 +140,7 @@ static int bitmap_test_common(int parity)
 	if (ret)
 		return ret;
 
+	start = bpf_ktime_get_ns();
 	for (i = zero; i < TEST_BITMAP_ITERS && can_loop; i++) {
 		ret = bitmap_test_common_single(parity);
 		if (ret)
@@ -147,6 +150,13 @@ static int bitmap_test_common(int parity)
 			break;
 
 		bitmap_test_reset_single(parity);
+
+		/*
+		 * Stop before the time slice of may_goto is used up. After that the
+		 * bmp_*() functions can't retry a cmpxchg that fails.
+		 */
+		if (bpf_ktime_get_ns() - start > TEST_BITMAP_NSEC)
+			break;
 	}
 
 	return 0;
-- 
2.55.0

[PATCH bpf v2 5/9] s390/bpf: Support internal-only MOV instruction to resolve per-CPU addrs

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

The verifier emits BPF_MOV64_PERCPU_REG to turn the address of a per-cpu
variable into the address of the copy of this cpu. s390 keeps the per-cpu
offset of the cpu in the lowcore. Add it to the register with one insn, the
way the JIT reads cpu_nr and current_task for the helpers that it inlines.

With bpf_jit_supports_percpu_insn() the verifier inlines the lookup in
per-cpu array and per-cpu hash maps, and resolves the address of a value in
a per-cpu array. Patch 7 needs the insn for may_goto.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 arch/s390/net/bpf_jit_comp.c | 16 ++++++++++++++++
 1 file changed, 16 insertions(+)

diff --git a/arch/s390/net/bpf_jit_comp.c b/arch/s390/net/bpf_jit_comp.c
index 56ec49894dda..ec32e10be24b 100644
--- a/arch/s390/net/bpf_jit_comp.c
+++ b/arch/s390/net/bpf_jit_comp.c
@@ -1005,6 +1005,17 @@ static noinline int bpf_jit_insn(struct bpf_jit *jit, struct bpf_prog *fp,
 					(jit->prg - patch_brc) >> 1;
 			break;
 		}
+		if (insn_is_mov_percpu_addr(insn)) {
+			const u64 *percpu_offset = &get_lowcore()->percpu_offset;
+
+			if (dst_reg != src_reg)
+				/* lgr %dst,%src */
+				EMIT4(0xb9040000, dst_reg, src_reg);
+			/* ag %dst,percpu_offset */
+			EMIT6_DISP_LH(0xe3000000, 0x0008, dst_reg, REG_0, REG_0,
+				      (unsigned long)percpu_offset);
+			break;
+		}
 		switch (insn->off) {
 		case 0: /* DST = SRC */
 			/* lgr %dst,%src */
@@ -3116,6 +3127,11 @@ bool bpf_jit_supports_timed_may_goto(void)
 	return true;
 }
 
+bool bpf_jit_supports_percpu_insn(void)
+{
+	return true;
+}
+
 bool bpf_jit_inlines_helper_call(s32 imm)
 {
 	switch (imm) {
-- 
2.55.0

[PATCH bpf v2 6/9] bpf: Pass a pointer to arch_bpf_timed_may_goto()

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

arch_bpf_timed_may_goto() gets the offset of count and timestamp in the
stack frame in BPF_REG_AX. Arch code adds the frame pointer to it, and
calls bpf_check_timed_may_goto() with the result. On arm64, riscv,
loongarch, powerpc and s390 the asm function does it. On x86-64 the JIT
does it, because the frame pointer is in another register when the prog has
a private stack.

The next patch moves count and timestamp out of the stack frame. So pass
the pointer in BPF_REG_AX, and let the verifier emit the addition:

  before                           after

  r12 = -16                        r12 = r10
  call arch_bpf_timed_may_goto     r12 += -16
                                   call arch_bpf_timed_may_goto

The JITs know which register r10 is. The asm functions have a move in place
of the addition, and the special case in the x86-64 JIT goes away.

These insns run when the count is used up: in each 65535th iteration. The
cost of an iteration does not change.

Three tests have the insns of may_goto in them. Update them.

Tested on x86-64, and on arm64 and s390 in QEMU. riscv, loongarch and
powerpc are compile tested only.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 arch/arm64/net/bpf_timed_may_goto.S           | 12 ++------
 arch/loongarch/net/bpf_timed_may_goto.S       | 10 ++-----
 arch/powerpc/net/bpf_timed_may_goto.S         |  9 ++----
 arch/riscv/net/bpf_timed_may_goto.S           | 10 +++----
 arch/s390/net/bpf_jit_comp.c                  |  6 ++--
 arch/s390/net/bpf_timed_may_goto.S            |  8 ++---
 arch/x86/net/bpf_jit_comp.c                   | 12 --------
 arch/x86/net/bpf_timed_may_goto.S             |  5 +---
 kernel/bpf/fixups.c                           |  9 +++---
 .../bpf/progs/verifier_bpf_fastcall.c         | 30 ++++++++++---------
 .../selftests/bpf/progs/verifier_may_goto_1.c | 17 ++++++-----
 11 files changed, 51 insertions(+), 77 deletions(-)

diff --git a/arch/arm64/net/bpf_timed_may_goto.S b/arch/arm64/net/bpf_timed_may_goto.S
index 1b4a4f91ffc9..f8732b13bb1e 100644
--- a/arch/arm64/net/bpf_timed_may_goto.S
+++ b/arch/arm64/net/bpf_timed_may_goto.S
@@ -17,16 +17,10 @@ SYM_FUNC_START(arch_bpf_timed_may_goto)
 	str	x7, [sp, #80]
 
 	/*
-	 * Stack depth was passed in BPF_REG_AX (x9), add it to the BPF_FP
-	 * (x25) to get the pointer to count and timestamp and pass it as the
-	 * first argument in x0.
-	 *
-	 * Before generating the call to arch_bpf_timed_may_goto, the verifier
-	 * generates a load instruction using FP, i.e. REG_AX = *(u64 *)(FP -
-	 * stack_off_cnt), so BPF_REG_FP (x25) is always set up by the arm64
-	 * jit in this case.
+	 * The pointer to count and timestamp was passed in BPF_REG_AX (x9),
+	 * pass it as the first argument in x0.
 	 */
-	add	x0, x9, x25
+	mov	x0, x9
 	bl	bpf_check_timed_may_goto
 	/* BPF_REG_AX(x9) will be stored into count, so move return value to it. */
 	mov	x9, x0
diff --git a/arch/loongarch/net/bpf_timed_may_goto.S b/arch/loongarch/net/bpf_timed_may_goto.S
index fa128acdb108..4aaca029404b 100644
--- a/arch/loongarch/net/bpf_timed_may_goto.S
+++ b/arch/loongarch/net/bpf_timed_may_goto.S
@@ -22,14 +22,10 @@ SYM_FUNC_START(arch_bpf_timed_may_goto)
 	st.d		a4, sp, 48
 
 	/*
-	 * BPF_REG_AX (t0) holds the offset passed in by the verifier;
-	 * add it to BPF_REG_FP (s4) to get the pointer to the count and
-	 * timestamp, then pass it as the first argument in a0.
-	 *
-	 * The verifier emits a load using FP right before this call,
-	 * so BPF_REG_FP (s4) is always set up by the JIT in this case.
+	 * BPF_REG_AX (t0) holds the pointer to the count and timestamp;
+	 * pass it as the first argument in a0.
 	 */
-	add.d		a0, t0, s4
+	move		a0, t0
 	bl		bpf_check_timed_may_goto
 	/* BPF_REG_AX (t0) will be stored into count, so move the return value to it. */
 	move		t0, a0
diff --git a/arch/powerpc/net/bpf_timed_may_goto.S b/arch/powerpc/net/bpf_timed_may_goto.S
index 84ecf6fa7f5d..b8ae9885eb31 100644
--- a/arch/powerpc/net/bpf_timed_may_goto.S
+++ b/arch/powerpc/net/bpf_timed_may_goto.S
@@ -8,7 +8,7 @@
  * arch_bpf_timed_may_goto() trampoline for powerpc64
  *
  * Custom BPF convention (verifier/JIT):
- *	- input:  stack offset in BPF_REG_AX (r12)
+ *	- input:  pointer to count and timestamp in BPF_REG_AX (r12)
  *	- output: updated count in BPF_REG_AX (r12)
  *
  * Call bpf_check_timed_may_goto(ptr) with normal powerpc64 ABI:
@@ -31,11 +31,8 @@ SYM_FUNC_START(arch_bpf_timed_may_goto)
 	std     r7, 64(r1)
 	std     r8, 72(r1)
 
-	/*
-	 * r3 = BPF_REG_FP + BPF_REG_AX
-	 * BPF_REG_FP is r31; BPF_REG_AX is r12 (stack offset in bytes).
-	 */
-	add     r3, r31, r12
+	/* r3 = BPF_REG_AX (r12) */
+	mr      r3, r12
 	bl      CFUNC(bpf_check_timed_may_goto)
 
 	/* Put return value back into AX */
diff --git a/arch/riscv/net/bpf_timed_may_goto.S b/arch/riscv/net/bpf_timed_may_goto.S
index 6ec37f634aff..2ce1c89c913e 100644
--- a/arch/riscv/net/bpf_timed_may_goto.S
+++ b/arch/riscv/net/bpf_timed_may_goto.S
@@ -6,13 +6,11 @@
 
 /*
  * Trampoline for the BPF timed may_goto loop bound. Custom calling convention:
- *	- input:  stack offset in BPF_REG_AX (t0)
+ *	- input:  pointer to count and timestamp in BPF_REG_AX (t0)
  *	- output: updated count in BPF_REG_AX (t0)
  *
- * Calls bpf_check_timed_may_goto(ptr) with the standard RISC-V ABI, where
- * ptr = BPF_REG_FP (s5) + BPF_REG_AX (t0). BPF R0-R5 (t6, a0-a4) and stack
- * arguments 6-8 (a5-a7) are saved across the call; BPF_REG_FP (s5) is
- * callee-saved and needs no saving.
+ * Calls bpf_check_timed_may_goto(ptr) with the standard RISC-V ABI. BPF R0-R5
+ * (t6, a0-a4) and stack arguments 6-8 (a5-a7) are saved across the call.
  */
 
 SYM_FUNC_START(arch_bpf_timed_may_goto)
@@ -33,7 +31,7 @@ SYM_FUNC_START(arch_bpf_timed_may_goto)
 	REG_S	a6, 7*SZREG(sp)
 	REG_S	a7, 8*SZREG(sp)
 
-	add	a0, t0, s5
+	mv	a0, t0
 	call	bpf_check_timed_may_goto
 	mv	t0, a0
 
diff --git a/arch/s390/net/bpf_jit_comp.c b/arch/s390/net/bpf_jit_comp.c
index ec32e10be24b..15029cedc50b 100644
--- a/arch/s390/net/bpf_jit_comp.c
+++ b/arch/s390/net/bpf_jit_comp.c
@@ -1877,9 +1877,9 @@ static noinline int bpf_jit_insn(struct bpf_jit *jit, struct bpf_prog *fp,
 		if ((void *)func == arch_bpf_timed_may_goto) {
 			/*
 			 * arch_bpf_timed_may_goto() has a special ABI: the
-			 * parameters are in BPF_REG_AX and BPF_REG_10; the
-			 * return value is in BPF_REG_AX; and all GPRs except
-			 * REG_W0, REG_W1, and BPF_REG_AX are callee-saved.
+			 * parameter is in BPF_REG_AX; the return value is in
+			 * BPF_REG_AX; and all GPRs except REG_W0, REG_W1, and
+			 * BPF_REG_AX are callee-saved.
 			 */
 
 			/* brasl %r0,func */
diff --git a/arch/s390/net/bpf_timed_may_goto.S b/arch/s390/net/bpf_timed_may_goto.S
index 06f567a460d7..05f532f8c639 100644
--- a/arch/s390/net/bpf_timed_may_goto.S
+++ b/arch/s390/net/bpf_timed_may_goto.S
@@ -21,9 +21,9 @@
 
 SYM_FUNC_START(arch_bpf_timed_may_goto)
 	/*
-	 * This function has a special ABI: the parameters are in %r12 and
-	 * %r13; the return value is in %r12; all GPRs except %r0, %r1, and
-	 * %r12 are callee-saved; and the return address is in %r0.
+	 * This function has a special ABI: the parameter is in %r12; the
+	 * return value is in %r12; all GPRs except %r0, %r1, and %r12 are
+	 * callee-saved; and the return address is in %r0.
 	 */
 	stmg %r2,%r5,FRAME_OFF+R2_OFF(%r15)
 	stg %r14,FRAME_OFF+R14_OFF(%r15)
@@ -33,7 +33,7 @@ SYM_FUNC_START(arch_bpf_timed_may_goto)
 	lay %r15,-FRAME_SIZE(%r15)
 	stg %r1,__SF_BACKCHAIN(%r15)
 
-	lay %r2,0(%r12,%r13)
+	lgr %r2,%r12
 	brasl %r14,bpf_check_timed_may_goto
 	lgr %r12,%r2
 
diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
index d90b6d238b3a..38871963e676 100644
--- a/arch/x86/net/bpf_jit_comp.c
+++ b/arch/x86/net/bpf_jit_comp.c
@@ -3436,18 +3436,6 @@ 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 dd2dde89836b..da42de7cca98 100644
--- a/arch/x86/net/bpf_timed_may_goto.S
+++ b/arch/x86/net/bpf_timed_may_goto.S
@@ -25,10 +25,7 @@ SYM_FUNC_START(arch_bpf_timed_may_goto)
 	/* Save stack argument 6. */
 	pushq %r9
 
-	/*
-	 * r10 has the pointer to count and timestamp. JIT added the frame
-	 * pointer to the offset. Pass it as first argument.
-	 */
+	/* r10 has the pointer to count and timestamp. Pass it as first argument. */
 	movq %r10, %rdi
 
 	/* Emit call depth accounting for call below. */
diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c
index bb6b57f5e144..5cbab55d84be 100644
--- a/kernel/bpf/fixups.c
+++ b/kernel/bpf/fixups.c
@@ -2083,14 +2083,15 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 		if (bpf_is_may_goto_insn(insn) && 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
+			 * AX is used as an argument to pass in the pointer to
+			 * count and timestamp, 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_JMP_IMM(BPF_JNE, BPF_REG_AX, 0, 3),
+				BPF_MOV64_REG(BPF_REG_AX, BPF_REG_10),
+				BPF_ALU64_IMM(BPF_ADD, 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),
 			};
diff --git a/tools/testing/selftests/bpf/progs/verifier_bpf_fastcall.c b/tools/testing/selftests/bpf/progs/verifier_bpf_fastcall.c
index e0c389102db9..faedf36eef2a 100644
--- a/tools/testing/selftests/bpf/progs/verifier_bpf_fastcall.c
+++ b/tools/testing/selftests/bpf/progs/verifier_bpf_fastcall.c
@@ -914,15 +914,16 @@ __xlated("4: r0 = &(void __percpu *)(r0)")
 __xlated("...")
 /* may_goto expansion starts */
 __xlated("6: r12 = *(u64 *)(r10 -24)")
-__xlated("7: if r12 == 0x0 goto pc+6")
+__xlated("7: if r12 == 0x0 goto pc+7")
 __xlated("8: r12 -= 1")
-__xlated("9: if r12 != 0x0 goto pc+2")
-__xlated("10: r12 = -24")
-__xlated("11: call unknown")
-__xlated("12: *(u64 *)(r10 -24) = r12")
+__xlated("9: if r12 != 0x0 goto pc+3")
+__xlated("10: r12 = r10")
+__xlated("11: r12 += -24")
+__xlated("12: call unknown")
+__xlated("13: *(u64 *)(r10 -24) = r12")
 /* may_goto expansion ends */
-__xlated("13: *(u64 *)(r10 -8) = r1")
-__xlated("14: exit")
+__xlated("14: *(u64 *)(r10 -8) = r1")
+__xlated("15: exit")
 __success
 __naked void may_goto_interaction_x86_64(void)
 {
@@ -955,15 +956,16 @@ __xlated("2: r1 = 1")
 __xlated("3: call bpf_get_smp_processor_id")
 /* may_goto expansion starts */
 __xlated("4: r12 = *(u64 *)(r10 -24)")
-__xlated("5: if r12 == 0x0 goto pc+6")
+__xlated("5: if r12 == 0x0 goto pc+7")
 __xlated("6: r12 -= 1")
-__xlated("7: if r12 != 0x0 goto pc+2")
-__xlated("8: r12 = -24")
-__xlated("9: call unknown")
-__xlated("10: *(u64 *)(r10 -24) = r12")
+__xlated("7: if r12 != 0x0 goto pc+3")
+__xlated("8: r12 = r10")
+__xlated("9: r12 += -24")
+__xlated("10: call unknown")
+__xlated("11: *(u64 *)(r10 -24) = r12")
 /* may_goto expansion ends */
-__xlated("11: *(u64 *)(r10 -8) = r1")
-__xlated("12: exit")
+__xlated("12: *(u64 *)(r10 -8) = r1")
+__xlated("13: exit")
 __success
 __naked void may_goto_interaction(void)
 {
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 c19b0522df61..2de1ae144ac9 100644
--- a/tools/testing/selftests/bpf/progs/verifier_may_goto_1.c
+++ b/tools/testing/selftests/bpf/progs/verifier_may_goto_1.c
@@ -91,15 +91,16 @@ __arch_loongarch
 __xlated("0: *(u64 *)(r10 -16) = 65535")
 __xlated("1: *(u64 *)(r10 -8) = 0")
 __xlated("2: r12 = *(u64 *)(r10 -16)")
-__xlated("3: if r12 == 0x0 goto pc+6")
+__xlated("3: if r12 == 0x0 goto pc+7")
 __xlated("4: r12 -= 1")
-__xlated("5: if r12 != 0x0 goto pc+2")
-__xlated("6: r12 = -16")
-__xlated("7: call unknown")
-__xlated("8: *(u64 *)(r10 -16) = r12")
-__xlated("9: r0 = 1")
-__xlated("10: r0 = 2")
-__xlated("11: exit")
+__xlated("5: if r12 != 0x0 goto pc+3")
+__xlated("6: r12 = r10")
+__xlated("7: r12 += -16")
+__xlated("8: call unknown")
+__xlated("9: *(u64 *)(r10 -16) = r12")
+__xlated("10: r0 = 1")
+__xlated("11: r0 = 2")
+__xlated("12: exit")
 __success
 __naked void may_goto_batch_2(void)
 {
-- 
2.55.0

[PATCH bpf v2 7/9] bpf: One may_goto time slice per prog invocation

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

The count and the timestamp of may_goto are in the stack frame. So the
limit of 250 ms is for one call of a subprog, not for one invocation of the
prog, and loops that nest across calls multiply it. These 9 insns cause a
soft lockup:

  main:                 sub:
  1: call sub           1: may_goto 2f
     may_goto 2f           goto 1b
     goto 1b            2: r0 = 0
  2: r0 = 1                exit
     exit

Use one count and one timestamp for all may_goto of a prog, in per-cpu
memory of the prog. The main prog sets them in its first insns. When the
time is up each loop ends at its next may_goto, in any function.

  rX = address of the count
  rX = &(void __percpu *)(rX)
  r12 = *(u64 *)(rX +0)
  if r12 == 0x0 goto target
  r12 -= 1
  if r12 != 0x0 goto pc+2
  r12 = rX
  call arch_bpf_timed_may_goto
  *(u64 *)(rX +0) = r12

rX is a register that is dead at the may_goto. When all ten are live R0 is
saved in the stack.

An async callback can interrupt the prog on the same cpu. So its caller
sets count and timestamp, and puts the old values back at the end. A second
invocation of the prog on the same cpu gives more time to the first one.

  x86-64 (Zen 5), nsec                             before  after
  iteration, empty loop                             0.36    0.44
  iteration, the body takes 4 cycles                0.89    0.89
  call of a subprog and 1 iteration                 1.21    1.16

The 56 progs of scx with may_goto get 1.7% more JITed code and use 25% less
stack.

Fixes: e723608bf428 ("bpf: Add verifier support for timed may_goto")
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 include/linux/bpf.h                           |   2 +
 include/linux/filter.h                        |   8 ++
 kernel/bpf/core.c                             |  33 +++++
 kernel/bpf/fixups.c                           | 125 ++++++++++++------
 kernel/bpf/helpers.c                          |  19 ++-
 .../bpf/progs/verifier_bpf_fastcall.c         |  74 ++++++-----
 .../selftests/bpf/progs/verifier_may_goto_1.c |  32 +++--
 7 files changed, 202 insertions(+), 91 deletions(-)

diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index ff0436781293..01d5c79b487e 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -1916,6 +1916,8 @@ struct bpf_prog_aux {
 	const char *attach_func_name;
 	struct bpf_prog **func;
 	struct bpf_prog_aux *main_prog_aux;
+	/* main prog: there when the prog has timed may_goto */
+	struct bpf_timed_may_goto __percpu *timed_may_goto;
 	void *jit_data; /* JIT specific data. arch dependent */
 	struct bpf_jit_poke_descriptor *poke_tab;
 	struct bpf_kfunc_desc_tab *kfunc_tab;
diff --git a/include/linux/filter.h b/include/linux/filter.h
index 98254742ae37..4f0cd67caccb 100644
--- a/include/linux/filter.h
+++ b/include/linux/filter.h
@@ -758,9 +758,15 @@ struct bpf_prog_stats {
 	struct u64_stats_sync syncp;
 } __aligned(2 * sizeof(u64));
 
+/*
+ * Per-cpu memory of a prog. All may_goto of one invocation of the prog use it. An invocation is
+ * one call from the kernel into the main prog, with the subprogs and sync callbacks it reaches.
+ */
 struct bpf_timed_may_goto {
 	u64 count;
 	u64 timestamp;
+	/* the async callback that has set count and timestamp, see bpf_timed_may_goto_save() */
+	void *owner;
 };
 
 struct sk_filter {
@@ -1328,6 +1334,8 @@ u64 bpf_arch_uaddress_limit(void);
 void arch_bpf_stack_walk(bool (*consume_fn)(void *cookie, u64 ip, u64 sp, u64 bp), void *cookie);
 u64 arch_bpf_timed_may_goto(void);
 u64 bpf_check_timed_may_goto(struct bpf_timed_may_goto *);
+void bpf_timed_may_goto_save(const struct bpf_prog *prog, struct bpf_timed_may_goto *saved);
+void bpf_timed_may_goto_restore(const struct bpf_prog *prog, struct bpf_timed_may_goto *saved);
 bool bpf_helper_changes_pkt_data(enum bpf_func_id func_id);
 
 static inline bool bpf_dump_raw_ok(const struct cred *cred)
diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index 7cf37690d41f..3b02aafba4c5 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -292,6 +292,7 @@ void __bpf_prog_free(struct bpf_prog *fp)
 		mutex_destroy(&fp->aux->used_maps_mutex);
 		mutex_destroy(&fp->aux->dst_mutex);
 		kfree(fp->aux->poke_tab);
+		free_percpu(fp->aux->timed_may_goto);
 		kfree(fp->aux);
 	}
 	free_percpu(fp->stats);
@@ -3643,6 +3644,38 @@ u64 bpf_check_timed_may_goto(struct bpf_timed_may_goto *p)
 	return BPF_MAX_TIMED_LOOPS;
 }
 
+/*
+ * The main prog sets count and timestamp in its first insns. A call of an async callback is an
+ * invocation of its own too, but it can interrupt an invocation of the prog on this cpu, or go on
+ * next to one that is preempted. So its caller sets count and timestamp, and puts the old ones
+ * back at the end. Not when another invocation has set them in the meantime: they are for that
+ * one now.
+ * The caller has disabled migration.
+ */
+void bpf_timed_may_goto_save(const struct bpf_prog *prog, struct bpf_timed_may_goto *saved)
+{
+	struct bpf_timed_may_goto *cur;
+
+	if (!prog->aux->timed_may_goto)
+		return;
+	cur = this_cpu_ptr(prog->aux->timed_may_goto);
+	*saved = *cur;
+	cur->count = BPF_MAX_TIMED_LOOPS;
+	cur->timestamp = 0;
+	cur->owner = saved;
+}
+
+void bpf_timed_may_goto_restore(const struct bpf_prog *prog, struct bpf_timed_may_goto *saved)
+{
+	struct bpf_timed_may_goto *cur;
+
+	if (!prog->aux->timed_may_goto)
+		return;
+	cur = this_cpu_ptr(prog->aux->timed_may_goto);
+	if (cur->owner == saved)
+		*cur = *saved;
+}
+
 /* for configs without MMU or 32-bit */
 __weak const struct bpf_map_ops arena_map_ops;
 __weak u64 bpf_arena_get_user_vm_start(struct bpf_arena *arena)
diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c
index 5cbab55d84be..66b9d1d9e961 100644
--- a/kernel/bpf/fixups.c
+++ b/kernel/bpf/fixups.c
@@ -1803,6 +1803,50 @@ static int may_goto_expand(struct bpf_insn *insn_buf, int off, int stack_off,
 	return cnt + tail_cnt;
 }
 
+/*
+ * Timed may_goto. All may_goto of a prog use one count and one timestamp: per-cpu memory of the
+ * prog, set in the first insns of the main prog, and by the callers of async callbacks.
+ * @reg holds the address. It is a register that is dead at the may_goto, or R0 that is saved at
+ * @save_off in the stack.
+ */
+static int may_goto_expand_timed(struct bpf_insn *insn_buf, int off,
+				 struct bpf_timed_may_goto __percpu *tmg, int reg, int save_off)
+{
+	struct bpf_insn ld_tmg[] = { BPF_LD_IMM64(reg, (__force unsigned long)tmg) };
+	int cnt = 0, jmp, tail_cnt = save_off ? 6 : 5;
+
+	if (save_off)
+		insn_buf[cnt++] = BPF_STX_MEM(BPF_DW, BPF_REG_10, reg, save_off);
+	insn_buf[cnt++] = ld_tmg[0];
+	insn_buf[cnt++] = ld_tmg[1];
+	insn_buf[cnt++] = BPF_MOV64_PERCPU_REG(reg, reg);
+	insn_buf[cnt++] = BPF_LDX_MEM(BPF_DW, BPF_REG_AX, reg, 0);
+	if (save_off) {
+		insn_buf[cnt++] = BPF_JMP_IMM(BPF_JNE, BPF_REG_AX, 0, 2);
+		insn_buf[cnt++] = BPF_LDX_MEM(BPF_DW, reg, BPF_REG_10, save_off);
+		jmp = cnt++;
+		insn_buf[jmp] = BPF_JMP32_A(off >= 0 ? off + tail_cnt : off - jmp);
+	} else {
+		jmp = cnt;
+		off = off >= 0 ? off + tail_cnt : off - jmp;
+		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);
+		}
+	}
+	insn_buf[cnt++] = BPF_ALU64_IMM(BPF_SUB, BPF_REG_AX, 1);
+	insn_buf[cnt++] = BPF_JMP_IMM(BPF_JNE, BPF_REG_AX, 0, 2);
+	/* AX is the argument and the return value */
+	insn_buf[cnt++] = BPF_MOV64_REG(BPF_REG_AX, reg);
+	insn_buf[cnt++] = BPF_EMIT_CALL(arch_bpf_timed_may_goto);
+	insn_buf[cnt++] = BPF_STX_MEM(BPF_DW, reg, BPF_REG_AX, 0);
+	if (save_off)
+		insn_buf[cnt++] = BPF_LDX_MEM(BPF_DW, reg, BPF_REG_10, save_off);
+	return cnt;
+}
+
 /* Do various post-verification rewrites in a single program pass.
  * These rewrites simplify JIT and interpreter implementations.
  */
@@ -1825,6 +1869,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 	u16 stack_depth_extra = 0;
 	/* arch_bpf_timed_may_goto() takes and returns AX in a cpu register: for JITs only */
 	bool timed_may_goto = prog->jit_requested && bpf_jit_supports_timed_may_goto();
+	struct bpf_timed_may_goto __percpu *tmg = NULL;
 
 	if (env->seen_exception && !env->exception_callback_subprog) {
 		struct bpf_insn *patch = insn_buf;
@@ -2081,39 +2126,27 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 		}
 
 		if (bpf_is_may_goto_insn(insn) && timed_may_goto) {
-			int stack_off_cnt = -stack_depth - 16;
-			/*
-			 * AX is used as an argument to pass in the pointer to
-			 * count and timestamp, 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, 3),
-				BPF_MOV64_REG(BPF_REG_AX, BPF_REG_10),
-				BPF_ALU64_IMM(BPF_ADD, 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
-			 * depth-8 stores the start timestamp of the loop.
-			 *
-			 * The starting value of count is BPF_MAX_TIMED_LOOPS
-			 * (0xffff).  Every iteration loads it and subs it by 1,
-			 * until the value becomes 0 in AX (thus, 1 in stack),
-			 * after which we call arch_bpf_timed_may_goto, which
-			 * either sets AX to 0xffff to keep looping, or to 0
-			 * upon timeout. AX is then stored into the stack. In
-			 * the next iteration, we either see 0 and break out, or
-			 * continue iterating until the next time value is 0
-			 * after subtraction, rinse and repeat.
-			 */
-			stack_depth_extra = 16;
+			u16 live = env->insn_aux_data[i + delta].live_regs_before;
+			int reg, save_off = 0;
+
+			/* a register that is dead here holds the address of the count */
+			for (reg = BPF_REG_0; reg <= BPF_REG_9; reg++)
+				if (!(live & BIT(reg)))
+					break;
+			if (reg > BPF_REG_9) {
+				reg = BPF_REG_0;
+				save_off = -stack_depth - 8;
+				stack_depth_extra = 8;
+			}
+			if (!tmg) {
+				tmg = alloc_percpu_gfp(struct bpf_timed_may_goto,
+						       GFP_KERNEL_ACCOUNT);
+				if (!tmg)
+					return -ENOMEM;
+				prog->aux->timed_may_goto = tmg;
+			}
 			prog->jit_required = 1;
-			cnt = may_goto_expand(insn_buf, insn->off, stack_off_cnt,
-					      tail, ARRAY_SIZE(tail));
+			cnt = may_goto_expand_timed(insn_buf, insn->off, tmg, reg, save_off);
 
 			new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
 			if (!new_prog)
@@ -2734,24 +2767,36 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 
 	env->prog->aux->stack_depth = subprogs[0].stack_depth;
 	for (i = 0; i < env->subprog_cnt; i++) {
-		int delta = timed_may_goto ? 2 : 1;
 		int subprog_start = subprogs[i].start;
 		int stack_slots = subprogs[i].stack_extra / 8;
-		int slots = delta, cnt = 0;
+		/* an invocation begins, see bpf_timed_may_goto_save() for async callbacks */
+		bool main_prog = tmg && !i;
+		int cnt = 0;
 
-		if (!stack_slots)
+		if (timed_may_goto ? !main_prog : !stack_slots)
 			continue;
-		/* We need two slots in case timed may_goto is supported. */
-		if (stack_slots > slots) {
+		if (stack_slots > 1) {
 			verifier_bug(env, "stack_slots supports may_goto only");
 			return -EFAULT;
 		}
 
 		stack_depth = subprogs[i].stack_depth;
 		if (timed_may_goto) {
-			insn_buf[cnt++] = BPF_ST_MEM(BPF_DW, BPF_REG_FP, -stack_depth,
+			struct bpf_insn ld_tmg[] = {
+				BPF_LD_IMM64(BPF_REG_0, (__force unsigned long)tmg)
+			};
+			int count_off = offsetof(struct bpf_timed_may_goto, count);
+			int timestamp_off = offsetof(struct bpf_timed_may_goto, timestamp);
+			int owner_off = offsetof(struct bpf_timed_may_goto, owner);
+
+			/* R0 has nothing at the entry */
+			insn_buf[cnt++] = ld_tmg[0];
+			insn_buf[cnt++] = ld_tmg[1];
+			insn_buf[cnt++] = BPF_MOV64_PERCPU_REG(BPF_REG_0, BPF_REG_0);
+			insn_buf[cnt++] = BPF_ST_MEM(BPF_DW, BPF_REG_0, count_off,
 						     BPF_MAX_TIMED_LOOPS);
-			insn_buf[cnt++] = BPF_ST_MEM(BPF_DW, BPF_REG_FP, -stack_depth + 8, 0);
+			insn_buf[cnt++] = BPF_ST_MEM(BPF_DW, BPF_REG_0, timestamp_off, 0);
+			insn_buf[cnt++] = BPF_ST_MEM(BPF_DW, BPF_REG_0, owner_off, 0);
 		} else {
 			/* Add ST insn to subprog prologue to init extra stack */
 			insn_buf[cnt++] = BPF_ST_MEM(BPF_DW, BPF_REG_FP, -stack_depth,
@@ -2778,7 +2823,7 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 		 * to insn after BPF_ST that inits may_goto count.
 		 * Adjustment will succeed because bpf_patch_insn_data() didn't fail.
 		 */
-		WARN_ON(adjust_jmp_off(env->prog, subprog_start, delta));
+		WARN_ON(adjust_jmp_off(env->prog, subprog_start, cnt - 1));
 	}
 
 	/* Since poke tab is now finalized, publish aux to tracker. */
diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c
index 58e357302850..2b75f7ba07a5 100644
--- a/kernel/bpf/helpers.c
+++ b/kernel/bpf/helpers.c
@@ -1222,6 +1222,8 @@ static enum hrtimer_restart bpf_timer_cb(struct hrtimer *hrtimer)
 {
 	struct bpf_hrtimer *t = container_of(hrtimer, struct bpf_hrtimer, timer);
 	struct bpf_map *map = READ_ONCE(t->cb.map);
+	struct bpf_prog *prog = READ_ONCE(t->cb.prog);
+	struct bpf_timed_may_goto saved;
 	void *value = t->cb.value;
 	bpf_callback_t callback_fn;
 	void *key;
@@ -1229,7 +1231,7 @@ static enum hrtimer_restart bpf_timer_cb(struct hrtimer *hrtimer)
 
 	BTF_TYPE_EMIT(struct bpf_timer);
 	callback_fn = rcu_dereference_check(t->cb.callback_fn, rcu_read_lock_bh_held());
-	if (!callback_fn || !map)
+	if (!callback_fn || !map || !prog)
 		goto out;
 
 	/* bpf_timer_cb() runs in hrtimer_run_softirq. It doesn't migrate and
@@ -1242,8 +1244,10 @@ static enum hrtimer_restart bpf_timer_cb(struct hrtimer *hrtimer)
 
 	key = map_key_from_value(map, value, &idx);
 
+	bpf_timed_may_goto_save(prog, &saved);
 	callback_fn((u64)(long)map, (u64)(long)key, (u64)(long)value, 0, 0);
 	/* The verifier checked that return value is zero. */
+	bpf_timed_may_goto_restore(prog, &saved);
 
 	this_cpu_write(hrtimer_running, NULL);
 out:
@@ -1254,6 +1258,8 @@ static void bpf_wq_work(struct work_struct *work)
 {
 	struct bpf_work *w = container_of(work, struct bpf_work, work);
 	struct bpf_async_cb *cb = &w->cb;
+	struct bpf_timed_may_goto saved;
+	struct bpf_prog *prog;
 	struct bpf_map *map;
 	bpf_callback_t callback_fn;
 	void *value = cb->value;
@@ -1267,14 +1273,17 @@ static void bpf_wq_work(struct work_struct *work)
 
 	map = READ_ONCE(cb->map);
 	callback_fn = READ_ONCE(cb->callback_fn);
-	if (!callback_fn || !map)
+	prog = READ_ONCE(cb->prog);
+	if (!callback_fn || !map || !prog)
 		goto out;
 
 	key = map_key_from_value(map, value, &idx);
 
 	migrate_disable();
 
+	bpf_timed_may_goto_save(prog, &saved);
 	callback_fn((u64)(long)map, (u64)(long)key, (u64)(long)value, 0, 0);
+	bpf_timed_may_goto_restore(prog, &saved);
 
 	migrate_enable();
 out:
@@ -4593,6 +4602,7 @@ static void bpf_task_work_cancel(struct bpf_task_work_ctx *ctx,
 static void bpf_task_work_callback(struct callback_head *cb)
 {
 	struct bpf_task_work_ctx *ctx = container_of(cb, struct bpf_task_work_ctx, work);
+	struct bpf_timed_may_goto saved;
 	enum bpf_task_work_state state;
 	u32 idx;
 	void *key;
@@ -4614,8 +4624,10 @@ static void bpf_task_work_callback(struct callback_head *cb)
 	key = (void *)map_key_from_value(ctx->map, ctx->map_val, &idx);
 
 	migrate_disable();
+	bpf_timed_may_goto_save(ctx->prog, &saved);
 	ctx->callback_fn((u64)(long)ctx->map, (u64)(long)key,
 			 (u64)(long)ctx->map_val, 0, 0);
+	bpf_timed_may_goto_restore(ctx->prog, &saved);
 	migrate_enable();
 
 	bpf_task_work_ctx_reset(ctx);
@@ -4855,6 +4867,7 @@ static void bpf_rcu_run_callback(struct rcu_head *rcu)
 	struct bpf_rcu_head_kern *rh = container_of(rcu, struct bpf_rcu_head_kern, rcu);
 	bpf_callback_t callback_fn = rh->callback_fn;
 	struct bpf_prog *prog = rh->prog;
+	struct bpf_timed_may_goto saved;
 	struct bpf_map *map = rh->map;
 	void *value, *key;
 	u32 idx;
@@ -4866,7 +4879,9 @@ static void bpf_rcu_run_callback(struct rcu_head *rcu)
 	smp_store_release(&rh->armed, 0);
 
 	rcu_read_lock_dont_migrate();
+	bpf_timed_may_goto_save(prog, &saved);
 	callback_fn((u64)(long)map, (u64)(long)key, (u64)(long)value, 0, 0);
+	bpf_timed_may_goto_restore(prog, &saved);
 	rcu_read_unlock_migrate();
 
 	bpf_prog_put(prog);
diff --git a/tools/testing/selftests/bpf/progs/verifier_bpf_fastcall.c b/tools/testing/selftests/bpf/progs/verifier_bpf_fastcall.c
index faedf36eef2a..d908298b9fc7 100644
--- a/tools/testing/selftests/bpf/progs/verifier_bpf_fastcall.c
+++ b/tools/testing/selftests/bpf/progs/verifier_bpf_fastcall.c
@@ -903,27 +903,28 @@ __naked void unconditional_jump_to_fill(void)
 SEC("raw_tp")
 __arch_x86_64
 __log_level(4)
-__msg("subprog 0 (may_goto_interaction_x86_64) main {{.*}} stack 24")
-/* may_goto counter at -24 */
-__xlated("0: *(u64 *)(r10 -24) =")
-/* may_goto timestamp at -16 */
-__xlated("1: *(u64 *)(r10 -16) =")
-__xlated("2: r1 = 1")
+__msg("subprog 0 (may_goto_interaction_x86_64) main {{.*}} stack 8")
+/* may_goto counter and timestamp */
+__xlated("0: r0 = ")
+__xlated("2: r0 = &(void __percpu *)(r0)")
 __xlated("...")
-__xlated("4: r0 = &(void __percpu *)(r0)")
+__xlated("6: r1 = 1")
+__xlated("...")
+__xlated("8: r0 = &(void __percpu *)(r0)")
 __xlated("...")
-/* may_goto expansion starts */
-__xlated("6: r12 = *(u64 *)(r10 -24)")
-__xlated("7: if r12 == 0x0 goto pc+7")
-__xlated("8: r12 -= 1")
-__xlated("9: if r12 != 0x0 goto pc+3")
-__xlated("10: r12 = r10")
-__xlated("11: r12 += -24")
-__xlated("12: call unknown")
-__xlated("13: *(u64 *)(r10 -24) = r12")
+/* may_goto expansion starts, r0 and r1 are live */
+__xlated("10: r2 = ")
+__xlated("12: r2 = &(void __percpu *)(r2)")
+__xlated("13: r12 = *(u64 *)(r2 +0)")
+__xlated("14: if r12 == 0x0 goto pc+6")
+__xlated("15: r12 -= 1")
+__xlated("16: if r12 != 0x0 goto pc+2")
+__xlated("17: r12 = r2")
+__xlated("18: call unknown")
+__xlated("19: *(u64 *)(r2 +0) = r12")
 /* may_goto expansion ends */
-__xlated("14: *(u64 *)(r10 -8) = r1")
-__xlated("15: exit")
+__xlated("20: *(u64 *)(r10 -8) = r1")
+__xlated("21: exit")
 __success
 __naked void may_goto_interaction_x86_64(void)
 {
@@ -947,25 +948,26 @@ __arch_arm64
 __arch_riscv64
 __arch_loongarch
 __log_level(4)
-__msg("subprog 0 (may_goto_interaction) main {{.*}} stack 24")
-/* may_goto counter at -24 */
-__xlated("0: *(u64 *)(r10 -24) =")
-/* may_goto timestamp at -16 */
-__xlated("1: *(u64 *)(r10 -16) =")
-__xlated("2: r1 = 1")
-__xlated("3: call bpf_get_smp_processor_id")
-/* may_goto expansion starts */
-__xlated("4: r12 = *(u64 *)(r10 -24)")
-__xlated("5: if r12 == 0x0 goto pc+7")
-__xlated("6: r12 -= 1")
-__xlated("7: if r12 != 0x0 goto pc+3")
-__xlated("8: r12 = r10")
-__xlated("9: r12 += -24")
-__xlated("10: call unknown")
-__xlated("11: *(u64 *)(r10 -24) = r12")
+__msg("subprog 0 (may_goto_interaction) main {{.*}} stack 8")
+/* may_goto counter and timestamp */
+__xlated("0: r0 = ")
+__xlated("2: r0 = &(void __percpu *)(r0)")
+__xlated("...")
+__xlated("6: r1 = 1")
+__xlated("7: call bpf_get_smp_processor_id")
+/* may_goto expansion starts, r0 and r1 are live */
+__xlated("8: r2 = ")
+__xlated("10: r2 = &(void __percpu *)(r2)")
+__xlated("11: r12 = *(u64 *)(r2 +0)")
+__xlated("12: if r12 == 0x0 goto pc+6")
+__xlated("13: r12 -= 1")
+__xlated("14: if r12 != 0x0 goto pc+2")
+__xlated("15: r12 = r2")
+__xlated("16: call unknown")
+__xlated("17: *(u64 *)(r2 +0) = r12")
 /* may_goto expansion ends */
-__xlated("12: *(u64 *)(r10 -8) = r1")
-__xlated("13: exit")
+__xlated("18: *(u64 *)(r10 -8) = r1")
+__xlated("19: exit")
 __success
 __naked void may_goto_interaction(void)
 {
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 2de1ae144ac9..20152a15ca36 100644
--- a/tools/testing/selftests/bpf/progs/verifier_may_goto_1.c
+++ b/tools/testing/selftests/bpf/progs/verifier_may_goto_1.c
@@ -88,19 +88,25 @@ __arch_s390x
 __arch_arm64
 __arch_riscv64
 __arch_loongarch
-__xlated("0: *(u64 *)(r10 -16) = 65535")
-__xlated("1: *(u64 *)(r10 -8) = 0")
-__xlated("2: r12 = *(u64 *)(r10 -16)")
-__xlated("3: if r12 == 0x0 goto pc+7")
-__xlated("4: r12 -= 1")
-__xlated("5: if r12 != 0x0 goto pc+3")
-__xlated("6: r12 = r10")
-__xlated("7: r12 += -16")
-__xlated("8: call unknown")
-__xlated("9: *(u64 *)(r10 -16) = r12")
-__xlated("10: r0 = 1")
-__xlated("11: r0 = 2")
-__xlated("12: exit")
+/* the main prog sets count, timestamp, owner */
+__xlated("0: r0 = ")
+__xlated("2: r0 = &(void __percpu *)(r0)")
+__xlated("3: *(u64 *)(r0 +0) = 65535")
+__xlated("4: *(u64 *)(r0 +8) = 0")
+__xlated("5: *(u64 *)(r0 +16) = 0")
+/* may_goto, r0 is dead */
+__xlated("6: r0 = ")
+__xlated("8: r0 = &(void __percpu *)(r0)")
+__xlated("9: r12 = *(u64 *)(r0 +0)")
+__xlated("10: if r12 == 0x0 goto pc+6")
+__xlated("11: r12 -= 1")
+__xlated("12: if r12 != 0x0 goto pc+2")
+__xlated("13: r12 = r0")
+__xlated("14: call unknown")
+__xlated("15: *(u64 *)(r0 +0) = r12")
+__xlated("16: r0 = 1")
+__xlated("17: r0 = 2")
+__xlated("18: exit")
 __success
 __naked void may_goto_batch_2(void)
 {
-- 
2.55.0

[PATCH bpf v2 8/9] bpf: End bpf_loop() when the time of may_goto is up

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

When the time of a prog is up all loops with may_goto end, but bpf_loop()
goes on. It calls its callback up to 1 << 23 times. The loops in the
callback make no iteration, but the rest of the callback runs, and that can
be another bpf_loop(). Two test progs with bpf_loop(1 << 23, cb) and some
work in cb return after 4 sec and 10 sec. With this patch they return after
250 ms.

bpf_loop() and bpf_for_each_map_elem() end their loop when the callback
returns 1. So return 1 in the first insns of the callback when the time is
up:

  r0 = address of the count
  r0 = &(void __percpu *)(r0)
  r0 = *(u64 *)(r0 +0)
  if r0 != 0x0 goto pc+2
  r0 = 1
  exit

The verifier has seen what follows: the loop of the helper can end after
each call of the callback.

A function that BPF code calls too, or that is the callback of another
helper or kfunc, stays as it is: there the return value has another
meaning. The callback of bpf_user_ringbuf_drain() stays as it is too. The
helper takes a sample out of the buffer for each call, so a call that
does nothing loses the sample. Its loop ends after 128K samples.

This patch does not limit bpf_loop() itself. Only may_goto counts and reads
the clock. So nested bpf_loop() are not stopped when the prog has no
may_goto, or has none in the callbacks: bpf_loop(1 << 20, cb) with
bpf_loop(4096, cb2) in cb takes 5 sec. Nested open coded iterators have the
same problem. A follow up will fix these holes.

A call of such a callback executes 4 more insns. The cost on x86-64 (Zen 5)
in nsec:

                                                   before  after
  callback makes 1 iteration, inlined bpf_loop()    1.16    1.54
  callback makes 1 iteration, bpf_loop()            6.52    6.74
  callback without may_goto, inlined bpf_loop()     1.16    1.16
  callback without may_goto, bpf_loop()             4.95    4.95
  callback without may_goto, nested bpf_loop()      1.13    1.38

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 include/linux/bpf_verifier.h |  4 ++++
 kernel/bpf/fixups.c          | 26 +++++++++++++++++++++-----
 kernel/bpf/verifier.c        |  7 +++++++
 3 files changed, 32 insertions(+), 5 deletions(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 7baeb831281f..12ec5b14007f 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -964,6 +964,10 @@ struct bpf_subprog_info {
 	bool is_cb: 1;
 	bool is_async_cb: 1;
 	bool is_exception_cb: 1;
+	/* bpf_loop() or bpf_for_each_map_elem() call it in a loop */
+	bool is_loop_cb: 1;
+	/* BPF code, another helper or a kfunc call it */
+	bool is_called: 1;
 	bool args_cached: 1;
 	/* true if the return value is passed in the R0:R2 register pair */
 	bool ret_reg_pair: 1;
diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c
index 66b9d1d9e961..a656634fa9e4 100644
--- a/kernel/bpf/fixups.c
+++ b/kernel/bpf/fixups.c
@@ -2771,9 +2771,12 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 		int stack_slots = subprogs[i].stack_extra / 8;
 		/* an invocation begins, see bpf_timed_may_goto_save() for async callbacks */
 		bool main_prog = tmg && !i;
+		/* only a helper calls it, in a loop that ends when it returns 1 */
+		bool loop_cb = tmg && i && subprogs[i].is_loop_cb && !subprogs[i].is_called &&
+			       !subprogs[i].is_async_cb;
 		int cnt = 0;
 
-		if (timed_may_goto ? !main_prog : !stack_slots)
+		if (timed_may_goto ? !main_prog && !loop_cb : !stack_slots)
 			continue;
 		if (stack_slots > 1) {
 			verifier_bug(env, "stack_slots supports may_goto only");
@@ -2793,10 +2796,23 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			insn_buf[cnt++] = ld_tmg[0];
 			insn_buf[cnt++] = ld_tmg[1];
 			insn_buf[cnt++] = BPF_MOV64_PERCPU_REG(BPF_REG_0, BPF_REG_0);
-			insn_buf[cnt++] = BPF_ST_MEM(BPF_DW, BPF_REG_0, count_off,
-						     BPF_MAX_TIMED_LOOPS);
-			insn_buf[cnt++] = BPF_ST_MEM(BPF_DW, BPF_REG_0, timestamp_off, 0);
-			insn_buf[cnt++] = BPF_ST_MEM(BPF_DW, BPF_REG_0, owner_off, 0);
+			if (main_prog) {
+				insn_buf[cnt++] = BPF_ST_MEM(BPF_DW, BPF_REG_0, count_off,
+							     BPF_MAX_TIMED_LOOPS);
+				insn_buf[cnt++] = BPF_ST_MEM(BPF_DW, BPF_REG_0, timestamp_off, 0);
+				insn_buf[cnt++] = BPF_ST_MEM(BPF_DW, BPF_REG_0, owner_off, 0);
+			} else {
+				/*
+				 * The time is up, but the helper would call the function again and
+				 * again. End its loop. The verifier has seen that: the loop can end
+				 * after each call.
+				 */
+				insn_buf[cnt++] = BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_0,
+							      count_off);
+				insn_buf[cnt++] = BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 2);
+				insn_buf[cnt++] = BPF_MOV64_IMM(BPF_REG_0, 1);
+				insn_buf[cnt++] = BPF_EXIT_INSN();
+			}
 		} else {
 			/* Add ST insn to subprog prologue to init extra stack */
 			insn_buf[cnt++] = BPF_ST_MEM(BPF_DW, BPF_REG_FP, -stack_depth,
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 26a5ee0708a3..383cdc11b5b4 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -11469,6 +11469,12 @@ static int push_callback_call(struct bpf_verifier_env *env, struct bpf_insn *ins
 	if (err)
 		return err;
 
+	if (!bpf_pseudo_kfunc_call(insn) &&
+	    (insn->imm == BPF_FUNC_loop || insn->imm == BPF_FUNC_for_each_map_elem))
+		env->subprog_info[subprog].is_loop_cb = true;
+	else
+		env->subprog_info[subprog].is_called = true;
+
 	/* for callback functions enqueue entry to callback and
 	 * proceed with next instruction within current frame.
 	 */
@@ -11505,6 +11511,7 @@ static int check_static_func_call(struct bpf_verifier_env *env, int subprog,
 	int err;
 
 	caller = state->frame[state->curframe];
+	env->subprog_info[subprog].is_called = true;
 
 	/*
 	 * Track caller's total stack arg count (incoming + max outgoing).
-- 
2.55.0

[PATCH bpf v2 9/9] selftests/bpf: Test one may_goto time slice per prog invocation

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

Most tests call a function that spins until may_goto stops it, four times.
With one time slice for an invocation of the prog only the first call
spins. With a time slice for each frame all four calls spin, and the test
fails after 1 sec.

  group           tests
  --------------  ------------------------------------------------------
  the problem     9 insns, three levels of short loops, a subprog with
                  65534 iterations, bpf_loop() with a callback that spins
                  or makes 60000 iterations
  ways to a loop  call, call through a function without a loop, global
                  function, callx, bpf_loop() inlined and not,
                  bpf_for_each_map_elem(), bpf_user_ringbuf_drain(),
                  bpf_find_vma(), bpf_rbtree_add()
  bpf_loop()      ends when the time is up: inlined and not, in a callback
                  of bpf_loop(). Goes on when BPF code calls the callback
                  too
  count           a loop that is on the stack ends when the time is up,
                  65535 calls that make one iteration read the clock
  new time slice  timer, wq, task_work, call_rcu, call_rcu_tasks_trace,
                  each after a prog on the cpu that used up its time. Tail
                  call, extension prog
  same one        a timer callback that interrupts the prog doesn't give it
                  more time, the exception callback
  registers       may_goto takes a register that is dead: R0-RN are live,
                  for each N. A register that is live through the back
                  edge only, at the target only, behind the may_goto only.
                  All of that when it calls C and when the time is up.
                  16-byte return value
  other           tracing prog with frames in a private stack, may_goto in
                  dead code

Two tests lock up a cpu on a kernel with a time slice for each frame: the
9 insns and the three levels of short loops. All other tests give up and
fail there, or pass. The tests are for x86-64 and arm64 with the JIT only.

may_goto_far gets four subtests with the may_goto in a subprog.

The test is serial. Its progs spin for 250 ms in an RCU read-side critical
section, one after the other. Next to them in 'test_progs -j' the test
"mmap" gives up its wait for the end of a map. The test takes 10 sec.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 .../selftests/bpf/prog_tests/may_goto_far.c   |  24 +-
 .../selftests/bpf/prog_tests/timed_may_goto.c | 195 ++++
 .../selftests/bpf/progs/timed_may_goto.c      | 898 ++++++++++++++++++
 .../selftests/bpf/progs/timed_may_goto_ext.c  |  23 +
 .../selftests/bpf/progs/timed_may_goto_user.c | 311 ++++++
 5 files changed, 1446 insertions(+), 5 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/timed_may_goto.c
 create mode 100644 tools/testing/selftests/bpf/progs/timed_may_goto.c
 create mode 100644 tools/testing/selftests/bpf/progs/timed_may_goto_ext.c
 create mode 100644 tools/testing/selftests/bpf/progs/timed_may_goto_user.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
index 8d0ff30bd068..b6d262911a3e 100644
--- a/tools/testing/selftests/bpf/prog_tests/may_goto_far.c
+++ b/tools/testing/selftests/bpf/prog_tests/may_goto_far.c
@@ -34,8 +34,10 @@ static struct bpf_insn *fill(struct bpf_insn *insn, int cnt, int reg)
  * 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.
+ *
+ * With 'subprog' all of that is a subprog.
  */
-static void test_far(int off)
+static void test_far(int off, bool subprog)
 {
 	LIBBPF_OPTS(bpf_prog_load_opts, opts, .prog_flags = BPF_F_SLEEPABLE);
 	LIBBPF_OPTS(bpf_test_run_opts, topts);
@@ -50,6 +52,10 @@ static void test_far(int off)
 		return;
 
 	insn = insns;
+	if (subprog) {
+		*insn++ = BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, BPF_PSEUDO_CALL, 0, 1);
+		*insn++ = BPF_EXIT_INSN();
+	}
 	*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);
@@ -82,11 +88,19 @@ static void test_far(int off)
 void test_may_goto_far(void)
 {
 	if (test__start_subtest("32762"))
-		test_far(32762);
+		test_far(32762, false);
 	if (test__start_subtest("32767"))
-		test_far(32767);
+		test_far(32767, false);
 	if (test__start_subtest("-32767"))
-		test_far(-32767);
+		test_far(-32767, false);
 	if (test__start_subtest("-32768"))
-		test_far(-32768);
+		test_far(-32768, false);
+	if (test__start_subtest("subprog 1"))
+		test_far(1, true);
+	if (test__start_subtest("subprog 32767"))
+		test_far(32767, true);
+	if (test__start_subtest("subprog -6"))
+		test_far(-6, true);
+	if (test__start_subtest("subprog -32768"))
+		test_far(-32768, true);
 }
diff --git a/tools/testing/selftests/bpf/prog_tests/timed_may_goto.c b/tools/testing/selftests/bpf/prog_tests/timed_may_goto.c
new file mode 100644
index 000000000000..3da3f33a2898
--- /dev/null
+++ b/tools/testing/selftests/bpf/prog_tests/timed_may_goto.c
@@ -0,0 +1,195 @@
+// SPDX-License-Identifier: GPL-2.0
+#define _GNU_SOURCE
+#include <sched.h>
+#include <test_progs.h>
+#include <network_helpers.h>
+#include "timed_may_goto.skel.h"
+#include "timed_may_goto_user.skel.h"
+#include "timed_may_goto_ext.skel.h"
+
+#define TRIES 4
+
+static int run_tc(struct bpf_program *prog)
+{
+	LIBBPF_OPTS(bpf_test_run_opts, opts,
+		.data_in = &pkt_v4,
+		.data_size_in = sizeof(pkt_v4),
+		.repeat = 1,
+	);
+
+	if (!ASSERT_OK(bpf_prog_test_run_opts(bpf_program__fd(prog), &opts), "test_run"))
+		return -1;
+	return opts.retval;
+}
+
+static int run_syscall(struct bpf_program *prog)
+{
+	LIBBPF_OPTS(bpf_test_run_opts, opts);
+
+	if (!ASSERT_OK(bpf_prog_test_run_opts(bpf_program__fd(prog), &opts), "test_run"))
+		return -1;
+	return opts.retval;
+}
+
+static void wait_for(int *val, int expected, const char *name)
+{
+	int i;
+
+	for (i = 0; i < 500 && *(volatile int *)val != expected; i++)
+		usleep(10000);
+	ASSERT_EQ(*val, expected, name);
+}
+
+static void test_async(struct timed_may_goto_user *skel)
+{
+	ASSERT_EQ(run_syscall(skel->progs.async_after_timeout), 0, "async_after_timeout");
+	wait_for(&skel->bss->timer_cnt, 1000, "timer_cnt");
+	wait_for(&skel->bss->wq_cnt, 1000, "wq_cnt");
+	wait_for(&skel->bss->tw_cnt, 1000, "tw_cnt");
+	wait_for(&skel->bss->rcu_cnt, 1000, "rcu_cnt");
+	wait_for(&skel->bss->rcu_trace_cnt, 1000, "rcu_trace_cnt");
+}
+
+static void test_timer_on_top(struct timed_may_goto_user *skel)
+{
+	int ms = run_syscall(skel->progs.spin_under_timer);
+	int ticks = skel->bss->ticks;
+
+	/* stop the timer */
+	skel->bss->ticks = 100;
+	ASSERT_GE(ms, 200, "ms");
+	ASSERT_LE(ms, 500, "ms");
+	/* control: the callback interrupted the prog, and its loop went on to the end */
+	ASSERT_GE(ticks, 5, "ticks");
+	ASSERT_LT(ticks, 100, "ticks");
+}
+
+static void test_freplace(struct timed_may_goto_user *skel)
+{
+	struct timed_may_goto_ext *ext;
+
+	ASSERT_EQ(run_tc(skel->progs.freplace_target), 1, "not replaced");
+
+	ext = timed_may_goto_ext__open();
+	if (!ASSERT_OK_PTR(ext, "ext_open"))
+		return;
+	bpf_program__set_attach_target(ext->progs.replacement,
+				       bpf_program__fd(skel->progs.freplace_target),
+				       "replaced_global");
+	if (!ASSERT_OK(timed_may_goto_ext__load(ext), "ext_load") ||
+	    !ASSERT_OK(timed_may_goto_ext__attach(ext), "ext_attach"))
+		goto out;
+	ASSERT_EQ(run_tc(skel->progs.freplace_target), TRIES, "replaced");
+out:
+	timed_may_goto_ext__destroy(ext);
+	ASSERT_EQ(run_tc(skel->progs.freplace_target), 1, "not replaced");
+}
+
+/* What a prog leaves behind when its time is up doesn't matter for the next one on the cpu. */
+static void test_tail_call_and_throw(struct timed_may_goto_user *skel)
+{
+	int key = 0, fd = bpf_program__fd(skel->progs.tail_callee);
+	int map_fd = bpf_map__fd(skel->maps.jmp_table);
+
+	if (!ASSERT_OK(bpf_map_update_elem(map_fd, &key, &fd, 0), "update"))
+		return;
+
+	ASSERT_EQ(run_tc(skel->progs.normal_prog), 1, "normal_prog");
+	ASSERT_EQ(run_tc(skel->progs.normal_prog), 1, "normal_prog");
+
+	ASSERT_EQ(run_tc(skel->progs.tail_call_in_subprog), 1, "tail_call_in_subprog");
+	ASSERT_EQ(skel->bss->tail_callee_spun, 1, "tail_callee_spun");
+
+	ASSERT_EQ(run_tc(skel->progs.tail_call_after_timeout), 0, "tail_call_after_timeout");
+	ASSERT_EQ(skel->bss->tail_callee_spun, 1, "tail_callee_spun");
+
+	ASSERT_EQ(run_tc(skel->progs.throw_after_timeout), 7, "throw_after_timeout");
+	ASSERT_EQ(run_tc(skel->progs.throw_after_timeout), 7, "throw_after_timeout");
+}
+
+static void test_user_ringbuf(struct timed_may_goto_user *skel)
+{
+	struct user_ring_buffer *rb;
+	void *sample;
+	int i;
+
+	rb = user_ring_buffer__new(bpf_map__fd(skel->maps.user_ringbuf), NULL);
+	if (!ASSERT_OK_PTR(rb, "user_ring_buffer__new"))
+		return;
+	for (i = 0; i < TRIES; i++) {
+		sample = user_ring_buffer__reserve(rb, 8);
+		if (!ASSERT_OK_PTR(sample, "reserve"))
+			goto out;
+		user_ring_buffer__submit(rb, sample);
+	}
+	/* The helper takes a sample out of the buffer for each call: all calls have to run. */
+	ASSERT_EQ(run_syscall(skel->progs.drain), TRIES * 10 + 1, "drain");
+out:
+	user_ring_buffer__free(rb);
+}
+
+static void test_priv_stack(struct timed_may_goto_user *skel)
+{
+	LIBBPF_OPTS(bpf_test_run_opts, opts);
+	int fd = bpf_program__fd(skel->progs.priv_stack);
+	struct bpf_link *link;
+
+	link = bpf_program__attach(skel->progs.priv_stack);
+	if (!ASSERT_OK_PTR(link, "attach"))
+		return;
+	ASSERT_OK(bpf_prog_test_run_opts(fd, &opts), "test_run");
+	ASSERT_EQ(skel->bss->priv_stack_spun, 1, "priv_stack_spun");
+	ASSERT_EQ(skel->bss->priv_stack_cb_spun, 0, "priv_stack_cb_spun");
+	bpf_link__destroy(link);
+}
+
+/*
+ * Serial: most progs spin for 250 ms in an RCU read-side critical section, one after the other.
+ * That delays what other tests wait for. In parallel mode "mmap" gives up its wait for the end of
+ * a map.
+ */
+void serial_test_timed_may_goto(void)
+{
+	struct timed_may_goto_user *skel;
+	cpu_set_t old, new;
+
+	/* The interpreter counts in each frame. */
+	if (!is_jit_enabled()) {
+		test__skip();
+		return;
+	}
+
+	RUN_TESTS(timed_may_goto);
+
+#if !defined(__x86_64__) && !defined(__aarch64__)
+	return;
+#endif
+	skel = timed_may_goto_user__open_and_load();
+	if (!ASSERT_OK_PTR(skel, "open_and_load"))
+		return;
+
+	/* Count and timestamp are per-cpu: all progs of a subtest run on one cpu. */
+	if (!ASSERT_OK(sched_getaffinity(0, sizeof(old), &old), "getaffinity"))
+		goto out;
+	CPU_ZERO(&new);
+	CPU_SET(sched_getcpu(), &new);
+	if (!ASSERT_OK(sched_setaffinity(0, sizeof(new), &new), "setaffinity"))
+		goto out;
+
+	if (test__start_subtest("async"))
+		test_async(skel);
+	if (test__start_subtest("timer_on_top"))
+		test_timer_on_top(skel);
+	if (test__start_subtest("freplace"))
+		test_freplace(skel);
+	if (test__start_subtest("tail_call_and_throw"))
+		test_tail_call_and_throw(skel);
+	if (test__start_subtest("user_ringbuf"))
+		test_user_ringbuf(skel);
+	if (test__start_subtest("priv_stack"))
+		test_priv_stack(skel);
+
+	sched_setaffinity(0, sizeof(old), &old);
+out:
+	timed_may_goto_user__destroy(skel);
+}
diff --git a/tools/testing/selftests/bpf/progs/timed_may_goto.c b/tools/testing/selftests/bpf/progs/timed_may_goto.c
new file mode 100644
index 000000000000..c1c48af808a9
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/timed_may_goto.c
@@ -0,0 +1,898 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * There is one time slice of may_goto for an invocation of a prog: one call from the kernel into
+ * the main prog, with the subprogs and sync callbacks that it reaches.
+ *
+ * Most tests call a function that spins until may_goto stops it, four times, each in a different
+ * way. Only the first call can spin. With a time slice for each call all four do.
+ */
+#include <vmlinux.h>
+#include <bpf/bpf_helpers.h>
+#include <bpf/bpf_tracing.h>
+#include "bpf_misc.h"
+#include "bpf_experimental.h"
+
+char _license[] SEC("license") = "GPL";
+
+#if (defined(__TARGET_ARCH_x86) || defined(__TARGET_ARCH_arm64)) && __clang_major__ >= 18
+
+#define TRIES 4
+
+int zero;
+
+/* Return 1 if the loop went on until the time was up. */
+static __always_inline int spin(void)
+{
+	__u64 t0 = bpf_ktime_get_ns();
+
+	while (can_loop)
+		;
+	return bpf_ktime_get_ns() - t0 > 100 * 1000 * 1000;
+}
+
+static __noinline int spins(void)
+{
+	return spin();
+}
+
+static __noinline int counts_to_1000(void)
+{
+	int i, cnt = zero;
+
+	for (i = zero; i < 1000 && can_loop; i++)
+		cnt++;
+	return cnt;
+}
+
+SEC("tc")
+__description("timed may_goto: call")
+__success __retval(1)
+int call_subprog(void *ctx)
+{
+	int i, n = 0;
+
+	for (i = 0; i < TRIES; i++)
+		n += spins();
+	return n;
+}
+
+SEC("tc")
+__description("timed may_goto: a call after the time is up makes no iteration")
+__success __retval(0)
+int short_loop_after_timeout(void *ctx)
+{
+	spins();
+	return counts_to_1000();
+}
+
+SEC("tc")
+__description("timed may_goto: the loop of the main prog stops when the time is up in a subprog")
+__success __retval(1)
+int main_loop_after_timeout(void *ctx)
+{
+	int n = 0;
+
+	while (can_loop && n < 2 * TRIES)
+		n += spins();
+	return n;
+}
+
+static __noinline int passes(int i)
+{
+	return spins() + i;
+}
+
+SEC("tc")
+__description("timed may_goto: call through a function without a loop")
+__success __retval(1)
+int call_through(void *ctx)
+{
+	int i, n = 0;
+
+	for (i = 0; i < TRIES; i++)
+		n += passes(zero);
+	return n;
+}
+
+__noinline int global_spins(void)
+{
+	return spin();
+}
+
+SEC("tc")
+__description("timed may_goto: call of a global function")
+__success __retval(1)
+int call_global(void *ctx)
+{
+	int i, n = 0;
+
+	for (i = 0; i < TRIES; i++)
+		n += global_spins();
+	return n;
+}
+
+SEC("tc")
+__description("timed may_goto: callx")
+__success __retval(1)
+__naked void callx_subprog(void)
+{
+	asm volatile (
+		"r6 = 0;"
+		"r7 = 0;"
+	"1:"
+		"r3 = %[spins] ll;"
+		"callx r3;"
+		"r6 += r0;"
+		"r7 += 1;"
+		"if r7 < 4 goto 1b;"
+		"r0 = r6;"
+		"exit;"
+		:
+		: __imm_addr(spins)
+		: __clobber_all);
+}
+
+/* With a time slice for each call it gives up, so that the test fails and doesn't lock up. */
+static int loop_cb(__u64 i, int *spun)
+{
+	*spun += spin();
+	return *spun > 2 * TRIES;
+}
+
+SEC("tc")
+__description("timed may_goto: bpf_loop() inlined")
+__success __retval(1)
+int loop_inlined(void *ctx)
+{
+	int spun = 0;
+
+	bpf_loop(1 << 20, loop_cb, &spun, 0);
+	return spun;
+}
+
+SEC("tc")
+__description("timed may_goto: bpf_loop() not inlined")
+__success __retval(1)
+int loop_not_inlined(void *ctx)
+{
+	int spun = 0;
+
+	bpf_loop(1 << 20, loop_cb, &spun, zero);
+	return spun;
+}
+
+static int count_cb(__u64 i, int *calls)
+{
+	(*calls)++;
+	return 0;
+}
+
+/* The time is up: the helper calls the callback one more time. It returns 1 in its first insns. */
+#define LOOP_ENDS(name, flags)							\
+SEC("tc")									\
+__description("timed may_goto: bpf_loop() " #name " ends when the time is up")	\
+__success __retval(10)								\
+int loop_ends_##name(void *ctx)							\
+{										\
+	int calls = 0;								\
+										\
+	spins();								\
+	return bpf_loop(1000, count_cb, &calls, flags) * 10 + calls;		\
+}
+
+LOOP_ENDS(inlined, 0)
+LOOP_ENDS(not_inlined, zero)
+
+struct nested {
+	__u64 t0;
+	int spun;
+};
+
+/* Without an end of bpf_loop(): give up, so that the test fails and doesn't lock up. */
+static int inner_cb(__u64 i, struct nested *n)
+{
+	if (!n->spun)
+		n->spun = spin();
+	return (i & 1023) == 0 && bpf_ktime_get_ns() - n->t0 > 1000 * 1000 * 1000;
+}
+
+static int outer_cb(__u64 i, struct nested *n)
+{
+	bpf_loop(1 << 23, inner_cb, n, 0);
+	return bpf_ktime_get_ns() - n->t0 > 1000 * 1000 * 1000;
+}
+
+SEC("tc")
+__description("timed may_goto: bpf_loop() in bpf_loop() ends when the time is up")
+__success __retval(1)
+int loop_in_loop(void *ctx)
+{
+	struct nested n = { .t0 = bpf_ktime_get_ns() };
+
+	bpf_loop(1 << 23, outer_cb, &n, 0);
+	return n.spun && bpf_ktime_get_ns() - n.t0 < 500 * 1000 * 1000;
+}
+
+static __noinline int called_cb(__u64 i, int *calls)
+{
+	(*calls)++;
+	return 0;
+}
+
+/* BPF code calls the callback too, so its return value has to be its own. bpf_loop() goes on. */
+SEC("tc")
+__description("timed may_goto: bpf_loop() with a callback that is called as well")
+__success __retval(45)
+int loop_and_call(void *ctx)
+{
+	int calls = 0;
+
+	spins();
+	if (called_cb(zero, &calls))
+		return 100;
+	return bpf_loop(TRIES, called_cb, &calls, 0) * 10 + calls;
+}
+
+static int short_cb(__u64 i, __u64 *t0)
+{
+	int j;
+
+	for (j = zero; j < 60000 && can_loop; j++)
+		;
+	return (i & 1023) == 0 && bpf_ktime_get_ns() - *t0 > 1000 * 1000 * 1000;
+}
+
+/*
+ * The main prog has no may_goto. Each call of the callback ends before it reads the clock. The
+ * iterations of all calls add up.
+ */
+SEC("tc")
+__description("timed may_goto: bpf_loop() the callback makes 60000 iterations")
+__success __retval(1)
+int loop_short_cb(void *ctx)
+{
+	__u64 t0 = bpf_ktime_get_ns();
+
+	bpf_loop(1 << 20, short_cb, &t0, 0);
+	return bpf_ktime_get_ns() - t0 < 1000 * 1000 * 1000;
+}
+
+/* spins() uses up the time. The loop that calls it ends at its next may_goto. */
+static __noinline int loops_around_spins(void)
+{
+	int n = zero;
+
+	while (can_loop && n < 20000) {
+		if (n < 2 * TRIES)
+			spins();
+		n++;
+	}
+	return n;
+}
+
+SEC("tc")
+__description("timed may_goto: a loop that is on the stack ends when the time is up")
+__success __retval(1)
+int rest_of_batch(void *ctx)
+{
+	return loops_around_spins();
+}
+
+static __noinline int one_iteration(void)
+{
+	int i, n = zero;
+
+	for (i = zero; i < 1 && can_loop; i++)
+		n++;
+	return n;
+}
+
+long calls_ok;
+
+static int call_one(__u64 i, __u64 *t0)
+{
+	if (!one_iteration())
+		return 1;
+	calls_ok++;
+	/* With a time slice for each call: give up. */
+	return (i & 1023) == 0 && bpf_ktime_get_ns() - *t0 > 1000 * 1000 * 1000;
+}
+
+static int call_many(__u64 i, __u64 *t0)
+{
+	long before = calls_ok;
+
+	bpf_loop(1 << 23, call_one, t0, 0);
+	return calls_ok - before != 1 << 23;
+}
+
+/*
+ * The iterations of all calls count: the prog reads the clock in each 65535th call. The call that
+ * finds out that the time is up makes its iteration.
+ */
+SEC("tc")
+__description("timed may_goto: 65535 calls that make one iteration read the clock")
+__success __retval(1)
+int clock_after_65535_calls(void *ctx)
+{
+	__u64 t0 = bpf_ktime_get_ns();
+
+	calls_ok = 0;
+	bpf_loop(1000, call_many, &t0, 0);
+	return calls_ok > 0 && calls_ok % 65535 == 0;
+}
+
+#define MAP(name, map_type, flags)			\
+struct {						\
+	__uint(type, map_type);				\
+	__uint(max_entries, TRIES);			\
+	__uint(map_flags, flags);			\
+	__type(key, int);				\
+	__type(value, int);				\
+} name SEC(".maps")
+
+MAP(array, BPF_MAP_TYPE_ARRAY, 0);
+MAP(hash, BPF_MAP_TYPE_HASH, 0);
+
+/* The first call uses up the time. The second call ends the loop of the helper. */
+static int elem_cb(void *map, int *key, int *val, int *spun)
+{
+	*spun += spin();
+	return 0;
+}
+
+#define FOR_EACH(name)								\
+SEC("tc")									\
+__description("timed may_goto: bpf_for_each_map_elem() " #name)			\
+__success __retval(21)								\
+int for_each_##name(void *ctx)							\
+{										\
+	int i, key, spun = 0;							\
+										\
+	for (i = 0; i < TRIES; i++) {						\
+		key = i;							\
+		bpf_map_update_elem(&name, &key, &key, 0);			\
+	}									\
+	return bpf_for_each_map_elem(&name, elem_cb, &spun, 0) * 10 + spun;	\
+}
+
+FOR_EACH(array)
+FOR_EACH(hash)
+
+static long vma_cb(struct task_struct *task, struct vm_area_struct *vma, int *spun)
+{
+	*spun += spin();
+	return 0;
+}
+
+SEC("raw_tp")
+__description("timed may_goto: bpf_find_vma()")
+__success __retval(1)
+int find_vma(void *ctx)
+{
+	struct task_struct *task = bpf_get_current_task_btf();
+	__u64 addr = task->mm->arg_start;
+	int i, spun = 0;
+
+	for (i = 0; i < TRIES; i++)
+		if (bpf_find_vma(task, addr, vma_cb, &spun, 0))
+			return 100;
+	return spun;
+}
+
+struct tree_node {
+	struct bpf_rb_node rb;
+	int key;
+};
+
+#define private(name) SEC(".data." #name) __hidden __attribute__((aligned(8)))
+private(A) struct bpf_spin_lock lock;
+private(A) struct bpf_rb_root root __contains(tree_node, rb);
+
+int less_spun, less_calls;
+
+static bool less(struct bpf_rb_node *a, const struct bpf_rb_node *b)
+{
+	long n = zero;
+
+	/* no helpers under the lock */
+	while (can_loop)
+		n++;
+	less_calls++;
+	less_spun += n > 1000 * 1000;
+	return container_of(a, struct tree_node, rb)->key <
+	       container_of(b, struct tree_node, rb)->key;
+}
+
+SEC("tc")
+__description("timed may_goto: bpf_rbtree_add()")
+__success __retval(1)
+int rbtree_add(void *ctx)
+{
+	struct bpf_rb_node *rb;
+	struct tree_node *n;
+	int i;
+
+	less_spun = less_calls = 0;
+	for (i = 0; i < TRIES; i++) {
+		n = bpf_obj_new(typeof(*n));
+		if (!n)
+			return 100;
+		n->key = TRIES - i;
+		bpf_spin_lock(&lock);
+		bpf_rbtree_add(&root, &n->rb, less);
+		bpf_spin_unlock(&lock);
+	}
+	for (i = 0; i < TRIES; i++) {
+		bpf_spin_lock(&lock);
+		rb = bpf_rbtree_first(&root);
+		if (rb)
+			rb = bpf_rbtree_remove(&root, rb);
+		bpf_spin_unlock(&lock);
+		if (!rb)
+			return 101;
+		bpf_obj_drop(container_of(rb, struct tree_node, rb));
+	}
+	if (less_calls < TRIES - 1)
+		return 102;
+	return less_spun;
+}
+
+/*
+ * All registers are live at the may_goto, so it saves one of them in the stack. They are the same
+ * after 70000 iterations: the loop reads the clock.
+ */
+__naked __noinline __used
+static long regs_across_may_goto(void)
+{
+	asm volatile (
+		"r0 = 10;"
+		"r6 = 6;"
+		"r7 = 7;"
+		"r8 = 8;"
+		"r9 = 0;"
+	"1:"
+		"may_goto 2f;"
+		"r9 += 1;"
+		"if r9 < 70000 goto 1b;"
+	"2:"
+		"r0 += r1;"
+		"r0 += r2;"
+		"r0 += r3;"
+		"r0 += r4;"
+		"r0 += r5;"
+		"r0 += r6;"
+		"r0 += r7;"
+		"r0 += r8;"
+		"r0 += r9;"
+		"exit;"
+		::: __clobber_all);
+}
+
+SEC("tc")
+__description("timed may_goto: registers across may_goto")
+__success __retval(70046)
+__naked void regs_across_may_goto_main(void)
+{
+	asm volatile (
+		"r1 = 1;"
+		"r2 = 2;"
+		"r3 = 3;"
+		"r4 = 4;"
+		"r5 = 5;"
+		"call regs_across_may_goto;"
+		"exit;"
+		::: __clobber_all);
+}
+
+/*
+ * may_goto uses a register that is dead. In live_r0_rN() R0 - RN are live at the may_goto and the
+ * next one is not. The values come from memory, so the verifier doesn't know them. Return their sum
+ * and the number of iterations.
+ */
+__u64 vals[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+__u64 zero64;
+
+#define LD0(b)		"r0 = *(u64 *)(r" #b " + 0);"
+#define LD1(b) LD0(b)	"r1 = *(u64 *)(r" #b " + 8);"
+#define LD2(b) LD1(b)	"r2 = *(u64 *)(r" #b " + 16);"
+#define LD3(b) LD2(b)	"r3 = *(u64 *)(r" #b " + 24);"
+#define LD4(b) LD3(b)	"r4 = *(u64 *)(r" #b " + 32);"
+#define LD5(b) LD4(b)	"r5 = *(u64 *)(r" #b " + 40);"
+#define LD6(b) LD5(b)	"r6 = *(u64 *)(r" #b " + 48);"
+#define LD7(b) LD6(b)	"r7 = *(u64 *)(r" #b " + 56);"
+#define LD8(b) LD7(b)	"r8 = *(u64 *)(r" #b " + 64);"
+
+#define SUM0
+#define SUM1 SUM0	"r0 += r1;"
+#define SUM2 SUM1	"r0 += r2;"
+#define SUM3 SUM2	"r0 += r3;"
+#define SUM4 SUM3	"r0 += r4;"
+#define SUM5 SUM4	"r0 += r5;"
+#define SUM6 SUM5	"r0 += r6;"
+#define SUM7 SUM6	"r0 += r7;"
+#define SUM8 SUM7	"r0 += r8;"
+
+/* The count of iterations is at r10 - 8. It begins with a number from memory too. */
+#define COUNT_INIT(t)						\
+		"r" #t " = %[zero64] ll;"			\
+		"r" #t " = *(u64 *)(r" #t " + 0);"		\
+		"*(u64 *)(r10 - 8) = r" #t ";"
+#define COUNT_AND_LOOP(t)					\
+		"r" #t " = *(u64 *)(r10 - 8);"			\
+		"r" #t " += 1;"					\
+		"*(u64 *)(r10 - 8) = r" #t ";"			\
+		"if r" #t " < 70000 goto 1b;"
+#define ADD_COUNT_AND_EXIT					\
+		"r1 = *(u64 *)(r10 - 8);"			\
+		"r0 += r1;"					\
+		"exit;"						\
+		:						\
+		: __imm_addr(vals), __imm_addr(zero64)		\
+		: __clobber_all
+
+#define LIVE_REGS(n, next)					\
+__naked __noinline __used					\
+static long live_r0_r##n(void)					\
+{								\
+	asm volatile (						\
+		COUNT_INIT(next)				\
+		"r" #n " = %[vals] ll;"				\
+		LD##n(n)					\
+	"1:"							\
+		"may_goto 2f;"					\
+		COUNT_AND_LOOP(next)				\
+	"2:"							\
+		SUM##n						\
+		ADD_COUNT_AND_EXIT);				\
+}
+
+LIVE_REGS(0, 1)
+LIVE_REGS(1, 2)
+LIVE_REGS(2, 3)
+LIVE_REGS(3, 4)
+LIVE_REGS(4, 5)
+LIVE_REGS(5, 6)
+LIVE_REGS(6, 7)
+LIVE_REGS(7, 8)
+LIVE_REGS(8, 9)
+
+/* R2 is read at the top of the loop only: it is live at the may_goto through the back edge. */
+__naked __noinline __used
+static long live_back_edge(void)
+{
+	asm volatile (
+		COUNT_INIT(3)
+		"r2 = %[vals] ll;"
+		LD2(2)
+	"1:"
+		"*(u64 *)(r10 - 16) = r2;"
+		"may_goto 2f;"
+		COUNT_AND_LOOP(3)
+	"2:"
+		"r0 += r1;"
+		"r2 = *(u64 *)(r10 - 16);"
+		"r0 += r2;"
+		ADD_COUNT_AND_EXIT);
+}
+
+/* R2 is read only where the may_goto jumps to. */
+__naked __noinline __used
+static long live_target(void)
+{
+	asm volatile (
+		COUNT_INIT(3)
+		"r2 = %[vals] ll;"
+		LD2(2)
+	"1:"
+		"may_goto 2f;"
+		COUNT_AND_LOOP(3)
+		"goto 3f;"
+	"2:"
+		"r0 += r2;"
+	"3:"
+		"r0 += r1;"
+		ADD_COUNT_AND_EXIT);
+}
+
+/* R2 is set in front of the may_goto in each iteration, and read only right behind it. */
+__naked __noinline __used
+static long live_fall_through(void)
+{
+	asm volatile (
+		COUNT_INIT(3)
+		"r1 = %[vals] ll;"
+		LD1(1)
+		"*(u64 *)(r10 - 16) = r0;"
+	"1:"
+		"r2 = %[vals] ll;"
+		"r2 = *(u64 *)(r2 + 16);"
+		"may_goto 2f;"
+		"*(u64 *)(r10 - 16) = r2;"
+		COUNT_AND_LOOP(3)
+	"2:"
+		"r0 += r1;"
+		"r2 = *(u64 *)(r10 - 16);"
+		"r0 += r2;"
+		ADD_COUNT_AND_EXIT);
+}
+
+#define CALL_AND_ADD(f)	"call " #f ";" "r6 += r0;"
+#define CALL_ALL_LIVE						\
+		"r6 = 0;"					\
+		CALL_AND_ADD(live_r0_r0)			\
+		CALL_AND_ADD(live_r0_r1)			\
+		CALL_AND_ADD(live_r0_r2)			\
+		CALL_AND_ADD(live_r0_r3)			\
+		CALL_AND_ADD(live_r0_r4)			\
+		CALL_AND_ADD(live_r0_r5)			\
+		CALL_AND_ADD(live_r0_r6)			\
+		CALL_AND_ADD(live_r0_r7)			\
+		CALL_AND_ADD(live_r0_r8)			\
+		CALL_AND_ADD(live_back_edge)			\
+		CALL_AND_ADD(live_target)			\
+		CALL_AND_ADD(live_fall_through)			\
+		"r0 = r6;"					\
+		"exit;"
+
+/*
+ * The sums: 1 + 3 + 6 + 10 + 15 + 21 + 28 + 36 + 45 = 165. Then 6, 3 (the may_goto doesn't jump)
+ * and 6. 12 * 70000 iterations: each function reads the clock.
+ */
+SEC("tc")
+__description("timed may_goto: may_goto takes a register that is dead")
+__success __retval(840180)
+__naked void dead_reg(void)
+{
+	asm volatile (
+		CALL_ALL_LIVE
+		::: __clobber_all);
+}
+
+/* No iteration: 165, then 6, 6 (the may_goto jumps) and 4 (R2 isn't stored). */
+SEC("tc")
+__description("timed may_goto: may_goto takes a register that is dead, the time is up")
+__success __retval(181)
+__naked void dead_reg_time_is_up(void)
+{
+	asm volatile (
+		"call spins_on_may_goto;"
+		CALL_ALL_LIVE
+		::: __clobber_all);
+}
+
+/*
+ * The subprog uses up the time of the prog and returns. With a time slice for each call the caller
+ * calls it 65535 times before it reads the clock.
+ */
+__naked __noinline __used
+static unsigned long spins_on_may_goto(void)
+{
+	asm volatile (
+	"1:"
+		"may_goto 2f;"
+		"goto 1b;"
+	"2:"
+		"r0 = 0;"
+		"exit;"
+		::: __clobber_all);
+}
+
+/* The first may_goto of the function finds that the time is up */
+SEC("tc")
+__description("timed may_goto: registers across may_goto when the time is up")
+__success __retval(46)
+__naked void regs_when_time_is_up(void)
+{
+	asm volatile (
+		"call spins_on_may_goto;"
+		"r1 = 1;"
+		"r2 = 2;"
+		"r3 = 3;"
+		"r4 = 4;"
+		"r5 = 5;"
+		"call regs_across_may_goto;"
+		"exit;"
+		::: __clobber_all);
+}
+
+/* The first insn of the main prog is the target of a jump. It must not set the count again. */
+SEC("socket")
+__description("timed may_goto: 9 insns")
+__success __retval(1)
+__naked void loop_calls_subprog_with_may_goto(void)
+{
+	asm volatile (
+	"1:"
+		"call spins_on_may_goto;"
+		"may_goto 2f;"
+		"goto 1b;"
+	"2:"
+		"r0 = 1;"
+		"exit;"
+		::: __clobber_all);
+}
+
+/*
+ * These subprogs make 60000 iterations in each call. With a read of the clock after 65535
+ * iterations of a call none of them reads it, and their caller does it after
+ * 65535 * 60000 * 60000 iterations.
+ */
+__naked __noinline __used
+static unsigned long loops_60000(void)
+{
+	asm volatile (
+		"r1 = 60000;"
+	"1:"
+		"may_goto 2f;"
+		"r1 += -1;"
+		"if r1 != 0 goto 1b;"
+	"2:"
+		"r0 = 0;"
+		"exit;"
+		::: __clobber_all);
+}
+
+__naked __noinline __used
+static unsigned long calls_60000_times(void)
+{
+	asm volatile (
+		"r6 = 60000;"
+	"1:"
+		"call loops_60000;"
+		"may_goto 2f;"
+		"r6 += -1;"
+		"if r6 != 0 goto 1b;"
+	"2:"
+		"r0 = 0;"
+		"exit;"
+		::: __clobber_all);
+}
+
+SEC("socket")
+__description("timed may_goto: three levels of loops that end before they read the clock")
+__success __retval(1)
+__naked void three_levels_of_short_loops(void)
+{
+	asm volatile (
+	"1:"
+		"call calls_60000_times;"
+		"may_goto 2f;"
+		"goto 1b;"
+	"2:"
+		"r0 = 1;"
+		"exit;"
+		::: __clobber_all);
+}
+
+/* The callee ends one iteration before it reads the clock. */
+__naked __noinline __used
+static unsigned long loops_65534(void)
+{
+	asm volatile (
+		"r1 = 65534;"
+	"1:"
+		"may_goto 2f;"
+		"r1 += -1;"
+		"if r1 != 0 goto 1b;"
+	"2:"
+		"r0 = 0;"
+		"exit;"
+		::: __clobber_all);
+}
+
+SEC("socket")
+__description("timed may_goto: the subprog makes 65534 iterations")
+__success __retval(1)
+__naked void loop_calls_subprog_with_65534_iterations(void)
+{
+	asm volatile (
+		"call %[bpf_ktime_get_ns];"
+		"r6 = r0;"
+	"1:"
+		"call loops_65534;"
+		"may_goto 2f;"
+		"goto 1b;"
+	"2:"
+		"call %[bpf_ktime_get_ns];"
+		"r0 -= r6;"
+		"r1 = r0;"
+		"r0 = 1;"
+		"if r1 < 1000000000 goto +1;"
+		"r0 = 0;"
+		"exit;"
+		:
+		: __imm(bpf_ktime_get_ns)
+		: __clobber_all);
+}
+
+/* The subprog returns 16 bytes in R0 and R2. may_goto must not change them. */
+__naked __noinline __used
+static unsigned __int128 returns_pair_after_may_goto(void)
+{
+	asm volatile (
+		"r0 = 1;"
+		"r2 = 2;"
+	"1:"
+		"may_goto 2f;"
+		"goto 1b;"
+	"2:"
+		"exit;"
+		::: __clobber_all);
+}
+
+SEC("socket")
+__description("timed may_goto: the subprog returns 16 bytes")
+__success __retval(3)
+__naked void subprog_with_may_goto_returns_pair(void)
+{
+	asm volatile (
+		"call returns_pair_after_may_goto;"
+		"r0 += r2;"
+		"exit;"
+		::: __clobber_all);
+}
+
+/* Dead code doesn't count: a prog that has no may_goto left gets no insns. */
+__naked __noinline __used
+static unsigned long may_goto_is_dead_code(void)
+{
+	asm volatile (
+		"r0 = 0;"
+		"if r0 == 0 goto 2f;"
+	"1:"
+		"may_goto 2f;"
+		"goto 1b;"
+	"2:"
+		"exit;"
+		::: __clobber_all);
+}
+
+SEC("socket")
+__description("timed may_goto: may_goto in dead code")
+__success __retval(0)
+__xlated("0: call pc+1")
+__xlated("1: exit")
+__xlated("2: r0 = 0")
+__xlated("3: exit")
+__naked void dead_may_goto(void)
+{
+	asm volatile (
+		"call may_goto_is_dead_code;"
+		"exit;"
+		::: __clobber_all);
+}
+
+static __noinline int throws_after_spin(void)
+{
+	spin();
+	bpf_throw(0);
+	return 0;
+}
+
+__noinline int exception_cb_loops(u64 cookie)
+{
+	return counts_to_1000();
+}
+
+/* The exception callback belongs to the invocation that throws. */
+SEC("tc")
+__description("timed may_goto: bpf_throw() the exception callback has a loop")
+__exception_cb(exception_cb_loops)
+__success __retval(0)
+int throw_after_timeout(void *ctx)
+{
+	return throws_after_spin();
+}
+
+#else
+
+SEC("socket")
+__description("timed may_goto: not supported dummy test")
+__success
+int dummy_test(void)
+{
+	return 0;
+}
+
+#endif
diff --git a/tools/testing/selftests/bpf/progs/timed_may_goto_ext.c b/tools/testing/selftests/bpf/progs/timed_may_goto_ext.c
new file mode 100644
index 000000000000..969ca58b6eed
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/timed_may_goto_ext.c
@@ -0,0 +1,23 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <vmlinux.h>
+#include <bpf/bpf_helpers.h>
+#include "bpf_misc.h"
+#include "bpf_experimental.h"
+
+char _license[] SEC("license") = "GPL";
+
+static __noinline int spins(void)
+{
+	__u64 t0 = bpf_ktime_get_ns();
+
+	while (can_loop)
+		;
+	return bpf_ktime_get_ns() - t0 > 100 * 1000 * 1000;
+}
+
+/* Each call of an extension prog is an invocation: one of its two calls spins. */
+SEC("freplace")
+int replacement(int i)
+{
+	return spins() + spins() + i;
+}
diff --git a/tools/testing/selftests/bpf/progs/timed_may_goto_user.c b/tools/testing/selftests/bpf/progs/timed_may_goto_user.c
new file mode 100644
index 000000000000..8b85815d45d2
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/timed_may_goto_user.c
@@ -0,0 +1,311 @@
+// SPDX-License-Identifier: GPL-2.0
+/* The tests of timed_may_goto.c that need help from user space. */
+#include <vmlinux.h>
+#include <bpf/bpf_helpers.h>
+#include <bpf/bpf_tracing.h>
+#include "bpf_misc.h"
+#include "bpf_experimental.h"
+
+char _license[] SEC("license") = "GPL";
+
+#define TRIES 4
+#define CLOCK_MONOTONIC 1
+
+int zero;
+
+/* Return 1 if the loop went on until the time was up. */
+static __always_inline int spin(void)
+{
+	__u64 t0 = bpf_ktime_get_ns();
+
+	while (can_loop)
+		;
+	return bpf_ktime_get_ns() - t0 > 100 * 1000 * 1000;
+}
+
+static __noinline int spins(void)
+{
+	return spin();
+}
+
+static __noinline int counts_to_1000(void)
+{
+	int i, cnt = zero;
+
+	for (i = zero; i < 1000 && can_loop; i++)
+		cnt++;
+	return cnt;
+}
+
+/* Nothing special: the loops go on, then the time is up one time. */
+SEC("tc")
+int normal_prog(void *ctx)
+{
+	int i, n = 0;
+
+	if (counts_to_1000() != 1000)
+		return 100;
+	for (i = 0; i < TRIES; i++)
+		n += spins();
+	return n;
+}
+
+/*
+ * Async callbacks
+ */
+struct elem {
+	struct bpf_timer timer;
+	struct bpf_wq wq;
+	struct bpf_task_work tw;
+	struct bpf_rcu_head rcu;
+};
+
+struct {
+	__uint(type, BPF_MAP_TYPE_ARRAY);
+	__uint(max_entries, 2);
+	__type(key, int);
+	__type(value, struct elem);
+} async SEC(".maps");
+
+int timer_cnt, wq_cnt, tw_cnt, rcu_cnt, rcu_trace_cnt;
+
+static int timer_cb(void *map, int *key, struct elem *e)
+{
+	timer_cnt = counts_to_1000();
+	return 0;
+}
+
+static int wq_cb(void *map, int *key, void *val)
+{
+	wq_cnt = counts_to_1000();
+	return 0;
+}
+
+static int tw_cb(struct bpf_map *map, void *key, void *val)
+{
+	tw_cnt = counts_to_1000();
+	return 0;
+}
+
+static int rcu_cb(struct bpf_map *map, void *key, void *val)
+{
+	rcu_cnt = counts_to_1000();
+	return 0;
+}
+
+static int rcu_trace_cb(struct bpf_map *map, void *key, void *val)
+{
+	rcu_trace_cnt = counts_to_1000();
+	return 0;
+}
+
+/*
+ * The time of this prog is up when it starts the callbacks. User space keeps the task on the cpu,
+ * so the callbacks find what it has left. Each call of a callback is an invocation of its own.
+ */
+SEC("syscall")
+int async_after_timeout(void *ctx)
+{
+	struct task_struct *task = bpf_get_current_task_btf();
+	struct elem *e, *e1;
+	int key = 0, key1 = 1;
+
+	e = bpf_map_lookup_elem(&async, &key);
+	e1 = bpf_map_lookup_elem(&async, &key1);
+	if (!e || !e1)
+		return 100;
+	if (bpf_timer_init(&e->timer, &async, CLOCK_MONOTONIC) ||
+	    bpf_timer_set_callback(&e->timer, timer_cb))
+		return 101;
+	if (bpf_wq_init(&e->wq, &async, 0) || bpf_wq_set_callback(&e->wq, wq_cb, 0))
+		return 102;
+	if (!spins())
+		return 103;
+	/* control: the time is up */
+	if (counts_to_1000())
+		return 109;
+	if (bpf_timer_start(&e->timer, 0, BPF_F_TIMER_CPU_PIN))
+		return 104;
+	if (bpf_wq_start(&e->wq, 0))
+		return 105;
+	if (bpf_task_work_schedule_resume(task, &e->tw, &async, tw_cb))
+		return 106;
+	if (bpf_call_rcu(&e->rcu, &async, rcu_cb))
+		return 107;
+	if (bpf_call_rcu_tasks_trace(&e1->rcu, &async, rcu_trace_cb))
+		return 108;
+	return 0;
+}
+
+int ticks;
+
+static int tick_cb(void *map, int *key, struct elem *e)
+{
+	if (counts_to_1000() != 1000)
+		ticks = 1000;
+	if (++ticks < 100)
+		bpf_timer_start(&e->timer, 20 * 1000 * 1000, BPF_F_TIMER_CPU_PIN);
+	return 0;
+}
+
+/*
+ * A callback of the prog interrupts it, on the same cpu, each 20 ms. It has its own time. That
+ * doesn't give more time to the prog. Return how long the loop went on, in ms.
+ */
+SEC("syscall")
+int spin_under_timer(void *ctx)
+{
+	struct elem *e;
+	int key = 1;
+	__u64 t0;
+
+	e = bpf_map_lookup_elem(&async, &key);
+	if (!e)
+		return 0;
+	if (bpf_timer_init(&e->timer, &async, CLOCK_MONOTONIC) ||
+	    bpf_timer_set_callback(&e->timer, tick_cb) ||
+	    bpf_timer_start(&e->timer, 20 * 1000 * 1000, BPF_F_TIMER_CPU_PIN))
+		return 0;
+	t0 = bpf_ktime_get_ns();
+	while (can_loop)
+		;
+	return (bpf_ktime_get_ns() - t0) / 1000000;
+}
+
+/*
+ * Extension prog
+ */
+__noinline int replaced_global(int i)
+{
+	return spin() + i;
+}
+
+SEC("tc")
+int freplace_target(void *ctx)
+{
+	int i, n = 0;
+
+	for (i = 0; i < TRIES; i++)
+		n += replaced_global(zero);
+	return n;
+}
+
+/*
+ * Tail calls
+ */
+struct {
+	__uint(type, BPF_MAP_TYPE_PROG_ARRAY);
+	__uint(max_entries, 1);
+	__uint(key_size, sizeof(int));
+	__uint(value_size, sizeof(int));
+} jmp_table SEC(".maps");
+
+int tail_callee_spun;
+
+SEC("tc")
+int tail_callee(struct __sk_buff *skb)
+{
+	int i;
+
+	tail_callee_spun = 0;
+	for (i = 0; i < TRIES; i++)
+		tail_callee_spun += spins();
+	return 0;
+}
+
+static __noinline int tail_calls(struct __sk_buff *skb)
+{
+	bpf_tail_call(skb, &jmp_table, 0);
+	return zero + 100;
+}
+
+/* The target of the tail call is another prog. It returns to this function. */
+SEC("tc")
+int tail_call_in_subprog(struct __sk_buff *skb)
+{
+	int i, n;
+
+	n = tail_calls(skb);
+	if (counts_to_1000() != 1000)
+		return 101;
+	for (i = 0; i < TRIES; i++)
+		n += spins();
+	return n;
+}
+
+SEC("tc")
+int tail_call_after_timeout(struct __sk_buff *skb)
+{
+	spins();
+	bpf_tail_call(skb, &jmp_table, 0);
+	return 100;
+}
+
+static __noinline int throws(void)
+{
+	spin();
+	bpf_throw(7);
+	return 0;
+}
+
+SEC("tc")
+int throw_after_timeout(void *ctx)
+{
+	return throws();
+}
+
+/*
+ * bpf_user_ringbuf_drain()
+ */
+struct {
+	__uint(type, BPF_MAP_TYPE_USER_RINGBUF);
+	__uint(max_entries, 4096);
+} user_ringbuf SEC(".maps");
+
+static long drain_cb(struct bpf_dynptr *dynptr, int *spun)
+{
+	*spun += spin();
+	return 0;
+}
+
+SEC("syscall")
+int drain(void *ctx)
+{
+	int spun = 0;
+
+	return bpf_user_ringbuf_drain(&user_ringbuf, drain_cb, &spun, 0) * 10 + spun;
+}
+
+/*
+ * A tracing prog with large frames: they are in a private stack.
+ */
+int priv_stack_spun, priv_stack_cb_spun;
+
+static __noinline int spins_with_stack(void)
+{
+	volatile char buf[128] = {};
+
+	return spin() + buf[zero & 127];
+}
+
+static int priv_stack_cb(__u64 i, int *spun)
+{
+	volatile char buf[128] = {};
+
+	*spun += spin() + buf[zero & 127];
+	return 0;
+}
+
+SEC("fentry/bpf_fentry_test1")
+int BPF_PROG(priv_stack)
+{
+	volatile char buf[128] = {};
+	int i, n = buf[zero & 127], spun = 0;
+
+	for (i = 0; i < TRIES; i++)
+		n += spins_with_stack();
+	bpf_loop(TRIES, priv_stack_cb, &spun, zero);
+	priv_stack_spun = n;
+	priv_stack_cb_spun = spun;
+	return 0;
+}
-- 
2.55.0

Re: [PATCH bpf v2 9/9] selftests/bpf: Test one may_goto time slice per prog invocation

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Low] selftests/bpf: missing __skip() annotation on dummy_test() in timed_may_goto.c
--

commit 0a2b0627ab964341b75c457825392248b5fb88a8
Author: Alexei Starovoitov <ast@kernel.org>

selftests/bpf: Test one may_goto time slice per prog invocation

This commit adds BPF selftests verifying that a single may_goto time slice
is shared across an entire program invocation, including subprogs and
synchronous callbacks, and extends may_goto_far with subprog test cases.

> diff --git a/tools/testing/selftests/bpf/progs/timed_may_goto.c b/tools/testing/selftests/bpf/progs/timed_may_goto.c
> new file mode 100644
> index 0000000000000..c1c48af808a99
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/progs/timed_may_goto.c
> @@ -0,0 +1,898 @@

[ ... ]

> +#if (defined(__TARGET_ARCH_x86) || defined(__TARGET_ARCH_arm64)) && __clang_major__ >= 18

[ ... ]

> +#else
> +
> +SEC("socket")
> +__description("timed may_goto: not supported dummy test")
> +__success
> +int dummy_test(void)
> +{
> +	return 0;
> +}
> +
> +#endif

[Severity: Low]
Should dummy_test() in tools/testing/selftests/bpf/progs/timed_may_goto.c
also include a __skip(...) annotation?

When timed_may_goto.c is built on architectures other than x86_64 and arm64
or with GCC or Clang older than 18, serial_test_timed_may_goto() in
tools/testing/selftests/bpf/prog_tests/timed_may_goto.c runs
RUN_TESTS(timed_may_goto) and returns early. Without __skip(...) on
dummy_test(), test_loader executes the placeholder program and reports OK
instead of SKIP, unlike the other placeholder dummy_test() definitions
updated in commit 8928f5ffdb65 ("selftests/bpf: Report placeholder tests as
SKIP, not OK").

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261031215543.682284-1-alexei.starovoitov@gmail.com?part=9

Re: [PATCH bpf v2 7/9] bpf: One may_goto time slice per prog invocation

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
- [Medium] bpf: 16-bit jump offset overflow in may_goto_expand_timed() under blinding
- [Medium] bpf: torn reads of cb->prog and cb->callback_fn in timer and wq callbacks
--

commit 382d62c2e4ba7bcffedca7ed4f3c49e710163db0
Author: Alexei Starovoitov <ast@kernel.org>

bpf: One may_goto time slice per prog invocation

This commit moves the timed may_goto count and timestamp from each subprog's
stack frame into per-CPU memory owned by the main program so that a single
250 ms time slice applies across an entire program invocation. It also saves
and restores the per-CPU timed may_goto state around asynchronous callbacks.

> diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c
> index 5cbab55d84be0..66b9d1d9e961c 100644
> --- a/kernel/bpf/fixups.c
> +++ b/kernel/bpf/fixups.c
> @@ -1803,6 +1803,50 @@ static int may_goto_expand(struct bpf_insn *insn_buf, int off, int stack_off,
>  	return cnt + tail_cnt;
>  }
>  
> +/*
> + * Timed may_goto. All may_goto of a prog use one count and one timestamp: per-cpu memory of the
> + * prog, set in the first insns of the main prog, and by the callers of async callbacks.
> + * @reg holds the address. It is a register that is dead at the may_goto, or R0 that is saved at
> + * @save_off in the stack.
> + */
> +static int may_goto_expand_timed(struct bpf_insn *insn_buf, int off,
> +				 struct bpf_timed_may_goto __percpu *tmg, int reg, int save_off)
> +{
> +	struct bpf_insn ld_tmg[] = { BPF_LD_IMM64(reg, (__force unsigned long)tmg) };
> +	int cnt = 0, jmp, tail_cnt = save_off ? 6 : 5;
> +
> +	if (save_off)
> +		insn_buf[cnt++] = BPF_STX_MEM(BPF_DW, BPF_REG_10, reg, save_off);
> +	insn_buf[cnt++] = ld_tmg[0];
> +	insn_buf[cnt++] = ld_tmg[1];
> +	insn_buf[cnt++] = BPF_MOV64_PERCPU_REG(reg, reg);
> +	insn_buf[cnt++] = BPF_LDX_MEM(BPF_DW, BPF_REG_AX, reg, 0);
> +	if (save_off) {
> +		insn_buf[cnt++] = BPF_JMP_IMM(BPF_JNE, BPF_REG_AX, 0, 2);
> +		insn_buf[cnt++] = BPF_LDX_MEM(BPF_DW, reg, BPF_REG_10, save_off);
> +		jmp = cnt++;
> +		insn_buf[jmp] = BPF_JMP32_A(off >= 0 ? off + tail_cnt : off - jmp);
> +	} else {
> +		jmp = cnt;
> +		off = off >= 0 ? off + tail_cnt : off - jmp;
> +		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);
> +		}
> +	}

[Severity: Medium]
Can constant blinding cause the 16-bit jump offset in may_goto_expand_timed()
to overflow S16_MIN on backward branches?

When save_off is 0, may_goto_expand_timed() emits the 2-instruction
BPF_LD_IMM64(reg, tmg) into reg (one of BPF_REG_0..BPF_REG_9) before the
branch at jmp = 4. For a backward branch (orig_off < 0), off becomes
orig_off - 4, and if that fits in s16 (for example, orig_off in
[-32764, -32759]), it emits a 16-bit BPF_JMP_IMM(BPF_JEQ, BPF_REG_AX, 0, off)
instead of BPF_JMP32_A.

Later, when JIT constant blinding is enabled,
bpf_jit_blind_constants() -> bpf_jit_blind_insn() expands the 2-instruction
BPF_LD_IMM64(reg, tmg) into 7 or 8 instructions:

kernel/bpf/core.c:bpf_jit_blind_insn() {
	...
	case BPF_LD | BPF_IMM | BPF_DW:
		*to++ = BPF_ALU64_IMM(BPF_MOV, BPF_REG_AX, imm_rnd ^ aux[1].imm);
		*to++ = BPF_ALU64_IMM(BPF_XOR, BPF_REG_AX, imm_rnd);
		*to++ = BPF_ALU64_IMM(BPF_LSH, BPF_REG_AX, 32);
		*to++ = BPF_ALU64_REG(BPF_MOV, aux[0].dst_reg, BPF_REG_AX);
		break;
	case 0: /* Part 2 of BPF_LD | BPF_IMM | BPF_DW. */
		*to++ = BPF_ALU32_IMM(BPF_MOV, BPF_REG_AX, imm_rnd ^ aux[0].imm);
		*to++ = BPF_ALU32_IMM(BPF_XOR, BPF_REG_AX, imm_rnd);
		if (emit_zext)
			*to++ = BPF_ZEXT_REG(BPF_REG_AX);
		*to++ = BPF_ALU64_REG(BPF_OR,  aux[0].dst_reg, BPF_REG_AX);
		break;
}

Because those 5 or 6 extra instructions are inserted between a backward jump
target and the 16-bit BPF_JEQ, bpf_adj_branches() -> bpf_adj_delta_to_off()
subtracts 5 or 6 from the 16-bit offset, underflowing S16_MIN and failing
blinding with -ERANGE. Since bpf_do_misc_fixups() sets prog->jit_required = 1,
the program cannot fall back to the interpreter and fails to load.

[ ... ]

> diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c
> index 58e357302850e..2b75f7ba07a56 100644
> --- a/kernel/bpf/helpers.c
> +++ b/kernel/bpf/helpers.c
> @@ -1222,6 +1222,8 @@ static enum hrtimer_restart bpf_timer_cb(struct hrtimer *hrtimer)
>  {
>  	struct bpf_hrtimer *t = container_of(hrtimer, struct bpf_hrtimer, timer);
>  	struct bpf_map *map = READ_ONCE(t->cb.map);
> +	struct bpf_prog *prog = READ_ONCE(t->cb.prog);
> +	struct bpf_timed_may_goto saved;
>  	void *value = t->cb.value;
>  	bpf_callback_t callback_fn;
>  	void *key;
> @@ -1229,7 +1231,7 @@ static enum hrtimer_restart bpf_timer_cb(struct hrtimer *hrtimer)
>  
>  	BTF_TYPE_EMIT(struct bpf_timer);
>  	callback_fn = rcu_dereference_check(t->cb.callback_fn, rcu_read_lock_bh_held());
> -	if (!callback_fn || !map)
> +	if (!callback_fn || !map || !prog)
>  		goto out;
>  
>  	/* bpf_timer_cb() runs in hrtimer_run_softirq. It doesn't migrate and
> @@ -1242,8 +1244,10 @@ static enum hrtimer_restart bpf_timer_cb(struct hrtimer *hrtimer)
>  
>  	key = map_key_from_value(map, value, &idx);
>  
> +	bpf_timed_may_goto_save(prog, &saved);
>  	callback_fn((u64)(long)map, (u64)(long)key, (u64)(long)value, 0, 0);
>  	/* The verifier checked that return value is zero. */
> +	bpf_timed_may_goto_restore(prog, &saved);
>  
>  	this_cpu_write(hrtimer_running, NULL);
>  out:
> @@ -1254,6 +1258,8 @@ static void bpf_wq_work(struct work_struct *work)
>  {
>  	struct bpf_work *w = container_of(work, struct bpf_work, work);
>  	struct bpf_async_cb *cb = &w->cb;
> +	struct bpf_timed_may_goto saved;
> +	struct bpf_prog *prog;
>  	struct bpf_map *map;
>  	bpf_callback_t callback_fn;
>  	void *value = cb->value;
> @@ -1267,14 +1273,17 @@ static void bpf_wq_work(struct work_struct *work)
>  
>  	map = READ_ONCE(cb->map);
>  	callback_fn = READ_ONCE(cb->callback_fn);
> -	if (!callback_fn || !map)
> +	prog = READ_ONCE(cb->prog);
> +	if (!callback_fn || !map || !prog)
>  		goto out;
>  
>  	key = map_key_from_value(map, value, &idx);
>  
>  	migrate_disable();
>  
> +	bpf_timed_may_goto_save(prog, &saved);
>  	callback_fn((u64)(long)map, (u64)(long)key, (u64)(long)value, 0, 0);
> +	bpf_timed_may_goto_restore(prog, &saved);

[Severity: Medium]
What prevents bpf_timer_cb() and bpf_wq_work() from reading a mismatched pair
of cb->prog and cb->callback_fn when bpf_async_update_prog_callback() runs
concurrently?

In bpf_async_update_prog_callback(), cb->prog and cb->callback_fn are updated
with two separate lockless stores:

kernel/bpf/helpers.c:bpf_async_update_prog_callback() {
	...
	do {
		if (prog)
			prog = bpf_prog_inc_not_zero(prog);
		prev = xchg(&cb->prog, prog);
		rcu_assign_pointer(cb->callback_fn, callback_fn);
	...
}

When two programs share a map containing a bpf_timer or bpf_wq and update the
callback concurrently while the timer or workqueue fires, bpf_timer_cb() or
bpf_wq_work() can read prog from one program and callback_fn from the other.

If that happens, bpf_timed_may_goto_save() and bpf_timed_may_goto_restore()
will save, initialize, and restore the wrong program's per-CPU
timed_may_goto state while callback_fn accesses its own program's
timed_may_goto. If the callback's program still has count == 0 on this CPU
(because its main program has not run on this CPU yet or previously timed
out), its timed may_goto loops will terminate immediately on the first
iteration, or if it interrupted its own main program on the same CPU, the
interrupted invocation's count and timestamp will not be saved and restored.

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261031215543.682284-1-alexei.starovoitov@gmail.com?part=7

Re: [PATCH bpf v2 5/9] s390/bpf: Support internal-only MOV instruction to resolve per-CPU addrs

[bot+bpf-ci]

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

> s390/bpf: Support internal-only MOV instruction to resolve per-CPU addrs

TL;DR: Commit message only, not a bug: the "Patch 7" reference will be
meaningless once the series is applied; suggest naming the commit that needs
this insn for timed may_goto.

>     s390/bpf: Support internal-only MOV instruction to resolve per-CPU addrs
>
>     The verifier emits BPF_MOV64_PERCPU_REG to turn the address of a per-cpu
>     variable into the address of the copy of this cpu. s390 keeps the per-cpu
>     offset of the cpu in the lowcore. Add it to the register with one insn, the
>     way the JIT reads cpu_nr and current_task for the helpers that it inlines.
>
>     With bpf_jit_supports_percpu_insn() the verifier inlines the lookup in
>     per-cpu array and per-cpu hash maps, and resolves the address of a value in
>     a per-cpu array. Patch 7 needs the insn for may_goto.
>
>     Signed-off-by: Alexei Starovoitov <ast@kernel.org>

this isn't a bug, but could the "Patch 7" reference be reworded to say which
change needs this insn, for example "a following commit uses it for timed
may_goto"?

The patch numbers are lost once the series is applied.  The change being
referred to appears to be "bpf: One may_goto time slice per prog invocation",
which emits BPF_MOV64_PERCPU_REG for the shared may_goto count, so that commit
could also be named directly.


---
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/41246505049

Re: [PATCH bpf v2 7/9] bpf: One may_goto time slice per prog invocation

[Alexei Starovoitov]

On Sat, Oct 31, 2026 at 03:25 PM sashiko-bot@kernel.org <sashiko-bot@kernel.org> wrote:
>> +		off = off >= 0 ? off + tail_cnt : off - jmp;
>> +		if (off == (s16)off) {
>> +			insn_buf[cnt++] = BPF_JMP_IMM(BPF_JEQ, BPF_REG_AX, 0, off);
>
> [Severity: Medium]
> Can constant blinding cause the 16-bit jump offset in may_goto_expand_timed()
> to overflow S16_MIN on backward branches?

Not a bug. That's the limit of blinding, not of may_goto.
Blinding adds 2 insns to each insn with a constant. A loop body of 32K
insns with five constants in it fails with the same -ERANGE before this
patch. Every conditional jump of a prog has this limit.

[...]

>> +	bpf_timed_may_goto_save(prog, &saved);
>>  	callback_fn((u64)(long)map, (u64)(long)key, (u64)(long)value, 0, 0);
>> +	bpf_timed_may_goto_restore(prog, &saved);
>
> [Severity: Medium]
> What prevents bpf_timer_cb() and bpf_wq_work() from reading a mismatched pair
> of cb->prog and cb->callback_fn when bpf_async_update_prog_callback() runs
> concurrently?

Nothing. The race is there, but it's harmless.
Two progs have to set a callback on the same timer at the moment when it
fires. Then the callback uses the count and timestamp that its prog left
on this cpu. Nobody sets them anew, so the callback gets less time, never
more. The limit of 250 ms holds. The other prog gets its values back.

Re: [PATCH bpf v2 9/9] selftests/bpf: Test one may_goto time slice per prog invocation

[Alexei Starovoitov]

On Sat, Oct 31, 2026 at 03:12 PM sashiko-bot@kernel.org <sashiko-bot@kernel.org> wrote:
> - [Low] selftests/bpf: missing __skip() annotation on dummy_test() in timed_may_goto.c

Not worth a respin.
It's OK vs SKIP in the report on archs where the tests don't run.

Re: [PATCH bpf v2 7/9] bpf: One may_goto time slice per prog invocation

[bot+bpf-ci]

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

> bpf: One may_goto time slice per prog invocation

TL;DR: Each main-prog entry resets the shared per-cpu may_goto state, so a
nested invocation (or one interrupting an async callback) may restart the 250
ms slice repeatedly, letting loops spin unbounded and causing soft lockups.

> diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c
> index 5cbab55d84be..66b9d1d9e961 100644
> --- a/kernel/bpf/fixups.c
> +++ b/kernel/bpf/fixups.c

[ ... ]

> @@ -2734,24 +2767,36 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
>
>  	env->prog->aux->stack_depth = subprogs[0].stack_depth;
>  	for (i = 0; i < env->subprog_cnt; i++) {

[ ... ]

> +		/* an invocation begins, see bpf_timed_may_goto_save() for async callbacks */
> +		bool main_prog = tmg && !i;

[ ... ]

>  		stack_depth = subprogs[i].stack_depth;
>  		if (timed_may_goto) {
> +			struct bpf_insn ld_tmg[] = {
> +				BPF_LD_IMM64(BPF_REG_0, (__force unsigned long)tmg)
> +			};
> +			int count_off = offsetof(struct bpf_timed_may_goto, count);
> +			int timestamp_off = offsetof(struct bpf_timed_may_goto, timestamp);
> +			int owner_off = offsetof(struct bpf_timed_may_goto, owner);
> +
> +			/* R0 has nothing at the entry */
> +			insn_buf[cnt++] = ld_tmg[0];
> +			insn_buf[cnt++] = ld_tmg[1];
> +			insn_buf[cnt++] = BPF_MOV64_PERCPU_REG(BPF_REG_0, BPF_REG_0);
> +			insn_buf[cnt++] = BPF_ST_MEM(BPF_DW, BPF_REG_0, count_off,
>  						     BPF_MAX_TIMED_LOOPS);
> +			insn_buf[cnt++] = BPF_ST_MEM(BPF_DW, BPF_REG_0, timestamp_off, 0);
> +			insn_buf[cnt++] = BPF_ST_MEM(BPF_DW, BPF_REG_0, owner_off, 0);

Can a nested invocation of the same prog extend the time slice of the
invocation it interrupted without bound?

Every entry into the main prog now writes count = BPF_MAX_TIMED_LOOPS and
timestamp = 0 into the per-cpu struct bpf_timed_may_goto that is shared with
every other invocation of that prog on the same CPU, and nothing puts the
old values back when that invocation returns.  Only the async callers,
bpf_timed_may_goto_save() and bpf_timed_may_goto_restore(), save and
restore.

bpf_check_timed_may_goto() treats timestamp == 0 as "start a new 250 ms
window", so after each nested entry the interrupted loop gets a full new
slice.  If nested entries keep coming more often than every 250 ms, the
interrupted loop never reaches the timeout.  Before this patch the count
and timestamp were in the stack frame of each invocation, so nesting could
not touch them.

There are two ways the same prog can nest on one CPU.

First, an async callback interrupted by the main prog.  bpf_timer_cb()
(softirq), bpf_wq_work() (kworker, migration disabled) and
bpf_task_work_callback() run callback_fn without taking prog->active.  So
bpf_prog_get_recursion_context() in __bpf_trace_run(), or the trampoline
recursion check, does not stop a main invocation of the same prog from
running in hardirq or softirq on top of the callback.  Each such entry runs
the prologue above, which sets owner = 0 and resets count and timestamp.
The callback's while (can_loop) loop then starts over, and its restore is
skipped because cur->owner != &saved.  Example: a tp_btf prog on a frequent
hardirq tracepoint with a bpf_timer callback, or an XDP prog with a bpf_wq
callback while traffic arrives on that CPU.

Second, main over main, for prog types without per-prog recursion
protection.  For example, a cgroup_skb egress prog runs from process
context with BH enabled (bpf_prog_run_array_cg() only does
migrate_disable() and rcu_read_lock()) and also from softirq (TCP ACKs and
retransmits, or ingress when the same prog is attached there too).

In both cases the outer loop can spin with no bound.  On
PREEMPT_NONE/VOLUNTARY that is the soft lockup this commit is meant to
prevent.

The commit message says "A second invocation of the prog on the same cpu
gives more time to the first one".  But each nested entry restarts the
whole window, so the extra time is unbounded, not a one-off extension.  The
later commit 954996f5c8be ("bpf: End bpf_loop() when the time of may_goto
is up") in the same series does not change this.

Should the main prog entry save and restore the state the way the async
callers do, or only reset it when no invocation owns the state?

[ ... ]

> diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c
> index 58e357302850..2b75f7ba07a5 100644
> --- a/kernel/bpf/helpers.c
> +++ b/kernel/bpf/helpers.c
> @@ -1222,6 +1222,8 @@ static enum hrtimer_restart bpf_timer_cb(struct hrtimer *hrtimer)
>  {

[ ... ]

> @@ -1242,8 +1244,10 @@ static enum hrtimer_restart bpf_timer_cb(struct hrtimer *hrtimer)
>
>  	key = map_key_from_value(map, value, &idx);
>
> +	bpf_timed_may_goto_save(prog, &saved);
>  	callback_fn((u64)(long)map, (u64)(long)key, (u64)(long)value, 0, 0);
>  	/* The verifier checked that return value is zero. */
> +	bpf_timed_may_goto_restore(prog, &saved);

Does the save/restore pair here protect the callback from an invocation of
the main prog that interrupts it?

Before this patch an async callback subprog containing may_goto set up its
own count and timestamp in its own stack frame, so nothing else could reset
them and its loops ended after 250 ms.  After this patch the callback has
no prologue.  It uses the per-cpu prog->aux->timed_may_goto that
bpf_timed_may_goto_save() resets here, and the first insns of the main prog
of the same prog write to that same memory on every invocation
(bpf_do_misc_fixups(), the main_prog prologue):

    insn_buf[cnt++] = BPF_ST_MEM(BPF_DW, BPF_REG_0, count_off, BPF_MAX_TIMED_LOOPS);
    insn_buf[cnt++] = BPF_ST_MEM(BPF_DW, BPF_REG_0, timestamp_off, 0);
    insn_buf[cnt++] = BPF_ST_MEM(BPF_DW, BPF_REG_0, owner_off, 0);

The save/restore pair protects an invocation that the callback interrupts.
It does not protect the callback from an invocation of the main prog that
interrupts it.  Each such invocation sets timestamp back to 0, and
bpf_check_timed_may_goto() then just takes a new timestamp:

    if (!p->timestamp) {
        p->timestamp = time;
        return BPF_MAX_TIMED_LOOPS;
    }

So if the prog is invoked on the CPU at least once every 250 ms while the
callback is looping, the time check never fires and the loop never ends.
Nothing stops this nesting: bpf_timer_cb() increments neither
bpf_prog_active nor prog->active, so trace_call_bpf() and
__bpf_prog_enter_recur() let the same prog run in hardirq while its timer
callback is running in softirq.

Example: a kprobe or fentry prog P on a function in the tick or irq path
(bpf_timer_* are in bpf_base_func_proto, and nothing in the verifier keeps
tracing progs from using timers any more) arms a timer whose callback runs
while (can_loop) {...}.  The tick invokes P every 1-4 ms on that CPU, the
callback loops forever in HRTIMER_SOFTIRQ, and the result is a soft lockup
or an RCU stall.  That is the failure this patch is meant to fix.

The same applies to the other three callers changed in this file:

- bpf_wq_work() and bpf_task_work_callback() run in task context with BH
  enabled.  A TC or XDP invocation of the same prog in NET_RX softirq on
  that CPU resets the state on every packet (common_kfunc_set, which holds
  bpf_wq_* and bpf_task_work_*, is registered for BPF_PROG_TYPE_UNSPEC).
  The kworker then runs forever with migration disabled and
  rcu_read_lock_trace held: a soft lockup on non-preemptible kernels, and a
  tasks-trace RCU stall on any kernel.

- bpf_rcu_run_callback() has the same problem with hardirq invocations.

The commit message says "A second invocation of the prog on the same cpu
gives more time to the first one", but with periodic invocations the extra
time has no bound.  Neither 954996f5c8be ("bpf: End bpf_loop() when the
time of may_goto is up") nor 837f057a25f6 ("selftests/bpf: Test one
may_goto time slice per prog invocation") later in the series changes this.

Should an async callback be protected from main-prog invocations too?  For
example, the main prog prologue could leave count and timestamp alone while
owner is set, or the async callers could mark the prog as active so that a
nested invocation of it is skipped.


---
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/41246505049

Re: [PATCH bpf v2 7/9] bpf: One may_goto time slice per prog invocation

[Alexei Starovoitov]

On Sat, Oct 31, 2026 at 03:37 PM bot+bpf-ci@kernel.org <bot+bpf-ci@kernel.org> wrote:
>> +			insn_buf[cnt++] = BPF_ST_MEM(BPF_DW, BPF_REG_0, timestamp_off, 0);
>> +			insn_buf[cnt++] = BPF_ST_MEM(BPF_DW, BPF_REG_0, owner_off, 0);
>
> Can a nested invocation of the same prog extend the time slice of the
> invocation it interrupted without bound?

It's already explained in the log and in the cover letter.

> Should an async callback be protected from main-prog invocations too?  For
> example, the main prog prologue could leave count and timestamp alone while
> owner is set, or the async callers could mark the prog as active so that a
> nested invocation of it is skipped.

Same limitation. Both ideas cost more than they fix.