| Message ID | 20221206231000.3180914-9-davemarchevsky@fb.com (mailing list archive) |
|---|---|
| State | Superseded |
| Delegated to: | BPF |
| Headers | show |
| Series | BPF rbtree next-gen datastructure | expand |
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.
On 12/6/22 9:01 PM, Alexei Starovoitov wrote: > 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. I didn't directly address this in v2. cur_state->active_lock isn't cleared. rbtree callback is explicitly prevented from calling spin_{lock,unlock}, and this check above is preserved so that verifier doesn't complain when cb exits w/o releasing lock. Logic for keeping it this way was: * We discussed allowing rbtree_first() call in less() cb, which requires correct lock to be held, so might as well keep lock info around * Similarly, because non-owning refs use active_lock info, need to keep info around. * Could work around both issues above, but net result would probably be _more_ special-casing, just in different places. Not trying to resurrect v1 with this comment, we can continue convo on same patch in v2: https://lore.kernel.org/bpf/20221217082506.1570898-9-davemarchevsky@fb.com/
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; + + __mark_reg_not_init(env, &callee->regs[BPF_REG_3]); + __mark_reg_not_init(env, &callee->regs[BPF_REG_4]); + __mark_reg_not_init(env, &callee->regs[BPF_REG_5]); + callee->in_callback_fn = true; + 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)) { verbose(env, "bpf_spin_unlock is missing\n"); return -EINVAL; }
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(-)