On Tue, Dec 06, 2022 at 03:09:52PM -0800, Dave Marchevsky wrote:
>
> +#define OWNER_FIELD_MASK (BPF_LIST_HEAD | BPF_RB_ROOT)
> +#define OWNEE_FIELD_MASK (BPF_LIST_NODE | BPF_RB_NODE)
One letter difference makes it so hard to review.
How about
GRAPH_ROOT_MASK
GRAPH_NODE_MASK
?
> +
> 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 & OWNER_FIELD_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 & OWNER_FIELD_MASK))
> continue;
> btf_id = rec->fields[i].datastructure_head.value_btf_id;
> meta = btf_find_struct_meta(btf, btf_id);
> @@ -3742,39 +3783,47 @@ int btf_check_and_fixup_fields(const struct btf *btf, struct btf_record *rec)
> return -EFAULT;
> rec->fields[i].datastructure_head.value_rec = meta->record;
>
> - if (!(rec->field_mask & BPF_LIST_NODE))
> + /* We need to set value_rec for all owner types, but no need
> + * to check ownership cycle for a type unless it's also an
> + * ownee type.
> + */
> + if (!(rec->field_mask & OWNEE_FIELD_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 ownee 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 owner 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 an owner and ownee, its
> + * element types cannot be owner types.
> *
> * To ensure acyclicity:
> *
> - * When A only has bpf_list_head, ownership chain can be:
> + * When A is an owner type but not an ownee, its ownership
and that would become:
When A is a root type, but not a node type...
reads easier.
> + * 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 owner, e.g. has bpf_rb_root.
> + * - B is both an owner and ownee, e.g. has bpf_rb_node and
> + * bpf_list_head.
> + * - C is only an owner, 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 an owner and ownee, some other type already
> + * owns it in the BTF domain, hence it can not own
> + * another owner type through any of the ownership edges.
> * A -> B
> * Where:
> - * - B only has bpf_list_node.
> + * - A is both an owner and ownee.
> + * - B is only an ownee.
