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