On Tue, Dec 06, 2022 at 03:09:56PM -0800, Dave Marchevsky wrote:
> Newly-added bpf_rbtree_{remove,first} kfuncs have some special properties
> that require handling in the verifier:
>
> * both bpf_rbtree_remove and bpf_rbtree_first return the type containing
> the bpf_rb_node field, with the offset set to that field's offset,
> instead of a struct bpf_rb_node *
> * Generalized existing next-gen list verifier handling for this
> as mark_reg_datastructure_node helper
>
> * Unlike other functions, which set release_on_unlock on one of their
> args, bpf_rbtree_first takes no arguments, rather setting
> release_on_unlock on its return value
>
> * bpf_rbtree_remove's node input is a node that's been inserted
> in the tree. Only non-owning references (PTR_UNTRUSTED +
> release_on_unlock) refer to such nodes, but kfuncs don't take
> PTR_UNTRUSTED args
> * Added special carveout for bpf_rbtree_remove to take PTR_UNTRUSTED
> * Since node input already has release_on_unlock set, don't set
> it again
>
> This patch, along with the previous one, complete special verifier
> handling for all rbtree API functions added in this series.
>
> Signed-off-by: Dave Marchevsky <davemarchevsky@xxxxxx>
> ---
> kernel/bpf/verifier.c | 89 +++++++++++++++++++++++++++++++++++--------
> 1 file changed, 73 insertions(+), 16 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 9ad8c0b264dc..29983e2c27df 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -6122,6 +6122,23 @@ static int check_reg_type(struct bpf_verifier_env *env, u32 regno,
> return 0;
> }
>
> +static bool
> +func_arg_reg_rb_node_offset(const struct bpf_reg_state *reg, s32 off)
> +{
> + struct btf_record *rec;
> + struct btf_field *field;
> +
> + rec = reg_btf_record(reg);
> + if (!rec)
> + return false;
> +
> + field = btf_record_find(rec, off, BPF_RB_NODE);
> + if (!field)
> + return false;
> +
> + return true;
> +}
> +
> int check_func_arg_reg_off(struct bpf_verifier_env *env,
> const struct bpf_reg_state *reg, int regno,
> enum bpf_arg_type arg_type)
> @@ -6176,6 +6193,13 @@ int check_func_arg_reg_off(struct bpf_verifier_env *env,
> */
> fixed_off_ok = true;
> break;
> + case PTR_TO_BTF_ID | MEM_ALLOC | PTR_UNTRUSTED:
> + /* Currently only bpf_rbtree_remove accepts a PTR_UNTRUSTED
> + * bpf_rb_node. Fixed off of the node type is OK
> + */
> + if (reg->off && func_arg_reg_rb_node_offset(reg, reg->off))
> + fixed_off_ok = true;
> + break;
This doesn't look safe.
We cannot pass generic PTR_UNTRUSTED to bpf_rbtree_remove.
bpf_rbtree_remove wouldn't be able to distinguish invalid pointer.
Considering the cover letter example:
bpf_spin_lock(&glock);
res = bpf_rbtree_first(&groot);
// groot and res are both trusted, no?
if (!res)
/* skip */
// res is acquired and !null here
res = bpf_rbtree_remove(&groot, res); // both args are trusted
// here old res becomes untrusted because it went through release kfunc
// new res is untrusted
if (!res)
/* skip */
bpf_spin_unlock(&glock);
what am I missing?
I thought
bpf_obj_new -> returns acq obj
bpf_rbtree_add -> releases that obj
same way bpf_rbtree_first/next/ -> return acq obj
that can be passed to both rbtree_add and rbtree_remove.
The former will be a nop in runtime, but release from the verifier pov.
Similar with rbtree_remove:
obj = bpf_obj_new
bpf_rbtree_remove(root, obj); will be equivalent to bpf_obj_drop at run-time
and release form the verifier pov.
Are you trying to return untrusted from bpf_rbtree_first?
But then how we can guarantee safety?
