Re: [PATCH v4 bpf-next 08/11] bpf: Special verifier handling for bpf_rbtree_{remove, first}

[Kumar Kartikeya Dwivedi <memxor@gmail.com>]

On Thu, Feb 09, 2023 at 06:41:41PM CET, 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 *
>     * mark_reg_graph_node helper added in previous patch generalizes
>       this logic, use it
>
>   * bpf_rbtree_remove's node input is a node that's been inserted
>     in the tree - a non-owning reference.
>
>   * bpf_rbtree_remove must invalidate non-owning references in order to
>     avoid aliasing issue. Use previously-added
>     invalidate_non_owning_refs helper to mark this function as a
>     non-owning ref invalidation point.
>
>   * Unlike other functions, which convert one of their input arg regs to
>     non-owning reference, bpf_rbtree_first takes no arguments and just
>     returns a non-owning reference (possibly null)
>     * For now verifier logic for this is special-cased instead of
>       adding new kfunc flag.
>
> This patch, along with the previous one, complete special verifier
> handling for all rbtree API functions added in this series.
>

I think there are two issues with the current approach. The fundamental
assumption with non-owning references is that it is part of the collection. So
bpf_rbtree_{add,first}, bpf_list_push_{front,back} will create them, as no node
is being removed from collection. Marking bpf_rbtree_remove (and in the future
bpf_list_del) as invalidation points is also right, since once a node has been
removed it is going to be unclear whether existing non-owning references have
the same value, and thus the property of 'part of the collection' will be
broken.

The first issue relates to usability. If I have non-owning references to nodes
inserted into both a list and an rbtree, bpf_rbtree_remove should only
invalidate the ones that are part of the particular rbtree. It should have no
effect on others. Likewise for the bpf_list_del operation in the future.
Therefore, we need to track the collection identity associated with each
non-owning reference, then only invalidate non-owning references associated with
the same collection.

The case of bpf_spin_unlock is different, which should invalidate all non-owning
references.

The second issue is more serious. By not tracking the collection identity, we
will currently allow a non-owning reference for an object inserted into a list
to be passed to bpf_rbtree_remove, because the verifier cannot discern between
'inserted into rbtree' vs 'inserted into list'. For it, both are currently
equivalent in the verifier state. An object is allowed to have both
bpf_list_node and bpf_rb_node, but it can only be part of one collection at a
time (because of no shared ownership).

	struct obj {
		bpf_list_node ln;
		bpf_rb_node rn;
	};

	bpf_list_push_front(head, &obj->ln); // node is non-own-ref
	bpf_rbtree_remove(&obj->rn); // should not work, but does

So some notion of a collection identity needs to be constructed, the amount of
data which needs to be remembered in each non-owning reference's register state
depends on our requirements.

The first sanity check is that bpf_rbtree_remove only removes something in an
rbtree, so probably an enum member indicating whether collection is a list or
rbtree. To ensure proper scoped invalidation, we will unfortunately need more
than just the reg->id of the reg holding the graph root, since map values of
different maps may have same id (0). Hence, we need id and ptr similar to the
active lock case for proper matching. Even this won't be enough, as there can be
multiple list or rbtree roots in a particular memory region, therefore the
offset also needs to be part of the collection identity.

So it seems it will amount to:

	struct bpf_collection_id {
		enum bpf_collection_type type;
		void *ptr;
		int id;
		int off;
	};

There might be ways to optimize the memory footprint of this struct, but I'm
just trying to state why we'll need to include all four, so we don't miss out on
a corner case again.

> Signed-off-by: Dave Marchevsky <davemarchevsky@fb.com>
> ---
> [...]