From: Alexei Starovoitov A prerequisite of the removal of scalar ids. flow_join_makes_up() is the last code that learns something about the prog from them: which registers and stack slots hold copies of a scalar. Recognize the copies by their ranges. The function is a heuristic that decides which states are joined. So this patch is about the number of states. Soundness does not depend on it. err = update(); ret = err < 0 ? DROP : 0; .. if (err < 0) goto out; .. if (ret < 0) .. The states (err >= 0, ret = 0) and (err < 0, ret = DROP) get to a join point before the jumps. Their join loses the correlation of err and ret: it has err < 0 with ret = 0. So two states stay apart if two scalars that later jumps test each have disjoint ranges in the two states, as err and ret do. Copies of a scalar are treated as one scalar there. A jump that tests one of them refines the others, so their join makes up nothing, and compilers keep a value in a register and in stack slots at the same time. Copies are recognized by their id, in one of the two states: if (one && (!id || id != (ra->id & ~BPF_ADD_CONST))) return true; If every copy is a scalar of its own, too many states stay apart. The init prog of a sched_ext scheduler in Rust goes from 36 to 512 states at one insn and takes twice as long to load. At 512 flow_has_room() is false, and states are joined by force. Copies have the same range and tnum, in each of the two states. Treat scalars with that property as copies. Two scalars that are not copies can have it too. Then two states are joined that stayed apart. veristat over the selftests, Cilium, sched_ext, katran, bpfjailer and programs in Rust: no verdict changes, 199 of 32913 progs move, by 0.01 % of the insns in all. The scheduler stays at 36 states. Signed-off-by: Alexei Starovoitov --- kernel/bpf/flow.c | 13 ++++++------- 1 file changed, 6 insertions(+), 7 deletions(-) diff --git a/kernel/bpf/flow.c b/kernel/bpf/flow.c index c9458b3ad114..778288acb5ba 100644 --- a/kernel/bpf/flow.c +++ b/kernel/bpf/flow.c @@ -2603,10 +2603,9 @@ static bool flow_join_makes_up(const struct bpf_flow *flow, struct bpf_verifier_ struct bpf_verifier_state *b) { struct bpf_func_state *fa = a->frame[a->curframe], *fb = b->frame[b->curframe]; - const struct bpf_reg_state *ra, *rb; + const struct bpf_reg_state *ra, *rb, *one_a = NULL, *one_b = NULL; const struct flow_need *tested = flow->need[FLOW_NEED_JUMP], *need; - u32 fr, i, id = 0; - bool one = false; + u32 fr, i, len = offsetof(struct bpf_reg_state, id); if (!tested) return false; @@ -2623,11 +2622,11 @@ static bool flow_join_makes_up(const struct bpf_flow *flow, struct bpf_verifier_ continue; if (flow_gap(ra, rb)) return true; - /* copies of a number are one number */ - if (one && (!id || id != (ra->id & ~BPF_ADD_CONST))) + /* copies of a scalar count once: same range and tnum in each state */ + if (one_a && (memcmp(ra, one_a, len) || memcmp(rb, one_b, len))) return true; - one = true; - id = ra->id & ~BPF_ADD_CONST; + one_a = ra; + one_b = rb; } } if (!flow_needed_consts_differ(flow, FLOW_NEED_FLAG, a, b)) -- 2.55.0