aboutsummaryrefslogtreecommitdiffstats
path: root/tools/lib/bpf/btf.c
diff options
context:
space:
mode:
Diffstat (limited to 'tools/lib/bpf/btf.c')
-rw-r--r--tools/lib/bpf/btf.c2032
1 files changed, 1924 insertions, 108 deletions
diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
index d682d3b8f7b9..ab6528c935a1 100644
--- a/tools/lib/bpf/btf.c
+++ b/tools/lib/bpf/btf.c
@@ -1,6 +1,7 @@
1// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) 1// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)
2/* Copyright (c) 2018 Facebook */ 2/* Copyright (c) 2018 Facebook */
3 3
4#include <stdio.h>
4#include <stdlib.h> 5#include <stdlib.h>
5#include <string.h> 6#include <string.h>
6#include <unistd.h> 7#include <unistd.h>
@@ -9,8 +10,9 @@
9#include <linux/btf.h> 10#include <linux/btf.h>
10#include "btf.h" 11#include "btf.h"
11#include "bpf.h" 12#include "bpf.h"
13#include "libbpf.h"
14#include "libbpf_util.h"
12 15
13#define elog(fmt, ...) { if (err_log) err_log(fmt, ##__VA_ARGS__); }
14#define max(a, b) ((a) > (b) ? (a) : (b)) 16#define max(a, b) ((a) > (b) ? (a) : (b))
15#define min(a, b) ((a) < (b) ? (a) : (b)) 17#define min(a, b) ((a) < (b) ? (a) : (b))
16 18
@@ -107,54 +109,54 @@ static int btf_add_type(struct btf *btf, struct btf_type *t)
107 return 0; 109 return 0;
108} 110}
109 111
110static int btf_parse_hdr(struct btf *btf, btf_print_fn_t err_log) 112static int btf_parse_hdr(struct btf *btf)
111{ 113{
112 const struct btf_header *hdr = btf->hdr; 114 const struct btf_header *hdr = btf->hdr;
113 __u32 meta_left; 115 __u32 meta_left;
114 116
115 if (btf->data_size < sizeof(struct btf_header)) { 117 if (btf->data_size < sizeof(struct btf_header)) {
116 elog("BTF header not found\n"); 118 pr_debug("BTF header not found\n");
117 return -EINVAL; 119 return -EINVAL;
118 } 120 }
119 121
120 if (hdr->magic != BTF_MAGIC) { 122 if (hdr->magic != BTF_MAGIC) {
121 elog("Invalid BTF magic:%x\n", hdr->magic); 123 pr_debug("Invalid BTF magic:%x\n", hdr->magic);
122 return -EINVAL; 124 return -EINVAL;
123 } 125 }
124 126
125 if (hdr->version != BTF_VERSION) { 127 if (hdr->version != BTF_VERSION) {
126 elog("Unsupported BTF version:%u\n", hdr->version); 128 pr_debug("Unsupported BTF version:%u\n", hdr->version);
127 return -ENOTSUP; 129 return -ENOTSUP;
128 } 130 }
129 131
130 if (hdr->flags) { 132 if (hdr->flags) {
131 elog("Unsupported BTF flags:%x\n", hdr->flags); 133 pr_debug("Unsupported BTF flags:%x\n", hdr->flags);
132 return -ENOTSUP; 134 return -ENOTSUP;
133 } 135 }
134 136
135 meta_left = btf->data_size - sizeof(*hdr); 137 meta_left = btf->data_size - sizeof(*hdr);
136 if (!meta_left) { 138 if (!meta_left) {
137 elog("BTF has no data\n"); 139 pr_debug("BTF has no data\n");
138 return -EINVAL; 140 return -EINVAL;
139 } 141 }
140 142
141 if (meta_left < hdr->type_off) { 143 if (meta_left < hdr->type_off) {
142 elog("Invalid BTF type section offset:%u\n", hdr->type_off); 144 pr_debug("Invalid BTF type section offset:%u\n", hdr->type_off);
143 return -EINVAL; 145 return -EINVAL;
144 } 146 }
145 147
146 if (meta_left < hdr->str_off) { 148 if (meta_left < hdr->str_off) {
147 elog("Invalid BTF string section offset:%u\n", hdr->str_off); 149 pr_debug("Invalid BTF string section offset:%u\n", hdr->str_off);
148 return -EINVAL; 150 return -EINVAL;
149 } 151 }
150 152
151 if (hdr->type_off >= hdr->str_off) { 153 if (hdr->type_off >= hdr->str_off) {
152 elog("BTF type section offset >= string section offset. No type?\n"); 154 pr_debug("BTF type section offset >= string section offset. No type?\n");
153 return -EINVAL; 155 return -EINVAL;
154 } 156 }
155 157
156 if (hdr->type_off & 0x02) { 158 if (hdr->type_off & 0x02) {
157 elog("BTF type section is not aligned to 4 bytes\n"); 159 pr_debug("BTF type section is not aligned to 4 bytes\n");
158 return -EINVAL; 160 return -EINVAL;
159 } 161 }
160 162
@@ -163,7 +165,7 @@ static int btf_parse_hdr(struct btf *btf, btf_print_fn_t err_log)
163 return 0; 165 return 0;
164} 166}
165 167
166static int btf_parse_str_sec(struct btf *btf, btf_print_fn_t err_log) 168static int btf_parse_str_sec(struct btf *btf)
167{ 169{
168 const struct btf_header *hdr = btf->hdr; 170 const struct btf_header *hdr = btf->hdr;
169 const char *start = btf->nohdr_data + hdr->str_off; 171 const char *start = btf->nohdr_data + hdr->str_off;
@@ -171,7 +173,7 @@ static int btf_parse_str_sec(struct btf *btf, btf_print_fn_t err_log)
171 173
172 if (!hdr->str_len || hdr->str_len - 1 > BTF_MAX_NAME_OFFSET || 174 if (!hdr->str_len || hdr->str_len - 1 > BTF_MAX_NAME_OFFSET ||
173 start[0] || end[-1]) { 175 start[0] || end[-1]) {
174 elog("Invalid BTF string section\n"); 176 pr_debug("Invalid BTF string section\n");
175 return -EINVAL; 177 return -EINVAL;
176 } 178 }
177 179
@@ -180,7 +182,38 @@ static int btf_parse_str_sec(struct btf *btf, btf_print_fn_t err_log)
180 return 0; 182 return 0;
181} 183}
182 184
183static int btf_parse_type_sec(struct btf *btf, btf_print_fn_t err_log) 185static int btf_type_size(struct btf_type *t)
186{
187 int base_size = sizeof(struct btf_type);
188 __u16 vlen = BTF_INFO_VLEN(t->info);
189
190 switch (BTF_INFO_KIND(t->info)) {
191 case BTF_KIND_FWD:
192 case BTF_KIND_CONST:
193 case BTF_KIND_VOLATILE:
194 case BTF_KIND_RESTRICT:
195 case BTF_KIND_PTR:
196 case BTF_KIND_TYPEDEF:
197 case BTF_KIND_FUNC:
198 return base_size;
199 case BTF_KIND_INT:
200 return base_size + sizeof(__u32);
201 case BTF_KIND_ENUM:
202 return base_size + vlen * sizeof(struct btf_enum);
203 case BTF_KIND_ARRAY:
204 return base_size + sizeof(struct btf_array);
205 case BTF_KIND_STRUCT:
206 case BTF_KIND_UNION:
207 return base_size + vlen * sizeof(struct btf_member);
208 case BTF_KIND_FUNC_PROTO:
209 return base_size + vlen * sizeof(struct btf_param);
210 default:
211 pr_debug("Unsupported BTF_KIND:%u\n", BTF_INFO_KIND(t->info));
212 return -EINVAL;
213 }
214}
215
216static int btf_parse_type_sec(struct btf *btf)
184{ 217{
185 struct btf_header *hdr = btf->hdr; 218 struct btf_header *hdr = btf->hdr;
186 void *nohdr_data = btf->nohdr_data; 219 void *nohdr_data = btf->nohdr_data;
@@ -189,41 +222,13 @@ static int btf_parse_type_sec(struct btf *btf, btf_print_fn_t err_log)
189 222
190 while (next_type < end_type) { 223 while (next_type < end_type) {
191 struct btf_type *t = next_type; 224 struct btf_type *t = next_type;
192 __u16 vlen = BTF_INFO_VLEN(t->info); 225 int type_size;
193 int err; 226 int err;
194 227
195 next_type += sizeof(*t); 228 type_size = btf_type_size(t);
196 switch (BTF_INFO_KIND(t->info)) { 229 if (type_size < 0)
197 case BTF_KIND_INT: 230 return type_size;
198 next_type += sizeof(int); 231 next_type += type_size;
199 break;
200 case BTF_KIND_ARRAY:
201 next_type += sizeof(struct btf_array);
202 break;
203 case BTF_KIND_STRUCT:
204 case BTF_KIND_UNION:
205 next_type += vlen * sizeof(struct btf_member);
206 break;
207 case BTF_KIND_ENUM:
208 next_type += vlen * sizeof(struct btf_enum);
209 break;
210 case BTF_KIND_FUNC_PROTO:
211 next_type += vlen * sizeof(struct btf_param);
212 break;
213 case BTF_KIND_FUNC:
214 case BTF_KIND_TYPEDEF:
215 case BTF_KIND_PTR:
216 case BTF_KIND_FWD:
217 case BTF_KIND_VOLATILE:
218 case BTF_KIND_CONST:
219 case BTF_KIND_RESTRICT:
220 break;
221 default:
222 elog("Unsupported BTF_KIND:%u\n",
223 BTF_INFO_KIND(t->info));
224 return -EINVAL;
225 }
226
227 err = btf_add_type(btf, t); 232 err = btf_add_type(btf, t);
228 if (err) 233 if (err)
229 return err; 234 return err;
@@ -232,6 +237,11 @@ static int btf_parse_type_sec(struct btf *btf, btf_print_fn_t err_log)
232 return 0; 237 return 0;
233} 238}
234 239
240__u32 btf__get_nr_types(const struct btf *btf)
241{
242 return btf->nr_types;
243}
244
235const struct btf_type *btf__type_by_id(const struct btf *btf, __u32 type_id) 245const struct btf_type *btf__type_by_id(const struct btf *btf, __u32 type_id)
236{ 246{
237 if (type_id > btf->nr_types) 247 if (type_id > btf->nr_types)
@@ -250,21 +260,6 @@ static bool btf_type_is_void_or_null(const struct btf_type *t)
250 return !t || btf_type_is_void(t); 260 return !t || btf_type_is_void(t);
251} 261}
252 262
253static __s64 btf_type_size(const struct btf_type *t)
254{
255 switch (BTF_INFO_KIND(t->info)) {
256 case BTF_KIND_INT:
257 case BTF_KIND_STRUCT:
258 case BTF_KIND_UNION:
259 case BTF_KIND_ENUM:
260 return t->size;
261 case BTF_KIND_PTR:
262 return sizeof(void *);
263 default:
264 return -EINVAL;
265 }
266}
267
268#define MAX_RESOLVE_DEPTH 32 263#define MAX_RESOLVE_DEPTH 32
269 264
270__s64 btf__resolve_size(const struct btf *btf, __u32 type_id) 265__s64 btf__resolve_size(const struct btf *btf, __u32 type_id)
@@ -278,11 +273,16 @@ __s64 btf__resolve_size(const struct btf *btf, __u32 type_id)
278 t = btf__type_by_id(btf, type_id); 273 t = btf__type_by_id(btf, type_id);
279 for (i = 0; i < MAX_RESOLVE_DEPTH && !btf_type_is_void_or_null(t); 274 for (i = 0; i < MAX_RESOLVE_DEPTH && !btf_type_is_void_or_null(t);
280 i++) { 275 i++) {
281 size = btf_type_size(t);
282 if (size >= 0)
283 break;
284
285 switch (BTF_INFO_KIND(t->info)) { 276 switch (BTF_INFO_KIND(t->info)) {
277 case BTF_KIND_INT:
278 case BTF_KIND_STRUCT:
279 case BTF_KIND_UNION:
280 case BTF_KIND_ENUM:
281 size = t->size;
282 goto done;
283 case BTF_KIND_PTR:
284 size = sizeof(void *);
285 goto done;
286 case BTF_KIND_TYPEDEF: 286 case BTF_KIND_TYPEDEF:
287 case BTF_KIND_VOLATILE: 287 case BTF_KIND_VOLATILE:
288 case BTF_KIND_CONST: 288 case BTF_KIND_CONST:
@@ -306,6 +306,7 @@ __s64 btf__resolve_size(const struct btf *btf, __u32 type_id)
306 if (size < 0) 306 if (size < 0)
307 return -EINVAL; 307 return -EINVAL;
308 308
309done:
309 if (nelems && size > UINT32_MAX / nelems) 310 if (nelems && size > UINT32_MAX / nelems)
310 return -E2BIG; 311 return -E2BIG;
311 312
@@ -363,7 +364,7 @@ void btf__free(struct btf *btf)
363 free(btf); 364 free(btf);
364} 365}
365 366
366struct btf *btf__new(__u8 *data, __u32 size, btf_print_fn_t err_log) 367struct btf *btf__new(__u8 *data, __u32 size)
367{ 368{
368 __u32 log_buf_size = 0; 369 __u32 log_buf_size = 0;
369 char *log_buf = NULL; 370 char *log_buf = NULL;
@@ -376,16 +377,15 @@ struct btf *btf__new(__u8 *data, __u32 size, btf_print_fn_t err_log)
376 377
377 btf->fd = -1; 378 btf->fd = -1;
378 379
379 if (err_log) { 380 log_buf = malloc(BPF_LOG_BUF_SIZE);
380 log_buf = malloc(BPF_LOG_BUF_SIZE); 381 if (!log_buf) {
381 if (!log_buf) { 382 err = -ENOMEM;
382 err = -ENOMEM; 383 goto done;
383 goto done;
384 }
385 *log_buf = 0;
386 log_buf_size = BPF_LOG_BUF_SIZE;
387 } 384 }
388 385
386 *log_buf = 0;
387 log_buf_size = BPF_LOG_BUF_SIZE;
388
389 btf->data = malloc(size); 389 btf->data = malloc(size);
390 if (!btf->data) { 390 if (!btf->data) {
391 err = -ENOMEM; 391 err = -ENOMEM;
@@ -400,21 +400,21 @@ struct btf *btf__new(__u8 *data, __u32 size, btf_print_fn_t err_log)
400 400
401 if (btf->fd == -1) { 401 if (btf->fd == -1) {
402 err = -errno; 402 err = -errno;
403 elog("Error loading BTF: %s(%d)\n", strerror(errno), errno); 403 pr_warning("Error loading BTF: %s(%d)\n", strerror(errno), errno);
404 if (log_buf && *log_buf) 404 if (log_buf && *log_buf)
405 elog("%s\n", log_buf); 405 pr_warning("%s\n", log_buf);
406 goto done; 406 goto done;
407 } 407 }
408 408
409 err = btf_parse_hdr(btf, err_log); 409 err = btf_parse_hdr(btf);
410 if (err) 410 if (err)
411 goto done; 411 goto done;
412 412
413 err = btf_parse_str_sec(btf, err_log); 413 err = btf_parse_str_sec(btf);
414 if (err) 414 if (err)
415 goto done; 415 goto done;
416 416
417 err = btf_parse_type_sec(btf, err_log); 417 err = btf_parse_type_sec(btf);
418 418
419done: 419done:
420 free(log_buf); 420 free(log_buf);
@@ -432,6 +432,13 @@ int btf__fd(const struct btf *btf)
432 return btf->fd; 432 return btf->fd;
433} 433}
434 434
435void btf__get_strings(const struct btf *btf, const char **strings,
436 __u32 *str_len)
437{
438 *strings = btf->strings;
439 *str_len = btf->hdr->str_len;
440}
441
435const char *btf__name_by_offset(const struct btf *btf, __u32 offset) 442const char *btf__name_by_offset(const struct btf *btf, __u32 offset)
436{ 443{
437 if (offset < btf->hdr->str_len) 444 if (offset < btf->hdr->str_len)
@@ -491,7 +498,7 @@ int btf__get_from_id(__u32 id, struct btf **btf)
491 goto exit_free; 498 goto exit_free;
492 } 499 }
493 500
494 *btf = btf__new((__u8 *)(long)btf_info.btf, btf_info.btf_size, NULL); 501 *btf = btf__new((__u8 *)(long)btf_info.btf, btf_info.btf_size);
495 if (IS_ERR(*btf)) { 502 if (IS_ERR(*btf)) {
496 err = PTR_ERR(*btf); 503 err = PTR_ERR(*btf);
497 *btf = NULL; 504 *btf = NULL;
@@ -504,6 +511,78 @@ exit_free:
504 return err; 511 return err;
505} 512}
506 513
514int btf__get_map_kv_tids(const struct btf *btf, const char *map_name,
515 __u32 expected_key_size, __u32 expected_value_size,
516 __u32 *key_type_id, __u32 *value_type_id)
517{
518 const struct btf_type *container_type;
519 const struct btf_member *key, *value;
520 const size_t max_name = 256;
521 char container_name[max_name];
522 __s64 key_size, value_size;
523 __s32 container_id;
524
525 if (snprintf(container_name, max_name, "____btf_map_%s", map_name) ==
526 max_name) {
527 pr_warning("map:%s length of '____btf_map_%s' is too long\n",
528 map_name, map_name);
529 return -EINVAL;
530 }
531
532 container_id = btf__find_by_name(btf, container_name);
533 if (container_id < 0) {
534 pr_debug("map:%s container_name:%s cannot be found in BTF. Missing BPF_ANNOTATE_KV_PAIR?\n",
535 map_name, container_name);
536 return container_id;
537 }
538
539 container_type = btf__type_by_id(btf, container_id);
540 if (!container_type) {
541 pr_warning("map:%s cannot find BTF type for container_id:%u\n",
542 map_name, container_id);
543 return -EINVAL;
544 }
545
546 if (BTF_INFO_KIND(container_type->info) != BTF_KIND_STRUCT ||
547 BTF_INFO_VLEN(container_type->info) < 2) {
548 pr_warning("map:%s container_name:%s is an invalid container struct\n",
549 map_name, container_name);
550 return -EINVAL;
551 }
552
553 key = (struct btf_member *)(container_type + 1);
554 value = key + 1;
555
556 key_size = btf__resolve_size(btf, key->type);
557 if (key_size < 0) {
558 pr_warning("map:%s invalid BTF key_type_size\n", map_name);
559 return key_size;
560 }
561
562 if (expected_key_size != key_size) {
563 pr_warning("map:%s btf_key_type_size:%u != map_def_key_size:%u\n",
564 map_name, (__u32)key_size, expected_key_size);
565 return -EINVAL;
566 }
567
568 value_size = btf__resolve_size(btf, value->type);
569 if (value_size < 0) {
570 pr_warning("map:%s invalid BTF value_type_size\n", map_name);
571 return value_size;
572 }
573
574 if (expected_value_size != value_size) {
575 pr_warning("map:%s btf_value_type_size:%u != map_def_value_size:%u\n",
576 map_name, (__u32)value_size, expected_value_size);
577 return -EINVAL;
578 }
579
580 *key_type_id = key->type;
581 *value_type_id = value->type;
582
583 return 0;
584}
585
507struct btf_ext_sec_copy_param { 586struct btf_ext_sec_copy_param {
508 __u32 off; 587 __u32 off;
509 __u32 len; 588 __u32 len;
@@ -514,8 +593,7 @@ struct btf_ext_sec_copy_param {
514 593
515static int btf_ext_copy_info(struct btf_ext *btf_ext, 594static int btf_ext_copy_info(struct btf_ext *btf_ext,
516 __u8 *data, __u32 data_size, 595 __u8 *data, __u32 data_size,
517 struct btf_ext_sec_copy_param *ext_sec, 596 struct btf_ext_sec_copy_param *ext_sec)
518 btf_print_fn_t err_log)
519{ 597{
520 const struct btf_ext_header *hdr = (struct btf_ext_header *)data; 598 const struct btf_ext_header *hdr = (struct btf_ext_header *)data;
521 const struct btf_ext_info_sec *sinfo; 599 const struct btf_ext_info_sec *sinfo;
@@ -529,14 +607,14 @@ static int btf_ext_copy_info(struct btf_ext *btf_ext,
529 data_size -= hdr->hdr_len; 607 data_size -= hdr->hdr_len;
530 608
531 if (ext_sec->off & 0x03) { 609 if (ext_sec->off & 0x03) {
532 elog(".BTF.ext %s section is not aligned to 4 bytes\n", 610 pr_debug(".BTF.ext %s section is not aligned to 4 bytes\n",
533 ext_sec->desc); 611 ext_sec->desc);
534 return -EINVAL; 612 return -EINVAL;
535 } 613 }
536 614
537 if (data_size < ext_sec->off || 615 if (data_size < ext_sec->off ||
538 ext_sec->len > data_size - ext_sec->off) { 616 ext_sec->len > data_size - ext_sec->off) {
539 elog("%s section (off:%u len:%u) is beyond the end of the ELF section .BTF.ext\n", 617 pr_debug("%s section (off:%u len:%u) is beyond the end of the ELF section .BTF.ext\n",
540 ext_sec->desc, ext_sec->off, ext_sec->len); 618 ext_sec->desc, ext_sec->off, ext_sec->len);
541 return -EINVAL; 619 return -EINVAL;
542 } 620 }
@@ -546,7 +624,7 @@ static int btf_ext_copy_info(struct btf_ext *btf_ext,
546 624
547 /* At least a record size */ 625 /* At least a record size */
548 if (info_left < sizeof(__u32)) { 626 if (info_left < sizeof(__u32)) {
549 elog(".BTF.ext %s record size not found\n", ext_sec->desc); 627 pr_debug(".BTF.ext %s record size not found\n", ext_sec->desc);
550 return -EINVAL; 628 return -EINVAL;
551 } 629 }
552 630
@@ -554,7 +632,7 @@ static int btf_ext_copy_info(struct btf_ext *btf_ext,
554 record_size = *(__u32 *)info; 632 record_size = *(__u32 *)info;
555 if (record_size < ext_sec->min_rec_size || 633 if (record_size < ext_sec->min_rec_size ||
556 record_size & 0x03) { 634 record_size & 0x03) {
557 elog("%s section in .BTF.ext has invalid record size %u\n", 635 pr_debug("%s section in .BTF.ext has invalid record size %u\n",
558 ext_sec->desc, record_size); 636 ext_sec->desc, record_size);
559 return -EINVAL; 637 return -EINVAL;
560 } 638 }
@@ -564,7 +642,7 @@ static int btf_ext_copy_info(struct btf_ext *btf_ext,
564 642
565 /* If no records, return failure now so .BTF.ext won't be used. */ 643 /* If no records, return failure now so .BTF.ext won't be used. */
566 if (!info_left) { 644 if (!info_left) {
567 elog("%s section in .BTF.ext has no records", ext_sec->desc); 645 pr_debug("%s section in .BTF.ext has no records", ext_sec->desc);
568 return -EINVAL; 646 return -EINVAL;
569 } 647 }
570 648
@@ -574,14 +652,14 @@ static int btf_ext_copy_info(struct btf_ext *btf_ext,
574 __u32 num_records; 652 __u32 num_records;
575 653
576 if (info_left < sec_hdrlen) { 654 if (info_left < sec_hdrlen) {
577 elog("%s section header is not found in .BTF.ext\n", 655 pr_debug("%s section header is not found in .BTF.ext\n",
578 ext_sec->desc); 656 ext_sec->desc);
579 return -EINVAL; 657 return -EINVAL;
580 } 658 }
581 659
582 num_records = sinfo->num_info; 660 num_records = sinfo->num_info;
583 if (num_records == 0) { 661 if (num_records == 0) {
584 elog("%s section has incorrect num_records in .BTF.ext\n", 662 pr_debug("%s section has incorrect num_records in .BTF.ext\n",
585 ext_sec->desc); 663 ext_sec->desc);
586 return -EINVAL; 664 return -EINVAL;
587 } 665 }
@@ -589,7 +667,7 @@ static int btf_ext_copy_info(struct btf_ext *btf_ext,
589 total_record_size = sec_hdrlen + 667 total_record_size = sec_hdrlen +
590 (__u64)num_records * record_size; 668 (__u64)num_records * record_size;
591 if (info_left < total_record_size) { 669 if (info_left < total_record_size) {
592 elog("%s section has incorrect num_records in .BTF.ext\n", 670 pr_debug("%s section has incorrect num_records in .BTF.ext\n",
593 ext_sec->desc); 671 ext_sec->desc);
594 return -EINVAL; 672 return -EINVAL;
595 } 673 }
@@ -610,8 +688,7 @@ static int btf_ext_copy_info(struct btf_ext *btf_ext,
610} 688}
611 689
612static int btf_ext_copy_func_info(struct btf_ext *btf_ext, 690static int btf_ext_copy_func_info(struct btf_ext *btf_ext,
613 __u8 *data, __u32 data_size, 691 __u8 *data, __u32 data_size)
614 btf_print_fn_t err_log)
615{ 692{
616 const struct btf_ext_header *hdr = (struct btf_ext_header *)data; 693 const struct btf_ext_header *hdr = (struct btf_ext_header *)data;
617 struct btf_ext_sec_copy_param param = { 694 struct btf_ext_sec_copy_param param = {
@@ -622,12 +699,11 @@ static int btf_ext_copy_func_info(struct btf_ext *btf_ext,
622 .desc = "func_info" 699 .desc = "func_info"
623 }; 700 };
624 701
625 return btf_ext_copy_info(btf_ext, data, data_size, &param, err_log); 702 return btf_ext_copy_info(btf_ext, data, data_size, &param);
626} 703}
627 704
628static int btf_ext_copy_line_info(struct btf_ext *btf_ext, 705static int btf_ext_copy_line_info(struct btf_ext *btf_ext,
629 __u8 *data, __u32 data_size, 706 __u8 *data, __u32 data_size)
630 btf_print_fn_t err_log)
631{ 707{
632 const struct btf_ext_header *hdr = (struct btf_ext_header *)data; 708 const struct btf_ext_header *hdr = (struct btf_ext_header *)data;
633 struct btf_ext_sec_copy_param param = { 709 struct btf_ext_sec_copy_param param = {
@@ -638,37 +714,36 @@ static int btf_ext_copy_line_info(struct btf_ext *btf_ext,
638 .desc = "line_info", 714 .desc = "line_info",
639 }; 715 };
640 716
641 return btf_ext_copy_info(btf_ext, data, data_size, &param, err_log); 717 return btf_ext_copy_info(btf_ext, data, data_size, &param);
642} 718}
643 719
644static int btf_ext_parse_hdr(__u8 *data, __u32 data_size, 720static int btf_ext_parse_hdr(__u8 *data, __u32 data_size)
645 btf_print_fn_t err_log)
646{ 721{
647 const struct btf_ext_header *hdr = (struct btf_ext_header *)data; 722 const struct btf_ext_header *hdr = (struct btf_ext_header *)data;
648 723
649 if (data_size < offsetof(struct btf_ext_header, func_info_off) || 724 if (data_size < offsetof(struct btf_ext_header, func_info_off) ||
650 data_size < hdr->hdr_len) { 725 data_size < hdr->hdr_len) {
651 elog("BTF.ext header not found"); 726 pr_debug("BTF.ext header not found");
652 return -EINVAL; 727 return -EINVAL;
653 } 728 }
654 729
655 if (hdr->magic != BTF_MAGIC) { 730 if (hdr->magic != BTF_MAGIC) {
656 elog("Invalid BTF.ext magic:%x\n", hdr->magic); 731 pr_debug("Invalid BTF.ext magic:%x\n", hdr->magic);
657 return -EINVAL; 732 return -EINVAL;
658 } 733 }
659 734
660 if (hdr->version != BTF_VERSION) { 735 if (hdr->version != BTF_VERSION) {
661 elog("Unsupported BTF.ext version:%u\n", hdr->version); 736 pr_debug("Unsupported BTF.ext version:%u\n", hdr->version);
662 return -ENOTSUP; 737 return -ENOTSUP;
663 } 738 }
664 739
665 if (hdr->flags) { 740 if (hdr->flags) {
666 elog("Unsupported BTF.ext flags:%x\n", hdr->flags); 741 pr_debug("Unsupported BTF.ext flags:%x\n", hdr->flags);
667 return -ENOTSUP; 742 return -ENOTSUP;
668 } 743 }
669 744
670 if (data_size == hdr->hdr_len) { 745 if (data_size == hdr->hdr_len) {
671 elog("BTF.ext has no data\n"); 746 pr_debug("BTF.ext has no data\n");
672 return -EINVAL; 747 return -EINVAL;
673 } 748 }
674 749
@@ -685,12 +760,12 @@ void btf_ext__free(struct btf_ext *btf_ext)
685 free(btf_ext); 760 free(btf_ext);
686} 761}
687 762
688struct btf_ext *btf_ext__new(__u8 *data, __u32 size, btf_print_fn_t err_log) 763struct btf_ext *btf_ext__new(__u8 *data, __u32 size)
689{ 764{
690 struct btf_ext *btf_ext; 765 struct btf_ext *btf_ext;
691 int err; 766 int err;
692 767
693 err = btf_ext_parse_hdr(data, size, err_log); 768 err = btf_ext_parse_hdr(data, size);
694 if (err) 769 if (err)
695 return ERR_PTR(err); 770 return ERR_PTR(err);
696 771
@@ -698,13 +773,13 @@ struct btf_ext *btf_ext__new(__u8 *data, __u32 size, btf_print_fn_t err_log)
698 if (!btf_ext) 773 if (!btf_ext)
699 return ERR_PTR(-ENOMEM); 774 return ERR_PTR(-ENOMEM);
700 775
701 err = btf_ext_copy_func_info(btf_ext, data, size, err_log); 776 err = btf_ext_copy_func_info(btf_ext, data, size);
702 if (err) { 777 if (err) {
703 btf_ext__free(btf_ext); 778 btf_ext__free(btf_ext);
704 return ERR_PTR(err); 779 return ERR_PTR(err);
705 } 780 }
706 781
707 err = btf_ext_copy_line_info(btf_ext, data, size, err_log); 782 err = btf_ext_copy_line_info(btf_ext, data, size);
708 if (err) { 783 if (err) {
709 btf_ext__free(btf_ext); 784 btf_ext__free(btf_ext);
710 return ERR_PTR(err); 785 return ERR_PTR(err);
@@ -786,3 +861,1744 @@ __u32 btf_ext__line_info_rec_size(const struct btf_ext *btf_ext)
786{ 861{
787 return btf_ext->line_info.rec_size; 862 return btf_ext->line_info.rec_size;
788} 863}
864
865struct btf_dedup;
866
867static struct btf_dedup *btf_dedup_new(struct btf *btf, struct btf_ext *btf_ext,
868 const struct btf_dedup_opts *opts);
869static void btf_dedup_free(struct btf_dedup *d);
870static int btf_dedup_strings(struct btf_dedup *d);
871static int btf_dedup_prim_types(struct btf_dedup *d);
872static int btf_dedup_struct_types(struct btf_dedup *d);
873static int btf_dedup_ref_types(struct btf_dedup *d);
874static int btf_dedup_compact_types(struct btf_dedup *d);
875static int btf_dedup_remap_types(struct btf_dedup *d);
876
877/*
878 * Deduplicate BTF types and strings.
879 *
880 * BTF dedup algorithm takes as an input `struct btf` representing `.BTF` ELF
881 * section with all BTF type descriptors and string data. It overwrites that
882 * memory in-place with deduplicated types and strings without any loss of
883 * information. If optional `struct btf_ext` representing '.BTF.ext' ELF section
884 * is provided, all the strings referenced from .BTF.ext section are honored
885 * and updated to point to the right offsets after deduplication.
886 *
887 * If function returns with error, type/string data might be garbled and should
888 * be discarded.
889 *
890 * More verbose and detailed description of both problem btf_dedup is solving,
891 * as well as solution could be found at:
892 * https://facebookmicrosites.github.io/bpf/blog/2018/11/14/btf-enhancement.html
893 *
894 * Problem description and justification
895 * =====================================
896 *
897 * BTF type information is typically emitted either as a result of conversion
898 * from DWARF to BTF or directly by compiler. In both cases, each compilation
899 * unit contains information about a subset of all the types that are used
900 * in an application. These subsets are frequently overlapping and contain a lot
901 * of duplicated information when later concatenated together into a single
902 * binary. This algorithm ensures that each unique type is represented by single
903 * BTF type descriptor, greatly reducing resulting size of BTF data.
904 *
905 * Compilation unit isolation and subsequent duplication of data is not the only
906 * problem. The same type hierarchy (e.g., struct and all the type that struct
907 * references) in different compilation units can be represented in BTF to
908 * various degrees of completeness (or, rather, incompleteness) due to
909 * struct/union forward declarations.
910 *
911 * Let's take a look at an example, that we'll use to better understand the
912 * problem (and solution). Suppose we have two compilation units, each using
913 * same `struct S`, but each of them having incomplete type information about
914 * struct's fields:
915 *
916 * // CU #1:
917 * struct S;
918 * struct A {
919 * int a;
920 * struct A* self;
921 * struct S* parent;
922 * };
923 * struct B;
924 * struct S {
925 * struct A* a_ptr;
926 * struct B* b_ptr;
927 * };
928 *
929 * // CU #2:
930 * struct S;
931 * struct A;
932 * struct B {
933 * int b;
934 * struct B* self;
935 * struct S* parent;
936 * };
937 * struct S {
938 * struct A* a_ptr;
939 * struct B* b_ptr;
940 * };
941 *
942 * In case of CU #1, BTF data will know only that `struct B` exist (but no
943 * more), but will know the complete type information about `struct A`. While
944 * for CU #2, it will know full type information about `struct B`, but will
945 * only know about forward declaration of `struct A` (in BTF terms, it will
946 * have `BTF_KIND_FWD` type descriptor with name `B`).
947 *
948 * This compilation unit isolation means that it's possible that there is no
949 * single CU with complete type information describing structs `S`, `A`, and
950 * `B`. Also, we might get tons of duplicated and redundant type information.
951 *
952 * Additional complication we need to keep in mind comes from the fact that
953 * types, in general, can form graphs containing cycles, not just DAGs.
954 *
955 * While algorithm does deduplication, it also merges and resolves type
956 * information (unless disabled throught `struct btf_opts`), whenever possible.
957 * E.g., in the example above with two compilation units having partial type
958 * information for structs `A` and `B`, the output of algorithm will emit
959 * a single copy of each BTF type that describes structs `A`, `B`, and `S`
960 * (as well as type information for `int` and pointers), as if they were defined
961 * in a single compilation unit as:
962 *
963 * struct A {
964 * int a;
965 * struct A* self;
966 * struct S* parent;
967 * };
968 * struct B {
969 * int b;
970 * struct B* self;
971 * struct S* parent;
972 * };
973 * struct S {
974 * struct A* a_ptr;
975 * struct B* b_ptr;
976 * };
977 *
978 * Algorithm summary
979 * =================
980 *
981 * Algorithm completes its work in 6 separate passes:
982 *
983 * 1. Strings deduplication.
984 * 2. Primitive types deduplication (int, enum, fwd).
985 * 3. Struct/union types deduplication.
986 * 4. Reference types deduplication (pointers, typedefs, arrays, funcs, func
987 * protos, and const/volatile/restrict modifiers).
988 * 5. Types compaction.
989 * 6. Types remapping.
990 *
991 * Algorithm determines canonical type descriptor, which is a single
992 * representative type for each truly unique type. This canonical type is the
993 * one that will go into final deduplicated BTF type information. For
994 * struct/unions, it is also the type that algorithm will merge additional type
995 * information into (while resolving FWDs), as it discovers it from data in
996 * other CUs. Each input BTF type eventually gets either mapped to itself, if
997 * that type is canonical, or to some other type, if that type is equivalent
998 * and was chosen as canonical representative. This mapping is stored in
999 * `btf_dedup->map` array. This map is also used to record STRUCT/UNION that
1000 * FWD type got resolved to.
1001 *
1002 * To facilitate fast discovery of canonical types, we also maintain canonical
1003 * index (`btf_dedup->dedup_table`), which maps type descriptor's signature hash
1004 * (i.e., hashed kind, name, size, fields, etc) into a list of canonical types
1005 * that match that signature. With sufficiently good choice of type signature
1006 * hashing function, we can limit number of canonical types for each unique type
1007 * signature to a very small number, allowing to find canonical type for any
1008 * duplicated type very quickly.
1009 *
1010 * Struct/union deduplication is the most critical part and algorithm for
1011 * deduplicating structs/unions is described in greater details in comments for
1012 * `btf_dedup_is_equiv` function.
1013 */
1014int btf__dedup(struct btf *btf, struct btf_ext *btf_ext,
1015 const struct btf_dedup_opts *opts)
1016{
1017 struct btf_dedup *d = btf_dedup_new(btf, btf_ext, opts);
1018 int err;
1019
1020 if (IS_ERR(d)) {
1021 pr_debug("btf_dedup_new failed: %ld", PTR_ERR(d));
1022 return -EINVAL;
1023 }
1024
1025 err = btf_dedup_strings(d);
1026 if (err < 0) {
1027 pr_debug("btf_dedup_strings failed:%d\n", err);
1028 goto done;
1029 }
1030 err = btf_dedup_prim_types(d);
1031 if (err < 0) {
1032 pr_debug("btf_dedup_prim_types failed:%d\n", err);
1033 goto done;
1034 }
1035 err = btf_dedup_struct_types(d);
1036 if (err < 0) {
1037 pr_debug("btf_dedup_struct_types failed:%d\n", err);
1038 goto done;
1039 }
1040 err = btf_dedup_ref_types(d);
1041 if (err < 0) {
1042 pr_debug("btf_dedup_ref_types failed:%d\n", err);
1043 goto done;
1044 }
1045 err = btf_dedup_compact_types(d);
1046 if (err < 0) {
1047 pr_debug("btf_dedup_compact_types failed:%d\n", err);
1048 goto done;
1049 }
1050 err = btf_dedup_remap_types(d);
1051 if (err < 0) {
1052 pr_debug("btf_dedup_remap_types failed:%d\n", err);
1053 goto done;
1054 }
1055
1056done:
1057 btf_dedup_free(d);
1058 return err;
1059}
1060
1061#define BTF_DEDUP_TABLE_SIZE_LOG 14
1062#define BTF_DEDUP_TABLE_MOD ((1 << BTF_DEDUP_TABLE_SIZE_LOG) - 1)
1063#define BTF_UNPROCESSED_ID ((__u32)-1)
1064#define BTF_IN_PROGRESS_ID ((__u32)-2)
1065
1066struct btf_dedup_node {
1067 struct btf_dedup_node *next;
1068 __u32 type_id;
1069};
1070
1071struct btf_dedup {
1072 /* .BTF section to be deduped in-place */
1073 struct btf *btf;
1074 /*
1075 * Optional .BTF.ext section. When provided, any strings referenced
1076 * from it will be taken into account when deduping strings
1077 */
1078 struct btf_ext *btf_ext;
1079 /*
1080 * This is a map from any type's signature hash to a list of possible
1081 * canonical representative type candidates. Hash collisions are
1082 * ignored, so even types of various kinds can share same list of
1083 * candidates, which is fine because we rely on subsequent
1084 * btf_xxx_equal() checks to authoritatively verify type equality.
1085 */
1086 struct btf_dedup_node **dedup_table;
1087 /* Canonical types map */
1088 __u32 *map;
1089 /* Hypothetical mapping, used during type graph equivalence checks */
1090 __u32 *hypot_map;
1091 __u32 *hypot_list;
1092 size_t hypot_cnt;
1093 size_t hypot_cap;
1094 /* Various option modifying behavior of algorithm */
1095 struct btf_dedup_opts opts;
1096};
1097
1098struct btf_str_ptr {
1099 const char *str;
1100 __u32 new_off;
1101 bool used;
1102};
1103
1104struct btf_str_ptrs {
1105 struct btf_str_ptr *ptrs;
1106 const char *data;
1107 __u32 cnt;
1108 __u32 cap;
1109};
1110
1111static inline __u32 hash_combine(__u32 h, __u32 value)
1112{
1113/* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
1114#define GOLDEN_RATIO_PRIME 0x9e370001UL
1115 return h * 37 + value * GOLDEN_RATIO_PRIME;
1116#undef GOLDEN_RATIO_PRIME
1117}
1118
1119#define for_each_hash_node(table, hash, node) \
1120 for (node = table[hash & BTF_DEDUP_TABLE_MOD]; node; node = node->next)
1121
1122static int btf_dedup_table_add(struct btf_dedup *d, __u32 hash, __u32 type_id)
1123{
1124 struct btf_dedup_node *node = malloc(sizeof(struct btf_dedup_node));
1125
1126 if (!node)
1127 return -ENOMEM;
1128 node->type_id = type_id;
1129 node->next = d->dedup_table[hash & BTF_DEDUP_TABLE_MOD];
1130 d->dedup_table[hash & BTF_DEDUP_TABLE_MOD] = node;
1131 return 0;
1132}
1133
1134static int btf_dedup_hypot_map_add(struct btf_dedup *d,
1135 __u32 from_id, __u32 to_id)
1136{
1137 if (d->hypot_cnt == d->hypot_cap) {
1138 __u32 *new_list;
1139
1140 d->hypot_cap += max(16, d->hypot_cap / 2);
1141 new_list = realloc(d->hypot_list, sizeof(__u32) * d->hypot_cap);
1142 if (!new_list)
1143 return -ENOMEM;
1144 d->hypot_list = new_list;
1145 }
1146 d->hypot_list[d->hypot_cnt++] = from_id;
1147 d->hypot_map[from_id] = to_id;
1148 return 0;
1149}
1150
1151static void btf_dedup_clear_hypot_map(struct btf_dedup *d)
1152{
1153 int i;
1154
1155 for (i = 0; i < d->hypot_cnt; i++)
1156 d->hypot_map[d->hypot_list[i]] = BTF_UNPROCESSED_ID;
1157 d->hypot_cnt = 0;
1158}
1159
1160static void btf_dedup_table_free(struct btf_dedup *d)
1161{
1162 struct btf_dedup_node *head, *tmp;
1163 int i;
1164
1165 if (!d->dedup_table)
1166 return;
1167
1168 for (i = 0; i < (1 << BTF_DEDUP_TABLE_SIZE_LOG); i++) {
1169 while (d->dedup_table[i]) {
1170 tmp = d->dedup_table[i];
1171 d->dedup_table[i] = tmp->next;
1172 free(tmp);
1173 }
1174
1175 head = d->dedup_table[i];
1176 while (head) {
1177 tmp = head;
1178 head = head->next;
1179 free(tmp);
1180 }
1181 }
1182
1183 free(d->dedup_table);
1184 d->dedup_table = NULL;
1185}
1186
1187static void btf_dedup_free(struct btf_dedup *d)
1188{
1189 btf_dedup_table_free(d);
1190
1191 free(d->map);
1192 d->map = NULL;
1193
1194 free(d->hypot_map);
1195 d->hypot_map = NULL;
1196
1197 free(d->hypot_list);
1198 d->hypot_list = NULL;
1199
1200 free(d);
1201}
1202
1203static struct btf_dedup *btf_dedup_new(struct btf *btf, struct btf_ext *btf_ext,
1204 const struct btf_dedup_opts *opts)
1205{
1206 struct btf_dedup *d = calloc(1, sizeof(struct btf_dedup));
1207 int i, err = 0;
1208
1209 if (!d)
1210 return ERR_PTR(-ENOMEM);
1211
1212 d->btf = btf;
1213 d->btf_ext = btf_ext;
1214
1215 d->dedup_table = calloc(1 << BTF_DEDUP_TABLE_SIZE_LOG,
1216 sizeof(struct btf_dedup_node *));
1217 if (!d->dedup_table) {
1218 err = -ENOMEM;
1219 goto done;
1220 }
1221
1222 d->map = malloc(sizeof(__u32) * (1 + btf->nr_types));
1223 if (!d->map) {
1224 err = -ENOMEM;
1225 goto done;
1226 }
1227 /* special BTF "void" type is made canonical immediately */
1228 d->map[0] = 0;
1229 for (i = 1; i <= btf->nr_types; i++)
1230 d->map[i] = BTF_UNPROCESSED_ID;
1231
1232 d->hypot_map = malloc(sizeof(__u32) * (1 + btf->nr_types));
1233 if (!d->hypot_map) {
1234 err = -ENOMEM;
1235 goto done;
1236 }
1237 for (i = 0; i <= btf->nr_types; i++)
1238 d->hypot_map[i] = BTF_UNPROCESSED_ID;
1239
1240 d->opts.dont_resolve_fwds = opts && opts->dont_resolve_fwds;
1241
1242done:
1243 if (err) {
1244 btf_dedup_free(d);
1245 return ERR_PTR(err);
1246 }
1247
1248 return d;
1249}
1250
1251typedef int (*str_off_fn_t)(__u32 *str_off_ptr, void *ctx);
1252
1253/*
1254 * Iterate over all possible places in .BTF and .BTF.ext that can reference
1255 * string and pass pointer to it to a provided callback `fn`.
1256 */
1257static int btf_for_each_str_off(struct btf_dedup *d, str_off_fn_t fn, void *ctx)
1258{
1259 void *line_data_cur, *line_data_end;
1260 int i, j, r, rec_size;
1261 struct btf_type *t;
1262
1263 for (i = 1; i <= d->btf->nr_types; i++) {
1264 t = d->btf->types[i];
1265 r = fn(&t->name_off, ctx);
1266 if (r)
1267 return r;
1268
1269 switch (BTF_INFO_KIND(t->info)) {
1270 case BTF_KIND_STRUCT:
1271 case BTF_KIND_UNION: {
1272 struct btf_member *m = (struct btf_member *)(t + 1);
1273 __u16 vlen = BTF_INFO_VLEN(t->info);
1274
1275 for (j = 0; j < vlen; j++) {
1276 r = fn(&m->name_off, ctx);
1277 if (r)
1278 return r;
1279 m++;
1280 }
1281 break;
1282 }
1283 case BTF_KIND_ENUM: {
1284 struct btf_enum *m = (struct btf_enum *)(t + 1);
1285 __u16 vlen = BTF_INFO_VLEN(t->info);
1286
1287 for (j = 0; j < vlen; j++) {
1288 r = fn(&m->name_off, ctx);
1289 if (r)
1290 return r;
1291 m++;
1292 }
1293 break;
1294 }
1295 case BTF_KIND_FUNC_PROTO: {
1296 struct btf_param *m = (struct btf_param *)(t + 1);
1297 __u16 vlen = BTF_INFO_VLEN(t->info);
1298
1299 for (j = 0; j < vlen; j++) {
1300 r = fn(&m->name_off, ctx);
1301 if (r)
1302 return r;
1303 m++;
1304 }
1305 break;
1306 }
1307 default:
1308 break;
1309 }
1310 }
1311
1312 if (!d->btf_ext)
1313 return 0;
1314
1315 line_data_cur = d->btf_ext->line_info.info;
1316 line_data_end = d->btf_ext->line_info.info + d->btf_ext->line_info.len;
1317 rec_size = d->btf_ext->line_info.rec_size;
1318
1319 while (line_data_cur < line_data_end) {
1320 struct btf_ext_info_sec *sec = line_data_cur;
1321 struct bpf_line_info_min *line_info;
1322 __u32 num_info = sec->num_info;
1323
1324 r = fn(&sec->sec_name_off, ctx);
1325 if (r)
1326 return r;
1327
1328 line_data_cur += sizeof(struct btf_ext_info_sec);
1329 for (i = 0; i < num_info; i++) {
1330 line_info = line_data_cur;
1331 r = fn(&line_info->file_name_off, ctx);
1332 if (r)
1333 return r;
1334 r = fn(&line_info->line_off, ctx);
1335 if (r)
1336 return r;
1337 line_data_cur += rec_size;
1338 }
1339 }
1340
1341 return 0;
1342}
1343
1344static int str_sort_by_content(const void *a1, const void *a2)
1345{
1346 const struct btf_str_ptr *p1 = a1;
1347 const struct btf_str_ptr *p2 = a2;
1348
1349 return strcmp(p1->str, p2->str);
1350}
1351
1352static int str_sort_by_offset(const void *a1, const void *a2)
1353{
1354 const struct btf_str_ptr *p1 = a1;
1355 const struct btf_str_ptr *p2 = a2;
1356
1357 if (p1->str != p2->str)
1358 return p1->str < p2->str ? -1 : 1;
1359 return 0;
1360}
1361
1362static int btf_dedup_str_ptr_cmp(const void *str_ptr, const void *pelem)
1363{
1364 const struct btf_str_ptr *p = pelem;
1365
1366 if (str_ptr != p->str)
1367 return (const char *)str_ptr < p->str ? -1 : 1;
1368 return 0;
1369}
1370
1371static int btf_str_mark_as_used(__u32 *str_off_ptr, void *ctx)
1372{
1373 struct btf_str_ptrs *strs;
1374 struct btf_str_ptr *s;
1375
1376 if (*str_off_ptr == 0)
1377 return 0;
1378
1379 strs = ctx;
1380 s = bsearch(strs->data + *str_off_ptr, strs->ptrs, strs->cnt,
1381 sizeof(struct btf_str_ptr), btf_dedup_str_ptr_cmp);
1382 if (!s)
1383 return -EINVAL;
1384 s->used = true;
1385 return 0;
1386}
1387
1388static int btf_str_remap_offset(__u32 *str_off_ptr, void *ctx)
1389{
1390 struct btf_str_ptrs *strs;
1391 struct btf_str_ptr *s;
1392
1393 if (*str_off_ptr == 0)
1394 return 0;
1395
1396 strs = ctx;
1397 s = bsearch(strs->data + *str_off_ptr, strs->ptrs, strs->cnt,
1398 sizeof(struct btf_str_ptr), btf_dedup_str_ptr_cmp);
1399 if (!s)
1400 return -EINVAL;
1401 *str_off_ptr = s->new_off;
1402 return 0;
1403}
1404
1405/*
1406 * Dedup string and filter out those that are not referenced from either .BTF
1407 * or .BTF.ext (if provided) sections.
1408 *
1409 * This is done by building index of all strings in BTF's string section,
1410 * then iterating over all entities that can reference strings (e.g., type
1411 * names, struct field names, .BTF.ext line info, etc) and marking corresponding
1412 * strings as used. After that all used strings are deduped and compacted into
1413 * sequential blob of memory and new offsets are calculated. Then all the string
1414 * references are iterated again and rewritten using new offsets.
1415 */
1416static int btf_dedup_strings(struct btf_dedup *d)
1417{
1418 const struct btf_header *hdr = d->btf->hdr;
1419 char *start = (char *)d->btf->nohdr_data + hdr->str_off;
1420 char *end = start + d->btf->hdr->str_len;
1421 char *p = start, *tmp_strs = NULL;
1422 struct btf_str_ptrs strs = {
1423 .cnt = 0,
1424 .cap = 0,
1425 .ptrs = NULL,
1426 .data = start,
1427 };
1428 int i, j, err = 0, grp_idx;
1429 bool grp_used;
1430
1431 /* build index of all strings */
1432 while (p < end) {
1433 if (strs.cnt + 1 > strs.cap) {
1434 struct btf_str_ptr *new_ptrs;
1435
1436 strs.cap += max(strs.cnt / 2, 16);
1437 new_ptrs = realloc(strs.ptrs,
1438 sizeof(strs.ptrs[0]) * strs.cap);
1439 if (!new_ptrs) {
1440 err = -ENOMEM;
1441 goto done;
1442 }
1443 strs.ptrs = new_ptrs;
1444 }
1445
1446 strs.ptrs[strs.cnt].str = p;
1447 strs.ptrs[strs.cnt].used = false;
1448
1449 p += strlen(p) + 1;
1450 strs.cnt++;
1451 }
1452
1453 /* temporary storage for deduplicated strings */
1454 tmp_strs = malloc(d->btf->hdr->str_len);
1455 if (!tmp_strs) {
1456 err = -ENOMEM;
1457 goto done;
1458 }
1459
1460 /* mark all used strings */
1461 strs.ptrs[0].used = true;
1462 err = btf_for_each_str_off(d, btf_str_mark_as_used, &strs);
1463 if (err)
1464 goto done;
1465
1466 /* sort strings by context, so that we can identify duplicates */
1467 qsort(strs.ptrs, strs.cnt, sizeof(strs.ptrs[0]), str_sort_by_content);
1468
1469 /*
1470 * iterate groups of equal strings and if any instance in a group was
1471 * referenced, emit single instance and remember new offset
1472 */
1473 p = tmp_strs;
1474 grp_idx = 0;
1475 grp_used = strs.ptrs[0].used;
1476 /* iterate past end to avoid code duplication after loop */
1477 for (i = 1; i <= strs.cnt; i++) {
1478 /*
1479 * when i == strs.cnt, we want to skip string comparison and go
1480 * straight to handling last group of strings (otherwise we'd
1481 * need to handle last group after the loop w/ duplicated code)
1482 */
1483 if (i < strs.cnt &&
1484 !strcmp(strs.ptrs[i].str, strs.ptrs[grp_idx].str)) {
1485 grp_used = grp_used || strs.ptrs[i].used;
1486 continue;
1487 }
1488
1489 /*
1490 * this check would have been required after the loop to handle
1491 * last group of strings, but due to <= condition in a loop
1492 * we avoid that duplication
1493 */
1494 if (grp_used) {
1495 int new_off = p - tmp_strs;
1496 __u32 len = strlen(strs.ptrs[grp_idx].str);
1497
1498 memmove(p, strs.ptrs[grp_idx].str, len + 1);
1499 for (j = grp_idx; j < i; j++)
1500 strs.ptrs[j].new_off = new_off;
1501 p += len + 1;
1502 }
1503
1504 if (i < strs.cnt) {
1505 grp_idx = i;
1506 grp_used = strs.ptrs[i].used;
1507 }
1508 }
1509
1510 /* replace original strings with deduped ones */
1511 d->btf->hdr->str_len = p - tmp_strs;
1512 memmove(start, tmp_strs, d->btf->hdr->str_len);
1513 end = start + d->btf->hdr->str_len;
1514
1515 /* restore original order for further binary search lookups */
1516 qsort(strs.ptrs, strs.cnt, sizeof(strs.ptrs[0]), str_sort_by_offset);
1517
1518 /* remap string offsets */
1519 err = btf_for_each_str_off(d, btf_str_remap_offset, &strs);
1520 if (err)
1521 goto done;
1522
1523 d->btf->hdr->str_len = end - start;
1524
1525done:
1526 free(tmp_strs);
1527 free(strs.ptrs);
1528 return err;
1529}
1530
1531static __u32 btf_hash_common(struct btf_type *t)
1532{
1533 __u32 h;
1534
1535 h = hash_combine(0, t->name_off);
1536 h = hash_combine(h, t->info);
1537 h = hash_combine(h, t->size);
1538 return h;
1539}
1540
1541static bool btf_equal_common(struct btf_type *t1, struct btf_type *t2)
1542{
1543 return t1->name_off == t2->name_off &&
1544 t1->info == t2->info &&
1545 t1->size == t2->size;
1546}
1547
1548/* Calculate type signature hash of INT. */
1549static __u32 btf_hash_int(struct btf_type *t)
1550{
1551 __u32 info = *(__u32 *)(t + 1);
1552 __u32 h;
1553
1554 h = btf_hash_common(t);
1555 h = hash_combine(h, info);
1556 return h;
1557}
1558
1559/* Check structural equality of two INTs. */
1560static bool btf_equal_int(struct btf_type *t1, struct btf_type *t2)
1561{
1562 __u32 info1, info2;
1563
1564 if (!btf_equal_common(t1, t2))
1565 return false;
1566 info1 = *(__u32 *)(t1 + 1);
1567 info2 = *(__u32 *)(t2 + 1);
1568 return info1 == info2;
1569}
1570
1571/* Calculate type signature hash of ENUM. */
1572static __u32 btf_hash_enum(struct btf_type *t)
1573{
1574 struct btf_enum *member = (struct btf_enum *)(t + 1);
1575 __u32 vlen = BTF_INFO_VLEN(t->info);
1576 __u32 h = btf_hash_common(t);
1577 int i;
1578
1579 for (i = 0; i < vlen; i++) {
1580 h = hash_combine(h, member->name_off);
1581 h = hash_combine(h, member->val);
1582 member++;
1583 }
1584 return h;
1585}
1586
1587/* Check structural equality of two ENUMs. */
1588static bool btf_equal_enum(struct btf_type *t1, struct btf_type *t2)
1589{
1590 struct btf_enum *m1, *m2;
1591 __u16 vlen;
1592 int i;
1593
1594 if (!btf_equal_common(t1, t2))
1595 return false;
1596
1597 vlen = BTF_INFO_VLEN(t1->info);
1598 m1 = (struct btf_enum *)(t1 + 1);
1599 m2 = (struct btf_enum *)(t2 + 1);
1600 for (i = 0; i < vlen; i++) {
1601 if (m1->name_off != m2->name_off || m1->val != m2->val)
1602 return false;
1603 m1++;
1604 m2++;
1605 }
1606 return true;
1607}
1608
1609/*
1610 * Calculate type signature hash of STRUCT/UNION, ignoring referenced type IDs,
1611 * as referenced type IDs equivalence is established separately during type
1612 * graph equivalence check algorithm.
1613 */
1614static __u32 btf_hash_struct(struct btf_type *t)
1615{
1616 struct btf_member *member = (struct btf_member *)(t + 1);
1617 __u32 vlen = BTF_INFO_VLEN(t->info);
1618 __u32 h = btf_hash_common(t);
1619 int i;
1620
1621 for (i = 0; i < vlen; i++) {
1622 h = hash_combine(h, member->name_off);
1623 h = hash_combine(h, member->offset);
1624 /* no hashing of referenced type ID, it can be unresolved yet */
1625 member++;
1626 }
1627 return h;
1628}
1629
1630/*
1631 * Check structural compatibility of two FUNC_PROTOs, ignoring referenced type
1632 * IDs. This check is performed during type graph equivalence check and
1633 * referenced types equivalence is checked separately.
1634 */
1635static bool btf_equal_struct(struct btf_type *t1, struct btf_type *t2)
1636{
1637 struct btf_member *m1, *m2;
1638 __u16 vlen;
1639 int i;
1640
1641 if (!btf_equal_common(t1, t2))
1642 return false;
1643
1644 vlen = BTF_INFO_VLEN(t1->info);
1645 m1 = (struct btf_member *)(t1 + 1);
1646 m2 = (struct btf_member *)(t2 + 1);
1647 for (i = 0; i < vlen; i++) {
1648 if (m1->name_off != m2->name_off || m1->offset != m2->offset)
1649 return false;
1650 m1++;
1651 m2++;
1652 }
1653 return true;
1654}
1655
1656/*
1657 * Calculate type signature hash of ARRAY, including referenced type IDs,
1658 * under assumption that they were already resolved to canonical type IDs and
1659 * are not going to change.
1660 */
1661static __u32 btf_hash_array(struct btf_type *t)
1662{
1663 struct btf_array *info = (struct btf_array *)(t + 1);
1664 __u32 h = btf_hash_common(t);
1665
1666 h = hash_combine(h, info->type);
1667 h = hash_combine(h, info->index_type);
1668 h = hash_combine(h, info->nelems);
1669 return h;
1670}
1671
1672/*
1673 * Check exact equality of two ARRAYs, taking into account referenced
1674 * type IDs, under assumption that they were already resolved to canonical
1675 * type IDs and are not going to change.
1676 * This function is called during reference types deduplication to compare
1677 * ARRAY to potential canonical representative.
1678 */
1679static bool btf_equal_array(struct btf_type *t1, struct btf_type *t2)
1680{
1681 struct btf_array *info1, *info2;
1682
1683 if (!btf_equal_common(t1, t2))
1684 return false;
1685
1686 info1 = (struct btf_array *)(t1 + 1);
1687 info2 = (struct btf_array *)(t2 + 1);
1688 return info1->type == info2->type &&
1689 info1->index_type == info2->index_type &&
1690 info1->nelems == info2->nelems;
1691}
1692
1693/*
1694 * Check structural compatibility of two ARRAYs, ignoring referenced type
1695 * IDs. This check is performed during type graph equivalence check and
1696 * referenced types equivalence is checked separately.
1697 */
1698static bool btf_compat_array(struct btf_type *t1, struct btf_type *t2)
1699{
1700 struct btf_array *info1, *info2;
1701
1702 if (!btf_equal_common(t1, t2))
1703 return false;
1704
1705 info1 = (struct btf_array *)(t1 + 1);
1706 info2 = (struct btf_array *)(t2 + 1);
1707 return info1->nelems == info2->nelems;
1708}
1709
1710/*
1711 * Calculate type signature hash of FUNC_PROTO, including referenced type IDs,
1712 * under assumption that they were already resolved to canonical type IDs and
1713 * are not going to change.
1714 */
1715static inline __u32 btf_hash_fnproto(struct btf_type *t)
1716{
1717 struct btf_param *member = (struct btf_param *)(t + 1);
1718 __u16 vlen = BTF_INFO_VLEN(t->info);
1719 __u32 h = btf_hash_common(t);
1720 int i;
1721
1722 for (i = 0; i < vlen; i++) {
1723 h = hash_combine(h, member->name_off);
1724 h = hash_combine(h, member->type);
1725 member++;
1726 }
1727 return h;
1728}
1729
1730/*
1731 * Check exact equality of two FUNC_PROTOs, taking into account referenced
1732 * type IDs, under assumption that they were already resolved to canonical
1733 * type IDs and are not going to change.
1734 * This function is called during reference types deduplication to compare
1735 * FUNC_PROTO to potential canonical representative.
1736 */
1737static inline bool btf_equal_fnproto(struct btf_type *t1, struct btf_type *t2)
1738{
1739 struct btf_param *m1, *m2;
1740 __u16 vlen;
1741 int i;
1742
1743 if (!btf_equal_common(t1, t2))
1744 return false;
1745
1746 vlen = BTF_INFO_VLEN(t1->info);
1747 m1 = (struct btf_param *)(t1 + 1);
1748 m2 = (struct btf_param *)(t2 + 1);
1749 for (i = 0; i < vlen; i++) {
1750 if (m1->name_off != m2->name_off || m1->type != m2->type)
1751 return false;
1752 m1++;
1753 m2++;
1754 }
1755 return true;
1756}
1757
1758/*
1759 * Check structural compatibility of two FUNC_PROTOs, ignoring referenced type
1760 * IDs. This check is performed during type graph equivalence check and
1761 * referenced types equivalence is checked separately.
1762 */
1763static inline bool btf_compat_fnproto(struct btf_type *t1, struct btf_type *t2)
1764{
1765 struct btf_param *m1, *m2;
1766 __u16 vlen;
1767 int i;
1768
1769 /* skip return type ID */
1770 if (t1->name_off != t2->name_off || t1->info != t2->info)
1771 return false;
1772
1773 vlen = BTF_INFO_VLEN(t1->info);
1774 m1 = (struct btf_param *)(t1 + 1);
1775 m2 = (struct btf_param *)(t2 + 1);
1776 for (i = 0; i < vlen; i++) {
1777 if (m1->name_off != m2->name_off)
1778 return false;
1779 m1++;
1780 m2++;
1781 }
1782 return true;
1783}
1784
1785/*
1786 * Deduplicate primitive types, that can't reference other types, by calculating
1787 * their type signature hash and comparing them with any possible canonical
1788 * candidate. If no canonical candidate matches, type itself is marked as
1789 * canonical and is added into `btf_dedup->dedup_table` as another candidate.
1790 */
1791static int btf_dedup_prim_type(struct btf_dedup *d, __u32 type_id)
1792{
1793 struct btf_type *t = d->btf->types[type_id];
1794 struct btf_type *cand;
1795 struct btf_dedup_node *cand_node;
1796 /* if we don't find equivalent type, then we are canonical */
1797 __u32 new_id = type_id;
1798 __u32 h;
1799
1800 switch (BTF_INFO_KIND(t->info)) {
1801 case BTF_KIND_CONST:
1802 case BTF_KIND_VOLATILE:
1803 case BTF_KIND_RESTRICT:
1804 case BTF_KIND_PTR:
1805 case BTF_KIND_TYPEDEF:
1806 case BTF_KIND_ARRAY:
1807 case BTF_KIND_STRUCT:
1808 case BTF_KIND_UNION:
1809 case BTF_KIND_FUNC:
1810 case BTF_KIND_FUNC_PROTO:
1811 return 0;
1812
1813 case BTF_KIND_INT:
1814 h = btf_hash_int(t);
1815 for_each_hash_node(d->dedup_table, h, cand_node) {
1816 cand = d->btf->types[cand_node->type_id];
1817 if (btf_equal_int(t, cand)) {
1818 new_id = cand_node->type_id;
1819 break;
1820 }
1821 }
1822 break;
1823
1824 case BTF_KIND_ENUM:
1825 h = btf_hash_enum(t);
1826 for_each_hash_node(d->dedup_table, h, cand_node) {
1827 cand = d->btf->types[cand_node->type_id];
1828 if (btf_equal_enum(t, cand)) {
1829 new_id = cand_node->type_id;
1830 break;
1831 }
1832 }
1833 break;
1834
1835 case BTF_KIND_FWD:
1836 h = btf_hash_common(t);
1837 for_each_hash_node(d->dedup_table, h, cand_node) {
1838 cand = d->btf->types[cand_node->type_id];
1839 if (btf_equal_common(t, cand)) {
1840 new_id = cand_node->type_id;
1841 break;
1842 }
1843 }
1844 break;
1845
1846 default:
1847 return -EINVAL;
1848 }
1849
1850 d->map[type_id] = new_id;
1851 if (type_id == new_id && btf_dedup_table_add(d, h, type_id))
1852 return -ENOMEM;
1853
1854 return 0;
1855}
1856
1857static int btf_dedup_prim_types(struct btf_dedup *d)
1858{
1859 int i, err;
1860
1861 for (i = 1; i <= d->btf->nr_types; i++) {
1862 err = btf_dedup_prim_type(d, i);
1863 if (err)
1864 return err;
1865 }
1866 return 0;
1867}
1868
1869/*
1870 * Check whether type is already mapped into canonical one (could be to itself).
1871 */
1872static inline bool is_type_mapped(struct btf_dedup *d, uint32_t type_id)
1873{
1874 return d->map[type_id] <= BTF_MAX_TYPE;
1875}
1876
1877/*
1878 * Resolve type ID into its canonical type ID, if any; otherwise return original
1879 * type ID. If type is FWD and is resolved into STRUCT/UNION already, follow
1880 * STRUCT/UNION link and resolve it into canonical type ID as well.
1881 */
1882static inline __u32 resolve_type_id(struct btf_dedup *d, __u32 type_id)
1883{
1884 while (is_type_mapped(d, type_id) && d->map[type_id] != type_id)
1885 type_id = d->map[type_id];
1886 return type_id;
1887}
1888
1889/*
1890 * Resolve FWD to underlying STRUCT/UNION, if any; otherwise return original
1891 * type ID.
1892 */
1893static uint32_t resolve_fwd_id(struct btf_dedup *d, uint32_t type_id)
1894{
1895 __u32 orig_type_id = type_id;
1896
1897 if (BTF_INFO_KIND(d->btf->types[type_id]->info) != BTF_KIND_FWD)
1898 return type_id;
1899
1900 while (is_type_mapped(d, type_id) && d->map[type_id] != type_id)
1901 type_id = d->map[type_id];
1902
1903 if (BTF_INFO_KIND(d->btf->types[type_id]->info) != BTF_KIND_FWD)
1904 return type_id;
1905
1906 return orig_type_id;
1907}
1908
1909
1910static inline __u16 btf_fwd_kind(struct btf_type *t)
1911{
1912 return BTF_INFO_KFLAG(t->info) ? BTF_KIND_UNION : BTF_KIND_STRUCT;
1913}
1914
1915/*
1916 * Check equivalence of BTF type graph formed by candidate struct/union (we'll
1917 * call it "candidate graph" in this description for brevity) to a type graph
1918 * formed by (potential) canonical struct/union ("canonical graph" for brevity
1919 * here, though keep in mind that not all types in canonical graph are
1920 * necessarily canonical representatives themselves, some of them might be
1921 * duplicates or its uniqueness might not have been established yet).
1922 * Returns:
1923 * - >0, if type graphs are equivalent;
1924 * - 0, if not equivalent;
1925 * - <0, on error.
1926 *
1927 * Algorithm performs side-by-side DFS traversal of both type graphs and checks
1928 * equivalence of BTF types at each step. If at any point BTF types in candidate
1929 * and canonical graphs are not compatible structurally, whole graphs are
1930 * incompatible. If types are structurally equivalent (i.e., all information
1931 * except referenced type IDs is exactly the same), a mapping from `canon_id` to
1932 * a `cand_id` is recored in hypothetical mapping (`btf_dedup->hypot_map`).
1933 * If a type references other types, then those referenced types are checked
1934 * for equivalence recursively.
1935 *
1936 * During DFS traversal, if we find that for current `canon_id` type we
1937 * already have some mapping in hypothetical map, we check for two possible
1938 * situations:
1939 * - `canon_id` is mapped to exactly the same type as `cand_id`. This will
1940 * happen when type graphs have cycles. In this case we assume those two
1941 * types are equivalent.
1942 * - `canon_id` is mapped to different type. This is contradiction in our
1943 * hypothetical mapping, because same graph in canonical graph corresponds
1944 * to two different types in candidate graph, which for equivalent type
1945 * graphs shouldn't happen. This condition terminates equivalence check
1946 * with negative result.
1947 *
1948 * If type graphs traversal exhausts types to check and find no contradiction,
1949 * then type graphs are equivalent.
1950 *
1951 * When checking types for equivalence, there is one special case: FWD types.
1952 * If FWD type resolution is allowed and one of the types (either from canonical
1953 * or candidate graph) is FWD and other is STRUCT/UNION (depending on FWD's kind
1954 * flag) and their names match, hypothetical mapping is updated to point from
1955 * FWD to STRUCT/UNION. If graphs will be determined as equivalent successfully,
1956 * this mapping will be used to record FWD -> STRUCT/UNION mapping permanently.
1957 *
1958 * Technically, this could lead to incorrect FWD to STRUCT/UNION resolution,
1959 * if there are two exactly named (or anonymous) structs/unions that are
1960 * compatible structurally, one of which has FWD field, while other is concrete
1961 * STRUCT/UNION, but according to C sources they are different structs/unions
1962 * that are referencing different types with the same name. This is extremely
1963 * unlikely to happen, but btf_dedup API allows to disable FWD resolution if
1964 * this logic is causing problems.
1965 *
1966 * Doing FWD resolution means that both candidate and/or canonical graphs can
1967 * consists of portions of the graph that come from multiple compilation units.
1968 * This is due to the fact that types within single compilation unit are always
1969 * deduplicated and FWDs are already resolved, if referenced struct/union
1970 * definiton is available. So, if we had unresolved FWD and found corresponding
1971 * STRUCT/UNION, they will be from different compilation units. This
1972 * consequently means that when we "link" FWD to corresponding STRUCT/UNION,
1973 * type graph will likely have at least two different BTF types that describe
1974 * same type (e.g., most probably there will be two different BTF types for the
1975 * same 'int' primitive type) and could even have "overlapping" parts of type
1976 * graph that describe same subset of types.
1977 *
1978 * This in turn means that our assumption that each type in canonical graph
1979 * must correspond to exactly one type in candidate graph might not hold
1980 * anymore and will make it harder to detect contradictions using hypothetical
1981 * map. To handle this problem, we allow to follow FWD -> STRUCT/UNION
1982 * resolution only in canonical graph. FWDs in candidate graphs are never
1983 * resolved. To see why it's OK, let's check all possible situations w.r.t. FWDs
1984 * that can occur:
1985 * - Both types in canonical and candidate graphs are FWDs. If they are
1986 * structurally equivalent, then they can either be both resolved to the
1987 * same STRUCT/UNION or not resolved at all. In both cases they are
1988 * equivalent and there is no need to resolve FWD on candidate side.
1989 * - Both types in canonical and candidate graphs are concrete STRUCT/UNION,
1990 * so nothing to resolve as well, algorithm will check equivalence anyway.
1991 * - Type in canonical graph is FWD, while type in candidate is concrete
1992 * STRUCT/UNION. In this case candidate graph comes from single compilation
1993 * unit, so there is exactly one BTF type for each unique C type. After
1994 * resolving FWD into STRUCT/UNION, there might be more than one BTF type
1995 * in canonical graph mapping to single BTF type in candidate graph, but
1996 * because hypothetical mapping maps from canonical to candidate types, it's
1997 * alright, and we still maintain the property of having single `canon_id`
1998 * mapping to single `cand_id` (there could be two different `canon_id`
1999 * mapped to the same `cand_id`, but it's not contradictory).
2000 * - Type in canonical graph is concrete STRUCT/UNION, while type in candidate
2001 * graph is FWD. In this case we are just going to check compatibility of
2002 * STRUCT/UNION and corresponding FWD, and if they are compatible, we'll
2003 * assume that whatever STRUCT/UNION FWD resolves to must be equivalent to
2004 * a concrete STRUCT/UNION from canonical graph. If the rest of type graphs
2005 * turn out equivalent, we'll re-resolve FWD to concrete STRUCT/UNION from
2006 * canonical graph.
2007 */
2008static int btf_dedup_is_equiv(struct btf_dedup *d, __u32 cand_id,
2009 __u32 canon_id)
2010{
2011 struct btf_type *cand_type;
2012 struct btf_type *canon_type;
2013 __u32 hypot_type_id;
2014 __u16 cand_kind;
2015 __u16 canon_kind;
2016 int i, eq;
2017
2018 /* if both resolve to the same canonical, they must be equivalent */
2019 if (resolve_type_id(d, cand_id) == resolve_type_id(d, canon_id))
2020 return 1;
2021
2022 canon_id = resolve_fwd_id(d, canon_id);
2023
2024 hypot_type_id = d->hypot_map[canon_id];
2025 if (hypot_type_id <= BTF_MAX_TYPE)
2026 return hypot_type_id == cand_id;
2027
2028 if (btf_dedup_hypot_map_add(d, canon_id, cand_id))
2029 return -ENOMEM;
2030
2031 cand_type = d->btf->types[cand_id];
2032 canon_type = d->btf->types[canon_id];
2033 cand_kind = BTF_INFO_KIND(cand_type->info);
2034 canon_kind = BTF_INFO_KIND(canon_type->info);
2035
2036 if (cand_type->name_off != canon_type->name_off)
2037 return 0;
2038
2039 /* FWD <--> STRUCT/UNION equivalence check, if enabled */
2040 if (!d->opts.dont_resolve_fwds
2041 && (cand_kind == BTF_KIND_FWD || canon_kind == BTF_KIND_FWD)
2042 && cand_kind != canon_kind) {
2043 __u16 real_kind;
2044 __u16 fwd_kind;
2045
2046 if (cand_kind == BTF_KIND_FWD) {
2047 real_kind = canon_kind;
2048 fwd_kind = btf_fwd_kind(cand_type);
2049 } else {
2050 real_kind = cand_kind;
2051 fwd_kind = btf_fwd_kind(canon_type);
2052 }
2053 return fwd_kind == real_kind;
2054 }
2055
2056 if (cand_type->info != canon_type->info)
2057 return 0;
2058
2059 switch (cand_kind) {
2060 case BTF_KIND_INT:
2061 return btf_equal_int(cand_type, canon_type);
2062
2063 case BTF_KIND_ENUM:
2064 return btf_equal_enum(cand_type, canon_type);
2065
2066 case BTF_KIND_FWD:
2067 return btf_equal_common(cand_type, canon_type);
2068
2069 case BTF_KIND_CONST:
2070 case BTF_KIND_VOLATILE:
2071 case BTF_KIND_RESTRICT:
2072 case BTF_KIND_PTR:
2073 case BTF_KIND_TYPEDEF:
2074 case BTF_KIND_FUNC:
2075 return btf_dedup_is_equiv(d, cand_type->type, canon_type->type);
2076
2077 case BTF_KIND_ARRAY: {
2078 struct btf_array *cand_arr, *canon_arr;
2079
2080 if (!btf_compat_array(cand_type, canon_type))
2081 return 0;
2082 cand_arr = (struct btf_array *)(cand_type + 1);
2083 canon_arr = (struct btf_array *)(canon_type + 1);
2084 eq = btf_dedup_is_equiv(d,
2085 cand_arr->index_type, canon_arr->index_type);
2086 if (eq <= 0)
2087 return eq;
2088 return btf_dedup_is_equiv(d, cand_arr->type, canon_arr->type);
2089 }
2090
2091 case BTF_KIND_STRUCT:
2092 case BTF_KIND_UNION: {
2093 struct btf_member *cand_m, *canon_m;
2094 __u16 vlen;
2095
2096 if (!btf_equal_struct(cand_type, canon_type))
2097 return 0;
2098 vlen = BTF_INFO_VLEN(cand_type->info);
2099 cand_m = (struct btf_member *)(cand_type + 1);
2100 canon_m = (struct btf_member *)(canon_type + 1);
2101 for (i = 0; i < vlen; i++) {
2102 eq = btf_dedup_is_equiv(d, cand_m->type, canon_m->type);
2103 if (eq <= 0)
2104 return eq;
2105 cand_m++;
2106 canon_m++;
2107 }
2108
2109 return 1;
2110 }
2111
2112 case BTF_KIND_FUNC_PROTO: {
2113 struct btf_param *cand_p, *canon_p;
2114 __u16 vlen;
2115
2116 if (!btf_compat_fnproto(cand_type, canon_type))
2117 return 0;
2118 eq = btf_dedup_is_equiv(d, cand_type->type, canon_type->type);
2119 if (eq <= 0)
2120 return eq;
2121 vlen = BTF_INFO_VLEN(cand_type->info);
2122 cand_p = (struct btf_param *)(cand_type + 1);
2123 canon_p = (struct btf_param *)(canon_type + 1);
2124 for (i = 0; i < vlen; i++) {
2125 eq = btf_dedup_is_equiv(d, cand_p->type, canon_p->type);
2126 if (eq <= 0)
2127 return eq;
2128 cand_p++;
2129 canon_p++;
2130 }
2131 return 1;
2132 }
2133
2134 default:
2135 return -EINVAL;
2136 }
2137 return 0;
2138}
2139
2140/*
2141 * Use hypothetical mapping, produced by successful type graph equivalence
2142 * check, to augment existing struct/union canonical mapping, where possible.
2143 *
2144 * If BTF_KIND_FWD resolution is allowed, this mapping is also used to record
2145 * FWD -> STRUCT/UNION correspondence as well. FWD resolution is bidirectional:
2146 * it doesn't matter if FWD type was part of canonical graph or candidate one,
2147 * we are recording the mapping anyway. As opposed to carefulness required
2148 * for struct/union correspondence mapping (described below), for FWD resolution
2149 * it's not important, as by the time that FWD type (reference type) will be
2150 * deduplicated all structs/unions will be deduped already anyway.
2151 *
2152 * Recording STRUCT/UNION mapping is purely a performance optimization and is
2153 * not required for correctness. It needs to be done carefully to ensure that
2154 * struct/union from candidate's type graph is not mapped into corresponding
2155 * struct/union from canonical type graph that itself hasn't been resolved into
2156 * canonical representative. The only guarantee we have is that canonical
2157 * struct/union was determined as canonical and that won't change. But any
2158 * types referenced through that struct/union fields could have been not yet
2159 * resolved, so in case like that it's too early to establish any kind of
2160 * correspondence between structs/unions.
2161 *
2162 * No canonical correspondence is derived for primitive types (they are already
2163 * deduplicated completely already anyway) or reference types (they rely on
2164 * stability of struct/union canonical relationship for equivalence checks).
2165 */
2166static void btf_dedup_merge_hypot_map(struct btf_dedup *d)
2167{
2168 __u32 cand_type_id, targ_type_id;
2169 __u16 t_kind, c_kind;
2170 __u32 t_id, c_id;
2171 int i;
2172
2173 for (i = 0; i < d->hypot_cnt; i++) {
2174 cand_type_id = d->hypot_list[i];
2175 targ_type_id = d->hypot_map[cand_type_id];
2176 t_id = resolve_type_id(d, targ_type_id);
2177 c_id = resolve_type_id(d, cand_type_id);
2178 t_kind = BTF_INFO_KIND(d->btf->types[t_id]->info);
2179 c_kind = BTF_INFO_KIND(d->btf->types[c_id]->info);
2180 /*
2181 * Resolve FWD into STRUCT/UNION.
2182 * It's ok to resolve FWD into STRUCT/UNION that's not yet
2183 * mapped to canonical representative (as opposed to
2184 * STRUCT/UNION <--> STRUCT/UNION mapping logic below), because
2185 * eventually that struct is going to be mapped and all resolved
2186 * FWDs will automatically resolve to correct canonical
2187 * representative. This will happen before ref type deduping,
2188 * which critically depends on stability of these mapping. This
2189 * stability is not a requirement for STRUCT/UNION equivalence
2190 * checks, though.
2191 */
2192 if (t_kind != BTF_KIND_FWD && c_kind == BTF_KIND_FWD)
2193 d->map[c_id] = t_id;
2194 else if (t_kind == BTF_KIND_FWD && c_kind != BTF_KIND_FWD)
2195 d->map[t_id] = c_id;
2196
2197 if ((t_kind == BTF_KIND_STRUCT || t_kind == BTF_KIND_UNION) &&
2198 c_kind != BTF_KIND_FWD &&
2199 is_type_mapped(d, c_id) &&
2200 !is_type_mapped(d, t_id)) {
2201 /*
2202 * as a perf optimization, we can map struct/union
2203 * that's part of type graph we just verified for
2204 * equivalence. We can do that for struct/union that has
2205 * canonical representative only, though.
2206 */
2207 d->map[t_id] = c_id;
2208 }
2209 }
2210}
2211
2212/*
2213 * Deduplicate struct/union types.
2214 *
2215 * For each struct/union type its type signature hash is calculated, taking
2216 * into account type's name, size, number, order and names of fields, but
2217 * ignoring type ID's referenced from fields, because they might not be deduped
2218 * completely until after reference types deduplication phase. This type hash
2219 * is used to iterate over all potential canonical types, sharing same hash.
2220 * For each canonical candidate we check whether type graphs that they form
2221 * (through referenced types in fields and so on) are equivalent using algorithm
2222 * implemented in `btf_dedup_is_equiv`. If such equivalence is found and
2223 * BTF_KIND_FWD resolution is allowed, then hypothetical mapping
2224 * (btf_dedup->hypot_map) produced by aforementioned type graph equivalence
2225 * algorithm is used to record FWD -> STRUCT/UNION mapping. It's also used to
2226 * potentially map other structs/unions to their canonical representatives,
2227 * if such relationship hasn't yet been established. This speeds up algorithm
2228 * by eliminating some of the duplicate work.
2229 *
2230 * If no matching canonical representative was found, struct/union is marked
2231 * as canonical for itself and is added into btf_dedup->dedup_table hash map
2232 * for further look ups.
2233 */
2234static int btf_dedup_struct_type(struct btf_dedup *d, __u32 type_id)
2235{
2236 struct btf_dedup_node *cand_node;
2237 struct btf_type *t;
2238 /* if we don't find equivalent type, then we are canonical */
2239 __u32 new_id = type_id;
2240 __u16 kind;
2241 __u32 h;
2242
2243 /* already deduped or is in process of deduping (loop detected) */
2244 if (d->map[type_id] <= BTF_MAX_TYPE)
2245 return 0;
2246
2247 t = d->btf->types[type_id];
2248 kind = BTF_INFO_KIND(t->info);
2249
2250 if (kind != BTF_KIND_STRUCT && kind != BTF_KIND_UNION)
2251 return 0;
2252
2253 h = btf_hash_struct(t);
2254 for_each_hash_node(d->dedup_table, h, cand_node) {
2255 int eq;
2256
2257 btf_dedup_clear_hypot_map(d);
2258 eq = btf_dedup_is_equiv(d, type_id, cand_node->type_id);
2259 if (eq < 0)
2260 return eq;
2261 if (!eq)
2262 continue;
2263 new_id = cand_node->type_id;
2264 btf_dedup_merge_hypot_map(d);
2265 break;
2266 }
2267
2268 d->map[type_id] = new_id;
2269 if (type_id == new_id && btf_dedup_table_add(d, h, type_id))
2270 return -ENOMEM;
2271
2272 return 0;
2273}
2274
2275static int btf_dedup_struct_types(struct btf_dedup *d)
2276{
2277 int i, err;
2278
2279 for (i = 1; i <= d->btf->nr_types; i++) {
2280 err = btf_dedup_struct_type(d, i);
2281 if (err)
2282 return err;
2283 }
2284 return 0;
2285}
2286
2287/*
2288 * Deduplicate reference type.
2289 *
2290 * Once all primitive and struct/union types got deduplicated, we can easily
2291 * deduplicate all other (reference) BTF types. This is done in two steps:
2292 *
2293 * 1. Resolve all referenced type IDs into their canonical type IDs. This
2294 * resolution can be done either immediately for primitive or struct/union types
2295 * (because they were deduped in previous two phases) or recursively for
2296 * reference types. Recursion will always terminate at either primitive or
2297 * struct/union type, at which point we can "unwind" chain of reference types
2298 * one by one. There is no danger of encountering cycles because in C type
2299 * system the only way to form type cycle is through struct/union, so any chain
2300 * of reference types, even those taking part in a type cycle, will inevitably
2301 * reach struct/union at some point.
2302 *
2303 * 2. Once all referenced type IDs are resolved into canonical ones, BTF type
2304 * becomes "stable", in the sense that no further deduplication will cause
2305 * any changes to it. With that, it's now possible to calculate type's signature
2306 * hash (this time taking into account referenced type IDs) and loop over all
2307 * potential canonical representatives. If no match was found, current type
2308 * will become canonical representative of itself and will be added into
2309 * btf_dedup->dedup_table as another possible canonical representative.
2310 */
2311static int btf_dedup_ref_type(struct btf_dedup *d, __u32 type_id)
2312{
2313 struct btf_dedup_node *cand_node;
2314 struct btf_type *t, *cand;
2315 /* if we don't find equivalent type, then we are representative type */
2316 __u32 new_id = type_id;
2317 __u32 h, ref_type_id;
2318
2319 if (d->map[type_id] == BTF_IN_PROGRESS_ID)
2320 return -ELOOP;
2321 if (d->map[type_id] <= BTF_MAX_TYPE)
2322 return resolve_type_id(d, type_id);
2323
2324 t = d->btf->types[type_id];
2325 d->map[type_id] = BTF_IN_PROGRESS_ID;
2326
2327 switch (BTF_INFO_KIND(t->info)) {
2328 case BTF_KIND_CONST:
2329 case BTF_KIND_VOLATILE:
2330 case BTF_KIND_RESTRICT:
2331 case BTF_KIND_PTR:
2332 case BTF_KIND_TYPEDEF:
2333 case BTF_KIND_FUNC:
2334 ref_type_id = btf_dedup_ref_type(d, t->type);
2335 if (ref_type_id < 0)
2336 return ref_type_id;
2337 t->type = ref_type_id;
2338
2339 h = btf_hash_common(t);
2340 for_each_hash_node(d->dedup_table, h, cand_node) {
2341 cand = d->btf->types[cand_node->type_id];
2342 if (btf_equal_common(t, cand)) {
2343 new_id = cand_node->type_id;
2344 break;
2345 }
2346 }
2347 break;
2348
2349 case BTF_KIND_ARRAY: {
2350 struct btf_array *info = (struct btf_array *)(t + 1);
2351
2352 ref_type_id = btf_dedup_ref_type(d, info->type);
2353 if (ref_type_id < 0)
2354 return ref_type_id;
2355 info->type = ref_type_id;
2356
2357 ref_type_id = btf_dedup_ref_type(d, info->index_type);
2358 if (ref_type_id < 0)
2359 return ref_type_id;
2360 info->index_type = ref_type_id;
2361
2362 h = btf_hash_array(t);
2363 for_each_hash_node(d->dedup_table, h, cand_node) {
2364 cand = d->btf->types[cand_node->type_id];
2365 if (btf_equal_array(t, cand)) {
2366 new_id = cand_node->type_id;
2367 break;
2368 }
2369 }
2370 break;
2371 }
2372
2373 case BTF_KIND_FUNC_PROTO: {
2374 struct btf_param *param;
2375 __u16 vlen;
2376 int i;
2377
2378 ref_type_id = btf_dedup_ref_type(d, t->type);
2379 if (ref_type_id < 0)
2380 return ref_type_id;
2381 t->type = ref_type_id;
2382
2383 vlen = BTF_INFO_VLEN(t->info);
2384 param = (struct btf_param *)(t + 1);
2385 for (i = 0; i < vlen; i++) {
2386 ref_type_id = btf_dedup_ref_type(d, param->type);
2387 if (ref_type_id < 0)
2388 return ref_type_id;
2389 param->type = ref_type_id;
2390 param++;
2391 }
2392
2393 h = btf_hash_fnproto(t);
2394 for_each_hash_node(d->dedup_table, h, cand_node) {
2395 cand = d->btf->types[cand_node->type_id];
2396 if (btf_equal_fnproto(t, cand)) {
2397 new_id = cand_node->type_id;
2398 break;
2399 }
2400 }
2401 break;
2402 }
2403
2404 default:
2405 return -EINVAL;
2406 }
2407
2408 d->map[type_id] = new_id;
2409 if (type_id == new_id && btf_dedup_table_add(d, h, type_id))
2410 return -ENOMEM;
2411
2412 return new_id;
2413}
2414
2415static int btf_dedup_ref_types(struct btf_dedup *d)
2416{
2417 int i, err;
2418
2419 for (i = 1; i <= d->btf->nr_types; i++) {
2420 err = btf_dedup_ref_type(d, i);
2421 if (err < 0)
2422 return err;
2423 }
2424 btf_dedup_table_free(d);
2425 return 0;
2426}
2427
2428/*
2429 * Compact types.
2430 *
2431 * After we established for each type its corresponding canonical representative
2432 * type, we now can eliminate types that are not canonical and leave only
2433 * canonical ones layed out sequentially in memory by copying them over
2434 * duplicates. During compaction btf_dedup->hypot_map array is reused to store
2435 * a map from original type ID to a new compacted type ID, which will be used
2436 * during next phase to "fix up" type IDs, referenced from struct/union and
2437 * reference types.
2438 */
2439static int btf_dedup_compact_types(struct btf_dedup *d)
2440{
2441 struct btf_type **new_types;
2442 __u32 next_type_id = 1;
2443 char *types_start, *p;
2444 int i, len;
2445
2446 /* we are going to reuse hypot_map to store compaction remapping */
2447 d->hypot_map[0] = 0;
2448 for (i = 1; i <= d->btf->nr_types; i++)
2449 d->hypot_map[i] = BTF_UNPROCESSED_ID;
2450
2451 types_start = d->btf->nohdr_data + d->btf->hdr->type_off;
2452 p = types_start;
2453
2454 for (i = 1; i <= d->btf->nr_types; i++) {
2455 if (d->map[i] != i)
2456 continue;
2457
2458 len = btf_type_size(d->btf->types[i]);
2459 if (len < 0)
2460 return len;
2461
2462 memmove(p, d->btf->types[i], len);
2463 d->hypot_map[i] = next_type_id;
2464 d->btf->types[next_type_id] = (struct btf_type *)p;
2465 p += len;
2466 next_type_id++;
2467 }
2468
2469 /* shrink struct btf's internal types index and update btf_header */
2470 d->btf->nr_types = next_type_id - 1;
2471 d->btf->types_size = d->btf->nr_types;
2472 d->btf->hdr->type_len = p - types_start;
2473 new_types = realloc(d->btf->types,
2474 (1 + d->btf->nr_types) * sizeof(struct btf_type *));
2475 if (!new_types)
2476 return -ENOMEM;
2477 d->btf->types = new_types;
2478
2479 /* make sure string section follows type information without gaps */
2480 d->btf->hdr->str_off = p - (char *)d->btf->nohdr_data;
2481 memmove(p, d->btf->strings, d->btf->hdr->str_len);
2482 d->btf->strings = p;
2483 p += d->btf->hdr->str_len;
2484
2485 d->btf->data_size = p - (char *)d->btf->data;
2486 return 0;
2487}
2488
2489/*
2490 * Figure out final (deduplicated and compacted) type ID for provided original
2491 * `type_id` by first resolving it into corresponding canonical type ID and
2492 * then mapping it to a deduplicated type ID, stored in btf_dedup->hypot_map,
2493 * which is populated during compaction phase.
2494 */
2495static int btf_dedup_remap_type_id(struct btf_dedup *d, __u32 type_id)
2496{
2497 __u32 resolved_type_id, new_type_id;
2498
2499 resolved_type_id = resolve_type_id(d, type_id);
2500 new_type_id = d->hypot_map[resolved_type_id];
2501 if (new_type_id > BTF_MAX_TYPE)
2502 return -EINVAL;
2503 return new_type_id;
2504}
2505
2506/*
2507 * Remap referenced type IDs into deduped type IDs.
2508 *
2509 * After BTF types are deduplicated and compacted, their final type IDs may
2510 * differ from original ones. The map from original to a corresponding
2511 * deduped type ID is stored in btf_dedup->hypot_map and is populated during
2512 * compaction phase. During remapping phase we are rewriting all type IDs
2513 * referenced from any BTF type (e.g., struct fields, func proto args, etc) to
2514 * their final deduped type IDs.
2515 */
2516static int btf_dedup_remap_type(struct btf_dedup *d, __u32 type_id)
2517{
2518 struct btf_type *t = d->btf->types[type_id];
2519 int i, r;
2520
2521 switch (BTF_INFO_KIND(t->info)) {
2522 case BTF_KIND_INT:
2523 case BTF_KIND_ENUM:
2524 break;
2525
2526 case BTF_KIND_FWD:
2527 case BTF_KIND_CONST:
2528 case BTF_KIND_VOLATILE:
2529 case BTF_KIND_RESTRICT:
2530 case BTF_KIND_PTR:
2531 case BTF_KIND_TYPEDEF:
2532 case BTF_KIND_FUNC:
2533 r = btf_dedup_remap_type_id(d, t->type);
2534 if (r < 0)
2535 return r;
2536 t->type = r;
2537 break;
2538
2539 case BTF_KIND_ARRAY: {
2540 struct btf_array *arr_info = (struct btf_array *)(t + 1);
2541
2542 r = btf_dedup_remap_type_id(d, arr_info->type);
2543 if (r < 0)
2544 return r;
2545 arr_info->type = r;
2546 r = btf_dedup_remap_type_id(d, arr_info->index_type);
2547 if (r < 0)
2548 return r;
2549 arr_info->index_type = r;
2550 break;
2551 }
2552
2553 case BTF_KIND_STRUCT:
2554 case BTF_KIND_UNION: {
2555 struct btf_member *member = (struct btf_member *)(t + 1);
2556 __u16 vlen = BTF_INFO_VLEN(t->info);
2557
2558 for (i = 0; i < vlen; i++) {
2559 r = btf_dedup_remap_type_id(d, member->type);
2560 if (r < 0)
2561 return r;
2562 member->type = r;
2563 member++;
2564 }
2565 break;
2566 }
2567
2568 case BTF_KIND_FUNC_PROTO: {
2569 struct btf_param *param = (struct btf_param *)(t + 1);
2570 __u16 vlen = BTF_INFO_VLEN(t->info);
2571
2572 r = btf_dedup_remap_type_id(d, t->type);
2573 if (r < 0)
2574 return r;
2575 t->type = r;
2576
2577 for (i = 0; i < vlen; i++) {
2578 r = btf_dedup_remap_type_id(d, param->type);
2579 if (r < 0)
2580 return r;
2581 param->type = r;
2582 param++;
2583 }
2584 break;
2585 }
2586
2587 default:
2588 return -EINVAL;
2589 }
2590
2591 return 0;
2592}
2593
2594static int btf_dedup_remap_types(struct btf_dedup *d)
2595{
2596 int i, r;
2597
2598 for (i = 1; i <= d->btf->nr_types; i++) {
2599 r = btf_dedup_remap_type(d, i);
2600 if (r < 0)
2601 return r;
2602 }
2603 return 0;
2604}
generated by cgit v1.2.2 (git 2.25.0) at 2025-10-06 15:33:39 -0400