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