| Message ID | 20240424154806.3417662-3-alan.maguire@oracle.com (mailing list archive) |
|---|---|
| State | Changes Requested |
| Delegated to: | BPF |
| Headers | show |
| Series | bpf: support resilient split BTF | expand |
On Wed, Apr 24, 2024 at 8:48 AM Alan Maguire <alan.maguire@oracle.com> wrote: > > To support more robust split BTF, adding supplemental context for the > base BTF type ids that split BTF refers to is required. Without such > references, a simple shuffling of base BTF type ids (without any other > significant change) invalidates the split BTF. Here the attempt is made > to store additional context to make split BTF more robust. > > This context comes in the form of distilled base BTF - this base BTF > constitutes the minimal BTF representation needed to disambiguate split BTF > references to base BTF. The rules are as follows: > > - INT, FLOAT are recorded in full. > - if a named base BTF STRUCT or UNION is referred to from split BTF, it > will be encoded either as a zero-member sized STRUCT/UNION (preserving > size for later relocation checks) or as a named FWD. Only base BTF > STRUCT/UNIONs that are embedded in split BTF STRUCT/UNIONs need to > preserve size information, so a FWD representation will be used in > most cases. > - if an ENUM[64] is named, a ENUM[64] forward representation (an ENUM[64] > with no values) is used. > - if a STRUCT, UNION, ENUM or ENUM64 is not named, it is recorded in full. > - base BTF reference types like CONST, RESTRICT, TYPEDEF, PTR are recorded > as-is. > > Avoiding struct/union/enum/enum64 expansion is important to keep the > distilled base BTF representation to a minimum size; however anonymous > struct, union and enum[64] types are represented in full since type details > are needed to disambiguate the reference - the name is not enough in those > cases since there is no name. In practice these are rare; in sample > cases where reference base BTF was generated for in-tree kernel modules, > only a few were needed in distilled base BTF. These represent the > anonymous struct/unions that are used by the module but were de-duplicated > to use base vmlinux BTF ids instead. > > When successful, new representations of the distilled base BTF and new > split BTF that refers to it are returned. Both need to be freed by the > caller. > > So to take a simple example, with split BTF with a type referring > to "struct sk_buff", we will generate base reference BTF with a > FWD struct sk_buff, and the split BTF will refer to it instead. > > Tools like pahole can utilize such split BTF to popuate the .BTF section typo: populate > (split BTF) and an additional .BTF.base section. > Then when the split BTF is loaded, the distilled base BTF can be used > to relocate split BTF to reference the current - and possibly changed - > base BTF. > > So for example if "struct sk_buff" was id 502 when the split BTF was > originally generated, we can use the distilled base BTF to see that > id 502 refers to a "struct sk_buff" and replace instances of id 502 > with the current (relocated) base BTF sk_buff type id. > > Distilled base BTF is small; when building a kernel with all modules > using distilled base BTF as a test, the average size for module > distilled base BTF is 1555 bytes (standard deviation 1563). The > maximum distilled base BTF size across ~2700 modules was 37895 bytes. > > Signed-off-by: Alan Maguire <alan.maguire@oracle.com> > --- > tools/lib/bpf/btf.c | 316 ++++++++++++++++++++++++++++++++++++++- > tools/lib/bpf/btf.h | 20 +++ > tools/lib/bpf/libbpf.map | 1 + > 3 files changed, 331 insertions(+), 6 deletions(-) > So, a few high-level notes. 1. I still think we should not add *anything* besides named structs/unions/enums into distilled base BTF. Unless proven otherwise, I don't see why we'd need them and complicate kernel-side. It's also not a big complication for libbpf and your code below is like 95% there anyways. See below about id map 2. I don't think we need to init id map to -1. 0 is always an "invalid" ID in the sense that no valid type has such ID. It's reserved for VOID and in this context could mean "not yet mapped" right after calloc(). 3. Please double-check the handling of all possible kinds (TYPE_TAG and DECL_TAG are notoriously missing, if I'm not missing anything myself) 4. we can use the same id map to remap those anonymous/copied types from original base BTF into new split BTF. We just map them to higher IDs (and append them to split BTF at the end). So we'll have a few interesting cases (for id map): a) id == 0, not yet mapped/visited/irrelevant b) id < btf__type_cnt(base_btf) -- remapped base BTF type in distilled BTF c) id >= btf__type_cnt(base_btf) -- remapped base BTF type appended to new split BTF (because anonymous or can't existing in distilled base BTF) remapping is trivial in this case. 5. it's minor, but it feel wasteful to waste 4 bytes per each type just to record "embedded" flag, we can just set highest bit to 1 for such IDs and account for that in the logic I described above and remapping overall. Again, it's minor, but feels wrong to allocate half a megabyte (my kernel has 130K types) just for those few bits. So, I think you are really close, let's try to iterate on this (both discussion and implementation) quickly and get it over the finish line. > diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c > index 44afae098369..419cc4fa2e86 100644 > --- a/tools/lib/bpf/btf.c > +++ b/tools/lib/bpf/btf.c > @@ -1771,9 +1771,8 @@ static int btf_rewrite_str(__u32 *str_off, void *ctx) > return 0; > } > [...] > static int btf_rewrite_type_ids(__u32 *type_id, void *ctx) > @@ -5217,3 +5223,301 @@ int btf_ext_visit_str_offs(struct btf_ext *btf_ext, str_off_visit_fn visit, void > > return 0; > } > + > +struct btf_distill_id { > + int id; > + bool embedded; /* true if id refers to a struct/union in base BTF > + * that is embedded in a split BTF struct/union. > + */ nit: add this multi-line comment before `bool embedded;` line > +}; > + [...] > + case BTF_KIND_STRUCT: > + case BTF_KIND_UNION: > + dist->ids[next_id].embedded = next_id > 0 && > + next_id <= dist->nr_base_types; hm... if next_id >= dist->nr_base_types, you are still overwriting some memory in dist->ids[next_id], no? And again, you are doing wrong < vs <= comparisons in nr_base_types (I think, please prove me wrong). > + return 0; > + default: > + return 0; > + } > + > + } while (next_id != 0); > + > + return 0; > +} > + > +static bool btf_is_eligible_named_fwd(const struct btf_type *t) > +{ > + return (btf_is_composite(t) || btf_is_any_enum(t)) && t->name_off != 0; > +} > + > +static int btf_add_distilled_type_ids(__u32 *id, void *ctx) > +{ > + struct btf_distill *dist = ctx; > + struct btf_type *t = btf_type_by_id(dist->pipe.src, *id); > + int ret; > + > + /* split BTF id, not needed */ > + if (*id > dist->nr_base_types) >=, no? otherwise we have access out of bounds of dist->ids array, I think > + return 0; > + /* already added ? */ > + if (dist->ids[*id].id >= 0) let's use > 0 to make very clear that zero is never a valid (mapped) ID > + return 0; > + dist->ids[*id].id = *id; > + [...] > +/* All split BTF ids will be shifted downwards since there are less base BTF > + * in distilled base BTF, and for those that refer to base BTF, we use the > + * reference map to map from original base BTF to distilled base BTF id. > + */ > +static int btf_update_distilled_type_ids(__u32 *id, void *ctx) > +{ > + struct btf_distill *dist = ctx; > + > + if (*id >= dist->nr_base_types) > + *id -= dist->diff_id; > + else > + *id = dist->ids[*id].id; > + return 0; > +} > + > +/* Create updated /split BTF with distilled base BTF; distilled base BTF /split -- was it supposed to be an emphasis, like "/split/" ? > + * consists of BTF information required to clarify the types that split > + * BTF refers to, omitting unneeded details. Specifically it will contain > + * base types and forward declarations of structs, unions and enumerated > + * types, along with associated reference types like pointers, arrays etc. > + * > + * The only case where structs, unions or enumerated types are fully represented > + * is when they are anonymous; in such cases, info about type content is needed > + * to clarify type references. > + * > + * We return newly-created split BTF where the split BTf refers to a newly-created BTf -> BTF > + * distilled base BTF. Both must be freed separately by the caller. > + * > + * When creating the BTF representation for a module and provided with the > + * distilled_base option, pahole will create split BTF using this API, and store > + * the distilled base BTF in the .BTF.base.distilled section. .BTF.base.distilled is outdated, update? It's also kind of unusual to explain specific .BTF.base and pahole convention. I guess it's fine to refer to pahole and .BTF.base, but more like an example (this is minor)? > + */ > +int btf__distill_base(const struct btf *src_btf, struct btf **new_base_btf, > + struct btf **new_split_btf) > +{ > + struct btf *new_base = NULL, *new_split = NULL; > + unsigned int n = btf__type_cnt(src_btf); > + struct btf_distill dist = {}; > + struct btf_type *t; > + __u32 i, id = 0; > + int ret = 0; > + > + /* src BTF must be split BTF. */ > + if (!new_base_btf || !new_split_btf || !btf__base_btf(src_btf)) { > + errno = EINVAL; > + return -EINVAL; use `return libbpf_err(-EINVAL);` here? > + } > + new_base = btf__new_empty(); > + if (!new_base) > + return -ENOMEM; libbpf_err() > + dist.ids = calloc(n, sizeof(*dist.ids)); > + if (!dist.ids) { > + ret = -ENOMEM; > + goto err_out; > + } > + for (i = 1; i < n; i++) > + dist.ids[i].id = -1; > + dist.pipe.src = src_btf; > + dist.pipe.dst = new_base; > + dist.pipe.str_off_map = hashmap__new(btf_dedup_identity_hash_fn, btf_dedup_equal_fn, NULL); > + if (IS_ERR(dist.pipe.str_off_map)) { > + ret = -ENOMEM; > + goto err_out; > + } > + dist.nr_base_types = btf__type_cnt(btf__base_btf(src_btf)); > + > + /* Pass over src split BTF; generate the list of base BTF > + * type ids it references; these will constitute our distilled > + * base BTF set. > + */ > + for (i = src_btf->start_id; i < n; i++) { > + t = (struct btf_type *)btf__type_by_id(src_btf, i); btf_type_by_id() exists (as internal helper) exactly to not do these casts > + > + /* check if members of struct/union in split BTF refer to base BTF > + * struct/union; if so, we will use an empty sized struct to represent > + * it rather than a FWD because its size must match on later BTF > + * relocation. > + */ > + if (btf_is_composite(t)) { > + ret = btf_type_visit_type_ids(t, btf_find_embedded_composite_type_ids, > + &dist); > + if (ret < 0) > + goto err_out; > + } > + ret = btf_type_visit_type_ids(t, btf_add_distilled_type_ids, &dist); > + if (ret < 0) > + goto err_out; > + } > + /* Next add types for each of the required references. */ > + for (i = 1; i < src_btf->start_id; i++) { I think you have dist.nr_base_types, let's use that as it's more explicit? > + if (dist.ids[i].id < 0) > + continue; > + t = btf_type_by_id(src_btf, i); > + > + if (dist.ids[i].embedded) { > + /* If a named struct/union in base BTF is referenced as a type > + * in split BTF without use of a pointer - i.e. as an embedded > + * struct/union - add an empty struct/union preserving size > + * since size must be consistent when relocating split and > + * possibly changed base BTF. > + */ > + ret = btf_add_composite(new_base, btf_kind(t), > + btf__name_by_offset(src_btf, t->name_off), nit: look up name ahead of time (it's fine to pass zero to btf__name_by_offset()), and use it below for btf__add_fwd() as well > + t->size); > + } else if (btf_is_eligible_named_fwd(t)) { > + enum btf_fwd_kind fwd_kind; > + > + /* If not embedded, use a fwd for named struct/unions since we > + * can match via name without any other details. > + */ > + switch (btf_kind(t)) { > + case BTF_KIND_STRUCT: > + fwd_kind = BTF_FWD_STRUCT; > + break; > + case BTF_KIND_UNION: > + fwd_kind = BTF_FWD_UNION; > + break; > + case BTF_KIND_ENUM: > + fwd_kind = BTF_FWD_ENUM; > + break; > + case BTF_KIND_ENUM64: > + fwd_kind = BTF_FWD_ENUM64; > + break; it feels like if you just have case BTF_KIND_ENUM: case BTF_KIND_ENUM64: fwd_kind = BTF_FWD_ENUM; break; we wouldn't lose anything and wouldn't need patch #1 > + default: > + pr_warn("unexpected kind [%u] when creating distilled base BTF.\n", > + btf_kind(t)); > + goto err_out; > + } > + ret = btf__add_fwd(new_base, btf__name_by_offset(src_btf, t->name_off), > + fwd_kind); > + } else { > + ret = btf_add_type(&dist.pipe, t); > + } > + if (ret < 0) > + goto err_out; > + dist.ids[i].id = ++id; > + } > + /* now create new split BTF with distilled base BTF as its base; we end up with > + * split BTF that has base BTF that represents enough about its base references > + * to allow it to be relocated with the base BTF available. > + */ > + new_split = btf__new_empty_split(new_base); > + if (!new_split_btf) { > + ret = libbpf_get_error(new_split); please don't add new uses of libbpf_get_error(), `ret = -errno` > + goto err_out; > + } > + > + dist.pipe.dst = new_split; > + /* all split BTF ids will be shifted downwards since there are less base BTF ids > + * in distilled base BTF. > + */ > + dist.diff_id = dist.nr_base_types - btf__type_cnt(new_base); > + > + /* First add all split types */ > + for (i = src_btf->start_id; i < n; i++) { > + t = btf_type_by_id(src_btf, i); > + ret = btf_add_type(&dist.pipe, t); > + if (ret < 0) > + goto err_out; > + } > + n = btf__type_cnt(new_split); > + /* Now update base/split BTF ids. */ > + for (i = 1; i < n; i++) { > + t = btf_type_by_id(new_split, i); > + > + ret = btf_type_visit_type_ids(t, btf_update_distilled_type_ids, &dist); > + if (ret < 0) > + goto err_out; > + } > + free(dist.ids); > + hashmap__free(dist.pipe.str_off_map); > + *new_base_btf = new_base; > + *new_split_btf = new_split; > + return 0; > +err_out: > + free(dist.ids); > + hashmap__free(dist.pipe.str_off_map); > + btf__free(new_split); > + btf__free(new_base); > + errno = -ret; > + return ret; libbpf_err(ret), but also s/ret/err/, it is literally error value or zero (for success) > +} > diff --git a/tools/lib/bpf/btf.h b/tools/lib/bpf/btf.h > index 47d3e00b25c7..025ed28b7fe8 100644 > --- a/tools/lib/bpf/btf.h > +++ b/tools/lib/bpf/btf.h > @@ -107,6 +107,26 @@ LIBBPF_API struct btf *btf__new_empty(void); > */ > LIBBPF_API struct btf *btf__new_empty_split(struct btf *base_btf); > > +/** > + * @brief **btf__distill_base()** creates new versions of the split BTF > + * *src_btf* and its base BTF. The new base BTF will only contain the types nit: extra spaces after '.' > + * needed to improve robustness of the split BTF to small changes in base BTF. > + * When that split BTF is loaded against a (possibly changed) base, this > + * distilled base BTF will help update references to that (possibly changed) > + * base BTF. > + * > + * Both the new split and its associated new base BTF must be freed by > + * the caller. > + * > + * If successful, 0 is returned and **new_base_btf** and **new_split_btf** > + * will point at new base/split BTF. Both the new split and its associated nit: extra spaces after '.' > + * new base BTF must be freed by the caller. > + * > + * A negative value is returned on error. > + */ > +LIBBPF_API int btf__distill_base(const struct btf *src_btf, struct btf **new_base_btf, > + struct btf **new_split_btf); > + > LIBBPF_API struct btf *btf__parse(const char *path, struct btf_ext **btf_ext); > LIBBPF_API struct btf *btf__parse_split(const char *path, struct btf *base_btf); > LIBBPF_API struct btf *btf__parse_elf(const char *path, struct btf_ext **btf_ext); > diff --git a/tools/lib/bpf/libbpf.map b/tools/lib/bpf/libbpf.map > index c1ce8aa3520b..c4d9bd7d3220 100644 > --- a/tools/lib/bpf/libbpf.map > +++ b/tools/lib/bpf/libbpf.map > @@ -420,6 +420,7 @@ LIBBPF_1.4.0 { > LIBBPF_1.5.0 { > global: > bpf_program__attach_sockmap; > + btf__distill_base; nit: '_' orders before 'p' > ring__consume_n; > ring_buffer__consume_n; > } LIBBPF_1.4.0; > -- > 2.31.1 >
On Wed, 2024-04-24 at 16:47 +0100, Alan Maguire wrote: Hi Alan, Looked through the patch, noted a few minor logical inconsistencies. Agree with Andrii's comments about memory size allocated for dist.ids. Otherwise this patch makes sense to me. [...] > @@ -5217,3 +5223,301 @@ int btf_ext_visit_str_offs(struct btf_ext *btf_ext, str_off_visit_fn visit, void > > return 0; > } > + > +struct btf_distill_id { > + int id; > + bool embedded; /* true if id refers to a struct/union in base BTF > + * that is embedded in a split BTF struct/union. > + */ > +}; > + > +struct btf_distill { > + struct btf_pipe pipe; > + struct btf_distill_id *ids; > + __u32 query_id; > + unsigned int nr_base_types; > + unsigned int diff_id; > +}; > + > +/* Check if a member of a split BTF struct/union refers to a base BTF > + * struct/union. Members can be const/restrict/volatile/typedef > + * reference types, but if a pointer is encountered, type is no longer > + * considered embedded. > + */ > +static int btf_find_embedded_composite_type_ids(__u32 *id, void *ctx) > +{ > + struct btf_distill *dist = ctx; > + const struct btf_type *t; > + __u32 next_id = *id; > + > + do { > + if (next_id == 0) > + return 0; > + t = btf_type_by_id(dist->pipe.src, next_id); > + switch (btf_kind(t)) { > + case BTF_KIND_CONST: > + case BTF_KIND_RESTRICT: > + case BTF_KIND_VOLATILE: > + case BTF_KIND_TYPEDEF: I think BTF_KIND_TYPE_TAG is missing. > + next_id = t->type; > + break; > + case BTF_KIND_ARRAY: { > + struct btf_array *a = btf_array(t); > + > + next_id = a->type; > + break; > + } > + case BTF_KIND_STRUCT: > + case BTF_KIND_UNION: > + dist->ids[next_id].embedded = next_id > 0 && > + next_id <= dist->nr_base_types; I think next_id can't be zero, otherwise it's kind would be UNKN. Also, should this be 'next_id < dist->nr_base_types'? __u32 btf__type_cnt(const struct btf *btf) { return btf->start_id + btf->nr_types; } static struct btf *btf_new(const void *data, __u32 size, struct btf *base_btf) { ... btf->nr_types = 0; btf->start_id = 1; ... if (base_btf) { ... btf->start_id = btf__type_cnt(base_btf); ... } ... } int btf__distill_base(const struct btf *src_btf, struct btf **new_base_btf, struct btf **new_split_btf) { ... dist.nr_base_types = btf__type_cnt(btf__base_btf(src_btf)); ... } So, suppose there is only one base type: - it's ID would be 1; - nr_types would be 1; - nr_base_types would be 2; - meaning that split BTF ids would start from 2. Maybe use .split_start_id instead of .nr_base_types to avoid confusion? > + return 0; > + default: > + return 0; > + } > + > + } while (next_id != 0); > + > + return 0; > +}
On 01/05/2024 00:06, Eduard Zingerman wrote: > On Wed, 2024-04-24 at 16:47 +0100, Alan Maguire wrote: > > Hi Alan, > > Looked through the patch, noted a few minor logical inconsistencies. > Agree with Andrii's comments about memory size allocated for dist.ids. > Otherwise this patch makes sense to me. > thanks for taking a look! I'm working on an updated series incorporating the approach of limiting distilled base to named struct/union/enum types, hope to have that ready by the end of the week. It will also OR in flags to mark types as embedded as per Andrii and your suggestion. A bit more below.. > [...] > >> @@ -5217,3 +5223,301 @@ int btf_ext_visit_str_offs(struct btf_ext *btf_ext, str_off_visit_fn visit, void >> >> return 0; >> } >> + >> +struct btf_distill_id { >> + int id; >> + bool embedded; /* true if id refers to a struct/union in base BTF >> + * that is embedded in a split BTF struct/union. >> + */ >> +}; >> + >> +struct btf_distill { >> + struct btf_pipe pipe; >> + struct btf_distill_id *ids; >> + __u32 query_id; >> + unsigned int nr_base_types; >> + unsigned int diff_id; >> +}; >> + >> +/* Check if a member of a split BTF struct/union refers to a base BTF >> + * struct/union. Members can be const/restrict/volatile/typedef >> + * reference types, but if a pointer is encountered, type is no longer >> + * considered embedded. >> + */ >> +static int btf_find_embedded_composite_type_ids(__u32 *id, void *ctx) >> +{ >> + struct btf_distill *dist = ctx; >> + const struct btf_type *t; >> + __u32 next_id = *id; >> + >> + do { >> + if (next_id == 0) >> + return 0; >> + t = btf_type_by_id(dist->pipe.src, next_id); >> + switch (btf_kind(t)) { >> + case BTF_KIND_CONST: >> + case BTF_KIND_RESTRICT: >> + case BTF_KIND_VOLATILE: >> + case BTF_KIND_TYPEDEF: > > I think BTF_KIND_TYPE_TAG is missing. > It's implicit in the default clause; I can't see a case for having a split BTF type tag base BTF types, but I might be missing something there. I can make all the unexpected types explicit if that would be clearer? >> + next_id = t->type; >> + break; >> + case BTF_KIND_ARRAY: { >> + struct btf_array *a = btf_array(t); >> + >> + next_id = a->type; >> + break; >> + } >> + case BTF_KIND_STRUCT: >> + case BTF_KIND_UNION: >> + dist->ids[next_id].embedded = next_id > 0 && >> + next_id <= dist->nr_base_types; > > I think next_id can't be zero, otherwise it's kind would be UNKN. > Also, should this be 'next_id < dist->nr_base_types'? > yeah this needs to be fixed; also isn't worth range-checking this as it's got to be a base type AFAICT. > __u32 btf__type_cnt(const struct btf *btf) > { > return btf->start_id + btf->nr_types; > } > > static struct btf *btf_new(const void *data, __u32 size, struct btf *base_btf) > { > ... > btf->nr_types = 0; > btf->start_id = 1; > ... > if (base_btf) { > ... > btf->start_id = btf__type_cnt(base_btf); > ... > } > ... > } > > int btf__distill_base(const struct btf *src_btf, struct btf **new_base_btf, > struct btf **new_split_btf) > { > ... > dist.nr_base_types = btf__type_cnt(btf__base_btf(src_btf)); > ... > } > > So, suppose there is only one base type: > - it's ID would be 1; > - nr_types would be 1; > - nr_base_types would be 2; > - meaning that split BTF ids would start from 2. > > Maybe use .split_start_id instead of .nr_base_types to avoid confusion? > good idea, will fix. thanks! >> + return 0; >> + default: >> + return 0; >> + } >> + >> + } while (next_id != 0); >> + >> + return 0; >> +}
On Wed, 2024-05-01 at 18:29 +0100, Alan Maguire wrote: [...] > > > +/* Check if a member of a split BTF struct/union refers to a base BTF > > > + * struct/union. Members can be const/restrict/volatile/typedef > > > + * reference types, but if a pointer is encountered, type is no longer > > > + * considered embedded. > > > + */ > > > +static int btf_find_embedded_composite_type_ids(__u32 *id, void *ctx) > > > +{ > > > + struct btf_distill *dist = ctx; > > > + const struct btf_type *t; > > > + __u32 next_id = *id; > > > + > > > + do { > > > + if (next_id == 0) > > > + return 0; > > > + t = btf_type_by_id(dist->pipe.src, next_id); > > > + switch (btf_kind(t)) { > > > + case BTF_KIND_CONST: > > > + case BTF_KIND_RESTRICT: > > > + case BTF_KIND_VOLATILE: > > > + case BTF_KIND_TYPEDEF: > > > > I think BTF_KIND_TYPE_TAG is missing. > > > > It's implicit in the default clause; I can't see a case for having a > split BTF type tag base BTF types, but I might be missing something > there. I can make all the unexpected types explicit if that would be > clearer? I mean, this skips a series of modifiers, e.g.: struct buz { // next_id will get to 'struct bar' eventually const volatile struct bar foo; } Now, it is legal to have this chain like below: struct buz { const volatile __type_tag("quux") struct bar foo; } In which case the traversal does not have to stop. Am I confused? (Note: at the moment type tags are only applied to pointers but that would change in the future, I have a stalled LLVM change for this). [...]
On 01/05/2024 18:43, Eduard Zingerman wrote: > On Wed, 2024-05-01 at 18:29 +0100, Alan Maguire wrote: > > [...] > >>>> +/* Check if a member of a split BTF struct/union refers to a base BTF >>>> + * struct/union. Members can be const/restrict/volatile/typedef >>>> + * reference types, but if a pointer is encountered, type is no longer >>>> + * considered embedded. >>>> + */ >>>> +static int btf_find_embedded_composite_type_ids(__u32 *id, void *ctx) >>>> +{ >>>> + struct btf_distill *dist = ctx; >>>> + const struct btf_type *t; >>>> + __u32 next_id = *id; >>>> + >>>> + do { >>>> + if (next_id == 0) >>>> + return 0; >>>> + t = btf_type_by_id(dist->pipe.src, next_id); >>>> + switch (btf_kind(t)) { >>>> + case BTF_KIND_CONST: >>>> + case BTF_KIND_RESTRICT: >>>> + case BTF_KIND_VOLATILE: >>>> + case BTF_KIND_TYPEDEF: >>> >>> I think BTF_KIND_TYPE_TAG is missing. >>> >> >> It's implicit in the default clause; I can't see a case for having a >> split BTF type tag base BTF types, but I might be missing something >> there. I can make all the unexpected types explicit if that would be >> clearer? > > I mean, this skips a series of modifiers, e.g.: > > struct buz { > // next_id will get to 'struct bar' eventually > const volatile struct bar foo; > } > > Now, it is legal to have this chain like below: > > struct buz { > const volatile __type_tag("quux") struct bar foo; > } > > In which case the traversal does not have to stop. > Am I confused? > no, sorry, I was! You're absolutely right, BTF_KIND_TYPE_TAG needs to be accounted for here. Thanks for catching this! > (Note: at the moment type tags are only applied to pointers but that > would change in the future, I have a stalled LLVM change for this). > > [...]
diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index 44afae098369..419cc4fa2e86 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -1771,9 +1771,8 @@ static int btf_rewrite_str(__u32 *str_off, void *ctx) return 0; } -int btf__add_type(struct btf *btf, const struct btf *src_btf, const struct btf_type *src_type) +static int btf_add_type(struct btf_pipe *p, const struct btf_type *src_type) { - struct btf_pipe p = { .src = src_btf, .dst = btf }; struct btf_type *t; int sz, err; @@ -1782,20 +1781,27 @@ int btf__add_type(struct btf *btf, const struct btf *src_btf, const struct btf_t return libbpf_err(sz); /* deconstruct BTF, if necessary, and invalidate raw_data */ - if (btf_ensure_modifiable(btf)) + if (btf_ensure_modifiable(p->dst)) return libbpf_err(-ENOMEM); - t = btf_add_type_mem(btf, sz); + t = btf_add_type_mem(p->dst, sz); if (!t) return libbpf_err(-ENOMEM); memcpy(t, src_type, sz); - err = btf_type_visit_str_offs(t, btf_rewrite_str, &p); + err = btf_type_visit_str_offs(t, btf_rewrite_str, p); if (err) return libbpf_err(err); - return btf_commit_type(btf, sz); + return btf_commit_type(p->dst, sz); +} + +int btf__add_type(struct btf *btf, const struct btf *src_btf, const struct btf_type *src_type) +{ + struct btf_pipe p = { .src = src_btf, .dst = btf }; + + return btf_add_type(&p, src_type); } static int btf_rewrite_type_ids(__u32 *type_id, void *ctx) @@ -5217,3 +5223,301 @@ int btf_ext_visit_str_offs(struct btf_ext *btf_ext, str_off_visit_fn visit, void return 0; } + +struct btf_distill_id { + int id; + bool embedded; /* true if id refers to a struct/union in base BTF + * that is embedded in a split BTF struct/union. + */ +}; + +struct btf_distill { + struct btf_pipe pipe; + struct btf_distill_id *ids; + __u32 query_id; + unsigned int nr_base_types; + unsigned int diff_id; +}; + +/* Check if a member of a split BTF struct/union refers to a base BTF + * struct/union. Members can be const/restrict/volatile/typedef + * reference types, but if a pointer is encountered, type is no longer + * considered embedded. + */ +static int btf_find_embedded_composite_type_ids(__u32 *id, void *ctx) +{ + struct btf_distill *dist = ctx; + const struct btf_type *t; + __u32 next_id = *id; + + do { + if (next_id == 0) + return 0; + t = btf_type_by_id(dist->pipe.src, next_id); + switch (btf_kind(t)) { + case BTF_KIND_CONST: + case BTF_KIND_RESTRICT: + case BTF_KIND_VOLATILE: + case BTF_KIND_TYPEDEF: + next_id = t->type; + break; + case BTF_KIND_ARRAY: { + struct btf_array *a = btf_array(t); + + next_id = a->type; + break; + } + case BTF_KIND_STRUCT: + case BTF_KIND_UNION: + dist->ids[next_id].embedded = next_id > 0 && + next_id <= dist->nr_base_types; + return 0; + default: + return 0; + } + + } while (next_id != 0); + + return 0; +} + +static bool btf_is_eligible_named_fwd(const struct btf_type *t) +{ + return (btf_is_composite(t) || btf_is_any_enum(t)) && t->name_off != 0; +} + +static int btf_add_distilled_type_ids(__u32 *id, void *ctx) +{ + struct btf_distill *dist = ctx; + struct btf_type *t = btf_type_by_id(dist->pipe.src, *id); + int ret; + + /* split BTF id, not needed */ + if (*id > dist->nr_base_types) + return 0; + /* already added ? */ + if (dist->ids[*id].id >= 0) + return 0; + dist->ids[*id].id = *id; + + /* only a subset of base BTF types should be referenced from split + * BTF; ensure nothing unexpected is referenced. + */ + switch (btf_kind(t)) { + case BTF_KIND_INT: + case BTF_KIND_FLOAT: + case BTF_KIND_ARRAY: + case BTF_KIND_STRUCT: + case BTF_KIND_UNION: + case BTF_KIND_TYPEDEF: + case BTF_KIND_ENUM: + case BTF_KIND_ENUM64: + case BTF_KIND_PTR: + case BTF_KIND_CONST: + case BTF_KIND_RESTRICT: + case BTF_KIND_VOLATILE: + case BTF_KIND_FUNC_PROTO: + break; + default: + pr_warn("unexpected reference to base type[%u] of kind [%u] when creating distilled base BTF.\n", + *id, btf_kind(t)); + return -EINVAL; + } + + /* struct/union members not needed, except for anonymous structs + * and unions, which we need since name won't help us determine + * matches; so if a named struct/union, no need to recurse + * into members. + */ + if (btf_is_eligible_named_fwd(t)) + return 0; + + /* ensure references in type are added also. */ + ret = btf_type_visit_type_ids(t, btf_add_distilled_type_ids, ctx); + if (ret < 0) + return ret; + return 0; +} + +/* All split BTF ids will be shifted downwards since there are less base BTF + * in distilled base BTF, and for those that refer to base BTF, we use the + * reference map to map from original base BTF to distilled base BTF id. + */ +static int btf_update_distilled_type_ids(__u32 *id, void *ctx) +{ + struct btf_distill *dist = ctx; + + if (*id >= dist->nr_base_types) + *id -= dist->diff_id; + else + *id = dist->ids[*id].id; + return 0; +} + +/* Create updated /split BTF with distilled base BTF; distilled base BTF + * consists of BTF information required to clarify the types that split + * BTF refers to, omitting unneeded details. Specifically it will contain + * base types and forward declarations of structs, unions and enumerated + * types, along with associated reference types like pointers, arrays etc. + * + * The only case where structs, unions or enumerated types are fully represented + * is when they are anonymous; in such cases, info about type content is needed + * to clarify type references. + * + * We return newly-created split BTF where the split BTf refers to a newly-created + * distilled base BTF. Both must be freed separately by the caller. + * + * When creating the BTF representation for a module and provided with the + * distilled_base option, pahole will create split BTF using this API, and store + * the distilled base BTF in the .BTF.base.distilled section. + */ +int btf__distill_base(const struct btf *src_btf, struct btf **new_base_btf, + struct btf **new_split_btf) +{ + struct btf *new_base = NULL, *new_split = NULL; + unsigned int n = btf__type_cnt(src_btf); + struct btf_distill dist = {}; + struct btf_type *t; + __u32 i, id = 0; + int ret = 0; + + /* src BTF must be split BTF. */ + if (!new_base_btf || !new_split_btf || !btf__base_btf(src_btf)) { + errno = EINVAL; + return -EINVAL; + } + new_base = btf__new_empty(); + if (!new_base) + return -ENOMEM; + dist.ids = calloc(n, sizeof(*dist.ids)); + if (!dist.ids) { + ret = -ENOMEM; + goto err_out; + } + for (i = 1; i < n; i++) + dist.ids[i].id = -1; + dist.pipe.src = src_btf; + dist.pipe.dst = new_base; + dist.pipe.str_off_map = hashmap__new(btf_dedup_identity_hash_fn, btf_dedup_equal_fn, NULL); + if (IS_ERR(dist.pipe.str_off_map)) { + ret = -ENOMEM; + goto err_out; + } + dist.nr_base_types = btf__type_cnt(btf__base_btf(src_btf)); + + /* Pass over src split BTF; generate the list of base BTF + * type ids it references; these will constitute our distilled + * base BTF set. + */ + for (i = src_btf->start_id; i < n; i++) { + t = (struct btf_type *)btf__type_by_id(src_btf, i); + + /* check if members of struct/union in split BTF refer to base BTF + * struct/union; if so, we will use an empty sized struct to represent + * it rather than a FWD because its size must match on later BTF + * relocation. + */ + if (btf_is_composite(t)) { + ret = btf_type_visit_type_ids(t, btf_find_embedded_composite_type_ids, + &dist); + if (ret < 0) + goto err_out; + } + ret = btf_type_visit_type_ids(t, btf_add_distilled_type_ids, &dist); + if (ret < 0) + goto err_out; + } + /* Next add types for each of the required references. */ + for (i = 1; i < src_btf->start_id; i++) { + if (dist.ids[i].id < 0) + continue; + t = btf_type_by_id(src_btf, i); + + if (dist.ids[i].embedded) { + /* If a named struct/union in base BTF is referenced as a type + * in split BTF without use of a pointer - i.e. as an embedded + * struct/union - add an empty struct/union preserving size + * since size must be consistent when relocating split and + * possibly changed base BTF. + */ + ret = btf_add_composite(new_base, btf_kind(t), + btf__name_by_offset(src_btf, t->name_off), + t->size); + } else if (btf_is_eligible_named_fwd(t)) { + enum btf_fwd_kind fwd_kind; + + /* If not embedded, use a fwd for named struct/unions since we + * can match via name without any other details. + */ + switch (btf_kind(t)) { + case BTF_KIND_STRUCT: + fwd_kind = BTF_FWD_STRUCT; + break; + case BTF_KIND_UNION: + fwd_kind = BTF_FWD_UNION; + break; + case BTF_KIND_ENUM: + fwd_kind = BTF_FWD_ENUM; + break; + case BTF_KIND_ENUM64: + fwd_kind = BTF_FWD_ENUM64; + break; + default: + pr_warn("unexpected kind [%u] when creating distilled base BTF.\n", + btf_kind(t)); + goto err_out; + } + ret = btf__add_fwd(new_base, btf__name_by_offset(src_btf, t->name_off), + fwd_kind); + } else { + ret = btf_add_type(&dist.pipe, t); + } + if (ret < 0) + goto err_out; + dist.ids[i].id = ++id; + } + /* now create new split BTF with distilled base BTF as its base; we end up with + * split BTF that has base BTF that represents enough about its base references + * to allow it to be relocated with the base BTF available. + */ + new_split = btf__new_empty_split(new_base); + if (!new_split_btf) { + ret = libbpf_get_error(new_split); + goto err_out; + } + + dist.pipe.dst = new_split; + /* all split BTF ids will be shifted downwards since there are less base BTF ids + * in distilled base BTF. + */ + dist.diff_id = dist.nr_base_types - btf__type_cnt(new_base); + + /* First add all split types */ + for (i = src_btf->start_id; i < n; i++) { + t = btf_type_by_id(src_btf, i); + ret = btf_add_type(&dist.pipe, t); + if (ret < 0) + goto err_out; + } + n = btf__type_cnt(new_split); + /* Now update base/split BTF ids. */ + for (i = 1; i < n; i++) { + t = btf_type_by_id(new_split, i); + + ret = btf_type_visit_type_ids(t, btf_update_distilled_type_ids, &dist); + if (ret < 0) + goto err_out; + } + free(dist.ids); + hashmap__free(dist.pipe.str_off_map); + *new_base_btf = new_base; + *new_split_btf = new_split; + return 0; +err_out: + free(dist.ids); + hashmap__free(dist.pipe.str_off_map); + btf__free(new_split); + btf__free(new_base); + errno = -ret; + return ret; +} diff --git a/tools/lib/bpf/btf.h b/tools/lib/bpf/btf.h index 47d3e00b25c7..025ed28b7fe8 100644 --- a/tools/lib/bpf/btf.h +++ b/tools/lib/bpf/btf.h @@ -107,6 +107,26 @@ LIBBPF_API struct btf *btf__new_empty(void); */ LIBBPF_API struct btf *btf__new_empty_split(struct btf *base_btf); +/** + * @brief **btf__distill_base()** creates new versions of the split BTF + * *src_btf* and its base BTF. The new base BTF will only contain the types + * needed to improve robustness of the split BTF to small changes in base BTF. + * When that split BTF is loaded against a (possibly changed) base, this + * distilled base BTF will help update references to that (possibly changed) + * base BTF. + * + * Both the new split and its associated new base BTF must be freed by + * the caller. + * + * If successful, 0 is returned and **new_base_btf** and **new_split_btf** + * will point at new base/split BTF. Both the new split and its associated + * new base BTF must be freed by the caller. + * + * A negative value is returned on error. + */ +LIBBPF_API int btf__distill_base(const struct btf *src_btf, struct btf **new_base_btf, + struct btf **new_split_btf); + LIBBPF_API struct btf *btf__parse(const char *path, struct btf_ext **btf_ext); LIBBPF_API struct btf *btf__parse_split(const char *path, struct btf *base_btf); LIBBPF_API struct btf *btf__parse_elf(const char *path, struct btf_ext **btf_ext); diff --git a/tools/lib/bpf/libbpf.map b/tools/lib/bpf/libbpf.map index c1ce8aa3520b..c4d9bd7d3220 100644 --- a/tools/lib/bpf/libbpf.map +++ b/tools/lib/bpf/libbpf.map @@ -420,6 +420,7 @@ LIBBPF_1.4.0 { LIBBPF_1.5.0 { global: bpf_program__attach_sockmap; + btf__distill_base; ring__consume_n; ring_buffer__consume_n; } LIBBPF_1.4.0;
To support more robust split BTF, adding supplemental context for the base BTF type ids that split BTF refers to is required. Without such references, a simple shuffling of base BTF type ids (without any other significant change) invalidates the split BTF. Here the attempt is made to store additional context to make split BTF more robust. This context comes in the form of distilled base BTF - this base BTF constitutes the minimal BTF representation needed to disambiguate split BTF references to base BTF. The rules are as follows: - INT, FLOAT are recorded in full. - if a named base BTF STRUCT or UNION is referred to from split BTF, it will be encoded either as a zero-member sized STRUCT/UNION (preserving size for later relocation checks) or as a named FWD. Only base BTF STRUCT/UNIONs that are embedded in split BTF STRUCT/UNIONs need to preserve size information, so a FWD representation will be used in most cases. - if an ENUM[64] is named, a ENUM[64] forward representation (an ENUM[64] with no values) is used. - if a STRUCT, UNION, ENUM or ENUM64 is not named, it is recorded in full. - base BTF reference types like CONST, RESTRICT, TYPEDEF, PTR are recorded as-is. Avoiding struct/union/enum/enum64 expansion is important to keep the distilled base BTF representation to a minimum size; however anonymous struct, union and enum[64] types are represented in full since type details are needed to disambiguate the reference - the name is not enough in those cases since there is no name. In practice these are rare; in sample cases where reference base BTF was generated for in-tree kernel modules, only a few were needed in distilled base BTF. These represent the anonymous struct/unions that are used by the module but were de-duplicated to use base vmlinux BTF ids instead. When successful, new representations of the distilled base BTF and new split BTF that refers to it are returned. Both need to be freed by the caller. So to take a simple example, with split BTF with a type referring to "struct sk_buff", we will generate base reference BTF with a FWD struct sk_buff, and the split BTF will refer to it instead. Tools like pahole can utilize such split BTF to popuate the .BTF section (split BTF) and an additional .BTF.base section. Then when the split BTF is loaded, the distilled base BTF can be used to relocate split BTF to reference the current - and possibly changed - base BTF. So for example if "struct sk_buff" was id 502 when the split BTF was originally generated, we can use the distilled base BTF to see that id 502 refers to a "struct sk_buff" and replace instances of id 502 with the current (relocated) base BTF sk_buff type id. Distilled base BTF is small; when building a kernel with all modules using distilled base BTF as a test, the average size for module distilled base BTF is 1555 bytes (standard deviation 1563). The maximum distilled base BTF size across ~2700 modules was 37895 bytes. Signed-off-by: Alan Maguire <alan.maguire@oracle.com> --- tools/lib/bpf/btf.c | 316 ++++++++++++++++++++++++++++++++++++++- tools/lib/bpf/btf.h | 20 +++ tools/lib/bpf/libbpf.map | 1 + 3 files changed, 331 insertions(+), 6 deletions(-)