tools/lib/bpf/btf.c

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