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