11bc38b8fSAlexei Starovoitov // SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) 28a138aedSMartin KaFai Lau /* Copyright (c) 2018 Facebook */ 38a138aedSMartin KaFai Lau 496408c43SYonghong Song #include <stdio.h> 58a138aedSMartin KaFai Lau #include <stdlib.h> 68a138aedSMartin KaFai Lau #include <string.h> 78a138aedSMartin KaFai Lau #include <unistd.h> 88a138aedSMartin KaFai Lau #include <errno.h> 98a138aedSMartin KaFai Lau #include <linux/err.h> 108a138aedSMartin KaFai Lau #include <linux/btf.h> 118a138aedSMartin KaFai Lau #include "btf.h" 128a138aedSMartin KaFai Lau #include "bpf.h" 138461ef8bSYonghong Song #include "libbpf.h" 148461ef8bSYonghong Song #include "libbpf_util.h" 158a138aedSMartin KaFai Lau 168a138aedSMartin KaFai Lau #define max(a, b) ((a) > (b) ? (a) : (b)) 178a138aedSMartin KaFai Lau #define min(a, b) ((a) < (b) ? (a) : (b)) 188a138aedSMartin KaFai Lau 195aab392cSAndrii Nakryiko #define BTF_MAX_NR_TYPES 0x7fffffff 205aab392cSAndrii Nakryiko #define BTF_MAX_STR_OFFSET 0x7fffffff 218a138aedSMartin KaFai Lau 2292b57121SOkash Khawaja #define IS_MODIFIER(k) (((k) == BTF_KIND_TYPEDEF) || \ 2392b57121SOkash Khawaja ((k) == BTF_KIND_VOLATILE) || \ 2492b57121SOkash Khawaja ((k) == BTF_KIND_CONST) || \ 2592b57121SOkash Khawaja ((k) == BTF_KIND_RESTRICT)) 2692b57121SOkash Khawaja 271713d68bSDaniel Borkmann #define IS_VAR(k) ((k) == BTF_KIND_VAR) 281713d68bSDaniel Borkmann 298a138aedSMartin KaFai Lau static struct btf_type btf_void; 308a138aedSMartin KaFai Lau 318a138aedSMartin KaFai Lau struct btf { 328a138aedSMartin KaFai Lau union { 338a138aedSMartin KaFai Lau struct btf_header *hdr; 348a138aedSMartin KaFai Lau void *data; 358a138aedSMartin KaFai Lau }; 368a138aedSMartin KaFai Lau struct btf_type **types; 378a138aedSMartin KaFai Lau const char *strings; 388a138aedSMartin KaFai Lau void *nohdr_data; 395b891af7SMartin KaFai Lau __u32 nr_types; 405b891af7SMartin KaFai Lau __u32 types_size; 415b891af7SMartin KaFai Lau __u32 data_size; 428a138aedSMartin KaFai Lau int fd; 438a138aedSMartin KaFai Lau }; 448a138aedSMartin KaFai Lau 453d650141SMartin KaFai Lau struct btf_ext_info { 463d650141SMartin KaFai Lau /* 47ae4ab4b4SAndrii Nakryiko * info points to the individual info section (e.g. func_info and 48ae4ab4b4SAndrii Nakryiko * line_info) from the .BTF.ext. It does not include the __u32 rec_size. 493d650141SMartin KaFai Lau */ 503d650141SMartin KaFai Lau void *info; 513d650141SMartin KaFai Lau __u32 rec_size; 523d650141SMartin KaFai Lau __u32 len; 532993e051SYonghong Song }; 542993e051SYonghong Song 553d650141SMartin KaFai Lau struct btf_ext { 56ae4ab4b4SAndrii Nakryiko union { 57ae4ab4b4SAndrii Nakryiko struct btf_ext_header *hdr; 58ae4ab4b4SAndrii Nakryiko void *data; 59ae4ab4b4SAndrii Nakryiko }; 603d650141SMartin KaFai Lau struct btf_ext_info func_info; 613d650141SMartin KaFai Lau struct btf_ext_info line_info; 62ae4ab4b4SAndrii Nakryiko __u32 data_size; 633d650141SMartin KaFai Lau }; 643d650141SMartin KaFai Lau 653d650141SMartin KaFai Lau struct btf_ext_info_sec { 66f0187f0bSMartin KaFai Lau __u32 sec_name_off; 673d650141SMartin KaFai Lau __u32 num_info; 683d650141SMartin KaFai Lau /* Followed by num_info * record_size number of bytes */ 69f0187f0bSMartin KaFai Lau __u8 data[0]; 70f0187f0bSMartin KaFai Lau }; 71f0187f0bSMartin KaFai Lau 722993e051SYonghong Song /* The minimum bpf_func_info checked by the loader */ 732993e051SYonghong Song struct bpf_func_info_min { 7484ecc1f9SMartin KaFai Lau __u32 insn_off; 752993e051SYonghong Song __u32 type_id; 762993e051SYonghong Song }; 772993e051SYonghong Song 783d650141SMartin KaFai Lau /* The minimum bpf_line_info checked by the loader */ 793d650141SMartin KaFai Lau struct bpf_line_info_min { 803d650141SMartin KaFai Lau __u32 insn_off; 813d650141SMartin KaFai Lau __u32 file_name_off; 823d650141SMartin KaFai Lau __u32 line_off; 833d650141SMartin KaFai Lau __u32 line_col; 843d650141SMartin KaFai Lau }; 853d650141SMartin KaFai Lau 86d7f5b5e0SYonghong Song static inline __u64 ptr_to_u64(const void *ptr) 87d7f5b5e0SYonghong Song { 88d7f5b5e0SYonghong Song return (__u64) (unsigned long) ptr; 89d7f5b5e0SYonghong Song } 90d7f5b5e0SYonghong Song 918a138aedSMartin KaFai Lau static int btf_add_type(struct btf *btf, struct btf_type *t) 928a138aedSMartin KaFai Lau { 938a138aedSMartin KaFai Lau if (btf->types_size - btf->nr_types < 2) { 948a138aedSMartin KaFai Lau struct btf_type **new_types; 955b891af7SMartin KaFai Lau __u32 expand_by, new_size; 968a138aedSMartin KaFai Lau 978a138aedSMartin KaFai Lau if (btf->types_size == BTF_MAX_NR_TYPES) 988a138aedSMartin KaFai Lau return -E2BIG; 998a138aedSMartin KaFai Lau 1008a138aedSMartin KaFai Lau expand_by = max(btf->types_size >> 2, 16); 1018a138aedSMartin KaFai Lau new_size = min(BTF_MAX_NR_TYPES, btf->types_size + expand_by); 1028a138aedSMartin KaFai Lau 1038a138aedSMartin KaFai Lau new_types = realloc(btf->types, sizeof(*new_types) * new_size); 1048a138aedSMartin KaFai Lau if (!new_types) 1058a138aedSMartin KaFai Lau return -ENOMEM; 1068a138aedSMartin KaFai Lau 1078a138aedSMartin KaFai Lau if (btf->nr_types == 0) 1088a138aedSMartin KaFai Lau new_types[0] = &btf_void; 1098a138aedSMartin KaFai Lau 1108a138aedSMartin KaFai Lau btf->types = new_types; 1118a138aedSMartin KaFai Lau btf->types_size = new_size; 1128a138aedSMartin KaFai Lau } 1138a138aedSMartin KaFai Lau 1148a138aedSMartin KaFai Lau btf->types[++(btf->nr_types)] = t; 1158a138aedSMartin KaFai Lau 1168a138aedSMartin KaFai Lau return 0; 1178a138aedSMartin KaFai Lau } 1188a138aedSMartin KaFai Lau 1198461ef8bSYonghong Song static int btf_parse_hdr(struct btf *btf) 1208a138aedSMartin KaFai Lau { 1218a138aedSMartin KaFai Lau const struct btf_header *hdr = btf->hdr; 1225b891af7SMartin KaFai Lau __u32 meta_left; 1238a138aedSMartin KaFai Lau 1248a138aedSMartin KaFai Lau if (btf->data_size < sizeof(struct btf_header)) { 1258461ef8bSYonghong Song pr_debug("BTF header not found\n"); 1268a138aedSMartin KaFai Lau return -EINVAL; 1278a138aedSMartin KaFai Lau } 1288a138aedSMartin KaFai Lau 1298a138aedSMartin KaFai Lau if (hdr->magic != BTF_MAGIC) { 1308461ef8bSYonghong Song pr_debug("Invalid BTF magic:%x\n", hdr->magic); 1318a138aedSMartin KaFai Lau return -EINVAL; 1328a138aedSMartin KaFai Lau } 1338a138aedSMartin KaFai Lau 1348a138aedSMartin KaFai Lau if (hdr->version != BTF_VERSION) { 1358461ef8bSYonghong Song pr_debug("Unsupported BTF version:%u\n", hdr->version); 1368a138aedSMartin KaFai Lau return -ENOTSUP; 1378a138aedSMartin KaFai Lau } 1388a138aedSMartin KaFai Lau 1398a138aedSMartin KaFai Lau if (hdr->flags) { 1408461ef8bSYonghong Song pr_debug("Unsupported BTF flags:%x\n", hdr->flags); 1418a138aedSMartin KaFai Lau return -ENOTSUP; 1428a138aedSMartin KaFai Lau } 1438a138aedSMartin KaFai Lau 1448a138aedSMartin KaFai Lau meta_left = btf->data_size - sizeof(*hdr); 1458a138aedSMartin KaFai Lau if (!meta_left) { 1468461ef8bSYonghong Song pr_debug("BTF has no data\n"); 1478a138aedSMartin KaFai Lau return -EINVAL; 1488a138aedSMartin KaFai Lau } 1498a138aedSMartin KaFai Lau 1508a138aedSMartin KaFai Lau if (meta_left < hdr->type_off) { 1518461ef8bSYonghong Song pr_debug("Invalid BTF type section offset:%u\n", hdr->type_off); 1528a138aedSMartin KaFai Lau return -EINVAL; 1538a138aedSMartin KaFai Lau } 1548a138aedSMartin KaFai Lau 1558a138aedSMartin KaFai Lau if (meta_left < hdr->str_off) { 1568461ef8bSYonghong Song pr_debug("Invalid BTF string section offset:%u\n", hdr->str_off); 1578a138aedSMartin KaFai Lau return -EINVAL; 1588a138aedSMartin KaFai Lau } 1598a138aedSMartin KaFai Lau 1608a138aedSMartin KaFai Lau if (hdr->type_off >= hdr->str_off) { 1618461ef8bSYonghong Song pr_debug("BTF type section offset >= string section offset. No type?\n"); 1628a138aedSMartin KaFai Lau return -EINVAL; 1638a138aedSMartin KaFai Lau } 1648a138aedSMartin KaFai Lau 1658a138aedSMartin KaFai Lau if (hdr->type_off & 0x02) { 1668461ef8bSYonghong Song pr_debug("BTF type section is not aligned to 4 bytes\n"); 1678a138aedSMartin KaFai Lau return -EINVAL; 1688a138aedSMartin KaFai Lau } 1698a138aedSMartin KaFai Lau 1708a138aedSMartin KaFai Lau btf->nohdr_data = btf->hdr + 1; 1718a138aedSMartin KaFai Lau 1728a138aedSMartin KaFai Lau return 0; 1738a138aedSMartin KaFai Lau } 1748a138aedSMartin KaFai Lau 1758461ef8bSYonghong Song static int btf_parse_str_sec(struct btf *btf) 1768a138aedSMartin KaFai Lau { 1778a138aedSMartin KaFai Lau const struct btf_header *hdr = btf->hdr; 1788a138aedSMartin KaFai Lau const char *start = btf->nohdr_data + hdr->str_off; 1798a138aedSMartin KaFai Lau const char *end = start + btf->hdr->str_len; 1808a138aedSMartin KaFai Lau 1815aab392cSAndrii Nakryiko if (!hdr->str_len || hdr->str_len - 1 > BTF_MAX_STR_OFFSET || 1828a138aedSMartin KaFai Lau start[0] || end[-1]) { 1838461ef8bSYonghong Song pr_debug("Invalid BTF string section\n"); 1848a138aedSMartin KaFai Lau return -EINVAL; 1858a138aedSMartin KaFai Lau } 1868a138aedSMartin KaFai Lau 1878a138aedSMartin KaFai Lau btf->strings = start; 1888a138aedSMartin KaFai Lau 1898a138aedSMartin KaFai Lau return 0; 1908a138aedSMartin KaFai Lau } 1918a138aedSMartin KaFai Lau 19269eaab04SAndrii Nakryiko static int btf_type_size(struct btf_type *t) 19369eaab04SAndrii Nakryiko { 19469eaab04SAndrii Nakryiko int base_size = sizeof(struct btf_type); 19569eaab04SAndrii Nakryiko __u16 vlen = BTF_INFO_VLEN(t->info); 19669eaab04SAndrii Nakryiko 19769eaab04SAndrii Nakryiko switch (BTF_INFO_KIND(t->info)) { 19869eaab04SAndrii Nakryiko case BTF_KIND_FWD: 19969eaab04SAndrii Nakryiko case BTF_KIND_CONST: 20069eaab04SAndrii Nakryiko case BTF_KIND_VOLATILE: 20169eaab04SAndrii Nakryiko case BTF_KIND_RESTRICT: 20269eaab04SAndrii Nakryiko case BTF_KIND_PTR: 20369eaab04SAndrii Nakryiko case BTF_KIND_TYPEDEF: 20469eaab04SAndrii Nakryiko case BTF_KIND_FUNC: 20569eaab04SAndrii Nakryiko return base_size; 20669eaab04SAndrii Nakryiko case BTF_KIND_INT: 20769eaab04SAndrii Nakryiko return base_size + sizeof(__u32); 20869eaab04SAndrii Nakryiko case BTF_KIND_ENUM: 20969eaab04SAndrii Nakryiko return base_size + vlen * sizeof(struct btf_enum); 21069eaab04SAndrii Nakryiko case BTF_KIND_ARRAY: 21169eaab04SAndrii Nakryiko return base_size + sizeof(struct btf_array); 21269eaab04SAndrii Nakryiko case BTF_KIND_STRUCT: 21369eaab04SAndrii Nakryiko case BTF_KIND_UNION: 21469eaab04SAndrii Nakryiko return base_size + vlen * sizeof(struct btf_member); 21569eaab04SAndrii Nakryiko case BTF_KIND_FUNC_PROTO: 21669eaab04SAndrii Nakryiko return base_size + vlen * sizeof(struct btf_param); 2171713d68bSDaniel Borkmann case BTF_KIND_VAR: 2181713d68bSDaniel Borkmann return base_size + sizeof(struct btf_var); 2191713d68bSDaniel Borkmann case BTF_KIND_DATASEC: 2201713d68bSDaniel Borkmann return base_size + vlen * sizeof(struct btf_var_secinfo); 22169eaab04SAndrii Nakryiko default: 22269eaab04SAndrii Nakryiko pr_debug("Unsupported BTF_KIND:%u\n", BTF_INFO_KIND(t->info)); 22369eaab04SAndrii Nakryiko return -EINVAL; 22469eaab04SAndrii Nakryiko } 22569eaab04SAndrii Nakryiko } 22669eaab04SAndrii Nakryiko 2278461ef8bSYonghong Song static int btf_parse_type_sec(struct btf *btf) 2288a138aedSMartin KaFai Lau { 2298a138aedSMartin KaFai Lau struct btf_header *hdr = btf->hdr; 2308a138aedSMartin KaFai Lau void *nohdr_data = btf->nohdr_data; 2318a138aedSMartin KaFai Lau void *next_type = nohdr_data + hdr->type_off; 2328a138aedSMartin KaFai Lau void *end_type = nohdr_data + hdr->str_off; 2338a138aedSMartin KaFai Lau 2348a138aedSMartin KaFai Lau while (next_type < end_type) { 2358a138aedSMartin KaFai Lau struct btf_type *t = next_type; 23669eaab04SAndrii Nakryiko int type_size; 2378a138aedSMartin KaFai Lau int err; 2388a138aedSMartin KaFai Lau 23969eaab04SAndrii Nakryiko type_size = btf_type_size(t); 24069eaab04SAndrii Nakryiko if (type_size < 0) 24169eaab04SAndrii Nakryiko return type_size; 24269eaab04SAndrii Nakryiko next_type += type_size; 2438a138aedSMartin KaFai Lau err = btf_add_type(btf, t); 2448a138aedSMartin KaFai Lau if (err) 2458a138aedSMartin KaFai Lau return err; 2468a138aedSMartin KaFai Lau } 2478a138aedSMartin KaFai Lau 2488a138aedSMartin KaFai Lau return 0; 2498a138aedSMartin KaFai Lau } 2508a138aedSMartin KaFai Lau 2519c651127SAndrii Nakryiko __u32 btf__get_nr_types(const struct btf *btf) 2529c651127SAndrii Nakryiko { 2539c651127SAndrii Nakryiko return btf->nr_types; 2549c651127SAndrii Nakryiko } 2559c651127SAndrii Nakryiko 25638d5d3b3SMartin KaFai Lau const struct btf_type *btf__type_by_id(const struct btf *btf, __u32 type_id) 2578a138aedSMartin KaFai Lau { 2588a138aedSMartin KaFai Lau if (type_id > btf->nr_types) 2598a138aedSMartin KaFai Lau return NULL; 2608a138aedSMartin KaFai Lau 2618a138aedSMartin KaFai Lau return btf->types[type_id]; 2628a138aedSMartin KaFai Lau } 2638a138aedSMartin KaFai Lau 2648a138aedSMartin KaFai Lau static bool btf_type_is_void(const struct btf_type *t) 2658a138aedSMartin KaFai Lau { 2668a138aedSMartin KaFai Lau return t == &btf_void || BTF_INFO_KIND(t->info) == BTF_KIND_FWD; 2678a138aedSMartin KaFai Lau } 2688a138aedSMartin KaFai Lau 2698a138aedSMartin KaFai Lau static bool btf_type_is_void_or_null(const struct btf_type *t) 2708a138aedSMartin KaFai Lau { 2718a138aedSMartin KaFai Lau return !t || btf_type_is_void(t); 2728a138aedSMartin KaFai Lau } 2738a138aedSMartin KaFai Lau 2748a138aedSMartin KaFai Lau #define MAX_RESOLVE_DEPTH 32 2758a138aedSMartin KaFai Lau 2765b891af7SMartin KaFai Lau __s64 btf__resolve_size(const struct btf *btf, __u32 type_id) 2778a138aedSMartin KaFai Lau { 2788a138aedSMartin KaFai Lau const struct btf_array *array; 2798a138aedSMartin KaFai Lau const struct btf_type *t; 2805b891af7SMartin KaFai Lau __u32 nelems = 1; 2815b891af7SMartin KaFai Lau __s64 size = -1; 2828a138aedSMartin KaFai Lau int i; 2838a138aedSMartin KaFai Lau 28492b57121SOkash Khawaja t = btf__type_by_id(btf, type_id); 2858a138aedSMartin KaFai Lau for (i = 0; i < MAX_RESOLVE_DEPTH && !btf_type_is_void_or_null(t); 2868a138aedSMartin KaFai Lau i++) { 2878a138aedSMartin KaFai Lau switch (BTF_INFO_KIND(t->info)) { 28869eaab04SAndrii Nakryiko case BTF_KIND_INT: 28969eaab04SAndrii Nakryiko case BTF_KIND_STRUCT: 29069eaab04SAndrii Nakryiko case BTF_KIND_UNION: 29169eaab04SAndrii Nakryiko case BTF_KIND_ENUM: 2921713d68bSDaniel Borkmann case BTF_KIND_DATASEC: 29369eaab04SAndrii Nakryiko size = t->size; 29469eaab04SAndrii Nakryiko goto done; 29569eaab04SAndrii Nakryiko case BTF_KIND_PTR: 29669eaab04SAndrii Nakryiko size = sizeof(void *); 29769eaab04SAndrii Nakryiko goto done; 2988a138aedSMartin KaFai Lau case BTF_KIND_TYPEDEF: 2998a138aedSMartin KaFai Lau case BTF_KIND_VOLATILE: 3008a138aedSMartin KaFai Lau case BTF_KIND_CONST: 3018a138aedSMartin KaFai Lau case BTF_KIND_RESTRICT: 3021713d68bSDaniel Borkmann case BTF_KIND_VAR: 3038a138aedSMartin KaFai Lau type_id = t->type; 3048a138aedSMartin KaFai Lau break; 3058a138aedSMartin KaFai Lau case BTF_KIND_ARRAY: 3068a138aedSMartin KaFai Lau array = (const struct btf_array *)(t + 1); 3078a138aedSMartin KaFai Lau if (nelems && array->nelems > UINT32_MAX / nelems) 3088a138aedSMartin KaFai Lau return -E2BIG; 3098a138aedSMartin KaFai Lau nelems *= array->nelems; 3108a138aedSMartin KaFai Lau type_id = array->type; 3118a138aedSMartin KaFai Lau break; 3128a138aedSMartin KaFai Lau default: 3138a138aedSMartin KaFai Lau return -EINVAL; 3148a138aedSMartin KaFai Lau } 3158a138aedSMartin KaFai Lau 31692b57121SOkash Khawaja t = btf__type_by_id(btf, type_id); 3178a138aedSMartin KaFai Lau } 3188a138aedSMartin KaFai Lau 3198a138aedSMartin KaFai Lau if (size < 0) 3208a138aedSMartin KaFai Lau return -EINVAL; 3218a138aedSMartin KaFai Lau 32269eaab04SAndrii Nakryiko done: 3238a138aedSMartin KaFai Lau if (nelems && size > UINT32_MAX / nelems) 3248a138aedSMartin KaFai Lau return -E2BIG; 3258a138aedSMartin KaFai Lau 3268a138aedSMartin KaFai Lau return nelems * size; 3278a138aedSMartin KaFai Lau } 3288a138aedSMartin KaFai Lau 32992b57121SOkash Khawaja int btf__resolve_type(const struct btf *btf, __u32 type_id) 33092b57121SOkash Khawaja { 33192b57121SOkash Khawaja const struct btf_type *t; 33292b57121SOkash Khawaja int depth = 0; 33392b57121SOkash Khawaja 33492b57121SOkash Khawaja t = btf__type_by_id(btf, type_id); 33592b57121SOkash Khawaja while (depth < MAX_RESOLVE_DEPTH && 33692b57121SOkash Khawaja !btf_type_is_void_or_null(t) && 3371713d68bSDaniel Borkmann (IS_MODIFIER(BTF_INFO_KIND(t->info)) || 3381713d68bSDaniel Borkmann IS_VAR(BTF_INFO_KIND(t->info)))) { 33992b57121SOkash Khawaja type_id = t->type; 34092b57121SOkash Khawaja t = btf__type_by_id(btf, type_id); 34192b57121SOkash Khawaja depth++; 34292b57121SOkash Khawaja } 34392b57121SOkash Khawaja 34492b57121SOkash Khawaja if (depth == MAX_RESOLVE_DEPTH || btf_type_is_void_or_null(t)) 34592b57121SOkash Khawaja return -EINVAL; 34692b57121SOkash Khawaja 34792b57121SOkash Khawaja return type_id; 34892b57121SOkash Khawaja } 34992b57121SOkash Khawaja 3505b891af7SMartin KaFai Lau __s32 btf__find_by_name(const struct btf *btf, const char *type_name) 3518a138aedSMartin KaFai Lau { 3525b891af7SMartin KaFai Lau __u32 i; 3538a138aedSMartin KaFai Lau 3548a138aedSMartin KaFai Lau if (!strcmp(type_name, "void")) 3558a138aedSMartin KaFai Lau return 0; 3568a138aedSMartin KaFai Lau 3578a138aedSMartin KaFai Lau for (i = 1; i <= btf->nr_types; i++) { 3588a138aedSMartin KaFai Lau const struct btf_type *t = btf->types[i]; 35992b57121SOkash Khawaja const char *name = btf__name_by_offset(btf, t->name_off); 3608a138aedSMartin KaFai Lau 3618a138aedSMartin KaFai Lau if (name && !strcmp(type_name, name)) 3628a138aedSMartin KaFai Lau return i; 3638a138aedSMartin KaFai Lau } 3648a138aedSMartin KaFai Lau 3658a138aedSMartin KaFai Lau return -ENOENT; 3668a138aedSMartin KaFai Lau } 3678a138aedSMartin KaFai Lau 3688a138aedSMartin KaFai Lau void btf__free(struct btf *btf) 3698a138aedSMartin KaFai Lau { 3708a138aedSMartin KaFai Lau if (!btf) 3718a138aedSMartin KaFai Lau return; 3728a138aedSMartin KaFai Lau 3738a138aedSMartin KaFai Lau if (btf->fd != -1) 3748a138aedSMartin KaFai Lau close(btf->fd); 3758a138aedSMartin KaFai Lau 3768a138aedSMartin KaFai Lau free(btf->data); 3778a138aedSMartin KaFai Lau free(btf->types); 3788a138aedSMartin KaFai Lau free(btf); 3798a138aedSMartin KaFai Lau } 3808a138aedSMartin KaFai Lau 3818461ef8bSYonghong Song struct btf *btf__new(__u8 *data, __u32 size) 3828a138aedSMartin KaFai Lau { 3838a138aedSMartin KaFai Lau struct btf *btf; 3848a138aedSMartin KaFai Lau int err; 3858a138aedSMartin KaFai Lau 3868a138aedSMartin KaFai Lau btf = calloc(1, sizeof(struct btf)); 3878a138aedSMartin KaFai Lau if (!btf) 3888a138aedSMartin KaFai Lau return ERR_PTR(-ENOMEM); 3898a138aedSMartin KaFai Lau 3908a138aedSMartin KaFai Lau btf->fd = -1; 3918a138aedSMartin KaFai Lau 3928a138aedSMartin KaFai Lau btf->data = malloc(size); 3938a138aedSMartin KaFai Lau if (!btf->data) { 3948a138aedSMartin KaFai Lau err = -ENOMEM; 3958a138aedSMartin KaFai Lau goto done; 3968a138aedSMartin KaFai Lau } 3978a138aedSMartin KaFai Lau 3988a138aedSMartin KaFai Lau memcpy(btf->data, data, size); 3998a138aedSMartin KaFai Lau btf->data_size = size; 4008a138aedSMartin KaFai Lau 4018461ef8bSYonghong Song err = btf_parse_hdr(btf); 4028a138aedSMartin KaFai Lau if (err) 4038a138aedSMartin KaFai Lau goto done; 4048a138aedSMartin KaFai Lau 4058461ef8bSYonghong Song err = btf_parse_str_sec(btf); 4068a138aedSMartin KaFai Lau if (err) 4078a138aedSMartin KaFai Lau goto done; 4088a138aedSMartin KaFai Lau 4098461ef8bSYonghong Song err = btf_parse_type_sec(btf); 4108a138aedSMartin KaFai Lau 4118a138aedSMartin KaFai Lau done: 4128a138aedSMartin KaFai Lau if (err) { 4138a138aedSMartin KaFai Lau btf__free(btf); 4148a138aedSMartin KaFai Lau return ERR_PTR(err); 4158a138aedSMartin KaFai Lau } 4168a138aedSMartin KaFai Lau 4178a138aedSMartin KaFai Lau return btf; 4188a138aedSMartin KaFai Lau } 4198a138aedSMartin KaFai Lau 4201713d68bSDaniel Borkmann static int compare_vsi_off(const void *_a, const void *_b) 4211713d68bSDaniel Borkmann { 4221713d68bSDaniel Borkmann const struct btf_var_secinfo *a = _a; 4231713d68bSDaniel Borkmann const struct btf_var_secinfo *b = _b; 4241713d68bSDaniel Borkmann 4251713d68bSDaniel Borkmann return a->offset - b->offset; 4261713d68bSDaniel Borkmann } 4271713d68bSDaniel Borkmann 4281713d68bSDaniel Borkmann static int btf_fixup_datasec(struct bpf_object *obj, struct btf *btf, 4291713d68bSDaniel Borkmann struct btf_type *t) 4301713d68bSDaniel Borkmann { 4311713d68bSDaniel Borkmann __u32 size = 0, off = 0, i, vars = BTF_INFO_VLEN(t->info); 4321713d68bSDaniel Borkmann const char *name = btf__name_by_offset(btf, t->name_off); 4331713d68bSDaniel Borkmann const struct btf_type *t_var; 4341713d68bSDaniel Borkmann struct btf_var_secinfo *vsi; 4351713d68bSDaniel Borkmann struct btf_var *var; 4361713d68bSDaniel Borkmann int ret; 4371713d68bSDaniel Borkmann 4381713d68bSDaniel Borkmann if (!name) { 4391713d68bSDaniel Borkmann pr_debug("No name found in string section for DATASEC kind.\n"); 4401713d68bSDaniel Borkmann return -ENOENT; 4411713d68bSDaniel Borkmann } 4421713d68bSDaniel Borkmann 4431713d68bSDaniel Borkmann ret = bpf_object__section_size(obj, name, &size); 4441713d68bSDaniel Borkmann if (ret || !size || (t->size && t->size != size)) { 4451713d68bSDaniel Borkmann pr_debug("Invalid size for section %s: %u bytes\n", name, size); 4461713d68bSDaniel Borkmann return -ENOENT; 4471713d68bSDaniel Borkmann } 4481713d68bSDaniel Borkmann 4491713d68bSDaniel Borkmann t->size = size; 4501713d68bSDaniel Borkmann 4511713d68bSDaniel Borkmann for (i = 0, vsi = (struct btf_var_secinfo *)(t + 1); 4521713d68bSDaniel Borkmann i < vars; i++, vsi++) { 4531713d68bSDaniel Borkmann t_var = btf__type_by_id(btf, vsi->type); 4541713d68bSDaniel Borkmann var = (struct btf_var *)(t_var + 1); 4551713d68bSDaniel Borkmann 4561713d68bSDaniel Borkmann if (BTF_INFO_KIND(t_var->info) != BTF_KIND_VAR) { 4571713d68bSDaniel Borkmann pr_debug("Non-VAR type seen in section %s\n", name); 4581713d68bSDaniel Borkmann return -EINVAL; 4591713d68bSDaniel Borkmann } 4601713d68bSDaniel Borkmann 4611713d68bSDaniel Borkmann if (var->linkage == BTF_VAR_STATIC) 4621713d68bSDaniel Borkmann continue; 4631713d68bSDaniel Borkmann 4641713d68bSDaniel Borkmann name = btf__name_by_offset(btf, t_var->name_off); 4651713d68bSDaniel Borkmann if (!name) { 4661713d68bSDaniel Borkmann pr_debug("No name found in string section for VAR kind\n"); 4671713d68bSDaniel Borkmann return -ENOENT; 4681713d68bSDaniel Borkmann } 4691713d68bSDaniel Borkmann 4701713d68bSDaniel Borkmann ret = bpf_object__variable_offset(obj, name, &off); 4711713d68bSDaniel Borkmann if (ret) { 4721713d68bSDaniel Borkmann pr_debug("No offset found in symbol table for VAR %s\n", name); 4731713d68bSDaniel Borkmann return -ENOENT; 4741713d68bSDaniel Borkmann } 4751713d68bSDaniel Borkmann 4761713d68bSDaniel Borkmann vsi->offset = off; 4771713d68bSDaniel Borkmann } 4781713d68bSDaniel Borkmann 4791713d68bSDaniel Borkmann qsort(t + 1, vars, sizeof(*vsi), compare_vsi_off); 4801713d68bSDaniel Borkmann return 0; 4811713d68bSDaniel Borkmann } 4821713d68bSDaniel Borkmann 4831713d68bSDaniel Borkmann int btf__finalize_data(struct bpf_object *obj, struct btf *btf) 4841713d68bSDaniel Borkmann { 4851713d68bSDaniel Borkmann int err = 0; 4861713d68bSDaniel Borkmann __u32 i; 4871713d68bSDaniel Borkmann 4881713d68bSDaniel Borkmann for (i = 1; i <= btf->nr_types; i++) { 4891713d68bSDaniel Borkmann struct btf_type *t = btf->types[i]; 4901713d68bSDaniel Borkmann 4911713d68bSDaniel Borkmann /* Loader needs to fix up some of the things compiler 4921713d68bSDaniel Borkmann * couldn't get its hands on while emitting BTF. This 4931713d68bSDaniel Borkmann * is section size and global variable offset. We use 4941713d68bSDaniel Borkmann * the info from the ELF itself for this purpose. 4951713d68bSDaniel Borkmann */ 4961713d68bSDaniel Borkmann if (BTF_INFO_KIND(t->info) == BTF_KIND_DATASEC) { 4971713d68bSDaniel Borkmann err = btf_fixup_datasec(obj, btf, t); 4981713d68bSDaniel Borkmann if (err) 4991713d68bSDaniel Borkmann break; 5001713d68bSDaniel Borkmann } 5011713d68bSDaniel Borkmann } 5021713d68bSDaniel Borkmann 5031713d68bSDaniel Borkmann return err; 5041713d68bSDaniel Borkmann } 5051713d68bSDaniel Borkmann 506d29d87f7SAndrii Nakryiko int btf__load(struct btf *btf) 507d29d87f7SAndrii Nakryiko { 508d29d87f7SAndrii Nakryiko __u32 log_buf_size = BPF_LOG_BUF_SIZE; 509d29d87f7SAndrii Nakryiko char *log_buf = NULL; 510d29d87f7SAndrii Nakryiko int err = 0; 511d29d87f7SAndrii Nakryiko 512d29d87f7SAndrii Nakryiko if (btf->fd >= 0) 513d29d87f7SAndrii Nakryiko return -EEXIST; 514d29d87f7SAndrii Nakryiko 515d29d87f7SAndrii Nakryiko log_buf = malloc(log_buf_size); 516d29d87f7SAndrii Nakryiko if (!log_buf) 517d29d87f7SAndrii Nakryiko return -ENOMEM; 518d29d87f7SAndrii Nakryiko 519d29d87f7SAndrii Nakryiko *log_buf = 0; 520d29d87f7SAndrii Nakryiko 521d29d87f7SAndrii Nakryiko btf->fd = bpf_load_btf(btf->data, btf->data_size, 522d29d87f7SAndrii Nakryiko log_buf, log_buf_size, false); 523d29d87f7SAndrii Nakryiko if (btf->fd < 0) { 524d29d87f7SAndrii Nakryiko err = -errno; 525d29d87f7SAndrii Nakryiko pr_warning("Error loading BTF: %s(%d)\n", strerror(errno), errno); 526d29d87f7SAndrii Nakryiko if (*log_buf) 527d29d87f7SAndrii Nakryiko pr_warning("%s\n", log_buf); 528d29d87f7SAndrii Nakryiko goto done; 529d29d87f7SAndrii Nakryiko } 530d29d87f7SAndrii Nakryiko 531d29d87f7SAndrii Nakryiko done: 532d29d87f7SAndrii Nakryiko free(log_buf); 533d29d87f7SAndrii Nakryiko return err; 534d29d87f7SAndrii Nakryiko } 535d29d87f7SAndrii Nakryiko 5368a138aedSMartin KaFai Lau int btf__fd(const struct btf *btf) 5378a138aedSMartin KaFai Lau { 5388a138aedSMartin KaFai Lau return btf->fd; 5398a138aedSMartin KaFai Lau } 54092b57121SOkash Khawaja 54102c87446SAndrii Nakryiko const void *btf__get_raw_data(const struct btf *btf, __u32 *size) 54202c87446SAndrii Nakryiko { 54302c87446SAndrii Nakryiko *size = btf->data_size; 54402c87446SAndrii Nakryiko return btf->data; 54502c87446SAndrii Nakryiko } 54602c87446SAndrii Nakryiko 54792b57121SOkash Khawaja const char *btf__name_by_offset(const struct btf *btf, __u32 offset) 54892b57121SOkash Khawaja { 54992b57121SOkash Khawaja if (offset < btf->hdr->str_len) 55092b57121SOkash Khawaja return &btf->strings[offset]; 55192b57121SOkash Khawaja else 55292b57121SOkash Khawaja return NULL; 55392b57121SOkash Khawaja } 5542993e051SYonghong Song 5551d2f44caSMartin KaFai Lau int btf__get_from_id(__u32 id, struct btf **btf) 556d7f5b5e0SYonghong Song { 557d7f5b5e0SYonghong Song struct bpf_btf_info btf_info = { 0 }; 558d7f5b5e0SYonghong Song __u32 len = sizeof(btf_info); 559d7f5b5e0SYonghong Song __u32 last_size; 560d7f5b5e0SYonghong Song int btf_fd; 561d7f5b5e0SYonghong Song void *ptr; 562d7f5b5e0SYonghong Song int err; 563d7f5b5e0SYonghong Song 564d7f5b5e0SYonghong Song err = 0; 565d7f5b5e0SYonghong Song *btf = NULL; 566d7f5b5e0SYonghong Song btf_fd = bpf_btf_get_fd_by_id(id); 567d7f5b5e0SYonghong Song if (btf_fd < 0) 568d7f5b5e0SYonghong Song return 0; 569d7f5b5e0SYonghong Song 570d7f5b5e0SYonghong Song /* we won't know btf_size until we call bpf_obj_get_info_by_fd(). so 571d7f5b5e0SYonghong Song * let's start with a sane default - 4KiB here - and resize it only if 572d7f5b5e0SYonghong Song * bpf_obj_get_info_by_fd() needs a bigger buffer. 573d7f5b5e0SYonghong Song */ 574d7f5b5e0SYonghong Song btf_info.btf_size = 4096; 575d7f5b5e0SYonghong Song last_size = btf_info.btf_size; 576d7f5b5e0SYonghong Song ptr = malloc(last_size); 577d7f5b5e0SYonghong Song if (!ptr) { 578d7f5b5e0SYonghong Song err = -ENOMEM; 579d7f5b5e0SYonghong Song goto exit_free; 580d7f5b5e0SYonghong Song } 581d7f5b5e0SYonghong Song 5821ad9cbb8SAndrii Nakryiko memset(ptr, 0, last_size); 583d7f5b5e0SYonghong Song btf_info.btf = ptr_to_u64(ptr); 584d7f5b5e0SYonghong Song err = bpf_obj_get_info_by_fd(btf_fd, &btf_info, &len); 585d7f5b5e0SYonghong Song 586d7f5b5e0SYonghong Song if (!err && btf_info.btf_size > last_size) { 587d7f5b5e0SYonghong Song void *temp_ptr; 588d7f5b5e0SYonghong Song 589d7f5b5e0SYonghong Song last_size = btf_info.btf_size; 590d7f5b5e0SYonghong Song temp_ptr = realloc(ptr, last_size); 591d7f5b5e0SYonghong Song if (!temp_ptr) { 592d7f5b5e0SYonghong Song err = -ENOMEM; 593d7f5b5e0SYonghong Song goto exit_free; 594d7f5b5e0SYonghong Song } 595d7f5b5e0SYonghong Song ptr = temp_ptr; 5961ad9cbb8SAndrii Nakryiko memset(ptr, 0, last_size); 597d7f5b5e0SYonghong Song btf_info.btf = ptr_to_u64(ptr); 598d7f5b5e0SYonghong Song err = bpf_obj_get_info_by_fd(btf_fd, &btf_info, &len); 599d7f5b5e0SYonghong Song } 600d7f5b5e0SYonghong Song 601d7f5b5e0SYonghong Song if (err || btf_info.btf_size > last_size) { 602d7f5b5e0SYonghong Song err = errno; 603d7f5b5e0SYonghong Song goto exit_free; 604d7f5b5e0SYonghong Song } 605d7f5b5e0SYonghong Song 6068461ef8bSYonghong Song *btf = btf__new((__u8 *)(long)btf_info.btf, btf_info.btf_size); 607d7f5b5e0SYonghong Song if (IS_ERR(*btf)) { 608d7f5b5e0SYonghong Song err = PTR_ERR(*btf); 609d7f5b5e0SYonghong Song *btf = NULL; 610d7f5b5e0SYonghong Song } 611d7f5b5e0SYonghong Song 612d7f5b5e0SYonghong Song exit_free: 613d7f5b5e0SYonghong Song close(btf_fd); 614d7f5b5e0SYonghong Song free(ptr); 615d7f5b5e0SYonghong Song 616d7f5b5e0SYonghong Song return err; 617d7f5b5e0SYonghong Song } 618d7f5b5e0SYonghong Song 619a6c109a6SYonghong Song int btf__get_map_kv_tids(const struct btf *btf, const char *map_name, 62096408c43SYonghong Song __u32 expected_key_size, __u32 expected_value_size, 62196408c43SYonghong Song __u32 *key_type_id, __u32 *value_type_id) 62296408c43SYonghong Song { 62396408c43SYonghong Song const struct btf_type *container_type; 62496408c43SYonghong Song const struct btf_member *key, *value; 62596408c43SYonghong Song const size_t max_name = 256; 62696408c43SYonghong Song char container_name[max_name]; 62796408c43SYonghong Song __s64 key_size, value_size; 62896408c43SYonghong Song __s32 container_id; 62996408c43SYonghong Song 63096408c43SYonghong Song if (snprintf(container_name, max_name, "____btf_map_%s", map_name) == 63196408c43SYonghong Song max_name) { 63296408c43SYonghong Song pr_warning("map:%s length of '____btf_map_%s' is too long\n", 63396408c43SYonghong Song map_name, map_name); 63496408c43SYonghong Song return -EINVAL; 63596408c43SYonghong Song } 63696408c43SYonghong Song 63796408c43SYonghong Song container_id = btf__find_by_name(btf, container_name); 63896408c43SYonghong Song if (container_id < 0) { 639f7748e29SYonghong Song pr_debug("map:%s container_name:%s cannot be found in BTF. Missing BPF_ANNOTATE_KV_PAIR?\n", 64096408c43SYonghong Song map_name, container_name); 64196408c43SYonghong Song return container_id; 64296408c43SYonghong Song } 64396408c43SYonghong Song 64496408c43SYonghong Song container_type = btf__type_by_id(btf, container_id); 64596408c43SYonghong Song if (!container_type) { 64696408c43SYonghong Song pr_warning("map:%s cannot find BTF type for container_id:%u\n", 64796408c43SYonghong Song map_name, container_id); 64896408c43SYonghong Song return -EINVAL; 64996408c43SYonghong Song } 65096408c43SYonghong Song 65196408c43SYonghong Song if (BTF_INFO_KIND(container_type->info) != BTF_KIND_STRUCT || 65296408c43SYonghong Song BTF_INFO_VLEN(container_type->info) < 2) { 65396408c43SYonghong Song pr_warning("map:%s container_name:%s is an invalid container struct\n", 65496408c43SYonghong Song map_name, container_name); 65596408c43SYonghong Song return -EINVAL; 65696408c43SYonghong Song } 65796408c43SYonghong Song 65896408c43SYonghong Song key = (struct btf_member *)(container_type + 1); 65996408c43SYonghong Song value = key + 1; 66096408c43SYonghong Song 66196408c43SYonghong Song key_size = btf__resolve_size(btf, key->type); 66296408c43SYonghong Song if (key_size < 0) { 66396408c43SYonghong Song pr_warning("map:%s invalid BTF key_type_size\n", map_name); 66496408c43SYonghong Song return key_size; 66596408c43SYonghong Song } 66696408c43SYonghong Song 66796408c43SYonghong Song if (expected_key_size != key_size) { 66896408c43SYonghong Song pr_warning("map:%s btf_key_type_size:%u != map_def_key_size:%u\n", 66996408c43SYonghong Song map_name, (__u32)key_size, expected_key_size); 67096408c43SYonghong Song return -EINVAL; 67196408c43SYonghong Song } 67296408c43SYonghong Song 67396408c43SYonghong Song value_size = btf__resolve_size(btf, value->type); 67496408c43SYonghong Song if (value_size < 0) { 67596408c43SYonghong Song pr_warning("map:%s invalid BTF value_type_size\n", map_name); 67696408c43SYonghong Song return value_size; 67796408c43SYonghong Song } 67896408c43SYonghong Song 67996408c43SYonghong Song if (expected_value_size != value_size) { 68096408c43SYonghong Song pr_warning("map:%s btf_value_type_size:%u != map_def_value_size:%u\n", 68196408c43SYonghong Song map_name, (__u32)value_size, expected_value_size); 68296408c43SYonghong Song return -EINVAL; 68396408c43SYonghong Song } 68496408c43SYonghong Song 68596408c43SYonghong Song *key_type_id = key->type; 68696408c43SYonghong Song *value_type_id = value->type; 68796408c43SYonghong Song 68896408c43SYonghong Song return 0; 68996408c43SYonghong Song } 69096408c43SYonghong Song 691ae4ab4b4SAndrii Nakryiko struct btf_ext_sec_setup_param { 6923d650141SMartin KaFai Lau __u32 off; 6933d650141SMartin KaFai Lau __u32 len; 6943d650141SMartin KaFai Lau __u32 min_rec_size; 6953d650141SMartin KaFai Lau struct btf_ext_info *ext_info; 6963d650141SMartin KaFai Lau const char *desc; 6973d650141SMartin KaFai Lau }; 6983d650141SMartin KaFai Lau 699ae4ab4b4SAndrii Nakryiko static int btf_ext_setup_info(struct btf_ext *btf_ext, 700ae4ab4b4SAndrii Nakryiko struct btf_ext_sec_setup_param *ext_sec) 7012993e051SYonghong Song { 7023d650141SMartin KaFai Lau const struct btf_ext_info_sec *sinfo; 7033d650141SMartin KaFai Lau struct btf_ext_info *ext_info; 704f0187f0bSMartin KaFai Lau __u32 info_left, record_size; 705f0187f0bSMartin KaFai Lau /* The start of the info sec (including the __u32 record_size). */ 706ae4ab4b4SAndrii Nakryiko void *info; 707f0187f0bSMartin KaFai Lau 7083d650141SMartin KaFai Lau if (ext_sec->off & 0x03) { 7098461ef8bSYonghong Song pr_debug(".BTF.ext %s section is not aligned to 4 bytes\n", 7103d650141SMartin KaFai Lau ext_sec->desc); 711f0187f0bSMartin KaFai Lau return -EINVAL; 712f0187f0bSMartin KaFai Lau } 713f0187f0bSMartin KaFai Lau 714ae4ab4b4SAndrii Nakryiko info = btf_ext->data + btf_ext->hdr->hdr_len + ext_sec->off; 715ae4ab4b4SAndrii Nakryiko info_left = ext_sec->len; 716ae4ab4b4SAndrii Nakryiko 717ae4ab4b4SAndrii Nakryiko if (btf_ext->data + btf_ext->data_size < info + ext_sec->len) { 7188461ef8bSYonghong Song pr_debug("%s section (off:%u len:%u) is beyond the end of the ELF section .BTF.ext\n", 7193d650141SMartin KaFai Lau ext_sec->desc, ext_sec->off, ext_sec->len); 720f0187f0bSMartin KaFai Lau return -EINVAL; 721f0187f0bSMartin KaFai Lau } 722f0187f0bSMartin KaFai Lau 7233d650141SMartin KaFai Lau /* At least a record size */ 724f0187f0bSMartin KaFai Lau if (info_left < sizeof(__u32)) { 7258461ef8bSYonghong Song pr_debug(".BTF.ext %s record size not found\n", ext_sec->desc); 7262993e051SYonghong Song return -EINVAL; 7272993e051SYonghong Song } 7282993e051SYonghong Song 729f0187f0bSMartin KaFai Lau /* The record size needs to meet the minimum standard */ 730f0187f0bSMartin KaFai Lau record_size = *(__u32 *)info; 7313d650141SMartin KaFai Lau if (record_size < ext_sec->min_rec_size || 732f0187f0bSMartin KaFai Lau record_size & 0x03) { 7338461ef8bSYonghong Song pr_debug("%s section in .BTF.ext has invalid record size %u\n", 7343d650141SMartin KaFai Lau ext_sec->desc, record_size); 7352993e051SYonghong Song return -EINVAL; 7362993e051SYonghong Song } 7372993e051SYonghong Song 738f0187f0bSMartin KaFai Lau sinfo = info + sizeof(__u32); 739f0187f0bSMartin KaFai Lau info_left -= sizeof(__u32); 7402993e051SYonghong Song 7413d650141SMartin KaFai Lau /* If no records, return failure now so .BTF.ext won't be used. */ 742f0187f0bSMartin KaFai Lau if (!info_left) { 7438461ef8bSYonghong Song pr_debug("%s section in .BTF.ext has no records", ext_sec->desc); 7442993e051SYonghong Song return -EINVAL; 7452993e051SYonghong Song } 7462993e051SYonghong Song 747f0187f0bSMartin KaFai Lau while (info_left) { 7483d650141SMartin KaFai Lau unsigned int sec_hdrlen = sizeof(struct btf_ext_info_sec); 749f0187f0bSMartin KaFai Lau __u64 total_record_size; 750f0187f0bSMartin KaFai Lau __u32 num_records; 751f0187f0bSMartin KaFai Lau 752f0187f0bSMartin KaFai Lau if (info_left < sec_hdrlen) { 7538461ef8bSYonghong Song pr_debug("%s section header is not found in .BTF.ext\n", 7543d650141SMartin KaFai Lau ext_sec->desc); 7552993e051SYonghong Song return -EINVAL; 7562993e051SYonghong Song } 7572993e051SYonghong Song 7583d650141SMartin KaFai Lau num_records = sinfo->num_info; 7592993e051SYonghong Song if (num_records == 0) { 7608461ef8bSYonghong Song pr_debug("%s section has incorrect num_records in .BTF.ext\n", 7613d650141SMartin KaFai Lau ext_sec->desc); 7622993e051SYonghong Song return -EINVAL; 7632993e051SYonghong Song } 7642993e051SYonghong Song 7652993e051SYonghong Song total_record_size = sec_hdrlen + 7662993e051SYonghong Song (__u64)num_records * record_size; 767f0187f0bSMartin KaFai Lau if (info_left < total_record_size) { 7688461ef8bSYonghong Song pr_debug("%s section has incorrect num_records in .BTF.ext\n", 7693d650141SMartin KaFai Lau ext_sec->desc); 7702993e051SYonghong Song return -EINVAL; 7712993e051SYonghong Song } 7722993e051SYonghong Song 773f0187f0bSMartin KaFai Lau info_left -= total_record_size; 7742993e051SYonghong Song sinfo = (void *)sinfo + total_record_size; 7752993e051SYonghong Song } 7762993e051SYonghong Song 7773d650141SMartin KaFai Lau ext_info = ext_sec->ext_info; 7783d650141SMartin KaFai Lau ext_info->len = ext_sec->len - sizeof(__u32); 7793d650141SMartin KaFai Lau ext_info->rec_size = record_size; 780ae4ab4b4SAndrii Nakryiko ext_info->info = info + sizeof(__u32); 781f0187f0bSMartin KaFai Lau 7822993e051SYonghong Song return 0; 7832993e051SYonghong Song } 7842993e051SYonghong Song 785ae4ab4b4SAndrii Nakryiko static int btf_ext_setup_func_info(struct btf_ext *btf_ext) 7863d650141SMartin KaFai Lau { 787ae4ab4b4SAndrii Nakryiko struct btf_ext_sec_setup_param param = { 788ae4ab4b4SAndrii Nakryiko .off = btf_ext->hdr->func_info_off, 789ae4ab4b4SAndrii Nakryiko .len = btf_ext->hdr->func_info_len, 7903d650141SMartin KaFai Lau .min_rec_size = sizeof(struct bpf_func_info_min), 7913d650141SMartin KaFai Lau .ext_info = &btf_ext->func_info, 7923d650141SMartin KaFai Lau .desc = "func_info" 7933d650141SMartin KaFai Lau }; 7943d650141SMartin KaFai Lau 795ae4ab4b4SAndrii Nakryiko return btf_ext_setup_info(btf_ext, ¶m); 7963d650141SMartin KaFai Lau } 7973d650141SMartin KaFai Lau 798ae4ab4b4SAndrii Nakryiko static int btf_ext_setup_line_info(struct btf_ext *btf_ext) 7993d650141SMartin KaFai Lau { 800ae4ab4b4SAndrii Nakryiko struct btf_ext_sec_setup_param param = { 801ae4ab4b4SAndrii Nakryiko .off = btf_ext->hdr->line_info_off, 802ae4ab4b4SAndrii Nakryiko .len = btf_ext->hdr->line_info_len, 8033d650141SMartin KaFai Lau .min_rec_size = sizeof(struct bpf_line_info_min), 8043d650141SMartin KaFai Lau .ext_info = &btf_ext->line_info, 8053d650141SMartin KaFai Lau .desc = "line_info", 8063d650141SMartin KaFai Lau }; 8073d650141SMartin KaFai Lau 808ae4ab4b4SAndrii Nakryiko return btf_ext_setup_info(btf_ext, ¶m); 8093d650141SMartin KaFai Lau } 8103d650141SMartin KaFai Lau 8118461ef8bSYonghong Song static int btf_ext_parse_hdr(__u8 *data, __u32 data_size) 8122993e051SYonghong Song { 8132993e051SYonghong Song const struct btf_ext_header *hdr = (struct btf_ext_header *)data; 8142993e051SYonghong Song 8152993e051SYonghong Song if (data_size < offsetof(struct btf_ext_header, func_info_off) || 8162993e051SYonghong Song data_size < hdr->hdr_len) { 8178461ef8bSYonghong Song pr_debug("BTF.ext header not found"); 8182993e051SYonghong Song return -EINVAL; 8192993e051SYonghong Song } 8202993e051SYonghong Song 8212993e051SYonghong Song if (hdr->magic != BTF_MAGIC) { 8228461ef8bSYonghong Song pr_debug("Invalid BTF.ext magic:%x\n", hdr->magic); 8232993e051SYonghong Song return -EINVAL; 8242993e051SYonghong Song } 8252993e051SYonghong Song 8262993e051SYonghong Song if (hdr->version != BTF_VERSION) { 8278461ef8bSYonghong Song pr_debug("Unsupported BTF.ext version:%u\n", hdr->version); 8282993e051SYonghong Song return -ENOTSUP; 8292993e051SYonghong Song } 8302993e051SYonghong Song 8312993e051SYonghong Song if (hdr->flags) { 8328461ef8bSYonghong Song pr_debug("Unsupported BTF.ext flags:%x\n", hdr->flags); 8332993e051SYonghong Song return -ENOTSUP; 8342993e051SYonghong Song } 8352993e051SYonghong Song 836f0187f0bSMartin KaFai Lau if (data_size == hdr->hdr_len) { 8378461ef8bSYonghong Song pr_debug("BTF.ext has no data\n"); 8382993e051SYonghong Song return -EINVAL; 8392993e051SYonghong Song } 8402993e051SYonghong Song 841f0187f0bSMartin KaFai Lau return 0; 8422993e051SYonghong Song } 8432993e051SYonghong Song 8442993e051SYonghong Song void btf_ext__free(struct btf_ext *btf_ext) 8452993e051SYonghong Song { 8462993e051SYonghong Song if (!btf_ext) 8472993e051SYonghong Song return; 848ae4ab4b4SAndrii Nakryiko free(btf_ext->data); 8492993e051SYonghong Song free(btf_ext); 8502993e051SYonghong Song } 8512993e051SYonghong Song 8528461ef8bSYonghong Song struct btf_ext *btf_ext__new(__u8 *data, __u32 size) 8532993e051SYonghong Song { 8542993e051SYonghong Song struct btf_ext *btf_ext; 8552993e051SYonghong Song int err; 8562993e051SYonghong Song 8578461ef8bSYonghong Song err = btf_ext_parse_hdr(data, size); 8582993e051SYonghong Song if (err) 8592993e051SYonghong Song return ERR_PTR(err); 8602993e051SYonghong Song 8612993e051SYonghong Song btf_ext = calloc(1, sizeof(struct btf_ext)); 8622993e051SYonghong Song if (!btf_ext) 8632993e051SYonghong Song return ERR_PTR(-ENOMEM); 8642993e051SYonghong Song 865ae4ab4b4SAndrii Nakryiko btf_ext->data_size = size; 866ae4ab4b4SAndrii Nakryiko btf_ext->data = malloc(size); 867ae4ab4b4SAndrii Nakryiko if (!btf_ext->data) { 868ae4ab4b4SAndrii Nakryiko err = -ENOMEM; 869ae4ab4b4SAndrii Nakryiko goto done; 8702993e051SYonghong Song } 871ae4ab4b4SAndrii Nakryiko memcpy(btf_ext->data, data, size); 8722993e051SYonghong Song 873ae4ab4b4SAndrii Nakryiko err = btf_ext_setup_func_info(btf_ext); 874ae4ab4b4SAndrii Nakryiko if (err) 875ae4ab4b4SAndrii Nakryiko goto done; 876ae4ab4b4SAndrii Nakryiko 877ae4ab4b4SAndrii Nakryiko err = btf_ext_setup_line_info(btf_ext); 878ae4ab4b4SAndrii Nakryiko if (err) 879ae4ab4b4SAndrii Nakryiko goto done; 880ae4ab4b4SAndrii Nakryiko 881ae4ab4b4SAndrii Nakryiko done: 8823d650141SMartin KaFai Lau if (err) { 8833d650141SMartin KaFai Lau btf_ext__free(btf_ext); 8843d650141SMartin KaFai Lau return ERR_PTR(err); 8853d650141SMartin KaFai Lau } 8863d650141SMartin KaFai Lau 8872993e051SYonghong Song return btf_ext; 8882993e051SYonghong Song } 8892993e051SYonghong Song 890ae4ab4b4SAndrii Nakryiko const void *btf_ext__get_raw_data(const struct btf_ext *btf_ext, __u32 *size) 891ae4ab4b4SAndrii Nakryiko { 892ae4ab4b4SAndrii Nakryiko *size = btf_ext->data_size; 893ae4ab4b4SAndrii Nakryiko return btf_ext->data; 894ae4ab4b4SAndrii Nakryiko } 895ae4ab4b4SAndrii Nakryiko 8963d650141SMartin KaFai Lau static int btf_ext_reloc_info(const struct btf *btf, 8973d650141SMartin KaFai Lau const struct btf_ext_info *ext_info, 8982993e051SYonghong Song const char *sec_name, __u32 insns_cnt, 8993d650141SMartin KaFai Lau void **info, __u32 *cnt) 9002993e051SYonghong Song { 9013d650141SMartin KaFai Lau __u32 sec_hdrlen = sizeof(struct btf_ext_info_sec); 9023d650141SMartin KaFai Lau __u32 i, record_size, existing_len, records_len; 9033d650141SMartin KaFai Lau struct btf_ext_info_sec *sinfo; 9042993e051SYonghong Song const char *info_sec_name; 9052993e051SYonghong Song __u64 remain_len; 9062993e051SYonghong Song void *data; 9072993e051SYonghong Song 9083d650141SMartin KaFai Lau record_size = ext_info->rec_size; 9093d650141SMartin KaFai Lau sinfo = ext_info->info; 9103d650141SMartin KaFai Lau remain_len = ext_info->len; 9112993e051SYonghong Song while (remain_len > 0) { 9123d650141SMartin KaFai Lau records_len = sinfo->num_info * record_size; 9132993e051SYonghong Song info_sec_name = btf__name_by_offset(btf, sinfo->sec_name_off); 9142993e051SYonghong Song if (strcmp(info_sec_name, sec_name)) { 9152993e051SYonghong Song remain_len -= sec_hdrlen + records_len; 9162993e051SYonghong Song sinfo = (void *)sinfo + sec_hdrlen + records_len; 9172993e051SYonghong Song continue; 9182993e051SYonghong Song } 9192993e051SYonghong Song 9203d650141SMartin KaFai Lau existing_len = (*cnt) * record_size; 9213d650141SMartin KaFai Lau data = realloc(*info, existing_len + records_len); 9222993e051SYonghong Song if (!data) 9232993e051SYonghong Song return -ENOMEM; 9242993e051SYonghong Song 9253d650141SMartin KaFai Lau memcpy(data + existing_len, sinfo->data, records_len); 92684ecc1f9SMartin KaFai Lau /* adjust insn_off only, the rest data will be passed 9272993e051SYonghong Song * to the kernel. 9282993e051SYonghong Song */ 9293d650141SMartin KaFai Lau for (i = 0; i < sinfo->num_info; i++) { 9303d650141SMartin KaFai Lau __u32 *insn_off; 9312993e051SYonghong Song 9323d650141SMartin KaFai Lau insn_off = data + existing_len + (i * record_size); 9333d650141SMartin KaFai Lau *insn_off = *insn_off / sizeof(struct bpf_insn) + 9342993e051SYonghong Song insns_cnt; 9352993e051SYonghong Song } 9363d650141SMartin KaFai Lau *info = data; 9373d650141SMartin KaFai Lau *cnt += sinfo->num_info; 9382993e051SYonghong Song return 0; 9392993e051SYonghong Song } 9402993e051SYonghong Song 941f0187f0bSMartin KaFai Lau return -ENOENT; 942f0187f0bSMartin KaFai Lau } 943f0187f0bSMartin KaFai Lau 944ae4ab4b4SAndrii Nakryiko int btf_ext__reloc_func_info(const struct btf *btf, 945ae4ab4b4SAndrii Nakryiko const struct btf_ext *btf_ext, 9463d650141SMartin KaFai Lau const char *sec_name, __u32 insns_cnt, 9473d650141SMartin KaFai Lau void **func_info, __u32 *cnt) 9483d650141SMartin KaFai Lau { 9493d650141SMartin KaFai Lau return btf_ext_reloc_info(btf, &btf_ext->func_info, sec_name, 9503d650141SMartin KaFai Lau insns_cnt, func_info, cnt); 9513d650141SMartin KaFai Lau } 9523d650141SMartin KaFai Lau 953ae4ab4b4SAndrii Nakryiko int btf_ext__reloc_line_info(const struct btf *btf, 954ae4ab4b4SAndrii Nakryiko const struct btf_ext *btf_ext, 9553d650141SMartin KaFai Lau const char *sec_name, __u32 insns_cnt, 9563d650141SMartin KaFai Lau void **line_info, __u32 *cnt) 9573d650141SMartin KaFai Lau { 9583d650141SMartin KaFai Lau return btf_ext_reloc_info(btf, &btf_ext->line_info, sec_name, 9593d650141SMartin KaFai Lau insns_cnt, line_info, cnt); 9603d650141SMartin KaFai Lau } 9613d650141SMartin KaFai Lau 962f0187f0bSMartin KaFai Lau __u32 btf_ext__func_info_rec_size(const struct btf_ext *btf_ext) 963f0187f0bSMartin KaFai Lau { 9643d650141SMartin KaFai Lau return btf_ext->func_info.rec_size; 9653d650141SMartin KaFai Lau } 9663d650141SMartin KaFai Lau 9673d650141SMartin KaFai Lau __u32 btf_ext__line_info_rec_size(const struct btf_ext *btf_ext) 9683d650141SMartin KaFai Lau { 9693d650141SMartin KaFai Lau return btf_ext->line_info.rec_size; 9702993e051SYonghong Song } 971d5caef5bSAndrii Nakryiko 972d5caef5bSAndrii Nakryiko struct btf_dedup; 973d5caef5bSAndrii Nakryiko 974d5caef5bSAndrii Nakryiko static struct btf_dedup *btf_dedup_new(struct btf *btf, struct btf_ext *btf_ext, 975d5caef5bSAndrii Nakryiko const struct btf_dedup_opts *opts); 976d5caef5bSAndrii Nakryiko static void btf_dedup_free(struct btf_dedup *d); 977d5caef5bSAndrii Nakryiko static int btf_dedup_strings(struct btf_dedup *d); 978d5caef5bSAndrii Nakryiko static int btf_dedup_prim_types(struct btf_dedup *d); 979d5caef5bSAndrii Nakryiko static int btf_dedup_struct_types(struct btf_dedup *d); 980d5caef5bSAndrii Nakryiko static int btf_dedup_ref_types(struct btf_dedup *d); 981d5caef5bSAndrii Nakryiko static int btf_dedup_compact_types(struct btf_dedup *d); 982d5caef5bSAndrii Nakryiko static int btf_dedup_remap_types(struct btf_dedup *d); 983d5caef5bSAndrii Nakryiko 984d5caef5bSAndrii Nakryiko /* 985d5caef5bSAndrii Nakryiko * Deduplicate BTF types and strings. 986d5caef5bSAndrii Nakryiko * 987d5caef5bSAndrii Nakryiko * BTF dedup algorithm takes as an input `struct btf` representing `.BTF` ELF 988d5caef5bSAndrii Nakryiko * section with all BTF type descriptors and string data. It overwrites that 989d5caef5bSAndrii Nakryiko * memory in-place with deduplicated types and strings without any loss of 990d5caef5bSAndrii Nakryiko * information. If optional `struct btf_ext` representing '.BTF.ext' ELF section 991d5caef5bSAndrii Nakryiko * is provided, all the strings referenced from .BTF.ext section are honored 992d5caef5bSAndrii Nakryiko * and updated to point to the right offsets after deduplication. 993d5caef5bSAndrii Nakryiko * 994d5caef5bSAndrii Nakryiko * If function returns with error, type/string data might be garbled and should 995d5caef5bSAndrii Nakryiko * be discarded. 996d5caef5bSAndrii Nakryiko * 997d5caef5bSAndrii Nakryiko * More verbose and detailed description of both problem btf_dedup is solving, 998d5caef5bSAndrii Nakryiko * as well as solution could be found at: 999d5caef5bSAndrii Nakryiko * https://facebookmicrosites.github.io/bpf/blog/2018/11/14/btf-enhancement.html 1000d5caef5bSAndrii Nakryiko * 1001d5caef5bSAndrii Nakryiko * Problem description and justification 1002d5caef5bSAndrii Nakryiko * ===================================== 1003d5caef5bSAndrii Nakryiko * 1004d5caef5bSAndrii Nakryiko * BTF type information is typically emitted either as a result of conversion 1005d5caef5bSAndrii Nakryiko * from DWARF to BTF or directly by compiler. In both cases, each compilation 1006d5caef5bSAndrii Nakryiko * unit contains information about a subset of all the types that are used 1007d5caef5bSAndrii Nakryiko * in an application. These subsets are frequently overlapping and contain a lot 1008d5caef5bSAndrii Nakryiko * of duplicated information when later concatenated together into a single 1009d5caef5bSAndrii Nakryiko * binary. This algorithm ensures that each unique type is represented by single 1010d5caef5bSAndrii Nakryiko * BTF type descriptor, greatly reducing resulting size of BTF data. 1011d5caef5bSAndrii Nakryiko * 1012d5caef5bSAndrii Nakryiko * Compilation unit isolation and subsequent duplication of data is not the only 1013d5caef5bSAndrii Nakryiko * problem. The same type hierarchy (e.g., struct and all the type that struct 1014d5caef5bSAndrii Nakryiko * references) in different compilation units can be represented in BTF to 1015d5caef5bSAndrii Nakryiko * various degrees of completeness (or, rather, incompleteness) due to 1016d5caef5bSAndrii Nakryiko * struct/union forward declarations. 1017d5caef5bSAndrii Nakryiko * 1018d5caef5bSAndrii Nakryiko * Let's take a look at an example, that we'll use to better understand the 1019d5caef5bSAndrii Nakryiko * problem (and solution). Suppose we have two compilation units, each using 1020d5caef5bSAndrii Nakryiko * same `struct S`, but each of them having incomplete type information about 1021d5caef5bSAndrii Nakryiko * struct's fields: 1022d5caef5bSAndrii Nakryiko * 1023d5caef5bSAndrii Nakryiko * // CU #1: 1024d5caef5bSAndrii Nakryiko * struct S; 1025d5caef5bSAndrii Nakryiko * struct A { 1026d5caef5bSAndrii Nakryiko * int a; 1027d5caef5bSAndrii Nakryiko * struct A* self; 1028d5caef5bSAndrii Nakryiko * struct S* parent; 1029d5caef5bSAndrii Nakryiko * }; 1030d5caef5bSAndrii Nakryiko * struct B; 1031d5caef5bSAndrii Nakryiko * struct S { 1032d5caef5bSAndrii Nakryiko * struct A* a_ptr; 1033d5caef5bSAndrii Nakryiko * struct B* b_ptr; 1034d5caef5bSAndrii Nakryiko * }; 1035d5caef5bSAndrii Nakryiko * 1036d5caef5bSAndrii Nakryiko * // CU #2: 1037d5caef5bSAndrii Nakryiko * struct S; 1038d5caef5bSAndrii Nakryiko * struct A; 1039d5caef5bSAndrii Nakryiko * struct B { 1040d5caef5bSAndrii Nakryiko * int b; 1041d5caef5bSAndrii Nakryiko * struct B* self; 1042d5caef5bSAndrii Nakryiko * struct S* parent; 1043d5caef5bSAndrii Nakryiko * }; 1044d5caef5bSAndrii Nakryiko * struct S { 1045d5caef5bSAndrii Nakryiko * struct A* a_ptr; 1046d5caef5bSAndrii Nakryiko * struct B* b_ptr; 1047d5caef5bSAndrii Nakryiko * }; 1048d5caef5bSAndrii Nakryiko * 1049d5caef5bSAndrii Nakryiko * In case of CU #1, BTF data will know only that `struct B` exist (but no 1050d5caef5bSAndrii Nakryiko * more), but will know the complete type information about `struct A`. While 1051d5caef5bSAndrii Nakryiko * for CU #2, it will know full type information about `struct B`, but will 1052d5caef5bSAndrii Nakryiko * only know about forward declaration of `struct A` (in BTF terms, it will 1053d5caef5bSAndrii Nakryiko * have `BTF_KIND_FWD` type descriptor with name `B`). 1054d5caef5bSAndrii Nakryiko * 1055d5caef5bSAndrii Nakryiko * This compilation unit isolation means that it's possible that there is no 1056d5caef5bSAndrii Nakryiko * single CU with complete type information describing structs `S`, `A`, and 1057d5caef5bSAndrii Nakryiko * `B`. Also, we might get tons of duplicated and redundant type information. 1058d5caef5bSAndrii Nakryiko * 1059d5caef5bSAndrii Nakryiko * Additional complication we need to keep in mind comes from the fact that 1060d5caef5bSAndrii Nakryiko * types, in general, can form graphs containing cycles, not just DAGs. 1061d5caef5bSAndrii Nakryiko * 1062d5caef5bSAndrii Nakryiko * While algorithm does deduplication, it also merges and resolves type 1063d5caef5bSAndrii Nakryiko * information (unless disabled throught `struct btf_opts`), whenever possible. 1064d5caef5bSAndrii Nakryiko * E.g., in the example above with two compilation units having partial type 1065d5caef5bSAndrii Nakryiko * information for structs `A` and `B`, the output of algorithm will emit 1066d5caef5bSAndrii Nakryiko * a single copy of each BTF type that describes structs `A`, `B`, and `S` 1067d5caef5bSAndrii Nakryiko * (as well as type information for `int` and pointers), as if they were defined 1068d5caef5bSAndrii Nakryiko * in a single compilation unit as: 1069d5caef5bSAndrii Nakryiko * 1070d5caef5bSAndrii Nakryiko * struct A { 1071d5caef5bSAndrii Nakryiko * int a; 1072d5caef5bSAndrii Nakryiko * struct A* self; 1073d5caef5bSAndrii Nakryiko * struct S* parent; 1074d5caef5bSAndrii Nakryiko * }; 1075d5caef5bSAndrii Nakryiko * struct B { 1076d5caef5bSAndrii Nakryiko * int b; 1077d5caef5bSAndrii Nakryiko * struct B* self; 1078d5caef5bSAndrii Nakryiko * struct S* parent; 1079d5caef5bSAndrii Nakryiko * }; 1080d5caef5bSAndrii Nakryiko * struct S { 1081d5caef5bSAndrii Nakryiko * struct A* a_ptr; 1082d5caef5bSAndrii Nakryiko * struct B* b_ptr; 1083d5caef5bSAndrii Nakryiko * }; 1084d5caef5bSAndrii Nakryiko * 1085d5caef5bSAndrii Nakryiko * Algorithm summary 1086d5caef5bSAndrii Nakryiko * ================= 1087d5caef5bSAndrii Nakryiko * 1088d5caef5bSAndrii Nakryiko * Algorithm completes its work in 6 separate passes: 1089d5caef5bSAndrii Nakryiko * 1090d5caef5bSAndrii Nakryiko * 1. Strings deduplication. 1091d5caef5bSAndrii Nakryiko * 2. Primitive types deduplication (int, enum, fwd). 1092d5caef5bSAndrii Nakryiko * 3. Struct/union types deduplication. 1093d5caef5bSAndrii Nakryiko * 4. Reference types deduplication (pointers, typedefs, arrays, funcs, func 1094d5caef5bSAndrii Nakryiko * protos, and const/volatile/restrict modifiers). 1095d5caef5bSAndrii Nakryiko * 5. Types compaction. 1096d5caef5bSAndrii Nakryiko * 6. Types remapping. 1097d5caef5bSAndrii Nakryiko * 1098d5caef5bSAndrii Nakryiko * Algorithm determines canonical type descriptor, which is a single 1099d5caef5bSAndrii Nakryiko * representative type for each truly unique type. This canonical type is the 1100d5caef5bSAndrii Nakryiko * one that will go into final deduplicated BTF type information. For 1101d5caef5bSAndrii Nakryiko * struct/unions, it is also the type that algorithm will merge additional type 1102d5caef5bSAndrii Nakryiko * information into (while resolving FWDs), as it discovers it from data in 1103d5caef5bSAndrii Nakryiko * other CUs. Each input BTF type eventually gets either mapped to itself, if 1104d5caef5bSAndrii Nakryiko * that type is canonical, or to some other type, if that type is equivalent 1105d5caef5bSAndrii Nakryiko * and was chosen as canonical representative. This mapping is stored in 1106d5caef5bSAndrii Nakryiko * `btf_dedup->map` array. This map is also used to record STRUCT/UNION that 1107d5caef5bSAndrii Nakryiko * FWD type got resolved to. 1108d5caef5bSAndrii Nakryiko * 1109d5caef5bSAndrii Nakryiko * To facilitate fast discovery of canonical types, we also maintain canonical 1110d5caef5bSAndrii Nakryiko * index (`btf_dedup->dedup_table`), which maps type descriptor's signature hash 1111d5caef5bSAndrii Nakryiko * (i.e., hashed kind, name, size, fields, etc) into a list of canonical types 1112d5caef5bSAndrii Nakryiko * that match that signature. With sufficiently good choice of type signature 1113d5caef5bSAndrii Nakryiko * hashing function, we can limit number of canonical types for each unique type 1114d5caef5bSAndrii Nakryiko * signature to a very small number, allowing to find canonical type for any 1115d5caef5bSAndrii Nakryiko * duplicated type very quickly. 1116d5caef5bSAndrii Nakryiko * 1117d5caef5bSAndrii Nakryiko * Struct/union deduplication is the most critical part and algorithm for 1118d5caef5bSAndrii Nakryiko * deduplicating structs/unions is described in greater details in comments for 1119d5caef5bSAndrii Nakryiko * `btf_dedup_is_equiv` function. 1120d5caef5bSAndrii Nakryiko */ 1121d5caef5bSAndrii Nakryiko int btf__dedup(struct btf *btf, struct btf_ext *btf_ext, 1122d5caef5bSAndrii Nakryiko const struct btf_dedup_opts *opts) 1123d5caef5bSAndrii Nakryiko { 1124d5caef5bSAndrii Nakryiko struct btf_dedup *d = btf_dedup_new(btf, btf_ext, opts); 1125d5caef5bSAndrii Nakryiko int err; 1126d5caef5bSAndrii Nakryiko 1127d5caef5bSAndrii Nakryiko if (IS_ERR(d)) { 1128d5caef5bSAndrii Nakryiko pr_debug("btf_dedup_new failed: %ld", PTR_ERR(d)); 1129d5caef5bSAndrii Nakryiko return -EINVAL; 1130d5caef5bSAndrii Nakryiko } 1131d5caef5bSAndrii Nakryiko 1132d5caef5bSAndrii Nakryiko err = btf_dedup_strings(d); 1133d5caef5bSAndrii Nakryiko if (err < 0) { 1134d5caef5bSAndrii Nakryiko pr_debug("btf_dedup_strings failed:%d\n", err); 1135d5caef5bSAndrii Nakryiko goto done; 1136d5caef5bSAndrii Nakryiko } 1137d5caef5bSAndrii Nakryiko err = btf_dedup_prim_types(d); 1138d5caef5bSAndrii Nakryiko if (err < 0) { 1139d5caef5bSAndrii Nakryiko pr_debug("btf_dedup_prim_types failed:%d\n", err); 1140d5caef5bSAndrii Nakryiko goto done; 1141d5caef5bSAndrii Nakryiko } 1142d5caef5bSAndrii Nakryiko err = btf_dedup_struct_types(d); 1143d5caef5bSAndrii Nakryiko if (err < 0) { 1144d5caef5bSAndrii Nakryiko pr_debug("btf_dedup_struct_types failed:%d\n", err); 1145d5caef5bSAndrii Nakryiko goto done; 1146d5caef5bSAndrii Nakryiko } 1147d5caef5bSAndrii Nakryiko err = btf_dedup_ref_types(d); 1148d5caef5bSAndrii Nakryiko if (err < 0) { 1149d5caef5bSAndrii Nakryiko pr_debug("btf_dedup_ref_types failed:%d\n", err); 1150d5caef5bSAndrii Nakryiko goto done; 1151d5caef5bSAndrii Nakryiko } 1152d5caef5bSAndrii Nakryiko err = btf_dedup_compact_types(d); 1153d5caef5bSAndrii Nakryiko if (err < 0) { 1154d5caef5bSAndrii Nakryiko pr_debug("btf_dedup_compact_types failed:%d\n", err); 1155d5caef5bSAndrii Nakryiko goto done; 1156d5caef5bSAndrii Nakryiko } 1157d5caef5bSAndrii Nakryiko err = btf_dedup_remap_types(d); 1158d5caef5bSAndrii Nakryiko if (err < 0) { 1159d5caef5bSAndrii Nakryiko pr_debug("btf_dedup_remap_types failed:%d\n", err); 1160d5caef5bSAndrii Nakryiko goto done; 1161d5caef5bSAndrii Nakryiko } 1162d5caef5bSAndrii Nakryiko 1163d5caef5bSAndrii Nakryiko done: 1164d5caef5bSAndrii Nakryiko btf_dedup_free(d); 1165d5caef5bSAndrii Nakryiko return err; 1166d5caef5bSAndrii Nakryiko } 1167d5caef5bSAndrii Nakryiko 116851edf5f6SAndrii Nakryiko #define BTF_DEDUP_TABLE_DEFAULT_SIZE (1 << 14) 116951edf5f6SAndrii Nakryiko #define BTF_DEDUP_TABLE_MAX_SIZE_LOG 31 1170d5caef5bSAndrii Nakryiko #define BTF_UNPROCESSED_ID ((__u32)-1) 1171d5caef5bSAndrii Nakryiko #define BTF_IN_PROGRESS_ID ((__u32)-2) 1172d5caef5bSAndrii Nakryiko 1173d5caef5bSAndrii Nakryiko struct btf_dedup_node { 1174d5caef5bSAndrii Nakryiko struct btf_dedup_node *next; 1175d5caef5bSAndrii Nakryiko __u32 type_id; 1176d5caef5bSAndrii Nakryiko }; 1177d5caef5bSAndrii Nakryiko 1178d5caef5bSAndrii Nakryiko struct btf_dedup { 1179d5caef5bSAndrii Nakryiko /* .BTF section to be deduped in-place */ 1180d5caef5bSAndrii Nakryiko struct btf *btf; 1181d5caef5bSAndrii Nakryiko /* 1182d5caef5bSAndrii Nakryiko * Optional .BTF.ext section. When provided, any strings referenced 1183d5caef5bSAndrii Nakryiko * from it will be taken into account when deduping strings 1184d5caef5bSAndrii Nakryiko */ 1185d5caef5bSAndrii Nakryiko struct btf_ext *btf_ext; 1186d5caef5bSAndrii Nakryiko /* 1187d5caef5bSAndrii Nakryiko * This is a map from any type's signature hash to a list of possible 1188d5caef5bSAndrii Nakryiko * canonical representative type candidates. Hash collisions are 1189d5caef5bSAndrii Nakryiko * ignored, so even types of various kinds can share same list of 1190d5caef5bSAndrii Nakryiko * candidates, which is fine because we rely on subsequent 1191d5caef5bSAndrii Nakryiko * btf_xxx_equal() checks to authoritatively verify type equality. 1192d5caef5bSAndrii Nakryiko */ 1193d5caef5bSAndrii Nakryiko struct btf_dedup_node **dedup_table; 1194d5caef5bSAndrii Nakryiko /* Canonical types map */ 1195d5caef5bSAndrii Nakryiko __u32 *map; 1196d5caef5bSAndrii Nakryiko /* Hypothetical mapping, used during type graph equivalence checks */ 1197d5caef5bSAndrii Nakryiko __u32 *hypot_map; 1198d5caef5bSAndrii Nakryiko __u32 *hypot_list; 1199d5caef5bSAndrii Nakryiko size_t hypot_cnt; 1200d5caef5bSAndrii Nakryiko size_t hypot_cap; 1201d5caef5bSAndrii Nakryiko /* Various option modifying behavior of algorithm */ 1202d5caef5bSAndrii Nakryiko struct btf_dedup_opts opts; 1203d5caef5bSAndrii Nakryiko }; 1204d5caef5bSAndrii Nakryiko 1205d5caef5bSAndrii Nakryiko struct btf_str_ptr { 1206d5caef5bSAndrii Nakryiko const char *str; 1207d5caef5bSAndrii Nakryiko __u32 new_off; 1208d5caef5bSAndrii Nakryiko bool used; 1209d5caef5bSAndrii Nakryiko }; 1210d5caef5bSAndrii Nakryiko 1211d5caef5bSAndrii Nakryiko struct btf_str_ptrs { 1212d5caef5bSAndrii Nakryiko struct btf_str_ptr *ptrs; 1213d5caef5bSAndrii Nakryiko const char *data; 1214d5caef5bSAndrii Nakryiko __u32 cnt; 1215d5caef5bSAndrii Nakryiko __u32 cap; 1216d5caef5bSAndrii Nakryiko }; 1217d5caef5bSAndrii Nakryiko 1218d5caef5bSAndrii Nakryiko static inline __u32 hash_combine(__u32 h, __u32 value) 1219d5caef5bSAndrii Nakryiko { 1220d5caef5bSAndrii Nakryiko /* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */ 1221d5caef5bSAndrii Nakryiko #define GOLDEN_RATIO_PRIME 0x9e370001UL 1222d5caef5bSAndrii Nakryiko return h * 37 + value * GOLDEN_RATIO_PRIME; 1223d5caef5bSAndrii Nakryiko #undef GOLDEN_RATIO_PRIME 1224d5caef5bSAndrii Nakryiko } 1225d5caef5bSAndrii Nakryiko 122651edf5f6SAndrii Nakryiko #define for_each_dedup_cand(d, hash, node) \ 122751edf5f6SAndrii Nakryiko for (node = d->dedup_table[hash & (d->opts.dedup_table_size - 1)]; \ 122851edf5f6SAndrii Nakryiko node; \ 122951edf5f6SAndrii Nakryiko node = node->next) 1230d5caef5bSAndrii Nakryiko 1231d5caef5bSAndrii Nakryiko static int btf_dedup_table_add(struct btf_dedup *d, __u32 hash, __u32 type_id) 1232d5caef5bSAndrii Nakryiko { 1233d5caef5bSAndrii Nakryiko struct btf_dedup_node *node = malloc(sizeof(struct btf_dedup_node)); 123451edf5f6SAndrii Nakryiko int bucket = hash & (d->opts.dedup_table_size - 1); 1235d5caef5bSAndrii Nakryiko 1236d5caef5bSAndrii Nakryiko if (!node) 1237d5caef5bSAndrii Nakryiko return -ENOMEM; 1238d5caef5bSAndrii Nakryiko node->type_id = type_id; 123951edf5f6SAndrii Nakryiko node->next = d->dedup_table[bucket]; 124051edf5f6SAndrii Nakryiko d->dedup_table[bucket] = node; 1241d5caef5bSAndrii Nakryiko return 0; 1242d5caef5bSAndrii Nakryiko } 1243d5caef5bSAndrii Nakryiko 1244d5caef5bSAndrii Nakryiko static int btf_dedup_hypot_map_add(struct btf_dedup *d, 1245d5caef5bSAndrii Nakryiko __u32 from_id, __u32 to_id) 1246d5caef5bSAndrii Nakryiko { 1247d5caef5bSAndrii Nakryiko if (d->hypot_cnt == d->hypot_cap) { 1248d5caef5bSAndrii Nakryiko __u32 *new_list; 1249d5caef5bSAndrii Nakryiko 1250d5caef5bSAndrii Nakryiko d->hypot_cap += max(16, d->hypot_cap / 2); 1251d5caef5bSAndrii Nakryiko new_list = realloc(d->hypot_list, sizeof(__u32) * d->hypot_cap); 1252d5caef5bSAndrii Nakryiko if (!new_list) 1253d5caef5bSAndrii Nakryiko return -ENOMEM; 1254d5caef5bSAndrii Nakryiko d->hypot_list = new_list; 1255d5caef5bSAndrii Nakryiko } 1256d5caef5bSAndrii Nakryiko d->hypot_list[d->hypot_cnt++] = from_id; 1257d5caef5bSAndrii Nakryiko d->hypot_map[from_id] = to_id; 1258d5caef5bSAndrii Nakryiko return 0; 1259d5caef5bSAndrii Nakryiko } 1260d5caef5bSAndrii Nakryiko 1261d5caef5bSAndrii Nakryiko static void btf_dedup_clear_hypot_map(struct btf_dedup *d) 1262d5caef5bSAndrii Nakryiko { 1263d5caef5bSAndrii Nakryiko int i; 1264d5caef5bSAndrii Nakryiko 1265d5caef5bSAndrii Nakryiko for (i = 0; i < d->hypot_cnt; i++) 1266d5caef5bSAndrii Nakryiko d->hypot_map[d->hypot_list[i]] = BTF_UNPROCESSED_ID; 1267d5caef5bSAndrii Nakryiko d->hypot_cnt = 0; 1268d5caef5bSAndrii Nakryiko } 1269d5caef5bSAndrii Nakryiko 1270d5caef5bSAndrii Nakryiko static void btf_dedup_table_free(struct btf_dedup *d) 1271d5caef5bSAndrii Nakryiko { 1272d5caef5bSAndrii Nakryiko struct btf_dedup_node *head, *tmp; 1273d5caef5bSAndrii Nakryiko int i; 1274d5caef5bSAndrii Nakryiko 1275d5caef5bSAndrii Nakryiko if (!d->dedup_table) 1276d5caef5bSAndrii Nakryiko return; 1277d5caef5bSAndrii Nakryiko 127851edf5f6SAndrii Nakryiko for (i = 0; i < d->opts.dedup_table_size; i++) { 1279d5caef5bSAndrii Nakryiko while (d->dedup_table[i]) { 1280d5caef5bSAndrii Nakryiko tmp = d->dedup_table[i]; 1281d5caef5bSAndrii Nakryiko d->dedup_table[i] = tmp->next; 1282d5caef5bSAndrii Nakryiko free(tmp); 1283d5caef5bSAndrii Nakryiko } 1284d5caef5bSAndrii Nakryiko 1285d5caef5bSAndrii Nakryiko head = d->dedup_table[i]; 1286d5caef5bSAndrii Nakryiko while (head) { 1287d5caef5bSAndrii Nakryiko tmp = head; 1288d5caef5bSAndrii Nakryiko head = head->next; 1289d5caef5bSAndrii Nakryiko free(tmp); 1290d5caef5bSAndrii Nakryiko } 1291d5caef5bSAndrii Nakryiko } 1292d5caef5bSAndrii Nakryiko 1293d5caef5bSAndrii Nakryiko free(d->dedup_table); 1294d5caef5bSAndrii Nakryiko d->dedup_table = NULL; 1295d5caef5bSAndrii Nakryiko } 1296d5caef5bSAndrii Nakryiko 1297d5caef5bSAndrii Nakryiko static void btf_dedup_free(struct btf_dedup *d) 1298d5caef5bSAndrii Nakryiko { 1299d5caef5bSAndrii Nakryiko btf_dedup_table_free(d); 1300d5caef5bSAndrii Nakryiko 1301d5caef5bSAndrii Nakryiko free(d->map); 1302d5caef5bSAndrii Nakryiko d->map = NULL; 1303d5caef5bSAndrii Nakryiko 1304d5caef5bSAndrii Nakryiko free(d->hypot_map); 1305d5caef5bSAndrii Nakryiko d->hypot_map = NULL; 1306d5caef5bSAndrii Nakryiko 1307d5caef5bSAndrii Nakryiko free(d->hypot_list); 1308d5caef5bSAndrii Nakryiko d->hypot_list = NULL; 1309d5caef5bSAndrii Nakryiko 1310d5caef5bSAndrii Nakryiko free(d); 1311d5caef5bSAndrii Nakryiko } 1312d5caef5bSAndrii Nakryiko 131351edf5f6SAndrii Nakryiko /* Find closest power of two >= to size, capped at 2^max_size_log */ 131451edf5f6SAndrii Nakryiko static __u32 roundup_pow2_max(__u32 size, int max_size_log) 131551edf5f6SAndrii Nakryiko { 131651edf5f6SAndrii Nakryiko int i; 131751edf5f6SAndrii Nakryiko 131851edf5f6SAndrii Nakryiko for (i = 0; i < max_size_log && (1U << i) < size; i++) 131951edf5f6SAndrii Nakryiko ; 132051edf5f6SAndrii Nakryiko return 1U << i; 132151edf5f6SAndrii Nakryiko } 132251edf5f6SAndrii Nakryiko 132351edf5f6SAndrii Nakryiko 1324d5caef5bSAndrii Nakryiko static struct btf_dedup *btf_dedup_new(struct btf *btf, struct btf_ext *btf_ext, 1325d5caef5bSAndrii Nakryiko const struct btf_dedup_opts *opts) 1326d5caef5bSAndrii Nakryiko { 1327d5caef5bSAndrii Nakryiko struct btf_dedup *d = calloc(1, sizeof(struct btf_dedup)); 1328d5caef5bSAndrii Nakryiko int i, err = 0; 132951edf5f6SAndrii Nakryiko __u32 sz; 1330d5caef5bSAndrii Nakryiko 1331d5caef5bSAndrii Nakryiko if (!d) 1332d5caef5bSAndrii Nakryiko return ERR_PTR(-ENOMEM); 1333d5caef5bSAndrii Nakryiko 133451edf5f6SAndrii Nakryiko d->opts.dont_resolve_fwds = opts && opts->dont_resolve_fwds; 133551edf5f6SAndrii Nakryiko sz = opts && opts->dedup_table_size ? opts->dedup_table_size 133651edf5f6SAndrii Nakryiko : BTF_DEDUP_TABLE_DEFAULT_SIZE; 133751edf5f6SAndrii Nakryiko sz = roundup_pow2_max(sz, BTF_DEDUP_TABLE_MAX_SIZE_LOG); 133851edf5f6SAndrii Nakryiko d->opts.dedup_table_size = sz; 133951edf5f6SAndrii Nakryiko 1340d5caef5bSAndrii Nakryiko d->btf = btf; 1341d5caef5bSAndrii Nakryiko d->btf_ext = btf_ext; 1342d5caef5bSAndrii Nakryiko 134351edf5f6SAndrii Nakryiko d->dedup_table = calloc(d->opts.dedup_table_size, 1344d5caef5bSAndrii Nakryiko sizeof(struct btf_dedup_node *)); 1345d5caef5bSAndrii Nakryiko if (!d->dedup_table) { 1346d5caef5bSAndrii Nakryiko err = -ENOMEM; 1347d5caef5bSAndrii Nakryiko goto done; 1348d5caef5bSAndrii Nakryiko } 1349d5caef5bSAndrii Nakryiko 1350d5caef5bSAndrii Nakryiko d->map = malloc(sizeof(__u32) * (1 + btf->nr_types)); 1351d5caef5bSAndrii Nakryiko if (!d->map) { 1352d5caef5bSAndrii Nakryiko err = -ENOMEM; 1353d5caef5bSAndrii Nakryiko goto done; 1354d5caef5bSAndrii Nakryiko } 1355d5caef5bSAndrii Nakryiko /* special BTF "void" type is made canonical immediately */ 1356d5caef5bSAndrii Nakryiko d->map[0] = 0; 1357d5caef5bSAndrii Nakryiko for (i = 1; i <= btf->nr_types; i++) 1358d5caef5bSAndrii Nakryiko d->map[i] = BTF_UNPROCESSED_ID; 1359d5caef5bSAndrii Nakryiko 1360d5caef5bSAndrii Nakryiko d->hypot_map = malloc(sizeof(__u32) * (1 + btf->nr_types)); 1361d5caef5bSAndrii Nakryiko if (!d->hypot_map) { 1362d5caef5bSAndrii Nakryiko err = -ENOMEM; 1363d5caef5bSAndrii Nakryiko goto done; 1364d5caef5bSAndrii Nakryiko } 1365d5caef5bSAndrii Nakryiko for (i = 0; i <= btf->nr_types; i++) 1366d5caef5bSAndrii Nakryiko d->hypot_map[i] = BTF_UNPROCESSED_ID; 1367d5caef5bSAndrii Nakryiko 1368d5caef5bSAndrii Nakryiko done: 1369d5caef5bSAndrii Nakryiko if (err) { 1370d5caef5bSAndrii Nakryiko btf_dedup_free(d); 1371d5caef5bSAndrii Nakryiko return ERR_PTR(err); 1372d5caef5bSAndrii Nakryiko } 1373d5caef5bSAndrii Nakryiko 1374d5caef5bSAndrii Nakryiko return d; 1375d5caef5bSAndrii Nakryiko } 1376d5caef5bSAndrii Nakryiko 1377d5caef5bSAndrii Nakryiko typedef int (*str_off_fn_t)(__u32 *str_off_ptr, void *ctx); 1378d5caef5bSAndrii Nakryiko 1379d5caef5bSAndrii Nakryiko /* 1380d5caef5bSAndrii Nakryiko * Iterate over all possible places in .BTF and .BTF.ext that can reference 1381d5caef5bSAndrii Nakryiko * string and pass pointer to it to a provided callback `fn`. 1382d5caef5bSAndrii Nakryiko */ 1383d5caef5bSAndrii Nakryiko static int btf_for_each_str_off(struct btf_dedup *d, str_off_fn_t fn, void *ctx) 1384d5caef5bSAndrii Nakryiko { 1385d5caef5bSAndrii Nakryiko void *line_data_cur, *line_data_end; 1386d5caef5bSAndrii Nakryiko int i, j, r, rec_size; 1387d5caef5bSAndrii Nakryiko struct btf_type *t; 1388d5caef5bSAndrii Nakryiko 1389d5caef5bSAndrii Nakryiko for (i = 1; i <= d->btf->nr_types; i++) { 1390d5caef5bSAndrii Nakryiko t = d->btf->types[i]; 1391d5caef5bSAndrii Nakryiko r = fn(&t->name_off, ctx); 1392d5caef5bSAndrii Nakryiko if (r) 1393d5caef5bSAndrii Nakryiko return r; 1394d5caef5bSAndrii Nakryiko 1395d5caef5bSAndrii Nakryiko switch (BTF_INFO_KIND(t->info)) { 1396d5caef5bSAndrii Nakryiko case BTF_KIND_STRUCT: 1397d5caef5bSAndrii Nakryiko case BTF_KIND_UNION: { 1398d5caef5bSAndrii Nakryiko struct btf_member *m = (struct btf_member *)(t + 1); 1399d5caef5bSAndrii Nakryiko __u16 vlen = BTF_INFO_VLEN(t->info); 1400d5caef5bSAndrii Nakryiko 1401d5caef5bSAndrii Nakryiko for (j = 0; j < vlen; j++) { 1402d5caef5bSAndrii Nakryiko r = fn(&m->name_off, ctx); 1403d5caef5bSAndrii Nakryiko if (r) 1404d5caef5bSAndrii Nakryiko return r; 1405d5caef5bSAndrii Nakryiko m++; 1406d5caef5bSAndrii Nakryiko } 1407d5caef5bSAndrii Nakryiko break; 1408d5caef5bSAndrii Nakryiko } 1409d5caef5bSAndrii Nakryiko case BTF_KIND_ENUM: { 1410d5caef5bSAndrii Nakryiko struct btf_enum *m = (struct btf_enum *)(t + 1); 1411d5caef5bSAndrii Nakryiko __u16 vlen = BTF_INFO_VLEN(t->info); 1412d5caef5bSAndrii Nakryiko 1413d5caef5bSAndrii Nakryiko for (j = 0; j < vlen; j++) { 1414d5caef5bSAndrii Nakryiko r = fn(&m->name_off, ctx); 1415d5caef5bSAndrii Nakryiko if (r) 1416d5caef5bSAndrii Nakryiko return r; 1417d5caef5bSAndrii Nakryiko m++; 1418d5caef5bSAndrii Nakryiko } 1419d5caef5bSAndrii Nakryiko break; 1420d5caef5bSAndrii Nakryiko } 1421d5caef5bSAndrii Nakryiko case BTF_KIND_FUNC_PROTO: { 1422d5caef5bSAndrii Nakryiko struct btf_param *m = (struct btf_param *)(t + 1); 1423d5caef5bSAndrii Nakryiko __u16 vlen = BTF_INFO_VLEN(t->info); 1424d5caef5bSAndrii Nakryiko 1425d5caef5bSAndrii Nakryiko for (j = 0; j < vlen; j++) { 1426d5caef5bSAndrii Nakryiko r = fn(&m->name_off, ctx); 1427d5caef5bSAndrii Nakryiko if (r) 1428d5caef5bSAndrii Nakryiko return r; 1429d5caef5bSAndrii Nakryiko m++; 1430d5caef5bSAndrii Nakryiko } 1431d5caef5bSAndrii Nakryiko break; 1432d5caef5bSAndrii Nakryiko } 1433d5caef5bSAndrii Nakryiko default: 1434d5caef5bSAndrii Nakryiko break; 1435d5caef5bSAndrii Nakryiko } 1436d5caef5bSAndrii Nakryiko } 1437d5caef5bSAndrii Nakryiko 1438d5caef5bSAndrii Nakryiko if (!d->btf_ext) 1439d5caef5bSAndrii Nakryiko return 0; 1440d5caef5bSAndrii Nakryiko 1441d5caef5bSAndrii Nakryiko line_data_cur = d->btf_ext->line_info.info; 1442d5caef5bSAndrii Nakryiko line_data_end = d->btf_ext->line_info.info + d->btf_ext->line_info.len; 1443d5caef5bSAndrii Nakryiko rec_size = d->btf_ext->line_info.rec_size; 1444d5caef5bSAndrii Nakryiko 1445d5caef5bSAndrii Nakryiko while (line_data_cur < line_data_end) { 1446d5caef5bSAndrii Nakryiko struct btf_ext_info_sec *sec = line_data_cur; 1447d5caef5bSAndrii Nakryiko struct bpf_line_info_min *line_info; 1448d5caef5bSAndrii Nakryiko __u32 num_info = sec->num_info; 1449d5caef5bSAndrii Nakryiko 1450d5caef5bSAndrii Nakryiko r = fn(&sec->sec_name_off, ctx); 1451d5caef5bSAndrii Nakryiko if (r) 1452d5caef5bSAndrii Nakryiko return r; 1453d5caef5bSAndrii Nakryiko 1454d5caef5bSAndrii Nakryiko line_data_cur += sizeof(struct btf_ext_info_sec); 1455d5caef5bSAndrii Nakryiko for (i = 0; i < num_info; i++) { 1456d5caef5bSAndrii Nakryiko line_info = line_data_cur; 1457d5caef5bSAndrii Nakryiko r = fn(&line_info->file_name_off, ctx); 1458d5caef5bSAndrii Nakryiko if (r) 1459d5caef5bSAndrii Nakryiko return r; 1460d5caef5bSAndrii Nakryiko r = fn(&line_info->line_off, ctx); 1461d5caef5bSAndrii Nakryiko if (r) 1462d5caef5bSAndrii Nakryiko return r; 1463d5caef5bSAndrii Nakryiko line_data_cur += rec_size; 1464d5caef5bSAndrii Nakryiko } 1465d5caef5bSAndrii Nakryiko } 1466d5caef5bSAndrii Nakryiko 1467d5caef5bSAndrii Nakryiko return 0; 1468d5caef5bSAndrii Nakryiko } 1469d5caef5bSAndrii Nakryiko 1470d5caef5bSAndrii Nakryiko static int str_sort_by_content(const void *a1, const void *a2) 1471d5caef5bSAndrii Nakryiko { 1472d5caef5bSAndrii Nakryiko const struct btf_str_ptr *p1 = a1; 1473d5caef5bSAndrii Nakryiko const struct btf_str_ptr *p2 = a2; 1474d5caef5bSAndrii Nakryiko 1475d5caef5bSAndrii Nakryiko return strcmp(p1->str, p2->str); 1476d5caef5bSAndrii Nakryiko } 1477d5caef5bSAndrii Nakryiko 1478d5caef5bSAndrii Nakryiko static int str_sort_by_offset(const void *a1, const void *a2) 1479d5caef5bSAndrii Nakryiko { 1480d5caef5bSAndrii Nakryiko const struct btf_str_ptr *p1 = a1; 1481d5caef5bSAndrii Nakryiko const struct btf_str_ptr *p2 = a2; 1482d5caef5bSAndrii Nakryiko 1483d5caef5bSAndrii Nakryiko if (p1->str != p2->str) 1484d5caef5bSAndrii Nakryiko return p1->str < p2->str ? -1 : 1; 1485d5caef5bSAndrii Nakryiko return 0; 1486d5caef5bSAndrii Nakryiko } 1487d5caef5bSAndrii Nakryiko 1488d5caef5bSAndrii Nakryiko static int btf_dedup_str_ptr_cmp(const void *str_ptr, const void *pelem) 1489d5caef5bSAndrii Nakryiko { 1490d5caef5bSAndrii Nakryiko const struct btf_str_ptr *p = pelem; 1491d5caef5bSAndrii Nakryiko 1492d5caef5bSAndrii Nakryiko if (str_ptr != p->str) 1493d5caef5bSAndrii Nakryiko return (const char *)str_ptr < p->str ? -1 : 1; 1494d5caef5bSAndrii Nakryiko return 0; 1495d5caef5bSAndrii Nakryiko } 1496d5caef5bSAndrii Nakryiko 1497d5caef5bSAndrii Nakryiko static int btf_str_mark_as_used(__u32 *str_off_ptr, void *ctx) 1498d5caef5bSAndrii Nakryiko { 1499d5caef5bSAndrii Nakryiko struct btf_str_ptrs *strs; 1500d5caef5bSAndrii Nakryiko struct btf_str_ptr *s; 1501d5caef5bSAndrii Nakryiko 1502d5caef5bSAndrii Nakryiko if (*str_off_ptr == 0) 1503d5caef5bSAndrii Nakryiko return 0; 1504d5caef5bSAndrii Nakryiko 1505d5caef5bSAndrii Nakryiko strs = ctx; 1506d5caef5bSAndrii Nakryiko s = bsearch(strs->data + *str_off_ptr, strs->ptrs, strs->cnt, 1507d5caef5bSAndrii Nakryiko sizeof(struct btf_str_ptr), btf_dedup_str_ptr_cmp); 1508d5caef5bSAndrii Nakryiko if (!s) 1509d5caef5bSAndrii Nakryiko return -EINVAL; 1510d5caef5bSAndrii Nakryiko s->used = true; 1511d5caef5bSAndrii Nakryiko return 0; 1512d5caef5bSAndrii Nakryiko } 1513d5caef5bSAndrii Nakryiko 1514d5caef5bSAndrii Nakryiko static int btf_str_remap_offset(__u32 *str_off_ptr, void *ctx) 1515d5caef5bSAndrii Nakryiko { 1516d5caef5bSAndrii Nakryiko struct btf_str_ptrs *strs; 1517d5caef5bSAndrii Nakryiko struct btf_str_ptr *s; 1518d5caef5bSAndrii Nakryiko 1519d5caef5bSAndrii Nakryiko if (*str_off_ptr == 0) 1520d5caef5bSAndrii Nakryiko return 0; 1521d5caef5bSAndrii Nakryiko 1522d5caef5bSAndrii Nakryiko strs = ctx; 1523d5caef5bSAndrii Nakryiko s = bsearch(strs->data + *str_off_ptr, strs->ptrs, strs->cnt, 1524d5caef5bSAndrii Nakryiko sizeof(struct btf_str_ptr), btf_dedup_str_ptr_cmp); 1525d5caef5bSAndrii Nakryiko if (!s) 1526d5caef5bSAndrii Nakryiko return -EINVAL; 1527d5caef5bSAndrii Nakryiko *str_off_ptr = s->new_off; 1528d5caef5bSAndrii Nakryiko return 0; 1529d5caef5bSAndrii Nakryiko } 1530d5caef5bSAndrii Nakryiko 1531d5caef5bSAndrii Nakryiko /* 1532d5caef5bSAndrii Nakryiko * Dedup string and filter out those that are not referenced from either .BTF 1533d5caef5bSAndrii Nakryiko * or .BTF.ext (if provided) sections. 1534d5caef5bSAndrii Nakryiko * 1535d5caef5bSAndrii Nakryiko * This is done by building index of all strings in BTF's string section, 1536d5caef5bSAndrii Nakryiko * then iterating over all entities that can reference strings (e.g., type 1537d5caef5bSAndrii Nakryiko * names, struct field names, .BTF.ext line info, etc) and marking corresponding 1538d5caef5bSAndrii Nakryiko * strings as used. After that all used strings are deduped and compacted into 1539d5caef5bSAndrii Nakryiko * sequential blob of memory and new offsets are calculated. Then all the string 1540d5caef5bSAndrii Nakryiko * references are iterated again and rewritten using new offsets. 1541d5caef5bSAndrii Nakryiko */ 1542d5caef5bSAndrii Nakryiko static int btf_dedup_strings(struct btf_dedup *d) 1543d5caef5bSAndrii Nakryiko { 1544d5caef5bSAndrii Nakryiko const struct btf_header *hdr = d->btf->hdr; 1545d5caef5bSAndrii Nakryiko char *start = (char *)d->btf->nohdr_data + hdr->str_off; 1546d5caef5bSAndrii Nakryiko char *end = start + d->btf->hdr->str_len; 1547d5caef5bSAndrii Nakryiko char *p = start, *tmp_strs = NULL; 1548d5caef5bSAndrii Nakryiko struct btf_str_ptrs strs = { 1549d5caef5bSAndrii Nakryiko .cnt = 0, 1550d5caef5bSAndrii Nakryiko .cap = 0, 1551d5caef5bSAndrii Nakryiko .ptrs = NULL, 1552d5caef5bSAndrii Nakryiko .data = start, 1553d5caef5bSAndrii Nakryiko }; 1554d5caef5bSAndrii Nakryiko int i, j, err = 0, grp_idx; 1555d5caef5bSAndrii Nakryiko bool grp_used; 1556d5caef5bSAndrii Nakryiko 1557d5caef5bSAndrii Nakryiko /* build index of all strings */ 1558d5caef5bSAndrii Nakryiko while (p < end) { 1559d5caef5bSAndrii Nakryiko if (strs.cnt + 1 > strs.cap) { 1560d5caef5bSAndrii Nakryiko struct btf_str_ptr *new_ptrs; 1561d5caef5bSAndrii Nakryiko 1562d5caef5bSAndrii Nakryiko strs.cap += max(strs.cnt / 2, 16); 1563d5caef5bSAndrii Nakryiko new_ptrs = realloc(strs.ptrs, 1564d5caef5bSAndrii Nakryiko sizeof(strs.ptrs[0]) * strs.cap); 1565d5caef5bSAndrii Nakryiko if (!new_ptrs) { 1566d5caef5bSAndrii Nakryiko err = -ENOMEM; 1567d5caef5bSAndrii Nakryiko goto done; 1568d5caef5bSAndrii Nakryiko } 1569d5caef5bSAndrii Nakryiko strs.ptrs = new_ptrs; 1570d5caef5bSAndrii Nakryiko } 1571d5caef5bSAndrii Nakryiko 1572d5caef5bSAndrii Nakryiko strs.ptrs[strs.cnt].str = p; 1573d5caef5bSAndrii Nakryiko strs.ptrs[strs.cnt].used = false; 1574d5caef5bSAndrii Nakryiko 1575d5caef5bSAndrii Nakryiko p += strlen(p) + 1; 1576d5caef5bSAndrii Nakryiko strs.cnt++; 1577d5caef5bSAndrii Nakryiko } 1578d5caef5bSAndrii Nakryiko 1579d5caef5bSAndrii Nakryiko /* temporary storage for deduplicated strings */ 1580d5caef5bSAndrii Nakryiko tmp_strs = malloc(d->btf->hdr->str_len); 1581d5caef5bSAndrii Nakryiko if (!tmp_strs) { 1582d5caef5bSAndrii Nakryiko err = -ENOMEM; 1583d5caef5bSAndrii Nakryiko goto done; 1584d5caef5bSAndrii Nakryiko } 1585d5caef5bSAndrii Nakryiko 1586d5caef5bSAndrii Nakryiko /* mark all used strings */ 1587d5caef5bSAndrii Nakryiko strs.ptrs[0].used = true; 1588d5caef5bSAndrii Nakryiko err = btf_for_each_str_off(d, btf_str_mark_as_used, &strs); 1589d5caef5bSAndrii Nakryiko if (err) 1590d5caef5bSAndrii Nakryiko goto done; 1591d5caef5bSAndrii Nakryiko 1592d5caef5bSAndrii Nakryiko /* sort strings by context, so that we can identify duplicates */ 1593d5caef5bSAndrii Nakryiko qsort(strs.ptrs, strs.cnt, sizeof(strs.ptrs[0]), str_sort_by_content); 1594d5caef5bSAndrii Nakryiko 1595d5caef5bSAndrii Nakryiko /* 1596d5caef5bSAndrii Nakryiko * iterate groups of equal strings and if any instance in a group was 1597d5caef5bSAndrii Nakryiko * referenced, emit single instance and remember new offset 1598d5caef5bSAndrii Nakryiko */ 1599d5caef5bSAndrii Nakryiko p = tmp_strs; 1600d5caef5bSAndrii Nakryiko grp_idx = 0; 1601d5caef5bSAndrii Nakryiko grp_used = strs.ptrs[0].used; 1602d5caef5bSAndrii Nakryiko /* iterate past end to avoid code duplication after loop */ 1603d5caef5bSAndrii Nakryiko for (i = 1; i <= strs.cnt; i++) { 1604d5caef5bSAndrii Nakryiko /* 1605d5caef5bSAndrii Nakryiko * when i == strs.cnt, we want to skip string comparison and go 1606d5caef5bSAndrii Nakryiko * straight to handling last group of strings (otherwise we'd 1607d5caef5bSAndrii Nakryiko * need to handle last group after the loop w/ duplicated code) 1608d5caef5bSAndrii Nakryiko */ 1609d5caef5bSAndrii Nakryiko if (i < strs.cnt && 1610d5caef5bSAndrii Nakryiko !strcmp(strs.ptrs[i].str, strs.ptrs[grp_idx].str)) { 1611d5caef5bSAndrii Nakryiko grp_used = grp_used || strs.ptrs[i].used; 1612d5caef5bSAndrii Nakryiko continue; 1613d5caef5bSAndrii Nakryiko } 1614d5caef5bSAndrii Nakryiko 1615d5caef5bSAndrii Nakryiko /* 1616d5caef5bSAndrii Nakryiko * this check would have been required after the loop to handle 1617d5caef5bSAndrii Nakryiko * last group of strings, but due to <= condition in a loop 1618d5caef5bSAndrii Nakryiko * we avoid that duplication 1619d5caef5bSAndrii Nakryiko */ 1620d5caef5bSAndrii Nakryiko if (grp_used) { 1621d5caef5bSAndrii Nakryiko int new_off = p - tmp_strs; 1622d5caef5bSAndrii Nakryiko __u32 len = strlen(strs.ptrs[grp_idx].str); 1623d5caef5bSAndrii Nakryiko 1624d5caef5bSAndrii Nakryiko memmove(p, strs.ptrs[grp_idx].str, len + 1); 1625d5caef5bSAndrii Nakryiko for (j = grp_idx; j < i; j++) 1626d5caef5bSAndrii Nakryiko strs.ptrs[j].new_off = new_off; 1627d5caef5bSAndrii Nakryiko p += len + 1; 1628d5caef5bSAndrii Nakryiko } 1629d5caef5bSAndrii Nakryiko 1630d5caef5bSAndrii Nakryiko if (i < strs.cnt) { 1631d5caef5bSAndrii Nakryiko grp_idx = i; 1632d5caef5bSAndrii Nakryiko grp_used = strs.ptrs[i].used; 1633d5caef5bSAndrii Nakryiko } 1634d5caef5bSAndrii Nakryiko } 1635d5caef5bSAndrii Nakryiko 1636d5caef5bSAndrii Nakryiko /* replace original strings with deduped ones */ 1637d5caef5bSAndrii Nakryiko d->btf->hdr->str_len = p - tmp_strs; 1638d5caef5bSAndrii Nakryiko memmove(start, tmp_strs, d->btf->hdr->str_len); 1639d5caef5bSAndrii Nakryiko end = start + d->btf->hdr->str_len; 1640d5caef5bSAndrii Nakryiko 1641d5caef5bSAndrii Nakryiko /* restore original order for further binary search lookups */ 1642d5caef5bSAndrii Nakryiko qsort(strs.ptrs, strs.cnt, sizeof(strs.ptrs[0]), str_sort_by_offset); 1643d5caef5bSAndrii Nakryiko 1644d5caef5bSAndrii Nakryiko /* remap string offsets */ 1645d5caef5bSAndrii Nakryiko err = btf_for_each_str_off(d, btf_str_remap_offset, &strs); 1646d5caef5bSAndrii Nakryiko if (err) 1647d5caef5bSAndrii Nakryiko goto done; 1648d5caef5bSAndrii Nakryiko 1649d5caef5bSAndrii Nakryiko d->btf->hdr->str_len = end - start; 1650d5caef5bSAndrii Nakryiko 1651d5caef5bSAndrii Nakryiko done: 1652d5caef5bSAndrii Nakryiko free(tmp_strs); 1653d5caef5bSAndrii Nakryiko free(strs.ptrs); 1654d5caef5bSAndrii Nakryiko return err; 1655d5caef5bSAndrii Nakryiko } 1656d5caef5bSAndrii Nakryiko 1657d5caef5bSAndrii Nakryiko static __u32 btf_hash_common(struct btf_type *t) 1658d5caef5bSAndrii Nakryiko { 1659d5caef5bSAndrii Nakryiko __u32 h; 1660d5caef5bSAndrii Nakryiko 1661d5caef5bSAndrii Nakryiko h = hash_combine(0, t->name_off); 1662d5caef5bSAndrii Nakryiko h = hash_combine(h, t->info); 1663d5caef5bSAndrii Nakryiko h = hash_combine(h, t->size); 1664d5caef5bSAndrii Nakryiko return h; 1665d5caef5bSAndrii Nakryiko } 1666d5caef5bSAndrii Nakryiko 1667d5caef5bSAndrii Nakryiko static bool btf_equal_common(struct btf_type *t1, struct btf_type *t2) 1668d5caef5bSAndrii Nakryiko { 1669d5caef5bSAndrii Nakryiko return t1->name_off == t2->name_off && 1670d5caef5bSAndrii Nakryiko t1->info == t2->info && 1671d5caef5bSAndrii Nakryiko t1->size == t2->size; 1672d5caef5bSAndrii Nakryiko } 1673d5caef5bSAndrii Nakryiko 1674d5caef5bSAndrii Nakryiko /* Calculate type signature hash of INT. */ 1675d5caef5bSAndrii Nakryiko static __u32 btf_hash_int(struct btf_type *t) 1676d5caef5bSAndrii Nakryiko { 1677d5caef5bSAndrii Nakryiko __u32 info = *(__u32 *)(t + 1); 1678d5caef5bSAndrii Nakryiko __u32 h; 1679d5caef5bSAndrii Nakryiko 1680d5caef5bSAndrii Nakryiko h = btf_hash_common(t); 1681d5caef5bSAndrii Nakryiko h = hash_combine(h, info); 1682d5caef5bSAndrii Nakryiko return h; 1683d5caef5bSAndrii Nakryiko } 1684d5caef5bSAndrii Nakryiko 1685d5caef5bSAndrii Nakryiko /* Check structural equality of two INTs. */ 1686d5caef5bSAndrii Nakryiko static bool btf_equal_int(struct btf_type *t1, struct btf_type *t2) 1687d5caef5bSAndrii Nakryiko { 1688d5caef5bSAndrii Nakryiko __u32 info1, info2; 1689d5caef5bSAndrii Nakryiko 1690d5caef5bSAndrii Nakryiko if (!btf_equal_common(t1, t2)) 1691d5caef5bSAndrii Nakryiko return false; 1692d5caef5bSAndrii Nakryiko info1 = *(__u32 *)(t1 + 1); 1693d5caef5bSAndrii Nakryiko info2 = *(__u32 *)(t2 + 1); 1694d5caef5bSAndrii Nakryiko return info1 == info2; 1695d5caef5bSAndrii Nakryiko } 1696d5caef5bSAndrii Nakryiko 1697d5caef5bSAndrii Nakryiko /* Calculate type signature hash of ENUM. */ 1698d5caef5bSAndrii Nakryiko static __u32 btf_hash_enum(struct btf_type *t) 1699d5caef5bSAndrii Nakryiko { 17009768095bSAndrii Nakryiko __u32 h; 1701d5caef5bSAndrii Nakryiko 17029768095bSAndrii Nakryiko /* don't hash vlen and enum members to support enum fwd resolving */ 17039768095bSAndrii Nakryiko h = hash_combine(0, t->name_off); 17049768095bSAndrii Nakryiko h = hash_combine(h, t->info & ~0xffff); 17059768095bSAndrii Nakryiko h = hash_combine(h, t->size); 1706d5caef5bSAndrii Nakryiko return h; 1707d5caef5bSAndrii Nakryiko } 1708d5caef5bSAndrii Nakryiko 1709d5caef5bSAndrii Nakryiko /* Check structural equality of two ENUMs. */ 1710d5caef5bSAndrii Nakryiko static bool btf_equal_enum(struct btf_type *t1, struct btf_type *t2) 1711d5caef5bSAndrii Nakryiko { 1712d5caef5bSAndrii Nakryiko struct btf_enum *m1, *m2; 1713d5caef5bSAndrii Nakryiko __u16 vlen; 1714d5caef5bSAndrii Nakryiko int i; 1715d5caef5bSAndrii Nakryiko 1716d5caef5bSAndrii Nakryiko if (!btf_equal_common(t1, t2)) 1717d5caef5bSAndrii Nakryiko return false; 1718d5caef5bSAndrii Nakryiko 1719d5caef5bSAndrii Nakryiko vlen = BTF_INFO_VLEN(t1->info); 1720d5caef5bSAndrii Nakryiko m1 = (struct btf_enum *)(t1 + 1); 1721d5caef5bSAndrii Nakryiko m2 = (struct btf_enum *)(t2 + 1); 1722d5caef5bSAndrii Nakryiko for (i = 0; i < vlen; i++) { 1723d5caef5bSAndrii Nakryiko if (m1->name_off != m2->name_off || m1->val != m2->val) 1724d5caef5bSAndrii Nakryiko return false; 1725d5caef5bSAndrii Nakryiko m1++; 1726d5caef5bSAndrii Nakryiko m2++; 1727d5caef5bSAndrii Nakryiko } 1728d5caef5bSAndrii Nakryiko return true; 1729d5caef5bSAndrii Nakryiko } 1730d5caef5bSAndrii Nakryiko 17319768095bSAndrii Nakryiko static inline bool btf_is_enum_fwd(struct btf_type *t) 17329768095bSAndrii Nakryiko { 17339768095bSAndrii Nakryiko return BTF_INFO_KIND(t->info) == BTF_KIND_ENUM && 17349768095bSAndrii Nakryiko BTF_INFO_VLEN(t->info) == 0; 17359768095bSAndrii Nakryiko } 17369768095bSAndrii Nakryiko 17379768095bSAndrii Nakryiko static bool btf_compat_enum(struct btf_type *t1, struct btf_type *t2) 17389768095bSAndrii Nakryiko { 17399768095bSAndrii Nakryiko if (!btf_is_enum_fwd(t1) && !btf_is_enum_fwd(t2)) 17409768095bSAndrii Nakryiko return btf_equal_enum(t1, t2); 17419768095bSAndrii Nakryiko /* ignore vlen when comparing */ 17429768095bSAndrii Nakryiko return t1->name_off == t2->name_off && 17439768095bSAndrii Nakryiko (t1->info & ~0xffff) == (t2->info & ~0xffff) && 17449768095bSAndrii Nakryiko t1->size == t2->size; 17459768095bSAndrii Nakryiko } 17469768095bSAndrii Nakryiko 1747d5caef5bSAndrii Nakryiko /* 1748d5caef5bSAndrii Nakryiko * Calculate type signature hash of STRUCT/UNION, ignoring referenced type IDs, 1749d5caef5bSAndrii Nakryiko * as referenced type IDs equivalence is established separately during type 1750d5caef5bSAndrii Nakryiko * graph equivalence check algorithm. 1751d5caef5bSAndrii Nakryiko */ 1752d5caef5bSAndrii Nakryiko static __u32 btf_hash_struct(struct btf_type *t) 1753d5caef5bSAndrii Nakryiko { 1754d5caef5bSAndrii Nakryiko struct btf_member *member = (struct btf_member *)(t + 1); 1755d5caef5bSAndrii Nakryiko __u32 vlen = BTF_INFO_VLEN(t->info); 1756d5caef5bSAndrii Nakryiko __u32 h = btf_hash_common(t); 1757d5caef5bSAndrii Nakryiko int i; 1758d5caef5bSAndrii Nakryiko 1759d5caef5bSAndrii Nakryiko for (i = 0; i < vlen; i++) { 1760d5caef5bSAndrii Nakryiko h = hash_combine(h, member->name_off); 1761d5caef5bSAndrii Nakryiko h = hash_combine(h, member->offset); 1762d5caef5bSAndrii Nakryiko /* no hashing of referenced type ID, it can be unresolved yet */ 1763d5caef5bSAndrii Nakryiko member++; 1764d5caef5bSAndrii Nakryiko } 1765d5caef5bSAndrii Nakryiko return h; 1766d5caef5bSAndrii Nakryiko } 1767d5caef5bSAndrii Nakryiko 1768d5caef5bSAndrii Nakryiko /* 1769d5caef5bSAndrii Nakryiko * Check structural compatibility of two FUNC_PROTOs, ignoring referenced type 1770d5caef5bSAndrii Nakryiko * IDs. This check is performed during type graph equivalence check and 1771d5caef5bSAndrii Nakryiko * referenced types equivalence is checked separately. 1772d5caef5bSAndrii Nakryiko */ 177391097fbeSAndrii Nakryiko static bool btf_shallow_equal_struct(struct btf_type *t1, struct btf_type *t2) 1774d5caef5bSAndrii Nakryiko { 1775d5caef5bSAndrii Nakryiko struct btf_member *m1, *m2; 1776d5caef5bSAndrii Nakryiko __u16 vlen; 1777d5caef5bSAndrii Nakryiko int i; 1778d5caef5bSAndrii Nakryiko 1779d5caef5bSAndrii Nakryiko if (!btf_equal_common(t1, t2)) 1780d5caef5bSAndrii Nakryiko return false; 1781d5caef5bSAndrii Nakryiko 1782d5caef5bSAndrii Nakryiko vlen = BTF_INFO_VLEN(t1->info); 1783d5caef5bSAndrii Nakryiko m1 = (struct btf_member *)(t1 + 1); 1784d5caef5bSAndrii Nakryiko m2 = (struct btf_member *)(t2 + 1); 1785d5caef5bSAndrii Nakryiko for (i = 0; i < vlen; i++) { 1786d5caef5bSAndrii Nakryiko if (m1->name_off != m2->name_off || m1->offset != m2->offset) 1787d5caef5bSAndrii Nakryiko return false; 1788d5caef5bSAndrii Nakryiko m1++; 1789d5caef5bSAndrii Nakryiko m2++; 1790d5caef5bSAndrii Nakryiko } 1791d5caef5bSAndrii Nakryiko return true; 1792d5caef5bSAndrii Nakryiko } 1793d5caef5bSAndrii Nakryiko 1794d5caef5bSAndrii Nakryiko /* 1795d5caef5bSAndrii Nakryiko * Calculate type signature hash of ARRAY, including referenced type IDs, 1796d5caef5bSAndrii Nakryiko * under assumption that they were already resolved to canonical type IDs and 1797d5caef5bSAndrii Nakryiko * are not going to change. 1798d5caef5bSAndrii Nakryiko */ 1799d5caef5bSAndrii Nakryiko static __u32 btf_hash_array(struct btf_type *t) 1800d5caef5bSAndrii Nakryiko { 1801d5caef5bSAndrii Nakryiko struct btf_array *info = (struct btf_array *)(t + 1); 1802d5caef5bSAndrii Nakryiko __u32 h = btf_hash_common(t); 1803d5caef5bSAndrii Nakryiko 1804d5caef5bSAndrii Nakryiko h = hash_combine(h, info->type); 1805d5caef5bSAndrii Nakryiko h = hash_combine(h, info->index_type); 1806d5caef5bSAndrii Nakryiko h = hash_combine(h, info->nelems); 1807d5caef5bSAndrii Nakryiko return h; 1808d5caef5bSAndrii Nakryiko } 1809d5caef5bSAndrii Nakryiko 1810d5caef5bSAndrii Nakryiko /* 1811d5caef5bSAndrii Nakryiko * Check exact equality of two ARRAYs, taking into account referenced 1812d5caef5bSAndrii Nakryiko * type IDs, under assumption that they were already resolved to canonical 1813d5caef5bSAndrii Nakryiko * type IDs and are not going to change. 1814d5caef5bSAndrii Nakryiko * This function is called during reference types deduplication to compare 1815d5caef5bSAndrii Nakryiko * ARRAY to potential canonical representative. 1816d5caef5bSAndrii Nakryiko */ 1817d5caef5bSAndrii Nakryiko static bool btf_equal_array(struct btf_type *t1, struct btf_type *t2) 1818d5caef5bSAndrii Nakryiko { 1819d5caef5bSAndrii Nakryiko struct btf_array *info1, *info2; 1820d5caef5bSAndrii Nakryiko 1821d5caef5bSAndrii Nakryiko if (!btf_equal_common(t1, t2)) 1822d5caef5bSAndrii Nakryiko return false; 1823d5caef5bSAndrii Nakryiko 1824d5caef5bSAndrii Nakryiko info1 = (struct btf_array *)(t1 + 1); 1825d5caef5bSAndrii Nakryiko info2 = (struct btf_array *)(t2 + 1); 1826d5caef5bSAndrii Nakryiko return info1->type == info2->type && 1827d5caef5bSAndrii Nakryiko info1->index_type == info2->index_type && 1828d5caef5bSAndrii Nakryiko info1->nelems == info2->nelems; 1829d5caef5bSAndrii Nakryiko } 1830d5caef5bSAndrii Nakryiko 1831d5caef5bSAndrii Nakryiko /* 1832d5caef5bSAndrii Nakryiko * Check structural compatibility of two ARRAYs, ignoring referenced type 1833d5caef5bSAndrii Nakryiko * IDs. This check is performed during type graph equivalence check and 1834d5caef5bSAndrii Nakryiko * referenced types equivalence is checked separately. 1835d5caef5bSAndrii Nakryiko */ 1836d5caef5bSAndrii Nakryiko static bool btf_compat_array(struct btf_type *t1, struct btf_type *t2) 1837d5caef5bSAndrii Nakryiko { 1838d5caef5bSAndrii Nakryiko struct btf_array *info1, *info2; 1839d5caef5bSAndrii Nakryiko 1840d5caef5bSAndrii Nakryiko if (!btf_equal_common(t1, t2)) 1841d5caef5bSAndrii Nakryiko return false; 1842d5caef5bSAndrii Nakryiko 1843d5caef5bSAndrii Nakryiko info1 = (struct btf_array *)(t1 + 1); 1844d5caef5bSAndrii Nakryiko info2 = (struct btf_array *)(t2 + 1); 1845d5caef5bSAndrii Nakryiko return info1->nelems == info2->nelems; 1846d5caef5bSAndrii Nakryiko } 1847d5caef5bSAndrii Nakryiko 1848d5caef5bSAndrii Nakryiko /* 1849d5caef5bSAndrii Nakryiko * Calculate type signature hash of FUNC_PROTO, including referenced type IDs, 1850d5caef5bSAndrii Nakryiko * under assumption that they were already resolved to canonical type IDs and 1851d5caef5bSAndrii Nakryiko * are not going to change. 1852d5caef5bSAndrii Nakryiko */ 1853d5caef5bSAndrii Nakryiko static inline __u32 btf_hash_fnproto(struct btf_type *t) 1854d5caef5bSAndrii Nakryiko { 1855d5caef5bSAndrii Nakryiko struct btf_param *member = (struct btf_param *)(t + 1); 1856d5caef5bSAndrii Nakryiko __u16 vlen = BTF_INFO_VLEN(t->info); 1857d5caef5bSAndrii Nakryiko __u32 h = btf_hash_common(t); 1858d5caef5bSAndrii Nakryiko int i; 1859d5caef5bSAndrii Nakryiko 1860d5caef5bSAndrii Nakryiko for (i = 0; i < vlen; i++) { 1861d5caef5bSAndrii Nakryiko h = hash_combine(h, member->name_off); 1862d5caef5bSAndrii Nakryiko h = hash_combine(h, member->type); 1863d5caef5bSAndrii Nakryiko member++; 1864d5caef5bSAndrii Nakryiko } 1865d5caef5bSAndrii Nakryiko return h; 1866d5caef5bSAndrii Nakryiko } 1867d5caef5bSAndrii Nakryiko 1868d5caef5bSAndrii Nakryiko /* 1869d5caef5bSAndrii Nakryiko * Check exact equality of two FUNC_PROTOs, taking into account referenced 1870d5caef5bSAndrii Nakryiko * type IDs, under assumption that they were already resolved to canonical 1871d5caef5bSAndrii Nakryiko * type IDs and are not going to change. 1872d5caef5bSAndrii Nakryiko * This function is called during reference types deduplication to compare 1873d5caef5bSAndrii Nakryiko * FUNC_PROTO to potential canonical representative. 1874d5caef5bSAndrii Nakryiko */ 1875d5caef5bSAndrii Nakryiko static inline bool btf_equal_fnproto(struct btf_type *t1, struct btf_type *t2) 1876d5caef5bSAndrii Nakryiko { 1877d5caef5bSAndrii Nakryiko struct btf_param *m1, *m2; 1878d5caef5bSAndrii Nakryiko __u16 vlen; 1879d5caef5bSAndrii Nakryiko int i; 1880d5caef5bSAndrii Nakryiko 1881d5caef5bSAndrii Nakryiko if (!btf_equal_common(t1, t2)) 1882d5caef5bSAndrii Nakryiko return false; 1883d5caef5bSAndrii Nakryiko 1884d5caef5bSAndrii Nakryiko vlen = BTF_INFO_VLEN(t1->info); 1885d5caef5bSAndrii Nakryiko m1 = (struct btf_param *)(t1 + 1); 1886d5caef5bSAndrii Nakryiko m2 = (struct btf_param *)(t2 + 1); 1887d5caef5bSAndrii Nakryiko for (i = 0; i < vlen; i++) { 1888d5caef5bSAndrii Nakryiko if (m1->name_off != m2->name_off || m1->type != m2->type) 1889d5caef5bSAndrii Nakryiko return false; 1890d5caef5bSAndrii Nakryiko m1++; 1891d5caef5bSAndrii Nakryiko m2++; 1892d5caef5bSAndrii Nakryiko } 1893d5caef5bSAndrii Nakryiko return true; 1894d5caef5bSAndrii Nakryiko } 1895d5caef5bSAndrii Nakryiko 1896d5caef5bSAndrii Nakryiko /* 1897d5caef5bSAndrii Nakryiko * Check structural compatibility of two FUNC_PROTOs, ignoring referenced type 1898d5caef5bSAndrii Nakryiko * IDs. This check is performed during type graph equivalence check and 1899d5caef5bSAndrii Nakryiko * referenced types equivalence is checked separately. 1900d5caef5bSAndrii Nakryiko */ 1901d5caef5bSAndrii Nakryiko static inline bool btf_compat_fnproto(struct btf_type *t1, struct btf_type *t2) 1902d5caef5bSAndrii Nakryiko { 1903d5caef5bSAndrii Nakryiko struct btf_param *m1, *m2; 1904d5caef5bSAndrii Nakryiko __u16 vlen; 1905d5caef5bSAndrii Nakryiko int i; 1906d5caef5bSAndrii Nakryiko 1907d5caef5bSAndrii Nakryiko /* skip return type ID */ 1908d5caef5bSAndrii Nakryiko if (t1->name_off != t2->name_off || t1->info != t2->info) 1909d5caef5bSAndrii Nakryiko return false; 1910d5caef5bSAndrii Nakryiko 1911d5caef5bSAndrii Nakryiko vlen = BTF_INFO_VLEN(t1->info); 1912d5caef5bSAndrii Nakryiko m1 = (struct btf_param *)(t1 + 1); 1913d5caef5bSAndrii Nakryiko m2 = (struct btf_param *)(t2 + 1); 1914d5caef5bSAndrii Nakryiko for (i = 0; i < vlen; i++) { 1915d5caef5bSAndrii Nakryiko if (m1->name_off != m2->name_off) 1916d5caef5bSAndrii Nakryiko return false; 1917d5caef5bSAndrii Nakryiko m1++; 1918d5caef5bSAndrii Nakryiko m2++; 1919d5caef5bSAndrii Nakryiko } 1920d5caef5bSAndrii Nakryiko return true; 1921d5caef5bSAndrii Nakryiko } 1922d5caef5bSAndrii Nakryiko 1923d5caef5bSAndrii Nakryiko /* 1924d5caef5bSAndrii Nakryiko * Deduplicate primitive types, that can't reference other types, by calculating 1925d5caef5bSAndrii Nakryiko * their type signature hash and comparing them with any possible canonical 1926d5caef5bSAndrii Nakryiko * candidate. If no canonical candidate matches, type itself is marked as 1927d5caef5bSAndrii Nakryiko * canonical and is added into `btf_dedup->dedup_table` as another candidate. 1928d5caef5bSAndrii Nakryiko */ 1929d5caef5bSAndrii Nakryiko static int btf_dedup_prim_type(struct btf_dedup *d, __u32 type_id) 1930d5caef5bSAndrii Nakryiko { 1931d5caef5bSAndrii Nakryiko struct btf_type *t = d->btf->types[type_id]; 1932d5caef5bSAndrii Nakryiko struct btf_type *cand; 1933d5caef5bSAndrii Nakryiko struct btf_dedup_node *cand_node; 1934d5caef5bSAndrii Nakryiko /* if we don't find equivalent type, then we are canonical */ 1935d5caef5bSAndrii Nakryiko __u32 new_id = type_id; 1936d5caef5bSAndrii Nakryiko __u32 h; 1937d5caef5bSAndrii Nakryiko 1938d5caef5bSAndrii Nakryiko switch (BTF_INFO_KIND(t->info)) { 1939d5caef5bSAndrii Nakryiko case BTF_KIND_CONST: 1940d5caef5bSAndrii Nakryiko case BTF_KIND_VOLATILE: 1941d5caef5bSAndrii Nakryiko case BTF_KIND_RESTRICT: 1942d5caef5bSAndrii Nakryiko case BTF_KIND_PTR: 1943d5caef5bSAndrii Nakryiko case BTF_KIND_TYPEDEF: 1944d5caef5bSAndrii Nakryiko case BTF_KIND_ARRAY: 1945d5caef5bSAndrii Nakryiko case BTF_KIND_STRUCT: 1946d5caef5bSAndrii Nakryiko case BTF_KIND_UNION: 1947d5caef5bSAndrii Nakryiko case BTF_KIND_FUNC: 1948d5caef5bSAndrii Nakryiko case BTF_KIND_FUNC_PROTO: 1949d5caef5bSAndrii Nakryiko return 0; 1950d5caef5bSAndrii Nakryiko 1951d5caef5bSAndrii Nakryiko case BTF_KIND_INT: 1952d5caef5bSAndrii Nakryiko h = btf_hash_int(t); 195351edf5f6SAndrii Nakryiko for_each_dedup_cand(d, h, cand_node) { 1954d5caef5bSAndrii Nakryiko cand = d->btf->types[cand_node->type_id]; 1955d5caef5bSAndrii Nakryiko if (btf_equal_int(t, cand)) { 1956d5caef5bSAndrii Nakryiko new_id = cand_node->type_id; 1957d5caef5bSAndrii Nakryiko break; 1958d5caef5bSAndrii Nakryiko } 1959d5caef5bSAndrii Nakryiko } 1960d5caef5bSAndrii Nakryiko break; 1961d5caef5bSAndrii Nakryiko 1962d5caef5bSAndrii Nakryiko case BTF_KIND_ENUM: 1963d5caef5bSAndrii Nakryiko h = btf_hash_enum(t); 196451edf5f6SAndrii Nakryiko for_each_dedup_cand(d, h, cand_node) { 1965d5caef5bSAndrii Nakryiko cand = d->btf->types[cand_node->type_id]; 1966d5caef5bSAndrii Nakryiko if (btf_equal_enum(t, cand)) { 1967d5caef5bSAndrii Nakryiko new_id = cand_node->type_id; 1968d5caef5bSAndrii Nakryiko break; 1969d5caef5bSAndrii Nakryiko } 19709768095bSAndrii Nakryiko if (d->opts.dont_resolve_fwds) 19719768095bSAndrii Nakryiko continue; 19729768095bSAndrii Nakryiko if (btf_compat_enum(t, cand)) { 19739768095bSAndrii Nakryiko if (btf_is_enum_fwd(t)) { 19749768095bSAndrii Nakryiko /* resolve fwd to full enum */ 19759768095bSAndrii Nakryiko new_id = cand_node->type_id; 19769768095bSAndrii Nakryiko break; 19779768095bSAndrii Nakryiko } 19789768095bSAndrii Nakryiko /* resolve canonical enum fwd to full enum */ 19799768095bSAndrii Nakryiko d->map[cand_node->type_id] = type_id; 19809768095bSAndrii Nakryiko } 1981d5caef5bSAndrii Nakryiko } 1982d5caef5bSAndrii Nakryiko break; 1983d5caef5bSAndrii Nakryiko 1984d5caef5bSAndrii Nakryiko case BTF_KIND_FWD: 1985d5caef5bSAndrii Nakryiko h = btf_hash_common(t); 198651edf5f6SAndrii Nakryiko for_each_dedup_cand(d, h, cand_node) { 1987d5caef5bSAndrii Nakryiko cand = d->btf->types[cand_node->type_id]; 1988d5caef5bSAndrii Nakryiko if (btf_equal_common(t, cand)) { 1989d5caef5bSAndrii Nakryiko new_id = cand_node->type_id; 1990d5caef5bSAndrii Nakryiko break; 1991d5caef5bSAndrii Nakryiko } 1992d5caef5bSAndrii Nakryiko } 1993d5caef5bSAndrii Nakryiko break; 1994d5caef5bSAndrii Nakryiko 1995d5caef5bSAndrii Nakryiko default: 1996d5caef5bSAndrii Nakryiko return -EINVAL; 1997d5caef5bSAndrii Nakryiko } 1998d5caef5bSAndrii Nakryiko 1999d5caef5bSAndrii Nakryiko d->map[type_id] = new_id; 2000d5caef5bSAndrii Nakryiko if (type_id == new_id && btf_dedup_table_add(d, h, type_id)) 2001d5caef5bSAndrii Nakryiko return -ENOMEM; 2002d5caef5bSAndrii Nakryiko 2003d5caef5bSAndrii Nakryiko return 0; 2004d5caef5bSAndrii Nakryiko } 2005d5caef5bSAndrii Nakryiko 2006d5caef5bSAndrii Nakryiko static int btf_dedup_prim_types(struct btf_dedup *d) 2007d5caef5bSAndrii Nakryiko { 2008d5caef5bSAndrii Nakryiko int i, err; 2009d5caef5bSAndrii Nakryiko 2010d5caef5bSAndrii Nakryiko for (i = 1; i <= d->btf->nr_types; i++) { 2011d5caef5bSAndrii Nakryiko err = btf_dedup_prim_type(d, i); 2012d5caef5bSAndrii Nakryiko if (err) 2013d5caef5bSAndrii Nakryiko return err; 2014d5caef5bSAndrii Nakryiko } 2015d5caef5bSAndrii Nakryiko return 0; 2016d5caef5bSAndrii Nakryiko } 2017d5caef5bSAndrii Nakryiko 2018d5caef5bSAndrii Nakryiko /* 2019d5caef5bSAndrii Nakryiko * Check whether type is already mapped into canonical one (could be to itself). 2020d5caef5bSAndrii Nakryiko */ 2021d5caef5bSAndrii Nakryiko static inline bool is_type_mapped(struct btf_dedup *d, uint32_t type_id) 2022d5caef5bSAndrii Nakryiko { 20235aab392cSAndrii Nakryiko return d->map[type_id] <= BTF_MAX_NR_TYPES; 2024d5caef5bSAndrii Nakryiko } 2025d5caef5bSAndrii Nakryiko 2026d5caef5bSAndrii Nakryiko /* 2027d5caef5bSAndrii Nakryiko * Resolve type ID into its canonical type ID, if any; otherwise return original 2028d5caef5bSAndrii Nakryiko * type ID. If type is FWD and is resolved into STRUCT/UNION already, follow 2029d5caef5bSAndrii Nakryiko * STRUCT/UNION link and resolve it into canonical type ID as well. 2030d5caef5bSAndrii Nakryiko */ 2031d5caef5bSAndrii Nakryiko static inline __u32 resolve_type_id(struct btf_dedup *d, __u32 type_id) 2032d5caef5bSAndrii Nakryiko { 2033d5caef5bSAndrii Nakryiko while (is_type_mapped(d, type_id) && d->map[type_id] != type_id) 2034d5caef5bSAndrii Nakryiko type_id = d->map[type_id]; 2035d5caef5bSAndrii Nakryiko return type_id; 2036d5caef5bSAndrii Nakryiko } 2037d5caef5bSAndrii Nakryiko 2038d5caef5bSAndrii Nakryiko /* 2039d5caef5bSAndrii Nakryiko * Resolve FWD to underlying STRUCT/UNION, if any; otherwise return original 2040d5caef5bSAndrii Nakryiko * type ID. 2041d5caef5bSAndrii Nakryiko */ 2042d5caef5bSAndrii Nakryiko static uint32_t resolve_fwd_id(struct btf_dedup *d, uint32_t type_id) 2043d5caef5bSAndrii Nakryiko { 2044d5caef5bSAndrii Nakryiko __u32 orig_type_id = type_id; 2045d5caef5bSAndrii Nakryiko 2046d5caef5bSAndrii Nakryiko if (BTF_INFO_KIND(d->btf->types[type_id]->info) != BTF_KIND_FWD) 2047d5caef5bSAndrii Nakryiko return type_id; 2048d5caef5bSAndrii Nakryiko 2049d5caef5bSAndrii Nakryiko while (is_type_mapped(d, type_id) && d->map[type_id] != type_id) 2050d5caef5bSAndrii Nakryiko type_id = d->map[type_id]; 2051d5caef5bSAndrii Nakryiko 2052d5caef5bSAndrii Nakryiko if (BTF_INFO_KIND(d->btf->types[type_id]->info) != BTF_KIND_FWD) 2053d5caef5bSAndrii Nakryiko return type_id; 2054d5caef5bSAndrii Nakryiko 2055d5caef5bSAndrii Nakryiko return orig_type_id; 2056d5caef5bSAndrii Nakryiko } 2057d5caef5bSAndrii Nakryiko 2058d5caef5bSAndrii Nakryiko 2059d5caef5bSAndrii Nakryiko static inline __u16 btf_fwd_kind(struct btf_type *t) 2060d5caef5bSAndrii Nakryiko { 2061d5caef5bSAndrii Nakryiko return BTF_INFO_KFLAG(t->info) ? BTF_KIND_UNION : BTF_KIND_STRUCT; 2062d5caef5bSAndrii Nakryiko } 2063d5caef5bSAndrii Nakryiko 2064d5caef5bSAndrii Nakryiko /* 2065d5caef5bSAndrii Nakryiko * Check equivalence of BTF type graph formed by candidate struct/union (we'll 2066d5caef5bSAndrii Nakryiko * call it "candidate graph" in this description for brevity) to a type graph 2067d5caef5bSAndrii Nakryiko * formed by (potential) canonical struct/union ("canonical graph" for brevity 2068d5caef5bSAndrii Nakryiko * here, though keep in mind that not all types in canonical graph are 2069d5caef5bSAndrii Nakryiko * necessarily canonical representatives themselves, some of them might be 2070d5caef5bSAndrii Nakryiko * duplicates or its uniqueness might not have been established yet). 2071d5caef5bSAndrii Nakryiko * Returns: 2072d5caef5bSAndrii Nakryiko * - >0, if type graphs are equivalent; 2073d5caef5bSAndrii Nakryiko * - 0, if not equivalent; 2074d5caef5bSAndrii Nakryiko * - <0, on error. 2075d5caef5bSAndrii Nakryiko * 2076d5caef5bSAndrii Nakryiko * Algorithm performs side-by-side DFS traversal of both type graphs and checks 2077d5caef5bSAndrii Nakryiko * equivalence of BTF types at each step. If at any point BTF types in candidate 2078d5caef5bSAndrii Nakryiko * and canonical graphs are not compatible structurally, whole graphs are 2079d5caef5bSAndrii Nakryiko * incompatible. If types are structurally equivalent (i.e., all information 2080d5caef5bSAndrii Nakryiko * except referenced type IDs is exactly the same), a mapping from `canon_id` to 2081d5caef5bSAndrii Nakryiko * a `cand_id` is recored in hypothetical mapping (`btf_dedup->hypot_map`). 2082d5caef5bSAndrii Nakryiko * If a type references other types, then those referenced types are checked 2083d5caef5bSAndrii Nakryiko * for equivalence recursively. 2084d5caef5bSAndrii Nakryiko * 2085d5caef5bSAndrii Nakryiko * During DFS traversal, if we find that for current `canon_id` type we 2086d5caef5bSAndrii Nakryiko * already have some mapping in hypothetical map, we check for two possible 2087d5caef5bSAndrii Nakryiko * situations: 2088d5caef5bSAndrii Nakryiko * - `canon_id` is mapped to exactly the same type as `cand_id`. This will 2089d5caef5bSAndrii Nakryiko * happen when type graphs have cycles. In this case we assume those two 2090d5caef5bSAndrii Nakryiko * types are equivalent. 2091d5caef5bSAndrii Nakryiko * - `canon_id` is mapped to different type. This is contradiction in our 2092d5caef5bSAndrii Nakryiko * hypothetical mapping, because same graph in canonical graph corresponds 2093d5caef5bSAndrii Nakryiko * to two different types in candidate graph, which for equivalent type 2094d5caef5bSAndrii Nakryiko * graphs shouldn't happen. This condition terminates equivalence check 2095d5caef5bSAndrii Nakryiko * with negative result. 2096d5caef5bSAndrii Nakryiko * 2097d5caef5bSAndrii Nakryiko * If type graphs traversal exhausts types to check and find no contradiction, 2098d5caef5bSAndrii Nakryiko * then type graphs are equivalent. 2099d5caef5bSAndrii Nakryiko * 2100d5caef5bSAndrii Nakryiko * When checking types for equivalence, there is one special case: FWD types. 2101d5caef5bSAndrii Nakryiko * If FWD type resolution is allowed and one of the types (either from canonical 2102d5caef5bSAndrii Nakryiko * or candidate graph) is FWD and other is STRUCT/UNION (depending on FWD's kind 2103d5caef5bSAndrii Nakryiko * flag) and their names match, hypothetical mapping is updated to point from 2104d5caef5bSAndrii Nakryiko * FWD to STRUCT/UNION. If graphs will be determined as equivalent successfully, 2105d5caef5bSAndrii Nakryiko * this mapping will be used to record FWD -> STRUCT/UNION mapping permanently. 2106d5caef5bSAndrii Nakryiko * 2107d5caef5bSAndrii Nakryiko * Technically, this could lead to incorrect FWD to STRUCT/UNION resolution, 2108d5caef5bSAndrii Nakryiko * if there are two exactly named (or anonymous) structs/unions that are 2109d5caef5bSAndrii Nakryiko * compatible structurally, one of which has FWD field, while other is concrete 2110d5caef5bSAndrii Nakryiko * STRUCT/UNION, but according to C sources they are different structs/unions 2111d5caef5bSAndrii Nakryiko * that are referencing different types with the same name. This is extremely 2112d5caef5bSAndrii Nakryiko * unlikely to happen, but btf_dedup API allows to disable FWD resolution if 2113d5caef5bSAndrii Nakryiko * this logic is causing problems. 2114d5caef5bSAndrii Nakryiko * 2115d5caef5bSAndrii Nakryiko * Doing FWD resolution means that both candidate and/or canonical graphs can 2116d5caef5bSAndrii Nakryiko * consists of portions of the graph that come from multiple compilation units. 2117d5caef5bSAndrii Nakryiko * This is due to the fact that types within single compilation unit are always 2118d5caef5bSAndrii Nakryiko * deduplicated and FWDs are already resolved, if referenced struct/union 2119d5caef5bSAndrii Nakryiko * definiton is available. So, if we had unresolved FWD and found corresponding 2120d5caef5bSAndrii Nakryiko * STRUCT/UNION, they will be from different compilation units. This 2121d5caef5bSAndrii Nakryiko * consequently means that when we "link" FWD to corresponding STRUCT/UNION, 2122d5caef5bSAndrii Nakryiko * type graph will likely have at least two different BTF types that describe 2123d5caef5bSAndrii Nakryiko * same type (e.g., most probably there will be two different BTF types for the 2124d5caef5bSAndrii Nakryiko * same 'int' primitive type) and could even have "overlapping" parts of type 2125d5caef5bSAndrii Nakryiko * graph that describe same subset of types. 2126d5caef5bSAndrii Nakryiko * 2127d5caef5bSAndrii Nakryiko * This in turn means that our assumption that each type in canonical graph 2128d5caef5bSAndrii Nakryiko * must correspond to exactly one type in candidate graph might not hold 2129d5caef5bSAndrii Nakryiko * anymore and will make it harder to detect contradictions using hypothetical 2130d5caef5bSAndrii Nakryiko * map. To handle this problem, we allow to follow FWD -> STRUCT/UNION 2131d5caef5bSAndrii Nakryiko * resolution only in canonical graph. FWDs in candidate graphs are never 2132d5caef5bSAndrii Nakryiko * resolved. To see why it's OK, let's check all possible situations w.r.t. FWDs 2133d5caef5bSAndrii Nakryiko * that can occur: 2134d5caef5bSAndrii Nakryiko * - Both types in canonical and candidate graphs are FWDs. If they are 2135d5caef5bSAndrii Nakryiko * structurally equivalent, then they can either be both resolved to the 2136d5caef5bSAndrii Nakryiko * same STRUCT/UNION or not resolved at all. In both cases they are 2137d5caef5bSAndrii Nakryiko * equivalent and there is no need to resolve FWD on candidate side. 2138d5caef5bSAndrii Nakryiko * - Both types in canonical and candidate graphs are concrete STRUCT/UNION, 2139d5caef5bSAndrii Nakryiko * so nothing to resolve as well, algorithm will check equivalence anyway. 2140d5caef5bSAndrii Nakryiko * - Type in canonical graph is FWD, while type in candidate is concrete 2141d5caef5bSAndrii Nakryiko * STRUCT/UNION. In this case candidate graph comes from single compilation 2142d5caef5bSAndrii Nakryiko * unit, so there is exactly one BTF type for each unique C type. After 2143d5caef5bSAndrii Nakryiko * resolving FWD into STRUCT/UNION, there might be more than one BTF type 2144d5caef5bSAndrii Nakryiko * in canonical graph mapping to single BTF type in candidate graph, but 2145d5caef5bSAndrii Nakryiko * because hypothetical mapping maps from canonical to candidate types, it's 2146d5caef5bSAndrii Nakryiko * alright, and we still maintain the property of having single `canon_id` 2147d5caef5bSAndrii Nakryiko * mapping to single `cand_id` (there could be two different `canon_id` 2148d5caef5bSAndrii Nakryiko * mapped to the same `cand_id`, but it's not contradictory). 2149d5caef5bSAndrii Nakryiko * - Type in canonical graph is concrete STRUCT/UNION, while type in candidate 2150d5caef5bSAndrii Nakryiko * graph is FWD. In this case we are just going to check compatibility of 2151d5caef5bSAndrii Nakryiko * STRUCT/UNION and corresponding FWD, and if they are compatible, we'll 2152d5caef5bSAndrii Nakryiko * assume that whatever STRUCT/UNION FWD resolves to must be equivalent to 2153d5caef5bSAndrii Nakryiko * a concrete STRUCT/UNION from canonical graph. If the rest of type graphs 2154d5caef5bSAndrii Nakryiko * turn out equivalent, we'll re-resolve FWD to concrete STRUCT/UNION from 2155d5caef5bSAndrii Nakryiko * canonical graph. 2156d5caef5bSAndrii Nakryiko */ 2157d5caef5bSAndrii Nakryiko static int btf_dedup_is_equiv(struct btf_dedup *d, __u32 cand_id, 2158d5caef5bSAndrii Nakryiko __u32 canon_id) 2159d5caef5bSAndrii Nakryiko { 2160d5caef5bSAndrii Nakryiko struct btf_type *cand_type; 2161d5caef5bSAndrii Nakryiko struct btf_type *canon_type; 2162d5caef5bSAndrii Nakryiko __u32 hypot_type_id; 2163d5caef5bSAndrii Nakryiko __u16 cand_kind; 2164d5caef5bSAndrii Nakryiko __u16 canon_kind; 2165d5caef5bSAndrii Nakryiko int i, eq; 2166d5caef5bSAndrii Nakryiko 2167d5caef5bSAndrii Nakryiko /* if both resolve to the same canonical, they must be equivalent */ 2168d5caef5bSAndrii Nakryiko if (resolve_type_id(d, cand_id) == resolve_type_id(d, canon_id)) 2169d5caef5bSAndrii Nakryiko return 1; 2170d5caef5bSAndrii Nakryiko 2171d5caef5bSAndrii Nakryiko canon_id = resolve_fwd_id(d, canon_id); 2172d5caef5bSAndrii Nakryiko 2173d5caef5bSAndrii Nakryiko hypot_type_id = d->hypot_map[canon_id]; 21745aab392cSAndrii Nakryiko if (hypot_type_id <= BTF_MAX_NR_TYPES) 2175d5caef5bSAndrii Nakryiko return hypot_type_id == cand_id; 2176d5caef5bSAndrii Nakryiko 2177d5caef5bSAndrii Nakryiko if (btf_dedup_hypot_map_add(d, canon_id, cand_id)) 2178d5caef5bSAndrii Nakryiko return -ENOMEM; 2179d5caef5bSAndrii Nakryiko 2180d5caef5bSAndrii Nakryiko cand_type = d->btf->types[cand_id]; 2181d5caef5bSAndrii Nakryiko canon_type = d->btf->types[canon_id]; 2182d5caef5bSAndrii Nakryiko cand_kind = BTF_INFO_KIND(cand_type->info); 2183d5caef5bSAndrii Nakryiko canon_kind = BTF_INFO_KIND(canon_type->info); 2184d5caef5bSAndrii Nakryiko 2185d5caef5bSAndrii Nakryiko if (cand_type->name_off != canon_type->name_off) 2186d5caef5bSAndrii Nakryiko return 0; 2187d5caef5bSAndrii Nakryiko 2188d5caef5bSAndrii Nakryiko /* FWD <--> STRUCT/UNION equivalence check, if enabled */ 2189d5caef5bSAndrii Nakryiko if (!d->opts.dont_resolve_fwds 2190d5caef5bSAndrii Nakryiko && (cand_kind == BTF_KIND_FWD || canon_kind == BTF_KIND_FWD) 2191d5caef5bSAndrii Nakryiko && cand_kind != canon_kind) { 2192d5caef5bSAndrii Nakryiko __u16 real_kind; 2193d5caef5bSAndrii Nakryiko __u16 fwd_kind; 2194d5caef5bSAndrii Nakryiko 2195d5caef5bSAndrii Nakryiko if (cand_kind == BTF_KIND_FWD) { 2196d5caef5bSAndrii Nakryiko real_kind = canon_kind; 2197d5caef5bSAndrii Nakryiko fwd_kind = btf_fwd_kind(cand_type); 2198d5caef5bSAndrii Nakryiko } else { 2199d5caef5bSAndrii Nakryiko real_kind = cand_kind; 2200d5caef5bSAndrii Nakryiko fwd_kind = btf_fwd_kind(canon_type); 2201d5caef5bSAndrii Nakryiko } 2202d5caef5bSAndrii Nakryiko return fwd_kind == real_kind; 2203d5caef5bSAndrii Nakryiko } 2204d5caef5bSAndrii Nakryiko 2205d5caef5bSAndrii Nakryiko switch (cand_kind) { 2206d5caef5bSAndrii Nakryiko case BTF_KIND_INT: 2207d5caef5bSAndrii Nakryiko return btf_equal_int(cand_type, canon_type); 2208d5caef5bSAndrii Nakryiko 2209d5caef5bSAndrii Nakryiko case BTF_KIND_ENUM: 22109768095bSAndrii Nakryiko if (d->opts.dont_resolve_fwds) 2211d5caef5bSAndrii Nakryiko return btf_equal_enum(cand_type, canon_type); 22129768095bSAndrii Nakryiko else 22139768095bSAndrii Nakryiko return btf_compat_enum(cand_type, canon_type); 2214d5caef5bSAndrii Nakryiko 2215d5caef5bSAndrii Nakryiko case BTF_KIND_FWD: 2216d5caef5bSAndrii Nakryiko return btf_equal_common(cand_type, canon_type); 2217d5caef5bSAndrii Nakryiko 2218d5caef5bSAndrii Nakryiko case BTF_KIND_CONST: 2219d5caef5bSAndrii Nakryiko case BTF_KIND_VOLATILE: 2220d5caef5bSAndrii Nakryiko case BTF_KIND_RESTRICT: 2221d5caef5bSAndrii Nakryiko case BTF_KIND_PTR: 2222d5caef5bSAndrii Nakryiko case BTF_KIND_TYPEDEF: 2223d5caef5bSAndrii Nakryiko case BTF_KIND_FUNC: 22249768095bSAndrii Nakryiko if (cand_type->info != canon_type->info) 22259768095bSAndrii Nakryiko return 0; 2226d5caef5bSAndrii Nakryiko return btf_dedup_is_equiv(d, cand_type->type, canon_type->type); 2227d5caef5bSAndrii Nakryiko 2228d5caef5bSAndrii Nakryiko case BTF_KIND_ARRAY: { 2229d5caef5bSAndrii Nakryiko struct btf_array *cand_arr, *canon_arr; 2230d5caef5bSAndrii Nakryiko 2231d5caef5bSAndrii Nakryiko if (!btf_compat_array(cand_type, canon_type)) 2232d5caef5bSAndrii Nakryiko return 0; 2233d5caef5bSAndrii Nakryiko cand_arr = (struct btf_array *)(cand_type + 1); 2234d5caef5bSAndrii Nakryiko canon_arr = (struct btf_array *)(canon_type + 1); 2235d5caef5bSAndrii Nakryiko eq = btf_dedup_is_equiv(d, 2236d5caef5bSAndrii Nakryiko cand_arr->index_type, canon_arr->index_type); 2237d5caef5bSAndrii Nakryiko if (eq <= 0) 2238d5caef5bSAndrii Nakryiko return eq; 2239d5caef5bSAndrii Nakryiko return btf_dedup_is_equiv(d, cand_arr->type, canon_arr->type); 2240d5caef5bSAndrii Nakryiko } 2241d5caef5bSAndrii Nakryiko 2242d5caef5bSAndrii Nakryiko case BTF_KIND_STRUCT: 2243d5caef5bSAndrii Nakryiko case BTF_KIND_UNION: { 2244d5caef5bSAndrii Nakryiko struct btf_member *cand_m, *canon_m; 2245d5caef5bSAndrii Nakryiko __u16 vlen; 2246d5caef5bSAndrii Nakryiko 224791097fbeSAndrii Nakryiko if (!btf_shallow_equal_struct(cand_type, canon_type)) 2248d5caef5bSAndrii Nakryiko return 0; 2249d5caef5bSAndrii Nakryiko vlen = BTF_INFO_VLEN(cand_type->info); 2250d5caef5bSAndrii Nakryiko cand_m = (struct btf_member *)(cand_type + 1); 2251d5caef5bSAndrii Nakryiko canon_m = (struct btf_member *)(canon_type + 1); 2252d5caef5bSAndrii Nakryiko for (i = 0; i < vlen; i++) { 2253d5caef5bSAndrii Nakryiko eq = btf_dedup_is_equiv(d, cand_m->type, canon_m->type); 2254d5caef5bSAndrii Nakryiko if (eq <= 0) 2255d5caef5bSAndrii Nakryiko return eq; 2256d5caef5bSAndrii Nakryiko cand_m++; 2257d5caef5bSAndrii Nakryiko canon_m++; 2258d5caef5bSAndrii Nakryiko } 2259d5caef5bSAndrii Nakryiko 2260d5caef5bSAndrii Nakryiko return 1; 2261d5caef5bSAndrii Nakryiko } 2262d5caef5bSAndrii Nakryiko 2263d5caef5bSAndrii Nakryiko case BTF_KIND_FUNC_PROTO: { 2264d5caef5bSAndrii Nakryiko struct btf_param *cand_p, *canon_p; 2265d5caef5bSAndrii Nakryiko __u16 vlen; 2266d5caef5bSAndrii Nakryiko 2267d5caef5bSAndrii Nakryiko if (!btf_compat_fnproto(cand_type, canon_type)) 2268d5caef5bSAndrii Nakryiko return 0; 2269d5caef5bSAndrii Nakryiko eq = btf_dedup_is_equiv(d, cand_type->type, canon_type->type); 2270d5caef5bSAndrii Nakryiko if (eq <= 0) 2271d5caef5bSAndrii Nakryiko return eq; 2272d5caef5bSAndrii Nakryiko vlen = BTF_INFO_VLEN(cand_type->info); 2273d5caef5bSAndrii Nakryiko cand_p = (struct btf_param *)(cand_type + 1); 2274d5caef5bSAndrii Nakryiko canon_p = (struct btf_param *)(canon_type + 1); 2275d5caef5bSAndrii Nakryiko for (i = 0; i < vlen; i++) { 2276d5caef5bSAndrii Nakryiko eq = btf_dedup_is_equiv(d, cand_p->type, canon_p->type); 2277d5caef5bSAndrii Nakryiko if (eq <= 0) 2278d5caef5bSAndrii Nakryiko return eq; 2279d5caef5bSAndrii Nakryiko cand_p++; 2280d5caef5bSAndrii Nakryiko canon_p++; 2281d5caef5bSAndrii Nakryiko } 2282d5caef5bSAndrii Nakryiko return 1; 2283d5caef5bSAndrii Nakryiko } 2284d5caef5bSAndrii Nakryiko 2285d5caef5bSAndrii Nakryiko default: 2286d5caef5bSAndrii Nakryiko return -EINVAL; 2287d5caef5bSAndrii Nakryiko } 2288d5caef5bSAndrii Nakryiko return 0; 2289d5caef5bSAndrii Nakryiko } 2290d5caef5bSAndrii Nakryiko 2291d5caef5bSAndrii Nakryiko /* 2292d5caef5bSAndrii Nakryiko * Use hypothetical mapping, produced by successful type graph equivalence 2293d5caef5bSAndrii Nakryiko * check, to augment existing struct/union canonical mapping, where possible. 2294d5caef5bSAndrii Nakryiko * 2295d5caef5bSAndrii Nakryiko * If BTF_KIND_FWD resolution is allowed, this mapping is also used to record 2296d5caef5bSAndrii Nakryiko * FWD -> STRUCT/UNION correspondence as well. FWD resolution is bidirectional: 2297d5caef5bSAndrii Nakryiko * it doesn't matter if FWD type was part of canonical graph or candidate one, 2298d5caef5bSAndrii Nakryiko * we are recording the mapping anyway. As opposed to carefulness required 2299d5caef5bSAndrii Nakryiko * for struct/union correspondence mapping (described below), for FWD resolution 2300d5caef5bSAndrii Nakryiko * it's not important, as by the time that FWD type (reference type) will be 2301d5caef5bSAndrii Nakryiko * deduplicated all structs/unions will be deduped already anyway. 2302d5caef5bSAndrii Nakryiko * 2303d5caef5bSAndrii Nakryiko * Recording STRUCT/UNION mapping is purely a performance optimization and is 2304d5caef5bSAndrii Nakryiko * not required for correctness. It needs to be done carefully to ensure that 2305d5caef5bSAndrii Nakryiko * struct/union from candidate's type graph is not mapped into corresponding 2306d5caef5bSAndrii Nakryiko * struct/union from canonical type graph that itself hasn't been resolved into 2307d5caef5bSAndrii Nakryiko * canonical representative. The only guarantee we have is that canonical 2308d5caef5bSAndrii Nakryiko * struct/union was determined as canonical and that won't change. But any 2309d5caef5bSAndrii Nakryiko * types referenced through that struct/union fields could have been not yet 2310d5caef5bSAndrii Nakryiko * resolved, so in case like that it's too early to establish any kind of 2311d5caef5bSAndrii Nakryiko * correspondence between structs/unions. 2312d5caef5bSAndrii Nakryiko * 2313d5caef5bSAndrii Nakryiko * No canonical correspondence is derived for primitive types (they are already 2314d5caef5bSAndrii Nakryiko * deduplicated completely already anyway) or reference types (they rely on 2315d5caef5bSAndrii Nakryiko * stability of struct/union canonical relationship for equivalence checks). 2316d5caef5bSAndrii Nakryiko */ 2317d5caef5bSAndrii Nakryiko static void btf_dedup_merge_hypot_map(struct btf_dedup *d) 2318d5caef5bSAndrii Nakryiko { 2319d5caef5bSAndrii Nakryiko __u32 cand_type_id, targ_type_id; 2320d5caef5bSAndrii Nakryiko __u16 t_kind, c_kind; 2321d5caef5bSAndrii Nakryiko __u32 t_id, c_id; 2322d5caef5bSAndrii Nakryiko int i; 2323d5caef5bSAndrii Nakryiko 2324d5caef5bSAndrii Nakryiko for (i = 0; i < d->hypot_cnt; i++) { 2325d5caef5bSAndrii Nakryiko cand_type_id = d->hypot_list[i]; 2326d5caef5bSAndrii Nakryiko targ_type_id = d->hypot_map[cand_type_id]; 2327d5caef5bSAndrii Nakryiko t_id = resolve_type_id(d, targ_type_id); 2328d5caef5bSAndrii Nakryiko c_id = resolve_type_id(d, cand_type_id); 2329d5caef5bSAndrii Nakryiko t_kind = BTF_INFO_KIND(d->btf->types[t_id]->info); 2330d5caef5bSAndrii Nakryiko c_kind = BTF_INFO_KIND(d->btf->types[c_id]->info); 2331d5caef5bSAndrii Nakryiko /* 2332d5caef5bSAndrii Nakryiko * Resolve FWD into STRUCT/UNION. 2333d5caef5bSAndrii Nakryiko * It's ok to resolve FWD into STRUCT/UNION that's not yet 2334d5caef5bSAndrii Nakryiko * mapped to canonical representative (as opposed to 2335d5caef5bSAndrii Nakryiko * STRUCT/UNION <--> STRUCT/UNION mapping logic below), because 2336d5caef5bSAndrii Nakryiko * eventually that struct is going to be mapped and all resolved 2337d5caef5bSAndrii Nakryiko * FWDs will automatically resolve to correct canonical 2338d5caef5bSAndrii Nakryiko * representative. This will happen before ref type deduping, 2339d5caef5bSAndrii Nakryiko * which critically depends on stability of these mapping. This 2340d5caef5bSAndrii Nakryiko * stability is not a requirement for STRUCT/UNION equivalence 2341d5caef5bSAndrii Nakryiko * checks, though. 2342d5caef5bSAndrii Nakryiko */ 2343d5caef5bSAndrii Nakryiko if (t_kind != BTF_KIND_FWD && c_kind == BTF_KIND_FWD) 2344d5caef5bSAndrii Nakryiko d->map[c_id] = t_id; 2345d5caef5bSAndrii Nakryiko else if (t_kind == BTF_KIND_FWD && c_kind != BTF_KIND_FWD) 2346d5caef5bSAndrii Nakryiko d->map[t_id] = c_id; 2347d5caef5bSAndrii Nakryiko 2348d5caef5bSAndrii Nakryiko if ((t_kind == BTF_KIND_STRUCT || t_kind == BTF_KIND_UNION) && 2349d5caef5bSAndrii Nakryiko c_kind != BTF_KIND_FWD && 2350d5caef5bSAndrii Nakryiko is_type_mapped(d, c_id) && 2351d5caef5bSAndrii Nakryiko !is_type_mapped(d, t_id)) { 2352d5caef5bSAndrii Nakryiko /* 2353d5caef5bSAndrii Nakryiko * as a perf optimization, we can map struct/union 2354d5caef5bSAndrii Nakryiko * that's part of type graph we just verified for 2355d5caef5bSAndrii Nakryiko * equivalence. We can do that for struct/union that has 2356d5caef5bSAndrii Nakryiko * canonical representative only, though. 2357d5caef5bSAndrii Nakryiko */ 2358d5caef5bSAndrii Nakryiko d->map[t_id] = c_id; 2359d5caef5bSAndrii Nakryiko } 2360d5caef5bSAndrii Nakryiko } 2361d5caef5bSAndrii Nakryiko } 2362d5caef5bSAndrii Nakryiko 2363d5caef5bSAndrii Nakryiko /* 2364d5caef5bSAndrii Nakryiko * Deduplicate struct/union types. 2365d5caef5bSAndrii Nakryiko * 2366d5caef5bSAndrii Nakryiko * For each struct/union type its type signature hash is calculated, taking 2367d5caef5bSAndrii Nakryiko * into account type's name, size, number, order and names of fields, but 2368d5caef5bSAndrii Nakryiko * ignoring type ID's referenced from fields, because they might not be deduped 2369d5caef5bSAndrii Nakryiko * completely until after reference types deduplication phase. This type hash 2370d5caef5bSAndrii Nakryiko * is used to iterate over all potential canonical types, sharing same hash. 2371d5caef5bSAndrii Nakryiko * For each canonical candidate we check whether type graphs that they form 2372d5caef5bSAndrii Nakryiko * (through referenced types in fields and so on) are equivalent using algorithm 2373d5caef5bSAndrii Nakryiko * implemented in `btf_dedup_is_equiv`. If such equivalence is found and 2374d5caef5bSAndrii Nakryiko * BTF_KIND_FWD resolution is allowed, then hypothetical mapping 2375d5caef5bSAndrii Nakryiko * (btf_dedup->hypot_map) produced by aforementioned type graph equivalence 2376d5caef5bSAndrii Nakryiko * algorithm is used to record FWD -> STRUCT/UNION mapping. It's also used to 2377d5caef5bSAndrii Nakryiko * potentially map other structs/unions to their canonical representatives, 2378d5caef5bSAndrii Nakryiko * if such relationship hasn't yet been established. This speeds up algorithm 2379d5caef5bSAndrii Nakryiko * by eliminating some of the duplicate work. 2380d5caef5bSAndrii Nakryiko * 2381d5caef5bSAndrii Nakryiko * If no matching canonical representative was found, struct/union is marked 2382d5caef5bSAndrii Nakryiko * as canonical for itself and is added into btf_dedup->dedup_table hash map 2383d5caef5bSAndrii Nakryiko * for further look ups. 2384d5caef5bSAndrii Nakryiko */ 2385d5caef5bSAndrii Nakryiko static int btf_dedup_struct_type(struct btf_dedup *d, __u32 type_id) 2386d5caef5bSAndrii Nakryiko { 2387d5caef5bSAndrii Nakryiko struct btf_dedup_node *cand_node; 238891097fbeSAndrii Nakryiko struct btf_type *cand_type, *t; 2389d5caef5bSAndrii Nakryiko /* if we don't find equivalent type, then we are canonical */ 2390d5caef5bSAndrii Nakryiko __u32 new_id = type_id; 2391d5caef5bSAndrii Nakryiko __u16 kind; 2392d5caef5bSAndrii Nakryiko __u32 h; 2393d5caef5bSAndrii Nakryiko 2394d5caef5bSAndrii Nakryiko /* already deduped or is in process of deduping (loop detected) */ 23955aab392cSAndrii Nakryiko if (d->map[type_id] <= BTF_MAX_NR_TYPES) 2396d5caef5bSAndrii Nakryiko return 0; 2397d5caef5bSAndrii Nakryiko 2398d5caef5bSAndrii Nakryiko t = d->btf->types[type_id]; 2399d5caef5bSAndrii Nakryiko kind = BTF_INFO_KIND(t->info); 2400d5caef5bSAndrii Nakryiko 2401d5caef5bSAndrii Nakryiko if (kind != BTF_KIND_STRUCT && kind != BTF_KIND_UNION) 2402d5caef5bSAndrii Nakryiko return 0; 2403d5caef5bSAndrii Nakryiko 2404d5caef5bSAndrii Nakryiko h = btf_hash_struct(t); 240551edf5f6SAndrii Nakryiko for_each_dedup_cand(d, h, cand_node) { 2406d5caef5bSAndrii Nakryiko int eq; 2407d5caef5bSAndrii Nakryiko 240891097fbeSAndrii Nakryiko /* 240991097fbeSAndrii Nakryiko * Even though btf_dedup_is_equiv() checks for 241091097fbeSAndrii Nakryiko * btf_shallow_equal_struct() internally when checking two 241191097fbeSAndrii Nakryiko * structs (unions) for equivalence, we need to guard here 241291097fbeSAndrii Nakryiko * from picking matching FWD type as a dedup candidate. 241391097fbeSAndrii Nakryiko * This can happen due to hash collision. In such case just 241491097fbeSAndrii Nakryiko * relying on btf_dedup_is_equiv() would lead to potentially 241591097fbeSAndrii Nakryiko * creating a loop (FWD -> STRUCT and STRUCT -> FWD), because 241691097fbeSAndrii Nakryiko * FWD and compatible STRUCT/UNION are considered equivalent. 241791097fbeSAndrii Nakryiko */ 241891097fbeSAndrii Nakryiko cand_type = d->btf->types[cand_node->type_id]; 241991097fbeSAndrii Nakryiko if (!btf_shallow_equal_struct(t, cand_type)) 242091097fbeSAndrii Nakryiko continue; 242191097fbeSAndrii Nakryiko 2422d5caef5bSAndrii Nakryiko btf_dedup_clear_hypot_map(d); 2423d5caef5bSAndrii Nakryiko eq = btf_dedup_is_equiv(d, type_id, cand_node->type_id); 2424d5caef5bSAndrii Nakryiko if (eq < 0) 2425d5caef5bSAndrii Nakryiko return eq; 2426d5caef5bSAndrii Nakryiko if (!eq) 2427d5caef5bSAndrii Nakryiko continue; 2428d5caef5bSAndrii Nakryiko new_id = cand_node->type_id; 2429d5caef5bSAndrii Nakryiko btf_dedup_merge_hypot_map(d); 2430d5caef5bSAndrii Nakryiko break; 2431d5caef5bSAndrii Nakryiko } 2432d5caef5bSAndrii Nakryiko 2433d5caef5bSAndrii Nakryiko d->map[type_id] = new_id; 2434d5caef5bSAndrii Nakryiko if (type_id == new_id && btf_dedup_table_add(d, h, type_id)) 2435d5caef5bSAndrii Nakryiko return -ENOMEM; 2436d5caef5bSAndrii Nakryiko 2437d5caef5bSAndrii Nakryiko return 0; 2438d5caef5bSAndrii Nakryiko } 2439d5caef5bSAndrii Nakryiko 2440d5caef5bSAndrii Nakryiko static int btf_dedup_struct_types(struct btf_dedup *d) 2441d5caef5bSAndrii Nakryiko { 2442d5caef5bSAndrii Nakryiko int i, err; 2443d5caef5bSAndrii Nakryiko 2444d5caef5bSAndrii Nakryiko for (i = 1; i <= d->btf->nr_types; i++) { 2445d5caef5bSAndrii Nakryiko err = btf_dedup_struct_type(d, i); 2446d5caef5bSAndrii Nakryiko if (err) 2447d5caef5bSAndrii Nakryiko return err; 2448d5caef5bSAndrii Nakryiko } 2449d5caef5bSAndrii Nakryiko return 0; 2450d5caef5bSAndrii Nakryiko } 2451d5caef5bSAndrii Nakryiko 2452d5caef5bSAndrii Nakryiko /* 2453d5caef5bSAndrii Nakryiko * Deduplicate reference type. 2454d5caef5bSAndrii Nakryiko * 2455d5caef5bSAndrii Nakryiko * Once all primitive and struct/union types got deduplicated, we can easily 2456d5caef5bSAndrii Nakryiko * deduplicate all other (reference) BTF types. This is done in two steps: 2457d5caef5bSAndrii Nakryiko * 2458d5caef5bSAndrii Nakryiko * 1. Resolve all referenced type IDs into their canonical type IDs. This 2459d5caef5bSAndrii Nakryiko * resolution can be done either immediately for primitive or struct/union types 2460d5caef5bSAndrii Nakryiko * (because they were deduped in previous two phases) or recursively for 2461d5caef5bSAndrii Nakryiko * reference types. Recursion will always terminate at either primitive or 2462d5caef5bSAndrii Nakryiko * struct/union type, at which point we can "unwind" chain of reference types 2463d5caef5bSAndrii Nakryiko * one by one. There is no danger of encountering cycles because in C type 2464d5caef5bSAndrii Nakryiko * system the only way to form type cycle is through struct/union, so any chain 2465d5caef5bSAndrii Nakryiko * of reference types, even those taking part in a type cycle, will inevitably 2466d5caef5bSAndrii Nakryiko * reach struct/union at some point. 2467d5caef5bSAndrii Nakryiko * 2468d5caef5bSAndrii Nakryiko * 2. Once all referenced type IDs are resolved into canonical ones, BTF type 2469d5caef5bSAndrii Nakryiko * becomes "stable", in the sense that no further deduplication will cause 2470d5caef5bSAndrii Nakryiko * any changes to it. With that, it's now possible to calculate type's signature 2471d5caef5bSAndrii Nakryiko * hash (this time taking into account referenced type IDs) and loop over all 2472d5caef5bSAndrii Nakryiko * potential canonical representatives. If no match was found, current type 2473d5caef5bSAndrii Nakryiko * will become canonical representative of itself and will be added into 2474d5caef5bSAndrii Nakryiko * btf_dedup->dedup_table as another possible canonical representative. 2475d5caef5bSAndrii Nakryiko */ 2476d5caef5bSAndrii Nakryiko static int btf_dedup_ref_type(struct btf_dedup *d, __u32 type_id) 2477d5caef5bSAndrii Nakryiko { 2478d5caef5bSAndrii Nakryiko struct btf_dedup_node *cand_node; 2479d5caef5bSAndrii Nakryiko struct btf_type *t, *cand; 2480d5caef5bSAndrii Nakryiko /* if we don't find equivalent type, then we are representative type */ 2481d5caef5bSAndrii Nakryiko __u32 new_id = type_id; 24823d8669e6SDan Carpenter int ref_type_id; 24833d8669e6SDan Carpenter __u32 h; 2484d5caef5bSAndrii Nakryiko 2485d5caef5bSAndrii Nakryiko if (d->map[type_id] == BTF_IN_PROGRESS_ID) 2486d5caef5bSAndrii Nakryiko return -ELOOP; 24875aab392cSAndrii Nakryiko if (d->map[type_id] <= BTF_MAX_NR_TYPES) 2488d5caef5bSAndrii Nakryiko return resolve_type_id(d, type_id); 2489d5caef5bSAndrii Nakryiko 2490d5caef5bSAndrii Nakryiko t = d->btf->types[type_id]; 2491d5caef5bSAndrii Nakryiko d->map[type_id] = BTF_IN_PROGRESS_ID; 2492d5caef5bSAndrii Nakryiko 2493d5caef5bSAndrii Nakryiko switch (BTF_INFO_KIND(t->info)) { 2494d5caef5bSAndrii Nakryiko case BTF_KIND_CONST: 2495d5caef5bSAndrii Nakryiko case BTF_KIND_VOLATILE: 2496d5caef5bSAndrii Nakryiko case BTF_KIND_RESTRICT: 2497d5caef5bSAndrii Nakryiko case BTF_KIND_PTR: 2498d5caef5bSAndrii Nakryiko case BTF_KIND_TYPEDEF: 2499d5caef5bSAndrii Nakryiko case BTF_KIND_FUNC: 2500d5caef5bSAndrii Nakryiko ref_type_id = btf_dedup_ref_type(d, t->type); 2501d5caef5bSAndrii Nakryiko if (ref_type_id < 0) 2502d5caef5bSAndrii Nakryiko return ref_type_id; 2503d5caef5bSAndrii Nakryiko t->type = ref_type_id; 2504d5caef5bSAndrii Nakryiko 2505d5caef5bSAndrii Nakryiko h = btf_hash_common(t); 250651edf5f6SAndrii Nakryiko for_each_dedup_cand(d, h, cand_node) { 2507d5caef5bSAndrii Nakryiko cand = d->btf->types[cand_node->type_id]; 2508d5caef5bSAndrii Nakryiko if (btf_equal_common(t, cand)) { 2509d5caef5bSAndrii Nakryiko new_id = cand_node->type_id; 2510d5caef5bSAndrii Nakryiko break; 2511d5caef5bSAndrii Nakryiko } 2512d5caef5bSAndrii Nakryiko } 2513d5caef5bSAndrii Nakryiko break; 2514d5caef5bSAndrii Nakryiko 2515d5caef5bSAndrii Nakryiko case BTF_KIND_ARRAY: { 2516d5caef5bSAndrii Nakryiko struct btf_array *info = (struct btf_array *)(t + 1); 2517d5caef5bSAndrii Nakryiko 2518d5caef5bSAndrii Nakryiko ref_type_id = btf_dedup_ref_type(d, info->type); 2519d5caef5bSAndrii Nakryiko if (ref_type_id < 0) 2520d5caef5bSAndrii Nakryiko return ref_type_id; 2521d5caef5bSAndrii Nakryiko info->type = ref_type_id; 2522d5caef5bSAndrii Nakryiko 2523d5caef5bSAndrii Nakryiko ref_type_id = btf_dedup_ref_type(d, info->index_type); 2524d5caef5bSAndrii Nakryiko if (ref_type_id < 0) 2525d5caef5bSAndrii Nakryiko return ref_type_id; 2526d5caef5bSAndrii Nakryiko info->index_type = ref_type_id; 2527d5caef5bSAndrii Nakryiko 2528d5caef5bSAndrii Nakryiko h = btf_hash_array(t); 252951edf5f6SAndrii Nakryiko for_each_dedup_cand(d, h, cand_node) { 2530d5caef5bSAndrii Nakryiko cand = d->btf->types[cand_node->type_id]; 2531d5caef5bSAndrii Nakryiko if (btf_equal_array(t, cand)) { 2532d5caef5bSAndrii Nakryiko new_id = cand_node->type_id; 2533d5caef5bSAndrii Nakryiko break; 2534d5caef5bSAndrii Nakryiko } 2535d5caef5bSAndrii Nakryiko } 2536d5caef5bSAndrii Nakryiko break; 2537d5caef5bSAndrii Nakryiko } 2538d5caef5bSAndrii Nakryiko 2539d5caef5bSAndrii Nakryiko case BTF_KIND_FUNC_PROTO: { 2540d5caef5bSAndrii Nakryiko struct btf_param *param; 2541d5caef5bSAndrii Nakryiko __u16 vlen; 2542d5caef5bSAndrii Nakryiko int i; 2543d5caef5bSAndrii Nakryiko 2544d5caef5bSAndrii Nakryiko ref_type_id = btf_dedup_ref_type(d, t->type); 2545d5caef5bSAndrii Nakryiko if (ref_type_id < 0) 2546d5caef5bSAndrii Nakryiko return ref_type_id; 2547d5caef5bSAndrii Nakryiko t->type = ref_type_id; 2548d5caef5bSAndrii Nakryiko 2549d5caef5bSAndrii Nakryiko vlen = BTF_INFO_VLEN(t->info); 2550d5caef5bSAndrii Nakryiko param = (struct btf_param *)(t + 1); 2551d5caef5bSAndrii Nakryiko for (i = 0; i < vlen; i++) { 2552d5caef5bSAndrii Nakryiko ref_type_id = btf_dedup_ref_type(d, param->type); 2553d5caef5bSAndrii Nakryiko if (ref_type_id < 0) 2554d5caef5bSAndrii Nakryiko return ref_type_id; 2555d5caef5bSAndrii Nakryiko param->type = ref_type_id; 2556d5caef5bSAndrii Nakryiko param++; 2557d5caef5bSAndrii Nakryiko } 2558d5caef5bSAndrii Nakryiko 2559d5caef5bSAndrii Nakryiko h = btf_hash_fnproto(t); 256051edf5f6SAndrii Nakryiko for_each_dedup_cand(d, h, cand_node) { 2561d5caef5bSAndrii Nakryiko cand = d->btf->types[cand_node->type_id]; 2562d5caef5bSAndrii Nakryiko if (btf_equal_fnproto(t, cand)) { 2563d5caef5bSAndrii Nakryiko new_id = cand_node->type_id; 2564d5caef5bSAndrii Nakryiko break; 2565d5caef5bSAndrii Nakryiko } 2566d5caef5bSAndrii Nakryiko } 2567d5caef5bSAndrii Nakryiko break; 2568d5caef5bSAndrii Nakryiko } 2569d5caef5bSAndrii Nakryiko 2570d5caef5bSAndrii Nakryiko default: 2571d5caef5bSAndrii Nakryiko return -EINVAL; 2572d5caef5bSAndrii Nakryiko } 2573d5caef5bSAndrii Nakryiko 2574d5caef5bSAndrii Nakryiko d->map[type_id] = new_id; 2575d5caef5bSAndrii Nakryiko if (type_id == new_id && btf_dedup_table_add(d, h, type_id)) 2576d5caef5bSAndrii Nakryiko return -ENOMEM; 2577d5caef5bSAndrii Nakryiko 2578d5caef5bSAndrii Nakryiko return new_id; 2579d5caef5bSAndrii Nakryiko } 2580d5caef5bSAndrii Nakryiko 2581d5caef5bSAndrii Nakryiko static int btf_dedup_ref_types(struct btf_dedup *d) 2582d5caef5bSAndrii Nakryiko { 2583d5caef5bSAndrii Nakryiko int i, err; 2584d5caef5bSAndrii Nakryiko 2585d5caef5bSAndrii Nakryiko for (i = 1; i <= d->btf->nr_types; i++) { 2586d5caef5bSAndrii Nakryiko err = btf_dedup_ref_type(d, i); 2587d5caef5bSAndrii Nakryiko if (err < 0) 2588d5caef5bSAndrii Nakryiko return err; 2589d5caef5bSAndrii Nakryiko } 2590d5caef5bSAndrii Nakryiko btf_dedup_table_free(d); 2591d5caef5bSAndrii Nakryiko return 0; 2592d5caef5bSAndrii Nakryiko } 2593d5caef5bSAndrii Nakryiko 2594d5caef5bSAndrii Nakryiko /* 2595d5caef5bSAndrii Nakryiko * Compact types. 2596d5caef5bSAndrii Nakryiko * 2597d5caef5bSAndrii Nakryiko * After we established for each type its corresponding canonical representative 2598d5caef5bSAndrii Nakryiko * type, we now can eliminate types that are not canonical and leave only 2599d5caef5bSAndrii Nakryiko * canonical ones layed out sequentially in memory by copying them over 2600d5caef5bSAndrii Nakryiko * duplicates. During compaction btf_dedup->hypot_map array is reused to store 2601d5caef5bSAndrii Nakryiko * a map from original type ID to a new compacted type ID, which will be used 2602d5caef5bSAndrii Nakryiko * during next phase to "fix up" type IDs, referenced from struct/union and 2603d5caef5bSAndrii Nakryiko * reference types. 2604d5caef5bSAndrii Nakryiko */ 2605d5caef5bSAndrii Nakryiko static int btf_dedup_compact_types(struct btf_dedup *d) 2606d5caef5bSAndrii Nakryiko { 2607d5caef5bSAndrii Nakryiko struct btf_type **new_types; 2608d5caef5bSAndrii Nakryiko __u32 next_type_id = 1; 2609d5caef5bSAndrii Nakryiko char *types_start, *p; 2610d5caef5bSAndrii Nakryiko int i, len; 2611d5caef5bSAndrii Nakryiko 2612d5caef5bSAndrii Nakryiko /* we are going to reuse hypot_map to store compaction remapping */ 2613d5caef5bSAndrii Nakryiko d->hypot_map[0] = 0; 2614d5caef5bSAndrii Nakryiko for (i = 1; i <= d->btf->nr_types; i++) 2615d5caef5bSAndrii Nakryiko d->hypot_map[i] = BTF_UNPROCESSED_ID; 2616d5caef5bSAndrii Nakryiko 2617d5caef5bSAndrii Nakryiko types_start = d->btf->nohdr_data + d->btf->hdr->type_off; 2618d5caef5bSAndrii Nakryiko p = types_start; 2619d5caef5bSAndrii Nakryiko 2620d5caef5bSAndrii Nakryiko for (i = 1; i <= d->btf->nr_types; i++) { 2621d5caef5bSAndrii Nakryiko if (d->map[i] != i) 2622d5caef5bSAndrii Nakryiko continue; 2623d5caef5bSAndrii Nakryiko 2624d5caef5bSAndrii Nakryiko len = btf_type_size(d->btf->types[i]); 2625d5caef5bSAndrii Nakryiko if (len < 0) 2626d5caef5bSAndrii Nakryiko return len; 2627d5caef5bSAndrii Nakryiko 2628d5caef5bSAndrii Nakryiko memmove(p, d->btf->types[i], len); 2629d5caef5bSAndrii Nakryiko d->hypot_map[i] = next_type_id; 2630d5caef5bSAndrii Nakryiko d->btf->types[next_type_id] = (struct btf_type *)p; 2631d5caef5bSAndrii Nakryiko p += len; 2632d5caef5bSAndrii Nakryiko next_type_id++; 2633d5caef5bSAndrii Nakryiko } 2634d5caef5bSAndrii Nakryiko 2635d5caef5bSAndrii Nakryiko /* shrink struct btf's internal types index and update btf_header */ 2636d5caef5bSAndrii Nakryiko d->btf->nr_types = next_type_id - 1; 2637d5caef5bSAndrii Nakryiko d->btf->types_size = d->btf->nr_types; 2638d5caef5bSAndrii Nakryiko d->btf->hdr->type_len = p - types_start; 2639d5caef5bSAndrii Nakryiko new_types = realloc(d->btf->types, 2640d5caef5bSAndrii Nakryiko (1 + d->btf->nr_types) * sizeof(struct btf_type *)); 2641d5caef5bSAndrii Nakryiko if (!new_types) 2642d5caef5bSAndrii Nakryiko return -ENOMEM; 2643d5caef5bSAndrii Nakryiko d->btf->types = new_types; 2644d5caef5bSAndrii Nakryiko 2645d5caef5bSAndrii Nakryiko /* make sure string section follows type information without gaps */ 2646d5caef5bSAndrii Nakryiko d->btf->hdr->str_off = p - (char *)d->btf->nohdr_data; 2647d5caef5bSAndrii Nakryiko memmove(p, d->btf->strings, d->btf->hdr->str_len); 2648d5caef5bSAndrii Nakryiko d->btf->strings = p; 2649d5caef5bSAndrii Nakryiko p += d->btf->hdr->str_len; 2650d5caef5bSAndrii Nakryiko 2651d5caef5bSAndrii Nakryiko d->btf->data_size = p - (char *)d->btf->data; 2652d5caef5bSAndrii Nakryiko return 0; 2653d5caef5bSAndrii Nakryiko } 2654d5caef5bSAndrii Nakryiko 2655d5caef5bSAndrii Nakryiko /* 2656d5caef5bSAndrii Nakryiko * Figure out final (deduplicated and compacted) type ID for provided original 2657d5caef5bSAndrii Nakryiko * `type_id` by first resolving it into corresponding canonical type ID and 2658d5caef5bSAndrii Nakryiko * then mapping it to a deduplicated type ID, stored in btf_dedup->hypot_map, 2659d5caef5bSAndrii Nakryiko * which is populated during compaction phase. 2660d5caef5bSAndrii Nakryiko */ 2661d5caef5bSAndrii Nakryiko static int btf_dedup_remap_type_id(struct btf_dedup *d, __u32 type_id) 2662d5caef5bSAndrii Nakryiko { 2663d5caef5bSAndrii Nakryiko __u32 resolved_type_id, new_type_id; 2664d5caef5bSAndrii Nakryiko 2665d5caef5bSAndrii Nakryiko resolved_type_id = resolve_type_id(d, type_id); 2666d5caef5bSAndrii Nakryiko new_type_id = d->hypot_map[resolved_type_id]; 26675aab392cSAndrii Nakryiko if (new_type_id > BTF_MAX_NR_TYPES) 2668d5caef5bSAndrii Nakryiko return -EINVAL; 2669d5caef5bSAndrii Nakryiko return new_type_id; 2670d5caef5bSAndrii Nakryiko } 2671d5caef5bSAndrii Nakryiko 2672d5caef5bSAndrii Nakryiko /* 2673d5caef5bSAndrii Nakryiko * Remap referenced type IDs into deduped type IDs. 2674d5caef5bSAndrii Nakryiko * 2675d5caef5bSAndrii Nakryiko * After BTF types are deduplicated and compacted, their final type IDs may 2676d5caef5bSAndrii Nakryiko * differ from original ones. The map from original to a corresponding 2677d5caef5bSAndrii Nakryiko * deduped type ID is stored in btf_dedup->hypot_map and is populated during 2678d5caef5bSAndrii Nakryiko * compaction phase. During remapping phase we are rewriting all type IDs 2679d5caef5bSAndrii Nakryiko * referenced from any BTF type (e.g., struct fields, func proto args, etc) to 2680d5caef5bSAndrii Nakryiko * their final deduped type IDs. 2681d5caef5bSAndrii Nakryiko */ 2682d5caef5bSAndrii Nakryiko static int btf_dedup_remap_type(struct btf_dedup *d, __u32 type_id) 2683d5caef5bSAndrii Nakryiko { 2684d5caef5bSAndrii Nakryiko struct btf_type *t = d->btf->types[type_id]; 2685d5caef5bSAndrii Nakryiko int i, r; 2686d5caef5bSAndrii Nakryiko 2687d5caef5bSAndrii Nakryiko switch (BTF_INFO_KIND(t->info)) { 2688d5caef5bSAndrii Nakryiko case BTF_KIND_INT: 2689d5caef5bSAndrii Nakryiko case BTF_KIND_ENUM: 2690d5caef5bSAndrii Nakryiko break; 2691d5caef5bSAndrii Nakryiko 2692d5caef5bSAndrii Nakryiko case BTF_KIND_FWD: 2693d5caef5bSAndrii Nakryiko case BTF_KIND_CONST: 2694d5caef5bSAndrii Nakryiko case BTF_KIND_VOLATILE: 2695d5caef5bSAndrii Nakryiko case BTF_KIND_RESTRICT: 2696d5caef5bSAndrii Nakryiko case BTF_KIND_PTR: 2697d5caef5bSAndrii Nakryiko case BTF_KIND_TYPEDEF: 2698d5caef5bSAndrii Nakryiko case BTF_KIND_FUNC: 2699d5caef5bSAndrii Nakryiko r = btf_dedup_remap_type_id(d, t->type); 2700d5caef5bSAndrii Nakryiko if (r < 0) 2701d5caef5bSAndrii Nakryiko return r; 2702d5caef5bSAndrii Nakryiko t->type = r; 2703d5caef5bSAndrii Nakryiko break; 2704d5caef5bSAndrii Nakryiko 2705d5caef5bSAndrii Nakryiko case BTF_KIND_ARRAY: { 2706d5caef5bSAndrii Nakryiko struct btf_array *arr_info = (struct btf_array *)(t + 1); 2707d5caef5bSAndrii Nakryiko 2708d5caef5bSAndrii Nakryiko r = btf_dedup_remap_type_id(d, arr_info->type); 2709d5caef5bSAndrii Nakryiko if (r < 0) 2710d5caef5bSAndrii Nakryiko return r; 2711d5caef5bSAndrii Nakryiko arr_info->type = r; 2712d5caef5bSAndrii Nakryiko r = btf_dedup_remap_type_id(d, arr_info->index_type); 2713d5caef5bSAndrii Nakryiko if (r < 0) 2714d5caef5bSAndrii Nakryiko return r; 2715d5caef5bSAndrii Nakryiko arr_info->index_type = r; 2716d5caef5bSAndrii Nakryiko break; 2717d5caef5bSAndrii Nakryiko } 2718d5caef5bSAndrii Nakryiko 2719d5caef5bSAndrii Nakryiko case BTF_KIND_STRUCT: 2720d5caef5bSAndrii Nakryiko case BTF_KIND_UNION: { 2721d5caef5bSAndrii Nakryiko struct btf_member *member = (struct btf_member *)(t + 1); 2722d5caef5bSAndrii Nakryiko __u16 vlen = BTF_INFO_VLEN(t->info); 2723d5caef5bSAndrii Nakryiko 2724d5caef5bSAndrii Nakryiko for (i = 0; i < vlen; i++) { 2725d5caef5bSAndrii Nakryiko r = btf_dedup_remap_type_id(d, member->type); 2726d5caef5bSAndrii Nakryiko if (r < 0) 2727d5caef5bSAndrii Nakryiko return r; 2728d5caef5bSAndrii Nakryiko member->type = r; 2729d5caef5bSAndrii Nakryiko member++; 2730d5caef5bSAndrii Nakryiko } 2731d5caef5bSAndrii Nakryiko break; 2732d5caef5bSAndrii Nakryiko } 2733d5caef5bSAndrii Nakryiko 2734d5caef5bSAndrii Nakryiko case BTF_KIND_FUNC_PROTO: { 2735d5caef5bSAndrii Nakryiko struct btf_param *param = (struct btf_param *)(t + 1); 2736d5caef5bSAndrii Nakryiko __u16 vlen = BTF_INFO_VLEN(t->info); 2737d5caef5bSAndrii Nakryiko 2738d5caef5bSAndrii Nakryiko r = btf_dedup_remap_type_id(d, t->type); 2739d5caef5bSAndrii Nakryiko if (r < 0) 2740d5caef5bSAndrii Nakryiko return r; 2741d5caef5bSAndrii Nakryiko t->type = r; 2742d5caef5bSAndrii Nakryiko 2743d5caef5bSAndrii Nakryiko for (i = 0; i < vlen; i++) { 2744d5caef5bSAndrii Nakryiko r = btf_dedup_remap_type_id(d, param->type); 2745d5caef5bSAndrii Nakryiko if (r < 0) 2746d5caef5bSAndrii Nakryiko return r; 2747d5caef5bSAndrii Nakryiko param->type = r; 2748d5caef5bSAndrii Nakryiko param++; 2749d5caef5bSAndrii Nakryiko } 2750d5caef5bSAndrii Nakryiko break; 2751d5caef5bSAndrii Nakryiko } 2752d5caef5bSAndrii Nakryiko 2753d5caef5bSAndrii Nakryiko default: 2754d5caef5bSAndrii Nakryiko return -EINVAL; 2755d5caef5bSAndrii Nakryiko } 2756d5caef5bSAndrii Nakryiko 2757d5caef5bSAndrii Nakryiko return 0; 2758d5caef5bSAndrii Nakryiko } 2759d5caef5bSAndrii Nakryiko 2760d5caef5bSAndrii Nakryiko static int btf_dedup_remap_types(struct btf_dedup *d) 2761d5caef5bSAndrii Nakryiko { 2762d5caef5bSAndrii Nakryiko int i, r; 2763d5caef5bSAndrii Nakryiko 2764d5caef5bSAndrii Nakryiko for (i = 1; i <= d->btf->nr_types; i++) { 2765d5caef5bSAndrii Nakryiko r = btf_dedup_remap_type(d, i); 2766d5caef5bSAndrii Nakryiko if (r < 0) 2767d5caef5bSAndrii Nakryiko return r; 2768d5caef5bSAndrii Nakryiko } 2769d5caef5bSAndrii Nakryiko return 0; 2770d5caef5bSAndrii Nakryiko } 2771