tools/lib/bpf/btf.c

   1 // SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)
   2 /* Copyright (c) 2018 Facebook */
   3
   4 #include <byteswap.h>
   5 #include <endian.h>
   6 #include <stdio.h>
   7 #include <stdlib.h>
   8 #include <string.h>
   9 #include <fcntl.h>
  10 #include <unistd.h>
  11 #include <errno.h>
  12 #include <sys/utsname.h>
  13 #include <sys/param.h>
  14 #include <sys/stat.h>
  15 #include <linux/kernel.h>
  16 #include <linux/err.h>
  17 #include <linux/btf.h>
  18 #include <gelf.h>
  19 #include "btf.h"
  20 #include "bpf.h"
  21 #include "libbpf.h"
  22 #include "libbpf_internal.h"
  23 #include "hashmap.h"
  24
  25 #define BTF_MAX_NR_TYPES 0x7fffffffU
  26 #define BTF_MAX_STR_OFFSET 0x7fffffffU
  27
  28 static struct btf_type btf_void;
  29
  30 struct btf {
  31         /* raw BTF data in native endianness */
  32         void *raw_data;
  33         /* raw BTF data in non-native endianness */
  34         void *raw_data_swapped;
  35         __u32 raw_size;
  36         /* whether target endianness differs from the native one */
  37         bool swapped_endian;
  38
  39         /*
  40          * When BTF is loaded from an ELF or raw memory it is stored
  41          * in a contiguous memory block. The hdr, type_data, and, strs_data
  42          * point inside that memory region to their respective parts of BTF
  43          * representation:
  44          *
  45          * +--------------------------------+
  46          * |  Header  |  Types  |  Strings  |
  47          * +--------------------------------+
  48          * ^          ^         ^
  49          * |          |         |
  50          * hdr        |         |
  51          * types_data-+         |
  52          * strs_data------------+
  53          *
  54          * If BTF data is later modified, e.g., due to types added or
  55          * removed, BTF deduplication performed, etc, this contiguous
  56          * representation is broken up into three independently allocated
  57          * memory regions to be able to modify them independently.
  58          * raw_data is nulled out at that point, but can be later allocated
  59          * and cached again if user calls btf__get_raw_data(), at which point
  60          * raw_data will contain a contiguous copy of header, types, and
  61          * strings:
  62          *
  63          * +----------+  +---------+  +-----------+
  64          * |  Header  |  |  Types  |  |  Strings  |
  65          * +----------+  +---------+  +-----------+
  66          * ^             ^            ^
  67          * |             |            |
  68          * hdr           |            |
  69          * types_data----+            |
  70          * strs_data------------------+
  71          *
  72          *               +----------+---------+-----------+
  73          *               |  Header  |  Types  |  Strings  |
  74          * raw_data----->+----------+---------+-----------+
  75          */
  76         struct btf_header *hdr;
  77
  78         void *types_data;
  79         size_t types_data_cap; /* used size stored in hdr->type_len */
  80
  81         /* type ID to `struct btf_type *` lookup index */
  82         __u32 *type_offs;
  83         size_t type_offs_cap;
  84         __u32 nr_types;
  85
  86         void *strs_data;
  87         size_t strs_data_cap; /* used size stored in hdr->str_len */
  88
  89         /* lookup index for each unique string in strings section */
  90         struct hashmap *strs_hash;
  91         /* whether strings are already deduplicated */
  92         bool strs_deduped;
  93         /* BTF object FD, if loaded into kernel */
  94         int fd;
  95
  96         /* Pointer size (in bytes) for a target architecture of this BTF */
  97         int ptr_sz;
  98 };
  99
 100 static inline __u64 ptr_to_u64(const void *ptr)
 101 {
 102         return (__u64) (unsigned long) ptr;
 103 }
 104
 105 /* Ensure given dynamically allocated memory region pointed to by *data* with
 106  * capacity of *cap_cnt* elements each taking *elem_sz* bytes has enough
 107  * memory to accomodate *add_cnt* new elements, assuming *cur_cnt* elements
 108  * are already used. At most *max_cnt* elements can be ever allocated.
 109  * If necessary, memory is reallocated and all existing data is copied over,
 110  * new pointer to the memory region is stored at *data, new memory region
 111  * capacity (in number of elements) is stored in *cap.
 112  * On success, memory pointer to the beginning of unused memory is returned.
 113  * On error, NULL is returned.
 114  */
 115 void *btf_add_mem(void **data, size_t *cap_cnt, size_t elem_sz,
 116                   size_t cur_cnt, size_t max_cnt, size_t add_cnt)
 117 {
 118         size_t new_cnt;
 119         void *new_data;
 120
 121         if (cur_cnt + add_cnt <= *cap_cnt)
 122                 return *data + cur_cnt * elem_sz;
 123
 124         /* requested more than the set limit */
 125         if (cur_cnt + add_cnt > max_cnt)
 126                 return NULL;
 127
 128         new_cnt = *cap_cnt;
 129         new_cnt += new_cnt / 4;           /* expand by 25% */
 130         if (new_cnt < 16)                 /* but at least 16 elements */
 131                 new_cnt = 16;
 132         if (new_cnt > max_cnt)            /* but not exceeding a set limit */
 133                 new_cnt = max_cnt;
 134         if (new_cnt < cur_cnt + add_cnt)  /* also ensure we have enough memory */
 135                 new_cnt = cur_cnt + add_cnt;
 136
 137         new_data = libbpf_reallocarray(*data, new_cnt, elem_sz);
 138         if (!new_data)
 139                 return NULL;
 140
 141         /* zero out newly allocated portion of memory */
 142         memset(new_data + (*cap_cnt) * elem_sz, 0, (new_cnt - *cap_cnt) * elem_sz);
 143
 144         *data = new_data;
 145         *cap_cnt = new_cnt;
 146         return new_data + cur_cnt * elem_sz;
 147 }
 148
 149 /* Ensure given dynamically allocated memory region has enough allocated space
 150  * to accommodate *need_cnt* elements of size *elem_sz* bytes each
 151  */
 152 int btf_ensure_mem(void **data, size_t *cap_cnt, size_t elem_sz, size_t need_cnt)
 153 {
 154         void *p;
 155
 156         if (need_cnt <= *cap_cnt)
 157                 return 0;
 158
 159         p = btf_add_mem(data, cap_cnt, elem_sz, *cap_cnt, SIZE_MAX, need_cnt - *cap_cnt);
 160         if (!p)
 161                 return -ENOMEM;
 162
 163         return 0;
 164 }
 165
 166 static int btf_add_type_idx_entry(struct btf *btf, __u32 type_off)
 167 {
 168         __u32 *p;
 169
 170         p = btf_add_mem((void **)&btf->type_offs, &btf->type_offs_cap, sizeof(__u32),
 171                         btf->nr_types + 1, BTF_MAX_NR_TYPES, 1);
 172         if (!p)
 173                 return -ENOMEM;
 174
 175         *p = type_off;
 176         return 0;
 177 }
 178
 179 static void btf_bswap_hdr(struct btf_header *h)
 180 {
 181         h->magic = bswap_16(h->magic);
 182         h->hdr_len = bswap_32(h->hdr_len);
 183         h->type_off = bswap_32(h->type_off);
 184         h->type_len = bswap_32(h->type_len);
 185         h->str_off = bswap_32(h->str_off);
 186         h->str_len = bswap_32(h->str_len);
 187 }
 188
 189 static int btf_parse_hdr(struct btf *btf)
 190 {
 191         struct btf_header *hdr = btf->hdr;
 192         __u32 meta_left;
 193
 194         if (btf->raw_size < sizeof(struct btf_header)) {
 195                 pr_debug("BTF header not found\n");
 196                 return -EINVAL;
 197         }
 198
 199         if (hdr->magic == bswap_16(BTF_MAGIC)) {
 200                 btf->swapped_endian = true;
 201                 if (bswap_32(hdr->hdr_len) != sizeof(struct btf_header)) {
 202                         pr_warn("Can't load BTF with non-native endianness due to unsupported header length %u\n",
 203                                 bswap_32(hdr->hdr_len));
 204                         return -ENOTSUP;
 205                 }
 206                 btf_bswap_hdr(hdr);
 207         } else if (hdr->magic != BTF_MAGIC) {
 208                 pr_debug("Invalid BTF magic: %x\n", hdr->magic);
 209                 return -EINVAL;
 210         }
 211
 212         if (btf->raw_size < hdr->hdr_len) {
 213                 pr_debug("BTF header len %u larger than data size %u\n",
 214                          hdr->hdr_len, btf->raw_size);
 215                 return -EINVAL;
 216         }
 217
 218         meta_left = btf->raw_size - hdr->hdr_len;
 219         if (meta_left < (long long)hdr->str_off + hdr->str_len) {
 220                 pr_debug("Invalid BTF total size: %u\n", btf->raw_size);
 221                 return -EINVAL;
 222         }
 223
 224         if ((long long)hdr->type_off + hdr->type_len > hdr->str_off) {
 225                 pr_debug("Invalid BTF data sections layout: type data at %u + %u, strings data at %u + %u\n",
 226                          hdr->type_off, hdr->type_len, hdr->str_off, hdr->str_len);
 227                 return -EINVAL;
 228         }
 229
 230         if (hdr->type_off % 4) {
 231                 pr_debug("BTF type section is not aligned to 4 bytes\n");
 232                 return -EINVAL;
 233         }
 234
 235         return 0;
 236 }
 237
 238 static int btf_parse_str_sec(struct btf *btf)
 239 {
 240         const struct btf_header *hdr = btf->hdr;
 241         const char *start = btf->strs_data;
 242         const char *end = start + btf->hdr->str_len;
 243
 244         if (!hdr->str_len || hdr->str_len - 1 > BTF_MAX_STR_OFFSET ||
 245             start[0] || end[-1]) {
 246                 pr_debug("Invalid BTF string section\n");
 247                 return -EINVAL;
 248         }
 249
 250         return 0;
 251 }
 252
 253 static int btf_type_size(const struct btf_type *t)
 254 {
 255         const int base_size = sizeof(struct btf_type);
 256         __u16 vlen = btf_vlen(t);
 257
 258         switch (btf_kind(t)) {
 259         case BTF_KIND_FWD:
 260         case BTF_KIND_CONST:
 261         case BTF_KIND_VOLATILE:
 262         case BTF_KIND_RESTRICT:
 263         case BTF_KIND_PTR:
 264         case BTF_KIND_TYPEDEF:
 265         case BTF_KIND_FUNC:
 266                 return base_size;
 267         case BTF_KIND_INT:
 268                 return base_size + sizeof(__u32);
 269         case BTF_KIND_ENUM:
 270                 return base_size + vlen * sizeof(struct btf_enum);
 271         case BTF_KIND_ARRAY:
 272                 return base_size + sizeof(struct btf_array);
 273         case BTF_KIND_STRUCT:
 274         case BTF_KIND_UNION:
 275                 return base_size + vlen * sizeof(struct btf_member);
 276         case BTF_KIND_FUNC_PROTO:
 277                 return base_size + vlen * sizeof(struct btf_param);
 278         case BTF_KIND_VAR:
 279                 return base_size + sizeof(struct btf_var);
 280         case BTF_KIND_DATASEC:
 281                 return base_size + vlen * sizeof(struct btf_var_secinfo);
 282         default:
 283                 pr_debug("Unsupported BTF_KIND:%u\n", btf_kind(t));
 284                 return -EINVAL;
 285         }
 286 }
 287
 288 static void btf_bswap_type_base(struct btf_type *t)
 289 {
 290         t->name_off = bswap_32(t->name_off);
 291         t->info = bswap_32(t->info);
 292         t->type = bswap_32(t->type);
 293 }
 294
 295 static int btf_bswap_type_rest(struct btf_type *t)
 296 {
 297         struct btf_var_secinfo *v;
 298         struct btf_member *m;
 299         struct btf_array *a;
 300         struct btf_param *p;
 301         struct btf_enum *e;
 302         __u16 vlen = btf_vlen(t);
 303         int i;
 304
 305         switch (btf_kind(t)) {
 306         case BTF_KIND_FWD:
 307         case BTF_KIND_CONST:
 308         case BTF_KIND_VOLATILE:
 309         case BTF_KIND_RESTRICT:
 310         case BTF_KIND_PTR:
 311         case BTF_KIND_TYPEDEF:
 312         case BTF_KIND_FUNC:
 313                 return 0;
 314         case BTF_KIND_INT:
 315                 *(__u32 *)(t + 1) = bswap_32(*(__u32 *)(t + 1));
 316                 return 0;
 317         case BTF_KIND_ENUM:
 318                 for (i = 0, e = btf_enum(t); i < vlen; i++, e++) {
 319                         e->name_off = bswap_32(e->name_off);
 320                         e->val = bswap_32(e->val);
 321                 }
 322                 return 0;
 323         case BTF_KIND_ARRAY:
 324                 a = btf_array(t);
 325                 a->type = bswap_32(a->type);
 326                 a->index_type = bswap_32(a->index_type);
 327                 a->nelems = bswap_32(a->nelems);
 328                 return 0;
 329         case BTF_KIND_STRUCT:
 330         case BTF_KIND_UNION:
 331                 for (i = 0, m = btf_members(t); i < vlen; i++, m++) {
 332                         m->name_off = bswap_32(m->name_off);
 333                         m->type = bswap_32(m->type);
 334                         m->offset = bswap_32(m->offset);
 335                 }
 336                 return 0;
 337         case BTF_KIND_FUNC_PROTO:
 338                 for (i = 0, p = btf_params(t); i < vlen; i++, p++) {
 339                         p->name_off = bswap_32(p->name_off);
 340                         p->type = bswap_32(p->type);
 341                 }
 342                 return 0;
 343         case BTF_KIND_VAR:
 344                 btf_var(t)->linkage = bswap_32(btf_var(t)->linkage);
 345                 return 0;
 346         case BTF_KIND_DATASEC:
 347                 for (i = 0, v = btf_var_secinfos(t); i < vlen; i++, v++) {
 348                         v->type = bswap_32(v->type);
 349                         v->offset = bswap_32(v->offset);
 350                         v->size = bswap_32(v->size);
 351                 }
 352                 return 0;
 353         default:
 354                 pr_debug("Unsupported BTF_KIND:%u\n", btf_kind(t));
 355                 return -EINVAL;
 356         }
 357 }
 358
 359 static int btf_parse_type_sec(struct btf *btf)
 360 {
 361         struct btf_header *hdr = btf->hdr;
 362         void *next_type = btf->types_data;
 363         void *end_type = next_type + hdr->type_len;
 364         int err, i = 0, type_size;
 365
 366         /* VOID (type_id == 0) is specially handled by btf__get_type_by_id(),
 367          * so ensure we can never properly use its offset from index by
 368          * setting it to a large value
 369          */
 370         err = btf_add_type_idx_entry(btf, UINT_MAX);
 371         if (err)
 372                 return err;
 373
 374         while (next_type + sizeof(struct btf_type) <= end_type) {
 375                 i++;
 376
 377                 if (btf->swapped_endian)
 378                         btf_bswap_type_base(next_type);
 379
 380                 type_size = btf_type_size(next_type);
 381                 if (type_size < 0)
 382                         return type_size;
 383                 if (next_type + type_size > end_type) {
 384                         pr_warn("BTF type [%d] is malformed\n", i);
 385                         return -EINVAL;
 386                 }
 387
 388                 if (btf->swapped_endian && btf_bswap_type_rest(next_type))
 389                         return -EINVAL;
 390
 391                 err = btf_add_type_idx_entry(btf, next_type - btf->types_data);
 392                 if (err)
 393                         return err;
 394
 395                 next_type += type_size;
 396                 btf->nr_types++;
 397         }
 398
 399         if (next_type != end_type) {
 400                 pr_warn("BTF types data is malformed\n");
 401                 return -EINVAL;
 402         }
 403
 404         return 0;
 405 }
 406
 407 __u32 btf__get_nr_types(const struct btf *btf)
 408 {
 409         return btf->nr_types;
 410 }
 411
 412 /* internal helper returning non-const pointer to a type */
 413 static struct btf_type *btf_type_by_id(struct btf *btf, __u32 type_id)
 414 {
 415         if (type_id == 0)
 416                 return &btf_void;
 417
 418         return btf->types_data + btf->type_offs[type_id];
 419 }
 420
 421 const struct btf_type *btf__type_by_id(const struct btf *btf, __u32 type_id)
 422 {
 423         if (type_id > btf->nr_types)
 424                 return NULL;
 425         return btf_type_by_id((struct btf *)btf, type_id);
 426 }
 427
 428 static int determine_ptr_size(const struct btf *btf)
 429 {
 430         const struct btf_type *t;
 431         const char *name;
 432         int i;
 433
 434         for (i = 1; i <= btf->nr_types; i++) {
 435                 t = btf__type_by_id(btf, i);
 436                 if (!btf_is_int(t))
 437                         continue;
 438
 439                 name = btf__name_by_offset(btf, t->name_off);
 440                 if (!name)
 441                         continue;
 442
 443                 if (strcmp(name, "long int") == 0 ||
 444                     strcmp(name, "long unsigned int") == 0) {
 445                         if (t->size != 4 && t->size != 8)
 446                                 continue;
 447                         return t->size;
 448                 }
 449         }
 450
 451         return -1;
 452 }
 453
 454 static size_t btf_ptr_sz(const struct btf *btf)
 455 {
 456         if (!btf->ptr_sz)
 457                 ((struct btf *)btf)->ptr_sz = determine_ptr_size(btf);
 458         return btf->ptr_sz < 0 ? sizeof(void *) : btf->ptr_sz;
 459 }
 460
 461 /* Return pointer size this BTF instance assumes. The size is heuristically
 462  * determined by looking for 'long' or 'unsigned long' integer type and
 463  * recording its size in bytes. If BTF type information doesn't have any such
 464  * type, this function returns 0. In the latter case, native architecture's
 465  * pointer size is assumed, so will be either 4 or 8, depending on
 466  * architecture that libbpf was compiled for. It's possible to override
 467  * guessed value by using btf__set_pointer_size() API.
 468  */
 469 size_t btf__pointer_size(const struct btf *btf)
 470 {
 471         if (!btf->ptr_sz)
 472                 ((struct btf *)btf)->ptr_sz = determine_ptr_size(btf);
 473
 474         if (btf->ptr_sz < 0)
 475                 /* not enough BTF type info to guess */
 476                 return 0;
 477
 478         return btf->ptr_sz;
 479 }
 480
 481 /* Override or set pointer size in bytes. Only values of 4 and 8 are
 482  * supported.
 483  */
 484 int btf__set_pointer_size(struct btf *btf, size_t ptr_sz)
 485 {
 486         if (ptr_sz != 4 && ptr_sz != 8)
 487                 return -EINVAL;
 488         btf->ptr_sz = ptr_sz;
 489         return 0;
 490 }
 491
 492 static bool is_host_big_endian(void)
 493 {
 494 #if __BYTE_ORDER == __LITTLE_ENDIAN
 495         return false;
 496 #elif __BYTE_ORDER == __BIG_ENDIAN
 497         return true;
 498 #else
 499 # error "Unrecognized __BYTE_ORDER__"
 500 #endif
 501 }
 502
 503 enum btf_endianness btf__endianness(const struct btf *btf)
 504 {
 505         if (is_host_big_endian())
 506                 return btf->swapped_endian ? BTF_LITTLE_ENDIAN : BTF_BIG_ENDIAN;
 507         else
 508                 return btf->swapped_endian ? BTF_BIG_ENDIAN : BTF_LITTLE_ENDIAN;
 509 }
 510
 511 int btf__set_endianness(struct btf *btf, enum btf_endianness endian)
 512 {
 513         if (endian != BTF_LITTLE_ENDIAN && endian != BTF_BIG_ENDIAN)
 514                 return -EINVAL;
 515
 516         btf->swapped_endian = is_host_big_endian() != (endian == BTF_BIG_ENDIAN);
 517         if (!btf->swapped_endian) {
 518                 free(btf->raw_data_swapped);
 519                 btf->raw_data_swapped = NULL;
 520         }
 521         return 0;
 522 }
 523
 524 static bool btf_type_is_void(const struct btf_type *t)
 525 {
 526         return t == &btf_void || btf_is_fwd(t);
 527 }
 528
 529 static bool btf_type_is_void_or_null(const struct btf_type *t)
 530 {
 531         return !t || btf_type_is_void(t);
 532 }
 533
 534 #define MAX_RESOLVE_DEPTH 32
 535
 536 __s64 btf__resolve_size(const struct btf *btf, __u32 type_id)
 537 {
 538         const struct btf_array *array;
 539         const struct btf_type *t;
 540         __u32 nelems = 1;
 541         __s64 size = -1;
 542         int i;
 543
 544         t = btf__type_by_id(btf, type_id);
 545         for (i = 0; i < MAX_RESOLVE_DEPTH && !btf_type_is_void_or_null(t);
 546              i++) {
 547                 switch (btf_kind(t)) {
 548                 case BTF_KIND_INT:
 549                 case BTF_KIND_STRUCT:
 550                 case BTF_KIND_UNION:
 551                 case BTF_KIND_ENUM:
 552                 case BTF_KIND_DATASEC:
 553                         size = t->size;
 554                         goto done;
 555                 case BTF_KIND_PTR:
 556                         size = btf_ptr_sz(btf);
 557                         goto done;
 558                 case BTF_KIND_TYPEDEF:
 559                 case BTF_KIND_VOLATILE:
 560                 case BTF_KIND_CONST:
 561                 case BTF_KIND_RESTRICT:
 562                 case BTF_KIND_VAR:
 563                         type_id = t->type;
 564                         break;
 565                 case BTF_KIND_ARRAY:
 566                         array = btf_array(t);
 567                         if (nelems && array->nelems > UINT32_MAX / nelems)
 568                                 return -E2BIG;
 569                         nelems *= array->nelems;
 570                         type_id = array->type;
 571                         break;
 572                 default:
 573                         return -EINVAL;
 574                 }
 575
 576                 t = btf__type_by_id(btf, type_id);
 577         }
 578
 579 done:
 580         if (size < 0)
 581                 return -EINVAL;
 582         if (nelems && size > UINT32_MAX / nelems)
 583                 return -E2BIG;
 584
 585         return nelems * size;
 586 }
 587
 588 int btf__align_of(const struct btf *btf, __u32 id)
 589 {
 590         const struct btf_type *t = btf__type_by_id(btf, id);
 591         __u16 kind = btf_kind(t);
 592
 593         switch (kind) {
 594         case BTF_KIND_INT:
 595         case BTF_KIND_ENUM:
 596                 return min(btf_ptr_sz(btf), (size_t)t->size);
 597         case BTF_KIND_PTR:
 598                 return btf_ptr_sz(btf);
 599         case BTF_KIND_TYPEDEF:
 600         case BTF_KIND_VOLATILE:
 601         case BTF_KIND_CONST:
 602         case BTF_KIND_RESTRICT:
 603                 return btf__align_of(btf, t->type);
 604         case BTF_KIND_ARRAY:
 605                 return btf__align_of(btf, btf_array(t)->type);
 606         case BTF_KIND_STRUCT:
 607         case BTF_KIND_UNION: {
 608                 const struct btf_member *m = btf_members(t);
 609                 __u16 vlen = btf_vlen(t);
 610                 int i, max_align = 1, align;
 611
 612                 for (i = 0; i < vlen; i++, m++) {
 613                         align = btf__align_of(btf, m->type);
 614                         if (align <= 0)
 615                                 return align;
 616                         max_align = max(max_align, align);
 617
 618                         /* if field offset isn't aligned according to field
 619                          * type's alignment, then struct must be packed
 620                          */
 621                         if (btf_member_bitfield_size(t, i) == 0 &&
 622                             (m->offset % (8 * align)) != 0)
 623                                 return 1;
 624                 }
 625
 626                 /* if struct/union size isn't a multiple of its alignment,
 627                  * then struct must be packed
 628                  */
 629                 if ((t->size % max_align) != 0)
 630                         return 1;
 631
 632                 return max_align;
 633         }
 634         default:
 635                 pr_warn("unsupported BTF_KIND:%u\n", btf_kind(t));
 636                 return 0;
 637         }
 638 }
 639
 640 int btf__resolve_type(const struct btf *btf, __u32 type_id)
 641 {
 642         const struct btf_type *t;
 643         int depth = 0;
 644
 645         t = btf__type_by_id(btf, type_id);
 646         while (depth < MAX_RESOLVE_DEPTH &&
 647                !btf_type_is_void_or_null(t) &&
 648                (btf_is_mod(t) || btf_is_typedef(t) || btf_is_var(t))) {
 649                 type_id = t->type;
 650                 t = btf__type_by_id(btf, type_id);
 651                 depth++;
 652         }
 653
 654         if (depth == MAX_RESOLVE_DEPTH || btf_type_is_void_or_null(t))
 655                 return -EINVAL;
 656
 657         return type_id;
 658 }
 659
 660 __s32 btf__find_by_name(const struct btf *btf, const char *type_name)
 661 {
 662         __u32 i;
 663
 664         if (!strcmp(type_name, "void"))
 665                 return 0;
 666
 667         for (i = 1; i <= btf->nr_types; i++) {
 668                 const struct btf_type *t = btf__type_by_id(btf, i);
 669                 const char *name = btf__name_by_offset(btf, t->name_off);
 670
 671                 if (name && !strcmp(type_name, name))
 672                         return i;
 673         }
 674
 675         return -ENOENT;
 676 }
 677
 678 __s32 btf__find_by_name_kind(const struct btf *btf, const char *type_name,
 679                              __u32 kind)
 680 {
 681         __u32 i;
 682
 683         if (kind == BTF_KIND_UNKN || !strcmp(type_name, "void"))
 684                 return 0;
 685
 686         for (i = 1; i <= btf->nr_types; i++) {
 687                 const struct btf_type *t = btf__type_by_id(btf, i);
 688                 const char *name;
 689
 690                 if (btf_kind(t) != kind)
 691                         continue;
 692                 name = btf__name_by_offset(btf, t->name_off);
 693                 if (name && !strcmp(type_name, name))
 694                         return i;
 695         }
 696
 697         return -ENOENT;
 698 }
 699
 700 static bool btf_is_modifiable(const struct btf *btf)
 701 {
 702         return (void *)btf->hdr != btf->raw_data;
 703 }
 704
 705 void btf__free(struct btf *btf)
 706 {
 707         if (IS_ERR_OR_NULL(btf))
 708                 return;
 709
 710         if (btf->fd >= 0)
 711                 close(btf->fd);
 712
 713         if (btf_is_modifiable(btf)) {
 714                 /* if BTF was modified after loading, it will have a split
 715                  * in-memory representation for header, types, and strings
 716                  * sections, so we need to free all of them individually. It
 717                  * might still have a cached contiguous raw data present,
 718                  * which will be unconditionally freed below.
 719                  */
 720                 free(btf->hdr);
 721                 free(btf->types_data);
 722                 free(btf->strs_data);
 723         }
 724         free(btf->raw_data);
 725         free(btf->raw_data_swapped);
 726         free(btf->type_offs);
 727         free(btf);
 728 }
 729
 730 struct btf *btf__new_empty(void)
 731 {
 732         struct btf *btf;
 733
 734         btf = calloc(1, sizeof(*btf));
 735         if (!btf)
 736                 return ERR_PTR(-ENOMEM);
 737
 738         btf->fd = -1;
 739         btf->ptr_sz = sizeof(void *);
 740         btf->swapped_endian = false;
 741
 742         /* +1 for empty string at offset 0 */
 743         btf->raw_size = sizeof(struct btf_header) + 1;
 744         btf->raw_data = calloc(1, btf->raw_size);
 745         if (!btf->raw_data) {
 746                 free(btf);
 747                 return ERR_PTR(-ENOMEM);
 748         }
 749
 750         btf->hdr = btf->raw_data;
 751         btf->hdr->hdr_len = sizeof(struct btf_header);
 752         btf->hdr->magic = BTF_MAGIC;
 753         btf->hdr->version = BTF_VERSION;
 754
 755         btf->types_data = btf->raw_data + btf->hdr->hdr_len;
 756         btf->strs_data = btf->raw_data + btf->hdr->hdr_len;
 757         btf->hdr->str_len = 1; /* empty string at offset 0 */
 758
 759         return btf;
 760 }
 761
 762 struct btf *btf__new(const void *data, __u32 size)
 763 {
 764         struct btf *btf;
 765         int err;
 766
 767         btf = calloc(1, sizeof(struct btf));
 768         if (!btf)
 769                 return ERR_PTR(-ENOMEM);
 770
 771         btf->raw_data = malloc(size);
 772         if (!btf->raw_data) {
 773                 err = -ENOMEM;
 774                 goto done;
 775         }
 776         memcpy(btf->raw_data, data, size);
 777         btf->raw_size = size;
 778
 779         btf->hdr = btf->raw_data;
 780         err = btf_parse_hdr(btf);
 781         if (err)
 782                 goto done;
 783
 784         btf->strs_data = btf->raw_data + btf->hdr->hdr_len + btf->hdr->str_off;
 785         btf->types_data = btf->raw_data + btf->hdr->hdr_len + btf->hdr->type_off;
 786
 787         err = btf_parse_str_sec(btf);
 788         err = err ?: btf_parse_type_sec(btf);
 789         if (err)
 790                 goto done;
 791
 792         btf->fd = -1;
 793
 794 done:
 795         if (err) {
 796                 btf__free(btf);
 797                 return ERR_PTR(err);
 798         }
 799
 800         return btf;
 801 }
 802
 803 struct btf *btf__parse_elf(const char *path, struct btf_ext **btf_ext)
 804 {
 805         Elf_Data *btf_data = NULL, *btf_ext_data = NULL;
 806         int err = 0, fd = -1, idx = 0;
 807         struct btf *btf = NULL;
 808         Elf_Scn *scn = NULL;
 809         Elf *elf = NULL;
 810         GElf_Ehdr ehdr;
 811
 812         if (elf_version(EV_CURRENT) == EV_NONE) {
 813                 pr_warn("failed to init libelf for %s\n", path);
 814                 return ERR_PTR(-LIBBPF_ERRNO__LIBELF);
 815         }
 816
 817         fd = open(path, O_RDONLY);
 818         if (fd < 0) {
 819                 err = -errno;
 820                 pr_warn("failed to open %s: %s\n", path, strerror(errno));
 821                 return ERR_PTR(err);
 822         }
 823
 824         err = -LIBBPF_ERRNO__FORMAT;
 825
 826         elf = elf_begin(fd, ELF_C_READ, NULL);
 827         if (!elf) {
 828                 pr_warn("failed to open %s as ELF file\n", path);
 829                 goto done;
 830         }
 831         if (!gelf_getehdr(elf, &ehdr)) {
 832                 pr_warn("failed to get EHDR from %s\n", path);
 833                 goto done;
 834         }
 835         if (!elf_rawdata(elf_getscn(elf, ehdr.e_shstrndx), NULL)) {
 836                 pr_warn("failed to get e_shstrndx from %s\n", path);
 837                 goto done;
 838         }
 839
 840         while ((scn = elf_nextscn(elf, scn)) != NULL) {
 841                 GElf_Shdr sh;
 842                 char *name;
 843
 844                 idx++;
 845                 if (gelf_getshdr(scn, &sh) != &sh) {
 846                         pr_warn("failed to get section(%d) header from %s\n",
 847                                 idx, path);
 848                         goto done;
 849                 }
 850                 name = elf_strptr(elf, ehdr.e_shstrndx, sh.sh_name);
 851                 if (!name) {
 852                         pr_warn("failed to get section(%d) name from %s\n",
 853                                 idx, path);
 854                         goto done;
 855                 }
 856                 if (strcmp(name, BTF_ELF_SEC) == 0) {
 857                         btf_data = elf_getdata(scn, 0);
 858                         if (!btf_data) {
 859                                 pr_warn("failed to get section(%d, %s) data from %s\n",
 860                                         idx, name, path);
 861                                 goto done;
 862                         }
 863                         continue;
 864                 } else if (btf_ext && strcmp(name, BTF_EXT_ELF_SEC) == 0) {
 865                         btf_ext_data = elf_getdata(scn, 0);
 866                         if (!btf_ext_data) {
 867                                 pr_warn("failed to get section(%d, %s) data from %s\n",
 868                                         idx, name, path);
 869                                 goto done;
 870                         }
 871                         continue;
 872                 }
 873         }
 874
 875         err = 0;
 876
 877         if (!btf_data) {
 878                 err = -ENOENT;
 879                 goto done;
 880         }
 881         btf = btf__new(btf_data->d_buf, btf_data->d_size);
 882         if (IS_ERR(btf))
 883                 goto done;
 884
 885         switch (gelf_getclass(elf)) {
 886         case ELFCLASS32:
 887                 btf__set_pointer_size(btf, 4);
 888                 break;
 889         case ELFCLASS64:
 890                 btf__set_pointer_size(btf, 8);
 891                 break;
 892         default:
 893                 pr_warn("failed to get ELF class (bitness) for %s\n", path);
 894                 break;
 895         }
 896
 897         if (btf_ext && btf_ext_data) {
 898                 *btf_ext = btf_ext__new(btf_ext_data->d_buf,
 899                                         btf_ext_data->d_size);
 900                 if (IS_ERR(*btf_ext))
 901                         goto done;
 902         } else if (btf_ext) {
 903                 *btf_ext = NULL;
 904         }
 905 done:
 906         if (elf)
 907                 elf_end(elf);
 908         close(fd);
 909
 910         if (err)
 911                 return ERR_PTR(err);
 912         /*
 913          * btf is always parsed before btf_ext, so no need to clean up
 914          * btf_ext, if btf loading failed
 915          */
 916         if (IS_ERR(btf))
 917                 return btf;
 918         if (btf_ext && IS_ERR(*btf_ext)) {
 919                 btf__free(btf);
 920                 err = PTR_ERR(*btf_ext);
 921                 return ERR_PTR(err);
 922         }
 923         return btf;
 924 }
 925
 926 struct btf *btf__parse_raw(const char *path)
 927 {
 928         struct btf *btf = NULL;
 929         void *data = NULL;
 930         FILE *f = NULL;
 931         __u16 magic;
 932         int err = 0;
 933         long sz;
 934
 935         f = fopen(path, "rb");
 936         if (!f) {
 937                 err = -errno;
 938                 goto err_out;
 939         }
 940
 941         /* check BTF magic */
 942         if (fread(&magic, 1, sizeof(magic), f) < sizeof(magic)) {
 943                 err = -EIO;
 944                 goto err_out;
 945         }
 946         if (magic != BTF_MAGIC && magic != bswap_16(BTF_MAGIC)) {
 947                 /* definitely not a raw BTF */
 948                 err = -EPROTO;
 949                 goto err_out;
 950         }
 951
 952         /* get file size */
 953         if (fseek(f, 0, SEEK_END)) {
 954                 err = -errno;
 955                 goto err_out;
 956         }
 957         sz = ftell(f);
 958         if (sz < 0) {
 959                 err = -errno;
 960                 goto err_out;
 961         }
 962         /* rewind to the start */
 963         if (fseek(f, 0, SEEK_SET)) {
 964                 err = -errno;
 965                 goto err_out;
 966         }
 967
 968         /* pre-alloc memory and read all of BTF data */
 969         data = malloc(sz);
 970         if (!data) {
 971                 err = -ENOMEM;
 972                 goto err_out;
 973         }
 974         if (fread(data, 1, sz, f) < sz) {
 975                 err = -EIO;
 976                 goto err_out;
 977         }
 978
 979         /* finally parse BTF data */
 980         btf = btf__new(data, sz);
 981
 982 err_out:
 983         free(data);
 984         if (f)
 985                 fclose(f);
 986         return err ? ERR_PTR(err) : btf;
 987 }
 988
 989 struct btf *btf__parse(const char *path, struct btf_ext **btf_ext)
 990 {
 991         struct btf *btf;
 992
 993         if (btf_ext)
 994                 *btf_ext = NULL;
 995
 996         btf = btf__parse_raw(path);
 997         if (!IS_ERR(btf) || PTR_ERR(btf) != -EPROTO)
 998                 return btf;
 999
1000         return btf__parse_elf(path, btf_ext);
1001 }
1002
1003 static int compare_vsi_off(const void *_a, const void *_b)
1004 {
1005         const struct btf_var_secinfo *a = _a;
1006         const struct btf_var_secinfo *b = _b;
1007
1008         return a->offset - b->offset;
1009 }
1010
1011 static int btf_fixup_datasec(struct bpf_object *obj, struct btf *btf,
1012                              struct btf_type *t)
1013 {
1014         __u32 size = 0, off = 0, i, vars = btf_vlen(t);
1015         const char *name = btf__name_by_offset(btf, t->name_off);
1016         const struct btf_type *t_var;
1017         struct btf_var_secinfo *vsi;
1018         const struct btf_var *var;
1019         int ret;
1020
1021         if (!name) {
1022                 pr_debug("No name found in string section for DATASEC kind.\n");
1023                 return -ENOENT;
1024         }
1025
1026         /* .extern datasec size and var offsets were set correctly during
1027          * extern collection step, so just skip straight to sorting variables
1028          */
1029         if (t->size)
1030                 goto sort_vars;
1031
1032         ret = bpf_object__section_size(obj, name, &size);
1033         if (ret || !size || (t->size && t->size != size)) {
1034                 pr_debug("Invalid size for section %s: %u bytes\n", name, size);
1035                 return -ENOENT;
1036         }
1037
1038         t->size = size;
1039
1040         for (i = 0, vsi = btf_var_secinfos(t); i < vars; i++, vsi++) {
1041                 t_var = btf__type_by_id(btf, vsi->type);
1042                 var = btf_var(t_var);
1043
1044                 if (!btf_is_var(t_var)) {
1045                         pr_debug("Non-VAR type seen in section %s\n", name);
1046                         return -EINVAL;
1047                 }
1048
1049                 if (var->linkage == BTF_VAR_STATIC)
1050                         continue;
1051
1052                 name = btf__name_by_offset(btf, t_var->name_off);
1053                 if (!name) {
1054                         pr_debug("No name found in string section for VAR kind\n");
1055                         return -ENOENT;
1056                 }
1057
1058                 ret = bpf_object__variable_offset(obj, name, &off);
1059                 if (ret) {
1060                         pr_debug("No offset found in symbol table for VAR %s\n",
1061                                  name);
1062                         return -ENOENT;
1063                 }
1064
1065                 vsi->offset = off;
1066         }
1067
1068 sort_vars:
1069         qsort(btf_var_secinfos(t), vars, sizeof(*vsi), compare_vsi_off);
1070         return 0;
1071 }
1072
1073 int btf__finalize_data(struct bpf_object *obj, struct btf *btf)
1074 {
1075         int err = 0;
1076         __u32 i;
1077
1078         for (i = 1; i <= btf->nr_types; i++) {
1079                 struct btf_type *t = btf_type_by_id(btf, i);
1080
1081                 /* Loader needs to fix up some of the things compiler
1082                  * couldn't get its hands on while emitting BTF. This
1083                  * is section size and global variable offset. We use
1084                  * the info from the ELF itself for this purpose.
1085                  */
1086                 if (btf_is_datasec(t)) {
1087                         err = btf_fixup_datasec(obj, btf, t);
1088                         if (err)
1089                                 break;
1090                 }
1091         }
1092
1093         return err;
1094 }
1095
1096 static void *btf_get_raw_data(const struct btf *btf, __u32 *size, bool swap_endian);
1097
1098 int btf__load(struct btf *btf)
1099 {
1100         __u32 log_buf_size = 0, raw_size;
1101         char *log_buf = NULL;
1102         void *raw_data;
1103         int err = 0;
1104
1105         if (btf->fd >= 0)
1106                 return -EEXIST;
1107
1108 retry_load:
1109         if (log_buf_size) {
1110                 log_buf = malloc(log_buf_size);
1111                 if (!log_buf)
1112                         return -ENOMEM;
1113
1114                 *log_buf = 0;
1115         }
1116
1117         raw_data = btf_get_raw_data(btf, &raw_size, false);
1118         if (!raw_data) {
1119                 err = -ENOMEM;
1120                 goto done;
1121         }
1122         /* cache native raw data representation */
1123         btf->raw_size = raw_size;
1124         btf->raw_data = raw_data;
1125
1126         btf->fd = bpf_load_btf(raw_data, raw_size, log_buf, log_buf_size, false);
1127         if (btf->fd < 0) {
1128                 if (!log_buf || errno == ENOSPC) {
1129                         log_buf_size = max((__u32)BPF_LOG_BUF_SIZE,
1130                                            log_buf_size << 1);
1131                         free(log_buf);
1132                         goto retry_load;
1133                 }
1134
1135                 err = -errno;
1136                 pr_warn("Error loading BTF: %s(%d)\n", strerror(errno), errno);
1137                 if (*log_buf)
1138                         pr_warn("%s\n", log_buf);
1139                 goto done;
1140         }
1141
1142 done:
1143         free(log_buf);
1144         return err;
1145 }
1146
1147 int btf__fd(const struct btf *btf)
1148 {
1149         return btf->fd;
1150 }
1151
1152 void btf__set_fd(struct btf *btf, int fd)
1153 {
1154         btf->fd = fd;
1155 }
1156
1157 static void *btf_get_raw_data(const struct btf *btf, __u32 *size, bool swap_endian)
1158 {
1159         struct btf_header *hdr = btf->hdr;
1160         struct btf_type *t;
1161         void *data, *p;
1162         __u32 data_sz;
1163         int i;
1164
1165         data = swap_endian ? btf->raw_data_swapped : btf->raw_data;
1166         if (data) {
1167                 *size = btf->raw_size;
1168                 return data;
1169         }
1170
1171         data_sz = hdr->hdr_len + hdr->type_len + hdr->str_len;
1172         data = calloc(1, data_sz);
1173         if (!data)
1174                 return NULL;
1175         p = data;
1176
1177         memcpy(p, hdr, hdr->hdr_len);
1178         if (swap_endian)
1179                 btf_bswap_hdr(p);
1180         p += hdr->hdr_len;
1181
1182         memcpy(p, btf->types_data, hdr->type_len);
1183         if (swap_endian) {
1184                 for (i = 1; i <= btf->nr_types; i++) {
1185                         t = p  + btf->type_offs[i];
1186                         /* btf_bswap_type_rest() relies on native t->info, so
1187                          * we swap base type info after we swapped all the
1188                          * additional information
1189                          */
1190                         if (btf_bswap_type_rest(t))
1191                                 goto err_out;
1192                         btf_bswap_type_base(t);
1193                 }
1194         }
1195         p += hdr->type_len;
1196
1197         memcpy(p, btf->strs_data, hdr->str_len);
1198         p += hdr->str_len;
1199
1200         *size = data_sz;
1201         return data;
1202 err_out:
1203         free(data);
1204         return NULL;
1205 }
1206
1207 const void *btf__get_raw_data(const struct btf *btf_ro, __u32 *size)
1208 {
1209         struct btf *btf = (struct btf *)btf_ro;
1210         __u32 data_sz;
1211         void *data;
1212
1213         data = btf_get_raw_data(btf, &data_sz, btf->swapped_endian);
1214         if (!data)
1215                 return NULL;
1216
1217         btf->raw_size = data_sz;
1218         if (btf->swapped_endian)
1219                 btf->raw_data_swapped = data;
1220         else
1221                 btf->raw_data = data;
1222         *size = data_sz;
1223         return data;
1224 }
1225
1226 const char *btf__str_by_offset(const struct btf *btf, __u32 offset)
1227 {
1228         if (offset < btf->hdr->str_len)
1229                 return btf->strs_data + offset;
1230         else
1231                 return NULL;
1232 }
1233
1234 const char *btf__name_by_offset(const struct btf *btf, __u32 offset)
1235 {
1236         return btf__str_by_offset(btf, offset);
1237 }
1238
1239 int btf__get_from_id(__u32 id, struct btf **btf)
1240 {
1241         struct bpf_btf_info btf_info = { 0 };
1242         __u32 len = sizeof(btf_info);
1243         __u32 last_size;
1244         int btf_fd;
1245         void *ptr;
1246         int err;
1247
1248         err = 0;
1249         *btf = NULL;
1250         btf_fd = bpf_btf_get_fd_by_id(id);
1251         if (btf_fd < 0)
1252                 return 0;
1253
1254         /* we won't know btf_size until we call bpf_obj_get_info_by_fd(). so
1255          * let's start with a sane default - 4KiB here - and resize it only if
1256          * bpf_obj_get_info_by_fd() needs a bigger buffer.
1257          */
1258         btf_info.btf_size = 4096;
1259         last_size = btf_info.btf_size;
1260         ptr = malloc(last_size);
1261         if (!ptr) {
1262                 err = -ENOMEM;
1263                 goto exit_free;
1264         }
1265
1266         memset(ptr, 0, last_size);
1267         btf_info.btf = ptr_to_u64(ptr);
1268         err = bpf_obj_get_info_by_fd(btf_fd, &btf_info, &len);
1269
1270         if (!err && btf_info.btf_size > last_size) {
1271                 void *temp_ptr;
1272
1273                 last_size = btf_info.btf_size;
1274                 temp_ptr = realloc(ptr, last_size);
1275                 if (!temp_ptr) {
1276                         err = -ENOMEM;
1277                         goto exit_free;
1278                 }
1279                 ptr = temp_ptr;
1280                 memset(ptr, 0, last_size);
1281                 btf_info.btf = ptr_to_u64(ptr);
1282                 err = bpf_obj_get_info_by_fd(btf_fd, &btf_info, &len);
1283         }
1284
1285         if (err || btf_info.btf_size > last_size) {
1286                 err = errno;
1287                 goto exit_free;
1288         }
1289
1290         *btf = btf__new((__u8 *)(long)btf_info.btf, btf_info.btf_size);
1291         if (IS_ERR(*btf)) {
1292                 err = PTR_ERR(*btf);
1293                 *btf = NULL;
1294         }
1295
1296 exit_free:
1297         close(btf_fd);
1298         free(ptr);
1299
1300         return err;
1301 }
1302
1303 int btf__get_map_kv_tids(const struct btf *btf, const char *map_name,
1304                          __u32 expected_key_size, __u32 expected_value_size,
1305                          __u32 *key_type_id, __u32 *value_type_id)
1306 {
1307         const struct btf_type *container_type;
1308         const struct btf_member *key, *value;
1309         const size_t max_name = 256;
1310         char container_name[max_name];
1311         __s64 key_size, value_size;
1312         __s32 container_id;
1313
1314         if (snprintf(container_name, max_name, "____btf_map_%s", map_name) ==
1315             max_name) {
1316                 pr_warn("map:%s length of '____btf_map_%s' is too long\n",
1317                         map_name, map_name);
1318                 return -EINVAL;
1319         }
1320
1321         container_id = btf__find_by_name(btf, container_name);
1322         if (container_id < 0) {
1323                 pr_debug("map:%s container_name:%s cannot be found in BTF. Missing BPF_ANNOTATE_KV_PAIR?\n",
1324                          map_name, container_name);
1325                 return container_id;
1326         }
1327
1328         container_type = btf__type_by_id(btf, container_id);
1329         if (!container_type) {
1330                 pr_warn("map:%s cannot find BTF type for container_id:%u\n",
1331                         map_name, container_id);
1332                 return -EINVAL;
1333         }
1334
1335         if (!btf_is_struct(container_type) || btf_vlen(container_type) < 2) {
1336                 pr_warn("map:%s container_name:%s is an invalid container struct\n",
1337                         map_name, container_name);
1338                 return -EINVAL;
1339         }
1340
1341         key = btf_members(container_type);
1342         value = key + 1;
1343
1344         key_size = btf__resolve_size(btf, key->type);
1345         if (key_size < 0) {
1346                 pr_warn("map:%s invalid BTF key_type_size\n", map_name);
1347                 return key_size;
1348         }
1349
1350         if (expected_key_size != key_size) {
1351                 pr_warn("map:%s btf_key_type_size:%u != map_def_key_size:%u\n",
1352                         map_name, (__u32)key_size, expected_key_size);
1353                 return -EINVAL;
1354         }
1355
1356         value_size = btf__resolve_size(btf, value->type);
1357         if (value_size < 0) {
1358                 pr_warn("map:%s invalid BTF value_type_size\n", map_name);
1359                 return value_size;
1360         }
1361
1362         if (expected_value_size != value_size) {
1363                 pr_warn("map:%s btf_value_type_size:%u != map_def_value_size:%u\n",
1364                         map_name, (__u32)value_size, expected_value_size);
1365                 return -EINVAL;
1366         }
1367
1368         *key_type_id = key->type;
1369         *value_type_id = value->type;
1370
1371         return 0;
1372 }
1373
1374 static size_t strs_hash_fn(const void *key, void *ctx)
1375 {
1376         struct btf *btf = ctx;
1377         const char *str = btf->strs_data + (long)key;
1378
1379         return str_hash(str);
1380 }
1381
1382 static bool strs_hash_equal_fn(const void *key1, const void *key2, void *ctx)
1383 {
1384         struct btf *btf = ctx;
1385         const char *str1 = btf->strs_data + (long)key1;
1386         const char *str2 = btf->strs_data + (long)key2;
1387
1388         return strcmp(str1, str2) == 0;
1389 }
1390
1391 static void btf_invalidate_raw_data(struct btf *btf)
1392 {
1393         if (btf->raw_data) {
1394                 free(btf->raw_data);
1395                 btf->raw_data = NULL;
1396         }
1397         if (btf->raw_data_swapped) {
1398                 free(btf->raw_data_swapped);
1399                 btf->raw_data_swapped = NULL;
1400         }
1401 }
1402
1403 /* Ensure BTF is ready to be modified (by splitting into a three memory
1404  * regions for header, types, and strings). Also invalidate cached
1405  * raw_data, if any.
1406  */
1407 static int btf_ensure_modifiable(struct btf *btf)
1408 {
1409         void *hdr, *types, *strs, *strs_end, *s;
1410         struct hashmap *hash = NULL;
1411         long off;
1412         int err;
1413
1414         if (btf_is_modifiable(btf)) {
1415                 /* any BTF modification invalidates raw_data */
1416                 btf_invalidate_raw_data(btf);
1417                 return 0;
1418         }
1419
1420         /* split raw data into three memory regions */
1421         hdr = malloc(btf->hdr->hdr_len);
1422         types = malloc(btf->hdr->type_len);
1423         strs = malloc(btf->hdr->str_len);
1424         if (!hdr || !types || !strs)
1425                 goto err_out;
1426
1427         memcpy(hdr, btf->hdr, btf->hdr->hdr_len);
1428         memcpy(types, btf->types_data, btf->hdr->type_len);
1429         memcpy(strs, btf->strs_data, btf->hdr->str_len);
1430
1431         /* build lookup index for all strings */
1432         hash = hashmap__new(strs_hash_fn, strs_hash_equal_fn, btf);
1433         if (IS_ERR(hash)) {
1434                 err = PTR_ERR(hash);
1435                 hash = NULL;
1436                 goto err_out;
1437         }
1438
1439         strs_end = strs + btf->hdr->str_len;
1440         for (off = 0, s = strs; s < strs_end; off += strlen(s) + 1, s = strs + off) {
1441                 /* hashmap__add() returns EEXIST if string with the same
1442                  * content already is in the hash map
1443                  */
1444                 err = hashmap__add(hash, (void *)off, (void *)off);
1445                 if (err == -EEXIST)
1446                         continue; /* duplicate */
1447                 if (err)
1448                         goto err_out;
1449         }
1450
1451         /* only when everything was successful, update internal state */
1452         btf->hdr = hdr;
1453         btf->types_data = types;
1454         btf->types_data_cap = btf->hdr->type_len;
1455         btf->strs_data = strs;
1456         btf->strs_data_cap = btf->hdr->str_len;
1457         btf->strs_hash = hash;
1458         /* if BTF was created from scratch, all strings are guaranteed to be
1459          * unique and deduplicated
1460          */
1461         btf->strs_deduped = btf->hdr->str_len <= 1;
1462
1463         /* invalidate raw_data representation */
1464         btf_invalidate_raw_data(btf);
1465
1466         return 0;
1467
1468 err_out:
1469         hashmap__free(hash);
1470         free(hdr);
1471         free(types);
1472         free(strs);
1473         return -ENOMEM;
1474 }
1475
1476 static void *btf_add_str_mem(struct btf *btf, size_t add_sz)
1477 {
1478         return btf_add_mem(&btf->strs_data, &btf->strs_data_cap, 1,
1479                            btf->hdr->str_len, BTF_MAX_STR_OFFSET, add_sz);
1480 }
1481
1482 /* Find an offset in BTF string section that corresponds to a given string *s*.
1483  * Returns:
1484  *   - >0 offset into string section, if string is found;
1485  *   - -ENOENT, if string is not in the string section;
1486  *   - <0, on any other error.
1487  */
1488 int btf__find_str(struct btf *btf, const char *s)
1489 {
1490         long old_off, new_off, len;
1491         void *p;
1492
1493         /* BTF needs to be in a modifiable state to build string lookup index */
1494         if (btf_ensure_modifiable(btf))
1495                 return -ENOMEM;
1496
1497         /* see btf__add_str() for why we do this */
1498         len = strlen(s) + 1;
1499         p = btf_add_str_mem(btf, len);
1500         if (!p)
1501                 return -ENOMEM;
1502
1503         new_off = btf->hdr->str_len;
1504         memcpy(p, s, len);
1505
1506         if (hashmap__find(btf->strs_hash, (void *)new_off, (void **)&old_off))
1507                 return old_off;
1508
1509         return -ENOENT;
1510 }
1511
1512 /* Add a string s to the BTF string section.
1513  * Returns:
1514  *   - > 0 offset into string section, on success;
1515  *   - < 0, on error.
1516  */
1517 int btf__add_str(struct btf *btf, const char *s)
1518 {
1519         long old_off, new_off, len;
1520         void *p;
1521         int err;
1522
1523         if (btf_ensure_modifiable(btf))
1524                 return -ENOMEM;
1525
1526         /* Hashmap keys are always offsets within btf->strs_data, so to even
1527          * look up some string from the "outside", we need to first append it
1528          * at the end, so that it can be addressed with an offset. Luckily,
1529          * until btf->hdr->str_len is incremented, that string is just a piece
1530          * of garbage for the rest of BTF code, so no harm, no foul. On the
1531          * other hand, if the string is unique, it's already appended and
1532          * ready to be used, only a simple btf->hdr->str_len increment away.
1533          */
1534         len = strlen(s) + 1;
1535         p = btf_add_str_mem(btf, len);
1536         if (!p)
1537                 return -ENOMEM;
1538
1539         new_off = btf->hdr->str_len;
1540         memcpy(p, s, len);
1541
1542         /* Now attempt to add the string, but only if the string with the same
1543          * contents doesn't exist already (HASHMAP_ADD strategy). If such
1544          * string exists, we'll get its offset in old_off (that's old_key).
1545          */
1546         err = hashmap__insert(btf->strs_hash, (void *)new_off, (void *)new_off,
1547                               HASHMAP_ADD, (const void **)&old_off, NULL);
1548         if (err == -EEXIST)
1549                 return old_off; /* duplicated string, return existing offset */
1550         if (err)
1551                 return err;
1552
1553         btf->hdr->str_len += len; /* new unique string, adjust data length */
1554         return new_off;
1555 }
1556
1557 static void *btf_add_type_mem(struct btf *btf, size_t add_sz)
1558 {
1559         return btf_add_mem(&btf->types_data, &btf->types_data_cap, 1,
1560                            btf->hdr->type_len, UINT_MAX, add_sz);
1561 }
1562
1563 static __u32 btf_type_info(int kind, int vlen, int kflag)
1564 {
1565         return (kflag << 31) | (kind << 24) | vlen;
1566 }
1567
1568 static void btf_type_inc_vlen(struct btf_type *t)
1569 {
1570         t->info = btf_type_info(btf_kind(t), btf_vlen(t) + 1, btf_kflag(t));
1571 }
1572
1573 /*
1574  * Append new BTF_KIND_INT type with:
1575  *   - *name* - non-empty, non-NULL type name;
1576  *   - *sz* - power-of-2 (1, 2, 4, ..) size of the type, in bytes;
1577  *   - encoding is a combination of BTF_INT_SIGNED, BTF_INT_CHAR, BTF_INT_BOOL.
1578  * Returns:
1579  *   - >0, type ID of newly added BTF type;
1580  *   - <0, on error.
1581  */
1582 int btf__add_int(struct btf *btf, const char *name, size_t byte_sz, int encoding)
1583 {
1584         struct btf_type *t;
1585         int sz, err, name_off;
1586
1587         /* non-empty name */
1588         if (!name || !name[0])
1589                 return -EINVAL;
1590         /* byte_sz must be power of 2 */
1591         if (!byte_sz || (byte_sz & (byte_sz - 1)) || byte_sz > 16)
1592                 return -EINVAL;
1593         if (encoding & ~(BTF_INT_SIGNED | BTF_INT_CHAR | BTF_INT_BOOL))
1594                 return -EINVAL;
1595
1596         /* deconstruct BTF, if necessary, and invalidate raw_data */
1597         if (btf_ensure_modifiable(btf))
1598                 return -ENOMEM;
1599
1600         sz = sizeof(struct btf_type) + sizeof(int);
1601         t = btf_add_type_mem(btf, sz);
1602         if (!t)
1603                 return -ENOMEM;
1604
1605         /* if something goes wrong later, we might end up with an extra string,
1606          * but that shouldn't be a problem, because BTF can't be constructed
1607          * completely anyway and will most probably be just discarded
1608          */
1609         name_off = btf__add_str(btf, name);
1610         if (name_off < 0)
1611                 return name_off;
1612
1613         t->name_off = name_off;
1614         t->info = btf_type_info(BTF_KIND_INT, 0, 0);
1615         t->size = byte_sz;
1616         /* set INT info, we don't allow setting legacy bit offset/size */
1617         *(__u32 *)(t + 1) = (encoding << 24) | (byte_sz * 8);
1618
1619         err = btf_add_type_idx_entry(btf, btf->hdr->type_len);
1620         if (err)
1621                 return err;
1622
1623         btf->hdr->type_len += sz;
1624         btf->hdr->str_off += sz;
1625         btf->nr_types++;
1626         return btf->nr_types;
1627 }
1628
1629 /* it's completely legal to append BTF types with type IDs pointing forward to
1630  * types that haven't been appended yet, so we only make sure that id looks
1631  * sane, we can't guarantee that ID will always be valid
1632  */
1633 static int validate_type_id(int id)
1634 {
1635         if (id < 0 || id > BTF_MAX_NR_TYPES)
1636                 return -EINVAL;
1637         return 0;
1638 }
1639
1640 /* generic append function for PTR, TYPEDEF, CONST/VOLATILE/RESTRICT */
1641 static int btf_add_ref_kind(struct btf *btf, int kind, const char *name, int ref_type_id)
1642 {
1643         struct btf_type *t;
1644         int sz, name_off = 0, err;
1645
1646         if (validate_type_id(ref_type_id))
1647                 return -EINVAL;
1648
1649         if (btf_ensure_modifiable(btf))
1650                 return -ENOMEM;
1651
1652         sz = sizeof(struct btf_type);
1653         t = btf_add_type_mem(btf, sz);
1654         if (!t)
1655                 return -ENOMEM;
1656
1657         if (name && name[0]) {
1658                 name_off = btf__add_str(btf, name);
1659                 if (name_off < 0)
1660                         return name_off;
1661         }
1662
1663         t->name_off = name_off;
1664         t->info = btf_type_info(kind, 0, 0);
1665         t->type = ref_type_id;
1666
1667         err = btf_add_type_idx_entry(btf, btf->hdr->type_len);
1668         if (err)
1669                 return err;
1670
1671         btf->hdr->type_len += sz;
1672         btf->hdr->str_off += sz;
1673         btf->nr_types++;
1674         return btf->nr_types;
1675 }
1676
1677 /*
1678  * Append new BTF_KIND_PTR type with:
1679  *   - *ref_type_id* - referenced type ID, it might not exist yet;
1680  * Returns:
1681  *   - >0, type ID of newly added BTF type;
1682  *   - <0, on error.
1683  */
1684 int btf__add_ptr(struct btf *btf, int ref_type_id)
1685 {
1686         return btf_add_ref_kind(btf, BTF_KIND_PTR, NULL, ref_type_id);
1687 }
1688
1689 /*
1690  * Append new BTF_KIND_ARRAY type with:
1691  *   - *index_type_id* - type ID of the type describing array index;
1692  *   - *elem_type_id* - type ID of the type describing array element;
1693  *   - *nr_elems* - the size of the array;
1694  * Returns:
1695  *   - >0, type ID of newly added BTF type;
1696  *   - <0, on error.
1697  */
1698 int btf__add_array(struct btf *btf, int index_type_id, int elem_type_id, __u32 nr_elems)
1699 {
1700         struct btf_type *t;
1701         struct btf_array *a;
1702         int sz, err;
1703
1704         if (validate_type_id(index_type_id) || validate_type_id(elem_type_id))
1705                 return -EINVAL;
1706
1707         if (btf_ensure_modifiable(btf))
1708                 return -ENOMEM;
1709
1710         sz = sizeof(struct btf_type) + sizeof(struct btf_array);
1711         t = btf_add_type_mem(btf, sz);
1712         if (!t)
1713                 return -ENOMEM;
1714
1715         t->name_off = 0;
1716         t->info = btf_type_info(BTF_KIND_ARRAY, 0, 0);
1717         t->size = 0;
1718
1719         a = btf_array(t);
1720         a->type = elem_type_id;
1721         a->index_type = index_type_id;
1722         a->nelems = nr_elems;
1723
1724         err = btf_add_type_idx_entry(btf, btf->hdr->type_len);
1725         if (err)
1726                 return err;
1727
1728         btf->hdr->type_len += sz;
1729         btf->hdr->str_off += sz;
1730         btf->nr_types++;
1731         return btf->nr_types;
1732 }
1733
1734 /* generic STRUCT/UNION append function */
1735 static int btf_add_composite(struct btf *btf, int kind, const char *name, __u32 bytes_sz)
1736 {
1737         struct btf_type *t;
1738         int sz, err, name_off = 0;
1739
1740         if (btf_ensure_modifiable(btf))
1741                 return -ENOMEM;
1742
1743         sz = sizeof(struct btf_type);
1744         t = btf_add_type_mem(btf, sz);
1745         if (!t)
1746                 return -ENOMEM;
1747
1748         if (name && name[0]) {
1749                 name_off = btf__add_str(btf, name);
1750                 if (name_off < 0)
1751                         return name_off;
1752         }
1753
1754         /* start out with vlen=0 and no kflag; this will be adjusted when
1755          * adding each member
1756          */
1757         t->name_off = name_off;
1758         t->info = btf_type_info(kind, 0, 0);
1759         t->size = bytes_sz;
1760
1761         err = btf_add_type_idx_entry(btf, btf->hdr->type_len);
1762         if (err)
1763                 return err;
1764
1765         btf->hdr->type_len += sz;
1766         btf->hdr->str_off += sz;
1767         btf->nr_types++;
1768         return btf->nr_types;
1769 }
1770
1771 /*
1772  * Append new BTF_KIND_STRUCT type with:
1773  *   - *name* - name of the struct, can be NULL or empty for anonymous structs;
1774  *   - *byte_sz* - size of the struct, in bytes;
1775  *
1776  * Struct initially has no fields in it. Fields can be added by
1777  * btf__add_field() right after btf__add_struct() succeeds.
1778  *
1779  * Returns:
1780  *   - >0, type ID of newly added BTF type;
1781  *   - <0, on error.
1782  */
1783 int btf__add_struct(struct btf *btf, const char *name, __u32 byte_sz)
1784 {
1785         return btf_add_composite(btf, BTF_KIND_STRUCT, name, byte_sz);
1786 }
1787
1788 /*
1789  * Append new BTF_KIND_UNION type with:
1790  *   - *name* - name of the union, can be NULL or empty for anonymous union;
1791  *   - *byte_sz* - size of the union, in bytes;
1792  *
1793  * Union initially has no fields in it. Fields can be added by
1794  * btf__add_field() right after btf__add_union() succeeds. All fields
1795  * should have *bit_offset* of 0.
1796  *
1797  * Returns:
1798  *   - >0, type ID of newly added BTF type;
1799  *   - <0, on error.
1800  */
1801 int btf__add_union(struct btf *btf, const char *name, __u32 byte_sz)
1802 {
1803         return btf_add_composite(btf, BTF_KIND_UNION, name, byte_sz);
1804 }
1805
1806 /*
1807  * Append new field for the current STRUCT/UNION type with:
1808  *   - *name* - name of the field, can be NULL or empty for anonymous field;
1809  *   - *type_id* - type ID for the type describing field type;
1810  *   - *bit_offset* - bit offset of the start of the field within struct/union;
1811  *   - *bit_size* - bit size of a bitfield, 0 for non-bitfield fields;
1812  * Returns:
1813  *   -  0, on success;
1814  *   - <0, on error.
1815  */
1816 int btf__add_field(struct btf *btf, const char *name, int type_id,
1817                    __u32 bit_offset, __u32 bit_size)
1818 {
1819         struct btf_type *t;
1820         struct btf_member *m;
1821         bool is_bitfield;
1822         int sz, name_off = 0;
1823
1824         /* last type should be union/struct */
1825         if (btf->nr_types == 0)
1826                 return -EINVAL;
1827         t = btf_type_by_id(btf, btf->nr_types);
1828         if (!btf_is_composite(t))
1829                 return -EINVAL;
1830
1831         if (validate_type_id(type_id))
1832                 return -EINVAL;
1833         /* best-effort bit field offset/size enforcement */
1834         is_bitfield = bit_size || (bit_offset % 8 != 0);
1835         if (is_bitfield && (bit_size == 0 || bit_size > 255 || bit_offset > 0xffffff))
1836                 return -EINVAL;
1837
1838         /* only offset 0 is allowed for unions */
1839         if (btf_is_union(t) && bit_offset)
1840                 return -EINVAL;
1841
1842         /* decompose and invalidate raw data */
1843         if (btf_ensure_modifiable(btf))
1844                 return -ENOMEM;
1845
1846         sz = sizeof(struct btf_member);
1847         m = btf_add_type_mem(btf, sz);
1848         if (!m)
1849                 return -ENOMEM;
1850
1851         if (name && name[0]) {
1852                 name_off = btf__add_str(btf, name);
1853                 if (name_off < 0)
1854                         return name_off;
1855         }
1856
1857         m->name_off = name_off;
1858         m->type = type_id;
1859         m->offset = bit_offset | (bit_size << 24);
1860
1861         /* btf_add_type_mem can invalidate t pointer */
1862         t = btf_type_by_id(btf, btf->nr_types);
1863         /* update parent type's vlen and kflag */
1864         t->info = btf_type_info(btf_kind(t), btf_vlen(t) + 1, is_bitfield || btf_kflag(t));
1865
1866         btf->hdr->type_len += sz;
1867         btf->hdr->str_off += sz;
1868         return 0;
1869 }
1870
1871 /*
1872  * Append new BTF_KIND_ENUM type with:
1873  *   - *name* - name of the enum, can be NULL or empty for anonymous enums;
1874  *   - *byte_sz* - size of the enum, in bytes.
1875  *
1876  * Enum initially has no enum values in it (and corresponds to enum forward
1877  * declaration). Enumerator values can be added by btf__add_enum_value()
1878  * immediately after btf__add_enum() succeeds.
1879  *
1880  * Returns:
1881  *   - >0, type ID of newly added BTF type;
1882  *   - <0, on error.
1883  */
1884 int btf__add_enum(struct btf *btf, const char *name, __u32 byte_sz)
1885 {
1886         struct btf_type *t;
1887         int sz, err, name_off = 0;
1888
1889         /* byte_sz must be power of 2 */
1890         if (!byte_sz || (byte_sz & (byte_sz - 1)) || byte_sz > 8)
1891                 return -EINVAL;
1892
1893         if (btf_ensure_modifiable(btf))
1894                 return -ENOMEM;
1895
1896         sz = sizeof(struct btf_type);
1897         t = btf_add_type_mem(btf, sz);
1898         if (!t)
1899                 return -ENOMEM;
1900
1901         if (name && name[0]) {
1902                 name_off = btf__add_str(btf, name);
1903                 if (name_off < 0)
1904                         return name_off;
1905         }
1906
1907         /* start out with vlen=0; it will be adjusted when adding enum values */
1908         t->name_off = name_off;
1909         t->info = btf_type_info(BTF_KIND_ENUM, 0, 0);
1910         t->size = byte_sz;
1911
1912         err = btf_add_type_idx_entry(btf, btf->hdr->type_len);
1913         if (err)
1914                 return err;
1915
1916         btf->hdr->type_len += sz;
1917         btf->hdr->str_off += sz;
1918         btf->nr_types++;
1919         return btf->nr_types;
1920 }
1921
1922 /*
1923  * Append new enum value for the current ENUM type with:
1924  *   - *name* - name of the enumerator value, can't be NULL or empty;
1925  *   - *value* - integer value corresponding to enum value *name*;
1926  * Returns:
1927  *   -  0, on success;
1928  *   - <0, on error.
1929  */
1930 int btf__add_enum_value(struct btf *btf, const char *name, __s64 value)
1931 {
1932         struct btf_type *t;
1933         struct btf_enum *v;
1934         int sz, name_off;
1935
1936         /* last type should be BTF_KIND_ENUM */
1937         if (btf->nr_types == 0)
1938                 return -EINVAL;
1939         t = btf_type_by_id(btf, btf->nr_types);
1940         if (!btf_is_enum(t))
1941                 return -EINVAL;
1942
1943         /* non-empty name */
1944         if (!name || !name[0])
1945                 return -EINVAL;
1946         if (value < INT_MIN || value > UINT_MAX)
1947                 return -E2BIG;
1948
1949         /* decompose and invalidate raw data */
1950         if (btf_ensure_modifiable(btf))
1951                 return -ENOMEM;
1952
1953         sz = sizeof(struct btf_enum);
1954         v = btf_add_type_mem(btf, sz);
1955         if (!v)
1956                 return -ENOMEM;
1957
1958         name_off = btf__add_str(btf, name);
1959         if (name_off < 0)
1960                 return name_off;
1961
1962         v->name_off = name_off;
1963         v->val = value;
1964
1965         /* update parent type's vlen */
1966         t = btf_type_by_id(btf, btf->nr_types);
1967         btf_type_inc_vlen(t);
1968
1969         btf->hdr->type_len += sz;
1970         btf->hdr->str_off += sz;
1971         return 0;
1972 }
1973
1974 /*
1975  * Append new BTF_KIND_FWD type with:
1976  *   - *name*, non-empty/non-NULL name;
1977  *   - *fwd_kind*, kind of forward declaration, one of BTF_FWD_STRUCT,
1978  *     BTF_FWD_UNION, or BTF_FWD_ENUM;
1979  * Returns:
1980  *   - >0, type ID of newly added BTF type;
1981  *   - <0, on error.
1982  */
1983 int btf__add_fwd(struct btf *btf, const char *name, enum btf_fwd_kind fwd_kind)
1984 {
1985         if (!name || !name[0])
1986                 return -EINVAL;
1987
1988         switch (fwd_kind) {
1989         case BTF_FWD_STRUCT:
1990         case BTF_FWD_UNION: {
1991                 struct btf_type *t;
1992                 int id;
1993
1994                 id = btf_add_ref_kind(btf, BTF_KIND_FWD, name, 0);
1995                 if (id <= 0)
1996                         return id;
1997                 t = btf_type_by_id(btf, id);
1998                 t->info = btf_type_info(BTF_KIND_FWD, 0, fwd_kind == BTF_FWD_UNION);
1999                 return id;
2000         }
2001         case BTF_FWD_ENUM:
2002                 /* enum forward in BTF currently is just an enum with no enum
2003                  * values; we also assume a standard 4-byte size for it
2004                  */
2005                 return btf__add_enum(btf, name, sizeof(int));
2006         default:
2007                 return -EINVAL;
2008         }
2009 }
2010
2011 /*
2012  * Append new BTF_KING_TYPEDEF type with:
2013  *   - *name*, non-empty/non-NULL name;
2014  *   - *ref_type_id* - referenced type ID, it might not exist yet;
2015  * Returns:
2016  *   - >0, type ID of newly added BTF type;
2017  *   - <0, on error.
2018  */
2019 int btf__add_typedef(struct btf *btf, const char *name, int ref_type_id)
2020 {
2021         if (!name || !name[0])
2022                 return -EINVAL;
2023
2024         return btf_add_ref_kind(btf, BTF_KIND_TYPEDEF, name, ref_type_id);
2025 }
2026
2027 /*
2028  * Append new BTF_KIND_VOLATILE type with:
2029  *   - *ref_type_id* - referenced type ID, it might not exist yet;
2030  * Returns:
2031  *   - >0, type ID of newly added BTF type;
2032  *   - <0, on error.
2033  */
2034 int btf__add_volatile(struct btf *btf, int ref_type_id)
2035 {
2036         return btf_add_ref_kind(btf, BTF_KIND_VOLATILE, NULL, ref_type_id);
2037 }
2038
2039 /*
2040  * Append new BTF_KIND_CONST type with:
2041  *   - *ref_type_id* - referenced type ID, it might not exist yet;
2042  * Returns:
2043  *   - >0, type ID of newly added BTF type;
2044  *   - <0, on error.
2045  */
2046 int btf__add_const(struct btf *btf, int ref_type_id)
2047 {
2048         return btf_add_ref_kind(btf, BTF_KIND_CONST, NULL, ref_type_id);
2049 }
2050
2051 /*
2052  * Append new BTF_KIND_RESTRICT type with:
2053  *   - *ref_type_id* - referenced type ID, it might not exist yet;
2054  * Returns:
2055  *   - >0, type ID of newly added BTF type;
2056  *   - <0, on error.
2057  */
2058 int btf__add_restrict(struct btf *btf, int ref_type_id)
2059 {
2060         return btf_add_ref_kind(btf, BTF_KIND_RESTRICT, NULL, ref_type_id);
2061 }
2062
2063 /*
2064  * Append new BTF_KIND_FUNC type with:
2065  *   - *name*, non-empty/non-NULL name;
2066  *   - *proto_type_id* - FUNC_PROTO's type ID, it might not exist yet;
2067  * Returns:
2068  *   - >0, type ID of newly added BTF type;
2069  *   - <0, on error.
2070  */
2071 int btf__add_func(struct btf *btf, const char *name,
2072                   enum btf_func_linkage linkage, int proto_type_id)
2073 {
2074         int id;
2075
2076         if (!name || !name[0])
2077                 return -EINVAL;
2078         if (linkage != BTF_FUNC_STATIC && linkage != BTF_FUNC_GLOBAL &&
2079             linkage != BTF_FUNC_EXTERN)
2080                 return -EINVAL;
2081
2082         id = btf_add_ref_kind(btf, BTF_KIND_FUNC, name, proto_type_id);
2083         if (id > 0) {
2084                 struct btf_type *t = btf_type_by_id(btf, id);
2085
2086                 t->info = btf_type_info(BTF_KIND_FUNC, linkage, 0);
2087         }
2088         return id;
2089 }
2090
2091 /*
2092  * Append new BTF_KIND_FUNC_PROTO with:
2093  *   - *ret_type_id* - type ID for return result of a function.
2094  *
2095  * Function prototype initially has no arguments, but they can be added by
2096  * btf__add_func_param() one by one, immediately after
2097  * btf__add_func_proto() succeeded.
2098  *
2099  * Returns:
2100  *   - >0, type ID of newly added BTF type;
2101  *   - <0, on error.
2102  */
2103 int btf__add_func_proto(struct btf *btf, int ret_type_id)
2104 {
2105         struct btf_type *t;
2106         int sz, err;
2107
2108         if (validate_type_id(ret_type_id))
2109                 return -EINVAL;
2110
2111         if (btf_ensure_modifiable(btf))
2112                 return -ENOMEM;
2113
2114         sz = sizeof(struct btf_type);
2115         t = btf_add_type_mem(btf, sz);
2116         if (!t)
2117                 return -ENOMEM;
2118
2119         /* start out with vlen=0; this will be adjusted when adding enum
2120          * values, if necessary
2121          */
2122         t->name_off = 0;
2123         t->info = btf_type_info(BTF_KIND_FUNC_PROTO, 0, 0);
2124         t->type = ret_type_id;
2125
2126         err = btf_add_type_idx_entry(btf, btf->hdr->type_len);
2127         if (err)
2128                 return err;
2129
2130         btf->hdr->type_len += sz;
2131         btf->hdr->str_off += sz;
2132         btf->nr_types++;
2133         return btf->nr_types;
2134 }
2135
2136 /*
2137  * Append new function parameter for current FUNC_PROTO type with:
2138  *   - *name* - parameter name, can be NULL or empty;
2139  *   - *type_id* - type ID describing the type of the parameter.
2140  * Returns:
2141  *   -  0, on success;
2142  *   - <0, on error.
2143  */
2144 int btf__add_func_param(struct btf *btf, const char *name, int type_id)
2145 {
2146         struct btf_type *t;
2147         struct btf_param *p;
2148         int sz, name_off = 0;
2149
2150         if (validate_type_id(type_id))
2151                 return -EINVAL;
2152
2153         /* last type should be BTF_KIND_FUNC_PROTO */
2154         if (btf->nr_types == 0)
2155                 return -EINVAL;
2156         t = btf_type_by_id(btf, btf->nr_types);
2157         if (!btf_is_func_proto(t))
2158                 return -EINVAL;
2159
2160         /* decompose and invalidate raw data */
2161         if (btf_ensure_modifiable(btf))
2162                 return -ENOMEM;
2163
2164         sz = sizeof(struct btf_param);
2165         p = btf_add_type_mem(btf, sz);
2166         if (!p)
2167                 return -ENOMEM;
2168
2169         if (name && name[0]) {
2170                 name_off = btf__add_str(btf, name);
2171                 if (name_off < 0)
2172                         return name_off;
2173         }
2174
2175         p->name_off = name_off;
2176         p->type = type_id;
2177
2178         /* update parent type's vlen */
2179         t = btf_type_by_id(btf, btf->nr_types);
2180         btf_type_inc_vlen(t);
2181
2182         btf->hdr->type_len += sz;
2183         btf->hdr->str_off += sz;
2184         return 0;
2185 }
2186
2187 /*
2188  * Append new BTF_KIND_VAR type with:
2189  *   - *name* - non-empty/non-NULL name;
2190  *   - *linkage* - variable linkage, one of BTF_VAR_STATIC,
2191  *     BTF_VAR_GLOBAL_ALLOCATED, or BTF_VAR_GLOBAL_EXTERN;
2192  *   - *type_id* - type ID of the type describing the type of the variable.
2193  * Returns:
2194  *   - >0, type ID of newly added BTF type;
2195  *   - <0, on error.
2196  */
2197 int btf__add_var(struct btf *btf, const char *name, int linkage, int type_id)
2198 {
2199         struct btf_type *t;
2200         struct btf_var *v;
2201         int sz, err, name_off;
2202
2203         /* non-empty name */
2204         if (!name || !name[0])
2205                 return -EINVAL;
2206         if (linkage != BTF_VAR_STATIC && linkage != BTF_VAR_GLOBAL_ALLOCATED &&
2207             linkage != BTF_VAR_GLOBAL_EXTERN)
2208                 return -EINVAL;
2209         if (validate_type_id(type_id))
2210                 return -EINVAL;
2211
2212         /* deconstruct BTF, if necessary, and invalidate raw_data */
2213         if (btf_ensure_modifiable(btf))
2214                 return -ENOMEM;
2215
2216         sz = sizeof(struct btf_type) + sizeof(struct btf_var);
2217         t = btf_add_type_mem(btf, sz);
2218         if (!t)
2219                 return -ENOMEM;
2220
2221         name_off = btf__add_str(btf, name);
2222         if (name_off < 0)
2223                 return name_off;
2224
2225         t->name_off = name_off;
2226         t->info = btf_type_info(BTF_KIND_VAR, 0, 0);
2227         t->type = type_id;
2228
2229         v = btf_var(t);
2230         v->linkage = linkage;
2231
2232         err = btf_add_type_idx_entry(btf, btf->hdr->type_len);
2233         if (err)
2234                 return err;
2235
2236         btf->hdr->type_len += sz;
2237         btf->hdr->str_off += sz;
2238         btf->nr_types++;
2239         return btf->nr_types;
2240 }
2241
2242 /*
2243  * Append new BTF_KIND_DATASEC type with:
2244  *   - *name* - non-empty/non-NULL name;
2245  *   - *byte_sz* - data section size, in bytes.
2246  *
2247  * Data section is initially empty. Variables info can be added with
2248  * btf__add_datasec_var_info() calls, after btf__add_datasec() succeeds.
2249  *
2250  * Returns:
2251  *   - >0, type ID of newly added BTF type;
2252  *   - <0, on error.
2253  */
2254 int btf__add_datasec(struct btf *btf, const char *name, __u32 byte_sz)
2255 {
2256         struct btf_type *t;
2257         int sz, err, name_off;
2258
2259         /* non-empty name */
2260         if (!name || !name[0])
2261                 return -EINVAL;
2262
2263         if (btf_ensure_modifiable(btf))
2264                 return -ENOMEM;
2265
2266         sz = sizeof(struct btf_type);
2267         t = btf_add_type_mem(btf, sz);
2268         if (!t)
2269                 return -ENOMEM;
2270
2271         name_off = btf__add_str(btf, name);
2272         if (name_off < 0)
2273                 return name_off;
2274
2275         /* start with vlen=0, which will be update as var_secinfos are added */
2276         t->name_off = name_off;
2277         t->info = btf_type_info(BTF_KIND_DATASEC, 0, 0);
2278         t->size = byte_sz;
2279
2280         err = btf_add_type_idx_entry(btf, btf->hdr->type_len);
2281         if (err)
2282                 return err;
2283
2284         btf->hdr->type_len += sz;
2285         btf->hdr->str_off += sz;
2286         btf->nr_types++;
2287         return btf->nr_types;
2288 }
2289
2290 /*
2291  * Append new data section variable information entry for current DATASEC type:
2292  *   - *var_type_id* - type ID, describing type of the variable;
2293  *   - *offset* - variable offset within data section, in bytes;
2294  *   - *byte_sz* - variable size, in bytes.
2295  *
2296  * Returns:
2297  *   -  0, on success;
2298  *   - <0, on error.
2299  */
2300 int btf__add_datasec_var_info(struct btf *btf, int var_type_id, __u32 offset, __u32 byte_sz)
2301 {
2302         struct btf_type *t;
2303         struct btf_var_secinfo *v;
2304         int sz;
2305
2306         /* last type should be BTF_KIND_DATASEC */
2307         if (btf->nr_types == 0)
2308                 return -EINVAL;
2309         t = btf_type_by_id(btf, btf->nr_types);
2310         if (!btf_is_datasec(t))
2311                 return -EINVAL;
2312
2313         if (validate_type_id(var_type_id))
2314                 return -EINVAL;
2315
2316         /* decompose and invalidate raw data */
2317         if (btf_ensure_modifiable(btf))
2318                 return -ENOMEM;
2319
2320         sz = sizeof(struct btf_var_secinfo);
2321         v = btf_add_type_mem(btf, sz);
2322         if (!v)
2323                 return -ENOMEM;
2324
2325         v->type = var_type_id;
2326         v->offset = offset;
2327         v->size = byte_sz;
2328
2329         /* update parent type's vlen */
2330         t = btf_type_by_id(btf, btf->nr_types);
2331         btf_type_inc_vlen(t);
2332
2333         btf->hdr->type_len += sz;
2334         btf->hdr->str_off += sz;
2335         return 0;
2336 }
2337
2338 struct btf_ext_sec_setup_param {
2339         __u32 off;
2340         __u32 len;
2341         __u32 min_rec_size;
2342         struct btf_ext_info *ext_info;
2343         const char *desc;
2344 };
2345
2346 static int btf_ext_setup_info(struct btf_ext *btf_ext,
2347                               struct btf_ext_sec_setup_param *ext_sec)
2348 {
2349         const struct btf_ext_info_sec *sinfo;
2350         struct btf_ext_info *ext_info;
2351         __u32 info_left, record_size;
2352         /* The start of the info sec (including the __u32 record_size). */
2353         void *info;
2354
2355         if (ext_sec->len == 0)
2356                 return 0;
2357
2358         if (ext_sec->off & 0x03) {
2359                 pr_debug(".BTF.ext %s section is not aligned to 4 bytes\n",
2360                      ext_sec->desc);
2361                 return -EINVAL;
2362         }
2363
2364         info = btf_ext->data + btf_ext->hdr->hdr_len + ext_sec->off;
2365         info_left = ext_sec->len;
2366
2367         if (btf_ext->data + btf_ext->data_size < info + ext_sec->len) {
2368                 pr_debug("%s section (off:%u len:%u) is beyond the end of the ELF section .BTF.ext\n",
2369                          ext_sec->desc, ext_sec->off, ext_sec->len);
2370                 return -EINVAL;
2371         }
2372
2373         /* At least a record size */
2374         if (info_left < sizeof(__u32)) {
2375                 pr_debug(".BTF.ext %s record size not found\n", ext_sec->desc);
2376                 return -EINVAL;
2377         }
2378
2379         /* The record size needs to meet the minimum standard */
2380         record_size = *(__u32 *)info;
2381         if (record_size < ext_sec->min_rec_size ||
2382             record_size & 0x03) {
2383                 pr_debug("%s section in .BTF.ext has invalid record size %u\n",
2384                          ext_sec->desc, record_size);
2385                 return -EINVAL;
2386         }
2387
2388         sinfo = info + sizeof(__u32);
2389         info_left -= sizeof(__u32);
2390
2391         /* If no records, return failure now so .BTF.ext won't be used. */
2392         if (!info_left) {
2393                 pr_debug("%s section in .BTF.ext has no records", ext_sec->desc);
2394                 return -EINVAL;
2395         }
2396
2397         while (info_left) {
2398                 unsigned int sec_hdrlen = sizeof(struct btf_ext_info_sec);
2399                 __u64 total_record_size;
2400                 __u32 num_records;
2401
2402                 if (info_left < sec_hdrlen) {
2403                         pr_debug("%s section header is not found in .BTF.ext\n",
2404                              ext_sec->desc);
2405                         return -EINVAL;
2406                 }
2407
2408                 num_records = sinfo->num_info;
2409                 if (num_records == 0) {
2410                         pr_debug("%s section has incorrect num_records in .BTF.ext\n",
2411                              ext_sec->desc);
2412                         return -EINVAL;
2413                 }
2414
2415                 total_record_size = sec_hdrlen +
2416                                     (__u64)num_records * record_size;
2417                 if (info_left < total_record_size) {
2418                         pr_debug("%s section has incorrect num_records in .BTF.ext\n",
2419                              ext_sec->desc);
2420                         return -EINVAL;
2421                 }
2422
2423                 info_left -= total_record_size;
2424                 sinfo = (void *)sinfo + total_record_size;
2425         }
2426
2427         ext_info = ext_sec->ext_info;
2428         ext_info->len = ext_sec->len - sizeof(__u32);
2429         ext_info->rec_size = record_size;
2430         ext_info->info = info + sizeof(__u32);
2431
2432         return 0;
2433 }
2434
2435 static int btf_ext_setup_func_info(struct btf_ext *btf_ext)
2436 {
2437         struct btf_ext_sec_setup_param param = {
2438                 .off = btf_ext->hdr->func_info_off,
2439                 .len = btf_ext->hdr->func_info_len,
2440                 .min_rec_size = sizeof(struct bpf_func_info_min),
2441                 .ext_info = &btf_ext->func_info,
2442                 .desc = "func_info"
2443         };
2444
2445         return btf_ext_setup_info(btf_ext, &param);
2446 }
2447
2448 static int btf_ext_setup_line_info(struct btf_ext *btf_ext)
2449 {
2450         struct btf_ext_sec_setup_param param = {
2451                 .off = btf_ext->hdr->line_info_off,
2452                 .len = btf_ext->hdr->line_info_len,
2453                 .min_rec_size = sizeof(struct bpf_line_info_min),
2454                 .ext_info = &btf_ext->line_info,
2455                 .desc = "line_info",
2456         };
2457
2458         return btf_ext_setup_info(btf_ext, &param);
2459 }
2460
2461 static int btf_ext_setup_core_relos(struct btf_ext *btf_ext)
2462 {
2463         struct btf_ext_sec_setup_param param = {
2464                 .off = btf_ext->hdr->core_relo_off,
2465                 .len = btf_ext->hdr->core_relo_len,
2466                 .min_rec_size = sizeof(struct bpf_core_relo),
2467                 .ext_info = &btf_ext->core_relo_info,
2468                 .desc = "core_relo",
2469         };
2470
2471         return btf_ext_setup_info(btf_ext, &param);
2472 }
2473
2474 static int btf_ext_parse_hdr(__u8 *data, __u32 data_size)
2475 {
2476         const struct btf_ext_header *hdr = (struct btf_ext_header *)data;
2477
2478         if (data_size < offsetofend(struct btf_ext_header, hdr_len) ||
2479             data_size < hdr->hdr_len) {
2480                 pr_debug("BTF.ext header not found");
2481                 return -EINVAL;
2482         }
2483
2484         if (hdr->magic == bswap_16(BTF_MAGIC)) {
2485                 pr_warn("BTF.ext in non-native endianness is not supported\n");
2486                 return -ENOTSUP;
2487         } else if (hdr->magic != BTF_MAGIC) {
2488                 pr_debug("Invalid BTF.ext magic:%x\n", hdr->magic);
2489                 return -EINVAL;
2490         }
2491
2492         if (hdr->version != BTF_VERSION) {
2493                 pr_debug("Unsupported BTF.ext version:%u\n", hdr->version);
2494                 return -ENOTSUP;
2495         }
2496
2497         if (hdr->flags) {
2498                 pr_debug("Unsupported BTF.ext flags:%x\n", hdr->flags);
2499                 return -ENOTSUP;
2500         }
2501
2502         if (data_size == hdr->hdr_len) {
2503                 pr_debug("BTF.ext has no data\n");
2504                 return -EINVAL;
2505         }
2506
2507         return 0;
2508 }
2509
2510 void btf_ext__free(struct btf_ext *btf_ext)
2511 {
2512         if (IS_ERR_OR_NULL(btf_ext))
2513                 return;
2514         free(btf_ext->data);
2515         free(btf_ext);
2516 }
2517
2518 struct btf_ext *btf_ext__new(__u8 *data, __u32 size)
2519 {
2520         struct btf_ext *btf_ext;
2521         int err;
2522
2523         err = btf_ext_parse_hdr(data, size);
2524         if (err)
2525                 return ERR_PTR(err);
2526
2527         btf_ext = calloc(1, sizeof(struct btf_ext));
2528         if (!btf_ext)
2529                 return ERR_PTR(-ENOMEM);
2530
2531         btf_ext->data_size = size;
2532         btf_ext->data = malloc(size);
2533         if (!btf_ext->data) {
2534                 err = -ENOMEM;
2535                 goto done;
2536         }
2537         memcpy(btf_ext->data, data, size);
2538
2539         if (btf_ext->hdr->hdr_len <
2540             offsetofend(struct btf_ext_header, line_info_len))
2541                 goto done;
2542         err = btf_ext_setup_func_info(btf_ext);
2543         if (err)
2544                 goto done;
2545
2546         err = btf_ext_setup_line_info(btf_ext);
2547         if (err)
2548                 goto done;
2549
2550         if (btf_ext->hdr->hdr_len < offsetofend(struct btf_ext_header, core_relo_len))
2551                 goto done;
2552         err = btf_ext_setup_core_relos(btf_ext);
2553         if (err)
2554                 goto done;
2555
2556 done:
2557         if (err) {
2558                 btf_ext__free(btf_ext);
2559                 return ERR_PTR(err);
2560         }
2561
2562         return btf_ext;
2563 }
2564
2565 const void *btf_ext__get_raw_data(const struct btf_ext *btf_ext, __u32 *size)
2566 {
2567         *size = btf_ext->data_size;
2568         return btf_ext->data;
2569 }
2570
2571 static int btf_ext_reloc_info(const struct btf *btf,
2572                               const struct btf_ext_info *ext_info,
2573                               const char *sec_name, __u32 insns_cnt,
2574                               void **info, __u32 *cnt)
2575 {
2576         __u32 sec_hdrlen = sizeof(struct btf_ext_info_sec);
2577         __u32 i, record_size, existing_len, records_len;
2578         struct btf_ext_info_sec *sinfo;
2579         const char *info_sec_name;
2580         __u64 remain_len;
2581         void *data;
2582
2583         record_size = ext_info->rec_size;
2584         sinfo = ext_info->info;
2585         remain_len = ext_info->len;
2586         while (remain_len > 0) {
2587                 records_len = sinfo->num_info * record_size;
2588                 info_sec_name = btf__name_by_offset(btf, sinfo->sec_name_off);
2589                 if (strcmp(info_sec_name, sec_name)) {
2590                         remain_len -= sec_hdrlen + records_len;
2591                         sinfo = (void *)sinfo + sec_hdrlen + records_len;
2592                         continue;
2593                 }
2594
2595                 existing_len = (*cnt) * record_size;
2596                 data = realloc(*info, existing_len + records_len);
2597                 if (!data)
2598                         return -ENOMEM;
2599
2600                 memcpy(data + existing_len, sinfo->data, records_len);
2601                 /* adjust insn_off only, the rest data will be passed
2602                  * to the kernel.
2603                  */
2604                 for (i = 0; i < sinfo->num_info; i++) {
2605                         __u32 *insn_off;
2606
2607                         insn_off = data + existing_len + (i * record_size);
2608                         *insn_off = *insn_off / sizeof(struct bpf_insn) +
2609                                 insns_cnt;
2610                 }
2611                 *info = data;
2612                 *cnt += sinfo->num_info;
2613                 return 0;
2614         }
2615
2616         return -ENOENT;
2617 }
2618
2619 int btf_ext__reloc_func_info(const struct btf *btf,
2620                              const struct btf_ext *btf_ext,
2621                              const char *sec_name, __u32 insns_cnt,
2622                              void **func_info, __u32 *cnt)
2623 {
2624         return btf_ext_reloc_info(btf, &btf_ext->func_info, sec_name,
2625                                   insns_cnt, func_info, cnt);
2626 }
2627
2628 int btf_ext__reloc_line_info(const struct btf *btf,
2629                              const struct btf_ext *btf_ext,
2630                              const char *sec_name, __u32 insns_cnt,
2631                              void **line_info, __u32 *cnt)
2632 {
2633         return btf_ext_reloc_info(btf, &btf_ext->line_info, sec_name,
2634                                   insns_cnt, line_info, cnt);
2635 }
2636
2637 __u32 btf_ext__func_info_rec_size(const struct btf_ext *btf_ext)
2638 {
2639         return btf_ext->func_info.rec_size;
2640 }
2641
2642 __u32 btf_ext__line_info_rec_size(const struct btf_ext *btf_ext)
2643 {
2644         return btf_ext->line_info.rec_size;
2645 }
2646
2647 struct btf_dedup;
2648
2649 static struct btf_dedup *btf_dedup_new(struct btf *btf, struct btf_ext *btf_ext,
2650                                        const struct btf_dedup_opts *opts);
2651 static void btf_dedup_free(struct btf_dedup *d);
2652 static int btf_dedup_strings(struct btf_dedup *d);
2653 static int btf_dedup_prim_types(struct btf_dedup *d);
2654 static int btf_dedup_struct_types(struct btf_dedup *d);
2655 static int btf_dedup_ref_types(struct btf_dedup *d);
2656 static int btf_dedup_compact_types(struct btf_dedup *d);
2657 static int btf_dedup_remap_types(struct btf_dedup *d);
2658
2659 /*
2660  * Deduplicate BTF types and strings.
2661  *
2662  * BTF dedup algorithm takes as an input `struct btf` representing `.BTF` ELF
2663  * section with all BTF type descriptors and string data. It overwrites that
2664  * memory in-place with deduplicated types and strings without any loss of
2665  * information. If optional `struct btf_ext` representing '.BTF.ext' ELF section
2666  * is provided, all the strings referenced from .BTF.ext section are honored
2667  * and updated to point to the right offsets after deduplication.
2668  *
2669  * If function returns with error, type/string data might be garbled and should
2670  * be discarded.
2671  *
2672  * More verbose and detailed description of both problem btf_dedup is solving,
2673  * as well as solution could be found at:
2674  * https://facebookmicrosites.github.io/bpf/blog/2018/11/14/btf-enhancement.html
2675  *
2676  * Problem description and justification
2677  * =====================================
2678  *
2679  * BTF type information is typically emitted either as a result of conversion
2680  * from DWARF to BTF or directly by compiler. In both cases, each compilation
2681  * unit contains information about a subset of all the types that are used
2682  * in an application. These subsets are frequently overlapping and contain a lot
2683  * of duplicated information when later concatenated together into a single
2684  * binary. This algorithm ensures that each unique type is represented by single
2685  * BTF type descriptor, greatly reducing resulting size of BTF data.
2686  *
2687  * Compilation unit isolation and subsequent duplication of data is not the only
2688  * problem. The same type hierarchy (e.g., struct and all the type that struct
2689  * references) in different compilation units can be represented in BTF to
2690  * various degrees of completeness (or, rather, incompleteness) due to
2691  * struct/union forward declarations.
2692  *
2693  * Let's take a look at an example, that we'll use to better understand the
2694  * problem (and solution). Suppose we have two compilation units, each using
2695  * same `struct S`, but each of them having incomplete type information about
2696  * struct's fields:
2697  *
2698  * // CU #1:
2699  * struct S;
2700  * struct A {
2701  *      int a;
2702  *      struct A* self;
2703  *      struct S* parent;
2704  * };
2705  * struct B;
2706  * struct S {
2707  *      struct A* a_ptr;
2708  *      struct B* b_ptr;
2709  * };
2710  *
2711  * // CU #2:
2712  * struct S;
2713  * struct A;
2714  * struct B {
2715  *      int b;
2716  *      struct B* self;
2717  *      struct S* parent;
2718  * };
2719  * struct S {
2720  *      struct A* a_ptr;
2721  *      struct B* b_ptr;
2722  * };
2723  *
2724  * In case of CU #1, BTF data will know only that `struct B` exist (but no
2725  * more), but will know the complete type information about `struct A`. While
2726  * for CU #2, it will know full type information about `struct B`, but will
2727  * only know about forward declaration of `struct A` (in BTF terms, it will
2728  * have `BTF_KIND_FWD` type descriptor with name `B`).
2729  *
2730  * This compilation unit isolation means that it's possible that there is no
2731  * single CU with complete type information describing structs `S`, `A`, and
2732  * `B`. Also, we might get tons of duplicated and redundant type information.
2733  *
2734  * Additional complication we need to keep in mind comes from the fact that
2735  * types, in general, can form graphs containing cycles, not just DAGs.
2736  *
2737  * While algorithm does deduplication, it also merges and resolves type
2738  * information (unless disabled throught `struct btf_opts`), whenever possible.
2739  * E.g., in the example above with two compilation units having partial type
2740  * information for structs `A` and `B`, the output of algorithm will emit
2741  * a single copy of each BTF type that describes structs `A`, `B`, and `S`
2742  * (as well as type information for `int` and pointers), as if they were defined
2743  * in a single compilation unit as:
2744  *
2745  * struct A {
2746  *      int a;
2747  *      struct A* self;
2748  *      struct S* parent;
2749  * };
2750  * struct B {
2751  *      int b;
2752  *      struct B* self;
2753  *      struct S* parent;
2754  * };
2755  * struct S {
2756  *      struct A* a_ptr;
2757  *      struct B* b_ptr;
2758  * };
2759  *
2760  * Algorithm summary
2761  * =================
2762  *
2763  * Algorithm completes its work in 6 separate passes:
2764  *
2765  * 1. Strings deduplication.
2766  * 2. Primitive types deduplication (int, enum, fwd).
2767  * 3. Struct/union types deduplication.
2768  * 4. Reference types deduplication (pointers, typedefs, arrays, funcs, func
2769  *    protos, and const/volatile/restrict modifiers).
2770  * 5. Types compaction.
2771  * 6. Types remapping.
2772  *
2773  * Algorithm determines canonical type descriptor, which is a single
2774  * representative type for each truly unique type. This canonical type is the
2775  * one that will go into final deduplicated BTF type information. For
2776  * struct/unions, it is also the type that algorithm will merge additional type
2777  * information into (while resolving FWDs), as it discovers it from data in
2778  * other CUs. Each input BTF type eventually gets either mapped to itself, if
2779  * that type is canonical, or to some other type, if that type is equivalent
2780  * and was chosen as canonical representative. This mapping is stored in
2781  * `btf_dedup->map` array. This map is also used to record STRUCT/UNION that
2782  * FWD type got resolved to.
2783  *
2784  * To facilitate fast discovery of canonical types, we also maintain canonical
2785  * index (`btf_dedup->dedup_table`), which maps type descriptor's signature hash
2786  * (i.e., hashed kind, name, size, fields, etc) into a list of canonical types
2787  * that match that signature. With sufficiently good choice of type signature
2788  * hashing function, we can limit number of canonical types for each unique type
2789  * signature to a very small number, allowing to find canonical type for any
2790  * duplicated type very quickly.
2791  *
2792  * Struct/union deduplication is the most critical part and algorithm for
2793  * deduplicating structs/unions is described in greater details in comments for
2794  * `btf_dedup_is_equiv` function.
2795  */
2796 int btf__dedup(struct btf *btf, struct btf_ext *btf_ext,
2797                const struct btf_dedup_opts *opts)
2798 {
2799         struct btf_dedup *d = btf_dedup_new(btf, btf_ext, opts);
2800         int err;
2801
2802         if (IS_ERR(d)) {
2803                 pr_debug("btf_dedup_new failed: %ld", PTR_ERR(d));
2804                 return -EINVAL;
2805         }
2806
2807         if (btf_ensure_modifiable(btf))
2808                 return -ENOMEM;
2809
2810         err = btf_dedup_strings(d);
2811         if (err < 0) {
2812                 pr_debug("btf_dedup_strings failed:%d\n", err);
2813                 goto done;
2814         }
2815         err = btf_dedup_prim_types(d);
2816         if (err < 0) {
2817                 pr_debug("btf_dedup_prim_types failed:%d\n", err);
2818                 goto done;
2819         }
2820         err = btf_dedup_struct_types(d);
2821         if (err < 0) {
2822                 pr_debug("btf_dedup_struct_types failed:%d\n", err);
2823                 goto done;
2824         }
2825         err = btf_dedup_ref_types(d);
2826         if (err < 0) {
2827                 pr_debug("btf_dedup_ref_types failed:%d\n", err);
2828                 goto done;
2829         }
2830         err = btf_dedup_compact_types(d);
2831         if (err < 0) {
2832                 pr_debug("btf_dedup_compact_types failed:%d\n", err);
2833                 goto done;
2834         }
2835         err = btf_dedup_remap_types(d);
2836         if (err < 0) {
2837                 pr_debug("btf_dedup_remap_types failed:%d\n", err);
2838                 goto done;
2839         }
2840
2841 done:
2842         btf_dedup_free(d);
2843         return err;
2844 }
2845
2846 #define BTF_UNPROCESSED_ID ((__u32)-1)
2847 #define BTF_IN_PROGRESS_ID ((__u32)-2)
2848
2849 struct btf_dedup {
2850         /* .BTF section to be deduped in-place */
2851         struct btf *btf;
2852         /*
2853          * Optional .BTF.ext section. When provided, any strings referenced
2854          * from it will be taken into account when deduping strings
2855          */
2856         struct btf_ext *btf_ext;
2857         /*
2858          * This is a map from any type's signature hash to a list of possible
2859          * canonical representative type candidates. Hash collisions are
2860          * ignored, so even types of various kinds can share same list of
2861          * candidates, which is fine because we rely on subsequent
2862          * btf_xxx_equal() checks to authoritatively verify type equality.
2863          */
2864         struct hashmap *dedup_table;
2865         /* Canonical types map */
2866         __u32 *map;
2867         /* Hypothetical mapping, used during type graph equivalence checks */
2868         __u32 *hypot_map;
2869         __u32 *hypot_list;
2870         size_t hypot_cnt;
2871         size_t hypot_cap;
2872         /* Various option modifying behavior of algorithm */
2873         struct btf_dedup_opts opts;
2874 };
2875
2876 struct btf_str_ptr {
2877         const char *str;
2878         __u32 new_off;
2879         bool used;
2880 };
2881
2882 struct btf_str_ptrs {
2883         struct btf_str_ptr *ptrs;
2884         const char *data;
2885         __u32 cnt;
2886         __u32 cap;
2887 };
2888
2889 static long hash_combine(long h, long value)
2890 {
2891         return h * 31 + value;
2892 }
2893
2894 #define for_each_dedup_cand(d, node, hash) \
2895         hashmap__for_each_key_entry(d->dedup_table, node, (void *)hash)
2896
2897 static int btf_dedup_table_add(struct btf_dedup *d, long hash, __u32 type_id)
2898 {
2899         return hashmap__append(d->dedup_table,
2900                                (void *)hash, (void *)(long)type_id);
2901 }
2902
2903 static int btf_dedup_hypot_map_add(struct btf_dedup *d,
2904                                    __u32 from_id, __u32 to_id)
2905 {
2906         if (d->hypot_cnt == d->hypot_cap) {
2907                 __u32 *new_list;
2908
2909                 d->hypot_cap += max((size_t)16, d->hypot_cap / 2);
2910                 new_list = libbpf_reallocarray(d->hypot_list, d->hypot_cap, sizeof(__u32));
2911                 if (!new_list)
2912                         return -ENOMEM;
2913                 d->hypot_list = new_list;
2914         }
2915         d->hypot_list[d->hypot_cnt++] = from_id;
2916         d->hypot_map[from_id] = to_id;
2917         return 0;
2918 }
2919
2920 static void btf_dedup_clear_hypot_map(struct btf_dedup *d)
2921 {
2922         int i;
2923
2924         for (i = 0; i < d->hypot_cnt; i++)
2925                 d->hypot_map[d->hypot_list[i]] = BTF_UNPROCESSED_ID;
2926         d->hypot_cnt = 0;
2927 }
2928
2929 static void btf_dedup_free(struct btf_dedup *d)
2930 {
2931         hashmap__free(d->dedup_table);
2932         d->dedup_table = NULL;
2933
2934         free(d->map);
2935         d->map = NULL;
2936
2937         free(d->hypot_map);
2938         d->hypot_map = NULL;
2939
2940         free(d->hypot_list);
2941         d->hypot_list = NULL;
2942
2943         free(d);
2944 }
2945
2946 static size_t btf_dedup_identity_hash_fn(const void *key, void *ctx)
2947 {
2948         return (size_t)key;
2949 }
2950
2951 static size_t btf_dedup_collision_hash_fn(const void *key, void *ctx)
2952 {
2953         return 0;
2954 }
2955
2956 static bool btf_dedup_equal_fn(const void *k1, const void *k2, void *ctx)
2957 {
2958         return k1 == k2;
2959 }
2960
2961 static struct btf_dedup *btf_dedup_new(struct btf *btf, struct btf_ext *btf_ext,
2962                                        const struct btf_dedup_opts *opts)
2963 {
2964         struct btf_dedup *d = calloc(1, sizeof(struct btf_dedup));
2965         hashmap_hash_fn hash_fn = btf_dedup_identity_hash_fn;
2966         int i, err = 0;
2967
2968         if (!d)
2969                 return ERR_PTR(-ENOMEM);
2970
2971         d->opts.dont_resolve_fwds = opts && opts->dont_resolve_fwds;
2972         /* dedup_table_size is now used only to force collisions in tests */
2973         if (opts && opts->dedup_table_size == 1)
2974                 hash_fn = btf_dedup_collision_hash_fn;
2975
2976         d->btf = btf;
2977         d->btf_ext = btf_ext;
2978
2979         d->dedup_table = hashmap__new(hash_fn, btf_dedup_equal_fn, NULL);
2980         if (IS_ERR(d->dedup_table)) {
2981                 err = PTR_ERR(d->dedup_table);
2982                 d->dedup_table = NULL;
2983                 goto done;
2984         }
2985
2986         d->map = malloc(sizeof(__u32) * (1 + btf->nr_types));
2987         if (!d->map) {
2988                 err = -ENOMEM;
2989                 goto done;
2990         }
2991         /* special BTF "void" type is made canonical immediately */
2992         d->map[0] = 0;
2993         for (i = 1; i <= btf->nr_types; i++) {
2994                 struct btf_type *t = btf_type_by_id(d->btf, i);
2995
2996                 /* VAR and DATASEC are never deduped and are self-canonical */
2997                 if (btf_is_var(t) || btf_is_datasec(t))
2998                         d->map[i] = i;
2999                 else
3000                         d->map[i] = BTF_UNPROCESSED_ID;
3001         }
3002
3003         d->hypot_map = malloc(sizeof(__u32) * (1 + btf->nr_types));
3004         if (!d->hypot_map) {
3005                 err = -ENOMEM;
3006                 goto done;
3007         }
3008         for (i = 0; i <= btf->nr_types; i++)
3009                 d->hypot_map[i] = BTF_UNPROCESSED_ID;
3010
3011 done:
3012         if (err) {
3013                 btf_dedup_free(d);
3014                 return ERR_PTR(err);
3015         }
3016
3017         return d;
3018 }
3019
3020 typedef int (*str_off_fn_t)(__u32 *str_off_ptr, void *ctx);
3021
3022 /*
3023  * Iterate over all possible places in .BTF and .BTF.ext that can reference
3024  * string and pass pointer to it to a provided callback `fn`.
3025  */
3026 static int btf_for_each_str_off(struct btf_dedup *d, str_off_fn_t fn, void *ctx)
3027 {
3028         void *line_data_cur, *line_data_end;
3029         int i, j, r, rec_size;
3030         struct btf_type *t;
3031
3032         for (i = 1; i <= d->btf->nr_types; i++) {
3033                 t = btf_type_by_id(d->btf, i);
3034                 r = fn(&t->name_off, ctx);
3035                 if (r)
3036                         return r;
3037
3038                 switch (btf_kind(t)) {
3039                 case BTF_KIND_STRUCT:
3040                 case BTF_KIND_UNION: {
3041                         struct btf_member *m = btf_members(t);
3042                         __u16 vlen = btf_vlen(t);
3043
3044                         for (j = 0; j < vlen; j++) {
3045                                 r = fn(&m->name_off, ctx);
3046                                 if (r)
3047                                         return r;
3048                                 m++;
3049                         }
3050                         break;
3051                 }
3052                 case BTF_KIND_ENUM: {
3053                         struct btf_enum *m = btf_enum(t);
3054                         __u16 vlen = btf_vlen(t);
3055
3056                         for (j = 0; j < vlen; j++) {
3057                                 r = fn(&m->name_off, ctx);
3058                                 if (r)
3059                                         return r;
3060                                 m++;
3061                         }
3062                         break;
3063                 }
3064                 case BTF_KIND_FUNC_PROTO: {
3065                         struct btf_param *m = btf_params(t);
3066                         __u16 vlen = btf_vlen(t);
3067
3068                         for (j = 0; j < vlen; j++) {
3069                                 r = fn(&m->name_off, ctx);
3070                                 if (r)
3071                                         return r;
3072                                 m++;
3073                         }
3074                         break;
3075                 }
3076                 default:
3077                         break;
3078                 }
3079         }
3080
3081         if (!d->btf_ext)
3082                 return 0;
3083
3084         line_data_cur = d->btf_ext->line_info.info;
3085         line_data_end = d->btf_ext->line_info.info + d->btf_ext->line_info.len;
3086         rec_size = d->btf_ext->line_info.rec_size;
3087
3088         while (line_data_cur < line_data_end) {
3089                 struct btf_ext_info_sec *sec = line_data_cur;
3090                 struct bpf_line_info_min *line_info;
3091                 __u32 num_info = sec->num_info;
3092
3093                 r = fn(&sec->sec_name_off, ctx);
3094                 if (r)
3095                         return r;
3096
3097                 line_data_cur += sizeof(struct btf_ext_info_sec);
3098                 for (i = 0; i < num_info; i++) {
3099                         line_info = line_data_cur;
3100                         r = fn(&line_info->file_name_off, ctx);
3101                         if (r)
3102                                 return r;
3103                         r = fn(&line_info->line_off, ctx);
3104                         if (r)
3105                                 return r;
3106                         line_data_cur += rec_size;
3107                 }
3108         }
3109
3110         return 0;
3111 }
3112
3113 static int str_sort_by_content(const void *a1, const void *a2)
3114 {
3115         const struct btf_str_ptr *p1 = a1;
3116         const struct btf_str_ptr *p2 = a2;
3117
3118         return strcmp(p1->str, p2->str);
3119 }
3120
3121 static int str_sort_by_offset(const void *a1, const void *a2)
3122 {
3123         const struct btf_str_ptr *p1 = a1;
3124         const struct btf_str_ptr *p2 = a2;
3125
3126         if (p1->str != p2->str)
3127                 return p1->str < p2->str ? -1 : 1;
3128         return 0;
3129 }
3130
3131 static int btf_dedup_str_ptr_cmp(const void *str_ptr, const void *pelem)
3132 {
3133         const struct btf_str_ptr *p = pelem;
3134
3135         if (str_ptr != p->str)
3136                 return (const char *)str_ptr < p->str ? -1 : 1;
3137         return 0;
3138 }
3139
3140 static int btf_str_mark_as_used(__u32 *str_off_ptr, void *ctx)
3141 {
3142         struct btf_str_ptrs *strs;
3143         struct btf_str_ptr *s;
3144
3145         if (*str_off_ptr == 0)
3146                 return 0;
3147
3148         strs = ctx;
3149         s = bsearch(strs->data + *str_off_ptr, strs->ptrs, strs->cnt,
3150                     sizeof(struct btf_str_ptr), btf_dedup_str_ptr_cmp);
3151         if (!s)
3152                 return -EINVAL;
3153         s->used = true;
3154         return 0;
3155 }
3156
3157 static int btf_str_remap_offset(__u32 *str_off_ptr, void *ctx)
3158 {
3159         struct btf_str_ptrs *strs;
3160         struct btf_str_ptr *s;
3161
3162         if (*str_off_ptr == 0)
3163                 return 0;
3164
3165         strs = ctx;
3166         s = bsearch(strs->data + *str_off_ptr, strs->ptrs, strs->cnt,
3167                     sizeof(struct btf_str_ptr), btf_dedup_str_ptr_cmp);
3168         if (!s)
3169                 return -EINVAL;
3170         *str_off_ptr = s->new_off;
3171         return 0;
3172 }
3173
3174 /*
3175  * Dedup string and filter out those that are not referenced from either .BTF
3176  * or .BTF.ext (if provided) sections.
3177  *
3178  * This is done by building index of all strings in BTF's string section,
3179  * then iterating over all entities that can reference strings (e.g., type
3180  * names, struct field names, .BTF.ext line info, etc) and marking corresponding
3181  * strings as used. After that all used strings are deduped and compacted into
3182  * sequential blob of memory and new offsets are calculated. Then all the string
3183  * references are iterated again and rewritten using new offsets.
3184  */
3185 static int btf_dedup_strings(struct btf_dedup *d)
3186 {
3187         char *start = d->btf->strs_data;
3188         char *end = start + d->btf->hdr->str_len;
3189         char *p = start, *tmp_strs = NULL;
3190         struct btf_str_ptrs strs = {
3191                 .cnt = 0,
3192                 .cap = 0,
3193                 .ptrs = NULL,
3194                 .data = start,
3195         };
3196         int i, j, err = 0, grp_idx;
3197         bool grp_used;
3198
3199         if (d->btf->strs_deduped)
3200                 return 0;
3201
3202         /* build index of all strings */
3203         while (p < end) {
3204                 if (strs.cnt + 1 > strs.cap) {
3205                         struct btf_str_ptr *new_ptrs;
3206
3207                         strs.cap += max(strs.cnt / 2, 16U);
3208                         new_ptrs = libbpf_reallocarray(strs.ptrs, strs.cap, sizeof(strs.ptrs[0]));
3209                         if (!new_ptrs) {
3210                                 err = -ENOMEM;
3211                                 goto done;
3212                         }
3213                         strs.ptrs = new_ptrs;
3214                 }
3215
3216                 strs.ptrs[strs.cnt].str = p;
3217                 strs.ptrs[strs.cnt].used = false;
3218
3219                 p += strlen(p) + 1;
3220                 strs.cnt++;
3221         }
3222
3223         /* temporary storage for deduplicated strings */
3224         tmp_strs = malloc(d->btf->hdr->str_len);
3225         if (!tmp_strs) {
3226                 err = -ENOMEM;
3227                 goto done;
3228         }
3229
3230         /* mark all used strings */
3231         strs.ptrs[0].used = true;
3232         err = btf_for_each_str_off(d, btf_str_mark_as_used, &strs);
3233         if (err)
3234                 goto done;
3235
3236         /* sort strings by context, so that we can identify duplicates */
3237         qsort(strs.ptrs, strs.cnt, sizeof(strs.ptrs[0]), str_sort_by_content);
3238
3239         /*
3240          * iterate groups of equal strings and if any instance in a group was
3241          * referenced, emit single instance and remember new offset
3242          */
3243         p = tmp_strs;
3244         grp_idx = 0;
3245         grp_used = strs.ptrs[0].used;
3246         /* iterate past end to avoid code duplication after loop */
3247         for (i = 1; i <= strs.cnt; i++) {
3248                 /*
3249                  * when i == strs.cnt, we want to skip string comparison and go
3250                  * straight to handling last group of strings (otherwise we'd
3251                  * need to handle last group after the loop w/ duplicated code)
3252                  */
3253                 if (i < strs.cnt &&
3254                     !strcmp(strs.ptrs[i].str, strs.ptrs[grp_idx].str)) {
3255                         grp_used = grp_used || strs.ptrs[i].used;
3256                         continue;
3257                 }
3258
3259                 /*
3260                  * this check would have been required after the loop to handle
3261                  * last group of strings, but due to <= condition in a loop
3262                  * we avoid that duplication
3263                  */
3264                 if (grp_used) {
3265                         int new_off = p - tmp_strs;
3266                         __u32 len = strlen(strs.ptrs[grp_idx].str);
3267
3268                         memmove(p, strs.ptrs[grp_idx].str, len + 1);
3269                         for (j = grp_idx; j < i; j++)
3270                                 strs.ptrs[j].new_off = new_off;
3271                         p += len + 1;
3272                 }
3273
3274                 if (i < strs.cnt) {
3275                         grp_idx = i;
3276                         grp_used = strs.ptrs[i].used;
3277                 }
3278         }
3279
3280         /* replace original strings with deduped ones */
3281         d->btf->hdr->str_len = p - tmp_strs;
3282         memmove(start, tmp_strs, d->btf->hdr->str_len);
3283         end = start + d->btf->hdr->str_len;
3284
3285         /* restore original order for further binary search lookups */
3286         qsort(strs.ptrs, strs.cnt, sizeof(strs.ptrs[0]), str_sort_by_offset);
3287
3288         /* remap string offsets */
3289         err = btf_for_each_str_off(d, btf_str_remap_offset, &strs);
3290         if (err)
3291                 goto done;
3292
3293         d->btf->hdr->str_len = end - start;
3294         d->btf->strs_deduped = true;
3295
3296 done:
3297         free(tmp_strs);
3298         free(strs.ptrs);
3299         return err;
3300 }
3301
3302 static long btf_hash_common(struct btf_type *t)
3303 {
3304         long h;
3305
3306         h = hash_combine(0, t->name_off);
3307         h = hash_combine(h, t->info);
3308         h = hash_combine(h, t->size);
3309         return h;
3310 }
3311
3312 static bool btf_equal_common(struct btf_type *t1, struct btf_type *t2)
3313 {
3314         return t1->name_off == t2->name_off &&
3315                t1->info == t2->info &&
3316                t1->size == t2->size;
3317 }
3318
3319 /* Calculate type signature hash of INT. */
3320 static long btf_hash_int(struct btf_type *t)
3321 {
3322         __u32 info = *(__u32 *)(t + 1);
3323         long h;
3324
3325         h = btf_hash_common(t);
3326         h = hash_combine(h, info);
3327         return h;
3328 }
3329
3330 /* Check structural equality of two INTs. */
3331 static bool btf_equal_int(struct btf_type *t1, struct btf_type *t2)
3332 {
3333         __u32 info1, info2;
3334
3335         if (!btf_equal_common(t1, t2))
3336                 return false;
3337         info1 = *(__u32 *)(t1 + 1);
3338         info2 = *(__u32 *)(t2 + 1);
3339         return info1 == info2;
3340 }
3341
3342 /* Calculate type signature hash of ENUM. */
3343 static long btf_hash_enum(struct btf_type *t)
3344 {
3345         long h;
3346
3347         /* don't hash vlen and enum members to support enum fwd resolving */
3348         h = hash_combine(0, t->name_off);
3349         h = hash_combine(h, t->info & ~0xffff);
3350         h = hash_combine(h, t->size);
3351         return h;
3352 }
3353
3354 /* Check structural equality of two ENUMs. */
3355 static bool btf_equal_enum(struct btf_type *t1, struct btf_type *t2)
3356 {
3357         const struct btf_enum *m1, *m2;
3358         __u16 vlen;
3359         int i;
3360
3361         if (!btf_equal_common(t1, t2))
3362                 return false;
3363
3364         vlen = btf_vlen(t1);
3365         m1 = btf_enum(t1);
3366         m2 = btf_enum(t2);
3367         for (i = 0; i < vlen; i++) {
3368                 if (m1->name_off != m2->name_off || m1->val != m2->val)
3369                         return false;
3370                 m1++;
3371                 m2++;
3372         }
3373         return true;
3374 }
3375
3376 static inline bool btf_is_enum_fwd(struct btf_type *t)
3377 {
3378         return btf_is_enum(t) && btf_vlen(t) == 0;
3379 }
3380
3381 static bool btf_compat_enum(struct btf_type *t1, struct btf_type *t2)
3382 {
3383         if (!btf_is_enum_fwd(t1) && !btf_is_enum_fwd(t2))
3384                 return btf_equal_enum(t1, t2);
3385         /* ignore vlen when comparing */
3386         return t1->name_off == t2->name_off &&
3387                (t1->info & ~0xffff) == (t2->info & ~0xffff) &&
3388                t1->size == t2->size;
3389 }
3390
3391 /*
3392  * Calculate type signature hash of STRUCT/UNION, ignoring referenced type IDs,
3393  * as referenced type IDs equivalence is established separately during type
3394  * graph equivalence check algorithm.
3395  */
3396 static long btf_hash_struct(struct btf_type *t)
3397 {
3398         const struct btf_member *member = btf_members(t);
3399         __u32 vlen = btf_vlen(t);
3400         long h = btf_hash_common(t);
3401         int i;
3402
3403         for (i = 0; i < vlen; i++) {
3404                 h = hash_combine(h, member->name_off);
3405                 h = hash_combine(h, member->offset);
3406                 /* no hashing of referenced type ID, it can be unresolved yet */
3407                 member++;
3408         }
3409         return h;
3410 }
3411
3412 /*
3413  * Check structural compatibility of two FUNC_PROTOs, ignoring referenced type
3414  * IDs. This check is performed during type graph equivalence check and
3415  * referenced types equivalence is checked separately.
3416  */
3417 static bool btf_shallow_equal_struct(struct btf_type *t1, struct btf_type *t2)
3418 {
3419         const struct btf_member *m1, *m2;
3420         __u16 vlen;
3421         int i;
3422
3423         if (!btf_equal_common(t1, t2))
3424                 return false;
3425
3426         vlen = btf_vlen(t1);
3427         m1 = btf_members(t1);
3428         m2 = btf_members(t2);
3429         for (i = 0; i < vlen; i++) {
3430                 if (m1->name_off != m2->name_off || m1->offset != m2->offset)
3431                         return false;
3432                 m1++;
3433                 m2++;
3434         }
3435         return true;
3436 }
3437
3438 /*
3439  * Calculate type signature hash of ARRAY, including referenced type IDs,
3440  * under assumption that they were already resolved to canonical type IDs and
3441  * are not going to change.
3442  */
3443 static long btf_hash_array(struct btf_type *t)
3444 {
3445         const struct btf_array *info = btf_array(t);
3446         long h = btf_hash_common(t);
3447
3448         h = hash_combine(h, info->type);
3449         h = hash_combine(h, info->index_type);
3450         h = hash_combine(h, info->nelems);
3451         return h;
3452 }
3453
3454 /*
3455  * Check exact equality of two ARRAYs, taking into account referenced
3456  * type IDs, under assumption that they were already resolved to canonical
3457  * type IDs and are not going to change.
3458  * This function is called during reference types deduplication to compare
3459  * ARRAY to potential canonical representative.
3460  */
3461 static bool btf_equal_array(struct btf_type *t1, struct btf_type *t2)
3462 {
3463         const struct btf_array *info1, *info2;
3464
3465         if (!btf_equal_common(t1, t2))
3466                 return false;
3467
3468         info1 = btf_array(t1);
3469         info2 = btf_array(t2);
3470         return info1->type == info2->type &&
3471                info1->index_type == info2->index_type &&
3472                info1->nelems == info2->nelems;
3473 }
3474
3475 /*
3476  * Check structural compatibility of two ARRAYs, ignoring referenced type
3477  * IDs. This check is performed during type graph equivalence check and
3478  * referenced types equivalence is checked separately.
3479  */
3480 static bool btf_compat_array(struct btf_type *t1, struct btf_type *t2)
3481 {
3482         if (!btf_equal_common(t1, t2))
3483                 return false;
3484
3485         return btf_array(t1)->nelems == btf_array(t2)->nelems;
3486 }
3487
3488 /*
3489  * Calculate type signature hash of FUNC_PROTO, including referenced type IDs,
3490  * under assumption that they were already resolved to canonical type IDs and
3491  * are not going to change.
3492  */
3493 static long btf_hash_fnproto(struct btf_type *t)
3494 {
3495         const struct btf_param *member = btf_params(t);
3496         __u16 vlen = btf_vlen(t);
3497         long h = btf_hash_common(t);
3498         int i;
3499
3500         for (i = 0; i < vlen; i++) {
3501                 h = hash_combine(h, member->name_off);
3502                 h = hash_combine(h, member->type);
3503                 member++;
3504         }
3505         return h;
3506 }
3507
3508 /*
3509  * Check exact equality of two FUNC_PROTOs, taking into account referenced
3510  * type IDs, under assumption that they were already resolved to canonical
3511  * type IDs and are not going to change.
3512  * This function is called during reference types deduplication to compare
3513  * FUNC_PROTO to potential canonical representative.
3514  */
3515 static bool btf_equal_fnproto(struct btf_type *t1, struct btf_type *t2)
3516 {
3517         const struct btf_param *m1, *m2;
3518         __u16 vlen;
3519         int i;
3520
3521         if (!btf_equal_common(t1, t2))
3522                 return false;
3523
3524         vlen = btf_vlen(t1);
3525         m1 = btf_params(t1);
3526         m2 = btf_params(t2);
3527         for (i = 0; i < vlen; i++) {
3528                 if (m1->name_off != m2->name_off || m1->type != m2->type)
3529                         return false;
3530                 m1++;
3531                 m2++;
3532         }
3533         return true;
3534 }
3535
3536 /*
3537  * Check structural compatibility of two FUNC_PROTOs, ignoring referenced type
3538  * IDs. This check is performed during type graph equivalence check and
3539  * referenced types equivalence is checked separately.
3540  */
3541 static bool btf_compat_fnproto(struct btf_type *t1, struct btf_type *t2)
3542 {
3543         const struct btf_param *m1, *m2;
3544         __u16 vlen;
3545         int i;
3546
3547         /* skip return type ID */
3548         if (t1->name_off != t2->name_off || t1->info != t2->info)
3549                 return false;
3550
3551         vlen = btf_vlen(t1);
3552         m1 = btf_params(t1);
3553         m2 = btf_params(t2);
3554         for (i = 0; i < vlen; i++) {
3555                 if (m1->name_off != m2->name_off)
3556                         return false;
3557                 m1++;
3558                 m2++;
3559         }
3560         return true;
3561 }
3562
3563 /*
3564  * Deduplicate primitive types, that can't reference other types, by calculating
3565  * their type signature hash and comparing them with any possible canonical
3566  * candidate. If no canonical candidate matches, type itself is marked as
3567  * canonical and is added into `btf_dedup->dedup_table` as another candidate.
3568  */
3569 static int btf_dedup_prim_type(struct btf_dedup *d, __u32 type_id)
3570 {
3571         struct btf_type *t = btf_type_by_id(d->btf, type_id);
3572         struct hashmap_entry *hash_entry;
3573         struct btf_type *cand;
3574         /* if we don't find equivalent type, then we are canonical */
3575         __u32 new_id = type_id;
3576         __u32 cand_id;
3577         long h;
3578
3579         switch (btf_kind(t)) {
3580         case BTF_KIND_CONST:
3581         case BTF_KIND_VOLATILE:
3582         case BTF_KIND_RESTRICT:
3583         case BTF_KIND_PTR:
3584         case BTF_KIND_TYPEDEF:
3585         case BTF_KIND_ARRAY:
3586         case BTF_KIND_STRUCT:
3587         case BTF_KIND_UNION:
3588         case BTF_KIND_FUNC:
3589         case BTF_KIND_FUNC_PROTO:
3590         case BTF_KIND_VAR:
3591         case BTF_KIND_DATASEC:
3592                 return 0;
3593
3594         case BTF_KIND_INT:
3595                 h = btf_hash_int(t);
3596                 for_each_dedup_cand(d, hash_entry, h) {
3597                         cand_id = (__u32)(long)hash_entry->value;
3598                         cand = btf_type_by_id(d->btf, cand_id);
3599                         if (btf_equal_int(t, cand)) {
3600                                 new_id = cand_id;
3601                                 break;
3602                         }
3603                 }
3604                 break;
3605
3606         case BTF_KIND_ENUM:
3607                 h = btf_hash_enum(t);
3608                 for_each_dedup_cand(d, hash_entry, h) {
3609                         cand_id = (__u32)(long)hash_entry->value;
3610                         cand = btf_type_by_id(d->btf, cand_id);
3611                         if (btf_equal_enum(t, cand)) {
3612                                 new_id = cand_id;
3613                                 break;
3614                         }
3615                         if (d->opts.dont_resolve_fwds)
3616                                 continue;
3617                         if (btf_compat_enum(t, cand)) {
3618                                 if (btf_is_enum_fwd(t)) {
3619                                         /* resolve fwd to full enum */
3620                                         new_id = cand_id;
3621                                         break;
3622                                 }
3623                                 /* resolve canonical enum fwd to full enum */
3624                                 d->map[cand_id] = type_id;
3625                         }
3626                 }
3627                 break;
3628
3629         case BTF_KIND_FWD:
3630                 h = btf_hash_common(t);
3631                 for_each_dedup_cand(d, hash_entry, h) {
3632                         cand_id = (__u32)(long)hash_entry->value;
3633                         cand = btf_type_by_id(d->btf, cand_id);
3634                         if (btf_equal_common(t, cand)) {
3635                                 new_id = cand_id;
3636                                 break;
3637                         }
3638                 }
3639                 break;
3640
3641         default:
3642                 return -EINVAL;
3643         }
3644
3645         d->map[type_id] = new_id;
3646         if (type_id == new_id && btf_dedup_table_add(d, h, type_id))
3647                 return -ENOMEM;
3648
3649         return 0;
3650 }
3651
3652 static int btf_dedup_prim_types(struct btf_dedup *d)
3653 {
3654         int i, err;
3655
3656         for (i = 1; i <= d->btf->nr_types; i++) {
3657                 err = btf_dedup_prim_type(d, i);
3658                 if (err)
3659                         return err;
3660         }
3661         return 0;
3662 }
3663
3664 /*
3665  * Check whether type is already mapped into canonical one (could be to itself).
3666  */
3667 static inline bool is_type_mapped(struct btf_dedup *d, uint32_t type_id)
3668 {
3669         return d->map[type_id] <= BTF_MAX_NR_TYPES;
3670 }
3671
3672 /*
3673  * Resolve type ID into its canonical type ID, if any; otherwise return original
3674  * type ID. If type is FWD and is resolved into STRUCT/UNION already, follow
3675  * STRUCT/UNION link and resolve it into canonical type ID as well.
3676  */
3677 static inline __u32 resolve_type_id(struct btf_dedup *d, __u32 type_id)
3678 {
3679         while (is_type_mapped(d, type_id) && d->map[type_id] != type_id)
3680                 type_id = d->map[type_id];
3681         return type_id;
3682 }
3683
3684 /*
3685  * Resolve FWD to underlying STRUCT/UNION, if any; otherwise return original
3686  * type ID.
3687  */
3688 static uint32_t resolve_fwd_id(struct btf_dedup *d, uint32_t type_id)
3689 {
3690         __u32 orig_type_id = type_id;
3691
3692         if (!btf_is_fwd(btf__type_by_id(d->btf, type_id)))
3693                 return type_id;
3694
3695         while (is_type_mapped(d, type_id) && d->map[type_id] != type_id)
3696                 type_id = d->map[type_id];
3697
3698         if (!btf_is_fwd(btf__type_by_id(d->btf, type_id)))
3699                 return type_id;
3700
3701         return orig_type_id;
3702 }
3703
3704
3705 static inline __u16 btf_fwd_kind(struct btf_type *t)
3706 {
3707         return btf_kflag(t) ? BTF_KIND_UNION : BTF_KIND_STRUCT;
3708 }
3709
3710 /*
3711  * Check equivalence of BTF type graph formed by candidate struct/union (we'll
3712  * call it "candidate graph" in this description for brevity) to a type graph
3713  * formed by (potential) canonical struct/union ("canonical graph" for brevity
3714  * here, though keep in mind that not all types in canonical graph are
3715  * necessarily canonical representatives themselves, some of them might be
3716  * duplicates or its uniqueness might not have been established yet).
3717  * Returns:
3718  *  - >0, if type graphs are equivalent;
3719  *  -  0, if not equivalent;
3720  *  - <0, on error.
3721  *
3722  * Algorithm performs side-by-side DFS traversal of both type graphs and checks
3723  * equivalence of BTF types at each step. If at any point BTF types in candidate
3724  * and canonical graphs are not compatible structurally, whole graphs are
3725  * incompatible. If types are structurally equivalent (i.e., all information
3726  * except referenced type IDs is exactly the same), a mapping from `canon_id` to
3727  * a `cand_id` is recored in hypothetical mapping (`btf_dedup->hypot_map`).
3728  * If a type references other types, then those referenced types are checked
3729  * for equivalence recursively.
3730  *
3731  * During DFS traversal, if we find that for current `canon_id` type we
3732  * already have some mapping in hypothetical map, we check for two possible
3733  * situations:
3734  *   - `canon_id` is mapped to exactly the same type as `cand_id`. This will
3735  *     happen when type graphs have cycles. In this case we assume those two
3736  *     types are equivalent.
3737  *   - `canon_id` is mapped to different type. This is contradiction in our
3738  *     hypothetical mapping, because same graph in canonical graph corresponds
3739  *     to two different types in candidate graph, which for equivalent type
3740  *     graphs shouldn't happen. This condition terminates equivalence check
3741  *     with negative result.
3742  *
3743  * If type graphs traversal exhausts types to check and find no contradiction,
3744  * then type graphs are equivalent.
3745  *
3746  * When checking types for equivalence, there is one special case: FWD types.
3747  * If FWD type resolution is allowed and one of the types (either from canonical
3748  * or candidate graph) is FWD and other is STRUCT/UNION (depending on FWD's kind
3749  * flag) and their names match, hypothetical mapping is updated to point from
3750  * FWD to STRUCT/UNION. If graphs will be determined as equivalent successfully,
3751  * this mapping will be used to record FWD -> STRUCT/UNION mapping permanently.
3752  *
3753  * Technically, this could lead to incorrect FWD to STRUCT/UNION resolution,
3754  * if there are two exactly named (or anonymous) structs/unions that are
3755  * compatible structurally, one of which has FWD field, while other is concrete
3756  * STRUCT/UNION, but according to C sources they are different structs/unions
3757  * that are referencing different types with the same name. This is extremely
3758  * unlikely to happen, but btf_dedup API allows to disable FWD resolution if
3759  * this logic is causing problems.
3760  *
3761  * Doing FWD resolution means that both candidate and/or canonical graphs can
3762  * consists of portions of the graph that come from multiple compilation units.
3763  * This is due to the fact that types within single compilation unit are always
3764  * deduplicated and FWDs are already resolved, if referenced struct/union
3765  * definiton is available. So, if we had unresolved FWD and found corresponding
3766  * STRUCT/UNION, they will be from different compilation units. This
3767  * consequently means that when we "link" FWD to corresponding STRUCT/UNION,
3768  * type graph will likely have at least two different BTF types that describe
3769  * same type (e.g., most probably there will be two different BTF types for the
3770  * same 'int' primitive type) and could even have "overlapping" parts of type
3771  * graph that describe same subset of types.
3772  *
3773  * This in turn means that our assumption that each type in canonical graph
3774  * must correspond to exactly one type in candidate graph might not hold
3775  * anymore and will make it harder to detect contradictions using hypothetical
3776  * map. To handle this problem, we allow to follow FWD -> STRUCT/UNION
3777  * resolution only in canonical graph. FWDs in candidate graphs are never
3778  * resolved. To see why it's OK, let's check all possible situations w.r.t. FWDs
3779  * that can occur:
3780  *   - Both types in canonical and candidate graphs are FWDs. If they are
3781  *     structurally equivalent, then they can either be both resolved to the
3782  *     same STRUCT/UNION or not resolved at all. In both cases they are
3783  *     equivalent and there is no need to resolve FWD on candidate side.
3784  *   - Both types in canonical and candidate graphs are concrete STRUCT/UNION,
3785  *     so nothing to resolve as well, algorithm will check equivalence anyway.
3786  *   - Type in canonical graph is FWD, while type in candidate is concrete
3787  *     STRUCT/UNION. In this case candidate graph comes from single compilation
3788  *     unit, so there is exactly one BTF type for each unique C type. After
3789  *     resolving FWD into STRUCT/UNION, there might be more than one BTF type
3790  *     in canonical graph mapping to single BTF type in candidate graph, but
3791  *     because hypothetical mapping maps from canonical to candidate types, it's
3792  *     alright, and we still maintain the property of having single `canon_id`
3793  *     mapping to single `cand_id` (there could be two different `canon_id`
3794  *     mapped to the same `cand_id`, but it's not contradictory).
3795  *   - Type in canonical graph is concrete STRUCT/UNION, while type in candidate
3796  *     graph is FWD. In this case we are just going to check compatibility of
3797  *     STRUCT/UNION and corresponding FWD, and if they are compatible, we'll
3798  *     assume that whatever STRUCT/UNION FWD resolves to must be equivalent to
3799  *     a concrete STRUCT/UNION from canonical graph. If the rest of type graphs
3800  *     turn out equivalent, we'll re-resolve FWD to concrete STRUCT/UNION from
3801  *     canonical graph.
3802  */
3803 static int btf_dedup_is_equiv(struct btf_dedup *d, __u32 cand_id,
3804                               __u32 canon_id)
3805 {
3806         struct btf_type *cand_type;
3807         struct btf_type *canon_type;
3808         __u32 hypot_type_id;
3809         __u16 cand_kind;
3810         __u16 canon_kind;
3811         int i, eq;
3812
3813         /* if both resolve to the same canonical, they must be equivalent */
3814         if (resolve_type_id(d, cand_id) == resolve_type_id(d, canon_id))
3815                 return 1;
3816
3817         canon_id = resolve_fwd_id(d, canon_id);
3818
3819         hypot_type_id = d->hypot_map[canon_id];
3820         if (hypot_type_id <= BTF_MAX_NR_TYPES)
3821                 return hypot_type_id == cand_id;
3822
3823         if (btf_dedup_hypot_map_add(d, canon_id, cand_id))
3824                 return -ENOMEM;
3825
3826         cand_type = btf_type_by_id(d->btf, cand_id);
3827         canon_type = btf_type_by_id(d->btf, canon_id);
3828         cand_kind = btf_kind(cand_type);
3829         canon_kind = btf_kind(canon_type);
3830
3831         if (cand_type->name_off != canon_type->name_off)
3832                 return 0;
3833
3834         /* FWD <--> STRUCT/UNION equivalence check, if enabled */
3835         if (!d->opts.dont_resolve_fwds
3836             && (cand_kind == BTF_KIND_FWD || canon_kind == BTF_KIND_FWD)
3837             && cand_kind != canon_kind) {
3838                 __u16 real_kind;
3839                 __u16 fwd_kind;
3840
3841                 if (cand_kind == BTF_KIND_FWD) {
3842                         real_kind = canon_kind;
3843                         fwd_kind = btf_fwd_kind(cand_type);
3844                 } else {
3845                         real_kind = cand_kind;
3846                         fwd_kind = btf_fwd_kind(canon_type);
3847                 }
3848                 return fwd_kind == real_kind;
3849         }
3850
3851         if (cand_kind != canon_kind)
3852                 return 0;
3853
3854         switch (cand_kind) {
3855         case BTF_KIND_INT:
3856                 return btf_equal_int(cand_type, canon_type);
3857
3858         case BTF_KIND_ENUM:
3859                 if (d->opts.dont_resolve_fwds)
3860                         return btf_equal_enum(cand_type, canon_type);
3861                 else
3862                         return btf_compat_enum(cand_type, canon_type);
3863
3864         case BTF_KIND_FWD:
3865                 return btf_equal_common(cand_type, canon_type);
3866
3867         case BTF_KIND_CONST:
3868         case BTF_KIND_VOLATILE:
3869         case BTF_KIND_RESTRICT:
3870         case BTF_KIND_PTR:
3871         case BTF_KIND_TYPEDEF:
3872         case BTF_KIND_FUNC:
3873                 if (cand_type->info != canon_type->info)
3874                         return 0;
3875                 return btf_dedup_is_equiv(d, cand_type->type, canon_type->type);
3876
3877         case BTF_KIND_ARRAY: {
3878                 const struct btf_array *cand_arr, *canon_arr;
3879
3880                 if (!btf_compat_array(cand_type, canon_type))
3881                         return 0;
3882                 cand_arr = btf_array(cand_type);
3883                 canon_arr = btf_array(canon_type);
3884                 eq = btf_dedup_is_equiv(d,
3885                         cand_arr->index_type, canon_arr->index_type);
3886                 if (eq <= 0)
3887                         return eq;
3888                 return btf_dedup_is_equiv(d, cand_arr->type, canon_arr->type);
3889         }
3890
3891         case BTF_KIND_STRUCT:
3892         case BTF_KIND_UNION: {
3893                 const struct btf_member *cand_m, *canon_m;
3894                 __u16 vlen;
3895
3896                 if (!btf_shallow_equal_struct(cand_type, canon_type))
3897                         return 0;
3898                 vlen = btf_vlen(cand_type);
3899                 cand_m = btf_members(cand_type);
3900                 canon_m = btf_members(canon_type);
3901                 for (i = 0; i < vlen; i++) {
3902                         eq = btf_dedup_is_equiv(d, cand_m->type, canon_m->type);
3903                         if (eq <= 0)
3904                                 return eq;
3905                         cand_m++;
3906                         canon_m++;
3907                 }
3908
3909                 return 1;
3910         }
3911
3912         case BTF_KIND_FUNC_PROTO: {
3913                 const struct btf_param *cand_p, *canon_p;
3914                 __u16 vlen;
3915
3916                 if (!btf_compat_fnproto(cand_type, canon_type))
3917                         return 0;
3918                 eq = btf_dedup_is_equiv(d, cand_type->type, canon_type->type);
3919                 if (eq <= 0)
3920                         return eq;
3921                 vlen = btf_vlen(cand_type);
3922                 cand_p = btf_params(cand_type);
3923                 canon_p = btf_params(canon_type);
3924                 for (i = 0; i < vlen; i++) {
3925                         eq = btf_dedup_is_equiv(d, cand_p->type, canon_p->type);
3926                         if (eq <= 0)
3927                                 return eq;
3928                         cand_p++;
3929                         canon_p++;
3930                 }
3931                 return 1;
3932         }
3933
3934         default:
3935                 return -EINVAL;
3936         }
3937         return 0;
3938 }
3939
3940 /*
3941  * Use hypothetical mapping, produced by successful type graph equivalence
3942  * check, to augment existing struct/union canonical mapping, where possible.
3943  *
3944  * If BTF_KIND_FWD resolution is allowed, this mapping is also used to record
3945  * FWD -> STRUCT/UNION correspondence as well. FWD resolution is bidirectional:
3946  * it doesn't matter if FWD type was part of canonical graph or candidate one,
3947  * we are recording the mapping anyway. As opposed to carefulness required
3948  * for struct/union correspondence mapping (described below), for FWD resolution
3949  * it's not important, as by the time that FWD type (reference type) will be
3950  * deduplicated all structs/unions will be deduped already anyway.
3951  *
3952  * Recording STRUCT/UNION mapping is purely a performance optimization and is
3953  * not required for correctness. It needs to be done carefully to ensure that
3954  * struct/union from candidate's type graph is not mapped into corresponding
3955  * struct/union from canonical type graph that itself hasn't been resolved into
3956  * canonical representative. The only guarantee we have is that canonical
3957  * struct/union was determined as canonical and that won't change. But any
3958  * types referenced through that struct/union fields could have been not yet
3959  * resolved, so in case like that it's too early to establish any kind of
3960  * correspondence between structs/unions.
3961  *
3962  * No canonical correspondence is derived for primitive types (they are already
3963  * deduplicated completely already anyway) or reference types (they rely on
3964  * stability of struct/union canonical relationship for equivalence checks).
3965  */
3966 static void btf_dedup_merge_hypot_map(struct btf_dedup *d)
3967 {
3968         __u32 cand_type_id, targ_type_id;
3969         __u16 t_kind, c_kind;
3970         __u32 t_id, c_id;
3971         int i;
3972
3973         for (i = 0; i < d->hypot_cnt; i++) {
3974                 cand_type_id = d->hypot_list[i];
3975                 targ_type_id = d->hypot_map[cand_type_id];
3976                 t_id = resolve_type_id(d, targ_type_id);
3977                 c_id = resolve_type_id(d, cand_type_id);
3978                 t_kind = btf_kind(btf__type_by_id(d->btf, t_id));
3979                 c_kind = btf_kind(btf__type_by_id(d->btf, c_id));
3980                 /*
3981                  * Resolve FWD into STRUCT/UNION.
3982                  * It's ok to resolve FWD into STRUCT/UNION that's not yet
3983                  * mapped to canonical representative (as opposed to
3984                  * STRUCT/UNION <--> STRUCT/UNION mapping logic below), because
3985                  * eventually that struct is going to be mapped and all resolved
3986                  * FWDs will automatically resolve to correct canonical
3987                  * representative. This will happen before ref type deduping,
3988                  * which critically depends on stability of these mapping. This
3989                  * stability is not a requirement for STRUCT/UNION equivalence
3990                  * checks, though.
3991                  */
3992                 if (t_kind != BTF_KIND_FWD && c_kind == BTF_KIND_FWD)
3993                         d->map[c_id] = t_id;
3994                 else if (t_kind == BTF_KIND_FWD && c_kind != BTF_KIND_FWD)
3995                         d->map[t_id] = c_id;
3996
3997                 if ((t_kind == BTF_KIND_STRUCT || t_kind == BTF_KIND_UNION) &&
3998                     c_kind != BTF_KIND_FWD &&
3999                     is_type_mapped(d, c_id) &&
4000                     !is_type_mapped(d, t_id)) {
4001                         /*
4002                          * as a perf optimization, we can map struct/union
4003                          * that's part of type graph we just verified for
4004                          * equivalence. We can do that for struct/union that has
4005                          * canonical representative only, though.
4006                          */
4007                         d->map[t_id] = c_id;
4008                 }
4009         }
4010 }
4011
4012 /*
4013  * Deduplicate struct/union types.
4014  *
4015  * For each struct/union type its type signature hash is calculated, taking
4016  * into account type's name, size, number, order and names of fields, but
4017  * ignoring type ID's referenced from fields, because they might not be deduped
4018  * completely until after reference types deduplication phase. This type hash
4019  * is used to iterate over all potential canonical types, sharing same hash.
4020  * For each canonical candidate we check whether type graphs that they form
4021  * (through referenced types in fields and so on) are equivalent using algorithm
4022  * implemented in `btf_dedup_is_equiv`. If such equivalence is found and
4023  * BTF_KIND_FWD resolution is allowed, then hypothetical mapping
4024  * (btf_dedup->hypot_map) produced by aforementioned type graph equivalence
4025  * algorithm is used to record FWD -> STRUCT/UNION mapping. It's also used to
4026  * potentially map other structs/unions to their canonical representatives,
4027  * if such relationship hasn't yet been established. This speeds up algorithm
4028  * by eliminating some of the duplicate work.
4029  *
4030  * If no matching canonical representative was found, struct/union is marked
4031  * as canonical for itself and is added into btf_dedup->dedup_table hash map
4032  * for further look ups.
4033  */
4034 static int btf_dedup_struct_type(struct btf_dedup *d, __u32 type_id)
4035 {
4036         struct btf_type *cand_type, *t;
4037         struct hashmap_entry *hash_entry;
4038         /* if we don't find equivalent type, then we are canonical */
4039         __u32 new_id = type_id;
4040         __u16 kind;
4041         long h;
4042
4043         /* already deduped or is in process of deduping (loop detected) */
4044         if (d->map[type_id] <= BTF_MAX_NR_TYPES)
4045                 return 0;
4046
4047         t = btf_type_by_id(d->btf, type_id);
4048         kind = btf_kind(t);
4049
4050         if (kind != BTF_KIND_STRUCT && kind != BTF_KIND_UNION)
4051                 return 0;
4052
4053         h = btf_hash_struct(t);
4054         for_each_dedup_cand(d, hash_entry, h) {
4055                 __u32 cand_id = (__u32)(long)hash_entry->value;
4056                 int eq;
4057
4058                 /*
4059                  * Even though btf_dedup_is_equiv() checks for
4060                  * btf_shallow_equal_struct() internally when checking two
4061                  * structs (unions) for equivalence, we need to guard here
4062                  * from picking matching FWD type as a dedup candidate.
4063                  * This can happen due to hash collision. In such case just
4064                  * relying on btf_dedup_is_equiv() would lead to potentially
4065                  * creating a loop (FWD -> STRUCT and STRUCT -> FWD), because
4066                  * FWD and compatible STRUCT/UNION are considered equivalent.
4067                  */
4068                 cand_type = btf_type_by_id(d->btf, cand_id);
4069                 if (!btf_shallow_equal_struct(t, cand_type))
4070                         continue;
4071
4072                 btf_dedup_clear_hypot_map(d);
4073                 eq = btf_dedup_is_equiv(d, type_id, cand_id);
4074                 if (eq < 0)
4075                         return eq;
4076                 if (!eq)
4077                         continue;
4078                 new_id = cand_id;
4079                 btf_dedup_merge_hypot_map(d);
4080                 break;
4081         }
4082
4083         d->map[type_id] = new_id;
4084         if (type_id == new_id && btf_dedup_table_add(d, h, type_id))
4085                 return -ENOMEM;
4086
4087         return 0;
4088 }
4089
4090 static int btf_dedup_struct_types(struct btf_dedup *d)
4091 {
4092         int i, err;
4093
4094         for (i = 1; i <= d->btf->nr_types; i++) {
4095                 err = btf_dedup_struct_type(d, i);
4096                 if (err)
4097                         return err;
4098         }
4099         return 0;
4100 }
4101
4102 /*
4103  * Deduplicate reference type.
4104  *
4105  * Once all primitive and struct/union types got deduplicated, we can easily
4106  * deduplicate all other (reference) BTF types. This is done in two steps:
4107  *
4108  * 1. Resolve all referenced type IDs into their canonical type IDs. This
4109  * resolution can be done either immediately for primitive or struct/union types
4110  * (because they were deduped in previous two phases) or recursively for
4111  * reference types. Recursion will always terminate at either primitive or
4112  * struct/union type, at which point we can "unwind" chain of reference types
4113  * one by one. There is no danger of encountering cycles because in C type
4114  * system the only way to form type cycle is through struct/union, so any chain
4115  * of reference types, even those taking part in a type cycle, will inevitably
4116  * reach struct/union at some point.
4117  *
4118  * 2. Once all referenced type IDs are resolved into canonical ones, BTF type
4119  * becomes "stable", in the sense that no further deduplication will cause
4120  * any changes to it. With that, it's now possible to calculate type's signature
4121  * hash (this time taking into account referenced type IDs) and loop over all
4122  * potential canonical representatives. If no match was found, current type
4123  * will become canonical representative of itself and will be added into
4124  * btf_dedup->dedup_table as another possible canonical representative.
4125  */
4126 static int btf_dedup_ref_type(struct btf_dedup *d, __u32 type_id)
4127 {
4128         struct hashmap_entry *hash_entry;
4129         __u32 new_id = type_id, cand_id;
4130         struct btf_type *t, *cand;
4131         /* if we don't find equivalent type, then we are representative type */
4132         int ref_type_id;
4133         long h;
4134
4135         if (d->map[type_id] == BTF_IN_PROGRESS_ID)
4136                 return -ELOOP;
4137         if (d->map[type_id] <= BTF_MAX_NR_TYPES)
4138                 return resolve_type_id(d, type_id);
4139
4140         t = btf_type_by_id(d->btf, type_id);
4141         d->map[type_id] = BTF_IN_PROGRESS_ID;
4142
4143         switch (btf_kind(t)) {
4144         case BTF_KIND_CONST:
4145         case BTF_KIND_VOLATILE:
4146         case BTF_KIND_RESTRICT:
4147         case BTF_KIND_PTR:
4148         case BTF_KIND_TYPEDEF:
4149         case BTF_KIND_FUNC:
4150                 ref_type_id = btf_dedup_ref_type(d, t->type);
4151                 if (ref_type_id < 0)
4152                         return ref_type_id;
4153                 t->type = ref_type_id;
4154
4155                 h = btf_hash_common(t);
4156                 for_each_dedup_cand(d, hash_entry, h) {
4157                         cand_id = (__u32)(long)hash_entry->value;
4158                         cand = btf_type_by_id(d->btf, cand_id);
4159                         if (btf_equal_common(t, cand)) {
4160                                 new_id = cand_id;
4161                                 break;
4162                         }
4163                 }
4164                 break;
4165
4166         case BTF_KIND_ARRAY: {
4167                 struct btf_array *info = btf_array(t);
4168
4169                 ref_type_id = btf_dedup_ref_type(d, info->type);
4170                 if (ref_type_id < 0)
4171                         return ref_type_id;
4172                 info->type = ref_type_id;
4173
4174                 ref_type_id = btf_dedup_ref_type(d, info->index_type);
4175                 if (ref_type_id < 0)
4176                         return ref_type_id;
4177                 info->index_type = ref_type_id;
4178
4179                 h = btf_hash_array(t);
4180                 for_each_dedup_cand(d, hash_entry, h) {
4181                         cand_id = (__u32)(long)hash_entry->value;
4182                         cand = btf_type_by_id(d->btf, cand_id);
4183                         if (btf_equal_array(t, cand)) {
4184                                 new_id = cand_id;
4185                                 break;
4186                         }
4187                 }
4188                 break;
4189         }
4190
4191         case BTF_KIND_FUNC_PROTO: {
4192                 struct btf_param *param;
4193                 __u16 vlen;
4194                 int i;
4195
4196                 ref_type_id = btf_dedup_ref_type(d, t->type);
4197                 if (ref_type_id < 0)
4198                         return ref_type_id;
4199                 t->type = ref_type_id;
4200
4201                 vlen = btf_vlen(t);
4202                 param = btf_params(t);
4203                 for (i = 0; i < vlen; i++) {
4204                         ref_type_id = btf_dedup_ref_type(d, param->type);
4205                         if (ref_type_id < 0)
4206                                 return ref_type_id;
4207                         param->type = ref_type_id;
4208                         param++;
4209                 }
4210
4211                 h = btf_hash_fnproto(t);
4212                 for_each_dedup_cand(d, hash_entry, h) {
4213                         cand_id = (__u32)(long)hash_entry->value;
4214                         cand = btf_type_by_id(d->btf, cand_id);
4215                         if (btf_equal_fnproto(t, cand)) {
4216                                 new_id = cand_id;
4217                                 break;
4218                         }
4219                 }
4220                 break;
4221         }
4222
4223         default:
4224                 return -EINVAL;
4225         }
4226
4227         d->map[type_id] = new_id;
4228         if (type_id == new_id && btf_dedup_table_add(d, h, type_id))
4229                 return -ENOMEM;
4230
4231         return new_id;
4232 }
4233
4234 static int btf_dedup_ref_types(struct btf_dedup *d)
4235 {
4236         int i, err;
4237
4238         for (i = 1; i <= d->btf->nr_types; i++) {
4239                 err = btf_dedup_ref_type(d, i);
4240                 if (err < 0)
4241                         return err;
4242         }
4243         /* we won't need d->dedup_table anymore */
4244         hashmap__free(d->dedup_table);
4245         d->dedup_table = NULL;
4246         return 0;
4247 }
4248
4249 /*
4250  * Compact types.
4251  *
4252  * After we established for each type its corresponding canonical representative
4253  * type, we now can eliminate types that are not canonical and leave only
4254  * canonical ones layed out sequentially in memory by copying them over
4255  * duplicates. During compaction btf_dedup->hypot_map array is reused to store
4256  * a map from original type ID to a new compacted type ID, which will be used
4257  * during next phase to "fix up" type IDs, referenced from struct/union and
4258  * reference types.
4259  */
4260 static int btf_dedup_compact_types(struct btf_dedup *d)
4261 {
4262         __u32 *new_offs;
4263         __u32 next_type_id = 1;
4264         void *p;
4265         int i, len;
4266
4267         /* we are going to reuse hypot_map to store compaction remapping */
4268         d->hypot_map[0] = 0;
4269         for (i = 1; i <= d->btf->nr_types; i++)
4270                 d->hypot_map[i] = BTF_UNPROCESSED_ID;
4271
4272         p = d->btf->types_data;
4273
4274         for (i = 1; i <= d->btf->nr_types; i++) {
4275                 if (d->map[i] != i)
4276                         continue;
4277
4278                 len = btf_type_size(btf__type_by_id(d->btf, i));
4279                 if (len < 0)
4280                         return len;
4281
4282                 memmove(p, btf__type_by_id(d->btf, i), len);
4283                 d->hypot_map[i] = next_type_id;
4284                 d->btf->type_offs[next_type_id] = p - d->btf->types_data;
4285                 p += len;
4286                 next_type_id++;
4287         }
4288
4289         /* shrink struct btf's internal types index and update btf_header */
4290         d->btf->nr_types = next_type_id - 1;
4291         d->btf->type_offs_cap = d->btf->nr_types + 1;
4292         d->btf->hdr->type_len = p - d->btf->types_data;
4293         new_offs = libbpf_reallocarray(d->btf->type_offs, d->btf->type_offs_cap,
4294                                        sizeof(*new_offs));
4295         if (!new_offs)
4296                 return -ENOMEM;
4297         d->btf->type_offs = new_offs;
4298         d->btf->hdr->str_off = d->btf->hdr->type_len;
4299         d->btf->raw_size = d->btf->hdr->hdr_len + d->btf->hdr->type_len + d->btf->hdr->str_len;
4300         return 0;
4301 }
4302
4303 /*
4304  * Figure out final (deduplicated and compacted) type ID for provided original
4305  * `type_id` by first resolving it into corresponding canonical type ID and
4306  * then mapping it to a deduplicated type ID, stored in btf_dedup->hypot_map,
4307  * which is populated during compaction phase.
4308  */
4309 static int btf_dedup_remap_type_id(struct btf_dedup *d, __u32 type_id)
4310 {
4311         __u32 resolved_type_id, new_type_id;
4312
4313         resolved_type_id = resolve_type_id(d, type_id);
4314         new_type_id = d->hypot_map[resolved_type_id];
4315         if (new_type_id > BTF_MAX_NR_TYPES)
4316                 return -EINVAL;
4317         return new_type_id;
4318 }
4319
4320 /*
4321  * Remap referenced type IDs into deduped type IDs.
4322  *
4323  * After BTF types are deduplicated and compacted, their final type IDs may
4324  * differ from original ones. The map from original to a corresponding
4325  * deduped type ID is stored in btf_dedup->hypot_map and is populated during
4326  * compaction phase. During remapping phase we are rewriting all type IDs
4327  * referenced from any BTF type (e.g., struct fields, func proto args, etc) to
4328  * their final deduped type IDs.
4329  */
4330 static int btf_dedup_remap_type(struct btf_dedup *d, __u32 type_id)
4331 {
4332         struct btf_type *t = btf_type_by_id(d->btf, type_id);
4333         int i, r;
4334
4335         switch (btf_kind(t)) {
4336         case BTF_KIND_INT:
4337         case BTF_KIND_ENUM:
4338                 break;
4339
4340         case BTF_KIND_FWD:
4341         case BTF_KIND_CONST:
4342         case BTF_KIND_VOLATILE:
4343         case BTF_KIND_RESTRICT:
4344         case BTF_KIND_PTR:
4345         case BTF_KIND_TYPEDEF:
4346         case BTF_KIND_FUNC:
4347         case BTF_KIND_VAR:
4348                 r = btf_dedup_remap_type_id(d, t->type);
4349                 if (r < 0)
4350                         return r;
4351                 t->type = r;
4352                 break;
4353
4354         case BTF_KIND_ARRAY: {
4355                 struct btf_array *arr_info = btf_array(t);
4356
4357                 r = btf_dedup_remap_type_id(d, arr_info->type);
4358                 if (r < 0)
4359                         return r;
4360                 arr_info->type = r;
4361                 r = btf_dedup_remap_type_id(d, arr_info->index_type);
4362                 if (r < 0)
4363                         return r;
4364                 arr_info->index_type = r;
4365                 break;
4366         }
4367
4368         case BTF_KIND_STRUCT:
4369         case BTF_KIND_UNION: {
4370                 struct btf_member *member = btf_members(t);
4371                 __u16 vlen = btf_vlen(t);
4372
4373                 for (i = 0; i < vlen; i++) {
4374                         r = btf_dedup_remap_type_id(d, member->type);
4375                         if (r < 0)
4376                                 return r;
4377                         member->type = r;
4378                         member++;
4379                 }
4380                 break;
4381         }
4382
4383         case BTF_KIND_FUNC_PROTO: {
4384                 struct btf_param *param = btf_params(t);
4385                 __u16 vlen = btf_vlen(t);
4386
4387                 r = btf_dedup_remap_type_id(d, t->type);
4388                 if (r < 0)
4389                         return r;
4390                 t->type = r;
4391
4392                 for (i = 0; i < vlen; i++) {
4393                         r = btf_dedup_remap_type_id(d, param->type);
4394                         if (r < 0)
4395                                 return r;
4396                         param->type = r;
4397                         param++;
4398                 }
4399                 break;
4400         }
4401
4402         case BTF_KIND_DATASEC: {
4403                 struct btf_var_secinfo *var = btf_var_secinfos(t);
4404                 __u16 vlen = btf_vlen(t);
4405
4406                 for (i = 0; i < vlen; i++) {
4407                         r = btf_dedup_remap_type_id(d, var->type);
4408                         if (r < 0)
4409                                 return r;
4410                         var->type = r;
4411                         var++;
4412                 }
4413                 break;
4414         }
4415
4416         default:
4417                 return -EINVAL;
4418         }
4419
4420         return 0;
4421 }
4422
4423 static int btf_dedup_remap_types(struct btf_dedup *d)
4424 {
4425         int i, r;
4426
4427         for (i = 1; i <= d->btf->nr_types; i++) {
4428                 r = btf_dedup_remap_type(d, i);
4429                 if (r < 0)
4430                         return r;
4431         }
4432         return 0;
4433 }
4434
4435 /*
4436  * Probe few well-known locations for vmlinux kernel image and try to load BTF
4437  * data out of it to use for target BTF.
4438  */
4439 struct btf *libbpf_find_kernel_btf(void)
4440 {
4441         struct {
4442                 const char *path_fmt;
4443                 bool raw_btf;
4444         } locations[] = {
4445                 /* try canonical vmlinux BTF through sysfs first */
4446                 { "/sys/kernel/btf/vmlinux", true /* raw BTF */ },
4447                 /* fall back to trying to find vmlinux ELF on disk otherwise */
4448                 { "/boot/vmlinux-%1$s" },
4449                 { "/lib/modules/%1$s/vmlinux-%1$s" },
4450                 { "/lib/modules/%1$s/build/vmlinux" },
4451                 { "/usr/lib/modules/%1$s/kernel/vmlinux" },
4452                 { "/usr/lib/debug/boot/vmlinux-%1$s" },
4453                 { "/usr/lib/debug/boot/vmlinux-%1$s.debug" },
4454                 { "/usr/lib/debug/lib/modules/%1$s/vmlinux" },
4455         };
4456         char path[PATH_MAX + 1];
4457         struct utsname buf;
4458         struct btf *btf;
4459         int i;
4460
4461         uname(&buf);
4462
4463         for (i = 0; i < ARRAY_SIZE(locations); i++) {
4464                 snprintf(path, PATH_MAX, locations[i].path_fmt, buf.release);
4465
4466                 if (access(path, R_OK))
4467                         continue;
4468
4469                 if (locations[i].raw_btf)
4470                         btf = btf__parse_raw(path);
4471                 else
4472                         btf = btf__parse_elf(path, NULL);
4473
4474                 pr_debug("loading kernel BTF '%s': %ld\n",
4475                          path, IS_ERR(btf) ? PTR_ERR(btf) : 0);
4476                 if (IS_ERR(btf))
4477                         continue;
4478
4479                 return btf;
4480         }
4481
4482         pr_warn("failed to find valid kernel BTF\n");
4483         return ERR_PTR(-ESRCH);
4484 }