From: Alexei Starovoitov get_some_addr() of the selftest mem_rdonly_untrusted: if (bpf_get_prandom_u32()) return bpf_rdonly_cast(0, bpf_core_type_id_kernel(struct sock)); else return bpf_rdonly_cast(0, 0); The compiler makes one call of the two, with r2 = 0 or the type id. The paths meet in front of the call, and a join makes a range of two constants: R2 must be a known constant cil_sock4_connect() and cil_sock4_sendmsg() of Cilium's bpf_sock: if (err == -EHOSTUNREACH || err == -ENOMEM) { try_set_retval(err); The compiler decides the 'if' where err is set, and keeps a flag. All paths meet, then the flag is tested. In the join err is [-113, 1]: At bpf_set_retval the register R1 has .. should have been in [-4095, 0] The progs are valid. A pass that joins states must know, ahead of a call, which registers it must not join. antistall_set() of scx_layered: bpf_for_each(scx_dsq, __p, dsq_id, 0) { bpf_iter_scx_dsq_next() ends this loop: it needs no may_goto. The pass that finds the places for may_goto must know that, before the main pass sets is_iter_next in insn_aux_data. With may_goto in each such loop layered_init and mitosis_init are rejected on the added edge, and the schedulers in tools/sched_ext take 48 % more insns. bpf_call_const_arg_regs() a helper or a kfunc takes only a known constant in these registers bpf_call_checked_arg_regs() it compares them with a range: sizes of memory, the argument of bpf_set_retval() bpf_insn_is_iter_next() the call is bpf_iter_*_next() The first two go by the types of the arguments in struct bpf_func_proto, like check_func_arg(), for r1 - r5. bpf_set_retval() is checked elsewhere and is added by hand. Nothing calls the three in this patch. Signed-off-by: Alexei Starovoitov --- include/linux/bpf_verifier.h | 3 ++ kernel/bpf/verifier.c | 62 ++++++++++++++++++++++++++++++++++++ 2 files changed, 65 insertions(+) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 922f01ee8136..7fda41a4bf25 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -1614,6 +1614,9 @@ int bpf_states_join(struct bpf_verifier_env *env, struct bpf_verifier_state *dst void bpf_join_free(struct bpf_verifier_env *env); int bpf_insert_loop_guards(struct bpf_verifier_env *env); +u16 bpf_call_const_arg_regs(struct bpf_verifier_env *env, struct bpf_insn *insn); +u16 bpf_call_checked_arg_regs(struct bpf_verifier_env *env, struct bpf_insn *insn); +bool bpf_insn_is_iter_next(struct bpf_verifier_env *env, struct bpf_insn *insn); bool bpf_edge_leaves_loop(struct bpf_verifier_env *env, int h, int n, int t); bool bpf_jump_leaves_loop(struct bpf_verifier_env *env, int h, int n); int bpf_insert_recursion_checks(struct bpf_verifier_env *env); diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 801e4607a462..ea6dd39982f2 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -9215,6 +9215,13 @@ static bool arg_type_is_mem_size(enum bpf_arg_type type) return type == ARG_MEM_SIZE || type == ARG_MEM_SIZE_OR_ZERO; } +/* A number that check_func_arg() takes only when it is a known constant */ +static bool arg_type_is_const(enum bpf_arg_type type) +{ + return type == ARG_CONST_SCALAR || type == ARG_CONST_MEM_SIZE || + type == ARG_CONST_ALLOC_SIZE_OR_ZERO; +} + static bool arg_type_is_raw_mem(enum bpf_arg_type type) { /* @@ -15379,6 +15386,61 @@ bpf_helper_stack_access_bytes(struct bpf_verifier_env *env, struct bpf_insn *ins return info; } +/* insn_aux_data->is_iter_next is not there before the main pass */ +bool bpf_insn_is_iter_next(struct bpf_verifier_env *env, struct bpf_insn *insn) +{ + struct bpf_call_arg_meta meta; + + return bpf_pseudo_kfunc_call(insn) && + !bpf_fetch_kfunc_arg_meta(env, insn->imm, insn->off, &meta) && + bpf_is_iter_next_kfunc(&meta); +} + +/* + * check_func_arg() goes by the types of the arguments in the proto of a helper or a kfunc. + * So does what has to be known ahead of the call: the registers with arguments of a kind. + */ +static u16 call_arg_regs(struct bpf_verifier_env *env, struct bpf_insn *insn, + bool (*is)(enum bpf_arg_type type)) +{ + const struct btf_func_model *fm = NULL; + const struct bpf_func_proto *fn; + struct bpf_kfunc_desc *desc; + u32 i, slot = 0; + u16 mask = 0; + + if (bpf_pseudo_kfunc_call(insn)) { + desc = find_kfunc_desc(env->prog, insn->imm, insn->off); + if (!desc) + return 0; + fn = &desc->proto; + fm = &desc->func_model; + } else if (bpf_get_helper_proto(env, insn->imm, &fn) < 0) { + return 0; + } + for (i = 0; i < ARRAY_SIZE(fn->arg_type) && fn->arg_type[i] != ARG_UNUSED && + slot < MAX_BPF_FUNC_REG_ARGS; i++) { + if (is(fn->arg_type[i])) + mask |= BIT(BPF_REG_1 + slot); + slot += fm ? btf_func_model_arg_slots(fm, i) : 1; + } + return mask; +} + +/* The registers in which the helper or the kfunc takes nothing but a known constant */ +u16 bpf_call_const_arg_regs(struct bpf_verifier_env *env, struct bpf_insn *insn) +{ + return call_arg_regs(env, insn, arg_type_is_const); +} + +/* The registers in which it takes a number that has to be in a range */ +u16 bpf_call_checked_arg_regs(struct bpf_verifier_env *env, struct bpf_insn *insn) +{ + if (bpf_helper_call(insn) && insn->imm == BPF_FUNC_set_retval) + return BIT(BPF_REG_1); + return call_arg_regs(env, insn, arg_type_is_mem_size); +} + /* * Describe a kfunc's stack access through argument slot @arg (0-based). * As for helpers, must_write describes destruction of prior verifier state, -- 2.55.0