[RFC bpf-next v1 6/7] bpf: use register liveness information for func_states_equal

[Eduard Zingerman <eddyz87@gmail.com>]

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%)

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 kernel/bpf/verifier.c | 14 ++++++++++----
 1 file changed, 10 insertions(+), 4 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index d36c5a3309e9..babc2e179c08 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -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;
-- 
2.47.1