1
2
3
4#include <endian.h>
5#include <stdio.h>
6#include <stdlib.h>
7#include <string.h>
8#include <fcntl.h>
9#include <unistd.h>
10#include <errno.h>
11#include <linux/err.h>
12#include <linux/btf.h>
13#include <gelf.h>
14#include "btf.h"
15#include "bpf.h"
16#include "libbpf.h"
17#include "libbpf_internal.h"
18#include "hashmap.h"
19
20#define BTF_MAX_NR_TYPES 0x7fffffff
21#define BTF_MAX_STR_OFFSET 0x7fffffff
22
23#define IS_MODIFIER(k) (((k) == BTF_KIND_TYPEDEF) || \
24 ((k) == BTF_KIND_VOLATILE) || \
25 ((k) == BTF_KIND_CONST) || \
26 ((k) == BTF_KIND_RESTRICT))
27
28#define IS_VAR(k) ((k) == BTF_KIND_VAR)
29
30static struct btf_type btf_void;
31
32struct btf {
33 union {
34 struct btf_header *hdr;
35 void *data;
36 };
37 struct btf_type **types;
38 const char *strings;
39 void *nohdr_data;
40 __u32 nr_types;
41 __u32 types_size;
42 __u32 data_size;
43 int fd;
44};
45
46struct btf_ext_info {
47
48
49
50
51 void *info;
52 __u32 rec_size;
53 __u32 len;
54};
55
56struct btf_ext {
57 union {
58 struct btf_ext_header *hdr;
59 void *data;
60 };
61 struct btf_ext_info func_info;
62 struct btf_ext_info line_info;
63 __u32 data_size;
64};
65
66struct btf_ext_info_sec {
67 __u32 sec_name_off;
68 __u32 num_info;
69
70 __u8 data[0];
71};
72
73
74struct bpf_func_info_min {
75 __u32 insn_off;
76 __u32 type_id;
77};
78
79
80struct bpf_line_info_min {
81 __u32 insn_off;
82 __u32 file_name_off;
83 __u32 line_off;
84 __u32 line_col;
85};
86
87static inline __u64 ptr_to_u64(const void *ptr)
88{
89 return (__u64) (unsigned long) ptr;
90}
91
92static int btf_add_type(struct btf *btf, struct btf_type *t)
93{
94 if (btf->types_size - btf->nr_types < 2) {
95 struct btf_type **new_types;
96 __u32 expand_by, new_size;
97
98 if (btf->types_size == BTF_MAX_NR_TYPES)
99 return -E2BIG;
100
101 expand_by = max(btf->types_size >> 2, 16);
102 new_size = min(BTF_MAX_NR_TYPES, btf->types_size + expand_by);
103
104 new_types = realloc(btf->types, sizeof(*new_types) * new_size);
105 if (!new_types)
106 return -ENOMEM;
107
108 if (btf->nr_types == 0)
109 new_types[0] = &btf_void;
110
111 btf->types = new_types;
112 btf->types_size = new_size;
113 }
114
115 btf->types[++(btf->nr_types)] = t;
116
117 return 0;
118}
119
120static int btf_parse_hdr(struct btf *btf)
121{
122 const struct btf_header *hdr = btf->hdr;
123 __u32 meta_left;
124
125 if (btf->data_size < sizeof(struct btf_header)) {
126 pr_debug("BTF header not found\n");
127 return -EINVAL;
128 }
129
130 if (hdr->magic != BTF_MAGIC) {
131 pr_debug("Invalid BTF magic:%x\n", hdr->magic);
132 return -EINVAL;
133 }
134
135 if (hdr->version != BTF_VERSION) {
136 pr_debug("Unsupported BTF version:%u\n", hdr->version);
137 return -ENOTSUP;
138 }
139
140 if (hdr->flags) {
141 pr_debug("Unsupported BTF flags:%x\n", hdr->flags);
142 return -ENOTSUP;
143 }
144
145 meta_left = btf->data_size - sizeof(*hdr);
146 if (!meta_left) {
147 pr_debug("BTF has no data\n");
148 return -EINVAL;
149 }
150
151 if (meta_left < hdr->type_off) {
152 pr_debug("Invalid BTF type section offset:%u\n", hdr->type_off);
153 return -EINVAL;
154 }
155
156 if (meta_left < hdr->str_off) {
157 pr_debug("Invalid BTF string section offset:%u\n", hdr->str_off);
158 return -EINVAL;
159 }
160
161 if (hdr->type_off >= hdr->str_off) {
162 pr_debug("BTF type section offset >= string section offset. No type?\n");
163 return -EINVAL;
164 }
165
166 if (hdr->type_off & 0x02) {
167 pr_debug("BTF type section is not aligned to 4 bytes\n");
168 return -EINVAL;
169 }
170
171 btf->nohdr_data = btf->hdr + 1;
172
173 return 0;
174}
175
176static int btf_parse_str_sec(struct btf *btf)
177{
178 const struct btf_header *hdr = btf->hdr;
179 const char *start = btf->nohdr_data + hdr->str_off;
180 const char *end = start + btf->hdr->str_len;
181
182 if (!hdr->str_len || hdr->str_len - 1 > BTF_MAX_STR_OFFSET ||
183 start[0] || end[-1]) {
184 pr_debug("Invalid BTF string section\n");
185 return -EINVAL;
186 }
187
188 btf->strings = start;
189
190 return 0;
191}
192
193static int btf_type_size(struct btf_type *t)
194{
195 int base_size = sizeof(struct btf_type);
196 __u16 vlen = BTF_INFO_VLEN(t->info);
197
198 switch (BTF_INFO_KIND(t->info)) {
199 case BTF_KIND_FWD:
200 case BTF_KIND_CONST:
201 case BTF_KIND_VOLATILE:
202 case BTF_KIND_RESTRICT:
203 case BTF_KIND_PTR:
204 case BTF_KIND_TYPEDEF:
205 case BTF_KIND_FUNC:
206 return base_size;
207 case BTF_KIND_INT:
208 return base_size + sizeof(__u32);
209 case BTF_KIND_ENUM:
210 return base_size + vlen * sizeof(struct btf_enum);
211 case BTF_KIND_ARRAY:
212 return base_size + sizeof(struct btf_array);
213 case BTF_KIND_STRUCT:
214 case BTF_KIND_UNION:
215 return base_size + vlen * sizeof(struct btf_member);
216 case BTF_KIND_FUNC_PROTO:
217 return base_size + vlen * sizeof(struct btf_param);
218 case BTF_KIND_VAR:
219 return base_size + sizeof(struct btf_var);
220 case BTF_KIND_DATASEC:
221 return base_size + vlen * sizeof(struct btf_var_secinfo);
222 default:
223 pr_debug("Unsupported BTF_KIND:%u\n", BTF_INFO_KIND(t->info));
224 return -EINVAL;
225 }
226}
227
228static int btf_parse_type_sec(struct btf *btf)
229{
230 struct btf_header *hdr = btf->hdr;
231 void *nohdr_data = btf->nohdr_data;
232 void *next_type = nohdr_data + hdr->type_off;
233 void *end_type = nohdr_data + hdr->str_off;
234
235 while (next_type < end_type) {
236 struct btf_type *t = next_type;
237 int type_size;
238 int err;
239
240 type_size = btf_type_size(t);
241 if (type_size < 0)
242 return type_size;
243 next_type += type_size;
244 err = btf_add_type(btf, t);
245 if (err)
246 return err;
247 }
248
249 return 0;
250}
251
252__u32 btf__get_nr_types(const struct btf *btf)
253{
254 return btf->nr_types;
255}
256
257const struct btf_type *btf__type_by_id(const struct btf *btf, __u32 type_id)
258{
259 if (type_id > btf->nr_types)
260 return NULL;
261
262 return btf->types[type_id];
263}
264
265static bool btf_type_is_void(const struct btf_type *t)
266{
267 return t == &btf_void || BTF_INFO_KIND(t->info) == BTF_KIND_FWD;
268}
269
270static bool btf_type_is_void_or_null(const struct btf_type *t)
271{
272 return !t || btf_type_is_void(t);
273}
274
275#define MAX_RESOLVE_DEPTH 32
276
277__s64 btf__resolve_size(const struct btf *btf, __u32 type_id)
278{
279 const struct btf_array *array;
280 const struct btf_type *t;
281 __u32 nelems = 1;
282 __s64 size = -1;
283 int i;
284
285 t = btf__type_by_id(btf, type_id);
286 for (i = 0; i < MAX_RESOLVE_DEPTH && !btf_type_is_void_or_null(t);
287 i++) {
288 switch (BTF_INFO_KIND(t->info)) {
289 case BTF_KIND_INT:
290 case BTF_KIND_STRUCT:
291 case BTF_KIND_UNION:
292 case BTF_KIND_ENUM:
293 case BTF_KIND_DATASEC:
294 size = t->size;
295 goto done;
296 case BTF_KIND_PTR:
297 size = sizeof(void *);
298 goto done;
299 case BTF_KIND_TYPEDEF:
300 case BTF_KIND_VOLATILE:
301 case BTF_KIND_CONST:
302 case BTF_KIND_RESTRICT:
303 case BTF_KIND_VAR:
304 type_id = t->type;
305 break;
306 case BTF_KIND_ARRAY:
307 array = (const struct btf_array *)(t + 1);
308 if (nelems && array->nelems > UINT32_MAX / nelems)
309 return -E2BIG;
310 nelems *= array->nelems;
311 type_id = array->type;
312 break;
313 default:
314 return -EINVAL;
315 }
316
317 t = btf__type_by_id(btf, type_id);
318 }
319
320 if (size < 0)
321 return -EINVAL;
322
323done:
324 if (nelems && size > UINT32_MAX / nelems)
325 return -E2BIG;
326
327 return nelems * size;
328}
329
330int btf__resolve_type(const struct btf *btf, __u32 type_id)
331{
332 const struct btf_type *t;
333 int depth = 0;
334
335 t = btf__type_by_id(btf, type_id);
336 while (depth < MAX_RESOLVE_DEPTH &&
337 !btf_type_is_void_or_null(t) &&
338 (IS_MODIFIER(BTF_INFO_KIND(t->info)) ||
339 IS_VAR(BTF_INFO_KIND(t->info)))) {
340 type_id = t->type;
341 t = btf__type_by_id(btf, type_id);
342 depth++;
343 }
344
345 if (depth == MAX_RESOLVE_DEPTH || btf_type_is_void_or_null(t))
346 return -EINVAL;
347
348 return type_id;
349}
350
351__s32 btf__find_by_name(const struct btf *btf, const char *type_name)
352{
353 __u32 i;
354
355 if (!strcmp(type_name, "void"))
356 return 0;
357
358 for (i = 1; i <= btf->nr_types; i++) {
359 const struct btf_type *t = btf->types[i];
360 const char *name = btf__name_by_offset(btf, t->name_off);
361
362 if (name && !strcmp(type_name, name))
363 return i;
364 }
365
366 return -ENOENT;
367}
368
369void btf__free(struct btf *btf)
370{
371 if (!btf)
372 return;
373
374 if (btf->fd != -1)
375 close(btf->fd);
376
377 free(btf->data);
378 free(btf->types);
379 free(btf);
380}
381
382struct btf *btf__new(__u8 *data, __u32 size)
383{
384 struct btf *btf;
385 int err;
386
387 btf = calloc(1, sizeof(struct btf));
388 if (!btf)
389 return ERR_PTR(-ENOMEM);
390
391 btf->fd = -1;
392
393 btf->data = malloc(size);
394 if (!btf->data) {
395 err = -ENOMEM;
396 goto done;
397 }
398
399 memcpy(btf->data, data, size);
400 btf->data_size = size;
401
402 err = btf_parse_hdr(btf);
403 if (err)
404 goto done;
405
406 err = btf_parse_str_sec(btf);
407 if (err)
408 goto done;
409
410 err = btf_parse_type_sec(btf);
411
412done:
413 if (err) {
414 btf__free(btf);
415 return ERR_PTR(err);
416 }
417
418 return btf;
419}
420
421static bool btf_check_endianness(const GElf_Ehdr *ehdr)
422{
423#if __BYTE_ORDER == __LITTLE_ENDIAN
424 return ehdr->e_ident[EI_DATA] == ELFDATA2LSB;
425#elif __BYTE_ORDER == __BIG_ENDIAN
426 return ehdr->e_ident[EI_DATA] == ELFDATA2MSB;
427#else
428# error "Unrecognized __BYTE_ORDER__"
429#endif
430}
431
432struct btf *btf__parse_elf(const char *path, struct btf_ext **btf_ext)
433{
434 Elf_Data *btf_data = NULL, *btf_ext_data = NULL;
435 int err = 0, fd = -1, idx = 0;
436 struct btf *btf = NULL;
437 Elf_Scn *scn = NULL;
438 Elf *elf = NULL;
439 GElf_Ehdr ehdr;
440
441 if (elf_version(EV_CURRENT) == EV_NONE) {
442 pr_warning("failed to init libelf for %s\n", path);
443 return ERR_PTR(-LIBBPF_ERRNO__LIBELF);
444 }
445
446 fd = open(path, O_RDONLY);
447 if (fd < 0) {
448 err = -errno;
449 pr_warning("failed to open %s: %s\n", path, strerror(errno));
450 return ERR_PTR(err);
451 }
452
453 err = -LIBBPF_ERRNO__FORMAT;
454
455 elf = elf_begin(fd, ELF_C_READ, NULL);
456 if (!elf) {
457 pr_warning("failed to open %s as ELF file\n", path);
458 goto done;
459 }
460 if (!gelf_getehdr(elf, &ehdr)) {
461 pr_warning("failed to get EHDR from %s\n", path);
462 goto done;
463 }
464 if (!btf_check_endianness(&ehdr)) {
465 pr_warning("non-native ELF endianness is not supported\n");
466 goto done;
467 }
468 if (!elf_rawdata(elf_getscn(elf, ehdr.e_shstrndx), NULL)) {
469 pr_warning("failed to get e_shstrndx from %s\n", path);
470 goto done;
471 }
472
473 while ((scn = elf_nextscn(elf, scn)) != NULL) {
474 GElf_Shdr sh;
475 char *name;
476
477 idx++;
478 if (gelf_getshdr(scn, &sh) != &sh) {
479 pr_warning("failed to get section(%d) header from %s\n",
480 idx, path);
481 goto done;
482 }
483 name = elf_strptr(elf, ehdr.e_shstrndx, sh.sh_name);
484 if (!name) {
485 pr_warning("failed to get section(%d) name from %s\n",
486 idx, path);
487 goto done;
488 }
489 if (strcmp(name, BTF_ELF_SEC) == 0) {
490 btf_data = elf_getdata(scn, 0);
491 if (!btf_data) {
492 pr_warning("failed to get section(%d, %s) data from %s\n",
493 idx, name, path);
494 goto done;
495 }
496 continue;
497 } else if (btf_ext && strcmp(name, BTF_EXT_ELF_SEC) == 0) {
498 btf_ext_data = elf_getdata(scn, 0);
499 if (!btf_ext_data) {
500 pr_warning("failed to get section(%d, %s) data from %s\n",
501 idx, name, path);
502 goto done;
503 }
504 continue;
505 }
506 }
507
508 err = 0;
509
510 if (!btf_data) {
511 err = -ENOENT;
512 goto done;
513 }
514 btf = btf__new(btf_data->d_buf, btf_data->d_size);
515 if (IS_ERR(btf))
516 goto done;
517
518 if (btf_ext && btf_ext_data) {
519 *btf_ext = btf_ext__new(btf_ext_data->d_buf,
520 btf_ext_data->d_size);
521 if (IS_ERR(*btf_ext))
522 goto done;
523 } else if (btf_ext) {
524 *btf_ext = NULL;
525 }
526done:
527 if (elf)
528 elf_end(elf);
529 close(fd);
530
531 if (err)
532 return ERR_PTR(err);
533
534
535
536
537 if (IS_ERR(btf))
538 return btf;
539 if (btf_ext && IS_ERR(*btf_ext)) {
540 btf__free(btf);
541 err = PTR_ERR(*btf_ext);
542 return ERR_PTR(err);
543 }
544 return btf;
545}
546
547static int compare_vsi_off(const void *_a, const void *_b)
548{
549 const struct btf_var_secinfo *a = _a;
550 const struct btf_var_secinfo *b = _b;
551
552 return a->offset - b->offset;
553}
554
555static int btf_fixup_datasec(struct bpf_object *obj, struct btf *btf,
556 struct btf_type *t)
557{
558 __u32 size = 0, off = 0, i, vars = BTF_INFO_VLEN(t->info);
559 const char *name = btf__name_by_offset(btf, t->name_off);
560 const struct btf_type *t_var;
561 struct btf_var_secinfo *vsi;
562 struct btf_var *var;
563 int ret;
564
565 if (!name) {
566 pr_debug("No name found in string section for DATASEC kind.\n");
567 return -ENOENT;
568 }
569
570 ret = bpf_object__section_size(obj, name, &size);
571 if (ret || !size || (t->size && t->size != size)) {
572 pr_debug("Invalid size for section %s: %u bytes\n", name, size);
573 return -ENOENT;
574 }
575
576 t->size = size;
577
578 for (i = 0, vsi = (struct btf_var_secinfo *)(t + 1);
579 i < vars; i++, vsi++) {
580 t_var = btf__type_by_id(btf, vsi->type);
581 var = (struct btf_var *)(t_var + 1);
582
583 if (BTF_INFO_KIND(t_var->info) != BTF_KIND_VAR) {
584 pr_debug("Non-VAR type seen in section %s\n", name);
585 return -EINVAL;
586 }
587
588 if (var->linkage == BTF_VAR_STATIC)
589 continue;
590
591 name = btf__name_by_offset(btf, t_var->name_off);
592 if (!name) {
593 pr_debug("No name found in string section for VAR kind\n");
594 return -ENOENT;
595 }
596
597 ret = bpf_object__variable_offset(obj, name, &off);
598 if (ret) {
599 pr_debug("No offset found in symbol table for VAR %s\n", name);
600 return -ENOENT;
601 }
602
603 vsi->offset = off;
604 }
605
606 qsort(t + 1, vars, sizeof(*vsi), compare_vsi_off);
607 return 0;
608}
609
610int btf__finalize_data(struct bpf_object *obj, struct btf *btf)
611{
612 int err = 0;
613 __u32 i;
614
615 for (i = 1; i <= btf->nr_types; i++) {
616 struct btf_type *t = btf->types[i];
617
618
619
620
621
622
623 if (BTF_INFO_KIND(t->info) == BTF_KIND_DATASEC) {
624 err = btf_fixup_datasec(obj, btf, t);
625 if (err)
626 break;
627 }
628 }
629
630 return err;
631}
632
633int btf__load(struct btf *btf)
634{
635 __u32 log_buf_size = BPF_LOG_BUF_SIZE;
636 char *log_buf = NULL;
637 int err = 0;
638
639 if (btf->fd >= 0)
640 return -EEXIST;
641
642 log_buf = malloc(log_buf_size);
643 if (!log_buf)
644 return -ENOMEM;
645
646 *log_buf = 0;
647
648 btf->fd = bpf_load_btf(btf->data, btf->data_size,
649 log_buf, log_buf_size, false);
650 if (btf->fd < 0) {
651 err = -errno;
652 pr_warning("Error loading BTF: %s(%d)\n", strerror(errno), errno);
653 if (*log_buf)
654 pr_warning("%s\n", log_buf);
655 goto done;
656 }
657
658done:
659 free(log_buf);
660 return err;
661}
662
663int btf__fd(const struct btf *btf)
664{
665 return btf->fd;
666}
667
668const void *btf__get_raw_data(const struct btf *btf, __u32 *size)
669{
670 *size = btf->data_size;
671 return btf->data;
672}
673
674const char *btf__name_by_offset(const struct btf *btf, __u32 offset)
675{
676 if (offset < btf->hdr->str_len)
677 return &btf->strings[offset];
678 else
679 return NULL;
680}
681
682int btf__get_from_id(__u32 id, struct btf **btf)
683{
684 struct bpf_btf_info btf_info = { 0 };
685 __u32 len = sizeof(btf_info);
686 __u32 last_size;
687 int btf_fd;
688 void *ptr;
689 int err;
690
691 err = 0;
692 *btf = NULL;
693 btf_fd = bpf_btf_get_fd_by_id(id);
694 if (btf_fd < 0)
695 return 0;
696
697
698
699
700
701 btf_info.btf_size = 4096;
702 last_size = btf_info.btf_size;
703 ptr = malloc(last_size);
704 if (!ptr) {
705 err = -ENOMEM;
706 goto exit_free;
707 }
708
709 memset(ptr, 0, last_size);
710 btf_info.btf = ptr_to_u64(ptr);
711 err = bpf_obj_get_info_by_fd(btf_fd, &btf_info, &len);
712
713 if (!err && btf_info.btf_size > last_size) {
714 void *temp_ptr;
715
716 last_size = btf_info.btf_size;
717 temp_ptr = realloc(ptr, last_size);
718 if (!temp_ptr) {
719 err = -ENOMEM;
720 goto exit_free;
721 }
722 ptr = temp_ptr;
723 memset(ptr, 0, last_size);
724 btf_info.btf = ptr_to_u64(ptr);
725 err = bpf_obj_get_info_by_fd(btf_fd, &btf_info, &len);
726 }
727
728 if (err || btf_info.btf_size > last_size) {
729 err = errno;
730 goto exit_free;
731 }
732
733 *btf = btf__new((__u8 *)(long)btf_info.btf, btf_info.btf_size);
734 if (IS_ERR(*btf)) {
735 err = PTR_ERR(*btf);
736 *btf = NULL;
737 }
738
739exit_free:
740 close(btf_fd);
741 free(ptr);
742
743 return err;
744}
745
746int btf__get_map_kv_tids(const struct btf *btf, const char *map_name,
747 __u32 expected_key_size, __u32 expected_value_size,
748 __u32 *key_type_id, __u32 *value_type_id)
749{
750 const struct btf_type *container_type;
751 const struct btf_member *key, *value;
752 const size_t max_name = 256;
753 char container_name[max_name];
754 __s64 key_size, value_size;
755 __s32 container_id;
756
757 if (snprintf(container_name, max_name, "____btf_map_%s", map_name) ==
758 max_name) {
759 pr_warning("map:%s length of '____btf_map_%s' is too long\n",
760 map_name, map_name);
761 return -EINVAL;
762 }
763
764 container_id = btf__find_by_name(btf, container_name);
765 if (container_id < 0) {
766 pr_debug("map:%s container_name:%s cannot be found in BTF. Missing BPF_ANNOTATE_KV_PAIR?\n",
767 map_name, container_name);
768 return container_id;
769 }
770
771 container_type = btf__type_by_id(btf, container_id);
772 if (!container_type) {
773 pr_warning("map:%s cannot find BTF type for container_id:%u\n",
774 map_name, container_id);
775 return -EINVAL;
776 }
777
778 if (BTF_INFO_KIND(container_type->info) != BTF_KIND_STRUCT ||
779 BTF_INFO_VLEN(container_type->info) < 2) {
780 pr_warning("map:%s container_name:%s is an invalid container struct\n",
781 map_name, container_name);
782 return -EINVAL;
783 }
784
785 key = (struct btf_member *)(container_type + 1);
786 value = key + 1;
787
788 key_size = btf__resolve_size(btf, key->type);
789 if (key_size < 0) {
790 pr_warning("map:%s invalid BTF key_type_size\n", map_name);
791 return key_size;
792 }
793
794 if (expected_key_size != key_size) {
795 pr_warning("map:%s btf_key_type_size:%u != map_def_key_size:%u\n",
796 map_name, (__u32)key_size, expected_key_size);
797 return -EINVAL;
798 }
799
800 value_size = btf__resolve_size(btf, value->type);
801 if (value_size < 0) {
802 pr_warning("map:%s invalid BTF value_type_size\n", map_name);
803 return value_size;
804 }
805
806 if (expected_value_size != value_size) {
807 pr_warning("map:%s btf_value_type_size:%u != map_def_value_size:%u\n",
808 map_name, (__u32)value_size, expected_value_size);
809 return -EINVAL;
810 }
811
812 *key_type_id = key->type;
813 *value_type_id = value->type;
814
815 return 0;
816}
817
818struct btf_ext_sec_setup_param {
819 __u32 off;
820 __u32 len;
821 __u32 min_rec_size;
822 struct btf_ext_info *ext_info;
823 const char *desc;
824};
825
826static int btf_ext_setup_info(struct btf_ext *btf_ext,
827 struct btf_ext_sec_setup_param *ext_sec)
828{
829 const struct btf_ext_info_sec *sinfo;
830 struct btf_ext_info *ext_info;
831 __u32 info_left, record_size;
832
833 void *info;
834
835 if (ext_sec->off & 0x03) {
836 pr_debug(".BTF.ext %s section is not aligned to 4 bytes\n",
837 ext_sec->desc);
838 return -EINVAL;
839 }
840
841 info = btf_ext->data + btf_ext->hdr->hdr_len + ext_sec->off;
842 info_left = ext_sec->len;
843
844 if (btf_ext->data + btf_ext->data_size < info + ext_sec->len) {
845 pr_debug("%s section (off:%u len:%u) is beyond the end of the ELF section .BTF.ext\n",
846 ext_sec->desc, ext_sec->off, ext_sec->len);
847 return -EINVAL;
848 }
849
850
851 if (info_left < sizeof(__u32)) {
852 pr_debug(".BTF.ext %s record size not found\n", ext_sec->desc);
853 return -EINVAL;
854 }
855
856
857 record_size = *(__u32 *)info;
858 if (record_size < ext_sec->min_rec_size ||
859 record_size & 0x03) {
860 pr_debug("%s section in .BTF.ext has invalid record size %u\n",
861 ext_sec->desc, record_size);
862 return -EINVAL;
863 }
864
865 sinfo = info + sizeof(__u32);
866 info_left -= sizeof(__u32);
867
868
869 if (!info_left) {
870 pr_debug("%s section in .BTF.ext has no records", ext_sec->desc);
871 return -EINVAL;
872 }
873
874 while (info_left) {
875 unsigned int sec_hdrlen = sizeof(struct btf_ext_info_sec);
876 __u64 total_record_size;
877 __u32 num_records;
878
879 if (info_left < sec_hdrlen) {
880 pr_debug("%s section header is not found in .BTF.ext\n",
881 ext_sec->desc);
882 return -EINVAL;
883 }
884
885 num_records = sinfo->num_info;
886 if (num_records == 0) {
887 pr_debug("%s section has incorrect num_records in .BTF.ext\n",
888 ext_sec->desc);
889 return -EINVAL;
890 }
891
892 total_record_size = sec_hdrlen +
893 (__u64)num_records * record_size;
894 if (info_left < total_record_size) {
895 pr_debug("%s section has incorrect num_records in .BTF.ext\n",
896 ext_sec->desc);
897 return -EINVAL;
898 }
899
900 info_left -= total_record_size;
901 sinfo = (void *)sinfo + total_record_size;
902 }
903
904 ext_info = ext_sec->ext_info;
905 ext_info->len = ext_sec->len - sizeof(__u32);
906 ext_info->rec_size = record_size;
907 ext_info->info = info + sizeof(__u32);
908
909 return 0;
910}
911
912static int btf_ext_setup_func_info(struct btf_ext *btf_ext)
913{
914 struct btf_ext_sec_setup_param param = {
915 .off = btf_ext->hdr->func_info_off,
916 .len = btf_ext->hdr->func_info_len,
917 .min_rec_size = sizeof(struct bpf_func_info_min),
918 .ext_info = &btf_ext->func_info,
919 .desc = "func_info"
920 };
921
922 return btf_ext_setup_info(btf_ext, ¶m);
923}
924
925static int btf_ext_setup_line_info(struct btf_ext *btf_ext)
926{
927 struct btf_ext_sec_setup_param param = {
928 .off = btf_ext->hdr->line_info_off,
929 .len = btf_ext->hdr->line_info_len,
930 .min_rec_size = sizeof(struct bpf_line_info_min),
931 .ext_info = &btf_ext->line_info,
932 .desc = "line_info",
933 };
934
935 return btf_ext_setup_info(btf_ext, ¶m);
936}
937
938static int btf_ext_parse_hdr(__u8 *data, __u32 data_size)
939{
940 const struct btf_ext_header *hdr = (struct btf_ext_header *)data;
941
942 if (data_size < offsetof(struct btf_ext_header, func_info_off) ||
943 data_size < hdr->hdr_len) {
944 pr_debug("BTF.ext header not found");
945 return -EINVAL;
946 }
947
948 if (hdr->magic != BTF_MAGIC) {
949 pr_debug("Invalid BTF.ext magic:%x\n", hdr->magic);
950 return -EINVAL;
951 }
952
953 if (hdr->version != BTF_VERSION) {
954 pr_debug("Unsupported BTF.ext version:%u\n", hdr->version);
955 return -ENOTSUP;
956 }
957
958 if (hdr->flags) {
959 pr_debug("Unsupported BTF.ext flags:%x\n", hdr->flags);
960 return -ENOTSUP;
961 }
962
963 if (data_size == hdr->hdr_len) {
964 pr_debug("BTF.ext has no data\n");
965 return -EINVAL;
966 }
967
968 return 0;
969}
970
971void btf_ext__free(struct btf_ext *btf_ext)
972{
973 if (!btf_ext)
974 return;
975 free(btf_ext->data);
976 free(btf_ext);
977}
978
979struct btf_ext *btf_ext__new(__u8 *data, __u32 size)
980{
981 struct btf_ext *btf_ext;
982 int err;
983
984 err = btf_ext_parse_hdr(data, size);
985 if (err)
986 return ERR_PTR(err);
987
988 btf_ext = calloc(1, sizeof(struct btf_ext));
989 if (!btf_ext)
990 return ERR_PTR(-ENOMEM);
991
992 btf_ext->data_size = size;
993 btf_ext->data = malloc(size);
994 if (!btf_ext->data) {
995 err = -ENOMEM;
996 goto done;
997 }
998 memcpy(btf_ext->data, data, size);
999
1000 err = btf_ext_setup_func_info(btf_ext);
1001 if (err)
1002 goto done;
1003
1004 err = btf_ext_setup_line_info(btf_ext);
1005 if (err)
1006 goto done;
1007
1008done:
1009 if (err) {
1010 btf_ext__free(btf_ext);
1011 return ERR_PTR(err);
1012 }
1013
1014 return btf_ext;
1015}
1016
1017const void *btf_ext__get_raw_data(const struct btf_ext *btf_ext, __u32 *size)
1018{
1019 *size = btf_ext->data_size;
1020 return btf_ext->data;
1021}
1022
1023static int btf_ext_reloc_info(const struct btf *btf,
1024 const struct btf_ext_info *ext_info,
1025 const char *sec_name, __u32 insns_cnt,
1026 void **info, __u32 *cnt)
1027{
1028 __u32 sec_hdrlen = sizeof(struct btf_ext_info_sec);
1029 __u32 i, record_size, existing_len, records_len;
1030 struct btf_ext_info_sec *sinfo;
1031 const char *info_sec_name;
1032 __u64 remain_len;
1033 void *data;
1034
1035 record_size = ext_info->rec_size;
1036 sinfo = ext_info->info;
1037 remain_len = ext_info->len;
1038 while (remain_len > 0) {
1039 records_len = sinfo->num_info * record_size;
1040 info_sec_name = btf__name_by_offset(btf, sinfo->sec_name_off);
1041 if (strcmp(info_sec_name, sec_name)) {
1042 remain_len -= sec_hdrlen + records_len;
1043 sinfo = (void *)sinfo + sec_hdrlen + records_len;
1044 continue;
1045 }
1046
1047 existing_len = (*cnt) * record_size;
1048 data = realloc(*info, existing_len + records_len);
1049 if (!data)
1050 return -ENOMEM;
1051
1052 memcpy(data + existing_len, sinfo->data, records_len);
1053
1054
1055
1056 for (i = 0; i < sinfo->num_info; i++) {
1057 __u32 *insn_off;
1058
1059 insn_off = data + existing_len + (i * record_size);
1060 *insn_off = *insn_off / sizeof(struct bpf_insn) +
1061 insns_cnt;
1062 }
1063 *info = data;
1064 *cnt += sinfo->num_info;
1065 return 0;
1066 }
1067
1068 return -ENOENT;
1069}
1070
1071int btf_ext__reloc_func_info(const struct btf *btf,
1072 const struct btf_ext *btf_ext,
1073 const char *sec_name, __u32 insns_cnt,
1074 void **func_info, __u32 *cnt)
1075{
1076 return btf_ext_reloc_info(btf, &btf_ext->func_info, sec_name,
1077 insns_cnt, func_info, cnt);
1078}
1079
1080int btf_ext__reloc_line_info(const struct btf *btf,
1081 const struct btf_ext *btf_ext,
1082 const char *sec_name, __u32 insns_cnt,
1083 void **line_info, __u32 *cnt)
1084{
1085 return btf_ext_reloc_info(btf, &btf_ext->line_info, sec_name,
1086 insns_cnt, line_info, cnt);
1087}
1088
1089__u32 btf_ext__func_info_rec_size(const struct btf_ext *btf_ext)
1090{
1091 return btf_ext->func_info.rec_size;
1092}
1093
1094__u32 btf_ext__line_info_rec_size(const struct btf_ext *btf_ext)
1095{
1096 return btf_ext->line_info.rec_size;
1097}
1098
1099struct btf_dedup;
1100
1101static struct btf_dedup *btf_dedup_new(struct btf *btf, struct btf_ext *btf_ext,
1102 const struct btf_dedup_opts *opts);
1103static void btf_dedup_free(struct btf_dedup *d);
1104static int btf_dedup_strings(struct btf_dedup *d);
1105static int btf_dedup_prim_types(struct btf_dedup *d);
1106static int btf_dedup_struct_types(struct btf_dedup *d);
1107static int btf_dedup_ref_types(struct btf_dedup *d);
1108static int btf_dedup_compact_types(struct btf_dedup *d);
1109static int btf_dedup_remap_types(struct btf_dedup *d);
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248int btf__dedup(struct btf *btf, struct btf_ext *btf_ext,
1249 const struct btf_dedup_opts *opts)
1250{
1251 struct btf_dedup *d = btf_dedup_new(btf, btf_ext, opts);
1252 int err;
1253
1254 if (IS_ERR(d)) {
1255 pr_debug("btf_dedup_new failed: %ld", PTR_ERR(d));
1256 return -EINVAL;
1257 }
1258
1259 err = btf_dedup_strings(d);
1260 if (err < 0) {
1261 pr_debug("btf_dedup_strings failed:%d\n", err);
1262 goto done;
1263 }
1264 err = btf_dedup_prim_types(d);
1265 if (err < 0) {
1266 pr_debug("btf_dedup_prim_types failed:%d\n", err);
1267 goto done;
1268 }
1269 err = btf_dedup_struct_types(d);
1270 if (err < 0) {
1271 pr_debug("btf_dedup_struct_types failed:%d\n", err);
1272 goto done;
1273 }
1274 err = btf_dedup_ref_types(d);
1275 if (err < 0) {
1276 pr_debug("btf_dedup_ref_types failed:%d\n", err);
1277 goto done;
1278 }
1279 err = btf_dedup_compact_types(d);
1280 if (err < 0) {
1281 pr_debug("btf_dedup_compact_types failed:%d\n", err);
1282 goto done;
1283 }
1284 err = btf_dedup_remap_types(d);
1285 if (err < 0) {
1286 pr_debug("btf_dedup_remap_types failed:%d\n", err);
1287 goto done;
1288 }
1289
1290done:
1291 btf_dedup_free(d);
1292 return err;
1293}
1294
1295#define BTF_UNPROCESSED_ID ((__u32)-1)
1296#define BTF_IN_PROGRESS_ID ((__u32)-2)
1297
1298struct btf_dedup {
1299
1300 struct btf *btf;
1301
1302
1303
1304
1305 struct btf_ext *btf_ext;
1306
1307
1308
1309
1310
1311
1312
1313 struct hashmap *dedup_table;
1314
1315 __u32 *map;
1316
1317 __u32 *hypot_map;
1318 __u32 *hypot_list;
1319 size_t hypot_cnt;
1320 size_t hypot_cap;
1321
1322 struct btf_dedup_opts opts;
1323};
1324
1325struct btf_str_ptr {
1326 const char *str;
1327 __u32 new_off;
1328 bool used;
1329};
1330
1331struct btf_str_ptrs {
1332 struct btf_str_ptr *ptrs;
1333 const char *data;
1334 __u32 cnt;
1335 __u32 cap;
1336};
1337
1338static long hash_combine(long h, long value)
1339{
1340 return h * 31 + value;
1341}
1342
1343#define for_each_dedup_cand(d, node, hash) \
1344 hashmap__for_each_key_entry(d->dedup_table, node, (void *)hash)
1345
1346static int btf_dedup_table_add(struct btf_dedup *d, long hash, __u32 type_id)
1347{
1348 return hashmap__append(d->dedup_table,
1349 (void *)hash, (void *)(long)type_id);
1350}
1351
1352static int btf_dedup_hypot_map_add(struct btf_dedup *d,
1353 __u32 from_id, __u32 to_id)
1354{
1355 if (d->hypot_cnt == d->hypot_cap) {
1356 __u32 *new_list;
1357
1358 d->hypot_cap += max(16, d->hypot_cap / 2);
1359 new_list = realloc(d->hypot_list, sizeof(__u32) * d->hypot_cap);
1360 if (!new_list)
1361 return -ENOMEM;
1362 d->hypot_list = new_list;
1363 }
1364 d->hypot_list[d->hypot_cnt++] = from_id;
1365 d->hypot_map[from_id] = to_id;
1366 return 0;
1367}
1368
1369static void btf_dedup_clear_hypot_map(struct btf_dedup *d)
1370{
1371 int i;
1372
1373 for (i = 0; i < d->hypot_cnt; i++)
1374 d->hypot_map[d->hypot_list[i]] = BTF_UNPROCESSED_ID;
1375 d->hypot_cnt = 0;
1376}
1377
1378static void btf_dedup_free(struct btf_dedup *d)
1379{
1380 hashmap__free(d->dedup_table);
1381 d->dedup_table = NULL;
1382
1383 free(d->map);
1384 d->map = NULL;
1385
1386 free(d->hypot_map);
1387 d->hypot_map = NULL;
1388
1389 free(d->hypot_list);
1390 d->hypot_list = NULL;
1391
1392 free(d);
1393}
1394
1395static size_t btf_dedup_identity_hash_fn(const void *key, void *ctx)
1396{
1397 return (size_t)key;
1398}
1399
1400static size_t btf_dedup_collision_hash_fn(const void *key, void *ctx)
1401{
1402 return 0;
1403}
1404
1405static bool btf_dedup_equal_fn(const void *k1, const void *k2, void *ctx)
1406{
1407 return k1 == k2;
1408}
1409
1410static struct btf_dedup *btf_dedup_new(struct btf *btf, struct btf_ext *btf_ext,
1411 const struct btf_dedup_opts *opts)
1412{
1413 struct btf_dedup *d = calloc(1, sizeof(struct btf_dedup));
1414 hashmap_hash_fn hash_fn = btf_dedup_identity_hash_fn;
1415 int i, err = 0;
1416
1417 if (!d)
1418 return ERR_PTR(-ENOMEM);
1419
1420 d->opts.dont_resolve_fwds = opts && opts->dont_resolve_fwds;
1421
1422 if (opts && opts->dedup_table_size == 1)
1423 hash_fn = btf_dedup_collision_hash_fn;
1424
1425 d->btf = btf;
1426 d->btf_ext = btf_ext;
1427
1428 d->dedup_table = hashmap__new(hash_fn, btf_dedup_equal_fn, NULL);
1429 if (IS_ERR(d->dedup_table)) {
1430 err = PTR_ERR(d->dedup_table);
1431 d->dedup_table = NULL;
1432 goto done;
1433 }
1434
1435 d->map = malloc(sizeof(__u32) * (1 + btf->nr_types));
1436 if (!d->map) {
1437 err = -ENOMEM;
1438 goto done;
1439 }
1440
1441 d->map[0] = 0;
1442 for (i = 1; i <= btf->nr_types; i++) {
1443 struct btf_type *t = d->btf->types[i];
1444 __u16 kind = BTF_INFO_KIND(t->info);
1445
1446
1447 if (kind == BTF_KIND_VAR || kind == BTF_KIND_DATASEC)
1448 d->map[i] = i;
1449 else
1450 d->map[i] = BTF_UNPROCESSED_ID;
1451 }
1452
1453 d->hypot_map = malloc(sizeof(__u32) * (1 + btf->nr_types));
1454 if (!d->hypot_map) {
1455 err = -ENOMEM;
1456 goto done;
1457 }
1458 for (i = 0; i <= btf->nr_types; i++)
1459 d->hypot_map[i] = BTF_UNPROCESSED_ID;
1460
1461done:
1462 if (err) {
1463 btf_dedup_free(d);
1464 return ERR_PTR(err);
1465 }
1466
1467 return d;
1468}
1469
1470typedef int (*str_off_fn_t)(__u32 *str_off_ptr, void *ctx);
1471
1472
1473
1474
1475
1476static int btf_for_each_str_off(struct btf_dedup *d, str_off_fn_t fn, void *ctx)
1477{
1478 void *line_data_cur, *line_data_end;
1479 int i, j, r, rec_size;
1480 struct btf_type *t;
1481
1482 for (i = 1; i <= d->btf->nr_types; i++) {
1483 t = d->btf->types[i];
1484 r = fn(&t->name_off, ctx);
1485 if (r)
1486 return r;
1487
1488 switch (BTF_INFO_KIND(t->info)) {
1489 case BTF_KIND_STRUCT:
1490 case BTF_KIND_UNION: {
1491 struct btf_member *m = (struct btf_member *)(t + 1);
1492 __u16 vlen = BTF_INFO_VLEN(t->info);
1493
1494 for (j = 0; j < vlen; j++) {
1495 r = fn(&m->name_off, ctx);
1496 if (r)
1497 return r;
1498 m++;
1499 }
1500 break;
1501 }
1502 case BTF_KIND_ENUM: {
1503 struct btf_enum *m = (struct btf_enum *)(t + 1);
1504 __u16 vlen = BTF_INFO_VLEN(t->info);
1505
1506 for (j = 0; j < vlen; j++) {
1507 r = fn(&m->name_off, ctx);
1508 if (r)
1509 return r;
1510 m++;
1511 }
1512 break;
1513 }
1514 case BTF_KIND_FUNC_PROTO: {
1515 struct btf_param *m = (struct btf_param *)(t + 1);
1516 __u16 vlen = BTF_INFO_VLEN(t->info);
1517
1518 for (j = 0; j < vlen; j++) {
1519 r = fn(&m->name_off, ctx);
1520 if (r)
1521 return r;
1522 m++;
1523 }
1524 break;
1525 }
1526 default:
1527 break;
1528 }
1529 }
1530
1531 if (!d->btf_ext)
1532 return 0;
1533
1534 line_data_cur = d->btf_ext->line_info.info;
1535 line_data_end = d->btf_ext->line_info.info + d->btf_ext->line_info.len;
1536 rec_size = d->btf_ext->line_info.rec_size;
1537
1538 while (line_data_cur < line_data_end) {
1539 struct btf_ext_info_sec *sec = line_data_cur;
1540 struct bpf_line_info_min *line_info;
1541 __u32 num_info = sec->num_info;
1542
1543 r = fn(&sec->sec_name_off, ctx);
1544 if (r)
1545 return r;
1546
1547 line_data_cur += sizeof(struct btf_ext_info_sec);
1548 for (i = 0; i < num_info; i++) {
1549 line_info = line_data_cur;
1550 r = fn(&line_info->file_name_off, ctx);
1551 if (r)
1552 return r;
1553 r = fn(&line_info->line_off, ctx);
1554 if (r)
1555 return r;
1556 line_data_cur += rec_size;
1557 }
1558 }
1559
1560 return 0;
1561}
1562
1563static int str_sort_by_content(const void *a1, const void *a2)
1564{
1565 const struct btf_str_ptr *p1 = a1;
1566 const struct btf_str_ptr *p2 = a2;
1567
1568 return strcmp(p1->str, p2->str);
1569}
1570
1571static int str_sort_by_offset(const void *a1, const void *a2)
1572{
1573 const struct btf_str_ptr *p1 = a1;
1574 const struct btf_str_ptr *p2 = a2;
1575
1576 if (p1->str != p2->str)
1577 return p1->str < p2->str ? -1 : 1;
1578 return 0;
1579}
1580
1581static int btf_dedup_str_ptr_cmp(const void *str_ptr, const void *pelem)
1582{
1583 const struct btf_str_ptr *p = pelem;
1584
1585 if (str_ptr != p->str)
1586 return (const char *)str_ptr < p->str ? -1 : 1;
1587 return 0;
1588}
1589
1590static int btf_str_mark_as_used(__u32 *str_off_ptr, void *ctx)
1591{
1592 struct btf_str_ptrs *strs;
1593 struct btf_str_ptr *s;
1594
1595 if (*str_off_ptr == 0)
1596 return 0;
1597
1598 strs = ctx;
1599 s = bsearch(strs->data + *str_off_ptr, strs->ptrs, strs->cnt,
1600 sizeof(struct btf_str_ptr), btf_dedup_str_ptr_cmp);
1601 if (!s)
1602 return -EINVAL;
1603 s->used = true;
1604 return 0;
1605}
1606
1607static int btf_str_remap_offset(__u32 *str_off_ptr, void *ctx)
1608{
1609 struct btf_str_ptrs *strs;
1610 struct btf_str_ptr *s;
1611
1612 if (*str_off_ptr == 0)
1613 return 0;
1614
1615 strs = ctx;
1616 s = bsearch(strs->data + *str_off_ptr, strs->ptrs, strs->cnt,
1617 sizeof(struct btf_str_ptr), btf_dedup_str_ptr_cmp);
1618 if (!s)
1619 return -EINVAL;
1620 *str_off_ptr = s->new_off;
1621 return 0;
1622}
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635static int btf_dedup_strings(struct btf_dedup *d)
1636{
1637 const struct btf_header *hdr = d->btf->hdr;
1638 char *start = (char *)d->btf->nohdr_data + hdr->str_off;
1639 char *end = start + d->btf->hdr->str_len;
1640 char *p = start, *tmp_strs = NULL;
1641 struct btf_str_ptrs strs = {
1642 .cnt = 0,
1643 .cap = 0,
1644 .ptrs = NULL,
1645 .data = start,
1646 };
1647 int i, j, err = 0, grp_idx;
1648 bool grp_used;
1649
1650
1651 while (p < end) {
1652 if (strs.cnt + 1 > strs.cap) {
1653 struct btf_str_ptr *new_ptrs;
1654
1655 strs.cap += max(strs.cnt / 2, 16);
1656 new_ptrs = realloc(strs.ptrs,
1657 sizeof(strs.ptrs[0]) * strs.cap);
1658 if (!new_ptrs) {
1659 err = -ENOMEM;
1660 goto done;
1661 }
1662 strs.ptrs = new_ptrs;
1663 }
1664
1665 strs.ptrs[strs.cnt].str = p;
1666 strs.ptrs[strs.cnt].used = false;
1667
1668 p += strlen(p) + 1;
1669 strs.cnt++;
1670 }
1671
1672
1673 tmp_strs = malloc(d->btf->hdr->str_len);
1674 if (!tmp_strs) {
1675 err = -ENOMEM;
1676 goto done;
1677 }
1678
1679
1680 strs.ptrs[0].used = true;
1681 err = btf_for_each_str_off(d, btf_str_mark_as_used, &strs);
1682 if (err)
1683 goto done;
1684
1685
1686 qsort(strs.ptrs, strs.cnt, sizeof(strs.ptrs[0]), str_sort_by_content);
1687
1688
1689
1690
1691
1692 p = tmp_strs;
1693 grp_idx = 0;
1694 grp_used = strs.ptrs[0].used;
1695
1696 for (i = 1; i <= strs.cnt; i++) {
1697
1698
1699
1700
1701
1702 if (i < strs.cnt &&
1703 !strcmp(strs.ptrs[i].str, strs.ptrs[grp_idx].str)) {
1704 grp_used = grp_used || strs.ptrs[i].used;
1705 continue;
1706 }
1707
1708
1709
1710
1711
1712
1713 if (grp_used) {
1714 int new_off = p - tmp_strs;
1715 __u32 len = strlen(strs.ptrs[grp_idx].str);
1716
1717 memmove(p, strs.ptrs[grp_idx].str, len + 1);
1718 for (j = grp_idx; j < i; j++)
1719 strs.ptrs[j].new_off = new_off;
1720 p += len + 1;
1721 }
1722
1723 if (i < strs.cnt) {
1724 grp_idx = i;
1725 grp_used = strs.ptrs[i].used;
1726 }
1727 }
1728
1729
1730 d->btf->hdr->str_len = p - tmp_strs;
1731 memmove(start, tmp_strs, d->btf->hdr->str_len);
1732 end = start + d->btf->hdr->str_len;
1733
1734
1735 qsort(strs.ptrs, strs.cnt, sizeof(strs.ptrs[0]), str_sort_by_offset);
1736
1737
1738 err = btf_for_each_str_off(d, btf_str_remap_offset, &strs);
1739 if (err)
1740 goto done;
1741
1742 d->btf->hdr->str_len = end - start;
1743
1744done:
1745 free(tmp_strs);
1746 free(strs.ptrs);
1747 return err;
1748}
1749
1750static long btf_hash_common(struct btf_type *t)
1751{
1752 long h;
1753
1754 h = hash_combine(0, t->name_off);
1755 h = hash_combine(h, t->info);
1756 h = hash_combine(h, t->size);
1757 return h;
1758}
1759
1760static bool btf_equal_common(struct btf_type *t1, struct btf_type *t2)
1761{
1762 return t1->name_off == t2->name_off &&
1763 t1->info == t2->info &&
1764 t1->size == t2->size;
1765}
1766
1767
1768static long btf_hash_int(struct btf_type *t)
1769{
1770 __u32 info = *(__u32 *)(t + 1);
1771 long h;
1772
1773 h = btf_hash_common(t);
1774 h = hash_combine(h, info);
1775 return h;
1776}
1777
1778
1779static bool btf_equal_int(struct btf_type *t1, struct btf_type *t2)
1780{
1781 __u32 info1, info2;
1782
1783 if (!btf_equal_common(t1, t2))
1784 return false;
1785 info1 = *(__u32 *)(t1 + 1);
1786 info2 = *(__u32 *)(t2 + 1);
1787 return info1 == info2;
1788}
1789
1790
1791static long btf_hash_enum(struct btf_type *t)
1792{
1793 long h;
1794
1795
1796 h = hash_combine(0, t->name_off);
1797 h = hash_combine(h, t->info & ~0xffff);
1798 h = hash_combine(h, t->size);
1799 return h;
1800}
1801
1802
1803static bool btf_equal_enum(struct btf_type *t1, struct btf_type *t2)
1804{
1805 struct btf_enum *m1, *m2;
1806 __u16 vlen;
1807 int i;
1808
1809 if (!btf_equal_common(t1, t2))
1810 return false;
1811
1812 vlen = BTF_INFO_VLEN(t1->info);
1813 m1 = (struct btf_enum *)(t1 + 1);
1814 m2 = (struct btf_enum *)(t2 + 1);
1815 for (i = 0; i < vlen; i++) {
1816 if (m1->name_off != m2->name_off || m1->val != m2->val)
1817 return false;
1818 m1++;
1819 m2++;
1820 }
1821 return true;
1822}
1823
1824static inline bool btf_is_enum_fwd(struct btf_type *t)
1825{
1826 return BTF_INFO_KIND(t->info) == BTF_KIND_ENUM &&
1827 BTF_INFO_VLEN(t->info) == 0;
1828}
1829
1830static bool btf_compat_enum(struct btf_type *t1, struct btf_type *t2)
1831{
1832 if (!btf_is_enum_fwd(t1) && !btf_is_enum_fwd(t2))
1833 return btf_equal_enum(t1, t2);
1834
1835 return t1->name_off == t2->name_off &&
1836 (t1->info & ~0xffff) == (t2->info & ~0xffff) &&
1837 t1->size == t2->size;
1838}
1839
1840
1841
1842
1843
1844
1845static long btf_hash_struct(struct btf_type *t)
1846{
1847 struct btf_member *member = (struct btf_member *)(t + 1);
1848 __u32 vlen = BTF_INFO_VLEN(t->info);
1849 long h = btf_hash_common(t);
1850 int i;
1851
1852 for (i = 0; i < vlen; i++) {
1853 h = hash_combine(h, member->name_off);
1854 h = hash_combine(h, member->offset);
1855
1856 member++;
1857 }
1858 return h;
1859}
1860
1861
1862
1863
1864
1865
1866static bool btf_shallow_equal_struct(struct btf_type *t1, struct btf_type *t2)
1867{
1868 struct btf_member *m1, *m2;
1869 __u16 vlen;
1870 int i;
1871
1872 if (!btf_equal_common(t1, t2))
1873 return false;
1874
1875 vlen = BTF_INFO_VLEN(t1->info);
1876 m1 = (struct btf_member *)(t1 + 1);
1877 m2 = (struct btf_member *)(t2 + 1);
1878 for (i = 0; i < vlen; i++) {
1879 if (m1->name_off != m2->name_off || m1->offset != m2->offset)
1880 return false;
1881 m1++;
1882 m2++;
1883 }
1884 return true;
1885}
1886
1887
1888
1889
1890
1891
1892static long btf_hash_array(struct btf_type *t)
1893{
1894 struct btf_array *info = (struct btf_array *)(t + 1);
1895 long h = btf_hash_common(t);
1896
1897 h = hash_combine(h, info->type);
1898 h = hash_combine(h, info->index_type);
1899 h = hash_combine(h, info->nelems);
1900 return h;
1901}
1902
1903
1904
1905
1906
1907
1908
1909
1910static bool btf_equal_array(struct btf_type *t1, struct btf_type *t2)
1911{
1912 struct btf_array *info1, *info2;
1913
1914 if (!btf_equal_common(t1, t2))
1915 return false;
1916
1917 info1 = (struct btf_array *)(t1 + 1);
1918 info2 = (struct btf_array *)(t2 + 1);
1919 return info1->type == info2->type &&
1920 info1->index_type == info2->index_type &&
1921 info1->nelems == info2->nelems;
1922}
1923
1924
1925
1926
1927
1928
1929static bool btf_compat_array(struct btf_type *t1, struct btf_type *t2)
1930{
1931 struct btf_array *info1, *info2;
1932
1933 if (!btf_equal_common(t1, t2))
1934 return false;
1935
1936 info1 = (struct btf_array *)(t1 + 1);
1937 info2 = (struct btf_array *)(t2 + 1);
1938 return info1->nelems == info2->nelems;
1939}
1940
1941
1942
1943
1944
1945
1946static long btf_hash_fnproto(struct btf_type *t)
1947{
1948 struct btf_param *member = (struct btf_param *)(t + 1);
1949 __u16 vlen = BTF_INFO_VLEN(t->info);
1950 long h = btf_hash_common(t);
1951 int i;
1952
1953 for (i = 0; i < vlen; i++) {
1954 h = hash_combine(h, member->name_off);
1955 h = hash_combine(h, member->type);
1956 member++;
1957 }
1958 return h;
1959}
1960
1961
1962
1963
1964
1965
1966
1967
1968static bool btf_equal_fnproto(struct btf_type *t1, struct btf_type *t2)
1969{
1970 struct btf_param *m1, *m2;
1971 __u16 vlen;
1972 int i;
1973
1974 if (!btf_equal_common(t1, t2))
1975 return false;
1976
1977 vlen = BTF_INFO_VLEN(t1->info);
1978 m1 = (struct btf_param *)(t1 + 1);
1979 m2 = (struct btf_param *)(t2 + 1);
1980 for (i = 0; i < vlen; i++) {
1981 if (m1->name_off != m2->name_off || m1->type != m2->type)
1982 return false;
1983 m1++;
1984 m2++;
1985 }
1986 return true;
1987}
1988
1989
1990
1991
1992
1993
1994static bool btf_compat_fnproto(struct btf_type *t1, struct btf_type *t2)
1995{
1996 struct btf_param *m1, *m2;
1997 __u16 vlen;
1998 int i;
1999
2000
2001 if (t1->name_off != t2->name_off || t1->info != t2->info)
2002 return false;
2003
2004 vlen = BTF_INFO_VLEN(t1->info);
2005 m1 = (struct btf_param *)(t1 + 1);
2006 m2 = (struct btf_param *)(t2 + 1);
2007 for (i = 0; i < vlen; i++) {
2008 if (m1->name_off != m2->name_off)
2009 return false;
2010 m1++;
2011 m2++;
2012 }
2013 return true;
2014}
2015
2016
2017
2018
2019
2020
2021
2022static int btf_dedup_prim_type(struct btf_dedup *d, __u32 type_id)
2023{
2024 struct btf_type *t = d->btf->types[type_id];
2025 struct hashmap_entry *hash_entry;
2026 struct btf_type *cand;
2027
2028 __u32 new_id = type_id;
2029 __u32 cand_id;
2030 long h;
2031
2032 switch (BTF_INFO_KIND(t->info)) {
2033 case BTF_KIND_CONST:
2034 case BTF_KIND_VOLATILE:
2035 case BTF_KIND_RESTRICT:
2036 case BTF_KIND_PTR:
2037 case BTF_KIND_TYPEDEF:
2038 case BTF_KIND_ARRAY:
2039 case BTF_KIND_STRUCT:
2040 case BTF_KIND_UNION:
2041 case BTF_KIND_FUNC:
2042 case BTF_KIND_FUNC_PROTO:
2043 case BTF_KIND_VAR:
2044 case BTF_KIND_DATASEC:
2045 return 0;
2046
2047 case BTF_KIND_INT:
2048 h = btf_hash_int(t);
2049 for_each_dedup_cand(d, hash_entry, h) {
2050 cand_id = (__u32)(long)hash_entry->value;
2051 cand = d->btf->types[cand_id];
2052 if (btf_equal_int(t, cand)) {
2053 new_id = cand_id;
2054 break;
2055 }
2056 }
2057 break;
2058
2059 case BTF_KIND_ENUM:
2060 h = btf_hash_enum(t);
2061 for_each_dedup_cand(d, hash_entry, h) {
2062 cand_id = (__u32)(long)hash_entry->value;
2063 cand = d->btf->types[cand_id];
2064 if (btf_equal_enum(t, cand)) {
2065 new_id = cand_id;
2066 break;
2067 }
2068 if (d->opts.dont_resolve_fwds)
2069 continue;
2070 if (btf_compat_enum(t, cand)) {
2071 if (btf_is_enum_fwd(t)) {
2072
2073 new_id = cand_id;
2074 break;
2075 }
2076
2077 d->map[cand_id] = type_id;
2078 }
2079 }
2080 break;
2081
2082 case BTF_KIND_FWD:
2083 h = btf_hash_common(t);
2084 for_each_dedup_cand(d, hash_entry, h) {
2085 cand_id = (__u32)(long)hash_entry->value;
2086 cand = d->btf->types[cand_id];
2087 if (btf_equal_common(t, cand)) {
2088 new_id = cand_id;
2089 break;
2090 }
2091 }
2092 break;
2093
2094 default:
2095 return -EINVAL;
2096 }
2097
2098 d->map[type_id] = new_id;
2099 if (type_id == new_id && btf_dedup_table_add(d, h, type_id))
2100 return -ENOMEM;
2101
2102 return 0;
2103}
2104
2105static int btf_dedup_prim_types(struct btf_dedup *d)
2106{
2107 int i, err;
2108
2109 for (i = 1; i <= d->btf->nr_types; i++) {
2110 err = btf_dedup_prim_type(d, i);
2111 if (err)
2112 return err;
2113 }
2114 return 0;
2115}
2116
2117
2118
2119
2120static inline bool is_type_mapped(struct btf_dedup *d, uint32_t type_id)
2121{
2122 return d->map[type_id] <= BTF_MAX_NR_TYPES;
2123}
2124
2125
2126
2127
2128
2129
2130static inline __u32 resolve_type_id(struct btf_dedup *d, __u32 type_id)
2131{
2132 while (is_type_mapped(d, type_id) && d->map[type_id] != type_id)
2133 type_id = d->map[type_id];
2134 return type_id;
2135}
2136
2137
2138
2139
2140
2141static uint32_t resolve_fwd_id(struct btf_dedup *d, uint32_t type_id)
2142{
2143 __u32 orig_type_id = type_id;
2144
2145 if (BTF_INFO_KIND(d->btf->types[type_id]->info) != BTF_KIND_FWD)
2146 return type_id;
2147
2148 while (is_type_mapped(d, type_id) && d->map[type_id] != type_id)
2149 type_id = d->map[type_id];
2150
2151 if (BTF_INFO_KIND(d->btf->types[type_id]->info) != BTF_KIND_FWD)
2152 return type_id;
2153
2154 return orig_type_id;
2155}
2156
2157
2158static inline __u16 btf_fwd_kind(struct btf_type *t)
2159{
2160 return BTF_INFO_KFLAG(t->info) ? BTF_KIND_UNION : BTF_KIND_STRUCT;
2161}
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187
2188
2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209
2210
2211
2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223
2224
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
2240
2241
2242
2243
2244
2245
2246
2247
2248
2249
2250
2251
2252
2253
2254
2255
2256static int btf_dedup_is_equiv(struct btf_dedup *d, __u32 cand_id,
2257 __u32 canon_id)
2258{
2259 struct btf_type *cand_type;
2260 struct btf_type *canon_type;
2261 __u32 hypot_type_id;
2262 __u16 cand_kind;
2263 __u16 canon_kind;
2264 int i, eq;
2265
2266
2267 if (resolve_type_id(d, cand_id) == resolve_type_id(d, canon_id))
2268 return 1;
2269
2270 canon_id = resolve_fwd_id(d, canon_id);
2271
2272 hypot_type_id = d->hypot_map[canon_id];
2273 if (hypot_type_id <= BTF_MAX_NR_TYPES)
2274 return hypot_type_id == cand_id;
2275
2276 if (btf_dedup_hypot_map_add(d, canon_id, cand_id))
2277 return -ENOMEM;
2278
2279 cand_type = d->btf->types[cand_id];
2280 canon_type = d->btf->types[canon_id];
2281 cand_kind = BTF_INFO_KIND(cand_type->info);
2282 canon_kind = BTF_INFO_KIND(canon_type->info);
2283
2284 if (cand_type->name_off != canon_type->name_off)
2285 return 0;
2286
2287
2288 if (!d->opts.dont_resolve_fwds
2289 && (cand_kind == BTF_KIND_FWD || canon_kind == BTF_KIND_FWD)
2290 && cand_kind != canon_kind) {
2291 __u16 real_kind;
2292 __u16 fwd_kind;
2293
2294 if (cand_kind == BTF_KIND_FWD) {
2295 real_kind = canon_kind;
2296 fwd_kind = btf_fwd_kind(cand_type);
2297 } else {
2298 real_kind = cand_kind;
2299 fwd_kind = btf_fwd_kind(canon_type);
2300 }
2301 return fwd_kind == real_kind;
2302 }
2303
2304 if (cand_kind != canon_kind)
2305 return 0;
2306
2307 switch (cand_kind) {
2308 case BTF_KIND_INT:
2309 return btf_equal_int(cand_type, canon_type);
2310
2311 case BTF_KIND_ENUM:
2312 if (d->opts.dont_resolve_fwds)
2313 return btf_equal_enum(cand_type, canon_type);
2314 else
2315 return btf_compat_enum(cand_type, canon_type);
2316
2317 case BTF_KIND_FWD:
2318 return btf_equal_common(cand_type, canon_type);
2319
2320 case BTF_KIND_CONST:
2321 case BTF_KIND_VOLATILE:
2322 case BTF_KIND_RESTRICT:
2323 case BTF_KIND_PTR:
2324 case BTF_KIND_TYPEDEF:
2325 case BTF_KIND_FUNC:
2326 if (cand_type->info != canon_type->info)
2327 return 0;
2328 return btf_dedup_is_equiv(d, cand_type->type, canon_type->type);
2329
2330 case BTF_KIND_ARRAY: {
2331 struct btf_array *cand_arr, *canon_arr;
2332
2333 if (!btf_compat_array(cand_type, canon_type))
2334 return 0;
2335 cand_arr = (struct btf_array *)(cand_type + 1);
2336 canon_arr = (struct btf_array *)(canon_type + 1);
2337 eq = btf_dedup_is_equiv(d,
2338 cand_arr->index_type, canon_arr->index_type);
2339 if (eq <= 0)
2340 return eq;
2341 return btf_dedup_is_equiv(d, cand_arr->type, canon_arr->type);
2342 }
2343
2344 case BTF_KIND_STRUCT:
2345 case BTF_KIND_UNION: {
2346 struct btf_member *cand_m, *canon_m;
2347 __u16 vlen;
2348
2349 if (!btf_shallow_equal_struct(cand_type, canon_type))
2350 return 0;
2351 vlen = BTF_INFO_VLEN(cand_type->info);
2352 cand_m = (struct btf_member *)(cand_type + 1);
2353 canon_m = (struct btf_member *)(canon_type + 1);
2354 for (i = 0; i < vlen; i++) {
2355 eq = btf_dedup_is_equiv(d, cand_m->type, canon_m->type);
2356 if (eq <= 0)
2357 return eq;
2358 cand_m++;
2359 canon_m++;
2360 }
2361
2362 return 1;
2363 }
2364
2365 case BTF_KIND_FUNC_PROTO: {
2366 struct btf_param *cand_p, *canon_p;
2367 __u16 vlen;
2368
2369 if (!btf_compat_fnproto(cand_type, canon_type))
2370 return 0;
2371 eq = btf_dedup_is_equiv(d, cand_type->type, canon_type->type);
2372 if (eq <= 0)
2373 return eq;
2374 vlen = BTF_INFO_VLEN(cand_type->info);
2375 cand_p = (struct btf_param *)(cand_type + 1);
2376 canon_p = (struct btf_param *)(canon_type + 1);
2377 for (i = 0; i < vlen; i++) {
2378 eq = btf_dedup_is_equiv(d, cand_p->type, canon_p->type);
2379 if (eq <= 0)
2380 return eq;
2381 cand_p++;
2382 canon_p++;
2383 }
2384 return 1;
2385 }
2386
2387 default:
2388 return -EINVAL;
2389 }
2390 return 0;
2391}
2392
2393
2394
2395
2396
2397
2398
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
2414
2415
2416
2417
2418
2419static void btf_dedup_merge_hypot_map(struct btf_dedup *d)
2420{
2421 __u32 cand_type_id, targ_type_id;
2422 __u16 t_kind, c_kind;
2423 __u32 t_id, c_id;
2424 int i;
2425
2426 for (i = 0; i < d->hypot_cnt; i++) {
2427 cand_type_id = d->hypot_list[i];
2428 targ_type_id = d->hypot_map[cand_type_id];
2429 t_id = resolve_type_id(d, targ_type_id);
2430 c_id = resolve_type_id(d, cand_type_id);
2431 t_kind = BTF_INFO_KIND(d->btf->types[t_id]->info);
2432 c_kind = BTF_INFO_KIND(d->btf->types[c_id]->info);
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
2444
2445 if (t_kind != BTF_KIND_FWD && c_kind == BTF_KIND_FWD)
2446 d->map[c_id] = t_id;
2447 else if (t_kind == BTF_KIND_FWD && c_kind != BTF_KIND_FWD)
2448 d->map[t_id] = c_id;
2449
2450 if ((t_kind == BTF_KIND_STRUCT || t_kind == BTF_KIND_UNION) &&
2451 c_kind != BTF_KIND_FWD &&
2452 is_type_mapped(d, c_id) &&
2453 !is_type_mapped(d, t_id)) {
2454
2455
2456
2457
2458
2459
2460 d->map[t_id] = c_id;
2461 }
2462 }
2463}
2464
2465
2466
2467
2468
2469
2470
2471
2472
2473
2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485
2486
2487static int btf_dedup_struct_type(struct btf_dedup *d, __u32 type_id)
2488{
2489 struct btf_type *cand_type, *t;
2490 struct hashmap_entry *hash_entry;
2491
2492 __u32 new_id = type_id;
2493 __u16 kind;
2494 long h;
2495
2496
2497 if (d->map[type_id] <= BTF_MAX_NR_TYPES)
2498 return 0;
2499
2500 t = d->btf->types[type_id];
2501 kind = BTF_INFO_KIND(t->info);
2502
2503 if (kind != BTF_KIND_STRUCT && kind != BTF_KIND_UNION)
2504 return 0;
2505
2506 h = btf_hash_struct(t);
2507 for_each_dedup_cand(d, hash_entry, h) {
2508 __u32 cand_id = (__u32)(long)hash_entry->value;
2509 int eq;
2510
2511
2512
2513
2514
2515
2516
2517
2518
2519
2520
2521 cand_type = d->btf->types[cand_id];
2522 if (!btf_shallow_equal_struct(t, cand_type))
2523 continue;
2524
2525 btf_dedup_clear_hypot_map(d);
2526 eq = btf_dedup_is_equiv(d, type_id, cand_id);
2527 if (eq < 0)
2528 return eq;
2529 if (!eq)
2530 continue;
2531 new_id = cand_id;
2532 btf_dedup_merge_hypot_map(d);
2533 break;
2534 }
2535
2536 d->map[type_id] = new_id;
2537 if (type_id == new_id && btf_dedup_table_add(d, h, type_id))
2538 return -ENOMEM;
2539
2540 return 0;
2541}
2542
2543static int btf_dedup_struct_types(struct btf_dedup *d)
2544{
2545 int i, err;
2546
2547 for (i = 1; i <= d->btf->nr_types; i++) {
2548 err = btf_dedup_struct_type(d, i);
2549 if (err)
2550 return err;
2551 }
2552 return 0;
2553}
2554
2555
2556
2557
2558
2559
2560
2561
2562
2563
2564
2565
2566
2567
2568
2569
2570
2571
2572
2573
2574
2575
2576
2577
2578
2579static int btf_dedup_ref_type(struct btf_dedup *d, __u32 type_id)
2580{
2581 struct hashmap_entry *hash_entry;
2582 __u32 new_id = type_id, cand_id;
2583 struct btf_type *t, *cand;
2584
2585 int ref_type_id;
2586 long h;
2587
2588 if (d->map[type_id] == BTF_IN_PROGRESS_ID)
2589 return -ELOOP;
2590 if (d->map[type_id] <= BTF_MAX_NR_TYPES)
2591 return resolve_type_id(d, type_id);
2592
2593 t = d->btf->types[type_id];
2594 d->map[type_id] = BTF_IN_PROGRESS_ID;
2595
2596 switch (BTF_INFO_KIND(t->info)) {
2597 case BTF_KIND_CONST:
2598 case BTF_KIND_VOLATILE:
2599 case BTF_KIND_RESTRICT:
2600 case BTF_KIND_PTR:
2601 case BTF_KIND_TYPEDEF:
2602 case BTF_KIND_FUNC:
2603 ref_type_id = btf_dedup_ref_type(d, t->type);
2604 if (ref_type_id < 0)
2605 return ref_type_id;
2606 t->type = ref_type_id;
2607
2608 h = btf_hash_common(t);
2609 for_each_dedup_cand(d, hash_entry, h) {
2610 cand_id = (__u32)(long)hash_entry->value;
2611 cand = d->btf->types[cand_id];
2612 if (btf_equal_common(t, cand)) {
2613 new_id = cand_id;
2614 break;
2615 }
2616 }
2617 break;
2618
2619 case BTF_KIND_ARRAY: {
2620 struct btf_array *info = (struct btf_array *)(t + 1);
2621
2622 ref_type_id = btf_dedup_ref_type(d, info->type);
2623 if (ref_type_id < 0)
2624 return ref_type_id;
2625 info->type = ref_type_id;
2626
2627 ref_type_id = btf_dedup_ref_type(d, info->index_type);
2628 if (ref_type_id < 0)
2629 return ref_type_id;
2630 info->index_type = ref_type_id;
2631
2632 h = btf_hash_array(t);
2633 for_each_dedup_cand(d, hash_entry, h) {
2634 cand_id = (__u32)(long)hash_entry->value;
2635 cand = d->btf->types[cand_id];
2636 if (btf_equal_array(t, cand)) {
2637 new_id = cand_id;
2638 break;
2639 }
2640 }
2641 break;
2642 }
2643
2644 case BTF_KIND_FUNC_PROTO: {
2645 struct btf_param *param;
2646 __u16 vlen;
2647 int i;
2648
2649 ref_type_id = btf_dedup_ref_type(d, t->type);
2650 if (ref_type_id < 0)
2651 return ref_type_id;
2652 t->type = ref_type_id;
2653
2654 vlen = BTF_INFO_VLEN(t->info);
2655 param = (struct btf_param *)(t + 1);
2656 for (i = 0; i < vlen; i++) {
2657 ref_type_id = btf_dedup_ref_type(d, param->type);
2658 if (ref_type_id < 0)
2659 return ref_type_id;
2660 param->type = ref_type_id;
2661 param++;
2662 }
2663
2664 h = btf_hash_fnproto(t);
2665 for_each_dedup_cand(d, hash_entry, h) {
2666 cand_id = (__u32)(long)hash_entry->value;
2667 cand = d->btf->types[cand_id];
2668 if (btf_equal_fnproto(t, cand)) {
2669 new_id = cand_id;
2670 break;
2671 }
2672 }
2673 break;
2674 }
2675
2676 default:
2677 return -EINVAL;
2678 }
2679
2680 d->map[type_id] = new_id;
2681 if (type_id == new_id && btf_dedup_table_add(d, h, type_id))
2682 return -ENOMEM;
2683
2684 return new_id;
2685}
2686
2687static int btf_dedup_ref_types(struct btf_dedup *d)
2688{
2689 int i, err;
2690
2691 for (i = 1; i <= d->btf->nr_types; i++) {
2692 err = btf_dedup_ref_type(d, i);
2693 if (err < 0)
2694 return err;
2695 }
2696
2697 hashmap__free(d->dedup_table);
2698 d->dedup_table = NULL;
2699 return 0;
2700}
2701
2702
2703
2704
2705
2706
2707
2708
2709
2710
2711
2712
2713static int btf_dedup_compact_types(struct btf_dedup *d)
2714{
2715 struct btf_type **new_types;
2716 __u32 next_type_id = 1;
2717 char *types_start, *p;
2718 int i, len;
2719
2720
2721 d->hypot_map[0] = 0;
2722 for (i = 1; i <= d->btf->nr_types; i++)
2723 d->hypot_map[i] = BTF_UNPROCESSED_ID;
2724
2725 types_start = d->btf->nohdr_data + d->btf->hdr->type_off;
2726 p = types_start;
2727
2728 for (i = 1; i <= d->btf->nr_types; i++) {
2729 if (d->map[i] != i)
2730 continue;
2731
2732 len = btf_type_size(d->btf->types[i]);
2733 if (len < 0)
2734 return len;
2735
2736 memmove(p, d->btf->types[i], len);
2737 d->hypot_map[i] = next_type_id;
2738 d->btf->types[next_type_id] = (struct btf_type *)p;
2739 p += len;
2740 next_type_id++;
2741 }
2742
2743
2744 d->btf->nr_types = next_type_id - 1;
2745 d->btf->types_size = d->btf->nr_types;
2746 d->btf->hdr->type_len = p - types_start;
2747 new_types = realloc(d->btf->types,
2748 (1 + d->btf->nr_types) * sizeof(struct btf_type *));
2749 if (!new_types)
2750 return -ENOMEM;
2751 d->btf->types = new_types;
2752
2753
2754 d->btf->hdr->str_off = p - (char *)d->btf->nohdr_data;
2755 memmove(p, d->btf->strings, d->btf->hdr->str_len);
2756 d->btf->strings = p;
2757 p += d->btf->hdr->str_len;
2758
2759 d->btf->data_size = p - (char *)d->btf->data;
2760 return 0;
2761}
2762
2763
2764
2765
2766
2767
2768
2769static int btf_dedup_remap_type_id(struct btf_dedup *d, __u32 type_id)
2770{
2771 __u32 resolved_type_id, new_type_id;
2772
2773 resolved_type_id = resolve_type_id(d, type_id);
2774 new_type_id = d->hypot_map[resolved_type_id];
2775 if (new_type_id > BTF_MAX_NR_TYPES)
2776 return -EINVAL;
2777 return new_type_id;
2778}
2779
2780
2781
2782
2783
2784
2785
2786
2787
2788
2789
2790static int btf_dedup_remap_type(struct btf_dedup *d, __u32 type_id)
2791{
2792 struct btf_type *t = d->btf->types[type_id];
2793 int i, r;
2794
2795 switch (BTF_INFO_KIND(t->info)) {
2796 case BTF_KIND_INT:
2797 case BTF_KIND_ENUM:
2798 break;
2799
2800 case BTF_KIND_FWD:
2801 case BTF_KIND_CONST:
2802 case BTF_KIND_VOLATILE:
2803 case BTF_KIND_RESTRICT:
2804 case BTF_KIND_PTR:
2805 case BTF_KIND_TYPEDEF:
2806 case BTF_KIND_FUNC:
2807 case BTF_KIND_VAR:
2808 r = btf_dedup_remap_type_id(d, t->type);
2809 if (r < 0)
2810 return r;
2811 t->type = r;
2812 break;
2813
2814 case BTF_KIND_ARRAY: {
2815 struct btf_array *arr_info = (struct btf_array *)(t + 1);
2816
2817 r = btf_dedup_remap_type_id(d, arr_info->type);
2818 if (r < 0)
2819 return r;
2820 arr_info->type = r;
2821 r = btf_dedup_remap_type_id(d, arr_info->index_type);
2822 if (r < 0)
2823 return r;
2824 arr_info->index_type = r;
2825 break;
2826 }
2827
2828 case BTF_KIND_STRUCT:
2829 case BTF_KIND_UNION: {
2830 struct btf_member *member = (struct btf_member *)(t + 1);
2831 __u16 vlen = BTF_INFO_VLEN(t->info);
2832
2833 for (i = 0; i < vlen; i++) {
2834 r = btf_dedup_remap_type_id(d, member->type);
2835 if (r < 0)
2836 return r;
2837 member->type = r;
2838 member++;
2839 }
2840 break;
2841 }
2842
2843 case BTF_KIND_FUNC_PROTO: {
2844 struct btf_param *param = (struct btf_param *)(t + 1);
2845 __u16 vlen = BTF_INFO_VLEN(t->info);
2846
2847 r = btf_dedup_remap_type_id(d, t->type);
2848 if (r < 0)
2849 return r;
2850 t->type = r;
2851
2852 for (i = 0; i < vlen; i++) {
2853 r = btf_dedup_remap_type_id(d, param->type);
2854 if (r < 0)
2855 return r;
2856 param->type = r;
2857 param++;
2858 }
2859 break;
2860 }
2861
2862 case BTF_KIND_DATASEC: {
2863 struct btf_var_secinfo *var = (struct btf_var_secinfo *)(t + 1);
2864 __u16 vlen = BTF_INFO_VLEN(t->info);
2865
2866 for (i = 0; i < vlen; i++) {
2867 r = btf_dedup_remap_type_id(d, var->type);
2868 if (r < 0)
2869 return r;
2870 var->type = r;
2871 var++;
2872 }
2873 break;
2874 }
2875
2876 default:
2877 return -EINVAL;
2878 }
2879
2880 return 0;
2881}
2882
2883static int btf_dedup_remap_types(struct btf_dedup *d)
2884{
2885 int i, r;
2886
2887 for (i = 1; i <= d->btf->nr_types; i++) {
2888 r = btf_dedup_remap_type(d, i);
2889 if (r < 0)
2890 return r;
2891 }
2892 return 0;
2893}
2894