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@xxxxxx>
> ---
> [...]
> +#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?
