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@xxxxxxxxx>
---
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
