[PATCH bpf-next 0/8] bpf: Verify loops without walking every iteration

[PATCH bpf-next 0/8] bpf: Verify loops without walking every iteration

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

This is RFC, but without RFC tag. See patch 6 for numbers.
I can clean it up for core idea looks good.

bot time...

The verifier walks a bounded loop one iteration at a time. The work is
proportional to the number of iterations, and the loop with too many of
them is rejected with "BPF program is too large" no matter how simple
it is.

Verify loops the way open coded iterators are verified. The state that
comes back to the loop head is either within the state that went around
the loop, and then there is nothing new to see, or its scalars are widened
and it goes around again. The range of the counter ends at the constant
the loop compares it with, so that a loop like

  for (i = 0; i != 1000000; i += 4)
          sum += *(u32 *)(val + i);

is verified in two trips around the loop and 24 insns.

The loop that is verified this way is not known to terminate:
 - if no state leaves the loop the program never leaves it either.
   Such loop is rejected as before.
 - otherwise the verifier adds may_goto to the back-edge. When may_goto
   is out of budget the program ends with bpf_throw(). Loops that go
   through may_goto or iterator already, and loops that are walked to the
   end are not touched.

Patch 1 trims range ends to var_off members. Without it the loop above
doesn't converge: the range of 'i' is [4, 1000003] after 'i += 4' and
'!=' cannot cut it.
Patch 2 marks loop heads.
Patch 3 widens states at loop heads.
Patch 4 detects loops that never exit.
Patch 5 adds may_goto.
Patch 6 turns it all on.
Patches 7 and 8 are selftests.

Widening gives up precision and bpf_throw() cannot be called everywhere,
so patch 6 walks the program with widening first and walks it the old
way when that fails. Nothing that is accepted today is rejected.
veristat for selftests (5251 programs):
 - 4 programs that were rejected are accepted: loop3/while_true,
   verifier_cfg/conditional_loop, verifier_movsx/mov64sx_s32_varoff_1,
   verifier_search_pruning/short_loop1. All have may_goto added.
 - 163 programs have different stats. 126 programs are walked twice and
   have the same stats as before.
 - insns processed in programs accepted before and after:
   5569499 -> 4774715 plus 88708 in walks that failed (-12.7%).
   loop1/nested_loops 361349 -> 135.
Patches 1-5 alone don't change stats of any program.

Not done:
 - pointers are not widened, only scalars. The loop that advances
   a pointer is walked every iteration.
 - constants that the counter is compared with come from 'if rX op imm'
   only. The bound in a register is not used.
 - may_goto is added to every loop that converged, also to the one that
   is bounded by its counter. It is a few insns per iteration.
 - when the program is rejected or has a loop that cannot have may_goto
   all of it is walked twice. The second walk of the rejected program
   can take 1M insns.

Alexei Starovoitov (8):
  bpf: Trim range ends to var_off members
  bpf: Mark loop heads in check_cfg()
  bpf: Widen scalars at loop heads
  bpf: Detect loops that never exit
  bpf: Add may_goto to loops that are not walked to the end
  bpf: Walk loops with widened states first
  selftests/bpf: Adjust tests to widened loops
  selftests/bpf: Add tests for widened loops

 include/linux/bpf_verifier.h                  |  31 +
 kernel/bpf/cfg.c                              |   8 +-
 kernel/bpf/fixups.c                           | 153 +++++
 kernel/bpf/states.c                           | 144 ++++-
 kernel/bpf/verifier.c                         | 609 +++++++++++++++++-
 .../bpf/prog_tests/bpf_verif_scale.c          |   4 +-
 .../selftests/bpf/prog_tests/verifier.c       |   2 +
 .../selftests/bpf/progs/verifier_cfg.c        |   4 +-
 .../selftests/bpf/progs/verifier_loop_widen.c | 344 ++++++++++
 .../selftests/bpf/progs/verifier_movsx.c      |   2 +-
 .../selftests/bpf/progs/verifier_precision.c  |  29 +-
 .../bpf/progs/verifier_search_pruning.c       |   3 +-
 tools/testing/selftests/bpf/verifier/calls.c  |   5 +-
 13 files changed, 1306 insertions(+), 32 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_loop_widen.c


base-commit: 91f8613d95ad8cd99d8baf094806d1ef98bc6380
-- 
2.55.0

[PATCH bpf-next 1/8] bpf: Trim range ends to var_off members

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

__update_reg{32,64}_bounds() intersect the range with [tnum min, tnum max],
but the ends of the result can still be values that are not members of
var_off. For example var_off=(0x0; 0xfc) umax=255 where 252 is the largest
possible value.

Move both ends of r64 and r32 inwards to the nearest member of var_off.
Values dropped from the ends are not members of var_off, so the set of
values described by the register doesn't change. If the range has no
member of var_off it is left as is.

It matters when a loop counter is tracked as a range. In the loop:

  13: (07) r6 += 4
  14: (55) if r6 != 0x190 goto pc-5

r6 of [0, 399] with var_off=(0x0; 0x1fc) at the loop head becomes
[4, 403] after insn 13 and insn 14 cannot cut it. With the ends trimmed
the ranges are [0, 396] and [4, 400]. Insn 14 cuts 400 off and r6 that
goes back to the loop head is within the range it started with.

No veristat changes in selftests.

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

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index a7c9e2d8965d..cb5d498ada69 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2094,9 +2094,71 @@ static struct cnum64 cnum64_from_tnum(struct tnum tnum)
 		return cnum64_from_urange(tnum.value, (tnum.value | tnum.mask));
 }
 
+/* smallest member of @t that is >= @x, wraps around to the smallest member of @t */
+static u64 tnum_member_ge(struct tnum t, u64 x)
+{
+	if ((x & ~t.mask) == t.value)
+		return x;
+	if (x > (t.value | t.mask))
+		return t.value;
+	return tnum_step(t, x);
+}
+
+/* largest member of @t that is <= @x, wraps around to the largest member of @t */
+static u64 tnum_member_le(struct tnum t, u64 x)
+{
+	/* members of 'tc' are bitwise complements of members of 't' */
+	struct tnum tc = { .value = ~(t.value | t.mask), .mask = t.mask };
+
+	return ~tnum_member_ge(tc, ~x);
+}
+
+/*
+ * Move both ends of arc @c inwards to the nearest members of @t.
+ * Values that are dropped are not members of @t.
+ */
+static struct cnum64 cnum64_tighten_by_tnum(struct cnum64 c, struct tnum t)
+{
+	u64 lo, hi, dlo, dhi;
+
+	if (cnum64_is_empty(c) || c.size == U64_MAX || !t.mask)
+		return c;
+	lo = tnum_member_ge(t, c.base);
+	dlo = lo - c.base;
+	if (dlo > c.size)
+		return c;
+	hi = tnum_member_le(t, c.base + c.size);
+	dhi = c.base + c.size - hi;
+	if (dhi > c.size - dlo)
+		return c;
+	return (struct cnum64){ .base = lo, .size = c.size - dlo - dhi };
+}
+
+static struct cnum32 cnum32_tighten_by_tnum(struct cnum32 c, struct tnum t)
+{
+	struct tnum tc;
+	u32 lo, hi, dlo, dhi;
+
+	t = tnum_subreg(t);
+	if (cnum32_is_empty(c) || c.size == U32_MAX || !t.mask)
+		return c;
+	lo = tnum_member_ge(t, c.base);
+	dlo = lo - c.base;
+	if (dlo > c.size)
+		return c;
+	/* complement within 32 bits */
+	tc = (struct tnum){ .value = (u32)~(t.value | t.mask), .mask = t.mask };
+	hi = ~(u32)tnum_member_ge(tc, (u32)~(c.base + c.size));
+	dhi = c.base + c.size - hi;
+	if (dhi > c.size - dlo)
+		return c;
+	return (struct cnum32){ .base = lo, .size = c.size - dlo - dhi };
+}
+
 static void __update_reg32_bounds(struct bpf_reg_state *reg)
 {
 	cnum32_intersect_with(&reg->r32, cnum32_from_tnum(reg->var_off));
+	reg->r32 = cnum32_tighten_by_tnum(reg->r32, reg->var_off);
 }
 
 static void __update_reg64_bounds(struct bpf_reg_state *reg)
@@ -2105,6 +2167,7 @@ static void __update_reg64_bounds(struct bpf_reg_state *reg)
 	bool umin_in_tnum;
 
 	cnum64_intersect_with(&reg->r64, cnum64_from_tnum(reg->var_off));
+	reg->r64 = cnum64_tighten_by_tnum(reg->r64, reg->var_off);
 
 	/* Check if u64 and tnum overlap in a single value */
 	tnum_next = tnum_step(reg->var_off, reg_umin(reg));
-- 
2.55.0

[PATCH bpf-next 2/8] bpf: Mark loop heads in check_cfg()

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

check_cfg() finds back-edges while it walks the control flow graph.
Remember their targets as loop heads and which edge of the insn is
the back-edge. The main pass needs it to tell the state that enters
the loop from the state that went around it.
No functional change.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 include/linux/bpf_verifier.h | 3 +++
 kernel/bpf/cfg.c             | 8 +++++++-
 2 files changed, 10 insertions(+), 1 deletion(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 92f528c45605..5a08f079a489 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -709,6 +709,9 @@ struct bpf_insn_aux_data {
 	u32 non_stack_access:1; /* instruction can access non-stack memory */
 	/* true if some jump or call instruction targets this instruction */
 	u32 jump_target:1;
+	u32 loop_head:1; /* target of a back-edge */
+	u32 backedge_ft:1; /* the edge to the next insn is a back-edge */
+	u32 backedge_br:1; /* the jump is a back-edge */
 	/*
 	 * CFG strongly connected component this instruction belongs to,
 	 * zero if it is a singleton SCC.
diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
index 842c7d1eabcc..748bf544d3ba 100644
--- a/kernel/bpf/cfg.c
+++ b/kernel/bpf/cfg.c
@@ -137,8 +137,14 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env)
 		insn_stack[env->cfg.cur_stack++] = w;
 		return KEEP_EXPLORING;
 	} else if ((insn_state[w] & 0xF0) == DISCOVERED) {
-		if (env->bpf_capable)
+		if (env->bpf_capable) {
+			env->insn_aux_data[w].loop_head = true;
+			if (e == FALLTHROUGH)
+				env->insn_aux_data[t].backedge_ft = true;
+			else
+				env->insn_aux_data[t].backedge_br = true;
 			return DONE_EXPLORING;
+		}
 		verbose_linfo(env, t, "%d: ", t);
 		verbose_linfo(env, w, "%d: ", w);
 		verbose(env, "back-edge from insn %d to %d\n", t, w);
-- 
2.55.0

[PATCH bpf-next 3/8] bpf: Widen scalars at loop heads

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

The verifier walks a bounded loop one iteration at a time. The work is
proportional to the number of iterations and the loop with 250k of them
is rejected with "BPF program is too large".

Let the state that comes back to the loop head stand for all iterations
the way it is done for open coded iterators. In is_state_visited():
 - if the state is within the state that went around the loop nothing
   new can happen on the next trip. Record SCC backedge and stop.
 - otherwise widen scalars in registers and spilled registers and go
   around the loop again.

widen_reg() takes the range that covers both states. The end that moved
is moved further to the nearest constant (imm - 1, imm, imm + 1) the
register is compared with inside the loop. Low bits of var_off that
are the same in both states are kept. In the loop:

   9: (b7) r6 = 0
  10: (bf) r1 = r7
  11: (0f) r1 += r6
  12: (61) r0 = *(u32 *)(r1 +0)
  13: (07) r6 += 4
  14: (55) if r6 != 0xf4240 goto pc-5

the second trip starts with
  R6=scalar(smin=0,smax=umax=0xf423c,var_off=(0x0; 0xffffc))
and the state that comes back is within it.

The first 4 trips use constants of the loop, the next 2 use S32_MIN, 0,
S32_MAX, U32_MAX, then the bound is dropped. Pointers and stack slots
other than spilled scalars are not widened. If that is what differs
the walk is given up after 10 trips.

The state that repeats exactly is treated as converged too instead of
"infinite loop detected". The loop that is not walked to the end is not
known to terminate. The next patches reject such loop when nothing
leaves it and add may_goto to it otherwise.

Nothing sets env->widen_loops yet.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 include/linux/bpf_verifier.h |  11 ++
 kernel/bpf/states.c          |  75 ++++++++-
 kernel/bpf/verifier.c        | 291 ++++++++++++++++++++++++++++++++++-
 3 files changed, 374 insertions(+), 3 deletions(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 5a08f079a489..981902cd5b71 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -527,6 +527,8 @@ struct bpf_verifier_state {
 	u32 dfs_depth;
 	u32 callback_unroll_depth;
 	u32 may_goto_depth;
+	/* number of times the loop head this state is a checkpoint of was widened */
+	u32 loop_passes;
 };
 
 static inline struct bpf_reg_state *
@@ -1049,6 +1051,12 @@ struct bpf_verifier_env {
 	/* array of pointers to bpf_scc_info indexed by SCC id */
 	struct bpf_scc_info **scc_info;
 	u32 scc_cnt;
+	/* per SCC constants that loop counters are compared with, see bpf_widen_loop_head() */
+	struct bpf_widen_thrs **scc_thrs;
+	/* states that come back to a loop head are widened instead of walking every iteration */
+	bool widen_loops;
+	/* the walk did or tried that, so a failure can be due to the lost precision */
+	bool widen_used;
 	struct bpf_iarray *succ;
 	struct bpf_iarray *gotox_tmp_buf;
 };
@@ -1221,6 +1229,9 @@ void bpf_free_kfunc_btf_tab(struct bpf_kfunc_btf_tab *tab);
 int mark_chain_precision(struct bpf_verifier_env *env, int regno);
 
 int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx);
+bool bpf_same_loop(struct bpf_verifier_state *old, struct bpf_verifier_state *cur);
+int bpf_widen_loop_head(struct bpf_verifier_env *env, int insn_idx, bool backedge,
+			struct bpf_verifier_state *old, struct bpf_verifier_state *cur);
 int bpf_update_branch_counts(struct bpf_verifier_env *env, struct bpf_verifier_state *st);
 
 void bpf_clear_jmp_history(struct bpf_verifier_state *state);
diff --git a/kernel/bpf/states.c b/kernel/bpf/states.c
index 66fb11b6c6a7..22987ce070e7 100644
--- a/kernel/bpf/states.c
+++ b/kernel/bpf/states.c
@@ -1108,6 +1108,41 @@ static int propagate_backedges(struct bpf_verifier_env *env, struct bpf_scc_visi
 	return 0;
 }
 
+/* Did the walk get to @insn_idx over a back-edge? */
+static bool is_backedge(struct bpf_verifier_env *env, int insn_idx)
+{
+	int prev = env->prev_insn_idx;
+	struct bpf_insn_aux_data *aux;
+	struct bpf_insn *insn;
+
+	if (prev < 0 || prev >= env->prog->len)
+		return false;
+	aux = &env->insn_aux_data[prev];
+	insn = &env->prog->insnsi[prev];
+	/* check_cfg() does not record the edge of an unconditional jump as a jump */
+	if ((BPF_CLASS(insn->code) == BPF_JMP || BPF_CLASS(insn->code) == BPF_JMP32) &&
+	    BPF_OP(insn->code) == BPF_JA)
+		return aux->backedge_ft || aux->backedge_br;
+	return insn_idx == prev + 1 ? aux->backedge_ft : aux->backedge_br;
+}
+
+/* The state of this walk that was the last to get to loop head @insn_idx. */
+static struct bpf_verifier_state *loop_head_state(struct bpf_verifier_env *env, int insn_idx)
+{
+	struct bpf_verifier_state *cur = env->cur_state;
+	struct bpf_verifier_state_list *sl;
+	struct list_head *pos;
+
+	/* states are most recent first */
+	list_for_each(pos, bpf_explored_state(env, insn_idx)) {
+		sl = container_of(pos, struct bpf_verifier_state_list, node);
+		if (sl->state.insn_idx == insn_idx && sl->state.branches &&
+		    bpf_same_loop(&sl->state, cur))
+			return &sl->state;
+	}
+	return NULL;
+}
+
 static bool states_maybe_looping(struct bpf_verifier_state *old,
 				 struct bpf_verifier_state *cur)
 {
@@ -1237,12 +1272,17 @@ int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 {
 	struct bpf_verifier_state_list *new_sl;
 	struct bpf_verifier_state_list *sl;
-	struct bpf_verifier_state *cur = env->cur_state, *new;
+	struct bpf_verifier_state *cur = env->cur_state, *new, *widen_from = NULL;
+	bool loop_head = env->widen_loops && env->insn_aux_data[insn_idx].loop_head;
 	bool force_new_state, add_new_state, loop;
 	int n, err, states_cnt = 0;
 	struct list_head *pos, *tmp, *head;
 
+	if (loop_head)
+		widen_from = loop_head_state(env, insn_idx);
+
 	force_new_state = env->test_state_freq || bpf_is_force_checkpoint(env, insn_idx) ||
+			  loop_head ||
 			  /* Avoid accumulating infinitely long jmp history */
 			  cur->jmp_history_cnt > 40;
 
@@ -1364,12 +1404,32 @@ int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 				}
 				goto skip_inf_loop_check;
 			}
+			/*
+			 * The state came back to the loop head. If it is within
+			 * the state that went around the loop nothing new can
+			 * happen on the next trip. Otherwise it is widened below
+			 * and goes around instead of all the iterations it stands for.
+			 */
+			if (loop_head && bpf_same_loop(&sl->state, cur)) {
+				if (states_equal(env, &sl->state, cur, RANGE_WITHIN)) {
+					env->widen_used = true;
+					loop = true;
+					goto hit;
+				}
+				goto skip_inf_loop_check;
+			}
 			/* attempt to detect infinite loop to avoid unnecessary doomed work */
 			if (states_maybe_looping(&sl->state, cur) &&
 			    states_equal(env, &sl->state, cur, EXACT) &&
 			    !iter_active_depths_differ(&sl->state, cur) &&
 			    sl->state.may_goto_depth == cur->may_goto_depth &&
 			    sl->state.callback_unroll_depth == cur->callback_unroll_depth) {
+				/* the state repeats, nothing new on the next trip */
+				if (env->widen_loops) {
+					env->widen_used = true;
+					loop = true;
+					goto hit;
+				}
 				verbose_linfo(env, insn_idx, "; ");
 				verbose(env, "infinite loop detected at insn %d\n", insn_idx);
 				verbose(env, "cur state:");
@@ -1522,7 +1582,8 @@ int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 		 * Use bigger 'n' for checkpoints because evicting checkpoint states
 		 * too early would hinder iterator convergence.
 		 */
-		n = bpf_is_force_checkpoint(env, insn_idx) && sl->state.branches > 0 ? 64 : 3;
+		n = (bpf_is_force_checkpoint(env, insn_idx) || loop_head) &&
+		    sl->state.branches > 0 ? 64 : 3;
 		if (sl->miss_cnt > sl->hit_cnt * n + n) {
 			/* the state is unlikely to be useful. Remove it to
 			 * speed up verification
@@ -1539,6 +1600,16 @@ int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 	if (env->max_states_per_insn < states_cnt)
 		env->max_states_per_insn = states_cnt;
 
+	if (loop_head) {
+		cur->loop_passes = 0;
+		if (widen_from) {
+			err = bpf_widen_loop_head(env, insn_idx, is_backedge(env, insn_idx),
+						  widen_from, cur);
+			if (err)
+				return err;
+		}
+	}
+
 	if (!env->bpf_capable && states_cnt > BPF_COMPLEXITY_LIMIT_STATES)
 		return 0;
 
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index cb5d498ada69..85b2691f81b1 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1733,6 +1733,7 @@ int bpf_copy_verifier_state(struct bpf_verifier_state *dst_state,
 	dst_state->dfs_depth = src->dfs_depth;
 	dst_state->callback_unroll_depth = src->callback_unroll_depth;
 	dst_state->may_goto_depth = src->may_goto_depth;
+	dst_state->loop_passes = src->loop_passes;
 	dst_state->equal_state = src->equal_state;
 	for (i = 0; i <= src->curframe; i++) {
 		dst = dst_state->frame[i];
@@ -8040,6 +8041,287 @@ static struct bpf_verifier_state *find_prev_entry(struct bpf_verifier_env *env,
 	return NULL;
 }
 
+/* A constant that register @regno is compared with, -1 if any register. */
+struct widen_thr {
+	s64 val;
+	int regno;
+};
+
+struct bpf_widen_thrs {
+	u32 cnt;
+	struct widen_thr thr[];
+};
+
+/* passes around a loop that widen to constants the loop compares with */
+#define WIDEN_THR_PASSES	4
+/* passes that widen to S32_MAX and the like, later ones drop the bound */
+#define WIDEN_GEN_PASSES	6
+/* states at the loop head differ in something that can't be widened */
+#define WIDEN_MAX_PASSES	10
+
+static const struct widen_thr widen_generic[] = {
+	{ S32_MIN, -1 }, { 0, -1 }, { S32_MAX, -1 }, { U32_MAX, -1 },
+};
+
+static int cmp_widen_thr(const void *a, const void *b)
+{
+	s64 x = ((const struct widen_thr *)a)->val;
+	s64 y = ((const struct widen_thr *)b)->val;
+
+	return x < y ? -1 : x > y;
+}
+
+static bool is_cmp_imm(const struct bpf_insn *insn)
+{
+	u8 class = BPF_CLASS(insn->code);
+	u8 op = BPF_OP(insn->code);
+
+	if (class != BPF_JMP && class != BPF_JMP32)
+		return false;
+	if (BPF_SRC(insn->code) != BPF_K)
+		return false;
+	return op != BPF_JA && op != BPF_CALL && op != BPF_EXIT && op != BPF_JCOND;
+}
+
+/*
+ * Sorted constants that registers are compared with in the SCC of @insn_idx.
+ * A range that ends at one of them can be cut back by the exit test of
+ * the loop, so that the state at the loop head stops growing.
+ */
+static const struct bpf_widen_thrs *scc_thresholds(struct bpf_verifier_env *env, int insn_idx)
+{
+	struct bpf_insn_aux_data *aux = env->insn_aux_data;
+	struct bpf_insn *insns = env->prog->insnsi;
+	u32 scc = aux[insn_idx].scc;
+	struct bpf_widen_thrs *thrs;
+	int i, d, n = 0;
+
+	if (!scc)
+		return NULL;
+	if (!env->scc_thrs) {
+		env->scc_thrs = kvzalloc_objs(*env->scc_thrs, env->scc_cnt, GFP_KERNEL_ACCOUNT);
+		if (!env->scc_thrs)
+			return NULL;
+	}
+	if (env->scc_thrs[scc])
+		return env->scc_thrs[scc];
+
+	for (i = 0; i < env->prog->len; i++)
+		if (aux[i].scc == scc && is_cmp_imm(&insns[i]))
+			n++;
+	thrs = kvzalloc(struct_size(thrs, thr, 3 * n), GFP_KERNEL_ACCOUNT);
+	if (!thrs)
+		return NULL;
+	for (i = 0; i < env->prog->len; i++) {
+		if (aux[i].scc != scc || !is_cmp_imm(&insns[i]))
+			continue;
+		for (d = -1; d <= 1; d++) {
+			thrs->thr[thrs->cnt].val = (s64)insns[i].imm + d;
+			thrs->thr[thrs->cnt++].regno = insns[i].dst_reg;
+		}
+	}
+	sort(thrs->thr, thrs->cnt, sizeof(thrs->thr[0]), cmp_widen_thr, NULL);
+	env->scc_thrs[scc] = thrs;
+	return thrs;
+}
+
+/*
+ * Nearest constant in sorted @thr that is >= @x if @up, <= @x otherwise.
+ * Constants that another register is compared with are skipped.
+ */
+static bool thr_nearest(const struct widen_thr *thr, u32 cnt, int regno, s64 x, bool up,
+			s64 *res)
+{
+	bool found = false;
+	u32 i;
+
+	for (i = 0; i < cnt; i++) {
+		if (regno >= 0 && thr[i].regno >= 0 && thr[i].regno != regno)
+			continue;
+		if (up && thr[i].val >= x) {
+			*res = thr[i].val;
+			return true;
+		}
+		if (!up && thr[i].val <= x) {
+			*res = thr[i].val;
+			found = true;
+		}
+	}
+	return found;
+}
+
+struct widen_ctx {
+	const struct bpf_widen_thrs *thrs;
+	u32 passes;
+	int regno;
+};
+
+/* Where to move the end @x of a range that keeps moving up or down. */
+static bool widen_pick(const struct widen_ctx *w, s64 x, bool up, s64 *res)
+{
+	bool found = false;
+	s64 t;
+
+	if (w->passes <= WIDEN_THR_PASSES && w->thrs &&
+	    thr_nearest(w->thrs->thr, w->thrs->cnt, w->regno, x, up, &t)) {
+		*res = t;
+		found = true;
+	}
+	if (w->passes <= WIDEN_GEN_PASSES &&
+	    thr_nearest(widen_generic, ARRAY_SIZE(widen_generic), -1, x, up, &t)) {
+		*res = !found ? t : up ? min(*res, t) : max(*res, t);
+		found = true;
+	}
+	return found;
+}
+
+static s64 widen_smax(const struct widen_ctx *w, s64 x, s64 lim)
+{
+	s64 t;
+
+	return widen_pick(w, x, true, &t) && t <= lim ? t : lim;
+}
+
+static s64 widen_smin(const struct widen_ctx *w, s64 x, s64 lim)
+{
+	s64 t;
+
+	return widen_pick(w, x, false, &t) && t >= lim ? t : lim;
+}
+
+static u64 widen_umax(const struct widen_ctx *w, u64 x, u64 lim)
+{
+	s64 t;
+
+	if (x > S64_MAX || !widen_pick(w, x, true, &t) || (u64)t > lim)
+		return lim;
+	return t;
+}
+
+static u64 widen_umin(const struct widen_ctx *w, u64 x)
+{
+	s64 t;
+
+	if (!widen_pick(w, min_t(u64, x, S64_MAX), false, &t) || t < 0)
+		return 0;
+	return t;
+}
+
+/*
+ * @old is the state of a register at the loop head, @cur is its state after
+ * a trip around the loop. If @cur has values that @old doesn't have make @cur
+ * a guess of all the values the register can have at the loop head: both
+ * @old and @cur, and where an end of the range moved it is moved further,
+ * to the nearest constant the loop compares the register with.
+ * Whether the guess is good is seen on the next trip: the state that comes
+ * back has to be within it.
+ */
+static void widen_reg(const struct widen_ctx *w, const struct bpf_reg_state *old,
+		      struct bpf_reg_state *cur)
+{
+	u64 umin, umax, low;
+	u32 u32_min, u32_max;
+	s32 s32_min, s32_max;
+	s64 smin, smax;
+	struct tnum t;
+
+	if (old->type != SCALAR_VALUE || cur->type != SCALAR_VALUE)
+		return;
+	if (cnum64_is_subset(old->r64, cur->r64) && cnum32_is_subset(old->r32, cur->r32) &&
+	    tnum_in(old->var_off, cur->var_off))
+		return;
+
+	umin = min(reg_umin(old), reg_umin(cur));
+	umax = max(reg_umax(old), reg_umax(cur));
+	smin = min(reg_smin(old), reg_smin(cur));
+	smax = max(reg_smax(old), reg_smax(cur));
+	u32_min = min(reg_u32_min(old), reg_u32_min(cur));
+	u32_max = max(reg_u32_max(old), reg_u32_max(cur));
+	s32_min = min(reg_s32_min(old), reg_s32_min(cur));
+	s32_max = max(reg_s32_max(old), reg_s32_max(cur));
+
+	if (reg_umin(cur) < reg_umin(old))
+		umin = widen_umin(w, umin);
+	if (reg_umax(cur) > reg_umax(old))
+		umax = widen_umax(w, umax, U64_MAX);
+	if (reg_smin(cur) < reg_smin(old))
+		smin = widen_smin(w, smin, S64_MIN);
+	if (reg_smax(cur) > reg_smax(old))
+		smax = widen_smax(w, smax, S64_MAX);
+	if (reg_u32_min(cur) < reg_u32_min(old))
+		u32_min = widen_umin(w, u32_min);
+	if (reg_u32_max(cur) > reg_u32_max(old))
+		u32_max = widen_umax(w, u32_max, U32_MAX);
+	if (reg_s32_min(cur) < reg_s32_min(old))
+		s32_min = widen_smin(w, s32_min, S32_MIN);
+	if (reg_s32_max(cur) > reg_s32_max(old))
+		s32_max = widen_smax(w, s32_max, S32_MAX);
+
+	/* low bits that are the same in all values seen so far are kept, e.g. alignment */
+	t = tnum_union(old->var_off, cur->var_off);
+	low = t.mask ? BIT_ULL(__ffs64(t.mask)) - 1 : 0;
+	cur->var_off = (struct tnum){ .value = t.value & low, .mask = ~low };
+	cur->r64 = cnum64_intersect(cnum64_from_urange(umin, umax),
+				    cnum64_from_srange(smin, smax));
+	cur->r32 = cnum32_intersect(cnum32_from_urange(u32_min, u32_max),
+				    cnum32_from_srange(s32_min, s32_max));
+	cur->id = 0;
+	cur->delta = 0;
+	reg_bounds_sync(cur);
+}
+
+bool bpf_same_loop(struct bpf_verifier_state *old, struct bpf_verifier_state *cur)
+{
+	return old->speculative == cur->speculative && same_callsites(old, cur);
+}
+
+/*
+ * @cur came to loop head @insn_idx and is not within @old, the state that
+ * went around the loop. Widen scalars of @cur, so that the walk goes around
+ * the loop with a state that stands for many iterations, see widen_reg().
+ * Everything else is left as is. If that is what differs the states never
+ * converge and the walk is given up after a few trips.
+ */
+int bpf_widen_loop_head(struct bpf_verifier_env *env, int insn_idx, bool backedge,
+			struct bpf_verifier_state *old, struct bpf_verifier_state *cur)
+{
+	/* @old is of an earlier run of the loop if @cur just entered it */
+	u32 passes = backedge ? old->loop_passes + 1 : 1;
+	struct widen_ctx w = { scc_thresholds(env, insn_idx), passes };
+	struct bpf_func_state *fold, *fcur;
+	int i, fr, num_slots;
+
+	env->widen_used = true;
+	if (passes > WIDEN_MAX_PASSES) {
+		verbose(env, "states at loop head %d don't converge\n", insn_idx);
+		return -E2BIG;
+	}
+
+	for (fr = 0; fr <= cur->curframe; fr++) {
+		fold = old->frame[fr];
+		fcur = cur->frame[fr];
+
+		for (i = 0; i < BPF_REG_FP; i++) {
+			/* registers of callers are not the ones the loop compares */
+			w.regno = fr == cur->curframe ? i : -1;
+			widen_reg(&w, &fold->regs[i], &fcur->regs[i]);
+		}
+
+		w.regno = -1;
+		num_slots = min(fold->allocated_stack, fcur->allocated_stack) / BPF_REG_SIZE;
+		for (i = 0; i < num_slots; i++) {
+			if (!bpf_is_spilled_reg(&fold->stack[i]) ||
+			    !bpf_is_spilled_reg(&fcur->stack[i]))
+				continue;
+			widen_reg(&w, &fold->stack[i].spilled_ptr, &fcur->stack[i].spilled_ptr);
+		}
+	}
+	cur->loop_passes = passes;
+	if (env->log.level & BPF_LOG_LEVEL2)
+		verbose(env, "loop head %d widened, pass %u\n", insn_idx, passes);
+	return 0;
+}
+
 /*
  * Check if scalar registers are exact for the purpose of not widening.
  * More lenient than regs_exact()
@@ -18970,7 +19252,9 @@ static int do_check(struct bpf_verifier_env *env)
 			}
 		}
 
-		if (bpf_is_prune_point(env, env->insn_idx)) {
+		/* loop heads are where states are widened, all of them have to be looked at */
+		if (bpf_is_prune_point(env, env->insn_idx) ||
+		    (env->widen_loops && insn_aux->loop_head)) {
 			err = bpf_is_state_visited(env, env->insn_idx);
 			if (err < 0)
 				return err;
@@ -22059,6 +22343,11 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr,
 	bpf_stack_liveness_free(env);
 	kvfree(env->cfg.insn_postorder);
 	kvfree(env->scc_info);
+	if (env->scc_thrs) {
+		for (i = 0; i < env->scc_cnt; i++)
+			kvfree(env->scc_thrs[i]);
+		kvfree(env->scc_thrs);
+	}
 	kvfree(env->succ);
 	kvfree(env->gotox_tmp_buf);
 	bpf_diag_free(env);
-- 
2.55.0

[PATCH bpf-next 4/8] bpf: Detect loops that never exit

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

When loops are widened all states that enter the loop can end up going
around it. If none of the states that came from the state that entered
the loop left it, the program never leaves the loop either:

  l1: r0 += 1
      goto l1

Remember in bpf_scc_visit that some state left the loop: the walk took
the jump out of SCC, got to exit or bpf_throw(), or the state was pruned
by the state that is fully explored. When the state that entered the loop
is done, there are backedges and nothing left the loop fail the walk.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 include/linux/bpf_verifier.h |  3 +++
 kernel/bpf/states.c          | 40 ++++++++++++++++++++++++++++++++++++
 kernel/bpf/verifier.c        | 20 ++++++++++++++++++
 3 files changed, 63 insertions(+)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 981902cd5b71..60f483d7e4a9 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -900,6 +900,8 @@ struct bpf_scc_visit {
 	struct bpf_verifier_state *entry_state;
 	struct bpf_scc_backedge *backedges; /* list of backedges */
 	u32 num_backedges;
+	/* some state left the SCC since entry_state was set */
+	bool exited;
 };
 
 /* An array of bpf_scc_visit structs sharing tht same bpf_scc_callchain->scc
@@ -1230,6 +1232,7 @@ int mark_chain_precision(struct bpf_verifier_env *env, int regno);
 
 int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx);
 bool bpf_same_loop(struct bpf_verifier_state *old, struct bpf_verifier_state *cur);
+void bpf_scc_mark_exit(struct bpf_verifier_env *env, struct bpf_verifier_state *st, int insn_idx);
 int bpf_widen_loop_head(struct bpf_verifier_env *env, int insn_idx, bool backedge,
 			struct bpf_verifier_state *old, struct bpf_verifier_state *cur);
 int bpf_update_branch_counts(struct bpf_verifier_env *env, struct bpf_verifier_state *st);
diff --git a/kernel/bpf/states.c b/kernel/bpf/states.c
index 22987ce070e7..39e6052922e5 100644
--- a/kernel/bpf/states.c
+++ b/kernel/bpf/states.c
@@ -170,6 +170,7 @@ static int maybe_enter_scc(struct bpf_verifier_env *env, struct bpf_verifier_sta
 		return -ENOMEM;
 	if (!visit->entry_state) {
 		visit->entry_state = st;
+		visit->exited = false;
 		if (env->log.level & BPF_LOG_LEVEL2)
 			verbose(env, "SCC enter %s\n", format_callchain(env, callchain));
 	}
@@ -212,6 +213,16 @@ static int maybe_exit_scc(struct bpf_verifier_env *env, struct bpf_verifier_stat
 	}
 	if (visit->entry_state != st)
 		return 0;
+	/*
+	 * All states that came from @st are done. If some of them went
+	 * around the loop and none left it, nothing that enters the loop
+	 * the way @st did ever leaves it.
+	 */
+	if (env->widen_loops && !st->speculative && visit->backedges && !visit->exited) {
+		verbose(env, "loop at insn %d never exits\n", st->insn_idx);
+		env->widen_used = true;
+		return -EINVAL;
+	}
 	if (env->log.level & BPF_LOG_LEVEL2)
 		verbose(env, "SCC exit %s\n", format_callchain(env, callchain));
 	visit->entry_state = NULL;
@@ -221,6 +232,32 @@ static int maybe_exit_scc(struct bpf_verifier_env *env, struct bpf_verifier_stat
 	return propagate_backedges(env, visit);
 }
 
+/*
+ * @st left the loop that @insn_idx of its current frame is in. The loop is
+ * left when the frame that bpf_scc_visit is for leaves it. Loops in callees
+ * of that frame are part of one trip around the loop of the caller.
+ */
+void bpf_scc_mark_exit(struct bpf_verifier_env *env, struct bpf_verifier_state *st, int insn_idx)
+{
+	struct bpf_scc_callchain *callchain = &env->callchain_buf;
+	struct bpf_scc_visit *visit;
+	u32 i, callsite;
+
+	if (st->speculative || !env->insn_aux_data[insn_idx].scc)
+		return;
+	memset(callchain, 0, sizeof(*callchain));
+	for (i = 0; i < st->curframe; i++) {
+		callsite = bpf_frame_insn_idx(st, i);
+		if (env->insn_aux_data[callsite].scc)
+			return;
+		callchain->callsites[i] = callsite;
+	}
+	callchain->scc = env->insn_aux_data[insn_idx].scc;
+	visit = scc_visit_lookup(env, callchain);
+	if (visit)
+		visit->exited = true;
+}
+
 /* Lookup an bpf_scc_visit instance corresponding to @st callchain
  * and add @backedge to visit->backedges. @st callchain must exist.
  */
@@ -1462,6 +1499,9 @@ int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 		if (states_equal(env, &sl->state, cur, loop ? RANGE_WITHIN : NOT_EXACT)) {
 hit:
 			sl->hit_cnt++;
+			/* what follows the old state was seen, it may leave the loop */
+			if (env->widen_loops && !sl->state.branches)
+				bpf_scc_mark_exit(env, cur, insn_idx);
 
 			/* if previous state reached the exit with precision and
 			 * current state is equivalent to it (except precision marks)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 85b2691f81b1..06dc269991b2 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -19192,6 +19192,21 @@ static int do_check_insn(struct bpf_verifier_env *env, bool *do_print_state)
 	return -EFAULT;
 }
 
+/* Did the jump at @prev take the walk out of the loop @prev is in? */
+static bool left_loop(struct bpf_verifier_env *env, int prev, int insn_idx)
+{
+	struct bpf_insn_aux_data *aux = env->insn_aux_data;
+	struct bpf_insn *insn;
+
+	if (prev < 0 || prev >= env->prog->len || !aux[prev].scc ||
+	    aux[prev].scc == aux[insn_idx].scc)
+		return false;
+	/* the callee is not in SCC of the call, the insn after the call is */
+	insn = &env->prog->insnsi[prev];
+	return !((BPF_CLASS(insn->code) == BPF_JMP || BPF_CLASS(insn->code) == BPF_JMP32) &&
+		 BPF_OP(insn->code) == BPF_CALL);
+}
+
 static int do_check(struct bpf_verifier_env *env)
 {
 	bool pop_log = !(env->log.level & BPF_LOG_LEVEL2);
@@ -19230,6 +19245,8 @@ static int do_check(struct bpf_verifier_env *env)
 
 		state->last_insn_idx = env->prev_insn_idx;
 		state->insn_idx = env->insn_idx;
+		if (env->widen_loops && left_loop(env, prev_insn_idx, env->insn_idx))
+			bpf_scc_mark_exit(env, state, prev_insn_idx);
 		/*
 		 * Record the incoming edge so active and queued paths use the same
 		 * branch-recording path. A zero-offset conditional has identical
@@ -19358,6 +19375,9 @@ static int do_check(struct bpf_verifier_env *env)
 		} else if (err < 0) {
 			return err;
 		} else if (err == PROCESS_BPF_EXIT) {
+			/* exit or bpf_throw() inside of a loop */
+			if (env->widen_loops)
+				bpf_scc_mark_exit(env, state, env->insn_idx);
 			goto process_bpf_exit;
 		} else if (err == INSN_IDX_UPDATED) {
 		} else if (err == 0) {
-- 
2.55.0

[PATCH bpf-next 5/8] bpf: Add may_goto to loops that are not walked to the end

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

The loop that is accepted because the state at the loop head converged
can run for any number of iterations:

  l1: r0 = *(u32 *)(r7 +0)
      if r0 == 0 goto l1

Bound it at run time. When the walk goes over the back-edge and the trip
around the loop didn't take from the budget of may_goto and didn't get
an element from an iterator remember the insn. After the walk add
may_goto to such back-edges of the loops where some state converged.
The loops that are walked to the end are not touched.

The program cannot go on when may_goto is out of budget. Nothing but the
loop was verified for the state in the loop. So may_goto ends in
bpf_throw():

  17: (61) r0 = *(u32 *)(r7 +0)
  18: (15) if r0 == 0x0 goto pc+1
  19: (05) goto pc+10
  20: (79) r12 = *(u64 *)(r10 -24)
  21: (15) if r12 == 0x0 goto pc+6
  22: (17) r12 -= 1
  23: (55) if r12 != 0x0 goto pc+2
  24: (b7) r12 = -24
  25: (85) call arch_bpf_timed_may_goto
  26: (7b) *(u64 *)(r10 -24) = r12
  27: (05) goto pc-11
  28: (b7) r1 = 0
  29: (85) call bpf_throw
  30: (b7) r0 = 2

bpf_throw() cannot be called when the program holds a reference or
a lock, from a callback, from a global function whose callers don't
expect it, when JIT doesn't support exceptions. The states that come
to the loop head over such back-edge are not widened, and if the loop
converges anyway the walk fails.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 include/linux/bpf_verifier.h |  12 +++
 kernel/bpf/fixups.c          | 153 +++++++++++++++++++++++++++++++++++
 kernel/bpf/states.c          |  31 ++++++-
 kernel/bpf/verifier.c        |  68 ++++++++++++++++
 4 files changed, 263 insertions(+), 1 deletion(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 60f483d7e4a9..fb35f8a7aedd 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -714,6 +714,13 @@ struct bpf_insn_aux_data {
 	u32 loop_head:1; /* target of a back-edge */
 	u32 backedge_ft:1; /* the edge to the next insn is a back-edge */
 	u32 backedge_br:1; /* the jump is a back-edge */
+	/*
+	 * The walk went over the back-edge of this insn with nothing to bound
+	 * the number of trips, in a state where bpf_throw() can and cannot be called.
+	 */
+	u32 guard_pending:1;
+	u32 guard_impossible:1;
+	u32 loop_guard:1; /* may_goto has to be added to the back-edge of this insn */
 	/*
 	 * CFG strongly connected component this instruction belongs to,
 	 * zero if it is a singleton SCC.
@@ -1055,6 +1062,8 @@ struct bpf_verifier_env {
 	u32 scc_cnt;
 	/* per SCC constants that loop counters are compared with, see bpf_widen_loop_head() */
 	struct bpf_widen_thrs **scc_thrs;
+	/* SCCs where some state came back to a state that is still walked */
+	unsigned long *scc_converged;
 	/* states that come back to a loop head are widened instead of walking every iteration */
 	bool widen_loops;
 	/* the walk did or tried that, so a failure can be due to the lost precision */
@@ -1232,6 +1241,9 @@ int mark_chain_precision(struct bpf_verifier_env *env, int regno);
 
 int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx);
 bool bpf_same_loop(struct bpf_verifier_state *old, struct bpf_verifier_state *cur);
+bool bpf_mark_loop_guard(struct bpf_verifier_env *env, struct bpf_verifier_state *cur);
+int bpf_commit_loop_guards(struct bpf_verifier_env *env);
+void bpf_throw(u64 cookie);
 void bpf_scc_mark_exit(struct bpf_verifier_env *env, struct bpf_verifier_state *st, int insn_idx);
 int bpf_widen_loop_head(struct bpf_verifier_env *env, int insn_idx, bool backedge,
 			struct bpf_verifier_state *old, struct bpf_verifier_state *cur);
diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c
index 2add8001c3ec..2b965fa4bacc 100644
--- a/kernel/bpf/fixups.c
+++ b/kernel/bpf/fixups.c
@@ -1537,6 +1537,143 @@ static int add_hidden_subprog(struct bpf_verifier_env *env, struct bpf_insn *pat
 /* Do various post-verification rewrites in a single program pass.
  * These rewrites simplify JIT and interpreter implementations.
  */
+/*
+ * The walk with widened loops is done. Loops where some state came back to
+ * a state that was still walked were not walked to the end and have to be
+ * bounded at run time.
+ */
+int bpf_commit_loop_guards(struct bpf_verifier_env *env)
+{
+	struct bpf_insn_aux_data *aux = env->insn_aux_data;
+	int i;
+
+	for (i = 0; i < env->prog->len; i++) {
+		if (!aux[i].scc || !test_bit(aux[i].scc, env->scc_converged))
+			continue;
+		if (aux[i].guard_impossible) {
+			verbose(env, "loop with back-edge at insn %d cannot be bounded\n", i);
+			return -E2BIG;
+		}
+		if (aux[i].guard_pending) {
+			aux[i].loop_guard = true;
+			env->seen_exception = true;
+		}
+	}
+	return 0;
+}
+
+/* Jump from insn @from of the patch that replaces insn @idx to insn @target of the program. */
+static int guard_jump(struct bpf_insn *insn, int idx, int from, int cnt, int target)
+{
+	int off;
+
+	/* insns after @idx move by the size of the patch */
+	if (target > idx)
+		target += cnt - 1;
+	off = target - (idx + from) - 1;
+	if (BPF_OP(insn->code) == BPF_JA && BPF_CLASS(insn->code) == BPF_JMP32) {
+		insn->imm = off;
+		return 0;
+	}
+	if (off < S16_MIN || off > S16_MAX) {
+		if (BPF_OP(insn->code) != BPF_JA)
+			return -ERANGE;
+		*insn = BPF_JMP32_A(off);
+		return 0;
+	}
+	insn->off = off;
+	return 0;
+}
+
+/*
+ * The main pass went over the back-edge of jump @insn at @idx with a state
+ * that stands for any number of iterations. Nothing bounds the loop at run
+ * time, so add may_goto to the back-edge. The program cannot go on when
+ * may_goto is out of budget: nothing but the loop was verified for the state
+ * in the loop. Call bpf_throw(). The main pass made sure it can be called.
+ *
+ * back-edge is the jump:             back-edge is the edge to the next insn:
+ *   if cond goto guard                 if cond goto target
+ *   goto next                        guard:
+ * guard:                               may_goto throw
+ *   may_goto throw                     goto next
+ *   goto head                        throw:
+ * throw:                               r1 = 0
+ *   r1 = 0                             call bpf_throw
+ *   call bpf_throw                   next:
+ * next:
+ *
+ * Returns the number of insns in @buf.
+ */
+static int add_loop_guard(struct bpf_verifier_env *env, int idx, struct bpf_insn *buf,
+			  int stack_depth, u16 *stack_depth_extra)
+{
+	struct bpf_insn_aux_data *aux = &env->insn_aux_data[idx];
+	struct bpf_insn orig = env->prog->insnsi[idx];
+	bool ja = BPF_OP(orig.code) == BPF_JA;
+	bool gotol = ja && BPF_CLASS(orig.code) == BPF_JMP32;
+	int target = idx + 1 + (gotol ? orig.imm : orig.off);
+	bool guard_jump_edge = ja || aux->backedge_br;
+	struct bpf_insn *p = buf, *jeq, *skip = NULL, *back = NULL;
+	int stack_off, cnt, err = 0;
+
+	if (guard_jump_edge && !ja) {
+		*p = orig;
+		p->off = 1;
+		p++;
+		skip = p;
+		*p++ = BPF_JMP_A(0);
+	} else if (!guard_jump_edge) {
+		*p++ = orig;
+	}
+
+	/* the same insns may_goto is replaced with, see bpf_do_misc_fixups() */
+	if (bpf_jit_supports_timed_may_goto()) {
+		stack_off = -stack_depth - 16;
+		*stack_depth_extra = 16;
+		*p++ = BPF_LDX_MEM(BPF_DW, BPF_REG_AX, BPF_REG_10, stack_off);
+		jeq = p;
+		*p++ = BPF_JMP_IMM(BPF_JEQ, BPF_REG_AX, 0, 0);
+		*p++ = BPF_ALU64_IMM(BPF_SUB, BPF_REG_AX, 1);
+		*p++ = BPF_JMP_IMM(BPF_JNE, BPF_REG_AX, 0, 2);
+		*p++ = BPF_MOV64_IMM(BPF_REG_AX, stack_off);
+		*p++ = BPF_EMIT_CALL(arch_bpf_timed_may_goto);
+		*p++ = BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_AX, stack_off);
+	} else {
+		stack_off = -stack_depth - 8;
+		*stack_depth_extra = max_t(u16, *stack_depth_extra, 8);
+		*p++ = BPF_LDX_MEM(BPF_DW, BPF_REG_AX, BPF_REG_10, stack_off);
+		jeq = p;
+		*p++ = BPF_JMP_IMM(BPF_JEQ, BPF_REG_AX, 0, 0);
+		*p++ = BPF_ALU64_IMM(BPF_SUB, BPF_REG_AX, 1);
+		*p++ = BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_AX, stack_off);
+	}
+
+	if (guard_jump_edge) {
+		back = p;
+		*p++ = gotol ? orig : BPF_JMP_A(0);
+	} else {
+		/* over bpf_throw() to the loop head that follows */
+		*p++ = BPF_JMP_A(2);
+	}
+	jeq->off = p - jeq - 1;
+	*p++ = BPF_MOV64_IMM(BPF_REG_1, 0);
+	*p++ = BPF_EMIT_CALL(bpf_throw);
+	cnt = p - buf;
+
+	if (skip)
+		skip->off = cnt - (skip - buf) - 1;
+	if (back)
+		err = guard_jump(back, idx, back - buf, cnt, target);
+	else
+		err = guard_jump(&buf[0], idx, 0, cnt, target);
+	if (err) {
+		verbose(env, "insn %d: jump is out of range after may_goto is added\n", idx);
+		return err;
+	}
+	return cnt;
+}
+
 int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 {
 	struct bpf_prog *prog = env->prog;
@@ -1573,6 +1710,22 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 	}
 
 	for (i = 0; i < insn_cnt;) {
+		if (env->insn_aux_data[i + delta].loop_guard) {
+			cnt = add_loop_guard(env, i + delta, insn_buf, stack_depth,
+					     &stack_depth_extra);
+			if (cnt < 0)
+				return cnt;
+
+			new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
+			if (!new_prog)
+				return -ENOMEM;
+
+			delta    += cnt - 1;
+			env->prog = prog = new_prog;
+			insn      = new_prog->insnsi + i + delta;
+			goto next_insn;
+		}
+
 		if (is_addr_space_cast32(env->prog, insn)) {
 			/* convert to 32-bit mov that clears upper 32-bit */
 			insn->code = BPF_ALU | BPF_MOV | BPF_X;
diff --git a/kernel/bpf/states.c b/kernel/bpf/states.c
index 39e6052922e5..24422b7db6d9 100644
--- a/kernel/bpf/states.c
+++ b/kernel/bpf/states.c
@@ -281,6 +281,8 @@ static int add_scc_backedge(struct bpf_verifier_env *env,
 	}
 	if (env->log.level & BPF_LOG_LEVEL2)
 		verbose(env, "SCC backedge %s\n", format_callchain(env, callchain));
+	if (env->scc_converged)
+		__set_bit(callchain->scc, env->scc_converged);
 	backedge->next = visit->backedges;
 	visit->backedges = backedge;
 	visit->num_backedges++;
@@ -1163,6 +1165,9 @@ static bool is_backedge(struct bpf_verifier_env *env, int insn_idx)
 	return insn_idx == prev + 1 ? aux->backedge_ft : aux->backedge_br;
 }
 
+static bool iter_active_depths_differ(struct bpf_verifier_state *old,
+				      struct bpf_verifier_state *cur);
+
 /* The state of this walk that was the last to get to loop head @insn_idx. */
 static struct bpf_verifier_state *loop_head_state(struct bpf_verifier_env *env, int insn_idx)
 {
@@ -1180,6 +1185,24 @@ static struct bpf_verifier_state *loop_head_state(struct bpf_verifier_env *env,
 	return NULL;
 }
 
+/*
+ * @cur got to loop head @insn_idx, @old is the state that started this trip
+ * around the loop if there is one. The trip is bounded at run time if it
+ * took from the budget of may_goto or got an element from an iterator.
+ * Otherwise may_goto has to be added to the back-edge if the loop is not
+ * walked to the end. Returns false if that is not possible.
+ */
+static bool loop_head_guard(struct bpf_verifier_env *env, int insn_idx,
+			    struct bpf_verifier_state *old, struct bpf_verifier_state *cur)
+{
+	if (!is_backedge(env, insn_idx))
+		return true;
+	if (old && (old->may_goto_depth != cur->may_goto_depth ||
+		    iter_active_depths_differ(old, cur)))
+		return true;
+	return bpf_mark_loop_guard(env, cur);
+}
+
 static bool states_maybe_looping(struct bpf_verifier_state *old,
 				 struct bpf_verifier_state *cur)
 {
@@ -1315,8 +1338,14 @@ int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 	int n, err, states_cnt = 0;
 	struct list_head *pos, *tmp, *head;
 
-	if (loop_head)
+	if (loop_head) {
 		widen_from = loop_head_state(env, insn_idx);
+		/* the loop cannot be bounded at run time, walk all of it */
+		if (!loop_head_guard(env, insn_idx, widen_from, cur)) {
+			loop_head = false;
+			widen_from = NULL;
+		}
+	}
 
 	force_new_state = env->test_state_freq || bpf_is_force_checkpoint(env, insn_idx) ||
 			  loop_head ||
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 06dc269991b2..2fb5a66bd7d4 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -8322,6 +8322,73 @@ int bpf_widen_loop_head(struct bpf_verifier_env *env, int insn_idx, bool backedg
 	return 0;
 }
 
+static bool program_returns_void(struct bpf_verifier_env *env);
+static bool return_retval_range(struct bpf_verifier_env *env, struct bpf_retval_range *range);
+
+/* Why bpf_throw() cannot be called in @st, NULL if it can. */
+static const char *cannot_throw(struct bpf_verifier_env *env, struct bpf_verifier_state *st)
+{
+	struct bpf_retval_range range;
+	struct bpf_func_state *frame;
+	int i;
+
+	if (!env->prog->jit_requested || !bpf_jit_supports_exceptions())
+		return "JIT does not support exceptions";
+	for (i = 0; i < st->acquired_refs; i++)
+		if (st->refs[i].type == REF_TYPE_PTR)
+			return "reference is held";
+	if (st->active_locks || st->active_irq_id || st->active_rcu_locks ||
+	    st->active_preempt_locks)
+		return "lock is held";
+	for (i = 0; i <= st->curframe; i++) {
+		frame = st->frame[i];
+		if (frame->in_callback_fn || frame->in_async_callback_fn ||
+		    frame->in_exception_callback_fn)
+			return "in callback";
+	}
+	/* callers of the global function were not told that it can throw */
+	if (st->frame[0]->subprogno && !subprog_info(env, st->frame[0]->subprogno)->might_throw)
+		return "in global function";
+	/* default exception callback returns the cookie, that is 0 */
+	if (!env->exception_callback_subprog && !program_returns_void(env) &&
+	    resolve_prog_type(env->prog) != BPF_PROG_TYPE_STRUCT_OPS &&
+	    return_retval_range(env, &range) && (range.minval > 0 || range.maxval < 0))
+		return "0 is not a valid return value";
+	return NULL;
+}
+
+/*
+ * The walk went over the back-edge of env->prev_insn_idx and nothing bounds
+ * the number of trips. If the loop is not walked to the end may_goto that
+ * ends in bpf_throw() is added to the back-edge, see commit_loop_guards().
+ * Returns false when that cannot be done in state @cur.
+ */
+bool bpf_mark_loop_guard(struct bpf_verifier_env *env, struct bpf_verifier_state *cur)
+{
+	struct bpf_insn_aux_data *aux = &env->insn_aux_data[env->prev_insn_idx];
+	struct bpf_insn *insn = &env->prog->insnsi[env->prev_insn_idx];
+	u8 class = BPF_CLASS(insn->code);
+	u8 op = BPF_OP(insn->code);
+	const char *why;
+
+	why = cannot_throw(env, cur);
+	if ((class != BPF_JMP && class != BPF_JMP32) ||
+	    op == BPF_CALL || op == BPF_EXIT || op == BPF_JCOND ||
+	    (op == BPF_JA && BPF_SRC(insn->code) == BPF_X))
+		why = "not a jump";
+	else if (op != BPF_JA && aux->backedge_ft && aux->backedge_br)
+		why = "both edges are back-edges";
+	if (why) {
+		if (env->log.level & BPF_LOG_LEVEL2)
+			verbose(env, "cannot add may_goto to back-edge of insn %d: %s\n",
+				env->prev_insn_idx, why);
+		aux->guard_impossible = true;
+		return false;
+	}
+	aux->guard_pending = true;
+	return true;
+}
+
 /*
  * Check if scalar registers are exact for the purpose of not widening.
  * More lenient than regs_exact()
@@ -22363,6 +22430,7 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr,
 	bpf_stack_liveness_free(env);
 	kvfree(env->cfg.insn_postorder);
 	kvfree(env->scc_info);
+	kvfree(env->scc_converged);
 	if (env->scc_thrs) {
 		for (i = 0; i < env->scc_cnt; i++)
 			kvfree(env->scc_thrs[i]);
-- 
2.55.0

[PATCH bpf-next 6/8] bpf: Walk loops with widened states first

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

Widening gives up precision. A loop that initializes one stack slot per
iteration or advances a pointer along with the counter cannot be verified
with the counter being a range. may_goto cannot be added to the loop
that holds a reference.

Walk the program with widening first. If that walk fails restore
everything it changed outside of verifier states: insn_aux_data,
subprog_info, func_info_aux, flags of the prog, counters and the log,
and walk every iteration as before. The program is accepted when either
walk accepts it. It is all or nothing for the main program and global
functions: may_goto added to a loop of a static function is there for
all callers. The insns processed by the walk that failed are reported
separately:

  processed 258028 insns (limit 1000000) max_states_per_insn 27 ...
  walks with widened loops that failed processed 24102 insns

Offloaded programs are walked the old way. The driver sees every insn
that is visited.

veristat for selftests, 5251 programs: nothing that was accepted is
rejected. 4 programs that were rejected are accepted: the loops in them
can exit, but don't have to. 126 programs are walked twice. Their stats
of the second walk are the same as before.
Total insns of programs accepted before and after go from 5569499 to
4774715 plus 88708 in walks that failed (-12.7%).

File                         Program                          Insns A Insns B      Diff
loop1                        nested_loops                      361349     135   -99.96%
bpf_iter_tasks               dump_task_sleepable                85521     583   -99.32%
verifier_loops1              jumps_out_rather_than_in           40004      15   -99.96%
timer_start_delete_race      start_timer                        40008      49   -99.88%
profiler2                    tracepoint__syscalls__sys_enter_   51274   26746   -47.84%
verifier_iterating_callbacks loop_inside_iter_volatile_limit    22026     114   -99.48%
verifier_iterating_callbacks loop_inside_iter                   19022      90   -99.53%
verifier_iterating_callbacks loop_inside_iter_signed            19022      90   -99.53%
access_map_in_map            access_map_in_array                18462      49   -99.73%
access_map_in_map            access_map_in_htab                 18462      49   -99.73%
access_map_in_map            sleepable_access_map_in_array      18462      49   -99.73%
access_map_in_map            sleepable_access_map_in_htab       18462      49   -99.73%
timer_start_delete_race      delete_elem                        14004      19   -99.86%
linked_list                  clear_global_array_list            13071     108   -99.17%
...
iters                        stack_misc_vs_scalar_in_a_loop       106     120   +13.21%
profiler2                    kprobe__proc_sys_write              3268    4210   +28.82%
profiler2                    raw_tracepoint__sched_process_ex    3846    6907   +79.59%
xdp_lb_bench                 xdp_lb_bench                       27529   30974   +12.51%

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 include/linux/bpf_verifier.h |   2 +
 kernel/bpf/verifier.c        | 167 ++++++++++++++++++++++++++++++++++-
 2 files changed, 167 insertions(+), 2 deletions(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index fb35f8a7aedd..e02ee286067d 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -1068,6 +1068,8 @@ struct bpf_verifier_env {
 	bool widen_loops;
 	/* the walk did or tried that, so a failure can be due to the lost precision */
 	bool widen_used;
+	/* insns processed by a walk that was given up */
+	u32 insn_wasted;
 	struct bpf_iarray *succ;
 	struct bpf_iarray *gotox_tmp_buf;
 };
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 2fb5a66bd7d4..871aa45031d6 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -20536,6 +20536,122 @@ static int do_check_common(struct bpf_verifier_env *env, int subprog)
 	return ret;
 }
 
+/* What a walk changes outside of verifier states and per insn data. */
+struct walk_snapshot {
+	struct bpf_insn_aux_data *insn_aux;
+	struct bpf_func_info_aux *func_aux;
+	struct bpf_subprog_info *subprogs;
+	struct bpf_prog *prog;
+	u64 log_pos, diag_pos;
+	u32 insn_processed, prev_insn_processed;
+	u32 jmps_processed, prev_jmps_processed;
+	u32 total_states, peak_states, max_states_per_insn, longest_mark_read_walk;
+	u32 explored_states_size, free_list_size, num_backedges;
+	u32 id_gen, pass_cnt, max_stack_depth;
+	u32 max_ctx_offset, max_pkt_offset, max_tp_access, max_rdonly_access, max_rdwr_access;
+	bool seen_direct_write, seen_exception, explore_alu_limits, tail_call_reachable;
+	void *arena;
+};
+
+static void walk_snapshot_free(struct walk_snapshot *s)
+{
+	kvfree(s->insn_aux);
+	kvfree(s->func_aux);
+	kvfree(s->subprogs);
+	kfree(s->prog);
+}
+
+static size_t func_aux_size(struct bpf_verifier_env *env)
+{
+	return array_size(env->prog->aux->func_info_cnt, sizeof(*env->prog->aux->func_info_aux));
+}
+
+static int walk_snapshot_save(struct bpf_verifier_env *env, struct walk_snapshot *s)
+{
+	struct bpf_prog_aux *aux = env->prog->aux;
+
+	memset(s, 0, sizeof(*s));
+	s->insn_aux = kvmemdup(env->insn_aux_data,
+			       array_size(env->prog->len, sizeof(*env->insn_aux_data)),
+			       GFP_KERNEL_ACCOUNT);
+	s->subprogs = kvmemdup(env->subprog_info, sizeof(env->subprog_info), GFP_KERNEL_ACCOUNT);
+	/* flags of the program, not its insns */
+	s->prog = kmemdup(env->prog, offsetof(struct bpf_prog, insnsi), GFP_KERNEL_ACCOUNT);
+	if (aux->func_info_aux)
+		s->func_aux = kvmemdup(aux->func_info_aux, func_aux_size(env), GFP_KERNEL_ACCOUNT);
+	if (!s->insn_aux || !s->subprogs || !s->prog || (aux->func_info_aux && !s->func_aux)) {
+		walk_snapshot_free(s);
+		return -ENOMEM;
+	}
+	s->log_pos = env->log.end_pos;
+	s->diag_pos = bpf_diag_event_log_save(env);
+	s->insn_processed = env->insn_processed;
+	s->prev_insn_processed = env->prev_insn_processed;
+	s->jmps_processed = env->jmps_processed;
+	s->prev_jmps_processed = env->prev_jmps_processed;
+	s->total_states = env->total_states;
+	s->peak_states = env->peak_states;
+	s->max_states_per_insn = env->max_states_per_insn;
+	s->longest_mark_read_walk = env->longest_mark_read_walk;
+	s->explored_states_size = env->explored_states_size;
+	s->free_list_size = env->free_list_size;
+	s->num_backedges = env->num_backedges;
+	s->id_gen = env->id_gen;
+	s->pass_cnt = env->pass_cnt;
+	s->max_stack_depth = env->max_stack_depth;
+	s->seen_direct_write = env->seen_direct_write;
+	s->seen_exception = env->seen_exception;
+	s->explore_alu_limits = env->explore_alu_limits;
+	s->max_ctx_offset = aux->max_ctx_offset;
+	s->max_pkt_offset = aux->max_pkt_offset;
+	s->max_tp_access = aux->max_tp_access;
+	s->max_rdonly_access = aux->max_rdonly_access;
+	s->max_rdwr_access = aux->max_rdwr_access;
+	s->tail_call_reachable = aux->tail_call_reachable;
+	s->arena = aux->arena;
+	return 0;
+}
+
+static void walk_snapshot_restore(struct bpf_verifier_env *env, struct walk_snapshot *s)
+{
+	struct bpf_prog_aux *aux = env->prog->aux;
+
+	memcpy(env->insn_aux_data, s->insn_aux,
+	       array_size(env->prog->len, sizeof(*env->insn_aux_data)));
+	memcpy(env->subprog_info, s->subprogs, sizeof(env->subprog_info));
+	memcpy(env->prog, s->prog, offsetof(struct bpf_prog, insnsi));
+	if (s->func_aux)
+		memcpy(aux->func_info_aux, s->func_aux, func_aux_size(env));
+	env->insn_wasted += env->insn_processed - s->insn_processed;
+	env->insn_processed = s->insn_processed;
+	env->prev_insn_processed = s->prev_insn_processed;
+	env->jmps_processed = s->jmps_processed;
+	env->prev_jmps_processed = s->prev_jmps_processed;
+	env->total_states = s->total_states;
+	env->peak_states = s->peak_states;
+	env->max_states_per_insn = s->max_states_per_insn;
+	env->longest_mark_read_walk = s->longest_mark_read_walk;
+	env->explored_states_size = s->explored_states_size;
+	env->free_list_size = s->free_list_size;
+	env->num_backedges = s->num_backedges;
+	env->id_gen = s->id_gen;
+	env->pass_cnt = s->pass_cnt;
+	env->max_stack_depth = s->max_stack_depth;
+	env->seen_direct_write = s->seen_direct_write;
+	env->seen_exception = s->seen_exception;
+	env->explore_alu_limits = s->explore_alu_limits;
+	aux->max_ctx_offset = s->max_ctx_offset;
+	aux->max_pkt_offset = s->max_pkt_offset;
+	aux->max_tp_access = s->max_tp_access;
+	aux->max_rdonly_access = s->max_rdonly_access;
+	aux->max_rdwr_access = s->max_rdwr_access;
+	aux->tail_call_reachable = s->tail_call_reachable;
+	aux->arena = s->arena;
+	if (!(env->log.level & BPF_LOG_LEVEL2))
+		bpf_vlog_reset(&env->log, s->log_pos);
+	bpf_diag_event_log_restore(env, s->diag_pos);
+}
+
 /* Lazily verify all global functions based on their BTF, if they are called
  * from main BPF program or any of subprograms transitively.
  * BPF global subprogs called from dead code are not validated.
@@ -20617,6 +20733,51 @@ static int do_check_main(struct bpf_verifier_env *env)
 	return ret;
 }
 
+/*
+ * Walk the program with loops widened first. It is much less work when it
+ * succeeds. If it fails the reason can be the precision that widening gave
+ * up. Then undo everything that walk did, so that the walk of every
+ * iteration that follows can't tell that it is not the first one.
+ * It is all or nothing for the main program and global functions, because
+ * may_goto added to a loop of a static function is there for all callers.
+ */
+static int do_check_prog(struct bpf_verifier_env *env)
+{
+	struct walk_snapshot snap;
+	int ret;
+
+	/* no loops without bpf_capable, the driver of an offloaded prog sees every insn visit */
+	if (!env->bpf_capable || env->scc_cnt <= 1 || bpf_prog_is_offloaded(env->prog->aux)) {
+		ret = do_check_main(env);
+		return ret ?: do_check_subprogs(env);
+	}
+
+	env->scc_converged = kvzalloc_objs(*env->scc_converged, BITS_TO_LONGS(env->scc_cnt),
+					   GFP_KERNEL_ACCOUNT);
+	if (!env->scc_converged)
+		return -ENOMEM;
+	ret = walk_snapshot_save(env, &snap);
+	if (ret)
+		return ret;
+
+	env->widen_loops = true;
+	env->widen_used = false;
+	ret = do_check_main(env);
+	ret = ret ?: do_check_subprogs(env);
+	if (!ret && env->widen_used)
+		ret = bpf_commit_loop_guards(env);
+	env->widen_loops = false;
+	if (ret && ret != -ENOMEM && ret != -EAGAIN && ret != -EFAULT && env->widen_used) {
+		walk_snapshot_restore(env, &snap);
+		if (env->log.level & BPF_LOG_LEVEL)
+			verbose(env, "walk with widened loops failed, walking every iteration\n");
+		ret = do_check_main(env);
+		ret = ret ?: do_check_subprogs(env);
+	}
+	walk_snapshot_free(&snap);
+	return ret;
+}
+
 static void print_verification_stats(struct bpf_verifier_env *env)
 {
 	/* Skip over hidden subprogs which are not verified. */
@@ -20645,6 +20806,9 @@ static void print_verification_stats(struct bpf_verifier_env *env)
 		env->insn_processed, BPF_COMPLEXITY_LIMIT_INSNS,
 		env->max_states_per_insn, env->total_states,
 		env->peak_states, env->longest_mark_read_walk);
+	if (env->insn_wasted)
+		verbose(env, "walks with widened loops that failed processed %d insns\n",
+			env->insn_wasted);
 }
 
 int bpf_prog_ctx_arg_info_init(struct bpf_prog *prog,
@@ -22287,8 +22451,7 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr,
 	if (ret < 0)
 		goto skip_full_check;
 
-	ret = do_check_main(env);
-	ret = ret ?: do_check_subprogs(env);
+	ret = do_check_prog(env);
 
 	if (ret == 0 && bpf_prog_is_offloaded(env->prog->aux))
 		ret = bpf_prog_offload_finalize(env);
-- 
2.55.0

[PATCH bpf-next 7/8] selftests/bpf: Adjust tests to widened loops

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

The loop that can exit, but is not known to, is accepted with may_goto
added to it. The tests that expect "infinite loop detected" or
"BPF program is too large" for such loop expect it to load:
 - verifier_cfg: conditional loop
 - verifier_movsx: MOV32SX, S8, var_off u32_max
 - verifier_search_pruning: short_loop1
 - verif_scale_loop3
 - test_verifier: "calls: conditional call 6". Don't run it, it takes
   may_goto 250ms to end it.

The loops that never exit are rejected as before.

verifier_precision/state_loop_first_last_equal: the loop converges on
the second trip. Checkpoint with first_idx == last_idx doesn't happen.
Expect mark_precise from the exit test of the first trip.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 .../bpf/prog_tests/bpf_verif_scale.c          |  4 +--
 .../selftests/bpf/progs/verifier_cfg.c        |  4 +--
 .../selftests/bpf/progs/verifier_movsx.c      |  2 +-
 .../selftests/bpf/progs/verifier_precision.c  | 29 ++++++++-----------
 .../bpf/progs/verifier_search_pruning.c       |  3 +-
 tools/testing/selftests/bpf/verifier/calls.c  |  5 ++--
 6 files changed, 21 insertions(+), 26 deletions(-)

diff --git a/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c b/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
index 902a70d5afeb..2dc37090d7a4 100644
--- a/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
+++ b/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
@@ -154,9 +154,9 @@ void test_verif_scale_loop2()
 	scale_test("loop2.bpf.o", BPF_PROG_TYPE_RAW_TRACEPOINT, false);
 }
 
-void test_verif_scale_loop3_fail()
+void test_verif_scale_loop3()
 {
-	scale_test("loop3.bpf.o", BPF_PROG_TYPE_RAW_TRACEPOINT, true /* fails */);
+	scale_test("loop3.bpf.o", BPF_PROG_TYPE_RAW_TRACEPOINT, false);
 }
 
 void test_verif_scale_loop4()
diff --git a/tools/testing/selftests/bpf/progs/verifier_cfg.c b/tools/testing/selftests/bpf/progs/verifier_cfg.c
index 3c3bb03e8217..700eadf5d430 100644
--- a/tools/testing/selftests/bpf/progs/verifier_cfg.c
+++ b/tools/testing/selftests/bpf/progs/verifier_cfg.c
@@ -98,8 +98,8 @@ l0_%=:	r1 = r0;					\
 
 SEC("socket")
 __description("conditional loop")
-__failure __msg("infinite loop detected")
-__msg_unpriv("back-edge")
+__success
+__failure_unpriv __msg_unpriv("back-edge")
 __naked void conditional_loop(void)
 {
 	asm volatile ("					\
diff --git a/tools/testing/selftests/bpf/progs/verifier_movsx.c b/tools/testing/selftests/bpf/progs/verifier_movsx.c
index 195b27a51224..280ccee33663 100644
--- a/tools/testing/selftests/bpf/progs/verifier_movsx.c
+++ b/tools/testing/selftests/bpf/progs/verifier_movsx.c
@@ -226,7 +226,7 @@ l0_%=:							\
 
 SEC("socket")
 __description("MOV32SX, S8, var_off u32_max")
-__failure __msg("infinite loop detected")
+__success
 __failure_unpriv __msg_unpriv("back-edge from insn 2 to 0")
 __naked void mov64sx_s32_varoff_1(void)
 {
diff --git a/tools/testing/selftests/bpf/progs/verifier_precision.c b/tools/testing/selftests/bpf/progs/verifier_precision.c
index f4459561bf39..88358586e796 100644
--- a/tools/testing/selftests/bpf/progs/verifier_precision.c
+++ b/tools/testing/selftests/bpf/progs/verifier_precision.c
@@ -152,22 +152,21 @@ __naked int bpf_store_release(void)
 SEC("?raw_tp")
 __success __log_level(2)
 /*
- * Without the bug fix there will be no history between "last_idx 3 first_idx 3"
- * and "parent state regs=" lines. "R0=6" parts are here to help anchor
- * expected log messages to the one specific mark_chain_precision operation.
- *
- * This is quite fragile: if verifier checkpointing heuristic changes, this
- * might need adjusting.
+ * The state is widened when it comes back to the loop head, so the exit test
+ * is decided only on the first trip around the loop. "R0=2" parts are here to
+ * help anchor expected log messages to that mark_chain_precision operation.
  */
-__msg("2: (07) r0 += 1                       ; R0=6")
+__msg("2: (07) r0 += 1                       ; R0=2")
 __msg("3: (35) if r0 >= 0xa goto pc+1")
-__msg("mark_precise: frame0: last_idx 3 first_idx 3 subseq_idx -1")
+__msg("mark_precise: frame0: last_idx 3 first_idx 1 subseq_idx -1")
 __msg("mark_precise: frame0: regs=r0 stack= before 2: (07) r0 += 1")
 __msg("mark_precise: frame0: regs=r0 stack= before 1: (07) r0 += 1")
-__msg("mark_precise: frame0: regs=r0 stack= before 4: (05) goto pc-4")
-__msg("mark_precise: frame0: regs=r0 stack= before 3: (35) if r0 >= 0xa goto pc+1")
-__msg("mark_precise: frame0: parent state regs= stack=:  R0=P4")
-__msg("3: R0=6")
+__msg("mark_precise: frame0: parent state regs=r0 stack=:  R0=P0")
+__msg("mark_precise: frame0: last_idx 0 first_idx 0 subseq_idx 1")
+__msg("mark_precise: frame0: regs=r0 stack= before 0: (b7) r0 = 0")
+__msg("3: R0=2")
+__msg("loop head 1 widened, pass 1")
+__msg("1: safe")
 __naked int state_loop_first_last_equal(void)
 {
 	asm volatile (
@@ -175,11 +174,7 @@ __naked int state_loop_first_last_equal(void)
 	"l0_%=:"
 		"r0 += 1;"
 		"r0 += 1;"
-		/* every few iterations we'll have a checkpoint here with
-		 * first_idx == last_idx, potentially confusing precision
-		 * backtracking logic
-		 */
-		"if r0 >= 10 goto l1_%=;"	/* checkpoint + mark_precise */
+		"if r0 >= 10 goto l1_%=;"	/* mark_precise */
 		"goto l0_%=;"
 	"l1_%=:"
 		"exit;"
diff --git a/tools/testing/selftests/bpf/progs/verifier_search_pruning.c b/tools/testing/selftests/bpf/progs/verifier_search_pruning.c
index f40e57251e94..7098b44faafc 100644
--- a/tools/testing/selftests/bpf/progs/verifier_search_pruning.c
+++ b/tools/testing/selftests/bpf/progs/verifier_search_pruning.c
@@ -341,8 +341,7 @@ l0_%=:	r1 = 42;					\
  * test would take a very long time to verify.
  */
 SEC("kprobe")
-__failure __log_level(4)
-__msg("BPF program is too large.")
+__success
 __naked void short_loop1(void)
 {
 	asm volatile (
diff --git a/tools/testing/selftests/bpf/verifier/calls.c b/tools/testing/selftests/bpf/verifier/calls.c
index 8b94b87135bc..c7c501bfc660 100644
--- a/tools/testing/selftests/bpf/verifier/calls.c
+++ b/tools/testing/selftests/bpf/verifier/calls.c
@@ -559,8 +559,9 @@
 	BPF_EXIT_INSN(),
 	},
 	.prog_type = BPF_PROG_TYPE_SCHED_CLS,
-	.errstr = "infinite loop detected",
-	.result = REJECT,
+	/* may_goto ends the loop after 250ms, do not run it */
+	.result = ACCEPT,
+	.runs = -1,
 },
 {
 	"calls: using r0 returned by callee",
-- 
2.55.0

[PATCH bpf-next 8/8] selftests/bpf: Add tests for widened loops

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

Loops with the counter that steps by 1, 4, 8, up and down, with 64-bit
and 32-bit counter, nested, with too many iterations to walk every
one of them. The ones with the step other than 1 that leave the loop
on '!=' need range ends trimmed to var_off members.

Negative tests: the loop with one iteration too many, the counter that
never equals the bound, the access at the exit value of the counter.

spin_until_flag tests run the loop that never ends and check that
may_goto added by the verifier ends the program. loop_with_reference
cannot have may_goto and is walked every iteration.

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

diff --git a/tools/testing/selftests/bpf/prog_tests/verifier.c b/tools/testing/selftests/bpf/prog_tests/verifier.c
index 4f1e1c1cd5ab..5bed8f958777 100644
--- a/tools/testing/selftests/bpf/prog_tests/verifier.c
+++ b/tools/testing/selftests/bpf/prog_tests/verifier.c
@@ -65,6 +65,7 @@
 #include "verifier_live_stack.skel.h"
 #include "verifier_liveness_exp.skel.h"
 #include "verifier_load_acquire.skel.h"
+#include "verifier_loop_widen.skel.h"
 #include "verifier_loops1.skel.h"
 #include "verifier_lwt.skel.h"
 #include "verifier_map_in_map.skel.h"
@@ -234,6 +235,7 @@ void test_verifier_leak_ptr(void)             { RUN(verifier_leak_ptr); }
 void test_verifier_linked_scalars(void)       { RUN(verifier_linked_scalars); }
 void test_verifier_live_stack(void)           { RUN(verifier_live_stack); }
 void test_verifier_liveness_exp(void)         { RUN(verifier_liveness_exp); }
+void test_verifier_loop_widen(void)           { RUN(verifier_loop_widen); }
 void test_verifier_loops1(void)               { RUN(verifier_loops1); }
 void test_verifier_lwt(void)                  { RUN(verifier_lwt); }
 void test_verifier_map_in_map(void)           { RUN(verifier_map_in_map); }
diff --git a/tools/testing/selftests/bpf/progs/verifier_loop_widen.c b/tools/testing/selftests/bpf/progs/verifier_loop_widen.c
new file mode 100644
index 000000000000..4bdfc198bfaa
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/verifier_loop_widen.c
@@ -0,0 +1,344 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Loops that are verified by widening the state at the loop head. */
+
+#include <linux/bpf.h>
+#include <bpf/bpf_helpers.h>
+#include "bpf_misc.h"
+
+struct small_val {
+	char buf[400];
+};
+
+struct big_val {
+	char buf[1000000];
+};
+
+struct {
+	__uint(type, BPF_MAP_TYPE_ARRAY);
+	__uint(max_entries, 1);
+	__type(key, int);
+	__type(value, struct small_val);
+} map_small SEC(".maps");
+
+struct {
+	__uint(type, BPF_MAP_TYPE_ARRAY);
+	__uint(max_entries, 1);
+	__type(key, int);
+	__type(value, struct big_val);
+} map_big SEC(".maps");
+
+struct {
+	__uint(type, BPF_MAP_TYPE_RINGBUF);
+	__uint(max_entries, 4096);
+} ringbuf SEC(".maps");
+
+#define LOOKUP(map)					\
+	"r1 = 0;"					\
+	"*(u64*)(r10 - 8) = r1;"			\
+	"r2 = r10;"					\
+	"r2 += -8;"					\
+	"r1 = %[" #map "] ll;"				\
+	"call %[bpf_map_lookup_elem];"			\
+	"if r0 == 0 goto l_exit_%=;"			\
+	"r7 = r0;"
+
+/* counter steps by 4 and the loop is left on '!=', 100 trips */
+SEC("socket")
+__success
+__naked void stride4_ne_100(void)
+{
+	asm volatile (
+	LOOKUP(map_small)
+	"r6 = 0;"
+"l_loop_%=:"
+	"r1 = r7;"
+	"r1 += r6;"
+	"r0 = *(u32*)(r1 + 0);"
+	"r6 += 4;"
+	"if r6 != 400 goto l_loop_%=;"
+"l_exit_%=:"
+	"r0 = 0;"
+	"exit;"
+	:
+	: __imm(bpf_map_lookup_elem), __imm_addr(map_small)
+	: __clobber_all);
+}
+
+/* same loop, 250000 trips, too many to walk every one of them */
+SEC("socket")
+__success
+__naked void stride4_ne_250k(void)
+{
+	asm volatile (
+	LOOKUP(map_big)
+	"r6 = 0;"
+"l_loop_%=:"
+	"r1 = r7;"
+	"r1 += r6;"
+	"r0 = *(u32*)(r1 + 0);"
+	"r6 += 4;"
+	"if r6 != 1000000 goto l_loop_%=;"
+"l_exit_%=:"
+	"r0 = 0;"
+	"exit;"
+	:
+	: __imm(bpf_map_lookup_elem), __imm_addr(map_big)
+	: __clobber_all);
+}
+
+/* 8 byte stride, 32-bit counter */
+SEC("socket")
+__success
+__naked void stride8_ne_w_125k(void)
+{
+	asm volatile (
+	LOOKUP(map_big)
+	"w6 = 0;"
+"l_loop_%=:"
+	"r1 = r7;"
+	"r1 += r6;"
+	"r0 = *(u64*)(r1 + 0);"
+	"w6 += 8;"
+	"if w6 != 1000000 goto l_loop_%=;"
+"l_exit_%=:"
+	"r0 = 0;"
+	"exit;"
+	:
+	: __imm(bpf_map_lookup_elem), __imm_addr(map_big)
+	: __clobber_all);
+}
+
+/* counts down by 4 to zero */
+SEC("socket")
+__success
+__naked void stride4_down_250k(void)
+{
+	asm volatile (
+	LOOKUP(map_big)
+	"r6 = 1000000;"
+"l_loop_%=:"
+	"r6 += -4;"
+	"r1 = r7;"
+	"r1 += r6;"
+	"r0 = *(u32*)(r1 + 0);"
+	"if r6 != 0 goto l_loop_%=;"
+"l_exit_%=:"
+	"r0 = 0;"
+	"exit;"
+	:
+	: __imm(bpf_map_lookup_elem), __imm_addr(map_big)
+	: __clobber_all);
+}
+
+/* step of 1 and '<', no alignment to make use of */
+SEC("socket")
+__success
+__naked void stride1_lt_1m(void)
+{
+	asm volatile (
+	LOOKUP(map_big)
+	"r6 = 0;"
+"l_loop_%=:"
+	"r1 = r7;"
+	"r1 += r6;"
+	"r0 = *(u8*)(r1 + 0);"
+	"r6 += 1;"
+	"if r6 < 1000000 goto l_loop_%=;"
+"l_exit_%=:"
+	"r0 = 0;"
+	"exit;"
+	:
+	: __imm(bpf_map_lookup_elem), __imm_addr(map_big)
+	: __clobber_all);
+}
+
+/* two loops, one in the other */
+SEC("socket")
+__success
+__naked void nested_stride4(void)
+{
+	asm volatile (
+	LOOKUP(map_big)
+	"r8 = 0;"
+"l_outer_%=:"
+	"r6 = 0;"
+"l_loop_%=:"
+	"r1 = r7;"
+	"r1 += r6;"
+	"r0 = *(u32*)(r1 + 0);"
+	"r6 += 4;"
+	"if r6 != 1000000 goto l_loop_%=;"
+	"r8 += 1;"
+	"if r8 != 1000 goto l_outer_%=;"
+"l_exit_%=:"
+	"r0 = 0;"
+	"exit;"
+	:
+	: __imm(bpf_map_lookup_elem), __imm_addr(map_big)
+	: __clobber_all);
+}
+
+/* the last trip reads 4 bytes at offset 400 of 400 */
+SEC("socket")
+__failure __msg("invalid access to map value")
+__naked void stride4_ne_one_too_many(void)
+{
+	asm volatile (
+	LOOKUP(map_small)
+	"r6 = 0;"
+"l_loop_%=:"
+	"r1 = r7;"
+	"r1 += r6;"
+	"r0 = *(u32*)(r1 + 0);"
+	"r6 += 4;"
+	"if r6 != 404 goto l_loop_%=;"
+"l_exit_%=:"
+	"r0 = 0;"
+	"exit;"
+	:
+	: __imm(bpf_map_lookup_elem), __imm_addr(map_small)
+	: __clobber_all);
+}
+
+/* same with too many trips to walk */
+SEC("socket")
+__failure __msg("BPF program is too large")
+__naked void stride4_ne_250k_one_too_many(void)
+{
+	asm volatile (
+	LOOKUP(map_big)
+	"r6 = 0;"
+"l_loop_%=:"
+	"r1 = r7;"
+	"r1 += r6;"
+	"r0 = *(u32*)(r1 + 0);"
+	"r6 += 4;"
+	"if r6 != 1000004 goto l_loop_%=;"
+"l_exit_%=:"
+	"r0 = 0;"
+	"exit;"
+	:
+	: __imm(bpf_map_lookup_elem), __imm_addr(map_big)
+	: __clobber_all);
+}
+
+/* the counter never equals the bound and reads out of bounds */
+SEC("socket")
+__failure __msg("BPF program is too large")
+__naked void stride4_ne_misses_bound(void)
+{
+	asm volatile (
+	LOOKUP(map_big)
+	"r6 = 0;"
+"l_loop_%=:"
+	"r1 = r7;"
+	"r1 += r6;"
+	"r0 = *(u32*)(r1 + 0);"
+	"r6 += 4;"
+	"if r6 != 999998 goto l_loop_%=;"
+"l_exit_%=:"
+	"r0 = 0;"
+	"exit;"
+	:
+	: __imm(bpf_map_lookup_elem), __imm_addr(map_big)
+	: __clobber_all);
+}
+
+/* the value read after the loop is at the exit value of the counter */
+SEC("socket")
+__failure __msg("BPF program is too large")
+__naked void stride4_ne_use_after_loop(void)
+{
+	asm volatile (
+	LOOKUP(map_big)
+	"r6 = 0;"
+"l_loop_%=:"
+	"r1 = r7;"
+	"r1 += r6;"
+	"r0 = *(u32*)(r1 + 0);"
+	"r6 += 4;"
+	"if r6 != 1000000 goto l_loop_%=;"
+	"r1 = r7;"
+	"r1 += r6;"
+	"r0 = *(u32*)(r1 + 0);"
+"l_exit_%=:"
+	"r0 = 0;"
+	"exit;"
+	:
+	: __imm(bpf_map_lookup_elem), __imm_addr(map_big)
+	: __clobber_all);
+}
+
+/*
+ * Nothing in the loop changes what it tests. may_goto that the verifier
+ * adds to the back-edge ends the program: 0 is returned instead of 2.
+ */
+SEC("socket")
+__success __retval(0)
+__naked void spin_until_flag(void)
+{
+	asm volatile (
+	LOOKUP(map_small)
+"l_loop_%=:"
+	"r0 = *(u32*)(r7 + 0);"
+	"if r0 == 0 goto l_loop_%=;"
+	"r0 = 2;"
+	"exit;"
+"l_exit_%=:"
+	"r0 = 1;"
+	"exit;"
+	:
+	: __imm(bpf_map_lookup_elem), __imm_addr(map_small)
+	: __clobber_all);
+}
+
+/* same with the back-edge that is not a conditional jump */
+SEC("socket")
+__success __retval(0)
+__naked void spin_until_flag_ja(void)
+{
+	asm volatile (
+	LOOKUP(map_small)
+"l_loop_%=:"
+	"r0 = *(u32*)(r7 + 0);"
+	"if r0 != 0 goto l_done_%=;"
+	"goto l_loop_%=;"
+"l_done_%=:"
+	"r0 = 2;"
+	"exit;"
+"l_exit_%=:"
+	"r0 = 1;"
+	"exit;"
+	:
+	: __imm(bpf_map_lookup_elem), __imm_addr(map_small)
+	: __clobber_all);
+}
+
+/* may_goto cannot end the program that holds a reference, every iteration is walked */
+SEC("socket")
+__success __retval(0)
+__naked void loop_with_reference(void)
+{
+	asm volatile (
+	"r1 = %[ringbuf] ll;"
+	"r2 = 8;"
+	"r3 = 0;"
+	"call %[bpf_ringbuf_reserve];"
+	"if r0 == 0 goto l_exit_%=;"
+	"r7 = r0;"
+	"r6 = 0;"
+"l_loop_%=:"
+	"r6 += 1;"
+	"if r6 != 100 goto l_loop_%=;"
+	"r1 = r7;"
+	"r2 = 0;"
+	"call %[bpf_ringbuf_discard];"
+"l_exit_%=:"
+	"r0 = 0;"
+	"exit;"
+	:
+	: __imm(bpf_ringbuf_reserve), __imm(bpf_ringbuf_discard), __imm_addr(ringbuf)
+	: __clobber_all);
+}
+
+char _license[] SEC("license") = "GPL";
-- 
2.55.0

Re: [PATCH bpf-next 2/8] bpf: Mark loop heads in check_cfg()

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [High] bpf: stale CFG backedge metadata causes incorrect loop detection
--

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

bpf: Mark loop heads in check_cfg()

check_cfg() finds back-edges while it walks the control flow graph.
Remember their targets as loop heads and which edge of the insn is
the back-edge. The main pass needs it to tell the state that enters
the loop from the state that went around it.
No functional change.

> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 92f528c456052..5a08f079a4896 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -709,6 +709,9 @@ struct bpf_insn_aux_data {
>  	u32 non_stack_access:1; /* instruction can access non-stack memory */
>  	/* true if some jump or call instruction targets this instruction */
>  	u32 jump_target:1;
> +	u32 loop_head:1; /* target of a back-edge */
> +	u32 backedge_ft:1; /* the edge to the next insn is a back-edge */
> +	u32 backedge_br:1; /* the jump is a back-edge */

[Severity: High]
Does this new CFG metadata need to be cleared when dead conditional jumps are
rewritten?

When bpf_prune_dead_branches() in kernel/bpf/const_fold.c rewrites dead
conditional jumps into unconditional BPF_JA jumps:

kernel/bpf/const_fold.c:bpf_prune_dead_branches()
    *insn = BPF_JMP_A(taken ? insn->off : 0);
    changed = true;

it does not seem to clear the newly added backedge_br or backedge_ft metadata.

If a pruned branch was a back-edge but the actually taken branch is a forward
edge, and a later function like is_backedge() assumes unconditional jumps have
only a single edge:

kernel/bpf/states.c:is_backedge()
    if ((BPF_CLASS(insn->code) == BPF_JMP || BPF_CLASS(insn->code) == BPF_JMP32) &&
        BPF_OP(insn->code) == BPF_JA)
        return aux->backedge_ft || aux->backedge_br;

could this stale metadata cause forward edges to be incorrectly classified as
loop back-edges? This might lead to spurious state widening and the addition
of unnecessary may_goto loop guards.

>  	/*
>  	 * CFG strongly connected component this instruction belongs to,
>  	 * zero if it is a singleton SCC.

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

Re: [PATCH bpf-next 8/8] selftests/bpf: Add tests for widened loops

[bot+bpf-ci]

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

> diff --git a/tools/testing/selftests/bpf/prog_tests/verifier.c b/tools/testing/selftests/bpf/prog_tests/verifier.c
> index 4f1e1c1cd5ab3..5bed8f9587772 100644
> --- a/tools/testing/selftests/bpf/prog_tests/verifier.c
> +++ b/tools/testing/selftests/bpf/prog_tests/verifier.c
> @@ -65,6 +65,7 @@
>  #include "verifier_live_stack.skel.h"
>  #include "verifier_liveness_exp.skel.h"
>  #include "verifier_load_acquire.skel.h"
> +#include "verifier_loop_widen.skel.h"
>  #include "verifier_loops1.skel.h"
>  #include "verifier_lwt.skel.h"
>  #include "verifier_map_in_map.skel.h"
> @@ -234,6 +235,7 @@ void test_verifier_leak_ptr(void)             { RUN(verifier_leak_ptr); }
>  void test_verifier_linked_scalars(void)       { RUN(verifier_linked_scalars); }
>  void test_verifier_live_stack(void)           { RUN(verifier_live_stack); }
>  void test_verifier_liveness_exp(void)         { RUN(verifier_liveness_exp); }
> +void test_verifier_loop_widen(void)           { RUN(verifier_loop_widen); }
>  void test_verifier_loops1(void)               { RUN(verifier_loops1); }
>  void test_verifier_lwt(void)                  { RUN(verifier_lwt); }
>  void test_verifier_map_in_map(void)           { RUN(verifier_map_in_map); }

Does this registration need architecture filtering? Several of the
__success subtests in verifier_loop_widen.c appear to require JIT
exception support for the loop widening path to work.

Looking at the series, commit 3a779857709c5 ("bpf: Add may_goto to loops
that are not walked to the end") shows that widening at a loop head happens
only when loop_head_guard() returns true. In bpf_is_state_visited(), when
cannot_throw() returns a reason string, the code does:

    if (!loop_head_guard(env, insn_idx, widen_from, cur)) {
        loop_head = false;
        widen_from = NULL;
    }

And in cannot_throw() (kernel/bpf/verifier.c):

    if (!env->prog->jit_requested || !bpf_jit_supports_exceptions())
        return "JIT does not support exceptions";

Only x86 (with CONFIG_UNWINDER_ORC), arm64, s390 and powerpc64 implement
bpf_jit_supports_exceptions(). On riscv64 and loongarch, the __weak default
returns false.

When widening is not available, the verifier walks every loop iteration.
Tests like stride4_ne_250k, stride4_down_250k, stride1_lt_1m, and
nested_stride4 each need well over 1M processed instructions (stride4_ne_250k
alone is 250000 trips x 5 insns), so they fail with "BPF program is too
large" even though they are annotated __success.

Similarly, spin_until_flag and spin_until_flag_ja are not widened on those
platforms, so their infinite loops are rejected instead of getting a
may_goto guard.

tools/testing/selftests/bpf/DENYLIST.riscv64 already has an entry for
the exceptions test:

    exceptions                              # JIT does not support exceptions

But there's no corresponding entry for verifier_loop_widen. Other tests
that depend on this capability use __arch_x86_64, __arch_arm64, __arch_s390x
tags (like progs/verifier_may_goto_1.c does), or __load_if_JITed().

Should verifier_loop_widen either be added to DENYLIST.riscv64 and similar
deny lists, or should the architecture-dependent tests in
progs/verifier_loop_widen.c use __arch_* or __load_if_JITed() annotations
to skip on platforms without exception support?

> diff --git a/tools/testing/selftests/bpf/progs/verifier_loop_widen.c b/tools/testing/selftests/bpf/progs/verifier_loop_widen.c
> new file mode 100644
> index 0000000000000..4bdfc198bfaa8
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/progs/verifier_loop_widen.c

[ ... ]

> +/* same loop, 250000 trips, too many to walk every one of them */
> +SEC("socket")
> +__success
> +__naked void stride4_ne_250k(void)

[ ... ]

> +/* 8 byte stride, 32-bit counter */
> +SEC("socket")
> +__success
> +__naked void stride8_ne_w_125k(void)

[ ... ]

> +/* counts down by 4 to zero */
> +SEC("socket")
> +__success
> +__naked void stride4_down_250k(void)

[ ... ]

> +/* step of 1 and '<', no alignment to make use of */
> +SEC("socket")
> +__success
> +__naked void stride1_lt_1m(void)

[ ... ]

> +/* two loops, one in the other */
> +SEC("socket")
> +__success
> +__naked void nested_stride4(void)

[ ... ]

> +/*
> + * Nothing in the loop changes what it tests. may_goto that the verifier
> + * adds to the back-edge ends the program: 0 is returned instead of 2.
> + */
> +SEC("socket")
> +__success __retval(0)
> +__naked void spin_until_flag(void)

[ ... ]

> +/* same with the back-edge that is not a conditional jump */
> +SEC("socket")
> +__success __retval(0)
> +__naked void spin_until_flag_ja(void)

[ ... ]


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

Re: [PATCH bpf-next 6/8] bpf: Walk loops with widened states first

[bot+bpf-ci]

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

> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index fb35f8a7aedd2..e02ee286067d2 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -1068,6 +1068,8 @@ struct bpf_verifier_env {
>  	bool widen_loops;
>  	/* the walk did or tried that, so a failure can be due to the lost precision */
>  	bool widen_used;
> +	/* insns processed by a walk that was given up */
> +	u32 insn_wasted;
>  	struct bpf_iarray *succ;
>  	struct bpf_iarray *gotox_tmp_buf;
>  };
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 2fb5a66bd7d49..871aa45031d61 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c

[ ... ]

> +/* What a walk changes outside of verifier states and per insn data. */
> +struct walk_snapshot {
> +	struct bpf_insn_aux_data *insn_aux;
> +	struct bpf_func_info_aux *func_aux;
> +	struct bpf_subprog_info *subprogs;
> +	struct bpf_prog *prog;
> +	u64 log_pos, diag_pos;
> +	u32 insn_processed, prev_insn_processed;
> +	u32 jmps_processed, prev_jmps_processed;
> +	u32 total_states, peak_states, max_states_per_insn, longest_mark_read_walk;
> +	u32 explored_states_size, free_list_size, num_backedges;
> +	u32 id_gen, pass_cnt, max_stack_depth;
> +	u32 max_ctx_offset, max_pkt_offset, max_tp_access, max_rdonly_access, max_rdwr_access;
> +	bool seen_direct_write, seen_exception, explore_alu_limits, tail_call_reachable;
> +	void *arena;
> +};

[ ... ]

> +static void walk_snapshot_restore(struct bpf_verifier_env *env, struct walk_snapshot *s)
> +{
> +	struct bpf_prog_aux *aux = env->prog->aux;
> +
> +	memcpy(env->insn_aux_data, s->insn_aux,
> +	       array_size(env->prog->len, sizeof(*env->insn_aux_data)));
> +	memcpy(env->subprog_info, s->subprogs, sizeof(env->subprog_info));
> +	memcpy(env->prog, s->prog, offsetof(struct bpf_prog, insnsi));
                    ^^^^

Does this memcpy leak a callchain buffer reference?

The bpf_prog header (everything before insnsi) contains the bitfield
has_callchain_buf (include/linux/bpf.h:1926). This is not just a flag -
it records that a reference was taken on the global perf callchain buffers.

check_helper_call() takes the reference when it encounters
bpf_get_stack() or bpf_get_task_stack():

kernel/bpf/verifier.c:check_helper_call() {
    if ((func_id == BPF_FUNC_get_stack ||
         func_id == BPF_FUNC_get_task_stack) &&
        !env->prog->has_callchain_buf) {
        ...
        err = get_callchain_buffers(sysctl_perf_event_max_stack);
        ...
        env->prog->has_callchain_buf = true;
    }
}

The matching put is only in bpf_prog_free_deferred():

kernel/bpf/core.c:bpf_prog_free_deferred() {
    if (aux->prog->has_callchain_buf)
        put_callchain_buffers();
}

Consider this sequence when the widened walk fails and is redone:

1. walk_snapshot_save() snapshots the header with has_callchain_buf == 0

2. The widened walk reaches bpf_get_stack() or bpf_get_task_stack() for
   the first time. get_callchain_buffers() increments nr_callchain_events
   and sets has_callchain_buf = 1

3. The walk fails with widen_used set (e.g. -EINVAL, -EACCES, or -E2BIG
   from bpf_commit_loop_guards()). walk_snapshot_restore() copies the
   saved header back with has_callchain_buf == 0, but the reference is
   still held

4. The second walk reaches the helper again. Since has_callchain_buf is
   0, get_callchain_buffers() is called again, incrementing
   nr_callchain_events a second time and setting the bit

5. When the program is freed, bpf_prog_free_deferred() calls
   put_callchain_buffers() once, so one reference leaks

Each such load leaks one count on nr_callchain_events. The count never
returns to zero, so release_callchain_buffers() never runs and the per-CPU
callchain buffers stay allocated forever.

Also, perf_event_max_stack_handler() in kernel/events/callchain.c returns
-EBUSY while nr_callchain_events != 0, so writes to the
kernel.perf_event_max_stack and kernel.perf_event_max_contexts_per_stack
sysctls fail permanently once this happens.

Trigger requirements (all reachable today):
- The program is loaded with bpf_capable
- It has a loop (scc_cnt > 1) and is not offloaded
- It calls bpf_get_stack() or bpf_get_task_stack()
- The widened walk fails with widen_used set

The commit message says 126 selftests programs are walked twice, so the
redo path is hit often. Any repeated load of such a program leaks more
references.

The commit message says the restore covers the "flags of the prog", but
has_callchain_buf is a flag that owns a resource. Should the restore
either preserve has_callchain_buf across the memcpy (save and OR it back
in afterwards) or call put_callchain_buffers() when the live header has
the bit set and the snapshot does not?

> +	if (s->func_aux)
> +		memcpy(aux->func_info_aux, s->func_aux, func_aux_size(env));

[ ... ]

> +	if (!(env->log.level & BPF_LOG_LEVEL2))
> +		bpf_vlog_reset(&env->log, s->log_pos);
> +	bpf_diag_event_log_restore(env, s->diag_pos);
> +}

[ ... ]

> +static int do_check_prog(struct bpf_verifier_env *env)
> +{
> +	struct walk_snapshot snap;
> +	int ret;
> +
> +	/* no loops without bpf_capable, the driver of an offloaded prog sees every insn visit */
> +	if (!env->bpf_capable || env->scc_cnt <= 1 || bpf_prog_is_offloaded(env->prog->aux)) {
> +		ret = do_check_main(env);
> +		return ret ?: do_check_subprogs(env);
> +	}
> +
> +	env->scc_converged = kvzalloc_objs(*env->scc_converged, BITS_TO_LONGS(env->scc_cnt),
> +					   GFP_KERNEL_ACCOUNT);
> +	if (!env->scc_converged)
> +		return -ENOMEM;
> +	ret = walk_snapshot_save(env, &snap);
> +	if (ret)
> +		return ret;
> +
> +	env->widen_loops = true;
> +	env->widen_used = false;
> +	ret = do_check_main(env);
> +	ret = ret ?: do_check_subprogs(env);
> +	if (!ret && env->widen_used)
> +		ret = bpf_commit_loop_guards(env);
> +	env->widen_loops = false;
> +	if (ret && ret != -ENOMEM && ret != -EAGAIN && ret != -EFAULT && env->widen_used) {
> +		walk_snapshot_restore(env, &snap);
> +		if (env->log.level & BPF_LOG_LEVEL)
> +			verbose(env, "walk with widened loops failed, walking every iteration\n");
> +		ret = do_check_main(env);
> +		ret = ret ?: do_check_subprogs(env);
> +	}
> +	walk_snapshot_free(&snap);
> +	return ret;
> +}

[ ... ]


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

Re: [PATCH bpf-next 4/8] bpf: Detect loops that never exit

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
- [High] bpf: bpf_throw() in subprogram fails to mark caller's loop as exited
- [Medium] bpf: infinite loops bypass detection due to flawed branches == 0 check
--

commit 62aaae8d61f9848eafade71feeeed8eb13c4f0d6
Author: Alexei Starovoitov <ast@kernel.org>

bpf: Detect loops that never exit

This commit introduces detection of infinite loops in BPF programs by tracking
whether a loop was ever exited during verification. It adds state tracking via
visit->exited and marks states as exited using bpf_scc_mark_exit().

> diff --git a/kernel/bpf/states.c b/kernel/bpf/states.c
> index 22987ce070e74..39e6052922e59 100644
> --- a/kernel/bpf/states.c
> +++ b/kernel/bpf/states.c
[ ... ]
> @@ -221,6 +232,32 @@ static int maybe_exit_scc(struct bpf_verifier_env *env, struct bpf_verifier_stat
>  	return propagate_backedges(env, visit);
>  }
>  
> +/*
> + * @st left the loop that @insn_idx of its current frame is in. The loop is
> + * left when the frame that bpf_scc_visit is for leaves it. Loops in callees
> + * of that frame are part of one trip around the loop of the caller.
> + */
> +void bpf_scc_mark_exit(struct bpf_verifier_env *env, struct bpf_verifier_state *st, int insn_idx)
> +{
> +	struct bpf_scc_callchain *callchain = &env->callchain_buf;
> +	struct bpf_scc_visit *visit;
> +	u32 i, callsite;
> +
> +	if (st->speculative || !env->insn_aux_data[insn_idx].scc)
> +		return;
> +	memset(callchain, 0, sizeof(*callchain));
> +	for (i = 0; i < st->curframe; i++) {
> +		callsite = bpf_frame_insn_idx(st, i);
> +		if (env->insn_aux_data[callsite].scc)
> +			return;

[Severity: High]
Does this early return prevent caller loops from being marked as exited during
a global stack-unwinding event like bpf_throw()? 

If a BPF program loop calls a subprogram, and the subprogram calls bpf_throw(),
the verifier processes PROCESS_BPF_EXIT in do_check():

    } else if (err == PROCESS_BPF_EXIT) {
        /* exit or bpf_throw() inside of a loop */
        if (env->widen_loops)
            bpf_scc_mark_exit(env, state, env->insn_idx);

This invokes bpf_scc_mark_exit() with the instruction index of bpf_throw().
However, since bpf_scc_mark_exit() returns early here if any caller frame
is in an SCC, it fails to mark the caller's loop as exited.

As a result, when the loop's entry state is fully explored, maybe_exit_scc()
finds visit->exited == false and could falsely reject valid programs.

> +		callchain->callsites[i] = callsite;
> +	}
> +	callchain->scc = env->insn_aux_data[insn_idx].scc;
> +	visit = scc_visit_lookup(env, callchain);
> +	if (visit)
> +		visit->exited = true;
> +}
[ ... ]
> @@ -1462,6 +1499,9 @@ int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx)
>  		if (states_equal(env, &sl->state, cur, loop ? RANGE_WITHIN : NOT_EXACT)) {
>  hit:
>  			sl->hit_cnt++;
> +			/* what follows the old state was seen, it may leave the loop */
> +			if (env->widen_loops && !sl->state.branches)
> +				bpf_scc_mark_exit(env, cur, insn_idx);

[Severity: Medium]
Does this logic correctly handle paths that only loop back and prune?

The assumption here seems to be that an explored state (branches == 0) must
have successfully left the loop. However, a state can reach branches == 0
simply because all its paths looped back to the widened loop head and pruned.

If an infinite loop explores such a path, and a subsequent path hits one of
the first path's intermediate states, this logic will prematurely set
visit->exited = true. Will this bypass the verifier's static infinite loop
detection and incorrectly accept the program?

>  
>  			/* if previous state reached the exit with precision and
>  			 * current state is equivalent to it (except precision marks)

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

Re: [PATCH bpf-next 2/8] bpf: Mark loop heads in check_cfg()

[bot+bpf-ci]

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

> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 92f528c456052..5a08f079a4896 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -709,6 +709,9 @@ struct bpf_insn_aux_data {
>  	u32 non_stack_access:1; /* instruction can access non-stack memory */
>  	/* true if some jump or call instruction targets this instruction */
>  	u32 jump_target:1;
> +	u32 loop_head:1; /* target of a back-edge */
> +	u32 backedge_ft:1; /* the edge to the next insn is a back-edge */
> +	u32 backedge_br:1; /* the jump is a back-edge */

Do these comments accurately describe what push_insn() records? The bit
seems to be chosen by push_insn()'s e argument rather than by where the edge
actually goes.

Looking at visit_insn() in kernel/bpf/cfg.c, it walks the only edge of an
unconditional jump as FALLTHROUGH:

kernel/bpf/cfg.c:visit_insn() {
    /* unconditional jump with single edge */
    ret = push_insn(t, t + off + 1, FALLTHROUGH, env);
}

For a backward goto/gotol, wouldn't the jump back-edge set backedge_ft, with
backedge_br staying clear even though "the jump is a back-edge"?

Similarly, for ldimm64 (including the pseudo func load) the FALLTHROUGH edge
goes to t + 2, not t + 1, and for the pseudo func the BRANCH edge goes to a
callback entry which is not a jump.

This mismatch affects the series. is_backedge() in de2a4da618ff needs its
own note ("check_cfg() does not record the edge of an unconditional jump as
a jump"). It picks the bit with insn_idx == prev + 1, which means it reads
backedge_br for a back-edge that is the fall-through of an ldimm64 (do_check()
goes from t to t + 2 with prev_insn_idx == t). It does the same for the
fall-through of a call to a static subprog, where env->prev_insn_idx at
callsite + 1 is the callee's BPF_EXIT (prepare_func_exit()). In both cases
loop_head_guard() then skips the may_goto guard.

Could the comments say these are the FALLTHROUGH and BRANCH edges as
check_cfg() walks them? That would clarify the intent for later readers.

>  	/*
>  	 * CFG strongly connected component this instruction belongs to,
>  	 * zero if it is a singleton SCC.
> diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
> index 842c7d1eabccc..748bf544d3ba5 100644
> --- a/kernel/bpf/cfg.c
> +++ b/kernel/bpf/cfg.c
> @@ -137,8 +137,14 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env)
>  		insn_stack[env->cfg.cur_stack++] = w;
>  		return KEEP_EXPLORING;
>  	} else if ((insn_state[w] & 0xF0) == DISCOVERED) {
> -		if (env->bpf_capable)
> +		if (env->bpf_capable) {
> +			env->insn_aux_data[w].loop_head = true;
> +			if (e == FALLTHROUGH)
> +				env->insn_aux_data[t].backedge_ft = true;
> +			else
> +				env->insn_aux_data[t].backedge_br = true;
>  			return DONE_EXPLORING;
> +		}
>  		verbose_linfo(env, t, "%d: ", t);
>  		verbose_linfo(env, w, "%d: ", w);
>  		verbose(env, "back-edge from insn %d to %d\n", t, w);

Loop heads and back-edges are recorded here in push_insn(). But check_cfg()
also finds back-edges in visit_gotox_insn(), which still drops them without
recording:

kernel/bpf/cfg.c:415 visit_gotox_insn() {
    /* EXPLORED || DISCOVERED */
    if (insn_state[w])
        continue;
}

A DISCOVERED target at that point is a back-edge of the indirect jump. It
sets neither loop_head on w nor a backedge bit on t. So the commit message's
"check_cfg() finds back-edges ... Remember their targets as loop heads"
doesn't hold for gotox. Loops closed by a computed goto (goto *jt[i] to a
label at the loop top, as exercised in selftests/bpf/progs/bpf_gotox.c) get
no loop head. A gotox back-edge to a head marked through another edge also
looks like an entry edge.

Nothing reads the bits in this commit. But the later commits in
8f70ee36d2ef..7d6b7dd8cb91 assume every back-edge is recorded:

de2a4da618ff ("bpf: Widen scalars at loop heads"): is_backedge() returns
aux->backedge_ft || aux->backedge_br for any BPF_JA prev insn. For gotox
that is always false. The same commit changes the EXACT-repeat check in
bpf_is_state_visited() so that under widen_loops it prunes (loop = true)
instead of reporting "infinite loop detected".

3a779857709c ("bpf: Add may_goto to loops that are not walked to the end"):
loop_head_guard() returns true without a guard when !is_backedge().
bpf_mark_loop_guard() has an explicit gotox case (op == BPF_JA &&
BPF_SRC(insn->code) == BPF_X -> "not a jump" -> guard_impossible). That case
can never be reached, because the bits are never set for gotox.

Scenario at 7d6b7dd8cb91 (bpf_capable):

  head:
      v = *(volatile u32 *)map_val;
      goto *jt[v & 1];        /* jt = { &&head, &&out } */
  out:
      return 0;

push_insn() sees no back-edge, so there is no loop head. visit_gotox_insn()
makes the gotox insn a prune point. On the second trip the state there is
EXACT equal to the in-progress one, so it is pruned with widen_used. The out
target leaves the SCC, so "loop ... never exits" does not fire.
bpf_commit_loop_guards() has no guard_pending or guard_impossible to act on,
and the program is accepted with nothing bounding the loop at run time.
Before the series this was rejected with "infinite loop detected". The same
happens if head also has a conditional back-edge: that edge gets a may_goto,
but the gotox edge does not.

Should visit_gotox_insn() also mark loop_head on DISCOVERED targets and
record the back-edge on the gotox insn (for example backedge_br)? The later
bpf_mark_loop_guard() would then set guard_impossible and fall back to
walking every iteration.


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

Re: [PATCH bpf-next 7/8] selftests/bpf: Adjust tests to widened loops

[bot+bpf-ci]

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

> diff --git a/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c b/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
> index 902a70d5afeb6..2dc37090d7a4f 100644
> --- a/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
> +++ b/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c

[ ... ]

> diff --git a/tools/testing/selftests/bpf/progs/verifier_cfg.c b/tools/testing/selftests/bpf/progs/verifier_cfg.c
> index 3c3bb03e8217a..700eadf5d430a 100644
> --- a/tools/testing/selftests/bpf/progs/verifier_cfg.c
> +++ b/tools/testing/selftests/bpf/progs/verifier_cfg.c
> @@ -98,8 +98,8 @@ l0_%=:	r1 = r0;					\
>
>  SEC("socket")
>  __description("conditional loop")
> -__failure __msg("infinite loop detected")
> -__msg_unpriv("back-edge")
> +__success
> +__failure_unpriv __msg_unpriv("back-edge")
>  __naked void conditional_loop(void)
>  {
>  	asm volatile ("					\

Can this test pass on arches where the JIT doesn't support exceptions?
Adding the may_goto guard depends on bpf_jit_supports_exceptions()
returning true in the verifier's cannot_throw() check. When that check
fails, the loop isn't widened, and the verifier rejects the program with
"infinite loop detected" or "BPF program is too large" like before the
series.

Looking at bpf_jit_supports_exceptions() in kernel/bpf/verifier.c:

	if (!env->prog->jit_requested || !bpf_jit_supports_exceptions())
		return "JIT does not support exceptions";

Arches where bpf_jit_supports_exceptions() is false include riscv64
(which has an official config.riscv64, and DENYLIST.riscv64 already lists
"exceptions # JIT does not support exceptions"), loongarch, ppc32, and x86
without CONFIG_UNWINDER_ORC. Kernels with the JIT disabled are also
affected.

This applies to the other tests updated in this commit as well:
 - verifier_movsx: MOV32SX, S8, var_off u32_max
 - verifier_search_pruning: short_loop1
 - verif_scale_loop3
 - test_verifier: "calls: conditional call 6"

None of these use __load_if_JITed(), __arch_x86_64, __arch_arm64,
__arch_s390x gating, F_NEEDS_JIT_ENABLED, or DENYLIST.riscv64 entries,
so they will fail instead of being skipped on those arches.

Per the selftests guide, a test that fails when a capability is missing,
instead of skipping, is a bug.

Should these tests be gated on JIT plus exception support? For example,
__load_if_JITed() and arch masks in the test_loader programs,
F_NEEDS_JIT_ENABLED for test_verifier, and a skip for verif_scale_loop3,
or adding them to DENYLIST.riscv64?

> diff --git a/tools/testing/selftests/bpf/progs/verifier_movsx.c b/tools/testing/selftests/bpf/progs/verifier_movsx.c
> index 195b27a51224f..280ccee336635 100644
> --- a/tools/testing/selftests/bpf/progs/verifier_movsx.c
> +++ b/tools/testing/selftests/bpf/progs/verifier_movsx.c

[ ... ]

> diff --git a/tools/testing/selftests/bpf/progs/verifier_precision.c b/tools/testing/selftests/bpf/progs/verifier_precision.c
> index f4459561bf393..88358586e7964 100644
> --- a/tools/testing/selftests/bpf/progs/verifier_precision.c
> +++ b/tools/testing/selftests/bpf/progs/verifier_precision.c
> @@ -152,22 +152,21 @@ __naked int bpf_store_release(void)
>  SEC("?raw_tp")
>  __success __log_level(2)
>  /*
> - * Without the bug fix there will be no history between "last_idx 3 first_idx 3"
> - * and "parent state regs=" lines. "R0=6" parts are here to help anchor
> - * expected log messages to the one specific mark_chain_precision operation.
> - *
> - * This is quite fragile: if verifier checkpointing heuristic changes, this
> - * might need adjusting.
> + * The state is widened when it comes back to the loop head, so the exit test
> + * is decided only on the first trip around the loop. "R0=2" parts are here to
> + * help anchor expected log messages to that mark_chain_precision operation.
>   */
> -__msg("2: (07) r0 += 1                       ; R0=6")
> +__msg("2: (07) r0 += 1                       ; R0=2")
>  __msg("3: (35) if r0 >= 0xa goto pc+1")
> -__msg("mark_precise: frame0: last_idx 3 first_idx 3 subseq_idx -1")
> +__msg("mark_precise: frame0: last_idx 3 first_idx 1 subseq_idx -1")
>  __msg("mark_precise: frame0: regs=r0 stack= before 2: (07) r0 += 1")
>  __msg("mark_precise: frame0: regs=r0 stack= before 1: (07) r0 += 1")
> -__msg("mark_precise: frame0: regs=r0 stack= before 4: (05) goto pc-4")
> -__msg("mark_precise: frame0: regs=r0 stack= before 3: (35) if r0 >= 0xa goto pc+1")
> -__msg("mark_precise: frame0: parent state regs= stack=:  R0=P4")
> -__msg("3: R0=6")
> +__msg("mark_precise: frame0: parent state regs=r0 stack=:  R0=P0")
> +__msg("mark_precise: frame0: last_idx 0 first_idx 0 subseq_idx 1")
> +__msg("mark_precise: frame0: regs=r0 stack= before 0: (b7) r0 = 0")
> +__msg("3: R0=2")
> +__msg("loop head 1 widened, pass 1")
> +__msg("1: safe")
>  __naked int state_loop_first_last_equal(void)
>  {
>  	asm volatile (
> @@ -175,11 +174,7 @@ __naked int state_loop_first_last_equal(void)
>  	"l0_%=:"
>  		"r0 += 1;"
>  		"r0 += 1;"
> -		/* every few iterations we'll have a checkpoint here with
> -		 * first_idx == last_idx, potentially confusing precision
> -		 * backtracking logic
> -		 */
> -		"if r0 >= 10 goto l1_%=;"	/* checkpoint + mark_precise */
> +		"if r0 >= 10 goto l1_%=;"	/* mark_precise */
>  		"goto l0_%=;"
>  	"l1_%=:"
>  		"exit;"

Does this test still cover the original bug it was written to test?
state_loop_first_last_equal was the regression test for precision
backtracking when a checkpoint has first_idx == last_idx and jump history.
The old expectations checked the "before 4: (05) goto pc-4" / "before 3:
(35) if r0 >= 0xa" history between "last_idx 3 first_idx 3" and "parent
state regs=" lines.

As the commit message says, loop widening means that checkpoint no longer
happens. The test now only checks one straight-line backtrack from the
first trip. The name no longer describes what it tests, and nothing else
covers the first_idx == last_idx case.

The backtracking code in bpf_mark_chain_precision/get_prev_insn_idx is
unchanged and still runs through the every-iteration walk in these cases:

	loops that hold references or locks
	callbacks
	fallback walk after a widened walk fails
	JITs without exception support

So a regression of the original bug would no longer be caught on
JIT-capable arches.

Should there be a variant that forces the old walk, for example by holding
a reference across the loop or using a program type where 0 is not a valid
return value, and keep the old expectations for that variant?

> diff --git a/tools/testing/selftests/bpf/progs/verifier_search_pruning.c b/tools/testing/selftests/bpf/progs/verifier_search_pruning.c
> index f40e57251e941..7098b44faafc5 100644
> --- a/tools/testing/selftests/bpf/progs/verifier_search_pruning.c
> +++ b/tools/testing/selftests/bpf/progs/verifier_search_pruning.c

[ ... ]

> diff --git a/tools/testing/selftests/bpf/verifier/calls.c b/tools/testing/selftests/bpf/verifier/calls.c
> index 8b94b87135bcf..c7c501bfc660a 100644
> --- a/tools/testing/selftests/bpf/verifier/calls.c
> +++ b/tools/testing/selftests/bpf/verifier/calls.c

[ ... ]


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

Re: [PATCH bpf-next 5/8] bpf: Add may_goto to loops that are not walked to the end

[bot+bpf-ci]

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

> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 60f483d7e4a96..fb35f8a7aedd2 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h

[ ... ]

> diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c
> index 2add8001c3ec3..2b965fa4bacc0 100644
> --- a/kernel/bpf/fixups.c
> +++ b/kernel/bpf/fixups.c

[ ... ]

> @@ -1537,6 +1537,143 @@ static int add_hidden_subprog(struct bpf_verifier_env *env, struct bpf_insn *pat
>  /* Do various post-verification rewrites in a single program pass.
>   * These rewrites simplify JIT and interpreter implementations.
>   */
> +/*
> + * The walk with widened loops is done. Loops where some state came back to
> + * a state that was still walked were not walked to the end and have to be
> + * bounded at run time.
> + */
> +int bpf_commit_loop_guards(struct bpf_verifier_env *env)
> +{
> +	struct bpf_insn_aux_data *aux = env->insn_aux_data;
> +	int i;
> +
> +	for (i = 0; i < env->prog->len; i++) {
> +		if (!aux[i].scc || !test_bit(aux[i].scc, env->scc_converged))
> +			continue;
> +		if (aux[i].guard_impossible) {
> +			verbose(env, "loop with back-edge at insn %d cannot be bounded\n", i);
> +			return -E2BIG;
> +		}
> +		if (aux[i].guard_pending) {
> +			aux[i].loop_guard = true;
> +			env->seen_exception = true;
> +		}
> +	}
> +	return 0;
> +}

[ ... ]

> +/*
> + * The main pass went over the back-edge of jump @insn at @idx with a state
> + * that stands for any number of iterations. Nothing bounds the loop at run
> + * time, so add may_goto to the back-edge. The program cannot go on when
> + * may_goto is out of budget: nothing but the loop was verified for the state
> + * in the loop. Call bpf_throw(). The main pass made sure it can be called.
> + *
> + * back-edge is the jump:             back-edge is the edge to the next insn:
> + *   if cond goto guard                 if cond goto target
> + *   goto next                        guard:
> + * guard:                               may_goto throw
> + *   may_goto throw                     goto next
> + *   goto head                        throw:
> + * throw:                               r1 = 0
> + *   r1 = 0                             call bpf_throw
> + *   call bpf_throw                   next:
> + * next:
> + *
> + * Returns the number of insns in @buf.
> + */
> +static int add_loop_guard(struct bpf_verifier_env *env, int idx, struct bpf_insn *buf,
> +			  int stack_depth, u16 *stack_depth_extra)
> +{
> +	struct bpf_insn_aux_data *aux = &env->insn_aux_data[idx];
> +	struct bpf_insn orig = env->prog->insnsi[idx];
> +	bool ja = BPF_OP(orig.code) == BPF_JA;
> +	bool gotol = ja && BPF_CLASS(orig.code) == BPF_JMP32;
> +	int target = idx + 1 + (gotol ? orig.imm : orig.off);
> +	bool guard_jump_edge = ja || aux->backedge_br;
> +	struct bpf_insn *p = buf, *jeq, *skip = NULL, *back = NULL;
> +	int stack_off, cnt, err = 0;
> +
> +	if (guard_jump_edge && !ja) {
> +		*p = orig;
> +		p->off = 1;
> +		p++;
> +		skip = p;
> +		*p++ = BPF_JMP_A(0);
> +	} else if (!guard_jump_edge) {
> +		*p++ = orig;
> +	}
> +
> +	/* the same insns may_goto is replaced with, see bpf_do_misc_fixups() */
> +	if (bpf_jit_supports_timed_may_goto()) {
> +		stack_off = -stack_depth - 16;
> +		*stack_depth_extra = 16;
> +		*p++ = BPF_LDX_MEM(BPF_DW, BPF_REG_AX, BPF_REG_10, stack_off);

If a subprogram has multiple loops, will add_loop_guard() be called
multiple times?

Looking at bpf_commit_loop_guards():

    for (i = 0; i < env->prog->len; i++) {
        if (aux[i].guard_pending) {
            aux[i].loop_guard = true;

and bpf_do_misc_fixups():

    for (i = 0; i < insn_cnt;) {
        if (env->insn_aux_data[i + delta].loop_guard) {
            cnt = add_loop_guard(env, i + delta, insn_buf, stack_depth,
                                 &stack_depth_extra);

add_loop_guard() gets called once per back-edge that needs a guard.

When bpf_jit_supports_timed_may_goto() returns true, add_loop_guard()
computes stack_off = -stack_depth - 16 and sets *stack_depth_extra = 16.

If add_loop_guard() is called a second time for another back-edge in the
same subprogram, it will compute the same stack_off and overwrite
stack_depth_extra with 16 again.

Both guards would use the same stack slot (-stack_depth - 16), corrupting
each other's loop counters.

Further down in bpf_do_misc_fixups(), the code checks:

    int stack_slots = subprogs[i].stack_extra / 8;
    int slots = delta;  // delta = 2 for timed
    if (stack_slots > slots) {
        verifier_bug(env, "stack_slots supports may_goto only");
        return -EFAULT;
    }

With one guard: stack_extra=16, stack_slots=2, slots=2 => passes
With two guards: stack_extra=16 (wrong!), stack_slots=2, slots=2 => passes
but the guards share one slot

Should the timed case accumulate stack_depth_extra?

    stack_off = -stack_depth - *stack_depth_extra - 16;
    *stack_depth_extra += 16;

The non-timed case has a similar issue:

> +	} else {
> +		stack_off = -stack_depth - 8;
> +		*stack_depth_extra = max_t(u16, *stack_depth_extra, 8);

If a subprogram has multiple non-timed guards, they would all compute
stack_off = -stack_depth - 8 and share the same stack slot.

Should this also accumulate?

    stack_off = -stack_depth - *stack_depth_extra - 8;
    *stack_depth_extra += 8;

[ ... ]

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 06dc269991b22..2fb5a66bd7d49 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -8322,6 +8322,73 @@ int bpf_widen_loop_head(struct bpf_verifier_env *env, int insn_idx, bool backedg
>  	return 0;
>  }
>
> +static bool program_returns_void(struct bpf_verifier_env *env);
> +static bool return_retval_range(struct bpf_verifier_env *env, struct bpf_retval_range *range);
> +
> +/* Why bpf_throw() cannot be called in @st, NULL if it can. */
> +static const char *cannot_throw(struct bpf_verifier_env *env, struct bpf_verifier_state *st)
> +{
> +	struct bpf_retval_range range;
> +	struct bpf_func_state *frame;
> +	int i;
> +
> +	if (!env->prog->jit_requested || !bpf_jit_supports_exceptions())
> +		return "JIT does not support exceptions";

This checks jit_requested, but nothing requires the program to actually use
JIT at load time.

When add_loop_guard() emits BPF_EMIT_CALL(bpf_throw), does anything set
prog->jit_required?

For an explicit bpf_throw() in the program, add_kfunc_call() sets
env->prog->jit_required = 1, so a JIT failure rejects the program.

For loop guards, on a kernel without CONFIG_BPF_JIT_ALWAYS_ON,
bpf_fixup_call_args() can fall back to the interpreter:

    if (env->prog->jit_requested && !bpf_prog_is_offloaded(env->prog->aux)) {
        err = bpf_jit_subprogs(env);
        if (err == 0)
            return 0;
        if (err == -EFAULT)
            return err;
    }
#ifndef CONFIG_BPF_JIT_ALWAYS_ON
    if (prog->jit_required) { ... return -EINVAL; }

The exception callback makes subprog_cnt > 1, so JIT goes through
bpf_jit_subprogs(). If that fails (e.g., JIT allocation failure), the
out_cleanup path clears prog->jit_requested.

Since jit_required is false, the program is accepted and
__bpf_prog_select_runtime() lets it run in the interpreter.

When the may_goto budget of a guarded loop runs out, the interpreter calls
bpf_throw(). arch_bpf_stack_walk() finds no JITed BPF frame, so ctx.aux
stays NULL.

After WARN_ON_ONCE(!ctx.aux), bpf_throw() dereferences ctx.aux:

    ctx.aux->bpf_exception_cb(cookie, ctx.sp +
        ctx.aux->stack_arg_sp_adjust, ctx.bp, 0, 0);

Can bpf_commit_loop_guards() set env->prog->jit_required = true when it
commits a guard?

[ ... ]


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

Re: [PATCH bpf-next 3/8] bpf: Widen scalars at loop heads

[bot+bpf-ci]

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

> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 5a08f079a4896..981902cd5b71a 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h

[ ... ]

> diff --git a/kernel/bpf/states.c b/kernel/bpf/states.c
> index 66fb11b6c6a76..22987ce070e74 100644
> --- a/kernel/bpf/states.c
> +++ b/kernel/bpf/states.c
> @@ -1108,6 +1108,41 @@ static int propagate_backedges(struct bpf_verifier_env *env, struct bpf_scc_visi
>  	return 0;
>  }
>
> +/* Did the walk get to @insn_idx over a back-edge? */
> +static bool is_backedge(struct bpf_verifier_env *env, int insn_idx)
> +{
> +	int prev = env->prev_insn_idx;
> +	struct bpf_insn_aux_data *aux;
> +	struct bpf_insn *insn;
> +
> +	if (prev < 0 || prev >= env->prog->len)
> +		return false;
> +	aux = &env->insn_aux_data[prev];
> +	insn = &env->prog->insnsi[prev];
> +	/* check_cfg() does not record the edge of an unconditional jump as a jump */
> +	if ((BPF_CLASS(insn->code) == BPF_JMP || BPF_CLASS(insn->code) == BPF_JMP32) &&
> +	    BPF_OP(insn->code) == BPF_JA)
> +		return aux->backedge_ft || aux->backedge_br;
> +	return insn_idx == prev + 1 ? aux->backedge_ft : aux->backedge_br;
                                      ^^^^

Does this correctly handle LD_IMM64 fall-through and static subprog call
fall-through back-edges?

For LD_IMM64, check_cfg() pushes t + 2 as FALLTHROUGH and marks
backedge_ft on the LD_IMM64 insn. After do_check_insn() adds 1 and
do_check() adds another, is_backedge() is called with insn_idx == prev +
2, not prev + 1. This causes the function to return aux->backedge_br,
which is false:

  0: goto +2
  1: r1 = 0 ll            <- back-edge 1 -> 3 is LD_IMM64 fall-through
  3: r0 = *(u32 *)(r7 +0)
  4: if r0 != 0 goto -4
  5: exit

For a static subprog call, visit_func_call_insn() pushes t + 1 as
FALLTHROUGH, which marks backedge_ft on the call insn. After the callee
returns, prepare_func_exit() sets insn_idx = callsite + 1, while
prev_insn_idx is still the callee's BPF_EXIT. is_backedge() reads the
EXIT insn's aux, which has no backedge flags, and returns false:

  0: goto +1
  1: call subprog         <- back-edge 1 -> 2 is the call fall-through
  2: r0 = *(u32 *)(r7 +0)
  3: if r0 != 0 goto -3
  4: exit

In this commit the result goes to bpf_widen_loop_head():

kernel/bpf/verifier.c:bpf_widen_loop_head() {
  u32 passes = backedge ? old->loop_passes + 1 : 1;
  ...
}

so passes stays at 1 on every trip. The pass schedule (WIDEN_THR_PASSES
/ WIDEN_GEN_PASSES) never moves forward, and the 'states at loop head
%d don't converge' check (passes > WIDEN_MAX_PASSES) never fires. A loop
whose states never converge is walked until the 1M-insn limit, not given
up after 10 trips as the commit message says.

Nothing sets env->widen_loops yet in this commit, so this path only runs
once c7896d6154118 is applied. The larger impact comes with 3a779857709c5
("bpf: Add may_goto to loops that are not walked to the end"), where the
same helper decides whether a run-time bound is needed:

kernel/bpf/verifier.c:loop_head_guard() {
  if (!is_backedge(env, insn_idx))
    return true;
  ...
  return bpf_mark_loop_guard(env, cur);
}

For both edges above this returns true early. Neither guard_pending nor
guard_impossible is set, but the loop-head RANGE_WITHIN hit still calls
add_scc_backedge(), which sets scc_converged for the SCC.
bpf_commit_loop_guards() only looks at insns that have guard_pending or
guard_impossible, so it finds nothing and returns 0. The loop is accepted
even though it was not walked to the end, and no may_goto is added. In
both examples the loop condition depends on memory at r7. A program where
that value stays non-zero never terminates, which can cause soft lockups
or RCU stalls. This needs bpf_capable, since loop heads are only marked
for capable users.

Note that bpf_mark_loop_guard() explicitly handles 'not a jump' (class !=
JMP, op == CALL/EXIT), but these two edges never reach it.

is_backedge() is unchanged at 7d6b7dd8cb91b, the end of the series. A
possible fix: treat the LD_IMM64 fall-through (insn_idx == prev + 2) as
backedge_ft. For a subprog return, look up the call insn (callsite =
insn_idx - 1) instead of the EXIT insn. The guard for that case also has
to be marked, or made impossible, on the call insn so that
bpf_commit_loop_guards() sees it.

> +}
> +
> +/* The state of this walk that was the last to get to loop head @insn_idx. */
> +static struct bpf_verifier_state *loop_head_state(struct bpf_verifier_env *env, int insn_idx)
> +{

[ ... ]

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index cb5d498ada698..85b2691f81b12 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c

[ ... ]

> @@ -8040,6 +8041,287 @@ static struct bpf_verifier_state *find_prev_entry(struct bpf_verifier_env *env,
>  	return NULL;
>  }
>
> +/* A constant that register @regno is compared with, -1 if any register. */
> +struct widen_thr {
> +	s64 val;
> +	int regno;
> +};
> +
> +struct bpf_widen_thrs {
> +	u32 cnt;
> +	struct widen_thr thr[];
> +};
> +
> +/* passes around a loop that widen to constants the loop compares with */
> +#define WIDEN_THR_PASSES	4
> +/* passes that widen to S32_MAX and the like, later ones drop the bound */
> +#define WIDEN_GEN_PASSES	6
> +/* states at the loop head differ in something that can't be widened */
> +#define WIDEN_MAX_PASSES	10
> +
> +static const struct widen_thr widen_generic[] = {
> +	{ S32_MIN, -1 }, { 0, -1 }, { S32_MAX, -1 }, { U32_MAX, -1 },
> +};
> +
> +static int cmp_widen_thr(const void *a, const void *b)
> +{
> +	s64 x = ((const struct widen_thr *)a)->val;
> +	s64 y = ((const struct widen_thr *)b)->val;
> +
> +	return x < y ? -1 : x > y;
> +}
> +
> +static bool is_cmp_imm(const struct bpf_insn *insn)
> +{
> +	u8 class = BPF_CLASS(insn->code);
> +	u8 op = BPF_OP(insn->code);
> +
> +	if (class != BPF_JMP && class != BPF_JMP32)
> +		return false;
> +	if (BPF_SRC(insn->code) != BPF_K)
> +		return false;
> +	return op != BPF_JA && op != BPF_CALL && op != BPF_EXIT && op != BPF_JCOND;
> +}
> +
> +/*
> + * Sorted constants that registers are compared with in the SCC of @insn_idx.
> + * A range that ends at one of them can be cut back by the exit test of
> + * the loop, so that the state at the loop head stops growing.
> + */
> +static const struct bpf_widen_thrs *scc_thresholds(struct bpf_verifier_env *env, int insn_idx)
> +{
> +	struct bpf_insn_aux_data *aux = env->insn_aux_data;
> +	struct bpf_insn *insns = env->prog->insnsi;
> +	u32 scc = aux[insn_idx].scc;
> +	struct bpf_widen_thrs *thrs;
> +	int i, d, n = 0;
> +
> +	if (!scc)
> +		return NULL;
> +	if (!env->scc_thrs) {
> +		env->scc_thrs = kvzalloc_objs(*env->scc_thrs, env->scc_cnt, GFP_KERNEL_ACCOUNT);
> +		if (!env->scc_thrs)
> +			return NULL;
> +	}
> +	if (env->scc_thrs[scc])
> +		return env->scc_thrs[scc];
> +
> +	for (i = 0; i < env->prog->len; i++)
> +		if (aux[i].scc == scc && is_cmp_imm(&insns[i]))
> +			n++;
> +	thrs = kvzalloc(struct_size(thrs, thr, 3 * n), GFP_KERNEL_ACCOUNT);
> +	if (!thrs)
> +		return NULL;
> +	for (i = 0; i < env->prog->len; i++) {
> +		if (aux[i].scc != scc || !is_cmp_imm(&insns[i]))
> +			continue;
             ^^^^

Can this avoid the quadratic cost when a program has many loops? The
function walks the whole program twice the first time each SCC is widened:

kernel/bpf/verifier.c:scc_thresholds() {
  for (i = 0; i < env->prog->len; i++)
    if (aux[i].scc == scc && is_cmp_imm(&insns[i]))
      n++;
  ...
  for (i = 0; i < env->prog->len; i++) {
    if (aux[i].scc != scc || !is_cmp_imm(&insns[i]))
      continue;
  ...
}

The cache in env->scc_thrs only saves repeat lookups for the same SCC, so
the total cost is O(number of widened loops * prog->len).
bpf_compute_scc() gives every loop its own SCC id. The call chain is
do_check() -> bpf_is_state_visited() -> bpf_widen_loop_head() ->
scc_thresholds(), and it runs the second time any loop head is reached.

With CAP_BPF a program can be up to BPF_COMPLEXITY_LIMIT_INSNS (1M)
instructions long (bpf_prog_load()). Consider a program made of many
copies of a tiny loop such as:

  r1 = 0
L:
  r1 += 1
  if r1 >= 100 goto out
  goto L

Each copy costs only about 10 processed instructions to widen and
converge, so the 1M processed-insn budget allows on the order of 100k
loops in a program several hundred thousand instructions long. That adds
up to about 1e10-1e11 scans of insn_aux_data entries, on the order of
minutes of verifier CPU time. Walking the same program without widening
needs about 1M processed instructions.

The scan cannot cause a soft lockup, because do_check() calls
cond_resched() and checks signal_pending(). It is still an avoidable
quadratic cost that also slows down ordinary large programs with many
loops.

No other per-state path in the verifier scans the whole program: the only
other full passes in verifier.c are check_subprogs() and
sanitize_dead_code().

This commit does not set env->widen_loops yet. The code becomes active in
c7896d6154118 ("bpf: Walk loops with widened states first") for
bpf_capable programs with scc_cnt > 1. scc_thresholds() is unchanged at
the end of the series (7d6b7dd8cb91b), so no later fix was found.

A single O(prog->len) pass would avoid this: count and fill the constants
for all SCCs at once, bucketed by aux[i].scc, on the first call or after
bpf_compute_scc().

> +		for (d = -1; d <= 1; d++) {
> +			thrs->thr[thrs->cnt].val = (s64)insns[i].imm + d;
> +			thrs->thr[thrs->cnt++].regno = insns[i].dst_reg;
> +		}
> +	}
> +	sort(thrs->thr, thrs->cnt, sizeof(thrs->thr[0]), cmp_widen_thr, NULL);
> +	env->scc_thrs[scc] = thrs;
> +	return thrs;
> +}
> +
> +/*
> + * Nearest constant in sorted @thr that is >= @x if @up, <= @x otherwise.
> + * Constants that another register is compared with are skipped.
> + */
> +static bool thr_nearest(const struct widen_thr *thr, u32 cnt, int regno, s64 x, bool up,
> +			s64 *res)
> +{
> +	bool found = false;
> +	u32 i;
> +
> +	for (i = 0; i < cnt; i++) {
> +		if (regno >= 0 && thr[i].regno >= 0 && thr[i].regno != regno)
> +			continue;
> +		if (up && thr[i].val >= x) {
> +			*res = thr[i].val;
> +			return true;
> +		}
> +		if (!up && thr[i].val <= x) {
> +			*res = thr[i].val;
> +			found = true;
> +		}
> +	}
> +	return found;
> +}
> +
> +struct widen_ctx {
> +	const struct bpf_widen_thrs *thrs;
> +	u32 passes;
> +	int regno;
> +};
> +
> +/* Where to move the end @x of a range that keeps moving up or down. */
> +static bool widen_pick(const struct widen_ctx *w, s64 x, bool up, s64 *res)
> +{
> +	bool found = false;
> +	s64 t;
> +
> +	if (w->passes <= WIDEN_THR_PASSES && w->thrs &&
> +	    thr_nearest(w->thrs->thr, w->thrs->cnt, w->regno, x, up, &t)) {
> +		*res = t;
> +		found = true;
> +	}
> +	if (w->passes <= WIDEN_GEN_PASSES &&
> +	    thr_nearest(widen_generic, ARRAY_SIZE(widen_generic), -1, x, up, &t)) {
> +		*res = !found ? t : up ? min(*res, t) : max(*res, t);
> +		found = true;
> +	}
> +	return found;
> +}

The commit message says:

> The first 4 trips use constants of the loop, the next 2 use S32_MIN, 0,
> S32_MAX, U32_MAX, then the bound is dropped.

But widen_pick() checks generic constants on every pass <= WIDEN_GEN_PASSES,
including passes 1-4, and the nearer of the loop constant and the generic
constant wins:

kernel/bpf/verifier.c:widen_pick() {
  if (w->passes <= WIDEN_GEN_PASSES &&
      thr_nearest(widen_generic, ARRAY_SIZE(widen_generic), -1, x, up, &t)) {
    *res = !found ? t : up ? min(*res, t) : max(*res, t);
}

So in passes 1-4 a range end can stop at 0, S32_MIN, S32_MAX or U32_MAX
before it reaches the loop constant.

Example: `for (i = -100; i < 100; i++)`. On pass 1, smax moves from -100
to -99. The loop constants offer 99 and the generic list offers 0, so
smax is widened to 0 rather than 99, and one extra trip is needed before
the state converges. Such stops use up the WIDEN_THR_PASSES budget. After
pass 4 the loop constants are no longer used, so a loop that needs close
to 4 loop-constant steps can end up with a wider bound than the commit
message describes.

This is not unsound, since every choice still widens outward. But either
the commit message should describe the combined behaviour, or the generic
constants should only be used when passes > WIDEN_THR_PASSES, as the
message says.

[ ... ]


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

Re: [PATCH bpf-next 1/8] bpf: Trim range ends to var_off members

[bot+bpf-ci]

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

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index a7c9e2d8965d5..cb5d498ada698 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c

[ ... ]

> @@ -2094,9 +2094,71 @@ static struct cnum64 cnum64_from_tnum(struct tnum tnum)
>  		return cnum64_from_urange(tnum.value, (tnum.value | tnum.mask));
>  }
>
> +/* smallest member of @t that is >= @x, wraps around to the smallest member of @t */
> +static u64 tnum_member_ge(struct tnum t, u64 x)
> +{
> +	if ((x & ~t.mask) == t.value)
> +		return x;
> +	if (x > (t.value | t.mask))
> +		return t.value;
> +	return tnum_step(t, x);
> +}
> +
> +/* largest member of @t that is <= @x, wraps around to the largest member of @t */
> +static u64 tnum_member_le(struct tnum t, u64 x)
> +{
> +	/* members of 'tc' are bitwise complements of members of 't' */
> +	struct tnum tc = { .value = ~(t.value | t.mask), .mask = t.mask };
> +
> +	return ~tnum_member_ge(tc, ~x);
> +}
> +
> +/*
> + * Move both ends of arc @c inwards to the nearest members of @t.
> + * Values that are dropped are not members of @t.
> + */
> +static struct cnum64 cnum64_tighten_by_tnum(struct cnum64 c, struct tnum t)
> +{
> +	u64 lo, hi, dlo, dhi;
> +
> +	if (cnum64_is_empty(c) || c.size == U64_MAX || !t.mask)
> +		return c;
> +	lo = tnum_member_ge(t, c.base);
> +	dlo = lo - c.base;
> +	if (dlo > c.size)
> +		return c;
> +	hi = tnum_member_le(t, c.base + c.size);
> +	dhi = c.base + c.size - hi;
> +	if (dhi > c.size - dlo)
> +		return c;
> +	return (struct cnum64){ .base = lo, .size = c.size - dlo - dhi };
> +}
> +
> +static struct cnum32 cnum32_tighten_by_tnum(struct cnum32 c, struct tnum t)
> +{
> +	struct tnum tc;
> +	u32 lo, hi, dlo, dhi;
> +
> +	t = tnum_subreg(t);
> +	if (cnum32_is_empty(c) || c.size == U32_MAX || !t.mask)
> +		return c;
> +	lo = tnum_member_ge(t, c.base);
> +	dlo = lo - c.base;
> +	if (dlo > c.size)
> +		return c;
> +	/* complement within 32 bits */
> +	tc = (struct tnum){ .value = (u32)~(t.value | t.mask), .mask = t.mask };
> +	hi = ~(u32)tnum_member_ge(tc, (u32)~(c.base + c.size));
> +	dhi = c.base + c.size - hi;
> +	if (dhi > c.size - dlo)
> +		return c;
> +	return (struct cnum32){ .base = lo, .size = c.size - dlo - dhi };
> +}
> +

[ ... ]

>  static void __update_reg64_bounds(struct bpf_reg_state *reg)
>  {
> +	u64 tnum_next;
> +	bool umin_in_tnum;
> +
>  	cnum64_intersect_with(&reg->r64, cnum64_from_tnum(reg->var_off));
> +	reg->r64 = cnum64_tighten_by_tnum(reg->r64, reg->var_off);
>
>  	/* Check if u64 and tnum overlap in a single value */
>  	tnum_next = tnum_step(reg->var_off, reg_umin(reg));
> +	umin_in_tnum = (reg_umin(reg) & ~reg->var_off.mask) == reg->var_off.value;
> +	tmax = reg->var_off.value | reg->var_off.mask;
> +	if (umin_in_tnum && tnum_next > reg_umax(reg)) {
> +		/* The u64 range and the tnum only overlap in umin.
> +		 * u64:  ---[xxxxxx]-----
> +		 * tnum: --xx----------x-
> +		 */
> +		___mark_reg_known(reg, reg_umin(reg));
> +	} else if (!umin_in_tnum && tnum_next == tmax) {
> +		/* The u64 range and the tnum only overlap in the maximum value
> +		 * represented by the tnum, called tmax.
> +		 * u64:  ---[xxxxxx]-----
> +		 * tnum: xx-----x--------
> +		 */
> +		___mark_reg_known(reg, tmax);
> +	} else if (!umin_in_tnum && tnum_next <= reg_umax(reg) &&
> +		   tnum_step(reg->var_off, tnum_next) > reg_umax(reg)) {
> +		/* The u64 range and the tnum only overlap in between umin
> +		 * (excluded) and umax.
> +		 * u64:  ---[xxxxxx]-----
> +		 * tnum: xx----x-------x-
> +		 */
> +		___mark_reg_known(reg, tnum_next);
> +	}
>  }

After the tighten call, can the second and third branches of this
"Check if u64 and tnum overlap" block still execute?

The tighten call moves the range base to tnum_member_ge(t, base).
For a non-wrapping arc, reg_umin() is now always a member, so
umin_in_tnum is always true.

For a wrapping or full arc, reg_umin() returns 0. The second branch
requires tnum_next == tmax and !umin_in_tnum, which would need a const
tnum, but the tighten path and the full-range path already handle that
case. The third branch would need tnum_step(var_off, tnum_next) >
reg_umax(reg) == U64_MAX, which cannot occur.

This makes the second branch unreachable for the case it was designed to
handle: when the only member left in the range is tmax. The tighten
logic converts [non-member umin .. tmax] into the singleton [tmax, tmax].
Then umin_in_tnum is true, but tnum_next = tnum_step(var_off, tmax)
returns tmax when the input is already at or beyond tmax, so the first
branch test `tnum_next > reg_umax(reg)` is false and the register is
not marked known.

For example, with var_off=(0x5; 0x200000000) and r64=[0xe, 0x20000000f],
the range becomes [0x200000005, 0x200000005] after tighten, but var_off
stays (0x5; 0x200000000) and is_reg_const() sees it as non-constant.

The first __update_reg_bounds() inside reg_bounds_sync() is followed by
__reg_bound_offset(), which fixes var_off. But the trailing
__update_reg_bounds() call is not followed by __reg_bound_offset(), so
the register can be left with a constant range and a non-constant tnum.

Does this logic need updating to replace the three-case block with a
single constant check on the trimmed range?


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

Re: [PATCH bpf-next 4/8] bpf: Detect loops that never exit

[bot+bpf-ci]

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

> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 981902cd5b71a..60f483d7e4a96 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h

[ ... ]

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 85b2691f81b12..06dc269991b22 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -19192,6 +19192,21 @@ static int do_check_insn(struct bpf_verifier_env *env, bool *do_print_state)
>  	return -EFAULT;
>  }
>
> +/* Did the jump at @prev take the walk out of the loop @prev is in? */
> +static bool left_loop(struct bpf_verifier_env *env, int prev, int insn_idx)
> +{
> +	struct bpf_insn_aux_data *aux = env->insn_aux_data;
> +	struct bpf_insn *insn;
> +
> +	if (prev < 0 || prev >= env->prog->len || !aux[prev].scc ||
> +	    aux[prev].scc == aux[insn_idx].scc)
> +		return false;
> +	/* the callee is not in SCC of the call, the insn after the call is */
> +	insn = &env->prog->insnsi[prev];
> +	return !((BPF_CLASS(insn->code) == BPF_JMP || BPF_CLASS(insn->code) == BPF_JMP32) &&
> +		 BPF_OP(insn->code) == BPF_CALL);
> +}

Does left_loop() handle sync callback-calling helpers correctly?

The comment says "the insn after the call is" in the SCC of the call,
which holds for bpf-to-bpf calls inside a loop. But for a sync
callback-calling helper outside any loop, bpf_compute_scc() gives the call
insn C its own singleton SCC:

kernel/bpf/cfg.c:bpf_compute_scc()
	if (bpf_calls_callback(env, w)) /* implicit loop? */
		assign_scc = true;

The insn C+1 is outside that SCC. When the helper returns and do_check()
calls left_loop(env, C, C+1), aux[C].scc is nonzero and differs from
aux[C+1].scc, but the function returns false because insn C is BPF_CALL.
So bpf_scc_mark_exit() is never called for the only edge out of that
implicit loop.

The callback convergence branch in bpf_is_state_visited() always adds a
backedge:

kernel/bpf/states.c:bpf_is_state_visited()
	if (bpf_calls_callback(env, insn_idx)) {
		if (states_equal(env, &sl->state, cur, RANGE_WITHIN)) {
			loop = true;
			goto hit;

The checkpoint at C never marks visit->exited, so when it reaches
branches == 0, maybe_exit_scc() sees backedges != NULL and exited ==
false:

kernel/bpf/states.c:maybe_exit_scc()
	if (env->widen_loops && !st->speculative && visit->backedges && !visit->exited) {
		verbose(env, "loop at insn %d never exits\n", st->insn_idx);
		env->widen_used = true;
		return -EINVAL;
	}

and fails with "loop at insn %d never exits" for helpers like bpf_loop,
bpf_for_each_map_elem, bpf_find_vma, bpf_user_ringbuf_drain,
bpf_rbtree_add, and others.

After commit c7896d6154118 enables widen_loops for every bpf_capable
program with more than one SCC, this false verdict causes the widened walk
to fail and fall back to walking every iteration again. That roughly
doubles verification work, removes the benefit of widening for the whole
program, and leaves a false "never exits" message in the log. A program
that uses a callback helper and has a loop that only verifies when widened
remains rejected.

A minimal reproducer is:

	r1 = 10
	r2 = cb
	r3 = 0
	r4 = 0
	call bpf_loop
	r0 = 0
	exit

with cb returning 0.

Should the fallthrough of a callback-calling insn (insn_idx == prev + 1)
be treated as a normal edge rather than excluded?

> @@ -19358,6 +19375,9 @@ static int do_check(struct bpf_verifier_env *env)
>  		} else if (err < 0) {
>  			return err;
>  		} else if (err == PROCESS_BPF_EXIT) {
> +			/* exit or bpf_throw() inside of a loop */
> +			if (env->widen_loops)
> +				bpf_scc_mark_exit(env, state, env->insn_idx);
>  			goto process_bpf_exit;

Can bpf_throw() from a callee mark the caller's loop as exited?

bpf_scc_mark_exit() only marks the visit whose SCC contains env->insn_idx
in the current frame, and only when no outer callsite is in an SCC:

kernel/bpf/states.c:bpf_scc_mark_exit()
	if (st->speculative || !env->insn_aux_data[insn_idx].scc)
		return;
	...
	for (i = 0; i < st->curframe; i++) {
		callsite = bpf_frame_insn_idx(st, i);
		if (env->insn_aux_data[callsite].scc)
			return;

An exception ends the whole program, so it leaves every enclosing loop.
But if bpf_throw() or bpf_assert() is in a static subprog called from a
loop body:

	l: ...
	   call foo
	   goto l

and foo() throws on some path, the caller's loop is never marked:

- If foo has no loop, the throw insn has scc 0 and the function returns at
  the first check.
- If foo has a loop, frame 0's callsite is in an SCC and the function
  returns in the loop.

If the throw is the only way out of the loop, the widened walk fails with
"loop at insn N never exits". After commit c7896d6154118 this costs a full
re-walk, and the fallback may then reject the program with "infinite loop
detected". The same assert inlined in the loop body is accepted.

Should exception exits mark the visit that compute_scc_callchain() picks
for the state (the outermost frame in an SCC) instead?

Also, the "exit" half of the comment never happens: an exit insn has no
CFG successors so its aux->scc is always 0, and PROCESS_BPF_EXIT from a
real exit only happens at curframe 0. Only the throw half of this hunk
does anything.

> diff --git a/kernel/bpf/states.c b/kernel/bpf/states.c
> index 22987ce070e74..39e6052922e59 100644
> --- a/kernel/bpf/states.c
> +++ b/kernel/bpf/states.c

[ ... ]

> @@ -1462,6 +1499,9 @@ int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx)
>  		if (states_equal(env, &sl->state, cur, loop ? RANGE_WITHIN : NOT_EXACT)) {
>  hit:
>  			sl->hit_cnt++;
> +			/* what follows the old state was seen, it may leave the loop */
> +			if (env->widen_loops && !sl->state.branches)
> +				bpf_scc_mark_exit(env, cur, insn_idx);

Can this mark set visit->exited for a loop that never exits?

The mark fires whenever cur is pruned by any fully explored state. That
includes a checkpoint created inside the same visit whose whole subtree
only went around the loop.

Consider a loop with a counter and an unpredictable branch, with no edge
out of the SCC:

	r6 = 0
	l: r6 += 1
	   call bpf_get_prandom_u32
	   if r0 > 5 goto a
	   goto l
	a: goto l

Walk with widen_loops:

1. L1 (r6 = 0) at l becomes entry_state. Trip 1 pushes branch B1 (r6 = 1)
   at the if.
2. The fallthrough reaches l with r6 = 1. That is not within L1, so it is
   widened and a new checkpoint L2 (r6 unknown) is added to the head of
   the explored list.
3. Trip 2 pushes B2 and converges on L2 through a backedge. B2 also
   converges on L2 while L2 is still in progress, so neither hit sets the
   mark. L2 reaches branches == 0, and maybe_exit_scc(L2) returns early
   because L2 is not the entry_state.
4. B1 is popped and reaches l with r6 = 1. It is compared against L2
   first. L2 is a superset, so the result is a hit with
   !sl->state.branches, and bpf_scc_mark_exit(env, cur, l) sets
   visit->exited = true.
5. When L1 completes, maybe_exit_scc() sees exited == true and accepts the
   loop.

The program then spins until the may_goto budget runs out and bpf_throw()
fires. Before this series such a program was rejected with "BPF program is
too large" or "infinite loop detected".

The commit message lists pruning by a fully explored state as a way of
leaving the loop. Is this over-approximation intentional, or should the
mark only fire when sl belongs to a different (earlier or outer) visit?


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

Re: [PATCH bpf-next 5/8] bpf: Add may_goto to loops that are not walked to the end

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Critical] bpf: kernel panic via interpreter fallback for unbounded loops
--

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

bpf: Add may_goto to loops that are not walked to the end

This commit bounds BPF loop iterations at runtime by injecting a may_goto
instruction on the back-edges of loops that are not fully walked. If the
loop budget is exhausted, execution aborts by terminating in bpf_throw().

[ ... ]
> diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c
> index 2add8001c3ec3..2b965fa4bacc0 100644
> --- a/kernel/bpf/fixups.c
> +++ b/kernel/bpf/fixups.c
[ ... ]
> @@ -1537,6 +1537,143 @@ static int add_hidden_subprog(struct bpf_verifier_env *env, struct bpf_insn *pat
>  /* Do various post-verification rewrites in a single program pass.
>   * These rewrites simplify JIT and interpreter implementations.
>   */
> +/*
> + * The walk with widened loops is done. Loops where some state came back to
> + * a state that was still walked were not walked to the end and have to be
> + * bounded at run time.
> + */
> +int bpf_commit_loop_guards(struct bpf_verifier_env *env)
> +{
> +	struct bpf_insn_aux_data *aux = env->insn_aux_data;
> +	int i;
> +
> +	for (i = 0; i < env->prog->len; i++) {
> +		if (!aux[i].scc || !test_bit(aux[i].scc, env->scc_converged))
> +			continue;
> +		if (aux[i].guard_impossible) {
> +			verbose(env, "loop with back-edge at insn %d cannot be bounded\n", i);
> +			return -E2BIG;
> +		}
> +		if (aux[i].guard_pending) {
> +			aux[i].loop_guard = true;
> +			env->seen_exception = true;

[Severity: Critical]
Does this sequence allow a kernel panic if the BPF program falls back to the
interpreter?

When the verifier implicitly injects a bpf_throw call as a runtime loop guard
by setting env->seen_exception = true here, it doesn't appear to set
env->prog->jit_required = 1.

If the system falls back to the BPF interpreter, for example due to memory
constraints or program size, the interpreter will hit the loop guard and
execute bpf_throw(). When this happens, arch_bpf_stack_walk() cannot find any
BPF JIT frames, returning without setting ctx.aux and leaving it NULL.
bpf_throw() then unconditionally dereferences ctx.aux, which triggers a NULL
pointer dereference.

Should env->prog->jit_required = 1 be set here, similar to what happens for
explicit bpf_throw kfunc calls, to prevent this fallback crash?

> +		}
> +	}
> +	return 0;
> +}

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