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