* [PATCH bpf-next v2 00/11] bpf: propagate read/precision marks over state graph backedges
@ 2025-06-06 21:03 Eduard Zingerman
2025-06-06 21:03 ` [PATCH bpf-next v2 01/11] Revert "bpf: use common instruction history across all states" Eduard Zingerman
` (10 more replies)
0 siblings, 11 replies; 12+ messages in thread
From: Eduard Zingerman @ 2025-06-06 21:03 UTC (permalink / raw)
To: bpf, ast
Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song,
Eduard Zingerman
Current loop_entry-based states comparison logic does not handle the
following case:
.-> A --. Assume the states are visited in the order A, B, C.
| | | Assume that state B reaches a state equivalent to state A.
| v v At this point, state C is not processed yet, so state A
'-- B C has not received any read or precision marks from C.
As a result, these marks won't be propagated to B.
If B has incomplete marks, it is unsafe to use it in states_equal()
checks. This issue was first reported in [1].
This patch-set
--------------
Here is the gist of the algorithm implemented by this patch-set:
- Compute strongly connected components (SCCs) in the program CFG.
- When a verifier state enters an SCC, that state is recorded as the
SCC's entry point.
- When a verifier state is found to be equivalent to another
(e.g., B to A in the example above), it is recorded as a
states-graph backedge.
- Backedges are accumulated per SCC (*).
- When an SCC entry state reaches `branches == 0`, propagate read and
precision marks through the backedges until a fixed point is reached
(e.g., from A to B, from C to A, and then again from A to B).
(*) This is an oversimplification, see patch #8 for details.
Unfortunately, this means that commit [2] needs to be reverted,
as precision propagation requires access to jump history,
and backedges represent history not belonging to `env->cur_state`.
Details are provided in patch #8; a comment in `is_state_visited()`
explains most of the mechanics.
Patch #2 adds a `compute_scc()` function, which computes SCCs in the
program CFG. This function was tested using property-based testing in
[3], but it is not included in selftests.
Previous attempt
----------------
A previous attempt to fix this is described in [4]:
1. Within the states loop, `states_equal(... RANGE_WITHIN)` ignores
read and precision marks.
2. For states outside the loop, all registers for states within the
loop are marked as read and precise.
This approach led to an 86x regression on the `cond_break1` selftest.
In that test, one loop was followed by another, and a certain variable
was incremented in the second loop. This variable was marked as
precise due to rule (2), which hindered convergence in the first loop.
After some off-list discussion, it was decided that this might be a
typical case and such regressions are undesirable.
This patch-set avoids such eager precision markings.
Alternatives
------------
Another option is to associate a mask of read/written/precise stack
slots with each instruction. This mask can be populated during
verifier states exploration. Upon reaching an `EXIT` instruction or an
equivalent state, the accumulated masks can be used to propagate
read/written/precise bits across the program's control flow graph
using an analysis similar to use-def.
Unfortunately, a naive implementation of this approach [5] results in
a 10x regression in `veristat` for some `sched_ext` programs due to
the inability to express the must-write property. This issue requires
further investigation.
Changes in verification performance
-----------------------------------
There are some veristat regressions when comparing with master using
selftests and sched_ext BPF binaries. The comparison is done using
master from [6] and this patch-set from [7] where memory accounting
logic is added to veristat.
========= selftests: master vs patch-set =========
File Program Insns Peak memory (KiB)
------------------------------- ----------------------------------- ----- ---- ---------------- ---- ----- ----------------
arena_list.bpf.o arena_list_add 374 406 +32 (+8.56%) 0 0 +0 (+0.00%)
dynptr_success.bpf.o test_copy_from_user_str_dynptr 268 284 +16 (+5.97%) 768 1024 +256 (+33.33%)
dynptr_success.bpf.o test_probe_read_kernel_dynptr 994 1101 +107 (+10.76%) 1024 1240 +216 (+21.09%)
dynptr_success.bpf.o test_probe_read_user_dynptr 1000 1107 +107 (+10.70%) 1024 1240 +216 (+21.09%)
iters.bpf.o checkpoint_states_deletion 1211 1216 +5 (+0.41%) 512 1288 +776 (+151.56%)
iters.bpf.o clean_live_states 588 620 +32 (+5.44%) 256 764 +508 (+198.44%)
pyperf600_iter.bpf.o on_event 2591 5929 +3338 (+128.83%) 4648 11320 +6672 (+143.55%)
Total progs: 3600
Old success: 2084
New success: 2084
total_insns diff min : 0.00 %
total_insns diff max : 128.83 %
total_insns abs max old : 837,487
total_insns abs max new : 837,487
0 .. 5 %: 3592
5 .. 15 %: 6
20 .. 30 %: 1
125 .. 130 %: 1
mem_peak diff min : -100.00 %
mem_peak diff max : 198.44 %
mem_peak abs max old : 269,312 KiB
mem_peak abs max new : 269,312 KiB
-100 .. -95 %: 63
-60 .. -50 %: 1
-10 .. 0 %: 20
0 .. 5 %: 3413
5 .. 15 %: 6
20 .. 30 %: 4
30 .. 40 %: 7
40 .. 50 %: 1
50 .. 60 %: 3
60 .. 70 %: 1
140 .. 150 %: 1
150 .. 160 %: 1
195 .. 200 %: 1
0 -> something: 78
========= scx: master vs patch-set =========
Program Insns Peak memory (KiB)
------------------------ ----- ----- --------------- ----- ----- -----------------
arena_topology_node_init 2129 2391 +262 (+12.31%) 768 768 +0 (+0.00%)
arena_topology_node_init 2129 2391 +262 (+12.31%) 768 768 +0 (+0.00%)
arena_topology_print 591 826 +235 (+39.76%) 256 256 +0 (+0.00%)
arena_topology_print 591 826 +235 (+39.76%) 256 256 +0 (+0.00%)
chaos_init 4261 5090 +829 (+19.46%) 2540 3032 +492 (+19.37%)
lavd_cpu_offline 5074 5706 +632 (+12.46%) 3940 6304 +2364 (+60.00%)
lavd_cpu_online 5074 5706 +632 (+12.46%) 3940 6304 +2364 (+60.00%)
lavd_dispatch 41769 47578 +5809 (+13.91%) 6208 29200 +22992 (+370.36%)
lavd_enqueue 24190 27749 +3559 (+14.71%) 22740 42872 +20132 (+88.53%)
lavd_init 6748 7474 +726 (+10.76%) 5096 6864 +1768 (+34.69%)
lavd_select_cpu 27243 30802 +3559 (+13.06%) 26056 45048 +18992 (+72.89%)
layered_dispatch 8909 13295 +4386 (+49.23%) 7976 18028 +10052 (+126.03%)
layered_dump 1890 2097 +207 (+10.95%) 2036 3036 +1000 (+49.12%)
layered_init 4149 4531 +382 (+9.21%) 2716 2896 +180 (+6.63%)
layered_runnable 2566 2601 +35 (+1.36%) 748 1244 +496 (+66.31%)
p2dq_init 3640 4474 +834 (+22.91%) 2004 2504 +500 (+24.95%)
refresh_layer_cpumasks 735 1048 +313 (+42.59%) 256 756 +500 (+195.31%)
rusty_init_task 31104 31104 +0 (+0.00%) 2164 2368 +204 (+9.43%)
rusty_select_cpu 1110 1110 +0 (+0.00%) 768 1004 +236 (+30.73%)
tp_cgroup_attach_task 149 203 +54 (+36.24%) 0 0 +0 (+0.00%)
Total progs: 147
Old success: 134
New success: 134
total_insns diff min : 0.00 %
total_insns diff max : 49.23 %
total_insns abs max old : 72,434
total_insns abs max new : 72,434
0 .. 5 %: 132
5 .. 15 %: 9
15 .. 25 %: 2
35 .. 45 %: 3
45 .. 50 %: 1
mem_peak diff min : -0.95 %
mem_peak diff max : 370.36 %
mem_peak abs max old : 26,056 KiB
mem_peak abs max new : 45,048 KiB
-5 .. 0 %: 4
0 .. 5 %: 128
5 .. 15 %: 2
15 .. 25 %: 2
30 .. 40 %: 2
45 .. 55 %: 1
60 .. 70 %: 3
70 .. 80 %: 1
85 .. 95 %: 1
125 .. 135 %: 1
195 .. 205 %: 1
370 .. 375 %: 1
Changelog
---------
v1: https://lore.kernel.org/bpf/20250524191932.389444-1-eddyz87@gmail.com/
v1 -> v2:
- Rebase
- added mem_peak statistics (Alexei)
- selftests: fixed comments and removed useless r7 assignments (Yonghong)
Links
-----
[1] https://lore.kernel.org/bpf/20250312031344.3735498-1-eddyz87@gmail.com/
[2] commit 96a30e469ca1 ("bpf: use common instruction history across all states")
[3] https://github.com/eddyz87/scc-test
[4] https://lore.kernel.org/bpf/20250426104634.744077-1-eddyz87@gmail.com/
[5] https://github.com/eddyz87/bpf/tree/propagate-read-and-precision-in-cfg
[6] https://github.com/eddyz87/bpf/tree/veristat-memory-accounting
[7] https://github.com/eddyz87/bpf/tree/scc-accumulate-backedges
Eduard Zingerman (11):
Revert "bpf: use common instruction history across all states"
bpf: compute SCCs in program control flow graph
bpf: frame_insn_idx() utility function
bpf: starting_state parameter for __mark_chain_precision()
bpf: set 'changed' status if propagate_precision() did any updates
bpf: set 'changed' status if propagate_liveness() did any updates
bpf: move REG_LIVE_DONE check to clean_live_states()
bpf: propagate read/precision marks over state graph backedges
bpf: remove {update,get}_loop_entry functions
bpf: include backedges in peak_states stat
selftests/bpf: tests with a loop state missing read/precision mark
include/linux/bpf_verifier.h | 77 +-
kernel/bpf/verifier.c | 970 +++++++++++++++-------
tools/testing/selftests/bpf/progs/iters.c | 277 ++++++
3 files changed, 998 insertions(+), 326 deletions(-)
--
2.48.1
^ permalink raw reply [flat|nested] 12+ messages in thread
* [PATCH bpf-next v2 01/11] Revert "bpf: use common instruction history across all states"
2025-06-06 21:03 [PATCH bpf-next v2 00/11] bpf: propagate read/precision marks over state graph backedges Eduard Zingerman
@ 2025-06-06 21:03 ` Eduard Zingerman
2025-06-06 21:03 ` [PATCH bpf-next v2 02/11] bpf: compute SCCs in program control flow graph Eduard Zingerman
` (9 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: Eduard Zingerman @ 2025-06-06 21:03 UTC (permalink / raw)
To: bpf, ast
Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song,
Eduard Zingerman
This reverts commit 96a30e469ca1d2b8cc7811b40911f8614b558241.
Next patches in the series modify propagate_precision() to allow
arbitrary starting state. Precision propagation requires access to
jump history, and arbitrary states represent history not belonging to
`env->cur_state`.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
include/linux/bpf_verifier.h | 19 +++----
kernel/bpf/verifier.c | 107 ++++++++++++++++++-----------------
2 files changed, 63 insertions(+), 63 deletions(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 256274acb1d8..489105d0c8ab 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -344,7 +344,7 @@ struct bpf_func_state {
#define MAX_CALL_FRAMES 8
-/* instruction history flags, used in bpf_insn_hist_entry.flags field */
+/* instruction history flags, used in bpf_jmp_history_entry.flags field */
enum {
/* instruction references stack slot through PTR_TO_STACK register;
* we also store stack's frame number in lower 3 bits (MAX_CALL_FRAMES is 8)
@@ -366,7 +366,7 @@ enum {
static_assert(INSN_F_FRAMENO_MASK + 1 >= MAX_CALL_FRAMES);
static_assert(INSN_F_SPI_MASK + 1 >= MAX_BPF_STACK / 8);
-struct bpf_insn_hist_entry {
+struct bpf_jmp_history_entry {
u32 idx;
/* insn idx can't be bigger than 1 million */
u32 prev_idx : 20;
@@ -459,14 +459,13 @@ struct bpf_verifier_state {
* See get_loop_entry() for more information.
*/
struct bpf_verifier_state *loop_entry;
- /* Sub-range of env->insn_hist[] corresponding to this state's
- * instruction history.
- * Backtracking is using it to go from last to first.
- * For most states instruction history is short, 0-3 instructions.
+ /* jmp history recorded from first to last.
+ * backtracking is using it to go from last to first.
+ * For most states jmp_history_cnt is [0-3].
* For loops can go up to ~40.
*/
- u32 insn_hist_start;
- u32 insn_hist_end;
+ struct bpf_jmp_history_entry *jmp_history;
+ u32 jmp_history_cnt;
u32 dfs_depth;
u32 callback_unroll_depth;
u32 may_goto_depth;
@@ -775,9 +774,7 @@ struct bpf_verifier_env {
int cur_postorder;
} cfg;
struct backtrack_state bt;
- struct bpf_insn_hist_entry *insn_hist;
- struct bpf_insn_hist_entry *cur_hist_ent;
- u32 insn_hist_cap;
+ struct bpf_jmp_history_entry *cur_hist_ent;
u32 pass_cnt; /* number of times do_check() was called */
u32 subprog_cnt;
/* number of instructions analyzed by the verifier */
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index e31f6b0ccb30..98130b982a37 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1659,6 +1659,13 @@ static void free_func_state(struct bpf_func_state *state)
kfree(state);
}
+static void clear_jmp_history(struct bpf_verifier_state *state)
+{
+ kfree(state->jmp_history);
+ state->jmp_history = NULL;
+ state->jmp_history_cnt = 0;
+}
+
static void free_verifier_state(struct bpf_verifier_state *state,
bool free_self)
{
@@ -1669,6 +1676,7 @@ static void free_verifier_state(struct bpf_verifier_state *state,
state->frame[i] = NULL;
}
kfree(state->refs);
+ clear_jmp_history(state);
if (free_self)
kfree(state);
}
@@ -1733,6 +1741,13 @@ static int copy_verifier_state(struct bpf_verifier_state *dst_state,
struct bpf_func_state *dst;
int i, err;
+ dst_state->jmp_history = copy_array(dst_state->jmp_history, src->jmp_history,
+ src->jmp_history_cnt, sizeof(*dst_state->jmp_history),
+ GFP_USER);
+ if (!dst_state->jmp_history)
+ return -ENOMEM;
+ dst_state->jmp_history_cnt = src->jmp_history_cnt;
+
/* if dst has more stack frames then src frame, free them, this is also
* necessary in case of exceptional exits using bpf_throw.
*/
@@ -1750,8 +1765,6 @@ static int copy_verifier_state(struct bpf_verifier_state *dst_state,
dst_state->parent = src->parent;
dst_state->first_insn_idx = src->first_insn_idx;
dst_state->last_insn_idx = src->last_insn_idx;
- dst_state->insn_hist_start = src->insn_hist_start;
- dst_state->insn_hist_end = src->insn_hist_end;
dst_state->dfs_depth = src->dfs_depth;
dst_state->callback_unroll_depth = src->callback_unroll_depth;
dst_state->used_as_loop_entry = src->used_as_loop_entry;
@@ -2807,14 +2820,9 @@ static struct bpf_verifier_state *push_async_cb(struct bpf_verifier_env *env,
* The caller state doesn't matter.
* This is async callback. It starts in a fresh stack.
* Initialize it similar to do_check_common().
- * But we do need to make sure to not clobber insn_hist, so we keep
- * chaining insn_hist_start/insn_hist_end indices as for a normal
- * child state.
*/
elem->st.branches = 1;
elem->st.in_sleepable = is_sleepable;
- elem->st.insn_hist_start = env->cur_state->insn_hist_end;
- elem->st.insn_hist_end = elem->st.insn_hist_start;
frame = kzalloc(sizeof(*frame), GFP_KERNEL);
if (!frame)
goto err;
@@ -3843,10 +3851,11 @@ static void linked_regs_unpack(u64 val, struct linked_regs *s)
}
/* for any branch, call, exit record the history of jmps in the given state */
-static int push_insn_history(struct bpf_verifier_env *env, struct bpf_verifier_state *cur,
- int insn_flags, u64 linked_regs)
+static int push_jmp_history(struct bpf_verifier_env *env, struct bpf_verifier_state *cur,
+ int insn_flags, u64 linked_regs)
{
- struct bpf_insn_hist_entry *p;
+ u32 cnt = cur->jmp_history_cnt;
+ struct bpf_jmp_history_entry *p;
size_t alloc_size;
/* combine instruction flags if we already recorded this instruction */
@@ -3866,32 +3875,29 @@ static int push_insn_history(struct bpf_verifier_env *env, struct bpf_verifier_s
return 0;
}
- if (cur->insn_hist_end + 1 > env->insn_hist_cap) {
- alloc_size = size_mul(cur->insn_hist_end + 1, sizeof(*p));
- p = kvrealloc(env->insn_hist, alloc_size, GFP_USER);
- if (!p)
- return -ENOMEM;
- env->insn_hist = p;
- env->insn_hist_cap = alloc_size / sizeof(*p);
- }
+ cnt++;
+ alloc_size = kmalloc_size_roundup(size_mul(cnt, sizeof(*p)));
+ p = krealloc(cur->jmp_history, alloc_size, GFP_USER);
+ if (!p)
+ return -ENOMEM;
+ cur->jmp_history = p;
- p = &env->insn_hist[cur->insn_hist_end];
+ p = &cur->jmp_history[cnt - 1];
p->idx = env->insn_idx;
p->prev_idx = env->prev_insn_idx;
p->flags = insn_flags;
p->linked_regs = linked_regs;
-
- cur->insn_hist_end++;
+ cur->jmp_history_cnt = cnt;
env->cur_hist_ent = p;
return 0;
}
-static struct bpf_insn_hist_entry *get_insn_hist_entry(struct bpf_verifier_env *env,
- u32 hist_start, u32 hist_end, int insn_idx)
+static struct bpf_jmp_history_entry *get_jmp_hist_entry(struct bpf_verifier_state *st,
+ u32 hist_end, int insn_idx)
{
- if (hist_end > hist_start && env->insn_hist[hist_end - 1].idx == insn_idx)
- return &env->insn_hist[hist_end - 1];
+ if (hist_end > 0 && st->jmp_history[hist_end - 1].idx == insn_idx)
+ return &st->jmp_history[hist_end - 1];
return NULL;
}
@@ -3908,26 +3914,25 @@ static struct bpf_insn_hist_entry *get_insn_hist_entry(struct bpf_verifier_env *
* history entry recording a jump from last instruction of parent state and
* first instruction of given state.
*/
-static int get_prev_insn_idx(const struct bpf_verifier_env *env,
- struct bpf_verifier_state *st,
- int insn_idx, u32 hist_start, u32 *hist_endp)
+static int get_prev_insn_idx(struct bpf_verifier_state *st, int i,
+ u32 *history)
{
- u32 hist_end = *hist_endp;
- u32 cnt = hist_end - hist_start;
+ u32 cnt = *history;
- if (insn_idx == st->first_insn_idx) {
+ if (i == st->first_insn_idx) {
if (cnt == 0)
return -ENOENT;
- if (cnt == 1 && env->insn_hist[hist_start].idx == insn_idx)
+ if (cnt == 1 && st->jmp_history[0].idx == i)
return -ENOENT;
}
- if (cnt && env->insn_hist[hist_end - 1].idx == insn_idx) {
- (*hist_endp)--;
- return env->insn_hist[hist_end - 1].prev_idx;
+ if (cnt && st->jmp_history[cnt - 1].idx == i) {
+ i = st->jmp_history[cnt - 1].prev_idx;
+ (*history)--;
} else {
- return insn_idx - 1;
+ i--;
}
+ return i;
}
static const char *disasm_kfunc_name(void *data, const struct bpf_insn *insn)
@@ -4108,7 +4113,7 @@ static void fmt_stack_mask(char *buf, ssize_t buf_sz, u64 stack_mask)
/* If any register R in hist->linked_regs is marked as precise in bt,
* do bt_set_frame_{reg,slot}(bt, R) for all registers in hist->linked_regs.
*/
-static void bt_sync_linked_regs(struct backtrack_state *bt, struct bpf_insn_hist_entry *hist)
+static void bt_sync_linked_regs(struct backtrack_state *bt, struct bpf_jmp_history_entry *hist)
{
struct linked_regs linked_regs;
bool some_precise = false;
@@ -4153,7 +4158,7 @@ static bool calls_callback(struct bpf_verifier_env *env, int insn_idx);
* - *was* processed previously during backtracking.
*/
static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
- struct bpf_insn_hist_entry *hist, struct backtrack_state *bt)
+ struct bpf_jmp_history_entry *hist, struct backtrack_state *bt)
{
struct bpf_insn *insn = env->prog->insnsi + idx;
u8 class = BPF_CLASS(insn->code);
@@ -4571,7 +4576,7 @@ static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_
* SCALARS, as well as any other registers and slots that contribute to
* a tracked state of given registers/stack slots, depending on specific BPF
* assembly instructions (see backtrack_insns() for exact instruction handling
- * logic). This backtracking relies on recorded insn_hist and is able to
+ * logic). This backtracking relies on recorded jmp_history and is able to
* traverse entire chain of parent states. This process ends only when all the
* necessary registers/slots and their transitive dependencies are marked as
* precise.
@@ -4688,9 +4693,8 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno)
for (;;) {
DECLARE_BITMAP(mask, 64);
- u32 hist_start = st->insn_hist_start;
- u32 hist_end = st->insn_hist_end;
- struct bpf_insn_hist_entry *hist;
+ u32 history = st->jmp_history_cnt;
+ struct bpf_jmp_history_entry *hist;
if (env->log.level & BPF_LOG_LEVEL2) {
verbose(env, "mark_precise: frame%d: last_idx %d first_idx %d subseq_idx %d \n",
@@ -4728,7 +4732,7 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno)
err = 0;
skip_first = false;
} else {
- hist = get_insn_hist_entry(env, hist_start, hist_end, i);
+ hist = get_jmp_hist_entry(st, history, i);
err = backtrack_insn(env, i, subseq_idx, hist, bt);
}
if (err == -ENOTSUPP) {
@@ -4745,7 +4749,7 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno)
*/
return 0;
subseq_idx = i;
- i = get_prev_insn_idx(env, st, i, hist_start, &hist_end);
+ i = get_prev_insn_idx(st, i, &history);
if (i == -ENOENT)
break;
if (i >= env->prog->len) {
@@ -5109,7 +5113,7 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,
}
if (insn_flags)
- return push_insn_history(env, env->cur_state, insn_flags, 0);
+ return push_jmp_history(env, env->cur_state, insn_flags, 0);
return 0;
}
@@ -5416,7 +5420,7 @@ static int check_stack_read_fixed_off(struct bpf_verifier_env *env,
insn_flags = 0; /* we are not restoring spilled register */
}
if (insn_flags)
- return push_insn_history(env, env->cur_state, insn_flags, 0);
+ return push_jmp_history(env, env->cur_state, insn_flags, 0);
return 0;
}
@@ -16539,7 +16543,7 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
if (dst_reg->type == SCALAR_VALUE && dst_reg->id)
collect_linked_regs(this_branch, dst_reg->id, &linked_regs);
if (linked_regs.cnt > 1) {
- err = push_insn_history(env, this_branch, 0, linked_regs_pack(&linked_regs));
+ err = push_jmp_history(env, this_branch, 0, linked_regs_pack(&linked_regs));
if (err)
return err;
}
@@ -19037,7 +19041,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
force_new_state = env->test_state_freq || is_force_checkpoint(env, insn_idx) ||
/* Avoid accumulating infinitely long jmp history */
- cur->insn_hist_end - cur->insn_hist_start > 40;
+ cur->jmp_history_cnt > 40;
/* bpf progs typically have pruning point every 4 instructions
* http://vger.kernel.org/bpfconf2019.html#session-1
@@ -19236,7 +19240,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
* the current state.
*/
if (is_jmp_point(env, env->insn_idx))
- err = err ? : push_insn_history(env, cur, 0, 0);
+ err = err ? : push_jmp_history(env, cur, 0, 0);
err = err ? : propagate_precision(env, &sl->state);
if (err)
return err;
@@ -19318,8 +19322,8 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
cur->parent = new;
cur->first_insn_idx = insn_idx;
- cur->insn_hist_start = cur->insn_hist_end;
cur->dfs_depth = new->dfs_depth + 1;
+ clear_jmp_history(cur);
list_add(&new_sl->node, head);
/* connect new state to parentage chain. Current frame needs all
@@ -19487,7 +19491,7 @@ static int do_check(struct bpf_verifier_env *env)
}
if (is_jmp_point(env, env->insn_idx)) {
- err = push_insn_history(env, state, 0, 0);
+ err = push_jmp_history(env, state, 0, 0);
if (err)
return err;
}
@@ -24202,7 +24206,6 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3
if (!is_priv)
mutex_unlock(&bpf_verifier_lock);
vfree(env->insn_aux_data);
- kvfree(env->insn_hist);
err_free_env:
kvfree(env->cfg.insn_postorder);
kvfree(env);
--
2.48.1
^ permalink raw reply related [flat|nested] 12+ messages in thread
* [PATCH bpf-next v2 02/11] bpf: compute SCCs in program control flow graph
2025-06-06 21:03 [PATCH bpf-next v2 00/11] bpf: propagate read/precision marks over state graph backedges Eduard Zingerman
2025-06-06 21:03 ` [PATCH bpf-next v2 01/11] Revert "bpf: use common instruction history across all states" Eduard Zingerman
@ 2025-06-06 21:03 ` Eduard Zingerman
2025-06-06 21:03 ` [PATCH bpf-next v2 03/11] bpf: frame_insn_idx() utility function Eduard Zingerman
` (8 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: Eduard Zingerman @ 2025-06-06 21:03 UTC (permalink / raw)
To: bpf, ast
Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song,
Eduard Zingerman
Compute strongly connected components in the program CFG.
Assign an SCC number to each instruction, recorded in
env->insn_aux[*].scc. Use Tarjan's algorithm for SCC computation
adapted to run non-recursively.
For debug purposes print out computed SCCs as a part of full program
dump in compute_live_registers() at log level 2, e.g.:
func#0 @0
Live regs before insn:
0: .......... (b4) w6 = 10
2 1: ......6... (18) r1 = 0xffff88810bbb5565
2 3: .1....6... (b4) w2 = 2
2 4: .12...6... (85) call bpf_trace_printk#6
2 5: ......6... (04) w6 += -1
2 6: ......6... (56) if w6 != 0x0 goto pc-6
7: .......... (b4) w6 = 5
1 8: ......6... (18) r1 = 0xffff88810bbb5567
1 10: .1....6... (b4) w2 = 2
1 11: .12...6... (85) call bpf_trace_printk#6
1 12: ......6... (04) w6 += -1
1 13: ......6... (56) if w6 != 0x0 goto pc-6
14: .......... (b4) w0 = 0
15: 0......... (95) exit
^^^
SCC number for the instruction
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
include/linux/bpf_verifier.h | 5 +
kernel/bpf/verifier.c | 182 +++++++++++++++++++++++++++++++++++
2 files changed, 187 insertions(+)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 489105d0c8ab..f0b4e48c9d90 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -608,6 +608,11 @@ struct bpf_insn_aux_data {
* accepts callback function as a parameter.
*/
bool calls_callback;
+ /*
+ * CFG strongly connected component this instruction belongs to,
+ * zero if it is a singleton SCC.
+ */
+ u32 scc;
/* registers alive before this instruction. */
u16 live_regs_before;
};
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 98130b982a37..fa8c227775a5 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -23924,6 +23924,10 @@ static int compute_live_registers(struct bpf_verifier_env *env)
if (env->log.level & BPF_LOG_LEVEL2) {
verbose(env, "Live regs before insn:\n");
for (i = 0; i < insn_cnt; ++i) {
+ if (env->insn_aux_data[i].scc)
+ verbose(env, "%3d ", env->insn_aux_data[i].scc);
+ else
+ verbose(env, " ");
verbose(env, "%3d: ", i);
for (j = BPF_REG_0; j < BPF_REG_10; ++j)
if (insn_aux[i].live_regs_before & BIT(j))
@@ -23945,6 +23949,180 @@ static int compute_live_registers(struct bpf_verifier_env *env)
return err;
}
+/*
+ * Compute strongly connected components (SCCs) on the CFG.
+ * Assign an SCC number to each instruction, recorded in env->insn_aux[*].scc.
+ * If instruction is a sole member of its SCC and there are no self edges,
+ * assign it SCC number of zero.
+ * Uses a non-recursive adaptation of Tarjan's algorithm for SCC computation.
+ */
+static int compute_scc(struct bpf_verifier_env *env)
+{
+ const u32 NOT_ON_STACK = U32_MAX;
+
+ struct bpf_insn_aux_data *aux = env->insn_aux_data;
+ const u32 insn_cnt = env->prog->len;
+ int stack_sz, dfs_sz, err = 0;
+ u32 *stack, *pre, *low, *dfs;
+ u32 succ_cnt, i, j, t, w;
+ u32 next_preorder_num;
+ u32 next_scc_id;
+ bool assign_scc;
+ u32 succ[2];
+
+ next_preorder_num = 1;
+ next_scc_id = 1;
+ /*
+ * - 'stack' accumulates vertices in DFS order, see invariant comment below;
+ * - 'pre[t] == p' => preorder number of vertex 't' is 'p';
+ * - 'low[t] == n' => smallest preorder number of the vertex reachable from 't' is 'n';
+ * - 'dfs' DFS traversal stack, used to emulate explicit recursion.
+ */
+ stack = kvcalloc(insn_cnt, sizeof(int), GFP_KERNEL);
+ pre = kvcalloc(insn_cnt, sizeof(int), GFP_KERNEL);
+ low = kvcalloc(insn_cnt, sizeof(int), GFP_KERNEL);
+ dfs = kvcalloc(insn_cnt, sizeof(*dfs), GFP_KERNEL);
+ if (!stack || !pre || !low || !dfs) {
+ err = -ENOMEM;
+ goto exit;
+ }
+ /*
+ * References:
+ * [1] R. Tarjan "Depth-First Search and Linear Graph Algorithms"
+ * [2] D. J. Pearce "A Space-Efficient Algorithm for Finding Strongly Connected Components"
+ *
+ * The algorithm maintains the following invariant:
+ * - suppose there is a path 'u' ~> 'v', such that 'pre[v] < pre[u]';
+ * - then, vertex 'u' remains on stack while vertex 'v' is on stack.
+ *
+ * Consequently:
+ * - If 'low[v] < pre[v]', there is a path from 'v' to some vertex 'u',
+ * such that 'pre[u] == low[v]'; vertex 'u' is currently on the stack,
+ * and thus there is an SCC (loop) containing both 'u' and 'v'.
+ * - If 'low[v] == pre[v]', loops containing 'v' have been explored,
+ * and 'v' can be considered the root of some SCC.
+ *
+ * Here is a pseudo-code for an explicitly recursive version of the algorithm:
+ *
+ * NOT_ON_STACK = insn_cnt + 1
+ * pre = [0] * insn_cnt
+ * low = [0] * insn_cnt
+ * scc = [0] * insn_cnt
+ * stack = []
+ *
+ * next_preorder_num = 1
+ * next_scc_id = 1
+ *
+ * def recur(w):
+ * nonlocal next_preorder_num
+ * nonlocal next_scc_id
+ *
+ * pre[w] = next_preorder_num
+ * low[w] = next_preorder_num
+ * next_preorder_num += 1
+ * stack.append(w)
+ * for s in successors(w):
+ * # Note: for classic algorithm the block below should look as:
+ * #
+ * # if pre[s] == 0:
+ * # recur(s)
+ * # low[w] = min(low[w], low[s])
+ * # elif low[s] != NOT_ON_STACK:
+ * # low[w] = min(low[w], pre[s])
+ * #
+ * # But replacing both 'min' instructions with 'low[w] = min(low[w], low[s])'
+ * # does not break the invariant and makes itartive version of the algorithm
+ * # simpler. See 'Algorithm #3' from [2].
+ *
+ * # 's' not yet visited
+ * if pre[s] == 0:
+ * recur(s)
+ * # if 's' is on stack, pick lowest reachable preorder number from it;
+ * # if 's' is not on stack 'low[s] == NOT_ON_STACK > low[w]',
+ * # so 'min' would be a noop.
+ * low[w] = min(low[w], low[s])
+ *
+ * if low[w] == pre[w]:
+ * # 'w' is the root of an SCC, pop all vertices
+ * # below 'w' on stack and assign same SCC to them.
+ * while True:
+ * t = stack.pop()
+ * low[t] = NOT_ON_STACK
+ * scc[t] = next_scc_id
+ * if t == w:
+ * break
+ * next_scc_id += 1
+ *
+ * for i in range(0, insn_cnt):
+ * if pre[i] == 0:
+ * recur(i)
+ *
+ * Below implementation replaces explicit recusion with array 'dfs'.
+ */
+ for (i = 0; i < insn_cnt; i++) {
+ if (pre[i])
+ continue;
+ stack_sz = 0;
+ dfs_sz = 1;
+ dfs[0] = i;
+dfs_continue:
+ while (dfs_sz) {
+ w = dfs[dfs_sz - 1];
+ if (pre[w] == 0) {
+ low[w] = next_preorder_num;
+ pre[w] = next_preorder_num;
+ next_preorder_num++;
+ stack[stack_sz++] = w;
+ }
+ /* Visit 'w' successors */
+ succ_cnt = insn_successors(env->prog, w, succ);
+ for (j = 0; j < succ_cnt; ++j) {
+ if (pre[succ[j]]) {
+ low[w] = min(low[w], low[succ[j]]);
+ } else {
+ dfs[dfs_sz++] = succ[j];
+ goto dfs_continue;
+ }
+ }
+ /*
+ * Preserve the invariant: if some vertex above in the stack
+ * is reachable from 'w', keep 'w' on the stack.
+ */
+ if (low[w] < pre[w]) {
+ dfs_sz--;
+ goto dfs_continue;
+ }
+ /*
+ * Assign SCC number only if component has two or more elements,
+ * or if component has a self reference.
+ */
+ assign_scc = stack[stack_sz - 1] != w;
+ for (j = 0; j < succ_cnt; ++j) {
+ if (succ[j] == w) {
+ assign_scc = true;
+ break;
+ }
+ }
+ /* Pop component elements from stack */
+ do {
+ t = stack[--stack_sz];
+ low[t] = NOT_ON_STACK;
+ if (assign_scc)
+ aux[t].scc = next_scc_id;
+ } while (t != w);
+ if (assign_scc)
+ next_scc_id++;
+ dfs_sz--;
+ }
+ }
+exit:
+ kvfree(stack);
+ kvfree(pre);
+ kvfree(low);
+ kvfree(dfs);
+ return err;
+}
+
int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u32 uattr_size)
{
u64 start_time = ktime_get_ns();
@@ -24066,6 +24244,10 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3
if (ret)
goto skip_full_check;
+ ret = compute_scc(env);
+ if (ret < 0)
+ goto skip_full_check;
+
ret = compute_live_registers(env);
if (ret < 0)
goto skip_full_check;
--
2.48.1
^ permalink raw reply related [flat|nested] 12+ messages in thread
* [PATCH bpf-next v2 03/11] bpf: frame_insn_idx() utility function
2025-06-06 21:03 [PATCH bpf-next v2 00/11] bpf: propagate read/precision marks over state graph backedges Eduard Zingerman
2025-06-06 21:03 ` [PATCH bpf-next v2 01/11] Revert "bpf: use common instruction history across all states" Eduard Zingerman
2025-06-06 21:03 ` [PATCH bpf-next v2 02/11] bpf: compute SCCs in program control flow graph Eduard Zingerman
@ 2025-06-06 21:03 ` Eduard Zingerman
2025-06-06 21:03 ` [PATCH bpf-next v2 04/11] bpf: starting_state parameter for __mark_chain_precision() Eduard Zingerman
` (7 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: Eduard Zingerman @ 2025-06-06 21:03 UTC (permalink / raw)
To: bpf, ast
Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song,
Eduard Zingerman
A function to return IP for a given frame in a call stack of a state.
Will be used by a next patch.
The `state->insn_idx = env->insn_idx;` assignment in the do_check()
allows to use frame_insn_idx with env->cur_state.
At the moment bpf_verifier_state->insn_idx is set when new cached
state is added in is_state_visited() and accessed only in the contexts
when the state is already in the cache. Hence this assignment does not
change verifier behaviour.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
kernel/bpf/verifier.c | 13 ++++++++++---
1 file changed, 10 insertions(+), 3 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index fa8c227775a5..644ffc23db1a 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1963,6 +1963,14 @@ static void update_loop_entry(struct bpf_verifier_env *env,
}
}
+/* Return IP for a given frame in a call stack */
+static u32 frame_insn_idx(struct bpf_verifier_state *st, u32 frame)
+{
+ return frame == st->curframe
+ ? st->insn_idx
+ : st->frame[frame + 1]->callsite;
+}
+
static void update_branch_counts(struct bpf_verifier_env *env, struct bpf_verifier_state *st)
{
struct bpf_verifier_state_list *sl = NULL, *parent_sl;
@@ -18775,9 +18783,7 @@ static bool states_equal(struct bpf_verifier_env *env,
* and all frame states need to be equivalent
*/
for (i = 0; i <= old->curframe; i++) {
- insn_idx = i == old->curframe
- ? env->insn_idx
- : old->frame[i + 1]->callsite;
+ insn_idx = frame_insn_idx(old, i);
if (old->frame[i]->callsite != cur->frame[i]->callsite)
return false;
if (!func_states_equal(env, old->frame[i], cur->frame[i], insn_idx, exact))
@@ -19470,6 +19476,7 @@ static int do_check(struct bpf_verifier_env *env)
}
state->last_insn_idx = env->prev_insn_idx;
+ state->insn_idx = env->insn_idx;
if (is_prune_point(env, env->insn_idx)) {
err = is_state_visited(env, env->insn_idx);
--
2.48.1
^ permalink raw reply related [flat|nested] 12+ messages in thread
* [PATCH bpf-next v2 04/11] bpf: starting_state parameter for __mark_chain_precision()
2025-06-06 21:03 [PATCH bpf-next v2 00/11] bpf: propagate read/precision marks over state graph backedges Eduard Zingerman
` (2 preceding siblings ...)
2025-06-06 21:03 ` [PATCH bpf-next v2 03/11] bpf: frame_insn_idx() utility function Eduard Zingerman
@ 2025-06-06 21:03 ` Eduard Zingerman
2025-06-06 21:03 ` [PATCH bpf-next v2 05/11] bpf: set 'changed' status if propagate_precision() did any updates Eduard Zingerman
` (6 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: Eduard Zingerman @ 2025-06-06 21:03 UTC (permalink / raw)
To: bpf, ast
Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song,
Eduard Zingerman
Allow `mark_chain_precision()` to run from an arbitrary starting state
by replacing direct references to `env->cur_state` with a parameter.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
kernel/bpf/verifier.c | 24 +++++++++++++-----------
1 file changed, 13 insertions(+), 11 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 644ffc23db1a..20e9d629380f 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -4664,12 +4664,13 @@ static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_
* mark_all_scalars_imprecise() to hopefully get more permissive and generic
* finalized states which help in short circuiting more future states.
*/
-static int __mark_chain_precision(struct bpf_verifier_env *env, int regno)
+static int __mark_chain_precision(struct bpf_verifier_env *env,
+ struct bpf_verifier_state *starting_state, int regno)
{
+ struct bpf_verifier_state *st = starting_state;
struct backtrack_state *bt = &env->bt;
- struct bpf_verifier_state *st = env->cur_state;
int first_idx = st->first_insn_idx;
- int last_idx = env->insn_idx;
+ int last_idx = starting_state->insn_idx;
int subseq_idx = -1;
struct bpf_func_state *func;
struct bpf_reg_state *reg;
@@ -4680,7 +4681,7 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno)
return 0;
/* set frame number from which we are starting to backtrack */
- bt_init(bt, env->cur_state->curframe);
+ bt_init(bt, starting_state->curframe);
/* Do sanity checks against current state of register and/or stack
* slot, but don't set precise flag in current state, as precision
@@ -4744,7 +4745,7 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno)
err = backtrack_insn(env, i, subseq_idx, hist, bt);
}
if (err == -ENOTSUPP) {
- mark_all_scalars_precise(env, env->cur_state);
+ mark_all_scalars_precise(env, starting_state);
bt_reset(bt);
return 0;
} else if (err) {
@@ -4832,7 +4833,7 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno)
* fallback to marking all precise
*/
if (!bt_empty(bt)) {
- mark_all_scalars_precise(env, env->cur_state);
+ mark_all_scalars_precise(env, starting_state);
bt_reset(bt);
}
@@ -4841,15 +4842,16 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno)
int mark_chain_precision(struct bpf_verifier_env *env, int regno)
{
- return __mark_chain_precision(env, regno);
+ return __mark_chain_precision(env, env->cur_state, regno);
}
/* mark_chain_precision_batch() assumes that env->bt is set in the caller to
* desired reg and stack masks across all relevant frames
*/
-static int mark_chain_precision_batch(struct bpf_verifier_env *env)
+static int mark_chain_precision_batch(struct bpf_verifier_env *env,
+ struct bpf_verifier_state *starting_state)
{
- return __mark_chain_precision(env, -1);
+ return __mark_chain_precision(env, starting_state, -1);
}
static bool is_spillable_regtype(enum bpf_reg_type type)
@@ -9502,7 +9504,7 @@ static int get_constant_map_key(struct bpf_verifier_env *env,
* to prevent pruning on it.
*/
bt_set_frame_slot(&env->bt, key->frameno, spi);
- err = mark_chain_precision_batch(env);
+ err = mark_chain_precision_batch(env, env->cur_state);
if (err < 0)
return err;
@@ -18924,7 +18926,7 @@ static int propagate_precision(struct bpf_verifier_env *env,
verbose(env, "\n");
}
- err = mark_chain_precision_batch(env);
+ err = mark_chain_precision_batch(env, env->cur_state);
if (err < 0)
return err;
--
2.48.1
^ permalink raw reply related [flat|nested] 12+ messages in thread
* [PATCH bpf-next v2 05/11] bpf: set 'changed' status if propagate_precision() did any updates
2025-06-06 21:03 [PATCH bpf-next v2 00/11] bpf: propagate read/precision marks over state graph backedges Eduard Zingerman
` (3 preceding siblings ...)
2025-06-06 21:03 ` [PATCH bpf-next v2 04/11] bpf: starting_state parameter for __mark_chain_precision() Eduard Zingerman
@ 2025-06-06 21:03 ` Eduard Zingerman
2025-06-06 21:03 ` [PATCH bpf-next v2 06/11] bpf: set 'changed' status if propagate_liveness() " Eduard Zingerman
` (5 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: Eduard Zingerman @ 2025-06-06 21:03 UTC (permalink / raw)
To: bpf, ast
Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song,
Eduard Zingerman
Add an out parameter to `propagate_precision()` to record whether any
new precision bits were set during its execution.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
kernel/bpf/verifier.c | 35 +++++++++++++++++++++++------------
1 file changed, 23 insertions(+), 12 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 20e9d629380f..046d5515008b 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -4665,7 +4665,9 @@ static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_
* finalized states which help in short circuiting more future states.
*/
static int __mark_chain_precision(struct bpf_verifier_env *env,
- struct bpf_verifier_state *starting_state, int regno)
+ struct bpf_verifier_state *starting_state,
+ int regno,
+ bool *changed)
{
struct bpf_verifier_state *st = starting_state;
struct backtrack_state *bt = &env->bt;
@@ -4673,13 +4675,14 @@ static int __mark_chain_precision(struct bpf_verifier_env *env,
int last_idx = starting_state->insn_idx;
int subseq_idx = -1;
struct bpf_func_state *func;
+ bool tmp, skip_first = true;
struct bpf_reg_state *reg;
- bool skip_first = true;
int i, fr, err;
if (!env->bpf_capable)
return 0;
+ changed = changed ?: &tmp;
/* set frame number from which we are starting to backtrack */
bt_init(bt, starting_state->curframe);
@@ -4725,8 +4728,10 @@ static int __mark_chain_precision(struct bpf_verifier_env *env,
for_each_set_bit(i, mask, 32) {
reg = &st->frame[0]->regs[i];
bt_clear_reg(bt, i);
- if (reg->type == SCALAR_VALUE)
+ if (reg->type == SCALAR_VALUE) {
reg->precise = true;
+ *changed = true;
+ }
}
return 0;
}
@@ -4785,10 +4790,12 @@ static int __mark_chain_precision(struct bpf_verifier_env *env,
bt_clear_frame_reg(bt, fr, i);
continue;
}
- if (reg->precise)
+ if (reg->precise) {
bt_clear_frame_reg(bt, fr, i);
- else
+ } else {
reg->precise = true;
+ *changed = true;
+ }
}
bitmap_from_u64(mask, bt_frame_stack_mask(bt, fr));
@@ -4803,10 +4810,12 @@ static int __mark_chain_precision(struct bpf_verifier_env *env,
continue;
}
reg = &func->stack[i].spilled_ptr;
- if (reg->precise)
+ if (reg->precise) {
bt_clear_frame_slot(bt, fr, i);
- else
+ } else {
reg->precise = true;
+ *changed = true;
+ }
}
if (env->log.level & BPF_LOG_LEVEL2) {
fmt_reg_mask(env->tmp_str_buf, TMP_STR_BUF_LEN,
@@ -4842,7 +4851,7 @@ static int __mark_chain_precision(struct bpf_verifier_env *env,
int mark_chain_precision(struct bpf_verifier_env *env, int regno)
{
- return __mark_chain_precision(env, env->cur_state, regno);
+ return __mark_chain_precision(env, env->cur_state, regno, NULL);
}
/* mark_chain_precision_batch() assumes that env->bt is set in the caller to
@@ -4851,7 +4860,7 @@ int mark_chain_precision(struct bpf_verifier_env *env, int regno)
static int mark_chain_precision_batch(struct bpf_verifier_env *env,
struct bpf_verifier_state *starting_state)
{
- return __mark_chain_precision(env, starting_state, -1);
+ return __mark_chain_precision(env, starting_state, -1, NULL);
}
static bool is_spillable_regtype(enum bpf_reg_type type)
@@ -18878,7 +18887,9 @@ static int propagate_liveness(struct bpf_verifier_env *env,
* propagate them into the current state
*/
static int propagate_precision(struct bpf_verifier_env *env,
- const struct bpf_verifier_state *old)
+ const struct bpf_verifier_state *old,
+ struct bpf_verifier_state *cur,
+ bool *changed)
{
struct bpf_reg_state *state_reg;
struct bpf_func_state *state;
@@ -18926,7 +18937,7 @@ static int propagate_precision(struct bpf_verifier_env *env,
verbose(env, "\n");
}
- err = mark_chain_precision_batch(env, env->cur_state);
+ err = __mark_chain_precision(env, cur, -1, changed);
if (err < 0)
return err;
@@ -19249,7 +19260,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
*/
if (is_jmp_point(env, env->insn_idx))
err = err ? : push_jmp_history(env, cur, 0, 0);
- err = err ? : propagate_precision(env, &sl->state);
+ err = err ? : propagate_precision(env, &sl->state, cur, NULL);
if (err)
return err;
return 1;
--
2.48.1
^ permalink raw reply related [flat|nested] 12+ messages in thread
* [PATCH bpf-next v2 06/11] bpf: set 'changed' status if propagate_liveness() did any updates
2025-06-06 21:03 [PATCH bpf-next v2 00/11] bpf: propagate read/precision marks over state graph backedges Eduard Zingerman
` (4 preceding siblings ...)
2025-06-06 21:03 ` [PATCH bpf-next v2 05/11] bpf: set 'changed' status if propagate_precision() did any updates Eduard Zingerman
@ 2025-06-06 21:03 ` Eduard Zingerman
2025-06-06 21:03 ` [PATCH bpf-next v2 07/11] bpf: move REG_LIVE_DONE check to clean_live_states() Eduard Zingerman
` (4 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: Eduard Zingerman @ 2025-06-06 21:03 UTC (permalink / raw)
To: bpf, ast
Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song,
Eduard Zingerman
Add an out parameter to `propagate_liveness()` to record whether any
new liveness bits were set during its execution.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
kernel/bpf/verifier.c | 9 +++++++--
1 file changed, 7 insertions(+), 2 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 046d5515008b..8e2062e38307 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -18841,12 +18841,15 @@ static int propagate_liveness_reg(struct bpf_verifier_env *env,
*/
static int propagate_liveness(struct bpf_verifier_env *env,
const struct bpf_verifier_state *vstate,
- struct bpf_verifier_state *vparent)
+ struct bpf_verifier_state *vparent,
+ bool *changed)
{
struct bpf_reg_state *state_reg, *parent_reg;
struct bpf_func_state *state, *parent;
int i, frame, err = 0;
+ bool tmp;
+ changed = changed ?: &tmp;
if (vparent->curframe != vstate->curframe) {
WARN(1, "propagate_live: parent frame %d current frame %d\n",
vparent->curframe, vstate->curframe);
@@ -18865,6 +18868,7 @@ static int propagate_liveness(struct bpf_verifier_env *env,
&parent_reg[i]);
if (err < 0)
return err;
+ *changed |= err > 0;
if (err == REG_LIVE_READ64)
mark_insn_zext(env, &parent_reg[i]);
}
@@ -18876,6 +18880,7 @@ static int propagate_liveness(struct bpf_verifier_env *env,
state_reg = &state->stack[i].spilled_ptr;
err = propagate_liveness_reg(env, state_reg,
parent_reg);
+ *changed |= err > 0;
if (err < 0)
return err;
}
@@ -19251,7 +19256,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
* they'll be immediately forgotten as we're pruning
* this state and will pop a new one.
*/
- err = propagate_liveness(env, &sl->state, cur);
+ err = propagate_liveness(env, &sl->state, cur, NULL);
/* if previous state reached the exit with precision and
* current state is equivalent to it (except precision marks)
--
2.48.1
^ permalink raw reply related [flat|nested] 12+ messages in thread
* [PATCH bpf-next v2 07/11] bpf: move REG_LIVE_DONE check to clean_live_states()
2025-06-06 21:03 [PATCH bpf-next v2 00/11] bpf: propagate read/precision marks over state graph backedges Eduard Zingerman
` (5 preceding siblings ...)
2025-06-06 21:03 ` [PATCH bpf-next v2 06/11] bpf: set 'changed' status if propagate_liveness() " Eduard Zingerman
@ 2025-06-06 21:03 ` Eduard Zingerman
2025-06-06 21:03 ` [PATCH bpf-next v2 08/11] bpf: propagate read/precision marks over state graph backedges Eduard Zingerman
` (3 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: Eduard Zingerman @ 2025-06-06 21:03 UTC (permalink / raw)
To: bpf, ast
Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song,
Eduard Zingerman
The next patch would add some relatively heavy-weight operation to
clean_live_states(), this operation can be skipped if REG_LIVE_DONE
is set. Move the check from clean_verifier_state() to
clean_verifier_state() as a small refactoring commit.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
kernel/bpf/verifier.c | 7 +++----
1 file changed, 3 insertions(+), 4 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 8e2062e38307..4dd95f34f7fd 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -18290,10 +18290,6 @@ static void clean_verifier_state(struct bpf_verifier_env *env,
{
int i;
- if (st->frame[0]->regs[0].live & REG_LIVE_DONE)
- /* all regs in this state in all frames were already marked */
- return;
-
for (i = 0; i <= st->curframe; i++)
clean_func_state(env, st->frame[i]);
}
@@ -18348,6 +18344,9 @@ static void clean_live_states(struct bpf_verifier_env *env, int insn,
if (sl->state.insn_idx != insn ||
!same_callsites(&sl->state, cur))
continue;
+ if (sl->state.frame[0]->regs[0].live & REG_LIVE_DONE)
+ /* all regs in this state in all frames were already marked */
+ continue;
clean_verifier_state(env, &sl->state);
}
}
--
2.48.1
^ permalink raw reply related [flat|nested] 12+ messages in thread
* [PATCH bpf-next v2 08/11] bpf: propagate read/precision marks over state graph backedges
2025-06-06 21:03 [PATCH bpf-next v2 00/11] bpf: propagate read/precision marks over state graph backedges Eduard Zingerman
` (6 preceding siblings ...)
2025-06-06 21:03 ` [PATCH bpf-next v2 07/11] bpf: move REG_LIVE_DONE check to clean_live_states() Eduard Zingerman
@ 2025-06-06 21:03 ` Eduard Zingerman
2025-06-06 21:03 ` [PATCH bpf-next v2 09/11] bpf: remove {update,get}_loop_entry functions Eduard Zingerman
` (2 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: Eduard Zingerman @ 2025-06-06 21:03 UTC (permalink / raw)
To: bpf, ast
Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song,
Eduard Zingerman
Current loop_entry-based exact states comparison logic does not handle
the following case:
.-> A --. Assume the states are visited in the order A, B, C.
| | | Assume that state B reaches a state equivalent to state A.
| v v At this point, state C is not processed yet, so state A
'-- B C has not received any read or precision marks from C.
As a result, these marks won't be propagated to B.
If B has incomplete marks, it is unsafe to use it in states_equal()
checks.
This commit replaces the existing logic with the following:
- Strongly connected components (SCCs) are computed over the program's
control flow graph (intraprocedurally).
- When a verifier state enters an SCC, that state is recorded as the
SCC entry point.
- When a verifier state is found equivalent to another (e.g., B to A
in the example), it is recorded as a states graph backedge.
Backedges are accumulated per SCC.
- When an SCC entry state reaches `branches == 0`, read and precision
marks are propagated through the backedges (e.g., from A to B, from
C to A, and then again from A to B).
To support nested subprogram calls, the entry state and backedge list
are associated not with the SCC itself but with an object called
`bpf_scc_callchain`. A callchain is a tuple `(callsite*, scc_id)`,
where `callsite` is the index of a call instruction for each frame
except the last.
See the comments added in `is_state_visited()` and
`compute_scc_callchain()` for more details.
Fixes: 2a0992829ea3 ("bpf: correct loop detection for iterators convergence")
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
include/linux/bpf_verifier.h | 38 +++
kernel/bpf/verifier.c | 454 +++++++++++++++++++++++++++++------
2 files changed, 423 insertions(+), 69 deletions(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index f0b4e48c9d90..5190d71bd8fb 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -459,6 +459,10 @@ struct bpf_verifier_state {
* See get_loop_entry() for more information.
*/
struct bpf_verifier_state *loop_entry;
+ /* if this state is a backedge state then equal_state
+ * records cached state to which this state is equal.
+ */
+ struct bpf_verifier_state *equal_state;
/* jmp history recorded from first to last.
* backtracking is using it to go from last to first.
* For most states jmp_history_cnt is [0-3].
@@ -722,6 +726,37 @@ struct bpf_idset {
u32 ids[BPF_ID_MAP_SIZE];
};
+/* see verifier.c:compute_scc_callchain() */
+struct bpf_scc_callchain {
+ /* call sites from bpf_verifier_state->frame[*]->callsite leading to this SCC */
+ u32 callsites[MAX_CALL_FRAMES - 1];
+ /* last frame in a chain is identified by SCC id */
+ u32 scc;
+};
+
+/* verifier state waiting for propagate_backedges() */
+struct bpf_scc_backedge {
+ struct bpf_scc_backedge *next;
+ struct bpf_verifier_state state;
+};
+
+struct bpf_scc_visit {
+ struct bpf_scc_callchain callchain;
+ /* first state in current verification path that entered SCC
+ * identified by the callchain
+ */
+ struct bpf_verifier_state *entry_state;
+ struct bpf_scc_backedge *backedges; /* list of backedges */
+};
+
+/* An array of bpf_scc_visit structs sharing tht same bpf_scc_callchain->scc
+ * but having different bpf_scc_callchain->callsites.
+ */
+struct bpf_scc_info {
+ u32 num_visits;
+ struct bpf_scc_visit visits[];
+};
+
/* single container for all structs
* one verifier_env per bpf_check() call
*/
@@ -818,6 +853,9 @@ struct bpf_verifier_env {
char tmp_str_buf[TMP_STR_BUF_LEN];
struct bpf_insn insn_buf[INSN_BUF_SIZE];
struct bpf_insn epilogue_buf[INSN_BUF_SIZE];
+ /* array of pointers to bpf_scc_info indexed by SCC id */
+ struct bpf_scc_info **scc_info;
+ u32 scc_cnt;
};
static inline struct bpf_func_info_aux *subprog_aux(struct bpf_verifier_env *env, int subprog)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 4dd95f34f7fd..9a5af34f5917 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1699,6 +1699,9 @@ static struct bpf_verifier_state_list *state_loop_entry_as_list(struct bpf_verif
return NULL;
}
+static bool incomplete_read_marks(struct bpf_verifier_env *env,
+ struct bpf_verifier_state *st);
+
/* A state can be freed if it is no longer referenced:
* - is in the env->free_list;
* - has no children states;
@@ -1709,20 +1712,14 @@ static struct bpf_verifier_state_list *state_loop_entry_as_list(struct bpf_verif
static void maybe_free_verifier_state(struct bpf_verifier_env *env,
struct bpf_verifier_state_list *sl)
{
- struct bpf_verifier_state_list *loop_entry_sl;
-
- while (sl && sl->in_free_list &&
- sl->state.branches == 0 &&
- sl->state.used_as_loop_entry == 0) {
- loop_entry_sl = state_loop_entry_as_list(&sl->state);
- if (loop_entry_sl)
- loop_entry_sl->state.used_as_loop_entry--;
- list_del(&sl->node);
- free_verifier_state(&sl->state, false);
- kfree(sl);
- env->free_list_size--;
- sl = loop_entry_sl;
- }
+ if (!sl->in_free_list
+ || sl->state.branches != 0
+ || incomplete_read_marks(env, &sl->state))
+ return;
+ list_del(&sl->node);
+ free_verifier_state(&sl->state, false);
+ kfree(sl);
+ env->free_list_size--;
}
/* copy verifier state from src to dst growing dst stack space
@@ -1770,6 +1767,7 @@ static int copy_verifier_state(struct bpf_verifier_state *dst_state,
dst_state->used_as_loop_entry = src->used_as_loop_entry;
dst_state->may_goto_depth = src->may_goto_depth;
dst_state->loop_entry = src->loop_entry;
+ dst_state->equal_state = src->equal_state;
for (i = 0; i <= src->curframe; i++) {
dst = dst_state->frame[i];
if (!dst) {
@@ -1971,22 +1969,218 @@ static u32 frame_insn_idx(struct bpf_verifier_state *st, u32 frame)
: st->frame[frame + 1]->callsite;
}
-static void update_branch_counts(struct bpf_verifier_env *env, struct bpf_verifier_state *st)
+/* For state @st look for a topmost frame with frame_insn_idx() in some SCC,
+ * if such frame exists form a corresponding @callchain as an array of
+ * call sites leading to this frame and SCC id.
+ * E.g.:
+ *
+ * void foo() { A: loop {... SCC#1 ...}; }
+ * void bar() { B: loop { C: foo(); ... SCC#2 ... }
+ * D: loop { E: foo(); ... SCC#3 ... } }
+ * void main() { F: bar(); }
+ *
+ * @callchain at (A) would be either (F,SCC#2) or (F,SCC#3) depending
+ * on @st frame call sites being (F,C,A) or (F,E,A).
+ */
+static bool compute_scc_callchain(struct bpf_verifier_env *env,
+ struct bpf_verifier_state *st,
+ struct bpf_scc_callchain *callchain)
+{
+ u32 i, scc, insn_idx;
+
+ memset(callchain, 0, sizeof(*callchain));
+ for (i = 0; i <= st->curframe; i++) {
+ insn_idx = frame_insn_idx(st, i);
+ scc = env->insn_aux_data[insn_idx].scc;
+ if (scc) {
+ callchain->scc = scc;
+ break;
+ } else if (i < st->curframe) {
+ callchain->callsites[i] = insn_idx;
+ } else {
+ return false;
+ }
+ }
+ return true;
+}
+
+/* Check if bpf_scc_visit instance for @callchain exists. */
+static struct bpf_scc_visit *scc_visit_lookup(struct bpf_verifier_env *env,
+ struct bpf_scc_callchain *callchain)
+{
+ struct bpf_scc_info *info = env->scc_info[callchain->scc];
+ struct bpf_scc_visit *visits = info->visits;
+ u32 i;
+
+ if (!info)
+ return NULL;
+ for (i = 0; i < info->num_visits; i++)
+ if (memcmp(callchain, &visits[i].callchain, sizeof(*callchain)) == 0)
+ return &visits[i];
+ return NULL;
+}
+
+/* Allocate a new bpf_scc_visit instance corresponding to @callchain.
+ * Allocated instances are alive for a duration of the do_check_common()
+ * call and are freed by free_states().
+ */
+static struct bpf_scc_visit *scc_visit_alloc(struct bpf_verifier_env *env,
+ struct bpf_scc_callchain *callchain)
+{
+ struct bpf_scc_visit *visit;
+ struct bpf_scc_info *info;
+ u32 scc, num_visits;
+ u64 new_sz;
+
+ scc = callchain->scc;
+ info = env->scc_info[scc];
+ num_visits = info ? info->num_visits : 0;
+ new_sz = sizeof(*info) + sizeof(struct bpf_scc_visit) * (num_visits + 1);
+ info = kvrealloc(env->scc_info[scc], new_sz, GFP_KERNEL);
+ if (!info)
+ return NULL;
+ env->scc_info[scc] = info;
+ info->num_visits = num_visits + 1;
+ visit = &info->visits[num_visits];
+ memset(visit, 0, sizeof(*visit));
+ memcpy(&visit->callchain, callchain, sizeof(*callchain));
+ return visit;
+}
+
+/* Form a string '(callsite#1,callsite#2,...,scc)' in env->tmp_str_buf */
+static char *format_callchain(struct bpf_verifier_env *env, struct bpf_scc_callchain *callchain)
+{
+ char *buf = env->tmp_str_buf;
+ int i, delta = 0;
+
+ delta += snprintf(buf + delta, TMP_STR_BUF_LEN - delta, "(");
+ for (i = 0; i < ARRAY_SIZE(callchain->callsites); i++) {
+ if (!callchain->callsites[i])
+ break;
+ delta += snprintf(buf + delta, TMP_STR_BUF_LEN - delta, "%u,",
+ callchain->callsites[i]);
+ }
+ delta += snprintf(buf + delta, TMP_STR_BUF_LEN - delta, "%u)", callchain->scc);
+ return env->tmp_str_buf;
+}
+
+/* If callchain for @st exists (@st is in some SCC), ensure that
+ * bpf_scc_visit instance for this callchain exists.
+ * If instance does not exist or is empty, assign visit->entry_state to @st.
+ */
+static int maybe_enter_scc(struct bpf_verifier_env *env, struct bpf_verifier_state *st)
+{
+ struct bpf_scc_callchain callchain;
+ struct bpf_scc_visit *visit;
+
+ if (!compute_scc_callchain(env, st, &callchain))
+ return 0;
+ visit = scc_visit_lookup(env, &callchain);
+ visit = visit ?: scc_visit_alloc(env, &callchain);
+ if (!visit)
+ return -ENOMEM;
+ if (!visit->entry_state) {
+ visit->entry_state = st;
+ if (env->log.level & BPF_LOG_LEVEL2)
+ verbose(env, "SCC enter %s\n", format_callchain(env, &callchain));
+ }
+ return 0;
+}
+
+static int propagate_backedges(struct bpf_verifier_env *env, struct bpf_scc_visit *visit);
+
+/* If callchain for @st exists (@st is in some SCC), make it empty:
+ * - set visit->entry_state to NULL;
+ * - flush accumulated backedges.
+ */
+static int maybe_exit_scc(struct bpf_verifier_env *env, struct bpf_verifier_state *st)
+{
+ struct bpf_scc_callchain callchain;
+ struct bpf_scc_visit *visit;
+
+ if (!compute_scc_callchain(env, st, &callchain))
+ return 0;
+ visit = scc_visit_lookup(env, &callchain);
+ if (!visit) {
+ verifier_bug(env, "scc exit: no visit info for call chain %s",
+ format_callchain(env, &callchain));
+ return -EFAULT;
+ }
+ if (visit->entry_state != st)
+ return 0;
+ if (env->log.level & BPF_LOG_LEVEL2)
+ verbose(env, "SCC exit %s\n", format_callchain(env, &callchain));
+ visit->entry_state = NULL;
+ return propagate_backedges(env, visit);
+}
+
+/* Lookup an bpf_scc_visit instance corresponding to @st callchain
+ * and add @backedge to visit->backedges. @st callchain must exist.
+ */
+static int add_scc_backedge(struct bpf_verifier_env *env,
+ struct bpf_verifier_state *st,
+ struct bpf_scc_backedge *backedge)
+{
+ struct bpf_scc_callchain callchain;
+ struct bpf_scc_visit *visit;
+
+ if (!compute_scc_callchain(env, st, &callchain)) {
+ verifier_bug(env, "add backedge: no SCC in verification path, insn_idx %d",
+ st->insn_idx);
+ return -EFAULT;
+ }
+ visit = scc_visit_lookup(env, &callchain);
+ if (!visit) {
+ verifier_bug(env, "add backedge: no visit info for call chain %s",
+ format_callchain(env, &callchain));
+ return -EFAULT;
+ }
+ if (env->log.level & BPF_LOG_LEVEL2)
+ verbose(env, "SCC backedge %s\n", format_callchain(env, &callchain));
+ backedge->next = visit->backedges;
+ visit->backedges = backedge;
+ return 0;
+}
+
+/* bpf_reg_state->live marks for registers in a state @st are incomplete,
+ * if state @st is in some SCC and not all execution paths starting at this
+ * SCC are fully explored.
+ */
+static bool incomplete_read_marks(struct bpf_verifier_env *env,
+ struct bpf_verifier_state *st)
+{
+ struct bpf_scc_callchain callchain;
+ struct bpf_scc_visit *visit;
+
+ if (!compute_scc_callchain(env, st, &callchain))
+ return false;
+ visit = scc_visit_lookup(env, &callchain);
+ if (!visit)
+ return false;
+ return !!visit->backedges;
+}
+
+static void free_backedges(struct bpf_scc_visit *visit)
+{
+ struct bpf_scc_backedge *backedge, *next;
+
+ for (backedge = visit->backedges; backedge; backedge = next) {
+ free_verifier_state(&backedge->state, false);
+ next = backedge->next;
+ kvfree(backedge);
+ }
+ visit->backedges = NULL;
+}
+
+static int update_branch_counts(struct bpf_verifier_env *env, struct bpf_verifier_state *st)
{
struct bpf_verifier_state_list *sl = NULL, *parent_sl;
struct bpf_verifier_state *parent;
+ int err;
while (st) {
u32 br = --st->branches;
- /* br == 0 signals that DFS exploration for 'st' is finished,
- * thus it is necessary to update parent's loop entry if it
- * turned out that st is a part of some loop.
- * This is a part of 'case A' in get_loop_entry() comment.
- */
- if (br == 0 && st->parent && st->loop_entry)
- update_loop_entry(env, st->parent, st->loop_entry);
-
/* WARN_ON(br > 1) technically makes sense here,
* but see comment in push_stack(), hence:
*/
@@ -1995,6 +2189,9 @@ static void update_branch_counts(struct bpf_verifier_env *env, struct bpf_verifi
br);
if (br)
break;
+ err = maybe_exit_scc(env, st);
+ if (err)
+ return err;
parent = st->parent;
parent_sl = state_parent_as_list(st);
if (sl)
@@ -2002,6 +2199,7 @@ static void update_branch_counts(struct bpf_verifier_env *env, struct bpf_verifi
st = parent;
sl = parent_sl;
}
+ return 0;
}
static int pop_stack(struct bpf_verifier_env *env, int *prev_insn_idx,
@@ -16504,7 +16702,7 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
}
if (insn_flags) {
- err = push_insn_history(env, this_branch, insn_flags, 0);
+ err = push_jmp_history(env, this_branch, insn_flags, 0);
if (err)
return err;
}
@@ -18329,7 +18527,6 @@ static void clean_verifier_state(struct bpf_verifier_env *env,
static void clean_live_states(struct bpf_verifier_env *env, int insn,
struct bpf_verifier_state *cur)
{
- struct bpf_verifier_state *loop_entry;
struct bpf_verifier_state_list *sl;
struct list_head *pos, *head;
@@ -18338,15 +18535,14 @@ static void clean_live_states(struct bpf_verifier_env *env, int insn,
sl = container_of(pos, struct bpf_verifier_state_list, node);
if (sl->state.branches)
continue;
- loop_entry = get_loop_entry(env, &sl->state);
- if (!IS_ERR_OR_NULL(loop_entry) && loop_entry->branches)
- continue;
if (sl->state.insn_idx != insn ||
!same_callsites(&sl->state, cur))
continue;
if (sl->state.frame[0]->regs[0].live & REG_LIVE_DONE)
/* all regs in this state in all frames were already marked */
continue;
+ if (incomplete_read_marks(env, &sl->state))
+ continue;
clean_verifier_state(env, &sl->state);
}
}
@@ -18948,6 +19144,46 @@ static int propagate_precision(struct bpf_verifier_env *env,
return 0;
}
+#define MAX_BACKEDGE_ITERS 64
+
+/* Propagate read and precision marks from visit->backedges[*].state->equal_state
+ * to corresponding parent states of visit->backedges[*].state until fixed point is reached,
+ * then free visit->backedges.
+ * After execution of this function incomplete_read_marks() will return false
+ * for all states corresponding to @visit->callchain.
+ */
+static int propagate_backedges(struct bpf_verifier_env *env, struct bpf_scc_visit *visit)
+{
+ struct bpf_scc_backedge *backedge;
+ struct bpf_verifier_state *st;
+ bool changed;
+ int i, err;
+
+ i = 0;
+ do {
+ if (i++ > MAX_BACKEDGE_ITERS) {
+ if (env->log.level & BPF_LOG_LEVEL2)
+ verbose(env, "%s: too many iterations\n", __func__);
+ for (backedge = visit->backedges; backedge; backedge = backedge->next)
+ mark_all_scalars_precise(env, &backedge->state);
+ break;
+ }
+ changed = false;
+ for (backedge = visit->backedges; backedge; backedge = backedge->next) {
+ st = &backedge->state;
+ err = propagate_liveness(env, st->equal_state, st, &changed);
+ if (err)
+ return err;
+ err = propagate_precision(env, st->equal_state, st, &changed);
+ if (err)
+ return err;
+ }
+ } while (changed);
+
+ free_backedges(visit);
+ return 0;
+}
+
static bool states_maybe_looping(struct bpf_verifier_state *old,
struct bpf_verifier_state *cur)
{
@@ -19057,9 +19293,9 @@ static int 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, *loop_entry;
+ struct bpf_verifier_state *cur = env->cur_state, *new;
+ bool force_new_state, add_new_state, loop;
int i, j, n, err, states_cnt = 0;
- bool force_new_state, add_new_state, force_exact;
struct list_head *pos, *tmp, *head;
force_new_state = env->test_state_freq || is_force_checkpoint(env, insn_idx) ||
@@ -19081,6 +19317,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
clean_live_states(env, insn_idx, cur);
+ loop = false;
head = explored_state(env, insn_idx);
list_for_each_safe(pos, tmp, head) {
sl = container_of(pos, struct bpf_verifier_state_list, node);
@@ -19160,7 +19397,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
spi = __get_spi(iter_reg->off + iter_reg->var_off.value);
iter_state = &func(env, iter_reg)->stack[spi].spilled_ptr;
if (iter_state->iter.state == BPF_ITER_STATE_ACTIVE) {
- update_loop_entry(env, cur, &sl->state);
+ loop = true;
goto hit;
}
}
@@ -19169,7 +19406,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
if (is_may_goto_insn_at(env, insn_idx)) {
if (sl->state.may_goto_depth != cur->may_goto_depth &&
states_equal(env, &sl->state, cur, RANGE_WITHIN)) {
- update_loop_entry(env, cur, &sl->state);
+ loop = true;
goto hit;
}
}
@@ -19211,38 +19448,9 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
add_new_state = false;
goto miss;
}
- /* If sl->state is a part of a loop and this loop's entry is a part of
- * current verification path then states have to be compared exactly.
- * 'force_exact' is needed to catch the following case:
- *
- * initial Here state 'succ' was processed first,
- * | it was eventually tracked to produce a
- * V state identical to 'hdr'.
- * .---------> hdr All branches from 'succ' had been explored
- * | | and thus 'succ' has its .branches == 0.
- * | V
- * | .------... Suppose states 'cur' and 'succ' correspond
- * | | | to the same instruction + callsites.
- * | V V In such case it is necessary to check
- * | ... ... if 'succ' and 'cur' are states_equal().
- * | | | If 'succ' and 'cur' are a part of the
- * | V V same loop exact flag has to be set.
- * | succ <- cur To check if that is the case, verify
- * | | if loop entry of 'succ' is in current
- * | V DFS path.
- * | ...
- * | |
- * '----'
- *
- * Additional details are in the comment before get_loop_entry().
- */
- loop_entry = get_loop_entry(env, &sl->state);
- if (IS_ERR(loop_entry))
- return PTR_ERR(loop_entry);
- force_exact = loop_entry && loop_entry->branches > 0;
- if (states_equal(env, &sl->state, cur, force_exact ? RANGE_WITHIN : NOT_EXACT)) {
- if (force_exact)
- update_loop_entry(env, cur, loop_entry);
+ /* See comments for mark_all_regs_read_and_precise() */
+ loop = incomplete_read_marks(env, &sl->state);
+ if (states_equal(env, &sl->state, cur, loop ? RANGE_WITHIN : NOT_EXACT)) {
hit:
sl->hit_cnt++;
/* reached equivalent register/stack state,
@@ -19267,6 +19475,94 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
err = err ? : propagate_precision(env, &sl->state, cur, NULL);
if (err)
return err;
+ /* When processing iterator based loops above propagate_liveness and
+ * propagate_precision calls are not sufficient to transfer all relevant
+ * read and precision marks. E.g. consider the following case:
+ *
+ * .-> A --. Assume the states are visited in the order A, B, C.
+ * | | | Assume that state B reaches a state equivalent to state A.
+ * | v v At this point, state C is not processed yet, so state A
+ * '-- B C has not received any read or precision marks from C.
+ * Thus, marks propagated from A to B are incomplete.
+ *
+ * The verifier mitigates this by performing the following steps:
+ *
+ * - Prior to the main verification pass, strongly connected components
+ * (SCCs) are computed over the program's control flow graph,
+ * intraprocedurally.
+ *
+ * - During the main verification pass, `maybe_enter_scc()` checks
+ * whether the current verifier state is entering an SCC. If so, an
+ * instance of a `bpf_scc_visit` object is created, and the state
+ * entering the SCC is recorded as the entry state.
+ *
+ * - This instance is associated not with the SCC itself, but with a
+ * `bpf_scc_callchain`: a tuple consisting of the call sites leading to
+ * the SCC and the SCC id. See `compute_scc_callchain()`.
+ *
+ * - When a verification path encounters a `states_equal(...,
+ * RANGE_WITHIN)` condition, there exists a call chain describing the
+ * current state and a corresponding `bpf_scc_visit` instance. A copy
+ * of the current state is created and added to
+ * `bpf_scc_visit->backedges`.
+ *
+ * - When a verification path terminates, `maybe_exit_scc()` is called
+ * from `update_branch_counts()`. For states with `branches == 0`, it
+ * checks whether the state is the entry state of any `bpf_scc_visit`
+ * instance. If it is, this indicates that all paths originating from
+ * this SCC visit have been explored. `propagate_backedges()` is then
+ * called, which propagates read and precision marks through the
+ * backedges until a fixed point is reached.
+ * (In the earlier example, this would propagate marks from A to B,
+ * from C to A, and then again from A to B.)
+ *
+ * A note on callchains
+ * --------------------
+ *
+ * Consider the following example:
+ *
+ * void foo() { loop { ... SCC#1 ... } }
+ * void main() {
+ * A: foo();
+ * B: ...
+ * C: foo();
+ * }
+ *
+ * Here, there are two distinct callchains leading to SCC#1:
+ * - (A, SCC#1)
+ * - (C, SCC#1)
+ *
+ * Each callchain identifies a separate `bpf_scc_visit` instance that
+ * accumulates backedge states. The `propagate_{liveness,precision}()`
+ * functions traverse the parent state of each backedge state, which
+ * means these parent states must remain valid (i.e., not freed) while
+ * the corresponding `bpf_scc_visit` instance exists.
+ *
+ * Associating `bpf_scc_visit` instances directly with SCCs instead of
+ * callchains would break this invariant:
+ * - States explored during `C: foo()` would contribute backedges to
+ * SCC#1, but SCC#1 would only be exited once the exploration of
+ * `A: foo()` completes.
+ * - By that time, the states explored between `A: foo()` and `C: foo()`
+ * (i.e., `B: ...`) may have already been freed, causing the parent
+ * links for states from `C: foo()` to become invalid.
+ */
+ if (loop) {
+ struct bpf_scc_backedge *backedge;
+
+ backedge = kzalloc(sizeof(*backedge), GFP_KERNEL);
+ if (!backedge)
+ return -ENOMEM;
+ err = copy_verifier_state(&backedge->state, cur);
+ backedge->state.equal_state = &sl->state;
+ backedge->state.insn_idx = insn_idx;
+ err = err ?: add_scc_backedge(env, &sl->state, backedge);
+ if (err) {
+ free_verifier_state(&backedge->state, false);
+ kvfree(backedge);
+ return err;
+ }
+ }
return 1;
}
miss:
@@ -19342,6 +19638,12 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
new->insn_idx = insn_idx;
WARN_ONCE(new->branches != 1,
"BUG is_state_visited:branches_to_explore=%d insn %d\n", new->branches, insn_idx);
+ err = maybe_enter_scc(env, new);
+ if (err) {
+ free_verifier_state(new, false);
+ kvfree(new_sl);
+ return err;
+ }
cur->parent = new;
cur->first_insn_idx = insn_idx;
@@ -19719,7 +20021,9 @@ static int do_check(struct bpf_verifier_env *env)
return err;
process_bpf_exit:
mark_verifier_state_scratched(env);
- update_branch_counts(env, env->cur_state);
+ err = update_branch_counts(env, env->cur_state);
+ if (err)
+ return err;
err = pop_stack(env, &prev_insn_idx,
&env->insn_idx, pop_log);
if (err < 0) {
@@ -19727,9 +20031,6 @@ static int do_check(struct bpf_verifier_env *env)
return err;
break;
} else {
- if (verifier_bug_if(env->cur_state->loop_entry, env,
- "broken loop detection"))
- return -EFAULT;
do_print_state = true;
continue;
}
@@ -22698,7 +22999,8 @@ static void free_states(struct bpf_verifier_env *env)
{
struct bpf_verifier_state_list *sl;
struct list_head *head, *pos, *tmp;
- int i;
+ struct bpf_scc_info *info;
+ int i, j;
list_for_each_safe(pos, tmp, &env->free_list) {
sl = container_of(pos, struct bpf_verifier_state_list, node);
@@ -22707,6 +23009,14 @@ static void free_states(struct bpf_verifier_env *env)
}
INIT_LIST_HEAD(&env->free_list);
+ for (i = 0; i < env->scc_cnt; ++i) {
+ info = env->scc_info[i];
+ for (j = 0; j < info->num_visits; j++)
+ free_backedges(&info->visits[j]);
+ kvfree(info);
+ env->scc_info[i] = NULL;
+ }
+
if (!env->explored_states)
return;
@@ -24139,6 +24449,11 @@ static int compute_scc(struct bpf_verifier_env *env)
dfs_sz--;
}
}
+ env->scc_info = kvcalloc(next_scc_id, sizeof(*env->scc_info), GFP_KERNEL);
+ if (!env->scc_info) {
+ err = -ENOMEM;
+ goto exit;
+ }
exit:
kvfree(stack);
kvfree(pre);
@@ -24414,6 +24729,7 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3
vfree(env->insn_aux_data);
err_free_env:
kvfree(env->cfg.insn_postorder);
+ kvfree(env->scc_info);
kvfree(env);
return ret;
}
--
2.48.1
^ permalink raw reply related [flat|nested] 12+ messages in thread
* [PATCH bpf-next v2 09/11] bpf: remove {update,get}_loop_entry functions
2025-06-06 21:03 [PATCH bpf-next v2 00/11] bpf: propagate read/precision marks over state graph backedges Eduard Zingerman
` (7 preceding siblings ...)
2025-06-06 21:03 ` [PATCH bpf-next v2 08/11] bpf: propagate read/precision marks over state graph backedges Eduard Zingerman
@ 2025-06-06 21:03 ` Eduard Zingerman
2025-06-06 21:03 ` [PATCH bpf-next v2 10/11] bpf: include backedges in peak_states stat Eduard Zingerman
2025-06-06 21:03 ` [PATCH bpf-next v2 11/11] selftests/bpf: tests with a loop state missing read/precision mark Eduard Zingerman
10 siblings, 0 replies; 12+ messages in thread
From: Eduard Zingerman @ 2025-06-06 21:03 UTC (permalink / raw)
To: bpf, ast
Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song,
Eduard Zingerman
The previous patch switched read and precision tracking for
iterator-based loops from state-graph-based loop tracking to
control-flow-graph-based loop tracking.
This patch removes the now-unused `update_loop_entry()` and
`get_loop_entry()` functions, which were part of the state-graph-based
logic.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
include/linux/bpf_verifier.h | 15 ----
kernel/bpf/verifier.c | 165 +----------------------------------
2 files changed, 1 insertion(+), 179 deletions(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 5190d71bd8fb..06848291ed21 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -449,16 +449,6 @@ struct bpf_verifier_state {
/* first and last insn idx of this verifier state */
u32 first_insn_idx;
u32 last_insn_idx;
- /* If this state is a part of states loop this field points to some
- * parent of this state such that:
- * - it is also a member of the same states loop;
- * - DFS states traversal starting from initial state visits loop_entry
- * state before this state.
- * Used to compute topmost loop entry for state loops.
- * State loops might appear because of open coded iterators logic.
- * See get_loop_entry() for more information.
- */
- struct bpf_verifier_state *loop_entry;
/* if this state is a backedge state then equal_state
* records cached state to which this state is equal.
*/
@@ -473,11 +463,6 @@ struct bpf_verifier_state {
u32 dfs_depth;
u32 callback_unroll_depth;
u32 may_goto_depth;
- /* If this state was ever pointed-to by other state's loop_entry field
- * this flag would be set to true. Used to avoid freeing such states
- * while they are still in use.
- */
- u32 used_as_loop_entry;
};
#define bpf_get_spilled_reg(slot, frame, mask) \
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 9a5af34f5917..6cf3a9654e91 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1681,7 +1681,7 @@ static void free_verifier_state(struct bpf_verifier_state *state,
kfree(state);
}
-/* struct bpf_verifier_state->{parent,loop_entry} refer to states
+/* struct bpf_verifier_state->parent refers to states
* that are in either of env->{expored_states,free_list}.
* In both cases the state is contained in struct bpf_verifier_state_list.
*/
@@ -1692,22 +1692,12 @@ static struct bpf_verifier_state_list *state_parent_as_list(struct bpf_verifier_
return NULL;
}
-static struct bpf_verifier_state_list *state_loop_entry_as_list(struct bpf_verifier_state *st)
-{
- if (st->loop_entry)
- return container_of(st->loop_entry, struct bpf_verifier_state_list, state);
- return NULL;
-}
-
static bool incomplete_read_marks(struct bpf_verifier_env *env,
struct bpf_verifier_state *st);
/* A state can be freed if it is no longer referenced:
* - is in the env->free_list;
* - has no children states;
- * - is not used as loop_entry.
- *
- * Freeing a state can make it's loop_entry free-able.
*/
static void maybe_free_verifier_state(struct bpf_verifier_env *env,
struct bpf_verifier_state_list *sl)
@@ -1764,9 +1754,7 @@ static int copy_verifier_state(struct bpf_verifier_state *dst_state,
dst_state->last_insn_idx = src->last_insn_idx;
dst_state->dfs_depth = src->dfs_depth;
dst_state->callback_unroll_depth = src->callback_unroll_depth;
- dst_state->used_as_loop_entry = src->used_as_loop_entry;
dst_state->may_goto_depth = src->may_goto_depth;
- dst_state->loop_entry = src->loop_entry;
dst_state->equal_state = src->equal_state;
for (i = 0; i <= src->curframe; i++) {
dst = dst_state->frame[i];
@@ -1810,157 +1798,6 @@ static bool same_callsites(struct bpf_verifier_state *a, struct bpf_verifier_sta
return true;
}
-/* Open coded iterators allow back-edges in the state graph in order to
- * check unbounded loops that iterators.
- *
- * In is_state_visited() it is necessary to know if explored states are
- * part of some loops in order to decide whether non-exact states
- * comparison could be used:
- * - non-exact states comparison establishes sub-state relation and uses
- * read and precision marks to do so, these marks are propagated from
- * children states and thus are not guaranteed to be final in a loop;
- * - exact states comparison just checks if current and explored states
- * are identical (and thus form a back-edge).
- *
- * Paper "A New Algorithm for Identifying Loops in Decompilation"
- * by Tao Wei, Jian Mao, Wei Zou and Yu Chen [1] presents a convenient
- * algorithm for loop structure detection and gives an overview of
- * relevant terminology. It also has helpful illustrations.
- *
- * [1] https://api.semanticscholar.org/CorpusID:15784067
- *
- * We use a similar algorithm but because loop nested structure is
- * irrelevant for verifier ours is significantly simpler and resembles
- * strongly connected components algorithm from Sedgewick's textbook.
- *
- * Define topmost loop entry as a first node of the loop traversed in a
- * depth first search starting from initial state. The goal of the loop
- * tracking algorithm is to associate topmost loop entries with states
- * derived from these entries.
- *
- * For each step in the DFS states traversal algorithm needs to identify
- * the following situations:
- *
- * initial initial initial
- * | | |
- * V V V
- * ... ... .---------> hdr
- * | | | |
- * V V | V
- * cur .-> succ | .------...
- * | | | | | |
- * V | V | V V
- * succ '-- cur | ... ...
- * | | |
- * | V V
- * | succ <- cur
- * | |
- * | V
- * | ...
- * | |
- * '----'
- *
- * (A) successor state of cur (B) successor state of cur or it's entry
- * not yet traversed are in current DFS path, thus cur and succ
- * are members of the same outermost loop
- *
- * initial initial
- * | |
- * V V
- * ... ...
- * | |
- * V V
- * .------... .------...
- * | | | |
- * V V V V
- * .-> hdr ... ... ...
- * | | | | |
- * | V V V V
- * | succ <- cur succ <- cur
- * | | |
- * | V V
- * | ... ...
- * | | |
- * '----' exit
- *
- * (C) successor state of cur is a part of some loop but this loop
- * does not include cur or successor state is not in a loop at all.
- *
- * Algorithm could be described as the following python code:
- *
- * traversed = set() # Set of traversed nodes
- * entries = {} # Mapping from node to loop entry
- * depths = {} # Depth level assigned to graph node
- * path = set() # Current DFS path
- *
- * # Find outermost loop entry known for n
- * def get_loop_entry(n):
- * h = entries.get(n, None)
- * while h in entries:
- * h = entries[h]
- * return h
- *
- * # Update n's loop entry if h comes before n in current DFS path.
- * def update_loop_entry(n, h):
- * if h in path and depths[entries.get(n, n)] < depths[n]:
- * entries[n] = h1
- *
- * def dfs(n, depth):
- * traversed.add(n)
- * path.add(n)
- * depths[n] = depth
- * for succ in G.successors(n):
- * if succ not in traversed:
- * # Case A: explore succ and update cur's loop entry
- * # only if succ's entry is in current DFS path.
- * dfs(succ, depth + 1)
- * h = entries.get(succ, None)
- * update_loop_entry(n, h)
- * else:
- * # Case B or C depending on `h1 in path` check in update_loop_entry().
- * update_loop_entry(n, succ)
- * path.remove(n)
- *
- * To adapt this algorithm for use with verifier:
- * - use st->branch == 0 as a signal that DFS of succ had been finished
- * and cur's loop entry has to be updated (case A), handle this in
- * update_branch_counts();
- * - use st->branch > 0 as a signal that st is in the current DFS path;
- * - handle cases B and C in is_state_visited().
- */
-static struct bpf_verifier_state *get_loop_entry(struct bpf_verifier_env *env,
- struct bpf_verifier_state *st)
-{
- struct bpf_verifier_state *topmost = st->loop_entry;
- u32 steps = 0;
-
- while (topmost && topmost->loop_entry) {
- if (verifier_bug_if(steps++ > st->dfs_depth, env, "infinite loop"))
- return ERR_PTR(-EFAULT);
- topmost = topmost->loop_entry;
- }
- return topmost;
-}
-
-static void update_loop_entry(struct bpf_verifier_env *env,
- struct bpf_verifier_state *cur, struct bpf_verifier_state *hdr)
-{
- /* The hdr->branches check decides between cases B and C in
- * comment for get_loop_entry(). If hdr->branches == 0 then
- * head's topmost loop entry is not in current DFS path,
- * hence 'cur' and 'hdr' are not in the same loop and there is
- * no need to update cur->loop_entry.
- */
- if (hdr->branches && hdr->dfs_depth < (cur->loop_entry ?: cur)->dfs_depth) {
- if (cur->loop_entry) {
- cur->loop_entry->used_as_loop_entry--;
- maybe_free_verifier_state(env, state_loop_entry_as_list(cur));
- }
- cur->loop_entry = hdr;
- hdr->used_as_loop_entry++;
- }
-}
-
/* Return IP for a given frame in a call stack */
static u32 frame_insn_idx(struct bpf_verifier_state *st, u32 frame)
{
--
2.48.1
^ permalink raw reply related [flat|nested] 12+ messages in thread
* [PATCH bpf-next v2 10/11] bpf: include backedges in peak_states stat
2025-06-06 21:03 [PATCH bpf-next v2 00/11] bpf: propagate read/precision marks over state graph backedges Eduard Zingerman
` (8 preceding siblings ...)
2025-06-06 21:03 ` [PATCH bpf-next v2 09/11] bpf: remove {update,get}_loop_entry functions Eduard Zingerman
@ 2025-06-06 21:03 ` Eduard Zingerman
2025-06-06 21:03 ` [PATCH bpf-next v2 11/11] selftests/bpf: tests with a loop state missing read/precision mark Eduard Zingerman
10 siblings, 0 replies; 12+ messages in thread
From: Eduard Zingerman @ 2025-06-06 21:03 UTC (permalink / raw)
To: bpf, ast
Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song,
Eduard Zingerman
Count states accumulated in bpf_scc_visit->backedges in
env->peak_states.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
include/linux/bpf_verifier.h | 2 ++
kernel/bpf/verifier.c | 8 +++++++-
2 files changed, 9 insertions(+), 1 deletion(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 06848291ed21..47444983b353 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -732,6 +732,7 @@ struct bpf_scc_visit {
*/
struct bpf_verifier_state *entry_state;
struct bpf_scc_backedge *backedges; /* list of backedges */
+ u32 num_backedges;
};
/* An array of bpf_scc_visit structs sharing tht same bpf_scc_callchain->scc
@@ -821,6 +822,7 @@ struct bpf_verifier_env {
u32 longest_mark_read_walk;
u32 free_list_size;
u32 explored_states_size;
+ u32 num_backedges;
bpfptr_t fd_array;
/* bit mask to keep track of whether a register has been accessed
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 6cf3a9654e91..54b06f342caf 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1647,7 +1647,7 @@ static void update_peak_states(struct bpf_verifier_env *env)
{
u32 cur_states;
- cur_states = env->explored_states_size + env->free_list_size;
+ cur_states = env->explored_states_size + env->free_list_size + env->num_backedges;
env->peak_states = max(env->peak_states, cur_states);
}
@@ -1948,6 +1948,9 @@ static int maybe_exit_scc(struct bpf_verifier_env *env, struct bpf_verifier_stat
if (env->log.level & BPF_LOG_LEVEL2)
verbose(env, "SCC exit %s\n", format_callchain(env, &callchain));
visit->entry_state = NULL;
+ env->num_backedges -= visit->num_backedges;
+ visit->num_backedges = 0;
+ update_peak_states(env);
return propagate_backedges(env, visit);
}
@@ -1976,6 +1979,9 @@ static int add_scc_backedge(struct bpf_verifier_env *env,
verbose(env, "SCC backedge %s\n", format_callchain(env, &callchain));
backedge->next = visit->backedges;
visit->backedges = backedge;
+ visit->num_backedges++;
+ env->num_backedges++;
+ update_peak_states(env);
return 0;
}
--
2.48.1
^ permalink raw reply related [flat|nested] 12+ messages in thread
* [PATCH bpf-next v2 11/11] selftests/bpf: tests with a loop state missing read/precision mark
2025-06-06 21:03 [PATCH bpf-next v2 00/11] bpf: propagate read/precision marks over state graph backedges Eduard Zingerman
` (9 preceding siblings ...)
2025-06-06 21:03 ` [PATCH bpf-next v2 10/11] bpf: include backedges in peak_states stat Eduard Zingerman
@ 2025-06-06 21:03 ` Eduard Zingerman
10 siblings, 0 replies; 12+ messages in thread
From: Eduard Zingerman @ 2025-06-06 21:03 UTC (permalink / raw)
To: bpf, ast
Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song,
Eduard Zingerman
The test case absent_mark_in_the_middle_state is equivalent of the
following C program:
1: r8 = bpf_get_prandom_u32();
2: r6 = -32;
3: bpf_iter_num_new(&fp[-8], 0, 10);
4: if (unlikely(bpf_get_prandom_u32() == r8))
5: r6 = -31;
6: for (;;) {
7: if (!bpf_iter_num_next(&fp[-8]))
8: break;
9: if (unlikely(bpf_get_prandom_u32() == r8))
10: *(u64 *)(fp + r6) = 7;
11: }
12: bpf_iter_num_destroy(&fp[-8]);
13: return 0;
W/o a fix that instructs verifier to ignore branches count for loop
entries verification proceeds as follows:
- 1-4, state is {r6=-32,fp-8=active};
- 6, checkpoint A is created with {r6=-32,fp-8=active};
- 7, checkpoint B is created with {r6=-32,fp-8=active},
push state {r6=-32,fp-8=active} from 7 to 9;
- 8,12,13, {r6=-32,fp-8=drained}, exit;
- pop state with {r6=-32,fp-8=active} from 7 to 9;
- 9, push state {r6=-32,fp-8=active} from 9 to 10;
- 6, checkpoint C is created with {r6=-32,fp-8=active};
- 7, checkpoint A is hit, no precision propagated for r6 to C;
- pop state {r6=-32,fp-8=active} from 9 to 10;
- 10, state is {r6=-31,fp-8=active}, r6 is marked as read and precise,
these marks are propagated to checkpoints A and B (but not C, as
it is not the parent of current state;
- 6, {r6=-31,fp-8=active} checkpoint C is hit, because r6 is not
marked precise for this checkpoint;
- the program is accepted, despite a possibility of unaligned u64
stack access at offset -31.
The test case absent_mark_in_the_middle_state2 is similar except the
following change:
r8 = bpf_get_prandom_u32();
r6 = -32;
bpf_iter_num_new(&fp[-8], 0, 10);
if (unlikely(bpf_get_prandom_u32() == r8)) {
r6 = -31;
+ jump_into_loop:
+ goto +0;
+ goto loop;
+ }
+ if (unlikely(bpf_get_prandom_u32() == r8))
+ goto jump_into_loop;
+ loop:
for (;;) {
if (!bpf_iter_num_next(&fp[-8]))
break;
if (unlikely(bpf_get_prandom_u32() == r8))
*(u64 *)(fp + r6) = 7;
}
bpf_iter_num_destroy(&fp[-8])
return 0
The goal is to check that read/precision marks are propagated to
checkpoint created at 'goto +0' that resides outside of the loop.
The test case absent_mark_in_the_middle_state3 is a bit different and
is equivalent to the C program below:
int absent_mark_in_the_middle_state3(void)
{
bpf_iter_num_new(&fp[-8], 0, 10)
loop1(-32, &fp[-8])
loop1_wrapper(&fp[-8])
bpf_iter_num_destroy(&fp[-8])
}
int loop1(num, iter)
{
while (bpf_iter_num_next(iter)) {
if (unlikely(bpf_get_prandom_u32()))
*(fp + num) = 7;
}
return 0
}
int loop1_wrapper(iter)
{
r6 = -32;
r8 = bpf_get_prandom_u32();
if (unlikely(bpf_get_prandom_u32() == r8))
r6 = -31;
loop1(r6, iter);
return 0;
}
The unsafe state is reached in a similar manner, but the loop is
located inside a subprogram that is called from two locations in the
main subprogram. This detail is important for exercising
bpf_scc_visit->backedges memory management.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
tools/testing/selftests/bpf/progs/iters.c | 277 ++++++++++++++++++++++
1 file changed, 277 insertions(+)
diff --git a/tools/testing/selftests/bpf/progs/iters.c b/tools/testing/selftests/bpf/progs/iters.c
index 76adf4a8f2da..649b239585e5 100644
--- a/tools/testing/selftests/bpf/progs/iters.c
+++ b/tools/testing/selftests/bpf/progs/iters.c
@@ -1649,4 +1649,281 @@ int clean_live_states(const void *ctx)
return 0;
}
+SEC("?raw_tp")
+__flag(BPF_F_TEST_STATE_FREQ)
+__failure __msg("misaligned stack access off 0+-31+0 size 8")
+__naked int absent_mark_in_the_middle_state(void)
+{
+ /* This is equivalent to C program below.
+ *
+ * r8 = bpf_get_prandom_u32();
+ * r6 = -32;
+ * bpf_iter_num_new(&fp[-8], 0, 10);
+ * if (unlikely(bpf_get_prandom_u32() == r8))
+ * r6 = -31;
+ * while (bpf_iter_num_next(&fp[-8])) {
+ * if (unlikely(bpf_get_prandom_u32() == r8))
+ * *(fp + r6) = 7;
+ * }
+ * bpf_iter_num_destroy(&fp[-8])
+ * return 0
+ */
+ asm volatile (
+ "call %[bpf_get_prandom_u32];"
+ "r8 = r0;"
+ "r6 = -32;"
+ "r0 = 0;"
+ "*(u64 *)(r10 - 16) = r0;"
+ "r1 = r10;"
+ "r1 += -8;"
+ "r2 = 0;"
+ "r3 = 10;"
+ "call %[bpf_iter_num_new];"
+ "call %[bpf_get_prandom_u32];"
+ "if r0 == r8 goto change_r6_%=;"
+ "loop_%=:"
+ "call noop;"
+ "r1 = r10;"
+ "r1 += -8;"
+ "call %[bpf_iter_num_next];"
+ "if r0 == 0 goto loop_end_%=;"
+ "call %[bpf_get_prandom_u32];"
+ "if r0 == r8 goto use_r6_%=;"
+ "goto loop_%=;"
+ "loop_end_%=:"
+ "r1 = r10;"
+ "r1 += -8;"
+ "call %[bpf_iter_num_destroy];"
+ "r0 = 0;"
+ "exit;"
+ "use_r6_%=:"
+ "r0 = r10;"
+ "r0 += r6;"
+ "r1 = 7;"
+ "*(u64 *)(r0 + 0) = r1;"
+ "goto loop_%=;"
+ "change_r6_%=:"
+ "r6 = -31;"
+ "goto loop_%=;"
+ :
+ : __imm(bpf_iter_num_new),
+ __imm(bpf_iter_num_next),
+ __imm(bpf_iter_num_destroy),
+ __imm(bpf_get_prandom_u32)
+ : __clobber_all
+ );
+}
+
+__used __naked
+static int noop(void)
+{
+ asm volatile (
+ "r0 = 0;"
+ "exit;"
+ );
+}
+
+SEC("?raw_tp")
+__flag(BPF_F_TEST_STATE_FREQ)
+__failure __msg("misaligned stack access off 0+-31+0 size 8")
+__naked int absent_mark_in_the_middle_state2(void)
+{
+ /* This is equivalent to C program below.
+ *
+ * r8 = bpf_get_prandom_u32();
+ * r6 = -32;
+ * bpf_iter_num_new(&fp[-8], 0, 10);
+ * if (unlikely(bpf_get_prandom_u32() == r8)) {
+ * r6 = -31;
+ * jump_into_loop:
+ * goto +0;
+ * goto loop;
+ * }
+ * if (unlikely(bpf_get_prandom_u32() == r8))
+ * goto jump_into_loop;
+ * loop:
+ * while (bpf_iter_num_next(&fp[-8])) {
+ * if (unlikely(bpf_get_prandom_u32() == r8))
+ * *(fp + r6) = 7;
+ * }
+ * bpf_iter_num_destroy(&fp[-8])
+ * return 0
+ */
+ asm volatile (
+ "call %[bpf_get_prandom_u32];"
+ "r8 = r0;"
+ "r6 = -32;"
+ "r0 = 0;"
+ "*(u64 *)(r10 - 16) = r0;"
+ "r1 = r10;"
+ "r1 += -8;"
+ "r2 = 0;"
+ "r3 = 10;"
+ "call %[bpf_iter_num_new];"
+ "call %[bpf_get_prandom_u32];"
+ "if r0 == r8 goto change_r6_%=;"
+ "call %[bpf_get_prandom_u32];"
+ "if r0 == r8 goto jump_into_loop_%=;"
+ "loop_%=:"
+ "r1 = r10;"
+ "r1 += -8;"
+ "call %[bpf_iter_num_next];"
+ "if r0 == 0 goto loop_end_%=;"
+ "call %[bpf_get_prandom_u32];"
+ "if r0 == r8 goto use_r6_%=;"
+ "goto loop_%=;"
+ "loop_end_%=:"
+ "r1 = r10;"
+ "r1 += -8;"
+ "call %[bpf_iter_num_destroy];"
+ "r0 = 0;"
+ "exit;"
+ "use_r6_%=:"
+ "r0 = r10;"
+ "r0 += r6;"
+ "r1 = 7;"
+ "*(u64 *)(r0 + 0) = r1;"
+ "goto loop_%=;"
+ "change_r6_%=:"
+ "r6 = -31;"
+ "jump_into_loop_%=: "
+ "goto +0;"
+ "goto loop_%=;"
+ :
+ : __imm(bpf_iter_num_new),
+ __imm(bpf_iter_num_next),
+ __imm(bpf_iter_num_destroy),
+ __imm(bpf_get_prandom_u32)
+ : __clobber_all
+ );
+}
+
+SEC("?raw_tp")
+__flag(BPF_F_TEST_STATE_FREQ)
+__failure __msg("misaligned stack access off 0+-31+0 size 8")
+__naked int absent_mark_in_the_middle_state3(void)
+{
+ /*
+ * bpf_iter_num_new(&fp[-8], 0, 10)
+ * loop1(-32, &fp[-8])
+ * loop1_wrapper(&fp[-8])
+ * bpf_iter_num_destroy(&fp[-8])
+ */
+ asm volatile (
+ "r1 = r10;"
+ "r1 += -8;"
+ "r2 = 0;"
+ "r3 = 10;"
+ "call %[bpf_iter_num_new];"
+ /* call #1 */
+ "r1 = -32;"
+ "r2 = r10;"
+ "r2 += -8;"
+ "call loop1;"
+ "r1 = r10;"
+ "r1 += -8;"
+ "call %[bpf_iter_num_destroy];"
+ /* call #2 */
+ "r1 = r10;"
+ "r1 += -8;"
+ "r2 = 0;"
+ "r3 = 10;"
+ "call %[bpf_iter_num_new];"
+ "r1 = r10;"
+ "r1 += -8;"
+ "call loop1_wrapper;"
+ /* return */
+ "r1 = r10;"
+ "r1 += -8;"
+ "call %[bpf_iter_num_destroy];"
+ "r0 = 0;"
+ "exit;"
+ :
+ : __imm(bpf_iter_num_new),
+ __imm(bpf_iter_num_destroy),
+ __imm(bpf_get_prandom_u32)
+ : __clobber_all
+ );
+}
+
+__used __naked
+static int loop1(void)
+{
+ /*
+ * int loop1(num, iter) {
+ * r8 = bpf_get_prandom_u32();
+ * r6 = num;
+ * r7 = iter;
+ * while (bpf_iter_num_next(r7)) {
+ * if (unlikely(bpf_get_prandom_u32() == r8))
+ * *(fp + r6) = 7;
+ * }
+ * return 0
+ * }
+ */
+ asm volatile (
+ "r6 = r1;"
+ "r7 = r2;"
+ "call %[bpf_get_prandom_u32];"
+ "r8 = r0;"
+ "loop_%=:"
+ "r1 = r7;"
+ "call %[bpf_iter_num_next];"
+ "if r0 == 0 goto loop_end_%=;"
+ "call %[bpf_get_prandom_u32];"
+ "if r0 == r8 goto use_r6_%=;"
+ "goto loop_%=;"
+ "loop_end_%=:"
+ "r0 = 0;"
+ "exit;"
+ "use_r6_%=:"
+ "r0 = r10;"
+ "r0 += r6;"
+ "r1 = 7;"
+ "*(u64 *)(r0 + 0) = r1;"
+ "goto loop_%=;"
+ :
+ : __imm(bpf_iter_num_next),
+ __imm(bpf_get_prandom_u32)
+ : __clobber_all
+ );
+}
+
+__used __naked
+static int loop1_wrapper(void)
+{
+ /*
+ * int loop1_wrapper(iter) {
+ * r6 = -32;
+ * r7 = iter;
+ * r8 = bpf_get_prandom_u32();
+ * if (unlikely(bpf_get_prandom_u32() == r8))
+ * r6 = -31;
+ * loop1(r6, r7);
+ * return 0;
+ * }
+ */
+ asm volatile (
+ "r6 = -32;"
+ "r7 = r1;"
+ "call %[bpf_get_prandom_u32];"
+ "r8 = r0;"
+ "call %[bpf_get_prandom_u32];"
+ "if r0 == r8 goto change_r6_%=;"
+ "loop_%=:"
+ "r1 = r6;"
+ "r2 = r7;"
+ "call loop1;"
+ "r0 = 0;"
+ "exit;"
+ "change_r6_%=:"
+ "r6 = -31;"
+ "goto loop_%=;"
+ :
+ : __imm(bpf_iter_num_next),
+ __imm(bpf_get_prandom_u32)
+ : __clobber_all
+ );
+}
+
char _license[] SEC("license") = "GPL";
--
2.48.1
^ permalink raw reply related [flat|nested] 12+ messages in thread
end of thread, other threads:[~2025-06-06 21:04 UTC | newest]
Thread overview: 12+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2025-06-06 21:03 [PATCH bpf-next v2 00/11] bpf: propagate read/precision marks over state graph backedges Eduard Zingerman
2025-06-06 21:03 ` [PATCH bpf-next v2 01/11] Revert "bpf: use common instruction history across all states" Eduard Zingerman
2025-06-06 21:03 ` [PATCH bpf-next v2 02/11] bpf: compute SCCs in program control flow graph Eduard Zingerman
2025-06-06 21:03 ` [PATCH bpf-next v2 03/11] bpf: frame_insn_idx() utility function Eduard Zingerman
2025-06-06 21:03 ` [PATCH bpf-next v2 04/11] bpf: starting_state parameter for __mark_chain_precision() Eduard Zingerman
2025-06-06 21:03 ` [PATCH bpf-next v2 05/11] bpf: set 'changed' status if propagate_precision() did any updates Eduard Zingerman
2025-06-06 21:03 ` [PATCH bpf-next v2 06/11] bpf: set 'changed' status if propagate_liveness() " Eduard Zingerman
2025-06-06 21:03 ` [PATCH bpf-next v2 07/11] bpf: move REG_LIVE_DONE check to clean_live_states() Eduard Zingerman
2025-06-06 21:03 ` [PATCH bpf-next v2 08/11] bpf: propagate read/precision marks over state graph backedges Eduard Zingerman
2025-06-06 21:03 ` [PATCH bpf-next v2 09/11] bpf: remove {update,get}_loop_entry functions Eduard Zingerman
2025-06-06 21:03 ` [PATCH bpf-next v2 10/11] bpf: include backedges in peak_states stat Eduard Zingerman
2025-06-06 21:03 ` [PATCH bpf-next v2 11/11] selftests/bpf: tests with a loop state missing read/precision mark Eduard Zingerman
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox