修改led为gpio

hc

2024-10-12 a5969cabbb4660eab42b6ef0412cbbd1200cf14d

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