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