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