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