bpf: simple DFA-based live registers analysis
Subsystems (4)
Eduard Zingerman
maintainercover bpf: simple DFA-based live registers analysis
This patch set introduces a simple live register DFA analysis. The analysis is performed as a separate step before the main verification pass, and results are stored in env->insn_aux_data for each instruction.
This change improves handling of iterator/callback-based loops, as regular register liveness marks are not finalized while loops are being processed. See veristat results for selftests and sched_ext in patch #2.
The patch set was tested in branch [1] by disabling the current register parentage chain liveness computation, using DFA-based liveness for registers while assuming all stack slots as live. No notable regressions were found in test_progs-based tests.
Note: For regular subprogram calls, the analysis conservatively assumes that registers r1-r5 are used and that r0 is used at each exit instruction. Experiments in [1] show that adding precise handling for these cases has no impact on verification performance for selftests and sched_ext.
This was previously shared as RFC [2].
Changes since RFC:
- The parameter count for helpers and kfuncs is now taken into account.
- The analysis is now enabled only in privileged mode (Alexei);
- The copy_verifier_state() bug fix was merged separately and is no longer a part of this patch set.
[1] https://github.com/eddyz87/bpf/tree/liveregs-dfa-std-liveregs-off
[2] https://lore.kernel.org/bpf/[email protected]/
Eduard Zingerman (3):
bpf: simple DFA-based live registers analysis
bpf: use register liveness information for func_states_equal selftests/bpf: test cases for compute_live_registers()
include/linux/bpf_verifier.h | 7 + kernel/bpf/verifier.c | 394 +++++++++++++++-- .../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 | 397 ++++++++++++++++++ .../selftests/bpf/progs/verifier_gotol.c | 6 +- .../bpf/progs/verifier_iterating_callbacks.c | 6 +- 8 files changed, 804 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.48.1
Eduard Zingerman
maintainerPATCH 1/3 bpf: simple DFA-based live registers analysis
Compute may-live registers before each instruction in the program. A register is live before instruction I if it is read by I or by some instruction S that follows I, provided it is not overwritten between I and S.
This information will 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 : the set of all registers read by instruction I;
- I.def : the set of all registers written by instruction I;
- I.in : the set of all registers that may be alive before I
execution;
- I.out : the set of all registers that may be alive after I
execution;
- I.successors : the 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 the 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:
- perform fixed-point computation by visiting each instruction;
- maintain a simple 'changed' flag to track if I.{in,out} changes
for any instruction;
Measurements show that even this simplistic implementation does not add measurable verification time overhead (at least for selftests).
Note on check_cfg() ex_insn_beg/ex_done change:
To avoid out of bounds access to env->cfg.insn_postorder array, it must be guaranteed that an instruction transitions to the EXPLORED state only once. Previously, this was not the case for incorrect programs with direct calls to exception callbacks.
The 'align' selftest needs adjustment to skip the computed instruction/live registers printout. Otherwise, it matches lines from this printout instead of verification log.
[1] https://en.wikipedia.org/wiki/Live-variable_analysis
--- include/linux/bpf_verifier.h | 6 + kernel/bpf/verifier.c | 376 ++++++++++++++++-- .../testing/selftests/bpf/prog_tests/align.c | 11 +- 3 files changed, 369 insertions(+), 24 deletions(-)
include/linux/bpf_verifier.h +6 -0
@@ -591,6 +591,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 */
@@ -747,7 +749,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 +353 -23
470 lines not on this page · raw message
tools/testing/selftests/bpf/prog_tests/align.c +10 -1
@@ -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.48.1
Quoted 108 lines · Eduard Zingerman
Compute may-live registers before each instruction in the program. A register is live before instruction I if it is read by I or by some instruction S that follows I, provided it is not overwritten between I and S.
This information will 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 : the set of all registers read by instruction I;
- I.def : the set of all registers written by instruction I;
- I.in : the set of all registers that may be alive before Iexecution; - I.out : the set of all registers that may be alive after I execution; - I.successors : the 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 the 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:
- perform fixed-point computation by visiting each instruction;
- maintain a simple 'changed' flag to track if I.{in,out} changesfor any instruction;Measurements show that even this simplistic implementation does not add measurable verification time overhead (at least for selftests).
Note on
check_cfg()ex_insn_beg/ex_done change:
To avoid out of bounds access toenv->cfg.insn_postorderarray, it must be guaranteed that an instruction transitions to the EXPLORED state only once. Previously, this was not the case for incorrect programs with direct calls to exception callbacks.The 'align' selftest needs adjustment to skip the computed instruction/live registers printout. Otherwise, it matches lines from this printout instead of verification log.
[1] https://en.wikipedia.org/wiki/Live-variable_analysis
Suggested-by Alexei Starovoitov <[email protected]>Signed-off-by Eduard Zingerman <[email protected]>--- include/linux/bpf_verifier.h | 6 + kernel/bpf/verifier.c | 376 ++++++++++++++++-- .../testing/selftests/bpf/prog_tests/align.c | 11 +- 3 files changed, 369 insertions(+), 24 deletions(-)include/linux/bpf_verifier.h +6
-0@@ -591,6 +591,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 */ @@ -747,7 +749,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 +9
-0@@ -3353,6 +3353,15 @@ static int add_subprog_and_kfunc(struct bpf_verifier_env *env)return 0 ; } +static int jmp_offset (struct bpf_insn *insn) +{ +u8 code = insn->code; + +if (code == (BPF_JMP32 |BPF_JA )) +return insn->imm; +return insn->off; +} +static int check_subprogs (struct bpf_verifier_env *env) {int i, subprog_start, subprog_end, off, cur_subprog =0 ;
kernel/bpf/verifier.c static int check_subprogs(struct bpf_verifier_env *env) · line 3391
Quoted 8 lines
kernel/bpf/verifier.c +1
-4@@ -3379,10 +3388,7 @@ static int check_subprogs(struct bpf_verifier_env *env) goto next;if (BPF_OP (code) ==BPF_EXIT ||BPF_OP (code) ==BPF_CALL ) goto next; -if (code == (BPF_JMP32 |BPF_JA )) - off = i + insn[i].imm +1 ; -else - off = i + insn[i].off +1 ; + off = i +jmp_offset (&insn[i]) +1 ;
Nice cleanup, but pls split it into pre-patch,
so that main liveness logic is in the main patch.
Quoted 34 lines
kernel/bpf/verifier.c +11
-5if (off < subprog_start || off >= subprog_end) {verbose (env,"jump out of range from insn %d to %d\n" , i, off);return -EINVAL ;@@ -3912,6 +3918,17 @@ static const char *disasm_kfunc_name(void *data, const struct bpf_insn *insn)return btf_name_by_offset (desc_btf, func->name_off); } +static void verbose_insn (struct bpf_verifier_env *env,struct bpf_insn *insn) +{ +const struct bpf_insn_cbs cbs = { + .cb_call = disasm_kfunc_name, + .cb_print = verbose, + .private_data = env, + }; + +print_bpf_insn (&cbs, insn, env->allow_ptr_leaks); +} +static inline void bt_init (struct backtrack_state *bt,u32 frame) { bt->frame = frame;@@ -4112,11 +4129,6 @@ static bool calls_callback(struct bpf_verifier_env *env, int insn_idx);static int backtrack_insn (struct bpf_verifier_env *env,int idx,int subseq_idx,struct bpf_insn_hist_entry *hist,struct backtrack_state *bt) { -const struct bpf_insn_cbs cbs = { - .cb_call = disasm_kfunc_name, - .cb_print = verbose, - .private_data = env, - };struct bpf_insn *insn = env->prog->insnsi + idx;u8 class =BPF_CLASS (insn->code);u8 opcode =BPF_OP (insn->code);
kernel/bpf/verifier.c static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx, · line 4149
Quoted 5 lines
kernel/bpf/verifier.c +1
-1@@ -4134,7 +4146,7 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,fmt_stack_mask (env->tmp_str_buf,TMP_STR_BUF_LEN ,bt_stack_mask (bt));verbose (env,"stack=%s before " , env->tmp_str_buf);verbose (env,"%d: " , idx); -print_bpf_insn (&cbs, insn, env->allow_ptr_leaks); +verbose_insn (env, insn);
Same. Nice cleanup, but move it into pre-patch with all cleanups. No need for separate patches per cleanup.
Just all cleanups into one will do.
Quoted 129 lines
kernel/bpf/verifier.c +57
-13}/* If there is a history record that some registers gained range at this insn, @@ -11011,6 +11023,9 @@ static int get_helper_proto(struct bpf_verifier_env *env, int func_id,return *ptr ?0 : -EINVAL ; } +/* Bitmask with 1s for all caller saved registers */ +#define ALL_CALLER_SAVED_REGS ((1u << CALLER_SAVED_REGS) - 1) +static int check_helper_call (struct bpf_verifier_env *env,struct bpf_insn *insn,int *insn_idx_p) {@@ -17246,9 +17261,8 @@ static int visit_insn(int t, struct bpf_verifier_env *env)static int check_cfg (struct bpf_verifier_env *env) {int insn_cnt = env->prog->len; -int *insn_stack, *insn_state; +int *insn_stack, *insn_state, *insn_postorder;int ex_insn_beg, i, ret =0 ; -bool ex_done = false; insn_state = env->cfg.insn_state =kvcalloc (insn_cnt,sizeof (int ),GFP_KERNEL );if (!insn_state)@@ -17260,6 +17274,17 @@ static int check_cfg(struct bpf_verifier_env *env)return -ENOMEM ; } + insn_postorder = env->cfg.insn_postorder =kvcalloc (insn_cnt,sizeof (int ),GFP_KERNEL ); +if (!insn_postorder) { +kvfree (insn_state); +kvfree (insn_stack); +return -ENOMEM ; + } + + ex_insn_beg = env->exception_callback_subprog + ? env->subprog_info[env->exception_callback_subprog].start + :0 ; + insn_state[0 ] =DISCOVERED ;/* mark 1st insn as discovered */ insn_stack[0 ] =0 ;/* 0 is the first instruction */ env->cfg.cur_stack =1 ;@@ -17273,6 +17298,7 @@ static int check_cfg(struct bpf_verifier_env *env)case DONE_EXPLORING : insn_state[t] =EXPLORED ; env->cfg.cur_stack--; + insn_postorder[env->cfg.cur_postorder++] = t;break ;case KEEP_EXPLORING :break ;@@ -17291,13 +17317,10 @@ static int check_cfg(struct bpf_verifier_env *env) goto err_free; } -if (env->exception_callback_subprog && !ex_done) { - ex_insn_beg = env->subprog_info[env->exception_callback_subprog].start; - +if (ex_insn_beg && insn_state[ex_insn_beg] !=EXPLORED ) { insn_state[ex_insn_beg] =DISCOVERED ; insn_stack[0 ] = ex_insn_beg; env->cfg.cur_stack =1 ; - ex_done = true; goto walk_cfg; }@@ -19121,19 +19144,13 @@ static int do_check(struct bpf_verifier_env *env) }if (env->log.level &BPF_LOG_LEVEL ) { -const struct bpf_insn_cbs cbs = { - .cb_call = disasm_kfunc_name, - .cb_print = verbose, - .private_data = env, - }; -if (verifier_state_scratched (env))print_insn_state (env, state, state->curframe);verbose_linfo (env, env->insn_idx,"; " ); env->prev_log_pos = env->log.end_pos;verbose (env,"%d: " , env->insn_idx); -print_bpf_insn (&cbs, insn, env->allow_ptr_leaks); +verbose_insn (env, insn); env->prev_insn_print_pos = env->log.end_pos - env->prev_log_pos; env->prev_log_pos = env->log.end_pos; }@@ -23199,6 +23216,312 @@ static int process_fd_array(struct bpf_verifier_env *env, union bpf_attr *attr,return 0 ; } +static bool can_fallthrough (struct bpf_insn *insn) +{ +u8 class =BPF_CLASS (insn->code); +u8 opcode =BPF_OP (insn->code); + +if (class !=BPF_JMP && class !=BPF_JMP32 ) +return true; + +if (opcode ==BPF_EXIT || opcode ==BPF_JA ) +return false; + +return true; +} + +static bool can_jump (struct bpf_insn *insn) +{ +u8 class =BPF_CLASS (insn->code); +u8 opcode =BPF_OP (insn->code); + +if (class !=BPF_JMP && class !=BPF_JMP32 ) +return false; + +switch (opcode) { +case BPF_JA : +case BPF_JEQ : +case BPF_JNE : +case BPF_JLT : +case BPF_JLE : +case BPF_JGT : +case BPF_JGE : +case BPF_JSGT : +case BPF_JSGE : +case BPF_JSLT : +case BPF_JSLE : +case BPF_JCOND : +return true; + } + +return false;
kernel/bpf/verifier.c static int process_fd_array(struct bpf_verifier_env *env, union bpf_attr *attr, · line 23267
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+} + +static int insn_successors (struct bpf_prog *prog,u32 idx,u32 succ[2 ]) +{ +struct bpf_insn *insn = &prog->insnsi[idx]; +int i =0 , insn_sz; +u32 dst; + + succ[0 ] = prog->len; + succ[1 ] = prog->len;
Why initialize them? They won't be used anyway.
Quoted 43 lines
kernel/bpf/verifier.c +43
-0+ + insn_sz =bpf_is_ldimm64 (insn) ?2 :1 ; +if (can_fallthrough (insn) && idx +1 < prog->len) + succ[i++] = idx + insn_sz; + +if (can_jump (insn)) { + dst = idx +jmp_offset (insn) +1 ; +if (i ==0 || succ[0 ] != dst) + succ[i++] = dst; + } + +return i; +} + +/* Each field is a register bitmask */ +struct insn_live_regs { +u16 use;/* registers read by instruction */ +u16 def;/* registers written by instruction */ +u16 in;/* registers that may be alive before instruction */ +u16 out;/* registers that may be alive after instruction */ +}; + +/* Compute *use and *def values for the call instruction */ +static void compute_call_live_regs (struct bpf_verifier_env *env, +struct bpf_insn *insn, +u16 *use,u16 *def) +{ +struct bpf_kfunc_call_arg_meta meta; +const struct bpf_func_proto *fn; +int err, i, nargs; + + *def =ALL_CALLER_SAVED_REGS ; + *use = *def & ~BIT (BPF_REG_0 ); +if (bpf_helper_call (insn)) { + err =get_helper_proto (env, insn->imm, &fn); +if (err) +return ; + *use =0 ; +for (i =1 ; i <CALLER_SAVED_REGS ; i++) { +if (fn->arg_type[i -1 ] ==ARG_DONTCARE ) +break ; + *use |=BIT (i); + }
kernel/bpf/verifier.c static int process_fd_array(struct bpf_verifier_env *env, union bpf_attr *attr, · line 23320
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+ }else if (bpf_pseudo_kfunc_call (insn)) { + err =fetch_kfunc_meta (env, insn, &meta,NULL ); +if (err) +return ; + nargs =btf_type_vlen (meta.func_proto); + *use =0 ; +for (i =1 ; i <= nargs; i++) + *use |=BIT (i); + } +}
The helper is very close to helper_fastcall_clobber_mask() and kfunc_fastcall_clobber_mask(),
and the beginning of mark_fastcall_pattern_for_call(). Let's generalize the code and make it a pre-patch 2. (separate from trivial cleanups).
In generic helper I'd standardize on 'use' word instead of 'clobber_mask'.
The move of ALL_CALLER_SAVED_REGS can be there as well.
Quoted 123 lines
kernel/bpf/verifier.c +123
-0+ +/* Compute info->{use,def} fields for the instruction */ +static void compute_insn_live_regs (struct bpf_verifier_env *env, +struct bpf_insn *insn, +struct insn_live_regs *info) +{ +u8 class =BPF_CLASS (insn->code); +u8 code =BPF_OP (insn->code); +u8 mode =BPF_MODE (insn->code); +u16 src =BIT (insn->src_reg); +u16 dst =BIT (insn->dst_reg); +u16 r0 =BIT (0 ); +u16 def =0 ; +u16 use =0xffff ; + +switch (class) { +case BPF_LD : +switch (mode) { +case BPF_IMM : +if (BPF_SIZE (insn->code) ==BPF_DW ) { + def = dst; + use =0 ; + } +break ; +case BPF_LD |BPF_ABS : +case BPF_LD |BPF_IND : +/* stick with defaults */ +break ; + } +break ; +case BPF_LDX : +switch (mode) { +case BPF_MEM : +case BPF_MEMSX : + def = dst; + use = src; +break ; + } +break ; +case BPF_ST : +switch (mode) { +case BPF_MEM : + def =0 ; + use = dst; +break ; + } +break ; +case BPF_STX : +switch (mode) { +case BPF_MEM : + def =0 ; + use = dst | src; +break ; +case BPF_ATOMIC : + use = dst | src; +if (insn->imm &BPF_FETCH ) { +if (insn->imm ==BPF_CMPXCHG ) + def = r0; +else + def = src; + }else { + def =0 ; + } +break ; + } +break ; +case BPF_ALU : +case BPF_ALU64 : +switch (code) { +case BPF_END : + use = dst; + def = dst; +break ; +case BPF_MOV : + def = dst; +if (BPF_SRC (insn->code) ==BPF_K ) + use =0 ; +else + use = src; +break ; +default : + def = dst; +if (BPF_SRC (insn->code) ==BPF_K ) + use = dst; +else + use = dst | src; + } +break ; +case BPF_JMP : +case BPF_JMP32 : +switch (code) { +case BPF_JA : + def =0 ; + use =0 ; +break ; +case BPF_EXIT : + def =0 ; + use = r0; +break ; +case BPF_CALL : +compute_call_live_regs (env, insn, &use, &def); +break ; +default : + def =0 ; +if (BPF_SRC (insn->code) ==BPF_K ) + use = dst; +else + use = dst | src; + } +break ; + } + + info->def = def; + info->use = use; +} + +/* Compute may-live registers before each instruction in the program. +* A register is live before instruction I if it is read by I or by some +* instruction S that follows I, provided it is not overwritten between I +* and S. +* +* Store result in env->insn_aux_data[i].live_regs. +*/
kernel/bpf/verifier.c static int process_fd_array(struct bpf_verifier_env *env, union bpf_attr *attr, · line 23453
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+static int compute_live_registers (struct bpf_verifier_env *env) +{ +struct bpf_insn_aux_data *insn_aux = env->insn_aux_data; +struct bpf_insn *insns = env->prog->insnsi; +struct insn_live_regs *state; +int insn_cnt = env->prog->len; +int err =0 , i, j; +bool changed; + +/* Use simple algorithm desribed in:
described
kernel/bpf/verifier.c static int process_fd_array(struct bpf_verifier_env *env, union bpf_attr *attr, · line 23454
Quoted 1 line
kernel/bpf/verifier.c +1
-0+* https://en.wikipedia.org/wiki/Live-variable_analysis
instead of the link let's copy paste definition of I.use|def from commit log into this comment.
Quoted 45 lines
kernel/bpf/verifier.c +45
-0+* +* - visit each instruction in a postorder and update +* state[i].in, state[i].out as follows: +* +* state[i].out = U [state[s].in for S in insn_successors(i)] +* state[i].in = (state[i].out / state[i].def) U state[i].use +* +* (where U stands for set union, / stands for set difference) +* - repeat the computation while {in,out} fields change for +* any instruction. +*/ + state =kvcalloc (insn_cnt,sizeof (*state),GFP_KERNEL ); +if (!state) { + err = -ENOMEM ; + goto out; + } + +for (i =0 ; i < insn_cnt; ++i) +compute_insn_live_regs (env, &insns[i], &state[i]); + + changed = true; +while (changed) { + changed = false; +for (i =0 ; i < env->cfg.cur_postorder; ++i) { +int insn_idx = env->cfg.insn_postorder[i]; +struct insn_live_regs *live = &state[insn_idx]; +int succ_num; +u32 succ[2 ]; +u16 new_out =0 ; +u16 new_in =0 ; + + succ_num =insn_successors (env->prog, insn_idx, succ); +for (int s =0 ; s < succ_num; ++s) + new_out |= state[succ[s]].in; + new_in = (new_out & ~live->def) | live->use; +if (new_out != live->out || new_in != live->in) { + live->in = new_in; + live->out = new_out; + changed = true; + } + } + } + +for (i =0 ; i < insn_cnt; ++i) + insn_aux[i].live_regs_before = state[i].in;
kernel/bpf/verifier.c static int process_fd_array(struct bpf_verifier_env *env, union bpf_attr *attr, · line 23509
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+ +if (env->log.level &BPF_LOG_LEVEL2 ) { +verbose (env,"Live regs before insn:\n" ); +for (i =0 ; i < insn_cnt; ++i) { +verbose (env,"%3d: " , i); +for (j =BPF_REG_0 ; j <BPF_REG_10 ; ++j) +if (insn_aux[i].live_regs_before &BIT (j)) +verbose (env,"%d" , j); +else +verbose (env,"." );
I wonder whether we would need to see liveness at log_level=2 during the normal verifier output instead of once in a beginning. I guess it's fine doing it once like you did.
Quoted 81 lines
kernel/bpf/verifier.c +22
-0+verbose (env," " ); +verbose_insn (env, &insns[i]); +if (bpf_is_ldimm64 (&insns[i])) + i++; + } + } + +out: +kvfree (state); +kvfree (env->cfg.insn_postorder); + env->cfg.insn_postorder =NULL ; + env->cfg.cur_postorder =0 ; +return err; +} +int bpf_check (struct bpf_prog **prog,union bpf_attr *attr,bpfptr_t uattr,__u32 uattr_size) {u64 start_time =ktime_get_ns ();@@ -23320,6 +23643,12 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3if (ret) goto skip_full_check; +if (is_priv) { + ret =compute_live_registers (env); +if (ret <0 ) + goto skip_full_check; + } + ret =mark_fastcall_patterns (env);if (ret <0 ) goto skip_full_check;@@ -23458,6 +23787,7 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3vfree (env->insn_aux_data);kvfree (env->insn_hist); err_free_env: +kvfree (env->cfg.insn_postorder);kvfree (env);return ret; }tools/testing/selftests/bpf/prog_tests/align.c +10
-2@@ -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); } --2.48.1
Eduard Zingerman
maintainerQuoted 1 line · Alexei Starovoitov
On Thu, Feb 27, 2025 at 10:01 PM Eduard Zingerman <[email protected]> wrote:
[...]
Quoted 4 lines
Quoted 4 lines
kernel/bpf/verifier.c +0
-0@@ -3379,10 +3388,7 @@ static int check_subprogs(struct bpf_verifier_env *env) goto next;if (BPF_OP (code) ==BPF_EXIT ||BPF_OP (code) ==BPF_CALL ) goto next;
Quoted 8 lines
kernel/bpf/verifier.c static int check_subprogs(struct bpf_verifier_env *env) · line 3391
Quoted 5 lines
kernel/bpf/verifier.c +1
-4-if (code == (BPF_JMP32 |BPF_JA )) - off = i + insn[i].imm +1 ; -else - off = i + insn[i].off +1 ; + off = i +jmp_offset (&insn[i]) +1 ;Nice cleanup, but pls split it into pre-patch,
so that main liveness logic is in the main patch.
Thanks for the feedback.
I'll include all requested changes in v2.
[...]
Eduard Zingerman
maintainerPATCH 2/3 bpf: use register liveness information for func_states_equal
In reply to Eduard ZingermanLiveness 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%)
--- include/linux/bpf_verifier.h | 1 + kernel/bpf/verifier.c | 18 ++++++++++++++---- 2 files changed, 15 insertions(+), 4 deletions(-)
include/linux/bpf_verifier.h +1 -0
@@ -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;
kernel/bpf/verifier.c +14 -4
@@ -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);
Signature · 1 line
2.48.1
Eduard Zingerman
maintainerPATCH 3/3 selftests/bpf: test cases for compute_live_registers()
In reply to Eduard ZingermanCover 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 | 397 ++++++++++++++++++ .../selftests/bpf/progs/verifier_gotol.c | 6 +- .../bpf/progs/verifier_iterating_callbacks.c | 6 +- 5 files changed, 420 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
@@ -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
@@ -213,4 +213,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 +397 -0
397 lines not on this page · raw message
tools/testing/selftests/bpf/progs/verifier_gotol.c +1 -5
@@ -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
@@ -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.48.1
Quoted 11 lines · Eduard Zingerman
This patch set introduces a simple live register DFA analysis. The analysis is performed as a separate step before the main verification pass, and results are stored in
env->insn_aux_datafor each instruction.This change improves handling of iterator/callback-based loops, as regular register liveness marks are not finalized while loops are being processed. See veristat results for selftests and
sched_extin patch #2.
Quoted 4 lines
The patch set was tested in branch [1] by disabling the current register parentage chain liveness computation, using DFA-based liveness for registers while assuming all stack slots as live. No notable regressions were found in test_progs-based tests.
I think the end goal is to get rid of mark_reg_read() and switch to proper live reg analysis.
So please include the numbers to see how much work left.
Also note that mark_reg_read() tracks 32 vs 64 reads separately. iirc we did it to support fine grain mark_insn_zext
to help architectures where zext has to be inserted by JIT. I'm not sure whether new liveness has to do it as well.
Eduard Zingerman
maintainerOn Fri, 2025-02-28 at 18:10 -0800, Alexei Starovoitov wrote:
[...]
Quoted 3 lines
I think the end goal is to get rid of
mark_reg_read()and switch to proper live reg analysis.
So please include the numbers to see how much work left.
Complete removal of mark_reg_read() means that analysis needs to be done for stack slots as well. The algorithm to handle stack slots is much more complicated:
- it needs to track register / stack slot type to handle cases like "r1 = r10" and spills of the stack pointer to stack;
- it needs to track register values, at-least crudely, to handle cases like "r1 = r10; r1 += r2;" (array access).
The worst case scenario, as you suggested, is just to assume stack slots live, but it is a big verification performance hit. Exact numbers are at the end of the email.
Quoted 4 lines
Also note that
mark_reg_read()tracks 32 vs 64 reads separately. iirc we did it to support fine grainmark_insn_zext
to help architectures where zext has to be inserted by JIT. I'm not sure whether new liveness has to do it as well.
As far as I understand, this is important for one check in propagate_liveness(). And that check means something like:
"if this register was read as 64-bit value, remember that
it needs zero extension on 32-bit load".
Meaning that either DFA would need to track this bit of information (should be simple), or more zero extensions would be added.
---
Repository [1] shared in cover letter was used for benchmarks below. Abbreviations are as follows:
- Name: dfa-opts
Commit: b73005452a4a
Meaning: DFA as shared in this patch-set + a set of small
improvements which I decided to exclude from the patch-set as described in the cover letter.
- Name: dfa-opts-no-rm
Commit: e486757fdada
Meaning: dfa-opts + read marks are disabled for registers.
- Name: dfa-opts-no-rm-sl
Commit: a9930e8127a9
Meaning: dfa-opts + read marks are disabled for registers
and stack.
[1] https://github.com/eddyz87/bpf/tree/liveregs-dfa-std-liveregs-off
Veristat output is filtered using -f "states_pct>5" -f "!insns<200". Veristat results are followed by a histogram that accounts for all tests.
Two comparisons are made:
- dfa-opts vs dfa-opts-no-rm (small negative impact, except two sched_ext programs that hit 1M instructions limit; positive impact would have indicated a bug);
- dfa-opts vs dfa-opts-no-rm-sl (big negative impact).
========= selftests: dfa-opts vs dfa-opts-no-rm =========
File Program States (A) States (B) States (DIFF) ------------------------ ---------------- ---------- ---------- ------------- test_l4lb_noinline.bpf.o balancer_ingress 219 231 +12 (+5.48%)
Total progs: 3565 Old success: 2054 New success: 2054 States diff min: 0.00% States diff max: 5.48%
0% .. 5%: 3564
5% .. 10%: 1
========= scx: dfa-opts vs dfa-opts-no-rm =========
File Program States (A) States (B) States (DIFF) --------- --------------- ---------- ---------- ------------------ bpf.bpf.o rusty_init 1944 55004 +53060 (+2729.42%) bpf.bpf.o rusty_init_task 1732 55049 +53317 (+3078.35%)
Total progs: 216
Old success: 186
New success: 184
States diff min: 0.00%
States diff max: 3078.35%
0% .. 5%: 214
2725% .. 3080%: 2
========= selftests: dfa-opts vs dfa-opts-no-rm-sl =========
File Program States (A) States (B) States (DIFF) -------------------------------- ------------------------------------ ---------- ---------- ----------------- arena_htab_asm.bpf.o arena_htab_asm 33 40 +7 (+21.21%) bpf_cubic.bpf.o bpf_cubic_cong_avoid 92 98 +6 (+6.52%) bpf_flow.bpf.o flow_dissector_0 66 125 +59 (+89.39%) bpf_iter_ksym.bpf.o dump_ksym 16 21 +5 (+31.25%) profiler1.bpf.o kprobe__proc_sys_write 84 140 +56 (+66.67%) profiler1.bpf.o kprobe__vfs_link 504 543 +39 (+7.74%) profiler1.bpf.o kprobe__vfs_symlink 238 466 +228 (+95.80%) profiler1.bpf.o kprobe_ret__do_filp_open 247 274 +27 (+10.93%) profiler1.bpf.o raw_tracepoint__sched_process_exec 139 350 +211 (+151.80%) profiler1.bpf.o raw_tracepoint__sched_process_exit 67 86 +19 (+28.36%) profiler1.bpf.o tracepoint__syscalls__sys_enter_kill 649 758 +109 (+16.80%) profiler2.bpf.o kprobe__vfs_link 149 257 +108 (+72.48%) profiler2.bpf.o kprobe_ret__do_filp_open 106 120 +14 (+13.21%) profiler2.bpf.o raw_tracepoint__sched_process_exec 126 140 +14 (+11.11%) profiler3.bpf.o kprobe__vfs_link 805 1182 +377 (+46.83%) pyperf180.bpf.o on_event 10564 17659 +7095 (+67.16%) pyperf50.bpf.o on_event 2489 3375 +886 (+35.60%) pyperf600_iter.bpf.o on_event 192 214 +22 (+11.46%) pyperf_subprogs.bpf.o on_event 2331 2514 +183 (+7.85%) setget_sockopt.bpf.o skops_sockopt 429 458 +29 (+6.76%) setget_sockopt.bpf.o socket_post_create 90 95 +5 (+5.56%) sock_iter_batch.bpf.o iter_tcp_soreuse 3 5 +2 (+66.67%) strobemeta_bpf_loop.bpf.o on_event 209 331 +122 (+58.37%) test_bpf_nf.bpf.o nf_skb_ct_test 41 56 +15 (+36.59%) test_bpf_nf.bpf.o nf_xdp_ct_test 41 56 +15 (+36.59%) test_cls_redirect.bpf.o cls_redirect 2175 14083 +11908 (+547.49%) test_cls_redirect_dynptr.bpf.o cls_redirect 220 327 +107 (+48.64%) test_cls_redirect_subprogs.bpf.o cls_redirect 4390 17001 +12611 (+287.27%) test_l4lb.bpf.o balancer_ingress 137 256 +119 (+86.86%) test_l4lb_noinline.bpf.o balancer_ingress 219 643 +424 (+193.61%) test_l4lb_noinline_dynptr.bpf.o balancer_ingress 73 182 +109 (+149.32%) test_misc_tcp_hdr_options.bpf.o misc_estab 88 98 +10 (+11.36%) test_pkt_access.bpf.o test_pkt_access 21 25 +4 (+19.05%) test_sock_fields.bpf.o egress_read_sock_fields 20 29 +9 (+45.00%) test_tc_neigh_fib.bpf.o tc_dst 12 14 +2 (+16.67%) test_tc_neigh_fib.bpf.o tc_src 12 14 +2 (+16.67%) test_tcp_custom_syncookie.bpf.o tcp_custom_syncookie 420 560 +140 (+33.33%) test_tcp_hdr_options.bpf.o estab 189 225 +36 (+19.05%) test_xdp.bpf.o _xdp_tx_iptunnel 17 18 +1 (+5.88%) test_xdp_dynptr.bpf.o _xdp_tx_iptunnel 26 36 +10 (+38.46%) test_xdp_loop.bpf.o _xdp_tx_iptunnel 19 20 +1 (+5.26%) test_xdp_noinline.bpf.o balancer_ingress_v4 271 1080 +809 (+298.52%) test_xdp_noinline.bpf.o balancer_ingress_v6 268 1030 +762 (+284.33%) xdp_features.bpf.o xdp_do_tx 10 13 +3 (+30.00%) xdp_synproxy_kern.bpf.o syncookie_tc 390 467 +77 (+19.74%) xdp_synproxy_kern.bpf.o syncookie_xdp 384 450 +66 (+17.19%)
Total progs: 3565 Old success: 2054 New success: 2054 States diff min: -9.09% States diff max: 547.49% -10% .. 0%: 3 0% .. 5%: 3492 5% .. 10%: 10 10% .. 15%: 8 15% .. 20%: 10 20% .. 25%: 6 25% .. 35%: 8 35% .. 40%: 4 45% .. 50%: 3 50% .. 55%: 4 55% .. 70%: 4 70% .. 90%: 3 95% .. 105%: 3 145% .. 195%: 3 280% .. 300%: 3 545% .. 550%: 1
========= scx: dfa-opts vs dfa-opts-no-rm-sl =========
File Program States (A) States (B) States (DIFF) -------------- ------------------ ---------- ---------- ------------------ bpf.bpf.o bpfland_enqueue 18 20 +2 (+11.11%) bpf.bpf.o bpfland_select_cpu 83 103 +20 (+24.10%) bpf.bpf.o flash_select_cpu 30 49 +19 (+63.33%) bpf.bpf.o lavd_cpu_offline 303 360 +57 (+18.81%) bpf.bpf.o lavd_cpu_online 303 360 +57 (+18.81%) bpf.bpf.o lavd_dispatch 7065 10652 +3587 (+50.77%) bpf.bpf.o lavd_init 480 554 +74 (+15.42%) bpf.bpf.o lavd_running 89 94 +5 (+5.62%) bpf.bpf.o lavd_select_cpu 451 483 +32 (+7.10%) bpf.bpf.o layered_dispatch 501 950 +449 (+89.62%) bpf.bpf.o layered_dump 237 258 +21 (+8.86%) bpf.bpf.o layered_enqueue 1290 1655 +365 (+28.29%) bpf.bpf.o layered_init 423 552 +129 (+30.50%) bpf.bpf.o layered_select_cpu 201 311 +110 (+54.73%) bpf.bpf.o p2dq_dispatch 53 116 +63 (+118.87%) bpf.bpf.o rusty_init 1944 55006 +53062 (+2729.53%) bpf.bpf.o rusty_init_task 1732 55052 +53320 (+3078.52%) bpf.bpf.o rusty_running 19 23 +4 (+21.05%) bpf.bpf.o rusty_select_cpu 108 227 +119 (+110.19%) bpf.bpf.o rusty_set_cpumask 313 479 +166 (+53.04%) scx_nest.bpf.o nest_select_cpu 49 53 +4 (+8.16%)
Total progs: 216
Old success: 186
New success: 184
States diff min: 0.00%
States diff max: 3078.52%
0% .. 5%: 186
5% .. 10%: 4 10% .. 15%: 5 15% .. 20%: 6 20% .. 25%: 3 25% .. 55%: 6
60% .. 115%: 3
115% .. 3080%: 3
Quoted 9 lines · Eduard Zingerman
On Fri, 2025-02-28 at 18:10 -0800, Alexei Starovoitov wrote:
[...]
Quoted 3 lines
I think the end goal is to get rid of
mark_reg_read()and switch to proper live reg analysis.
So please include the numbers to see how much work left.
Quoted 7 lines
Complete removal of
mark_reg_read()means that analysis needs to be done for stack slots as well. The algorithm to handle stack slots is much more complicated:
- it needs to track register / stack slot type to handle cases like "r1 = r10" and spills of the stack pointer to stack;
- it needs to track register values, at-least crudely, to handle cases like "r1 = r10; r1 += r2;" (array access).
Doing this kind of register movement tracking before do_check() may be difficult indeed.
Can we do this use/def tracking inline similar to current liveness, but without ->parent logic.
Using postorder array that this patch adds ?
verifier states are path sensitive and more accurate while this one will be insn based, but maybe good enough ?
Quoted 9 lines
The worst case scenario, as you suggested, is just to assume stack slots live, but it is a big verification performance hit. Exact numbers are at the end of the email.
Quoted 4 lines
Also note that
mark_reg_read()tracks 32 vs 64 reads separately. iirc we did it to support fine grainmark_insn_zext
to help architectures where zext has to be inserted by JIT. I'm not sure whether new liveness has to do it as well.
Quoted 7 lines
As far as I understand, this is important for one check in
propagate_liveness(). And that check means something like:
"if this register was read as 64-bit value, remember that
it needs zero extension on 32-bit load".Meaning that either DFA would need to track this bit of information (should be simple), or more zero extensions would be added.
Right. New liveness doesn't break zext, but makes it worse for arch that needs it. We would need to quantify the impact. iirc it was noticeable enough that we added this support.
Quoted 20 lines
---
Repository [1] shared in cover letter was used for benchmarks below. Abbreviations are as follows:
- Name: dfa-opts
Commit:b73005452a4a
Meaning: DFA as shared in this patch-set + a set of small
improvements which I decided to exclude from the patch-set as described in the cover letter.
- Name: dfa-opts-no-rm
Commit:e486757fdada
Meaning: dfa-opts + read marks are disabled for registers.
- Name: dfa-opts-no-rm-sl
Commit:a9930e8127a9
Meaning: dfa-opts + read marks are disabled for registers
and stack.[1] https://github.com/eddyz87/bpf/tree/liveregs-dfa-std-liveregs-off
Quoted 8 lines
Veristat output is filtered using -f "states_pct>5" -f "!insns<200". Veristat results are followed by a histogram that accounts for all tests.
Two comparisons are made:
- dfa-opts vs dfa-opts-no-rm (small negative impact, except twosched_extprograms that hit 1M instructions limit; positive impact would have indicated a bug);
Let's figure out what is causing rusty_init[_task] to explode.
And proceed with this set in parallel.
Quoted 1 line
- dfa-opts vs dfa-opts-no-rm-sl (big negative impact).
I don't read it as a big negative.cls_redirect and balancer_ingress need to be understood, but nothing exploded to hit 1M insns,
so hopefully bare minimum stack tracking would do the trick.
So in terms of priorities, let's land this set, then figure out rusty_init,
figure out read32 vs 64 for zext,
at that time we may land -no-rm.
Then stack tracking.
Eduard Zingerman
maintainerQuoted 1 line · Alexei Starovoitov
On Fri, Feb 28, 2025 at 8:40 PM Eduard Zingerman <[email protected]> wrote:
[...]
Quoted 8 lines
Quoted 7 lines
Complete removal of
mark_reg_read()means that analysis needs to be done for stack slots as well. The algorithm to handle stack slots is much more complicated:
- it needs to track register / stack slot type to handle cases like "r1 = r10" and spills of the stack pointer to stack;
- it needs to track register values, at-least crudely, to handle cases like "r1 = r10; r1 += r2;" (array access).
Quoted 7 lines
Doing this kind of register movement tracking before
do_check()may be difficult indeed.
Can we do this use/def tracking inline similar to current liveness, but without ->parent logic.
Using postorder array that this patch adds ?
verifier states are path sensitive and more accurate while this one will be insn based, but maybe good enough ?
You mean act like precision tracking? Whenever instruction is verified and use is recorded propagate this use upwards in execution path, updating live-in/live-out sets for instructions?
The problem here is termination (when to consider live-in/live-out sets final). DFA computation stops as soon as live-in/live-out marks stop changing. Idk how this condition should look for the scheme above.
[...]
Quoted 10 lines
Quoted 10 lines
Quoted 4 lines
Also note that
mark_reg_read()tracks 32 vs 64 reads separately. iirc we did it to support fine grainmark_insn_zext
to help architectures where zext has to be inserted by JIT. I'm not sure whether new liveness has to do it as well.As far as I understand, this is important for one check in
propagate_liveness(). And that check means something like:
"if this register was read as 64-bit value, remember that
it needs zero extension on 32-bit load".
Quoted 6 lines
Quoted 2 lines
Meaning that either DFA would need to track this bit of information (should be simple), or more zero extensions would be added.
Right. New liveness doesn't break zext, but makes it worse for arch that needs it. We would need to quantify the impact. iirc it was noticeable enough that we added this support.
I'm surprised that no test_progs or test_verifier tests a broken. Agree that this needs to be quantified.
[...]
Quoted 8 lines
Quoted 4 lines
Two comparisons are made:
- dfa-opts vs dfa-opts-no-rm (small negative impact, except twosched_extprograms that hit 1M instructions limit; positive impact would have indicated a bug);Let's figure out what is causing rusty_init[_task] to explode.
And proceed with this set in parallel.
Will do.
Quoted 7 lines
Quoted 1 line
- dfa-opts vs dfa-opts-no-rm-sl (big negative impact).
I don't read it as a big negative.
cls_redirectandbalancer_ingressneed to be understood, but nothing exploded to hit 1M insns,
so hopefully bare minimum stack tracking would do the trick.
Quoted 5 lines
So in terms of priorities, let's land this set, then figure out
rusty_init,
figure out read32 vs 64 for zext,
at that time we may land -no-rm.
Then stack tracking.
Tbh, I think that landing dfa-opts-no-rm separately from dfa-opts-no-rm-sl doesn't make things much simpler.
The register chain based liveness computation would still be a thing. I'd try to figure out how to make the dfa-opts-no-rm-sl variant faster first.
Eduard Zingerman
maintainerQuoted 1 line · Alexei Starovoitov
On Fri, Feb 28, 2025 at 8:40 PM Eduard Zingerman <[email protected]> wrote:
[...]
Quoted 8 lines
Quoted 4 lines
Two comparisons are made:
- dfa-opts vs dfa-opts-no-rm (small negative impact, except twosched_extprograms that hit 1M instructions limit; positive impact would have indicated a bug);Let's figure out what is causing rusty_init[_task] to explode.
And proceed with this set in parallel.
The regression for rusty_init was caused by incorrect mark of "r0" as used because of "may_goto" instruction. This is fixed by:
https://lore.kernel.org/bpf/[email protected]/
Quoted 12 lines
Quoted 1 line
- dfa-opts vs dfa-opts-no-rm-sl (big negative impact).
I don't read it as a big negative.
cls_redirectandbalancer_ingressneed to be understood, but nothing exploded to hit 1M insns,
so hopefully bare minimum stack tracking would do the trick.So in terms of priorities, let's land this set, then figure out
rusty_init,
figure out read32 vs 64 for zext,
at that time we may land -no-rm.
Then stack tracking.