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