| Message ID | 20220128223312.1253169-7-mauricio@kinvolk.io (mailing list archive) |
|---|---|
| State | Superseded |
| Delegated to: | BPF |
| Headers | show |
| Series | libbpf: Implement BTFGen | expand |
| Context | Check | Description |
|---|---|---|
| netdev/tree_selection | success | Clearly marked for bpf-next |
| netdev/apply | fail | Patch does not apply to bpf-next |
| bpf/vmtest-bpf-next-PR | fail | merge-conflict |
On Fri, Jan 28, 2022 at 2:33 PM Mauricio Vásquez <mauricio@kinvolk.io> wrote: > > This commit implements the logic to record the relocation information > for the different kind of relocations. > > btfgen_record_field_relo() uses the target specification to save all the > types that are involved in a field-based CO-RE relocation. In this case > types resolved and added recursively (using btfgen_put_type()). > Only the struct and union members and their types) involved in the > relocation are added to optimize the size of the generated BTF file. > > On the other hand, btfgen_record_type_relo() saves the types involved in > a type-based CO-RE relocation. In this case all the members for the Do I understand correctly that if someone does bpf_core_type_size(struct task_struct), you'll save not just task_struct, but also any type that directly and indirectly referenced from any task_struct's field, even if that is through a pointer. As in, do you substitute forward declarations for types that are never directly used? If not, that's going to be very suboptimal for something like task_struct and any other type that's part of a big cluster of types. > struct and union types are added. This is not strictly required since > libbpf doesn't use them while performing this kind of relocation, > however that logic could change on the future. Additionally, we expect > that the number of this kind of relocations in an BPF object to be very > low, hence the impact on the size of the generated BTF should be > negligible. > > Finally, btfgen_record_enumval_relo() saves the whole enum type for > enum-based relocations. > > Signed-off-by: Mauricio Vásquez <mauricio@kinvolk.io> > Signed-off-by: Rafael David Tinoco <rafael.tinoco@aquasec.com> > Signed-off-by: Lorenzo Fontana <lorenzo.fontana@elastic.co> > Signed-off-by: Leonardo Di Donato <leonardo.didonato@elastic.co> > --- > tools/bpf/bpftool/gen.c | 260 +++++++++++++++++++++++++++++++++++++++- > 1 file changed, 257 insertions(+), 3 deletions(-) > > diff --git a/tools/bpf/bpftool/gen.c b/tools/bpf/bpftool/gen.c > index bb9c56401ee5..7413ec808a80 100644 > --- a/tools/bpf/bpftool/gen.c > +++ b/tools/bpf/bpftool/gen.c > @@ -1119,9 +1119,17 @@ static int btf_save_raw(const struct btf *btf, const char *path) > return err; > } > > +struct btfgen_member { > + struct btf_member *member; > + int idx; > +}; > + > struct btfgen_type { > struct btf_type *type; > unsigned int id; > + bool all_members; > + > + struct hashmap *members; > }; > > struct btfgen_info { > @@ -1151,6 +1159,19 @@ static void *u32_as_hash_key(__u32 x) > > static void btfgen_free_type(struct btfgen_type *type) > { > + struct hashmap_entry *entry; > + size_t bkt; > + > + if (!type) > + return; > + > + if (!IS_ERR_OR_NULL(type->members)) { > + hashmap__for_each_entry(type->members, entry, bkt) { > + free(entry->value); > + } > + hashmap__free(type->members); > + } > + > free(type); > } > > @@ -1199,19 +1220,252 @@ btfgen_new_info(const char *targ_btf_path) > return info; > } > > +static int btfgen_add_member(struct btfgen_type *btfgen_type, > + struct btf_member *btf_member, int idx) > +{ > + struct btfgen_member *btfgen_member; > + int err; > + > + /* create new members hashmap for this btfgen type if needed */ > + if (!btfgen_type->members) { > + btfgen_type->members = hashmap__new(btfgen_hash_fn, btfgen_equal_fn, NULL); > + if (IS_ERR(btfgen_type->members)) > + return PTR_ERR(btfgen_type->members); > + } > + > + btfgen_member = calloc(1, sizeof(*btfgen_member)); > + if (!btfgen_member) > + return -ENOMEM; > + btfgen_member->member = btf_member; > + btfgen_member->idx = idx; > + /* add btf_member as member to given btfgen_type */ > + err = hashmap__add(btfgen_type->members, uint_as_hash_key(btfgen_member->idx), > + btfgen_member); > + if (err) { > + free(btfgen_member); > + if (err != -EEXIST) why not check that such a member exists before doing btfgen_member allocation? > + return err; > + } > + > + return 0; > +} > + > +static struct btfgen_type *btfgen_get_type(struct btfgen_info *info, int id) > +{ > + struct btfgen_type *type = NULL; > + > + hashmap__find(info->types, uint_as_hash_key(id), (void **)&type); if (!hashmap__find(...)) return NULL; > + > + return type; > +} > + > +static struct btfgen_type * > +_btfgen_put_type(struct btf *btf, struct btfgen_info *info, struct btf_type *btf_type, > + unsigned int id, bool all_members) > +{ > + struct btfgen_type *btfgen_type, *tmp; > + struct btf_array *array; > + unsigned int child_id; > + struct btf_member *m; > + int err, i, n; > + > + /* check if we already have this type */ > + if (hashmap__find(info->types, uint_as_hash_key(id), (void **) &btfgen_type)) { > + if (!all_members || btfgen_type->all_members) > + return btfgen_type; > + } else { > + btfgen_type = calloc(1, sizeof(*btfgen_type)); > + if (!btfgen_type) > + return NULL; > + > + btfgen_type->type = btf_type; > + btfgen_type->id = id; > + > + /* append this type to the types list before anything else */ what do you mean by "before anything else"? > + err = hashmap__add(info->types, uint_as_hash_key(btfgen_type->id), btfgen_type); > + if (err) { > + free(btfgen_type); > + return NULL; > + } > + } > + > + /* avoid infinite recursion and yet be able to add all > + * fields/members for types also managed by this function > + */ > + btfgen_type->all_members = all_members; > + > + /* recursively add other types needed by it */ > + switch (btf_kind(btfgen_type->type)) { > + case BTF_KIND_UNKN: > + case BTF_KIND_INT: > + case BTF_KIND_FLOAT: > + case BTF_KIND_ENUM: > + break; > + case BTF_KIND_STRUCT: > + case BTF_KIND_UNION: > + /* doesn't need resolution if not adding all members */ > + if (!all_members) > + break; > + > + n = btf_vlen(btf_type); > + m = btf_members(btf_type); > + for (i = 0; i < n; i++, m++) { > + btf_type = (struct btf_type *) btf__type_by_id(btf, m->type); why `const struct btf_type *` doesn't work everywhere? You are not modifying btf_type itself, no? > + > + /* add all member types */ > + tmp = _btfgen_put_type(btf, info, btf_type, m->type, all_members); > + if (!tmp) > + return NULL; > + > + /* add all members */ > + err = btfgen_add_member(btfgen_type, m, i); > + if (err) > + return NULL; > + } > + break; > + case BTF_KIND_PTR: > + if (!all_members) > + break; > + /* fall through */ > + /* Also add the type it's pointing to when adding all members */ > + case BTF_KIND_CONST: > + case BTF_KIND_VOLATILE: > + case BTF_KIND_TYPEDEF: > + child_id = btf_type->type; > + btf_type = (struct btf_type *) btf__type_by_id(btf, child_id); > + > + tmp = _btfgen_put_type(btf, info, btf_type, child_id, all_members); > + if (!tmp) > + return NULL; > + break; > + case BTF_KIND_ARRAY: > + array = btf_array(btfgen_type->type); > + > + /* add type for array type */ > + btf_type = (struct btf_type *) btf__type_by_id(btf, array->type); > + tmp = _btfgen_put_type(btf, info, btf_type, array->type, all_members); > + if (!tmp) > + return NULL; > + > + /* add type for array's index type */ > + btf_type = (struct btf_type *) btf__type_by_id(btf, array->index_type); > + tmp = _btfgen_put_type(btf, info, btf_type, array->index_type, all_members); > + if (!tmp) > + return NULL; > + break; > + /* tells if some other type needs to be handled */ > + default: > + p_err("unsupported kind: %s (%d)", > + btf_kind_str(btfgen_type->type), btfgen_type->id); > + errno = EINVAL; > + return NULL; > + } > + > + return btfgen_type; > +} > + > +/* Put type in the list. If the type already exists it's returned, otherwise a > + * new one is created and added to the list. This is called recursively adding > + * all the types that are needed for the current one. > + */ > +static struct btfgen_type * > +btfgen_put_type(struct btf *btf, struct btfgen_info *info, struct btf_type *btf_type, > + unsigned int id) > +{ > + return _btfgen_put_type(btf, info, btf_type, id, false); > +} > + > +/* Same as btfgen_put_type, but adding all members, from given complex type, recursively */ > +static struct btfgen_type * > +btfgen_put_type_all(struct btf *btf, struct btfgen_info *info, > + struct btf_type *btf_type, unsigned int id) > +{ > + return _btfgen_put_type(btf, info, btf_type, id, true); > +} these wrappers seem unnecessary, just pass false/true in 5 call sites below without extra wrapping of _btfgen_put_type (and call it btfgen_put_type then) > + > static int btfgen_record_field_relo(struct btfgen_info *info, struct bpf_core_spec *targ_spec) > { > - return -EOPNOTSUPP; > + struct btf *btf = (struct btf *) info->src_btf; > + struct btfgen_type *btfgen_type; > + struct btf_member *btf_member; > + struct btf_type *btf_type; > + struct btf_array *array; > + unsigned int id; > + int idx, err; > + > + btf_type = (struct btf_type *) btf__type_by_id(btf, targ_spec->root_type_id); > + > + /* create btfgen_type for root type */ > + btfgen_type = btfgen_put_type(btf, info, btf_type, targ_spec->root_type_id); > + if (!btfgen_type) > + return -errno; > + > + /* add types for complex types (arrays, unions, structures) */ > + for (int i = 1; i < targ_spec->raw_len; i++) { > + /* skip typedefs and mods */ > + while (btf_is_mod(btf_type) || btf_is_typedef(btf_type)) { > + id = btf_type->type; > + btfgen_type = btfgen_get_type(info, id); > + if (!btfgen_type) > + return -ENOENT; > + btf_type = (struct btf_type *) btf__type_by_id(btf, id); > + } > + > + switch (btf_kind(btf_type)) { > + case BTF_KIND_STRUCT: > + case BTF_KIND_UNION: > + idx = targ_spec->raw_spec[i]; > + btf_member = btf_members(btf_type) + idx; > + btf_type = (struct btf_type *) btf__type_by_id(btf, btf_member->type); > + > + /* add member to relocation type */ > + err = btfgen_add_member(btfgen_type, btf_member, idx); > + if (err) > + return err; > + /* put btfgen type */ > + btfgen_type = btfgen_put_type(btf, info, btf_type, btf_member->type); > + if (!btfgen_type) > + return -errno; > + break; > + case BTF_KIND_ARRAY: > + array = btf_array(btf_type); > + btfgen_type = btfgen_get_type(info, array->type); > + if (!btfgen_type) > + return -ENOENT; > + btf_type = (struct btf_type *) btf__type_by_id(btf, array->type); should index_type be added as well? > + break; > + default: > + p_err("unsupported kind: %s (%d)", > + btf_kind_str(btf_type), btf_type->type); > + return -EINVAL; > + } > + } > + > + return 0; > } > > static int btfgen_record_type_relo(struct btfgen_info *info, struct bpf_core_spec *targ_spec) > { > - return -EOPNOTSUPP; > + struct btf *btf = (struct btf *) info->src_btf; > + struct btfgen_type *btfgen_type; > + struct btf_type *btf_type; > + > + btf_type = (struct btf_type *) btf__type_by_id(btf, targ_spec->root_type_id); > + > + btfgen_type = btfgen_put_type_all(btf, info, btf_type, targ_spec->root_type_id); > + return btfgen_type ? 0 : -errno; > } > > static int btfgen_record_enumval_relo(struct btfgen_info *info, struct bpf_core_spec *targ_spec) > { > - return -EOPNOTSUPP; > + struct btf *btf = (struct btf *) info->src_btf; > + struct btfgen_type *btfgen_type; > + struct btf_type *btf_type; > + > + btf_type = (struct btf_type *) btf__type_by_id(btf, targ_spec->root_type_id); > + > + btfgen_type = btfgen_put_type_all(btf, info, btf_type, targ_spec->root_type_id); > + return btfgen_type ? 0 : -errno; > } > > static int btfgen_record_reloc(struct btfgen_info *info, struct bpf_core_spec *res) > -- > 2.25.1 >
On Fri, Jan 28, 2022 at 2:33 PM Mauricio Vásquez <mauricio@kinvolk.io> wrote: > > This commit implements the logic to record the relocation information > for the different kind of relocations. > > btfgen_record_field_relo() uses the target specification to save all the > types that are involved in a field-based CO-RE relocation. In this case > types resolved and added recursively (using btfgen_put_type()). > Only the struct and union members and their types) involved in the > relocation are added to optimize the size of the generated BTF file. > > On the other hand, btfgen_record_type_relo() saves the types involved in > a type-based CO-RE relocation. In this case all the members for the > struct and union types are added. This is not strictly required since > libbpf doesn't use them while performing this kind of relocation, > however that logic could change on the future. Additionally, we expect > that the number of this kind of relocations in an BPF object to be very > low, hence the impact on the size of the generated BTF should be > negligible. > > Finally, btfgen_record_enumval_relo() saves the whole enum type for > enum-based relocations. > > Signed-off-by: Mauricio Vásquez <mauricio@kinvolk.io> > Signed-off-by: Rafael David Tinoco <rafael.tinoco@aquasec.com> > Signed-off-by: Lorenzo Fontana <lorenzo.fontana@elastic.co> > Signed-off-by: Leonardo Di Donato <leonardo.didonato@elastic.co> > --- I've been thinking about this in background. This proliferation of hashmaps to store used types and their members really adds to complexity (and no doubt to memory usage and CPU utilization, even though I don't think either is too big for this use case). What if instead of keeping track of used types and members separately, we initialize the original struct btf and its btf_type, btf_member, btf_enum, etc types. We can carve out one bit in them to mark whether that specific entity was used. That way you don't need any extra hashmap maintenance. You just set or check bit on each type or its member to figure out if it has to be in the resulting BTF. This can be highest bit of name_off or type fields, depending on specific case. This will work well because type IDs never use highest bit and string offset can never be as high as to needing full 32 bits. You'll probably want to have two copies of target BTF for this, of course, but I think simplicity of bookkeeping trumps this inefficiency. WDYT? > tools/bpf/bpftool/gen.c | 260 +++++++++++++++++++++++++++++++++++++++- > 1 file changed, 257 insertions(+), 3 deletions(-) > [...]
On Wed, Feb 2, 2022 at 2:31 PM Andrii Nakryiko <andrii.nakryiko@gmail.com> wrote: > > On Fri, Jan 28, 2022 at 2:33 PM Mauricio Vásquez <mauricio@kinvolk.io> wrote: > > > > This commit implements the logic to record the relocation information > > for the different kind of relocations. > > > > btfgen_record_field_relo() uses the target specification to save all the > > types that are involved in a field-based CO-RE relocation. In this case > > types resolved and added recursively (using btfgen_put_type()). > > Only the struct and union members and their types) involved in the > > relocation are added to optimize the size of the generated BTF file. > > > > On the other hand, btfgen_record_type_relo() saves the types involved in > > a type-based CO-RE relocation. In this case all the members for the > > Do I understand correctly that if someone does > bpf_core_type_size(struct task_struct), you'll save not just > task_struct, but also any type that directly and indirectly referenced > from any task_struct's field, even if that is through a pointer. That's correct. > As > in, do you substitute forward declarations for types that are never > directly used? If not, that's going to be very suboptimal for > something like task_struct and any other type that's part of a big > cluster of types. > We decided to include the whole types and all direct and indirect types referenced from a structure field for type-based relocations. Our reasoning is that we don't know if the matching algorithm of libbpf could be changed to require more information in the future and type-based relocations are few compared to field based relocations. If you are confident enough that adding empty structures/unions is ok then I'll update the algorithm. Actually it'll make our lives easier. > > struct and union types are added. This is not strictly required since > > libbpf doesn't use them while performing this kind of relocation, > > however that logic could change on the future. Additionally, we expect > > that the number of this kind of relocations in an BPF object to be very > > low, hence the impact on the size of the generated BTF should be > > negligible. > > > > Finally, btfgen_record_enumval_relo() saves the whole enum type for > > enum-based relocations. > > > > Signed-off-by: Mauricio Vásquez <mauricio@kinvolk.io> > > Signed-off-by: Rafael David Tinoco <rafael.tinoco@aquasec.com> > > Signed-off-by: Lorenzo Fontana <lorenzo.fontana@elastic.co> > > Signed-off-by: Leonardo Di Donato <leonardo.didonato@elastic.co> > > --- > > tools/bpf/bpftool/gen.c | 260 +++++++++++++++++++++++++++++++++++++++- > > 1 file changed, 257 insertions(+), 3 deletions(-) > > > > diff --git a/tools/bpf/bpftool/gen.c b/tools/bpf/bpftool/gen.c > > index bb9c56401ee5..7413ec808a80 100644 > > --- a/tools/bpf/bpftool/gen.c > > +++ b/tools/bpf/bpftool/gen.c > > @@ -1119,9 +1119,17 @@ static int btf_save_raw(const struct btf *btf, const char *path) > > return err; > > } > > > > +struct btfgen_member { > > + struct btf_member *member; > > + int idx; > > +}; > > + > > struct btfgen_type { > > struct btf_type *type; > > unsigned int id; > > + bool all_members; > > + > > + struct hashmap *members; > > }; > > > > struct btfgen_info { > > @@ -1151,6 +1159,19 @@ static void *u32_as_hash_key(__u32 x) > > > > static void btfgen_free_type(struct btfgen_type *type) > > { > > + struct hashmap_entry *entry; > > + size_t bkt; > > + > > + if (!type) > > + return; > > + > > + if (!IS_ERR_OR_NULL(type->members)) { > > + hashmap__for_each_entry(type->members, entry, bkt) { > > + free(entry->value); > > + } > > + hashmap__free(type->members); > > + } > > + > > free(type); > > } > > > > @@ -1199,19 +1220,252 @@ btfgen_new_info(const char *targ_btf_path) > > return info; > > } > > > > +static int btfgen_add_member(struct btfgen_type *btfgen_type, > > + struct btf_member *btf_member, int idx) > > +{ > > + struct btfgen_member *btfgen_member; > > + int err; > > + > > + /* create new members hashmap for this btfgen type if needed */ > > + if (!btfgen_type->members) { > > + btfgen_type->members = hashmap__new(btfgen_hash_fn, btfgen_equal_fn, NULL); > > + if (IS_ERR(btfgen_type->members)) > > + return PTR_ERR(btfgen_type->members); > > + } > > + > > + btfgen_member = calloc(1, sizeof(*btfgen_member)); > > + if (!btfgen_member) > > + return -ENOMEM; > > + btfgen_member->member = btf_member; > > + btfgen_member->idx = idx; > > + /* add btf_member as member to given btfgen_type */ > > + err = hashmap__add(btfgen_type->members, uint_as_hash_key(btfgen_member->idx), > > + btfgen_member); > > + if (err) { > > + free(btfgen_member); > > + if (err != -EEXIST) > > why not check that such a member exists before doing btfgen_member allocation? > I thought that it could be more efficient calling hashmap__add() directly without checking and then handling the case when it was already there. Having a second thought it seems to me that it's not always true and depends on how many times the code follows each path, what we don't know. I'll change it to check if it's there before. > > + return err; > > + } > > + > > + return 0; > > +} > > + > > +static struct btfgen_type *btfgen_get_type(struct btfgen_info *info, int id) > > +{ > > + struct btfgen_type *type = NULL; > > + > > + hashmap__find(info->types, uint_as_hash_key(id), (void **)&type); > > if (!hashmap__find(...)) > return NULL; > > > + > > + return type; > > +} > > + > > +static struct btfgen_type * > > +_btfgen_put_type(struct btf *btf, struct btfgen_info *info, struct btf_type *btf_type, > > + unsigned int id, bool all_members) > > +{ > > + struct btfgen_type *btfgen_type, *tmp; > > + struct btf_array *array; > > + unsigned int child_id; > > + struct btf_member *m; > > + int err, i, n; > > + > > + /* check if we already have this type */ > > + if (hashmap__find(info->types, uint_as_hash_key(id), (void **) &btfgen_type)) { > > + if (!all_members || btfgen_type->all_members) > > + return btfgen_type; > > + } else { > > + btfgen_type = calloc(1, sizeof(*btfgen_type)); > > + if (!btfgen_type) > > + return NULL; > > + > > + btfgen_type->type = btf_type; > > + btfgen_type->id = id; > > + > > + /* append this type to the types list before anything else */ > > what do you mean by "before anything else"? Add this before starting the recursion below. I'll update the comment to make it more clear. > > > + err = hashmap__add(info->types, uint_as_hash_key(btfgen_type->id), btfgen_type); > > + if (err) { > > + free(btfgen_type); > > + return NULL; > > + } > > + } > > + > > + /* avoid infinite recursion and yet be able to add all > > + * fields/members for types also managed by this function > > + */ > > + btfgen_type->all_members = all_members; > > + > > + /* recursively add other types needed by it */ > > + switch (btf_kind(btfgen_type->type)) { > > + case BTF_KIND_UNKN: > > + case BTF_KIND_INT: > > + case BTF_KIND_FLOAT: > > + case BTF_KIND_ENUM: > > + break; > > + case BTF_KIND_STRUCT: > > + case BTF_KIND_UNION: > > + /* doesn't need resolution if not adding all members */ > > + if (!all_members) > > + break; > > + > > + n = btf_vlen(btf_type); > > + m = btf_members(btf_type); > > + for (i = 0; i < n; i++, m++) { > > + btf_type = (struct btf_type *) btf__type_by_id(btf, m->type); > > why `const struct btf_type *` doesn't work everywhere? You are not > modifying btf_type itself, no? Yes, `const struct btf_type *` works fine everywhere. > > > + > > + /* add all member types */ > > + tmp = _btfgen_put_type(btf, info, btf_type, m->type, all_members); > > + if (!tmp) > > + return NULL; > > + > > + /* add all members */ > > + err = btfgen_add_member(btfgen_type, m, i); > > + if (err) > > + return NULL; > > + } > > + break; > > + case BTF_KIND_PTR: > > + if (!all_members) > > + break; > > + /* fall through */ > > + /* Also add the type it's pointing to when adding all members */ > > + case BTF_KIND_CONST: > > + case BTF_KIND_VOLATILE: > > + case BTF_KIND_TYPEDEF: > > + child_id = btf_type->type; > > + btf_type = (struct btf_type *) btf__type_by_id(btf, child_id); > > + > > + tmp = _btfgen_put_type(btf, info, btf_type, child_id, all_members); > > + if (!tmp) > > + return NULL; > > + break; > > + case BTF_KIND_ARRAY: > > + array = btf_array(btfgen_type->type); > > + > > + /* add type for array type */ > > + btf_type = (struct btf_type *) btf__type_by_id(btf, array->type); > > + tmp = _btfgen_put_type(btf, info, btf_type, array->type, all_members); > > + if (!tmp) > > + return NULL; > > + > > + /* add type for array's index type */ > > + btf_type = (struct btf_type *) btf__type_by_id(btf, array->index_type); > > + tmp = _btfgen_put_type(btf, info, btf_type, array->index_type, all_members); > > + if (!tmp) > > + return NULL; > > + break; > > + /* tells if some other type needs to be handled */ > > + default: > > + p_err("unsupported kind: %s (%d)", > > + btf_kind_str(btfgen_type->type), btfgen_type->id); > > + errno = EINVAL; > > + return NULL; > > + } > > + > > + return btfgen_type; > > +} > > + > > +/* Put type in the list. If the type already exists it's returned, otherwise a > > + * new one is created and added to the list. This is called recursively adding > > + * all the types that are needed for the current one. > > + */ > > +static struct btfgen_type * > > +btfgen_put_type(struct btf *btf, struct btfgen_info *info, struct btf_type *btf_type, > > + unsigned int id) > > +{ > > + return _btfgen_put_type(btf, info, btf_type, id, false); > > +} > > + > > +/* Same as btfgen_put_type, but adding all members, from given complex type, recursively */ > > +static struct btfgen_type * > > +btfgen_put_type_all(struct btf *btf, struct btfgen_info *info, > > + struct btf_type *btf_type, unsigned int id) > > +{ > > + return _btfgen_put_type(btf, info, btf_type, id, true); > > +} > > these wrappers seem unnecessary, just pass false/true in 5 call sites > below without extra wrapping of _btfgen_put_type (and call it > btfgen_put_type then) > > > + > > static int btfgen_record_field_relo(struct btfgen_info *info, struct bpf_core_spec *targ_spec) > > { > > - return -EOPNOTSUPP; > > + struct btf *btf = (struct btf *) info->src_btf; > > + struct btfgen_type *btfgen_type; > > + struct btf_member *btf_member; > > + struct btf_type *btf_type; > > + struct btf_array *array; > > + unsigned int id; > > + int idx, err; > > + > > + btf_type = (struct btf_type *) btf__type_by_id(btf, targ_spec->root_type_id); > > + > > + /* create btfgen_type for root type */ > > + btfgen_type = btfgen_put_type(btf, info, btf_type, targ_spec->root_type_id); > > + if (!btfgen_type) > > + return -errno; > > + > > + /* add types for complex types (arrays, unions, structures) */ > > + for (int i = 1; i < targ_spec->raw_len; i++) { > > + /* skip typedefs and mods */ > > + while (btf_is_mod(btf_type) || btf_is_typedef(btf_type)) { > > + id = btf_type->type; > > + btfgen_type = btfgen_get_type(info, id); > > + if (!btfgen_type) > > + return -ENOENT; > > + btf_type = (struct btf_type *) btf__type_by_id(btf, id); > > + } > > + > > + switch (btf_kind(btf_type)) { > > + case BTF_KIND_STRUCT: > > + case BTF_KIND_UNION: > > + idx = targ_spec->raw_spec[i]; > > + btf_member = btf_members(btf_type) + idx; > > + btf_type = (struct btf_type *) btf__type_by_id(btf, btf_member->type); > > + > > + /* add member to relocation type */ > > + err = btfgen_add_member(btfgen_type, btf_member, idx); > > + if (err) > > + return err; > > + /* put btfgen type */ > > + btfgen_type = btfgen_put_type(btf, info, btf_type, btf_member->type); > > + if (!btfgen_type) > > + return -errno; > > + break; > > + case BTF_KIND_ARRAY: > > + array = btf_array(btf_type); > > + btfgen_type = btfgen_get_type(info, array->type); > > + if (!btfgen_type) > > + return -ENOENT; > > + btf_type = (struct btf_type *) btf__type_by_id(btf, array->type); > > should index_type be added as well? This is added in _btfgen_put_type(). Here we're just updating `btf_type` with the array's type for the next iteration of this loop. > > > + break; > > + default: > > + p_err("unsupported kind: %s (%d)", > > + btf_kind_str(btf_type), btf_type->type); > > + return -EINVAL; > > + } > > + } > > + > > + return 0; > > } > > > > static int btfgen_record_type_relo(struct btfgen_info *info, struct bpf_core_spec *targ_spec) > > { > > - return -EOPNOTSUPP; > > + struct btf *btf = (struct btf *) info->src_btf; > > + struct btfgen_type *btfgen_type; > > + struct btf_type *btf_type; > > + > > + btf_type = (struct btf_type *) btf__type_by_id(btf, targ_spec->root_type_id); > > + > > + btfgen_type = btfgen_put_type_all(btf, info, btf_type, targ_spec->root_type_id); > > + return btfgen_type ? 0 : -errno; > > } > > > > static int btfgen_record_enumval_relo(struct btfgen_info *info, struct bpf_core_spec *targ_spec) > > { > > - return -EOPNOTSUPP; > > + struct btf *btf = (struct btf *) info->src_btf; > > + struct btfgen_type *btfgen_type; > > + struct btf_type *btf_type; > > + > > + btf_type = (struct btf_type *) btf__type_by_id(btf, targ_spec->root_type_id); > > + > > + btfgen_type = btfgen_put_type_all(btf, info, btf_type, targ_spec->root_type_id); > > + return btfgen_type ? 0 : -errno; > > } > > > > static int btfgen_record_reloc(struct btfgen_info *info, struct bpf_core_spec *res) > > -- > > 2.25.1 > >
On Thu, Feb 3, 2022 at 8:40 AM Mauricio Vásquez Bernal <mauricio@kinvolk.io> wrote: > > On Wed, Feb 2, 2022 at 2:31 PM Andrii Nakryiko > <andrii.nakryiko@gmail.com> wrote: > > > > On Fri, Jan 28, 2022 at 2:33 PM Mauricio Vásquez <mauricio@kinvolk.io> wrote: > > > > > > This commit implements the logic to record the relocation information > > > for the different kind of relocations. > > > > > > btfgen_record_field_relo() uses the target specification to save all the > > > types that are involved in a field-based CO-RE relocation. In this case > > > types resolved and added recursively (using btfgen_put_type()). > > > Only the struct and union members and their types) involved in the > > > relocation are added to optimize the size of the generated BTF file. > > > > > > On the other hand, btfgen_record_type_relo() saves the types involved in > > > a type-based CO-RE relocation. In this case all the members for the > > > > Do I understand correctly that if someone does > > bpf_core_type_size(struct task_struct), you'll save not just > > task_struct, but also any type that directly and indirectly referenced > > from any task_struct's field, even if that is through a pointer. > > That's correct. > > > As > > in, do you substitute forward declarations for types that are never > > directly used? If not, that's going to be very suboptimal for > > something like task_struct and any other type that's part of a big > > cluster of types. > > > > We decided to include the whole types and all direct and indirect > types referenced from a structure field for type-based relocations. > Our reasoning is that we don't know if the matching algorithm of > libbpf could be changed to require more information in the future and > type-based relocations are few compared to field based relocations. > It will depend on application and which type is used in relocation. task_struct reaches tons of types and will add a very noticeable size to minimized BTF, for no good reason, IMO. If we discover that we do need those types, we'll update bpftool to generate more. > If you are confident enough that adding empty structures/unions is ok > then I'll update the algorithm. Actually it'll make our lives easier. > Well, test it of course, but I think it should work. > > > struct and union types are added. This is not strictly required since > > > libbpf doesn't use them while performing this kind of relocation, > > > however that logic could change on the future. Additionally, we expect > > > that the number of this kind of relocations in an BPF object to be very > > > low, hence the impact on the size of the generated BTF should be > > > negligible. > > > > > > Finally, btfgen_record_enumval_relo() saves the whole enum type for > > > enum-based relocations. > > > > > > Signed-off-by: Mauricio Vásquez <mauricio@kinvolk.io> > > > Signed-off-by: Rafael David Tinoco <rafael.tinoco@aquasec.com> > > > Signed-off-by: Lorenzo Fontana <lorenzo.fontana@elastic.co> > > > Signed-off-by: Leonardo Di Donato <leonardo.didonato@elastic.co> > > > --- > > > tools/bpf/bpftool/gen.c | 260 +++++++++++++++++++++++++++++++++++++++- > > > 1 file changed, 257 insertions(+), 3 deletions(-) > > > [...] > > > + > > > + btfgen_member = calloc(1, sizeof(*btfgen_member)); > > > + if (!btfgen_member) > > > + return -ENOMEM; > > > + btfgen_member->member = btf_member; > > > + btfgen_member->idx = idx; > > > + /* add btf_member as member to given btfgen_type */ > > > + err = hashmap__add(btfgen_type->members, uint_as_hash_key(btfgen_member->idx), > > > + btfgen_member); > > > + if (err) { > > > + free(btfgen_member); > > > + if (err != -EEXIST) > > > > why not check that such a member exists before doing btfgen_member allocation? > > > > I thought that it could be more efficient calling hashmap__add() > directly without checking and then handling the case when it was > already there. Having a second thought it seems to me that it's not > always true and depends on how many times the code follows each path, > what we don't know. I'll change it to check if it's there before. > See my other reply on this patch. Maybe you won't need a hashmap at all if you modify btf_type in place (As in, set extra bit to mark that type or its member is needed)? It feels a bit hacky, but this is an internal and one specific case inside bpftool, so I think it's justified (and it will be much cleaner and shorter code, IMO). > > > + return err; > > > + } > > > + > > > + return 0; > > > +} > > > + [...]
>>> As in, do you substitute forward declarations for types that are >>> never directly used? If not, that's going to be very suboptimal for >>> something like task_struct and any other type that's part of a big >>> cluster of types. >> We decided to include the whole types and all direct and indirect >> types referenced from a structure field for type-based relocations. >> Our reasoning is that we don't know if the matching algorithm of >> libbpf could be changed to require more information in the future and >> type-based relocations are few compared to field based relocations. > It will depend on application and which type is used in relocation. > task_struct reaches tons of types and will add a very noticeable size > to minimized BTF, for no good reason, IMO. If we discover that we do > need those types, we'll update bpftool to generate more. Just to see if I understood this part correctly. IIRC, we started type based relocations support in btfgen because of this particular case: union kernfs_node_id { struct { u32 ino; u32 generation; }; u64 id; }; struct kernfs_node___older_v55 { const char *name; union kernfs_node_id id; }; struct kernfs_node___rh8 { const char *name; union { u64 id; struct { union kernfs_node_id id; } rh_kabi_hidden_172; union { }; }; }; So we have 3 situations: (struct kernfs_node *)->id as u64 [29] STRUCT 'kernfs_node' size=128 vlen=1 'id' type_id=42 bits_offset=832 [42] TYPEDEF 'u64' type_id=10 (struct kernfs_node___older_v55 *)->id as u64 (union kernfs_node_id)->id [79] STRUCT 'kernfs_node' size=128 vlen=1 'id' type_id=69 bits_offset=832 [69] UNION 'kernfs_node_id' size=8 vlen=2 '(anon)' type_id=132 bits_offset=0 'id' type_id=40 bits_offset=0 [40] TYPEDEF 'u64' type_id=12 (struct kernfs_node___rh8 *)->id = (anon union)->id [56] STRUCT 'kernfs_node' size=128 vlen=1 '(anon)' type_id=24 bits_offset=832 [24] UNION '(anon)' size=8 vlen=1 'id' type_id=40 bits_offset=0 [40] TYPEDEF 'u64' type_id=11 We're finding needed BTF types, that should be added to generated BTF, based on fields/members of CORE relo info. How we would know we had to add the anon union of the last case if it does not exist in the local BTF ? What is your suggestion ? Thanks! -rafaeldtinoco
On Thu, Feb 3, 2022 at 10:20 PM Rafael David Tinoco <rafaeldtinoco@gmail.com> wrote: > > >>> As in, do you substitute forward declarations for types that are > >>> never directly used? If not, that's going to be very suboptimal for > >>> something like task_struct and any other type that's part of a big > >>> cluster of types. > > >> We decided to include the whole types and all direct and indirect > >> types referenced from a structure field for type-based relocations. > >> Our reasoning is that we don't know if the matching algorithm of > >> libbpf could be changed to require more information in the future and > >> type-based relocations are few compared to field based relocations. > > > It will depend on application and which type is used in relocation. > > task_struct reaches tons of types and will add a very noticeable size > > to minimized BTF, for no good reason, IMO. If we discover that we do > > need those types, we'll update bpftool to generate more. > > Just to see if I understood this part correctly. IIRC, we started type > based relocations support in btfgen because of this particular case: > > union kernfs_node_id { > struct { > u32 ino; > u32 generation; > }; > u64 id; > }; > > struct kernfs_node___older_v55 { > const char *name; > union kernfs_node_id id; > }; > > struct kernfs_node___rh8 { > const char *name; > union { > u64 id; > struct { > union kernfs_node_id id; > } rh_kabi_hidden_172; > union { }; > }; > }; > > So we have 3 situations: > > (struct kernfs_node *)->id as u64 > > [29] STRUCT 'kernfs_node' size=128 vlen=1 > 'id' type_id=42 bits_offset=832 > [42] TYPEDEF 'u64' type_id=10 > > (struct kernfs_node___older_v55 *)->id as u64 (union kernfs_node_id)->id > > [79] STRUCT 'kernfs_node' size=128 vlen=1 > 'id' type_id=69 bits_offset=832 > [69] UNION 'kernfs_node_id' size=8 vlen=2 > '(anon)' type_id=132 bits_offset=0 > 'id' type_id=40 bits_offset=0 > [40] TYPEDEF 'u64' type_id=12 > > (struct kernfs_node___rh8 *)->id = (anon union)->id > > [56] STRUCT 'kernfs_node' size=128 vlen=1 > '(anon)' type_id=24 bits_offset=832 > [24] UNION '(anon)' size=8 vlen=1 > 'id' type_id=40 bits_offset=0 > [40] TYPEDEF 'u64' type_id=11 > > We're finding needed BTF types, that should be added to generated BTF, > based on fields/members of CORE relo info. How we would know we had to > add the anon union of the last case if it does not exist in the local > BTF ? What is your suggestion ? > I'd need to see real BPF program code for this situation, but if you don't have field-based relocation that needs that anonymous union, then it shouldn't matter if that union is there or not. I suspect you do have field-based relocations that access fields of struct kernfs_node___rh8 and kernfs_node___older_v55, so both structs and necessary fields should be marked as "used" by btfgen algorithm. > Thanks! > > -rafaeldtinoco
On Wed, Feb 2, 2022 at 5:55 PM Andrii Nakryiko <andrii.nakryiko@gmail.com> wrote: > > On Fri, Jan 28, 2022 at 2:33 PM Mauricio Vásquez <mauricio@kinvolk.io> wrote: > > > > This commit implements the logic to record the relocation information > > for the different kind of relocations. > > > > btfgen_record_field_relo() uses the target specification to save all the > > types that are involved in a field-based CO-RE relocation. In this case > > types resolved and added recursively (using btfgen_put_type()). > > Only the struct and union members and their types) involved in the > > relocation are added to optimize the size of the generated BTF file. > > > > On the other hand, btfgen_record_type_relo() saves the types involved in > > a type-based CO-RE relocation. In this case all the members for the > > struct and union types are added. This is not strictly required since > > libbpf doesn't use them while performing this kind of relocation, > > however that logic could change on the future. Additionally, we expect > > that the number of this kind of relocations in an BPF object to be very > > low, hence the impact on the size of the generated BTF should be > > negligible. > > > > Finally, btfgen_record_enumval_relo() saves the whole enum type for > > enum-based relocations. > > > > Signed-off-by: Mauricio Vásquez <mauricio@kinvolk.io> > > Signed-off-by: Rafael David Tinoco <rafael.tinoco@aquasec.com> > > Signed-off-by: Lorenzo Fontana <lorenzo.fontana@elastic.co> > > Signed-off-by: Leonardo Di Donato <leonardo.didonato@elastic.co> > > --- > > I've been thinking about this in background. This proliferation of > hashmaps to store used types and their members really adds to > complexity (and no doubt to memory usage and CPU utilization, even > though I don't think either is too big for this use case). > > What if instead of keeping track of used types and members separately, > we initialize the original struct btf and its btf_type, btf_member, > btf_enum, etc types. We can carve out one bit in them to mark whether > that specific entity was used. That way you don't need any extra > hashmap maintenance. You just set or check bit on each type or its > member to figure out if it has to be in the resulting BTF. > > This can be highest bit of name_off or type fields, depending on > specific case. This will work well because type IDs never use highest > bit and string offset can never be as high as to needing full 32 bits. > > You'll probably want to have two copies of target BTF for this, of > course, but I think simplicity of bookkeeping trumps this > inefficiency. WDYT? > It's a very nice idea indeed. I got a version working with this idea. I keep two instances of the target BTF (as you suggested) one is only for keeping track of the used types/members, the other one is used as source when copying the BTF types and also to run the candidate search algorithm and so on. Actually there is no need to use the highest bit, I'm just setting the whole name_off to UINT32_MAX. It works fine because that copy of the BTF isn't used anywhere else. I'm cleaning this up and hope to send it early next week. Thanks for all the feedback!
diff --git a/tools/bpf/bpftool/gen.c b/tools/bpf/bpftool/gen.c index bb9c56401ee5..7413ec808a80 100644 --- a/tools/bpf/bpftool/gen.c +++ b/tools/bpf/bpftool/gen.c @@ -1119,9 +1119,17 @@ static int btf_save_raw(const struct btf *btf, const char *path) return err; } +struct btfgen_member { + struct btf_member *member; + int idx; +}; + struct btfgen_type { struct btf_type *type; unsigned int id; + bool all_members; + + struct hashmap *members; }; struct btfgen_info { @@ -1151,6 +1159,19 @@ static void *u32_as_hash_key(__u32 x) static void btfgen_free_type(struct btfgen_type *type) { + struct hashmap_entry *entry; + size_t bkt; + + if (!type) + return; + + if (!IS_ERR_OR_NULL(type->members)) { + hashmap__for_each_entry(type->members, entry, bkt) { + free(entry->value); + } + hashmap__free(type->members); + } + free(type); } @@ -1199,19 +1220,252 @@ btfgen_new_info(const char *targ_btf_path) return info; } +static int btfgen_add_member(struct btfgen_type *btfgen_type, + struct btf_member *btf_member, int idx) +{ + struct btfgen_member *btfgen_member; + int err; + + /* create new members hashmap for this btfgen type if needed */ + if (!btfgen_type->members) { + btfgen_type->members = hashmap__new(btfgen_hash_fn, btfgen_equal_fn, NULL); + if (IS_ERR(btfgen_type->members)) + return PTR_ERR(btfgen_type->members); + } + + btfgen_member = calloc(1, sizeof(*btfgen_member)); + if (!btfgen_member) + return -ENOMEM; + btfgen_member->member = btf_member; + btfgen_member->idx = idx; + /* add btf_member as member to given btfgen_type */ + err = hashmap__add(btfgen_type->members, uint_as_hash_key(btfgen_member->idx), + btfgen_member); + if (err) { + free(btfgen_member); + if (err != -EEXIST) + return err; + } + + return 0; +} + +static struct btfgen_type *btfgen_get_type(struct btfgen_info *info, int id) +{ + struct btfgen_type *type = NULL; + + hashmap__find(info->types, uint_as_hash_key(id), (void **)&type); + + return type; +} + +static struct btfgen_type * +_btfgen_put_type(struct btf *btf, struct btfgen_info *info, struct btf_type *btf_type, + unsigned int id, bool all_members) +{ + struct btfgen_type *btfgen_type, *tmp; + struct btf_array *array; + unsigned int child_id; + struct btf_member *m; + int err, i, n; + + /* check if we already have this type */ + if (hashmap__find(info->types, uint_as_hash_key(id), (void **) &btfgen_type)) { + if (!all_members || btfgen_type->all_members) + return btfgen_type; + } else { + btfgen_type = calloc(1, sizeof(*btfgen_type)); + if (!btfgen_type) + return NULL; + + btfgen_type->type = btf_type; + btfgen_type->id = id; + + /* append this type to the types list before anything else */ + err = hashmap__add(info->types, uint_as_hash_key(btfgen_type->id), btfgen_type); + if (err) { + free(btfgen_type); + return NULL; + } + } + + /* avoid infinite recursion and yet be able to add all + * fields/members for types also managed by this function + */ + btfgen_type->all_members = all_members; + + /* recursively add other types needed by it */ + switch (btf_kind(btfgen_type->type)) { + case BTF_KIND_UNKN: + case BTF_KIND_INT: + case BTF_KIND_FLOAT: + case BTF_KIND_ENUM: + break; + case BTF_KIND_STRUCT: + case BTF_KIND_UNION: + /* doesn't need resolution if not adding all members */ + if (!all_members) + break; + + n = btf_vlen(btf_type); + m = btf_members(btf_type); + for (i = 0; i < n; i++, m++) { + btf_type = (struct btf_type *) btf__type_by_id(btf, m->type); + + /* add all member types */ + tmp = _btfgen_put_type(btf, info, btf_type, m->type, all_members); + if (!tmp) + return NULL; + + /* add all members */ + err = btfgen_add_member(btfgen_type, m, i); + if (err) + return NULL; + } + break; + case BTF_KIND_PTR: + if (!all_members) + break; + /* fall through */ + /* Also add the type it's pointing to when adding all members */ + case BTF_KIND_CONST: + case BTF_KIND_VOLATILE: + case BTF_KIND_TYPEDEF: + child_id = btf_type->type; + btf_type = (struct btf_type *) btf__type_by_id(btf, child_id); + + tmp = _btfgen_put_type(btf, info, btf_type, child_id, all_members); + if (!tmp) + return NULL; + break; + case BTF_KIND_ARRAY: + array = btf_array(btfgen_type->type); + + /* add type for array type */ + btf_type = (struct btf_type *) btf__type_by_id(btf, array->type); + tmp = _btfgen_put_type(btf, info, btf_type, array->type, all_members); + if (!tmp) + return NULL; + + /* add type for array's index type */ + btf_type = (struct btf_type *) btf__type_by_id(btf, array->index_type); + tmp = _btfgen_put_type(btf, info, btf_type, array->index_type, all_members); + if (!tmp) + return NULL; + break; + /* tells if some other type needs to be handled */ + default: + p_err("unsupported kind: %s (%d)", + btf_kind_str(btfgen_type->type), btfgen_type->id); + errno = EINVAL; + return NULL; + } + + return btfgen_type; +} + +/* Put type in the list. If the type already exists it's returned, otherwise a + * new one is created and added to the list. This is called recursively adding + * all the types that are needed for the current one. + */ +static struct btfgen_type * +btfgen_put_type(struct btf *btf, struct btfgen_info *info, struct btf_type *btf_type, + unsigned int id) +{ + return _btfgen_put_type(btf, info, btf_type, id, false); +} + +/* Same as btfgen_put_type, but adding all members, from given complex type, recursively */ +static struct btfgen_type * +btfgen_put_type_all(struct btf *btf, struct btfgen_info *info, + struct btf_type *btf_type, unsigned int id) +{ + return _btfgen_put_type(btf, info, btf_type, id, true); +} + static int btfgen_record_field_relo(struct btfgen_info *info, struct bpf_core_spec *targ_spec) { - return -EOPNOTSUPP; + struct btf *btf = (struct btf *) info->src_btf; + struct btfgen_type *btfgen_type; + struct btf_member *btf_member; + struct btf_type *btf_type; + struct btf_array *array; + unsigned int id; + int idx, err; + + btf_type = (struct btf_type *) btf__type_by_id(btf, targ_spec->root_type_id); + + /* create btfgen_type for root type */ + btfgen_type = btfgen_put_type(btf, info, btf_type, targ_spec->root_type_id); + if (!btfgen_type) + return -errno; + + /* add types for complex types (arrays, unions, structures) */ + for (int i = 1; i < targ_spec->raw_len; i++) { + /* skip typedefs and mods */ + while (btf_is_mod(btf_type) || btf_is_typedef(btf_type)) { + id = btf_type->type; + btfgen_type = btfgen_get_type(info, id); + if (!btfgen_type) + return -ENOENT; + btf_type = (struct btf_type *) btf__type_by_id(btf, id); + } + + switch (btf_kind(btf_type)) { + case BTF_KIND_STRUCT: + case BTF_KIND_UNION: + idx = targ_spec->raw_spec[i]; + btf_member = btf_members(btf_type) + idx; + btf_type = (struct btf_type *) btf__type_by_id(btf, btf_member->type); + + /* add member to relocation type */ + err = btfgen_add_member(btfgen_type, btf_member, idx); + if (err) + return err; + /* put btfgen type */ + btfgen_type = btfgen_put_type(btf, info, btf_type, btf_member->type); + if (!btfgen_type) + return -errno; + break; + case BTF_KIND_ARRAY: + array = btf_array(btf_type); + btfgen_type = btfgen_get_type(info, array->type); + if (!btfgen_type) + return -ENOENT; + btf_type = (struct btf_type *) btf__type_by_id(btf, array->type); + break; + default: + p_err("unsupported kind: %s (%d)", + btf_kind_str(btf_type), btf_type->type); + return -EINVAL; + } + } + + return 0; } static int btfgen_record_type_relo(struct btfgen_info *info, struct bpf_core_spec *targ_spec) { - return -EOPNOTSUPP; + struct btf *btf = (struct btf *) info->src_btf; + struct btfgen_type *btfgen_type; + struct btf_type *btf_type; + + btf_type = (struct btf_type *) btf__type_by_id(btf, targ_spec->root_type_id); + + btfgen_type = btfgen_put_type_all(btf, info, btf_type, targ_spec->root_type_id); + return btfgen_type ? 0 : -errno; } static int btfgen_record_enumval_relo(struct btfgen_info *info, struct bpf_core_spec *targ_spec) { - return -EOPNOTSUPP; + struct btf *btf = (struct btf *) info->src_btf; + struct btfgen_type *btfgen_type; + struct btf_type *btf_type; + + btf_type = (struct btf_type *) btf__type_by_id(btf, targ_spec->root_type_id); + + btfgen_type = btfgen_put_type_all(btf, info, btf_type, targ_spec->root_type_id); + return btfgen_type ? 0 : -errno; } static int btfgen_record_reloc(struct btfgen_info *info, struct bpf_core_spec *res)