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