On Tue, Dec 06, 2022 at 03:09:55PM -0800, Dave Marchevsky wrote:
> Some BPF helpers take a callback function which the helper calls. For
> each helper that takes such a callback, there's a special call to
> __check_func_call with a callback-state-setting callback that sets up
> verifier bpf_func_state for the callback's frame.
>
> kfuncs don't have any of this infrastructure yet, so let's add it in
> this patch, following existing helper pattern as much as possible. To
> validate functionality of this added plumbing, this patch adds
> callback handling for the bpf_rbtree_add kfunc and hopes to lay
> groundwork for future next-gen datastructure callbacks.
>
> In the "general plumbing" category we have:
>
> * check_kfunc_call doing callback verification right before clearing
> CALLER_SAVED_REGS, exactly like check_helper_call
> * recognition of func_ptr BTF types in kfunc args as
> KF_ARG_PTR_TO_CALLBACK + propagation of subprogno for this arg type
>
> In the "rbtree_add / next-gen datastructure-specific plumbing" category:
>
> * Since bpf_rbtree_add must be called while the spin_lock associated
> with the tree is held, don't complain when callback's func_state
> doesn't unlock it by frame exit
> * Mark rbtree_add callback's args PTR_UNTRUSTED to prevent rbtree
> api functions from being called in the callback
>
> Signed-off-by: Dave Marchevsky <davemarchevsky@xxxxxx>
> ---
> kernel/bpf/verifier.c | 136 ++++++++++++++++++++++++++++++++++++++++--
> 1 file changed, 130 insertions(+), 6 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 652112007b2c..9ad8c0b264dc 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -1448,6 +1448,16 @@ static void mark_ptr_not_null_reg(struct bpf_reg_state *reg)
> reg->type &= ~PTR_MAYBE_NULL;
> }
>
> +static void mark_reg_datastructure_node(struct bpf_reg_state *regs, u32 regno,
> + struct btf_field_datastructure_head *ds_head)
> +{
> + __mark_reg_known_zero(®s[regno]);
> + regs[regno].type = PTR_TO_BTF_ID | MEM_ALLOC;
> + regs[regno].btf = ds_head->btf;
> + regs[regno].btf_id = ds_head->value_btf_id;
> + regs[regno].off = ds_head->node_offset;
> +}
> +
> static bool reg_is_pkt_pointer(const struct bpf_reg_state *reg)
> {
> return type_is_pkt_pointer(reg->type);
> @@ -4771,7 +4781,8 @@ static int check_ptr_to_btf_access(struct bpf_verifier_env *env,
> return -EACCES;
> }
>
> - if (type_is_alloc(reg->type) && !reg->ref_obj_id) {
> + if (type_is_alloc(reg->type) && !reg->ref_obj_id &&
> + !cur_func(env)->in_callback_fn) {
> verbose(env, "verifier internal error: ref_obj_id for allocated object must be non-zero\n");
> return -EFAULT;
> }
> @@ -6952,6 +6963,8 @@ static int set_callee_state(struct bpf_verifier_env *env,
> struct bpf_func_state *caller,
> struct bpf_func_state *callee, int insn_idx);
>
> +static bool is_callback_calling_kfunc(u32 btf_id);
> +
> static int __check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
> int *insn_idx, int subprog,
> set_callee_state_fn set_callee_state_cb)
> @@ -7006,10 +7019,18 @@ static int __check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn
> * interested in validating only BPF helpers that can call subprogs as
> * callbacks
> */
> - if (set_callee_state_cb != set_callee_state && !is_callback_calling_function(insn->imm)) {
> - verbose(env, "verifier bug: helper %s#%d is not marked as callback-calling\n",
> - func_id_name(insn->imm), insn->imm);
> - return -EFAULT;
> + if (set_callee_state_cb != set_callee_state) {
> + if (bpf_pseudo_kfunc_call(insn) &&
> + !is_callback_calling_kfunc(insn->imm)) {
> + verbose(env, "verifier bug: kfunc %s#%d not marked as callback-calling\n",
> + func_id_name(insn->imm), insn->imm);
> + return -EFAULT;
> + } else if (!bpf_pseudo_kfunc_call(insn) &&
> + !is_callback_calling_function(insn->imm)) { /* helper */
> + verbose(env, "verifier bug: helper %s#%d not marked as callback-calling\n",
> + func_id_name(insn->imm), insn->imm);
> + return -EFAULT;
> + }
> }
>
> if (insn->code == (BPF_JMP | BPF_CALL) &&
> @@ -7275,6 +7296,67 @@ static int set_user_ringbuf_callback_state(struct bpf_verifier_env *env,
> return 0;
> }
>
> +static int set_rbtree_add_callback_state(struct bpf_verifier_env *env,
> + struct bpf_func_state *caller,
> + struct bpf_func_state *callee,
> + int insn_idx)
> +{
> + /* void bpf_rbtree_add(struct bpf_rb_root *root, struct bpf_rb_node *node,
> + * bool (less)(struct bpf_rb_node *a, const struct bpf_rb_node *b));
> + *
> + * 'struct bpf_rb_node *node' arg to bpf_rbtree_add is the same PTR_TO_BTF_ID w/ offset
> + * that 'less' callback args will be receiving. However, 'node' arg was release_reference'd
> + * by this point, so look at 'root'
> + */
> + struct btf_field *field;
> + struct btf_record *rec;
> +
> + rec = reg_btf_record(&caller->regs[BPF_REG_1]);
> + if (!rec)
> + return -EFAULT;
> +
> + field = btf_record_find(rec, caller->regs[BPF_REG_1].off, BPF_RB_ROOT);
> + if (!field || !field->datastructure_head.value_btf_id)
> + return -EFAULT;
> +
> + mark_reg_datastructure_node(callee->regs, BPF_REG_1, &field->datastructure_head);
> + callee->regs[BPF_REG_1].type |= PTR_UNTRUSTED;
> + mark_reg_datastructure_node(callee->regs, BPF_REG_2, &field->datastructure_head);
> + callee->regs[BPF_REG_2].type |= PTR_UNTRUSTED;
Please add a comment here to explain that the pointers are actually trusted
and here it's a quick hack to prevent callback to call into rb_tree kfuncs.
We definitely would need to clean it up.
Have you tried to check for is_bpf_list_api_kfunc() || is_bpf_rbtree_api_kfunc()
while processing kfuncs inside callback ?
> + callee->in_callback_fn = true;
this will give you a flag to do that check.
> + callee->callback_ret_range = tnum_range(0, 1);
> + return 0;
> +}
> +
> +static bool is_rbtree_lock_required_kfunc(u32 btf_id);
> +
> +/* Are we currently verifying the callback for a rbtree helper that must
> + * be called with lock held? If so, no need to complain about unreleased
> + * lock
> + */
> +static bool in_rbtree_lock_required_cb(struct bpf_verifier_env *env)
> +{
> + struct bpf_verifier_state *state = env->cur_state;
> + struct bpf_insn *insn = env->prog->insnsi;
> + struct bpf_func_state *callee;
> + int kfunc_btf_id;
> +
> + if (!state->curframe)
> + return false;
> +
> + callee = state->frame[state->curframe];
> +
> + if (!callee->in_callback_fn)
> + return false;
> +
> + kfunc_btf_id = insn[callee->callsite].imm;
> + return is_rbtree_lock_required_kfunc(kfunc_btf_id);
> +}
> +
> static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx)
> {
> struct bpf_verifier_state *state = env->cur_state;
> @@ -8007,6 +8089,7 @@ struct bpf_kfunc_call_arg_meta {
> bool r0_rdonly;
> u32 ret_btf_id;
> u64 r0_size;
> + u32 subprogno;
> struct {
> u64 value;
> bool found;
> @@ -8185,6 +8268,18 @@ static bool is_kfunc_arg_rbtree_node(const struct btf *btf, const struct btf_par
> return __is_kfunc_ptr_arg_type(btf, arg, KF_ARG_RB_NODE_ID);
> }
>
> +static bool is_kfunc_arg_callback(struct bpf_verifier_env *env, const struct btf *btf,
> + const struct btf_param *arg)
> +{
> + const struct btf_type *t;
> +
> + t = btf_type_resolve_func_ptr(btf, arg->type, NULL);
> + if (!t)
> + return false;
> +
> + return true;
> +}
> +
> /* Returns true if struct is composed of scalars, 4 levels of nesting allowed */
> static bool __btf_type_is_scalar_struct(struct bpf_verifier_env *env,
> const struct btf *btf,
> @@ -8244,6 +8339,7 @@ enum kfunc_ptr_arg_type {
> KF_ARG_PTR_TO_BTF_ID, /* Also covers reg2btf_ids conversions */
> KF_ARG_PTR_TO_MEM,
> KF_ARG_PTR_TO_MEM_SIZE, /* Size derived from next argument, skip it */
> + KF_ARG_PTR_TO_CALLBACK,
> KF_ARG_PTR_TO_RB_ROOT,
> KF_ARG_PTR_TO_RB_NODE,
> };
> @@ -8368,6 +8464,9 @@ get_kfunc_ptr_arg_type(struct bpf_verifier_env *env,
> return KF_ARG_PTR_TO_BTF_ID;
> }
>
> + if (is_kfunc_arg_callback(env, meta->btf, &args[argno]))
> + return KF_ARG_PTR_TO_CALLBACK;
> +
> if (argno + 1 < nargs && is_kfunc_arg_mem_size(meta->btf, &args[argno + 1], ®s[regno + 1]))
> arg_mem_size = true;
>
> @@ -8585,6 +8684,16 @@ static bool is_bpf_datastructure_api_kfunc(u32 btf_id)
> return is_bpf_list_api_kfunc(btf_id) || is_bpf_rbtree_api_kfunc(btf_id);
> }
>
> +static bool is_callback_calling_kfunc(u32 btf_id)
> +{
> + return btf_id == special_kfunc_list[KF_bpf_rbtree_add];
> +}
> +
> +static bool is_rbtree_lock_required_kfunc(u32 btf_id)
> +{
> + return is_bpf_rbtree_api_kfunc(btf_id);
> +}
> +
> static bool check_kfunc_is_datastructure_head_api(struct bpf_verifier_env *env,
> enum btf_field_type head_field_type,
> u32 kfunc_btf_id)
> @@ -8920,6 +9029,7 @@ static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_
> case KF_ARG_PTR_TO_RB_NODE:
> case KF_ARG_PTR_TO_MEM:
> case KF_ARG_PTR_TO_MEM_SIZE:
> + case KF_ARG_PTR_TO_CALLBACK:
> /* Trusted by default */
> break;
> default:
> @@ -9078,6 +9188,9 @@ static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_
> /* Skip next '__sz' argument */
> i++;
> break;
> + case KF_ARG_PTR_TO_CALLBACK:
> + meta->subprogno = reg->subprogno;
> + break;
> }
> }
>
> @@ -9193,6 +9306,16 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
> }
> }
>
> + if (meta.func_id == special_kfunc_list[KF_bpf_rbtree_add]) {
> + err = __check_func_call(env, insn, insn_idx_p, meta.subprogno,
> + set_rbtree_add_callback_state);
> + if (err) {
> + verbose(env, "kfunc %s#%d failed callback verification\n",
> + func_name, func_id);
> + return err;
> + }
> + }
> +
> for (i = 0; i < CALLER_SAVED_REGS; i++)
> mark_reg_not_init(env, regs, caller_saved[i]);
>
> @@ -14023,7 +14146,8 @@ static int do_check(struct bpf_verifier_env *env)
> return -EINVAL;
> }
>
> - if (env->cur_state->active_lock.ptr) {
> + if (env->cur_state->active_lock.ptr &&
> + !in_rbtree_lock_required_cb(env)) {
That looks wrong.
It will allow callbacks to use unpaired lock/unlock.
Have you tried clearing cur_state->active_lock when entering callback?
That should solve it and won't cause lock/unlock imbalance.
