linux - tools/lib/bpf/btf.c

6376 lines · 167.0 KiB

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