Skip to contentSkip to conversation

bpf: improvements for iterator-based loops convergence

RFC In review Eduard Zingerman 1 participant 9 messages Jan 22, 2025

Subsystems (4)
lore
Share & tools
lore

Eduard Zingerman

author maintainer
#0 lore raw

cover bpf: improvements for iterator-based loops convergence

This RFC consists of a bug fix and two improvements for iterator/callback based loops handling:
- Patch #1 fixes a bug in copy_verifier_state(), where field 'loop_entry' was not copied. The fix has negative impact on verification performance.
- Patch #3 mitigates negative impact from patch #1 by avoiding clean_live_states() for states that have loop_entry that is still being verified. This reduces amount of processed instructions for sched_ext by 28-92% for some programs.
- Patches #5,6 introduce a simple live registers DFA analysis. Results of this analysis are used in func_states_equal() and further reduce amount of processed instructions for sched_ext by 17-30% for some programs.

Below are veristat results comparing master to this RFC.

selftests:

File                   Program                     Insns      (DIFF)  States    (DIFF)
---------------------  --------------------------  -----------------  ----------------
arena_htab.bpf.o       arena_htab_llvm                -294 (-41.00%)     -20 (-35.09%)
arena_htab_asm.bpf.o   arena_htab_asm                 -152 (-25.46%)     -10 (-21.28%)
arena_list.bpf.o       arena_list_add                 +329 (+22.04%)      +7 (+23.33%)
arena_list.bpf.o       arena_list_del                 -161 (-52.10%)     -12 (-52.17%)
iters.bpf.o            checkpoint_states_deletion   -16914 (-93.32%)    -778 (-95.11%)
iters.bpf.o            iter_nested_deeply_iters       -293 (-49.41%)     -30 (-44.78%)
iters.bpf.o            iter_nested_iters              -181 (-22.26%)     -17 (-21.52%)
iters.bpf.o            iter_subprog_iters             -430 (-39.31%)     -29 (-32.95%)
iters.bpf.o            loop_state_deps2               -158 (-32.99%)     -14 (-30.43%)
pyperf600_iter.bpf.o   on_event                      -8633 (-69.97%)    -189 (-42.86%)

sched_ext:

Program                 Insns      (DIFF)  States    (DIFF)
----------------------  -----------------  ----------------
lavd_dispatch            -34018 (-22.00%)   -1885 (-21.06%)
layered_dispatch          -5378 (-46.81%)    -313 (-36.91%)
layered_dump              -3689 (-49.71%)    -455 (-66.81%)
layered_enqueue           -4038 (-30.90%)    -351 (-29.80%)
layered_init            -995483 (-99.55%)  -84233 (-99.48%)
layered_runnable          -1587 (-49.32%)    -172 (-58.31%)
refresh_layer_cpumasks   -15597 (-94.60%)   -1684 (-95.14%)
rustland_init               -85 (-17.07%)      -7 (-17.07%)
rustland_init               -85 (-17.07%)      -7 (-17.07%)
rusty_select_cpu           -706 (-33.65%)     -55 (-30.39%)
rusty_set_cpumask        -15934 (-78.67%)   -1359 (-81.62%)
tp_cgroup_attach_task       -57 (-27.67%)      -4 (-22.22%)
central_dispatch            -87 (-13.68%)      -9 (-14.29%)

central_init -476 (-52.19%) -12 (-25.00%)
pair_dispatch -998423 (-99.84%) -58264 (-99.78%)
qmap_dispatch -581 (-24.28%) -48 (-24.49%)
userland_dispatch -36 (-22.78%) -4 (-23.53%)

('layered_init' and 'pair_dispatch' hit 1M on master,
but are verified ok with this patch-set).

sched_ext used for testing:
commit 2b7f3bba928f ("Merge pull request #1197 from devnexen/code_simpl4")

Eduard Zingerman (7):
bpf: copy_verifier_state() should copy 'loop_entry' field selftests/bpf: test correct loop_entry update in copy_verifier_state
bpf: don't do clean_live_states when state->loop_entry->branches > 0 selftests/bpf: check states pruning for deeply nested iterator
bpf: DFA-based liveness analysis for program registers
bpf: use register liveness information for func_states_equal selftests/bpf: test cases for compute_live_registers()

 include/linux/bpf_verifier.h                  |   6 +
 kernel/bpf/verifier.c                         | 372 ++++++++++++++++--
 .../testing/selftests/bpf/prog_tests/align.c  |  11 +-
 .../bpf/prog_tests/compute_live_registers.c   |   9 +
 tools/testing/selftests/bpf/progs/bpf_misc.h  |  12 +
 .../bpf/progs/compute_live_registers.c        | 363 +++++++++++++++++
 tools/testing/selftests/bpf/progs/iters.c     | 139 +++++++
 .../selftests/bpf/progs/verifier_gotol.c      |   6 +-
 .../bpf/progs/verifier_iterating_callbacks.c  |   6 +-
 9 files changed, 886 insertions(+), 38 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/compute_live_registers.c
 create mode 100644 tools/testing/selftests/bpf/progs/compute_live_registers.c
Signature · 1 line
2.47.1
author maintainer
#1 lore raw

RFC 1/7 bpf: copy_verifier_state() should copy 'loop_entry' field

The bpf_verifier_state.loop_entry state should be copied by copy_verifier_state(). Otherwise, .loop_entry values from unrelated states would poison env->cur_state.

Additionally, env->stack should not contain any states with .loop_entry != NULL. The states in env->stack are yet to be verified, while .loop_entry is set for states that reached an equivalent state. This means that env->cur_state->loop_entry should always be NULL after pop_stack().

See the selftest in the next commit for an example of the program that is not safe yet is accepted by verifier w/o this fix.

This change has some verification performance impact for selftests:

Program                       Insns   (DIFF)  States (DIFF)
----------------------------  --------------  -------------
arena_htab_llvm               -291 (-40.59%)  -20 (-35.09%)
arena_htab_asm                -152 (-25.46%)  -10 (-21.28%)
arena_list_del                  -30 (-9.71%)   -9 (-39.13%)
checkpoint_states_deletion       -5 (-0.03%)    -1 (-0.12%)
iter_nested_deeply_iters        -26 (-4.38%)    -4 (-5.97%)
iter_subprog_check_stacksafe    -14 (-9.03%)    -1 (-6.67%)
iter_subprog_iters              -91 (-8.32%)    -5 (-5.68%)
loop_state_deps2              +246 (+51.36%)  +17 (+36.96%)
open_coded_iter                  -4 (-6.35%)   -1 (-14.29%)
on_event                       -320 (-2.59%)  -80 (-18.14%)
big_alloc2                       +7 (+0.24%)    +1 (+0.65%)
max_words                        -8 (-8.70%)   -1 (-12.50%)
cond_break2                      -6 (-5.31%)    +0 (+0.00%)

And significant negative impact for sched_ext:

Program                 Insns         (DIFF)  States      (DIFF)
----------------------  --------------------  ------------------
lavd_cpu_offline                 +4 (+0.09%)         -1 (-0.32%)
lavd_cpu_online                  +4 (+0.09%)         -1 (-0.32%)
lavd_enqueue                     -4 (-0.08%)         +0 (+0.00%)

lavd_init +7684 (+109.40%) +649 (+133.26%)
layered_dispatch -937 (-8.16%) -86 (-10.14%)
layered_dump +992580 (+13375.29%) +30497 (+4478.27%)
layered_enqueue -2733 (-20.91%) -260 (-22.07%)
layered_runnable -435 (-13.52%) -38 (-12.88%)
refresh_layer_cpumasks +658273 (+3992.68%) +63600 (+3593.22%)

rustland_init                   -22 (-4.42%)         -4 (-9.76%)
rustland_init                   -22 (-4.42%)         -4 (-9.76%)
rusty_init                   +1917 (+12.72%)      +175 (+22.76%)
rusty_init_task                +135 (+0.32%)        +10 (+0.45%)
rusty_select_cpu          +75128 (+3580.93%)   +5807 (+3208.29%)
rusty_set_cpumask           -15799 (-78.00%)     -1349 (-81.02%)
central_dispatch            +2051 (+322.48%)     +164 (+260.32%)

nest_init +179 (+28.14%) +13 (+21.67%)
qmap_dispatch +1187 (+49.60%) +57 (+29.08%)
qmap_dump +85 (+36.48%) +8 (+36.36%)
qmap_init +1069 (+6.53%) +66 (+10.95%)

Note 'layered_dump' program, which now hits 1M instructions limit. This impact would be mitigated in the next patch.

---
 kernel/bpf/verifier.c | 3 +++
 1 file changed, 3 insertions(+)
kernel/bpf/verifier.c +3 -0
index 74525392714e..c7ceb59d3a19 100644
@@ -1659,6 +1659,7 @@ static int copy_verifier_state(struct bpf_verifier_state *dst_state,
 	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;
 	for (i = 0; i <= src->curframe; i++) {
 		dst = dst_state->frame[i];
 		if (!dst) {
@@ -19230,6 +19231,8 @@ static int do_check(struct bpf_verifier_env *env)
 						return err;
 					break;
 				} else {
+					if (WARN_ON_ONCE(env->cur_state->loop_entry))
+						env->cur_state->loop_entry = NULL;
 					do_print_state = true;
 					continue;
 				}
Signature · 1 line
2.47.1
author maintainer
#2 lore raw

RFC 2/7 selftests/bpf: test correct loop_entry update in copy_verifier_state

In reply to Eduard Zingerman

A somewhat cumbersome test case sensitive to correct copying of bpf_verifier_state->loop_entry fields in verifier.c:copy_verifier_state().
W/o the fix from a previous commit the program is accepted as safe.

     1:  /* poison block */
     2:  if (random() != 24) {       // assume false branch is placed first
     3:    i = iter_new();
     4:    while (iter_next(i));
     5:    iter_destroy(i);
     6:    return;
     7:  }
     8:
     9:  /* dfs_depth block */
    10:  for (i = 10; i > 0; i--);
    11:
    12:  /* main block */
    13:  i = iter_new();             // fp[-16]
    14:  b = -24;                    // r8
    15:  for (;;) {
    16:    if (iter_next(i))
    17:      break;
    18:    if (random() == 77) {     // assume false branch is placed first
    19:      *(u64 *)(r10 + b) = 7;  // this is not safe when b == -25
    20:      iter_destroy(i);
    21:      return;
    22:    }
    23:    if (random() == 42) {     // assume false branch is placed first
    24:      b = -25;
    25:    }
    26:  }
    27:  iter_destroy(i);

The goal of this example is to:
(a) poison env->cur_state->loop_entry with a state S,

    such that S->branches == 0;
(b) set state S as a loop_entry for all checkpoints in
    /* main block */, thus forcing NOT_EXACT states comparisons;
(c) exploit incorrect loop_entry set for checkpoint at line 18
    by first creating a checkpoint with b == -24 and then
    pruning the state with b == -25 using that checkpoint.

The /* poison block */ is responsible for goal (a).
It forces verifier to first validate some unrelated iterator based loop, which leads to an update_loop_entry() call in is_state_visited(), which places checkpoint created at line 4 as env->cur_state->loop_entry. Starting from line 8, the branch count for that checkpoint is 0.

The /* dfs_depth block */ is responsible for goal (b).
It abuses the fact that update_loop_entry(cur, hdr) only updates cur->loop_entry when hdr->dfs_depth <= cur->dfs_depth. After line 12 every state has dfs_depth bigger then dfs_depth of poisoned env->cur_state->loop_entry. Thus the above condition is never true for lines 12-27.

The /* main block */ is responsible for goal (c). Verification proceeds as follows:
- checkpoint {b=-24,i=active} created at line 16;
- jump 18->23 is verified first, jump to 19 pushed to stack;
- jump 23->26 is verified first, jump to 24 pushed to stack;
- checkpoint {b=-24,i=active} created at line 15;
- current state is pruned by checkpoint created at line 16, this sets branches count for checkpoint at line 15 to 0;
- jump to 24 is popped from stack;
- line 16 is reached in state {b=-25,i=active};
- this is pruned by a previous checkpoint {b=-24,i=active}:
- checkpoint's loop_entry is poisoned and has branch count of 0,

    hence states are compared using NOT_EXACT rules;

- b is not marked precise yet.

---
 tools/testing/selftests/bpf/progs/iters.c | 116 ++++++++++++++++++++++
 1 file changed, 116 insertions(+)
tools/testing/selftests/bpf/progs/iters.c +116 -0
index 190822b2f08b..007831dc8c46 100644
@@ -1174,6 +1174,122 @@ __naked int loop_state_deps2(void)
 	);
 }
 
+SEC("?raw_tp")
+__failure
+__msg("math between fp pointer and register with unbounded")
+__flag(BPF_F_TEST_STATE_FREQ)
+__naked int loop_state_deps3(void)
+{
+	/* This is equivalent to a C program below.
+	 *
+	 *   if (random() != 24) {       // assume false branch is placed first
+	 *     i = iter_new();           // fp[-8]
+	 *     while (iter_next(i));
+	 *     iter_destroy(i);
+	 *     return;
+	 *   }
+	 *
+	 *   for (i = 10; i > 0; i--);   // increase dfs_depth for child states
+	 *
+	 *   i = iter_new();             // fp[-8]
+	 *   b = -24;                    // r8
+	 *   for (;;) {                  // checkpoint (L)
+	 *     if (iter_next(i))         // checkpoint (N)
+	 *       break;
+	 *     if (random() == 77) {     // assume false branch is placed first
+	 *       *(u64 *)(r10 + b) = 7;  // this is not safe when b == -25
+	 *       iter_destroy(i);
+	 *       return;
+	 *     }
+	 *     if (random() == 42) {     // assume false branch is placed first
+	 *       b = -25;
+	 *     }
+	 *   }
+	 *   iter_destroy(i);
+	 *
+	 * In case of a buggy verifier first loop might poison
+	 * env->cur_state->loop_entry with a state having 0 branches
+	 * and small dfs_depth. This would trigger NOT_EXACT states
+	 * comparison for some states within second loop.
+	 * Specifically, checkpoint (L) might be problematic if:
+	 * - branch with '*(u64 *)(r10 + b) = 7' is not explored yet;
+	 * - checkpoint (L) is first reached in state {b=-24};
+	 * - traversal is pruned at checkpoint (N) setting checkpoint's (L)
+	 *   branch count to 0, thus making it eligible for use in pruning;
+	 * - checkpoint (L) is next reached in state {b=-25},
+	 *   this would cause NOT_EXACT comparison with a state {b=-24}
+	 *   while 'b' is not marked precise yet.
+	 */
+	asm volatile (
+		"call %[bpf_get_prandom_u32];"
+		"if r0 == 24 goto 2f;"
+		"r1 = r10;"
+		"r1 += -8;"
+		"r2 = 0;"
+		"r3 = 5;"
+		"call %[bpf_iter_num_new];"
+	"1:"
+		"r1 = r10;"
+		"r1 += -8;"
+		"call %[bpf_iter_num_next];"
+		"if r0 != 0 goto 1b;"
+		"r1 = r10;"
+		"r1 += -8;"
+		"call %[bpf_iter_num_destroy];"
+		"r0 = 0;"
+		"exit;"
+	"2:"
+		/* loop to increase dfs_depth */
+		"r0 = 10;"
+	"3:"
+		"r0 -= 1;"
+		"if r0 != 0 goto 3b;"
+		/* end of loop */
+		"r1 = r10;"
+		"r1 += -8;"
+		"r2 = 0;"
+		"r3 = 10;"
+		"call %[bpf_iter_num_new];"
+		"r8 = -24;"
+	"main_loop_%=:"
+		"r1 = r10;"
+		"r1 += -8;"
+		"call %[bpf_iter_num_next];"
+		"if r0 == 0 goto main_loop_end_%=;"
+		/* first if */
+		"call %[bpf_get_prandom_u32];"
+		"if r0 == 77 goto unsafe_write_%=;"
+		/* second if */
+		"call %[bpf_get_prandom_u32];"
+		"if r0 == 42 goto poison_r8_%=;"
+		/* iterate */
+		"goto main_loop_%=;"
+	"main_loop_end_%=:"
+		"r1 = r10;"
+		"r1 += -8;"
+		"call %[bpf_iter_num_destroy];"
+		"r0 = 0;"
+		"exit;"
+
+	"unsafe_write_%=:"
+		"r0 = r10;"
+		"r0 += r8;"
+		"r1 = 7;"
+		"*(u64 *)(r0 + 0) = r1;"
+		"goto main_loop_end_%=;"
+
+	"poison_r8_%=:"
+		"r8 = -25;"
+		"goto main_loop_%=;"
+		:
+		: __imm(bpf_get_prandom_u32),
+		  __imm(bpf_iter_num_new),
+		  __imm(bpf_iter_num_next),
+		  __imm(bpf_iter_num_destroy)
+		: __clobber_all
+	);
+}
+
 SEC("?raw_tp")
 __success
 __naked int triple_continue(void)
Signature · 1 line
2.47.1
author maintainer
#3 lore raw

RFC 3/7 bpf: don't do clean_live_states when state->loop_entry->branches > 0

In reply to Eduard Zingerman

verifier.c:is_state_visited() uses RANGE_WITHIN states comparison rules for cached states that have loop_entry with non-zero branches count (meaning that loop_entry's verification is not yet done).

The RANGE_WITHIN rules in regsafe()/stacksafe() require register and stack objects types to be identical in current and old states.

verifier.c:clean_live_states() replaces registers and stack spills with NOT_INIT/STACK_INVALID marks, if these registers/stack spills are not read in any child state. This means that clean_live_states() works against loop convergence logic under some conditions. See selftest in the next patch for a specific example.

Mitigate this by prohibiting clean_verifier_state() when state->loop_entry->branches > 0.

This undoes negative verification performance impact of the copy_verifier_state() fix from the previous patch. Below is comparison between master and current patch.

selftests:

File                  Program                       Insns      (DIFF)  States    (DIFF)
--------------------  ----------------------------  -----------------  ----------------
arena_htab.bpf.o      arena_htab_llvm                  -294 (-41.00%)     -20 (-35.09%)
arena_htab_asm.bpf.o  arena_htab_asm                   -152 (-25.46%)     -10 (-21.28%)
arena_list.bpf.o      arena_list_add                   +329 (+22.04%)      +7 (+23.33%)
arena_list.bpf.o      arena_list_del                    -51 (-16.50%)      -8 (-34.78%)
iters.bpf.o           checkpoint_states_deletion      -8297 (-45.78%)    -451 (-55.13%)
iters.bpf.o           clean_live_states             -998653 (-99.87%)  -90126 (-99.85%)
iters.bpf.o           iter_nested_deeply_iters         -226 (-38.11%)     -24 (-35.82%)
iters.bpf.o           iter_subprog_check_stacksafe      -20 (-12.90%)       -1 (-6.67%)
iters.bpf.o           iter_subprog_iters               -286 (-26.14%)     -20 (-22.73%)
iters.bpf.o           loop_state_deps2                 -123 (-25.68%)     -11 (-23.91%)
iters.bpf.o           triple_continue                    -4 (-11.43%)       +0 (+0.00%)
mptcp_subflow.bpf.o   _getsockopt_subflow               -55 (-10.98%)       -2 (-8.00%)
pyperf600_iter.bpf.o  on_event                        -6025 (-48.83%)    -160 (-36.28%)

(arena_list_add requires further investigation)

sched_ext:

Program                 Insns      (DIFF)  States    (DIFF)
----------------------  -----------------  ----------------
layered_dispatch          -3570 (-31.08%)    -227 (-26.77%)
layered_dump              -2746 (-37.00%)    -411 (-60.35%)
layered_enqueue           -3781 (-28.93%)    -341 (-28.95%)

layered_init -994488 (-99.45%) -84153 (-99.39%)
layered_runnable -1467 (-45.59%) -160 (-54.24%)
refresh_layer_cpumasks -15202 (-92.21%) -1650 (-93.22%)
rusty_select_cpu -647 (-30.84%) -53 (-29.28%)
rusty_set_cpumask -15934 (-78.67%) -1359 (-81.62%)
central_init -330 (-36.18%) -10 (-20.83%)
pair_dispatch -998092 (-99.81%) -58249 (-99.76%)

'layered_init' and 'pair_dispatch' hit 1M on master, but are verified ok with this patch.

---
 kernel/bpf/verifier.c | 4 ++++
 1 file changed, 4 insertions(+)
kernel/bpf/verifier.c +4 -0
index c7ceb59d3a19..1c2199a3f38f 100644
@@ -17801,12 +17801,16 @@ 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;
 
 	sl = *explored_state(env, insn);
 	while (sl) {
 		if (sl->state.branches)
 			goto next;
+		loop_entry = get_loop_entry(&sl->state);
+		if (loop_entry && loop_entry->branches)
+			goto next;
 		if (sl->state.insn_idx != insn ||
 		    !same_callsites(&sl->state, cur))
 			goto next;
Signature · 1 line
2.47.1
author maintainer
#4 lore raw

RFC 4/7 selftests/bpf: check states pruning for deeply nested iterator

In reply to Eduard Zingerman

A test case with ridiculously deep bpf_for() nesting and a conditional update of a stack location.

Consider the innermost loop structure:

	1: bpf_for(o, 0, 10)
	2:	if (unlikely(bpf_get_prandom_u32()))
	3:		buf[0] = 42;
	4: <exit>

Assuming that verifier.c:clean_live_states() operates w/o change from the previous patch (e.g. as on current master) verification would proceed as follows:
- at (1) state {buf[0]=?,o=drained}:
- checkpoint
- push visit to (2) for later
- at (4) {buf[0]=?,o=drained}
- pop (2) {buf[0]=?,o=active}, push visit to (3) for later
- at (1) {buf[0]=?,o=active}
- checkpoint
- push visit to (2) for later
- at (4) {buf[0]=?,o=drained}
- pop (2) {buf[0]=?,o=active}, push visit to (3) for later
- at (1) {buf[0]=?,o=active}:
- checkpoint reached, checkpoint's branch count becomes 0
- checkpoint is processed by clean_live_states() and

    becomes {o=active}

- pop (3) {buf[0]=42,o=active}
- at (1), {buf[0]=42,o=active}
- checkpoint
- push visit to (2) for later
- at (4) {buf[0]=42,o=drained}
- pop (2) {buf[0]=42,o=active}, push visit to (3) for later
- at (1) {buf[0]=42,o=active}, checkpoint reached
- pop (3) {buf[0]=42,o=active}
- at (1) {buf[0]=42,o=active}:
- checkpoint reached, checkpoint's branch count becomes 0
- checkpoint is processed by clean_live_states() and

    becomes {o=active}

- ...

Note how clean_live_states() converted the checkpoint {buf[0]=42,o=active} to {o=active} and it can no longer be matched against {buf[0]=<any>,o=active}, because iterator based states are compared using stacksafe(... RANGE_WITHIN), that requires stack slots to have same types. At the same time there are still states {buf[0]=42,o=active} pushed to DFS stack.

This behaviour becomes exacerbated with multiple nesting levels, here are veristat results:
- nesting level 1: 69 insns
- nesting level 2: 258 insns
- nesting level 3: 900 insns
- nesting level 4: 4754 insns
- nesting level 5: 35944 insns
- nesting level 6: 312558 insns
- nesting level 7: 1M limit

---
 tools/testing/selftests/bpf/progs/iters.c | 23 +++++++++++++++++++++++
 1 file changed, 23 insertions(+)
tools/testing/selftests/bpf/progs/iters.c +23 -0
index 007831dc8c46..427b72954b87 100644
@@ -7,6 +7,8 @@
 #include "bpf_misc.h"
 #include "bpf_compiler.h"
 
+#define unlikely(x)	__builtin_expect(!!(x), 0)
+
 static volatile int zero = 0;
 
 int my_pid;
@@ -1628,4 +1630,25 @@ int iter_destroy_bad_arg(const void *ctx)
 	return 0;
 }
 
+SEC("raw_tp")
+__success
+int clean_live_states(const void *ctx)
+{
+	char buf[1];
+	int i, j, k, l, m, n, o;
+
+	bpf_for(i, 0, 10)
+	bpf_for(j, 0, 10)
+	bpf_for(k, 0, 10)
+	bpf_for(l, 0, 10)
+	bpf_for(m, 0, 10)
+	bpf_for(n, 0, 10)
+	bpf_for(o, 0, 10) {
+		if (unlikely(bpf_get_prandom_u32()))
+			buf[0] = 42;
+		bpf_printk("%s", buf);
+	}
+	return 0;
+}
+
 char _license[] SEC("license") = "GPL";
Signature · 1 line
2.47.1
author maintainer
#5 lore raw

RFC 5/7 bpf: DFA-based liveness analysis for program registers

In reply to Eduard Zingerman

Compute may-live registers before each instruction in the program. The register is live before the instruction I if it is read by I or some instruction S following I during program execution and is not overwritten between I and S.

This information would be used in the next patch as a hint in func_states_equal().

Use a simple algorithm described in [1] to compute this information:
- define the following:
- I.use : a set of all registers read by instruction I;
- I.def : a set of all registers written by instruction I;
- I.in : a set of all registers that may be alive before I execution;
- I.out : a set of all registers that may be alive after I execution;
- I.successors : a set of instructions S that might immediately

                   follow I for some program execution;

- associate separate empty sets 'I.in' and 'I.out' with each instruction;
- visit each instruction in a postorder and update corresponding 'I.in' and 'I.out' sets as follows:

I.out = U [S.in for S in I.successors]
I.in = (I.out / I.def) U I.use

(where U stands for set union, / stands for set difference)
- repeat the computation while I.{in,out} changes for any instruction.

On implementation side keep things as simple, as possible:
- check_cfg() already marks instructions EXPLORED in post-order, modify it to save the index of each EXPLORED instruction in a vector;
- represent I.{in,out,use,def} as bitmasks;
- don't split the program into basic blocks and don't maintain the work queue, instead:
- do fixed-point computation by visiting each instruction;
- maintain a simple 'changed' flag if I.{in,out} for any instruction

    change;

Measurements show that even such simplistic implementation does not add measurable verification time overhead (for selftests, at-least).

Note on check_cfg() ex_insn_beg/ex_done change:
To avoid out of bounds access to env->cfg.insn_postorder array, it should be guaranteed that instruction transitions to EXPLORED state only once. Previously this was not the fact for incorrect programs with direct calls to exception callbacks.

The 'align' selftest needs adjustment to skip computed insn/live registers printout. Otherwise it matches lines from the live registers printout.

[1] https://en.wikipedia.org/wiki/Live-variable_analysis

---
 include/linux/bpf_verifier.h                  |   6 +
 kernel/bpf/verifier.c                         | 351 ++++++++++++++++--
 .../testing/selftests/bpf/prog_tests/align.c  |  11 +-
 3 files changed, 344 insertions(+), 24 deletions(-)
include/linux/bpf_verifier.h +6 -0
index 32c23f2a3086..2b243a32d846 100644
@@ -589,6 +589,8 @@ struct bpf_insn_aux_data {
 	 * accepts callback function as a parameter.
 	 */
 	bool calls_callback;
+	/* registers alive before this instruction. */
+	u16 live_regs_before;
 };
 
 #define MAX_USED_MAPS 64 /* max number of maps accessed by one eBPF program */
@@ -742,7 +744,11 @@ struct bpf_verifier_env {
 	struct {
 		int *insn_state;
 		int *insn_stack;
+		/* vector of instruction indexes sorted in post-order */
+		int *insn_postorder;
 		int cur_stack;
+		/* current position in the insn_postorder vector */
+		int cur_postorder;
 	} cfg;
 	struct backtrack_state bt;
 	struct bpf_insn_hist_entry *insn_hist;
kernel/bpf/verifier.c +328 -23

445 lines not on this page · raw message

tools/testing/selftests/bpf/prog_tests/align.c +10 -1
index 4ebd0da898f5..1d53a8561ee2 100644
@@ -610,9 +610,11 @@ static int do_test_single(struct bpf_align_test *test)
 		.log_size = sizeof(bpf_vlog),
 		.log_level = 2,
 	);
+	const char *main_pass_start = "0: R1=ctx() R10=fp0";
 	const char *line_ptr;
 	int cur_line = -1;
 	int prog_len, i;
+	char *start;
 	int fd_prog;
 	int ret;
 
@@ -632,7 +634,13 @@ static int do_test_single(struct bpf_align_test *test)
 		ret = 0;
 		/* We make a local copy so that we can strtok() it */
 		strncpy(bpf_vlog_copy, bpf_vlog, sizeof(bpf_vlog_copy));
-		line_ptr = strtok(bpf_vlog_copy, "\n");
+		start = strstr(bpf_vlog_copy, main_pass_start);
+		if (!start) {
+			ret = 1;
+			printf("Can't find initial line '%s'\n", main_pass_start);
+			goto out;
+		}
+		line_ptr = strtok(start, "\n");
 		for (i = 0; i < MAX_MATCHES; i++) {
 			struct bpf_reg_match m = test->matches[i];
 			const char *p;
@@ -682,6 +690,7 @@ static int do_test_single(struct bpf_align_test *test)
 				break;
 			}
 		}
+out:
 		if (fd_prog >= 0)
 			close(fd_prog);
 	}
Signature · 1 line
2.47.1
author maintainer
#6 lore raw

Re: [RFC bpf-next v1 5/7] bpf: DFA-based liveness analysis for program registers

On Wed, 2025-01-22 at 04:04 -0800, Eduard Zingerman wrote:

[...]

kernel/bpf/verifier.c int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3 · line 23450

Quoted 11 lines
kernel/bpf/verifier.c +4 -0
@@ -23141,6 +23441,10 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3
 	if (ret)
 		goto skip_full_check;
 
+	ret = compute_live_registers(env);
+	if (ret < 0)
+		goto skip_full_check;
+
 	ret = mark_fastcall_patterns(env);
 	if (ret < 0)
 		goto skip_full_check;

In an off-list discussion Alexei asked to keep this enabled only in privileged mode.

[...]

author maintainer
#7 lore raw

RFC 6/7 bpf: use register liveness information for func_states_equal

In reply to Eduard Zingerman

Liveness analysis DFA computes a set of registers live before each instruction. Leverage this information to skip comparison of dead registers in func_states_equal(). This helps with convergance of iterator processing loops, as bpf_reg_state->live marks can't be used when loops are processed.

This has certain performance impact for selftests, here is a veristat listing for bigger ones (this patch compared to previous patch):

File                  Program                     Insns    (DIFF)  States  (DIFF)
--------------------  --------------------------  ---------------  --------------
iters.bpf.o           checkpoint_states_deletion  -8617 (-87.68%)  -327 (-89.10%)
iters.bpf.o           iter_nested_iters            -140 (-18.13%)   -10 (-13.89%)
pyperf600_iter.bpf.o  on_event                    -2608 (-41.31%)   -29 (-10.32%)

Impact on sched_ext:

Program                 Insns     (DIFF)  States   (DIFF)
----------------------  ----------------  ---------------
lavd_dispatch           -34018 (-22.00%)  -1885 (-21.06%)
layered_dispatch         -1808 (-22.83%)    -86 (-13.85%)
layered_dump              -943 (-20.17%)    -44 (-16.30%)
layered_init              -995 (-18.05%)    -80 (-15.41%)
refresh_layer_cpumasks    -395 (-30.74%)    -34 (-28.33%)
rustland_init              -63 (-13.24%)      -3 (-8.11%)
rustland_init              -63 (-13.24%)      -3 (-8.11%)
tp_cgroup_attach_task      -53 (-26.24%)     -4 (-22.22%)
central_init              -146 (-25.09%)      -2 (-5.26%)
pair_dispatch             -331 (-17.34%)    -15 (-10.56%)
qmap_dispatch             -375 (-17.15%)    -26 (-14.94%)

userland_dispatch -34 (-21.79%) -4 (-23.53%)

---
 kernel/bpf/verifier.c | 14 ++++++++++----
 1 file changed, 10 insertions(+), 4 deletions(-)
kernel/bpf/verifier.c +10 -4
index d36c5a3309e9..babc2e179c08 100644
@@ -18223,15 +18223,17 @@ static bool refsafe(struct bpf_verifier_state *old, struct bpf_verifier_state *c
  * the current state will reach 'bpf_exit' instruction safely
  */
 static bool func_states_equal(struct bpf_verifier_env *env, struct bpf_func_state *old,
-			      struct bpf_func_state *cur, enum exact_level exact)
+			      struct bpf_func_state *cur, u32 insn_idx, enum exact_level exact)
 {
-	int i;
+	u16 live_regs = env->insn_aux_data[insn_idx].live_regs_before;
+	u16 i;
 
 	if (old->callback_depth > cur->callback_depth)
 		return false;
 
 	for (i = 0; i < MAX_BPF_REG; i++)
-		if (!regsafe(env, &old->regs[i], &cur->regs[i],
+		if (((1 << i) & live_regs) &&
+		    !regsafe(env, &old->regs[i], &cur->regs[i],
 			     &env->idmap_scratch, exact))
 			return false;
 
@@ -18252,6 +18254,7 @@ static bool states_equal(struct bpf_verifier_env *env,
 			 struct bpf_verifier_state *cur,
 			 enum exact_level exact)
 {
+	u32 insn_idx;
 	int i;
 
 	if (old->curframe != cur->curframe)
@@ -18275,9 +18278,12 @@ 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;
 		if (old->frame[i]->callsite != cur->frame[i]->callsite)
 			return false;
-		if (!func_states_equal(env, old->frame[i], cur->frame[i], exact))
+		if (!func_states_equal(env, old->frame[i], cur->frame[i], insn_idx, exact))
 			return false;
 	}
 	return true;
Signature · 1 line
2.47.1
author maintainer
#8 lore raw

RFC 7/7 selftests/bpf: test cases for compute_live_registers()

In reply to Eduard Zingerman

Cover instructions from each kind:
- assignment
- arithmetic
- store/load
- endian conversion
- atomics
- branches, conditional branches, may_goto, calls
- LD_ABS/LD_IND
- address_space_cast

---
 .../bpf/prog_tests/compute_live_registers.c   |   9 +
 tools/testing/selftests/bpf/progs/bpf_misc.h  |  12 +
 .../bpf/progs/compute_live_registers.c        | 363 ++++++++++++++++++
 .../selftests/bpf/progs/verifier_gotol.c      |   6 +-
 .../bpf/progs/verifier_iterating_callbacks.c  |   6 +-
 5 files changed, 386 insertions(+), 10 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/compute_live_registers.c
 create mode 100644 tools/testing/selftests/bpf/progs/compute_live_registers.c
tools/testing/selftests/bpf/prog_tests/compute_live_registers.c new file +9 -0
new file mode 100644
index 000000000000..285f20241fe1
@@ -0,0 +1,9 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include "compute_live_registers.skel.h"
+#include "test_progs.h"
+
+void test_compute_live_registers(void)
+{
+	RUN_TESTS(compute_live_registers);
+}
tools/testing/selftests/bpf/progs/bpf_misc.h +12 -0
index f45f4352feeb..2b34911439d4 100644
@@ -208,4 +208,16 @@
 #define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
 #endif
 
+#if (defined(__TARGET_ARCH_arm64) || defined(__TARGET_ARCH_x86) ||	\
+     (defined(__TARGET_ARCH_riscv) && __riscv_xlen == 64) ||		\
+     defined(__TARGET_ARCH_arm) || defined(__TARGET_ARCH_s390) ||	\
+     defined(__TARGET_ARCH_loongarch)) &&				\
+	__clang_major__ >= 18
+#define CAN_USE_GOTOL
+#endif
+
+#if _clang_major__ >= 18
+#define CAN_USE_BPF_ST
+#endif
+
 #endif
tools/testing/selftests/bpf/progs/compute_live_registers.c new file +363 -0

363 lines not on this page · raw message

tools/testing/selftests/bpf/progs/verifier_gotol.c +1 -5
index 05a329ee45ee..d5d8f24df394 100644
@@ -4,11 +4,7 @@
 #include <bpf/bpf_helpers.h>
 #include "bpf_misc.h"
 
-#if (defined(__TARGET_ARCH_arm64) || defined(__TARGET_ARCH_x86) || \
-	(defined(__TARGET_ARCH_riscv) && __riscv_xlen == 64) || \
-	defined(__TARGET_ARCH_arm) || defined(__TARGET_ARCH_s390) || \
-	defined(__TARGET_ARCH_loongarch)) && \
-	__clang_major__ >= 18
+#ifdef CAN_USE_GOTOL
 
 SEC("socket")
 __description("gotol, small_imm")
tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c +1 -5
index e54bb5385bc1..75dd922e4e9f 100644
@@ -407,11 +407,7 @@ l0_%=:	call %[bpf_jiffies64];		\
 	: __clobber_all);
 }
 
-#if (defined(__TARGET_ARCH_arm64) || defined(__TARGET_ARCH_x86) || \
-	(defined(__TARGET_ARCH_riscv) && __riscv_xlen == 64) || \
-	defined(__TARGET_ARCH_arm) || defined(__TARGET_ARCH_s390) || \
-	defined(__TARGET_ARCH_loongarch)) && \
-	__clang_major__ >= 18
+#ifdef CAN_USE_GOTOL
 SEC("socket")
 __success __retval(0)
 __naked void gotol_and_may_goto(void)
Signature · 1 line
2.47.1