]>
Commit | Line | Data |
---|---|---|
1bc38b8f | 1 | // SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) |
8a138aed MKL |
2 | /* Copyright (c) 2018 Facebook */ |
3 | ||
cdb2f920 | 4 | #include <endian.h> |
96408c43 | 5 | #include <stdio.h> |
8a138aed | 6 | #include <stdlib.h> |
8a138aed | 7 | #include <string.h> |
e6c64855 | 8 | #include <fcntl.h> |
8a138aed MKL |
9 | #include <unistd.h> |
10 | #include <errno.h> | |
11 | #include <linux/err.h> | |
12 | #include <linux/btf.h> | |
e6c64855 | 13 | #include <gelf.h> |
8a138aed MKL |
14 | #include "btf.h" |
15 | #include "bpf.h" | |
8461ef8b | 16 | #include "libbpf.h" |
d72386fe | 17 | #include "libbpf_internal.h" |
2fc3fc0b | 18 | #include "hashmap.h" |
8a138aed | 19 | |
5aab392c AN |
20 | #define BTF_MAX_NR_TYPES 0x7fffffff |
21 | #define BTF_MAX_STR_OFFSET 0x7fffffff | |
8a138aed | 22 | |
92b57121 OK |
23 | #define IS_MODIFIER(k) (((k) == BTF_KIND_TYPEDEF) || \ |
24 | ((k) == BTF_KIND_VOLATILE) || \ | |
25 | ((k) == BTF_KIND_CONST) || \ | |
26 | ((k) == BTF_KIND_RESTRICT)) | |
27 | ||
1713d68b DB |
28 | #define IS_VAR(k) ((k) == BTF_KIND_VAR) |
29 | ||
8a138aed MKL |
30 | static struct btf_type btf_void; |
31 | ||
32 | struct btf { | |
33 | union { | |
34 | struct btf_header *hdr; | |
35 | void *data; | |
36 | }; | |
37 | struct btf_type **types; | |
38 | const char *strings; | |
39 | void *nohdr_data; | |
5b891af7 MKL |
40 | __u32 nr_types; |
41 | __u32 types_size; | |
42 | __u32 data_size; | |
8a138aed MKL |
43 | int fd; |
44 | }; | |
45 | ||
3d650141 MKL |
46 | struct btf_ext_info { |
47 | /* | |
ae4ab4b4 AN |
48 | * info points to the individual info section (e.g. func_info and |
49 | * line_info) from the .BTF.ext. It does not include the __u32 rec_size. | |
3d650141 MKL |
50 | */ |
51 | void *info; | |
52 | __u32 rec_size; | |
53 | __u32 len; | |
54 | }; | |
55 | ||
2993e051 | 56 | struct btf_ext { |
ae4ab4b4 AN |
57 | union { |
58 | struct btf_ext_header *hdr; | |
59 | void *data; | |
60 | }; | |
3d650141 MKL |
61 | struct btf_ext_info func_info; |
62 | struct btf_ext_info line_info; | |
ae4ab4b4 | 63 | __u32 data_size; |
2993e051 YS |
64 | }; |
65 | ||
3d650141 | 66 | struct btf_ext_info_sec { |
f0187f0b | 67 | __u32 sec_name_off; |
3d650141 MKL |
68 | __u32 num_info; |
69 | /* Followed by num_info * record_size number of bytes */ | |
f0187f0b MKL |
70 | __u8 data[0]; |
71 | }; | |
72 | ||
2993e051 YS |
73 | /* The minimum bpf_func_info checked by the loader */ |
74 | struct bpf_func_info_min { | |
84ecc1f9 | 75 | __u32 insn_off; |
2993e051 YS |
76 | __u32 type_id; |
77 | }; | |
78 | ||
3d650141 MKL |
79 | /* The minimum bpf_line_info checked by the loader */ |
80 | struct bpf_line_info_min { | |
81 | __u32 insn_off; | |
82 | __u32 file_name_off; | |
83 | __u32 line_off; | |
84 | __u32 line_col; | |
85 | }; | |
86 | ||
d7f5b5e0 YS |
87 | static inline __u64 ptr_to_u64(const void *ptr) |
88 | { | |
89 | return (__u64) (unsigned long) ptr; | |
90 | } | |
91 | ||
8a138aed MKL |
92 | static int btf_add_type(struct btf *btf, struct btf_type *t) |
93 | { | |
94 | if (btf->types_size - btf->nr_types < 2) { | |
95 | struct btf_type **new_types; | |
5b891af7 | 96 | __u32 expand_by, new_size; |
8a138aed MKL |
97 | |
98 | if (btf->types_size == BTF_MAX_NR_TYPES) | |
99 | return -E2BIG; | |
100 | ||
101 | expand_by = max(btf->types_size >> 2, 16); | |
102 | new_size = min(BTF_MAX_NR_TYPES, btf->types_size + expand_by); | |
103 | ||
104 | new_types = realloc(btf->types, sizeof(*new_types) * new_size); | |
105 | if (!new_types) | |
106 | return -ENOMEM; | |
107 | ||
108 | if (btf->nr_types == 0) | |
109 | new_types[0] = &btf_void; | |
110 | ||
111 | btf->types = new_types; | |
112 | btf->types_size = new_size; | |
113 | } | |
114 | ||
115 | btf->types[++(btf->nr_types)] = t; | |
116 | ||
117 | return 0; | |
118 | } | |
119 | ||
8461ef8b | 120 | static int btf_parse_hdr(struct btf *btf) |
8a138aed MKL |
121 | { |
122 | const struct btf_header *hdr = btf->hdr; | |
5b891af7 | 123 | __u32 meta_left; |
8a138aed MKL |
124 | |
125 | if (btf->data_size < sizeof(struct btf_header)) { | |
8461ef8b | 126 | pr_debug("BTF header not found\n"); |
8a138aed MKL |
127 | return -EINVAL; |
128 | } | |
129 | ||
130 | if (hdr->magic != BTF_MAGIC) { | |
8461ef8b | 131 | pr_debug("Invalid BTF magic:%x\n", hdr->magic); |
8a138aed MKL |
132 | return -EINVAL; |
133 | } | |
134 | ||
135 | if (hdr->version != BTF_VERSION) { | |
8461ef8b | 136 | pr_debug("Unsupported BTF version:%u\n", hdr->version); |
8a138aed MKL |
137 | return -ENOTSUP; |
138 | } | |
139 | ||
140 | if (hdr->flags) { | |
8461ef8b | 141 | pr_debug("Unsupported BTF flags:%x\n", hdr->flags); |
8a138aed MKL |
142 | return -ENOTSUP; |
143 | } | |
144 | ||
145 | meta_left = btf->data_size - sizeof(*hdr); | |
146 | if (!meta_left) { | |
8461ef8b | 147 | pr_debug("BTF has no data\n"); |
8a138aed MKL |
148 | return -EINVAL; |
149 | } | |
150 | ||
151 | if (meta_left < hdr->type_off) { | |
8461ef8b | 152 | pr_debug("Invalid BTF type section offset:%u\n", hdr->type_off); |
8a138aed MKL |
153 | return -EINVAL; |
154 | } | |
155 | ||
156 | if (meta_left < hdr->str_off) { | |
8461ef8b | 157 | pr_debug("Invalid BTF string section offset:%u\n", hdr->str_off); |
8a138aed MKL |
158 | return -EINVAL; |
159 | } | |
160 | ||
161 | if (hdr->type_off >= hdr->str_off) { | |
8461ef8b | 162 | pr_debug("BTF type section offset >= string section offset. No type?\n"); |
8a138aed MKL |
163 | return -EINVAL; |
164 | } | |
165 | ||
166 | if (hdr->type_off & 0x02) { | |
8461ef8b | 167 | pr_debug("BTF type section is not aligned to 4 bytes\n"); |
8a138aed MKL |
168 | return -EINVAL; |
169 | } | |
170 | ||
171 | btf->nohdr_data = btf->hdr + 1; | |
172 | ||
173 | return 0; | |
174 | } | |
175 | ||
8461ef8b | 176 | static int btf_parse_str_sec(struct btf *btf) |
8a138aed MKL |
177 | { |
178 | const struct btf_header *hdr = btf->hdr; | |
179 | const char *start = btf->nohdr_data + hdr->str_off; | |
180 | const char *end = start + btf->hdr->str_len; | |
181 | ||
5aab392c | 182 | if (!hdr->str_len || hdr->str_len - 1 > BTF_MAX_STR_OFFSET || |
8a138aed | 183 | start[0] || end[-1]) { |
8461ef8b | 184 | pr_debug("Invalid BTF string section\n"); |
8a138aed MKL |
185 | return -EINVAL; |
186 | } | |
187 | ||
188 | btf->strings = start; | |
189 | ||
190 | return 0; | |
191 | } | |
192 | ||
69eaab04 AN |
193 | static int btf_type_size(struct btf_type *t) |
194 | { | |
195 | int base_size = sizeof(struct btf_type); | |
196 | __u16 vlen = BTF_INFO_VLEN(t->info); | |
197 | ||
198 | switch (BTF_INFO_KIND(t->info)) { | |
199 | case BTF_KIND_FWD: | |
200 | case BTF_KIND_CONST: | |
201 | case BTF_KIND_VOLATILE: | |
202 | case BTF_KIND_RESTRICT: | |
203 | case BTF_KIND_PTR: | |
204 | case BTF_KIND_TYPEDEF: | |
205 | case BTF_KIND_FUNC: | |
206 | return base_size; | |
207 | case BTF_KIND_INT: | |
208 | return base_size + sizeof(__u32); | |
209 | case BTF_KIND_ENUM: | |
210 | return base_size + vlen * sizeof(struct btf_enum); | |
211 | case BTF_KIND_ARRAY: | |
212 | return base_size + sizeof(struct btf_array); | |
213 | case BTF_KIND_STRUCT: | |
214 | case BTF_KIND_UNION: | |
215 | return base_size + vlen * sizeof(struct btf_member); | |
216 | case BTF_KIND_FUNC_PROTO: | |
217 | return base_size + vlen * sizeof(struct btf_param); | |
1713d68b DB |
218 | case BTF_KIND_VAR: |
219 | return base_size + sizeof(struct btf_var); | |
220 | case BTF_KIND_DATASEC: | |
221 | return base_size + vlen * sizeof(struct btf_var_secinfo); | |
69eaab04 AN |
222 | default: |
223 | pr_debug("Unsupported BTF_KIND:%u\n", BTF_INFO_KIND(t->info)); | |
224 | return -EINVAL; | |
225 | } | |
226 | } | |
227 | ||
8461ef8b | 228 | static int btf_parse_type_sec(struct btf *btf) |
8a138aed MKL |
229 | { |
230 | struct btf_header *hdr = btf->hdr; | |
231 | void *nohdr_data = btf->nohdr_data; | |
232 | void *next_type = nohdr_data + hdr->type_off; | |
233 | void *end_type = nohdr_data + hdr->str_off; | |
234 | ||
235 | while (next_type < end_type) { | |
236 | struct btf_type *t = next_type; | |
69eaab04 | 237 | int type_size; |
8a138aed MKL |
238 | int err; |
239 | ||
69eaab04 AN |
240 | type_size = btf_type_size(t); |
241 | if (type_size < 0) | |
242 | return type_size; | |
243 | next_type += type_size; | |
8a138aed MKL |
244 | err = btf_add_type(btf, t); |
245 | if (err) | |
246 | return err; | |
247 | } | |
248 | ||
249 | return 0; | |
250 | } | |
251 | ||
9c651127 AN |
252 | __u32 btf__get_nr_types(const struct btf *btf) |
253 | { | |
254 | return btf->nr_types; | |
255 | } | |
256 | ||
38d5d3b3 | 257 | const struct btf_type *btf__type_by_id(const struct btf *btf, __u32 type_id) |
8a138aed MKL |
258 | { |
259 | if (type_id > btf->nr_types) | |
260 | return NULL; | |
261 | ||
262 | return btf->types[type_id]; | |
263 | } | |
264 | ||
265 | static bool btf_type_is_void(const struct btf_type *t) | |
266 | { | |
267 | return t == &btf_void || BTF_INFO_KIND(t->info) == BTF_KIND_FWD; | |
268 | } | |
269 | ||
270 | static bool btf_type_is_void_or_null(const struct btf_type *t) | |
271 | { | |
272 | return !t || btf_type_is_void(t); | |
273 | } | |
274 | ||
8a138aed MKL |
275 | #define MAX_RESOLVE_DEPTH 32 |
276 | ||
5b891af7 | 277 | __s64 btf__resolve_size(const struct btf *btf, __u32 type_id) |
8a138aed MKL |
278 | { |
279 | const struct btf_array *array; | |
280 | const struct btf_type *t; | |
5b891af7 MKL |
281 | __u32 nelems = 1; |
282 | __s64 size = -1; | |
8a138aed MKL |
283 | int i; |
284 | ||
92b57121 | 285 | t = btf__type_by_id(btf, type_id); |
8a138aed MKL |
286 | for (i = 0; i < MAX_RESOLVE_DEPTH && !btf_type_is_void_or_null(t); |
287 | i++) { | |
8a138aed | 288 | switch (BTF_INFO_KIND(t->info)) { |
69eaab04 AN |
289 | case BTF_KIND_INT: |
290 | case BTF_KIND_STRUCT: | |
291 | case BTF_KIND_UNION: | |
292 | case BTF_KIND_ENUM: | |
1713d68b | 293 | case BTF_KIND_DATASEC: |
69eaab04 AN |
294 | size = t->size; |
295 | goto done; | |
296 | case BTF_KIND_PTR: | |
297 | size = sizeof(void *); | |
298 | goto done; | |
8a138aed MKL |
299 | case BTF_KIND_TYPEDEF: |
300 | case BTF_KIND_VOLATILE: | |
301 | case BTF_KIND_CONST: | |
302 | case BTF_KIND_RESTRICT: | |
1713d68b | 303 | case BTF_KIND_VAR: |
8a138aed MKL |
304 | type_id = t->type; |
305 | break; | |
306 | case BTF_KIND_ARRAY: | |
307 | array = (const struct btf_array *)(t + 1); | |
308 | if (nelems && array->nelems > UINT32_MAX / nelems) | |
309 | return -E2BIG; | |
310 | nelems *= array->nelems; | |
311 | type_id = array->type; | |
312 | break; | |
313 | default: | |
314 | return -EINVAL; | |
315 | } | |
316 | ||
92b57121 | 317 | t = btf__type_by_id(btf, type_id); |
8a138aed MKL |
318 | } |
319 | ||
320 | if (size < 0) | |
321 | return -EINVAL; | |
322 | ||
69eaab04 | 323 | done: |
8a138aed MKL |
324 | if (nelems && size > UINT32_MAX / nelems) |
325 | return -E2BIG; | |
326 | ||
327 | return nelems * size; | |
328 | } | |
329 | ||
92b57121 OK |
330 | int btf__resolve_type(const struct btf *btf, __u32 type_id) |
331 | { | |
332 | const struct btf_type *t; | |
333 | int depth = 0; | |
334 | ||
335 | t = btf__type_by_id(btf, type_id); | |
336 | while (depth < MAX_RESOLVE_DEPTH && | |
337 | !btf_type_is_void_or_null(t) && | |
1713d68b DB |
338 | (IS_MODIFIER(BTF_INFO_KIND(t->info)) || |
339 | IS_VAR(BTF_INFO_KIND(t->info)))) { | |
92b57121 OK |
340 | type_id = t->type; |
341 | t = btf__type_by_id(btf, type_id); | |
342 | depth++; | |
343 | } | |
344 | ||
345 | if (depth == MAX_RESOLVE_DEPTH || btf_type_is_void_or_null(t)) | |
346 | return -EINVAL; | |
347 | ||
348 | return type_id; | |
349 | } | |
350 | ||
5b891af7 | 351 | __s32 btf__find_by_name(const struct btf *btf, const char *type_name) |
8a138aed | 352 | { |
5b891af7 | 353 | __u32 i; |
8a138aed MKL |
354 | |
355 | if (!strcmp(type_name, "void")) | |
356 | return 0; | |
357 | ||
358 | for (i = 1; i <= btf->nr_types; i++) { | |
359 | const struct btf_type *t = btf->types[i]; | |
92b57121 | 360 | const char *name = btf__name_by_offset(btf, t->name_off); |
8a138aed MKL |
361 | |
362 | if (name && !strcmp(type_name, name)) | |
363 | return i; | |
364 | } | |
365 | ||
366 | return -ENOENT; | |
367 | } | |
368 | ||
369 | void btf__free(struct btf *btf) | |
370 | { | |
371 | if (!btf) | |
372 | return; | |
373 | ||
374 | if (btf->fd != -1) | |
375 | close(btf->fd); | |
376 | ||
377 | free(btf->data); | |
378 | free(btf->types); | |
379 | free(btf); | |
380 | } | |
381 | ||
8461ef8b | 382 | struct btf *btf__new(__u8 *data, __u32 size) |
8a138aed | 383 | { |
8a138aed MKL |
384 | struct btf *btf; |
385 | int err; | |
386 | ||
387 | btf = calloc(1, sizeof(struct btf)); | |
388 | if (!btf) | |
389 | return ERR_PTR(-ENOMEM); | |
390 | ||
391 | btf->fd = -1; | |
392 | ||
8a138aed MKL |
393 | btf->data = malloc(size); |
394 | if (!btf->data) { | |
395 | err = -ENOMEM; | |
396 | goto done; | |
397 | } | |
398 | ||
399 | memcpy(btf->data, data, size); | |
400 | btf->data_size = size; | |
401 | ||
8461ef8b | 402 | err = btf_parse_hdr(btf); |
8a138aed MKL |
403 | if (err) |
404 | goto done; | |
405 | ||
8461ef8b | 406 | err = btf_parse_str_sec(btf); |
8a138aed MKL |
407 | if (err) |
408 | goto done; | |
409 | ||
8461ef8b | 410 | err = btf_parse_type_sec(btf); |
8a138aed MKL |
411 | |
412 | done: | |
8a138aed MKL |
413 | if (err) { |
414 | btf__free(btf); | |
415 | return ERR_PTR(err); | |
416 | } | |
417 | ||
418 | return btf; | |
419 | } | |
420 | ||
e6c64855 AN |
421 | static bool btf_check_endianness(const GElf_Ehdr *ehdr) |
422 | { | |
cdb2f920 | 423 | #if __BYTE_ORDER == __LITTLE_ENDIAN |
e6c64855 | 424 | return ehdr->e_ident[EI_DATA] == ELFDATA2LSB; |
cdb2f920 | 425 | #elif __BYTE_ORDER == __BIG_ENDIAN |
e6c64855 AN |
426 | return ehdr->e_ident[EI_DATA] == ELFDATA2MSB; |
427 | #else | |
428 | # error "Unrecognized __BYTE_ORDER__" | |
429 | #endif | |
430 | } | |
431 | ||
432 | struct btf *btf__parse_elf(const char *path, struct btf_ext **btf_ext) | |
433 | { | |
434 | Elf_Data *btf_data = NULL, *btf_ext_data = NULL; | |
435 | int err = 0, fd = -1, idx = 0; | |
436 | struct btf *btf = NULL; | |
437 | Elf_Scn *scn = NULL; | |
438 | Elf *elf = NULL; | |
439 | GElf_Ehdr ehdr; | |
440 | ||
441 | if (elf_version(EV_CURRENT) == EV_NONE) { | |
442 | pr_warning("failed to init libelf for %s\n", path); | |
443 | return ERR_PTR(-LIBBPF_ERRNO__LIBELF); | |
444 | } | |
445 | ||
446 | fd = open(path, O_RDONLY); | |
447 | if (fd < 0) { | |
448 | err = -errno; | |
449 | pr_warning("failed to open %s: %s\n", path, strerror(errno)); | |
450 | return ERR_PTR(err); | |
451 | } | |
452 | ||
453 | err = -LIBBPF_ERRNO__FORMAT; | |
454 | ||
455 | elf = elf_begin(fd, ELF_C_READ, NULL); | |
456 | if (!elf) { | |
457 | pr_warning("failed to open %s as ELF file\n", path); | |
458 | goto done; | |
459 | } | |
460 | if (!gelf_getehdr(elf, &ehdr)) { | |
461 | pr_warning("failed to get EHDR from %s\n", path); | |
462 | goto done; | |
463 | } | |
464 | if (!btf_check_endianness(&ehdr)) { | |
465 | pr_warning("non-native ELF endianness is not supported\n"); | |
466 | goto done; | |
467 | } | |
468 | if (!elf_rawdata(elf_getscn(elf, ehdr.e_shstrndx), NULL)) { | |
469 | pr_warning("failed to get e_shstrndx from %s\n", path); | |
470 | goto done; | |
471 | } | |
472 | ||
473 | while ((scn = elf_nextscn(elf, scn)) != NULL) { | |
474 | GElf_Shdr sh; | |
475 | char *name; | |
476 | ||
477 | idx++; | |
478 | if (gelf_getshdr(scn, &sh) != &sh) { | |
479 | pr_warning("failed to get section(%d) header from %s\n", | |
480 | idx, path); | |
481 | goto done; | |
482 | } | |
483 | name = elf_strptr(elf, ehdr.e_shstrndx, sh.sh_name); | |
484 | if (!name) { | |
485 | pr_warning("failed to get section(%d) name from %s\n", | |
486 | idx, path); | |
487 | goto done; | |
488 | } | |
489 | if (strcmp(name, BTF_ELF_SEC) == 0) { | |
490 | btf_data = elf_getdata(scn, 0); | |
491 | if (!btf_data) { | |
492 | pr_warning("failed to get section(%d, %s) data from %s\n", | |
493 | idx, name, path); | |
494 | goto done; | |
495 | } | |
496 | continue; | |
497 | } else if (btf_ext && strcmp(name, BTF_EXT_ELF_SEC) == 0) { | |
498 | btf_ext_data = elf_getdata(scn, 0); | |
499 | if (!btf_ext_data) { | |
500 | pr_warning("failed to get section(%d, %s) data from %s\n", | |
501 | idx, name, path); | |
502 | goto done; | |
503 | } | |
504 | continue; | |
505 | } | |
506 | } | |
507 | ||
508 | err = 0; | |
509 | ||
510 | if (!btf_data) { | |
511 | err = -ENOENT; | |
512 | goto done; | |
513 | } | |
514 | btf = btf__new(btf_data->d_buf, btf_data->d_size); | |
515 | if (IS_ERR(btf)) | |
516 | goto done; | |
517 | ||
518 | if (btf_ext && btf_ext_data) { | |
519 | *btf_ext = btf_ext__new(btf_ext_data->d_buf, | |
520 | btf_ext_data->d_size); | |
521 | if (IS_ERR(*btf_ext)) | |
522 | goto done; | |
523 | } else if (btf_ext) { | |
524 | *btf_ext = NULL; | |
525 | } | |
526 | done: | |
527 | if (elf) | |
528 | elf_end(elf); | |
529 | close(fd); | |
530 | ||
531 | if (err) | |
532 | return ERR_PTR(err); | |
533 | /* | |
534 | * btf is always parsed before btf_ext, so no need to clean up | |
535 | * btf_ext, if btf loading failed | |
536 | */ | |
537 | if (IS_ERR(btf)) | |
538 | return btf; | |
539 | if (btf_ext && IS_ERR(*btf_ext)) { | |
540 | btf__free(btf); | |
541 | err = PTR_ERR(*btf_ext); | |
542 | return ERR_PTR(err); | |
543 | } | |
544 | return btf; | |
545 | } | |
546 | ||
1713d68b DB |
547 | static int compare_vsi_off(const void *_a, const void *_b) |
548 | { | |
549 | const struct btf_var_secinfo *a = _a; | |
550 | const struct btf_var_secinfo *b = _b; | |
551 | ||
552 | return a->offset - b->offset; | |
553 | } | |
554 | ||
555 | static int btf_fixup_datasec(struct bpf_object *obj, struct btf *btf, | |
556 | struct btf_type *t) | |
557 | { | |
558 | __u32 size = 0, off = 0, i, vars = BTF_INFO_VLEN(t->info); | |
559 | const char *name = btf__name_by_offset(btf, t->name_off); | |
560 | const struct btf_type *t_var; | |
561 | struct btf_var_secinfo *vsi; | |
562 | struct btf_var *var; | |
563 | int ret; | |
564 | ||
565 | if (!name) { | |
566 | pr_debug("No name found in string section for DATASEC kind.\n"); | |
567 | return -ENOENT; | |
568 | } | |
569 | ||
570 | ret = bpf_object__section_size(obj, name, &size); | |
571 | if (ret || !size || (t->size && t->size != size)) { | |
572 | pr_debug("Invalid size for section %s: %u bytes\n", name, size); | |
573 | return -ENOENT; | |
574 | } | |
575 | ||
576 | t->size = size; | |
577 | ||
578 | for (i = 0, vsi = (struct btf_var_secinfo *)(t + 1); | |
579 | i < vars; i++, vsi++) { | |
580 | t_var = btf__type_by_id(btf, vsi->type); | |
581 | var = (struct btf_var *)(t_var + 1); | |
582 | ||
583 | if (BTF_INFO_KIND(t_var->info) != BTF_KIND_VAR) { | |
584 | pr_debug("Non-VAR type seen in section %s\n", name); | |
585 | return -EINVAL; | |
586 | } | |
587 | ||
588 | if (var->linkage == BTF_VAR_STATIC) | |
589 | continue; | |
590 | ||
591 | name = btf__name_by_offset(btf, t_var->name_off); | |
592 | if (!name) { | |
593 | pr_debug("No name found in string section for VAR kind\n"); | |
594 | return -ENOENT; | |
595 | } | |
596 | ||
597 | ret = bpf_object__variable_offset(obj, name, &off); | |
598 | if (ret) { | |
599 | pr_debug("No offset found in symbol table for VAR %s\n", name); | |
600 | return -ENOENT; | |
601 | } | |
602 | ||
603 | vsi->offset = off; | |
604 | } | |
605 | ||
606 | qsort(t + 1, vars, sizeof(*vsi), compare_vsi_off); | |
607 | return 0; | |
608 | } | |
609 | ||
610 | int btf__finalize_data(struct bpf_object *obj, struct btf *btf) | |
611 | { | |
612 | int err = 0; | |
613 | __u32 i; | |
614 | ||
615 | for (i = 1; i <= btf->nr_types; i++) { | |
616 | struct btf_type *t = btf->types[i]; | |
617 | ||
618 | /* Loader needs to fix up some of the things compiler | |
619 | * couldn't get its hands on while emitting BTF. This | |
620 | * is section size and global variable offset. We use | |
621 | * the info from the ELF itself for this purpose. | |
622 | */ | |
623 | if (BTF_INFO_KIND(t->info) == BTF_KIND_DATASEC) { | |
624 | err = btf_fixup_datasec(obj, btf, t); | |
625 | if (err) | |
626 | break; | |
627 | } | |
628 | } | |
629 | ||
630 | return err; | |
631 | } | |
632 | ||
d29d87f7 AN |
633 | int btf__load(struct btf *btf) |
634 | { | |
635 | __u32 log_buf_size = BPF_LOG_BUF_SIZE; | |
636 | char *log_buf = NULL; | |
637 | int err = 0; | |
638 | ||
639 | if (btf->fd >= 0) | |
640 | return -EEXIST; | |
641 | ||
642 | log_buf = malloc(log_buf_size); | |
643 | if (!log_buf) | |
644 | return -ENOMEM; | |
645 | ||
646 | *log_buf = 0; | |
647 | ||
648 | btf->fd = bpf_load_btf(btf->data, btf->data_size, | |
649 | log_buf, log_buf_size, false); | |
650 | if (btf->fd < 0) { | |
651 | err = -errno; | |
652 | pr_warning("Error loading BTF: %s(%d)\n", strerror(errno), errno); | |
653 | if (*log_buf) | |
654 | pr_warning("%s\n", log_buf); | |
655 | goto done; | |
656 | } | |
657 | ||
658 | done: | |
659 | free(log_buf); | |
660 | return err; | |
661 | } | |
662 | ||
8a138aed MKL |
663 | int btf__fd(const struct btf *btf) |
664 | { | |
665 | return btf->fd; | |
666 | } | |
92b57121 | 667 | |
02c87446 AN |
668 | const void *btf__get_raw_data(const struct btf *btf, __u32 *size) |
669 | { | |
670 | *size = btf->data_size; | |
671 | return btf->data; | |
672 | } | |
673 | ||
92b57121 OK |
674 | const char *btf__name_by_offset(const struct btf *btf, __u32 offset) |
675 | { | |
676 | if (offset < btf->hdr->str_len) | |
677 | return &btf->strings[offset]; | |
678 | else | |
679 | return NULL; | |
680 | } | |
2993e051 | 681 | |
1d2f44ca | 682 | int btf__get_from_id(__u32 id, struct btf **btf) |
d7f5b5e0 YS |
683 | { |
684 | struct bpf_btf_info btf_info = { 0 }; | |
685 | __u32 len = sizeof(btf_info); | |
686 | __u32 last_size; | |
687 | int btf_fd; | |
688 | void *ptr; | |
689 | int err; | |
690 | ||
691 | err = 0; | |
692 | *btf = NULL; | |
693 | btf_fd = bpf_btf_get_fd_by_id(id); | |
694 | if (btf_fd < 0) | |
695 | return 0; | |
696 | ||
697 | /* we won't know btf_size until we call bpf_obj_get_info_by_fd(). so | |
698 | * let's start with a sane default - 4KiB here - and resize it only if | |
699 | * bpf_obj_get_info_by_fd() needs a bigger buffer. | |
700 | */ | |
701 | btf_info.btf_size = 4096; | |
702 | last_size = btf_info.btf_size; | |
703 | ptr = malloc(last_size); | |
704 | if (!ptr) { | |
705 | err = -ENOMEM; | |
706 | goto exit_free; | |
707 | } | |
708 | ||
1ad9cbb8 | 709 | memset(ptr, 0, last_size); |
d7f5b5e0 YS |
710 | btf_info.btf = ptr_to_u64(ptr); |
711 | err = bpf_obj_get_info_by_fd(btf_fd, &btf_info, &len); | |
712 | ||
713 | if (!err && btf_info.btf_size > last_size) { | |
714 | void *temp_ptr; | |
715 | ||
716 | last_size = btf_info.btf_size; | |
717 | temp_ptr = realloc(ptr, last_size); | |
718 | if (!temp_ptr) { | |
719 | err = -ENOMEM; | |
720 | goto exit_free; | |
721 | } | |
722 | ptr = temp_ptr; | |
1ad9cbb8 | 723 | memset(ptr, 0, last_size); |
d7f5b5e0 YS |
724 | btf_info.btf = ptr_to_u64(ptr); |
725 | err = bpf_obj_get_info_by_fd(btf_fd, &btf_info, &len); | |
726 | } | |
727 | ||
728 | if (err || btf_info.btf_size > last_size) { | |
729 | err = errno; | |
730 | goto exit_free; | |
731 | } | |
732 | ||
8461ef8b | 733 | *btf = btf__new((__u8 *)(long)btf_info.btf, btf_info.btf_size); |
d7f5b5e0 YS |
734 | if (IS_ERR(*btf)) { |
735 | err = PTR_ERR(*btf); | |
736 | *btf = NULL; | |
737 | } | |
738 | ||
739 | exit_free: | |
740 | close(btf_fd); | |
741 | free(ptr); | |
742 | ||
743 | return err; | |
744 | } | |
745 | ||
a6c109a6 | 746 | int btf__get_map_kv_tids(const struct btf *btf, const char *map_name, |
96408c43 YS |
747 | __u32 expected_key_size, __u32 expected_value_size, |
748 | __u32 *key_type_id, __u32 *value_type_id) | |
749 | { | |
750 | const struct btf_type *container_type; | |
751 | const struct btf_member *key, *value; | |
752 | const size_t max_name = 256; | |
753 | char container_name[max_name]; | |
754 | __s64 key_size, value_size; | |
755 | __s32 container_id; | |
756 | ||
757 | if (snprintf(container_name, max_name, "____btf_map_%s", map_name) == | |
758 | max_name) { | |
759 | pr_warning("map:%s length of '____btf_map_%s' is too long\n", | |
760 | map_name, map_name); | |
761 | return -EINVAL; | |
762 | } | |
763 | ||
764 | container_id = btf__find_by_name(btf, container_name); | |
765 | if (container_id < 0) { | |
f7748e29 YS |
766 | pr_debug("map:%s container_name:%s cannot be found in BTF. Missing BPF_ANNOTATE_KV_PAIR?\n", |
767 | map_name, container_name); | |
96408c43 YS |
768 | return container_id; |
769 | } | |
770 | ||
771 | container_type = btf__type_by_id(btf, container_id); | |
772 | if (!container_type) { | |
773 | pr_warning("map:%s cannot find BTF type for container_id:%u\n", | |
774 | map_name, container_id); | |
775 | return -EINVAL; | |
776 | } | |
777 | ||
778 | if (BTF_INFO_KIND(container_type->info) != BTF_KIND_STRUCT || | |
779 | BTF_INFO_VLEN(container_type->info) < 2) { | |
780 | pr_warning("map:%s container_name:%s is an invalid container struct\n", | |
781 | map_name, container_name); | |
782 | return -EINVAL; | |
783 | } | |
784 | ||
785 | key = (struct btf_member *)(container_type + 1); | |
786 | value = key + 1; | |
787 | ||
788 | key_size = btf__resolve_size(btf, key->type); | |
789 | if (key_size < 0) { | |
790 | pr_warning("map:%s invalid BTF key_type_size\n", map_name); | |
791 | return key_size; | |
792 | } | |
793 | ||
794 | if (expected_key_size != key_size) { | |
795 | pr_warning("map:%s btf_key_type_size:%u != map_def_key_size:%u\n", | |
796 | map_name, (__u32)key_size, expected_key_size); | |
797 | return -EINVAL; | |
798 | } | |
799 | ||
800 | value_size = btf__resolve_size(btf, value->type); | |
801 | if (value_size < 0) { | |
802 | pr_warning("map:%s invalid BTF value_type_size\n", map_name); | |
803 | return value_size; | |
804 | } | |
805 | ||
806 | if (expected_value_size != value_size) { | |
807 | pr_warning("map:%s btf_value_type_size:%u != map_def_value_size:%u\n", | |
808 | map_name, (__u32)value_size, expected_value_size); | |
809 | return -EINVAL; | |
810 | } | |
811 | ||
812 | *key_type_id = key->type; | |
813 | *value_type_id = value->type; | |
814 | ||
815 | return 0; | |
816 | } | |
817 | ||
ae4ab4b4 | 818 | struct btf_ext_sec_setup_param { |
3d650141 MKL |
819 | __u32 off; |
820 | __u32 len; | |
821 | __u32 min_rec_size; | |
822 | struct btf_ext_info *ext_info; | |
823 | const char *desc; | |
824 | }; | |
825 | ||
ae4ab4b4 AN |
826 | static int btf_ext_setup_info(struct btf_ext *btf_ext, |
827 | struct btf_ext_sec_setup_param *ext_sec) | |
2993e051 | 828 | { |
3d650141 MKL |
829 | const struct btf_ext_info_sec *sinfo; |
830 | struct btf_ext_info *ext_info; | |
f0187f0b MKL |
831 | __u32 info_left, record_size; |
832 | /* The start of the info sec (including the __u32 record_size). */ | |
ae4ab4b4 | 833 | void *info; |
f0187f0b | 834 | |
3d650141 | 835 | if (ext_sec->off & 0x03) { |
8461ef8b | 836 | pr_debug(".BTF.ext %s section is not aligned to 4 bytes\n", |
3d650141 | 837 | ext_sec->desc); |
f0187f0b MKL |
838 | return -EINVAL; |
839 | } | |
840 | ||
ae4ab4b4 AN |
841 | info = btf_ext->data + btf_ext->hdr->hdr_len + ext_sec->off; |
842 | info_left = ext_sec->len; | |
843 | ||
844 | if (btf_ext->data + btf_ext->data_size < info + ext_sec->len) { | |
8461ef8b | 845 | pr_debug("%s section (off:%u len:%u) is beyond the end of the ELF section .BTF.ext\n", |
ae4ab4b4 | 846 | ext_sec->desc, ext_sec->off, ext_sec->len); |
f0187f0b MKL |
847 | return -EINVAL; |
848 | } | |
849 | ||
3d650141 | 850 | /* At least a record size */ |
f0187f0b | 851 | if (info_left < sizeof(__u32)) { |
8461ef8b | 852 | pr_debug(".BTF.ext %s record size not found\n", ext_sec->desc); |
2993e051 YS |
853 | return -EINVAL; |
854 | } | |
855 | ||
f0187f0b MKL |
856 | /* The record size needs to meet the minimum standard */ |
857 | record_size = *(__u32 *)info; | |
3d650141 | 858 | if (record_size < ext_sec->min_rec_size || |
f0187f0b | 859 | record_size & 0x03) { |
8461ef8b | 860 | pr_debug("%s section in .BTF.ext has invalid record size %u\n", |
ae4ab4b4 | 861 | ext_sec->desc, record_size); |
2993e051 YS |
862 | return -EINVAL; |
863 | } | |
864 | ||
f0187f0b MKL |
865 | sinfo = info + sizeof(__u32); |
866 | info_left -= sizeof(__u32); | |
2993e051 | 867 | |
3d650141 | 868 | /* If no records, return failure now so .BTF.ext won't be used. */ |
f0187f0b | 869 | if (!info_left) { |
8461ef8b | 870 | pr_debug("%s section in .BTF.ext has no records", ext_sec->desc); |
2993e051 YS |
871 | return -EINVAL; |
872 | } | |
873 | ||
f0187f0b | 874 | while (info_left) { |
3d650141 | 875 | unsigned int sec_hdrlen = sizeof(struct btf_ext_info_sec); |
f0187f0b MKL |
876 | __u64 total_record_size; |
877 | __u32 num_records; | |
878 | ||
879 | if (info_left < sec_hdrlen) { | |
8461ef8b | 880 | pr_debug("%s section header is not found in .BTF.ext\n", |
3d650141 | 881 | ext_sec->desc); |
2993e051 YS |
882 | return -EINVAL; |
883 | } | |
884 | ||
3d650141 | 885 | num_records = sinfo->num_info; |
2993e051 | 886 | if (num_records == 0) { |
8461ef8b | 887 | pr_debug("%s section has incorrect num_records in .BTF.ext\n", |
3d650141 | 888 | ext_sec->desc); |
2993e051 YS |
889 | return -EINVAL; |
890 | } | |
891 | ||
892 | total_record_size = sec_hdrlen + | |
893 | (__u64)num_records * record_size; | |
f0187f0b | 894 | if (info_left < total_record_size) { |
8461ef8b | 895 | pr_debug("%s section has incorrect num_records in .BTF.ext\n", |
3d650141 | 896 | ext_sec->desc); |
2993e051 YS |
897 | return -EINVAL; |
898 | } | |
899 | ||
f0187f0b | 900 | info_left -= total_record_size; |
2993e051 YS |
901 | sinfo = (void *)sinfo + total_record_size; |
902 | } | |
903 | ||
3d650141 MKL |
904 | ext_info = ext_sec->ext_info; |
905 | ext_info->len = ext_sec->len - sizeof(__u32); | |
906 | ext_info->rec_size = record_size; | |
ae4ab4b4 | 907 | ext_info->info = info + sizeof(__u32); |
f0187f0b | 908 | |
2993e051 YS |
909 | return 0; |
910 | } | |
911 | ||
ae4ab4b4 | 912 | static int btf_ext_setup_func_info(struct btf_ext *btf_ext) |
3d650141 | 913 | { |
ae4ab4b4 AN |
914 | struct btf_ext_sec_setup_param param = { |
915 | .off = btf_ext->hdr->func_info_off, | |
916 | .len = btf_ext->hdr->func_info_len, | |
3d650141 MKL |
917 | .min_rec_size = sizeof(struct bpf_func_info_min), |
918 | .ext_info = &btf_ext->func_info, | |
919 | .desc = "func_info" | |
920 | }; | |
921 | ||
ae4ab4b4 | 922 | return btf_ext_setup_info(btf_ext, ¶m); |
3d650141 MKL |
923 | } |
924 | ||
ae4ab4b4 | 925 | static int btf_ext_setup_line_info(struct btf_ext *btf_ext) |
3d650141 | 926 | { |
ae4ab4b4 AN |
927 | struct btf_ext_sec_setup_param param = { |
928 | .off = btf_ext->hdr->line_info_off, | |
929 | .len = btf_ext->hdr->line_info_len, | |
3d650141 MKL |
930 | .min_rec_size = sizeof(struct bpf_line_info_min), |
931 | .ext_info = &btf_ext->line_info, | |
932 | .desc = "line_info", | |
933 | }; | |
934 | ||
ae4ab4b4 | 935 | return btf_ext_setup_info(btf_ext, ¶m); |
3d650141 MKL |
936 | } |
937 | ||
8461ef8b | 938 | static int btf_ext_parse_hdr(__u8 *data, __u32 data_size) |
2993e051 YS |
939 | { |
940 | const struct btf_ext_header *hdr = (struct btf_ext_header *)data; | |
2993e051 YS |
941 | |
942 | if (data_size < offsetof(struct btf_ext_header, func_info_off) || | |
943 | data_size < hdr->hdr_len) { | |
8461ef8b | 944 | pr_debug("BTF.ext header not found"); |
2993e051 YS |
945 | return -EINVAL; |
946 | } | |
947 | ||
948 | if (hdr->magic != BTF_MAGIC) { | |
8461ef8b | 949 | pr_debug("Invalid BTF.ext magic:%x\n", hdr->magic); |
2993e051 YS |
950 | return -EINVAL; |
951 | } | |
952 | ||
953 | if (hdr->version != BTF_VERSION) { | |
8461ef8b | 954 | pr_debug("Unsupported BTF.ext version:%u\n", hdr->version); |
2993e051 YS |
955 | return -ENOTSUP; |
956 | } | |
957 | ||
958 | if (hdr->flags) { | |
8461ef8b | 959 | pr_debug("Unsupported BTF.ext flags:%x\n", hdr->flags); |
2993e051 YS |
960 | return -ENOTSUP; |
961 | } | |
962 | ||
f0187f0b | 963 | if (data_size == hdr->hdr_len) { |
8461ef8b | 964 | pr_debug("BTF.ext has no data\n"); |
2993e051 YS |
965 | return -EINVAL; |
966 | } | |
967 | ||
f0187f0b | 968 | return 0; |
2993e051 YS |
969 | } |
970 | ||
971 | void btf_ext__free(struct btf_ext *btf_ext) | |
972 | { | |
973 | if (!btf_ext) | |
974 | return; | |
ae4ab4b4 | 975 | free(btf_ext->data); |
2993e051 YS |
976 | free(btf_ext); |
977 | } | |
978 | ||
8461ef8b | 979 | struct btf_ext *btf_ext__new(__u8 *data, __u32 size) |
2993e051 | 980 | { |
2993e051 | 981 | struct btf_ext *btf_ext; |
2993e051 YS |
982 | int err; |
983 | ||
8461ef8b | 984 | err = btf_ext_parse_hdr(data, size); |
2993e051 YS |
985 | if (err) |
986 | return ERR_PTR(err); | |
987 | ||
988 | btf_ext = calloc(1, sizeof(struct btf_ext)); | |
989 | if (!btf_ext) | |
990 | return ERR_PTR(-ENOMEM); | |
991 | ||
ae4ab4b4 AN |
992 | btf_ext->data_size = size; |
993 | btf_ext->data = malloc(size); | |
994 | if (!btf_ext->data) { | |
995 | err = -ENOMEM; | |
996 | goto done; | |
2993e051 | 997 | } |
ae4ab4b4 AN |
998 | memcpy(btf_ext->data, data, size); |
999 | ||
1000 | err = btf_ext_setup_func_info(btf_ext); | |
1001 | if (err) | |
1002 | goto done; | |
2993e051 | 1003 | |
ae4ab4b4 AN |
1004 | err = btf_ext_setup_line_info(btf_ext); |
1005 | if (err) | |
1006 | goto done; | |
1007 | ||
1008 | done: | |
3d650141 MKL |
1009 | if (err) { |
1010 | btf_ext__free(btf_ext); | |
1011 | return ERR_PTR(err); | |
1012 | } | |
1013 | ||
2993e051 YS |
1014 | return btf_ext; |
1015 | } | |
1016 | ||
ae4ab4b4 AN |
1017 | const void *btf_ext__get_raw_data(const struct btf_ext *btf_ext, __u32 *size) |
1018 | { | |
1019 | *size = btf_ext->data_size; | |
1020 | return btf_ext->data; | |
1021 | } | |
1022 | ||
3d650141 MKL |
1023 | static int btf_ext_reloc_info(const struct btf *btf, |
1024 | const struct btf_ext_info *ext_info, | |
1025 | const char *sec_name, __u32 insns_cnt, | |
1026 | void **info, __u32 *cnt) | |
2993e051 | 1027 | { |
3d650141 MKL |
1028 | __u32 sec_hdrlen = sizeof(struct btf_ext_info_sec); |
1029 | __u32 i, record_size, existing_len, records_len; | |
1030 | struct btf_ext_info_sec *sinfo; | |
2993e051 YS |
1031 | const char *info_sec_name; |
1032 | __u64 remain_len; | |
1033 | void *data; | |
1034 | ||
3d650141 MKL |
1035 | record_size = ext_info->rec_size; |
1036 | sinfo = ext_info->info; | |
1037 | remain_len = ext_info->len; | |
2993e051 | 1038 | while (remain_len > 0) { |
3d650141 | 1039 | records_len = sinfo->num_info * record_size; |
2993e051 YS |
1040 | info_sec_name = btf__name_by_offset(btf, sinfo->sec_name_off); |
1041 | if (strcmp(info_sec_name, sec_name)) { | |
1042 | remain_len -= sec_hdrlen + records_len; | |
1043 | sinfo = (void *)sinfo + sec_hdrlen + records_len; | |
1044 | continue; | |
1045 | } | |
1046 | ||
3d650141 MKL |
1047 | existing_len = (*cnt) * record_size; |
1048 | data = realloc(*info, existing_len + records_len); | |
2993e051 YS |
1049 | if (!data) |
1050 | return -ENOMEM; | |
1051 | ||
3d650141 | 1052 | memcpy(data + existing_len, sinfo->data, records_len); |
84ecc1f9 | 1053 | /* adjust insn_off only, the rest data will be passed |
2993e051 YS |
1054 | * to the kernel. |
1055 | */ | |
3d650141 MKL |
1056 | for (i = 0; i < sinfo->num_info; i++) { |
1057 | __u32 *insn_off; | |
2993e051 | 1058 | |
3d650141 MKL |
1059 | insn_off = data + existing_len + (i * record_size); |
1060 | *insn_off = *insn_off / sizeof(struct bpf_insn) + | |
2993e051 YS |
1061 | insns_cnt; |
1062 | } | |
3d650141 MKL |
1063 | *info = data; |
1064 | *cnt += sinfo->num_info; | |
2993e051 YS |
1065 | return 0; |
1066 | } | |
1067 | ||
f0187f0b MKL |
1068 | return -ENOENT; |
1069 | } | |
1070 | ||
ae4ab4b4 AN |
1071 | int btf_ext__reloc_func_info(const struct btf *btf, |
1072 | const struct btf_ext *btf_ext, | |
3d650141 MKL |
1073 | const char *sec_name, __u32 insns_cnt, |
1074 | void **func_info, __u32 *cnt) | |
1075 | { | |
1076 | return btf_ext_reloc_info(btf, &btf_ext->func_info, sec_name, | |
1077 | insns_cnt, func_info, cnt); | |
1078 | } | |
1079 | ||
ae4ab4b4 AN |
1080 | int btf_ext__reloc_line_info(const struct btf *btf, |
1081 | const struct btf_ext *btf_ext, | |
3d650141 MKL |
1082 | const char *sec_name, __u32 insns_cnt, |
1083 | void **line_info, __u32 *cnt) | |
1084 | { | |
1085 | return btf_ext_reloc_info(btf, &btf_ext->line_info, sec_name, | |
1086 | insns_cnt, line_info, cnt); | |
1087 | } | |
1088 | ||
f0187f0b MKL |
1089 | __u32 btf_ext__func_info_rec_size(const struct btf_ext *btf_ext) |
1090 | { | |
3d650141 MKL |
1091 | return btf_ext->func_info.rec_size; |
1092 | } | |
1093 | ||
1094 | __u32 btf_ext__line_info_rec_size(const struct btf_ext *btf_ext) | |
1095 | { | |
1096 | return btf_ext->line_info.rec_size; | |
2993e051 | 1097 | } |
d5caef5b AN |
1098 | |
1099 | struct btf_dedup; | |
1100 | ||
1101 | static struct btf_dedup *btf_dedup_new(struct btf *btf, struct btf_ext *btf_ext, | |
1102 | const struct btf_dedup_opts *opts); | |
1103 | static void btf_dedup_free(struct btf_dedup *d); | |
1104 | static int btf_dedup_strings(struct btf_dedup *d); | |
1105 | static int btf_dedup_prim_types(struct btf_dedup *d); | |
1106 | static int btf_dedup_struct_types(struct btf_dedup *d); | |
1107 | static int btf_dedup_ref_types(struct btf_dedup *d); | |
1108 | static int btf_dedup_compact_types(struct btf_dedup *d); | |
1109 | static int btf_dedup_remap_types(struct btf_dedup *d); | |
1110 | ||
1111 | /* | |
1112 | * Deduplicate BTF types and strings. | |
1113 | * | |
1114 | * BTF dedup algorithm takes as an input `struct btf` representing `.BTF` ELF | |
1115 | * section with all BTF type descriptors and string data. It overwrites that | |
1116 | * memory in-place with deduplicated types and strings without any loss of | |
1117 | * information. If optional `struct btf_ext` representing '.BTF.ext' ELF section | |
1118 | * is provided, all the strings referenced from .BTF.ext section are honored | |
1119 | * and updated to point to the right offsets after deduplication. | |
1120 | * | |
1121 | * If function returns with error, type/string data might be garbled and should | |
1122 | * be discarded. | |
1123 | * | |
1124 | * More verbose and detailed description of both problem btf_dedup is solving, | |
1125 | * as well as solution could be found at: | |
1126 | * https://facebookmicrosites.github.io/bpf/blog/2018/11/14/btf-enhancement.html | |
1127 | * | |
1128 | * Problem description and justification | |
1129 | * ===================================== | |
1130 | * | |
1131 | * BTF type information is typically emitted either as a result of conversion | |
1132 | * from DWARF to BTF or directly by compiler. In both cases, each compilation | |
1133 | * unit contains information about a subset of all the types that are used | |
1134 | * in an application. These subsets are frequently overlapping and contain a lot | |
1135 | * of duplicated information when later concatenated together into a single | |
1136 | * binary. This algorithm ensures that each unique type is represented by single | |
1137 | * BTF type descriptor, greatly reducing resulting size of BTF data. | |
1138 | * | |
1139 | * Compilation unit isolation and subsequent duplication of data is not the only | |
1140 | * problem. The same type hierarchy (e.g., struct and all the type that struct | |
1141 | * references) in different compilation units can be represented in BTF to | |
1142 | * various degrees of completeness (or, rather, incompleteness) due to | |
1143 | * struct/union forward declarations. | |
1144 | * | |
1145 | * Let's take a look at an example, that we'll use to better understand the | |
1146 | * problem (and solution). Suppose we have two compilation units, each using | |
1147 | * same `struct S`, but each of them having incomplete type information about | |
1148 | * struct's fields: | |
1149 | * | |
1150 | * // CU #1: | |
1151 | * struct S; | |
1152 | * struct A { | |
1153 | * int a; | |
1154 | * struct A* self; | |
1155 | * struct S* parent; | |
1156 | * }; | |
1157 | * struct B; | |
1158 | * struct S { | |
1159 | * struct A* a_ptr; | |
1160 | * struct B* b_ptr; | |
1161 | * }; | |
1162 | * | |
1163 | * // CU #2: | |
1164 | * struct S; | |
1165 | * struct A; | |
1166 | * struct B { | |
1167 | * int b; | |
1168 | * struct B* self; | |
1169 | * struct S* parent; | |
1170 | * }; | |
1171 | * struct S { | |
1172 | * struct A* a_ptr; | |
1173 | * struct B* b_ptr; | |
1174 | * }; | |
1175 | * | |
1176 | * In case of CU #1, BTF data will know only that `struct B` exist (but no | |
1177 | * more), but will know the complete type information about `struct A`. While | |
1178 | * for CU #2, it will know full type information about `struct B`, but will | |
1179 | * only know about forward declaration of `struct A` (in BTF terms, it will | |
1180 | * have `BTF_KIND_FWD` type descriptor with name `B`). | |
1181 | * | |
1182 | * This compilation unit isolation means that it's possible that there is no | |
1183 | * single CU with complete type information describing structs `S`, `A`, and | |
1184 | * `B`. Also, we might get tons of duplicated and redundant type information. | |
1185 | * | |
1186 | * Additional complication we need to keep in mind comes from the fact that | |
1187 | * types, in general, can form graphs containing cycles, not just DAGs. | |
1188 | * | |
1189 | * While algorithm does deduplication, it also merges and resolves type | |
1190 | * information (unless disabled throught `struct btf_opts`), whenever possible. | |
1191 | * E.g., in the example above with two compilation units having partial type | |
1192 | * information for structs `A` and `B`, the output of algorithm will emit | |
1193 | * a single copy of each BTF type that describes structs `A`, `B`, and `S` | |
1194 | * (as well as type information for `int` and pointers), as if they were defined | |
1195 | * in a single compilation unit as: | |
1196 | * | |
1197 | * struct A { | |
1198 | * int a; | |
1199 | * struct A* self; | |
1200 | * struct S* parent; | |
1201 | * }; | |
1202 | * struct B { | |
1203 | * int b; | |
1204 | * struct B* self; | |
1205 | * struct S* parent; | |
1206 | * }; | |
1207 | * struct S { | |
1208 | * struct A* a_ptr; | |
1209 | * struct B* b_ptr; | |
1210 | * }; | |
1211 | * | |
1212 | * Algorithm summary | |
1213 | * ================= | |
1214 | * | |
1215 | * Algorithm completes its work in 6 separate passes: | |
1216 | * | |
1217 | * 1. Strings deduplication. | |
1218 | * 2. Primitive types deduplication (int, enum, fwd). | |
1219 | * 3. Struct/union types deduplication. | |
1220 | * 4. Reference types deduplication (pointers, typedefs, arrays, funcs, func | |
1221 | * protos, and const/volatile/restrict modifiers). | |
1222 | * 5. Types compaction. | |
1223 | * 6. Types remapping. | |
1224 | * | |
1225 | * Algorithm determines canonical type descriptor, which is a single | |
1226 | * representative type for each truly unique type. This canonical type is the | |
1227 | * one that will go into final deduplicated BTF type information. For | |
1228 | * struct/unions, it is also the type that algorithm will merge additional type | |
1229 | * information into (while resolving FWDs), as it discovers it from data in | |
1230 | * other CUs. Each input BTF type eventually gets either mapped to itself, if | |
1231 | * that type is canonical, or to some other type, if that type is equivalent | |
1232 | * and was chosen as canonical representative. This mapping is stored in | |
1233 | * `btf_dedup->map` array. This map is also used to record STRUCT/UNION that | |
1234 | * FWD type got resolved to. | |
1235 | * | |
1236 | * To facilitate fast discovery of canonical types, we also maintain canonical | |
1237 | * index (`btf_dedup->dedup_table`), which maps type descriptor's signature hash | |
1238 | * (i.e., hashed kind, name, size, fields, etc) into a list of canonical types | |
1239 | * that match that signature. With sufficiently good choice of type signature | |
1240 | * hashing function, we can limit number of canonical types for each unique type | |
1241 | * signature to a very small number, allowing to find canonical type for any | |
1242 | * duplicated type very quickly. | |
1243 | * | |
1244 | * Struct/union deduplication is the most critical part and algorithm for | |
1245 | * deduplicating structs/unions is described in greater details in comments for | |
1246 | * `btf_dedup_is_equiv` function. | |
1247 | */ | |
1248 | int btf__dedup(struct btf *btf, struct btf_ext *btf_ext, | |
1249 | const struct btf_dedup_opts *opts) | |
1250 | { | |
1251 | struct btf_dedup *d = btf_dedup_new(btf, btf_ext, opts); | |
1252 | int err; | |
1253 | ||
1254 | if (IS_ERR(d)) { | |
1255 | pr_debug("btf_dedup_new failed: %ld", PTR_ERR(d)); | |
1256 | return -EINVAL; | |
1257 | } | |
1258 | ||
1259 | err = btf_dedup_strings(d); | |
1260 | if (err < 0) { | |
1261 | pr_debug("btf_dedup_strings failed:%d\n", err); | |
1262 | goto done; | |
1263 | } | |
1264 | err = btf_dedup_prim_types(d); | |
1265 | if (err < 0) { | |
1266 | pr_debug("btf_dedup_prim_types failed:%d\n", err); | |
1267 | goto done; | |
1268 | } | |
1269 | err = btf_dedup_struct_types(d); | |
1270 | if (err < 0) { | |
1271 | pr_debug("btf_dedup_struct_types failed:%d\n", err); | |
1272 | goto done; | |
1273 | } | |
1274 | err = btf_dedup_ref_types(d); | |
1275 | if (err < 0) { | |
1276 | pr_debug("btf_dedup_ref_types failed:%d\n", err); | |
1277 | goto done; | |
1278 | } | |
1279 | err = btf_dedup_compact_types(d); | |
1280 | if (err < 0) { | |
1281 | pr_debug("btf_dedup_compact_types failed:%d\n", err); | |
1282 | goto done; | |
1283 | } | |
1284 | err = btf_dedup_remap_types(d); | |
1285 | if (err < 0) { | |
1286 | pr_debug("btf_dedup_remap_types failed:%d\n", err); | |
1287 | goto done; | |
1288 | } | |
1289 | ||
1290 | done: | |
1291 | btf_dedup_free(d); | |
1292 | return err; | |
1293 | } | |
1294 | ||
d5caef5b AN |
1295 | #define BTF_UNPROCESSED_ID ((__u32)-1) |
1296 | #define BTF_IN_PROGRESS_ID ((__u32)-2) | |
1297 | ||
d5caef5b AN |
1298 | struct btf_dedup { |
1299 | /* .BTF section to be deduped in-place */ | |
1300 | struct btf *btf; | |
1301 | /* | |
1302 | * Optional .BTF.ext section. When provided, any strings referenced | |
1303 | * from it will be taken into account when deduping strings | |
1304 | */ | |
1305 | struct btf_ext *btf_ext; | |
1306 | /* | |
1307 | * This is a map from any type's signature hash to a list of possible | |
1308 | * canonical representative type candidates. Hash collisions are | |
1309 | * ignored, so even types of various kinds can share same list of | |
1310 | * candidates, which is fine because we rely on subsequent | |
1311 | * btf_xxx_equal() checks to authoritatively verify type equality. | |
1312 | */ | |
2fc3fc0b | 1313 | struct hashmap *dedup_table; |
d5caef5b AN |
1314 | /* Canonical types map */ |
1315 | __u32 *map; | |
1316 | /* Hypothetical mapping, used during type graph equivalence checks */ | |
1317 | __u32 *hypot_map; | |
1318 | __u32 *hypot_list; | |
1319 | size_t hypot_cnt; | |
1320 | size_t hypot_cap; | |
1321 | /* Various option modifying behavior of algorithm */ | |
1322 | struct btf_dedup_opts opts; | |
1323 | }; | |
1324 | ||
1325 | struct btf_str_ptr { | |
1326 | const char *str; | |
1327 | __u32 new_off; | |
1328 | bool used; | |
1329 | }; | |
1330 | ||
1331 | struct btf_str_ptrs { | |
1332 | struct btf_str_ptr *ptrs; | |
1333 | const char *data; | |
1334 | __u32 cnt; | |
1335 | __u32 cap; | |
1336 | }; | |
1337 | ||
2fc3fc0b | 1338 | static long hash_combine(long h, long value) |
d5caef5b | 1339 | { |
2fc3fc0b | 1340 | return h * 31 + value; |
d5caef5b AN |
1341 | } |
1342 | ||
2fc3fc0b AN |
1343 | #define for_each_dedup_cand(d, node, hash) \ |
1344 | hashmap__for_each_key_entry(d->dedup_table, node, (void *)hash) | |
d5caef5b | 1345 | |
2fc3fc0b | 1346 | static int btf_dedup_table_add(struct btf_dedup *d, long hash, __u32 type_id) |
d5caef5b | 1347 | { |
2fc3fc0b AN |
1348 | return hashmap__append(d->dedup_table, |
1349 | (void *)hash, (void *)(long)type_id); | |
d5caef5b AN |
1350 | } |
1351 | ||
1352 | static int btf_dedup_hypot_map_add(struct btf_dedup *d, | |
1353 | __u32 from_id, __u32 to_id) | |
1354 | { | |
1355 | if (d->hypot_cnt == d->hypot_cap) { | |
1356 | __u32 *new_list; | |
1357 | ||
1358 | d->hypot_cap += max(16, d->hypot_cap / 2); | |
1359 | new_list = realloc(d->hypot_list, sizeof(__u32) * d->hypot_cap); | |
1360 | if (!new_list) | |
1361 | return -ENOMEM; | |
1362 | d->hypot_list = new_list; | |
1363 | } | |
1364 | d->hypot_list[d->hypot_cnt++] = from_id; | |
1365 | d->hypot_map[from_id] = to_id; | |
1366 | return 0; | |
1367 | } | |
1368 | ||
1369 | static void btf_dedup_clear_hypot_map(struct btf_dedup *d) | |
1370 | { | |
1371 | int i; | |
1372 | ||
1373 | for (i = 0; i < d->hypot_cnt; i++) | |
1374 | d->hypot_map[d->hypot_list[i]] = BTF_UNPROCESSED_ID; | |
1375 | d->hypot_cnt = 0; | |
1376 | } | |
1377 | ||
d5caef5b AN |
1378 | static void btf_dedup_free(struct btf_dedup *d) |
1379 | { | |
2fc3fc0b AN |
1380 | hashmap__free(d->dedup_table); |
1381 | d->dedup_table = NULL; | |
d5caef5b AN |
1382 | |
1383 | free(d->map); | |
1384 | d->map = NULL; | |
1385 | ||
1386 | free(d->hypot_map); | |
1387 | d->hypot_map = NULL; | |
1388 | ||
1389 | free(d->hypot_list); | |
1390 | d->hypot_list = NULL; | |
1391 | ||
1392 | free(d); | |
1393 | } | |
1394 | ||
2fc3fc0b | 1395 | static size_t btf_dedup_identity_hash_fn(const void *key, void *ctx) |
51edf5f6 | 1396 | { |
2fc3fc0b AN |
1397 | return (size_t)key; |
1398 | } | |
51edf5f6 | 1399 | |
2fc3fc0b AN |
1400 | static size_t btf_dedup_collision_hash_fn(const void *key, void *ctx) |
1401 | { | |
1402 | return 0; | |
51edf5f6 AN |
1403 | } |
1404 | ||
2fc3fc0b AN |
1405 | static bool btf_dedup_equal_fn(const void *k1, const void *k2, void *ctx) |
1406 | { | |
1407 | return k1 == k2; | |
1408 | } | |
51edf5f6 | 1409 | |
d5caef5b AN |
1410 | static struct btf_dedup *btf_dedup_new(struct btf *btf, struct btf_ext *btf_ext, |
1411 | const struct btf_dedup_opts *opts) | |
1412 | { | |
1413 | struct btf_dedup *d = calloc(1, sizeof(struct btf_dedup)); | |
2fc3fc0b | 1414 | hashmap_hash_fn hash_fn = btf_dedup_identity_hash_fn; |
d5caef5b AN |
1415 | int i, err = 0; |
1416 | ||
1417 | if (!d) | |
1418 | return ERR_PTR(-ENOMEM); | |
1419 | ||
51edf5f6 | 1420 | d->opts.dont_resolve_fwds = opts && opts->dont_resolve_fwds; |
2fc3fc0b AN |
1421 | /* dedup_table_size is now used only to force collisions in tests */ |
1422 | if (opts && opts->dedup_table_size == 1) | |
1423 | hash_fn = btf_dedup_collision_hash_fn; | |
51edf5f6 | 1424 | |
d5caef5b AN |
1425 | d->btf = btf; |
1426 | d->btf_ext = btf_ext; | |
1427 | ||
2fc3fc0b AN |
1428 | d->dedup_table = hashmap__new(hash_fn, btf_dedup_equal_fn, NULL); |
1429 | if (IS_ERR(d->dedup_table)) { | |
1430 | err = PTR_ERR(d->dedup_table); | |
1431 | d->dedup_table = NULL; | |
d5caef5b AN |
1432 | goto done; |
1433 | } | |
1434 | ||
1435 | d->map = malloc(sizeof(__u32) * (1 + btf->nr_types)); | |
1436 | if (!d->map) { | |
1437 | err = -ENOMEM; | |
1438 | goto done; | |
1439 | } | |
1440 | /* special BTF "void" type is made canonical immediately */ | |
1441 | d->map[0] = 0; | |
189cf5a4 AN |
1442 | for (i = 1; i <= btf->nr_types; i++) { |
1443 | struct btf_type *t = d->btf->types[i]; | |
1444 | __u16 kind = BTF_INFO_KIND(t->info); | |
1445 | ||
1446 | /* VAR and DATASEC are never deduped and are self-canonical */ | |
1447 | if (kind == BTF_KIND_VAR || kind == BTF_KIND_DATASEC) | |
1448 | d->map[i] = i; | |
1449 | else | |
1450 | d->map[i] = BTF_UNPROCESSED_ID; | |
1451 | } | |
d5caef5b AN |
1452 | |
1453 | d->hypot_map = malloc(sizeof(__u32) * (1 + btf->nr_types)); | |
1454 | if (!d->hypot_map) { | |
1455 | err = -ENOMEM; | |
1456 | goto done; | |
1457 | } | |
1458 | for (i = 0; i <= btf->nr_types; i++) | |
1459 | d->hypot_map[i] = BTF_UNPROCESSED_ID; | |
1460 | ||
d5caef5b AN |
1461 | done: |
1462 | if (err) { | |
1463 | btf_dedup_free(d); | |
1464 | return ERR_PTR(err); | |
1465 | } | |
1466 | ||
1467 | return d; | |
1468 | } | |
1469 | ||
1470 | typedef int (*str_off_fn_t)(__u32 *str_off_ptr, void *ctx); | |
1471 | ||
1472 | /* | |
1473 | * Iterate over all possible places in .BTF and .BTF.ext that can reference | |
1474 | * string and pass pointer to it to a provided callback `fn`. | |
1475 | */ | |
1476 | static int btf_for_each_str_off(struct btf_dedup *d, str_off_fn_t fn, void *ctx) | |
1477 | { | |
1478 | void *line_data_cur, *line_data_end; | |
1479 | int i, j, r, rec_size; | |
1480 | struct btf_type *t; | |
1481 | ||
1482 | for (i = 1; i <= d->btf->nr_types; i++) { | |
1483 | t = d->btf->types[i]; | |
1484 | r = fn(&t->name_off, ctx); | |
1485 | if (r) | |
1486 | return r; | |
1487 | ||
1488 | switch (BTF_INFO_KIND(t->info)) { | |
1489 | case BTF_KIND_STRUCT: | |
1490 | case BTF_KIND_UNION: { | |
1491 | struct btf_member *m = (struct btf_member *)(t + 1); | |
1492 | __u16 vlen = BTF_INFO_VLEN(t->info); | |
1493 | ||
1494 | for (j = 0; j < vlen; j++) { | |
1495 | r = fn(&m->name_off, ctx); | |
1496 | if (r) | |
1497 | return r; | |
1498 | m++; | |
1499 | } | |
1500 | break; | |
1501 | } | |
1502 | case BTF_KIND_ENUM: { | |
1503 | struct btf_enum *m = (struct btf_enum *)(t + 1); | |
1504 | __u16 vlen = BTF_INFO_VLEN(t->info); | |
1505 | ||
1506 | for (j = 0; j < vlen; j++) { | |
1507 | r = fn(&m->name_off, ctx); | |
1508 | if (r) | |
1509 | return r; | |
1510 | m++; | |
1511 | } | |
1512 | break; | |
1513 | } | |
1514 | case BTF_KIND_FUNC_PROTO: { | |
1515 | struct btf_param *m = (struct btf_param *)(t + 1); | |
1516 | __u16 vlen = BTF_INFO_VLEN(t->info); | |
1517 | ||
1518 | for (j = 0; j < vlen; j++) { | |
1519 | r = fn(&m->name_off, ctx); | |
1520 | if (r) | |
1521 | return r; | |
1522 | m++; | |
1523 | } | |
1524 | break; | |
1525 | } | |
1526 | default: | |
1527 | break; | |
1528 | } | |
1529 | } | |
1530 | ||
1531 | if (!d->btf_ext) | |
1532 | return 0; | |
1533 | ||
1534 | line_data_cur = d->btf_ext->line_info.info; | |
1535 | line_data_end = d->btf_ext->line_info.info + d->btf_ext->line_info.len; | |
1536 | rec_size = d->btf_ext->line_info.rec_size; | |
1537 | ||
1538 | while (line_data_cur < line_data_end) { | |
1539 | struct btf_ext_info_sec *sec = line_data_cur; | |
1540 | struct bpf_line_info_min *line_info; | |
1541 | __u32 num_info = sec->num_info; | |
1542 | ||
1543 | r = fn(&sec->sec_name_off, ctx); | |
1544 | if (r) | |
1545 | return r; | |
1546 | ||
1547 | line_data_cur += sizeof(struct btf_ext_info_sec); | |
1548 | for (i = 0; i < num_info; i++) { | |
1549 | line_info = line_data_cur; | |
1550 | r = fn(&line_info->file_name_off, ctx); | |
1551 | if (r) | |
1552 | return r; | |
1553 | r = fn(&line_info->line_off, ctx); | |
1554 | if (r) | |
1555 | return r; | |
1556 | line_data_cur += rec_size; | |
1557 | } | |
1558 | } | |
1559 | ||
1560 | return 0; | |
1561 | } | |
1562 | ||
1563 | static int str_sort_by_content(const void *a1, const void *a2) | |
1564 | { | |
1565 | const struct btf_str_ptr *p1 = a1; | |
1566 | const struct btf_str_ptr *p2 = a2; | |
1567 | ||
1568 | return strcmp(p1->str, p2->str); | |
1569 | } | |
1570 | ||
1571 | static int str_sort_by_offset(const void *a1, const void *a2) | |
1572 | { | |
1573 | const struct btf_str_ptr *p1 = a1; | |
1574 | const struct btf_str_ptr *p2 = a2; | |
1575 | ||
1576 | if (p1->str != p2->str) | |
1577 | return p1->str < p2->str ? -1 : 1; | |
1578 | return 0; | |
1579 | } | |
1580 | ||
1581 | static int btf_dedup_str_ptr_cmp(const void *str_ptr, const void *pelem) | |
1582 | { | |
1583 | const struct btf_str_ptr *p = pelem; | |
1584 | ||
1585 | if (str_ptr != p->str) | |
1586 | return (const char *)str_ptr < p->str ? -1 : 1; | |
1587 | return 0; | |
1588 | } | |
1589 | ||
1590 | static int btf_str_mark_as_used(__u32 *str_off_ptr, void *ctx) | |
1591 | { | |
1592 | struct btf_str_ptrs *strs; | |
1593 | struct btf_str_ptr *s; | |
1594 | ||
1595 | if (*str_off_ptr == 0) | |
1596 | return 0; | |
1597 | ||
1598 | strs = ctx; | |
1599 | s = bsearch(strs->data + *str_off_ptr, strs->ptrs, strs->cnt, | |
1600 | sizeof(struct btf_str_ptr), btf_dedup_str_ptr_cmp); | |
1601 | if (!s) | |
1602 | return -EINVAL; | |
1603 | s->used = true; | |
1604 | return 0; | |
1605 | } | |
1606 | ||
1607 | static int btf_str_remap_offset(__u32 *str_off_ptr, void *ctx) | |
1608 | { | |
1609 | struct btf_str_ptrs *strs; | |
1610 | struct btf_str_ptr *s; | |
1611 | ||
1612 | if (*str_off_ptr == 0) | |
1613 | return 0; | |
1614 | ||
1615 | strs = ctx; | |
1616 | s = bsearch(strs->data + *str_off_ptr, strs->ptrs, strs->cnt, | |
1617 | sizeof(struct btf_str_ptr), btf_dedup_str_ptr_cmp); | |
1618 | if (!s) | |
1619 | return -EINVAL; | |
1620 | *str_off_ptr = s->new_off; | |
1621 | return 0; | |
1622 | } | |
1623 | ||
1624 | /* | |
1625 | * Dedup string and filter out those that are not referenced from either .BTF | |
1626 | * or .BTF.ext (if provided) sections. | |
1627 | * | |
1628 | * This is done by building index of all strings in BTF's string section, | |
1629 | * then iterating over all entities that can reference strings (e.g., type | |
1630 | * names, struct field names, .BTF.ext line info, etc) and marking corresponding | |
1631 | * strings as used. After that all used strings are deduped and compacted into | |
1632 | * sequential blob of memory and new offsets are calculated. Then all the string | |
1633 | * references are iterated again and rewritten using new offsets. | |
1634 | */ | |
1635 | static int btf_dedup_strings(struct btf_dedup *d) | |
1636 | { | |
1637 | const struct btf_header *hdr = d->btf->hdr; | |
1638 | char *start = (char *)d->btf->nohdr_data + hdr->str_off; | |
1639 | char *end = start + d->btf->hdr->str_len; | |
1640 | char *p = start, *tmp_strs = NULL; | |
1641 | struct btf_str_ptrs strs = { | |
1642 | .cnt = 0, | |
1643 | .cap = 0, | |
1644 | .ptrs = NULL, | |
1645 | .data = start, | |
1646 | }; | |
1647 | int i, j, err = 0, grp_idx; | |
1648 | bool grp_used; | |
1649 | ||
1650 | /* build index of all strings */ | |
1651 | while (p < end) { | |
1652 | if (strs.cnt + 1 > strs.cap) { | |
1653 | struct btf_str_ptr *new_ptrs; | |
1654 | ||
1655 | strs.cap += max(strs.cnt / 2, 16); | |
1656 | new_ptrs = realloc(strs.ptrs, | |
1657 | sizeof(strs.ptrs[0]) * strs.cap); | |
1658 | if (!new_ptrs) { | |
1659 | err = -ENOMEM; | |
1660 | goto done; | |
1661 | } | |
1662 | strs.ptrs = new_ptrs; | |
1663 | } | |
1664 | ||
1665 | strs.ptrs[strs.cnt].str = p; | |
1666 | strs.ptrs[strs.cnt].used = false; | |
1667 | ||
1668 | p += strlen(p) + 1; | |
1669 | strs.cnt++; | |
1670 | } | |
1671 | ||
1672 | /* temporary storage for deduplicated strings */ | |
1673 | tmp_strs = malloc(d->btf->hdr->str_len); | |
1674 | if (!tmp_strs) { | |
1675 | err = -ENOMEM; | |
1676 | goto done; | |
1677 | } | |
1678 | ||
1679 | /* mark all used strings */ | |
1680 | strs.ptrs[0].used = true; | |
1681 | err = btf_for_each_str_off(d, btf_str_mark_as_used, &strs); | |
1682 | if (err) | |
1683 | goto done; | |
1684 | ||
1685 | /* sort strings by context, so that we can identify duplicates */ | |
1686 | qsort(strs.ptrs, strs.cnt, sizeof(strs.ptrs[0]), str_sort_by_content); | |
1687 | ||
1688 | /* | |
1689 | * iterate groups of equal strings and if any instance in a group was | |
1690 | * referenced, emit single instance and remember new offset | |
1691 | */ | |
1692 | p = tmp_strs; | |
1693 | grp_idx = 0; | |
1694 | grp_used = strs.ptrs[0].used; | |
1695 | /* iterate past end to avoid code duplication after loop */ | |
1696 | for (i = 1; i <= strs.cnt; i++) { | |
1697 | /* | |
1698 | * when i == strs.cnt, we want to skip string comparison and go | |
1699 | * straight to handling last group of strings (otherwise we'd | |
1700 | * need to handle last group after the loop w/ duplicated code) | |
1701 | */ | |
1702 | if (i < strs.cnt && | |
1703 | !strcmp(strs.ptrs[i].str, strs.ptrs[grp_idx].str)) { | |
1704 | grp_used = grp_used || strs.ptrs[i].used; | |
1705 | continue; | |
1706 | } | |
1707 | ||
1708 | /* | |
1709 | * this check would have been required after the loop to handle | |
1710 | * last group of strings, but due to <= condition in a loop | |
1711 | * we avoid that duplication | |
1712 | */ | |
1713 | if (grp_used) { | |
1714 | int new_off = p - tmp_strs; | |
1715 | __u32 len = strlen(strs.ptrs[grp_idx].str); | |
1716 | ||
1717 | memmove(p, strs.ptrs[grp_idx].str, len + 1); | |
1718 | for (j = grp_idx; j < i; j++) | |
1719 | strs.ptrs[j].new_off = new_off; | |
1720 | p += len + 1; | |
1721 | } | |
1722 | ||
1723 | if (i < strs.cnt) { | |
1724 | grp_idx = i; | |
1725 | grp_used = strs.ptrs[i].used; | |
1726 | } | |
1727 | } | |
1728 | ||
1729 | /* replace original strings with deduped ones */ | |
1730 | d->btf->hdr->str_len = p - tmp_strs; | |
1731 | memmove(start, tmp_strs, d->btf->hdr->str_len); | |
1732 | end = start + d->btf->hdr->str_len; | |
1733 | ||
1734 | /* restore original order for further binary search lookups */ | |
1735 | qsort(strs.ptrs, strs.cnt, sizeof(strs.ptrs[0]), str_sort_by_offset); | |
1736 | ||
1737 | /* remap string offsets */ | |
1738 | err = btf_for_each_str_off(d, btf_str_remap_offset, &strs); | |
1739 | if (err) | |
1740 | goto done; | |
1741 | ||
1742 | d->btf->hdr->str_len = end - start; | |
1743 | ||
1744 | done: | |
1745 | free(tmp_strs); | |
1746 | free(strs.ptrs); | |
1747 | return err; | |
1748 | } | |
1749 | ||
2fc3fc0b | 1750 | static long btf_hash_common(struct btf_type *t) |
d5caef5b | 1751 | { |
2fc3fc0b | 1752 | long h; |
d5caef5b AN |
1753 | |
1754 | h = hash_combine(0, t->name_off); | |
1755 | h = hash_combine(h, t->info); | |
1756 | h = hash_combine(h, t->size); | |
1757 | return h; | |
1758 | } | |
1759 | ||
1760 | static bool btf_equal_common(struct btf_type *t1, struct btf_type *t2) | |
1761 | { | |
1762 | return t1->name_off == t2->name_off && | |
1763 | t1->info == t2->info && | |
1764 | t1->size == t2->size; | |
1765 | } | |
1766 | ||
1767 | /* Calculate type signature hash of INT. */ | |
2fc3fc0b | 1768 | static long btf_hash_int(struct btf_type *t) |
d5caef5b AN |
1769 | { |
1770 | __u32 info = *(__u32 *)(t + 1); | |
2fc3fc0b | 1771 | long h; |
d5caef5b AN |
1772 | |
1773 | h = btf_hash_common(t); | |
1774 | h = hash_combine(h, info); | |
1775 | return h; | |
1776 | } | |
1777 | ||
1778 | /* Check structural equality of two INTs. */ | |
1779 | static bool btf_equal_int(struct btf_type *t1, struct btf_type *t2) | |
1780 | { | |
1781 | __u32 info1, info2; | |
1782 | ||
1783 | if (!btf_equal_common(t1, t2)) | |
1784 | return false; | |
1785 | info1 = *(__u32 *)(t1 + 1); | |
1786 | info2 = *(__u32 *)(t2 + 1); | |
1787 | return info1 == info2; | |
1788 | } | |
1789 | ||
1790 | /* Calculate type signature hash of ENUM. */ | |
2fc3fc0b | 1791 | static long btf_hash_enum(struct btf_type *t) |
d5caef5b | 1792 | { |
2fc3fc0b | 1793 | long h; |
d5caef5b | 1794 | |
9768095b AN |
1795 | /* don't hash vlen and enum members to support enum fwd resolving */ |
1796 | h = hash_combine(0, t->name_off); | |
1797 | h = hash_combine(h, t->info & ~0xffff); | |
1798 | h = hash_combine(h, t->size); | |
d5caef5b AN |
1799 | return h; |
1800 | } | |
1801 | ||
1802 | /* Check structural equality of two ENUMs. */ | |
1803 | static bool btf_equal_enum(struct btf_type *t1, struct btf_type *t2) | |
1804 | { | |
1805 | struct btf_enum *m1, *m2; | |
1806 | __u16 vlen; | |
1807 | int i; | |
1808 | ||
1809 | if (!btf_equal_common(t1, t2)) | |
1810 | return false; | |
1811 | ||
1812 | vlen = BTF_INFO_VLEN(t1->info); | |
1813 | m1 = (struct btf_enum *)(t1 + 1); | |
1814 | m2 = (struct btf_enum *)(t2 + 1); | |
1815 | for (i = 0; i < vlen; i++) { | |
1816 | if (m1->name_off != m2->name_off || m1->val != m2->val) | |
1817 | return false; | |
1818 | m1++; | |
1819 | m2++; | |
1820 | } | |
1821 | return true; | |
1822 | } | |
1823 | ||
9768095b AN |
1824 | static inline bool btf_is_enum_fwd(struct btf_type *t) |
1825 | { | |
1826 | return BTF_INFO_KIND(t->info) == BTF_KIND_ENUM && | |
1827 | BTF_INFO_VLEN(t->info) == 0; | |
1828 | } | |
1829 | ||
1830 | static bool btf_compat_enum(struct btf_type *t1, struct btf_type *t2) | |
1831 | { | |
1832 | if (!btf_is_enum_fwd(t1) && !btf_is_enum_fwd(t2)) | |
1833 | return btf_equal_enum(t1, t2); | |
1834 | /* ignore vlen when comparing */ | |
1835 | return t1->name_off == t2->name_off && | |
1836 | (t1->info & ~0xffff) == (t2->info & ~0xffff) && | |
1837 | t1->size == t2->size; | |
1838 | } | |
1839 | ||
d5caef5b AN |
1840 | /* |
1841 | * Calculate type signature hash of STRUCT/UNION, ignoring referenced type IDs, | |
1842 | * as referenced type IDs equivalence is established separately during type | |
1843 | * graph equivalence check algorithm. | |
1844 | */ | |
2fc3fc0b | 1845 | static long btf_hash_struct(struct btf_type *t) |
d5caef5b AN |
1846 | { |
1847 | struct btf_member *member = (struct btf_member *)(t + 1); | |
1848 | __u32 vlen = BTF_INFO_VLEN(t->info); | |
2fc3fc0b | 1849 | long h = btf_hash_common(t); |
d5caef5b AN |
1850 | int i; |
1851 | ||
1852 | for (i = 0; i < vlen; i++) { | |
1853 | h = hash_combine(h, member->name_off); | |
1854 | h = hash_combine(h, member->offset); | |
1855 | /* no hashing of referenced type ID, it can be unresolved yet */ | |
1856 | member++; | |
1857 | } | |
1858 | return h; | |
1859 | } | |
1860 | ||
1861 | /* | |
1862 | * Check structural compatibility of two FUNC_PROTOs, ignoring referenced type | |
1863 | * IDs. This check is performed during type graph equivalence check and | |
1864 | * referenced types equivalence is checked separately. | |
1865 | */ | |
91097fbe | 1866 | static bool btf_shallow_equal_struct(struct btf_type *t1, struct btf_type *t2) |
d5caef5b AN |
1867 | { |
1868 | struct btf_member *m1, *m2; | |
1869 | __u16 vlen; | |
1870 | int i; | |
1871 | ||
1872 | if (!btf_equal_common(t1, t2)) | |
1873 | return false; | |
1874 | ||
1875 | vlen = BTF_INFO_VLEN(t1->info); | |
1876 | m1 = (struct btf_member *)(t1 + 1); | |
1877 | m2 = (struct btf_member *)(t2 + 1); | |
1878 | for (i = 0; i < vlen; i++) { | |
1879 | if (m1->name_off != m2->name_off || m1->offset != m2->offset) | |
1880 | return false; | |
1881 | m1++; | |
1882 | m2++; | |
1883 | } | |
1884 | return true; | |
1885 | } | |
1886 | ||
1887 | /* | |
1888 | * Calculate type signature hash of ARRAY, including referenced type IDs, | |
1889 | * under assumption that they were already resolved to canonical type IDs and | |
1890 | * are not going to change. | |
1891 | */ | |
2fc3fc0b | 1892 | static long btf_hash_array(struct btf_type *t) |
d5caef5b AN |
1893 | { |
1894 | struct btf_array *info = (struct btf_array *)(t + 1); | |
2fc3fc0b | 1895 | long h = btf_hash_common(t); |
d5caef5b AN |
1896 | |
1897 | h = hash_combine(h, info->type); | |
1898 | h = hash_combine(h, info->index_type); | |
1899 | h = hash_combine(h, info->nelems); | |
1900 | return h; | |
1901 | } | |
1902 | ||
1903 | /* | |
1904 | * Check exact equality of two ARRAYs, taking into account referenced | |
1905 | * type IDs, under assumption that they were already resolved to canonical | |
1906 | * type IDs and are not going to change. | |
1907 | * This function is called during reference types deduplication to compare | |
1908 | * ARRAY to potential canonical representative. | |
1909 | */ | |
1910 | static bool btf_equal_array(struct btf_type *t1, struct btf_type *t2) | |
1911 | { | |
1912 | struct btf_array *info1, *info2; | |
1913 | ||
1914 | if (!btf_equal_common(t1, t2)) | |
1915 | return false; | |
1916 | ||
1917 | info1 = (struct btf_array *)(t1 + 1); | |
1918 | info2 = (struct btf_array *)(t2 + 1); | |
1919 | return info1->type == info2->type && | |
1920 | info1->index_type == info2->index_type && | |
1921 | info1->nelems == info2->nelems; | |
1922 | } | |
1923 | ||
1924 | /* | |
1925 | * Check structural compatibility of two ARRAYs, ignoring referenced type | |
1926 | * IDs. This check is performed during type graph equivalence check and | |
1927 | * referenced types equivalence is checked separately. | |
1928 | */ | |
1929 | static bool btf_compat_array(struct btf_type *t1, struct btf_type *t2) | |
1930 | { | |
1931 | struct btf_array *info1, *info2; | |
1932 | ||
1933 | if (!btf_equal_common(t1, t2)) | |
1934 | return false; | |
1935 | ||
1936 | info1 = (struct btf_array *)(t1 + 1); | |
1937 | info2 = (struct btf_array *)(t2 + 1); | |
1938 | return info1->nelems == info2->nelems; | |
1939 | } | |
1940 | ||
1941 | /* | |
1942 | * Calculate type signature hash of FUNC_PROTO, including referenced type IDs, | |
1943 | * under assumption that they were already resolved to canonical type IDs and | |
1944 | * are not going to change. | |
1945 | */ | |
2fc3fc0b | 1946 | static long btf_hash_fnproto(struct btf_type *t) |
d5caef5b AN |
1947 | { |
1948 | struct btf_param *member = (struct btf_param *)(t + 1); | |
1949 | __u16 vlen = BTF_INFO_VLEN(t->info); | |
2fc3fc0b | 1950 | long h = btf_hash_common(t); |
d5caef5b AN |
1951 | int i; |
1952 | ||
1953 | for (i = 0; i < vlen; i++) { | |
1954 | h = hash_combine(h, member->name_off); | |
1955 | h = hash_combine(h, member->type); | |
1956 | member++; | |
1957 | } | |
1958 | return h; | |
1959 | } | |
1960 | ||
1961 | /* | |
1962 | * Check exact equality of two FUNC_PROTOs, taking into account referenced | |
1963 | * type IDs, under assumption that they were already resolved to canonical | |
1964 | * type IDs and are not going to change. | |
1965 | * This function is called during reference types deduplication to compare | |
1966 | * FUNC_PROTO to potential canonical representative. | |
1967 | */ | |
2fc3fc0b | 1968 | static bool btf_equal_fnproto(struct btf_type *t1, struct btf_type *t2) |
d5caef5b AN |
1969 | { |
1970 | struct btf_param *m1, *m2; | |
1971 | __u16 vlen; | |
1972 | int i; | |
1973 | ||
1974 | if (!btf_equal_common(t1, t2)) | |
1975 | return false; | |
1976 | ||
1977 | vlen = BTF_INFO_VLEN(t1->info); | |
1978 | m1 = (struct btf_param *)(t1 + 1); | |
1979 | m2 = (struct btf_param *)(t2 + 1); | |
1980 | for (i = 0; i < vlen; i++) { | |
1981 | if (m1->name_off != m2->name_off || m1->type != m2->type) | |
1982 | return false; | |
1983 | m1++; | |
1984 | m2++; | |
1985 | } | |
1986 | return true; | |
1987 | } | |
1988 | ||
1989 | /* | |
1990 | * Check structural compatibility of two FUNC_PROTOs, ignoring referenced type | |
1991 | * IDs. This check is performed during type graph equivalence check and | |
1992 | * referenced types equivalence is checked separately. | |
1993 | */ | |
2fc3fc0b | 1994 | static bool btf_compat_fnproto(struct btf_type *t1, struct btf_type *t2) |
d5caef5b AN |
1995 | { |
1996 | struct btf_param *m1, *m2; | |
1997 | __u16 vlen; | |
1998 | int i; | |
1999 | ||
2000 | /* skip return type ID */ | |
2001 | if (t1->name_off != t2->name_off || t1->info != t2->info) | |
2002 | return false; | |
2003 | ||
2004 | vlen = BTF_INFO_VLEN(t1->info); | |
2005 | m1 = (struct btf_param *)(t1 + 1); | |
2006 | m2 = (struct btf_param *)(t2 + 1); | |
2007 | for (i = 0; i < vlen; i++) { | |
2008 | if (m1->name_off != m2->name_off) | |
2009 | return false; | |
2010 | m1++; | |
2011 | m2++; | |
2012 | } | |
2013 | return true; | |
2014 | } | |
2015 | ||
2016 | /* | |
2017 | * Deduplicate primitive types, that can't reference other types, by calculating | |
2018 | * their type signature hash and comparing them with any possible canonical | |
2019 | * candidate. If no canonical candidate matches, type itself is marked as | |
2020 | * canonical and is added into `btf_dedup->dedup_table` as another candidate. | |
2021 | */ | |
2022 | static int btf_dedup_prim_type(struct btf_dedup *d, __u32 type_id) | |
2023 | { | |
2024 | struct btf_type *t = d->btf->types[type_id]; | |
2fc3fc0b | 2025 | struct hashmap_entry *hash_entry; |
d5caef5b | 2026 | struct btf_type *cand; |
d5caef5b AN |
2027 | /* if we don't find equivalent type, then we are canonical */ |
2028 | __u32 new_id = type_id; | |
2fc3fc0b AN |
2029 | __u32 cand_id; |
2030 | long h; | |
d5caef5b AN |
2031 | |
2032 | switch (BTF_INFO_KIND(t->info)) { | |
2033 | case BTF_KIND_CONST: | |
2034 | case BTF_KIND_VOLATILE: | |
2035 | case BTF_KIND_RESTRICT: | |
2036 | case BTF_KIND_PTR: | |
2037 | case BTF_KIND_TYPEDEF: | |
2038 | case BTF_KIND_ARRAY: | |
2039 | case BTF_KIND_STRUCT: | |
2040 | case BTF_KIND_UNION: | |
2041 | case BTF_KIND_FUNC: | |
2042 | case BTF_KIND_FUNC_PROTO: | |
189cf5a4 AN |
2043 | case BTF_KIND_VAR: |
2044 | case BTF_KIND_DATASEC: | |
d5caef5b AN |
2045 | return 0; |
2046 | ||
2047 | case BTF_KIND_INT: | |
2048 | h = btf_hash_int(t); | |
2fc3fc0b AN |
2049 | for_each_dedup_cand(d, hash_entry, h) { |
2050 | cand_id = (__u32)(long)hash_entry->value; | |
2051 | cand = d->btf->types[cand_id]; | |
d5caef5b | 2052 | if (btf_equal_int(t, cand)) { |
2fc3fc0b | 2053 | new_id = cand_id; |
d5caef5b AN |
2054 | break; |
2055 | } | |
2056 | } | |
2057 | break; | |
2058 | ||
2059 | case BTF_KIND_ENUM: | |
2060 | h = btf_hash_enum(t); | |
2fc3fc0b AN |
2061 | for_each_dedup_cand(d, hash_entry, h) { |
2062 | cand_id = (__u32)(long)hash_entry->value; | |
2063 | cand = d->btf->types[cand_id]; | |
d5caef5b | 2064 | if (btf_equal_enum(t, cand)) { |
2fc3fc0b | 2065 | new_id = cand_id; |
d5caef5b AN |
2066 | break; |
2067 | } | |
9768095b AN |
2068 | if (d->opts.dont_resolve_fwds) |
2069 | continue; | |
2070 | if (btf_compat_enum(t, cand)) { | |
2071 | if (btf_is_enum_fwd(t)) { | |
2072 | /* resolve fwd to full enum */ | |
2fc3fc0b | 2073 | new_id = cand_id; |
9768095b AN |
2074 | break; |
2075 | } | |
2076 | /* resolve canonical enum fwd to full enum */ | |
2fc3fc0b | 2077 | d->map[cand_id] = type_id; |
9768095b | 2078 | } |
d5caef5b AN |
2079 | } |
2080 | break; | |
2081 | ||
2082 | case BTF_KIND_FWD: | |
2083 | h = btf_hash_common(t); | |
2fc3fc0b AN |
2084 | for_each_dedup_cand(d, hash_entry, h) { |
2085 | cand_id = (__u32)(long)hash_entry->value; | |
2086 | cand = d->btf->types[cand_id]; | |
d5caef5b | 2087 | if (btf_equal_common(t, cand)) { |
2fc3fc0b | 2088 | new_id = cand_id; |
d5caef5b AN |
2089 | break; |
2090 | } | |
2091 | } | |
2092 | break; | |
2093 | ||
2094 | default: | |
2095 | return -EINVAL; | |
2096 | } | |
2097 | ||
2098 | d->map[type_id] = new_id; | |
2099 | if (type_id == new_id && btf_dedup_table_add(d, h, type_id)) | |
2100 | return -ENOMEM; | |
2101 | ||
2102 | return 0; | |
2103 | } | |
2104 | ||
2105 | static int btf_dedup_prim_types(struct btf_dedup *d) | |
2106 | { | |
2107 | int i, err; | |
2108 | ||
2109 | for (i = 1; i <= d->btf->nr_types; i++) { | |
2110 | err = btf_dedup_prim_type(d, i); | |
2111 | if (err) | |
2112 | return err; | |
2113 | } | |
2114 | return 0; | |
2115 | } | |
2116 | ||
2117 | /* | |
2118 | * Check whether type is already mapped into canonical one (could be to itself). | |
2119 | */ | |
2120 | static inline bool is_type_mapped(struct btf_dedup *d, uint32_t type_id) | |
2121 | { | |
5aab392c | 2122 | return d->map[type_id] <= BTF_MAX_NR_TYPES; |
d5caef5b AN |
2123 | } |
2124 | ||
2125 | /* | |
2126 | * Resolve type ID into its canonical type ID, if any; otherwise return original | |
2127 | * type ID. If type is FWD and is resolved into STRUCT/UNION already, follow | |
2128 | * STRUCT/UNION link and resolve it into canonical type ID as well. | |
2129 | */ | |
2130 | static inline __u32 resolve_type_id(struct btf_dedup *d, __u32 type_id) | |
2131 | { | |
2132 | while (is_type_mapped(d, type_id) && d->map[type_id] != type_id) | |
2133 | type_id = d->map[type_id]; | |
2134 | return type_id; | |
2135 | } | |
2136 | ||
2137 | /* | |
2138 | * Resolve FWD to underlying STRUCT/UNION, if any; otherwise return original | |
2139 | * type ID. | |
2140 | */ | |
2141 | static uint32_t resolve_fwd_id(struct btf_dedup *d, uint32_t type_id) | |
2142 | { | |
2143 | __u32 orig_type_id = type_id; | |
2144 | ||
2145 | if (BTF_INFO_KIND(d->btf->types[type_id]->info) != BTF_KIND_FWD) | |
2146 | return type_id; | |
2147 | ||
2148 | while (is_type_mapped(d, type_id) && d->map[type_id] != type_id) | |
2149 | type_id = d->map[type_id]; | |
2150 | ||
2151 | if (BTF_INFO_KIND(d->btf->types[type_id]->info) != BTF_KIND_FWD) | |
2152 | return type_id; | |
2153 | ||
2154 | return orig_type_id; | |
2155 | } | |
2156 | ||
2157 | ||
2158 | static inline __u16 btf_fwd_kind(struct btf_type *t) | |
2159 | { | |
2160 | return BTF_INFO_KFLAG(t->info) ? BTF_KIND_UNION : BTF_KIND_STRUCT; | |
2161 | } | |
2162 | ||
2163 | /* | |
2164 | * Check equivalence of BTF type graph formed by candidate struct/union (we'll | |
2165 | * call it "candidate graph" in this description for brevity) to a type graph | |
2166 | * formed by (potential) canonical struct/union ("canonical graph" for brevity | |
2167 | * here, though keep in mind that not all types in canonical graph are | |
2168 | * necessarily canonical representatives themselves, some of them might be | |
2169 | * duplicates or its uniqueness might not have been established yet). | |
2170 | * Returns: | |
2171 | * - >0, if type graphs are equivalent; | |
2172 | * - 0, if not equivalent; | |
2173 | * - <0, on error. | |
2174 | * | |
2175 | * Algorithm performs side-by-side DFS traversal of both type graphs and checks | |
2176 | * equivalence of BTF types at each step. If at any point BTF types in candidate | |
2177 | * and canonical graphs are not compatible structurally, whole graphs are | |
2178 | * incompatible. If types are structurally equivalent (i.e., all information | |
2179 | * except referenced type IDs is exactly the same), a mapping from `canon_id` to | |
2180 | * a `cand_id` is recored in hypothetical mapping (`btf_dedup->hypot_map`). | |
2181 | * If a type references other types, then those referenced types are checked | |
2182 | * for equivalence recursively. | |
2183 | * | |
2184 | * During DFS traversal, if we find that for current `canon_id` type we | |
2185 | * already have some mapping in hypothetical map, we check for two possible | |
2186 | * situations: | |
2187 | * - `canon_id` is mapped to exactly the same type as `cand_id`. This will | |
2188 | * happen when type graphs have cycles. In this case we assume those two | |
2189 | * types are equivalent. | |
2190 | * - `canon_id` is mapped to different type. This is contradiction in our | |
2191 | * hypothetical mapping, because same graph in canonical graph corresponds | |
2192 | * to two different types in candidate graph, which for equivalent type | |
2193 | * graphs shouldn't happen. This condition terminates equivalence check | |
2194 | * with negative result. | |
2195 | * | |
2196 | * If type graphs traversal exhausts types to check and find no contradiction, | |
2197 | * then type graphs are equivalent. | |
2198 | * | |
2199 | * When checking types for equivalence, there is one special case: FWD types. | |
2200 | * If FWD type resolution is allowed and one of the types (either from canonical | |
2201 | * or candidate graph) is FWD and other is STRUCT/UNION (depending on FWD's kind | |
2202 | * flag) and their names match, hypothetical mapping is updated to point from | |
2203 | * FWD to STRUCT/UNION. If graphs will be determined as equivalent successfully, | |
2204 | * this mapping will be used to record FWD -> STRUCT/UNION mapping permanently. | |
2205 | * | |
2206 | * Technically, this could lead to incorrect FWD to STRUCT/UNION resolution, | |
2207 | * if there are two exactly named (or anonymous) structs/unions that are | |
2208 | * compatible structurally, one of which has FWD field, while other is concrete | |
2209 | * STRUCT/UNION, but according to C sources they are different structs/unions | |
2210 | * that are referencing different types with the same name. This is extremely | |
2211 | * unlikely to happen, but btf_dedup API allows to disable FWD resolution if | |
2212 | * this logic is causing problems. | |
2213 | * | |
2214 | * Doing FWD resolution means that both candidate and/or canonical graphs can | |
2215 | * consists of portions of the graph that come from multiple compilation units. | |
2216 | * This is due to the fact that types within single compilation unit are always | |
2217 | * deduplicated and FWDs are already resolved, if referenced struct/union | |
2218 | * definiton is available. So, if we had unresolved FWD and found corresponding | |
2219 | * STRUCT/UNION, they will be from different compilation units. This | |
2220 | * consequently means that when we "link" FWD to corresponding STRUCT/UNION, | |
2221 | * type graph will likely have at least two different BTF types that describe | |
2222 | * same type (e.g., most probably there will be two different BTF types for the | |
2223 | * same 'int' primitive type) and could even have "overlapping" parts of type | |
2224 | * graph that describe same subset of types. | |
2225 | * | |
2226 | * This in turn means that our assumption that each type in canonical graph | |
2227 | * must correspond to exactly one type in candidate graph might not hold | |
2228 | * anymore and will make it harder to detect contradictions using hypothetical | |
2229 | * map. To handle this problem, we allow to follow FWD -> STRUCT/UNION | |
2230 | * resolution only in canonical graph. FWDs in candidate graphs are never | |
2231 | * resolved. To see why it's OK, let's check all possible situations w.r.t. FWDs | |
2232 | * that can occur: | |
2233 | * - Both types in canonical and candidate graphs are FWDs. If they are | |
2234 | * structurally equivalent, then they can either be both resolved to the | |
2235 | * same STRUCT/UNION or not resolved at all. In both cases they are | |
2236 | * equivalent and there is no need to resolve FWD on candidate side. | |
2237 | * - Both types in canonical and candidate graphs are concrete STRUCT/UNION, | |
2238 | * so nothing to resolve as well, algorithm will check equivalence anyway. | |
2239 | * - Type in canonical graph is FWD, while type in candidate is concrete | |
2240 | * STRUCT/UNION. In this case candidate graph comes from single compilation | |
2241 | * unit, so there is exactly one BTF type for each unique C type. After | |
2242 | * resolving FWD into STRUCT/UNION, there might be more than one BTF type | |
2243 | * in canonical graph mapping to single BTF type in candidate graph, but | |
2244 | * because hypothetical mapping maps from canonical to candidate types, it's | |
2245 | * alright, and we still maintain the property of having single `canon_id` | |
2246 | * mapping to single `cand_id` (there could be two different `canon_id` | |
2247 | * mapped to the same `cand_id`, but it's not contradictory). | |
2248 | * - Type in canonical graph is concrete STRUCT/UNION, while type in candidate | |
2249 | * graph is FWD. In this case we are just going to check compatibility of | |
2250 | * STRUCT/UNION and corresponding FWD, and if they are compatible, we'll | |
2251 | * assume that whatever STRUCT/UNION FWD resolves to must be equivalent to | |
2252 | * a concrete STRUCT/UNION from canonical graph. If the rest of type graphs | |
2253 | * turn out equivalent, we'll re-resolve FWD to concrete STRUCT/UNION from | |
2254 | * canonical graph. | |
2255 | */ | |
2256 | static int btf_dedup_is_equiv(struct btf_dedup *d, __u32 cand_id, | |
2257 | __u32 canon_id) | |
2258 | { | |
2259 | struct btf_type *cand_type; | |
2260 | struct btf_type *canon_type; | |
2261 | __u32 hypot_type_id; | |
2262 | __u16 cand_kind; | |
2263 | __u16 canon_kind; | |
2264 | int i, eq; | |
2265 | ||
2266 | /* if both resolve to the same canonical, they must be equivalent */ | |
2267 | if (resolve_type_id(d, cand_id) == resolve_type_id(d, canon_id)) | |
2268 | return 1; | |
2269 | ||
2270 | canon_id = resolve_fwd_id(d, canon_id); | |
2271 | ||
2272 | hypot_type_id = d->hypot_map[canon_id]; | |
5aab392c | 2273 | if (hypot_type_id <= BTF_MAX_NR_TYPES) |
d5caef5b AN |
2274 | return hypot_type_id == cand_id; |
2275 | ||
2276 | if (btf_dedup_hypot_map_add(d, canon_id, cand_id)) | |
2277 | return -ENOMEM; | |
2278 | ||
2279 | cand_type = d->btf->types[cand_id]; | |
2280 | canon_type = d->btf->types[canon_id]; | |
2281 | cand_kind = BTF_INFO_KIND(cand_type->info); | |
2282 | canon_kind = BTF_INFO_KIND(canon_type->info); | |
2283 | ||
2284 | if (cand_type->name_off != canon_type->name_off) | |
2285 | return 0; | |
2286 | ||
2287 | /* FWD <--> STRUCT/UNION equivalence check, if enabled */ | |
2288 | if (!d->opts.dont_resolve_fwds | |
2289 | && (cand_kind == BTF_KIND_FWD || canon_kind == BTF_KIND_FWD) | |
2290 | && cand_kind != canon_kind) { | |
2291 | __u16 real_kind; | |
2292 | __u16 fwd_kind; | |
2293 | ||
2294 | if (cand_kind == BTF_KIND_FWD) { | |
2295 | real_kind = canon_kind; | |
2296 | fwd_kind = btf_fwd_kind(cand_type); | |
2297 | } else { | |
2298 | real_kind = cand_kind; | |
2299 | fwd_kind = btf_fwd_kind(canon_type); | |
2300 | } | |
2301 | return fwd_kind == real_kind; | |
2302 | } | |
2303 | ||
9ec71c1c AN |
2304 | if (cand_kind != canon_kind) |
2305 | return 0; | |
2306 | ||
d5caef5b AN |
2307 | switch (cand_kind) { |
2308 | case BTF_KIND_INT: | |
2309 | return btf_equal_int(cand_type, canon_type); | |
2310 | ||
2311 | case BTF_KIND_ENUM: | |
9768095b AN |
2312 | if (d->opts.dont_resolve_fwds) |
2313 | return btf_equal_enum(cand_type, canon_type); | |
2314 | else | |
2315 | return btf_compat_enum(cand_type, canon_type); | |
d5caef5b AN |
2316 | |
2317 | case BTF_KIND_FWD: | |
2318 | return btf_equal_common(cand_type, canon_type); | |
2319 | ||
2320 | case BTF_KIND_CONST: | |
2321 | case BTF_KIND_VOLATILE: | |
2322 | case BTF_KIND_RESTRICT: | |
2323 | case BTF_KIND_PTR: | |
2324 | case BTF_KIND_TYPEDEF: | |
2325 | case BTF_KIND_FUNC: | |
9768095b AN |
2326 | if (cand_type->info != canon_type->info) |
2327 | return 0; | |
d5caef5b AN |
2328 | return btf_dedup_is_equiv(d, cand_type->type, canon_type->type); |
2329 | ||
2330 | case BTF_KIND_ARRAY: { | |
2331 | struct btf_array *cand_arr, *canon_arr; | |
2332 | ||
2333 | if (!btf_compat_array(cand_type, canon_type)) | |
2334 | return 0; | |
2335 | cand_arr = (struct btf_array *)(cand_type + 1); | |
2336 | canon_arr = (struct btf_array *)(canon_type + 1); | |
2337 | eq = btf_dedup_is_equiv(d, | |
2338 | cand_arr->index_type, canon_arr->index_type); | |
2339 | if (eq <= 0) | |
2340 | return eq; | |
2341 | return btf_dedup_is_equiv(d, cand_arr->type, canon_arr->type); | |
2342 | } | |
2343 | ||
2344 | case BTF_KIND_STRUCT: | |
2345 | case BTF_KIND_UNION: { | |
2346 | struct btf_member *cand_m, *canon_m; | |
2347 | __u16 vlen; | |
2348 | ||
91097fbe | 2349 | if (!btf_shallow_equal_struct(cand_type, canon_type)) |
d5caef5b AN |
2350 | return 0; |
2351 | vlen = BTF_INFO_VLEN(cand_type->info); | |
2352 | cand_m = (struct btf_member *)(cand_type + 1); | |
2353 | canon_m = (struct btf_member *)(canon_type + 1); | |
2354 | for (i = 0; i < vlen; i++) { | |
2355 | eq = btf_dedup_is_equiv(d, cand_m->type, canon_m->type); | |
2356 | if (eq <= 0) | |
2357 | return eq; | |
2358 | cand_m++; | |
2359 | canon_m++; | |
2360 | } | |
2361 | ||
2362 | return 1; | |
2363 | } | |
2364 | ||
2365 | case BTF_KIND_FUNC_PROTO: { | |
2366 | struct btf_param *cand_p, *canon_p; | |
2367 | __u16 vlen; | |
2368 | ||
2369 | if (!btf_compat_fnproto(cand_type, canon_type)) | |
2370 | return 0; | |
2371 | eq = btf_dedup_is_equiv(d, cand_type->type, canon_type->type); | |
2372 | if (eq <= 0) | |
2373 | return eq; | |
2374 | vlen = BTF_INFO_VLEN(cand_type->info); | |
2375 | cand_p = (struct btf_param *)(cand_type + 1); | |
2376 | canon_p = (struct btf_param *)(canon_type + 1); | |
2377 | for (i = 0; i < vlen; i++) { | |
2378 | eq = btf_dedup_is_equiv(d, cand_p->type, canon_p->type); | |
2379 | if (eq <= 0) | |
2380 | return eq; | |
2381 | cand_p++; | |
2382 | canon_p++; | |
2383 | } | |
2384 | return 1; | |
2385 | } | |
2386 | ||
2387 | default: | |
2388 | return -EINVAL; | |
2389 | } | |
2390 | return 0; | |
2391 | } | |
2392 | ||
2393 | /* | |
2394 | * Use hypothetical mapping, produced by successful type graph equivalence | |
2395 | * check, to augment existing struct/union canonical mapping, where possible. | |
2396 | * | |
2397 | * If BTF_KIND_FWD resolution is allowed, this mapping is also used to record | |
2398 | * FWD -> STRUCT/UNION correspondence as well. FWD resolution is bidirectional: | |
2399 | * it doesn't matter if FWD type was part of canonical graph or candidate one, | |
2400 | * we are recording the mapping anyway. As opposed to carefulness required | |
2401 | * for struct/union correspondence mapping (described below), for FWD resolution | |
2402 | * it's not important, as by the time that FWD type (reference type) will be | |
2403 | * deduplicated all structs/unions will be deduped already anyway. | |
2404 | * | |
2405 | * Recording STRUCT/UNION mapping is purely a performance optimization and is | |
2406 | * not required for correctness. It needs to be done carefully to ensure that | |
2407 | * struct/union from candidate's type graph is not mapped into corresponding | |
2408 | * struct/union from canonical type graph that itself hasn't been resolved into | |
2409 | * canonical representative. The only guarantee we have is that canonical | |
2410 | * struct/union was determined as canonical and that won't change. But any | |
2411 | * types referenced through that struct/union fields could have been not yet | |
2412 | * resolved, so in case like that it's too early to establish any kind of | |
2413 | * correspondence between structs/unions. | |
2414 | * | |
2415 | * No canonical correspondence is derived for primitive types (they are already | |
2416 | * deduplicated completely already anyway) or reference types (they rely on | |
2417 | * stability of struct/union canonical relationship for equivalence checks). | |
2418 | */ | |
2419 | static void btf_dedup_merge_hypot_map(struct btf_dedup *d) | |
2420 | { | |
2421 | __u32 cand_type_id, targ_type_id; | |
2422 | __u16 t_kind, c_kind; | |
2423 | __u32 t_id, c_id; | |
2424 | int i; | |
2425 | ||
2426 | for (i = 0; i < d->hypot_cnt; i++) { | |
2427 | cand_type_id = d->hypot_list[i]; | |
2428 | targ_type_id = d->hypot_map[cand_type_id]; | |
2429 | t_id = resolve_type_id(d, targ_type_id); | |
2430 | c_id = resolve_type_id(d, cand_type_id); | |
2431 | t_kind = BTF_INFO_KIND(d->btf->types[t_id]->info); | |
2432 | c_kind = BTF_INFO_KIND(d->btf->types[c_id]->info); | |
2433 | /* | |
2434 | * Resolve FWD into STRUCT/UNION. | |
2435 | * It's ok to resolve FWD into STRUCT/UNION that's not yet | |
2436 | * mapped to canonical representative (as opposed to | |
2437 | * STRUCT/UNION <--> STRUCT/UNION mapping logic below), because | |
2438 | * eventually that struct is going to be mapped and all resolved | |
2439 | * FWDs will automatically resolve to correct canonical | |
2440 | * representative. This will happen before ref type deduping, | |
2441 | * which critically depends on stability of these mapping. This | |
2442 | * stability is not a requirement for STRUCT/UNION equivalence | |
2443 | * checks, though. | |
2444 | */ | |
2445 | if (t_kind != BTF_KIND_FWD && c_kind == BTF_KIND_FWD) | |
2446 | d->map[c_id] = t_id; | |
2447 | else if (t_kind == BTF_KIND_FWD && c_kind != BTF_KIND_FWD) | |
2448 | d->map[t_id] = c_id; | |
2449 | ||
2450 | if ((t_kind == BTF_KIND_STRUCT || t_kind == BTF_KIND_UNION) && | |
2451 | c_kind != BTF_KIND_FWD && | |
2452 | is_type_mapped(d, c_id) && | |
2453 | !is_type_mapped(d, t_id)) { | |
2454 | /* | |
2455 | * as a perf optimization, we can map struct/union | |
2456 | * that's part of type graph we just verified for | |
2457 | * equivalence. We can do that for struct/union that has | |
2458 | * canonical representative only, though. | |
2459 | */ | |
2460 | d->map[t_id] = c_id; | |
2461 | } | |
2462 | } | |
2463 | } | |
2464 | ||
2465 | /* | |
2466 | * Deduplicate struct/union types. | |
2467 | * | |
2468 | * For each struct/union type its type signature hash is calculated, taking | |
2469 | * into account type's name, size, number, order and names of fields, but | |
2470 | * ignoring type ID's referenced from fields, because they might not be deduped | |
2471 | * completely until after reference types deduplication phase. This type hash | |
2472 | * is used to iterate over all potential canonical types, sharing same hash. | |
2473 | * For each canonical candidate we check whether type graphs that they form | |
2474 | * (through referenced types in fields and so on) are equivalent using algorithm | |
2475 | * implemented in `btf_dedup_is_equiv`. If such equivalence is found and | |
2476 | * BTF_KIND_FWD resolution is allowed, then hypothetical mapping | |
2477 | * (btf_dedup->hypot_map) produced by aforementioned type graph equivalence | |
2478 | * algorithm is used to record FWD -> STRUCT/UNION mapping. It's also used to | |
2479 | * potentially map other structs/unions to their canonical representatives, | |
2480 | * if such relationship hasn't yet been established. This speeds up algorithm | |
2481 | * by eliminating some of the duplicate work. | |
2482 | * | |
2483 | * If no matching canonical representative was found, struct/union is marked | |
2484 | * as canonical for itself and is added into btf_dedup->dedup_table hash map | |
2485 | * for further look ups. | |
2486 | */ | |
2487 | static int btf_dedup_struct_type(struct btf_dedup *d, __u32 type_id) | |
2488 | { | |
91097fbe | 2489 | struct btf_type *cand_type, *t; |
2fc3fc0b | 2490 | struct hashmap_entry *hash_entry; |
d5caef5b AN |
2491 | /* if we don't find equivalent type, then we are canonical */ |
2492 | __u32 new_id = type_id; | |
2493 | __u16 kind; | |
2fc3fc0b | 2494 | long h; |
d5caef5b AN |
2495 | |
2496 | /* already deduped or is in process of deduping (loop detected) */ | |
5aab392c | 2497 | if (d->map[type_id] <= BTF_MAX_NR_TYPES) |
d5caef5b AN |
2498 | return 0; |
2499 | ||
2500 | t = d->btf->types[type_id]; | |
2501 | kind = BTF_INFO_KIND(t->info); | |
2502 | ||
2503 | if (kind != BTF_KIND_STRUCT && kind != BTF_KIND_UNION) | |
2504 | return 0; | |
2505 | ||
2506 | h = btf_hash_struct(t); | |
2fc3fc0b AN |
2507 | for_each_dedup_cand(d, hash_entry, h) { |
2508 | __u32 cand_id = (__u32)(long)hash_entry->value; | |
d5caef5b AN |
2509 | int eq; |
2510 | ||
91097fbe AN |
2511 | /* |
2512 | * Even though btf_dedup_is_equiv() checks for | |
2513 | * btf_shallow_equal_struct() internally when checking two | |
2514 | * structs (unions) for equivalence, we need to guard here | |
2515 | * from picking matching FWD type as a dedup candidate. | |
2516 | * This can happen due to hash collision. In such case just | |
2517 | * relying on btf_dedup_is_equiv() would lead to potentially | |
2518 | * creating a loop (FWD -> STRUCT and STRUCT -> FWD), because | |
2519 | * FWD and compatible STRUCT/UNION are considered equivalent. | |
2520 | */ | |
2fc3fc0b | 2521 | cand_type = d->btf->types[cand_id]; |
91097fbe AN |
2522 | if (!btf_shallow_equal_struct(t, cand_type)) |
2523 | continue; | |
2524 | ||
d5caef5b | 2525 | btf_dedup_clear_hypot_map(d); |
2fc3fc0b | 2526 | eq = btf_dedup_is_equiv(d, type_id, cand_id); |
d5caef5b AN |
2527 | if (eq < 0) |
2528 | return eq; | |
2529 | if (!eq) | |
2530 | continue; | |
2fc3fc0b | 2531 | new_id = cand_id; |
d5caef5b AN |
2532 | btf_dedup_merge_hypot_map(d); |
2533 | break; | |
2534 | } | |
2535 | ||
2536 | d->map[type_id] = new_id; | |
2537 | if (type_id == new_id && btf_dedup_table_add(d, h, type_id)) | |
2538 | return -ENOMEM; | |
2539 | ||
2540 | return 0; | |
2541 | } | |
2542 | ||
2543 | static int btf_dedup_struct_types(struct btf_dedup *d) | |
2544 | { | |
2545 | int i, err; | |
2546 | ||
2547 | for (i = 1; i <= d->btf->nr_types; i++) { | |
2548 | err = btf_dedup_struct_type(d, i); | |
2549 | if (err) | |
2550 | return err; | |
2551 | } | |
2552 | return 0; | |
2553 | } | |
2554 | ||
2555 | /* | |
2556 | * Deduplicate reference type. | |
2557 | * | |
2558 | * Once all primitive and struct/union types got deduplicated, we can easily | |
2559 | * deduplicate all other (reference) BTF types. This is done in two steps: | |
2560 | * | |
2561 | * 1. Resolve all referenced type IDs into their canonical type IDs. This | |
2562 | * resolution can be done either immediately for primitive or struct/union types | |
2563 | * (because they were deduped in previous two phases) or recursively for | |
2564 | * reference types. Recursion will always terminate at either primitive or | |
2565 | * struct/union type, at which point we can "unwind" chain of reference types | |
2566 | * one by one. There is no danger of encountering cycles because in C type | |
2567 | * system the only way to form type cycle is through struct/union, so any chain | |
2568 | * of reference types, even those taking part in a type cycle, will inevitably | |
2569 | * reach struct/union at some point. | |
2570 | * | |
2571 | * 2. Once all referenced type IDs are resolved into canonical ones, BTF type | |
2572 | * becomes "stable", in the sense that no further deduplication will cause | |
2573 | * any changes to it. With that, it's now possible to calculate type's signature | |
2574 | * hash (this time taking into account referenced type IDs) and loop over all | |
2575 | * potential canonical representatives. If no match was found, current type | |
2576 | * will become canonical representative of itself and will be added into | |
2577 | * btf_dedup->dedup_table as another possible canonical representative. | |
2578 | */ | |
2579 | static int btf_dedup_ref_type(struct btf_dedup *d, __u32 type_id) | |
2580 | { | |
2fc3fc0b AN |
2581 | struct hashmap_entry *hash_entry; |
2582 | __u32 new_id = type_id, cand_id; | |
d5caef5b AN |
2583 | struct btf_type *t, *cand; |
2584 | /* if we don't find equivalent type, then we are representative type */ | |
3d8669e6 | 2585 | int ref_type_id; |
2fc3fc0b | 2586 | long h; |
d5caef5b AN |
2587 | |
2588 | if (d->map[type_id] == BTF_IN_PROGRESS_ID) | |
2589 | return -ELOOP; | |
5aab392c | 2590 | if (d->map[type_id] <= BTF_MAX_NR_TYPES) |
d5caef5b AN |
2591 | return resolve_type_id(d, type_id); |
2592 | ||
2593 | t = d->btf->types[type_id]; | |
2594 | d->map[type_id] = BTF_IN_PROGRESS_ID; | |
2595 | ||
2596 | switch (BTF_INFO_KIND(t->info)) { | |
2597 | case BTF_KIND_CONST: | |
2598 | case BTF_KIND_VOLATILE: | |
2599 | case BTF_KIND_RESTRICT: | |
2600 | case BTF_KIND_PTR: | |
2601 | case BTF_KIND_TYPEDEF: | |
2602 | case BTF_KIND_FUNC: | |
2603 | ref_type_id = btf_dedup_ref_type(d, t->type); | |
2604 | if (ref_type_id < 0) | |
2605 | return ref_type_id; | |
2606 | t->type = ref_type_id; | |
2607 | ||
2608 | h = btf_hash_common(t); | |
2fc3fc0b AN |
2609 | for_each_dedup_cand(d, hash_entry, h) { |
2610 | cand_id = (__u32)(long)hash_entry->value; | |
2611 | cand = d->btf->types[cand_id]; | |
d5caef5b | 2612 | if (btf_equal_common(t, cand)) { |
2fc3fc0b | 2613 | new_id = cand_id; |
d5caef5b AN |
2614 | break; |
2615 | } | |
2616 | } | |
2617 | break; | |
2618 | ||
2619 | case BTF_KIND_ARRAY: { | |
2620 | struct btf_array *info = (struct btf_array *)(t + 1); | |
2621 | ||
2622 | ref_type_id = btf_dedup_ref_type(d, info->type); | |
2623 | if (ref_type_id < 0) | |
2624 | return ref_type_id; | |
2625 | info->type = ref_type_id; | |
2626 | ||
2627 | ref_type_id = btf_dedup_ref_type(d, info->index_type); | |
2628 | if (ref_type_id < 0) | |
2629 | return ref_type_id; | |
2630 | info->index_type = ref_type_id; | |
2631 | ||
2632 | h = btf_hash_array(t); | |
2fc3fc0b AN |
2633 | for_each_dedup_cand(d, hash_entry, h) { |
2634 | cand_id = (__u32)(long)hash_entry->value; | |
2635 | cand = d->btf->types[cand_id]; | |
d5caef5b | 2636 | if (btf_equal_array(t, cand)) { |
2fc3fc0b | 2637 | new_id = cand_id; |
d5caef5b AN |
2638 | break; |
2639 | } | |
2640 | } | |
2641 | break; | |
2642 | } | |
2643 | ||
2644 | case BTF_KIND_FUNC_PROTO: { | |
2645 | struct btf_param *param; | |
2646 | __u16 vlen; | |
2647 | int i; | |
2648 | ||
2649 | ref_type_id = btf_dedup_ref_type(d, t->type); | |
2650 | if (ref_type_id < 0) | |
2651 | return ref_type_id; | |
2652 | t->type = ref_type_id; | |
2653 | ||
2654 | vlen = BTF_INFO_VLEN(t->info); | |
2655 | param = (struct btf_param *)(t + 1); | |
2656 | for (i = 0; i < vlen; i++) { | |
2657 | ref_type_id = btf_dedup_ref_type(d, param->type); | |
2658 | if (ref_type_id < 0) | |
2659 | return ref_type_id; | |
2660 | param->type = ref_type_id; | |
2661 | param++; | |
2662 | } | |
2663 | ||
2664 | h = btf_hash_fnproto(t); | |
2fc3fc0b AN |
2665 | for_each_dedup_cand(d, hash_entry, h) { |
2666 | cand_id = (__u32)(long)hash_entry->value; | |
2667 | cand = d->btf->types[cand_id]; | |
d5caef5b | 2668 | if (btf_equal_fnproto(t, cand)) { |
2fc3fc0b | 2669 | new_id = cand_id; |
d5caef5b AN |
2670 | break; |
2671 | } | |
2672 | } | |
2673 | break; | |
2674 | } | |
2675 | ||
2676 | default: | |
2677 | return -EINVAL; | |
2678 | } | |
2679 | ||
2680 | d->map[type_id] = new_id; | |
2681 | if (type_id == new_id && btf_dedup_table_add(d, h, type_id)) | |
2682 | return -ENOMEM; | |
2683 | ||
2684 | return new_id; | |
2685 | } | |
2686 | ||
2687 | static int btf_dedup_ref_types(struct btf_dedup *d) | |
2688 | { | |
2689 | int i, err; | |
2690 | ||
2691 | for (i = 1; i <= d->btf->nr_types; i++) { | |
2692 | err = btf_dedup_ref_type(d, i); | |
2693 | if (err < 0) | |
2694 | return err; | |
2695 | } | |
2fc3fc0b AN |
2696 | /* we won't need d->dedup_table anymore */ |
2697 | hashmap__free(d->dedup_table); | |
2698 | d->dedup_table = NULL; | |
d5caef5b AN |
2699 | return 0; |
2700 | } | |
2701 | ||
2702 | /* | |
2703 | * Compact types. | |
2704 | * | |
2705 | * After we established for each type its corresponding canonical representative | |
2706 | * type, we now can eliminate types that are not canonical and leave only | |
2707 | * canonical ones layed out sequentially in memory by copying them over | |
2708 | * duplicates. During compaction btf_dedup->hypot_map array is reused to store | |
2709 | * a map from original type ID to a new compacted type ID, which will be used | |
2710 | * during next phase to "fix up" type IDs, referenced from struct/union and | |
2711 | * reference types. | |
2712 | */ | |
2713 | static int btf_dedup_compact_types(struct btf_dedup *d) | |
2714 | { | |
2715 | struct btf_type **new_types; | |
2716 | __u32 next_type_id = 1; | |
2717 | char *types_start, *p; | |
2718 | int i, len; | |
2719 | ||
2720 | /* we are going to reuse hypot_map to store compaction remapping */ | |
2721 | d->hypot_map[0] = 0; | |
2722 | for (i = 1; i <= d->btf->nr_types; i++) | |
2723 | d->hypot_map[i] = BTF_UNPROCESSED_ID; | |
2724 | ||
2725 | types_start = d->btf->nohdr_data + d->btf->hdr->type_off; | |
2726 | p = types_start; | |
2727 | ||
2728 | for (i = 1; i <= d->btf->nr_types; i++) { | |
2729 | if (d->map[i] != i) | |
2730 | continue; | |
2731 | ||
2732 | len = btf_type_size(d->btf->types[i]); | |
2733 | if (len < 0) | |
2734 | return len; | |
2735 | ||
2736 | memmove(p, d->btf->types[i], len); | |
2737 | d->hypot_map[i] = next_type_id; | |
2738 | d->btf->types[next_type_id] = (struct btf_type *)p; | |
2739 | p += len; | |
2740 | next_type_id++; | |
2741 | } | |
2742 | ||
2743 | /* shrink struct btf's internal types index and update btf_header */ | |
2744 | d->btf->nr_types = next_type_id - 1; | |
2745 | d->btf->types_size = d->btf->nr_types; | |
2746 | d->btf->hdr->type_len = p - types_start; | |
2747 | new_types = realloc(d->btf->types, | |
2748 | (1 + d->btf->nr_types) * sizeof(struct btf_type *)); | |
2749 | if (!new_types) | |
2750 | return -ENOMEM; | |
2751 | d->btf->types = new_types; | |
2752 | ||
2753 | /* make sure string section follows type information without gaps */ | |
2754 | d->btf->hdr->str_off = p - (char *)d->btf->nohdr_data; | |
2755 | memmove(p, d->btf->strings, d->btf->hdr->str_len); | |
2756 | d->btf->strings = p; | |
2757 | p += d->btf->hdr->str_len; | |
2758 | ||
2759 | d->btf->data_size = p - (char *)d->btf->data; | |
2760 | return 0; | |
2761 | } | |
2762 | ||
2763 | /* | |
2764 | * Figure out final (deduplicated and compacted) type ID for provided original | |
2765 | * `type_id` by first resolving it into corresponding canonical type ID and | |
2766 | * then mapping it to a deduplicated type ID, stored in btf_dedup->hypot_map, | |
2767 | * which is populated during compaction phase. | |
2768 | */ | |
2769 | static int btf_dedup_remap_type_id(struct btf_dedup *d, __u32 type_id) | |
2770 | { | |
2771 | __u32 resolved_type_id, new_type_id; | |
2772 | ||
2773 | resolved_type_id = resolve_type_id(d, type_id); | |
2774 | new_type_id = d->hypot_map[resolved_type_id]; | |
5aab392c | 2775 | if (new_type_id > BTF_MAX_NR_TYPES) |
d5caef5b AN |
2776 | return -EINVAL; |
2777 | return new_type_id; | |
2778 | } | |
2779 | ||
2780 | /* | |
2781 | * Remap referenced type IDs into deduped type IDs. | |
2782 | * | |
2783 | * After BTF types are deduplicated and compacted, their final type IDs may | |
2784 | * differ from original ones. The map from original to a corresponding | |
2785 | * deduped type ID is stored in btf_dedup->hypot_map and is populated during | |
2786 | * compaction phase. During remapping phase we are rewriting all type IDs | |
2787 | * referenced from any BTF type (e.g., struct fields, func proto args, etc) to | |
2788 | * their final deduped type IDs. | |
2789 | */ | |
2790 | static int btf_dedup_remap_type(struct btf_dedup *d, __u32 type_id) | |
2791 | { | |
2792 | struct btf_type *t = d->btf->types[type_id]; | |
2793 | int i, r; | |
2794 | ||
2795 | switch (BTF_INFO_KIND(t->info)) { | |
2796 | case BTF_KIND_INT: | |
2797 | case BTF_KIND_ENUM: | |
2798 | break; | |
2799 | ||
2800 | case BTF_KIND_FWD: | |
2801 | case BTF_KIND_CONST: | |
2802 | case BTF_KIND_VOLATILE: | |
2803 | case BTF_KIND_RESTRICT: | |
2804 | case BTF_KIND_PTR: | |
2805 | case BTF_KIND_TYPEDEF: | |
2806 | case BTF_KIND_FUNC: | |
189cf5a4 | 2807 | case BTF_KIND_VAR: |
d5caef5b AN |
2808 | r = btf_dedup_remap_type_id(d, t->type); |
2809 | if (r < 0) | |
2810 | return r; | |
2811 | t->type = r; | |
2812 | break; | |
2813 | ||
2814 | case BTF_KIND_ARRAY: { | |
2815 | struct btf_array *arr_info = (struct btf_array *)(t + 1); | |
2816 | ||
2817 | r = btf_dedup_remap_type_id(d, arr_info->type); | |
2818 | if (r < 0) | |
2819 | return r; | |
2820 | arr_info->type = r; | |
2821 | r = btf_dedup_remap_type_id(d, arr_info->index_type); | |
2822 | if (r < 0) | |
2823 | return r; | |
2824 | arr_info->index_type = r; | |
2825 | break; | |
2826 | } | |
2827 | ||
2828 | case BTF_KIND_STRUCT: | |
2829 | case BTF_KIND_UNION: { | |
2830 | struct btf_member *member = (struct btf_member *)(t + 1); | |
2831 | __u16 vlen = BTF_INFO_VLEN(t->info); | |
2832 | ||
2833 | for (i = 0; i < vlen; i++) { | |
2834 | r = btf_dedup_remap_type_id(d, member->type); | |
2835 | if (r < 0) | |
2836 | return r; | |
2837 | member->type = r; | |
2838 | member++; | |
2839 | } | |
2840 | break; | |
2841 | } | |
2842 | ||
2843 | case BTF_KIND_FUNC_PROTO: { | |
2844 | struct btf_param *param = (struct btf_param *)(t + 1); | |
2845 | __u16 vlen = BTF_INFO_VLEN(t->info); | |
2846 | ||
2847 | r = btf_dedup_remap_type_id(d, t->type); | |
2848 | if (r < 0) | |
2849 | return r; | |
2850 | t->type = r; | |
2851 | ||
2852 | for (i = 0; i < vlen; i++) { | |
2853 | r = btf_dedup_remap_type_id(d, param->type); | |
2854 | if (r < 0) | |
2855 | return r; | |
2856 | param->type = r; | |
2857 | param++; | |
2858 | } | |
2859 | break; | |
2860 | } | |
2861 | ||
189cf5a4 AN |
2862 | case BTF_KIND_DATASEC: { |
2863 | struct btf_var_secinfo *var = (struct btf_var_secinfo *)(t + 1); | |
2864 | __u16 vlen = BTF_INFO_VLEN(t->info); | |
2865 | ||
2866 | for (i = 0; i < vlen; i++) { | |
2867 | r = btf_dedup_remap_type_id(d, var->type); | |
2868 | if (r < 0) | |
2869 | return r; | |
2870 | var->type = r; | |
2871 | var++; | |
2872 | } | |
2873 | break; | |
2874 | } | |
2875 | ||
d5caef5b AN |
2876 | default: |
2877 | return -EINVAL; | |
2878 | } | |
2879 | ||
2880 | return 0; | |
2881 | } | |
2882 | ||
2883 | static int btf_dedup_remap_types(struct btf_dedup *d) | |
2884 | { | |
2885 | int i, r; | |
2886 | ||
2887 | for (i = 1; i <= d->btf->nr_types; i++) { | |
2888 | r = btf_dedup_remap_type(d, i); | |
2889 | if (r < 0) | |
2890 | return r; | |
2891 | } | |
2892 | return 0; | |
2893 | } |