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