Re: [PATCH v4 bpf-next 04/11] bpf: Add basic bpf_rb_{root,node} support

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

On Thu, Feb 09, 2023 at 06:41:37PM CET, Dave Marchevsky wrote:
> This patch adds special BPF_RB_{ROOT,NODE} btf_field_types similar to
> BPF_LIST_{HEAD,NODE}, adds the necessary plumbing to detect the new
> types, and adds bpf_rb_root_free function for freeing bpf_rb_root in
> map_values.
>
> structs bpf_rb_root and bpf_rb_node are opaque types meant to
> obscure structs rb_root_cached rb_node, respectively.
>
> btf_struct_access will prevent BPF programs from touching these special
> fields automatically now that they're recognized.
>
> btf_check_and_fixup_fields now groups list_head and rb_root together as
> "graph root" fields and {list,rb}_node as "graph node", and does same
> ownership cycle checking as before. Note that this function does _not_
> prevent ownership type mixups (e.g. rb_root owning list_node) - that's
> handled by btf_parse_graph_root.
>
> After this patch, a bpf program can have a struct bpf_rb_root in a
> map_value, but not add anything to nor do anything useful with it.
>
> Signed-off-by: Dave Marchevsky <davemarchevsky@fb.com>
> ---
> [...]
> +#define GRAPH_ROOT_MASK (BPF_LIST_HEAD | BPF_RB_ROOT)
> +#define GRAPH_NODE_MASK (BPF_LIST_NODE | BPF_RB_NODE)
> +
>  int btf_check_and_fixup_fields(const struct btf *btf, struct btf_record *rec)
>  {
>  	int i;
>
> -	/* There are two owning types, kptr_ref and bpf_list_head. The former
> -	 * only supports storing kernel types, which can never store references
> -	 * to program allocated local types, atleast not yet. Hence we only need
> -	 * to ensure that bpf_list_head ownership does not form cycles.
> +	/* There are three types that signify ownership of some other type:
> +	 *  kptr_ref, bpf_list_head, bpf_rb_root.
> +	 * kptr_ref only supports storing kernel types, which can't store
> +	 * references to program allocated local types.
> +	 *
> +	 * Hence we only need to ensure that bpf_{list_head,rb_root} ownership
> +	 * does not form cycles.
>  	 */
> -	if (IS_ERR_OR_NULL(rec) || !(rec->field_mask & BPF_LIST_HEAD))
> +	if (IS_ERR_OR_NULL(rec) || !(rec->field_mask & GRAPH_ROOT_MASK))
>  		return 0;
>  	for (i = 0; i < rec->cnt; i++) {
>  		struct btf_struct_meta *meta;
>  		u32 btf_id;
>
> -		if (!(rec->fields[i].type & BPF_LIST_HEAD))
> +		if (!(rec->fields[i].type & GRAPH_ROOT_MASK))
>  			continue;
>  		btf_id = rec->fields[i].graph_root.value_btf_id;
>  		meta = btf_find_struct_meta(btf, btf_id);
> @@ -3762,39 +3803,47 @@ int btf_check_and_fixup_fields(const struct btf *btf, struct btf_record *rec)
>  			return -EFAULT;
>  		rec->fields[i].graph_root.value_rec = meta->record;
>
> -		if (!(rec->field_mask & BPF_LIST_NODE))
> +		/* We need to set value_rec for all root types, but no need
> +		 * to check ownership cycle for a type unless it's also a
> +		 * node type.
> +		 */
> +		if (!(rec->field_mask & GRAPH_NODE_MASK))
>  			continue;
>
>  		/* We need to ensure ownership acyclicity among all types. The
>  		 * proper way to do it would be to topologically sort all BTF
>  		 * IDs based on the ownership edges, since there can be multiple
> -		 * bpf_list_head in a type. Instead, we use the following
> -		 * reasoning:
> +		 * bpf_{list_head,rb_node} in a type. Instead, we use the
> +		 * following resaoning:
>  		 *
>  		 * - A type can only be owned by another type in user BTF if it
> -		 *   has a bpf_list_node.
> +		 *   has a bpf_{list,rb}_node. Let's call these node types.
>  		 * - A type can only _own_ another type in user BTF if it has a
> -		 *   bpf_list_head.
> +		 *   bpf_{list_head,rb_root}. Let's call these root types.
>  		 *
> -		 * We ensure that if a type has both bpf_list_head and
> -		 * bpf_list_node, its element types cannot be owning types.
> +		 * We ensure that if a type is both a root and node, its
> +		 * element types cannot be root types.
>  		 *
>  		 * To ensure acyclicity:
>  		 *
> -		 * When A only has bpf_list_head, ownership chain can be:
> +		 * When A is an root type but not a node, its ownership
> +		 * chain can be:
>  		 *	A -> B -> C
>  		 * Where:
> -		 * - B has both bpf_list_head and bpf_list_node.
> -		 * - C only has bpf_list_node.
> +		 * - A is an root, e.g. has bpf_rb_root.
> +		 * - B is both a root and node, e.g. has bpf_rb_node and
> +		 *   bpf_list_head.
> +		 * - C is only an root, e.g. has bpf_list_node
>  		 *
> -		 * When A has both bpf_list_head and bpf_list_node, some other
> -		 * type already owns it in the BTF domain, hence it can not own
> -		 * another owning type through any of the bpf_list_head edges.
> +		 * When A is both a root and node, some other type already
> +		 * owns it in the BTF domain, hence it can not own
> +		 * another root type through any of the ownership edges.
>  		 *	A -> B
>  		 * Where:
> -		 * - B only has bpf_list_node.
> +		 * - A is both an root and node.
> +		 * - B is only an node.
>  		 */
> -		if (meta->record->field_mask & BPF_LIST_HEAD)
> +		if (meta->record->field_mask & GRAPH_ROOT_MASK)
>  			return -ELOOP;

While you are at it, can you include BTF selftests (similar to what linked list
tests are doing in test_btf) to ensure all of this being correctly rejected for
rbtree and mixed rbtree + list cases?