[PATCH bpf-next v1 2/3] bpf: use register liveness information for func_states_equal

[Eduard Zingerman <eddyz87@gmail.com>]

Liveness analysis DFA computes a set of registers that are live before
each instruction. Leverage this information to skip the comparison of
dead registers in `func_states_equal()`. This helps with the
convergence of iterator-based loops, as `bpf_reg_state->live` marks
can't be used when loops are processed. For now, enable this only in
privileged mode.

Verification performance impact on selftests and sched_ext is listed
below. (Using `veristat -C -f "insns_pct>5" -f "!insns<200"` filters).

selftests:

File                  Program                        Insns (A)  Insns (B)  Insns     (DIFF)  States (A)  States (B)  States  (DIFF)
--------------------  -----------------------------  ---------  ---------  ----------------  ----------  ----------  --------------
arena_htab_asm.bpf.o  arena_htab_asm                       445        413      -32 (-7.19%)          37          33    -4 (-10.81%)
arena_list.bpf.o      arena_list_add                      1822        833    -989 (-54.28%)          37          22   -15 (-40.54%)
dynptr_success.bpf.o  test_dynptr_copy                     267        203     -64 (-23.97%)          22          16    -6 (-27.27%)
dynptr_success.bpf.o  test_dynptr_copy_xdp                 719        615    -104 (-14.46%)          68          58   -10 (-14.71%)
iters.bpf.o           checkpoint_states_deletion         22154       1211  -20943 (-94.53%)         918          40  -878 (-95.64%)
iters.bpf.o           clean_live_states                   1348        588    -760 (-56.38%)         136          66   -70 (-51.47%)
iters.bpf.o           iter_nested_deeply_iters             367        300     -67 (-18.26%)          43          37    -6 (-13.95%)
iters.bpf.o           iter_nested_iters                    772        632    -140 (-18.13%)          72          62   -10 (-13.89%)
iters.bpf.o           iter_pass_iter_ptr_to_subprog        285        243     -42 (-14.74%)          30          26    -4 (-13.33%)
iters.bpf.o           iter_subprog_iters                   808        664    -144 (-17.82%)          68          59    -9 (-13.24%)
iters.bpf.o           loop_state_deps2                     356        321      -35 (-9.83%)          35          32     -3 (-8.57%)
iters_css.bpf.o       iter_css_for_each                    296        267      -29 (-9.80%)          32          29     -3 (-9.38%)
pyperf600_iter.bpf.o  on_event                            6379       2591   -3788 (-59.38%)         286         192   -94 (-32.87%)
test_usdt.bpf.o       usdt12                              1983       1803     -180 (-9.08%)         143         136     -7 (-4.90%)

sched_ext:

File               Program                 Insns (A)  Insns (B)  Insns     (DIFF)  States (A)  States (B)  States   (DIFF)
-----------------  ----------------------  ---------  ---------  ----------------  ----------  ----------  ---------------
bpf.bpf.o          lavd_dispatch              154608     120590  -34018 (-22.00%)        8950        7065  -1885 (-21.06%)
bpf.bpf.o          lavd_init                    7330       6935     -395 (-5.39%)         516         480     -36 (-6.98%)
bpf.bpf.o          layered_dispatch             9039       5590   -3449 (-38.16%)         662         501   -161 (-24.32%)
bpf.bpf.o          layered_dump                 5022       3669   -1353 (-26.94%)         298         237    -61 (-20.47%)
bpf.bpf.o          layered_init                 5549       4298   -1251 (-22.54%)         523         423   -100 (-19.12%)
bpf.bpf.o          layered_init_task             270        234     -36 (-13.33%)          24          22      -2 (-8.33%)
bpf.bpf.o          layered_runnable             1899       1635    -264 (-13.90%)         151         125    -26 (-17.22%)
bpf.bpf.o          p2dq_dispatch                 659        533    -126 (-19.12%)          66          53    -13 (-19.70%)
bpf.bpf.o          p2dq_init                    1936       1560    -376 (-19.42%)         170         142    -28 (-16.47%)
bpf.bpf.o          refresh_layer_cpumasks       1285        785    -500 (-38.91%)         120          78    -42 (-35.00%)
bpf.bpf.o          rustland_init                 476        413     -63 (-13.24%)          37          34      -3 (-8.11%)
bpf.bpf.o          rustland_init                 476        413     -63 (-13.24%)          37          34      -3 (-8.11%)
bpf.bpf.o          rusty_select_cpu             1386       1110    -276 (-19.91%)         125         108    -17 (-13.60%)
bpf.bpf.o          rusty_set_cpumask            4558       4276     -282 (-6.19%)         323         313     -10 (-3.10%)
scx_central.bpf.o  central_dispatch              600        422    -178 (-29.67%)          59          43    -16 (-27.12%)
scx_central.bpf.o  central_init                  632        318    -314 (-49.68%)          39          28    -11 (-28.21%)
scx_nest.bpf.o     nest_init                     601        519     -82 (-13.64%)          58          51     -7 (-12.07%)
scx_pair.bpf.o     pair_dispatch                1914       1376    -538 (-28.11%)         142         111    -31 (-21.83%)
scx_qmap.bpf.o     qmap_dispatch                2187       1703    -484 (-22.13%)         174         141    -33 (-18.97%)
scx_qmap.bpf.o     qmap_init                   22777      18458   -4319 (-18.96%)         768         654   -114 (-14.84%)

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 include/linux/bpf_verifier.h |  1 +
 kernel/bpf/verifier.c        | 18 ++++++++++++++----
 2 files changed, 15 insertions(+), 4 deletions(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 8c23958bc471..39097835b326 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -733,6 +733,7 @@ struct bpf_verifier_env {
 	 * to writes with variable offset and to indirect (helper) accesses.
 	 */
 	bool allow_uninit_stack;
+	bool allow_liveregs_dfa;
 	bool bpf_capable;
 	bool bypass_spec_v1;
 	bool bypass_spec_v4;
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 4ac7dc58d9b1..b6ab49ee31e1 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -18358,15 +18358,20 @@ 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;
+	u16 i;
 
 	if (old->callback_depth > cur->callback_depth)
 		return false;
 
+	live_regs = env->allow_liveregs_dfa
+		    ? env->insn_aux_data[insn_idx].live_regs_before
+		    : 0xffff;
 	for (i = 0; i < MAX_BPF_REG; i++)
-		if (!regsafe(env, &old->regs[i], &cur->regs[i],
+		if ((BIT(i) & live_regs) &&
+		    !regsafe(env, &old->regs[i], &cur->regs[i],
 			     &env->idmap_scratch, exact))
 			return false;
 
@@ -18387,6 +18392,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)
@@ -18410,9 +18416,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;
@@ -23647,6 +23656,7 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3
 		ret = compute_live_registers(env);
 		if (ret < 0)
 			goto skip_full_check;
+		env->allow_liveregs_dfa = true;
 	}
 
 	ret = mark_fastcall_patterns(env);
-- 
2.48.1