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