~hc/RK356X_SDK_RELEASE.git

..	..	@@ -1,222 +1,534 @@
1		-// SPDX-License-Identifier: LGPL-2.1
	1	+// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)
2	2	/* Copyright (c) 2018 Facebook */
3	3
	4	+#include <byteswap.h>
	5	+#include <endian.h>
	6	+#include <stdio.h>
4	7	#include <stdlib.h>
5	8	#include <string.h>
	9	+#include <fcntl.h>
6	10	#include <unistd.h>
7	11	#include <errno.h>
	12	+#include <sys/utsname.h>
	13	+#include <sys/param.h>
	14	+#include <sys/stat.h>
	15	+#include <linux/kernel.h>
8	16	#include <linux/err.h>
9	17	#include <linux/btf.h>
	18	+#include <gelf.h>
10	19	#include "btf.h"
11	20	#include "bpf.h"
	21	+#include "libbpf.h"
	22	+#include "libbpf_internal.h"
	23	+#include "hashmap.h"
12	24
13		-#define elog(fmt, ...) { if (err_log) err_log(fmt, ##__VA_ARGS__); }
14		-#define max(a, b) ((a) > (b) ? (a) : (b))
15		-#define min(a, b) ((a) < (b) ? (a) : (b))
16		-
17		-#define BTF_MAX_NR_TYPES 65535
18		-
19		-#define IS_MODIFIER(k) (((k) == BTF_KIND_TYPEDEF) \|\| \
20		- ((k) == BTF_KIND_VOLATILE) \|\| \
21		- ((k) == BTF_KIND_CONST) \|\| \
22		- ((k) == BTF_KIND_RESTRICT))
	25	+#define BTF_MAX_NR_TYPES 0x7fffffffU
	26	+#define BTF_MAX_STR_OFFSET 0x7fffffffU
23	27
24	28	static struct btf_type btf_void;
25	29
26	30	struct btf {
27		- union {
28		- struct btf_header *hdr;
29		- void *data;
30		- };
31		- struct btf_type **types;
32		- const char *strings;
33		- void *nohdr_data;
	31	+ /* raw BTF data in native endianness */
	32	+ void *raw_data;
	33	+ /* raw BTF data in non-native endianness */
	34	+ void *raw_data_swapped;
	35	+ __u32 raw_size;
	36	+ /* whether target endianness differs from the native one */
	37	+ bool swapped_endian;
	38	+
	39	+ /*
	40	+ * When BTF is loaded from an ELF or raw memory it is stored
	41	+ * in a contiguous memory block. The hdr, type_data, and, strs_data
	42	+ * point inside that memory region to their respective parts of BTF
	43	+ * representation:
	44	+ *
	45	+ * +--------------------------------+
	46	+ * \| Header \| Types \| Strings \|
	47	+ * +--------------------------------+
	48	+ * ^ ^ ^
	49	+ * \| \| \|
	50	+ * hdr \| \|
	51	+ * types_data-+ \|
	52	+ * strs_data------------+
	53	+ *
	54	+ * If BTF data is later modified, e.g., due to types added or
	55	+ * removed, BTF deduplication performed, etc, this contiguous
	56	+ * representation is broken up into three independently allocated
	57	+ * memory regions to be able to modify them independently.
	58	+ * raw_data is nulled out at that point, but can be later allocated
	59	+ * and cached again if user calls btf__get_raw_data(), at which point
	60	+ * raw_data will contain a contiguous copy of header, types, and
	61	+ * strings:
	62	+ *
	63	+ * +----------+ +---------+ +-----------+
	64	+ * \| Header \| \| Types \| \| Strings \|
	65	+ * +----------+ +---------+ +-----------+
	66	+ * ^ ^ ^
	67	+ * \| \| \|
	68	+ * hdr \| \|
	69	+ * types_data----+ \|
	70	+ * strs_data------------------+
	71	+ *
	72	+ * +----------+---------+-----------+
	73	+ * \| Header \| Types \| Strings \|
	74	+ * raw_data----->+----------+---------+-----------+
	75	+ */
	76	+ struct btf_header *hdr;
	77	+
	78	+ void *types_data;
	79	+ size_t types_data_cap; /* used size stored in hdr->type_len */
	80	+
	81	+ /* type ID to `struct btf_type ` lookup index /
	82	+ __u32 *type_offs;
	83	+ size_t type_offs_cap;
34	84	__u32 nr_types;
35		- __u32 types_size;
36		- __u32 data_size;
	85	+
	86	+ void *strs_data;
	87	+ size_t strs_data_cap; /* used size stored in hdr->str_len */
	88	+
	89	+ /* lookup index for each unique string in strings section */
	90	+ struct hashmap *strs_hash;
	91	+ /* whether strings are already deduplicated */
	92	+ bool strs_deduped;
	93	+ /* BTF object FD, if loaded into kernel */
37	94	int fd;
	95	+
	96	+ /* Pointer size (in bytes) for a target architecture of this BTF */
	97	+ int ptr_sz;
38	98	};
39	99
40		-static int btf_add_type(struct btf btf, struct btf_type t)
	100	+static inline __u64 ptr_to_u64(const void *ptr)
41	101	{
42		- if (btf->types_size - btf->nr_types < 2) {
43		- struct btf_type **new_types;
44		- __u32 expand_by, new_size;
	102	+ return (__u64) (unsigned long) ptr;
	103	+}
45	104
46		- if (btf->types_size == BTF_MAX_NR_TYPES)
47		- return -E2BIG;
	105	+/* Ensure given dynamically allocated memory region pointed to by data with
	106	+ * capacity of cap_cnt elements each taking elem_sz bytes has enough
	107	+ * memory to accomodate add_cnt new elements, assuming cur_cnt elements
	108	+ * are already used. At most max_cnt elements can be ever allocated.
	109	+ * If necessary, memory is reallocated and all existing data is copied over,
	110	+ * new pointer to the memory region is stored at *data, new memory region
	111	+ * capacity (in number of elements) is stored in *cap.
	112	+ * On success, memory pointer to the beginning of unused memory is returned.
	113	+ * On error, NULL is returned.
	114	+ */
	115	+void btf_add_mem(void data, size_t cap_cnt, size_t elem_sz,
	116	+ size_t cur_cnt, size_t max_cnt, size_t add_cnt)
	117	+{
	118	+ size_t new_cnt;
	119	+ void *new_data;
48	120
49		- expand_by = max(btf->types_size >> 2, 16);
50		- new_size = min(BTF_MAX_NR_TYPES, btf->types_size + expand_by);
	121	+ if (cur_cnt + add_cnt <= *cap_cnt)
	122	+ return data + cur_cnt elem_sz;
51	123
52		- new_types = realloc(btf->types, sizeof(new_types) new_size);
53		- if (!new_types)
54		- return -ENOMEM;
	124	+ /* requested more than the set limit */
	125	+ if (cur_cnt + add_cnt > max_cnt)
	126	+ return NULL;
55	127
56		- if (btf->nr_types == 0)
57		- new_types[0] = &btf_void;
	128	+ new_cnt = *cap_cnt;
	129	+ new_cnt += new_cnt / 4; /* expand by 25% */
	130	+ if (new_cnt < 16) /* but at least 16 elements */
	131	+ new_cnt = 16;
	132	+ if (new_cnt > max_cnt) /* but not exceeding a set limit */
	133	+ new_cnt = max_cnt;
	134	+ if (new_cnt < cur_cnt + add_cnt) /* also ensure we have enough memory */
	135	+ new_cnt = cur_cnt + add_cnt;
58	136
59		- btf->types = new_types;
60		- btf->types_size = new_size;
61		- }
	137	+ new_data = libbpf_reallocarray(*data, new_cnt, elem_sz);
	138	+ if (!new_data)
	139	+ return NULL;
62	140
63		- btf->types[++(btf->nr_types)] = t;
	141	+ /* zero out newly allocated portion of memory */
	142	+ memset(new_data + (cap_cnt) elem_sz, 0, (new_cnt - cap_cnt) elem_sz);
	143	+
	144	+ *data = new_data;
	145	+ *cap_cnt = new_cnt;
	146	+ return new_data + cur_cnt * elem_sz;
	147	+}
	148	+
	149	+/* Ensure given dynamically allocated memory region has enough allocated space
	150	+ * to accommodate need_cnt elements of size elem_sz bytes each
	151	+ */
	152	+int btf_ensure_mem(void *data, size_t cap_cnt, size_t elem_sz, size_t need_cnt)
	153	+{
	154	+ void *p;
	155	+
	156	+ if (need_cnt <= *cap_cnt)
	157	+ return 0;
	158	+
	159	+ p = btf_add_mem(data, cap_cnt, elem_sz, cap_cnt, SIZE_MAX, need_cnt - cap_cnt);
	160	+ if (!p)
	161	+ return -ENOMEM;
64	162
65	163	return 0;
66	164	}
67	165
68		-static int btf_parse_hdr(struct btf *btf, btf_print_fn_t err_log)
	166	+static int btf_add_type_idx_entry(struct btf *btf, __u32 type_off)
69	167	{
70		- const struct btf_header *hdr = btf->hdr;
71		- __u32 meta_left;
	168	+ __u32 *p;
72	169
73		- if (btf->data_size < sizeof(struct btf_header)) {
74		- elog("BTF header not found\n");
75		- return -EINVAL;
76		- }
	170	+ p = btf_add_mem((void **)&btf->type_offs, &btf->type_offs_cap, sizeof(__u32),
	171	+ btf->nr_types + 1, BTF_MAX_NR_TYPES, 1);
	172	+ if (!p)
	173	+ return -ENOMEM;
77	174
78		- if (hdr->magic != BTF_MAGIC) {
79		- elog("Invalid BTF magic:%x\n", hdr->magic);
80		- return -EINVAL;
81		- }
82		-
83		- if (hdr->version != BTF_VERSION) {
84		- elog("Unsupported BTF version:%u\n", hdr->version);
85		- return -ENOTSUP;
86		- }
87		-
88		- if (hdr->flags) {
89		- elog("Unsupported BTF flags:%x\n", hdr->flags);
90		- return -ENOTSUP;
91		- }
92		-
93		- meta_left = btf->data_size - sizeof(*hdr);
94		- if (!meta_left) {
95		- elog("BTF has no data\n");
96		- return -EINVAL;
97		- }
98		-
99		- if (meta_left < hdr->type_off) {
100		- elog("Invalid BTF type section offset:%u\n", hdr->type_off);
101		- return -EINVAL;
102		- }
103		-
104		- if (meta_left < hdr->str_off) {
105		- elog("Invalid BTF string section offset:%u\n", hdr->str_off);
106		- return -EINVAL;
107		- }
108		-
109		- if (hdr->type_off >= hdr->str_off) {
110		- elog("BTF type section offset >= string section offset. No type?\n");
111		- return -EINVAL;
112		- }
113		-
114		- if (hdr->type_off & 0x02) {
115		- elog("BTF type section is not aligned to 4 bytes\n");
116		- return -EINVAL;
117		- }
118		-
119		- btf->nohdr_data = btf->hdr + 1;
120		-
	175	+ *p = type_off;
121	176	return 0;
122	177	}
123	178
124		-static int btf_parse_str_sec(struct btf *btf, btf_print_fn_t err_log)
	179	+static void btf_bswap_hdr(struct btf_header *h)
125	180	{
126		- const struct btf_header *hdr = btf->hdr;
127		- const char *start = btf->nohdr_data + hdr->str_off;
128		- const char *end = start + btf->hdr->str_len;
129		-
130		- if (!hdr->str_len \|\| hdr->str_len - 1 > BTF_MAX_NAME_OFFSET \|\|
131		- start[0] \|\| end[-1]) {
132		- elog("Invalid BTF string section\n");
133		- return -EINVAL;
134		- }
135		-
136		- btf->strings = start;
137		-
138		- return 0;
	181	+ h->magic = bswap_16(h->magic);
	182	+ h->hdr_len = bswap_32(h->hdr_len);
	183	+ h->type_off = bswap_32(h->type_off);
	184	+ h->type_len = bswap_32(h->type_len);
	185	+ h->str_off = bswap_32(h->str_off);
	186	+ h->str_len = bswap_32(h->str_len);
139	187	}
140	188
141		-static int btf_parse_type_sec(struct btf *btf, btf_print_fn_t err_log)
	189	+static int btf_parse_hdr(struct btf *btf)
142	190	{
143	191	struct btf_header *hdr = btf->hdr;
144		- void *nohdr_data = btf->nohdr_data;
145		- void *next_type = nohdr_data + hdr->type_off;
146		- void *end_type = nohdr_data + hdr->str_off;
	192	+ __u32 meta_left;
147	193
148		- while (next_type < end_type) {
149		- struct btf_type *t = next_type;
150		- __u16 vlen = BTF_INFO_VLEN(t->info);
151		- int err;
	194	+ if (btf->raw_size < sizeof(struct btf_header)) {
	195	+ pr_debug("BTF header not found\n");
	196	+ return -EINVAL;
	197	+ }
152	198
153		- next_type += sizeof(*t);
154		- switch (BTF_INFO_KIND(t->info)) {
155		- case BTF_KIND_INT:
156		- next_type += sizeof(int);
157		- break;
158		- case BTF_KIND_ARRAY:
159		- next_type += sizeof(struct btf_array);
160		- break;
161		- case BTF_KIND_STRUCT:
162		- case BTF_KIND_UNION:
163		- next_type += vlen * sizeof(struct btf_member);
164		- break;
165		- case BTF_KIND_ENUM:
166		- next_type += vlen * sizeof(struct btf_enum);
167		- break;
168		- case BTF_KIND_TYPEDEF:
169		- case BTF_KIND_PTR:
170		- case BTF_KIND_FWD:
171		- case BTF_KIND_VOLATILE:
172		- case BTF_KIND_CONST:
173		- case BTF_KIND_RESTRICT:
174		- break;
175		- default:
176		- elog("Unsupported BTF_KIND:%u\n",
177		- BTF_INFO_KIND(t->info));
	199	+ if (hdr->magic == bswap_16(BTF_MAGIC)) {
	200	+ btf->swapped_endian = true;
	201	+ if (bswap_32(hdr->hdr_len) != sizeof(struct btf_header)) {
	202	+ pr_warn("Can't load BTF with non-native endianness due to unsupported header length %u\n",
	203	+ bswap_32(hdr->hdr_len));
	204	+ return -ENOTSUP;
	205	+ }
	206	+ btf_bswap_hdr(hdr);
	207	+ } else if (hdr->magic != BTF_MAGIC) {
	208	+ pr_debug("Invalid BTF magic: %x\n", hdr->magic);
	209	+ return -EINVAL;
	210	+ }
	211	+
	212	+ if (btf->raw_size < hdr->hdr_len) {
	213	+ pr_debug("BTF header len %u larger than data size %u\n",
	214	+ hdr->hdr_len, btf->raw_size);
	215	+ return -EINVAL;
	216	+ }
	217	+
	218	+ meta_left = btf->raw_size - hdr->hdr_len;
	219	+ if (meta_left < (long long)hdr->str_off + hdr->str_len) {
	220	+ pr_debug("Invalid BTF total size: %u\n", btf->raw_size);
	221	+ return -EINVAL;
	222	+ }
	223	+
	224	+ if ((long long)hdr->type_off + hdr->type_len > hdr->str_off) {
	225	+ pr_debug("Invalid BTF data sections layout: type data at %u + %u, strings data at %u + %u\n",
	226	+ hdr->type_off, hdr->type_len, hdr->str_off, hdr->str_len);
	227	+ return -EINVAL;
	228	+ }
	229	+
	230	+ if (hdr->type_off % 4) {
	231	+ pr_debug("BTF type section is not aligned to 4 bytes\n");
	232	+ return -EINVAL;
	233	+ }
	234	+
	235	+ return 0;
	236	+}
	237	+
	238	+static int btf_parse_str_sec(struct btf *btf)
	239	+{
	240	+ const struct btf_header *hdr = btf->hdr;
	241	+ const char *start = btf->strs_data;
	242	+ const char *end = start + btf->hdr->str_len;
	243	+
	244	+ if (!hdr->str_len \|\| hdr->str_len - 1 > BTF_MAX_STR_OFFSET \|\|
	245	+ start[0] \|\| end[-1]) {
	246	+ pr_debug("Invalid BTF string section\n");
	247	+ return -EINVAL;
	248	+ }
	249	+
	250	+ return 0;
	251	+}
	252	+
	253	+static int btf_type_size(const struct btf_type *t)
	254	+{
	255	+ const int base_size = sizeof(struct btf_type);
	256	+ __u16 vlen = btf_vlen(t);
	257	+
	258	+ switch (btf_kind(t)) {
	259	+ case BTF_KIND_FWD:
	260	+ case BTF_KIND_CONST:
	261	+ case BTF_KIND_VOLATILE:
	262	+ case BTF_KIND_RESTRICT:
	263	+ case BTF_KIND_PTR:
	264	+ case BTF_KIND_TYPEDEF:
	265	+ case BTF_KIND_FUNC:
	266	+ return base_size;
	267	+ case BTF_KIND_INT:
	268	+ return base_size + sizeof(__u32);
	269	+ case BTF_KIND_ENUM:
	270	+ return base_size + vlen * sizeof(struct btf_enum);
	271	+ case BTF_KIND_ARRAY:
	272	+ return base_size + sizeof(struct btf_array);
	273	+ case BTF_KIND_STRUCT:
	274	+ case BTF_KIND_UNION:
	275	+ return base_size + vlen * sizeof(struct btf_member);
	276	+ case BTF_KIND_FUNC_PROTO:
	277	+ return base_size + vlen * sizeof(struct btf_param);
	278	+ case BTF_KIND_VAR:
	279	+ return base_size + sizeof(struct btf_var);
	280	+ case BTF_KIND_DATASEC:
	281	+ return base_size + vlen * sizeof(struct btf_var_secinfo);
	282	+ default:
	283	+ pr_debug("Unsupported BTF_KIND:%u\n", btf_kind(t));
	284	+ return -EINVAL;
	285	+ }
	286	+}
	287	+
	288	+static void btf_bswap_type_base(struct btf_type *t)
	289	+{
	290	+ t->name_off = bswap_32(t->name_off);
	291	+ t->info = bswap_32(t->info);
	292	+ t->type = bswap_32(t->type);
	293	+}
	294	+
	295	+static int btf_bswap_type_rest(struct btf_type *t)
	296	+{
	297	+ struct btf_var_secinfo *v;
	298	+ struct btf_member *m;
	299	+ struct btf_array *a;
	300	+ struct btf_param *p;
	301	+ struct btf_enum *e;
	302	+ __u16 vlen = btf_vlen(t);
	303	+ int i;
	304	+
	305	+ switch (btf_kind(t)) {
	306	+ case BTF_KIND_FWD:
	307	+ case BTF_KIND_CONST:
	308	+ case BTF_KIND_VOLATILE:
	309	+ case BTF_KIND_RESTRICT:
	310	+ case BTF_KIND_PTR:
	311	+ case BTF_KIND_TYPEDEF:
	312	+ case BTF_KIND_FUNC:
	313	+ return 0;
	314	+ case BTF_KIND_INT:
	315	+ (__u32 )(t + 1) = bswap_32((__u32 )(t + 1));
	316	+ return 0;
	317	+ case BTF_KIND_ENUM:
	318	+ for (i = 0, e = btf_enum(t); i < vlen; i++, e++) {
	319	+ e->name_off = bswap_32(e->name_off);
	320	+ e->val = bswap_32(e->val);
	321	+ }
	322	+ return 0;
	323	+ case BTF_KIND_ARRAY:
	324	+ a = btf_array(t);
	325	+ a->type = bswap_32(a->type);
	326	+ a->index_type = bswap_32(a->index_type);
	327	+ a->nelems = bswap_32(a->nelems);
	328	+ return 0;
	329	+ case BTF_KIND_STRUCT:
	330	+ case BTF_KIND_UNION:
	331	+ for (i = 0, m = btf_members(t); i < vlen; i++, m++) {
	332	+ m->name_off = bswap_32(m->name_off);
	333	+ m->type = bswap_32(m->type);
	334	+ m->offset = bswap_32(m->offset);
	335	+ }
	336	+ return 0;
	337	+ case BTF_KIND_FUNC_PROTO:
	338	+ for (i = 0, p = btf_params(t); i < vlen; i++, p++) {
	339	+ p->name_off = bswap_32(p->name_off);
	340	+ p->type = bswap_32(p->type);
	341	+ }
	342	+ return 0;
	343	+ case BTF_KIND_VAR:
	344	+ btf_var(t)->linkage = bswap_32(btf_var(t)->linkage);
	345	+ return 0;
	346	+ case BTF_KIND_DATASEC:
	347	+ for (i = 0, v = btf_var_secinfos(t); i < vlen; i++, v++) {
	348	+ v->type = bswap_32(v->type);
	349	+ v->offset = bswap_32(v->offset);
	350	+ v->size = bswap_32(v->size);
	351	+ }
	352	+ return 0;
	353	+ default:
	354	+ pr_debug("Unsupported BTF_KIND:%u\n", btf_kind(t));
	355	+ return -EINVAL;
	356	+ }
	357	+}
	358	+
	359	+static int btf_parse_type_sec(struct btf *btf)
	360	+{
	361	+ struct btf_header *hdr = btf->hdr;
	362	+ void *next_type = btf->types_data;
	363	+ void *end_type = next_type + hdr->type_len;
	364	+ int err, i = 0, type_size;
	365	+
	366	+ /* VOID (type_id == 0) is specially handled by btf__get_type_by_id(),
	367	+ * so ensure we can never properly use its offset from index by
	368	+ * setting it to a large value
	369	+ */
	370	+ err = btf_add_type_idx_entry(btf, UINT_MAX);
	371	+ if (err)
	372	+ return err;
	373	+
	374	+ while (next_type + sizeof(struct btf_type) <= end_type) {
	375	+ i++;
	376	+
	377	+ if (btf->swapped_endian)
	378	+ btf_bswap_type_base(next_type);
	379	+
	380	+ type_size = btf_type_size(next_type);
	381	+ if (type_size < 0)
	382	+ return type_size;
	383	+ if (next_type + type_size > end_type) {
	384	+ pr_warn("BTF type [%d] is malformed\n", i);
178	385	return -EINVAL;
179	386	}
180	387
181		- err = btf_add_type(btf, t);
	388	+ if (btf->swapped_endian && btf_bswap_type_rest(next_type))
	389	+ return -EINVAL;
	390	+
	391	+ err = btf_add_type_idx_entry(btf, next_type - btf->types_data);
182	392	if (err)
183	393	return err;
	394	+
	395	+ next_type += type_size;
	396	+ btf->nr_types++;
	397	+ }
	398	+
	399	+ if (next_type != end_type) {
	400	+ pr_warn("BTF types data is malformed\n");
	401	+ return -EINVAL;
184	402	}
185	403
186	404	return 0;
	405	+}
	406	+
	407	+__u32 btf__get_nr_types(const struct btf *btf)
	408	+{
	409	+ return btf->nr_types;
	410	+}
	411	+
	412	+/* internal helper returning non-const pointer to a type */
	413	+static struct btf_type btf_type_by_id(struct btf btf, __u32 type_id)
	414	+{
	415	+ if (type_id == 0)
	416	+ return &btf_void;
	417	+
	418	+ return btf->types_data + btf->type_offs[type_id];
187	419	}
188	420
189	421	const struct btf_type btf__type_by_id(const struct btf btf, __u32 type_id)
190	422	{
191	423	if (type_id > btf->nr_types)
192	424	return NULL;
	425	+ return btf_type_by_id((struct btf *)btf, type_id);
	426	+}
193	427
194		- return btf->types[type_id];
	428	+static int determine_ptr_size(const struct btf *btf)
	429	+{
	430	+ const struct btf_type *t;
	431	+ const char *name;
	432	+ int i;
	433	+
	434	+ for (i = 1; i <= btf->nr_types; i++) {
	435	+ t = btf__type_by_id(btf, i);
	436	+ if (!btf_is_int(t))
	437	+ continue;
	438	+
	439	+ name = btf__name_by_offset(btf, t->name_off);
	440	+ if (!name)
	441	+ continue;
	442	+
	443	+ if (strcmp(name, "long int") == 0 \|\|
	444	+ strcmp(name, "long unsigned int") == 0) {
	445	+ if (t->size != 4 && t->size != 8)
	446	+ continue;
	447	+ return t->size;
	448	+ }
	449	+ }
	450	+
	451	+ return -1;
	452	+}
	453	+
	454	+static size_t btf_ptr_sz(const struct btf *btf)
	455	+{
	456	+ if (!btf->ptr_sz)
	457	+ ((struct btf *)btf)->ptr_sz = determine_ptr_size(btf);
	458	+ return btf->ptr_sz < 0 ? sizeof(void *) : btf->ptr_sz;
	459	+}
	460	+
	461	+/* Return pointer size this BTF instance assumes. The size is heuristically
	462	+ * determined by looking for 'long' or 'unsigned long' integer type and
	463	+ * recording its size in bytes. If BTF type information doesn't have any such
	464	+ * type, this function returns 0. In the latter case, native architecture's
	465	+ * pointer size is assumed, so will be either 4 or 8, depending on
	466	+ * architecture that libbpf was compiled for. It's possible to override
	467	+ * guessed value by using btf__set_pointer_size() API.
	468	+ */
	469	+size_t btf__pointer_size(const struct btf *btf)
	470	+{
	471	+ if (!btf->ptr_sz)
	472	+ ((struct btf *)btf)->ptr_sz = determine_ptr_size(btf);
	473	+
	474	+ if (btf->ptr_sz < 0)
	475	+ /* not enough BTF type info to guess */
	476	+ return 0;
	477	+
	478	+ return btf->ptr_sz;
	479	+}
	480	+
	481	+/* Override or set pointer size in bytes. Only values of 4 and 8 are
	482	+ * supported.
	483	+ */
	484	+int btf__set_pointer_size(struct btf *btf, size_t ptr_sz)
	485	+{
	486	+ if (ptr_sz != 4 && ptr_sz != 8)
	487	+ return -EINVAL;
	488	+ btf->ptr_sz = ptr_sz;
	489	+ return 0;
	490	+}
	491	+
	492	+static bool is_host_big_endian(void)
	493	+{
	494	+#if __BYTE_ORDER == __LITTLE_ENDIAN
	495	+ return false;
	496	+#elif __BYTE_ORDER == __BIG_ENDIAN
	497	+ return true;
	498	+#else
	499	+# error "Unrecognized __BYTE_ORDER__"
	500	+#endif
	501	+}
	502	+
	503	+enum btf_endianness btf__endianness(const struct btf *btf)
	504	+{
	505	+ if (is_host_big_endian())
	506	+ return btf->swapped_endian ? BTF_LITTLE_ENDIAN : BTF_BIG_ENDIAN;
	507	+ else
	508	+ return btf->swapped_endian ? BTF_BIG_ENDIAN : BTF_LITTLE_ENDIAN;
	509	+}
	510	+
	511	+int btf__set_endianness(struct btf *btf, enum btf_endianness endian)
	512	+{
	513	+ if (endian != BTF_LITTLE_ENDIAN && endian != BTF_BIG_ENDIAN)
	514	+ return -EINVAL;
	515	+
	516	+ btf->swapped_endian = is_host_big_endian() != (endian == BTF_BIG_ENDIAN);
	517	+ if (!btf->swapped_endian) {
	518	+ free(btf->raw_data_swapped);
	519	+ btf->raw_data_swapped = NULL;
	520	+ }
	521	+ return 0;
195	522	}
196	523
197	524	static bool btf_type_is_void(const struct btf_type *t)
198	525	{
199		- return t == &btf_void \|\| BTF_INFO_KIND(t->info) == BTF_KIND_FWD;
	526	+ return t == &btf_void \|\| btf_is_fwd(t);
200	527	}
201	528
202	529	static bool btf_type_is_void_or_null(const struct btf_type *t)
203	530	{
204	531	return !t \|\| btf_type_is_void(t);
205		-}
206		-
207		-static __s64 btf_type_size(const struct btf_type *t)
208		-{
209		- switch (BTF_INFO_KIND(t->info)) {
210		- case BTF_KIND_INT:
211		- case BTF_KIND_STRUCT:
212		- case BTF_KIND_UNION:
213		- case BTF_KIND_ENUM:
214		- return t->size;
215		- case BTF_KIND_PTR:
216		- return sizeof(void *);
217		- default:
218		- return -EINVAL;
219		- }
220	532	}
221	533
222	534	#define MAX_RESOLVE_DEPTH 32
..	..	@@ -232,19 +544,26 @@
232	544	t = btf__type_by_id(btf, type_id);
233	545	for (i = 0; i < MAX_RESOLVE_DEPTH && !btf_type_is_void_or_null(t);
234	546	i++) {
235		- size = btf_type_size(t);
236		- if (size >= 0)
237		- break;
238		-
239		- switch (BTF_INFO_KIND(t->info)) {
	547	+ switch (btf_kind(t)) {
	548	+ case BTF_KIND_INT:
	549	+ case BTF_KIND_STRUCT:
	550	+ case BTF_KIND_UNION:
	551	+ case BTF_KIND_ENUM:
	552	+ case BTF_KIND_DATASEC:
	553	+ size = t->size;
	554	+ goto done;
	555	+ case BTF_KIND_PTR:
	556	+ size = btf_ptr_sz(btf);
	557	+ goto done;
240	558	case BTF_KIND_TYPEDEF:
241	559	case BTF_KIND_VOLATILE:
242	560	case BTF_KIND_CONST:
243	561	case BTF_KIND_RESTRICT:
	562	+ case BTF_KIND_VAR:
244	563	type_id = t->type;
245	564	break;
246	565	case BTF_KIND_ARRAY:
247		- array = (const struct btf_array *)(t + 1);
	566	+ array = btf_array(t);
248	567	if (nelems && array->nelems > UINT32_MAX / nelems)
249	568	return -E2BIG;
250	569	nelems *= array->nelems;
..	..	@@ -257,13 +576,52 @@
257	576	t = btf__type_by_id(btf, type_id);
258	577	}
259	578
	579	+done:
260	580	if (size < 0)
261	581	return -EINVAL;
262		-
263	582	if (nelems && size > UINT32_MAX / nelems)
264	583	return -E2BIG;
265	584
266	585	return nelems * size;
	586	+}
	587	+
	588	+int btf__align_of(const struct btf *btf, __u32 id)
	589	+{
	590	+ const struct btf_type *t = btf__type_by_id(btf, id);
	591	+ __u16 kind = btf_kind(t);
	592	+
	593	+ switch (kind) {
	594	+ case BTF_KIND_INT:
	595	+ case BTF_KIND_ENUM:
	596	+ return min(btf_ptr_sz(btf), (size_t)t->size);
	597	+ case BTF_KIND_PTR:
	598	+ return btf_ptr_sz(btf);
	599	+ case BTF_KIND_TYPEDEF:
	600	+ case BTF_KIND_VOLATILE:
	601	+ case BTF_KIND_CONST:
	602	+ case BTF_KIND_RESTRICT:
	603	+ return btf__align_of(btf, t->type);
	604	+ case BTF_KIND_ARRAY:
	605	+ return btf__align_of(btf, btf_array(t)->type);
	606	+ case BTF_KIND_STRUCT:
	607	+ case BTF_KIND_UNION: {
	608	+ const struct btf_member *m = btf_members(t);
	609	+ __u16 vlen = btf_vlen(t);
	610	+ int i, max_align = 1, align;
	611	+
	612	+ for (i = 0; i < vlen; i++, m++) {
	613	+ align = btf__align_of(btf, m->type);
	614	+ if (align <= 0)
	615	+ return align;
	616	+ max_align = max(max_align, align);
	617	+ }
	618	+
	619	+ return max_align;
	620	+ }
	621	+ default:
	622	+ pr_warn("unsupported BTF_KIND:%u\n", btf_kind(t));
	623	+ return 0;
	624	+ }
267	625	}
268	626
269	627	int btf__resolve_type(const struct btf *btf, __u32 type_id)
..	..	@@ -274,7 +632,7 @@
274	632	t = btf__type_by_id(btf, type_id);
275	633	while (depth < MAX_RESOLVE_DEPTH &&
276	634	!btf_type_is_void_or_null(t) &&
277		- IS_MODIFIER(BTF_INFO_KIND(t->info))) {
	635	+ (btf_is_mod(t) \|\| btf_is_typedef(t) \|\| btf_is_var(t))) {
278	636	type_id = t->type;
279	637	t = btf__type_by_id(btf, type_id);
280	638	depth++;
..	..	@@ -294,7 +652,7 @@
294	652	return 0;
295	653
296	654	for (i = 1; i <= btf->nr_types; i++) {
297		- const struct btf_type *t = btf->types[i];
	655	+ const struct btf_type *t = btf__type_by_id(btf, i);
298	656	const char *name = btf__name_by_offset(btf, t->name_off);
299	657
300	658	if (name && !strcmp(type_name, name))
..	..	@@ -304,23 +662,92 @@
304	662	return -ENOENT;
305	663	}
306	664
	665	+__s32 btf__find_by_name_kind(const struct btf btf, const char type_name,
	666	+ __u32 kind)
	667	+{
	668	+ __u32 i;
	669	+
	670	+ if (kind == BTF_KIND_UNKN \|\| !strcmp(type_name, "void"))
	671	+ return 0;
	672	+
	673	+ for (i = 1; i <= btf->nr_types; i++) {
	674	+ const struct btf_type *t = btf__type_by_id(btf, i);
	675	+ const char *name;
	676	+
	677	+ if (btf_kind(t) != kind)
	678	+ continue;
	679	+ name = btf__name_by_offset(btf, t->name_off);
	680	+ if (name && !strcmp(type_name, name))
	681	+ return i;
	682	+ }
	683	+
	684	+ return -ENOENT;
	685	+}
	686	+
	687	+static bool btf_is_modifiable(const struct btf *btf)
	688	+{
	689	+ return (void *)btf->hdr != btf->raw_data;
	690	+}
	691	+
307	692	void btf__free(struct btf *btf)
308	693	{
309		- if (!btf)
	694	+ if (IS_ERR_OR_NULL(btf))
310	695	return;
311	696
312		- if (btf->fd != -1)
	697	+ if (btf->fd >= 0)
313	698	close(btf->fd);
314	699
315		- free(btf->data);
316		- free(btf->types);
	700	+ if (btf_is_modifiable(btf)) {
	701	+ /* if BTF was modified after loading, it will have a split
	702	+ * in-memory representation for header, types, and strings
	703	+ * sections, so we need to free all of them individually. It
	704	+ * might still have a cached contiguous raw data present,
	705	+ * which will be unconditionally freed below.
	706	+ */
	707	+ free(btf->hdr);
	708	+ free(btf->types_data);
	709	+ free(btf->strs_data);
	710	+ }
	711	+ free(btf->raw_data);
	712	+ free(btf->raw_data_swapped);
	713	+ free(btf->type_offs);
317	714	free(btf);
318	715	}
319	716
320		-struct btf btf__new(__u8 data, __u32 size, btf_print_fn_t err_log)
	717	+struct btf *btf__new_empty(void)
321	718	{
322		- __u32 log_buf_size = 0;
323		- char *log_buf = NULL;
	719	+ struct btf *btf;
	720	+
	721	+ btf = calloc(1, sizeof(*btf));
	722	+ if (!btf)
	723	+ return ERR_PTR(-ENOMEM);
	724	+
	725	+ btf->fd = -1;
	726	+ btf->ptr_sz = sizeof(void *);
	727	+ btf->swapped_endian = false;
	728	+
	729	+ /* +1 for empty string at offset 0 */
	730	+ btf->raw_size = sizeof(struct btf_header) + 1;
	731	+ btf->raw_data = calloc(1, btf->raw_size);
	732	+ if (!btf->raw_data) {
	733	+ free(btf);
	734	+ return ERR_PTR(-ENOMEM);
	735	+ }
	736	+
	737	+ btf->hdr = btf->raw_data;
	738	+ btf->hdr->hdr_len = sizeof(struct btf_header);
	739	+ btf->hdr->magic = BTF_MAGIC;
	740	+ btf->hdr->version = BTF_VERSION;
	741	+
	742	+ btf->types_data = btf->raw_data + btf->hdr->hdr_len;
	743	+ btf->strs_data = btf->raw_data + btf->hdr->hdr_len;
	744	+ btf->hdr->str_len = 1; /* empty string at offset 0 */
	745	+
	746	+ return btf;
	747	+}
	748	+
	749	+struct btf btf__new(const void data, __u32 size)
	750	+{
324	751	struct btf *btf;
325	752	int err;
326	753
..	..	@@ -328,51 +755,30 @@
328	755	if (!btf)
329	756	return ERR_PTR(-ENOMEM);
330	757
331		- btf->fd = -1;
332		-
333		- if (err_log) {
334		- log_buf = malloc(BPF_LOG_BUF_SIZE);
335		- if (!log_buf) {
336		- err = -ENOMEM;
337		- goto done;
338		- }
339		- *log_buf = 0;
340		- log_buf_size = BPF_LOG_BUF_SIZE;
341		- }
342		-
343		- btf->data = malloc(size);
344		- if (!btf->data) {
	758	+ btf->raw_data = malloc(size);
	759	+ if (!btf->raw_data) {
345	760	err = -ENOMEM;
346	761	goto done;
347	762	}
	763	+ memcpy(btf->raw_data, data, size);
	764	+ btf->raw_size = size;
348	765
349		- memcpy(btf->data, data, size);
350		- btf->data_size = size;
351		-
352		- btf->fd = bpf_load_btf(btf->data, btf->data_size,
353		- log_buf, log_buf_size, false);
354		-
355		- if (btf->fd == -1) {
356		- err = -errno;
357		- elog("Error loading BTF: %s(%d)\n", strerror(errno), errno);
358		- if (log_buf && *log_buf)
359		- elog("%s\n", log_buf);
360		- goto done;
361		- }
362		-
363		- err = btf_parse_hdr(btf, err_log);
	766	+ btf->hdr = btf->raw_data;
	767	+ err = btf_parse_hdr(btf);
364	768	if (err)
365	769	goto done;
366	770
367		- err = btf_parse_str_sec(btf, err_log);
	771	+ btf->strs_data = btf->raw_data + btf->hdr->hdr_len + btf->hdr->str_off;
	772	+ btf->types_data = btf->raw_data + btf->hdr->hdr_len + btf->hdr->type_off;
	773	+
	774	+ err = btf_parse_str_sec(btf);
	775	+ err = err ?: btf_parse_type_sec(btf);
368	776	if (err)
369	777	goto done;
370	778
371		- err = btf_parse_type_sec(btf, err_log);
	779	+ btf->fd = -1;
372	780
373	781	done:
374		- free(log_buf);
375		-
376	782	if (err) {
377	783	btf__free(btf);
378	784	return ERR_PTR(err);
..	..	@@ -381,15 +787,3685 @@
381	787	return btf;
382	788	}
383	789
	790	+struct btf btf__parse_elf(const char path, struct btf_ext **btf_ext)
	791	+{
	792	+ Elf_Data btf_data = NULL, btf_ext_data = NULL;
	793	+ int err = 0, fd = -1, idx = 0;
	794	+ struct btf *btf = NULL;
	795	+ Elf_Scn *scn = NULL;
	796	+ Elf *elf = NULL;
	797	+ GElf_Ehdr ehdr;
	798	+
	799	+ if (elf_version(EV_CURRENT) == EV_NONE) {
	800	+ pr_warn("failed to init libelf for %s\n", path);
	801	+ return ERR_PTR(-LIBBPF_ERRNO__LIBELF);
	802	+ }
	803	+
	804	+ fd = open(path, O_RDONLY);
	805	+ if (fd < 0) {
	806	+ err = -errno;
	807	+ pr_warn("failed to open %s: %s\n", path, strerror(errno));
	808	+ return ERR_PTR(err);
	809	+ }
	810	+
	811	+ err = -LIBBPF_ERRNO__FORMAT;
	812	+
	813	+ elf = elf_begin(fd, ELF_C_READ, NULL);
	814	+ if (!elf) {
	815	+ pr_warn("failed to open %s as ELF file\n", path);
	816	+ goto done;
	817	+ }
	818	+ if (!gelf_getehdr(elf, &ehdr)) {
	819	+ pr_warn("failed to get EHDR from %s\n", path);
	820	+ goto done;
	821	+ }
	822	+ if (!elf_rawdata(elf_getscn(elf, ehdr.e_shstrndx), NULL)) {
	823	+ pr_warn("failed to get e_shstrndx from %s\n", path);
	824	+ goto done;
	825	+ }
	826	+
	827	+ while ((scn = elf_nextscn(elf, scn)) != NULL) {
	828	+ GElf_Shdr sh;
	829	+ char *name;
	830	+
	831	+ idx++;
	832	+ if (gelf_getshdr(scn, &sh) != &sh) {
	833	+ pr_warn("failed to get section(%d) header from %s\n",
	834	+ idx, path);
	835	+ goto done;
	836	+ }
	837	+ name = elf_strptr(elf, ehdr.e_shstrndx, sh.sh_name);
	838	+ if (!name) {
	839	+ pr_warn("failed to get section(%d) name from %s\n",
	840	+ idx, path);
	841	+ goto done;
	842	+ }
	843	+ if (strcmp(name, BTF_ELF_SEC) == 0) {
	844	+ btf_data = elf_getdata(scn, 0);
	845	+ if (!btf_data) {
	846	+ pr_warn("failed to get section(%d, %s) data from %s\n",
	847	+ idx, name, path);
	848	+ goto done;
	849	+ }
	850	+ continue;
	851	+ } else if (btf_ext && strcmp(name, BTF_EXT_ELF_SEC) == 0) {
	852	+ btf_ext_data = elf_getdata(scn, 0);
	853	+ if (!btf_ext_data) {
	854	+ pr_warn("failed to get section(%d, %s) data from %s\n",
	855	+ idx, name, path);
	856	+ goto done;
	857	+ }
	858	+ continue;
	859	+ }
	860	+ }
	861	+
	862	+ err = 0;
	863	+
	864	+ if (!btf_data) {
	865	+ err = -ENOENT;
	866	+ goto done;
	867	+ }
	868	+ btf = btf__new(btf_data->d_buf, btf_data->d_size);
	869	+ if (IS_ERR(btf))
	870	+ goto done;
	871	+
	872	+ switch (gelf_getclass(elf)) {
	873	+ case ELFCLASS32:
	874	+ btf__set_pointer_size(btf, 4);
	875	+ break;
	876	+ case ELFCLASS64:
	877	+ btf__set_pointer_size(btf, 8);
	878	+ break;
	879	+ default:
	880	+ pr_warn("failed to get ELF class (bitness) for %s\n", path);
	881	+ break;
	882	+ }
	883	+
	884	+ if (btf_ext && btf_ext_data) {
	885	+ *btf_ext = btf_ext__new(btf_ext_data->d_buf,
	886	+ btf_ext_data->d_size);
	887	+ if (IS_ERR(*btf_ext))
	888	+ goto done;
	889	+ } else if (btf_ext) {
	890	+ *btf_ext = NULL;
	891	+ }
	892	+done:
	893	+ if (elf)
	894	+ elf_end(elf);
	895	+ close(fd);
	896	+
	897	+ if (err)
	898	+ return ERR_PTR(err);
	899	+ /*
	900	+ * btf is always parsed before btf_ext, so no need to clean up
	901	+ * btf_ext, if btf loading failed
	902	+ */
	903	+ if (IS_ERR(btf))
	904	+ return btf;
	905	+ if (btf_ext && IS_ERR(*btf_ext)) {
	906	+ btf__free(btf);
	907	+ err = PTR_ERR(*btf_ext);
	908	+ return ERR_PTR(err);
	909	+ }
	910	+ return btf;
	911	+}
	912	+
	913	+struct btf btf__parse_raw(const char path)
	914	+{
	915	+ struct btf *btf = NULL;
	916	+ void *data = NULL;
	917	+ FILE *f = NULL;
	918	+ __u16 magic;
	919	+ int err = 0;
	920	+ long sz;
	921	+
	922	+ f = fopen(path, "rb");
	923	+ if (!f) {
	924	+ err = -errno;
	925	+ goto err_out;
	926	+ }
	927	+
	928	+ /* check BTF magic */
	929	+ if (fread(&magic, 1, sizeof(magic), f) < sizeof(magic)) {
	930	+ err = -EIO;
	931	+ goto err_out;
	932	+ }
	933	+ if (magic != BTF_MAGIC && magic != bswap_16(BTF_MAGIC)) {
	934	+ /* definitely not a raw BTF */
	935	+ err = -EPROTO;
	936	+ goto err_out;
	937	+ }
	938	+
	939	+ /* get file size */
	940	+ if (fseek(f, 0, SEEK_END)) {
	941	+ err = -errno;
	942	+ goto err_out;
	943	+ }
	944	+ sz = ftell(f);
	945	+ if (sz < 0) {
	946	+ err = -errno;
	947	+ goto err_out;
	948	+ }
	949	+ /* rewind to the start */
	950	+ if (fseek(f, 0, SEEK_SET)) {
	951	+ err = -errno;
	952	+ goto err_out;
	953	+ }
	954	+
	955	+ /* pre-alloc memory and read all of BTF data */
	956	+ data = malloc(sz);
	957	+ if (!data) {
	958	+ err = -ENOMEM;
	959	+ goto err_out;
	960	+ }
	961	+ if (fread(data, 1, sz, f) < sz) {
	962	+ err = -EIO;
	963	+ goto err_out;
	964	+ }
	965	+
	966	+ /* finally parse BTF data */
	967	+ btf = btf__new(data, sz);
	968	+
	969	+err_out:
	970	+ free(data);
	971	+ if (f)
	972	+ fclose(f);
	973	+ return err ? ERR_PTR(err) : btf;
	974	+}
	975	+
	976	+struct btf btf__parse(const char path, struct btf_ext **btf_ext)
	977	+{
	978	+ struct btf *btf;
	979	+
	980	+ if (btf_ext)
	981	+ *btf_ext = NULL;
	982	+
	983	+ btf = btf__parse_raw(path);
	984	+ if (!IS_ERR(btf) \|\| PTR_ERR(btf) != -EPROTO)
	985	+ return btf;
	986	+
	987	+ return btf__parse_elf(path, btf_ext);
	988	+}
	989	+
	990	+static int compare_vsi_off(const void _a, const void _b)
	991	+{
	992	+ const struct btf_var_secinfo *a = _a;
	993	+ const struct btf_var_secinfo *b = _b;
	994	+
	995	+ return a->offset - b->offset;
	996	+}
	997	+
	998	+static int btf_fixup_datasec(struct bpf_object obj, struct btf btf,
	999	+ struct btf_type *t)
	1000	+{
	1001	+ __u32 size = 0, off = 0, i, vars = btf_vlen(t);
	1002	+ const char *name = btf__name_by_offset(btf, t->name_off);
	1003	+ const struct btf_type *t_var;
	1004	+ struct btf_var_secinfo *vsi;
	1005	+ const struct btf_var *var;
	1006	+ int ret;
	1007	+
	1008	+ if (!name) {
	1009	+ pr_debug("No name found in string section for DATASEC kind.\n");
	1010	+ return -ENOENT;
	1011	+ }
	1012	+
	1013	+ /* .extern datasec size and var offsets were set correctly during
	1014	+ * extern collection step, so just skip straight to sorting variables
	1015	+ */
	1016	+ if (t->size)
	1017	+ goto sort_vars;
	1018	+
	1019	+ ret = bpf_object__section_size(obj, name, &size);
	1020	+ if (ret \|\| !size \|\| (t->size && t->size != size)) {
	1021	+ pr_debug("Invalid size for section %s: %u bytes\n", name, size);
	1022	+ return -ENOENT;
	1023	+ }
	1024	+
	1025	+ t->size = size;
	1026	+
	1027	+ for (i = 0, vsi = btf_var_secinfos(t); i < vars; i++, vsi++) {
	1028	+ t_var = btf__type_by_id(btf, vsi->type);
	1029	+ var = btf_var(t_var);
	1030	+
	1031	+ if (!btf_is_var(t_var)) {
	1032	+ pr_debug("Non-VAR type seen in section %s\n", name);
	1033	+ return -EINVAL;
	1034	+ }
	1035	+
	1036	+ if (var->linkage == BTF_VAR_STATIC)
	1037	+ continue;
	1038	+
	1039	+ name = btf__name_by_offset(btf, t_var->name_off);
	1040	+ if (!name) {
	1041	+ pr_debug("No name found in string section for VAR kind\n");
	1042	+ return -ENOENT;
	1043	+ }
	1044	+
	1045	+ ret = bpf_object__variable_offset(obj, name, &off);
	1046	+ if (ret) {
	1047	+ pr_debug("No offset found in symbol table for VAR %s\n",
	1048	+ name);
	1049	+ return -ENOENT;
	1050	+ }
	1051	+
	1052	+ vsi->offset = off;
	1053	+ }
	1054	+
	1055	+sort_vars:
	1056	+ qsort(btf_var_secinfos(t), vars, sizeof(*vsi), compare_vsi_off);
	1057	+ return 0;
	1058	+}
	1059	+
	1060	+int btf__finalize_data(struct bpf_object obj, struct btf btf)
	1061	+{
	1062	+ int err = 0;
	1063	+ __u32 i;
	1064	+
	1065	+ for (i = 1; i <= btf->nr_types; i++) {
	1066	+ struct btf_type *t = btf_type_by_id(btf, i);
	1067	+
	1068	+ /* Loader needs to fix up some of the things compiler
	1069	+ * couldn't get its hands on while emitting BTF. This
	1070	+ * is section size and global variable offset. We use
	1071	+ * the info from the ELF itself for this purpose.
	1072	+ */
	1073	+ if (btf_is_datasec(t)) {
	1074	+ err = btf_fixup_datasec(obj, btf, t);
	1075	+ if (err)
	1076	+ break;
	1077	+ }
	1078	+ }
	1079	+
	1080	+ return err;
	1081	+}
	1082	+
	1083	+static void btf_get_raw_data(const struct btf btf, __u32 *size, bool swap_endian);
	1084	+
	1085	+int btf__load(struct btf *btf)
	1086	+{
	1087	+ __u32 log_buf_size = 0, raw_size;
	1088	+ char *log_buf = NULL;
	1089	+ void *raw_data;
	1090	+ int err = 0;
	1091	+
	1092	+ if (btf->fd >= 0)
	1093	+ return -EEXIST;
	1094	+
	1095	+retry_load:
	1096	+ if (log_buf_size) {
	1097	+ log_buf = malloc(log_buf_size);
	1098	+ if (!log_buf)
	1099	+ return -ENOMEM;
	1100	+
	1101	+ *log_buf = 0;
	1102	+ }
	1103	+
	1104	+ raw_data = btf_get_raw_data(btf, &raw_size, false);
	1105	+ if (!raw_data) {
	1106	+ err = -ENOMEM;
	1107	+ goto done;
	1108	+ }
	1109	+ /* cache native raw data representation */
	1110	+ btf->raw_size = raw_size;
	1111	+ btf->raw_data = raw_data;
	1112	+
	1113	+ btf->fd = bpf_load_btf(raw_data, raw_size, log_buf, log_buf_size, false);
	1114	+ if (btf->fd < 0) {
	1115	+ if (!log_buf \|\| errno == ENOSPC) {
	1116	+ log_buf_size = max((__u32)BPF_LOG_BUF_SIZE,
	1117	+ log_buf_size << 1);
	1118	+ free(log_buf);
	1119	+ goto retry_load;
	1120	+ }
	1121	+
	1122	+ err = -errno;
	1123	+ pr_warn("Error loading BTF: %s(%d)\n", strerror(errno), errno);
	1124	+ if (*log_buf)
	1125	+ pr_warn("%s\n", log_buf);
	1126	+ goto done;
	1127	+ }
	1128	+
	1129	+done:
	1130	+ free(log_buf);
	1131	+ return err;
	1132	+}
	1133	+
384	1134	int btf__fd(const struct btf *btf)
385	1135	{
386	1136	return btf->fd;
387	1137	}
388	1138
389		-const char btf__name_by_offset(const struct btf btf, __u32 offset)
	1139	+void btf__set_fd(struct btf *btf, int fd)
	1140	+{
	1141	+ btf->fd = fd;
	1142	+}
	1143	+
	1144	+static void btf_get_raw_data(const struct btf btf, __u32 *size, bool swap_endian)
	1145	+{
	1146	+ struct btf_header *hdr = btf->hdr;
	1147	+ struct btf_type *t;
	1148	+ void data, p;
	1149	+ __u32 data_sz;
	1150	+ int i;
	1151	+
	1152	+ data = swap_endian ? btf->raw_data_swapped : btf->raw_data;
	1153	+ if (data) {
	1154	+ *size = btf->raw_size;
	1155	+ return data;
	1156	+ }
	1157	+
	1158	+ data_sz = hdr->hdr_len + hdr->type_len + hdr->str_len;
	1159	+ data = calloc(1, data_sz);
	1160	+ if (!data)
	1161	+ return NULL;
	1162	+ p = data;
	1163	+
	1164	+ memcpy(p, hdr, hdr->hdr_len);
	1165	+ if (swap_endian)
	1166	+ btf_bswap_hdr(p);
	1167	+ p += hdr->hdr_len;
	1168	+
	1169	+ memcpy(p, btf->types_data, hdr->type_len);
	1170	+ if (swap_endian) {
	1171	+ for (i = 1; i <= btf->nr_types; i++) {
	1172	+ t = p + btf->type_offs[i];
	1173	+ /* btf_bswap_type_rest() relies on native t->info, so
	1174	+ * we swap base type info after we swapped all the
	1175	+ * additional information
	1176	+ */
	1177	+ if (btf_bswap_type_rest(t))
	1178	+ goto err_out;
	1179	+ btf_bswap_type_base(t);
	1180	+ }
	1181	+ }
	1182	+ p += hdr->type_len;
	1183	+
	1184	+ memcpy(p, btf->strs_data, hdr->str_len);
	1185	+ p += hdr->str_len;
	1186	+
	1187	+ *size = data_sz;
	1188	+ return data;
	1189	+err_out:
	1190	+ free(data);
	1191	+ return NULL;
	1192	+}
	1193	+
	1194	+const void btf__get_raw_data(const struct btf btf_ro, __u32 *size)
	1195	+{
	1196	+ struct btf btf = (struct btf )btf_ro;
	1197	+ __u32 data_sz;
	1198	+ void *data;
	1199	+
	1200	+ data = btf_get_raw_data(btf, &data_sz, btf->swapped_endian);
	1201	+ if (!data)
	1202	+ return NULL;
	1203	+
	1204	+ btf->raw_size = data_sz;
	1205	+ if (btf->swapped_endian)
	1206	+ btf->raw_data_swapped = data;
	1207	+ else
	1208	+ btf->raw_data = data;
	1209	+ *size = data_sz;
	1210	+ return data;
	1211	+}
	1212	+
	1213	+const char btf__str_by_offset(const struct btf btf, __u32 offset)
390	1214	{
391	1215	if (offset < btf->hdr->str_len)
392		- return &btf->strings[offset];
	1216	+ return btf->strs_data + offset;
393	1217	else
394	1218	return NULL;
395	1219	}
	1220	+
	1221	+const char btf__name_by_offset(const struct btf btf, __u32 offset)
	1222	+{
	1223	+ return btf__str_by_offset(btf, offset);
	1224	+}
	1225	+
	1226	+int btf__get_from_id(__u32 id, struct btf **btf)
	1227	+{
	1228	+ struct bpf_btf_info btf_info = { 0 };
	1229	+ __u32 len = sizeof(btf_info);
	1230	+ __u32 last_size;
	1231	+ int btf_fd;
	1232	+ void *ptr;
	1233	+ int err;
	1234	+
	1235	+ err = 0;
	1236	+ *btf = NULL;
	1237	+ btf_fd = bpf_btf_get_fd_by_id(id);
	1238	+ if (btf_fd < 0)
	1239	+ return 0;
	1240	+
	1241	+ /* we won't know btf_size until we call bpf_obj_get_info_by_fd(). so
	1242	+ * let's start with a sane default - 4KiB here - and resize it only if
	1243	+ * bpf_obj_get_info_by_fd() needs a bigger buffer.
	1244	+ */
	1245	+ btf_info.btf_size = 4096;
	1246	+ last_size = btf_info.btf_size;
	1247	+ ptr = malloc(last_size);
	1248	+ if (!ptr) {
	1249	+ err = -ENOMEM;
	1250	+ goto exit_free;
	1251	+ }
	1252	+
	1253	+ memset(ptr, 0, last_size);
	1254	+ btf_info.btf = ptr_to_u64(ptr);
	1255	+ err = bpf_obj_get_info_by_fd(btf_fd, &btf_info, &len);
	1256	+
	1257	+ if (!err && btf_info.btf_size > last_size) {
	1258	+ void *temp_ptr;
	1259	+
	1260	+ last_size = btf_info.btf_size;
	1261	+ temp_ptr = realloc(ptr, last_size);
	1262	+ if (!temp_ptr) {
	1263	+ err = -ENOMEM;
	1264	+ goto exit_free;
	1265	+ }
	1266	+ ptr = temp_ptr;
	1267	+ memset(ptr, 0, last_size);
	1268	+ btf_info.btf = ptr_to_u64(ptr);
	1269	+ err = bpf_obj_get_info_by_fd(btf_fd, &btf_info, &len);
	1270	+ }
	1271	+
	1272	+ if (err \|\| btf_info.btf_size > last_size) {
	1273	+ err = errno;
	1274	+ goto exit_free;
	1275	+ }
	1276	+
	1277	+ btf = btf__new((__u8 )(long)btf_info.btf, btf_info.btf_size);
	1278	+ if (IS_ERR(*btf)) {
	1279	+ err = PTR_ERR(*btf);
	1280	+ *btf = NULL;
	1281	+ }
	1282	+
	1283	+exit_free:
	1284	+ close(btf_fd);
	1285	+ free(ptr);
	1286	+
	1287	+ return err;
	1288	+}
	1289	+
	1290	+int btf__get_map_kv_tids(const struct btf btf, const char map_name,
	1291	+ __u32 expected_key_size, __u32 expected_value_size,
	1292	+ __u32 key_type_id, __u32 value_type_id)
	1293	+{
	1294	+ const struct btf_type *container_type;
	1295	+ const struct btf_member key, value;
	1296	+ const size_t max_name = 256;
	1297	+ char container_name[max_name];
	1298	+ __s64 key_size, value_size;
	1299	+ __s32 container_id;
	1300	+
	1301	+ if (snprintf(container_name, max_name, "____btf_map_%s", map_name) ==
	1302	+ max_name) {
	1303	+ pr_warn("map:%s length of '____btf_map_%s' is too long\n",
	1304	+ map_name, map_name);
	1305	+ return -EINVAL;
	1306	+ }
	1307	+
	1308	+ container_id = btf__find_by_name(btf, container_name);
	1309	+ if (container_id < 0) {
	1310	+ pr_debug("map:%s container_name:%s cannot be found in BTF. Missing BPF_ANNOTATE_KV_PAIR?\n",
	1311	+ map_name, container_name);
	1312	+ return container_id;
	1313	+ }
	1314	+
	1315	+ container_type = btf__type_by_id(btf, container_id);
	1316	+ if (!container_type) {
	1317	+ pr_warn("map:%s cannot find BTF type for container_id:%u\n",
	1318	+ map_name, container_id);
	1319	+ return -EINVAL;
	1320	+ }
	1321	+
	1322	+ if (!btf_is_struct(container_type) \|\| btf_vlen(container_type) < 2) {
	1323	+ pr_warn("map:%s container_name:%s is an invalid container struct\n",
	1324	+ map_name, container_name);
	1325	+ return -EINVAL;
	1326	+ }
	1327	+
	1328	+ key = btf_members(container_type);
	1329	+ value = key + 1;
	1330	+
	1331	+ key_size = btf__resolve_size(btf, key->type);
	1332	+ if (key_size < 0) {
	1333	+ pr_warn("map:%s invalid BTF key_type_size\n", map_name);
	1334	+ return key_size;
	1335	+ }
	1336	+
	1337	+ if (expected_key_size != key_size) {
	1338	+ pr_warn("map:%s btf_key_type_size:%u != map_def_key_size:%u\n",
	1339	+ map_name, (__u32)key_size, expected_key_size);
	1340	+ return -EINVAL;
	1341	+ }
	1342	+
	1343	+ value_size = btf__resolve_size(btf, value->type);
	1344	+ if (value_size < 0) {
	1345	+ pr_warn("map:%s invalid BTF value_type_size\n", map_name);
	1346	+ return value_size;
	1347	+ }
	1348	+
	1349	+ if (expected_value_size != value_size) {
	1350	+ pr_warn("map:%s btf_value_type_size:%u != map_def_value_size:%u\n",
	1351	+ map_name, (__u32)value_size, expected_value_size);
	1352	+ return -EINVAL;
	1353	+ }
	1354	+
	1355	+ *key_type_id = key->type;
	1356	+ *value_type_id = value->type;
	1357	+
	1358	+ return 0;
	1359	+}
	1360	+
	1361	+static size_t strs_hash_fn(const void key, void ctx)
	1362	+{
	1363	+ struct btf *btf = ctx;
	1364	+ const char *str = btf->strs_data + (long)key;
	1365	+
	1366	+ return str_hash(str);
	1367	+}
	1368	+
	1369	+static bool strs_hash_equal_fn(const void key1, const void key2, void *ctx)
	1370	+{
	1371	+ struct btf *btf = ctx;
	1372	+ const char *str1 = btf->strs_data + (long)key1;
	1373	+ const char *str2 = btf->strs_data + (long)key2;
	1374	+
	1375	+ return strcmp(str1, str2) == 0;
	1376	+}
	1377	+
	1378	+static void btf_invalidate_raw_data(struct btf *btf)
	1379	+{
	1380	+ if (btf->raw_data) {
	1381	+ free(btf->raw_data);
	1382	+ btf->raw_data = NULL;
	1383	+ }
	1384	+ if (btf->raw_data_swapped) {
	1385	+ free(btf->raw_data_swapped);
	1386	+ btf->raw_data_swapped = NULL;
	1387	+ }
	1388	+}
	1389	+
	1390	+/* Ensure BTF is ready to be modified (by splitting into a three memory
	1391	+ * regions for header, types, and strings). Also invalidate cached
	1392	+ * raw_data, if any.
	1393	+ */
	1394	+static int btf_ensure_modifiable(struct btf *btf)
	1395	+{
	1396	+ void hdr, types, strs, strs_end, *s;
	1397	+ struct hashmap *hash = NULL;
	1398	+ long off;
	1399	+ int err;
	1400	+
	1401	+ if (btf_is_modifiable(btf)) {
	1402	+ /* any BTF modification invalidates raw_data */
	1403	+ btf_invalidate_raw_data(btf);
	1404	+ return 0;
	1405	+ }
	1406	+
	1407	+ /* split raw data into three memory regions */
	1408	+ hdr = malloc(btf->hdr->hdr_len);
	1409	+ types = malloc(btf->hdr->type_len);
	1410	+ strs = malloc(btf->hdr->str_len);
	1411	+ if (!hdr \|\| !types \|\| !strs)
	1412	+ goto err_out;
	1413	+
	1414	+ memcpy(hdr, btf->hdr, btf->hdr->hdr_len);
	1415	+ memcpy(types, btf->types_data, btf->hdr->type_len);
	1416	+ memcpy(strs, btf->strs_data, btf->hdr->str_len);
	1417	+
	1418	+ /* build lookup index for all strings */
	1419	+ hash = hashmap__new(strs_hash_fn, strs_hash_equal_fn, btf);
	1420	+ if (IS_ERR(hash)) {
	1421	+ err = PTR_ERR(hash);
	1422	+ hash = NULL;
	1423	+ goto err_out;
	1424	+ }
	1425	+
	1426	+ strs_end = strs + btf->hdr->str_len;
	1427	+ for (off = 0, s = strs; s < strs_end; off += strlen(s) + 1, s = strs + off) {
	1428	+ /* hashmap__add() returns EEXIST if string with the same
	1429	+ * content already is in the hash map
	1430	+ */
	1431	+ err = hashmap__add(hash, (void )off, (void )off);
	1432	+ if (err == -EEXIST)
	1433	+ continue; /* duplicate */
	1434	+ if (err)
	1435	+ goto err_out;
	1436	+ }
	1437	+
	1438	+ /* only when everything was successful, update internal state */
	1439	+ btf->hdr = hdr;
	1440	+ btf->types_data = types;
	1441	+ btf->types_data_cap = btf->hdr->type_len;
	1442	+ btf->strs_data = strs;
	1443	+ btf->strs_data_cap = btf->hdr->str_len;
	1444	+ btf->strs_hash = hash;
	1445	+ /* if BTF was created from scratch, all strings are guaranteed to be
	1446	+ * unique and deduplicated
	1447	+ */
	1448	+ btf->strs_deduped = btf->hdr->str_len <= 1;
	1449	+
	1450	+ /* invalidate raw_data representation */
	1451	+ btf_invalidate_raw_data(btf);
	1452	+
	1453	+ return 0;
	1454	+
	1455	+err_out:
	1456	+ hashmap__free(hash);
	1457	+ free(hdr);
	1458	+ free(types);
	1459	+ free(strs);
	1460	+ return -ENOMEM;
	1461	+}
	1462	+
	1463	+static void btf_add_str_mem(struct btf btf, size_t add_sz)
	1464	+{
	1465	+ return btf_add_mem(&btf->strs_data, &btf->strs_data_cap, 1,
	1466	+ btf->hdr->str_len, BTF_MAX_STR_OFFSET, add_sz);
	1467	+}
	1468	+
	1469	+/* Find an offset in BTF string section that corresponds to a given string s.
	1470	+ * Returns:
	1471	+ * - >0 offset into string section, if string is found;
	1472	+ * - -ENOENT, if string is not in the string section;
	1473	+ * - <0, on any other error.
	1474	+ */
	1475	+int btf__find_str(struct btf btf, const char s)
	1476	+{
	1477	+ long old_off, new_off, len;
	1478	+ void *p;
	1479	+
	1480	+ /* BTF needs to be in a modifiable state to build string lookup index */
	1481	+ if (btf_ensure_modifiable(btf))
	1482	+ return -ENOMEM;
	1483	+
	1484	+ /* see btf__add_str() for why we do this */
	1485	+ len = strlen(s) + 1;
	1486	+ p = btf_add_str_mem(btf, len);
	1487	+ if (!p)
	1488	+ return -ENOMEM;
	1489	+
	1490	+ new_off = btf->hdr->str_len;
	1491	+ memcpy(p, s, len);
	1492	+
	1493	+ if (hashmap__find(btf->strs_hash, (void )new_off, (void *)&old_off))
	1494	+ return old_off;
	1495	+
	1496	+ return -ENOENT;
	1497	+}
	1498	+
	1499	+/* Add a string s to the BTF string section.
	1500	+ * Returns:
	1501	+ * - > 0 offset into string section, on success;
	1502	+ * - < 0, on error.
	1503	+ */
	1504	+int btf__add_str(struct btf btf, const char s)
	1505	+{
	1506	+ long old_off, new_off, len;
	1507	+ void *p;
	1508	+ int err;
	1509	+
	1510	+ if (btf_ensure_modifiable(btf))
	1511	+ return -ENOMEM;
	1512	+
	1513	+ /* Hashmap keys are always offsets within btf->strs_data, so to even
	1514	+ * look up some string from the "outside", we need to first append it
	1515	+ * at the end, so that it can be addressed with an offset. Luckily,
	1516	+ * until btf->hdr->str_len is incremented, that string is just a piece
	1517	+ * of garbage for the rest of BTF code, so no harm, no foul. On the
	1518	+ * other hand, if the string is unique, it's already appended and
	1519	+ * ready to be used, only a simple btf->hdr->str_len increment away.
	1520	+ */
	1521	+ len = strlen(s) + 1;
	1522	+ p = btf_add_str_mem(btf, len);
	1523	+ if (!p)
	1524	+ return -ENOMEM;
	1525	+
	1526	+ new_off = btf->hdr->str_len;
	1527	+ memcpy(p, s, len);
	1528	+
	1529	+ /* Now attempt to add the string, but only if the string with the same
	1530	+ * contents doesn't exist already (HASHMAP_ADD strategy). If such
	1531	+ * string exists, we'll get its offset in old_off (that's old_key).
	1532	+ */
	1533	+ err = hashmap__insert(btf->strs_hash, (void )new_off, (void )new_off,
	1534	+ HASHMAP_ADD, (const void **)&old_off, NULL);
	1535	+ if (err == -EEXIST)
	1536	+ return old_off; /* duplicated string, return existing offset */
	1537	+ if (err)
	1538	+ return err;
	1539	+
	1540	+ btf->hdr->str_len += len; /* new unique string, adjust data length */
	1541	+ return new_off;
	1542	+}
	1543	+
	1544	+static void btf_add_type_mem(struct btf btf, size_t add_sz)
	1545	+{
	1546	+ return btf_add_mem(&btf->types_data, &btf->types_data_cap, 1,
	1547	+ btf->hdr->type_len, UINT_MAX, add_sz);
	1548	+}
	1549	+
	1550	+static __u32 btf_type_info(int kind, int vlen, int kflag)
	1551	+{
	1552	+ return (kflag << 31) \| (kind << 24) \| vlen;
	1553	+}
	1554	+
	1555	+static void btf_type_inc_vlen(struct btf_type *t)
	1556	+{
	1557	+ t->info = btf_type_info(btf_kind(t), btf_vlen(t) + 1, btf_kflag(t));
	1558	+}
	1559	+
	1560	+/*
	1561	+ * Append new BTF_KIND_INT type with:
	1562	+ * - name - non-empty, non-NULL type name;
	1563	+ * - sz - power-of-2 (1, 2, 4, ..) size of the type, in bytes;
	1564	+ * - encoding is a combination of BTF_INT_SIGNED, BTF_INT_CHAR, BTF_INT_BOOL.
	1565	+ * Returns:
	1566	+ * - >0, type ID of newly added BTF type;
	1567	+ * - <0, on error.
	1568	+ */
	1569	+int btf__add_int(struct btf btf, const char name, size_t byte_sz, int encoding)
	1570	+{
	1571	+ struct btf_type *t;
	1572	+ int sz, err, name_off;
	1573	+
	1574	+ /* non-empty name */
	1575	+ if (!name \|\| !name[0])
	1576	+ return -EINVAL;
	1577	+ /* byte_sz must be power of 2 */
	1578	+ if (!byte_sz \|\| (byte_sz & (byte_sz - 1)) \|\| byte_sz > 16)
	1579	+ return -EINVAL;
	1580	+ if (encoding & ~(BTF_INT_SIGNED \| BTF_INT_CHAR \| BTF_INT_BOOL))
	1581	+ return -EINVAL;
	1582	+
	1583	+ /* deconstruct BTF, if necessary, and invalidate raw_data */
	1584	+ if (btf_ensure_modifiable(btf))
	1585	+ return -ENOMEM;
	1586	+
	1587	+ sz = sizeof(struct btf_type) + sizeof(int);
	1588	+ t = btf_add_type_mem(btf, sz);
	1589	+ if (!t)
	1590	+ return -ENOMEM;
	1591	+
	1592	+ /* if something goes wrong later, we might end up with an extra string,
	1593	+ * but that shouldn't be a problem, because BTF can't be constructed
	1594	+ * completely anyway and will most probably be just discarded
	1595	+ */
	1596	+ name_off = btf__add_str(btf, name);
	1597	+ if (name_off < 0)
	1598	+ return name_off;
	1599	+
	1600	+ t->name_off = name_off;
	1601	+ t->info = btf_type_info(BTF_KIND_INT, 0, 0);
	1602	+ t->size = byte_sz;
	1603	+ /* set INT info, we don't allow setting legacy bit offset/size */
	1604	+ (__u32 )(t + 1) = (encoding << 24) \| (byte_sz * 8);
	1605	+
	1606	+ err = btf_add_type_idx_entry(btf, btf->hdr->type_len);
	1607	+ if (err)
	1608	+ return err;
	1609	+
	1610	+ btf->hdr->type_len += sz;
	1611	+ btf->hdr->str_off += sz;
	1612	+ btf->nr_types++;
	1613	+ return btf->nr_types;
	1614	+}
	1615	+
	1616	+/* it's completely legal to append BTF types with type IDs pointing forward to
	1617	+ * types that haven't been appended yet, so we only make sure that id looks
	1618	+ * sane, we can't guarantee that ID will always be valid
	1619	+ */
	1620	+static int validate_type_id(int id)
	1621	+{
	1622	+ if (id < 0 \|\| id > BTF_MAX_NR_TYPES)
	1623	+ return -EINVAL;
	1624	+ return 0;
	1625	+}
	1626	+
	1627	+/* generic append function for PTR, TYPEDEF, CONST/VOLATILE/RESTRICT */
	1628	+static int btf_add_ref_kind(struct btf btf, int kind, const char name, int ref_type_id)
	1629	+{
	1630	+ struct btf_type *t;
	1631	+ int sz, name_off = 0, err;
	1632	+
	1633	+ if (validate_type_id(ref_type_id))
	1634	+ return -EINVAL;
	1635	+
	1636	+ if (btf_ensure_modifiable(btf))
	1637	+ return -ENOMEM;
	1638	+
	1639	+ sz = sizeof(struct btf_type);
	1640	+ t = btf_add_type_mem(btf, sz);
	1641	+ if (!t)
	1642	+ return -ENOMEM;
	1643	+
	1644	+ if (name && name[0]) {
	1645	+ name_off = btf__add_str(btf, name);
	1646	+ if (name_off < 0)
	1647	+ return name_off;
	1648	+ }
	1649	+
	1650	+ t->name_off = name_off;
	1651	+ t->info = btf_type_info(kind, 0, 0);
	1652	+ t->type = ref_type_id;
	1653	+
	1654	+ err = btf_add_type_idx_entry(btf, btf->hdr->type_len);
	1655	+ if (err)
	1656	+ return err;
	1657	+
	1658	+ btf->hdr->type_len += sz;
	1659	+ btf->hdr->str_off += sz;
	1660	+ btf->nr_types++;
	1661	+ return btf->nr_types;
	1662	+}
	1663	+
	1664	+/*
	1665	+ * Append new BTF_KIND_PTR type with:
	1666	+ * - ref_type_id - referenced type ID, it might not exist yet;
	1667	+ * Returns:
	1668	+ * - >0, type ID of newly added BTF type;
	1669	+ * - <0, on error.
	1670	+ */
	1671	+int btf__add_ptr(struct btf *btf, int ref_type_id)
	1672	+{
	1673	+ return btf_add_ref_kind(btf, BTF_KIND_PTR, NULL, ref_type_id);
	1674	+}
	1675	+
	1676	+/*
	1677	+ * Append new BTF_KIND_ARRAY type with:
	1678	+ * - index_type_id - type ID of the type describing array index;
	1679	+ * - elem_type_id - type ID of the type describing array element;
	1680	+ * - nr_elems - the size of the array;
	1681	+ * Returns:
	1682	+ * - >0, type ID of newly added BTF type;
	1683	+ * - <0, on error.
	1684	+ */
	1685	+int btf__add_array(struct btf *btf, int index_type_id, int elem_type_id, __u32 nr_elems)
	1686	+{
	1687	+ struct btf_type *t;
	1688	+ struct btf_array *a;
	1689	+ int sz, err;
	1690	+
	1691	+ if (validate_type_id(index_type_id) \|\| validate_type_id(elem_type_id))
	1692	+ return -EINVAL;
	1693	+
	1694	+ if (btf_ensure_modifiable(btf))
	1695	+ return -ENOMEM;
	1696	+
	1697	+ sz = sizeof(struct btf_type) + sizeof(struct btf_array);
	1698	+ t = btf_add_type_mem(btf, sz);
	1699	+ if (!t)
	1700	+ return -ENOMEM;
	1701	+
	1702	+ t->name_off = 0;
	1703	+ t->info = btf_type_info(BTF_KIND_ARRAY, 0, 0);
	1704	+ t->size = 0;
	1705	+
	1706	+ a = btf_array(t);
	1707	+ a->type = elem_type_id;
	1708	+ a->index_type = index_type_id;
	1709	+ a->nelems = nr_elems;
	1710	+
	1711	+ err = btf_add_type_idx_entry(btf, btf->hdr->type_len);
	1712	+ if (err)
	1713	+ return err;
	1714	+
	1715	+ btf->hdr->type_len += sz;
	1716	+ btf->hdr->str_off += sz;
	1717	+ btf->nr_types++;
	1718	+ return btf->nr_types;
	1719	+}
	1720	+
	1721	+/* generic STRUCT/UNION append function */
	1722	+static int btf_add_composite(struct btf btf, int kind, const char name, __u32 bytes_sz)
	1723	+{
	1724	+ struct btf_type *t;
	1725	+ int sz, err, name_off = 0;
	1726	+
	1727	+ if (btf_ensure_modifiable(btf))
	1728	+ return -ENOMEM;
	1729	+
	1730	+ sz = sizeof(struct btf_type);
	1731	+ t = btf_add_type_mem(btf, sz);
	1732	+ if (!t)
	1733	+ return -ENOMEM;
	1734	+
	1735	+ if (name && name[0]) {
	1736	+ name_off = btf__add_str(btf, name);
	1737	+ if (name_off < 0)
	1738	+ return name_off;
	1739	+ }
	1740	+
	1741	+ /* start out with vlen=0 and no kflag; this will be adjusted when
	1742	+ * adding each member
	1743	+ */
	1744	+ t->name_off = name_off;
	1745	+ t->info = btf_type_info(kind, 0, 0);
	1746	+ t->size = bytes_sz;
	1747	+
	1748	+ err = btf_add_type_idx_entry(btf, btf->hdr->type_len);
	1749	+ if (err)
	1750	+ return err;
	1751	+
	1752	+ btf->hdr->type_len += sz;
	1753	+ btf->hdr->str_off += sz;
	1754	+ btf->nr_types++;
	1755	+ return btf->nr_types;
	1756	+}
	1757	+
	1758	+/*
	1759	+ * Append new BTF_KIND_STRUCT type with:
	1760	+ * - name - name of the struct, can be NULL or empty for anonymous structs;
	1761	+ * - byte_sz - size of the struct, in bytes;
	1762	+ *
	1763	+ * Struct initially has no fields in it. Fields can be added by
	1764	+ * btf__add_field() right after btf__add_struct() succeeds.
	1765	+ *
	1766	+ * Returns:
	1767	+ * - >0, type ID of newly added BTF type;
	1768	+ * - <0, on error.
	1769	+ */
	1770	+int btf__add_struct(struct btf btf, const char name, __u32 byte_sz)
	1771	+{
	1772	+ return btf_add_composite(btf, BTF_KIND_STRUCT, name, byte_sz);
	1773	+}
	1774	+
	1775	+/*
	1776	+ * Append new BTF_KIND_UNION type with:
	1777	+ * - name - name of the union, can be NULL or empty for anonymous union;
	1778	+ * - byte_sz - size of the union, in bytes;
	1779	+ *
	1780	+ * Union initially has no fields in it. Fields can be added by
	1781	+ * btf__add_field() right after btf__add_union() succeeds. All fields
	1782	+ * should have bit_offset of 0.
	1783	+ *
	1784	+ * Returns:
	1785	+ * - >0, type ID of newly added BTF type;
	1786	+ * - <0, on error.
	1787	+ */
	1788	+int btf__add_union(struct btf btf, const char name, __u32 byte_sz)
	1789	+{
	1790	+ return btf_add_composite(btf, BTF_KIND_UNION, name, byte_sz);
	1791	+}
	1792	+
	1793	+/*
	1794	+ * Append new field for the current STRUCT/UNION type with:
	1795	+ * - name - name of the field, can be NULL or empty for anonymous field;
	1796	+ * - type_id - type ID for the type describing field type;
	1797	+ * - bit_offset - bit offset of the start of the field within struct/union;
	1798	+ * - bit_size - bit size of a bitfield, 0 for non-bitfield fields;
	1799	+ * Returns:
	1800	+ * - 0, on success;
	1801	+ * - <0, on error.
	1802	+ */
	1803	+int btf__add_field(struct btf btf, const char name, int type_id,
	1804	+ __u32 bit_offset, __u32 bit_size)
	1805	+{
	1806	+ struct btf_type *t;
	1807	+ struct btf_member *m;
	1808	+ bool is_bitfield;
	1809	+ int sz, name_off = 0;
	1810	+
	1811	+ /* last type should be union/struct */
	1812	+ if (btf->nr_types == 0)
	1813	+ return -EINVAL;
	1814	+ t = btf_type_by_id(btf, btf->nr_types);
	1815	+ if (!btf_is_composite(t))
	1816	+ return -EINVAL;
	1817	+
	1818	+ if (validate_type_id(type_id))
	1819	+ return -EINVAL;
	1820	+ /* best-effort bit field offset/size enforcement */
	1821	+ is_bitfield = bit_size \|\| (bit_offset % 8 != 0);
	1822	+ if (is_bitfield && (bit_size == 0 \|\| bit_size > 255 \|\| bit_offset > 0xffffff))
	1823	+ return -EINVAL;
	1824	+
	1825	+ /* only offset 0 is allowed for unions */
	1826	+ if (btf_is_union(t) && bit_offset)
	1827	+ return -EINVAL;
	1828	+
	1829	+ /* decompose and invalidate raw data */
	1830	+ if (btf_ensure_modifiable(btf))
	1831	+ return -ENOMEM;
	1832	+
	1833	+ sz = sizeof(struct btf_member);
	1834	+ m = btf_add_type_mem(btf, sz);
	1835	+ if (!m)
	1836	+ return -ENOMEM;
	1837	+
	1838	+ if (name && name[0]) {
	1839	+ name_off = btf__add_str(btf, name);
	1840	+ if (name_off < 0)
	1841	+ return name_off;
	1842	+ }
	1843	+
	1844	+ m->name_off = name_off;
	1845	+ m->type = type_id;
	1846	+ m->offset = bit_offset \| (bit_size << 24);
	1847	+
	1848	+ /* btf_add_type_mem can invalidate t pointer */
	1849	+ t = btf_type_by_id(btf, btf->nr_types);
	1850	+ /* update parent type's vlen and kflag */
	1851	+ t->info = btf_type_info(btf_kind(t), btf_vlen(t) + 1, is_bitfield \|\| btf_kflag(t));
	1852	+
	1853	+ btf->hdr->type_len += sz;
	1854	+ btf->hdr->str_off += sz;
	1855	+ return 0;
	1856	+}
	1857	+
	1858	+/*
	1859	+ * Append new BTF_KIND_ENUM type with:
	1860	+ * - name - name of the enum, can be NULL or empty for anonymous enums;
	1861	+ * - byte_sz - size of the enum, in bytes.
	1862	+ *
	1863	+ * Enum initially has no enum values in it (and corresponds to enum forward
	1864	+ * declaration). Enumerator values can be added by btf__add_enum_value()
	1865	+ * immediately after btf__add_enum() succeeds.
	1866	+ *
	1867	+ * Returns:
	1868	+ * - >0, type ID of newly added BTF type;
	1869	+ * - <0, on error.
	1870	+ */
	1871	+int btf__add_enum(struct btf btf, const char name, __u32 byte_sz)
	1872	+{
	1873	+ struct btf_type *t;
	1874	+ int sz, err, name_off = 0;
	1875	+
	1876	+ /* byte_sz must be power of 2 */
	1877	+ if (!byte_sz \|\| (byte_sz & (byte_sz - 1)) \|\| byte_sz > 8)
	1878	+ return -EINVAL;
	1879	+
	1880	+ if (btf_ensure_modifiable(btf))
	1881	+ return -ENOMEM;
	1882	+
	1883	+ sz = sizeof(struct btf_type);
	1884	+ t = btf_add_type_mem(btf, sz);
	1885	+ if (!t)
	1886	+ return -ENOMEM;
	1887	+
	1888	+ if (name && name[0]) {
	1889	+ name_off = btf__add_str(btf, name);
	1890	+ if (name_off < 0)
	1891	+ return name_off;
	1892	+ }
	1893	+
	1894	+ /* start out with vlen=0; it will be adjusted when adding enum values */
	1895	+ t->name_off = name_off;
	1896	+ t->info = btf_type_info(BTF_KIND_ENUM, 0, 0);
	1897	+ t->size = byte_sz;
	1898	+
	1899	+ err = btf_add_type_idx_entry(btf, btf->hdr->type_len);
	1900	+ if (err)
	1901	+ return err;
	1902	+
	1903	+ btf->hdr->type_len += sz;
	1904	+ btf->hdr->str_off += sz;
	1905	+ btf->nr_types++;
	1906	+ return btf->nr_types;
	1907	+}
	1908	+
	1909	+/*
	1910	+ * Append new enum value for the current ENUM type with:
	1911	+ * - name - name of the enumerator value, can't be NULL or empty;
	1912	+ * - value - integer value corresponding to enum value name;
	1913	+ * Returns:
	1914	+ * - 0, on success;
	1915	+ * - <0, on error.
	1916	+ */
	1917	+int btf__add_enum_value(struct btf btf, const char name, __s64 value)
	1918	+{
	1919	+ struct btf_type *t;
	1920	+ struct btf_enum *v;
	1921	+ int sz, name_off;
	1922	+
	1923	+ /* last type should be BTF_KIND_ENUM */
	1924	+ if (btf->nr_types == 0)
	1925	+ return -EINVAL;
	1926	+ t = btf_type_by_id(btf, btf->nr_types);
	1927	+ if (!btf_is_enum(t))
	1928	+ return -EINVAL;
	1929	+
	1930	+ /* non-empty name */
	1931	+ if (!name \|\| !name[0])
	1932	+ return -EINVAL;
	1933	+ if (value < INT_MIN \|\| value > UINT_MAX)
	1934	+ return -E2BIG;
	1935	+
	1936	+ /* decompose and invalidate raw data */
	1937	+ if (btf_ensure_modifiable(btf))
	1938	+ return -ENOMEM;
	1939	+
	1940	+ sz = sizeof(struct btf_enum);
	1941	+ v = btf_add_type_mem(btf, sz);
	1942	+ if (!v)
	1943	+ return -ENOMEM;
	1944	+
	1945	+ name_off = btf__add_str(btf, name);
	1946	+ if (name_off < 0)
	1947	+ return name_off;
	1948	+
	1949	+ v->name_off = name_off;
	1950	+ v->val = value;
	1951	+
	1952	+ /* update parent type's vlen */
	1953	+ t = btf_type_by_id(btf, btf->nr_types);
	1954	+ btf_type_inc_vlen(t);
	1955	+
	1956	+ btf->hdr->type_len += sz;
	1957	+ btf->hdr->str_off += sz;
	1958	+ return 0;
	1959	+}
	1960	+
	1961	+/*
	1962	+ * Append new BTF_KIND_FWD type with:
	1963	+ * - name, non-empty/non-NULL name;
	1964	+ * - fwd_kind, kind of forward declaration, one of BTF_FWD_STRUCT,
	1965	+ * BTF_FWD_UNION, or BTF_FWD_ENUM;
	1966	+ * Returns:
	1967	+ * - >0, type ID of newly added BTF type;
	1968	+ * - <0, on error.
	1969	+ */
	1970	+int btf__add_fwd(struct btf btf, const char name, enum btf_fwd_kind fwd_kind)
	1971	+{
	1972	+ if (!name \|\| !name[0])
	1973	+ return -EINVAL;
	1974	+
	1975	+ switch (fwd_kind) {
	1976	+ case BTF_FWD_STRUCT:
	1977	+ case BTF_FWD_UNION: {
	1978	+ struct btf_type *t;
	1979	+ int id;
	1980	+
	1981	+ id = btf_add_ref_kind(btf, BTF_KIND_FWD, name, 0);
	1982	+ if (id <= 0)
	1983	+ return id;
	1984	+ t = btf_type_by_id(btf, id);
	1985	+ t->info = btf_type_info(BTF_KIND_FWD, 0, fwd_kind == BTF_FWD_UNION);
	1986	+ return id;
	1987	+ }
	1988	+ case BTF_FWD_ENUM:
	1989	+ /* enum forward in BTF currently is just an enum with no enum
	1990	+ * values; we also assume a standard 4-byte size for it
	1991	+ */
	1992	+ return btf__add_enum(btf, name, sizeof(int));
	1993	+ default:
	1994	+ return -EINVAL;
	1995	+ }
	1996	+}
	1997	+
	1998	+/*
	1999	+ * Append new BTF_KING_TYPEDEF type with:
	2000	+ * - name, non-empty/non-NULL name;
	2001	+ * - ref_type_id - referenced type ID, it might not exist yet;
	2002	+ * Returns:
	2003	+ * - >0, type ID of newly added BTF type;
	2004	+ * - <0, on error.
	2005	+ */
	2006	+int btf__add_typedef(struct btf btf, const char name, int ref_type_id)
	2007	+{
	2008	+ if (!name \|\| !name[0])
	2009	+ return -EINVAL;
	2010	+
	2011	+ return btf_add_ref_kind(btf, BTF_KIND_TYPEDEF, name, ref_type_id);
	2012	+}
	2013	+
	2014	+/*
	2015	+ * Append new BTF_KIND_VOLATILE type with:
	2016	+ * - ref_type_id - referenced type ID, it might not exist yet;
	2017	+ * Returns:
	2018	+ * - >0, type ID of newly added BTF type;
	2019	+ * - <0, on error.
	2020	+ */
	2021	+int btf__add_volatile(struct btf *btf, int ref_type_id)
	2022	+{
	2023	+ return btf_add_ref_kind(btf, BTF_KIND_VOLATILE, NULL, ref_type_id);
	2024	+}
	2025	+
	2026	+/*
	2027	+ * Append new BTF_KIND_CONST type with:
	2028	+ * - ref_type_id - referenced type ID, it might not exist yet;
	2029	+ * Returns:
	2030	+ * - >0, type ID of newly added BTF type;
	2031	+ * - <0, on error.
	2032	+ */
	2033	+int btf__add_const(struct btf *btf, int ref_type_id)
	2034	+{
	2035	+ return btf_add_ref_kind(btf, BTF_KIND_CONST, NULL, ref_type_id);
	2036	+}
	2037	+
	2038	+/*
	2039	+ * Append new BTF_KIND_RESTRICT type with:
	2040	+ * - ref_type_id - referenced type ID, it might not exist yet;
	2041	+ * Returns:
	2042	+ * - >0, type ID of newly added BTF type;
	2043	+ * - <0, on error.
	2044	+ */
	2045	+int btf__add_restrict(struct btf *btf, int ref_type_id)
	2046	+{
	2047	+ return btf_add_ref_kind(btf, BTF_KIND_RESTRICT, NULL, ref_type_id);
	2048	+}
	2049	+
	2050	+/*
	2051	+ * Append new BTF_KIND_FUNC type with:
	2052	+ * - name, non-empty/non-NULL name;
	2053	+ * - proto_type_id - FUNC_PROTO's type ID, it might not exist yet;
	2054	+ * Returns:
	2055	+ * - >0, type ID of newly added BTF type;
	2056	+ * - <0, on error.
	2057	+ */
	2058	+int btf__add_func(struct btf btf, const char name,
	2059	+ enum btf_func_linkage linkage, int proto_type_id)
	2060	+{
	2061	+ int id;
	2062	+
	2063	+ if (!name \|\| !name[0])
	2064	+ return -EINVAL;
	2065	+ if (linkage != BTF_FUNC_STATIC && linkage != BTF_FUNC_GLOBAL &&
	2066	+ linkage != BTF_FUNC_EXTERN)
	2067	+ return -EINVAL;
	2068	+
	2069	+ id = btf_add_ref_kind(btf, BTF_KIND_FUNC, name, proto_type_id);
	2070	+ if (id > 0) {
	2071	+ struct btf_type *t = btf_type_by_id(btf, id);
	2072	+
	2073	+ t->info = btf_type_info(BTF_KIND_FUNC, linkage, 0);
	2074	+ }
	2075	+ return id;
	2076	+}
	2077	+
	2078	+/*
	2079	+ * Append new BTF_KIND_FUNC_PROTO with:
	2080	+ * - ret_type_id - type ID for return result of a function.
	2081	+ *
	2082	+ * Function prototype initially has no arguments, but they can be added by
	2083	+ * btf__add_func_param() one by one, immediately after
	2084	+ * btf__add_func_proto() succeeded.
	2085	+ *
	2086	+ * Returns:
	2087	+ * - >0, type ID of newly added BTF type;
	2088	+ * - <0, on error.
	2089	+ */
	2090	+int btf__add_func_proto(struct btf *btf, int ret_type_id)
	2091	+{
	2092	+ struct btf_type *t;
	2093	+ int sz, err;
	2094	+
	2095	+ if (validate_type_id(ret_type_id))
	2096	+ return -EINVAL;
	2097	+
	2098	+ if (btf_ensure_modifiable(btf))
	2099	+ return -ENOMEM;
	2100	+
	2101	+ sz = sizeof(struct btf_type);
	2102	+ t = btf_add_type_mem(btf, sz);
	2103	+ if (!t)
	2104	+ return -ENOMEM;
	2105	+
	2106	+ /* start out with vlen=0; this will be adjusted when adding enum
	2107	+ * values, if necessary
	2108	+ */
	2109	+ t->name_off = 0;
	2110	+ t->info = btf_type_info(BTF_KIND_FUNC_PROTO, 0, 0);
	2111	+ t->type = ret_type_id;
	2112	+
	2113	+ err = btf_add_type_idx_entry(btf, btf->hdr->type_len);
	2114	+ if (err)
	2115	+ return err;
	2116	+
	2117	+ btf->hdr->type_len += sz;
	2118	+ btf->hdr->str_off += sz;
	2119	+ btf->nr_types++;
	2120	+ return btf->nr_types;
	2121	+}
	2122	+
	2123	+/*
	2124	+ * Append new function parameter for current FUNC_PROTO type with:
	2125	+ * - name - parameter name, can be NULL or empty;
	2126	+ * - type_id - type ID describing the type of the parameter.
	2127	+ * Returns:
	2128	+ * - 0, on success;
	2129	+ * - <0, on error.
	2130	+ */
	2131	+int btf__add_func_param(struct btf btf, const char name, int type_id)
	2132	+{
	2133	+ struct btf_type *t;
	2134	+ struct btf_param *p;
	2135	+ int sz, name_off = 0;
	2136	+
	2137	+ if (validate_type_id(type_id))
	2138	+ return -EINVAL;
	2139	+
	2140	+ /* last type should be BTF_KIND_FUNC_PROTO */
	2141	+ if (btf->nr_types == 0)
	2142	+ return -EINVAL;
	2143	+ t = btf_type_by_id(btf, btf->nr_types);
	2144	+ if (!btf_is_func_proto(t))
	2145	+ return -EINVAL;
	2146	+
	2147	+ /* decompose and invalidate raw data */
	2148	+ if (btf_ensure_modifiable(btf))
	2149	+ return -ENOMEM;
	2150	+
	2151	+ sz = sizeof(struct btf_param);
	2152	+ p = btf_add_type_mem(btf, sz);
	2153	+ if (!p)
	2154	+ return -ENOMEM;
	2155	+
	2156	+ if (name && name[0]) {
	2157	+ name_off = btf__add_str(btf, name);
	2158	+ if (name_off < 0)
	2159	+ return name_off;
	2160	+ }
	2161	+
	2162	+ p->name_off = name_off;
	2163	+ p->type = type_id;
	2164	+
	2165	+ /* update parent type's vlen */
	2166	+ t = btf_type_by_id(btf, btf->nr_types);
	2167	+ btf_type_inc_vlen(t);
	2168	+
	2169	+ btf->hdr->type_len += sz;
	2170	+ btf->hdr->str_off += sz;
	2171	+ return 0;
	2172	+}
	2173	+
	2174	+/*
	2175	+ * Append new BTF_KIND_VAR type with:
	2176	+ * - name - non-empty/non-NULL name;
	2177	+ * - linkage - variable linkage, one of BTF_VAR_STATIC,
	2178	+ * BTF_VAR_GLOBAL_ALLOCATED, or BTF_VAR_GLOBAL_EXTERN;
	2179	+ * - type_id - type ID of the type describing the type of the variable.
	2180	+ * Returns:
	2181	+ * - >0, type ID of newly added BTF type;
	2182	+ * - <0, on error.
	2183	+ */
	2184	+int btf__add_var(struct btf btf, const char name, int linkage, int type_id)
	2185	+{
	2186	+ struct btf_type *t;
	2187	+ struct btf_var *v;
	2188	+ int sz, err, name_off;
	2189	+
	2190	+ /* non-empty name */
	2191	+ if (!name \|\| !name[0])
	2192	+ return -EINVAL;
	2193	+ if (linkage != BTF_VAR_STATIC && linkage != BTF_VAR_GLOBAL_ALLOCATED &&
	2194	+ linkage != BTF_VAR_GLOBAL_EXTERN)
	2195	+ return -EINVAL;
	2196	+ if (validate_type_id(type_id))
	2197	+ return -EINVAL;
	2198	+
	2199	+ /* deconstruct BTF, if necessary, and invalidate raw_data */
	2200	+ if (btf_ensure_modifiable(btf))
	2201	+ return -ENOMEM;
	2202	+
	2203	+ sz = sizeof(struct btf_type) + sizeof(struct btf_var);
	2204	+ t = btf_add_type_mem(btf, sz);
	2205	+ if (!t)
	2206	+ return -ENOMEM;
	2207	+
	2208	+ name_off = btf__add_str(btf, name);
	2209	+ if (name_off < 0)
	2210	+ return name_off;
	2211	+
	2212	+ t->name_off = name_off;
	2213	+ t->info = btf_type_info(BTF_KIND_VAR, 0, 0);
	2214	+ t->type = type_id;
	2215	+
	2216	+ v = btf_var(t);
	2217	+ v->linkage = linkage;
	2218	+
	2219	+ err = btf_add_type_idx_entry(btf, btf->hdr->type_len);
	2220	+ if (err)
	2221	+ return err;
	2222	+
	2223	+ btf->hdr->type_len += sz;
	2224	+ btf->hdr->str_off += sz;
	2225	+ btf->nr_types++;
	2226	+ return btf->nr_types;
	2227	+}
	2228	+
	2229	+/*
	2230	+ * Append new BTF_KIND_DATASEC type with:
	2231	+ * - name - non-empty/non-NULL name;
	2232	+ * - byte_sz - data section size, in bytes.
	2233	+ *
	2234	+ * Data section is initially empty. Variables info can be added with
	2235	+ * btf__add_datasec_var_info() calls, after btf__add_datasec() succeeds.
	2236	+ *
	2237	+ * Returns:
	2238	+ * - >0, type ID of newly added BTF type;
	2239	+ * - <0, on error.
	2240	+ */
	2241	+int btf__add_datasec(struct btf btf, const char name, __u32 byte_sz)
	2242	+{
	2243	+ struct btf_type *t;
	2244	+ int sz, err, name_off;
	2245	+
	2246	+ /* non-empty name */
	2247	+ if (!name \|\| !name[0])
	2248	+ return -EINVAL;
	2249	+
	2250	+ if (btf_ensure_modifiable(btf))
	2251	+ return -ENOMEM;
	2252	+
	2253	+ sz = sizeof(struct btf_type);
	2254	+ t = btf_add_type_mem(btf, sz);
	2255	+ if (!t)
	2256	+ return -ENOMEM;
	2257	+
	2258	+ name_off = btf__add_str(btf, name);
	2259	+ if (name_off < 0)
	2260	+ return name_off;
	2261	+
	2262	+ /* start with vlen=0, which will be update as var_secinfos are added */
	2263	+ t->name_off = name_off;
	2264	+ t->info = btf_type_info(BTF_KIND_DATASEC, 0, 0);
	2265	+ t->size = byte_sz;
	2266	+
	2267	+ err = btf_add_type_idx_entry(btf, btf->hdr->type_len);
	2268	+ if (err)
	2269	+ return err;
	2270	+
	2271	+ btf->hdr->type_len += sz;
	2272	+ btf->hdr->str_off += sz;
	2273	+ btf->nr_types++;
	2274	+ return btf->nr_types;
	2275	+}
	2276	+
	2277	+/*
	2278	+ * Append new data section variable information entry for current DATASEC type:
	2279	+ * - var_type_id - type ID, describing type of the variable;
	2280	+ * - offset - variable offset within data section, in bytes;
	2281	+ * - byte_sz - variable size, in bytes.
	2282	+ *
	2283	+ * Returns:
	2284	+ * - 0, on success;
	2285	+ * - <0, on error.
	2286	+ */
	2287	+int btf__add_datasec_var_info(struct btf *btf, int var_type_id, __u32 offset, __u32 byte_sz)
	2288	+{
	2289	+ struct btf_type *t;
	2290	+ struct btf_var_secinfo *v;
	2291	+ int sz;
	2292	+
	2293	+ /* last type should be BTF_KIND_DATASEC */
	2294	+ if (btf->nr_types == 0)
	2295	+ return -EINVAL;
	2296	+ t = btf_type_by_id(btf, btf->nr_types);
	2297	+ if (!btf_is_datasec(t))
	2298	+ return -EINVAL;
	2299	+
	2300	+ if (validate_type_id(var_type_id))
	2301	+ return -EINVAL;
	2302	+
	2303	+ /* decompose and invalidate raw data */
	2304	+ if (btf_ensure_modifiable(btf))
	2305	+ return -ENOMEM;
	2306	+
	2307	+ sz = sizeof(struct btf_var_secinfo);
	2308	+ v = btf_add_type_mem(btf, sz);
	2309	+ if (!v)
	2310	+ return -ENOMEM;
	2311	+
	2312	+ v->type = var_type_id;
	2313	+ v->offset = offset;
	2314	+ v->size = byte_sz;
	2315	+
	2316	+ /* update parent type's vlen */
	2317	+ t = btf_type_by_id(btf, btf->nr_types);
	2318	+ btf_type_inc_vlen(t);
	2319	+
	2320	+ btf->hdr->type_len += sz;
	2321	+ btf->hdr->str_off += sz;
	2322	+ return 0;
	2323	+}
	2324	+
	2325	+struct btf_ext_sec_setup_param {
	2326	+ __u32 off;
	2327	+ __u32 len;
	2328	+ __u32 min_rec_size;
	2329	+ struct btf_ext_info *ext_info;
	2330	+ const char *desc;
	2331	+};
	2332	+
	2333	+static int btf_ext_setup_info(struct btf_ext *btf_ext,
	2334	+ struct btf_ext_sec_setup_param *ext_sec)
	2335	+{
	2336	+ const struct btf_ext_info_sec *sinfo;
	2337	+ struct btf_ext_info *ext_info;
	2338	+ __u32 info_left, record_size;
	2339	+ /* The start of the info sec (including the __u32 record_size). */
	2340	+ void *info;
	2341	+
	2342	+ if (ext_sec->len == 0)
	2343	+ return 0;
	2344	+
	2345	+ if (ext_sec->off & 0x03) {
	2346	+ pr_debug(".BTF.ext %s section is not aligned to 4 bytes\n",
	2347	+ ext_sec->desc);
	2348	+ return -EINVAL;
	2349	+ }
	2350	+
	2351	+ info = btf_ext->data + btf_ext->hdr->hdr_len + ext_sec->off;
	2352	+ info_left = ext_sec->len;
	2353	+
	2354	+ if (btf_ext->data + btf_ext->data_size < info + ext_sec->len) {
	2355	+ pr_debug("%s section (off:%u len:%u) is beyond the end of the ELF section .BTF.ext\n",
	2356	+ ext_sec->desc, ext_sec->off, ext_sec->len);
	2357	+ return -EINVAL;
	2358	+ }
	2359	+
	2360	+ /* At least a record size */
	2361	+ if (info_left < sizeof(__u32)) {
	2362	+ pr_debug(".BTF.ext %s record size not found\n", ext_sec->desc);
	2363	+ return -EINVAL;
	2364	+ }
	2365	+
	2366	+ /* The record size needs to meet the minimum standard */
	2367	+ record_size = (__u32 )info;
	2368	+ if (record_size < ext_sec->min_rec_size \|\|
	2369	+ record_size & 0x03) {
	2370	+ pr_debug("%s section in .BTF.ext has invalid record size %u\n",
	2371	+ ext_sec->desc, record_size);
	2372	+ return -EINVAL;
	2373	+ }
	2374	+
	2375	+ sinfo = info + sizeof(__u32);
	2376	+ info_left -= sizeof(__u32);
	2377	+
	2378	+ /* If no records, return failure now so .BTF.ext won't be used. */
	2379	+ if (!info_left) {
	2380	+ pr_debug("%s section in .BTF.ext has no records", ext_sec->desc);
	2381	+ return -EINVAL;
	2382	+ }
	2383	+
	2384	+ while (info_left) {
	2385	+ unsigned int sec_hdrlen = sizeof(struct btf_ext_info_sec);
	2386	+ __u64 total_record_size;
	2387	+ __u32 num_records;
	2388	+
	2389	+ if (info_left < sec_hdrlen) {
	2390	+ pr_debug("%s section header is not found in .BTF.ext\n",
	2391	+ ext_sec->desc);
	2392	+ return -EINVAL;
	2393	+ }
	2394	+
	2395	+ num_records = sinfo->num_info;
	2396	+ if (num_records == 0) {
	2397	+ pr_debug("%s section has incorrect num_records in .BTF.ext\n",
	2398	+ ext_sec->desc);
	2399	+ return -EINVAL;
	2400	+ }
	2401	+
	2402	+ total_record_size = sec_hdrlen +
	2403	+ (__u64)num_records * record_size;
	2404	+ if (info_left < total_record_size) {
	2405	+ pr_debug("%s section has incorrect num_records in .BTF.ext\n",
	2406	+ ext_sec->desc);
	2407	+ return -EINVAL;
	2408	+ }
	2409	+
	2410	+ info_left -= total_record_size;
	2411	+ sinfo = (void *)sinfo + total_record_size;
	2412	+ }
	2413	+
	2414	+ ext_info = ext_sec->ext_info;
	2415	+ ext_info->len = ext_sec->len - sizeof(__u32);
	2416	+ ext_info->rec_size = record_size;
	2417	+ ext_info->info = info + sizeof(__u32);
	2418	+
	2419	+ return 0;
	2420	+}
	2421	+
	2422	+static int btf_ext_setup_func_info(struct btf_ext *btf_ext)
	2423	+{
	2424	+ struct btf_ext_sec_setup_param param = {
	2425	+ .off = btf_ext->hdr->func_info_off,
	2426	+ .len = btf_ext->hdr->func_info_len,
	2427	+ .min_rec_size = sizeof(struct bpf_func_info_min),
	2428	+ .ext_info = &btf_ext->func_info,
	2429	+ .desc = "func_info"
	2430	+ };
	2431	+
	2432	+ return btf_ext_setup_info(btf_ext, &param);
	2433	+}
	2434	+
	2435	+static int btf_ext_setup_line_info(struct btf_ext *btf_ext)
	2436	+{
	2437	+ struct btf_ext_sec_setup_param param = {
	2438	+ .off = btf_ext->hdr->line_info_off,
	2439	+ .len = btf_ext->hdr->line_info_len,
	2440	+ .min_rec_size = sizeof(struct bpf_line_info_min),
	2441	+ .ext_info = &btf_ext->line_info,
	2442	+ .desc = "line_info",
	2443	+ };
	2444	+
	2445	+ return btf_ext_setup_info(btf_ext, &param);
	2446	+}
	2447	+
	2448	+static int btf_ext_setup_core_relos(struct btf_ext *btf_ext)
	2449	+{
	2450	+ struct btf_ext_sec_setup_param param = {
	2451	+ .off = btf_ext->hdr->core_relo_off,
	2452	+ .len = btf_ext->hdr->core_relo_len,
	2453	+ .min_rec_size = sizeof(struct bpf_core_relo),
	2454	+ .ext_info = &btf_ext->core_relo_info,
	2455	+ .desc = "core_relo",
	2456	+ };
	2457	+
	2458	+ return btf_ext_setup_info(btf_ext, &param);
	2459	+}
	2460	+
	2461	+static int btf_ext_parse_hdr(__u8 *data, __u32 data_size)
	2462	+{
	2463	+ const struct btf_ext_header hdr = (struct btf_ext_header )data;
	2464	+
	2465	+ if (data_size < offsetofend(struct btf_ext_header, hdr_len) \|\|
	2466	+ data_size < hdr->hdr_len) {
	2467	+ pr_debug("BTF.ext header not found");
	2468	+ return -EINVAL;
	2469	+ }
	2470	+
	2471	+ if (hdr->magic == bswap_16(BTF_MAGIC)) {
	2472	+ pr_warn("BTF.ext in non-native endianness is not supported\n");
	2473	+ return -ENOTSUP;
	2474	+ } else if (hdr->magic != BTF_MAGIC) {
	2475	+ pr_debug("Invalid BTF.ext magic:%x\n", hdr->magic);
	2476	+ return -EINVAL;
	2477	+ }
	2478	+
	2479	+ if (hdr->version != BTF_VERSION) {
	2480	+ pr_debug("Unsupported BTF.ext version:%u\n", hdr->version);
	2481	+ return -ENOTSUP;
	2482	+ }
	2483	+
	2484	+ if (hdr->flags) {
	2485	+ pr_debug("Unsupported BTF.ext flags:%x\n", hdr->flags);
	2486	+ return -ENOTSUP;
	2487	+ }
	2488	+
	2489	+ if (data_size == hdr->hdr_len) {
	2490	+ pr_debug("BTF.ext has no data\n");
	2491	+ return -EINVAL;
	2492	+ }
	2493	+
	2494	+ return 0;
	2495	+}
	2496	+
	2497	+void btf_ext__free(struct btf_ext *btf_ext)
	2498	+{
	2499	+ if (IS_ERR_OR_NULL(btf_ext))
	2500	+ return;
	2501	+ free(btf_ext->data);
	2502	+ free(btf_ext);
	2503	+}
	2504	+
	2505	+struct btf_ext btf_ext__new(__u8 data, __u32 size)
	2506	+{
	2507	+ struct btf_ext *btf_ext;
	2508	+ int err;
	2509	+
	2510	+ err = btf_ext_parse_hdr(data, size);
	2511	+ if (err)
	2512	+ return ERR_PTR(err);
	2513	+
	2514	+ btf_ext = calloc(1, sizeof(struct btf_ext));
	2515	+ if (!btf_ext)
	2516	+ return ERR_PTR(-ENOMEM);
	2517	+
	2518	+ btf_ext->data_size = size;
	2519	+ btf_ext->data = malloc(size);
	2520	+ if (!btf_ext->data) {
	2521	+ err = -ENOMEM;
	2522	+ goto done;
	2523	+ }
	2524	+ memcpy(btf_ext->data, data, size);
	2525	+
	2526	+ if (btf_ext->hdr->hdr_len <
	2527	+ offsetofend(struct btf_ext_header, line_info_len))
	2528	+ goto done;
	2529	+ err = btf_ext_setup_func_info(btf_ext);
	2530	+ if (err)
	2531	+ goto done;
	2532	+
	2533	+ err = btf_ext_setup_line_info(btf_ext);
	2534	+ if (err)
	2535	+ goto done;
	2536	+
	2537	+ if (btf_ext->hdr->hdr_len < offsetofend(struct btf_ext_header, core_relo_len))
	2538	+ goto done;
	2539	+ err = btf_ext_setup_core_relos(btf_ext);
	2540	+ if (err)
	2541	+ goto done;
	2542	+
	2543	+done:
	2544	+ if (err) {
	2545	+ btf_ext__free(btf_ext);
	2546	+ return ERR_PTR(err);
	2547	+ }
	2548	+
	2549	+ return btf_ext;
	2550	+}
	2551	+
	2552	+const void btf_ext__get_raw_data(const struct btf_ext btf_ext, __u32 *size)
	2553	+{
	2554	+ *size = btf_ext->data_size;
	2555	+ return btf_ext->data;
	2556	+}
	2557	+
	2558	+static int btf_ext_reloc_info(const struct btf *btf,
	2559	+ const struct btf_ext_info *ext_info,
	2560	+ const char *sec_name, __u32 insns_cnt,
	2561	+ void *info, __u32 cnt)
	2562	+{
	2563	+ __u32 sec_hdrlen = sizeof(struct btf_ext_info_sec);
	2564	+ __u32 i, record_size, existing_len, records_len;
	2565	+ struct btf_ext_info_sec *sinfo;
	2566	+ const char *info_sec_name;
	2567	+ __u64 remain_len;
	2568	+ void *data;
	2569	+
	2570	+ record_size = ext_info->rec_size;
	2571	+ sinfo = ext_info->info;
	2572	+ remain_len = ext_info->len;
	2573	+ while (remain_len > 0) {
	2574	+ records_len = sinfo->num_info * record_size;
	2575	+ info_sec_name = btf__name_by_offset(btf, sinfo->sec_name_off);
	2576	+ if (strcmp(info_sec_name, sec_name)) {
	2577	+ remain_len -= sec_hdrlen + records_len;
	2578	+ sinfo = (void *)sinfo + sec_hdrlen + records_len;
	2579	+ continue;
	2580	+ }
	2581	+
	2582	+ existing_len = (cnt) record_size;
	2583	+ data = realloc(*info, existing_len + records_len);
	2584	+ if (!data)
	2585	+ return -ENOMEM;
	2586	+
	2587	+ memcpy(data + existing_len, sinfo->data, records_len);
	2588	+ /* adjust insn_off only, the rest data will be passed
	2589	+ * to the kernel.
	2590	+ */
	2591	+ for (i = 0; i < sinfo->num_info; i++) {
	2592	+ __u32 *insn_off;
	2593	+
	2594	+ insn_off = data + existing_len + (i * record_size);
	2595	+ insn_off = insn_off / sizeof(struct bpf_insn) +
	2596	+ insns_cnt;
	2597	+ }
	2598	+ *info = data;
	2599	+ *cnt += sinfo->num_info;
	2600	+ return 0;
	2601	+ }
	2602	+
	2603	+ return -ENOENT;
	2604	+}
	2605	+
	2606	+int btf_ext__reloc_func_info(const struct btf *btf,
	2607	+ const struct btf_ext *btf_ext,
	2608	+ const char *sec_name, __u32 insns_cnt,
	2609	+ void *func_info, __u32 cnt)
	2610	+{
	2611	+ return btf_ext_reloc_info(btf, &btf_ext->func_info, sec_name,
	2612	+ insns_cnt, func_info, cnt);
	2613	+}
	2614	+
	2615	+int btf_ext__reloc_line_info(const struct btf *btf,
	2616	+ const struct btf_ext *btf_ext,
	2617	+ const char *sec_name, __u32 insns_cnt,
	2618	+ void *line_info, __u32 cnt)
	2619	+{
	2620	+ return btf_ext_reloc_info(btf, &btf_ext->line_info, sec_name,
	2621	+ insns_cnt, line_info, cnt);
	2622	+}
	2623	+
	2624	+__u32 btf_ext__func_info_rec_size(const struct btf_ext *btf_ext)
	2625	+{
	2626	+ return btf_ext->func_info.rec_size;
	2627	+}
	2628	+
	2629	+__u32 btf_ext__line_info_rec_size(const struct btf_ext *btf_ext)
	2630	+{
	2631	+ return btf_ext->line_info.rec_size;
	2632	+}
	2633	+
	2634	+struct btf_dedup;
	2635	+
	2636	+static struct btf_dedup btf_dedup_new(struct btf btf, struct btf_ext *btf_ext,
	2637	+ const struct btf_dedup_opts *opts);
	2638	+static void btf_dedup_free(struct btf_dedup *d);
	2639	+static int btf_dedup_strings(struct btf_dedup *d);
	2640	+static int btf_dedup_prim_types(struct btf_dedup *d);
	2641	+static int btf_dedup_struct_types(struct btf_dedup *d);
	2642	+static int btf_dedup_ref_types(struct btf_dedup *d);
	2643	+static int btf_dedup_compact_types(struct btf_dedup *d);
	2644	+static int btf_dedup_remap_types(struct btf_dedup *d);
	2645	+
	2646	+/*
	2647	+ * Deduplicate BTF types and strings.
	2648	+ *
	2649	+ * BTF dedup algorithm takes as an input `struct btf` representing `.BTF` ELF
	2650	+ * section with all BTF type descriptors and string data. It overwrites that
	2651	+ * memory in-place with deduplicated types and strings without any loss of
	2652	+ * information. If optional `struct btf_ext` representing '.BTF.ext' ELF section
	2653	+ * is provided, all the strings referenced from .BTF.ext section are honored
	2654	+ * and updated to point to the right offsets after deduplication.
	2655	+ *
	2656	+ * If function returns with error, type/string data might be garbled and should
	2657	+ * be discarded.
	2658	+ *
	2659	+ * More verbose and detailed description of both problem btf_dedup is solving,
	2660	+ * as well as solution could be found at:
	2661	+ * https://facebookmicrosites.github.io/bpf/blog/2018/11/14/btf-enhancement.html
	2662	+ *
	2663	+ * Problem description and justification
	2664	+ * =====================================
	2665	+ *
	2666	+ * BTF type information is typically emitted either as a result of conversion
	2667	+ * from DWARF to BTF or directly by compiler. In both cases, each compilation
	2668	+ * unit contains information about a subset of all the types that are used
	2669	+ * in an application. These subsets are frequently overlapping and contain a lot
	2670	+ * of duplicated information when later concatenated together into a single
	2671	+ * binary. This algorithm ensures that each unique type is represented by single
	2672	+ * BTF type descriptor, greatly reducing resulting size of BTF data.
	2673	+ *
	2674	+ * Compilation unit isolation and subsequent duplication of data is not the only
	2675	+ * problem. The same type hierarchy (e.g., struct and all the type that struct
	2676	+ * references) in different compilation units can be represented in BTF to
	2677	+ * various degrees of completeness (or, rather, incompleteness) due to
	2678	+ * struct/union forward declarations.
	2679	+ *
	2680	+ * Let's take a look at an example, that we'll use to better understand the
	2681	+ * problem (and solution). Suppose we have two compilation units, each using
	2682	+ * same `struct S`, but each of them having incomplete type information about
	2683	+ * struct's fields:
	2684	+ *
	2685	+ * // CU #1:
	2686	+ * struct S;
	2687	+ * struct A {
	2688	+ * int a;
	2689	+ * struct A* self;
	2690	+ * struct S* parent;
	2691	+ * };
	2692	+ * struct B;
	2693	+ * struct S {
	2694	+ * struct A* a_ptr;
	2695	+ * struct B* b_ptr;
	2696	+ * };
	2697	+ *
	2698	+ * // CU #2:
	2699	+ * struct S;
	2700	+ * struct A;
	2701	+ * struct B {
	2702	+ * int b;
	2703	+ * struct B* self;
	2704	+ * struct S* parent;
	2705	+ * };
	2706	+ * struct S {
	2707	+ * struct A* a_ptr;
	2708	+ * struct B* b_ptr;
	2709	+ * };
	2710	+ *
	2711	+ * In case of CU #1, BTF data will know only that `struct B` exist (but no
	2712	+ * more), but will know the complete type information about `struct A`. While
	2713	+ * for CU #2, it will know full type information about `struct B`, but will
	2714	+ * only know about forward declaration of `struct A` (in BTF terms, it will
	2715	+ * have `BTF_KIND_FWD` type descriptor with name `B`).
	2716	+ *
	2717	+ * This compilation unit isolation means that it's possible that there is no
	2718	+ * single CU with complete type information describing structs `S`, `A`, and
	2719	+ * `B`. Also, we might get tons of duplicated and redundant type information.
	2720	+ *
	2721	+ * Additional complication we need to keep in mind comes from the fact that
	2722	+ * types, in general, can form graphs containing cycles, not just DAGs.
	2723	+ *
	2724	+ * While algorithm does deduplication, it also merges and resolves type
	2725	+ * information (unless disabled throught `struct btf_opts`), whenever possible.
	2726	+ * E.g., in the example above with two compilation units having partial type
	2727	+ * information for structs `A` and `B`, the output of algorithm will emit
	2728	+ * a single copy of each BTF type that describes structs `A`, `B`, and `S`
	2729	+ * (as well as type information for `int` and pointers), as if they were defined
	2730	+ * in a single compilation unit as:
	2731	+ *
	2732	+ * struct A {
	2733	+ * int a;
	2734	+ * struct A* self;
	2735	+ * struct S* parent;
	2736	+ * };
	2737	+ * struct B {
	2738	+ * int b;
	2739	+ * struct B* self;
	2740	+ * struct S* parent;
	2741	+ * };
	2742	+ * struct S {
	2743	+ * struct A* a_ptr;
	2744	+ * struct B* b_ptr;
	2745	+ * };
	2746	+ *
	2747	+ * Algorithm summary
	2748	+ * =================
	2749	+ *
	2750	+ * Algorithm completes its work in 6 separate passes:
	2751	+ *
	2752	+ * 1. Strings deduplication.
	2753	+ * 2. Primitive types deduplication (int, enum, fwd).
	2754	+ * 3. Struct/union types deduplication.
	2755	+ * 4. Reference types deduplication (pointers, typedefs, arrays, funcs, func
	2756	+ * protos, and const/volatile/restrict modifiers).
	2757	+ * 5. Types compaction.
	2758	+ * 6. Types remapping.
	2759	+ *
	2760	+ * Algorithm determines canonical type descriptor, which is a single
	2761	+ * representative type for each truly unique type. This canonical type is the
	2762	+ * one that will go into final deduplicated BTF type information. For
	2763	+ * struct/unions, it is also the type that algorithm will merge additional type
	2764	+ * information into (while resolving FWDs), as it discovers it from data in
	2765	+ * other CUs. Each input BTF type eventually gets either mapped to itself, if
	2766	+ * that type is canonical, or to some other type, if that type is equivalent
	2767	+ * and was chosen as canonical representative. This mapping is stored in
	2768	+ * `btf_dedup->map` array. This map is also used to record STRUCT/UNION that
	2769	+ * FWD type got resolved to.
	2770	+ *
	2771	+ * To facilitate fast discovery of canonical types, we also maintain canonical
	2772	+ * index (`btf_dedup->dedup_table`), which maps type descriptor's signature hash
	2773	+ * (i.e., hashed kind, name, size, fields, etc) into a list of canonical types
	2774	+ * that match that signature. With sufficiently good choice of type signature
	2775	+ * hashing function, we can limit number of canonical types for each unique type
	2776	+ * signature to a very small number, allowing to find canonical type for any
	2777	+ * duplicated type very quickly.
	2778	+ *
	2779	+ * Struct/union deduplication is the most critical part and algorithm for
	2780	+ * deduplicating structs/unions is described in greater details in comments for
	2781	+ * `btf_dedup_is_equiv` function.
	2782	+ */
	2783	+int btf__dedup(struct btf btf, struct btf_ext btf_ext,
	2784	+ const struct btf_dedup_opts *opts)
	2785	+{
	2786	+ struct btf_dedup *d = btf_dedup_new(btf, btf_ext, opts);
	2787	+ int err;
	2788	+
	2789	+ if (IS_ERR(d)) {
	2790	+ pr_debug("btf_dedup_new failed: %ld", PTR_ERR(d));
	2791	+ return -EINVAL;
	2792	+ }
	2793	+
	2794	+ if (btf_ensure_modifiable(btf))
	2795	+ return -ENOMEM;
	2796	+
	2797	+ err = btf_dedup_strings(d);
	2798	+ if (err < 0) {
	2799	+ pr_debug("btf_dedup_strings failed:%d\n", err);
	2800	+ goto done;
	2801	+ }
	2802	+ err = btf_dedup_prim_types(d);
	2803	+ if (err < 0) {
	2804	+ pr_debug("btf_dedup_prim_types failed:%d\n", err);
	2805	+ goto done;
	2806	+ }
	2807	+ err = btf_dedup_struct_types(d);
	2808	+ if (err < 0) {
	2809	+ pr_debug("btf_dedup_struct_types failed:%d\n", err);
	2810	+ goto done;
	2811	+ }
	2812	+ err = btf_dedup_ref_types(d);
	2813	+ if (err < 0) {
	2814	+ pr_debug("btf_dedup_ref_types failed:%d\n", err);
	2815	+ goto done;
	2816	+ }
	2817	+ err = btf_dedup_compact_types(d);
	2818	+ if (err < 0) {
	2819	+ pr_debug("btf_dedup_compact_types failed:%d\n", err);
	2820	+ goto done;
	2821	+ }
	2822	+ err = btf_dedup_remap_types(d);
	2823	+ if (err < 0) {
	2824	+ pr_debug("btf_dedup_remap_types failed:%d\n", err);
	2825	+ goto done;
	2826	+ }
	2827	+
	2828	+done:
	2829	+ btf_dedup_free(d);
	2830	+ return err;
	2831	+}
	2832	+
	2833	+#define BTF_UNPROCESSED_ID ((__u32)-1)
	2834	+#define BTF_IN_PROGRESS_ID ((__u32)-2)
	2835	+
	2836	+struct btf_dedup {
	2837	+ /* .BTF section to be deduped in-place */
	2838	+ struct btf *btf;
	2839	+ /*
	2840	+ * Optional .BTF.ext section. When provided, any strings referenced
	2841	+ * from it will be taken into account when deduping strings
	2842	+ */
	2843	+ struct btf_ext *btf_ext;
	2844	+ /*
	2845	+ * This is a map from any type's signature hash to a list of possible
	2846	+ * canonical representative type candidates. Hash collisions are
	2847	+ * ignored, so even types of various kinds can share same list of
	2848	+ * candidates, which is fine because we rely on subsequent
	2849	+ * btf_xxx_equal() checks to authoritatively verify type equality.
	2850	+ */
	2851	+ struct hashmap *dedup_table;
	2852	+ /* Canonical types map */
	2853	+ __u32 *map;
	2854	+ /* Hypothetical mapping, used during type graph equivalence checks */
	2855	+ __u32 *hypot_map;
	2856	+ __u32 *hypot_list;
	2857	+ size_t hypot_cnt;
	2858	+ size_t hypot_cap;
	2859	+ /* Various option modifying behavior of algorithm */
	2860	+ struct btf_dedup_opts opts;
	2861	+};
	2862	+
	2863	+struct btf_str_ptr {
	2864	+ const char *str;
	2865	+ __u32 new_off;
	2866	+ bool used;
	2867	+};
	2868	+
	2869	+struct btf_str_ptrs {
	2870	+ struct btf_str_ptr *ptrs;
	2871	+ const char *data;
	2872	+ __u32 cnt;
	2873	+ __u32 cap;
	2874	+};
	2875	+
	2876	+static long hash_combine(long h, long value)
	2877	+{
	2878	+ return h * 31 + value;
	2879	+}
	2880	+
	2881	+#define for_each_dedup_cand(d, node, hash) \
	2882	+ hashmap__for_each_key_entry(d->dedup_table, node, (void *)hash)
	2883	+
	2884	+static int btf_dedup_table_add(struct btf_dedup *d, long hash, __u32 type_id)
	2885	+{
	2886	+ return hashmap__append(d->dedup_table,
	2887	+ (void )hash, (void )(long)type_id);
	2888	+}
	2889	+
	2890	+static int btf_dedup_hypot_map_add(struct btf_dedup *d,
	2891	+ __u32 from_id, __u32 to_id)
	2892	+{
	2893	+ if (d->hypot_cnt == d->hypot_cap) {
	2894	+ __u32 *new_list;
	2895	+
	2896	+ d->hypot_cap += max((size_t)16, d->hypot_cap / 2);
	2897	+ new_list = libbpf_reallocarray(d->hypot_list, d->hypot_cap, sizeof(__u32));
	2898	+ if (!new_list)
	2899	+ return -ENOMEM;
	2900	+ d->hypot_list = new_list;
	2901	+ }
	2902	+ d->hypot_list[d->hypot_cnt++] = from_id;
	2903	+ d->hypot_map[from_id] = to_id;
	2904	+ return 0;
	2905	+}
	2906	+
	2907	+static void btf_dedup_clear_hypot_map(struct btf_dedup *d)
	2908	+{
	2909	+ int i;
	2910	+
	2911	+ for (i = 0; i < d->hypot_cnt; i++)
	2912	+ d->hypot_map[d->hypot_list[i]] = BTF_UNPROCESSED_ID;
	2913	+ d->hypot_cnt = 0;
	2914	+}
	2915	+
	2916	+static void btf_dedup_free(struct btf_dedup *d)
	2917	+{
	2918	+ hashmap__free(d->dedup_table);
	2919	+ d->dedup_table = NULL;
	2920	+
	2921	+ free(d->map);
	2922	+ d->map = NULL;
	2923	+
	2924	+ free(d->hypot_map);
	2925	+ d->hypot_map = NULL;
	2926	+
	2927	+ free(d->hypot_list);
	2928	+ d->hypot_list = NULL;
	2929	+
	2930	+ free(d);
	2931	+}
	2932	+
	2933	+static size_t btf_dedup_identity_hash_fn(const void key, void ctx)
	2934	+{
	2935	+ return (size_t)key;
	2936	+}
	2937	+
	2938	+static size_t btf_dedup_collision_hash_fn(const void key, void ctx)
	2939	+{
	2940	+ return 0;
	2941	+}
	2942	+
	2943	+static bool btf_dedup_equal_fn(const void k1, const void k2, void *ctx)
	2944	+{
	2945	+ return k1 == k2;
	2946	+}
	2947	+
	2948	+static struct btf_dedup btf_dedup_new(struct btf btf, struct btf_ext *btf_ext,
	2949	+ const struct btf_dedup_opts *opts)
	2950	+{
	2951	+ struct btf_dedup *d = calloc(1, sizeof(struct btf_dedup));
	2952	+ hashmap_hash_fn hash_fn = btf_dedup_identity_hash_fn;
	2953	+ int i, err = 0;
	2954	+
	2955	+ if (!d)
	2956	+ return ERR_PTR(-ENOMEM);
	2957	+
	2958	+ d->opts.dont_resolve_fwds = opts && opts->dont_resolve_fwds;
	2959	+ /* dedup_table_size is now used only to force collisions in tests */
	2960	+ if (opts && opts->dedup_table_size == 1)
	2961	+ hash_fn = btf_dedup_collision_hash_fn;
	2962	+
	2963	+ d->btf = btf;
	2964	+ d->btf_ext = btf_ext;
	2965	+
	2966	+ d->dedup_table = hashmap__new(hash_fn, btf_dedup_equal_fn, NULL);
	2967	+ if (IS_ERR(d->dedup_table)) {
	2968	+ err = PTR_ERR(d->dedup_table);
	2969	+ d->dedup_table = NULL;
	2970	+ goto done;
	2971	+ }
	2972	+
	2973	+ d->map = malloc(sizeof(__u32) * (1 + btf->nr_types));
	2974	+ if (!d->map) {
	2975	+ err = -ENOMEM;
	2976	+ goto done;
	2977	+ }
	2978	+ /* special BTF "void" type is made canonical immediately */
	2979	+ d->map[0] = 0;
	2980	+ for (i = 1; i <= btf->nr_types; i++) {
	2981	+ struct btf_type *t = btf_type_by_id(d->btf, i);
	2982	+
	2983	+ /* VAR and DATASEC are never deduped and are self-canonical */
	2984	+ if (btf_is_var(t) \|\| btf_is_datasec(t))
	2985	+ d->map[i] = i;
	2986	+ else
	2987	+ d->map[i] = BTF_UNPROCESSED_ID;
	2988	+ }
	2989	+
	2990	+ d->hypot_map = malloc(sizeof(__u32) * (1 + btf->nr_types));
	2991	+ if (!d->hypot_map) {
	2992	+ err = -ENOMEM;
	2993	+ goto done;
	2994	+ }
	2995	+ for (i = 0; i <= btf->nr_types; i++)
	2996	+ d->hypot_map[i] = BTF_UNPROCESSED_ID;
	2997	+
	2998	+done:
	2999	+ if (err) {
	3000	+ btf_dedup_free(d);
	3001	+ return ERR_PTR(err);
	3002	+ }
	3003	+
	3004	+ return d;
	3005	+}
	3006	+
	3007	+typedef int (str_off_fn_t)(__u32 str_off_ptr, void *ctx);
	3008	+
	3009	+/*
	3010	+ * Iterate over all possible places in .BTF and .BTF.ext that can reference
	3011	+ * string and pass pointer to it to a provided callback `fn`.
	3012	+ */
	3013	+static int btf_for_each_str_off(struct btf_dedup d, str_off_fn_t fn, void ctx)
	3014	+{
	3015	+ void line_data_cur, line_data_end;
	3016	+ int i, j, r, rec_size;
	3017	+ struct btf_type *t;
	3018	+
	3019	+ for (i = 1; i <= d->btf->nr_types; i++) {
	3020	+ t = btf_type_by_id(d->btf, i);
	3021	+ r = fn(&t->name_off, ctx);
	3022	+ if (r)
	3023	+ return r;
	3024	+
	3025	+ switch (btf_kind(t)) {
	3026	+ case BTF_KIND_STRUCT:
	3027	+ case BTF_KIND_UNION: {
	3028	+ struct btf_member *m = btf_members(t);
	3029	+ __u16 vlen = btf_vlen(t);
	3030	+
	3031	+ for (j = 0; j < vlen; j++) {
	3032	+ r = fn(&m->name_off, ctx);
	3033	+ if (r)
	3034	+ return r;
	3035	+ m++;
	3036	+ }
	3037	+ break;
	3038	+ }
	3039	+ case BTF_KIND_ENUM: {
	3040	+ struct btf_enum *m = btf_enum(t);
	3041	+ __u16 vlen = btf_vlen(t);
	3042	+
	3043	+ for (j = 0; j < vlen; j++) {
	3044	+ r = fn(&m->name_off, ctx);
	3045	+ if (r)
	3046	+ return r;
	3047	+ m++;
	3048	+ }
	3049	+ break;
	3050	+ }
	3051	+ case BTF_KIND_FUNC_PROTO: {
	3052	+ struct btf_param *m = btf_params(t);
	3053	+ __u16 vlen = btf_vlen(t);
	3054	+
	3055	+ for (j = 0; j < vlen; j++) {
	3056	+ r = fn(&m->name_off, ctx);
	3057	+ if (r)
	3058	+ return r;
	3059	+ m++;
	3060	+ }
	3061	+ break;
	3062	+ }
	3063	+ default:
	3064	+ break;
	3065	+ }
	3066	+ }
	3067	+
	3068	+ if (!d->btf_ext)
	3069	+ return 0;
	3070	+
	3071	+ line_data_cur = d->btf_ext->line_info.info;
	3072	+ line_data_end = d->btf_ext->line_info.info + d->btf_ext->line_info.len;
	3073	+ rec_size = d->btf_ext->line_info.rec_size;
	3074	+
	3075	+ while (line_data_cur < line_data_end) {
	3076	+ struct btf_ext_info_sec *sec = line_data_cur;
	3077	+ struct bpf_line_info_min *line_info;
	3078	+ __u32 num_info = sec->num_info;
	3079	+
	3080	+ r = fn(&sec->sec_name_off, ctx);
	3081	+ if (r)
	3082	+ return r;
	3083	+
	3084	+ line_data_cur += sizeof(struct btf_ext_info_sec);
	3085	+ for (i = 0; i < num_info; i++) {
	3086	+ line_info = line_data_cur;
	3087	+ r = fn(&line_info->file_name_off, ctx);
	3088	+ if (r)
	3089	+ return r;
	3090	+ r = fn(&line_info->line_off, ctx);
	3091	+ if (r)
	3092	+ return r;
	3093	+ line_data_cur += rec_size;
	3094	+ }
	3095	+ }
	3096	+
	3097	+ return 0;
	3098	+}
	3099	+
	3100	+static int str_sort_by_content(const void a1, const void a2)
	3101	+{
	3102	+ const struct btf_str_ptr *p1 = a1;
	3103	+ const struct btf_str_ptr *p2 = a2;
	3104	+
	3105	+ return strcmp(p1->str, p2->str);
	3106	+}
	3107	+
	3108	+static int str_sort_by_offset(const void a1, const void a2)
	3109	+{
	3110	+ const struct btf_str_ptr *p1 = a1;
	3111	+ const struct btf_str_ptr *p2 = a2;
	3112	+
	3113	+ if (p1->str != p2->str)
	3114	+ return p1->str < p2->str ? -1 : 1;
	3115	+ return 0;
	3116	+}
	3117	+
	3118	+static int btf_dedup_str_ptr_cmp(const void str_ptr, const void pelem)
	3119	+{
	3120	+ const struct btf_str_ptr *p = pelem;
	3121	+
	3122	+ if (str_ptr != p->str)
	3123	+ return (const char *)str_ptr < p->str ? -1 : 1;
	3124	+ return 0;
	3125	+}
	3126	+
	3127	+static int btf_str_mark_as_used(__u32 str_off_ptr, void ctx)
	3128	+{
	3129	+ struct btf_str_ptrs *strs;
	3130	+ struct btf_str_ptr *s;
	3131	+
	3132	+ if (*str_off_ptr == 0)
	3133	+ return 0;
	3134	+
	3135	+ strs = ctx;
	3136	+ s = bsearch(strs->data + *str_off_ptr, strs->ptrs, strs->cnt,
	3137	+ sizeof(struct btf_str_ptr), btf_dedup_str_ptr_cmp);
	3138	+ if (!s)
	3139	+ return -EINVAL;
	3140	+ s->used = true;
	3141	+ return 0;
	3142	+}
	3143	+
	3144	+static int btf_str_remap_offset(__u32 str_off_ptr, void ctx)
	3145	+{
	3146	+ struct btf_str_ptrs *strs;
	3147	+ struct btf_str_ptr *s;
	3148	+
	3149	+ if (*str_off_ptr == 0)
	3150	+ return 0;
	3151	+
	3152	+ strs = ctx;
	3153	+ s = bsearch(strs->data + *str_off_ptr, strs->ptrs, strs->cnt,
	3154	+ sizeof(struct btf_str_ptr), btf_dedup_str_ptr_cmp);
	3155	+ if (!s)
	3156	+ return -EINVAL;
	3157	+ *str_off_ptr = s->new_off;
	3158	+ return 0;
	3159	+}
	3160	+
	3161	+/*
	3162	+ * Dedup string and filter out those that are not referenced from either .BTF
	3163	+ * or .BTF.ext (if provided) sections.
	3164	+ *
	3165	+ * This is done by building index of all strings in BTF's string section,
	3166	+ * then iterating over all entities that can reference strings (e.g., type
	3167	+ * names, struct field names, .BTF.ext line info, etc) and marking corresponding
	3168	+ * strings as used. After that all used strings are deduped and compacted into
	3169	+ * sequential blob of memory and new offsets are calculated. Then all the string
	3170	+ * references are iterated again and rewritten using new offsets.
	3171	+ */
	3172	+static int btf_dedup_strings(struct btf_dedup *d)
	3173	+{
	3174	+ char *start = d->btf->strs_data;
	3175	+ char *end = start + d->btf->hdr->str_len;
	3176	+ char p = start, tmp_strs = NULL;
	3177	+ struct btf_str_ptrs strs = {
	3178	+ .cnt = 0,
	3179	+ .cap = 0,
	3180	+ .ptrs = NULL,
	3181	+ .data = start,
	3182	+ };
	3183	+ int i, j, err = 0, grp_idx;
	3184	+ bool grp_used;
	3185	+
	3186	+ if (d->btf->strs_deduped)
	3187	+ return 0;
	3188	+
	3189	+ /* build index of all strings */
	3190	+ while (p < end) {
	3191	+ if (strs.cnt + 1 > strs.cap) {
	3192	+ struct btf_str_ptr *new_ptrs;
	3193	+
	3194	+ strs.cap += max(strs.cnt / 2, 16U);
	3195	+ new_ptrs = libbpf_reallocarray(strs.ptrs, strs.cap, sizeof(strs.ptrs[0]));
	3196	+ if (!new_ptrs) {
	3197	+ err = -ENOMEM;
	3198	+ goto done;
	3199	+ }
	3200	+ strs.ptrs = new_ptrs;
	3201	+ }
	3202	+
	3203	+ strs.ptrs[strs.cnt].str = p;
	3204	+ strs.ptrs[strs.cnt].used = false;
	3205	+
	3206	+ p += strlen(p) + 1;
	3207	+ strs.cnt++;
	3208	+ }
	3209	+
	3210	+ /* temporary storage for deduplicated strings */
	3211	+ tmp_strs = malloc(d->btf->hdr->str_len);
	3212	+ if (!tmp_strs) {
	3213	+ err = -ENOMEM;
	3214	+ goto done;
	3215	+ }
	3216	+
	3217	+ /* mark all used strings */
	3218	+ strs.ptrs[0].used = true;
	3219	+ err = btf_for_each_str_off(d, btf_str_mark_as_used, &strs);
	3220	+ if (err)
	3221	+ goto done;
	3222	+
	3223	+ /* sort strings by context, so that we can identify duplicates */
	3224	+ qsort(strs.ptrs, strs.cnt, sizeof(strs.ptrs[0]), str_sort_by_content);
	3225	+
	3226	+ /*
	3227	+ * iterate groups of equal strings and if any instance in a group was
	3228	+ * referenced, emit single instance and remember new offset
	3229	+ */
	3230	+ p = tmp_strs;
	3231	+ grp_idx = 0;
	3232	+ grp_used = strs.ptrs[0].used;
	3233	+ /* iterate past end to avoid code duplication after loop */
	3234	+ for (i = 1; i <= strs.cnt; i++) {
	3235	+ /*
	3236	+ * when i == strs.cnt, we want to skip string comparison and go
	3237	+ * straight to handling last group of strings (otherwise we'd
	3238	+ * need to handle last group after the loop w/ duplicated code)
	3239	+ */
	3240	+ if (i < strs.cnt &&
	3241	+ !strcmp(strs.ptrs[i].str, strs.ptrs[grp_idx].str)) {
	3242	+ grp_used = grp_used \|\| strs.ptrs[i].used;
	3243	+ continue;
	3244	+ }
	3245	+
	3246	+ /*
	3247	+ * this check would have been required after the loop to handle
	3248	+ * last group of strings, but due to <= condition in a loop
	3249	+ * we avoid that duplication
	3250	+ */
	3251	+ if (grp_used) {
	3252	+ int new_off = p - tmp_strs;
	3253	+ __u32 len = strlen(strs.ptrs[grp_idx].str);
	3254	+
	3255	+ memmove(p, strs.ptrs[grp_idx].str, len + 1);
	3256	+ for (j = grp_idx; j < i; j++)
	3257	+ strs.ptrs[j].new_off = new_off;
	3258	+ p += len + 1;
	3259	+ }
	3260	+
	3261	+ if (i < strs.cnt) {
	3262	+ grp_idx = i;
	3263	+ grp_used = strs.ptrs[i].used;
	3264	+ }
	3265	+ }
	3266	+
	3267	+ /* replace original strings with deduped ones */
	3268	+ d->btf->hdr->str_len = p - tmp_strs;
	3269	+ memmove(start, tmp_strs, d->btf->hdr->str_len);
	3270	+ end = start + d->btf->hdr->str_len;
	3271	+
	3272	+ /* restore original order for further binary search lookups */
	3273	+ qsort(strs.ptrs, strs.cnt, sizeof(strs.ptrs[0]), str_sort_by_offset);
	3274	+
	3275	+ /* remap string offsets */
	3276	+ err = btf_for_each_str_off(d, btf_str_remap_offset, &strs);
	3277	+ if (err)
	3278	+ goto done;
	3279	+
	3280	+ d->btf->hdr->str_len = end - start;
	3281	+ d->btf->strs_deduped = true;
	3282	+
	3283	+done:
	3284	+ free(tmp_strs);
	3285	+ free(strs.ptrs);
	3286	+ return err;
	3287	+}
	3288	+
	3289	+static long btf_hash_common(struct btf_type *t)
	3290	+{
	3291	+ long h;
	3292	+
	3293	+ h = hash_combine(0, t->name_off);
	3294	+ h = hash_combine(h, t->info);
	3295	+ h = hash_combine(h, t->size);
	3296	+ return h;
	3297	+}
	3298	+
	3299	+static bool btf_equal_common(struct btf_type t1, struct btf_type t2)
	3300	+{
	3301	+ return t1->name_off == t2->name_off &&
	3302	+ t1->info == t2->info &&
	3303	+ t1->size == t2->size;
	3304	+}
	3305	+
	3306	+/* Calculate type signature hash of INT. */
	3307	+static long btf_hash_int(struct btf_type *t)
	3308	+{
	3309	+ __u32 info = (__u32 )(t + 1);
	3310	+ long h;
	3311	+
	3312	+ h = btf_hash_common(t);
	3313	+ h = hash_combine(h, info);
	3314	+ return h;
	3315	+}
	3316	+
	3317	+/* Check structural equality of two INTs. */
	3318	+static bool btf_equal_int(struct btf_type t1, struct btf_type t2)
	3319	+{
	3320	+ __u32 info1, info2;
	3321	+
	3322	+ if (!btf_equal_common(t1, t2))
	3323	+ return false;
	3324	+ info1 = (__u32 )(t1 + 1);
	3325	+ info2 = (__u32 )(t2 + 1);
	3326	+ return info1 == info2;
	3327	+}
	3328	+
	3329	+/* Calculate type signature hash of ENUM. */
	3330	+static long btf_hash_enum(struct btf_type *t)
	3331	+{
	3332	+ long h;
	3333	+
	3334	+ /* don't hash vlen and enum members to support enum fwd resolving */
	3335	+ h = hash_combine(0, t->name_off);
	3336	+ h = hash_combine(h, t->info & ~0xffff);
	3337	+ h = hash_combine(h, t->size);
	3338	+ return h;
	3339	+}
	3340	+
	3341	+/* Check structural equality of two ENUMs. */
	3342	+static bool btf_equal_enum(struct btf_type t1, struct btf_type t2)
	3343	+{
	3344	+ const struct btf_enum m1, m2;
	3345	+ __u16 vlen;
	3346	+ int i;
	3347	+
	3348	+ if (!btf_equal_common(t1, t2))
	3349	+ return false;
	3350	+
	3351	+ vlen = btf_vlen(t1);
	3352	+ m1 = btf_enum(t1);
	3353	+ m2 = btf_enum(t2);
	3354	+ for (i = 0; i < vlen; i++) {
	3355	+ if (m1->name_off != m2->name_off \|\| m1->val != m2->val)
	3356	+ return false;
	3357	+ m1++;
	3358	+ m2++;
	3359	+ }
	3360	+ return true;
	3361	+}
	3362	+
	3363	+static inline bool btf_is_enum_fwd(struct btf_type *t)
	3364	+{
	3365	+ return btf_is_enum(t) && btf_vlen(t) == 0;
	3366	+}
	3367	+
	3368	+static bool btf_compat_enum(struct btf_type t1, struct btf_type t2)
	3369	+{
	3370	+ if (!btf_is_enum_fwd(t1) && !btf_is_enum_fwd(t2))
	3371	+ return btf_equal_enum(t1, t2);
	3372	+ /* ignore vlen when comparing */
	3373	+ return t1->name_off == t2->name_off &&
	3374	+ (t1->info & ~0xffff) == (t2->info & ~0xffff) &&
	3375	+ t1->size == t2->size;
	3376	+}
	3377	+
	3378	+/*
	3379	+ * Calculate type signature hash of STRUCT/UNION, ignoring referenced type IDs,
	3380	+ * as referenced type IDs equivalence is established separately during type
	3381	+ * graph equivalence check algorithm.
	3382	+ */
	3383	+static long btf_hash_struct(struct btf_type *t)
	3384	+{
	3385	+ const struct btf_member *member = btf_members(t);
	3386	+ __u32 vlen = btf_vlen(t);
	3387	+ long h = btf_hash_common(t);
	3388	+ int i;
	3389	+
	3390	+ for (i = 0; i < vlen; i++) {
	3391	+ h = hash_combine(h, member->name_off);
	3392	+ h = hash_combine(h, member->offset);
	3393	+ /* no hashing of referenced type ID, it can be unresolved yet */
	3394	+ member++;
	3395	+ }
	3396	+ return h;
	3397	+}
	3398	+
	3399	+/*
	3400	+ * Check structural compatibility of two FUNC_PROTOs, ignoring referenced type
	3401	+ * IDs. This check is performed during type graph equivalence check and
	3402	+ * referenced types equivalence is checked separately.
	3403	+ */
	3404	+static bool btf_shallow_equal_struct(struct btf_type t1, struct btf_type t2)
	3405	+{
	3406	+ const struct btf_member m1, m2;
	3407	+ __u16 vlen;
	3408	+ int i;
	3409	+
	3410	+ if (!btf_equal_common(t1, t2))
	3411	+ return false;
	3412	+
	3413	+ vlen = btf_vlen(t1);
	3414	+ m1 = btf_members(t1);
	3415	+ m2 = btf_members(t2);
	3416	+ for (i = 0; i < vlen; i++) {
	3417	+ if (m1->name_off != m2->name_off \|\| m1->offset != m2->offset)
	3418	+ return false;
	3419	+ m1++;
	3420	+ m2++;
	3421	+ }
	3422	+ return true;
	3423	+}
	3424	+
	3425	+/*
	3426	+ * Calculate type signature hash of ARRAY, including referenced type IDs,
	3427	+ * under assumption that they were already resolved to canonical type IDs and
	3428	+ * are not going to change.
	3429	+ */
	3430	+static long btf_hash_array(struct btf_type *t)
	3431	+{
	3432	+ const struct btf_array *info = btf_array(t);
	3433	+ long h = btf_hash_common(t);
	3434	+
	3435	+ h = hash_combine(h, info->type);
	3436	+ h = hash_combine(h, info->index_type);
	3437	+ h = hash_combine(h, info->nelems);
	3438	+ return h;
	3439	+}
	3440	+
	3441	+/*
	3442	+ * Check exact equality of two ARRAYs, taking into account referenced
	3443	+ * type IDs, under assumption that they were already resolved to canonical
	3444	+ * type IDs and are not going to change.
	3445	+ * This function is called during reference types deduplication to compare
	3446	+ * ARRAY to potential canonical representative.
	3447	+ */
	3448	+static bool btf_equal_array(struct btf_type t1, struct btf_type t2)
	3449	+{
	3450	+ const struct btf_array info1, info2;
	3451	+
	3452	+ if (!btf_equal_common(t1, t2))
	3453	+ return false;
	3454	+
	3455	+ info1 = btf_array(t1);
	3456	+ info2 = btf_array(t2);
	3457	+ return info1->type == info2->type &&
	3458	+ info1->index_type == info2->index_type &&
	3459	+ info1->nelems == info2->nelems;
	3460	+}
	3461	+
	3462	+/*
	3463	+ * Check structural compatibility of two ARRAYs, ignoring referenced type
	3464	+ * IDs. This check is performed during type graph equivalence check and
	3465	+ * referenced types equivalence is checked separately.
	3466	+ */
	3467	+static bool btf_compat_array(struct btf_type t1, struct btf_type t2)
	3468	+{
	3469	+ if (!btf_equal_common(t1, t2))
	3470	+ return false;
	3471	+
	3472	+ return btf_array(t1)->nelems == btf_array(t2)->nelems;
	3473	+}
	3474	+
	3475	+/*
	3476	+ * Calculate type signature hash of FUNC_PROTO, including referenced type IDs,
	3477	+ * under assumption that they were already resolved to canonical type IDs and
	3478	+ * are not going to change.
	3479	+ */
	3480	+static long btf_hash_fnproto(struct btf_type *t)
	3481	+{
	3482	+ const struct btf_param *member = btf_params(t);
	3483	+ __u16 vlen = btf_vlen(t);
	3484	+ long h = btf_hash_common(t);
	3485	+ int i;
	3486	+
	3487	+ for (i = 0; i < vlen; i++) {
	3488	+ h = hash_combine(h, member->name_off);
	3489	+ h = hash_combine(h, member->type);
	3490	+ member++;
	3491	+ }
	3492	+ return h;
	3493	+}
	3494	+
	3495	+/*
	3496	+ * Check exact equality of two FUNC_PROTOs, taking into account referenced
	3497	+ * type IDs, under assumption that they were already resolved to canonical
	3498	+ * type IDs and are not going to change.
	3499	+ * This function is called during reference types deduplication to compare
	3500	+ * FUNC_PROTO to potential canonical representative.
	3501	+ */
	3502	+static bool btf_equal_fnproto(struct btf_type t1, struct btf_type t2)
	3503	+{
	3504	+ const struct btf_param m1, m2;
	3505	+ __u16 vlen;
	3506	+ int i;
	3507	+
	3508	+ if (!btf_equal_common(t1, t2))
	3509	+ return false;
	3510	+
	3511	+ vlen = btf_vlen(t1);
	3512	+ m1 = btf_params(t1);
	3513	+ m2 = btf_params(t2);
	3514	+ for (i = 0; i < vlen; i++) {
	3515	+ if (m1->name_off != m2->name_off \|\| m1->type != m2->type)
	3516	+ return false;
	3517	+ m1++;
	3518	+ m2++;
	3519	+ }
	3520	+ return true;
	3521	+}
	3522	+
	3523	+/*
	3524	+ * Check structural compatibility of two FUNC_PROTOs, ignoring referenced type
	3525	+ * IDs. This check is performed during type graph equivalence check and
	3526	+ * referenced types equivalence is checked separately.
	3527	+ */
	3528	+static bool btf_compat_fnproto(struct btf_type t1, struct btf_type t2)
	3529	+{
	3530	+ const struct btf_param m1, m2;
	3531	+ __u16 vlen;
	3532	+ int i;
	3533	+
	3534	+ /* skip return type ID */
	3535	+ if (t1->name_off != t2->name_off \|\| t1->info != t2->info)
	3536	+ return false;
	3537	+
	3538	+ vlen = btf_vlen(t1);
	3539	+ m1 = btf_params(t1);
	3540	+ m2 = btf_params(t2);
	3541	+ for (i = 0; i < vlen; i++) {
	3542	+ if (m1->name_off != m2->name_off)
	3543	+ return false;
	3544	+ m1++;
	3545	+ m2++;
	3546	+ }
	3547	+ return true;
	3548	+}
	3549	+
	3550	+/*
	3551	+ * Deduplicate primitive types, that can't reference other types, by calculating
	3552	+ * their type signature hash and comparing them with any possible canonical
	3553	+ * candidate. If no canonical candidate matches, type itself is marked as
	3554	+ * canonical and is added into `btf_dedup->dedup_table` as another candidate.
	3555	+ */
	3556	+static int btf_dedup_prim_type(struct btf_dedup *d, __u32 type_id)
	3557	+{
	3558	+ struct btf_type *t = btf_type_by_id(d->btf, type_id);
	3559	+ struct hashmap_entry *hash_entry;
	3560	+ struct btf_type *cand;
	3561	+ /* if we don't find equivalent type, then we are canonical */
	3562	+ __u32 new_id = type_id;
	3563	+ __u32 cand_id;
	3564	+ long h;
	3565	+
	3566	+ switch (btf_kind(t)) {
	3567	+ case BTF_KIND_CONST:
	3568	+ case BTF_KIND_VOLATILE:
	3569	+ case BTF_KIND_RESTRICT:
	3570	+ case BTF_KIND_PTR:
	3571	+ case BTF_KIND_TYPEDEF:
	3572	+ case BTF_KIND_ARRAY:
	3573	+ case BTF_KIND_STRUCT:
	3574	+ case BTF_KIND_UNION:
	3575	+ case BTF_KIND_FUNC:
	3576	+ case BTF_KIND_FUNC_PROTO:
	3577	+ case BTF_KIND_VAR:
	3578	+ case BTF_KIND_DATASEC:
	3579	+ return 0;
	3580	+
	3581	+ case BTF_KIND_INT:
	3582	+ h = btf_hash_int(t);
	3583	+ for_each_dedup_cand(d, hash_entry, h) {
	3584	+ cand_id = (__u32)(long)hash_entry->value;
	3585	+ cand = btf_type_by_id(d->btf, cand_id);
	3586	+ if (btf_equal_int(t, cand)) {
	3587	+ new_id = cand_id;
	3588	+ break;
	3589	+ }
	3590	+ }
	3591	+ break;
	3592	+
	3593	+ case BTF_KIND_ENUM:
	3594	+ h = btf_hash_enum(t);
	3595	+ for_each_dedup_cand(d, hash_entry, h) {
	3596	+ cand_id = (__u32)(long)hash_entry->value;
	3597	+ cand = btf_type_by_id(d->btf, cand_id);
	3598	+ if (btf_equal_enum(t, cand)) {
	3599	+ new_id = cand_id;
	3600	+ break;
	3601	+ }
	3602	+ if (d->opts.dont_resolve_fwds)
	3603	+ continue;
	3604	+ if (btf_compat_enum(t, cand)) {
	3605	+ if (btf_is_enum_fwd(t)) {
	3606	+ /* resolve fwd to full enum */
	3607	+ new_id = cand_id;
	3608	+ break;
	3609	+ }
	3610	+ /* resolve canonical enum fwd to full enum */
	3611	+ d->map[cand_id] = type_id;
	3612	+ }
	3613	+ }
	3614	+ break;
	3615	+
	3616	+ case BTF_KIND_FWD:
	3617	+ h = btf_hash_common(t);
	3618	+ for_each_dedup_cand(d, hash_entry, h) {
	3619	+ cand_id = (__u32)(long)hash_entry->value;
	3620	+ cand = btf_type_by_id(d->btf, cand_id);
	3621	+ if (btf_equal_common(t, cand)) {
	3622	+ new_id = cand_id;
	3623	+ break;
	3624	+ }
	3625	+ }
	3626	+ break;
	3627	+
	3628	+ default:
	3629	+ return -EINVAL;
	3630	+ }
	3631	+
	3632	+ d->map[type_id] = new_id;
	3633	+ if (type_id == new_id && btf_dedup_table_add(d, h, type_id))
	3634	+ return -ENOMEM;
	3635	+
	3636	+ return 0;
	3637	+}
	3638	+
	3639	+static int btf_dedup_prim_types(struct btf_dedup *d)
	3640	+{
	3641	+ int i, err;
	3642	+
	3643	+ for (i = 1; i <= d->btf->nr_types; i++) {
	3644	+ err = btf_dedup_prim_type(d, i);
	3645	+ if (err)
	3646	+ return err;
	3647	+ }
	3648	+ return 0;
	3649	+}
	3650	+
	3651	+/*
	3652	+ * Check whether type is already mapped into canonical one (could be to itself).
	3653	+ */
	3654	+static inline bool is_type_mapped(struct btf_dedup *d, uint32_t type_id)
	3655	+{
	3656	+ return d->map[type_id] <= BTF_MAX_NR_TYPES;
	3657	+}
	3658	+
	3659	+/*
	3660	+ * Resolve type ID into its canonical type ID, if any; otherwise return original
	3661	+ * type ID. If type is FWD and is resolved into STRUCT/UNION already, follow
	3662	+ * STRUCT/UNION link and resolve it into canonical type ID as well.
	3663	+ */
	3664	+static inline __u32 resolve_type_id(struct btf_dedup *d, __u32 type_id)
	3665	+{
	3666	+ while (is_type_mapped(d, type_id) && d->map[type_id] != type_id)
	3667	+ type_id = d->map[type_id];
	3668	+ return type_id;
	3669	+}
	3670	+
	3671	+/*
	3672	+ * Resolve FWD to underlying STRUCT/UNION, if any; otherwise return original
	3673	+ * type ID.
	3674	+ */
	3675	+static uint32_t resolve_fwd_id(struct btf_dedup *d, uint32_t type_id)
	3676	+{
	3677	+ __u32 orig_type_id = type_id;
	3678	+
	3679	+ if (!btf_is_fwd(btf__type_by_id(d->btf, type_id)))
	3680	+ return type_id;
	3681	+
	3682	+ while (is_type_mapped(d, type_id) && d->map[type_id] != type_id)
	3683	+ type_id = d->map[type_id];
	3684	+
	3685	+ if (!btf_is_fwd(btf__type_by_id(d->btf, type_id)))
	3686	+ return type_id;
	3687	+
	3688	+ return orig_type_id;
	3689	+}
	3690	+
	3691	+
	3692	+static inline __u16 btf_fwd_kind(struct btf_type *t)
	3693	+{
	3694	+ return btf_kflag(t) ? BTF_KIND_UNION : BTF_KIND_STRUCT;
	3695	+}
	3696	+
	3697	+/*
	3698	+ * Check equivalence of BTF type graph formed by candidate struct/union (we'll
	3699	+ * call it "candidate graph" in this description for brevity) to a type graph
	3700	+ * formed by (potential) canonical struct/union ("canonical graph" for brevity
	3701	+ * here, though keep in mind that not all types in canonical graph are
	3702	+ * necessarily canonical representatives themselves, some of them might be
	3703	+ * duplicates or its uniqueness might not have been established yet).
	3704	+ * Returns:
	3705	+ * - >0, if type graphs are equivalent;
	3706	+ * - 0, if not equivalent;
	3707	+ * - <0, on error.
	3708	+ *
	3709	+ * Algorithm performs side-by-side DFS traversal of both type graphs and checks
	3710	+ * equivalence of BTF types at each step. If at any point BTF types in candidate
	3711	+ * and canonical graphs are not compatible structurally, whole graphs are
	3712	+ * incompatible. If types are structurally equivalent (i.e., all information
	3713	+ * except referenced type IDs is exactly the same), a mapping from `canon_id` to
	3714	+ * a `cand_id` is recored in hypothetical mapping (`btf_dedup->hypot_map`).
	3715	+ * If a type references other types, then those referenced types are checked
	3716	+ * for equivalence recursively.
	3717	+ *
	3718	+ * During DFS traversal, if we find that for current `canon_id` type we
	3719	+ * already have some mapping in hypothetical map, we check for two possible
	3720	+ * situations:
	3721	+ * - `canon_id` is mapped to exactly the same type as `cand_id`. This will
	3722	+ * happen when type graphs have cycles. In this case we assume those two
	3723	+ * types are equivalent.
	3724	+ * - `canon_id` is mapped to different type. This is contradiction in our
	3725	+ * hypothetical mapping, because same graph in canonical graph corresponds
	3726	+ * to two different types in candidate graph, which for equivalent type
	3727	+ * graphs shouldn't happen. This condition terminates equivalence check
	3728	+ * with negative result.
	3729	+ *
	3730	+ * If type graphs traversal exhausts types to check and find no contradiction,
	3731	+ * then type graphs are equivalent.
	3732	+ *
	3733	+ * When checking types for equivalence, there is one special case: FWD types.
	3734	+ * If FWD type resolution is allowed and one of the types (either from canonical
	3735	+ * or candidate graph) is FWD and other is STRUCT/UNION (depending on FWD's kind
	3736	+ * flag) and their names match, hypothetical mapping is updated to point from
	3737	+ * FWD to STRUCT/UNION. If graphs will be determined as equivalent successfully,
	3738	+ * this mapping will be used to record FWD -> STRUCT/UNION mapping permanently.
	3739	+ *
	3740	+ * Technically, this could lead to incorrect FWD to STRUCT/UNION resolution,
	3741	+ * if there are two exactly named (or anonymous) structs/unions that are
	3742	+ * compatible structurally, one of which has FWD field, while other is concrete
	3743	+ * STRUCT/UNION, but according to C sources they are different structs/unions
	3744	+ * that are referencing different types with the same name. This is extremely
	3745	+ * unlikely to happen, but btf_dedup API allows to disable FWD resolution if
	3746	+ * this logic is causing problems.
	3747	+ *
	3748	+ * Doing FWD resolution means that both candidate and/or canonical graphs can
	3749	+ * consists of portions of the graph that come from multiple compilation units.
	3750	+ * This is due to the fact that types within single compilation unit are always
	3751	+ * deduplicated and FWDs are already resolved, if referenced struct/union
	3752	+ * definiton is available. So, if we had unresolved FWD and found corresponding
	3753	+ * STRUCT/UNION, they will be from different compilation units. This
	3754	+ * consequently means that when we "link" FWD to corresponding STRUCT/UNION,
	3755	+ * type graph will likely have at least two different BTF types that describe
	3756	+ * same type (e.g., most probably there will be two different BTF types for the
	3757	+ * same 'int' primitive type) and could even have "overlapping" parts of type
	3758	+ * graph that describe same subset of types.
	3759	+ *
	3760	+ * This in turn means that our assumption that each type in canonical graph
	3761	+ * must correspond to exactly one type in candidate graph might not hold
	3762	+ * anymore and will make it harder to detect contradictions using hypothetical
	3763	+ * map. To handle this problem, we allow to follow FWD -> STRUCT/UNION
	3764	+ * resolution only in canonical graph. FWDs in candidate graphs are never
	3765	+ * resolved. To see why it's OK, let's check all possible situations w.r.t. FWDs
	3766	+ * that can occur:
	3767	+ * - Both types in canonical and candidate graphs are FWDs. If they are
	3768	+ * structurally equivalent, then they can either be both resolved to the
	3769	+ * same STRUCT/UNION or not resolved at all. In both cases they are
	3770	+ * equivalent and there is no need to resolve FWD on candidate side.
	3771	+ * - Both types in canonical and candidate graphs are concrete STRUCT/UNION,
	3772	+ * so nothing to resolve as well, algorithm will check equivalence anyway.
	3773	+ * - Type in canonical graph is FWD, while type in candidate is concrete
	3774	+ * STRUCT/UNION. In this case candidate graph comes from single compilation
	3775	+ * unit, so there is exactly one BTF type for each unique C type. After
	3776	+ * resolving FWD into STRUCT/UNION, there might be more than one BTF type
	3777	+ * in canonical graph mapping to single BTF type in candidate graph, but
	3778	+ * because hypothetical mapping maps from canonical to candidate types, it's
	3779	+ * alright, and we still maintain the property of having single `canon_id`
	3780	+ * mapping to single `cand_id` (there could be two different `canon_id`
	3781	+ * mapped to the same `cand_id`, but it's not contradictory).
	3782	+ * - Type in canonical graph is concrete STRUCT/UNION, while type in candidate
	3783	+ * graph is FWD. In this case we are just going to check compatibility of
	3784	+ * STRUCT/UNION and corresponding FWD, and if they are compatible, we'll
	3785	+ * assume that whatever STRUCT/UNION FWD resolves to must be equivalent to
	3786	+ * a concrete STRUCT/UNION from canonical graph. If the rest of type graphs
	3787	+ * turn out equivalent, we'll re-resolve FWD to concrete STRUCT/UNION from
	3788	+ * canonical graph.
	3789	+ */
	3790	+static int btf_dedup_is_equiv(struct btf_dedup *d, __u32 cand_id,
	3791	+ __u32 canon_id)
	3792	+{
	3793	+ struct btf_type *cand_type;
	3794	+ struct btf_type *canon_type;
	3795	+ __u32 hypot_type_id;
	3796	+ __u16 cand_kind;
	3797	+ __u16 canon_kind;
	3798	+ int i, eq;
	3799	+
	3800	+ /* if both resolve to the same canonical, they must be equivalent */
	3801	+ if (resolve_type_id(d, cand_id) == resolve_type_id(d, canon_id))
	3802	+ return 1;
	3803	+
	3804	+ canon_id = resolve_fwd_id(d, canon_id);
	3805	+
	3806	+ hypot_type_id = d->hypot_map[canon_id];
	3807	+ if (hypot_type_id <= BTF_MAX_NR_TYPES)
	3808	+ return hypot_type_id == cand_id;
	3809	+
	3810	+ if (btf_dedup_hypot_map_add(d, canon_id, cand_id))
	3811	+ return -ENOMEM;
	3812	+
	3813	+ cand_type = btf_type_by_id(d->btf, cand_id);
	3814	+ canon_type = btf_type_by_id(d->btf, canon_id);
	3815	+ cand_kind = btf_kind(cand_type);
	3816	+ canon_kind = btf_kind(canon_type);
	3817	+
	3818	+ if (cand_type->name_off != canon_type->name_off)
	3819	+ return 0;
	3820	+
	3821	+ /* FWD <--> STRUCT/UNION equivalence check, if enabled */
	3822	+ if (!d->opts.dont_resolve_fwds
	3823	+ && (cand_kind == BTF_KIND_FWD \|\| canon_kind == BTF_KIND_FWD)
	3824	+ && cand_kind != canon_kind) {
	3825	+ __u16 real_kind;
	3826	+ __u16 fwd_kind;
	3827	+
	3828	+ if (cand_kind == BTF_KIND_FWD) {
	3829	+ real_kind = canon_kind;
	3830	+ fwd_kind = btf_fwd_kind(cand_type);
	3831	+ } else {
	3832	+ real_kind = cand_kind;
	3833	+ fwd_kind = btf_fwd_kind(canon_type);
	3834	+ }
	3835	+ return fwd_kind == real_kind;
	3836	+ }
	3837	+
	3838	+ if (cand_kind != canon_kind)
	3839	+ return 0;
	3840	+
	3841	+ switch (cand_kind) {
	3842	+ case BTF_KIND_INT:
	3843	+ return btf_equal_int(cand_type, canon_type);
	3844	+
	3845	+ case BTF_KIND_ENUM:
	3846	+ if (d->opts.dont_resolve_fwds)
	3847	+ return btf_equal_enum(cand_type, canon_type);
	3848	+ else
	3849	+ return btf_compat_enum(cand_type, canon_type);
	3850	+
	3851	+ case BTF_KIND_FWD:
	3852	+ return btf_equal_common(cand_type, canon_type);
	3853	+
	3854	+ case BTF_KIND_CONST:
	3855	+ case BTF_KIND_VOLATILE:
	3856	+ case BTF_KIND_RESTRICT:
	3857	+ case BTF_KIND_PTR:
	3858	+ case BTF_KIND_TYPEDEF:
	3859	+ case BTF_KIND_FUNC:
	3860	+ if (cand_type->info != canon_type->info)
	3861	+ return 0;
	3862	+ return btf_dedup_is_equiv(d, cand_type->type, canon_type->type);
	3863	+
	3864	+ case BTF_KIND_ARRAY: {
	3865	+ const struct btf_array cand_arr, canon_arr;
	3866	+
	3867	+ if (!btf_compat_array(cand_type, canon_type))
	3868	+ return 0;
	3869	+ cand_arr = btf_array(cand_type);
	3870	+ canon_arr = btf_array(canon_type);
	3871	+ eq = btf_dedup_is_equiv(d,
	3872	+ cand_arr->index_type, canon_arr->index_type);
	3873	+ if (eq <= 0)
	3874	+ return eq;
	3875	+ return btf_dedup_is_equiv(d, cand_arr->type, canon_arr->type);
	3876	+ }
	3877	+
	3878	+ case BTF_KIND_STRUCT:
	3879	+ case BTF_KIND_UNION: {
	3880	+ const struct btf_member cand_m, canon_m;
	3881	+ __u16 vlen;
	3882	+
	3883	+ if (!btf_shallow_equal_struct(cand_type, canon_type))
	3884	+ return 0;
	3885	+ vlen = btf_vlen(cand_type);
	3886	+ cand_m = btf_members(cand_type);
	3887	+ canon_m = btf_members(canon_type);
	3888	+ for (i = 0; i < vlen; i++) {
	3889	+ eq = btf_dedup_is_equiv(d, cand_m->type, canon_m->type);
	3890	+ if (eq <= 0)
	3891	+ return eq;
	3892	+ cand_m++;
	3893	+ canon_m++;
	3894	+ }
	3895	+
	3896	+ return 1;
	3897	+ }
	3898	+
	3899	+ case BTF_KIND_FUNC_PROTO: {
	3900	+ const struct btf_param cand_p, canon_p;
	3901	+ __u16 vlen;
	3902	+
	3903	+ if (!btf_compat_fnproto(cand_type, canon_type))
	3904	+ return 0;
	3905	+ eq = btf_dedup_is_equiv(d, cand_type->type, canon_type->type);
	3906	+ if (eq <= 0)
	3907	+ return eq;
	3908	+ vlen = btf_vlen(cand_type);
	3909	+ cand_p = btf_params(cand_type);
	3910	+ canon_p = btf_params(canon_type);
	3911	+ for (i = 0; i < vlen; i++) {
	3912	+ eq = btf_dedup_is_equiv(d, cand_p->type, canon_p->type);
	3913	+ if (eq <= 0)
	3914	+ return eq;
	3915	+ cand_p++;
	3916	+ canon_p++;
	3917	+ }
	3918	+ return 1;
	3919	+ }
	3920	+
	3921	+ default:
	3922	+ return -EINVAL;
	3923	+ }
	3924	+ return 0;
	3925	+}
	3926	+
	3927	+/*
	3928	+ * Use hypothetical mapping, produced by successful type graph equivalence
	3929	+ * check, to augment existing struct/union canonical mapping, where possible.
	3930	+ *
	3931	+ * If BTF_KIND_FWD resolution is allowed, this mapping is also used to record
	3932	+ * FWD -> STRUCT/UNION correspondence as well. FWD resolution is bidirectional:
	3933	+ * it doesn't matter if FWD type was part of canonical graph or candidate one,
	3934	+ * we are recording the mapping anyway. As opposed to carefulness required
	3935	+ * for struct/union correspondence mapping (described below), for FWD resolution
	3936	+ * it's not important, as by the time that FWD type (reference type) will be
	3937	+ * deduplicated all structs/unions will be deduped already anyway.
	3938	+ *
	3939	+ * Recording STRUCT/UNION mapping is purely a performance optimization and is
	3940	+ * not required for correctness. It needs to be done carefully to ensure that
	3941	+ * struct/union from candidate's type graph is not mapped into corresponding
	3942	+ * struct/union from canonical type graph that itself hasn't been resolved into
	3943	+ * canonical representative. The only guarantee we have is that canonical
	3944	+ * struct/union was determined as canonical and that won't change. But any
	3945	+ * types referenced through that struct/union fields could have been not yet
	3946	+ * resolved, so in case like that it's too early to establish any kind of
	3947	+ * correspondence between structs/unions.
	3948	+ *
	3949	+ * No canonical correspondence is derived for primitive types (they are already
	3950	+ * deduplicated completely already anyway) or reference types (they rely on
	3951	+ * stability of struct/union canonical relationship for equivalence checks).
	3952	+ */
	3953	+static void btf_dedup_merge_hypot_map(struct btf_dedup *d)
	3954	+{
	3955	+ __u32 cand_type_id, targ_type_id;
	3956	+ __u16 t_kind, c_kind;
	3957	+ __u32 t_id, c_id;
	3958	+ int i;
	3959	+
	3960	+ for (i = 0; i < d->hypot_cnt; i++) {
	3961	+ cand_type_id = d->hypot_list[i];
	3962	+ targ_type_id = d->hypot_map[cand_type_id];
	3963	+ t_id = resolve_type_id(d, targ_type_id);
	3964	+ c_id = resolve_type_id(d, cand_type_id);
	3965	+ t_kind = btf_kind(btf__type_by_id(d->btf, t_id));
	3966	+ c_kind = btf_kind(btf__type_by_id(d->btf, c_id));
	3967	+ /*
	3968	+ * Resolve FWD into STRUCT/UNION.
	3969	+ * It's ok to resolve FWD into STRUCT/UNION that's not yet
	3970	+ * mapped to canonical representative (as opposed to
	3971	+ * STRUCT/UNION <--> STRUCT/UNION mapping logic below), because
	3972	+ * eventually that struct is going to be mapped and all resolved
	3973	+ * FWDs will automatically resolve to correct canonical
	3974	+ * representative. This will happen before ref type deduping,
	3975	+ * which critically depends on stability of these mapping. This
	3976	+ * stability is not a requirement for STRUCT/UNION equivalence
	3977	+ * checks, though.
	3978	+ */
	3979	+ if (t_kind != BTF_KIND_FWD && c_kind == BTF_KIND_FWD)
	3980	+ d->map[c_id] = t_id;
	3981	+ else if (t_kind == BTF_KIND_FWD && c_kind != BTF_KIND_FWD)
	3982	+ d->map[t_id] = c_id;
	3983	+
	3984	+ if ((t_kind == BTF_KIND_STRUCT \|\| t_kind == BTF_KIND_UNION) &&
	3985	+ c_kind != BTF_KIND_FWD &&
	3986	+ is_type_mapped(d, c_id) &&
	3987	+ !is_type_mapped(d, t_id)) {
	3988	+ /*
	3989	+ * as a perf optimization, we can map struct/union
	3990	+ * that's part of type graph we just verified for
	3991	+ * equivalence. We can do that for struct/union that has
	3992	+ * canonical representative only, though.
	3993	+ */
	3994	+ d->map[t_id] = c_id;
	3995	+ }
	3996	+ }
	3997	+}
	3998	+
	3999	+/*
	4000	+ * Deduplicate struct/union types.
	4001	+ *
	4002	+ * For each struct/union type its type signature hash is calculated, taking
	4003	+ * into account type's name, size, number, order and names of fields, but
	4004	+ * ignoring type ID's referenced from fields, because they might not be deduped
	4005	+ * completely until after reference types deduplication phase. This type hash
	4006	+ * is used to iterate over all potential canonical types, sharing same hash.
	4007	+ * For each canonical candidate we check whether type graphs that they form
	4008	+ * (through referenced types in fields and so on) are equivalent using algorithm
	4009	+ * implemented in `btf_dedup_is_equiv`. If such equivalence is found and
	4010	+ * BTF_KIND_FWD resolution is allowed, then hypothetical mapping
	4011	+ * (btf_dedup->hypot_map) produced by aforementioned type graph equivalence
	4012	+ * algorithm is used to record FWD -> STRUCT/UNION mapping. It's also used to
	4013	+ * potentially map other structs/unions to their canonical representatives,
	4014	+ * if such relationship hasn't yet been established. This speeds up algorithm
	4015	+ * by eliminating some of the duplicate work.
	4016	+ *
	4017	+ * If no matching canonical representative was found, struct/union is marked
	4018	+ * as canonical for itself and is added into btf_dedup->dedup_table hash map
	4019	+ * for further look ups.
	4020	+ */
	4021	+static int btf_dedup_struct_type(struct btf_dedup *d, __u32 type_id)
	4022	+{
	4023	+ struct btf_type cand_type, t;
	4024	+ struct hashmap_entry *hash_entry;
	4025	+ /* if we don't find equivalent type, then we are canonical */
	4026	+ __u32 new_id = type_id;
	4027	+ __u16 kind;
	4028	+ long h;
	4029	+
	4030	+ /* already deduped or is in process of deduping (loop detected) */
	4031	+ if (d->map[type_id] <= BTF_MAX_NR_TYPES)
	4032	+ return 0;
	4033	+
	4034	+ t = btf_type_by_id(d->btf, type_id);
	4035	+ kind = btf_kind(t);
	4036	+
	4037	+ if (kind != BTF_KIND_STRUCT && kind != BTF_KIND_UNION)
	4038	+ return 0;
	4039	+
	4040	+ h = btf_hash_struct(t);
	4041	+ for_each_dedup_cand(d, hash_entry, h) {
	4042	+ __u32 cand_id = (__u32)(long)hash_entry->value;
	4043	+ int eq;
	4044	+
	4045	+ /*
	4046	+ * Even though btf_dedup_is_equiv() checks for
	4047	+ * btf_shallow_equal_struct() internally when checking two
	4048	+ * structs (unions) for equivalence, we need to guard here
	4049	+ * from picking matching FWD type as a dedup candidate.
	4050	+ * This can happen due to hash collision. In such case just
	4051	+ * relying on btf_dedup_is_equiv() would lead to potentially
	4052	+ * creating a loop (FWD -> STRUCT and STRUCT -> FWD), because
	4053	+ * FWD and compatible STRUCT/UNION are considered equivalent.
	4054	+ */
	4055	+ cand_type = btf_type_by_id(d->btf, cand_id);
	4056	+ if (!btf_shallow_equal_struct(t, cand_type))
	4057	+ continue;
	4058	+
	4059	+ btf_dedup_clear_hypot_map(d);
	4060	+ eq = btf_dedup_is_equiv(d, type_id, cand_id);
	4061	+ if (eq < 0)
	4062	+ return eq;
	4063	+ if (!eq)
	4064	+ continue;
	4065	+ new_id = cand_id;
	4066	+ btf_dedup_merge_hypot_map(d);
	4067	+ break;
	4068	+ }
	4069	+
	4070	+ d->map[type_id] = new_id;
	4071	+ if (type_id == new_id && btf_dedup_table_add(d, h, type_id))
	4072	+ return -ENOMEM;
	4073	+
	4074	+ return 0;
	4075	+}
	4076	+
	4077	+static int btf_dedup_struct_types(struct btf_dedup *d)
	4078	+{
	4079	+ int i, err;
	4080	+
	4081	+ for (i = 1; i <= d->btf->nr_types; i++) {
	4082	+ err = btf_dedup_struct_type(d, i);
	4083	+ if (err)
	4084	+ return err;
	4085	+ }
	4086	+ return 0;
	4087	+}
	4088	+
	4089	+/*
	4090	+ * Deduplicate reference type.
	4091	+ *
	4092	+ * Once all primitive and struct/union types got deduplicated, we can easily
	4093	+ * deduplicate all other (reference) BTF types. This is done in two steps:
	4094	+ *
	4095	+ * 1. Resolve all referenced type IDs into their canonical type IDs. This
	4096	+ * resolution can be done either immediately for primitive or struct/union types
	4097	+ * (because they were deduped in previous two phases) or recursively for
	4098	+ * reference types. Recursion will always terminate at either primitive or
	4099	+ * struct/union type, at which point we can "unwind" chain of reference types
	4100	+ * one by one. There is no danger of encountering cycles because in C type
	4101	+ * system the only way to form type cycle is through struct/union, so any chain
	4102	+ * of reference types, even those taking part in a type cycle, will inevitably
	4103	+ * reach struct/union at some point.
	4104	+ *
	4105	+ * 2. Once all referenced type IDs are resolved into canonical ones, BTF type
	4106	+ * becomes "stable", in the sense that no further deduplication will cause
	4107	+ * any changes to it. With that, it's now possible to calculate type's signature
	4108	+ * hash (this time taking into account referenced type IDs) and loop over all
	4109	+ * potential canonical representatives. If no match was found, current type
	4110	+ * will become canonical representative of itself and will be added into
	4111	+ * btf_dedup->dedup_table as another possible canonical representative.
	4112	+ */
	4113	+static int btf_dedup_ref_type(struct btf_dedup *d, __u32 type_id)
	4114	+{
	4115	+ struct hashmap_entry *hash_entry;
	4116	+ __u32 new_id = type_id, cand_id;
	4117	+ struct btf_type t, cand;
	4118	+ /* if we don't find equivalent type, then we are representative type */
	4119	+ int ref_type_id;
	4120	+ long h;
	4121	+
	4122	+ if (d->map[type_id] == BTF_IN_PROGRESS_ID)
	4123	+ return -ELOOP;
	4124	+ if (d->map[type_id] <= BTF_MAX_NR_TYPES)
	4125	+ return resolve_type_id(d, type_id);
	4126	+
	4127	+ t = btf_type_by_id(d->btf, type_id);
	4128	+ d->map[type_id] = BTF_IN_PROGRESS_ID;
	4129	+
	4130	+ switch (btf_kind(t)) {
	4131	+ case BTF_KIND_CONST:
	4132	+ case BTF_KIND_VOLATILE:
	4133	+ case BTF_KIND_RESTRICT:
	4134	+ case BTF_KIND_PTR:
	4135	+ case BTF_KIND_TYPEDEF:
	4136	+ case BTF_KIND_FUNC:
	4137	+ ref_type_id = btf_dedup_ref_type(d, t->type);
	4138	+ if (ref_type_id < 0)
	4139	+ return ref_type_id;
	4140	+ t->type = ref_type_id;
	4141	+
	4142	+ h = btf_hash_common(t);
	4143	+ for_each_dedup_cand(d, hash_entry, h) {
	4144	+ cand_id = (__u32)(long)hash_entry->value;
	4145	+ cand = btf_type_by_id(d->btf, cand_id);
	4146	+ if (btf_equal_common(t, cand)) {
	4147	+ new_id = cand_id;
	4148	+ break;
	4149	+ }
	4150	+ }
	4151	+ break;
	4152	+
	4153	+ case BTF_KIND_ARRAY: {
	4154	+ struct btf_array *info = btf_array(t);
	4155	+
	4156	+ ref_type_id = btf_dedup_ref_type(d, info->type);
	4157	+ if (ref_type_id < 0)
	4158	+ return ref_type_id;
	4159	+ info->type = ref_type_id;
	4160	+
	4161	+ ref_type_id = btf_dedup_ref_type(d, info->index_type);
	4162	+ if (ref_type_id < 0)
	4163	+ return ref_type_id;
	4164	+ info->index_type = ref_type_id;
	4165	+
	4166	+ h = btf_hash_array(t);
	4167	+ for_each_dedup_cand(d, hash_entry, h) {
	4168	+ cand_id = (__u32)(long)hash_entry->value;
	4169	+ cand = btf_type_by_id(d->btf, cand_id);
	4170	+ if (btf_equal_array(t, cand)) {
	4171	+ new_id = cand_id;
	4172	+ break;
	4173	+ }
	4174	+ }
	4175	+ break;
	4176	+ }
	4177	+
	4178	+ case BTF_KIND_FUNC_PROTO: {
	4179	+ struct btf_param *param;
	4180	+ __u16 vlen;
	4181	+ int i;
	4182	+
	4183	+ ref_type_id = btf_dedup_ref_type(d, t->type);
	4184	+ if (ref_type_id < 0)
	4185	+ return ref_type_id;
	4186	+ t->type = ref_type_id;
	4187	+
	4188	+ vlen = btf_vlen(t);
	4189	+ param = btf_params(t);
	4190	+ for (i = 0; i < vlen; i++) {
	4191	+ ref_type_id = btf_dedup_ref_type(d, param->type);
	4192	+ if (ref_type_id < 0)
	4193	+ return ref_type_id;
	4194	+ param->type = ref_type_id;
	4195	+ param++;
	4196	+ }
	4197	+
	4198	+ h = btf_hash_fnproto(t);
	4199	+ for_each_dedup_cand(d, hash_entry, h) {
	4200	+ cand_id = (__u32)(long)hash_entry->value;
	4201	+ cand = btf_type_by_id(d->btf, cand_id);
	4202	+ if (btf_equal_fnproto(t, cand)) {
	4203	+ new_id = cand_id;
	4204	+ break;
	4205	+ }
	4206	+ }
	4207	+ break;
	4208	+ }
	4209	+
	4210	+ default:
	4211	+ return -EINVAL;
	4212	+ }
	4213	+
	4214	+ d->map[type_id] = new_id;
	4215	+ if (type_id == new_id && btf_dedup_table_add(d, h, type_id))
	4216	+ return -ENOMEM;
	4217	+
	4218	+ return new_id;
	4219	+}
	4220	+
	4221	+static int btf_dedup_ref_types(struct btf_dedup *d)
	4222	+{
	4223	+ int i, err;
	4224	+
	4225	+ for (i = 1; i <= d->btf->nr_types; i++) {
	4226	+ err = btf_dedup_ref_type(d, i);
	4227	+ if (err < 0)
	4228	+ return err;
	4229	+ }
	4230	+ /* we won't need d->dedup_table anymore */
	4231	+ hashmap__free(d->dedup_table);
	4232	+ d->dedup_table = NULL;
	4233	+ return 0;
	4234	+}
	4235	+
	4236	+/*
	4237	+ * Compact types.
	4238	+ *
	4239	+ * After we established for each type its corresponding canonical representative
	4240	+ * type, we now can eliminate types that are not canonical and leave only
	4241	+ * canonical ones layed out sequentially in memory by copying them over
	4242	+ * duplicates. During compaction btf_dedup->hypot_map array is reused to store
	4243	+ * a map from original type ID to a new compacted type ID, which will be used
	4244	+ * during next phase to "fix up" type IDs, referenced from struct/union and
	4245	+ * reference types.
	4246	+ */
	4247	+static int btf_dedup_compact_types(struct btf_dedup *d)
	4248	+{
	4249	+ __u32 *new_offs;
	4250	+ __u32 next_type_id = 1;
	4251	+ void *p;
	4252	+ int i, len;
	4253	+
	4254	+ /* we are going to reuse hypot_map to store compaction remapping */
	4255	+ d->hypot_map[0] = 0;
	4256	+ for (i = 1; i <= d->btf->nr_types; i++)
	4257	+ d->hypot_map[i] = BTF_UNPROCESSED_ID;
	4258	+
	4259	+ p = d->btf->types_data;
	4260	+
	4261	+ for (i = 1; i <= d->btf->nr_types; i++) {
	4262	+ if (d->map[i] != i)
	4263	+ continue;
	4264	+
	4265	+ len = btf_type_size(btf__type_by_id(d->btf, i));
	4266	+ if (len < 0)
	4267	+ return len;
	4268	+
	4269	+ memmove(p, btf__type_by_id(d->btf, i), len);
	4270	+ d->hypot_map[i] = next_type_id;
	4271	+ d->btf->type_offs[next_type_id] = p - d->btf->types_data;
	4272	+ p += len;
	4273	+ next_type_id++;
	4274	+ }
	4275	+
	4276	+ /* shrink struct btf's internal types index and update btf_header */
	4277	+ d->btf->nr_types = next_type_id - 1;
	4278	+ d->btf->type_offs_cap = d->btf->nr_types + 1;
	4279	+ d->btf->hdr->type_len = p - d->btf->types_data;
	4280	+ new_offs = libbpf_reallocarray(d->btf->type_offs, d->btf->type_offs_cap,
	4281	+ sizeof(*new_offs));
	4282	+ if (!new_offs)
	4283	+ return -ENOMEM;
	4284	+ d->btf->type_offs = new_offs;
	4285	+ d->btf->hdr->str_off = d->btf->hdr->type_len;
	4286	+ d->btf->raw_size = d->btf->hdr->hdr_len + d->btf->hdr->type_len + d->btf->hdr->str_len;
	4287	+ return 0;
	4288	+}
	4289	+
	4290	+/*
	4291	+ * Figure out final (deduplicated and compacted) type ID for provided original
	4292	+ * `type_id` by first resolving it into corresponding canonical type ID and
	4293	+ * then mapping it to a deduplicated type ID, stored in btf_dedup->hypot_map,
	4294	+ * which is populated during compaction phase.
	4295	+ */
	4296	+static int btf_dedup_remap_type_id(struct btf_dedup *d, __u32 type_id)
	4297	+{
	4298	+ __u32 resolved_type_id, new_type_id;
	4299	+
	4300	+ resolved_type_id = resolve_type_id(d, type_id);
	4301	+ new_type_id = d->hypot_map[resolved_type_id];
	4302	+ if (new_type_id > BTF_MAX_NR_TYPES)
	4303	+ return -EINVAL;
	4304	+ return new_type_id;
	4305	+}
	4306	+
	4307	+/*
	4308	+ * Remap referenced type IDs into deduped type IDs.
	4309	+ *
	4310	+ * After BTF types are deduplicated and compacted, their final type IDs may
	4311	+ * differ from original ones. The map from original to a corresponding
	4312	+ * deduped type ID is stored in btf_dedup->hypot_map and is populated during
	4313	+ * compaction phase. During remapping phase we are rewriting all type IDs
	4314	+ * referenced from any BTF type (e.g., struct fields, func proto args, etc) to
	4315	+ * their final deduped type IDs.
	4316	+ */
	4317	+static int btf_dedup_remap_type(struct btf_dedup *d, __u32 type_id)
	4318	+{
	4319	+ struct btf_type *t = btf_type_by_id(d->btf, type_id);
	4320	+ int i, r;
	4321	+
	4322	+ switch (btf_kind(t)) {
	4323	+ case BTF_KIND_INT:
	4324	+ case BTF_KIND_ENUM:
	4325	+ break;
	4326	+
	4327	+ case BTF_KIND_FWD:
	4328	+ case BTF_KIND_CONST:
	4329	+ case BTF_KIND_VOLATILE:
	4330	+ case BTF_KIND_RESTRICT:
	4331	+ case BTF_KIND_PTR:
	4332	+ case BTF_KIND_TYPEDEF:
	4333	+ case BTF_KIND_FUNC:
	4334	+ case BTF_KIND_VAR:
	4335	+ r = btf_dedup_remap_type_id(d, t->type);
	4336	+ if (r < 0)
	4337	+ return r;
	4338	+ t->type = r;
	4339	+ break;
	4340	+
	4341	+ case BTF_KIND_ARRAY: {
	4342	+ struct btf_array *arr_info = btf_array(t);
	4343	+
	4344	+ r = btf_dedup_remap_type_id(d, arr_info->type);
	4345	+ if (r < 0)
	4346	+ return r;
	4347	+ arr_info->type = r;
	4348	+ r = btf_dedup_remap_type_id(d, arr_info->index_type);
	4349	+ if (r < 0)
	4350	+ return r;
	4351	+ arr_info->index_type = r;
	4352	+ break;
	4353	+ }
	4354	+
	4355	+ case BTF_KIND_STRUCT:
	4356	+ case BTF_KIND_UNION: {
	4357	+ struct btf_member *member = btf_members(t);
	4358	+ __u16 vlen = btf_vlen(t);
	4359	+
	4360	+ for (i = 0; i < vlen; i++) {
	4361	+ r = btf_dedup_remap_type_id(d, member->type);
	4362	+ if (r < 0)
	4363	+ return r;
	4364	+ member->type = r;
	4365	+ member++;
	4366	+ }
	4367	+ break;
	4368	+ }
	4369	+
	4370	+ case BTF_KIND_FUNC_PROTO: {
	4371	+ struct btf_param *param = btf_params(t);
	4372	+ __u16 vlen = btf_vlen(t);
	4373	+
	4374	+ r = btf_dedup_remap_type_id(d, t->type);
	4375	+ if (r < 0)
	4376	+ return r;
	4377	+ t->type = r;
	4378	+
	4379	+ for (i = 0; i < vlen; i++) {
	4380	+ r = btf_dedup_remap_type_id(d, param->type);
	4381	+ if (r < 0)
	4382	+ return r;
	4383	+ param->type = r;
	4384	+ param++;
	4385	+ }
	4386	+ break;
	4387	+ }
	4388	+
	4389	+ case BTF_KIND_DATASEC: {
	4390	+ struct btf_var_secinfo *var = btf_var_secinfos(t);
	4391	+ __u16 vlen = btf_vlen(t);
	4392	+
	4393	+ for (i = 0; i < vlen; i++) {
	4394	+ r = btf_dedup_remap_type_id(d, var->type);
	4395	+ if (r < 0)
	4396	+ return r;
	4397	+ var->type = r;
	4398	+ var++;
	4399	+ }
	4400	+ break;
	4401	+ }
	4402	+
	4403	+ default:
	4404	+ return -EINVAL;
	4405	+ }
	4406	+
	4407	+ return 0;
	4408	+}
	4409	+
	4410	+static int btf_dedup_remap_types(struct btf_dedup *d)
	4411	+{
	4412	+ int i, r;
	4413	+
	4414	+ for (i = 1; i <= d->btf->nr_types; i++) {
	4415	+ r = btf_dedup_remap_type(d, i);
	4416	+ if (r < 0)
	4417	+ return r;
	4418	+ }
	4419	+ return 0;
	4420	+}
	4421	+
	4422	+/*
	4423	+ * Probe few well-known locations for vmlinux kernel image and try to load BTF
	4424	+ * data out of it to use for target BTF.
	4425	+ */
	4426	+struct btf *libbpf_find_kernel_btf(void)
	4427	+{
	4428	+ struct {
	4429	+ const char *path_fmt;
	4430	+ bool raw_btf;
	4431	+ } locations[] = {
	4432	+ /* try canonical vmlinux BTF through sysfs first */
	4433	+ { "/sys/kernel/btf/vmlinux", true /* raw BTF */ },
	4434	+ /* fall back to trying to find vmlinux ELF on disk otherwise */
	4435	+ { "/boot/vmlinux-%1$s" },
	4436	+ { "/lib/modules/%1$s/vmlinux-%1$s" },
	4437	+ { "/lib/modules/%1$s/build/vmlinux" },
	4438	+ { "/usr/lib/modules/%1$s/kernel/vmlinux" },
	4439	+ { "/usr/lib/debug/boot/vmlinux-%1$s" },
	4440	+ { "/usr/lib/debug/boot/vmlinux-%1$s.debug" },
	4441	+ { "/usr/lib/debug/lib/modules/%1$s/vmlinux" },
	4442	+ };
	4443	+ char path[PATH_MAX + 1];
	4444	+ struct utsname buf;
	4445	+ struct btf *btf;
	4446	+ int i;
	4447	+
	4448	+ uname(&buf);
	4449	+
	4450	+ for (i = 0; i < ARRAY_SIZE(locations); i++) {
	4451	+ snprintf(path, PATH_MAX, locations[i].path_fmt, buf.release);
	4452	+
	4453	+ if (access(path, R_OK))
	4454	+ continue;
	4455	+
	4456	+ if (locations[i].raw_btf)
	4457	+ btf = btf__parse_raw(path);
	4458	+ else
	4459	+ btf = btf__parse_elf(path, NULL);
	4460	+
	4461	+ pr_debug("loading kernel BTF '%s': %ld\n",
	4462	+ path, IS_ERR(btf) ? PTR_ERR(btf) : 0);
	4463	+ if (IS_ERR(btf))
	4464	+ continue;
	4465	+
	4466	+ return btf;
	4467	+ }
	4468	+
	4469	+ pr_warn("failed to find valid kernel BTF\n");
	4470	+ return ERR_PTR(-ESRCH);
	4471	+}