From: Alexei Starovoitov <alexei.starovoitov@gmail.com>
To: Dave Marchevsky <davemarchevsky@fb.com>
Cc: bpf@vger.kernel.org, Alexei Starovoitov <ast@kernel.org>,
Daniel Borkmann <daniel@iogearbox.net>,
Andrii Nakryiko <andrii@kernel.org>,
Kernel Team <kernel-team@fb.com>,
Kumar Kartikeya Dwivedi <memxor@gmail.com>,
Tejun Heo <tj@kernel.org>
Subject: Re: [PATCH bpf-next 08/13] bpf: Add callback validation to kfunc verifier logic
Date: Tue, 6 Dec 2022 18:01:11 -0800 [thread overview]
Message-ID: <Y4/z54TrZgQUvc2p@macbook-pro-6.dhcp.thefacebook.com> (raw)
In-Reply-To: <20221206231000.3180914-9-davemarchevsky@fb.com>
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@fb.com>
> ---
> 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.
next prev parent reply other threads:[~2022-12-07 2:01 UTC|newest]
Thread overview: 51+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-12-06 23:09 [PATCH bpf-next 00/13] BPF rbtree next-gen datastructure Dave Marchevsky
2022-12-06 23:09 ` [PATCH bpf-next 01/13] bpf: Loosen alloc obj test in verifier's reg_btf_record Dave Marchevsky
2022-12-07 16:41 ` Kumar Kartikeya Dwivedi
2022-12-07 18:34 ` Dave Marchevsky
2022-12-07 18:59 ` Alexei Starovoitov
2022-12-07 20:38 ` Dave Marchevsky
2022-12-07 22:46 ` Alexei Starovoitov
2022-12-07 23:42 ` Dave Marchevsky
2022-12-07 19:03 ` Kumar Kartikeya Dwivedi
2022-12-06 23:09 ` [PATCH bpf-next 02/13] bpf: map_check_btf should fail if btf_parse_fields fails Dave Marchevsky
2022-12-07 1:32 ` Alexei Starovoitov
2022-12-07 16:49 ` Kumar Kartikeya Dwivedi
2022-12-07 19:05 ` Alexei Starovoitov
2022-12-17 8:59 ` Dave Marchevsky
2022-12-06 23:09 ` [PATCH bpf-next 03/13] bpf: Minor refactor of ref_set_release_on_unlock Dave Marchevsky
2022-12-06 23:09 ` [PATCH bpf-next 04/13] bpf: rename list_head -> datastructure_head in field info types Dave Marchevsky
2022-12-07 1:41 ` Alexei Starovoitov
2022-12-07 18:52 ` Dave Marchevsky
2022-12-07 19:01 ` Alexei Starovoitov
2022-12-06 23:09 ` [PATCH bpf-next 05/13] bpf: Add basic bpf_rb_{root,node} support Dave Marchevsky
2022-12-07 1:48 ` Alexei Starovoitov
2022-12-06 23:09 ` [PATCH bpf-next 06/13] bpf: Add bpf_rbtree_{add,remove,first} kfuncs Dave Marchevsky
2022-12-07 14:20 ` kernel test robot
2022-12-06 23:09 ` [PATCH bpf-next 07/13] bpf: Add support for bpf_rb_root and bpf_rb_node in kfunc args Dave Marchevsky
2022-12-07 1:51 ` Alexei Starovoitov
2022-12-06 23:09 ` [PATCH bpf-next 08/13] bpf: Add callback validation to kfunc verifier logic Dave Marchevsky
2022-12-07 2:01 ` Alexei Starovoitov [this message]
2022-12-17 8:49 ` Dave Marchevsky
2022-12-06 23:09 ` [PATCH bpf-next 09/13] bpf: Special verifier handling for bpf_rbtree_{remove, first} Dave Marchevsky
2022-12-07 2:18 ` Alexei Starovoitov
2022-12-06 23:09 ` [PATCH bpf-next 10/13] bpf, x86: BPF_PROBE_MEM handling for insn->off < 0 Dave Marchevsky
2022-12-07 2:39 ` Alexei Starovoitov
2022-12-07 6:46 ` Dave Marchevsky
2022-12-07 18:06 ` Alexei Starovoitov
2022-12-07 23:39 ` Dave Marchevsky
2022-12-08 0:47 ` Alexei Starovoitov
2022-12-08 8:50 ` Dave Marchevsky
2022-12-06 23:09 ` [PATCH bpf-next 11/13] bpf: Add bpf_rbtree_{add,remove,first} decls to bpf_experimental.h Dave Marchevsky
2022-12-06 23:09 ` [PATCH bpf-next 12/13] libbpf: Make BTF mandatory if program BTF has spin_lock or alloc_obj type Dave Marchevsky
2022-12-06 23:10 ` [PATCH bpf-next 13/13] selftests/bpf: Add rbtree selftests Dave Marchevsky
2022-12-07 2:50 ` [PATCH bpf-next 00/13] BPF rbtree next-gen datastructure patchwork-bot+netdevbpf
2022-12-07 19:36 ` Kumar Kartikeya Dwivedi
2022-12-07 22:28 ` Dave Marchevsky
2022-12-07 23:06 ` Alexei Starovoitov
2022-12-08 1:18 ` Dave Marchevsky
2022-12-08 3:51 ` Alexei Starovoitov
2022-12-08 8:28 ` Dave Marchevsky
2022-12-08 12:57 ` Kumar Kartikeya Dwivedi
2022-12-08 20:36 ` Alexei Starovoitov
2022-12-08 23:35 ` Dave Marchevsky
2022-12-09 0:39 ` Alexei Starovoitov
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=Y4/z54TrZgQUvc2p@macbook-pro-6.dhcp.thefacebook.com \
--to=alexei.starovoitov@gmail.com \
--cc=andrii@kernel.org \
--cc=ast@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=daniel@iogearbox.net \
--cc=davemarchevsky@fb.com \
--cc=kernel-team@fb.com \
--cc=memxor@gmail.com \
--cc=tj@kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.