From: Eduard Zingerman <eddyz87@gmail.com>
To: bpf@vger.kernel.org, ast@kernel.org
Cc: andrii@kernel.org, daniel@iogearbox.net, martin.lau@linux.dev,
kernel-team@fb.com, yonghong.song@linux.dev, tj@kernel.org,
Eduard Zingerman <eddyz87@gmail.com>
Subject: [PATCH bpf-next v1 2/3] bpf: use register liveness information for func_states_equal
Date: Thu, 27 Feb 2025 22:00:31 -0800 [thread overview]
Message-ID: <20250228060032.1425870-3-eddyz87@gmail.com> (raw)
In-Reply-To: <20250228060032.1425870-1-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
next prev parent reply other threads:[~2025-02-28 6:00 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-02-28 6:00 [PATCH bpf-next v1 0/3] bpf: simple DFA-based live registers analysis Eduard Zingerman
2025-02-28 6:00 ` [PATCH bpf-next v1 1/3] " Eduard Zingerman
2025-03-01 2:01 ` Alexei Starovoitov
2025-03-01 2:09 ` Eduard Zingerman
2025-02-28 6:00 ` Eduard Zingerman [this message]
2025-02-28 6:00 ` [PATCH bpf-next v1 3/3] selftests/bpf: test cases for compute_live_registers() Eduard Zingerman
2025-03-01 2:10 ` [PATCH bpf-next v1 0/3] bpf: simple DFA-based live registers analysis Alexei Starovoitov
2025-03-01 4:40 ` Eduard Zingerman
2025-03-02 0:09 ` Alexei Starovoitov
2025-03-03 19:28 ` Eduard Zingerman
2025-03-05 9:00 ` Eduard Zingerman
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20250228060032.1425870-3-eddyz87@gmail.com \
--to=eddyz87@gmail.com \
--cc=andrii@kernel.org \
--cc=ast@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=daniel@iogearbox.net \
--cc=kernel-team@fb.com \
--cc=martin.lau@linux.dev \
--cc=tj@kernel.org \
--cc=yonghong.song@linux.dev \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox