Skip to contentSkip to conversation

bpf: simple DFA-based live registers analysis

PATCH Superseded Eduard Zingerman 2 participants 11 messages Feb 28, 2025 – Mar 5, 2025

Subsystems (4)

v1 of 3 Superseded Latest is v3 →

lore
Share & tools
lore

Eduard Zingerman

author maintainer
#0 lore raw

cover 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
author maintainer
#1 lore raw

PATCH 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
index bbd013c38ff9..8c23958bc471 100644
@@ -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
index 4ebd0da898f5..1d53a8561ee2 100644
@@ -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
#2 lore raw
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 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
index bbd013c38ff9..8c23958bc471 100644
@@ -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
index dcd0da4e62fc..4ac7dc58d9b1 100644
@@ -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 -5
                if (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, __u3
        if (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, __u3
        vfree(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
index 4ebd0da898f5..1d53a8561ee2 100644
@@ -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

author maintainer
#3 lore raw
Quoted 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.

[...]

author maintainer
#4 lore raw

PATCH 2/3 bpf: use register liveness information for func_states_equal

In reply to Eduard Zingerman

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%)
---
 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
index 8c23958bc471..39097835b326 100644
@@ -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
index 4ac7dc58d9b1..b6ab49ee31e1 100644
@@ -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
author maintainer
#5 lore raw

PATCH 3/3 selftests/bpf: test cases for compute_live_registers()

In reply to Eduard Zingerman

Cover 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
new file mode 100644
index 000000000000..285f20241fe1
@@ -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
index 34f555da546f..e12e74e7e66e 100644
@@ -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
index 05a329ee45ee..d5d8f24df394 100644
@@ -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
index e54bb5385bc1..75dd922e4e9f 100644
@@ -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
#6 lore raw
In reply to Eduard Zingerman
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_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.

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.

author maintainer
#7 lore raw

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.

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 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.

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

#8 lore raw
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 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.

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 two sched_ext programs 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.

author maintainer
#9 lore raw
Quoted 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 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.

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 two sched_ext programs 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_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.

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.

author maintainer
#10 lore raw
In reply to Alexei Starovoitov
Quoted 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 two sched_ext programs 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_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.