tools/lib/bpf/btf.c

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