xref: /linux/tools/lib/bpf/btf.c (revision 9abe2c42ecab6c86b54838d2d645ca2e10204606)
1 // SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)
2 /* Copyright (c) 2018 Facebook */
3 
4 #include <byteswap.h>
5 #include <endian.h>
6 #include <stdio.h>
7 #include <stdlib.h>
8 #include <string.h>
9 #include <fcntl.h>
10 #include <unistd.h>
11 #include <errno.h>
12 #include <sys/utsname.h>
13 #include <sys/param.h>
14 #include <sys/stat.h>
15 #include <sys/mman.h>
16 #include <linux/kernel.h>
17 #include <linux/err.h>
18 #include <linux/btf.h>
19 #include <gelf.h>
20 #include "btf.h"
21 #include "bpf.h"
22 #include "libbpf.h"
23 #include "libbpf_internal.h"
24 #include "hashmap.h"
25 #include "strset.h"
26 
27 #define BTF_MAX_NR_TYPES 0x7fffffffU
28 #define BTF_MAX_STR_OFFSET 0x7fffffffU
29 
30 static struct btf_type btf_void;
31 
32 /*
33  * Describe how kinds are laid out; some have a singular element following the "struct btf_type",
34  * some have BTF_INFO_VLEN(t->info) elements.  Specify sizes for both.  Flags are currently unused.
35  * Kind layout can be optionally added to the BTF representation in a dedicated section to
36  * facilitate parsing.  New kinds must be added here.
37  */
38 static struct btf_layout layouts[NR_BTF_KINDS] = {
39 /*				singular element size		vlen element(s) size		flags */
40 [BTF_KIND_UNKN] =	{	0,				0,				0 },
41 [BTF_KIND_INT] =	{	sizeof(__u32),			0,				0 },
42 [BTF_KIND_PTR] =	{	0,				0,				0 },
43 [BTF_KIND_ARRAY] =	{	sizeof(struct btf_array),	0,				0 },
44 [BTF_KIND_STRUCT] =	{	0,				sizeof(struct btf_member),	0 },
45 [BTF_KIND_UNION] =	{	0,				sizeof(struct btf_member),	0 },
46 [BTF_KIND_ENUM] =	{	0,				sizeof(struct btf_enum),	0 },
47 [BTF_KIND_FWD] =	{	0,				0,				0 },
48 [BTF_KIND_TYPEDEF] =	{	0,				0,				0 },
49 [BTF_KIND_VOLATILE] =	{	0,				0,				0 },
50 [BTF_KIND_CONST] =	{	0,				0,				0 },
51 [BTF_KIND_RESTRICT] =	{	0,				0,				0 },
52 [BTF_KIND_FUNC] =	{	0,				0,				0 },
53 [BTF_KIND_FUNC_PROTO] =	{	0,				sizeof(struct btf_param),	0 },
54 [BTF_KIND_VAR] =	{	sizeof(struct btf_var),		0,				0 },
55 [BTF_KIND_DATASEC] =	{	0,				sizeof(struct btf_var_secinfo),	0 },
56 [BTF_KIND_FLOAT] =	{	0,				0,				0 },
57 [BTF_KIND_DECL_TAG] =	{	sizeof(struct btf_decl_tag),	0,				0 },
58 [BTF_KIND_TYPE_TAG] =	{	0,				0,				0 },
59 [BTF_KIND_ENUM64] =	{	0,				sizeof(struct btf_enum64),	0 },
60 [BTF_KIND_LOC_PARAM] =	{	sizeof(struct btf_loc_param),	sizeof(__u32),			0 },
61 [BTF_KIND_LOC_PROTO] =	{	0,				sizeof(__u32),			0 },
62 [BTF_KIND_LOCSEC] =	{	0,				sizeof(struct btf_loc),		0 },
63 };
64 
65 struct btf {
66 	/* raw BTF data in native endianness */
67 	void *raw_data;
68 	/* raw BTF data in non-native endianness */
69 	void *raw_data_swapped;
70 	__u32 raw_size;
71 	/* whether target endianness differs from the native one */
72 	bool swapped_endian;
73 
74 	/*
75 	 * When BTF is loaded from an ELF or raw memory it is stored
76 	 * in a contiguous memory block. The type_data, layout and strs_data
77 	 * point inside that memory region to their respective parts of BTF
78 	 * representation:
79 	 *
80 	 * +----------------------------------------+---------------+
81 	 * |  Header  |  Types  |  Optional layout  |  Strings      |
82 	 * +--------------------------------------------------------+
83 	 * ^          ^         ^                   ^
84 	 * |          |         |                   |
85 	 * raw_data   |         |                   |
86 	 * types_data-+         |                   |
87 	 * layout---------------+                   |
88 	 * strs_data--------------------------------+
89 	 *
90 	 * A separate struct btf_header is embedded as btf->hdr,
91 	 * and header information is copied into it.  This allows us
92 	 * to handle header data for various header formats; the original,
93 	 * the extended header with layout info, etc.
94 	 *
95 	 * If BTF data is later modified, e.g., due to types added or
96 	 * removed, BTF deduplication performed, etc, this contiguous
97 	 * representation is broken up into four independent memory
98 	 * regions.
99 	 *
100 	 * raw_data is nulled out at that point, but can be later allocated
101 	 * and cached again if user calls btf__raw_data(), at which point
102 	 * raw_data will contain a contiguous copy of header, types, optional
103 	 * layout and strings.  layout optionally points to a
104 	 * btf_layout array - this allows us to encode information about
105 	 * the kinds known at encoding time.  If layout is NULL no
106 	 * layout information is encoded.
107 	 *
108 	 * +----------+  +---------+  +-----------+   +-----------+
109 	 * |  Header  |  |  Types  |  |  Layout   |   |  Strings  |
110 	 * +----------+  +---------+  +-----------+   +-----------+
111 	 * ^             ^            ^               ^
112 	 * |             |            |               |
113 	 * hdr           |            |               |
114 	 * types_data----+            |               |
115 	 * layout---------------------+               |
116 	 * strset__data(strs_set)---------------------+
117 	 *
118 	 *               +----------+---------+-------------------+-----------+
119 	 *               |  Header  |  Types  |  Optional Layout  |  Strings  |
120 	 * raw_data----->+----------+---------+-------------------+-----------+
121 	 */
122 	struct btf_header hdr;
123 
124 	void *types_data;
125 	size_t types_data_cap; /* used size stored in hdr->type_len */
126 
127 	/* type ID to `struct btf_type *` lookup index
128 	 * type_offs[0] corresponds to the first non-VOID type:
129 	 *   - for base BTF it's type [1];
130 	 *   - for split BTF it's the first non-base BTF type.
131 	 */
132 	__u32 *type_offs;
133 	size_t type_offs_cap;
134 	/* number of types in this BTF instance:
135 	 *   - doesn't include special [0] void type;
136 	 *   - for split BTF counts number of types added on top of base BTF.
137 	 */
138 	__u32 nr_types;
139 	/* the start IDs of named types in sorted BTF */
140 	int named_start_id;
141 	/* if not NULL, points to the base BTF on top of which the current
142 	 * split BTF is based
143 	 */
144 	struct btf *base_btf;
145 	/* BTF type ID of the first type in this BTF instance:
146 	 *   - for base BTF it's equal to 1;
147 	 *   - for split BTF it's equal to biggest type ID of base BTF plus 1.
148 	 */
149 	int start_id;
150 	/* logical string offset of this BTF instance:
151 	 *   - for base BTF it's equal to 0;
152 	 *   - for split BTF it's equal to total size of base BTF's string section size.
153 	 */
154 	int start_str_off;
155 
156 	/* only one of strs_data or strs_set can be non-NULL, depending on
157 	 * whether BTF is in a modifiable state (strs_set is used) or not
158 	 * (strs_data points inside raw_data)
159 	 */
160 	void *strs_data;
161 	/* a set of unique strings */
162 	struct strset *strs_set;
163 	/* whether strings are already deduplicated */
164 	bool strs_deduped;
165 
166 	/* whether base_btf should be freed in btf_free for this instance */
167 	bool owns_base;
168 
169 	/* whether raw_data is a (read-only) mmap */
170 	bool raw_data_is_mmap;
171 
172 	/* is BTF modifiable? i.e. is it split into separate sections as described above? */
173 	bool modifiable;
174 	/* does BTF have header information we do not support?  If so, disallow
175 	 * modification.
176 	 */
177 	bool has_hdr_extra;
178 	/* Points either at raw kind layout data in parsed BTF (if present), or
179 	 * at an allocated kind layout array when BTF is modifiable.
180 	 */
181 	void *layout;
182 
183 	/* BTF object FD, if loaded into kernel */
184 	int fd;
185 
186 	/* Pointer size (in bytes) for a target architecture of this BTF */
187 	int ptr_sz;
188 };
189 
190 static inline __u64 ptr_to_u64(const void *ptr)
191 {
192 	return (__u64) (unsigned long) ptr;
193 }
194 
195 /* Ensure given dynamically allocated memory region pointed to by *data* with
196  * capacity of *cap_cnt* elements each taking *elem_sz* bytes has enough
197  * memory to accommodate *add_cnt* new elements, assuming *cur_cnt* elements
198  * are already used. At most *max_cnt* elements can be ever allocated.
199  * If necessary, memory is reallocated and all existing data is copied over,
200  * new pointer to the memory region is stored at *data, new memory region
201  * capacity (in number of elements) is stored in *cap.
202  * On success, memory pointer to the beginning of unused memory is returned.
203  * On error, NULL is returned.
204  */
205 void *libbpf_add_mem(void **data, size_t *cap_cnt, size_t elem_sz,
206 		     size_t cur_cnt, size_t max_cnt, size_t add_cnt)
207 {
208 	size_t new_cnt;
209 	void *new_data;
210 
211 	if (cur_cnt + add_cnt <= *cap_cnt)
212 		return *data + cur_cnt * elem_sz;
213 
214 	/* requested more than the set limit */
215 	if (cur_cnt + add_cnt > max_cnt)
216 		return NULL;
217 
218 	new_cnt = *cap_cnt;
219 	new_cnt += new_cnt / 4;		  /* expand by 25% */
220 	if (new_cnt < 16)		  /* but at least 16 elements */
221 		new_cnt = 16;
222 	if (new_cnt > max_cnt)		  /* but not exceeding a set limit */
223 		new_cnt = max_cnt;
224 	if (new_cnt < cur_cnt + add_cnt)  /* also ensure we have enough memory */
225 		new_cnt = cur_cnt + add_cnt;
226 
227 	new_data = libbpf_reallocarray(*data, new_cnt, elem_sz);
228 	if (!new_data)
229 		return NULL;
230 
231 	/* zero out newly allocated portion of memory */
232 	memset(new_data + (*cap_cnt) * elem_sz, 0, (new_cnt - *cap_cnt) * elem_sz);
233 
234 	*data = new_data;
235 	*cap_cnt = new_cnt;
236 	return new_data + cur_cnt * elem_sz;
237 }
238 
239 /* Ensure given dynamically allocated memory region has enough allocated space
240  * to accommodate *need_cnt* elements of size *elem_sz* bytes each
241  */
242 int libbpf_ensure_mem(void **data, size_t *cap_cnt, size_t elem_sz, size_t need_cnt)
243 {
244 	void *p;
245 
246 	if (need_cnt <= *cap_cnt)
247 		return 0;
248 
249 	p = libbpf_add_mem(data, cap_cnt, elem_sz, *cap_cnt, SIZE_MAX, need_cnt - *cap_cnt);
250 	if (!p)
251 		return -ENOMEM;
252 
253 	return 0;
254 }
255 
256 static void *btf_add_type_offs_mem(struct btf *btf, size_t add_cnt)
257 {
258 	return libbpf_add_mem((void **)&btf->type_offs, &btf->type_offs_cap, sizeof(__u32),
259 			      btf->nr_types, BTF_MAX_NR_TYPES, add_cnt);
260 }
261 
262 static int btf_add_type_idx_entry(struct btf *btf, __u32 type_off)
263 {
264 	__u32 *p;
265 
266 	p = btf_add_type_offs_mem(btf, 1);
267 	if (!p)
268 		return -ENOMEM;
269 
270 	*p = type_off;
271 	return 0;
272 }
273 
274 static void btf_bswap_hdr(struct btf_header *h, __u32 hdr_len)
275 {
276 	h->magic = bswap_16(h->magic);
277 	h->hdr_len = bswap_32(h->hdr_len);
278 	h->type_off = bswap_32(h->type_off);
279 	h->type_len = bswap_32(h->type_len);
280 	h->str_off = bswap_32(h->str_off);
281 	h->str_len = bswap_32(h->str_len);
282 	/* May be operating on raw data with hdr_len that does not include below fields */
283 	if (hdr_len >= sizeof(struct btf_header)) {
284 		h->layout_off = bswap_32(h->layout_off);
285 		h->layout_len = bswap_32(h->layout_len);
286 	}
287 }
288 
289 static int btf_parse_hdr(struct btf *btf)
290 {
291 	struct btf_header *hdr = btf->raw_data;
292 	__u32 hdr_len, meta_left;
293 
294 	if (btf->raw_size < offsetofend(struct btf_header, str_len)) {
295 		pr_debug("BTF header not found\n");
296 		return -EINVAL;
297 	}
298 
299 	hdr_len = hdr->hdr_len;
300 
301 	if (hdr->magic == bswap_16(BTF_MAGIC)) {
302 		btf->swapped_endian = true;
303 		hdr_len = bswap_32(hdr->hdr_len);
304 		if (hdr_len < offsetofend(struct btf_header, str_len)) {
305 			pr_warn("Can't load BTF with non-native endianness due to unsupported header length %u\n",
306 				hdr_len);
307 			return -ENOTSUP;
308 		}
309 	} else if (hdr->magic != BTF_MAGIC) {
310 		pr_debug("Invalid BTF magic: %x\n", hdr->magic);
311 		return -EINVAL;
312 	}
313 
314 	if (btf->raw_size < hdr_len) {
315 		pr_debug("BTF header len %u larger than data size %u\n",
316 			 hdr_len, btf->raw_size);
317 		return -EINVAL;
318 	}
319 
320 	if (btf->swapped_endian)
321 		btf_bswap_hdr(hdr, hdr_len);
322 
323 	memcpy(&btf->hdr, hdr, min((size_t)hdr_len, sizeof(struct btf_header)));
324 
325 	/* If unknown header data is found, modification is prohibited in
326 	 * btf_ensure_modifiable().
327 	 */
328 	if (hdr_len > sizeof(struct btf_header)) {
329 		__u8 *h = (__u8 *)hdr;
330 		__u32 i;
331 
332 		for (i = sizeof(struct btf_header); i < hdr_len; i++) {
333 			if (!h[i])
334 				continue;
335 			btf->has_hdr_extra = true;
336 			pr_debug("Unknown BTF header data at offset %u; modification is disallowed\n",
337 				 i);
338 			break;
339 		}
340 	}
341 
342 	meta_left = btf->raw_size - hdr_len;
343 	if (meta_left < (long long)btf->hdr.str_off + btf->hdr.str_len) {
344 		pr_debug("Invalid BTF total size: %u\n", btf->raw_size);
345 		return -EINVAL;
346 	}
347 
348 	if ((long long)btf->hdr.type_off + btf->hdr.type_len > btf->hdr.str_off) {
349 		pr_debug("Invalid BTF data sections layout: type data at %u + %u, strings data at %u + %u\n",
350 			 btf->hdr.type_off, btf->hdr.type_len, btf->hdr.str_off,
351 			 btf->hdr.str_len);
352 		return -EINVAL;
353 	}
354 
355 	if (btf->hdr.type_off % 4) {
356 		pr_debug("BTF type section is not aligned to 4 bytes\n");
357 		return -EINVAL;
358 	}
359 
360 	if (btf->hdr.layout_len == 0)
361 		return 0;
362 
363 	/* optional layout section sits between types and strings */
364 	if (btf->hdr.layout_off % 4) {
365 		pr_debug("BTF layout section is not aligned to 4 bytes\n");
366 		return -EINVAL;
367 	}
368 	if (btf->hdr.layout_off < (long long)btf->hdr.type_off + btf->hdr.type_len) {
369 		pr_debug("Invalid BTF data sections layout: type data at %u + %u,  layout data at %u + %u\n",
370 			 btf->hdr.type_off, btf->hdr.type_len,
371 			 btf->hdr.layout_off, btf->hdr.layout_len);
372 		return -EINVAL;
373 	}
374 	if ((long long)btf->hdr.layout_off + btf->hdr.layout_len > btf->hdr.str_off ||
375 	    btf->hdr.layout_off > btf->hdr.str_off) {
376 		pr_debug("Invalid BTF data sections layout: layout data at %u + %u, strings data at %u\n",
377 			 btf->hdr.layout_off, btf->hdr.layout_len, btf->hdr.str_off);
378 		return -EINVAL;
379 	}
380 	return 0;
381 }
382 
383 static int btf_parse_str_sec(struct btf *btf)
384 {
385 	const char *start = btf->strs_data;
386 	const char *end = start + btf->hdr.str_len;
387 
388 	if (btf->base_btf && btf->hdr.str_len == 0)
389 		return 0;
390 	if (!btf->hdr.str_len || btf->hdr.str_len - 1 > BTF_MAX_STR_OFFSET || end[-1]) {
391 		pr_debug("Invalid BTF string section\n");
392 		return -EINVAL;
393 	}
394 	if (!btf->base_btf && start[0]) {
395 		pr_debug("Malformed BTF string section, did you forget to provide base BTF?\n");
396 		return -EINVAL;
397 	}
398 	return 0;
399 }
400 
401 static int btf_parse_layout_sec(struct btf *btf)
402 {
403 	if (!btf->hdr.layout_len)
404 		return 0;
405 
406 	if (btf->hdr.layout_len % sizeof(struct btf_layout) != 0) {
407 		pr_debug("Invalid BTF kind layout section\n");
408 		return -EINVAL;
409 	}
410 	btf->layout = btf->raw_data + btf->hdr.hdr_len + btf->hdr.layout_off;
411 
412 	if (btf->swapped_endian) {
413 		struct btf_layout *l, *end = btf->layout + btf->hdr.layout_len;
414 
415 		for (l = btf->layout; l < end; l++)
416 			l->flags = bswap_16(l->flags);
417 	}
418 
419 	return 0;
420 }
421 
422 /* for unknown kinds, consult kind layout. */
423 static int btf_type_size_unknown(const struct btf *btf, const struct btf_type *t)
424 {
425 	__u32 l_cnt = btf->hdr.layout_len / sizeof(struct btf_layout);
426 	struct btf_layout *l = btf->layout;
427 	__u32 vlen = btf_vlen(t);
428 	__u32 kind = btf_kind(t);
429 
430 	/* Fall back to base BTF if needed as they share layout information */
431 	if (!l) {
432 		struct btf *base_btf = btf->base_btf;
433 
434 		if (base_btf) {
435 			l = base_btf->layout;
436 			l_cnt = base_btf->hdr.layout_len / sizeof(struct btf_layout);
437 		}
438 	}
439 	if (!l || kind >= l_cnt) {
440 		pr_debug("Unsupported BTF_KIND: %u\n", btf_kind(t));
441 		return -EINVAL;
442 	}
443 	if (l[kind].info_sz % 4) {
444 		pr_debug("Unsupported info_sz %u for kind %u\n",
445 			  l[kind].info_sz, kind);
446 		return -EINVAL;
447 	}
448 	if (l[kind].elem_sz % 4) {
449 		pr_debug("Unsupported elem_sz %u for kind %u\n",
450 			 l[kind].elem_sz, kind);
451 		return -EINVAL;
452 	}
453 
454 	return sizeof(struct btf_type) + l[kind].info_sz + vlen * l[kind].elem_sz;
455 }
456 
457 static int btf_type_size(const struct btf *btf, const struct btf_type *t)
458 {
459 	const int base_size = sizeof(struct btf_type);
460 	__u32 vlen = btf_vlen(t);
461 
462 	switch (btf_kind(t)) {
463 	case BTF_KIND_FWD:
464 	case BTF_KIND_CONST:
465 	case BTF_KIND_VOLATILE:
466 	case BTF_KIND_RESTRICT:
467 	case BTF_KIND_PTR:
468 	case BTF_KIND_TYPEDEF:
469 	case BTF_KIND_FUNC:
470 	case BTF_KIND_FLOAT:
471 	case BTF_KIND_TYPE_TAG:
472 		return base_size;
473 	case BTF_KIND_INT:
474 		return base_size + sizeof(__u32);
475 	case BTF_KIND_ENUM:
476 		return base_size + vlen * sizeof(struct btf_enum);
477 	case BTF_KIND_ENUM64:
478 		return base_size + vlen * sizeof(struct btf_enum64);
479 	case BTF_KIND_ARRAY:
480 		return base_size + sizeof(struct btf_array);
481 	case BTF_KIND_STRUCT:
482 	case BTF_KIND_UNION:
483 		return base_size + vlen * sizeof(struct btf_member);
484 	case BTF_KIND_FUNC_PROTO:
485 		return base_size + vlen * sizeof(struct btf_param);
486 	case BTF_KIND_VAR:
487 		return base_size + sizeof(struct btf_var);
488 	case BTF_KIND_DATASEC:
489 		return base_size + vlen * sizeof(struct btf_var_secinfo);
490 	case BTF_KIND_DECL_TAG:
491 		return base_size + sizeof(struct btf_decl_tag);
492 	case BTF_KIND_LOC_PARAM:
493 		return base_size + sizeof(struct btf_loc_param) + vlen * sizeof(__u32);
494 	case BTF_KIND_LOC_PROTO:
495 		return base_size + vlen * sizeof(__u32);
496 	case BTF_KIND_LOCSEC:
497 		return base_size + vlen * sizeof(struct btf_loc);
498 	default:
499 		return btf_type_size_unknown(btf, t);
500 	}
501 }
502 
503 static void btf_bswap_type_base(struct btf_type *t)
504 {
505 	t->name_off = bswap_32(t->name_off);
506 	t->info = bswap_32(t->info);
507 	t->type = bswap_32(t->type);
508 }
509 
510 static int btf_bswap_type_rest(struct btf_type *t)
511 {
512 	struct btf_var_secinfo *v;
513 	struct btf_loc_param *lp;
514 	struct btf_enum64 *e64;
515 	struct btf_member *m;
516 	struct btf_array *a;
517 	struct btf_param *p;
518 	struct btf_enum *e;
519 	struct btf_loc *l;
520 	__u32 vlen = btf_vlen(t);
521 	__u32 *d;
522 	int i;
523 
524 	switch (btf_kind(t)) {
525 	case BTF_KIND_FWD:
526 	case BTF_KIND_CONST:
527 	case BTF_KIND_VOLATILE:
528 	case BTF_KIND_RESTRICT:
529 	case BTF_KIND_PTR:
530 	case BTF_KIND_TYPEDEF:
531 	case BTF_KIND_FUNC:
532 	case BTF_KIND_FLOAT:
533 	case BTF_KIND_TYPE_TAG:
534 		return 0;
535 	case BTF_KIND_INT:
536 		*(__u32 *)(t + 1) = bswap_32(*(__u32 *)(t + 1));
537 		return 0;
538 	case BTF_KIND_ENUM:
539 		for (i = 0, e = btf_enum(t); i < vlen; i++, e++) {
540 			e->name_off = bswap_32(e->name_off);
541 			e->val = bswap_32(e->val);
542 		}
543 		return 0;
544 	case BTF_KIND_ENUM64:
545 		for (i = 0, e64 = btf_enum64(t); i < vlen; i++, e64++) {
546 			e64->name_off = bswap_32(e64->name_off);
547 			e64->val_lo32 = bswap_32(e64->val_lo32);
548 			e64->val_hi32 = bswap_32(e64->val_hi32);
549 		}
550 		return 0;
551 	case BTF_KIND_ARRAY:
552 		a = btf_array(t);
553 		a->type = bswap_32(a->type);
554 		a->index_type = bswap_32(a->index_type);
555 		a->nelems = bswap_32(a->nelems);
556 		return 0;
557 	case BTF_KIND_STRUCT:
558 	case BTF_KIND_UNION:
559 		for (i = 0, m = btf_members(t); i < vlen; i++, m++) {
560 			m->name_off = bswap_32(m->name_off);
561 			m->type = bswap_32(m->type);
562 			m->offset = bswap_32(m->offset);
563 		}
564 		return 0;
565 	case BTF_KIND_FUNC_PROTO:
566 		for (i = 0, p = btf_params(t); i < vlen; i++, p++) {
567 			p->name_off = bswap_32(p->name_off);
568 			p->type = bswap_32(p->type);
569 		}
570 		return 0;
571 	case BTF_KIND_VAR:
572 		btf_var(t)->linkage = bswap_32(btf_var(t)->linkage);
573 		return 0;
574 	case BTF_KIND_DATASEC:
575 		for (i = 0, v = btf_var_secinfos(t); i < vlen; i++, v++) {
576 			v->type = bswap_32(v->type);
577 			v->offset = bswap_32(v->offset);
578 			v->size = bswap_32(v->size);
579 		}
580 		return 0;
581 	case BTF_KIND_DECL_TAG:
582 		btf_decl_tag(t)->component_idx = bswap_32(btf_decl_tag(t)->component_idx);
583 		return 0;
584 	case BTF_KIND_LOC_PARAM:
585 		lp = btf_loc_param(t);
586 		lp->flags = bswap_32(lp->flags);
587 		for (i = 0, d = (__u32 *)(lp + 1); i < vlen; i++, d++)
588 			*d = bswap_32(*d);
589 		return 0;
590 	case BTF_KIND_LOC_PROTO:
591 		for (i = 0, d = btf_loc_proto_params(t); i < vlen; i++, d++)
592 			*d = bswap_32(*d);
593 		return 0;
594 	case BTF_KIND_LOCSEC:
595 		for (i = 0, l = btf_locsec_locs(t); i < vlen; i++, l++) {
596 			l->func = bswap_32(l->func);
597 			l->loc_proto = bswap_32(l->loc_proto);
598 			l->offset = bswap_32(l->offset);
599 		}
600 		return 0;
601 	default:
602 		pr_debug("Unsupported BTF_KIND:%u\n", btf_kind(t));
603 		return -EINVAL;
604 	}
605 }
606 
607 static int btf_parse_type_sec(struct btf *btf)
608 {
609 	void *next_type = btf->types_data;
610 	void *end_type = next_type + btf->hdr.type_len;
611 	int err, type_size;
612 
613 	while (next_type + sizeof(struct btf_type) <= end_type) {
614 		if (btf->swapped_endian)
615 			btf_bswap_type_base(next_type);
616 
617 		type_size = btf_type_size(btf, next_type);
618 		if (type_size < 0)
619 			return type_size;
620 		if (next_type + type_size > end_type) {
621 			pr_warn("BTF type [%u] is malformed\n", btf->start_id + btf->nr_types);
622 			return -EINVAL;
623 		}
624 
625 		if (btf->swapped_endian && btf_bswap_type_rest(next_type))
626 			return -EINVAL;
627 
628 		err = btf_add_type_idx_entry(btf, next_type - btf->types_data);
629 		if (err)
630 			return err;
631 
632 		next_type += type_size;
633 		btf->nr_types++;
634 	}
635 
636 	if (next_type != end_type) {
637 		pr_warn("BTF types data is malformed\n");
638 		return -EINVAL;
639 	}
640 
641 	return 0;
642 }
643 
644 static int btf_validate_str(const struct btf *btf, __u32 str_off, const char *what, __u32 type_id)
645 {
646 	const char *s;
647 
648 	s = btf__str_by_offset(btf, str_off);
649 	if (!s) {
650 		pr_warn("btf: type [%u]: invalid %s (string offset %u)\n", type_id, what, str_off);
651 		return -EINVAL;
652 	}
653 
654 	return 0;
655 }
656 
657 static int btf_validate_id(const struct btf *btf, __u32 id, __u32 ctx_id)
658 {
659 	const struct btf_type *t;
660 
661 	t = btf__type_by_id(btf, id);
662 	if (!t) {
663 		pr_warn("btf: type [%u]: invalid referenced type ID %u\n", ctx_id, id);
664 		return -EINVAL;
665 	}
666 
667 	return 0;
668 }
669 
670 static int btf_validate_type(const struct btf *btf, const struct btf_type *t, __u32 id)
671 {
672 	__u32 kind = btf_kind(t);
673 	int err, i, n;
674 
675 	err = btf_validate_str(btf, t->name_off, "type name", id);
676 	if (err)
677 		return err;
678 
679 	switch (kind) {
680 	case BTF_KIND_UNKN:
681 	case BTF_KIND_INT:
682 	case BTF_KIND_FWD:
683 	case BTF_KIND_FLOAT:
684 		break;
685 	case BTF_KIND_PTR:
686 	case BTF_KIND_TYPEDEF:
687 	case BTF_KIND_VOLATILE:
688 	case BTF_KIND_CONST:
689 	case BTF_KIND_RESTRICT:
690 	case BTF_KIND_VAR:
691 	case BTF_KIND_DECL_TAG:
692 	case BTF_KIND_TYPE_TAG:
693 		err = btf_validate_id(btf, t->type, id);
694 		if (err)
695 			return err;
696 		break;
697 	case BTF_KIND_ARRAY: {
698 		const struct btf_array *a = btf_array(t);
699 
700 		err = btf_validate_id(btf, a->type, id);
701 		err = err ?: btf_validate_id(btf, a->index_type, id);
702 		if (err)
703 			return err;
704 		break;
705 	}
706 	case BTF_KIND_STRUCT:
707 	case BTF_KIND_UNION: {
708 		const struct btf_member *m = btf_members(t);
709 
710 		n = btf_vlen(t);
711 		for (i = 0; i < n; i++, m++) {
712 			err = btf_validate_str(btf, m->name_off, "field name", id);
713 			err = err ?: btf_validate_id(btf, m->type, id);
714 			if (err)
715 				return err;
716 		}
717 		break;
718 	}
719 	case BTF_KIND_ENUM: {
720 		const struct btf_enum *m = btf_enum(t);
721 
722 		n = btf_vlen(t);
723 		for (i = 0; i < n; i++, m++) {
724 			err = btf_validate_str(btf, m->name_off, "enum name", id);
725 			if (err)
726 				return err;
727 		}
728 		break;
729 	}
730 	case BTF_KIND_ENUM64: {
731 		const struct btf_enum64 *m = btf_enum64(t);
732 
733 		n = btf_vlen(t);
734 		for (i = 0; i < n; i++, m++) {
735 			err = btf_validate_str(btf, m->name_off, "enum name", id);
736 			if (err)
737 				return err;
738 		}
739 		break;
740 	}
741 	case BTF_KIND_FUNC: {
742 		const struct btf_type *ft;
743 
744 		err = btf_validate_id(btf, t->type, id);
745 		if (err)
746 			return err;
747 		ft = btf__type_by_id(btf, t->type);
748 		if (btf_kind(ft) != BTF_KIND_FUNC_PROTO) {
749 			pr_warn("btf: type [%u]: referenced type [%u] is not FUNC_PROTO\n", id, t->type);
750 			return -EINVAL;
751 		}
752 		break;
753 	}
754 	case BTF_KIND_FUNC_PROTO: {
755 		const struct btf_param *m = btf_params(t);
756 
757 		n = btf_vlen(t);
758 		for (i = 0; i < n; i++, m++) {
759 			err = btf_validate_str(btf, m->name_off, "param name", id);
760 			err = err ?: btf_validate_id(btf, m->type, id);
761 			if (err)
762 				return err;
763 		}
764 		break;
765 	}
766 	case BTF_KIND_DATASEC: {
767 		const struct btf_var_secinfo *m = btf_var_secinfos(t);
768 
769 		n = btf_vlen(t);
770 		for (i = 0; i < n; i++, m++) {
771 			err = btf_validate_id(btf, m->type, id);
772 			if (err)
773 				return err;
774 		}
775 		break;
776 	}
777 	case BTF_KIND_LOC_PARAM:
778 		break;
779 	case BTF_KIND_LOC_PROTO: {
780 		__u32 *p = btf_loc_proto_params(t);
781 
782 		n = btf_vlen(t);
783 		for (i = 0; i < n; i++, p++) {
784 			err = btf_validate_id(btf, *p, id);
785 			if (err)
786 				return err;
787 		}
788 		break;
789 	}
790 	case BTF_KIND_LOCSEC: {
791 		const struct btf_loc *l = btf_locsec_locs(t);
792 
793 		n = btf_vlen(t);
794 		for (i = 0; i < n; i++, l++) {
795 			if (!err)
796 				err = btf_validate_id(btf, l->func, id);
797 			if (!err)
798 				err = btf_validate_id(btf, l->loc_proto, id);
799 			if (err)
800 				return err;
801 		}
802 		break;
803 	}
804 	default:
805 		/* Kind may be represented in kind layout information. */
806 		if (btf_type_size_unknown(btf, t) < 0) {
807 			pr_warn("btf: type [%u]: unrecognized kind %u\n", id, kind);
808 			return -EINVAL;
809 		}
810 		break;
811 	}
812 	return 0;
813 }
814 
815 /* Validate basic sanity of BTF. It's intentionally less thorough than
816  * kernel's validation and validates only properties of BTF that libbpf relies
817  * on to be correct (e.g., valid type IDs, valid string offsets, etc)
818  */
819 static int btf_sanity_check(const struct btf *btf)
820 {
821 	const struct btf_type *t;
822 	__u32 i, n = btf__type_cnt(btf);
823 	int err;
824 
825 	for (i = btf->start_id; i < n; i++) {
826 		t = btf_type_by_id(btf, i);
827 		err = btf_validate_type(btf, t, i);
828 		if (err)
829 			return err;
830 	}
831 	return 0;
832 }
833 
834 __u32 btf__type_cnt(const struct btf *btf)
835 {
836 	return btf->start_id + btf->nr_types;
837 }
838 
839 const struct btf *btf__base_btf(const struct btf *btf)
840 {
841 	return btf->base_btf;
842 }
843 
844 /* internal helper returning non-const pointer to a type */
845 struct btf_type *btf_type_by_id(const struct btf *btf, __u32 type_id)
846 {
847 	if (type_id == 0)
848 		return &btf_void;
849 	if (type_id < btf->start_id)
850 		return btf_type_by_id(btf->base_btf, type_id);
851 	return btf->types_data + btf->type_offs[type_id - btf->start_id];
852 }
853 
854 const struct btf_type *btf__type_by_id(const struct btf *btf, __u32 type_id)
855 {
856 	if (type_id >= btf->start_id + btf->nr_types)
857 		return errno = EINVAL, NULL;
858 	return btf_type_by_id((struct btf *)btf, type_id);
859 }
860 
861 static int determine_ptr_size(const struct btf *btf)
862 {
863 	static const char * const long_aliases[] = {
864 		"long",
865 		"long int",
866 		"int long",
867 		"unsigned long",
868 		"long unsigned",
869 		"unsigned long int",
870 		"unsigned int long",
871 		"long unsigned int",
872 		"long int unsigned",
873 		"int unsigned long",
874 		"int long unsigned",
875 	};
876 	const struct btf_type *t;
877 	const char *name;
878 	int i, j, n;
879 
880 	if (btf->base_btf && btf->base_btf->ptr_sz > 0)
881 		return btf->base_btf->ptr_sz;
882 
883 	n = btf__type_cnt(btf);
884 	for (i = 1; i < n; i++) {
885 		t = btf__type_by_id(btf, i);
886 		if (!btf_is_int(t))
887 			continue;
888 
889 		if (t->size != 4 && t->size != 8)
890 			continue;
891 
892 		name = btf__name_by_offset(btf, t->name_off);
893 		if (!name)
894 			continue;
895 
896 		for (j = 0; j < ARRAY_SIZE(long_aliases); j++) {
897 			if (strcmp(name, long_aliases[j]) == 0)
898 				return t->size;
899 		}
900 	}
901 
902 	return -1;
903 }
904 
905 static size_t btf_ptr_sz(const struct btf *btf)
906 {
907 	if (!btf->ptr_sz)
908 		((struct btf *)btf)->ptr_sz = determine_ptr_size(btf);
909 	return btf->ptr_sz < 0 ? sizeof(void *) : btf->ptr_sz;
910 }
911 
912 /* Return pointer size this BTF instance assumes. The size is heuristically
913  * determined by looking for 'long' or 'unsigned long' integer type and
914  * recording its size in bytes. If BTF type information doesn't have any such
915  * type, this function returns 0. In the latter case, native architecture's
916  * pointer size is assumed, so will be either 4 or 8, depending on
917  * architecture that libbpf was compiled for. It's possible to override
918  * guessed value by using btf__set_pointer_size() API.
919  */
920 size_t btf__pointer_size(const struct btf *btf)
921 {
922 	if (!btf->ptr_sz)
923 		((struct btf *)btf)->ptr_sz = determine_ptr_size(btf);
924 
925 	if (btf->ptr_sz < 0)
926 		/* not enough BTF type info to guess */
927 		return 0;
928 
929 	return btf->ptr_sz;
930 }
931 
932 /* Override or set pointer size in bytes. Only values of 4 and 8 are
933  * supported.
934  */
935 int btf__set_pointer_size(struct btf *btf, size_t ptr_sz)
936 {
937 	if (ptr_sz != 4 && ptr_sz != 8)
938 		return libbpf_err(-EINVAL);
939 	btf->ptr_sz = ptr_sz;
940 	return 0;
941 }
942 
943 static bool is_host_big_endian(void)
944 {
945 #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
946 	return false;
947 #elif __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
948 	return true;
949 #else
950 # error "Unrecognized __BYTE_ORDER__"
951 #endif
952 }
953 
954 enum btf_endianness btf__endianness(const struct btf *btf)
955 {
956 	if (is_host_big_endian())
957 		return btf->swapped_endian ? BTF_LITTLE_ENDIAN : BTF_BIG_ENDIAN;
958 	else
959 		return btf->swapped_endian ? BTF_BIG_ENDIAN : BTF_LITTLE_ENDIAN;
960 }
961 
962 int btf__set_endianness(struct btf *btf, enum btf_endianness endian)
963 {
964 	if (endian != BTF_LITTLE_ENDIAN && endian != BTF_BIG_ENDIAN)
965 		return libbpf_err(-EINVAL);
966 
967 	btf->swapped_endian = is_host_big_endian() != (endian == BTF_BIG_ENDIAN);
968 	if (!btf->swapped_endian) {
969 		free(btf->raw_data_swapped);
970 		btf->raw_data_swapped = NULL;
971 	}
972 	return 0;
973 }
974 
975 static bool btf_type_is_void(const struct btf_type *t)
976 {
977 	return t == &btf_void || btf_is_fwd(t);
978 }
979 
980 static bool btf_type_is_void_or_null(const struct btf_type *t)
981 {
982 	return !t || btf_type_is_void(t);
983 }
984 
985 #define MAX_RESOLVE_DEPTH 32
986 
987 __s64 btf__resolve_size(const struct btf *btf, __u32 type_id)
988 {
989 	const struct btf_array *array;
990 	const struct btf_type *t;
991 	__u32 nelems = 1;
992 	__s64 size = -1;
993 	int i;
994 
995 	t = btf__type_by_id(btf, type_id);
996 	for (i = 0; i < MAX_RESOLVE_DEPTH && !btf_type_is_void_or_null(t); i++) {
997 		switch (btf_kind(t)) {
998 		case BTF_KIND_INT:
999 		case BTF_KIND_STRUCT:
1000 		case BTF_KIND_UNION:
1001 		case BTF_KIND_ENUM:
1002 		case BTF_KIND_ENUM64:
1003 		case BTF_KIND_DATASEC:
1004 		case BTF_KIND_FLOAT:
1005 			size = t->size;
1006 			goto done;
1007 		case BTF_KIND_PTR:
1008 			size = btf_ptr_sz(btf);
1009 			goto done;
1010 		case BTF_KIND_TYPEDEF:
1011 		case BTF_KIND_VOLATILE:
1012 		case BTF_KIND_CONST:
1013 		case BTF_KIND_RESTRICT:
1014 		case BTF_KIND_VAR:
1015 		case BTF_KIND_DECL_TAG:
1016 		case BTF_KIND_TYPE_TAG:
1017 			type_id = t->type;
1018 			break;
1019 		case BTF_KIND_ARRAY:
1020 			array = btf_array(t);
1021 			if (nelems && array->nelems > UINT32_MAX / nelems)
1022 				return libbpf_err(-E2BIG);
1023 			nelems *= array->nelems;
1024 			type_id = array->type;
1025 			break;
1026 		default:
1027 			return libbpf_err(-EINVAL);
1028 		}
1029 
1030 		t = btf__type_by_id(btf, type_id);
1031 	}
1032 
1033 done:
1034 	if (size < 0)
1035 		return libbpf_err(-EINVAL);
1036 	if (nelems && size > UINT32_MAX / nelems)
1037 		return libbpf_err(-E2BIG);
1038 
1039 	return nelems * size;
1040 }
1041 
1042 int btf__align_of(const struct btf *btf, __u32 id)
1043 {
1044 	const struct btf_type *t = btf__type_by_id(btf, id);
1045 	__u16 kind = btf_kind(t);
1046 
1047 	switch (kind) {
1048 	case BTF_KIND_INT:
1049 	case BTF_KIND_ENUM:
1050 	case BTF_KIND_ENUM64:
1051 	case BTF_KIND_FLOAT:
1052 		return min(btf_ptr_sz(btf), (size_t)t->size);
1053 	case BTF_KIND_PTR:
1054 		return btf_ptr_sz(btf);
1055 	case BTF_KIND_TYPEDEF:
1056 	case BTF_KIND_VOLATILE:
1057 	case BTF_KIND_CONST:
1058 	case BTF_KIND_RESTRICT:
1059 	case BTF_KIND_TYPE_TAG:
1060 		return btf__align_of(btf, t->type);
1061 	case BTF_KIND_ARRAY:
1062 		return btf__align_of(btf, btf_array(t)->type);
1063 	case BTF_KIND_STRUCT:
1064 	case BTF_KIND_UNION: {
1065 		const struct btf_member *m = btf_members(t);
1066 		__u32 vlen = btf_vlen(t);
1067 		int i, max_align = 1, align;
1068 
1069 		for (i = 0; i < vlen; i++, m++) {
1070 			align = btf__align_of(btf, m->type);
1071 			if (align <= 0)
1072 				return libbpf_err(align);
1073 			max_align = max(max_align, align);
1074 
1075 			/* if field offset isn't aligned according to field
1076 			 * type's alignment, then struct must be packed
1077 			 */
1078 			if (btf_member_bitfield_size(t, i) == 0 &&
1079 			    (m->offset % (8 * align)) != 0)
1080 				return 1;
1081 		}
1082 
1083 		/* if struct/union size isn't a multiple of its alignment,
1084 		 * then struct must be packed
1085 		 */
1086 		if ((t->size % max_align) != 0)
1087 			return 1;
1088 
1089 		return max_align;
1090 	}
1091 	default:
1092 		pr_warn("unsupported BTF_KIND:%u\n", btf_kind(t));
1093 		return errno = EINVAL, 0;
1094 	}
1095 }
1096 
1097 int btf__resolve_type(const struct btf *btf, __u32 type_id)
1098 {
1099 	const struct btf_type *t;
1100 	int depth = 0;
1101 
1102 	t = btf__type_by_id(btf, type_id);
1103 	while (depth < MAX_RESOLVE_DEPTH &&
1104 	       !btf_type_is_void_or_null(t) &&
1105 	       (btf_is_mod(t) || btf_is_typedef(t) || btf_is_var(t))) {
1106 		type_id = t->type;
1107 		t = btf__type_by_id(btf, type_id);
1108 		depth++;
1109 	}
1110 
1111 	if (depth == MAX_RESOLVE_DEPTH || btf_type_is_void_or_null(t))
1112 		return libbpf_err(-EINVAL);
1113 
1114 	return type_id;
1115 }
1116 
1117 static void btf_check_sorted(struct btf *btf)
1118 {
1119 	__u32 i, n, named_start_id = 0;
1120 
1121 	n = btf__type_cnt(btf);
1122 	for (i = btf->start_id + 1; i < n; i++) {
1123 		struct btf_type *ta = btf_type_by_id(btf, i - 1);
1124 		struct btf_type *tb = btf_type_by_id(btf, i);
1125 		const char *na = btf__str_by_offset(btf, ta->name_off);
1126 		const char *nb = btf__str_by_offset(btf, tb->name_off);
1127 
1128 		if (strcmp(na, nb) > 0)
1129 			return;
1130 
1131 		if (named_start_id == 0 && na[0] != '\0')
1132 			named_start_id = i - 1;
1133 		if (named_start_id == 0 && nb[0] != '\0')
1134 			named_start_id = i;
1135 	}
1136 
1137 	if (named_start_id)
1138 		btf->named_start_id = named_start_id;
1139 }
1140 
1141 static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,
1142 					   __s32 start_id)
1143 {
1144 	const struct btf_type *t;
1145 	const char *tname;
1146 	__s32 l, r, m;
1147 
1148 	l = start_id;
1149 	r = btf__type_cnt(btf) - 1;
1150 	while (l <= r) {
1151 		m = l + (r - l) / 2;
1152 		t = btf_type_by_id(btf, m);
1153 		tname = btf__str_by_offset(btf, t->name_off);
1154 		if (strcmp(tname, name) >= 0) {
1155 			if (l == r)
1156 				return r;
1157 			r = m;
1158 		} else {
1159 			l = m + 1;
1160 		}
1161 	}
1162 
1163 	return btf__type_cnt(btf);
1164 }
1165 
1166 static __s32 btf_find_by_name_kind(const struct btf *btf, int start_id,
1167 				   const char *type_name, __s32 kind)
1168 {
1169 	__u32 nr_types = btf__type_cnt(btf);
1170 	const struct btf_type *t;
1171 	const char *tname;
1172 	__s32 id;
1173 
1174 	if (start_id < btf->start_id) {
1175 		id = btf_find_by_name_kind(btf->base_btf, start_id,
1176 					   type_name, kind);
1177 		if (id >= 0)
1178 			return id;
1179 		start_id = btf->start_id;
1180 	}
1181 
1182 	if (kind == BTF_KIND_UNKN || strcmp(type_name, "void") == 0)
1183 		return 0;
1184 
1185 	if (btf->named_start_id > 0 && type_name[0]) {
1186 		start_id = max(start_id, btf->named_start_id);
1187 		id = btf_find_type_by_name_bsearch(btf, type_name, start_id);
1188 		for (; id < nr_types; id++) {
1189 			t = btf__type_by_id(btf, id);
1190 			tname = btf__str_by_offset(btf, t->name_off);
1191 			if (strcmp(tname, type_name) != 0)
1192 				return libbpf_err(-ENOENT);
1193 			if (kind < 0 || btf_kind(t) == kind)
1194 				return id;
1195 		}
1196 	} else {
1197 		for (id = start_id; id < nr_types; id++) {
1198 			t = btf_type_by_id(btf, id);
1199 			if (kind > 0 && btf_kind(t) != kind)
1200 				continue;
1201 			tname = btf__str_by_offset(btf, t->name_off);
1202 			if (strcmp(tname, type_name) == 0)
1203 				return id;
1204 		}
1205 	}
1206 
1207 	return libbpf_err(-ENOENT);
1208 }
1209 
1210 /* the kind value of -1 indicates that kind matching should be skipped */
1211 __s32 btf__find_by_name(const struct btf *btf, const char *type_name)
1212 {
1213 	return btf_find_by_name_kind(btf, 1, type_name, -1);
1214 }
1215 
1216 __s32 btf__find_by_name_kind_own(const struct btf *btf, const char *type_name,
1217 				 __u32 kind)
1218 {
1219 	return btf_find_by_name_kind(btf, btf->start_id, type_name, kind);
1220 }
1221 
1222 __s32 btf__find_by_name_kind(const struct btf *btf, const char *type_name,
1223 			     __u32 kind)
1224 {
1225 	return btf_find_by_name_kind(btf, 1, type_name, kind);
1226 }
1227 
1228 static bool btf_is_modifiable(const struct btf *btf)
1229 {
1230 	/* BTF is modifiable if split into multiple sections */
1231 	return btf->modifiable;
1232 }
1233 
1234 static void btf_free_raw_data(struct btf *btf)
1235 {
1236 	if (btf->raw_data_is_mmap) {
1237 		munmap(btf->raw_data, btf->raw_size);
1238 		btf->raw_data_is_mmap = false;
1239 	} else {
1240 		free(btf->raw_data);
1241 	}
1242 	btf->raw_data = NULL;
1243 }
1244 
1245 void btf__free(struct btf *btf)
1246 {
1247 	if (IS_ERR_OR_NULL(btf))
1248 		return;
1249 
1250 	if (btf->fd >= 0)
1251 		close(btf->fd);
1252 
1253 	if (btf_is_modifiable(btf)) {
1254 		/* if BTF was modified after loading, it will have a split
1255 		 * in-memory representation for types, strings and layout
1256 		 * sections, so we need to free all of them individually. It
1257 		 * might still have a cached contiguous raw data present,
1258 		 * which will be unconditionally freed below.
1259 		 */
1260 		free(btf->types_data);
1261 		strset__free(btf->strs_set);
1262 		free(btf->layout);
1263 	}
1264 	btf_free_raw_data(btf);
1265 	free(btf->raw_data_swapped);
1266 	free(btf->type_offs);
1267 	if (btf->owns_base)
1268 		btf__free(btf->base_btf);
1269 	free(btf);
1270 }
1271 
1272 static struct btf *btf_new_empty(struct btf_new_opts *opts)
1273 {
1274 	bool add_layout = OPTS_GET(opts, add_layout, false);
1275 	struct btf *base_btf = OPTS_GET(opts, base_btf, NULL);
1276 	struct btf_header *hdr;
1277 	struct btf *btf;
1278 
1279 	btf = calloc(1, sizeof(*btf));
1280 	if (!btf)
1281 		return ERR_PTR(-ENOMEM);
1282 
1283 	btf->nr_types = 0;
1284 	btf->start_id = 1;
1285 	btf->start_str_off = 0;
1286 	btf->fd = -1;
1287 	btf->ptr_sz = sizeof(void *);
1288 	btf->swapped_endian = false;
1289 	btf->named_start_id = 0;
1290 
1291 	if (base_btf) {
1292 		btf->base_btf = base_btf;
1293 		btf->start_id = btf__type_cnt(base_btf);
1294 		btf->start_str_off = base_btf->hdr.str_len + base_btf->start_str_off;
1295 		btf->swapped_endian = base_btf->swapped_endian;
1296 	}
1297 
1298 	/* +1 for empty string at offset 0 */
1299 	btf->raw_size = sizeof(struct btf_header) + (base_btf ? 0 : 1);
1300 	if (add_layout)
1301 		btf->raw_size += sizeof(layouts);
1302 	btf->raw_data = calloc(1, btf->raw_size);
1303 	if (!btf->raw_data) {
1304 		free(btf);
1305 		return ERR_PTR(-ENOMEM);
1306 	}
1307 
1308 	hdr = btf->raw_data;
1309 	hdr->hdr_len = sizeof(struct btf_header);
1310 	hdr->magic = BTF_MAGIC;
1311 	hdr->version = BTF_VERSION;
1312 
1313 	btf->types_data = btf->raw_data + hdr->hdr_len;
1314 	btf->strs_data = btf->raw_data + hdr->hdr_len;
1315 	hdr->str_len = base_btf ? 0 : 1; /* empty string at offset 0 */
1316 
1317 	if (add_layout) {
1318 		hdr->layout_len = sizeof(layouts);
1319 		btf->layout = layouts;
1320 		/*
1321 		 * No need to swap endianness here as btf_get_raw_data()
1322 		 * will do this for us if btf->swapped_endian is true.
1323 		 */
1324 		memcpy(btf->raw_data + hdr->hdr_len, layouts, sizeof(layouts));
1325 		btf->strs_data += sizeof(layouts);
1326 		hdr->str_off += sizeof(layouts);
1327 	}
1328 
1329 	memcpy(&btf->hdr, hdr, sizeof(*hdr));
1330 
1331 	return btf;
1332 }
1333 
1334 struct btf *btf__new_empty(void)
1335 {
1336 	return libbpf_ptr(btf_new_empty(NULL));
1337 }
1338 
1339 struct btf *btf__new_empty_split(struct btf *base_btf)
1340 {
1341 	LIBBPF_OPTS(btf_new_opts, opts);
1342 
1343 	opts.base_btf = base_btf;
1344 
1345 	return libbpf_ptr(btf_new_empty(&opts));
1346 }
1347 
1348 struct btf *btf__new_empty_opts(struct btf_new_opts *opts)
1349 {
1350 	if (!OPTS_VALID(opts, btf_new_opts))
1351 		return libbpf_err_ptr(-EINVAL);
1352 
1353 	return libbpf_ptr(btf_new_empty(opts));
1354 }
1355 
1356 static struct btf *btf_new(const void *data, __u32 size, struct btf *base_btf, bool is_mmap)
1357 {
1358 	struct btf *btf;
1359 	int err;
1360 
1361 	btf = calloc(1, sizeof(struct btf));
1362 	if (!btf)
1363 		return ERR_PTR(-ENOMEM);
1364 
1365 	btf->nr_types = 0;
1366 	btf->start_id = 1;
1367 	btf->start_str_off = 0;
1368 	btf->fd = -1;
1369 	btf->named_start_id = 0;
1370 
1371 	if (base_btf) {
1372 		btf->base_btf = base_btf;
1373 		btf->start_id = btf__type_cnt(base_btf);
1374 		btf->start_str_off = base_btf->hdr.str_len + base_btf->start_str_off;
1375 	}
1376 
1377 	if (is_mmap) {
1378 		btf->raw_data = (void *)data;
1379 		btf->raw_data_is_mmap = true;
1380 	} else {
1381 		btf->raw_data = malloc(size);
1382 		if (!btf->raw_data) {
1383 			err = -ENOMEM;
1384 			goto done;
1385 		}
1386 		memcpy(btf->raw_data, data, size);
1387 	}
1388 
1389 	btf->raw_size = size;
1390 
1391 	err = btf_parse_hdr(btf);
1392 	if (err)
1393 		goto done;
1394 
1395 	btf->strs_data = btf->raw_data + btf->hdr.hdr_len + btf->hdr.str_off;
1396 	btf->types_data = btf->raw_data + btf->hdr.hdr_len + btf->hdr.type_off;
1397 
1398 	err = btf_parse_str_sec(btf);
1399 	err = err ?: btf_parse_layout_sec(btf);
1400 	err = err ?: btf_parse_type_sec(btf);
1401 	err = err ?: btf_sanity_check(btf);
1402 	if (err)
1403 		goto done;
1404 	btf_check_sorted(btf);
1405 
1406 done:
1407 	if (err) {
1408 		btf__free(btf);
1409 		return ERR_PTR(err);
1410 	}
1411 
1412 	return btf;
1413 }
1414 
1415 struct btf *btf__new(const void *data, __u32 size)
1416 {
1417 	return libbpf_ptr(btf_new(data, size, NULL, false));
1418 }
1419 
1420 struct btf *btf__new_split(const void *data, __u32 size, struct btf *base_btf)
1421 {
1422 	return libbpf_ptr(btf_new(data, size, base_btf, false));
1423 }
1424 
1425 struct btf_elf_secs {
1426 	Elf_Data *btf_data;
1427 	Elf_Data *btf_ext_data;
1428 	Elf_Data *btf_base_data;
1429 };
1430 
1431 static int btf_find_elf_sections(Elf *elf, const char *path, struct btf_elf_secs *secs)
1432 {
1433 	Elf_Scn *scn = NULL;
1434 	Elf_Data *data;
1435 	GElf_Ehdr ehdr;
1436 	size_t shstrndx;
1437 	int idx = 0;
1438 
1439 	if (!gelf_getehdr(elf, &ehdr)) {
1440 		pr_warn("failed to get EHDR from %s\n", path);
1441 		goto err;
1442 	}
1443 
1444 	if (elf_getshdrstrndx(elf, &shstrndx)) {
1445 		pr_warn("failed to get section names section index for %s\n",
1446 			path);
1447 		goto err;
1448 	}
1449 
1450 	if (!elf_rawdata(elf_getscn(elf, shstrndx), NULL)) {
1451 		pr_warn("failed to get e_shstrndx from %s\n", path);
1452 		goto err;
1453 	}
1454 
1455 	while ((scn = elf_nextscn(elf, scn)) != NULL) {
1456 		Elf_Data **field;
1457 		GElf_Shdr sh;
1458 		char *name;
1459 
1460 		idx++;
1461 		if (gelf_getshdr(scn, &sh) != &sh) {
1462 			pr_warn("failed to get section(%d) header from %s\n",
1463 				idx, path);
1464 			goto err;
1465 		}
1466 		name = elf_strptr(elf, shstrndx, sh.sh_name);
1467 		if (!name) {
1468 			pr_warn("failed to get section(%d) name from %s\n",
1469 				idx, path);
1470 			goto err;
1471 		}
1472 
1473 		if (strcmp(name, BTF_ELF_SEC) == 0)
1474 			field = &secs->btf_data;
1475 		else if (strcmp(name, BTF_EXT_ELF_SEC) == 0)
1476 			field = &secs->btf_ext_data;
1477 		else if (strcmp(name, BTF_BASE_ELF_SEC) == 0)
1478 			field = &secs->btf_base_data;
1479 		else
1480 			continue;
1481 
1482 		if (sh.sh_type != SHT_PROGBITS) {
1483 			pr_warn("unexpected section type (%u) of section(%d, %s) from %s\n",
1484 				sh.sh_type, idx, name, path);
1485 			goto err;
1486 		}
1487 
1488 		data = elf_getdata(scn, 0);
1489 		if (!data) {
1490 			pr_warn("failed to get section(%d, %s) data from %s\n",
1491 				idx, name, path);
1492 			goto err;
1493 		}
1494 		*field = data;
1495 	}
1496 
1497 	return 0;
1498 
1499 err:
1500 	return -LIBBPF_ERRNO__FORMAT;
1501 }
1502 
1503 static struct btf *btf_parse_elf(const char *path, struct btf *base_btf,
1504 				 struct btf_ext **btf_ext)
1505 {
1506 	struct btf_elf_secs secs = {};
1507 	struct btf *dist_base_btf = NULL;
1508 	struct btf *btf = NULL;
1509 	int err = 0, fd = -1;
1510 	Elf *elf = NULL;
1511 
1512 	if (elf_version(EV_CURRENT) == EV_NONE) {
1513 		pr_warn("failed to init libelf for %s\n", path);
1514 		return ERR_PTR(-LIBBPF_ERRNO__LIBELF);
1515 	}
1516 
1517 	fd = open(path, O_RDONLY | O_CLOEXEC);
1518 	if (fd < 0) {
1519 		err = -errno;
1520 		pr_warn("failed to open %s: %s\n", path, errstr(err));
1521 		return ERR_PTR(err);
1522 	}
1523 
1524 	elf = elf_begin(fd, ELF_C_READ, NULL);
1525 	if (!elf) {
1526 		err = -LIBBPF_ERRNO__FORMAT;
1527 		pr_warn("failed to open %s as ELF file\n", path);
1528 		goto done;
1529 	}
1530 
1531 	err = btf_find_elf_sections(elf, path, &secs);
1532 	if (err)
1533 		goto done;
1534 
1535 	if (!secs.btf_data) {
1536 		pr_warn("failed to find '%s' ELF section in %s\n", BTF_ELF_SEC, path);
1537 		err = -ENODATA;
1538 		goto done;
1539 	}
1540 
1541 	if (secs.btf_base_data) {
1542 		dist_base_btf = btf_new(secs.btf_base_data->d_buf, secs.btf_base_data->d_size,
1543 					NULL, false);
1544 		if (IS_ERR(dist_base_btf)) {
1545 			err = PTR_ERR(dist_base_btf);
1546 			dist_base_btf = NULL;
1547 			goto done;
1548 		}
1549 	}
1550 
1551 	btf = btf_new(secs.btf_data->d_buf, secs.btf_data->d_size,
1552 		      dist_base_btf ?: base_btf, false);
1553 	if (IS_ERR(btf)) {
1554 		err = PTR_ERR(btf);
1555 		goto done;
1556 	}
1557 	if (dist_base_btf && base_btf) {
1558 		err = btf__relocate(btf, base_btf);
1559 		if (err)
1560 			goto done;
1561 		btf__free(dist_base_btf);
1562 		dist_base_btf = NULL;
1563 	}
1564 
1565 	switch (gelf_getclass(elf)) {
1566 	case ELFCLASS32:
1567 		btf__set_pointer_size(btf, 4);
1568 		break;
1569 	case ELFCLASS64:
1570 		btf__set_pointer_size(btf, 8);
1571 		break;
1572 	default:
1573 		pr_warn("failed to get ELF class (bitness) for %s\n", path);
1574 		break;
1575 	}
1576 
1577 	if (btf_ext && secs.btf_ext_data) {
1578 		*btf_ext = btf_ext__new(secs.btf_ext_data->d_buf, secs.btf_ext_data->d_size);
1579 		if (!*btf_ext) {
1580 			err = -errno;
1581 			goto done;
1582 		}
1583 	} else if (btf_ext) {
1584 		*btf_ext = NULL;
1585 	}
1586 
1587 	if (dist_base_btf)
1588 		btf->owns_base = true;
1589 done:
1590 	if (elf)
1591 		elf_end(elf);
1592 	close(fd);
1593 
1594 	if (!err)
1595 		return btf;
1596 
1597 	if (btf_ext)
1598 		btf_ext__free(*btf_ext);
1599 	btf__free(dist_base_btf);
1600 	btf__free(btf);
1601 
1602 	return ERR_PTR(err);
1603 }
1604 
1605 struct btf *btf__parse_elf(const char *path, struct btf_ext **btf_ext)
1606 {
1607 	return libbpf_ptr(btf_parse_elf(path, NULL, btf_ext));
1608 }
1609 
1610 struct btf *btf__parse_elf_split(const char *path, struct btf *base_btf)
1611 {
1612 	return libbpf_ptr(btf_parse_elf(path, base_btf, NULL));
1613 }
1614 
1615 static struct btf *btf_parse_raw(const char *path, struct btf *base_btf)
1616 {
1617 	struct btf *btf = NULL;
1618 	void *data = NULL;
1619 	FILE *f = NULL;
1620 	__u16 magic;
1621 	int err = 0;
1622 	long sz;
1623 
1624 	f = fopen(path, "rbe");
1625 	if (!f) {
1626 		err = -errno;
1627 		goto err_out;
1628 	}
1629 
1630 	/* check BTF magic */
1631 	if (fread(&magic, 1, sizeof(magic), f) < sizeof(magic)) {
1632 		err = -EIO;
1633 		goto err_out;
1634 	}
1635 	if (magic != BTF_MAGIC && magic != bswap_16(BTF_MAGIC)) {
1636 		/* definitely not a raw BTF */
1637 		err = -EPROTO;
1638 		goto err_out;
1639 	}
1640 
1641 	/* get file size */
1642 	if (fseek(f, 0, SEEK_END)) {
1643 		err = -errno;
1644 		goto err_out;
1645 	}
1646 	sz = ftell(f);
1647 	if (sz < 0) {
1648 		err = -errno;
1649 		goto err_out;
1650 	}
1651 	/* rewind to the start */
1652 	if (fseek(f, 0, SEEK_SET)) {
1653 		err = -errno;
1654 		goto err_out;
1655 	}
1656 
1657 	/* pre-alloc memory and read all of BTF data */
1658 	data = malloc(sz);
1659 	if (!data) {
1660 		err = -ENOMEM;
1661 		goto err_out;
1662 	}
1663 	if (fread(data, 1, sz, f) < sz) {
1664 		err = -EIO;
1665 		goto err_out;
1666 	}
1667 
1668 	/* finally parse BTF data */
1669 	btf = btf_new(data, sz, base_btf, false);
1670 
1671 err_out:
1672 	free(data);
1673 	if (f)
1674 		fclose(f);
1675 	return err ? ERR_PTR(err) : btf;
1676 }
1677 
1678 struct btf *btf__parse_raw(const char *path)
1679 {
1680 	return libbpf_ptr(btf_parse_raw(path, NULL));
1681 }
1682 
1683 struct btf *btf__parse_raw_split(const char *path, struct btf *base_btf)
1684 {
1685 	return libbpf_ptr(btf_parse_raw(path, base_btf));
1686 }
1687 
1688 static struct btf *btf_parse_raw_mmap(const char *path, struct btf *base_btf)
1689 {
1690 	struct stat st;
1691 	void *data;
1692 	struct btf *btf;
1693 	int fd, err;
1694 
1695 	fd = open(path, O_RDONLY);
1696 	if (fd < 0)
1697 		return ERR_PTR(-errno);
1698 
1699 	if (fstat(fd, &st) < 0) {
1700 		err = -errno;
1701 		close(fd);
1702 		return ERR_PTR(err);
1703 	}
1704 
1705 	data = mmap(NULL, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
1706 	err = -errno;
1707 	close(fd);
1708 
1709 	if (data == MAP_FAILED)
1710 		return ERR_PTR(err);
1711 
1712 	btf = btf_new(data, st.st_size, base_btf, true);
1713 	if (IS_ERR(btf))
1714 		munmap(data, st.st_size);
1715 
1716 	return btf;
1717 }
1718 
1719 static struct btf *btf_parse(const char *path, struct btf *base_btf, struct btf_ext **btf_ext)
1720 {
1721 	struct btf *btf;
1722 	int err;
1723 
1724 	if (btf_ext)
1725 		*btf_ext = NULL;
1726 
1727 	btf = btf_parse_raw(path, base_btf);
1728 	err = libbpf_get_error(btf);
1729 	if (!err)
1730 		return btf;
1731 	if (err != -EPROTO)
1732 		return ERR_PTR(err);
1733 	return btf_parse_elf(path, base_btf, btf_ext);
1734 }
1735 
1736 struct btf *btf__parse(const char *path, struct btf_ext **btf_ext)
1737 {
1738 	return libbpf_ptr(btf_parse(path, NULL, btf_ext));
1739 }
1740 
1741 struct btf *btf__parse_split(const char *path, struct btf *base_btf)
1742 {
1743 	return libbpf_ptr(btf_parse(path, base_btf, NULL));
1744 }
1745 
1746 static void *btf_get_raw_data(const struct btf *btf, __u32 *size, bool swap_endian);
1747 
1748 int btf_load_into_kernel(struct btf *btf,
1749 			 char *log_buf, size_t log_sz, __u32 log_level,
1750 			 int token_fd)
1751 {
1752 	LIBBPF_OPTS(bpf_btf_load_opts, opts);
1753 	__u32 buf_sz = 0, raw_size;
1754 	char *buf = NULL, *tmp;
1755 	void *raw_data;
1756 	int err = 0;
1757 
1758 	if (btf->fd >= 0)
1759 		return libbpf_err(-EEXIST);
1760 	if (log_sz && !log_buf)
1761 		return libbpf_err(-EINVAL);
1762 
1763 	/* cache native raw data representation */
1764 	raw_data = btf_get_raw_data(btf, &raw_size, false);
1765 	if (!raw_data) {
1766 		err = -ENOMEM;
1767 		goto done;
1768 	}
1769 	btf->raw_size = raw_size;
1770 	btf->raw_data = raw_data;
1771 
1772 retry_load:
1773 	/* if log_level is 0, we won't provide log_buf/log_size to the kernel,
1774 	 * initially. Only if BTF loading fails, we bump log_level to 1 and
1775 	 * retry, using either auto-allocated or custom log_buf. This way
1776 	 * non-NULL custom log_buf provides a buffer just in case, but hopes
1777 	 * for successful load and no need for log_buf.
1778 	 */
1779 	if (log_level) {
1780 		/* if caller didn't provide custom log_buf, we'll keep
1781 		 * allocating our own progressively bigger buffers for BTF
1782 		 * verification log
1783 		 */
1784 		if (!log_buf) {
1785 			buf_sz = max((__u32)BPF_LOG_BUF_SIZE, buf_sz * 2);
1786 			tmp = realloc(buf, buf_sz);
1787 			if (!tmp) {
1788 				err = -ENOMEM;
1789 				goto done;
1790 			}
1791 			buf = tmp;
1792 			buf[0] = '\0';
1793 		}
1794 
1795 		opts.log_buf = log_buf ? log_buf : buf;
1796 		opts.log_size = log_buf ? log_sz : buf_sz;
1797 		opts.log_level = log_level;
1798 	}
1799 
1800 	opts.token_fd = token_fd;
1801 	if (token_fd)
1802 		opts.btf_flags |= BPF_F_TOKEN_FD;
1803 
1804 	btf->fd = bpf_btf_load(raw_data, raw_size, &opts);
1805 	if (btf->fd < 0) {
1806 		/* time to turn on verbose mode and try again */
1807 		if (log_level == 0) {
1808 			log_level = 1;
1809 			goto retry_load;
1810 		}
1811 		/* only retry if caller didn't provide custom log_buf, but
1812 		 * make sure we can never overflow buf_sz
1813 		 */
1814 		if (!log_buf && errno == ENOSPC && buf_sz <= UINT_MAX / 2)
1815 			goto retry_load;
1816 
1817 		err = -errno;
1818 		pr_warn("BTF loading error: %s\n", errstr(err));
1819 		/* don't print out contents of custom log_buf */
1820 		if (!log_buf && buf[0])
1821 			pr_warn("-- BEGIN BTF LOAD LOG ---\n%s\n-- END BTF LOAD LOG --\n", buf);
1822 	}
1823 
1824 done:
1825 	free(buf);
1826 	return libbpf_err(err);
1827 }
1828 
1829 int btf__load_into_kernel(struct btf *btf)
1830 {
1831 	return btf_load_into_kernel(btf, NULL, 0, 0, 0);
1832 }
1833 
1834 int btf__fd(const struct btf *btf)
1835 {
1836 	return btf->fd;
1837 }
1838 
1839 void btf__set_fd(struct btf *btf, int fd)
1840 {
1841 	btf->fd = fd;
1842 }
1843 
1844 static const void *btf_strs_data(const struct btf *btf)
1845 {
1846 	return btf->strs_data ? btf->strs_data : strset__data(btf->strs_set);
1847 }
1848 
1849 static void *btf_get_raw_data(const struct btf *btf, __u32 *size, bool swap_endian)
1850 {
1851 	const struct btf_header *hdr = &btf->hdr;
1852 	struct btf_type *t;
1853 	void *data, *p;
1854 	__u32 data_sz;
1855 	int i;
1856 
1857 	data = swap_endian ? btf->raw_data_swapped : btf->raw_data;
1858 	if (data) {
1859 		*size = btf->raw_size;
1860 		return data;
1861 	}
1862 
1863 	data_sz = hdr->hdr_len + hdr->type_len + hdr->str_len;
1864 	if (btf->layout)
1865 		data_sz += hdr->layout_len;
1866 
1867 	data = calloc(1, data_sz);
1868 	if (!data)
1869 		return NULL;
1870 	p = data;
1871 
1872 	memcpy(p, hdr, min((__u32)sizeof(struct btf_header), hdr->hdr_len));
1873 	if (swap_endian)
1874 		btf_bswap_hdr(p, hdr->hdr_len);
1875 	p += hdr->hdr_len;
1876 
1877 	memcpy(p, btf->types_data, hdr->type_len);
1878 	if (swap_endian) {
1879 		for (i = 0; i < btf->nr_types; i++) {
1880 			t = p + btf->type_offs[i];
1881 			/* btf_bswap_type_rest() relies on native t->info, so
1882 			 * we swap base type info after we swapped all the
1883 			 * additional information
1884 			 */
1885 			if (btf_bswap_type_rest(t))
1886 				goto err_out;
1887 			btf_bswap_type_base(t);
1888 		}
1889 	}
1890 	p += hdr->type_len;
1891 
1892 	if (btf->layout) {
1893 		memcpy(p, btf->layout, hdr->layout_len);
1894 		if (swap_endian) {
1895 			struct btf_layout *l, *end = p + hdr->layout_len;
1896 
1897 			for (l = p; l < end ; l++)
1898 				l->flags = bswap_16(l->flags);
1899 		}
1900 		p += hdr->layout_len;
1901 	}
1902 
1903 	memcpy(p, btf_strs_data(btf), hdr->str_len);
1904 
1905 	*size = data_sz;
1906 	return data;
1907 err_out:
1908 	free(data);
1909 	return NULL;
1910 }
1911 
1912 const void *btf__raw_data(const struct btf *btf_ro, __u32 *size)
1913 {
1914 	struct btf *btf = (struct btf *)btf_ro;
1915 	__u32 data_sz;
1916 	void *data;
1917 
1918 	data = btf_get_raw_data(btf, &data_sz, btf->swapped_endian);
1919 	if (!data)
1920 		return errno = ENOMEM, NULL;
1921 
1922 	btf->raw_size = data_sz;
1923 	if (btf->swapped_endian)
1924 		btf->raw_data_swapped = data;
1925 	else
1926 		btf->raw_data = data;
1927 	*size = data_sz;
1928 	return data;
1929 }
1930 
1931 __attribute__((alias("btf__raw_data")))
1932 const void *btf__get_raw_data(const struct btf *btf, __u32 *size);
1933 
1934 const char *btf__str_by_offset(const struct btf *btf, __u32 offset)
1935 {
1936 	if (offset < btf->start_str_off)
1937 		return btf__str_by_offset(btf->base_btf, offset);
1938 	else if (offset - btf->start_str_off < btf->hdr.str_len)
1939 		return btf_strs_data(btf) + (offset - btf->start_str_off);
1940 	else
1941 		return errno = EINVAL, NULL;
1942 }
1943 
1944 const char *btf__name_by_offset(const struct btf *btf, __u32 offset)
1945 {
1946 	return btf__str_by_offset(btf, offset);
1947 }
1948 
1949 struct btf *btf_get_from_fd(int btf_fd, struct btf *base_btf)
1950 {
1951 	struct bpf_btf_info btf_info;
1952 	__u32 len = sizeof(btf_info);
1953 	__u32 last_size;
1954 	struct btf *btf;
1955 	void *ptr;
1956 	int err;
1957 
1958 	/* we won't know btf_size until we call bpf_btf_get_info_by_fd(). so
1959 	 * let's start with a sane default - 4KiB here - and resize it only if
1960 	 * bpf_btf_get_info_by_fd() needs a bigger buffer.
1961 	 */
1962 	last_size = 4096;
1963 	ptr = malloc(last_size);
1964 	if (!ptr)
1965 		return ERR_PTR(-ENOMEM);
1966 
1967 	memset(&btf_info, 0, sizeof(btf_info));
1968 	btf_info.btf = ptr_to_u64(ptr);
1969 	btf_info.btf_size = last_size;
1970 	err = bpf_btf_get_info_by_fd(btf_fd, &btf_info, &len);
1971 
1972 	if (!err && btf_info.btf_size > last_size) {
1973 		void *temp_ptr;
1974 
1975 		last_size = btf_info.btf_size;
1976 		temp_ptr = realloc(ptr, last_size);
1977 		if (!temp_ptr) {
1978 			btf = ERR_PTR(-ENOMEM);
1979 			goto exit_free;
1980 		}
1981 		ptr = temp_ptr;
1982 
1983 		len = sizeof(btf_info);
1984 		memset(&btf_info, 0, sizeof(btf_info));
1985 		btf_info.btf = ptr_to_u64(ptr);
1986 		btf_info.btf_size = last_size;
1987 
1988 		err = bpf_btf_get_info_by_fd(btf_fd, &btf_info, &len);
1989 	}
1990 
1991 	if (err || btf_info.btf_size > last_size) {
1992 		btf = err ? ERR_PTR(-errno) : ERR_PTR(-E2BIG);
1993 		goto exit_free;
1994 	}
1995 
1996 	btf = btf_new(ptr, btf_info.btf_size, base_btf, false);
1997 
1998 exit_free:
1999 	free(ptr);
2000 	return btf;
2001 }
2002 
2003 struct btf *btf_load_from_kernel(__u32 id, struct btf *base_btf, int token_fd)
2004 {
2005 	struct btf *btf;
2006 	int btf_fd;
2007 	LIBBPF_OPTS(bpf_get_fd_by_id_opts, opts);
2008 
2009 	if (token_fd) {
2010 		opts.open_flags |= BPF_F_TOKEN_FD;
2011 		opts.token_fd = token_fd;
2012 	}
2013 
2014 	btf_fd = bpf_btf_get_fd_by_id_opts(id, &opts);
2015 	if (btf_fd < 0)
2016 		return libbpf_err_ptr(-errno);
2017 
2018 	btf = btf_get_from_fd(btf_fd, base_btf);
2019 	close(btf_fd);
2020 
2021 	return libbpf_ptr(btf);
2022 }
2023 
2024 struct btf *btf__load_from_kernel_by_id_split(__u32 id, struct btf *base_btf)
2025 {
2026 	return btf_load_from_kernel(id, base_btf, 0);
2027 }
2028 
2029 struct btf *btf__load_from_kernel_by_id(__u32 id)
2030 {
2031 	return btf__load_from_kernel_by_id_split(id, NULL);
2032 }
2033 
2034 static void btf_invalidate_raw_data(struct btf *btf)
2035 {
2036 	if (btf->raw_data)
2037 		btf_free_raw_data(btf);
2038 	if (btf->raw_data_swapped) {
2039 		free(btf->raw_data_swapped);
2040 		btf->raw_data_swapped = NULL;
2041 	}
2042 	btf->named_start_id = 0;
2043 }
2044 
2045 /* Ensure BTF is ready to be modified (by splitting into a three memory
2046  * regions for types, strings and layout. Also invalidate cached
2047  * raw_data, if any.
2048  */
2049 static int btf_ensure_modifiable(struct btf *btf)
2050 {
2051 	void *types, *layout = NULL;
2052 	struct strset *set = NULL;
2053 	int err = -ENOMEM;
2054 
2055 	if (btf_is_modifiable(btf)) {
2056 		/* any BTF modification invalidates raw_data */
2057 		btf_invalidate_raw_data(btf);
2058 		return 0;
2059 	}
2060 
2061 	if (btf->has_hdr_extra) {
2062 		/* Additional BTF header data was found; not safe to modify. */
2063 		return -EOPNOTSUPP;
2064 	}
2065 
2066 	/* split raw data into memory regions; btf->hdr is done already. */
2067 	types = malloc(btf->hdr.type_len);
2068 	if (!types)
2069 		goto err_out;
2070 	memcpy(types, btf->types_data, btf->hdr.type_len);
2071 
2072 	if (btf->hdr.layout_len) {
2073 		layout = malloc(btf->hdr.layout_len);
2074 		if (!layout)
2075 			goto err_out;
2076 		memcpy(layout, btf->raw_data + btf->hdr.hdr_len + btf->hdr.layout_off,
2077 		       btf->hdr.layout_len);
2078 	}
2079 
2080 	/* build lookup index for all strings */
2081 	set = strset__new(BTF_MAX_STR_OFFSET, btf->strs_data, btf->hdr.str_len);
2082 	if (IS_ERR(set)) {
2083 		err = PTR_ERR(set);
2084 		goto err_out;
2085 	}
2086 
2087 	/* only when everything was successful, update internal state */
2088 	btf->types_data = types;
2089 	btf->types_data_cap = btf->hdr.type_len;
2090 	btf->strs_data = NULL;
2091 	btf->strs_set = set;
2092 	if (layout)
2093 		btf->layout = layout;
2094 	/* if BTF was created from scratch, all strings are guaranteed to be
2095 	 * unique and deduplicated
2096 	 */
2097 	if (btf->hdr.str_len == 0)
2098 		btf->strs_deduped = true;
2099 	if (!btf->base_btf && btf->hdr.str_len == 1)
2100 		btf->strs_deduped = true;
2101 
2102 	/* invalidate raw_data representation */
2103 	btf_invalidate_raw_data(btf);
2104 
2105 	btf->modifiable = true;
2106 
2107 	return 0;
2108 
2109 err_out:
2110 	strset__free(set);
2111 	free(types);
2112 	free(layout);
2113 	return err;
2114 }
2115 
2116 /* Find an offset in BTF string section that corresponds to a given string *s*.
2117  * Returns:
2118  *   - >0 offset into string section, if string is found;
2119  *   - -ENOENT, if string is not in the string section;
2120  *   - <0, on any other error.
2121  */
2122 int btf__find_str(struct btf *btf, const char *s)
2123 {
2124 	int off;
2125 	int err;
2126 
2127 	if (btf->base_btf) {
2128 		off = btf__find_str(btf->base_btf, s);
2129 		if (off != -ENOENT)
2130 			return off;
2131 	}
2132 
2133 	/* BTF needs to be in a modifiable state to build string lookup index */
2134 	err = btf_ensure_modifiable(btf);
2135 	if (err)
2136 		return libbpf_err(err);
2137 
2138 	off = strset__find_str(btf->strs_set, s);
2139 	if (off < 0)
2140 		return libbpf_err(off);
2141 
2142 	return btf->start_str_off + off;
2143 }
2144 
2145 /* Add a string s to the BTF string section.
2146  * Returns:
2147  *   - > 0 offset into string section, on success;
2148  *   - < 0, on error.
2149  */
2150 int btf__add_str(struct btf *btf, const char *s)
2151 {
2152 	int off;
2153 	int err;
2154 
2155 	if (btf->base_btf) {
2156 		off = btf__find_str(btf->base_btf, s);
2157 		if (off != -ENOENT)
2158 			return off;
2159 	}
2160 
2161 	err = btf_ensure_modifiable(btf);
2162 	if (err)
2163 		return libbpf_err(err);
2164 
2165 	off = strset__add_str(btf->strs_set, s);
2166 	if (off < 0)
2167 		return libbpf_err(off);
2168 
2169 	btf->hdr.str_len = strset__data_size(btf->strs_set);
2170 
2171 	return btf->start_str_off + off;
2172 }
2173 
2174 static void *btf_add_type_mem(struct btf *btf, size_t add_sz)
2175 {
2176 	return libbpf_add_mem(&btf->types_data, &btf->types_data_cap, 1,
2177 			      btf->hdr.type_len, UINT_MAX, add_sz);
2178 }
2179 
2180 static int btf_type_inc_vlen(struct btf_type *t)
2181 {
2182 	if (btf_vlen(t) == BTF_MAX_VLEN)
2183 		return -ENOSPC;
2184 	t->info = btf_type_info(btf_kind(t), btf_vlen(t) + 1, btf_kflag(t));
2185 	return 0;
2186 }
2187 
2188 static void btf_hdr_update_type_len(struct btf *btf, int new_len)
2189 {
2190 	btf->hdr.type_len = new_len;
2191 	if (btf->layout) {
2192 		btf->hdr.layout_off = btf->hdr.type_off + new_len;
2193 		btf->hdr.str_off = btf->hdr.layout_off + btf->hdr.layout_len;
2194 	} else {
2195 		btf->hdr.str_off = btf->hdr.type_off + new_len;
2196 	}
2197 }
2198 
2199 static void btf_hdr_update_str_len(struct btf *btf, int new_len)
2200 {
2201 	btf->hdr.str_len = new_len;
2202 }
2203 
2204 static int btf_commit_type(struct btf *btf, int data_sz)
2205 {
2206 	int err;
2207 
2208 	err = btf_add_type_idx_entry(btf, btf->hdr.type_len);
2209 	if (err)
2210 		return libbpf_err(err);
2211 
2212 	btf_hdr_update_type_len(btf, btf->hdr.type_len + data_sz);
2213 	btf->nr_types++;
2214 	return btf->start_id + btf->nr_types - 1;
2215 }
2216 
2217 struct btf_pipe {
2218 	const struct btf *src;
2219 	struct btf *dst;
2220 	struct hashmap *str_off_map; /* map string offsets from src to dst */
2221 };
2222 
2223 static int btf_rewrite_str(struct btf_pipe *p, __u32 *str_off)
2224 {
2225 	struct btf *base;
2226 	long mapped_off;
2227 	int off, err;
2228 
2229 	if (!*str_off) /* nothing to do for empty strings */
2230 		return 0;
2231 
2232 	if (p->str_off_map &&
2233 	    hashmap__find(p->str_off_map, *str_off, &mapped_off)) {
2234 		*str_off = mapped_off;
2235 		return 0;
2236 	}
2237 
2238 	/*
2239 	 * btf__add_str() first looks the string up in the base BTFs of dst,
2240 	 * which makes each of them modifiable and frees its raw data. If src
2241 	 * shares a base with dst and the string lives in that base, the
2242 	 * pointer taken below would be left dangling. So make the bases
2243 	 * modifiable before the pointer is taken.
2244 	 */
2245 	for (base = p->dst->base_btf; base; base = base->base_btf) {
2246 		err = btf_ensure_modifiable(base);
2247 		if (err)
2248 			return err;
2249 	}
2250 
2251 	off = btf__add_str(p->dst, btf__str_by_offset(p->src, *str_off));
2252 	if (off < 0)
2253 		return off;
2254 
2255 	/* Remember string mapping from src to dst.  It avoids
2256 	 * performing expensive string comparisons.
2257 	 */
2258 	if (p->str_off_map) {
2259 		err = hashmap__append(p->str_off_map, *str_off, off);
2260 		if (err)
2261 			return err;
2262 	}
2263 
2264 	*str_off = off;
2265 	return 0;
2266 }
2267 
2268 static int btf_add_type(struct btf_pipe *p, const struct btf_type *src_type)
2269 {
2270 	struct btf_field_iter it;
2271 	struct btf_type *t;
2272 	__u32 *str_off;
2273 	int sz, err;
2274 
2275 	sz = btf_type_size(p->src, src_type);
2276 	if (sz < 0)
2277 		return libbpf_err(sz);
2278 
2279 	/* deconstruct BTF, if necessary, and invalidate raw_data */
2280 	err = btf_ensure_modifiable(p->dst);
2281 	if (err)
2282 		return libbpf_err(err);
2283 
2284 	t = btf_add_type_mem(p->dst, sz);
2285 	if (!t)
2286 		return libbpf_err(-ENOMEM);
2287 
2288 	memcpy(t, src_type, sz);
2289 
2290 	err = btf_field_iter_init(&it, t, BTF_FIELD_ITER_STRS);
2291 	if (err)
2292 		return libbpf_err(err);
2293 
2294 	while ((str_off = btf_field_iter_next(&it))) {
2295 		err = btf_rewrite_str(p, str_off);
2296 		if (err)
2297 			return libbpf_err(err);
2298 	}
2299 
2300 	return btf_commit_type(p->dst, sz);
2301 }
2302 
2303 int btf__add_type(struct btf *btf, const struct btf *src_btf, const struct btf_type *src_type)
2304 {
2305 	struct btf_pipe p = { .src = src_btf, .dst = btf };
2306 
2307 	return btf_add_type(&p, src_type);
2308 }
2309 
2310 static size_t btf_dedup_identity_hash_fn(long key, void *ctx);
2311 static bool btf_dedup_equal_fn(long k1, long k2, void *ctx);
2312 
2313 int btf__add_btf(struct btf *btf, const struct btf *src_btf)
2314 {
2315 	struct btf_pipe p = { .src = src_btf, .dst = btf };
2316 	int data_sz, sz, cnt, i, err, old_strs_len;
2317 	__u32 src_start_id;
2318 	__u32 *off;
2319 	void *t;
2320 
2321 	/*
2322 	 * When appending split BTF, the destination must share the same base
2323 	 * BTF so that base type ID references remain valid.
2324 	 */
2325 	if (src_btf->base_btf && src_btf->base_btf != btf->base_btf)
2326 		return libbpf_err(-EOPNOTSUPP);
2327 
2328 	src_start_id = src_btf->base_btf ? btf__type_cnt(src_btf->base_btf) : 1;
2329 
2330 	/* deconstruct BTF, if necessary, and invalidate raw_data */
2331 	err = btf_ensure_modifiable(btf);
2332 	if (err)
2333 		return libbpf_err(err);
2334 
2335 	/* remember original strings section size if we have to roll back
2336 	 * partial strings section changes
2337 	 */
2338 	old_strs_len = btf->hdr.str_len;
2339 
2340 	data_sz = src_btf->hdr.type_len;
2341 	cnt = src_btf->nr_types;
2342 
2343 	/* pre-allocate enough memory for new types */
2344 	t = btf_add_type_mem(btf, data_sz);
2345 	if (!t)
2346 		return libbpf_err(-ENOMEM);
2347 
2348 	/* pre-allocate enough memory for type offset index for new types */
2349 	off = btf_add_type_offs_mem(btf, cnt);
2350 	if (!off)
2351 		return libbpf_err(-ENOMEM);
2352 
2353 	/* Map the string offsets from src_btf to the offsets from btf to improve performance */
2354 	p.str_off_map = hashmap__new(btf_dedup_identity_hash_fn, btf_dedup_equal_fn, NULL);
2355 	if (IS_ERR(p.str_off_map))
2356 		return libbpf_err(-ENOMEM);
2357 
2358 	/* bulk copy types data for all types from src_btf */
2359 	memcpy(t, src_btf->types_data, data_sz);
2360 
2361 	for (i = 0; i < cnt; i++) {
2362 		struct btf_field_iter it;
2363 		__u32 *type_id, *str_off;
2364 
2365 		sz = btf_type_size(src_btf, t);
2366 		if (sz < 0) {
2367 			/* unlikely, has to be corrupted src_btf */
2368 			err = sz;
2369 			goto err_out;
2370 		}
2371 
2372 		/* fill out type ID to type offset mapping for lookups by type ID */
2373 		*off = t - btf->types_data;
2374 
2375 		/* add, dedup, and remap strings referenced by this BTF type */
2376 		err = btf_field_iter_init(&it, t, BTF_FIELD_ITER_STRS);
2377 		if (err)
2378 			goto err_out;
2379 		while ((str_off = btf_field_iter_next(&it))) {
2380 			/* don't remap strings from shared base BTF */
2381 			if (*str_off < src_btf->start_str_off)
2382 				continue;
2383 			err = btf_rewrite_str(&p, str_off);
2384 			if (err)
2385 				goto err_out;
2386 		}
2387 
2388 		/* remap all type IDs referenced from this BTF type */
2389 		err = btf_field_iter_init(&it, t, BTF_FIELD_ITER_IDS);
2390 		if (err)
2391 			goto err_out;
2392 
2393 		while ((type_id = btf_field_iter_next(&it))) {
2394 			if (!*type_id) /* nothing to do for VOID references */
2395 				continue;
2396 
2397 			/* don't remap types from shared base BTF */
2398 			if (*type_id < src_start_id)
2399 				continue;
2400 
2401 			*type_id += btf->start_id + btf->nr_types - src_start_id;
2402 		}
2403 
2404 		/* go to next type data and type offset index entry */
2405 		t += sz;
2406 		off++;
2407 	}
2408 
2409 	/* Up until now any of the copied type data was effectively invisible,
2410 	 * so if we exited early before this point due to error, BTF would be
2411 	 * effectively unmodified. There would be extra internal memory
2412 	 * pre-allocated, but it would not be available for querying.  But now
2413 	 * that we've copied and rewritten all the data successfully, we can
2414 	 * update type count and various internal offsets and sizes to
2415 	 * "commit" the changes and made them visible to the outside world.
2416 	 */
2417 	btf_hdr_update_type_len(btf, btf->hdr.type_len + data_sz);
2418 	btf->nr_types += cnt;
2419 
2420 	hashmap__free(p.str_off_map);
2421 
2422 	/* return type ID of the first added BTF type */
2423 	return btf->start_id + btf->nr_types - cnt;
2424 err_out:
2425 	/* zero out preallocated memory as if it was just allocated with
2426 	 * libbpf_add_mem()
2427 	 */
2428 	memset(btf->types_data + btf->hdr.type_len, 0, data_sz);
2429 	if (btf->strs_data)
2430 		memset(btf->strs_data + old_strs_len, 0, btf->hdr.str_len - old_strs_len);
2431 
2432 	/* and now restore original strings section size; types data size
2433 	 * wasn't modified, so doesn't need restoring, see big comment above
2434 	 */
2435 	btf_hdr_update_str_len(btf, old_strs_len);
2436 
2437 	hashmap__free(p.str_off_map);
2438 
2439 	return libbpf_err(err);
2440 }
2441 
2442 /*
2443  * Append new BTF_KIND_INT type with:
2444  *   - *name* - non-empty, non-NULL type name;
2445  *   - *sz* - power-of-2 (1, 2, 4, ..) size of the type, in bytes;
2446  *   - encoding is a combination of BTF_INT_SIGNED, BTF_INT_CHAR, BTF_INT_BOOL.
2447  * Returns:
2448  *   - >0, type ID of newly added BTF type;
2449  *   - <0, on error.
2450  */
2451 int btf__add_int(struct btf *btf, const char *name, size_t byte_sz, int encoding)
2452 {
2453 	struct btf_type *t;
2454 	int sz, name_off;
2455 	int err;
2456 
2457 	/* non-empty name */
2458 	if (str_is_empty(name))
2459 		return libbpf_err(-EINVAL);
2460 	/* byte_sz must be power of 2 */
2461 	if (!byte_sz || (byte_sz & (byte_sz - 1)) || byte_sz > 16)
2462 		return libbpf_err(-EINVAL);
2463 	if (encoding & ~(BTF_INT_SIGNED | BTF_INT_CHAR | BTF_INT_BOOL))
2464 		return libbpf_err(-EINVAL);
2465 
2466 	/* deconstruct BTF, if necessary, and invalidate raw_data */
2467 	err = btf_ensure_modifiable(btf);
2468 	if (err)
2469 		return libbpf_err(err);
2470 
2471 	sz = sizeof(struct btf_type) + sizeof(int);
2472 	t = btf_add_type_mem(btf, sz);
2473 	if (!t)
2474 		return libbpf_err(-ENOMEM);
2475 
2476 	/* if something goes wrong later, we might end up with an extra string,
2477 	 * but that shouldn't be a problem, because BTF can't be constructed
2478 	 * completely anyway and will most probably be just discarded
2479 	 */
2480 	name_off = btf__add_str(btf, name);
2481 	if (name_off < 0)
2482 		return name_off;
2483 
2484 	t->name_off = name_off;
2485 	t->info = btf_type_info(BTF_KIND_INT, 0, 0);
2486 	t->size = byte_sz;
2487 	/* set INT info, we don't allow setting legacy bit offset/size */
2488 	*(__u32 *)(t + 1) = (encoding << 24) | (byte_sz * 8);
2489 
2490 	return btf_commit_type(btf, sz);
2491 }
2492 
2493 /*
2494  * Append new BTF_KIND_FLOAT type with:
2495  *   - *name* - non-empty, non-NULL type name;
2496  *   - *sz* - size of the type, in bytes;
2497  * Returns:
2498  *   - >0, type ID of newly added BTF type;
2499  *   - <0, on error.
2500  */
2501 int btf__add_float(struct btf *btf, const char *name, size_t byte_sz)
2502 {
2503 	struct btf_type *t;
2504 	int sz, name_off;
2505 	int err;
2506 
2507 	/* non-empty name */
2508 	if (str_is_empty(name))
2509 		return libbpf_err(-EINVAL);
2510 
2511 	/* byte_sz must be one of the explicitly allowed values */
2512 	if (byte_sz != 2 && byte_sz != 4 && byte_sz != 8 && byte_sz != 12 &&
2513 	    byte_sz != 16)
2514 		return libbpf_err(-EINVAL);
2515 
2516 	err = btf_ensure_modifiable(btf);
2517 	if (err)
2518 		return libbpf_err(err);
2519 
2520 	sz = sizeof(struct btf_type);
2521 	t = btf_add_type_mem(btf, sz);
2522 	if (!t)
2523 		return libbpf_err(-ENOMEM);
2524 
2525 	name_off = btf__add_str(btf, name);
2526 	if (name_off < 0)
2527 		return name_off;
2528 
2529 	t->name_off = name_off;
2530 	t->info = btf_type_info(BTF_KIND_FLOAT, 0, 0);
2531 	t->size = byte_sz;
2532 
2533 	return btf_commit_type(btf, sz);
2534 }
2535 
2536 /* it's completely legal to append BTF types with type IDs pointing forward to
2537  * types that haven't been appended yet, so we only make sure that id looks
2538  * sane, we can't guarantee that ID will always be valid
2539  */
2540 static int validate_type_id(int id)
2541 {
2542 	if (id < 0 || id > BTF_MAX_NR_TYPES)
2543 		return -EINVAL;
2544 	return 0;
2545 }
2546 
2547 /* generic append function for PTR, TYPEDEF, CONST/VOLATILE/RESTRICT */
2548 static int btf_add_ref_kind(struct btf *btf, int kind, const char *name, int ref_type_id, int kflag)
2549 {
2550 	struct btf_type *t;
2551 	int sz, name_off = 0;
2552 	int err;
2553 
2554 	if (validate_type_id(ref_type_id))
2555 		return libbpf_err(-EINVAL);
2556 
2557 	err = btf_ensure_modifiable(btf);
2558 	if (err)
2559 		return libbpf_err(err);
2560 
2561 	sz = sizeof(struct btf_type);
2562 	t = btf_add_type_mem(btf, sz);
2563 	if (!t)
2564 		return libbpf_err(-ENOMEM);
2565 
2566 	if (!str_is_empty(name)) {
2567 		name_off = btf__add_str(btf, name);
2568 		if (name_off < 0)
2569 			return name_off;
2570 	}
2571 
2572 	t->name_off = name_off;
2573 	t->info = btf_type_info(kind, 0, kflag);
2574 	t->type = ref_type_id;
2575 
2576 	return btf_commit_type(btf, sz);
2577 }
2578 
2579 /*
2580  * Append new BTF_KIND_PTR type with:
2581  *   - *ref_type_id* - referenced type ID, it might not exist yet;
2582  * Returns:
2583  *   - >0, type ID of newly added BTF type;
2584  *   - <0, on error.
2585  */
2586 int btf__add_ptr(struct btf *btf, int ref_type_id)
2587 {
2588 	return btf_add_ref_kind(btf, BTF_KIND_PTR, NULL, ref_type_id, 0);
2589 }
2590 
2591 /*
2592  * Append new BTF_KIND_ARRAY type with:
2593  *   - *index_type_id* - type ID of the type describing array index;
2594  *   - *elem_type_id* - type ID of the type describing array element;
2595  *   - *nr_elems* - the size of the array;
2596  * Returns:
2597  *   - >0, type ID of newly added BTF type;
2598  *   - <0, on error.
2599  */
2600 int btf__add_array(struct btf *btf, int index_type_id, int elem_type_id, __u32 nr_elems)
2601 {
2602 	struct btf_type *t;
2603 	struct btf_array *a;
2604 	int err;
2605 	int sz;
2606 
2607 	if (validate_type_id(index_type_id) || validate_type_id(elem_type_id))
2608 		return libbpf_err(-EINVAL);
2609 
2610 	err = btf_ensure_modifiable(btf);
2611 	if (err)
2612 		return libbpf_err(err);
2613 
2614 	sz = sizeof(struct btf_type) + sizeof(struct btf_array);
2615 	t = btf_add_type_mem(btf, sz);
2616 	if (!t)
2617 		return libbpf_err(-ENOMEM);
2618 
2619 	t->name_off = 0;
2620 	t->info = btf_type_info(BTF_KIND_ARRAY, 0, 0);
2621 	t->size = 0;
2622 
2623 	a = btf_array(t);
2624 	a->type = elem_type_id;
2625 	a->index_type = index_type_id;
2626 	a->nelems = nr_elems;
2627 
2628 	return btf_commit_type(btf, sz);
2629 }
2630 
2631 /* generic STRUCT/UNION append function */
2632 static int btf_add_composite(struct btf *btf, int kind, const char *name, __u32 bytes_sz)
2633 {
2634 	struct btf_type *t;
2635 	int sz, name_off = 0;
2636 	int err;
2637 
2638 	err = btf_ensure_modifiable(btf);
2639 	if (err)
2640 		return libbpf_err(err);
2641 
2642 	sz = sizeof(struct btf_type);
2643 	t = btf_add_type_mem(btf, sz);
2644 	if (!t)
2645 		return libbpf_err(-ENOMEM);
2646 
2647 	if (!str_is_empty(name)) {
2648 		name_off = btf__add_str(btf, name);
2649 		if (name_off < 0)
2650 			return name_off;
2651 	}
2652 
2653 	/* start out with vlen=0 and no kflag; this will be adjusted when
2654 	 * adding each member
2655 	 */
2656 	t->name_off = name_off;
2657 	t->info = btf_type_info(kind, 0, 0);
2658 	t->size = bytes_sz;
2659 
2660 	return btf_commit_type(btf, sz);
2661 }
2662 
2663 /*
2664  * Append new BTF_KIND_STRUCT type with:
2665  *   - *name* - name of the struct, can be NULL or empty for anonymous structs;
2666  *   - *byte_sz* - size of the struct, in bytes;
2667  *
2668  * Struct initially has no fields in it. Fields can be added by
2669  * btf__add_field() right after btf__add_struct() succeeds.
2670  *
2671  * Returns:
2672  *   - >0, type ID of newly added BTF type;
2673  *   - <0, on error.
2674  */
2675 int btf__add_struct(struct btf *btf, const char *name, __u32 byte_sz)
2676 {
2677 	return btf_add_composite(btf, BTF_KIND_STRUCT, name, byte_sz);
2678 }
2679 
2680 /*
2681  * Append new BTF_KIND_UNION type with:
2682  *   - *name* - name of the union, can be NULL or empty for anonymous union;
2683  *   - *byte_sz* - size of the union, in bytes;
2684  *
2685  * Union initially has no fields in it. Fields can be added by
2686  * btf__add_field() right after btf__add_union() succeeds. All fields
2687  * should have *bit_offset* of 0.
2688  *
2689  * Returns:
2690  *   - >0, type ID of newly added BTF type;
2691  *   - <0, on error.
2692  */
2693 int btf__add_union(struct btf *btf, const char *name, __u32 byte_sz)
2694 {
2695 	return btf_add_composite(btf, BTF_KIND_UNION, name, byte_sz);
2696 }
2697 
2698 static struct btf_type *btf_last_type(struct btf *btf)
2699 {
2700 	return btf_type_by_id(btf, btf__type_cnt(btf) - 1);
2701 }
2702 
2703 /*
2704  * Append new field for the current STRUCT/UNION type with:
2705  *   - *name* - name of the field, can be NULL or empty for anonymous field;
2706  *   - *type_id* - type ID for the type describing field type;
2707  *   - *bit_offset* - bit offset of the start of the field within struct/union;
2708  *   - *bit_size* - bit size of a bitfield, 0 for non-bitfield fields;
2709  * Returns:
2710  *   -  0, on success;
2711  *   - <0, on error.
2712  */
2713 int btf__add_field(struct btf *btf, const char *name, int type_id,
2714 		   __u32 bit_offset, __u32 bit_size)
2715 {
2716 	struct btf_type *t;
2717 	struct btf_member *m;
2718 	bool is_bitfield;
2719 	int sz, name_off = 0;
2720 	int err;
2721 
2722 	/* last type should be union/struct */
2723 	if (btf->nr_types == 0)
2724 		return libbpf_err(-EINVAL);
2725 	t = btf_last_type(btf);
2726 	if (!btf_is_composite(t))
2727 		return libbpf_err(-EINVAL);
2728 	if (btf_vlen(t) == BTF_MAX_VLEN)
2729 		return libbpf_err(-ENOSPC);
2730 
2731 	if (validate_type_id(type_id))
2732 		return libbpf_err(-EINVAL);
2733 	/* best-effort bit field offset/size enforcement */
2734 	is_bitfield = bit_size || (bit_offset % 8 != 0);
2735 	if (is_bitfield && (bit_size == 0 || bit_size > 255 || bit_offset > 0xffffff))
2736 		return libbpf_err(-EINVAL);
2737 
2738 	/* only offset 0 is allowed for unions */
2739 	if (btf_is_union(t) && bit_offset)
2740 		return libbpf_err(-EINVAL);
2741 
2742 	/* decompose and invalidate raw data */
2743 	err = btf_ensure_modifiable(btf);
2744 	if (err)
2745 		return libbpf_err(err);
2746 
2747 	sz = sizeof(struct btf_member);
2748 	m = btf_add_type_mem(btf, sz);
2749 	if (!m)
2750 		return libbpf_err(-ENOMEM);
2751 
2752 	if (!str_is_empty(name)) {
2753 		name_off = btf__add_str(btf, name);
2754 		if (name_off < 0)
2755 			return name_off;
2756 	}
2757 
2758 	m->name_off = name_off;
2759 	m->type = type_id;
2760 	m->offset = bit_offset | (bit_size << 24);
2761 
2762 	/* btf_add_type_mem can invalidate t pointer */
2763 	t = btf_last_type(btf);
2764 
2765 	/* update parent type's vlen and kflag */
2766 	t->info = btf_type_info(btf_kind(t), btf_vlen(t) + 1, is_bitfield || btf_kflag(t));
2767 
2768 	btf_hdr_update_type_len(btf, btf->hdr.type_len + sz);
2769 	return 0;
2770 }
2771 
2772 static int btf_add_enum_common(struct btf *btf, const char *name, __u32 byte_sz,
2773 			       bool is_signed, __u8 kind)
2774 {
2775 	struct btf_type *t;
2776 	int sz, name_off = 0;
2777 	int err;
2778 
2779 	/* byte_sz must be power of 2 */
2780 	if (!byte_sz || (byte_sz & (byte_sz - 1)) || byte_sz > 8)
2781 		return libbpf_err(-EINVAL);
2782 
2783 	err = btf_ensure_modifiable(btf);
2784 	if (err)
2785 		return libbpf_err(err);
2786 
2787 	sz = sizeof(struct btf_type);
2788 	t = btf_add_type_mem(btf, sz);
2789 	if (!t)
2790 		return libbpf_err(-ENOMEM);
2791 
2792 	if (!str_is_empty(name)) {
2793 		name_off = btf__add_str(btf, name);
2794 		if (name_off < 0)
2795 			return name_off;
2796 	}
2797 
2798 	/* start out with vlen=0; it will be adjusted when adding enum values */
2799 	t->name_off = name_off;
2800 	t->info = btf_type_info(kind, 0, is_signed);
2801 	t->size = byte_sz;
2802 
2803 	return btf_commit_type(btf, sz);
2804 }
2805 
2806 /*
2807  * Append new BTF_KIND_ENUM type with:
2808  *   - *name* - name of the enum, can be NULL or empty for anonymous enums;
2809  *   - *byte_sz* - size of the enum, in bytes.
2810  *
2811  * Enum initially has no enum values in it (and corresponds to enum forward
2812  * declaration). Enumerator values can be added by btf__add_enum_value()
2813  * immediately after btf__add_enum() succeeds.
2814  *
2815  * Returns:
2816  *   - >0, type ID of newly added BTF type;
2817  *   - <0, on error.
2818  */
2819 int btf__add_enum(struct btf *btf, const char *name, __u32 byte_sz)
2820 {
2821 	/*
2822 	 * set the signedness to be unsigned, it will change to signed
2823 	 * if any later enumerator is negative.
2824 	 */
2825 	return btf_add_enum_common(btf, name, byte_sz, false, BTF_KIND_ENUM);
2826 }
2827 
2828 /*
2829  * Append new enum value for the current ENUM type with:
2830  *   - *name* - name of the enumerator value, can't be NULL or empty;
2831  *   - *value* - integer value corresponding to enum value *name*;
2832  * Returns:
2833  *   -  0, on success;
2834  *   - <0, on error.
2835  */
2836 int btf__add_enum_value(struct btf *btf, const char *name, __s64 value)
2837 {
2838 	struct btf_type *t;
2839 	struct btf_enum *v;
2840 	int sz, name_off;
2841 	int err;
2842 
2843 	/* last type should be BTF_KIND_ENUM */
2844 	if (btf->nr_types == 0)
2845 		return libbpf_err(-EINVAL);
2846 	t = btf_last_type(btf);
2847 	if (!btf_is_enum(t))
2848 		return libbpf_err(-EINVAL);
2849 
2850 	/* non-empty name */
2851 	if (str_is_empty(name))
2852 		return libbpf_err(-EINVAL);
2853 	if (value < INT_MIN || value > UINT_MAX)
2854 		return libbpf_err(-E2BIG);
2855 
2856 	/* decompose and invalidate raw data */
2857 	err = btf_ensure_modifiable(btf);
2858 	if (err)
2859 		return libbpf_err(err);
2860 
2861 	sz = sizeof(struct btf_enum);
2862 	v = btf_add_type_mem(btf, sz);
2863 	if (!v)
2864 		return libbpf_err(-ENOMEM);
2865 
2866 	name_off = btf__add_str(btf, name);
2867 	if (name_off < 0)
2868 		return name_off;
2869 
2870 	v->name_off = name_off;
2871 	v->val = value;
2872 
2873 	/* update parent type's vlen */
2874 	t = btf_last_type(btf);
2875 	err = btf_type_inc_vlen(t);
2876 	if (err)
2877 		return libbpf_err(err);
2878 
2879 	/* if negative value, set signedness to signed */
2880 	if (value < 0)
2881 		t->info = btf_type_info(btf_kind(t), btf_vlen(t), true);
2882 
2883 	btf_hdr_update_type_len(btf, btf->hdr.type_len + sz);
2884 	return 0;
2885 }
2886 
2887 /*
2888  * Append new BTF_KIND_ENUM64 type with:
2889  *   - *name* - name of the enum, can be NULL or empty for anonymous enums;
2890  *   - *byte_sz* - size of the enum, in bytes.
2891  *   - *is_signed* - whether the enum values are signed or not;
2892  *
2893  * Enum initially has no enum values in it (and corresponds to enum forward
2894  * declaration). Enumerator values can be added by btf__add_enum64_value()
2895  * immediately after btf__add_enum64() succeeds.
2896  *
2897  * Returns:
2898  *   - >0, type ID of newly added BTF type;
2899  *   - <0, on error.
2900  */
2901 int btf__add_enum64(struct btf *btf, const char *name, __u32 byte_sz,
2902 		    bool is_signed)
2903 {
2904 	return btf_add_enum_common(btf, name, byte_sz, is_signed,
2905 				   BTF_KIND_ENUM64);
2906 }
2907 
2908 /*
2909  * Append new enum value for the current ENUM64 type with:
2910  *   - *name* - name of the enumerator value, can't be NULL or empty;
2911  *   - *value* - integer value corresponding to enum value *name*;
2912  * Returns:
2913  *   -  0, on success;
2914  *   - <0, on error.
2915  */
2916 int btf__add_enum64_value(struct btf *btf, const char *name, __u64 value)
2917 {
2918 	struct btf_enum64 *v;
2919 	struct btf_type *t;
2920 	int sz, name_off;
2921 	int err;
2922 
2923 	/* last type should be BTF_KIND_ENUM64 */
2924 	if (btf->nr_types == 0)
2925 		return libbpf_err(-EINVAL);
2926 	t = btf_last_type(btf);
2927 	if (!btf_is_enum64(t))
2928 		return libbpf_err(-EINVAL);
2929 
2930 	/* non-empty name */
2931 	if (str_is_empty(name))
2932 		return libbpf_err(-EINVAL);
2933 
2934 	/* decompose and invalidate raw data */
2935 	err = btf_ensure_modifiable(btf);
2936 	if (err)
2937 		return libbpf_err(err);
2938 
2939 	sz = sizeof(struct btf_enum64);
2940 	v = btf_add_type_mem(btf, sz);
2941 	if (!v)
2942 		return libbpf_err(-ENOMEM);
2943 
2944 	name_off = btf__add_str(btf, name);
2945 	if (name_off < 0)
2946 		return name_off;
2947 
2948 	v->name_off = name_off;
2949 	v->val_lo32 = (__u32)value;
2950 	v->val_hi32 = value >> 32;
2951 
2952 	/* update parent type's vlen */
2953 	t = btf_last_type(btf);
2954 	err = btf_type_inc_vlen(t);
2955 	if (err)
2956 		return libbpf_err(err);
2957 
2958 	btf_hdr_update_type_len(btf, btf->hdr.type_len + sz);
2959 	return 0;
2960 }
2961 
2962 /*
2963  * Append new BTF_KIND_FWD type with:
2964  *   - *name*, non-empty/non-NULL name;
2965  *   - *fwd_kind*, kind of forward declaration, one of BTF_FWD_STRUCT,
2966  *     BTF_FWD_UNION, or BTF_FWD_ENUM;
2967  * Returns:
2968  *   - >0, type ID of newly added BTF type;
2969  *   - <0, on error.
2970  */
2971 int btf__add_fwd(struct btf *btf, const char *name, enum btf_fwd_kind fwd_kind)
2972 {
2973 	if (str_is_empty(name))
2974 		return libbpf_err(-EINVAL);
2975 
2976 	switch (fwd_kind) {
2977 	case BTF_FWD_STRUCT:
2978 	case BTF_FWD_UNION: {
2979 		struct btf_type *t;
2980 		int id;
2981 
2982 		id = btf_add_ref_kind(btf, BTF_KIND_FWD, name, 0, 0);
2983 		if (id <= 0)
2984 			return id;
2985 		t = btf_type_by_id(btf, id);
2986 		t->info = btf_type_info(BTF_KIND_FWD, 0, fwd_kind == BTF_FWD_UNION);
2987 		return id;
2988 	}
2989 	case BTF_FWD_ENUM:
2990 		/* enum forward in BTF currently is just an enum with no enum
2991 		 * values; we also assume a standard 4-byte size for it
2992 		 */
2993 		return btf__add_enum(btf, name, sizeof(int));
2994 	default:
2995 		return libbpf_err(-EINVAL);
2996 	}
2997 }
2998 
2999 /*
3000  * Append new BTF_KING_TYPEDEF type with:
3001  *   - *name*, non-empty/non-NULL name;
3002  *   - *ref_type_id* - referenced type ID, it might not exist yet;
3003  * Returns:
3004  *   - >0, type ID of newly added BTF type;
3005  *   - <0, on error.
3006  */
3007 int btf__add_typedef(struct btf *btf, const char *name, int ref_type_id)
3008 {
3009 	if (str_is_empty(name))
3010 		return libbpf_err(-EINVAL);
3011 
3012 	return btf_add_ref_kind(btf, BTF_KIND_TYPEDEF, name, ref_type_id, 0);
3013 }
3014 
3015 /*
3016  * Append new BTF_KIND_VOLATILE type with:
3017  *   - *ref_type_id* - referenced type ID, it might not exist yet;
3018  * Returns:
3019  *   - >0, type ID of newly added BTF type;
3020  *   - <0, on error.
3021  */
3022 int btf__add_volatile(struct btf *btf, int ref_type_id)
3023 {
3024 	return btf_add_ref_kind(btf, BTF_KIND_VOLATILE, NULL, ref_type_id, 0);
3025 }
3026 
3027 /*
3028  * Append new BTF_KIND_CONST type with:
3029  *   - *ref_type_id* - referenced type ID, it might not exist yet;
3030  * Returns:
3031  *   - >0, type ID of newly added BTF type;
3032  *   - <0, on error.
3033  */
3034 int btf__add_const(struct btf *btf, int ref_type_id)
3035 {
3036 	return btf_add_ref_kind(btf, BTF_KIND_CONST, NULL, ref_type_id, 0);
3037 }
3038 
3039 /*
3040  * Append new BTF_KIND_RESTRICT type with:
3041  *   - *ref_type_id* - referenced type ID, it might not exist yet;
3042  * Returns:
3043  *   - >0, type ID of newly added BTF type;
3044  *   - <0, on error.
3045  */
3046 int btf__add_restrict(struct btf *btf, int ref_type_id)
3047 {
3048 	return btf_add_ref_kind(btf, BTF_KIND_RESTRICT, NULL, ref_type_id, 0);
3049 }
3050 
3051 /*
3052  * Append new BTF_KIND_TYPE_TAG type with:
3053  *   - *value*, non-empty/non-NULL tag value;
3054  *   - *ref_type_id* - referenced type ID, it might not exist yet;
3055  * Returns:
3056  *   - >0, type ID of newly added BTF type;
3057  *   - <0, on error.
3058  */
3059 int btf__add_type_tag(struct btf *btf, const char *value, int ref_type_id)
3060 {
3061 	if (str_is_empty(value))
3062 		return libbpf_err(-EINVAL);
3063 
3064 	return btf_add_ref_kind(btf, BTF_KIND_TYPE_TAG, value, ref_type_id, 0);
3065 }
3066 
3067 /*
3068  * Append new BTF_KIND_TYPE_TAG type with:
3069  *   - *value*, non-empty/non-NULL tag value;
3070  *   - *ref_type_id* - referenced type ID, it might not exist yet;
3071  * Set info->kflag to 1, indicating this tag is an __attribute__
3072  * Returns:
3073  *   - >0, type ID of newly added BTF type;
3074  *   - <0, on error.
3075  */
3076 int btf__add_type_attr(struct btf *btf, const char *value, int ref_type_id)
3077 {
3078 	if (str_is_empty(value))
3079 		return libbpf_err(-EINVAL);
3080 
3081 	return btf_add_ref_kind(btf, BTF_KIND_TYPE_TAG, value, ref_type_id, 1);
3082 }
3083 
3084 /*
3085  * Append new BTF_KIND_FUNC type with:
3086  *   - *name*, non-empty/non-NULL name;
3087  *   - *proto_type_id* - FUNC_PROTO's type ID, it might not exist yet;
3088  * Returns:
3089  *   - >0, type ID of newly added BTF type;
3090  *   - <0, on error.
3091  */
3092 int btf__add_func(struct btf *btf, const char *name,
3093 		  enum btf_func_linkage linkage, int proto_type_id)
3094 {
3095 	int id;
3096 
3097 	if (str_is_empty(name))
3098 		return libbpf_err(-EINVAL);
3099 	if (linkage != BTF_FUNC_STATIC && linkage != BTF_FUNC_GLOBAL &&
3100 	    linkage != BTF_FUNC_EXTERN)
3101 		return libbpf_err(-EINVAL);
3102 
3103 	id = btf_add_ref_kind(btf, BTF_KIND_FUNC, name, proto_type_id, 0);
3104 	if (id > 0) {
3105 		struct btf_type *t = btf_type_by_id(btf, id);
3106 
3107 		t->info = btf_type_info(BTF_KIND_FUNC, linkage, 0);
3108 	}
3109 	return libbpf_err(id);
3110 }
3111 
3112 /*
3113  * Append new BTF_KIND_FUNC_PROTO with:
3114  *   - *ret_type_id* - type ID for return result of a function.
3115  *
3116  * Function prototype initially has no arguments, but they can be added by
3117  * btf__add_func_param() one by one, immediately after
3118  * btf__add_func_proto() succeeded.
3119  *
3120  * Returns:
3121  *   - >0, type ID of newly added BTF type;
3122  *   - <0, on error.
3123  */
3124 int btf__add_func_proto(struct btf *btf, int ret_type_id)
3125 {
3126 	struct btf_type *t;
3127 	int err;
3128 	int sz;
3129 
3130 	if (validate_type_id(ret_type_id))
3131 		return libbpf_err(-EINVAL);
3132 
3133 	err = btf_ensure_modifiable(btf);
3134 	if (err)
3135 		return libbpf_err(err);
3136 
3137 	sz = sizeof(struct btf_type);
3138 	t = btf_add_type_mem(btf, sz);
3139 	if (!t)
3140 		return libbpf_err(-ENOMEM);
3141 
3142 	/* start out with vlen=0; this will be adjusted when adding enum
3143 	 * values, if necessary
3144 	 */
3145 	t->name_off = 0;
3146 	t->info = btf_type_info(BTF_KIND_FUNC_PROTO, 0, 0);
3147 	t->type = ret_type_id;
3148 
3149 	return btf_commit_type(btf, sz);
3150 }
3151 
3152 /*
3153  * Append new function parameter for current FUNC_PROTO type with:
3154  *   - *name* - parameter name, can be NULL or empty;
3155  *   - *type_id* - type ID describing the type of the parameter.
3156  * Returns:
3157  *   -  0, on success;
3158  *   - <0, on error.
3159  */
3160 int btf__add_func_param(struct btf *btf, const char *name, int type_id)
3161 {
3162 	struct btf_type *t;
3163 	struct btf_param *p;
3164 	int sz, name_off = 0;
3165 	int err;
3166 
3167 	if (validate_type_id(type_id))
3168 		return libbpf_err(-EINVAL);
3169 
3170 	/* last type should be BTF_KIND_FUNC_PROTO */
3171 	if (btf->nr_types == 0)
3172 		return libbpf_err(-EINVAL);
3173 	t = btf_last_type(btf);
3174 	if (!btf_is_func_proto(t))
3175 		return libbpf_err(-EINVAL);
3176 
3177 	/* decompose and invalidate raw data */
3178 	err = btf_ensure_modifiable(btf);
3179 	if (err)
3180 		return libbpf_err(err);
3181 
3182 	sz = sizeof(struct btf_param);
3183 	p = btf_add_type_mem(btf, sz);
3184 	if (!p)
3185 		return libbpf_err(-ENOMEM);
3186 
3187 	if (!str_is_empty(name)) {
3188 		name_off = btf__add_str(btf, name);
3189 		if (name_off < 0)
3190 			return name_off;
3191 	}
3192 
3193 	p->name_off = name_off;
3194 	p->type = type_id;
3195 
3196 	/* update parent type's vlen */
3197 	t = btf_last_type(btf);
3198 	err = btf_type_inc_vlen(t);
3199 	if (err)
3200 		return libbpf_err(err);
3201 
3202 	btf_hdr_update_type_len(btf, btf->hdr.type_len + sz);
3203 	return 0;
3204 }
3205 
3206 /*
3207  * Append new BTF_KIND_VAR type with:
3208  *   - *name* - non-empty/non-NULL name;
3209  *   - *linkage* - variable linkage, one of BTF_VAR_STATIC,
3210  *     BTF_VAR_GLOBAL_ALLOCATED, or BTF_VAR_GLOBAL_EXTERN;
3211  *   - *type_id* - type ID of the type describing the type of the variable.
3212  * Returns:
3213  *   - >0, type ID of newly added BTF type;
3214  *   - <0, on error.
3215  */
3216 int btf__add_var(struct btf *btf, const char *name, int linkage, int type_id)
3217 {
3218 	struct btf_type *t;
3219 	struct btf_var *v;
3220 	int sz, name_off;
3221 	int err;
3222 
3223 	/* non-empty name */
3224 	if (str_is_empty(name))
3225 		return libbpf_err(-EINVAL);
3226 	if (linkage != BTF_VAR_STATIC && linkage != BTF_VAR_GLOBAL_ALLOCATED &&
3227 	    linkage != BTF_VAR_GLOBAL_EXTERN)
3228 		return libbpf_err(-EINVAL);
3229 	if (validate_type_id(type_id))
3230 		return libbpf_err(-EINVAL);
3231 
3232 	/* deconstruct BTF, if necessary, and invalidate raw_data */
3233 	err = btf_ensure_modifiable(btf);
3234 	if (err)
3235 		return libbpf_err(err);
3236 
3237 	sz = sizeof(struct btf_type) + sizeof(struct btf_var);
3238 	t = btf_add_type_mem(btf, sz);
3239 	if (!t)
3240 		return libbpf_err(-ENOMEM);
3241 
3242 	name_off = btf__add_str(btf, name);
3243 	if (name_off < 0)
3244 		return name_off;
3245 
3246 	t->name_off = name_off;
3247 	t->info = btf_type_info(BTF_KIND_VAR, 0, 0);
3248 	t->type = type_id;
3249 
3250 	v = btf_var(t);
3251 	v->linkage = linkage;
3252 
3253 	return btf_commit_type(btf, sz);
3254 }
3255 
3256 /*
3257  * Append new BTF_KIND_DATASEC type with:
3258  *   - *name* - non-empty/non-NULL name;
3259  *   - *byte_sz* - data section size, in bytes.
3260  *
3261  * Data section is initially empty. Variables info can be added with
3262  * btf__add_datasec_var_info() calls, after btf__add_datasec() succeeds.
3263  *
3264  * Returns:
3265  *   - >0, type ID of newly added BTF type;
3266  *   - <0, on error.
3267  */
3268 int btf__add_datasec(struct btf *btf, const char *name, __u32 byte_sz)
3269 {
3270 	struct btf_type *t;
3271 	int sz, name_off;
3272 	int err;
3273 
3274 	/* non-empty name */
3275 	if (str_is_empty(name))
3276 		return libbpf_err(-EINVAL);
3277 
3278 	err = btf_ensure_modifiable(btf);
3279 	if (err)
3280 		return libbpf_err(err);
3281 
3282 	sz = sizeof(struct btf_type);
3283 	t = btf_add_type_mem(btf, sz);
3284 	if (!t)
3285 		return libbpf_err(-ENOMEM);
3286 
3287 	name_off = btf__add_str(btf, name);
3288 	if (name_off < 0)
3289 		return name_off;
3290 
3291 	/* start with vlen=0, which will be update as var_secinfos are added */
3292 	t->name_off = name_off;
3293 	t->info = btf_type_info(BTF_KIND_DATASEC, 0, 0);
3294 	t->size = byte_sz;
3295 
3296 	return btf_commit_type(btf, sz);
3297 }
3298 
3299 /*
3300  * Append new data section variable information entry for current DATASEC type:
3301  *   - *var_type_id* - type ID, describing type of the variable;
3302  *   - *offset* - variable offset within data section, in bytes;
3303  *   - *byte_sz* - variable size, in bytes.
3304  *
3305  * Returns:
3306  *   -  0, on success;
3307  *   - <0, on error.
3308  */
3309 int btf__add_datasec_var_info(struct btf *btf, int var_type_id, __u32 offset, __u32 byte_sz)
3310 {
3311 	struct btf_type *t;
3312 	struct btf_var_secinfo *v;
3313 	int err;
3314 	int sz;
3315 
3316 	/* last type should be BTF_KIND_DATASEC */
3317 	if (btf->nr_types == 0)
3318 		return libbpf_err(-EINVAL);
3319 	t = btf_last_type(btf);
3320 	if (!btf_is_datasec(t))
3321 		return libbpf_err(-EINVAL);
3322 
3323 	if (validate_type_id(var_type_id))
3324 		return libbpf_err(-EINVAL);
3325 
3326 	/* decompose and invalidate raw data */
3327 	err = btf_ensure_modifiable(btf);
3328 	if (err)
3329 		return libbpf_err(err);
3330 
3331 	sz = sizeof(struct btf_var_secinfo);
3332 	v = btf_add_type_mem(btf, sz);
3333 	if (!v)
3334 		return libbpf_err(-ENOMEM);
3335 
3336 	v->type = var_type_id;
3337 	v->offset = offset;
3338 	v->size = byte_sz;
3339 
3340 	/* update parent type's vlen */
3341 	t = btf_last_type(btf);
3342 	err = btf_type_inc_vlen(t);
3343 	if (err)
3344 		return libbpf_err(err);
3345 
3346 	btf_hdr_update_type_len(btf, btf->hdr.type_len + sz);
3347 	return 0;
3348 }
3349 
3350 static int btf_add_decl_tag(struct btf *btf, const char *value, int ref_type_id,
3351 			    int component_idx, int kflag)
3352 {
3353 	struct btf_type *t;
3354 	int sz, value_off;
3355 	int err;
3356 
3357 	if (str_is_empty(value) || component_idx < -1)
3358 		return libbpf_err(-EINVAL);
3359 
3360 	if (validate_type_id(ref_type_id))
3361 		return libbpf_err(-EINVAL);
3362 
3363 	err = btf_ensure_modifiable(btf);
3364 	if (err)
3365 		return libbpf_err(err);
3366 
3367 	sz = sizeof(struct btf_type) + sizeof(struct btf_decl_tag);
3368 	t = btf_add_type_mem(btf, sz);
3369 	if (!t)
3370 		return libbpf_err(-ENOMEM);
3371 
3372 	value_off = btf__add_str(btf, value);
3373 	if (value_off < 0)
3374 		return value_off;
3375 
3376 	t->name_off = value_off;
3377 	t->info = btf_type_info(BTF_KIND_DECL_TAG, 0, kflag);
3378 	t->type = ref_type_id;
3379 	btf_decl_tag(t)->component_idx = component_idx;
3380 
3381 	return btf_commit_type(btf, sz);
3382 }
3383 
3384 /*
3385  * Append new BTF_KIND_DECL_TAG type with:
3386  *   - *value* - non-empty/non-NULL string;
3387  *   - *ref_type_id* - referenced type ID, it might not exist yet;
3388  *   - *component_idx* - -1 for tagging reference type, otherwise struct/union
3389  *     member or function argument index;
3390  * Returns:
3391  *   - >0, type ID of newly added BTF type;
3392  *   - <0, on error.
3393  */
3394 int btf__add_decl_tag(struct btf *btf, const char *value, int ref_type_id,
3395 		      int component_idx)
3396 {
3397 	return btf_add_decl_tag(btf, value, ref_type_id, component_idx, 0);
3398 }
3399 
3400 /*
3401  * Append new BTF_KIND_DECL_TAG type with:
3402  *   - *value* - non-empty/non-NULL string;
3403  *   - *ref_type_id* - referenced type ID, it might not exist yet;
3404  *   - *component_idx* - -1 for tagging reference type, otherwise struct/union
3405  *     member or function argument index;
3406  * Set info->kflag to 1, indicating this tag is an __attribute__
3407  * Returns:
3408  *   - >0, type ID of newly added BTF type;
3409  *   - <0, on error.
3410  */
3411 int btf__add_decl_attr(struct btf *btf, const char *value, int ref_type_id,
3412 		       int component_idx)
3413 {
3414 	return btf_add_decl_tag(btf, value, ref_type_id, component_idx, 1);
3415 }
3416 
3417 /*
3418  * Append new BTF_KIND_LOC_PARAM with specified size and flags.  Values are
3419  * added via btf__add_loc_param_value().
3420  *
3421  * - *byte_sz* - size of the type, in bytes (1 through 16);
3422  * - *flags* - combination of enum btf_loc_param_flags values
3423  *
3424  * Returns:
3425  *   -  >0, type ID of newly added BTF type;
3426  *   - <0, on error.
3427  */
3428 int btf__add_loc_param(struct btf *btf, __u32 byte_sz, __u32 flags)
3429 {
3430 	struct btf_loc_param *p;
3431 	struct btf_type *t;
3432 	int sz, err;
3433 
3434 	if (!byte_sz || byte_sz > 16)
3435 		return libbpf_err(-EINVAL);
3436 
3437 	err = btf_ensure_modifiable(btf);
3438 	if (err)
3439 		return libbpf_err(err);
3440 
3441 	sz = sizeof(struct btf_type) + sizeof(*p);
3442 	t = btf_add_type_mem(btf, sz);
3443 	if (!t)
3444 		return libbpf_err(-ENOMEM);
3445 
3446 	t->name_off = 0;
3447 	t->info = btf_type_info(BTF_KIND_LOC_PARAM, 0, 0);
3448 	t->size = byte_sz;
3449 
3450 	p = btf_loc_param(t);
3451 	p->flags = flags;
3452 
3453 	return btf_commit_type(btf, sz);
3454 }
3455 
3456 /*
3457  * Append *value* to existing BTF_KIND_LOC_PARAM.
3458  *
3459  * Returns:
3460  *   - 0 on success
3461  *   - <0, on error.
3462  */
3463 int btf__add_loc_param_value(struct btf *btf, __u32 value)
3464 {
3465 	struct btf_type *t;
3466 	int sz, err;
3467 	__u32 *v;
3468 
3469 	/* last type should be BTF_KIND_LOC_PARAM */
3470 	if (btf->nr_types == 0)
3471 		return libbpf_err(-EINVAL);
3472 	t = btf_last_type(btf);
3473 	if (!btf_is_loc_param(t))
3474 		return libbpf_err(-EINVAL);
3475 
3476 	/* decompose and invalidate raw data */
3477 	err = btf_ensure_modifiable(btf);
3478 	if (err)
3479 		return libbpf_err(err);
3480 
3481 	sz = sizeof(value);
3482 	v = btf_add_type_mem(btf, sz);
3483 	if (!v)
3484 		return libbpf_err(-ENOMEM);
3485 	*v = value;
3486 
3487 	/* update parent type's vlen */
3488 	t = btf_last_type(btf);
3489 	err = btf_type_inc_vlen(t);
3490 	if (err)
3491 		return libbpf_err(err);
3492 
3493 	btf_hdr_update_type_len(btf, btf->hdr.type_len + sz);
3494 	return 0;
3495 }
3496 
3497 /*
3498  * Append new BTF_KIND_LOC_PROTO
3499  *
3500  * The prototype is then populated with 0 or more BTF_KIND_LOC_PARAMs via
3501  * btf__add_loc_proto_param(); similar to how btf__add_func_param() adds
3502  * parameters to a FUNC_PROTO.
3503  *
3504  * Returns:
3505  *   -  >0, type ID of newly added BTF type;
3506  *   - <0, on error.
3507  */
3508 int btf__add_loc_proto(struct btf *btf)
3509 {
3510 	struct btf_type *t;
3511 	int err;
3512 
3513 	err = btf_ensure_modifiable(btf);
3514 	if (err)
3515 		return libbpf_err(err);
3516 
3517 	t = btf_add_type_mem(btf, sizeof(struct btf_type));
3518 	if (!t)
3519 		return libbpf_err(-ENOMEM);
3520 
3521 	t->name_off = 0;
3522 	t->info = btf_type_info(BTF_KIND_LOC_PROTO, 0, 0);
3523 	t->size = 0;
3524 
3525 	return btf_commit_type(btf, sizeof(struct btf_type));
3526 }
3527 
3528 /*
3529  * Append a BTF_KIND_LOC_PARAM id/0 to BTF_KIND_LOC_PROTO.
3530  *
3531  * Returns:
3532  *   - 0 on success;
3533  *   - <0, on error.
3534 
3535  */
3536 int btf__add_loc_proto_param(struct btf *btf, __u32 id)
3537 {
3538 	struct btf_type *t;
3539 	int sz, err;
3540 	__u32 *p;
3541 
3542 	if (validate_type_id(id))
3543 		return libbpf_err(-EINVAL);
3544 
3545 	/* last type should be BTF_KIND_LOC_PROTO */
3546 	if (btf->nr_types == 0)
3547 		return libbpf_err(-EINVAL);
3548 	t = btf_last_type(btf);
3549 	if (!btf_is_loc_proto(t))
3550 		return libbpf_err(-EINVAL);
3551 
3552 	/* decompose and invalidate raw data */
3553 	err = btf_ensure_modifiable(btf);
3554 	if (err)
3555 		return libbpf_err(err);
3556 
3557 	sz = sizeof(__u32);
3558 	p = btf_add_type_mem(btf, sz);
3559 	if (!p)
3560 		return libbpf_err(-ENOMEM);
3561 	*p = id;
3562 
3563 	/* update parent type's vlen */
3564 	t = btf_last_type(btf);
3565 	err = btf_type_inc_vlen(t);
3566 	if (err)
3567 		return libbpf_err(err);
3568 
3569 	btf_hdr_update_type_len(btf, btf->hdr.type_len + sz);
3570 	return 0;
3571 }
3572 
3573 /*
3574  * Append new BTF_KIND_LOCSEC type with:
3575  *   - *name* - non-empty/non-NULL name;
3576  *
3577  * Location section is initially empty. Location info can be added with
3578  * btf__add_locsec_loc() calls, after btf__add_locsec() succeeds.
3579  *
3580  * Returns:
3581  *   - >0, type ID of newly added BTF type;
3582  *   - <0, on error.
3583  */
3584 
3585 int btf__add_locsec(struct btf *btf, const char *name)
3586 {
3587 	struct btf_type *t;
3588 	int name_off = 0;
3589 	int err;
3590 
3591 	/* non-empty name */
3592 	if (str_is_empty(name))
3593 		return libbpf_err(-EINVAL);
3594 
3595 	err = btf_ensure_modifiable(btf);
3596 	if (err)
3597 		return libbpf_err(err);
3598 
3599 	t = btf_add_type_mem(btf, sizeof(struct btf_type));
3600 	if (!t)
3601 		return libbpf_err(-ENOMEM);
3602 
3603 	name_off = btf__add_str(btf, name);
3604 	if (name_off < 0)
3605 		return libbpf_err(name_off);
3606 	t->name_off = name_off;
3607 	t->info = btf_type_info(BTF_KIND_LOCSEC, 0, 0);
3608 	t->size = 0;
3609 
3610 	return btf_commit_type(btf, sizeof(struct btf_type));
3611 }
3612 
3613 int btf__add_locsec_loc(struct btf *btf, __u32 func, __u32 loc_proto,
3614 			__u32 offset)
3615 {
3616 	struct btf_type *t;
3617 	struct btf_loc *l;
3618 	int sz, err;
3619 
3620 	if (validate_type_id(func) || validate_type_id(loc_proto))
3621 		return libbpf_err(-EINVAL);
3622 
3623 	/* last type should be BTF_KIND_LOCSEC */
3624 	if (btf->nr_types == 0)
3625 		return libbpf_err(-EINVAL);
3626 	t = btf_last_type(btf);
3627 	if (!btf_is_locsec(t))
3628 		return libbpf_err(-EINVAL);
3629 
3630 	/* decompose and invalidate raw data */
3631 	err = btf_ensure_modifiable(btf);
3632 	if (err)
3633 		return libbpf_err(err);
3634 
3635 	sz = sizeof(*l);
3636 	l = btf_add_type_mem(btf, sz);
3637 	if (!l)
3638 		return libbpf_err(-ENOMEM);
3639 
3640 	l->func = func;
3641 	l->loc_proto = loc_proto;
3642 	l->offset = offset;
3643 
3644 	/* update parent type's vlen */
3645 	t = btf_last_type(btf);
3646 	err = btf_type_inc_vlen(t);
3647 	if (err)
3648 		return libbpf_err(err);
3649 
3650 	btf_hdr_update_type_len(btf, btf->hdr.type_len + sz);
3651 	return 0;
3652 }
3653 
3654 struct btf_ext_sec_info_param {
3655 	__u32 off;
3656 	__u32 len;
3657 	__u32 min_rec_size;
3658 	struct btf_ext_info *ext_info;
3659 	const char *desc;
3660 };
3661 
3662 /*
3663  * Parse a single info subsection of the BTF.ext info data:
3664  *  - validate subsection structure and elements
3665  *  - save info subsection start and sizing details in struct btf_ext
3666  *  - endian-independent operation, for calling before byte-swapping
3667  */
3668 static int btf_ext_parse_sec_info(struct btf_ext *btf_ext,
3669 				  struct btf_ext_sec_info_param *ext_sec,
3670 				  bool is_native)
3671 {
3672 	const struct btf_ext_info_sec *sinfo;
3673 	struct btf_ext_info *ext_info;
3674 	__u32 data_left, info_left, record_size;
3675 	size_t sec_cnt = 0;
3676 	void *info;
3677 
3678 	if (ext_sec->len == 0)
3679 		return 0;
3680 
3681 	if (ext_sec->off & 0x03) {
3682 		pr_debug(".BTF.ext %s section is not aligned to 4 bytes\n",
3683 		     ext_sec->desc);
3684 		return -EINVAL;
3685 	}
3686 
3687 	if (btf_ext->hdr->hdr_len > btf_ext->data_size)
3688 		return -EINVAL;
3689 
3690 	data_left = btf_ext->data_size - btf_ext->hdr->hdr_len;
3691 	if (ext_sec->off > data_left || ext_sec->len > data_left - ext_sec->off) {
3692 		pr_debug("%s section (off:%u len:%u) is beyond the end of the ELF section .BTF.ext\n",
3693 			 ext_sec->desc, ext_sec->off, ext_sec->len);
3694 		return -EINVAL;
3695 	}
3696 
3697 	/* The start of the info sec (including the __u32 record_size). */
3698 	info = btf_ext->data + btf_ext->hdr->hdr_len + ext_sec->off;
3699 	info_left = ext_sec->len;
3700 
3701 	/* At least a record size */
3702 	if (info_left < sizeof(__u32)) {
3703 		pr_debug(".BTF.ext %s record size not found\n", ext_sec->desc);
3704 		return -EINVAL;
3705 	}
3706 
3707 	/* The record size needs to meet either the minimum standard or, when
3708 	 * handling non-native endianness data, the exact standard so as
3709 	 * to allow safe byte-swapping.
3710 	 */
3711 	record_size = is_native ? *(__u32 *)info : bswap_32(*(__u32 *)info);
3712 	if (record_size < ext_sec->min_rec_size ||
3713 	    (!is_native && record_size != ext_sec->min_rec_size) ||
3714 	    record_size & 0x03) {
3715 		pr_debug("%s section in .BTF.ext has invalid record size %u\n",
3716 			 ext_sec->desc, record_size);
3717 		return -EINVAL;
3718 	}
3719 
3720 	sinfo = info + sizeof(__u32);
3721 	info_left -= sizeof(__u32);
3722 
3723 	/* If no records, return failure now so .BTF.ext won't be used. */
3724 	if (!info_left) {
3725 		pr_debug("%s section in .BTF.ext has no records\n", ext_sec->desc);
3726 		return -EINVAL;
3727 	}
3728 
3729 	while (info_left) {
3730 		unsigned int sec_hdrlen = sizeof(struct btf_ext_info_sec);
3731 		__u64 total_record_size;
3732 		__u32 num_records;
3733 
3734 		if (info_left < sec_hdrlen) {
3735 			pr_debug("%s section header is not found in .BTF.ext\n",
3736 			     ext_sec->desc);
3737 			return -EINVAL;
3738 		}
3739 
3740 		num_records = is_native ? sinfo->num_info : bswap_32(sinfo->num_info);
3741 		if (num_records == 0) {
3742 			pr_debug("%s section has incorrect num_records in .BTF.ext\n",
3743 			     ext_sec->desc);
3744 			return -EINVAL;
3745 		}
3746 
3747 		total_record_size = sec_hdrlen + (__u64)num_records * record_size;
3748 		if (info_left < total_record_size) {
3749 			pr_debug("%s section has incorrect num_records in .BTF.ext\n",
3750 			     ext_sec->desc);
3751 			return -EINVAL;
3752 		}
3753 
3754 		info_left -= total_record_size;
3755 		sinfo = (void *)sinfo + total_record_size;
3756 		sec_cnt++;
3757 	}
3758 
3759 	ext_info = ext_sec->ext_info;
3760 	ext_info->len = ext_sec->len - sizeof(__u32);
3761 	ext_info->rec_size = record_size;
3762 	ext_info->info = info + sizeof(__u32);
3763 	ext_info->sec_cnt = sec_cnt;
3764 
3765 	return 0;
3766 }
3767 
3768 /* Parse all info secs in the BTF.ext info data */
3769 static int btf_ext_parse_info(struct btf_ext *btf_ext, bool is_native)
3770 {
3771 	struct btf_ext_sec_info_param func_info = {
3772 		.off = btf_ext->hdr->func_info_off,
3773 		.len = btf_ext->hdr->func_info_len,
3774 		.min_rec_size = sizeof(struct bpf_func_info_min),
3775 		.ext_info = &btf_ext->func_info,
3776 		.desc = "func_info"
3777 	};
3778 	struct btf_ext_sec_info_param line_info = {
3779 		.off = btf_ext->hdr->line_info_off,
3780 		.len = btf_ext->hdr->line_info_len,
3781 		.min_rec_size = sizeof(struct bpf_line_info_min),
3782 		.ext_info = &btf_ext->line_info,
3783 		.desc = "line_info",
3784 	};
3785 	struct btf_ext_sec_info_param core_relo = {
3786 		.min_rec_size = sizeof(struct bpf_core_relo),
3787 		.ext_info = &btf_ext->core_relo_info,
3788 		.desc = "core_relo",
3789 	};
3790 	int err;
3791 
3792 	err = btf_ext_parse_sec_info(btf_ext, &func_info, is_native);
3793 	if (err)
3794 		return err;
3795 
3796 	err = btf_ext_parse_sec_info(btf_ext, &line_info, is_native);
3797 	if (err)
3798 		return err;
3799 
3800 	if (btf_ext->hdr->hdr_len < offsetofend(struct btf_ext_header, core_relo_len))
3801 		return 0; /* skip core relos parsing */
3802 
3803 	core_relo.off = btf_ext->hdr->core_relo_off;
3804 	core_relo.len = btf_ext->hdr->core_relo_len;
3805 	err = btf_ext_parse_sec_info(btf_ext, &core_relo, is_native);
3806 	if (err)
3807 		return err;
3808 
3809 	return 0;
3810 }
3811 
3812 /* Swap byte-order of BTF.ext header with any endianness */
3813 static void btf_ext_bswap_hdr(struct btf_ext_header *h)
3814 {
3815 	bool is_native = h->magic == BTF_MAGIC;
3816 	__u32 hdr_len;
3817 
3818 	hdr_len = is_native ? h->hdr_len : bswap_32(h->hdr_len);
3819 
3820 	h->magic = bswap_16(h->magic);
3821 	h->hdr_len = bswap_32(h->hdr_len);
3822 	h->func_info_off = bswap_32(h->func_info_off);
3823 	h->func_info_len = bswap_32(h->func_info_len);
3824 	h->line_info_off = bswap_32(h->line_info_off);
3825 	h->line_info_len = bswap_32(h->line_info_len);
3826 
3827 	if (hdr_len < offsetofend(struct btf_ext_header, core_relo_len))
3828 		return;
3829 
3830 	h->core_relo_off = bswap_32(h->core_relo_off);
3831 	h->core_relo_len = bswap_32(h->core_relo_len);
3832 }
3833 
3834 /* Swap byte-order of generic info subsection */
3835 static void btf_ext_bswap_info_sec(void *info, __u32 len, bool is_native,
3836 				   info_rec_bswap_fn bswap_fn)
3837 {
3838 	struct btf_ext_info_sec *sec;
3839 	__u32 info_left, rec_size, *rs;
3840 
3841 	if (len == 0)
3842 		return;
3843 
3844 	rs = info;				/* info record size */
3845 	rec_size = is_native ? *rs : bswap_32(*rs);
3846 	*rs = bswap_32(*rs);
3847 
3848 	sec = info + sizeof(__u32);		/* info sec #1 */
3849 	info_left = len - sizeof(__u32);
3850 	while (info_left) {
3851 		unsigned int sec_hdrlen = sizeof(struct btf_ext_info_sec);
3852 		__u32 i, num_recs;
3853 		void *p;
3854 
3855 		num_recs = is_native ? sec->num_info : bswap_32(sec->num_info);
3856 		sec->sec_name_off = bswap_32(sec->sec_name_off);
3857 		sec->num_info = bswap_32(sec->num_info);
3858 		p = sec->data;			/* info rec #1 */
3859 		for (i = 0; i < num_recs; i++, p += rec_size)
3860 			bswap_fn(p);
3861 		sec = p;
3862 		info_left -= sec_hdrlen + (__u64)rec_size * num_recs;
3863 	}
3864 }
3865 
3866 /*
3867  * Swap byte-order of all info data in a BTF.ext section
3868  *  - requires BTF.ext hdr in native endianness
3869  */
3870 static void btf_ext_bswap_info(struct btf_ext *btf_ext, void *data)
3871 {
3872 	const bool is_native = btf_ext->swapped_endian;
3873 	const struct btf_ext_header *h = data;
3874 	void *info;
3875 
3876 	/* Swap func_info subsection byte-order */
3877 	info = data + h->hdr_len + h->func_info_off;
3878 	btf_ext_bswap_info_sec(info, h->func_info_len, is_native,
3879 			       (info_rec_bswap_fn)bpf_func_info_bswap);
3880 
3881 	/* Swap line_info subsection byte-order */
3882 	info = data + h->hdr_len + h->line_info_off;
3883 	btf_ext_bswap_info_sec(info, h->line_info_len, is_native,
3884 			       (info_rec_bswap_fn)bpf_line_info_bswap);
3885 
3886 	/* Swap core_relo subsection byte-order (if present) */
3887 	if (h->hdr_len < offsetofend(struct btf_ext_header, core_relo_len))
3888 		return;
3889 
3890 	info = data + h->hdr_len + h->core_relo_off;
3891 	btf_ext_bswap_info_sec(info, h->core_relo_len, is_native,
3892 			       (info_rec_bswap_fn)bpf_core_relo_bswap);
3893 }
3894 
3895 /* Parse hdr data and info sections: check and convert to native endianness */
3896 static int btf_ext_parse(struct btf_ext *btf_ext)
3897 {
3898 	__u32 hdr_len, data_size = btf_ext->data_size;
3899 	struct btf_ext_header *hdr = btf_ext->hdr;
3900 	bool swapped_endian = false;
3901 	int err;
3902 
3903 	if (data_size < offsetofend(struct btf_ext_header, hdr_len)) {
3904 		pr_debug("BTF.ext header too short\n");
3905 		return -EINVAL;
3906 	}
3907 
3908 	hdr_len = hdr->hdr_len;
3909 	if (hdr->magic == bswap_16(BTF_MAGIC)) {
3910 		swapped_endian = true;
3911 		hdr_len = bswap_32(hdr_len);
3912 	} else if (hdr->magic != BTF_MAGIC) {
3913 		pr_debug("Invalid BTF.ext magic:%x\n", hdr->magic);
3914 		return -EINVAL;
3915 	}
3916 
3917 	/* Ensure known version of structs, current BTF_VERSION == 1 */
3918 	if (hdr->version != 1) {
3919 		pr_debug("Unsupported BTF.ext version:%u\n", hdr->version);
3920 		return -ENOTSUP;
3921 	}
3922 
3923 	if (hdr->flags) {
3924 		pr_debug("Unsupported BTF.ext flags:%x\n", hdr->flags);
3925 		return -ENOTSUP;
3926 	}
3927 
3928 	if (data_size < hdr_len) {
3929 		pr_debug("BTF.ext header not found\n");
3930 		return -EINVAL;
3931 	} else if (data_size == hdr_len) {
3932 		pr_debug("BTF.ext has no data\n");
3933 		return -EINVAL;
3934 	}
3935 
3936 	/* Verify mandatory hdr info details present */
3937 	if (hdr_len < offsetofend(struct btf_ext_header, line_info_len)) {
3938 		pr_warn("BTF.ext header missing func_info, line_info\n");
3939 		return -EINVAL;
3940 	}
3941 
3942 	/* Keep hdr native byte-order in memory for introspection */
3943 	if (swapped_endian)
3944 		btf_ext_bswap_hdr(btf_ext->hdr);
3945 
3946 	/* Validate info subsections and cache key metadata */
3947 	err = btf_ext_parse_info(btf_ext, !swapped_endian);
3948 	if (err)
3949 		return err;
3950 
3951 	/* Keep infos native byte-order in memory for introspection */
3952 	if (swapped_endian)
3953 		btf_ext_bswap_info(btf_ext, btf_ext->data);
3954 
3955 	/*
3956 	 * Set btf_ext->swapped_endian only after all header and info data has
3957 	 * been swapped, helping bswap functions determine if their data are
3958 	 * in native byte-order when called.
3959 	 */
3960 	btf_ext->swapped_endian = swapped_endian;
3961 	return 0;
3962 }
3963 
3964 void btf_ext__free(struct btf_ext *btf_ext)
3965 {
3966 	if (IS_ERR_OR_NULL(btf_ext))
3967 		return;
3968 	free(btf_ext->func_info.sec_idxs);
3969 	free(btf_ext->line_info.sec_idxs);
3970 	free(btf_ext->core_relo_info.sec_idxs);
3971 	free(btf_ext->data);
3972 	free(btf_ext->data_swapped);
3973 	free(btf_ext);
3974 }
3975 
3976 struct btf_ext *btf_ext__new(const __u8 *data, __u32 size)
3977 {
3978 	struct btf_ext *btf_ext;
3979 	int err;
3980 
3981 	btf_ext = calloc(1, sizeof(struct btf_ext));
3982 	if (!btf_ext)
3983 		return libbpf_err_ptr(-ENOMEM);
3984 
3985 	btf_ext->data_size = size;
3986 	btf_ext->data = malloc(size);
3987 	if (!btf_ext->data) {
3988 		err = -ENOMEM;
3989 		goto done;
3990 	}
3991 	memcpy(btf_ext->data, data, size);
3992 
3993 	err = btf_ext_parse(btf_ext);
3994 
3995 done:
3996 	if (err) {
3997 		btf_ext__free(btf_ext);
3998 		return libbpf_err_ptr(err);
3999 	}
4000 
4001 	return btf_ext;
4002 }
4003 
4004 static void *btf_ext_raw_data(const struct btf_ext *btf_ext_ro, bool swap_endian)
4005 {
4006 	struct btf_ext *btf_ext = (struct btf_ext *)btf_ext_ro;
4007 	const __u32 data_sz = btf_ext->data_size;
4008 	void *data;
4009 
4010 	/* Return native data (always present) or swapped data if present */
4011 	if (!swap_endian)
4012 		return btf_ext->data;
4013 	else if (btf_ext->data_swapped)
4014 		return btf_ext->data_swapped;
4015 
4016 	/* Recreate missing swapped data, then cache and return */
4017 	data = calloc(1, data_sz);
4018 	if (!data)
4019 		return NULL;
4020 	memcpy(data, btf_ext->data, data_sz);
4021 
4022 	btf_ext_bswap_info(btf_ext, data);
4023 	btf_ext_bswap_hdr(data);
4024 	btf_ext->data_swapped = data;
4025 	return data;
4026 }
4027 
4028 const void *btf_ext__raw_data(const struct btf_ext *btf_ext, __u32 *size)
4029 {
4030 	void *data;
4031 
4032 	data = btf_ext_raw_data(btf_ext, btf_ext->swapped_endian);
4033 	if (!data)
4034 		return errno = ENOMEM, NULL;
4035 
4036 	*size = btf_ext->data_size;
4037 	return data;
4038 }
4039 
4040 __attribute__((alias("btf_ext__raw_data")))
4041 const void *btf_ext__get_raw_data(const struct btf_ext *btf_ext, __u32 *size);
4042 
4043 enum btf_endianness btf_ext__endianness(const struct btf_ext *btf_ext)
4044 {
4045 	if (is_host_big_endian())
4046 		return btf_ext->swapped_endian ? BTF_LITTLE_ENDIAN : BTF_BIG_ENDIAN;
4047 	else
4048 		return btf_ext->swapped_endian ? BTF_BIG_ENDIAN : BTF_LITTLE_ENDIAN;
4049 }
4050 
4051 int btf_ext__set_endianness(struct btf_ext *btf_ext, enum btf_endianness endian)
4052 {
4053 	if (endian != BTF_LITTLE_ENDIAN && endian != BTF_BIG_ENDIAN)
4054 		return libbpf_err(-EINVAL);
4055 
4056 	btf_ext->swapped_endian = is_host_big_endian() != (endian == BTF_BIG_ENDIAN);
4057 
4058 	if (!btf_ext->swapped_endian) {
4059 		free(btf_ext->data_swapped);
4060 		btf_ext->data_swapped = NULL;
4061 	}
4062 	return 0;
4063 }
4064 
4065 struct btf_dedup;
4066 
4067 static struct btf_dedup *btf_dedup_new(struct btf *btf, const struct btf_dedup_opts *opts);
4068 static void btf_dedup_free(struct btf_dedup *d);
4069 static int btf_dedup_prep(struct btf_dedup *d);
4070 static int btf_dedup_strings(struct btf_dedup *d);
4071 static int btf_dedup_prim_types(struct btf_dedup *d);
4072 static int btf_dedup_struct_types(struct btf_dedup *d);
4073 static int btf_dedup_ref_types(struct btf_dedup *d);
4074 static int btf_dedup_resolve_fwds(struct btf_dedup *d);
4075 static int btf_dedup_compact_types(struct btf_dedup *d);
4076 static int btf_dedup_remap_types(struct btf_dedup *d);
4077 
4078 /*
4079  * Deduplicate BTF types and strings.
4080  *
4081  * BTF dedup algorithm takes as an input `struct btf` representing `.BTF` ELF
4082  * section with all BTF type descriptors and string data. It overwrites that
4083  * memory in-place with deduplicated types and strings without any loss of
4084  * information. If optional `struct btf_ext` representing '.BTF.ext' ELF section
4085  * is provided, all the strings referenced from .BTF.ext section are honored
4086  * and updated to point to the right offsets after deduplication.
4087  *
4088  * If function returns with error, type/string data might be garbled and should
4089  * be discarded.
4090  *
4091  * More verbose and detailed description of both problem btf_dedup is solving,
4092  * as well as solution could be found at:
4093  * https://facebookmicrosites.github.io/bpf/blog/2018/11/14/btf-enhancement.html
4094  *
4095  * Problem description and justification
4096  * =====================================
4097  *
4098  * BTF type information is typically emitted either as a result of conversion
4099  * from DWARF to BTF or directly by compiler. In both cases, each compilation
4100  * unit contains information about a subset of all the types that are used
4101  * in an application. These subsets are frequently overlapping and contain a lot
4102  * of duplicated information when later concatenated together into a single
4103  * binary. This algorithm ensures that each unique type is represented by single
4104  * BTF type descriptor, greatly reducing resulting size of BTF data.
4105  *
4106  * Compilation unit isolation and subsequent duplication of data is not the only
4107  * problem. The same type hierarchy (e.g., struct and all the type that struct
4108  * references) in different compilation units can be represented in BTF to
4109  * various degrees of completeness (or, rather, incompleteness) due to
4110  * struct/union forward declarations.
4111  *
4112  * Let's take a look at an example, that we'll use to better understand the
4113  * problem (and solution). Suppose we have two compilation units, each using
4114  * same `struct S`, but each of them having incomplete type information about
4115  * struct's fields:
4116  *
4117  * // CU #1:
4118  * struct S;
4119  * struct A {
4120  *	int a;
4121  *	struct A* self;
4122  *	struct S* parent;
4123  * };
4124  * struct B;
4125  * struct S {
4126  *	struct A* a_ptr;
4127  *	struct B* b_ptr;
4128  * };
4129  *
4130  * // CU #2:
4131  * struct S;
4132  * struct A;
4133  * struct B {
4134  *	int b;
4135  *	struct B* self;
4136  *	struct S* parent;
4137  * };
4138  * struct S {
4139  *	struct A* a_ptr;
4140  *	struct B* b_ptr;
4141  * };
4142  *
4143  * In case of CU #1, BTF data will know only that `struct B` exist (but no
4144  * more), but will know the complete type information about `struct A`. While
4145  * for CU #2, it will know full type information about `struct B`, but will
4146  * only know about forward declaration of `struct A` (in BTF terms, it will
4147  * have `BTF_KIND_FWD` type descriptor with name `B`).
4148  *
4149  * This compilation unit isolation means that it's possible that there is no
4150  * single CU with complete type information describing structs `S`, `A`, and
4151  * `B`. Also, we might get tons of duplicated and redundant type information.
4152  *
4153  * Additional complication we need to keep in mind comes from the fact that
4154  * types, in general, can form graphs containing cycles, not just DAGs.
4155  *
4156  * While algorithm does deduplication, it also merges and resolves type
4157  * information (unless disabled throught `struct btf_opts`), whenever possible.
4158  * E.g., in the example above with two compilation units having partial type
4159  * information for structs `A` and `B`, the output of algorithm will emit
4160  * a single copy of each BTF type that describes structs `A`, `B`, and `S`
4161  * (as well as type information for `int` and pointers), as if they were defined
4162  * in a single compilation unit as:
4163  *
4164  * struct A {
4165  *	int a;
4166  *	struct A* self;
4167  *	struct S* parent;
4168  * };
4169  * struct B {
4170  *	int b;
4171  *	struct B* self;
4172  *	struct S* parent;
4173  * };
4174  * struct S {
4175  *	struct A* a_ptr;
4176  *	struct B* b_ptr;
4177  * };
4178  *
4179  * Algorithm summary
4180  * =================
4181  *
4182  * Algorithm completes its work in 7 separate passes:
4183  *
4184  * 1. Strings deduplication.
4185  * 2. Primitive types deduplication (int, enum, fwd).
4186  * 3. Struct/union types deduplication.
4187  * 4. Resolve unambiguous forward declarations.
4188  * 5. Reference types deduplication (pointers, typedefs, arrays, funcs, func
4189  *    protos, and const/volatile/restrict modifiers).
4190  * 6. Types compaction.
4191  * 7. Types remapping.
4192  *
4193  * Algorithm determines canonical type descriptor, which is a single
4194  * representative type for each truly unique type. This canonical type is the
4195  * one that will go into final deduplicated BTF type information. For
4196  * struct/unions, it is also the type that algorithm will merge additional type
4197  * information into (while resolving FWDs), as it discovers it from data in
4198  * other CUs. Each input BTF type eventually gets either mapped to itself, if
4199  * that type is canonical, or to some other type, if that type is equivalent
4200  * and was chosen as canonical representative. This mapping is stored in
4201  * `btf_dedup->map` array. This map is also used to record STRUCT/UNION that
4202  * FWD type got resolved to.
4203  *
4204  * To facilitate fast discovery of canonical types, we also maintain canonical
4205  * index (`btf_dedup->dedup_table`), which maps type descriptor's signature hash
4206  * (i.e., hashed kind, name, size, fields, etc) into a list of canonical types
4207  * that match that signature. With sufficiently good choice of type signature
4208  * hashing function, we can limit number of canonical types for each unique type
4209  * signature to a very small number, allowing to find canonical type for any
4210  * duplicated type very quickly.
4211  *
4212  * Struct/union deduplication is the most critical part and algorithm for
4213  * deduplicating structs/unions is described in greater details in comments for
4214  * `btf_dedup_is_equiv` function.
4215  */
4216 int btf__dedup(struct btf *btf, const struct btf_dedup_opts *opts)
4217 {
4218 	struct btf_dedup *d;
4219 	int err;
4220 
4221 	if (!OPTS_VALID(opts, btf_dedup_opts))
4222 		return libbpf_err(-EINVAL);
4223 
4224 	d = btf_dedup_new(btf, opts);
4225 	if (IS_ERR(d)) {
4226 		pr_debug("btf_dedup_new failed: %ld\n", PTR_ERR(d));
4227 		return libbpf_err(-EINVAL);
4228 	}
4229 
4230 	err = btf_ensure_modifiable(btf);
4231 	if (err)
4232 		goto done;
4233 
4234 	err = btf_dedup_prep(d);
4235 	if (err) {
4236 		pr_debug("btf_dedup_prep failed: %s\n", errstr(err));
4237 		goto done;
4238 	}
4239 	err = btf_dedup_strings(d);
4240 	if (err < 0) {
4241 		pr_debug("btf_dedup_strings failed: %s\n", errstr(err));
4242 		goto done;
4243 	}
4244 	err = btf_dedup_prim_types(d);
4245 	if (err < 0) {
4246 		pr_debug("btf_dedup_prim_types failed: %s\n", errstr(err));
4247 		goto done;
4248 	}
4249 	err = btf_dedup_struct_types(d);
4250 	if (err < 0) {
4251 		pr_debug("btf_dedup_struct_types failed: %s\n", errstr(err));
4252 		goto done;
4253 	}
4254 	err = btf_dedup_resolve_fwds(d);
4255 	if (err < 0) {
4256 		pr_debug("btf_dedup_resolve_fwds failed: %s\n", errstr(err));
4257 		goto done;
4258 	}
4259 	err = btf_dedup_ref_types(d);
4260 	if (err < 0) {
4261 		pr_debug("btf_dedup_ref_types failed: %s\n", errstr(err));
4262 		goto done;
4263 	}
4264 	err = btf_dedup_compact_types(d);
4265 	if (err < 0) {
4266 		pr_debug("btf_dedup_compact_types failed: %s\n", errstr(err));
4267 		goto done;
4268 	}
4269 	err = btf_dedup_remap_types(d);
4270 	if (err < 0) {
4271 		pr_debug("btf_dedup_remap_types failed: %s\n", errstr(err));
4272 		goto done;
4273 	}
4274 
4275 done:
4276 	btf_dedup_free(d);
4277 	return libbpf_err(err);
4278 }
4279 
4280 #define BTF_UNPROCESSED_ID ((__u32)-1)
4281 #define BTF_IN_PROGRESS_ID ((__u32)-2)
4282 
4283 struct btf_dedup {
4284 	/* .BTF section to be deduped in-place */
4285 	struct btf *btf;
4286 	/*
4287 	 * Optional .BTF.ext section. When provided, any strings referenced
4288 	 * from it will be taken into account when deduping strings
4289 	 */
4290 	struct btf_ext *btf_ext;
4291 	/*
4292 	 * This is a map from any type's signature hash to a list of possible
4293 	 * canonical representative type candidates. Hash collisions are
4294 	 * ignored, so even types of various kinds can share same list of
4295 	 * candidates, which is fine because we rely on subsequent
4296 	 * btf_xxx_equal() checks to authoritatively verify type equality.
4297 	 */
4298 	struct hashmap *dedup_table;
4299 	/* Canonical types map */
4300 	__u32 *map;
4301 	/* Hypothetical mapping, used during type graph equivalence checks */
4302 	__u32 *hypot_map;
4303 	__u32 *hypot_list;
4304 	size_t hypot_cnt;
4305 	size_t hypot_cap;
4306 	/* Whether hypothetical mapping, if successful, would need to adjust
4307 	 * already canonicalized types (due to a new forward declaration to
4308 	 * concrete type resolution). In such case, during split BTF dedup
4309 	 * candidate type would still be considered as different, because base
4310 	 * BTF is considered to be immutable.
4311 	 */
4312 	bool hypot_adjust_canon;
4313 	/* Various option modifying behavior of algorithm */
4314 	struct btf_dedup_opts opts;
4315 	/* temporary strings deduplication state */
4316 	struct strset *strs_set;
4317 };
4318 
4319 static unsigned long hash_combine(unsigned long h, unsigned long value)
4320 {
4321 	return h * 31 + value;
4322 }
4323 
4324 #define for_each_dedup_cand(d, node, hash) \
4325 	hashmap__for_each_key_entry(d->dedup_table, node, hash)
4326 
4327 static int btf_dedup_table_add(struct btf_dedup *d, long hash, __u32 type_id)
4328 {
4329 	return hashmap__append(d->dedup_table, hash, type_id);
4330 }
4331 
4332 static int btf_dedup_hypot_map_add(struct btf_dedup *d,
4333 				   __u32 from_id, __u32 to_id)
4334 {
4335 	if (d->hypot_cnt == d->hypot_cap) {
4336 		__u32 *new_list;
4337 
4338 		d->hypot_cap += max((size_t)16, d->hypot_cap / 2);
4339 		new_list = libbpf_reallocarray(d->hypot_list, d->hypot_cap, sizeof(__u32));
4340 		if (!new_list)
4341 			return -ENOMEM;
4342 		d->hypot_list = new_list;
4343 	}
4344 	d->hypot_list[d->hypot_cnt++] = from_id;
4345 	d->hypot_map[from_id] = to_id;
4346 	return 0;
4347 }
4348 
4349 static void btf_dedup_clear_hypot_map(struct btf_dedup *d)
4350 {
4351 	int i;
4352 
4353 	for (i = 0; i < d->hypot_cnt; i++)
4354 		d->hypot_map[d->hypot_list[i]] = BTF_UNPROCESSED_ID;
4355 	d->hypot_cnt = 0;
4356 	d->hypot_adjust_canon = false;
4357 }
4358 
4359 static void btf_dedup_free(struct btf_dedup *d)
4360 {
4361 	hashmap__free(d->dedup_table);
4362 	d->dedup_table = NULL;
4363 
4364 	free(d->map);
4365 	d->map = NULL;
4366 
4367 	free(d->hypot_map);
4368 	d->hypot_map = NULL;
4369 
4370 	free(d->hypot_list);
4371 	d->hypot_list = NULL;
4372 
4373 	free(d);
4374 }
4375 
4376 static size_t btf_dedup_identity_hash_fn(long key, void *ctx)
4377 {
4378 	return key;
4379 }
4380 
4381 static size_t btf_dedup_collision_hash_fn(long key, void *ctx)
4382 {
4383 	return 0;
4384 }
4385 
4386 static bool btf_dedup_equal_fn(long k1, long k2, void *ctx)
4387 {
4388 	return k1 == k2;
4389 }
4390 
4391 static struct btf_dedup *btf_dedup_new(struct btf *btf, const struct btf_dedup_opts *opts)
4392 {
4393 	struct btf_dedup *d = calloc(1, sizeof(struct btf_dedup));
4394 	hashmap_hash_fn hash_fn = btf_dedup_identity_hash_fn;
4395 	int i, err = 0, type_cnt;
4396 
4397 	if (!d)
4398 		return ERR_PTR(-ENOMEM);
4399 
4400 	if (OPTS_GET(opts, force_collisions, false))
4401 		hash_fn = btf_dedup_collision_hash_fn;
4402 
4403 	d->btf = btf;
4404 	d->btf_ext = OPTS_GET(opts, btf_ext, NULL);
4405 
4406 	d->dedup_table = hashmap__new(hash_fn, btf_dedup_equal_fn, NULL);
4407 	if (IS_ERR(d->dedup_table)) {
4408 		err = PTR_ERR(d->dedup_table);
4409 		d->dedup_table = NULL;
4410 		goto done;
4411 	}
4412 
4413 	type_cnt = btf__type_cnt(btf);
4414 	d->map = malloc(sizeof(__u32) * type_cnt);
4415 	if (!d->map) {
4416 		err = -ENOMEM;
4417 		goto done;
4418 	}
4419 	/* special BTF "void" type is made canonical immediately */
4420 	d->map[0] = 0;
4421 	for (i = 1; i < type_cnt; i++) {
4422 		struct btf_type *t = btf_type_by_id(d->btf, i);
4423 
4424 		/* VAR, DATASEC and LOCSEC are never deduped and are self-canonical */
4425 		if (btf_is_var(t) || btf_is_datasec(t) || btf_is_locsec(t))
4426 			d->map[i] = i;
4427 		else
4428 			d->map[i] = BTF_UNPROCESSED_ID;
4429 	}
4430 
4431 	d->hypot_map = malloc(sizeof(__u32) * type_cnt);
4432 	if (!d->hypot_map) {
4433 		err = -ENOMEM;
4434 		goto done;
4435 	}
4436 	for (i = 0; i < type_cnt; i++)
4437 		d->hypot_map[i] = BTF_UNPROCESSED_ID;
4438 
4439 done:
4440 	if (err) {
4441 		btf_dedup_free(d);
4442 		return ERR_PTR(err);
4443 	}
4444 
4445 	return d;
4446 }
4447 
4448 /*
4449  * Iterate over all possible places in .BTF and .BTF.ext that can reference
4450  * string and pass pointer to it to a provided callback `fn`.
4451  */
4452 static int btf_for_each_str_off(struct btf_dedup *d, str_off_visit_fn fn, void *ctx)
4453 {
4454 	int i, r;
4455 
4456 	for (i = 0; i < d->btf->nr_types; i++) {
4457 		struct btf_field_iter it;
4458 		struct btf_type *t = btf_type_by_id(d->btf, d->btf->start_id + i);
4459 		__u32 *str_off;
4460 
4461 		r = btf_field_iter_init(&it, t, BTF_FIELD_ITER_STRS);
4462 		if (r)
4463 			return r;
4464 
4465 		while ((str_off = btf_field_iter_next(&it))) {
4466 			r = fn(str_off, ctx);
4467 			if (r)
4468 				return r;
4469 		}
4470 	}
4471 
4472 	if (!d->btf_ext)
4473 		return 0;
4474 
4475 	r = btf_ext_visit_str_offs(d->btf_ext, fn, ctx);
4476 	if (r)
4477 		return r;
4478 
4479 	return 0;
4480 }
4481 
4482 static int strs_dedup_remap_str_off(__u32 *str_off_ptr, void *ctx)
4483 {
4484 	struct btf_dedup *d = ctx;
4485 	__u32 str_off = *str_off_ptr;
4486 	const char *s;
4487 	int off, err;
4488 
4489 	/* don't touch empty string or string in main BTF */
4490 	if (str_off == 0 || str_off < d->btf->start_str_off)
4491 		return 0;
4492 
4493 	s = btf__str_by_offset(d->btf, str_off);
4494 	if (d->btf->base_btf) {
4495 		err = btf__find_str(d->btf->base_btf, s);
4496 		if (err >= 0) {
4497 			*str_off_ptr = err;
4498 			return 0;
4499 		}
4500 		if (err != -ENOENT)
4501 			return err;
4502 	}
4503 
4504 	off = strset__add_str(d->strs_set, s);
4505 	if (off < 0)
4506 		return off;
4507 
4508 	*str_off_ptr = d->btf->start_str_off + off;
4509 	return 0;
4510 }
4511 
4512 /*
4513  * Dedup string and filter out those that are not referenced from either .BTF
4514  * or .BTF.ext (if provided) sections.
4515  *
4516  * This is done by building index of all strings in BTF's string section,
4517  * then iterating over all entities that can reference strings (e.g., type
4518  * names, struct field names, .BTF.ext line info, etc) and marking corresponding
4519  * strings as used. After that all used strings are deduped and compacted into
4520  * sequential blob of memory and new offsets are calculated. Then all the string
4521  * references are iterated again and rewritten using new offsets.
4522  */
4523 static int btf_dedup_strings(struct btf_dedup *d)
4524 {
4525 	int err;
4526 
4527 	if (d->btf->strs_deduped)
4528 		return 0;
4529 
4530 	d->strs_set = strset__new(BTF_MAX_STR_OFFSET, NULL, 0);
4531 	if (IS_ERR(d->strs_set)) {
4532 		err = PTR_ERR(d->strs_set);
4533 		goto err_out;
4534 	}
4535 
4536 	if (!d->btf->base_btf) {
4537 		/* insert empty string; we won't be looking it up during strings
4538 		 * dedup, but it's good to have it for generic BTF string lookups
4539 		 */
4540 		err = strset__add_str(d->strs_set, "");
4541 		if (err < 0)
4542 			goto err_out;
4543 	}
4544 
4545 	/* remap string offsets */
4546 	err = btf_for_each_str_off(d, strs_dedup_remap_str_off, d);
4547 	if (err)
4548 		goto err_out;
4549 
4550 	/* replace BTF string data and hash with deduped ones */
4551 	strset__free(d->btf->strs_set);
4552 	btf_hdr_update_str_len(d->btf, strset__data_size(d->strs_set));
4553 	d->btf->strs_set = d->strs_set;
4554 	d->strs_set = NULL;
4555 	d->btf->strs_deduped = true;
4556 	return 0;
4557 
4558 err_out:
4559 	strset__free(d->strs_set);
4560 	d->strs_set = NULL;
4561 
4562 	return err;
4563 }
4564 
4565 /*
4566  * Calculate type signature hash of TYPEDEF, ignoring referenced type IDs,
4567  * as referenced type IDs equivalence is established separately during type
4568  * graph equivalence check algorithm.
4569  */
4570 static long btf_hash_typedef(struct btf_type *t)
4571 {
4572 	long h;
4573 
4574 	h = hash_combine(0, t->name_off);
4575 	h = hash_combine(h, t->info);
4576 	return h;
4577 }
4578 
4579 static long btf_hash_common(struct btf_type *t)
4580 {
4581 	long h;
4582 
4583 	h = hash_combine(0, t->name_off);
4584 	h = hash_combine(h, t->info);
4585 	h = hash_combine(h, t->size);
4586 	return h;
4587 }
4588 
4589 static bool btf_equal_common(struct btf_type *t1, struct btf_type *t2)
4590 {
4591 	return t1->name_off == t2->name_off &&
4592 	       t1->info == t2->info &&
4593 	       t1->size == t2->size;
4594 }
4595 
4596 /* Check structural compatibility of two TYPEDEF. */
4597 static bool btf_equal_typedef(struct btf_type *t1, struct btf_type *t2)
4598 {
4599 	return t1->name_off == t2->name_off &&
4600 	       t1->info == t2->info;
4601 }
4602 
4603 /* Calculate type signature hash of INT or TAG. */
4604 static long btf_hash_int_decl_tag(struct btf_type *t)
4605 {
4606 	__u32 info = *(__u32 *)(t + 1);
4607 	long h;
4608 
4609 	h = btf_hash_common(t);
4610 	h = hash_combine(h, info);
4611 	return h;
4612 }
4613 
4614 /* Check structural equality of two INTs or TAGs. */
4615 static bool btf_equal_int_tag(struct btf_type *t1, struct btf_type *t2)
4616 {
4617 	__u32 info1, info2;
4618 
4619 	if (!btf_equal_common(t1, t2))
4620 		return false;
4621 	info1 = *(__u32 *)(t1 + 1);
4622 	info2 = *(__u32 *)(t2 + 1);
4623 	return info1 == info2;
4624 }
4625 
4626 /* Calculate type signature hash of ENUM/ENUM64. */
4627 static long btf_hash_enum(struct btf_type *t)
4628 {
4629 	long h;
4630 
4631 	/* don't hash vlen, enum members and size to support enum fwd resolving */
4632 	h = hash_combine(0, t->name_off);
4633 	return h;
4634 }
4635 
4636 static bool btf_equal_enum_members(struct btf_type *t1, struct btf_type *t2)
4637 {
4638 	const struct btf_enum *m1, *m2;
4639 	__u32 vlen;
4640 	int i;
4641 
4642 	vlen = btf_vlen(t1);
4643 	m1 = btf_enum(t1);
4644 	m2 = btf_enum(t2);
4645 	for (i = 0; i < vlen; i++) {
4646 		if (m1->name_off != m2->name_off || m1->val != m2->val)
4647 			return false;
4648 		m1++;
4649 		m2++;
4650 	}
4651 	return true;
4652 }
4653 
4654 static bool btf_equal_enum64_members(struct btf_type *t1, struct btf_type *t2)
4655 {
4656 	const struct btf_enum64 *m1, *m2;
4657 	__u32 vlen;
4658 	int i;
4659 
4660 	vlen = btf_vlen(t1);
4661 	m1 = btf_enum64(t1);
4662 	m2 = btf_enum64(t2);
4663 	for (i = 0; i < vlen; i++) {
4664 		if (m1->name_off != m2->name_off || m1->val_lo32 != m2->val_lo32 ||
4665 		    m1->val_hi32 != m2->val_hi32)
4666 			return false;
4667 		m1++;
4668 		m2++;
4669 	}
4670 	return true;
4671 }
4672 
4673 /* Check structural equality of two ENUMs or ENUM64s. */
4674 static bool btf_equal_enum(struct btf_type *t1, struct btf_type *t2)
4675 {
4676 	if (!btf_equal_common(t1, t2))
4677 		return false;
4678 
4679 	/* t1 & t2 kinds are identical because of btf_equal_common */
4680 	if (btf_kind(t1) == BTF_KIND_ENUM)
4681 		return btf_equal_enum_members(t1, t2);
4682 	else
4683 		return btf_equal_enum64_members(t1, t2);
4684 }
4685 
4686 static inline bool btf_is_enum_fwd(struct btf_type *t)
4687 {
4688 	return btf_is_any_enum(t) && btf_vlen(t) == 0;
4689 }
4690 
4691 static bool btf_compat_enum(struct btf_type *t1, struct btf_type *t2)
4692 {
4693 	if (!btf_is_enum_fwd(t1) && !btf_is_enum_fwd(t2))
4694 		return btf_equal_enum(t1, t2);
4695 	/* At this point either t1 or t2 or both are forward declarations, thus:
4696 	 * - skip comparing vlen because it is zero for forward declarations;
4697 	 * - skip comparing size to allow enum forward declarations
4698 	 *   to be compatible with enum64 full declarations;
4699 	 * - skip comparing kind for the same reason.
4700 	 */
4701 	return t1->name_off == t2->name_off &&
4702 	       btf_is_any_enum(t1) && btf_is_any_enum(t2);
4703 }
4704 
4705 static long btf_hash_loc_param(struct btf_type *t)
4706 {
4707 	struct btf_loc_param *p = btf_loc_param(t);
4708 	long h = btf_hash_common(t);
4709 	int i, vlen = btf_vlen(t);
4710 
4711 	h = hash_combine(h, p->flags);
4712 
4713 	for (i = 0; i < vlen; i++)
4714 		h = hash_combine(h, p->values[i]);
4715 	return h;
4716 }
4717 
4718 static long btf_hash_loc_proto(struct btf_type *t)
4719 {
4720 	__u32 *p = btf_loc_proto_params(t);
4721 	long h = btf_hash_common(t);
4722 	int i, vlen = btf_vlen(t);
4723 
4724 	for (i = 0; i < vlen; i++, p++)
4725 		h = hash_combine(h, *p);
4726 	return h;
4727 }
4728 
4729 static bool btf_equal_loc_param(struct btf_type *t1, struct btf_type *t2)
4730 {
4731 	struct btf_loc_param *p1 = btf_loc_param(t1);
4732 	struct btf_loc_param *p2 = btf_loc_param(t2);
4733 	int i, vlen = btf_vlen(t1);
4734 
4735 	if (!btf_equal_common(t1, t2))
4736 		return false;
4737 	if (p1->flags != p2->flags)
4738 		return false;
4739 	for (i = 0; i < vlen; i++) {
4740 		if (p1->values[i] != p2->values[i])
4741 			return false;
4742 	}
4743 	return true;
4744 }
4745 
4746 /*
4747  * Calculate type signature hash of STRUCT/UNION, ignoring referenced type IDs,
4748  * as referenced type IDs equivalence is established separately during type
4749  * graph equivalence check algorithm.
4750  */
4751 static long btf_hash_struct(struct btf_type *t)
4752 {
4753 	const struct btf_member *member = btf_members(t);
4754 	__u32 vlen = btf_vlen(t);
4755 	long h = btf_hash_common(t);
4756 	int i;
4757 
4758 	for (i = 0; i < vlen; i++) {
4759 		h = hash_combine(h, member->name_off);
4760 		h = hash_combine(h, member->offset);
4761 		/* no hashing of referenced type ID, it can be unresolved yet */
4762 		member++;
4763 	}
4764 	return h;
4765 }
4766 
4767 /*
4768  * Check structural compatibility of two STRUCTs/UNIONs, ignoring referenced
4769  * type IDs. This check is performed during type graph equivalence check and
4770  * referenced types equivalence is checked separately.
4771  */
4772 static bool btf_shallow_equal_struct(struct btf_type *t1, struct btf_type *t2)
4773 {
4774 	const struct btf_member *m1, *m2;
4775 	__u32 vlen;
4776 	int i;
4777 
4778 	if (!btf_equal_common(t1, t2))
4779 		return false;
4780 
4781 	vlen = btf_vlen(t1);
4782 	m1 = btf_members(t1);
4783 	m2 = btf_members(t2);
4784 	for (i = 0; i < vlen; i++) {
4785 		if (m1->name_off != m2->name_off || m1->offset != m2->offset)
4786 			return false;
4787 		m1++;
4788 		m2++;
4789 	}
4790 	return true;
4791 }
4792 
4793 /*
4794  * Calculate type signature hash of ARRAY, including referenced type IDs,
4795  * under assumption that they were already resolved to canonical type IDs and
4796  * are not going to change.
4797  */
4798 static long btf_hash_array(struct btf_type *t)
4799 {
4800 	const struct btf_array *info = btf_array(t);
4801 	long h = btf_hash_common(t);
4802 
4803 	h = hash_combine(h, info->type);
4804 	h = hash_combine(h, info->index_type);
4805 	h = hash_combine(h, info->nelems);
4806 	return h;
4807 }
4808 
4809 /*
4810  * Check exact equality of two ARRAYs, taking into account referenced
4811  * type IDs, under assumption that they were already resolved to canonical
4812  * type IDs and are not going to change.
4813  * This function is called during reference types deduplication to compare
4814  * ARRAY to potential canonical representative.
4815  */
4816 static bool btf_equal_array(struct btf_type *t1, struct btf_type *t2)
4817 {
4818 	const struct btf_array *info1, *info2;
4819 
4820 	if (!btf_equal_common(t1, t2))
4821 		return false;
4822 
4823 	info1 = btf_array(t1);
4824 	info2 = btf_array(t2);
4825 	return info1->type == info2->type &&
4826 	       info1->index_type == info2->index_type &&
4827 	       info1->nelems == info2->nelems;
4828 }
4829 
4830 /*
4831  * Check structural compatibility of two ARRAYs, ignoring referenced type
4832  * IDs. This check is performed during type graph equivalence check and
4833  * referenced types equivalence is checked separately.
4834  */
4835 static bool btf_compat_array(struct btf_type *t1, struct btf_type *t2)
4836 {
4837 	if (!btf_equal_common(t1, t2))
4838 		return false;
4839 
4840 	return btf_array(t1)->nelems == btf_array(t2)->nelems;
4841 }
4842 
4843 /*
4844  * Calculate type signature hash of FUNC_PROTO, including referenced type IDs,
4845  * under assumption that they were already resolved to canonical type IDs and
4846  * are not going to change.
4847  */
4848 static long btf_hash_fnproto(struct btf_type *t)
4849 {
4850 	const struct btf_param *member = btf_params(t);
4851 	__u32 vlen = btf_vlen(t);
4852 	long h = btf_hash_common(t);
4853 	int i;
4854 
4855 	for (i = 0; i < vlen; i++) {
4856 		h = hash_combine(h, member->name_off);
4857 		h = hash_combine(h, member->type);
4858 		member++;
4859 	}
4860 	return h;
4861 }
4862 
4863 /*
4864  * Check exact equality of two FUNC_PROTOs, taking into account referenced
4865  * type IDs, under assumption that they were already resolved to canonical
4866  * type IDs and are not going to change.
4867  * This function is called during reference types deduplication to compare
4868  * FUNC_PROTO to potential canonical representative.
4869  */
4870 static bool btf_equal_fnproto(struct btf_type *t1, struct btf_type *t2)
4871 {
4872 	const struct btf_param *m1, *m2;
4873 	__u32 vlen;
4874 	int i;
4875 
4876 	if (!btf_equal_common(t1, t2))
4877 		return false;
4878 
4879 	vlen = btf_vlen(t1);
4880 	m1 = btf_params(t1);
4881 	m2 = btf_params(t2);
4882 	for (i = 0; i < vlen; i++) {
4883 		if (m1->name_off != m2->name_off || m1->type != m2->type)
4884 			return false;
4885 		m1++;
4886 		m2++;
4887 	}
4888 	return true;
4889 }
4890 
4891 /*
4892  * Check structural compatibility of two FUNC_PROTOs, ignoring referenced type
4893  * IDs. This check is performed during type graph equivalence check and
4894  * referenced types equivalence is checked separately.
4895  */
4896 static bool btf_compat_fnproto(struct btf_type *t1, struct btf_type *t2)
4897 {
4898 	const struct btf_param *m1, *m2;
4899 	__u32 vlen;
4900 	int i;
4901 
4902 	/* skip return type ID */
4903 	if (t1->name_off != t2->name_off || t1->info != t2->info)
4904 		return false;
4905 
4906 	vlen = btf_vlen(t1);
4907 	m1 = btf_params(t1);
4908 	m2 = btf_params(t2);
4909 	for (i = 0; i < vlen; i++) {
4910 		if (m1->name_off != m2->name_off)
4911 			return false;
4912 		m1++;
4913 		m2++;
4914 	}
4915 	return true;
4916 }
4917 
4918 /* Prepare split BTF for deduplication by calculating hashes of base BTF's
4919  * types and initializing the rest of the state (canonical type mapping) for
4920  * the fixed base BTF part.
4921  */
4922 static int btf_dedup_prep(struct btf_dedup *d)
4923 {
4924 	struct btf_type *t;
4925 	int type_id;
4926 	long h;
4927 
4928 	if (!d->btf->base_btf)
4929 		return 0;
4930 
4931 	for (type_id = 1; type_id < d->btf->start_id; type_id++) {
4932 		t = btf_type_by_id(d->btf, type_id);
4933 
4934 		/* all base BTF types are self-canonical by definition */
4935 		d->map[type_id] = type_id;
4936 
4937 		switch (btf_kind(t)) {
4938 		case BTF_KIND_VAR:
4939 		case BTF_KIND_DATASEC:
4940 		case BTF_KIND_LOCSEC:
4941 			/* VAR DATASEC and LOCSEC are never hash/deduplicated */
4942 			continue;
4943 		case BTF_KIND_CONST:
4944 		case BTF_KIND_VOLATILE:
4945 		case BTF_KIND_RESTRICT:
4946 		case BTF_KIND_PTR:
4947 		case BTF_KIND_FWD:
4948 		case BTF_KIND_FUNC:
4949 		case BTF_KIND_FLOAT:
4950 		case BTF_KIND_TYPE_TAG:
4951 			h = btf_hash_common(t);
4952 			break;
4953 		case BTF_KIND_TYPEDEF:
4954 			h = btf_hash_typedef(t);
4955 			break;
4956 		case BTF_KIND_INT:
4957 		case BTF_KIND_DECL_TAG:
4958 			h = btf_hash_int_decl_tag(t);
4959 			break;
4960 		case BTF_KIND_ENUM:
4961 		case BTF_KIND_ENUM64:
4962 			h = btf_hash_enum(t);
4963 			break;
4964 		case BTF_KIND_STRUCT:
4965 		case BTF_KIND_UNION:
4966 			h = btf_hash_struct(t);
4967 			break;
4968 		case BTF_KIND_ARRAY:
4969 			h = btf_hash_array(t);
4970 			break;
4971 		case BTF_KIND_FUNC_PROTO:
4972 			h = btf_hash_fnproto(t);
4973 			break;
4974 		case BTF_KIND_LOC_PARAM:
4975 			h = btf_hash_loc_param(t);
4976 			break;
4977 		case BTF_KIND_LOC_PROTO:
4978 			h = btf_hash_loc_proto(t);
4979 			break;
4980 		default:
4981 			pr_debug("unknown kind %d for type [%d]\n", btf_kind(t), type_id);
4982 			return -EINVAL;
4983 		}
4984 		if (btf_dedup_table_add(d, h, type_id))
4985 			return -ENOMEM;
4986 	}
4987 
4988 	return 0;
4989 }
4990 
4991 /*
4992  * Deduplicate primitive types, that can't reference other types, by calculating
4993  * their type signature hash and comparing them with any possible canonical
4994  * candidate. If no canonical candidate matches, type itself is marked as
4995  * canonical and is added into `btf_dedup->dedup_table` as another candidate.
4996  */
4997 static int btf_dedup_prim_type(struct btf_dedup *d, __u32 type_id)
4998 {
4999 	struct btf_type *t = btf_type_by_id(d->btf, type_id);
5000 	struct hashmap_entry *hash_entry;
5001 	struct btf_type *cand;
5002 	/* if we don't find equivalent type, then we are canonical */
5003 	__u32 new_id = type_id;
5004 	__u32 cand_id;
5005 	long h;
5006 
5007 	switch (btf_kind(t)) {
5008 	case BTF_KIND_CONST:
5009 	case BTF_KIND_VOLATILE:
5010 	case BTF_KIND_RESTRICT:
5011 	case BTF_KIND_PTR:
5012 	case BTF_KIND_TYPEDEF:
5013 	case BTF_KIND_ARRAY:
5014 	case BTF_KIND_STRUCT:
5015 	case BTF_KIND_UNION:
5016 	case BTF_KIND_FUNC:
5017 	case BTF_KIND_FUNC_PROTO:
5018 	case BTF_KIND_VAR:
5019 	case BTF_KIND_DATASEC:
5020 	case BTF_KIND_DECL_TAG:
5021 	case BTF_KIND_TYPE_TAG:
5022 	case BTF_KIND_LOC_PROTO:
5023 	case BTF_KIND_LOCSEC:
5024 		return 0;
5025 
5026 	case BTF_KIND_INT:
5027 		h = btf_hash_int_decl_tag(t);
5028 		for_each_dedup_cand(d, hash_entry, h) {
5029 			cand_id = hash_entry->value;
5030 			cand = btf_type_by_id(d->btf, cand_id);
5031 			if (btf_equal_int_tag(t, cand)) {
5032 				new_id = cand_id;
5033 				break;
5034 			}
5035 		}
5036 		break;
5037 
5038 	case BTF_KIND_ENUM:
5039 	case BTF_KIND_ENUM64:
5040 		h = btf_hash_enum(t);
5041 		for_each_dedup_cand(d, hash_entry, h) {
5042 			cand_id = hash_entry->value;
5043 			cand = btf_type_by_id(d->btf, cand_id);
5044 			if (btf_equal_enum(t, cand)) {
5045 				new_id = cand_id;
5046 				break;
5047 			}
5048 			if (btf_compat_enum(t, cand)) {
5049 				if (btf_is_enum_fwd(t)) {
5050 					/* resolve fwd to full enum */
5051 					new_id = cand_id;
5052 					break;
5053 				}
5054 				/* resolve canonical enum fwd to full enum */
5055 				d->map[cand_id] = type_id;
5056 			}
5057 		}
5058 		break;
5059 
5060 	case BTF_KIND_FWD:
5061 	case BTF_KIND_FLOAT:
5062 		h = btf_hash_common(t);
5063 		for_each_dedup_cand(d, hash_entry, h) {
5064 			cand_id = hash_entry->value;
5065 			cand = btf_type_by_id(d->btf, cand_id);
5066 			if (btf_equal_common(t, cand)) {
5067 				new_id = cand_id;
5068 				break;
5069 			}
5070 		}
5071 		break;
5072 
5073 	case BTF_KIND_LOC_PARAM:
5074 		h = btf_hash_loc_param(t);
5075 		for_each_dedup_cand(d, hash_entry, h) {
5076 			cand_id = hash_entry->value;
5077 			cand = btf_type_by_id(d->btf, cand_id);
5078 			if (btf_equal_loc_param(t, cand)) {
5079 				new_id = cand_id;
5080 				break;
5081 			}
5082 		}
5083 		break;
5084 
5085 	default:
5086 		return -EINVAL;
5087 	}
5088 
5089 	d->map[type_id] = new_id;
5090 	if (type_id == new_id && btf_dedup_table_add(d, h, type_id))
5091 		return -ENOMEM;
5092 
5093 	return 0;
5094 }
5095 
5096 static int btf_dedup_prim_types(struct btf_dedup *d)
5097 {
5098 	int i, err;
5099 
5100 	for (i = 0; i < d->btf->nr_types; i++) {
5101 		err = btf_dedup_prim_type(d, d->btf->start_id + i);
5102 		if (err)
5103 			return err;
5104 	}
5105 	return 0;
5106 }
5107 
5108 /*
5109  * Check whether type is already mapped into canonical one (could be to itself).
5110  */
5111 static inline bool is_type_mapped(struct btf_dedup *d, uint32_t type_id)
5112 {
5113 	return d->map[type_id] <= BTF_MAX_NR_TYPES;
5114 }
5115 
5116 /*
5117  * Resolve type ID into its canonical type ID, if any; otherwise return original
5118  * type ID. If type is FWD and is resolved into STRUCT/UNION already, follow
5119  * STRUCT/UNION link and resolve it into canonical type ID as well.
5120  */
5121 static inline __u32 resolve_type_id(struct btf_dedup *d, __u32 type_id)
5122 {
5123 	while (is_type_mapped(d, type_id) && d->map[type_id] != type_id)
5124 		type_id = d->map[type_id];
5125 	return type_id;
5126 }
5127 
5128 /*
5129  * Resolve FWD to underlying STRUCT/UNION, if any; otherwise return original
5130  * type ID.
5131  */
5132 static uint32_t resolve_fwd_id(struct btf_dedup *d, uint32_t type_id)
5133 {
5134 	__u32 orig_type_id = type_id;
5135 
5136 	if (!btf_is_fwd(btf__type_by_id(d->btf, type_id)))
5137 		return type_id;
5138 
5139 	while (is_type_mapped(d, type_id) && d->map[type_id] != type_id)
5140 		type_id = d->map[type_id];
5141 
5142 	if (!btf_is_fwd(btf__type_by_id(d->btf, type_id)))
5143 		return type_id;
5144 
5145 	return orig_type_id;
5146 }
5147 
5148 
5149 static inline __u16 btf_fwd_kind(struct btf_type *t)
5150 {
5151 	return btf_kflag(t) ? BTF_KIND_UNION : BTF_KIND_STRUCT;
5152 }
5153 
5154 static bool btf_dedup_identical_types(struct btf_dedup *d, __u32 id1, __u32 id2, int depth)
5155 {
5156 	struct btf_type *t1, *t2;
5157 	int k1, k2;
5158 recur:
5159 	t1 = btf_type_by_id(d->btf, id1);
5160 	t2 = btf_type_by_id(d->btf, id2);
5161 	if (depth <= 0) {
5162 		pr_debug("Reached depth limit for identical type comparison for '%s'/'%s'\n",
5163 			 btf__name_by_offset(d->btf, t1->name_off),
5164 			 btf__name_by_offset(d->btf, t2->name_off));
5165 		return false;
5166 	}
5167 
5168 	k1 = btf_kind(t1);
5169 	k2 = btf_kind(t2);
5170 	if (k1 != k2)
5171 		return false;
5172 
5173 	switch (k1) {
5174 	case BTF_KIND_UNKN: /* VOID */
5175 		return true;
5176 	case BTF_KIND_INT:
5177 		return btf_equal_int_tag(t1, t2);
5178 	case BTF_KIND_ENUM:
5179 	case BTF_KIND_ENUM64:
5180 		return btf_compat_enum(t1, t2);
5181 	case BTF_KIND_FWD:
5182 	case BTF_KIND_FLOAT:
5183 		return btf_equal_common(t1, t2);
5184 	case BTF_KIND_CONST:
5185 	case BTF_KIND_VOLATILE:
5186 	case BTF_KIND_RESTRICT:
5187 	case BTF_KIND_PTR:
5188 	case BTF_KIND_TYPEDEF:
5189 	case BTF_KIND_FUNC:
5190 	case BTF_KIND_TYPE_TAG:
5191 		if (t1->info != t2->info || t1->name_off != t2->name_off)
5192 			return false;
5193 		id1 = t1->type;
5194 		id2 = t2->type;
5195 		goto recur;
5196 	case BTF_KIND_ARRAY: {
5197 		struct btf_array *a1, *a2;
5198 
5199 		if (!btf_compat_array(t1, t2))
5200 			return false;
5201 
5202 		a1 = btf_array(t1);
5203 		a2 = btf_array(t2);
5204 
5205 		if (a1->index_type != a2->index_type &&
5206 		    !btf_dedup_identical_types(d, a1->index_type, a2->index_type, depth - 1))
5207 			return false;
5208 
5209 		if (a1->type != a2->type &&
5210 		    !btf_dedup_identical_types(d, a1->type, a2->type, depth - 1))
5211 			return false;
5212 
5213 		return true;
5214 	}
5215 	case BTF_KIND_STRUCT:
5216 	case BTF_KIND_UNION: {
5217 		const struct btf_member *m1, *m2;
5218 		int i, n;
5219 
5220 		if (!btf_shallow_equal_struct(t1, t2))
5221 			return false;
5222 
5223 		m1 = btf_members(t1);
5224 		m2 = btf_members(t2);
5225 		for (i = 0, n = btf_vlen(t1); i < n; i++, m1++, m2++) {
5226 			if (m1->type == m2->type)
5227 				continue;
5228 			if (!btf_dedup_identical_types(d, m1->type, m2->type, depth - 1)) {
5229 				if (t1->name_off) {
5230 					pr_debug("%s '%s' size=%u vlen=%u id1[%u] id2[%u] shallow-equal but not identical for field#%d '%s'\n",
5231 						 k1 == BTF_KIND_STRUCT ? "STRUCT" : "UNION",
5232 						 btf__name_by_offset(d->btf, t1->name_off),
5233 						 t1->size, btf_vlen(t1), id1, id2, i,
5234 						 btf__name_by_offset(d->btf, m1->name_off));
5235 				}
5236 				return false;
5237 			}
5238 		}
5239 		return true;
5240 	}
5241 	case BTF_KIND_FUNC_PROTO: {
5242 		const struct btf_param *p1, *p2;
5243 		int i, n;
5244 
5245 		if (!btf_compat_fnproto(t1, t2))
5246 			return false;
5247 
5248 		if (t1->type != t2->type &&
5249 		    !btf_dedup_identical_types(d, t1->type, t2->type, depth - 1))
5250 			return false;
5251 
5252 		p1 = btf_params(t1);
5253 		p2 = btf_params(t2);
5254 		for (i = 0, n = btf_vlen(t1); i < n; i++, p1++, p2++) {
5255 			if (p1->type == p2->type)
5256 				continue;
5257 			if (!btf_dedup_identical_types(d, p1->type, p2->type, depth - 1))
5258 				return false;
5259 		}
5260 		return true;
5261 	}
5262 	default:
5263 		return false;
5264 	}
5265 }
5266 
5267 
5268 /*
5269  * Check equivalence of BTF type graph formed by candidate struct/union (we'll
5270  * call it "candidate graph" in this description for brevity) to a type graph
5271  * formed by (potential) canonical struct/union ("canonical graph" for brevity
5272  * here, though keep in mind that not all types in canonical graph are
5273  * necessarily canonical representatives themselves, some of them might be
5274  * duplicates or its uniqueness might not have been established yet).
5275  * Returns:
5276  *  - >0, if type graphs are equivalent;
5277  *  -  0, if not equivalent;
5278  *  - <0, on error.
5279  *
5280  * Algorithm performs side-by-side DFS traversal of both type graphs and checks
5281  * equivalence of BTF types at each step. If at any point BTF types in candidate
5282  * and canonical graphs are not compatible structurally, whole graphs are
5283  * incompatible. If types are structurally equivalent (i.e., all information
5284  * except referenced type IDs is exactly the same), a mapping from `canon_id` to
5285  * a `cand_id` is recoded in hypothetical mapping (`btf_dedup->hypot_map`).
5286  * If a type references other types, then those referenced types are checked
5287  * for equivalence recursively.
5288  *
5289  * During DFS traversal, if we find that for current `canon_id` type we
5290  * already have some mapping in hypothetical map, we check for two possible
5291  * situations:
5292  *   - `canon_id` is mapped to exactly the same type as `cand_id`. This will
5293  *     happen when type graphs have cycles. In this case we assume those two
5294  *     types are equivalent.
5295  *   - `canon_id` is mapped to different type. This is contradiction in our
5296  *     hypothetical mapping, because same graph in canonical graph corresponds
5297  *     to two different types in candidate graph, which for equivalent type
5298  *     graphs shouldn't happen. This condition terminates equivalence check
5299  *     with negative result.
5300  *
5301  * If type graphs traversal exhausts types to check and find no contradiction,
5302  * then type graphs are equivalent.
5303  *
5304  * When checking types for equivalence, there is one special case: FWD types.
5305  * If FWD type resolution is allowed and one of the types (either from canonical
5306  * or candidate graph) is FWD and other is STRUCT/UNION (depending on FWD's kind
5307  * flag) and their names match, hypothetical mapping is updated to point from
5308  * FWD to STRUCT/UNION. If graphs will be determined as equivalent successfully,
5309  * this mapping will be used to record FWD -> STRUCT/UNION mapping permanently.
5310  *
5311  * Technically, this could lead to incorrect FWD to STRUCT/UNION resolution,
5312  * if there are two exactly named (or anonymous) structs/unions that are
5313  * compatible structurally, one of which has FWD field, while other is concrete
5314  * STRUCT/UNION, but according to C sources they are different structs/unions
5315  * that are referencing different types with the same name. This is extremely
5316  * unlikely to happen, but btf_dedup API allows to disable FWD resolution if
5317  * this logic is causing problems.
5318  *
5319  * Doing FWD resolution means that both candidate and/or canonical graphs can
5320  * consists of portions of the graph that come from multiple compilation units.
5321  * This is due to the fact that types within single compilation unit are always
5322  * deduplicated and FWDs are already resolved, if referenced struct/union
5323  * definition is available. So, if we had unresolved FWD and found corresponding
5324  * STRUCT/UNION, they will be from different compilation units. This
5325  * consequently means that when we "link" FWD to corresponding STRUCT/UNION,
5326  * type graph will likely have at least two different BTF types that describe
5327  * same type (e.g., most probably there will be two different BTF types for the
5328  * same 'int' primitive type) and could even have "overlapping" parts of type
5329  * graph that describe same subset of types.
5330  *
5331  * This in turn means that our assumption that each type in canonical graph
5332  * must correspond to exactly one type in candidate graph might not hold
5333  * anymore and will make it harder to detect contradictions using hypothetical
5334  * map. To handle this problem, we allow to follow FWD -> STRUCT/UNION
5335  * resolution only in canonical graph. FWDs in candidate graphs are never
5336  * resolved. To see why it's OK, let's check all possible situations w.r.t. FWDs
5337  * that can occur:
5338  *   - Both types in canonical and candidate graphs are FWDs. If they are
5339  *     structurally equivalent, then they can either be both resolved to the
5340  *     same STRUCT/UNION or not resolved at all. In both cases they are
5341  *     equivalent and there is no need to resolve FWD on candidate side.
5342  *   - Both types in canonical and candidate graphs are concrete STRUCT/UNION,
5343  *     so nothing to resolve as well, algorithm will check equivalence anyway.
5344  *   - Type in canonical graph is FWD, while type in candidate is concrete
5345  *     STRUCT/UNION. In this case candidate graph comes from single compilation
5346  *     unit, so there is exactly one BTF type for each unique C type. After
5347  *     resolving FWD into STRUCT/UNION, there might be more than one BTF type
5348  *     in canonical graph mapping to single BTF type in candidate graph, but
5349  *     because hypothetical mapping maps from canonical to candidate types, it's
5350  *     alright, and we still maintain the property of having single `canon_id`
5351  *     mapping to single `cand_id` (there could be two different `canon_id`
5352  *     mapped to the same `cand_id`, but it's not contradictory).
5353  *   - Type in canonical graph is concrete STRUCT/UNION, while type in candidate
5354  *     graph is FWD. In this case we are just going to check compatibility of
5355  *     STRUCT/UNION and corresponding FWD, and if they are compatible, we'll
5356  *     assume that whatever STRUCT/UNION FWD resolves to must be equivalent to
5357  *     a concrete STRUCT/UNION from canonical graph. If the rest of type graphs
5358  *     turn out equivalent, we'll re-resolve FWD to concrete STRUCT/UNION from
5359  *     canonical graph.
5360  */
5361 static int btf_dedup_is_equiv(struct btf_dedup *d, __u32 cand_id,
5362 			      __u32 canon_id)
5363 {
5364 	struct btf_type *cand_type;
5365 	struct btf_type *canon_type;
5366 	__u32 hypot_type_id;
5367 	__u16 cand_kind;
5368 	__u16 canon_kind;
5369 	int i, eq;
5370 
5371 	/* if both resolve to the same canonical, they must be equivalent */
5372 	if (resolve_type_id(d, cand_id) == resolve_type_id(d, canon_id))
5373 		return 1;
5374 
5375 	canon_id = resolve_fwd_id(d, canon_id);
5376 
5377 	hypot_type_id = d->hypot_map[canon_id];
5378 	if (hypot_type_id <= BTF_MAX_NR_TYPES) {
5379 		if (hypot_type_id == cand_id)
5380 			return 1;
5381 		/* In some cases compiler will generate different DWARF types
5382 		 * for *identical* array type definitions and use them for
5383 		 * different fields within the *same* struct. This breaks type
5384 		 * equivalence check, which makes an assumption that candidate
5385 		 * types sub-graph has a consistent and deduped-by-compiler
5386 		 * types within a single CU. And similar situation can happen
5387 		 * with struct/union sometimes, and event with pointers.
5388 		 * So accommodate cases like this doing a structural
5389 		 * comparison recursively, but avoiding being stuck in endless
5390 		 * loops by limiting the depth up to which we check.
5391 		 */
5392 		if (btf_dedup_identical_types(d, hypot_type_id, cand_id, 16))
5393 			return 1;
5394 		return 0;
5395 	}
5396 
5397 	if (btf_dedup_hypot_map_add(d, canon_id, cand_id))
5398 		return -ENOMEM;
5399 
5400 	cand_type = btf_type_by_id(d->btf, cand_id);
5401 	canon_type = btf_type_by_id(d->btf, canon_id);
5402 	cand_kind = btf_kind(cand_type);
5403 	canon_kind = btf_kind(canon_type);
5404 
5405 	if (cand_type->name_off != canon_type->name_off)
5406 		return 0;
5407 
5408 	/* FWD <--> STRUCT/UNION equivalence check, if enabled */
5409 	if ((cand_kind == BTF_KIND_FWD || canon_kind == BTF_KIND_FWD)
5410 	    && cand_kind != canon_kind) {
5411 		__u16 real_kind;
5412 		__u16 fwd_kind;
5413 
5414 		if (cand_kind == BTF_KIND_FWD) {
5415 			real_kind = canon_kind;
5416 			fwd_kind = btf_fwd_kind(cand_type);
5417 		} else {
5418 			real_kind = cand_kind;
5419 			fwd_kind = btf_fwd_kind(canon_type);
5420 			/* we'd need to resolve base FWD to STRUCT/UNION */
5421 			if (fwd_kind == real_kind && canon_id < d->btf->start_id)
5422 				d->hypot_adjust_canon = true;
5423 		}
5424 		return fwd_kind == real_kind;
5425 	}
5426 
5427 	if (cand_kind != canon_kind)
5428 		return 0;
5429 
5430 	switch (cand_kind) {
5431 	case BTF_KIND_INT:
5432 		return btf_equal_int_tag(cand_type, canon_type);
5433 
5434 	case BTF_KIND_ENUM:
5435 	case BTF_KIND_ENUM64:
5436 		return btf_compat_enum(cand_type, canon_type);
5437 
5438 	case BTF_KIND_FWD:
5439 	case BTF_KIND_FLOAT:
5440 		return btf_equal_common(cand_type, canon_type);
5441 
5442 	case BTF_KIND_CONST:
5443 	case BTF_KIND_VOLATILE:
5444 	case BTF_KIND_RESTRICT:
5445 	case BTF_KIND_PTR:
5446 	case BTF_KIND_TYPEDEF:
5447 	case BTF_KIND_FUNC:
5448 	case BTF_KIND_TYPE_TAG:
5449 		if (cand_type->info != canon_type->info)
5450 			return 0;
5451 		return btf_dedup_is_equiv(d, cand_type->type, canon_type->type);
5452 
5453 	case BTF_KIND_ARRAY: {
5454 		const struct btf_array *cand_arr, *canon_arr;
5455 
5456 		if (!btf_compat_array(cand_type, canon_type))
5457 			return 0;
5458 		cand_arr = btf_array(cand_type);
5459 		canon_arr = btf_array(canon_type);
5460 		eq = btf_dedup_is_equiv(d, cand_arr->index_type, canon_arr->index_type);
5461 		if (eq <= 0)
5462 			return eq;
5463 		return btf_dedup_is_equiv(d, cand_arr->type, canon_arr->type);
5464 	}
5465 
5466 	case BTF_KIND_STRUCT:
5467 	case BTF_KIND_UNION: {
5468 		const struct btf_member *cand_m, *canon_m;
5469 		__u32 vlen;
5470 
5471 		if (!btf_shallow_equal_struct(cand_type, canon_type))
5472 			return 0;
5473 		vlen = btf_vlen(cand_type);
5474 		cand_m = btf_members(cand_type);
5475 		canon_m = btf_members(canon_type);
5476 		for (i = 0; i < vlen; i++) {
5477 			eq = btf_dedup_is_equiv(d, cand_m->type, canon_m->type);
5478 			if (eq <= 0) {
5479 				if (cand_type->name_off) {
5480 					pr_debug("%s '%s' size=%u vlen=%u cand_id[%u] canon_id[%u] shallow-equal but not equiv for field#%d '%s': %d\n",
5481 						 cand_kind == BTF_KIND_STRUCT ? "STRUCT" : "UNION",
5482 						 btf__name_by_offset(d->btf, cand_type->name_off),
5483 						 cand_type->size, vlen, cand_id, canon_id, i,
5484 						 btf__name_by_offset(d->btf, cand_m->name_off), eq);
5485 				}
5486 				return eq;
5487 			}
5488 			cand_m++;
5489 			canon_m++;
5490 		}
5491 
5492 		return 1;
5493 	}
5494 
5495 	case BTF_KIND_FUNC_PROTO: {
5496 		const struct btf_param *cand_p, *canon_p;
5497 		__u32 vlen;
5498 
5499 		if (!btf_compat_fnproto(cand_type, canon_type))
5500 			return 0;
5501 		eq = btf_dedup_is_equiv(d, cand_type->type, canon_type->type);
5502 		if (eq <= 0)
5503 			return eq;
5504 		vlen = btf_vlen(cand_type);
5505 		cand_p = btf_params(cand_type);
5506 		canon_p = btf_params(canon_type);
5507 		for (i = 0; i < vlen; i++) {
5508 			eq = btf_dedup_is_equiv(d, cand_p->type, canon_p->type);
5509 			if (eq <= 0)
5510 				return eq;
5511 			cand_p++;
5512 			canon_p++;
5513 		}
5514 		return 1;
5515 	}
5516 
5517 	case BTF_KIND_LOC_PARAM:
5518 		return btf_equal_loc_param(cand_type, canon_type);
5519 
5520 	case BTF_KIND_LOC_PROTO:
5521 	case BTF_KIND_LOCSEC:
5522 		return 0;
5523 
5524 	default:
5525 		return -EINVAL;
5526 	}
5527 	return 0;
5528 }
5529 
5530 /*
5531  * Use hypothetical mapping, produced by successful type graph equivalence
5532  * check, to augment existing struct/union canonical mapping, where possible.
5533  *
5534  * If BTF_KIND_FWD resolution is allowed, this mapping is also used to record
5535  * FWD -> STRUCT/UNION correspondence as well. FWD resolution is bidirectional:
5536  * it doesn't matter if FWD type was part of canonical graph or candidate one,
5537  * we are recording the mapping anyway. As opposed to carefulness required
5538  * for struct/union correspondence mapping (described below), for FWD resolution
5539  * it's not important, as by the time that FWD type (reference type) will be
5540  * deduplicated all structs/unions will be deduped already anyway.
5541  *
5542  * Recording STRUCT/UNION mapping is purely a performance optimization and is
5543  * not required for correctness. It needs to be done carefully to ensure that
5544  * struct/union from candidate's type graph is not mapped into corresponding
5545  * struct/union from canonical type graph that itself hasn't been resolved into
5546  * canonical representative. The only guarantee we have is that canonical
5547  * struct/union was determined as canonical and that won't change. But any
5548  * types referenced through that struct/union fields could have been not yet
5549  * resolved, so in case like that it's too early to establish any kind of
5550  * correspondence between structs/unions.
5551  *
5552  * No canonical correspondence is derived for primitive types (they are already
5553  * deduplicated completely already anyway) or reference types (they rely on
5554  * stability of struct/union canonical relationship for equivalence checks).
5555  */
5556 static void btf_dedup_merge_hypot_map(struct btf_dedup *d)
5557 {
5558 	__u32 canon_type_id, targ_type_id;
5559 	__u16 t_kind, c_kind;
5560 	__u32 t_id, c_id;
5561 	int i;
5562 
5563 	for (i = 0; i < d->hypot_cnt; i++) {
5564 		canon_type_id = d->hypot_list[i];
5565 		targ_type_id = d->hypot_map[canon_type_id];
5566 		t_id = resolve_type_id(d, targ_type_id);
5567 		c_id = resolve_type_id(d, canon_type_id);
5568 		t_kind = btf_kind(btf__type_by_id(d->btf, t_id));
5569 		c_kind = btf_kind(btf__type_by_id(d->btf, c_id));
5570 		/*
5571 		 * Resolve FWD into STRUCT/UNION.
5572 		 * It's ok to resolve FWD into STRUCT/UNION that's not yet
5573 		 * mapped to canonical representative (as opposed to
5574 		 * STRUCT/UNION <--> STRUCT/UNION mapping logic below), because
5575 		 * eventually that struct is going to be mapped and all resolved
5576 		 * FWDs will automatically resolve to correct canonical
5577 		 * representative. This will happen before ref type deduping,
5578 		 * which critically depends on stability of these mapping. This
5579 		 * stability is not a requirement for STRUCT/UNION equivalence
5580 		 * checks, though.
5581 		 */
5582 
5583 		/* if it's the split BTF case, we still need to point base FWD
5584 		 * to STRUCT/UNION in a split BTF, because FWDs from split BTF
5585 		 * will be resolved against base FWD. If we don't point base
5586 		 * canonical FWD to the resolved STRUCT/UNION, then all the
5587 		 * FWDs in split BTF won't be correctly resolved to a proper
5588 		 * STRUCT/UNION.
5589 		 */
5590 		if (t_kind != BTF_KIND_FWD && c_kind == BTF_KIND_FWD)
5591 			d->map[c_id] = t_id;
5592 
5593 		/* if graph equivalence determined that we'd need to adjust
5594 		 * base canonical types, then we need to only point base FWDs
5595 		 * to STRUCTs/UNIONs and do no more modifications. For all
5596 		 * other purposes the type graphs were not equivalent.
5597 		 */
5598 		if (d->hypot_adjust_canon)
5599 			continue;
5600 
5601 		if (t_kind == BTF_KIND_FWD && c_kind != BTF_KIND_FWD)
5602 			d->map[t_id] = c_id;
5603 
5604 		if ((t_kind == BTF_KIND_STRUCT || t_kind == BTF_KIND_UNION) &&
5605 		    c_kind != BTF_KIND_FWD &&
5606 		    is_type_mapped(d, c_id) &&
5607 		    !is_type_mapped(d, t_id)) {
5608 			/*
5609 			 * as a perf optimization, we can map struct/union
5610 			 * that's part of type graph we just verified for
5611 			 * equivalence. We can do that for struct/union that has
5612 			 * canonical representative only, though.
5613 			 */
5614 			d->map[t_id] = c_id;
5615 		}
5616 	}
5617 }
5618 
5619 static inline long btf_hash_by_kind(struct btf_type *t, __u16 kind)
5620 {
5621 	if (kind == BTF_KIND_TYPEDEF)
5622 		return btf_hash_typedef(t);
5623 	else
5624 		return btf_hash_struct(t);
5625 }
5626 
5627 static inline bool btf_equal_by_kind(struct btf_type *t1, struct btf_type *t2, __u16 kind)
5628 {
5629 	if (kind == BTF_KIND_TYPEDEF)
5630 		return btf_equal_typedef(t1, t2);
5631 	else
5632 		return btf_shallow_equal_struct(t1, t2);
5633 }
5634 
5635 /*
5636  * Deduplicate struct/union and typedef types.
5637  *
5638  * For each struct/union type its type signature hash is calculated, taking
5639  * into account type's name, size, number, order and names of fields, but
5640  * ignoring type ID's referenced from fields, because they might not be deduped
5641  * completely until after reference types deduplication phase. For each typedef
5642  * type, the hash is computed based on the type’s name and size. This type hash
5643  * is used to iterate over all potential canonical types, sharing same hash.
5644  * For each canonical candidate we check whether type graphs that they form
5645  * (through referenced types in fields and so on) are equivalent using algorithm
5646  * implemented in `btf_dedup_is_equiv`. If such equivalence is found and
5647  * BTF_KIND_FWD resolution is allowed, then hypothetical mapping
5648  * (btf_dedup->hypot_map) produced by aforementioned type graph equivalence
5649  * algorithm is used to record FWD -> STRUCT/UNION mapping. It's also used to
5650  * potentially map other structs/unions to their canonical representatives,
5651  * if such relationship hasn't yet been established. This speeds up algorithm
5652  * by eliminating some of the duplicate work.
5653  *
5654  * If no matching canonical representative was found, struct/union is marked
5655  * as canonical for itself and is added into btf_dedup->dedup_table hash map
5656  * for further look ups.
5657  */
5658 static int btf_dedup_struct_type(struct btf_dedup *d, __u32 type_id)
5659 {
5660 	struct btf_type *cand_type, *t;
5661 	struct hashmap_entry *hash_entry;
5662 	/* if we don't find equivalent type, then we are canonical */
5663 	__u32 new_id = type_id;
5664 	__u16 kind;
5665 	long h;
5666 
5667 	/* already deduped or is in process of deduping (loop detected) */
5668 	if (d->map[type_id] <= BTF_MAX_NR_TYPES)
5669 		return 0;
5670 
5671 	t = btf_type_by_id(d->btf, type_id);
5672 	kind = btf_kind(t);
5673 
5674 	if (kind != BTF_KIND_STRUCT &&
5675 		kind != BTF_KIND_UNION &&
5676 		kind != BTF_KIND_TYPEDEF)
5677 		return 0;
5678 
5679 	h = btf_hash_by_kind(t, kind);
5680 	for_each_dedup_cand(d, hash_entry, h) {
5681 		__u32 cand_id = hash_entry->value;
5682 		int eq;
5683 
5684 		/*
5685 		 * Even though btf_dedup_is_equiv() checks for
5686 		 * btf_equal_by_kind() internally when checking two
5687 		 * structs (unions) or typedefs for equivalence, we need to guard here
5688 		 * from picking matching FWD type as a dedup candidate.
5689 		 * This can happen due to hash collision. In such case just
5690 		 * relying on btf_dedup_is_equiv() would lead to potentially
5691 		 * creating a loop (FWD -> STRUCT and STRUCT -> FWD), because
5692 		 * FWD and compatible STRUCT/UNION are considered equivalent.
5693 		 */
5694 		cand_type = btf_type_by_id(d->btf, cand_id);
5695 		if (!btf_equal_by_kind(t, cand_type, kind))
5696 			continue;
5697 
5698 		btf_dedup_clear_hypot_map(d);
5699 		eq = btf_dedup_is_equiv(d, type_id, cand_id);
5700 		if (eq < 0)
5701 			return eq;
5702 		if (!eq)
5703 			continue;
5704 		btf_dedup_merge_hypot_map(d);
5705 		if (d->hypot_adjust_canon) /* not really equivalent */
5706 			continue;
5707 		new_id = cand_id;
5708 		break;
5709 	}
5710 
5711 	d->map[type_id] = new_id;
5712 	if (type_id == new_id && btf_dedup_table_add(d, h, type_id))
5713 		return -ENOMEM;
5714 
5715 	return 0;
5716 }
5717 
5718 static int btf_dedup_struct_types(struct btf_dedup *d)
5719 {
5720 	int i, err;
5721 
5722 	for (i = 0; i < d->btf->nr_types; i++) {
5723 		err = btf_dedup_struct_type(d, d->btf->start_id + i);
5724 		if (err)
5725 			return err;
5726 	}
5727 	return 0;
5728 }
5729 
5730 /*
5731  * Deduplicate reference type.
5732  *
5733  * Once all primitive, struct/union and typedef types got deduplicated, we can easily
5734  * deduplicate all other (reference) BTF types. This is done in two steps:
5735  *
5736  * 1. Resolve all referenced type IDs into their canonical type IDs. This
5737  * resolution can be done either immediately for primitive, struct/union, and typedef
5738  * types (because they were deduped in previous two phases) or recursively for
5739  * reference types. Recursion will always terminate at either primitive or
5740  * struct/union and typedef types, at which point we can "unwind" chain of reference
5741  * types one by one. There is no danger of encountering cycles in C, as the only way to
5742  * form a type cycle is through struct or union types. Go can form such cycles through
5743  * typedef. Thus, any chain of reference types, even those taking part in a type cycle,
5744  * will inevitably reach a struct/union or typedef type at some point.
5745  *
5746  * 2. Once all referenced type IDs are resolved into canonical ones, BTF type
5747  * becomes "stable", in the sense that no further deduplication will cause
5748  * any changes to it. With that, it's now possible to calculate type's signature
5749  * hash (this time taking into account referenced type IDs) and loop over all
5750  * potential canonical representatives. If no match was found, current type
5751  * will become canonical representative of itself and will be added into
5752  * btf_dedup->dedup_table as another possible canonical representative.
5753  */
5754 static int btf_dedup_ref_type(struct btf_dedup *d, __u32 type_id)
5755 {
5756 	struct hashmap_entry *hash_entry;
5757 	__u32 new_id = type_id, cand_id;
5758 	struct btf_type *t, *cand;
5759 	/* if we don't find equivalent type, then we are representative type */
5760 	int ref_type_id;
5761 	long h;
5762 
5763 	if (d->map[type_id] == BTF_IN_PROGRESS_ID)
5764 		return -ELOOP;
5765 	if (d->map[type_id] <= BTF_MAX_NR_TYPES)
5766 		return resolve_type_id(d, type_id);
5767 
5768 	t = btf_type_by_id(d->btf, type_id);
5769 	d->map[type_id] = BTF_IN_PROGRESS_ID;
5770 
5771 	switch (btf_kind(t)) {
5772 	case BTF_KIND_CONST:
5773 	case BTF_KIND_VOLATILE:
5774 	case BTF_KIND_RESTRICT:
5775 	case BTF_KIND_PTR:
5776 	case BTF_KIND_FUNC:
5777 	case BTF_KIND_TYPE_TAG:
5778 		ref_type_id = btf_dedup_ref_type(d, t->type);
5779 		if (ref_type_id < 0)
5780 			return ref_type_id;
5781 		t->type = ref_type_id;
5782 
5783 		h = btf_hash_common(t);
5784 		for_each_dedup_cand(d, hash_entry, h) {
5785 			cand_id = hash_entry->value;
5786 			cand = btf_type_by_id(d->btf, cand_id);
5787 			if (btf_equal_common(t, cand)) {
5788 				new_id = cand_id;
5789 				break;
5790 			}
5791 		}
5792 		break;
5793 
5794 	case BTF_KIND_DECL_TAG:
5795 		ref_type_id = btf_dedup_ref_type(d, t->type);
5796 		if (ref_type_id < 0)
5797 			return ref_type_id;
5798 		t->type = ref_type_id;
5799 
5800 		h = btf_hash_int_decl_tag(t);
5801 		for_each_dedup_cand(d, hash_entry, h) {
5802 			cand_id = hash_entry->value;
5803 			cand = btf_type_by_id(d->btf, cand_id);
5804 			if (btf_equal_int_tag(t, cand)) {
5805 				new_id = cand_id;
5806 				break;
5807 			}
5808 		}
5809 		break;
5810 
5811 	case BTF_KIND_ARRAY: {
5812 		struct btf_array *info = btf_array(t);
5813 
5814 		ref_type_id = btf_dedup_ref_type(d, info->type);
5815 		if (ref_type_id < 0)
5816 			return ref_type_id;
5817 		info->type = ref_type_id;
5818 
5819 		ref_type_id = btf_dedup_ref_type(d, info->index_type);
5820 		if (ref_type_id < 0)
5821 			return ref_type_id;
5822 		info->index_type = ref_type_id;
5823 
5824 		h = btf_hash_array(t);
5825 		for_each_dedup_cand(d, hash_entry, h) {
5826 			cand_id = hash_entry->value;
5827 			cand = btf_type_by_id(d->btf, cand_id);
5828 			if (btf_equal_array(t, cand)) {
5829 				new_id = cand_id;
5830 				break;
5831 			}
5832 		}
5833 		break;
5834 	}
5835 
5836 	case BTF_KIND_FUNC_PROTO: {
5837 		struct btf_param *param;
5838 		__u32 vlen;
5839 		int i;
5840 
5841 		ref_type_id = btf_dedup_ref_type(d, t->type);
5842 		if (ref_type_id < 0)
5843 			return ref_type_id;
5844 		t->type = ref_type_id;
5845 
5846 		vlen = btf_vlen(t);
5847 		param = btf_params(t);
5848 		for (i = 0; i < vlen; i++) {
5849 			ref_type_id = btf_dedup_ref_type(d, param->type);
5850 			if (ref_type_id < 0)
5851 				return ref_type_id;
5852 			param->type = ref_type_id;
5853 			param++;
5854 		}
5855 
5856 		h = btf_hash_fnproto(t);
5857 		for_each_dedup_cand(d, hash_entry, h) {
5858 			cand_id = hash_entry->value;
5859 			cand = btf_type_by_id(d->btf, cand_id);
5860 			if (btf_equal_fnproto(t, cand)) {
5861 				new_id = cand_id;
5862 				break;
5863 			}
5864 		}
5865 		break;
5866 	}
5867 
5868 	case BTF_KIND_LOC_PROTO: {
5869 		__u32 *p1, *p2;
5870 		__u32 i, vlen;
5871 
5872 		p1 = btf_loc_proto_params(t);
5873 		vlen = btf_vlen(t);
5874 
5875 		for (i = 0; i < vlen; i++, p1++) {
5876 			ref_type_id = btf_dedup_ref_type(d, *p1);
5877 			if (ref_type_id < 0)
5878 				return ref_type_id;
5879 			*p1 = ref_type_id;
5880 		}
5881 
5882 		h = btf_hash_loc_proto(t);
5883 		for_each_dedup_cand(d, hash_entry, h) {
5884 			cand_id = hash_entry->value;
5885 			cand = btf_type_by_id(d->btf, cand_id);
5886 			if (!btf_equal_common(t, cand))
5887 				continue;
5888 			vlen = btf_vlen(cand);
5889 			p1 = btf_loc_proto_params(t);
5890 			p2 = btf_loc_proto_params(cand);
5891 			if (memcmp(p1, p2, vlen * sizeof(__u32)) == 0) {
5892 				new_id = cand_id;
5893 				break;
5894 			}
5895 		}
5896 		break;
5897 	}
5898 
5899 	default:
5900 		return -EINVAL;
5901 	}
5902 
5903 	d->map[type_id] = new_id;
5904 	if (type_id == new_id && btf_dedup_table_add(d, h, type_id))
5905 		return -ENOMEM;
5906 
5907 	return new_id;
5908 }
5909 
5910 static int btf_dedup_ref_types(struct btf_dedup *d)
5911 {
5912 	int i, err;
5913 
5914 	for (i = 0; i < d->btf->nr_types; i++) {
5915 		err = btf_dedup_ref_type(d, d->btf->start_id + i);
5916 		if (err < 0)
5917 			return err;
5918 	}
5919 	/* we won't need d->dedup_table anymore */
5920 	hashmap__free(d->dedup_table);
5921 	d->dedup_table = NULL;
5922 	return 0;
5923 }
5924 
5925 /*
5926  * Collect a map from type names to type ids for all canonical structs
5927  * and unions. If the same name is shared by several canonical types
5928  * use a special value 0 to indicate this fact.
5929  */
5930 static int btf_dedup_fill_unique_names_map(struct btf_dedup *d, struct hashmap *names_map)
5931 {
5932 	__u32 nr_types = btf__type_cnt(d->btf);
5933 	struct btf_type *t;
5934 	__u32 type_id;
5935 	__u16 kind;
5936 	int err;
5937 
5938 	/*
5939 	 * Iterate over base and split module ids in order to get all
5940 	 * available structs in the map.
5941 	 */
5942 	for (type_id = 1; type_id < nr_types; ++type_id) {
5943 		t = btf_type_by_id(d->btf, type_id);
5944 		kind = btf_kind(t);
5945 
5946 		if (kind != BTF_KIND_STRUCT && kind != BTF_KIND_UNION)
5947 			continue;
5948 
5949 		/* Skip non-canonical types */
5950 		if (type_id != d->map[type_id])
5951 			continue;
5952 
5953 		err = hashmap__add(names_map, t->name_off, type_id);
5954 		if (err == -EEXIST)
5955 			err = hashmap__set(names_map, t->name_off, 0, NULL, NULL);
5956 
5957 		if (err)
5958 			return err;
5959 	}
5960 
5961 	return 0;
5962 }
5963 
5964 static int btf_dedup_resolve_fwd(struct btf_dedup *d, struct hashmap *names_map, __u32 type_id)
5965 {
5966 	struct btf_type *t = btf_type_by_id(d->btf, type_id);
5967 	enum btf_fwd_kind fwd_kind = btf_kflag(t);
5968 	__u16 cand_kind, kind = btf_kind(t);
5969 	struct btf_type *cand_t;
5970 	uintptr_t cand_id;
5971 
5972 	if (kind != BTF_KIND_FWD)
5973 		return 0;
5974 
5975 	/* Skip if this FWD already has a mapping */
5976 	if (type_id != d->map[type_id])
5977 		return 0;
5978 
5979 	if (!hashmap__find(names_map, t->name_off, &cand_id))
5980 		return 0;
5981 
5982 	/* Zero is a special value indicating that name is not unique */
5983 	if (!cand_id)
5984 		return 0;
5985 
5986 	cand_t = btf_type_by_id(d->btf, cand_id);
5987 	cand_kind = btf_kind(cand_t);
5988 	if ((cand_kind == BTF_KIND_STRUCT && fwd_kind != BTF_FWD_STRUCT) ||
5989 	    (cand_kind == BTF_KIND_UNION && fwd_kind != BTF_FWD_UNION))
5990 		return 0;
5991 
5992 	d->map[type_id] = cand_id;
5993 
5994 	return 0;
5995 }
5996 
5997 /*
5998  * Resolve unambiguous forward declarations.
5999  *
6000  * The lion's share of all FWD declarations is resolved during
6001  * `btf_dedup_struct_types` phase when different type graphs are
6002  * compared against each other. However, if in some compilation unit a
6003  * FWD declaration is not a part of a type graph compared against
6004  * another type graph that declaration's canonical type would not be
6005  * changed. Example:
6006  *
6007  * CU #1:
6008  *
6009  * struct foo;
6010  * struct foo *some_global;
6011  *
6012  * CU #2:
6013  *
6014  * struct foo { int u; };
6015  * struct foo *another_global;
6016  *
6017  * After `btf_dedup_struct_types` the BTF looks as follows:
6018  *
6019  * [1] STRUCT 'foo' size=4 vlen=1 ...
6020  * [2] INT 'int' size=4 ...
6021  * [3] PTR '(anon)' type_id=1
6022  * [4] FWD 'foo' fwd_kind=struct
6023  * [5] PTR '(anon)' type_id=4
6024  *
6025  * This pass assumes that such FWD declarations should be mapped to
6026  * structs or unions with identical name in case if the name is not
6027  * ambiguous.
6028  */
6029 static int btf_dedup_resolve_fwds(struct btf_dedup *d)
6030 {
6031 	int i, err;
6032 	struct hashmap *names_map;
6033 
6034 	names_map = hashmap__new(btf_dedup_identity_hash_fn, btf_dedup_equal_fn, NULL);
6035 	if (IS_ERR(names_map))
6036 		return PTR_ERR(names_map);
6037 
6038 	err = btf_dedup_fill_unique_names_map(d, names_map);
6039 	if (err < 0)
6040 		goto exit;
6041 
6042 	for (i = 0; i < d->btf->nr_types; i++) {
6043 		err = btf_dedup_resolve_fwd(d, names_map, d->btf->start_id + i);
6044 		if (err < 0)
6045 			break;
6046 	}
6047 
6048 exit:
6049 	hashmap__free(names_map);
6050 	return err;
6051 }
6052 
6053 /*
6054  * Compact types.
6055  *
6056  * After we established for each type its corresponding canonical representative
6057  * type, we now can eliminate types that are not canonical and leave only
6058  * canonical ones layed out sequentially in memory by copying them over
6059  * duplicates. During compaction btf_dedup->hypot_map array is reused to store
6060  * a map from original type ID to a new compacted type ID, which will be used
6061  * during next phase to "fix up" type IDs, referenced from struct/union and
6062  * reference types.
6063  */
6064 static int btf_dedup_compact_types(struct btf_dedup *d)
6065 {
6066 	__u32 *new_offs;
6067 	__u32 next_type_id = d->btf->start_id;
6068 	const struct btf_type *t;
6069 	void *p;
6070 	int i, id, len;
6071 
6072 	/* we are going to reuse hypot_map to store compaction remapping */
6073 	d->hypot_map[0] = 0;
6074 	/* base BTF types are not renumbered */
6075 	for (id = 1; id < d->btf->start_id; id++)
6076 		d->hypot_map[id] = id;
6077 	for (i = 0, id = d->btf->start_id; i < d->btf->nr_types; i++, id++)
6078 		d->hypot_map[id] = BTF_UNPROCESSED_ID;
6079 
6080 	p = d->btf->types_data;
6081 
6082 	for (i = 0, id = d->btf->start_id; i < d->btf->nr_types; i++, id++) {
6083 		if (d->map[id] != id)
6084 			continue;
6085 
6086 		t = btf__type_by_id(d->btf, id);
6087 		len = btf_type_size(d->btf, t);
6088 		if (len < 0)
6089 			return len;
6090 
6091 		memmove(p, t, len);
6092 		d->hypot_map[id] = next_type_id;
6093 		d->btf->type_offs[next_type_id - d->btf->start_id] = p - d->btf->types_data;
6094 		p += len;
6095 		next_type_id++;
6096 	}
6097 
6098 	/* shrink struct btf's internal types index and update btf_header */
6099 	d->btf->nr_types = next_type_id - d->btf->start_id;
6100 	d->btf->type_offs_cap = d->btf->nr_types;
6101 	d->btf->hdr.type_len = p - d->btf->types_data;
6102 	new_offs = libbpf_reallocarray(d->btf->type_offs, d->btf->type_offs_cap,
6103 				       sizeof(*new_offs));
6104 	if (d->btf->type_offs_cap && !new_offs)
6105 		return -ENOMEM;
6106 	d->btf->type_offs = new_offs;
6107 	if (d->btf->layout)
6108 		d->btf->hdr.layout_off = d->btf->hdr.type_off + d->btf->hdr.type_len;
6109 	d->btf->hdr.str_off = d->btf->hdr.type_off + d->btf->hdr.type_len + d->btf->hdr.layout_len;
6110 	d->btf->raw_size = d->btf->hdr.hdr_len + d->btf->hdr.type_off + d->btf->hdr.type_len +
6111 			   d->btf->hdr.layout_len + d->btf->hdr.str_len;
6112 	return 0;
6113 }
6114 
6115 /*
6116  * Figure out final (deduplicated and compacted) type ID for provided original
6117  * `type_id` by first resolving it into corresponding canonical type ID and
6118  * then mapping it to a deduplicated type ID, stored in btf_dedup->hypot_map,
6119  * which is populated during compaction phase.
6120  */
6121 static int btf_dedup_remap_type_id(__u32 *type_id, void *ctx)
6122 {
6123 	struct btf_dedup *d = ctx;
6124 	__u32 resolved_type_id, new_type_id;
6125 
6126 	resolved_type_id = resolve_type_id(d, *type_id);
6127 	new_type_id = d->hypot_map[resolved_type_id];
6128 	if (new_type_id > BTF_MAX_NR_TYPES)
6129 		return -EINVAL;
6130 
6131 	*type_id = new_type_id;
6132 	return 0;
6133 }
6134 
6135 /*
6136  * Remap referenced type IDs into deduped type IDs.
6137  *
6138  * After BTF types are deduplicated and compacted, their final type IDs may
6139  * differ from original ones. The map from original to a corresponding
6140  * deduped type ID is stored in btf_dedup->hypot_map and is populated during
6141  * compaction phase. During remapping phase we are rewriting all type IDs
6142  * referenced from any BTF type (e.g., struct fields, func proto args, etc) to
6143  * their final deduped type IDs.
6144  */
6145 static int btf_dedup_remap_types(struct btf_dedup *d)
6146 {
6147 	int i, r;
6148 
6149 	for (i = 0; i < d->btf->nr_types; i++) {
6150 		struct btf_type *t = btf_type_by_id(d->btf, d->btf->start_id + i);
6151 		struct btf_field_iter it;
6152 		__u32 *type_id;
6153 
6154 		r = btf_field_iter_init(&it, t, BTF_FIELD_ITER_IDS);
6155 		if (r)
6156 			return r;
6157 
6158 		while ((type_id = btf_field_iter_next(&it))) {
6159 			__u32 resolved_id, new_id;
6160 
6161 			resolved_id = resolve_type_id(d, *type_id);
6162 			new_id = d->hypot_map[resolved_id];
6163 			if (new_id > BTF_MAX_NR_TYPES)
6164 				return -EINVAL;
6165 
6166 			*type_id = new_id;
6167 		}
6168 	}
6169 
6170 	if (!d->btf_ext)
6171 		return 0;
6172 
6173 	r = btf_ext_visit_type_ids(d->btf_ext, btf_dedup_remap_type_id, d);
6174 	if (r)
6175 		return r;
6176 
6177 	return 0;
6178 }
6179 
6180 /*
6181  * Probe few well-known locations for vmlinux kernel image and try to load BTF
6182  * data out of it to use for target BTF.
6183  */
6184 struct btf *btf__load_vmlinux_btf(void)
6185 {
6186 	const char *sysfs_btf_path = "/sys/kernel/btf/vmlinux";
6187 	/* fall back locations, trying to find vmlinux on disk */
6188 	const char *locations[] = {
6189 		"/boot/vmlinux-%1$s",
6190 		"/lib/modules/%1$s/vmlinux-%1$s",
6191 		"/lib/modules/%1$s/build/vmlinux",
6192 		"/usr/lib/modules/%1$s/kernel/vmlinux",
6193 		"/usr/lib/debug/boot/vmlinux-%1$s",
6194 		"/usr/lib/debug/boot/vmlinux-%1$s.debug",
6195 		"/usr/lib/debug/lib/modules/%1$s/vmlinux",
6196 	};
6197 	char path[PATH_MAX + 1];
6198 	struct utsname buf;
6199 	struct btf *btf;
6200 	int i, err;
6201 
6202 	/* is canonical sysfs location accessible? */
6203 	if (faccessat(AT_FDCWD, sysfs_btf_path, F_OK, AT_EACCESS) < 0) {
6204 		pr_warn("kernel BTF is missing at '%s', was CONFIG_DEBUG_INFO_BTF enabled?\n",
6205 			sysfs_btf_path);
6206 	} else {
6207 		btf = btf_parse_raw_mmap(sysfs_btf_path, NULL);
6208 		if (IS_ERR(btf))
6209 			btf = btf__parse(sysfs_btf_path, NULL);
6210 
6211 		if (!btf) {
6212 			err = -errno;
6213 			pr_warn("failed to read kernel BTF from '%s': %s\n",
6214 				sysfs_btf_path, errstr(err));
6215 			return libbpf_err_ptr(err);
6216 		}
6217 		pr_debug("loaded kernel BTF from '%s'\n", sysfs_btf_path);
6218 		return btf;
6219 	}
6220 
6221 	/* try fallback locations */
6222 	uname(&buf);
6223 	for (i = 0; i < ARRAY_SIZE(locations); i++) {
6224 		snprintf(path, PATH_MAX, locations[i], buf.release);
6225 
6226 		if (faccessat(AT_FDCWD, path, R_OK, AT_EACCESS))
6227 			continue;
6228 
6229 		btf = btf__parse(path, NULL);
6230 		err = libbpf_get_error(btf);
6231 		pr_debug("loading kernel BTF '%s': %s\n", path, errstr(err));
6232 		if (err)
6233 			continue;
6234 
6235 		return btf;
6236 	}
6237 
6238 	pr_warn("failed to find valid kernel BTF\n");
6239 	return libbpf_err_ptr(-ESRCH);
6240 }
6241 
6242 struct btf *libbpf_find_kernel_btf(void) __attribute__((alias("btf__load_vmlinux_btf")));
6243 
6244 struct btf *btf__load_module_btf(const char *module_name, struct btf *vmlinux_btf)
6245 {
6246 	char path[80];
6247 
6248 	snprintf(path, sizeof(path), "/sys/kernel/btf/%s", module_name);
6249 	return btf__parse_split(path, vmlinux_btf);
6250 }
6251 
6252 int btf_ext_visit_type_ids(struct btf_ext *btf_ext, type_id_visit_fn visit, void *ctx)
6253 {
6254 	const struct btf_ext_info *seg;
6255 	struct btf_ext_info_sec *sec;
6256 	int i, err;
6257 
6258 	seg = &btf_ext->func_info;
6259 	for_each_btf_ext_sec(seg, sec) {
6260 		struct bpf_func_info_min *rec;
6261 
6262 		for_each_btf_ext_rec(seg, sec, i, rec) {
6263 			err = visit(&rec->type_id, ctx);
6264 			if (err < 0)
6265 				return err;
6266 		}
6267 	}
6268 
6269 	seg = &btf_ext->core_relo_info;
6270 	for_each_btf_ext_sec(seg, sec) {
6271 		struct bpf_core_relo *rec;
6272 
6273 		for_each_btf_ext_rec(seg, sec, i, rec) {
6274 			err = visit(&rec->type_id, ctx);
6275 			if (err < 0)
6276 				return err;
6277 		}
6278 	}
6279 
6280 	return 0;
6281 }
6282 
6283 int btf_ext_visit_str_offs(struct btf_ext *btf_ext, str_off_visit_fn visit, void *ctx)
6284 {
6285 	const struct btf_ext_info *seg;
6286 	struct btf_ext_info_sec *sec;
6287 	int i, err;
6288 
6289 	seg = &btf_ext->func_info;
6290 	for_each_btf_ext_sec(seg, sec) {
6291 		err = visit(&sec->sec_name_off, ctx);
6292 		if (err)
6293 			return err;
6294 	}
6295 
6296 	seg = &btf_ext->line_info;
6297 	for_each_btf_ext_sec(seg, sec) {
6298 		struct bpf_line_info_min *rec;
6299 
6300 		err = visit(&sec->sec_name_off, ctx);
6301 		if (err)
6302 			return err;
6303 
6304 		for_each_btf_ext_rec(seg, sec, i, rec) {
6305 			err = visit(&rec->file_name_off, ctx);
6306 			if (err)
6307 				return err;
6308 			err = visit(&rec->line_off, ctx);
6309 			if (err)
6310 				return err;
6311 		}
6312 	}
6313 
6314 	seg = &btf_ext->core_relo_info;
6315 	for_each_btf_ext_sec(seg, sec) {
6316 		struct bpf_core_relo *rec;
6317 
6318 		err = visit(&sec->sec_name_off, ctx);
6319 		if (err)
6320 			return err;
6321 
6322 		for_each_btf_ext_rec(seg, sec, i, rec) {
6323 			err = visit(&rec->access_str_off, ctx);
6324 			if (err)
6325 				return err;
6326 		}
6327 	}
6328 
6329 	return 0;
6330 }
6331 
6332 struct btf_distill {
6333 	struct btf_pipe pipe;
6334 	int *id_map;
6335 	unsigned int split_start_id;
6336 	unsigned int split_start_str;
6337 	int diff_id;
6338 };
6339 
6340 static int btf_add_distilled_type_ids(struct btf_distill *dist, __u32 i)
6341 {
6342 	struct btf_type *split_t = btf_type_by_id(dist->pipe.src, i);
6343 	struct btf_field_iter it;
6344 	__u32 *id;
6345 	int err;
6346 
6347 	err = btf_field_iter_init(&it, split_t, BTF_FIELD_ITER_IDS);
6348 	if (err)
6349 		return err;
6350 	while ((id = btf_field_iter_next(&it))) {
6351 		struct btf_type *base_t;
6352 
6353 		if (!*id)
6354 			continue;
6355 		/* split BTF id, not needed */
6356 		if (*id >= dist->split_start_id)
6357 			continue;
6358 		/* already added ? */
6359 		if (dist->id_map[*id] > 0)
6360 			continue;
6361 
6362 		/* only a subset of base BTF types should be referenced from
6363 		 * split BTF; ensure nothing unexpected is referenced.
6364 		 */
6365 		base_t = btf_type_by_id(dist->pipe.src, *id);
6366 		switch (btf_kind(base_t)) {
6367 		case BTF_KIND_INT:
6368 		case BTF_KIND_FLOAT:
6369 		case BTF_KIND_FWD:
6370 		case BTF_KIND_ARRAY:
6371 		case BTF_KIND_STRUCT:
6372 		case BTF_KIND_UNION:
6373 		case BTF_KIND_TYPEDEF:
6374 		case BTF_KIND_ENUM:
6375 		case BTF_KIND_ENUM64:
6376 		case BTF_KIND_PTR:
6377 		case BTF_KIND_CONST:
6378 		case BTF_KIND_RESTRICT:
6379 		case BTF_KIND_VOLATILE:
6380 		case BTF_KIND_FUNC:
6381 		case BTF_KIND_FUNC_PROTO:
6382 		case BTF_KIND_TYPE_TAG:
6383 		case BTF_KIND_LOC_PARAM:
6384 		case BTF_KIND_LOC_PROTO:
6385 			dist->id_map[*id] = *id;
6386 			break;
6387 		default:
6388 			pr_warn("unexpected reference to base type[%u] of kind [%u] when creating distilled base BTF.\n",
6389 				*id, btf_kind(base_t));
6390 			return -EINVAL;
6391 		}
6392 		/* If a base type is used, ensure types it refers to are
6393 		 * marked as used also; so for example if we find a PTR to INT
6394 		 * we need both the PTR and INT.
6395 		 *
6396 		 * The only exception is named struct/unions, since distilled
6397 		 * base BTF composite types have no members.
6398 		 */
6399 		if (btf_is_composite(base_t) && base_t->name_off)
6400 			continue;
6401 		err = btf_add_distilled_type_ids(dist, *id);
6402 		if (err)
6403 			return err;
6404 	}
6405 	return 0;
6406 }
6407 
6408 static int btf_add_distilled_types(struct btf_distill *dist)
6409 {
6410 	bool adding_to_base = dist->pipe.dst->base_btf == NULL;
6411 	int id = btf__type_cnt(dist->pipe.dst);
6412 	struct btf_type *t;
6413 	int i, err = 0;
6414 
6415 
6416 	/* Add types for each of the required references to either distilled
6417 	 * base or split BTF, depending on type characteristics.
6418 	 */
6419 	for (i = 1; i < dist->split_start_id; i++) {
6420 		const char *name;
6421 		int kind;
6422 
6423 		if (!dist->id_map[i])
6424 			continue;
6425 		t = btf_type_by_id(dist->pipe.src, i);
6426 		kind = btf_kind(t);
6427 		name = btf__name_by_offset(dist->pipe.src, t->name_off);
6428 
6429 		switch (kind) {
6430 		case BTF_KIND_INT:
6431 		case BTF_KIND_FLOAT:
6432 		case BTF_KIND_FWD:
6433 			/* Named int, float, fwd are added to base. */
6434 			if (!adding_to_base)
6435 				continue;
6436 			err = btf_add_type(&dist->pipe, t);
6437 			break;
6438 		case BTF_KIND_STRUCT:
6439 		case BTF_KIND_UNION:
6440 			/* Named struct/union are added to base as 0-vlen
6441 			 * struct/union of same size.  Anonymous struct/unions
6442 			 * are added to split BTF as-is.
6443 			 */
6444 			if (adding_to_base) {
6445 				if (!t->name_off)
6446 					continue;
6447 				err = btf_add_composite(dist->pipe.dst, kind, name, t->size);
6448 			} else {
6449 				if (t->name_off)
6450 					continue;
6451 				err = btf_add_type(&dist->pipe, t);
6452 			}
6453 			break;
6454 		case BTF_KIND_ENUM:
6455 		case BTF_KIND_ENUM64:
6456 			/* Named enum[64]s are added to base as a sized
6457 			 * enum; relocation will match with appropriately-named
6458 			 * and sized enum or enum64.
6459 			 *
6460 			 * Anonymous enums are added to split BTF as-is.
6461 			 */
6462 			if (adding_to_base) {
6463 				if (!t->name_off)
6464 					continue;
6465 				err = btf__add_enum(dist->pipe.dst, name, t->size);
6466 			} else {
6467 				if (t->name_off)
6468 					continue;
6469 				err = btf_add_type(&dist->pipe, t);
6470 			}
6471 			break;
6472 		case BTF_KIND_ARRAY:
6473 		case BTF_KIND_TYPEDEF:
6474 		case BTF_KIND_PTR:
6475 		case BTF_KIND_CONST:
6476 		case BTF_KIND_RESTRICT:
6477 		case BTF_KIND_VOLATILE:
6478 		case BTF_KIND_FUNC:
6479 		case BTF_KIND_FUNC_PROTO:
6480 		case BTF_KIND_TYPE_TAG:
6481 		case BTF_KIND_LOC_PARAM:
6482 		case BTF_KIND_LOC_PROTO:
6483 		case BTF_KIND_LOCSEC:
6484 			/* All other types are added to split BTF. */
6485 			if (adding_to_base)
6486 				continue;
6487 			err = btf_add_type(&dist->pipe, t);
6488 			break;
6489 		default:
6490 			pr_warn("unexpected kind when adding base type '%s'[%d] of kind [%d] to distilled base BTF.\n",
6491 				name, i, kind);
6492 			return -EINVAL;
6493 
6494 		}
6495 		if (err < 0)
6496 			break;
6497 		dist->id_map[i] = id++;
6498 	}
6499 	return err;
6500 }
6501 
6502 /* Split BTF ids without a mapping will be shifted downwards since distilled
6503  * base BTF is smaller than the original base BTF.  For those that have a
6504  * mapping (either to base or updated split BTF), update the id based on
6505  * that mapping.
6506  */
6507 static int btf_update_distilled_type_ids(struct btf_distill *dist, __u32 i)
6508 {
6509 	struct btf_type *t = btf_type_by_id(dist->pipe.dst, i);
6510 	struct btf_field_iter it;
6511 	__u32 *id;
6512 	int err;
6513 
6514 	err = btf_field_iter_init(&it, t, BTF_FIELD_ITER_IDS);
6515 	if (err)
6516 		return err;
6517 	while ((id = btf_field_iter_next(&it))) {
6518 		if (dist->id_map[*id])
6519 			*id = dist->id_map[*id];
6520 		else if (*id >= dist->split_start_id)
6521 			*id -= dist->diff_id;
6522 	}
6523 	return 0;
6524 }
6525 
6526 /* Create updated split BTF with distilled base BTF; distilled base BTF
6527  * consists of BTF information required to clarify the types that split
6528  * BTF refers to, omitting unneeded details.  Specifically it will contain
6529  * base types and memberless definitions of named structs, unions and enumerated
6530  * types. Associated reference types like pointers, arrays and anonymous
6531  * structs, unions and enumerated types will be added to split BTF.
6532  * Size is recorded for named struct/unions to help guide matching to the
6533  * target base BTF during later relocation.
6534  *
6535  * The only case where structs, unions or enumerated types are fully represented
6536  * is when they are anonymous; in such cases, the anonymous type is added to
6537  * split BTF in full.
6538  *
6539  * We return newly-created split BTF where the split BTF refers to a newly-created
6540  * distilled base BTF. Both must be freed separately by the caller.
6541  */
6542 int btf__distill_base(const struct btf *src_btf, struct btf **new_base_btf,
6543 		      struct btf **new_split_btf)
6544 {
6545 	struct btf *new_base = NULL, *new_split = NULL;
6546 	const struct btf *old_base;
6547 	unsigned int n = btf__type_cnt(src_btf);
6548 	struct btf_distill dist = {};
6549 	struct btf_type *t;
6550 	int i, err = 0;
6551 
6552 	/* src BTF must be split BTF. */
6553 	old_base = btf__base_btf(src_btf);
6554 	if (!new_base_btf || !new_split_btf || !old_base)
6555 		return libbpf_err(-EINVAL);
6556 
6557 	new_base = btf__new_empty();
6558 	if (!new_base)
6559 		return libbpf_err(-ENOMEM);
6560 
6561 	btf__set_endianness(new_base, btf__endianness(src_btf));
6562 
6563 	dist.id_map = calloc(n, sizeof(*dist.id_map));
6564 	if (!dist.id_map) {
6565 		err = -ENOMEM;
6566 		goto done;
6567 	}
6568 	dist.pipe.src = src_btf;
6569 	dist.pipe.dst = new_base;
6570 	dist.pipe.str_off_map = hashmap__new(btf_dedup_identity_hash_fn, btf_dedup_equal_fn, NULL);
6571 	if (IS_ERR(dist.pipe.str_off_map)) {
6572 		err = -ENOMEM;
6573 		goto done;
6574 	}
6575 	dist.split_start_id = btf__type_cnt(old_base);
6576 	dist.split_start_str = old_base->hdr.str_len;
6577 
6578 	/* Pass over src split BTF; generate the list of base BTF type ids it
6579 	 * references; these will constitute our distilled BTF set to be
6580 	 * distributed over base and split BTF as appropriate.
6581 	 */
6582 	for (i = src_btf->start_id; i < n; i++) {
6583 		err = btf_add_distilled_type_ids(&dist, i);
6584 		if (err < 0)
6585 			goto done;
6586 	}
6587 	/* Next add types for each of the required references to base BTF and split BTF
6588 	 * in turn.
6589 	 */
6590 	err = btf_add_distilled_types(&dist);
6591 	if (err < 0)
6592 		goto done;
6593 
6594 	/* Create new split BTF with distilled base BTF as its base; the final
6595 	 * state is split BTF with distilled base BTF that represents enough
6596 	 * about its base references to allow it to be relocated with the base
6597 	 * BTF available.
6598 	 */
6599 	new_split = btf__new_empty_split(new_base);
6600 	if (!new_split) {
6601 		err = -errno;
6602 		goto done;
6603 	}
6604 	dist.pipe.dst = new_split;
6605 	/* First add all split types */
6606 	for (i = src_btf->start_id; i < n; i++) {
6607 		t = btf_type_by_id(src_btf, i);
6608 		err = btf_add_type(&dist.pipe, t);
6609 		if (err < 0)
6610 			goto done;
6611 	}
6612 	/* Now add distilled types to split BTF that are not added to base. */
6613 	err = btf_add_distilled_types(&dist);
6614 	if (err < 0)
6615 		goto done;
6616 
6617 	/* All split BTF ids will be shifted downwards since there are less base
6618 	 * BTF ids in distilled base BTF.
6619 	 */
6620 	dist.diff_id = dist.split_start_id - btf__type_cnt(new_base);
6621 
6622 	n = btf__type_cnt(new_split);
6623 	/* Now update base/split BTF ids. */
6624 	for (i = 1; i < n; i++) {
6625 		err = btf_update_distilled_type_ids(&dist, i);
6626 		if (err < 0)
6627 			break;
6628 	}
6629 done:
6630 	free(dist.id_map);
6631 	hashmap__free(dist.pipe.str_off_map);
6632 	if (err) {
6633 		btf__free(new_split);
6634 		btf__free(new_base);
6635 		return libbpf_err(err);
6636 	}
6637 	*new_base_btf = new_base;
6638 	*new_split_btf = new_split;
6639 
6640 	return 0;
6641 }
6642 
6643 const struct btf_header *btf_header(const struct btf *btf)
6644 {
6645 	return &btf->hdr;
6646 }
6647 
6648 void btf_set_base_btf(struct btf *btf, const struct btf *base_btf)
6649 {
6650 	btf->base_btf = (struct btf *)base_btf;
6651 	btf->start_id = btf__type_cnt(base_btf);
6652 	btf->start_str_off = base_btf->hdr.str_len + base_btf->start_str_off;
6653 }
6654 
6655 int btf__relocate(struct btf *btf, const struct btf *base_btf)
6656 {
6657 	int err = btf_relocate(btf, base_btf, NULL, NULL);
6658 
6659 	if (!err)
6660 		btf->owns_base = false;
6661 	return libbpf_err(err);
6662 }
6663 
6664 struct btf_permute {
6665 	struct btf *btf;
6666 	__u32 *id_map;
6667 	__u32 start_offs;
6668 };
6669 
6670 /* Callback function to remap individual type ID references */
6671 static int btf_permute_remap_type_id(__u32 *type_id, void *ctx)
6672 {
6673 	struct btf_permute *p = ctx;
6674 	__u32 new_id = *type_id;
6675 
6676 	/* refer to the base BTF or VOID type */
6677 	if (new_id < p->btf->start_id)
6678 		return 0;
6679 
6680 	if (new_id >= btf__type_cnt(p->btf))
6681 		return -EINVAL;
6682 
6683 	*type_id = p->id_map[new_id - p->btf->start_id + p->start_offs];
6684 	return 0;
6685 }
6686 
6687 int btf__permute(struct btf *btf, __u32 *id_map, __u32 id_map_cnt,
6688 		 const struct btf_permute_opts *opts)
6689 {
6690 	struct btf_permute p;
6691 	struct btf_ext *btf_ext;
6692 	void *nt, *new_types = NULL;
6693 	__u32 *order_map = NULL;
6694 	int err = 0, i;
6695 	__u32 n, id, start_offs = 0;
6696 
6697 	if (!OPTS_VALID(opts, btf_permute_opts))
6698 		return libbpf_err(-EINVAL);
6699 
6700 	if (btf__base_btf(btf)) {
6701 		n = btf->nr_types;
6702 	} else {
6703 		if (id_map[0] != 0)
6704 			return libbpf_err(-EINVAL);
6705 		n = btf__type_cnt(btf);
6706 		start_offs = 1;
6707 	}
6708 
6709 	if (id_map_cnt != n)
6710 		return libbpf_err(-EINVAL);
6711 
6712 	/* record the sequence of types */
6713 	order_map = calloc(id_map_cnt, sizeof(*id_map));
6714 	if (!order_map) {
6715 		err = -ENOMEM;
6716 		goto done;
6717 	}
6718 
6719 	new_types = calloc(btf->hdr.type_len, 1);
6720 	if (!new_types) {
6721 		err = -ENOMEM;
6722 		goto done;
6723 	}
6724 
6725 	err = btf_ensure_modifiable(btf);
6726 	if (err)
6727 		goto done;
6728 
6729 	for (i = start_offs; i < id_map_cnt; i++) {
6730 		id = id_map[i];
6731 		if (id < btf->start_id || id >= btf__type_cnt(btf)) {
6732 			err = -EINVAL;
6733 			goto done;
6734 		}
6735 		id -= btf->start_id - start_offs;
6736 		/* cannot be mapped to the same ID */
6737 		if (order_map[id]) {
6738 			err = -EINVAL;
6739 			goto done;
6740 		}
6741 		order_map[id] = i + btf->start_id - start_offs;
6742 	}
6743 
6744 	p.btf = btf;
6745 	p.id_map = id_map;
6746 	p.start_offs = start_offs;
6747 	nt = new_types;
6748 	for (i = start_offs; i < id_map_cnt; i++) {
6749 		struct btf_field_iter it;
6750 		const struct btf_type *t;
6751 		__u32 *type_id;
6752 		int type_size;
6753 
6754 		id = order_map[i];
6755 		t = btf__type_by_id(btf, id);
6756 		type_size = btf_type_size(btf, t);
6757 		memcpy(nt, t, type_size);
6758 
6759 		/* fix up referenced IDs for BTF */
6760 		err = btf_field_iter_init(&it, nt, BTF_FIELD_ITER_IDS);
6761 		if (err)
6762 			goto done;
6763 		while ((type_id = btf_field_iter_next(&it))) {
6764 			err = btf_permute_remap_type_id(type_id, &p);
6765 			if (err)
6766 				goto done;
6767 		}
6768 
6769 		nt += type_size;
6770 	}
6771 
6772 	/* fix up referenced IDs for btf_ext */
6773 	btf_ext = OPTS_GET(opts, btf_ext, NULL);
6774 	if (btf_ext) {
6775 		err = btf_ext_visit_type_ids(btf_ext, btf_permute_remap_type_id, &p);
6776 		if (err)
6777 			goto done;
6778 	}
6779 
6780 	for (nt = new_types, i = 0; i < id_map_cnt - start_offs; i++) {
6781 		btf->type_offs[i] = nt - new_types;
6782 		nt += btf_type_size(btf, nt);
6783 	}
6784 
6785 	free(order_map);
6786 	free(btf->types_data);
6787 	btf->types_data = new_types;
6788 	return 0;
6789 
6790 done:
6791 	free(order_map);
6792 	free(new_types);
6793 	return libbpf_err(err);
6794 }
6795