From: Donglin Peng Implement validation of BTF type ordering to enable efficient binary search for sorted BTF. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Cc: Xiaoqin Zhang Signed-off-by: Donglin Peng --- kernel/bpf/btf.c | 64 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 64 insertions(+) diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c index 5dd2c40d4874..e9d102360292 100644 --- a/kernel/bpf/btf.c +++ b/kernel/bpf/btf.c @@ -550,6 +550,66 @@ u32 btf_nr_types(const struct btf *btf) return total; } +/* Anonymous types (with empty names) are considered greater than named types + * and are sorted after them. Two anonymous types are considered equal. Named + * types are compared lexicographically. + */ +static int btf_compare_type_names(const void *a, const void *b, void *priv) +{ + struct btf *btf = (struct btf *)priv; + const struct btf_type *ta = btf_type_by_id(btf, *(__u32 *)a); + const struct btf_type *tb = btf_type_by_id(btf, *(__u32 *)b); + const char *na, *nb; + + if (!ta->name_off && tb->name_off) + return 1; + if (ta->name_off && !tb->name_off) + return -1; + if (!ta->name_off && !tb->name_off) + return 0; + + na = btf_name_by_offset(btf, ta->name_off); + nb = btf_name_by_offset(btf, tb->name_off); + return strcmp(na, nb); +} + +/* Verifies that BTF types are sorted in ascending order according to their + * names, with named types appearing before anonymous types. If the ordering + * is correct, counts the number of named types and updates the BTF object's + * nr_sorted_types field. Note that vmlinux and kernel module BTFs are sorted + * during the building phase, so the validation logic only needs to count the + * named types. + */ +static void btf_check_sorted(struct btf *btf) +{ + const struct btf_type *t; + int i, n, k = 0, nr_sorted_types; + bool skip_cmp = btf_is_kernel(btf); + + if (btf->nr_types < 2) + return; + + nr_sorted_types = 0; + n = btf_nr_types(btf) - 1; + for (i = btf_start_id(btf); i < n; i++) { + k = i + 1; + if (!skip_cmp && btf_compare_type_names(&i, &k, btf) > 0) + return; + + t = btf_type_by_id(btf, i); + if (t->name_off) + nr_sorted_types++; + else if (skip_cmp) + break; + } + + t = btf_type_by_id(btf, k); + if (t->name_off) + nr_sorted_types++; + if (nr_sorted_types) + btf->nr_sorted_types = nr_sorted_types; +} + static s32 btf_find_by_name_kind_bsearch(const struct btf *btf, const char *name, s32 start_id, s32 end_id) { @@ -5885,6 +5945,8 @@ static struct btf *btf_parse(const union bpf_attr *attr, bpfptr_t uattr, u32 uat if (err) goto errout; + btf_check_sorted(btf); + struct_meta_tab = btf_parse_struct_metas(&env->log, btf); if (IS_ERR(struct_meta_tab)) { err = PTR_ERR(struct_meta_tab); @@ -6292,6 +6354,7 @@ static struct btf *btf_parse_base(struct btf_verifier_env *env, const char *name if (err) goto errout; + btf_check_sorted(btf); refcount_set(&btf->refcnt, 1); return btf; @@ -6426,6 +6489,7 @@ static struct btf *btf_parse_module(const char *module_name, const void *data, } btf_verifier_env_free(env); + btf_check_sorted(btf); refcount_set(&btf->refcnt, 1); return btf; -- 2.34.1