tools/lib/bpf/btf.c

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