diff options
Diffstat (limited to 'tools/lib/bpf')
-rw-r--r-- | tools/lib/bpf/Build | 4 | ||||
-rw-r--r-- | tools/lib/bpf/Makefile | 12 | ||||
-rw-r--r-- | tools/lib/bpf/bpf.c | 1 | ||||
-rw-r--r-- | tools/lib/bpf/bpf.h | 1 | ||||
-rw-r--r-- | tools/lib/bpf/btf.c | 329 | ||||
-rw-r--r-- | tools/lib/bpf/btf.h | 19 | ||||
-rw-r--r-- | tools/lib/bpf/btf_dump.c | 1336 | ||||
-rw-r--r-- | tools/lib/bpf/hashmap.c | 229 | ||||
-rw-r--r-- | tools/lib/bpf/hashmap.h | 173 | ||||
-rw-r--r-- | tools/lib/bpf/libbpf.c | 175 | ||||
-rw-r--r-- | tools/lib/bpf/libbpf.h | 7 | ||||
-rw-r--r-- | tools/lib/bpf/libbpf.map | 9 | ||||
-rw-r--r-- | tools/lib/bpf/libbpf_internal.h | 2 |
13 files changed, 2085 insertions, 212 deletions
diff --git a/tools/lib/bpf/Build b/tools/lib/bpf/Build index ee9d5362f35b..e3962cfbc9a6 100644 --- a/tools/lib/bpf/Build +++ b/tools/lib/bpf/Build @@ -1 +1,3 @@ -libbpf-y := libbpf.o bpf.o nlattr.o btf.o libbpf_errno.o str_error.o netlink.o bpf_prog_linfo.o libbpf_probes.o xsk.o +libbpf-y := libbpf.o bpf.o nlattr.o btf.o libbpf_errno.o str_error.o \ + netlink.o bpf_prog_linfo.o libbpf_probes.o xsk.o hashmap.o \ + btf_dump.o diff --git a/tools/lib/bpf/Makefile b/tools/lib/bpf/Makefile index f91639bf5650..9312066a1ae3 100644 --- a/tools/lib/bpf/Makefile +++ b/tools/lib/bpf/Makefile @@ -3,7 +3,7 @@ BPF_VERSION = 0 BPF_PATCHLEVEL = 0 -BPF_EXTRAVERSION = 3 +BPF_EXTRAVERSION = 4 MAKEFLAGS += --no-print-directory @@ -204,6 +204,16 @@ check_abi: $(OUTPUT)libbpf.so "versioned symbols in $^ ($(VERSIONED_SYM_COUNT))." \ "Please make sure all LIBBPF_API symbols are" \ "versioned in $(VERSION_SCRIPT)." >&2; \ + readelf -s --wide $(OUTPUT)libbpf-in.o | \ + awk '/GLOBAL/ && /DEFAULT/ && !/UND/ {print $$8}'| \ + sort -u > $(OUTPUT)libbpf_global_syms.tmp; \ + readelf -s --wide $(OUTPUT)libbpf.so | \ + grep -Eo '[^ ]+@LIBBPF_' | cut -d@ -f1 | \ + sort -u > $(OUTPUT)libbpf_versioned_syms.tmp; \ + diff -u $(OUTPUT)libbpf_global_syms.tmp \ + $(OUTPUT)libbpf_versioned_syms.tmp; \ + rm $(OUTPUT)libbpf_global_syms.tmp \ + $(OUTPUT)libbpf_versioned_syms.tmp; \ exit 1; \ fi diff --git a/tools/lib/bpf/bpf.c b/tools/lib/bpf/bpf.c index c4a48086dc9a..0d4b4fe10a84 100644 --- a/tools/lib/bpf/bpf.c +++ b/tools/lib/bpf/bpf.c @@ -256,6 +256,7 @@ int bpf_load_program_xattr(const struct bpf_load_program_attr *load_attr, if (load_attr->name) memcpy(attr.prog_name, load_attr->name, min(strlen(load_attr->name), BPF_OBJ_NAME_LEN - 1)); + attr.prog_flags = load_attr->prog_flags; fd = sys_bpf_prog_load(&attr, sizeof(attr)); if (fd >= 0) diff --git a/tools/lib/bpf/bpf.h b/tools/lib/bpf/bpf.h index 9593fec75652..ff42ca043dc8 100644 --- a/tools/lib/bpf/bpf.h +++ b/tools/lib/bpf/bpf.h @@ -87,6 +87,7 @@ struct bpf_load_program_attr { const void *line_info; __u32 line_info_cnt; __u32 log_level; + __u32 prog_flags; }; /* Flags to direct loading requirements */ diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index 03348c4d6bd4..b2478e98c367 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -4,14 +4,17 @@ #include <stdio.h> #include <stdlib.h> #include <string.h> +#include <fcntl.h> #include <unistd.h> #include <errno.h> #include <linux/err.h> #include <linux/btf.h> +#include <gelf.h> #include "btf.h" #include "bpf.h" #include "libbpf.h" #include "libbpf_internal.h" +#include "hashmap.h" #define max(a, b) ((a) > (b) ? (a) : (b)) #define min(a, b) ((a) < (b) ? (a) : (b)) @@ -417,6 +420,132 @@ done: return btf; } +static bool btf_check_endianness(const GElf_Ehdr *ehdr) +{ +#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ + return ehdr->e_ident[EI_DATA] == ELFDATA2LSB; +#elif __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ + return ehdr->e_ident[EI_DATA] == ELFDATA2MSB; +#else +# error "Unrecognized __BYTE_ORDER__" +#endif +} + +struct btf *btf__parse_elf(const char *path, struct btf_ext **btf_ext) +{ + Elf_Data *btf_data = NULL, *btf_ext_data = NULL; + int err = 0, fd = -1, idx = 0; + struct btf *btf = NULL; + Elf_Scn *scn = NULL; + Elf *elf = NULL; + GElf_Ehdr ehdr; + + if (elf_version(EV_CURRENT) == EV_NONE) { + pr_warning("failed to init libelf for %s\n", path); + return ERR_PTR(-LIBBPF_ERRNO__LIBELF); + } + + fd = open(path, O_RDONLY); + if (fd < 0) { + err = -errno; + pr_warning("failed to open %s: %s\n", path, strerror(errno)); + return ERR_PTR(err); + } + + err = -LIBBPF_ERRNO__FORMAT; + + elf = elf_begin(fd, ELF_C_READ, NULL); + if (!elf) { + pr_warning("failed to open %s as ELF file\n", path); + goto done; + } + if (!gelf_getehdr(elf, &ehdr)) { + pr_warning("failed to get EHDR from %s\n", path); + goto done; + } + if (!btf_check_endianness(&ehdr)) { + pr_warning("non-native ELF endianness is not supported\n"); + goto done; + } + if (!elf_rawdata(elf_getscn(elf, ehdr.e_shstrndx), NULL)) { + pr_warning("failed to get e_shstrndx from %s\n", path); + goto done; + } + + while ((scn = elf_nextscn(elf, scn)) != NULL) { + GElf_Shdr sh; + char *name; + + idx++; + if (gelf_getshdr(scn, &sh) != &sh) { + pr_warning("failed to get section(%d) header from %s\n", + idx, path); + goto done; + } + name = elf_strptr(elf, ehdr.e_shstrndx, sh.sh_name); + if (!name) { + pr_warning("failed to get section(%d) name from %s\n", + idx, path); + goto done; + } + if (strcmp(name, BTF_ELF_SEC) == 0) { + btf_data = elf_getdata(scn, 0); + if (!btf_data) { + pr_warning("failed to get section(%d, %s) data from %s\n", + idx, name, path); + goto done; + } + continue; + } else if (btf_ext && strcmp(name, BTF_EXT_ELF_SEC) == 0) { + btf_ext_data = elf_getdata(scn, 0); + if (!btf_ext_data) { + pr_warning("failed to get section(%d, %s) data from %s\n", + idx, name, path); + goto done; + } + continue; + } + } + + err = 0; + + if (!btf_data) { + err = -ENOENT; + goto done; + } + btf = btf__new(btf_data->d_buf, btf_data->d_size); + if (IS_ERR(btf)) + goto done; + + if (btf_ext && btf_ext_data) { + *btf_ext = btf_ext__new(btf_ext_data->d_buf, + btf_ext_data->d_size); + if (IS_ERR(*btf_ext)) + goto done; + } else if (btf_ext) { + *btf_ext = NULL; + } +done: + if (elf) + elf_end(elf); + close(fd); + + if (err) + return ERR_PTR(err); + /* + * btf is always parsed before btf_ext, so no need to clean up + * btf_ext, if btf loading failed + */ + if (IS_ERR(btf)) + return btf; + if (btf_ext && IS_ERR(*btf_ext)) { + btf__free(btf); + err = PTR_ERR(*btf_ext); + return ERR_PTR(err); + } + return btf; +} + static int compare_vsi_off(const void *_a, const void *_b) { const struct btf_var_secinfo *a = _a; @@ -1165,16 +1294,9 @@ done: return err; } -#define BTF_DEDUP_TABLE_DEFAULT_SIZE (1 << 14) -#define BTF_DEDUP_TABLE_MAX_SIZE_LOG 31 #define BTF_UNPROCESSED_ID ((__u32)-1) #define BTF_IN_PROGRESS_ID ((__u32)-2) -struct btf_dedup_node { - struct btf_dedup_node *next; - __u32 type_id; -}; - struct btf_dedup { /* .BTF section to be deduped in-place */ struct btf *btf; @@ -1190,7 +1312,7 @@ struct btf_dedup { * candidates, which is fine because we rely on subsequent * btf_xxx_equal() checks to authoritatively verify type equality. */ - struct btf_dedup_node **dedup_table; + struct hashmap *dedup_table; /* Canonical types map */ __u32 *map; /* Hypothetical mapping, used during type graph equivalence checks */ @@ -1215,30 +1337,18 @@ struct btf_str_ptrs { __u32 cap; }; -static inline __u32 hash_combine(__u32 h, __u32 value) +static long hash_combine(long h, long value) { -/* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */ -#define GOLDEN_RATIO_PRIME 0x9e370001UL - return h * 37 + value * GOLDEN_RATIO_PRIME; -#undef GOLDEN_RATIO_PRIME + return h * 31 + value; } -#define for_each_dedup_cand(d, hash, node) \ - for (node = d->dedup_table[hash & (d->opts.dedup_table_size - 1)]; \ - node; \ - node = node->next) +#define for_each_dedup_cand(d, node, hash) \ + hashmap__for_each_key_entry(d->dedup_table, node, (void *)hash) -static int btf_dedup_table_add(struct btf_dedup *d, __u32 hash, __u32 type_id) +static int btf_dedup_table_add(struct btf_dedup *d, long hash, __u32 type_id) { - struct btf_dedup_node *node = malloc(sizeof(struct btf_dedup_node)); - int bucket = hash & (d->opts.dedup_table_size - 1); - - if (!node) - return -ENOMEM; - node->type_id = type_id; - node->next = d->dedup_table[bucket]; - d->dedup_table[bucket] = node; - return 0; + return hashmap__append(d->dedup_table, + (void *)hash, (void *)(long)type_id); } static int btf_dedup_hypot_map_add(struct btf_dedup *d, @@ -1267,36 +1377,10 @@ static void btf_dedup_clear_hypot_map(struct btf_dedup *d) d->hypot_cnt = 0; } -static void btf_dedup_table_free(struct btf_dedup *d) -{ - struct btf_dedup_node *head, *tmp; - int i; - - if (!d->dedup_table) - return; - - for (i = 0; i < d->opts.dedup_table_size; i++) { - while (d->dedup_table[i]) { - tmp = d->dedup_table[i]; - d->dedup_table[i] = tmp->next; - free(tmp); - } - - head = d->dedup_table[i]; - while (head) { - tmp = head; - head = head->next; - free(tmp); - } - } - - free(d->dedup_table); - d->dedup_table = NULL; -} - static void btf_dedup_free(struct btf_dedup *d) { - btf_dedup_table_free(d); + hashmap__free(d->dedup_table); + d->dedup_table = NULL; free(d->map); d->map = NULL; @@ -1310,40 +1394,43 @@ static void btf_dedup_free(struct btf_dedup *d) free(d); } -/* Find closest power of two >= to size, capped at 2^max_size_log */ -static __u32 roundup_pow2_max(__u32 size, int max_size_log) +static size_t btf_dedup_identity_hash_fn(const void *key, void *ctx) { - int i; + return (size_t)key; +} - for (i = 0; i < max_size_log && (1U << i) < size; i++) - ; - return 1U << i; +static size_t btf_dedup_collision_hash_fn(const void *key, void *ctx) +{ + return 0; } +static bool btf_dedup_equal_fn(const void *k1, const void *k2, void *ctx) +{ + return k1 == k2; +} static struct btf_dedup *btf_dedup_new(struct btf *btf, struct btf_ext *btf_ext, const struct btf_dedup_opts *opts) { struct btf_dedup *d = calloc(1, sizeof(struct btf_dedup)); + hashmap_hash_fn hash_fn = btf_dedup_identity_hash_fn; int i, err = 0; - __u32 sz; if (!d) return ERR_PTR(-ENOMEM); d->opts.dont_resolve_fwds = opts && opts->dont_resolve_fwds; - sz = opts && opts->dedup_table_size ? opts->dedup_table_size - : BTF_DEDUP_TABLE_DEFAULT_SIZE; - sz = roundup_pow2_max(sz, BTF_DEDUP_TABLE_MAX_SIZE_LOG); - d->opts.dedup_table_size = sz; + /* dedup_table_size is now used only to force collisions in tests */ + if (opts && opts->dedup_table_size == 1) + hash_fn = btf_dedup_collision_hash_fn; d->btf = btf; d->btf_ext = btf_ext; - d->dedup_table = calloc(d->opts.dedup_table_size, - sizeof(struct btf_dedup_node *)); - if (!d->dedup_table) { - err = -ENOMEM; + d->dedup_table = hashmap__new(hash_fn, btf_dedup_equal_fn, NULL); + if (IS_ERR(d->dedup_table)) { + err = PTR_ERR(d->dedup_table); + d->dedup_table = NULL; goto done; } @@ -1662,9 +1749,9 @@ done: return err; } -static __u32 btf_hash_common(struct btf_type *t) +static long btf_hash_common(struct btf_type *t) { - __u32 h; + long h; h = hash_combine(0, t->name_off); h = hash_combine(h, t->info); @@ -1680,10 +1767,10 @@ static bool btf_equal_common(struct btf_type *t1, struct btf_type *t2) } /* Calculate type signature hash of INT. */ -static __u32 btf_hash_int(struct btf_type *t) +static long btf_hash_int(struct btf_type *t) { __u32 info = *(__u32 *)(t + 1); - __u32 h; + long h; h = btf_hash_common(t); h = hash_combine(h, info); @@ -1703,9 +1790,9 @@ static bool btf_equal_int(struct btf_type *t1, struct btf_type *t2) } /* Calculate type signature hash of ENUM. */ -static __u32 btf_hash_enum(struct btf_type *t) +static long btf_hash_enum(struct btf_type *t) { - __u32 h; + long h; /* don't hash vlen and enum members to support enum fwd resolving */ h = hash_combine(0, t->name_off); @@ -1757,11 +1844,11 @@ static bool btf_compat_enum(struct btf_type *t1, struct btf_type *t2) * as referenced type IDs equivalence is established separately during type * graph equivalence check algorithm. */ -static __u32 btf_hash_struct(struct btf_type *t) +static long btf_hash_struct(struct btf_type *t) { struct btf_member *member = (struct btf_member *)(t + 1); __u32 vlen = BTF_INFO_VLEN(t->info); - __u32 h = btf_hash_common(t); + long h = btf_hash_common(t); int i; for (i = 0; i < vlen; i++) { @@ -1804,10 +1891,10 @@ static bool btf_shallow_equal_struct(struct btf_type *t1, struct btf_type *t2) * under assumption that they were already resolved to canonical type IDs and * are not going to change. */ -static __u32 btf_hash_array(struct btf_type *t) +static long btf_hash_array(struct btf_type *t) { struct btf_array *info = (struct btf_array *)(t + 1); - __u32 h = btf_hash_common(t); + long h = btf_hash_common(t); h = hash_combine(h, info->type); h = hash_combine(h, info->index_type); @@ -1858,11 +1945,11 @@ static bool btf_compat_array(struct btf_type *t1, struct btf_type *t2) * under assumption that they were already resolved to canonical type IDs and * are not going to change. */ -static inline __u32 btf_hash_fnproto(struct btf_type *t) +static long btf_hash_fnproto(struct btf_type *t) { struct btf_param *member = (struct btf_param *)(t + 1); __u16 vlen = BTF_INFO_VLEN(t->info); - __u32 h = btf_hash_common(t); + long h = btf_hash_common(t); int i; for (i = 0; i < vlen; i++) { @@ -1880,7 +1967,7 @@ static inline __u32 btf_hash_fnproto(struct btf_type *t) * This function is called during reference types deduplication to compare * FUNC_PROTO to potential canonical representative. */ -static inline bool btf_equal_fnproto(struct btf_type *t1, struct btf_type *t2) +static bool btf_equal_fnproto(struct btf_type *t1, struct btf_type *t2) { struct btf_param *m1, *m2; __u16 vlen; @@ -1906,7 +1993,7 @@ static inline bool btf_equal_fnproto(struct btf_type *t1, struct btf_type *t2) * IDs. This check is performed during type graph equivalence check and * referenced types equivalence is checked separately. */ -static inline bool btf_compat_fnproto(struct btf_type *t1, struct btf_type *t2) +static bool btf_compat_fnproto(struct btf_type *t1, struct btf_type *t2) { struct btf_param *m1, *m2; __u16 vlen; @@ -1937,11 +2024,12 @@ static inline bool btf_compat_fnproto(struct btf_type *t1, struct btf_type *t2) static int btf_dedup_prim_type(struct btf_dedup *d, __u32 type_id) { struct btf_type *t = d->btf->types[type_id]; + struct hashmap_entry *hash_entry; struct btf_type *cand; - struct btf_dedup_node *cand_node; /* if we don't find equivalent type, then we are canonical */ __u32 new_id = type_id; - __u32 h; + __u32 cand_id; + long h; switch (BTF_INFO_KIND(t->info)) { case BTF_KIND_CONST: @@ -1960,10 +2048,11 @@ static int btf_dedup_prim_type(struct btf_dedup *d, __u32 type_id) case BTF_KIND_INT: h = btf_hash_int(t); - for_each_dedup_cand(d, h, cand_node) { - cand = d->btf->types[cand_node->type_id]; + for_each_dedup_cand(d, hash_entry, h) { + cand_id = (__u32)(long)hash_entry->value; + cand = d->btf->types[cand_id]; if (btf_equal_int(t, cand)) { - new_id = cand_node->type_id; + new_id = cand_id; break; } } @@ -1971,10 +2060,11 @@ static int btf_dedup_prim_type(struct btf_dedup *d, __u32 type_id) case BTF_KIND_ENUM: h = btf_hash_enum(t); - for_each_dedup_cand(d, h, cand_node) { - cand = d->btf->types[cand_node->type_id]; + for_each_dedup_cand(d, hash_entry, h) { + cand_id = (__u32)(long)hash_entry->value; + cand = d->btf->types[cand_id]; if (btf_equal_enum(t, cand)) { - new_id = cand_node->type_id; + new_id = cand_id; break; } if (d->opts.dont_resolve_fwds) @@ -1982,21 +2072,22 @@ static int btf_dedup_prim_type(struct btf_dedup *d, __u32 type_id) if (btf_compat_enum(t, cand)) { if (btf_is_enum_fwd(t)) { /* resolve fwd to full enum */ - new_id = cand_node->type_id; + new_id = cand_id; break; } /* resolve canonical enum fwd to full enum */ - d->map[cand_node->type_id] = type_id; + d->map[cand_id] = type_id; } } break; case BTF_KIND_FWD: h = btf_hash_common(t); - for_each_dedup_cand(d, h, cand_node) { - cand = d->btf->types[cand_node->type_id]; + for_each_dedup_cand(d, hash_entry, h) { + cand_id = (__u32)(long)hash_entry->value; + cand = d->btf->types[cand_id]; if (btf_equal_common(t, cand)) { - new_id = cand_node->type_id; + new_id = cand_id; break; } } @@ -2397,12 +2488,12 @@ static void btf_dedup_merge_hypot_map(struct btf_dedup *d) */ static int btf_dedup_struct_type(struct btf_dedup *d, __u32 type_id) { - struct btf_dedup_node *cand_node; struct btf_type *cand_type, *t; + struct hashmap_entry *hash_entry; /* if we don't find equivalent type, then we are canonical */ __u32 new_id = type_id; __u16 kind; - __u32 h; + long h; /* already deduped or is in process of deduping (loop detected) */ if (d->map[type_id] <= BTF_MAX_NR_TYPES) @@ -2415,7 +2506,8 @@ static int btf_dedup_struct_type(struct btf_dedup *d, __u32 type_id) return 0; h = btf_hash_struct(t); - for_each_dedup_cand(d, h, cand_node) { + for_each_dedup_cand(d, hash_entry, h) { + __u32 cand_id = (__u32)(long)hash_entry->value; int eq; /* @@ -2428,17 +2520,17 @@ static int btf_dedup_struct_type(struct btf_dedup *d, __u32 type_id) * creating a loop (FWD -> STRUCT and STRUCT -> FWD), because * FWD and compatible STRUCT/UNION are considered equivalent. */ - cand_type = d->btf->types[cand_node->type_id]; + cand_type = d->btf->types[cand_id]; if (!btf_shallow_equal_struct(t, cand_type)) continue; btf_dedup_clear_hypot_map(d); - eq = btf_dedup_is_equiv(d, type_id, cand_node->type_id); + eq = btf_dedup_is_equiv(d, type_id, cand_id); if (eq < 0) return eq; if (!eq) continue; - new_id = cand_node->type_id; + new_id = cand_id; btf_dedup_merge_hypot_map(d); break; } @@ -2488,12 +2580,12 @@ static int btf_dedup_struct_types(struct btf_dedup *d) */ static int btf_dedup_ref_type(struct btf_dedup *d, __u32 type_id) { - struct btf_dedup_node *cand_node; + struct hashmap_entry *hash_entry; + __u32 new_id = type_id, cand_id; struct btf_type *t, *cand; /* if we don't find equivalent type, then we are representative type */ - __u32 new_id = type_id; int ref_type_id; - __u32 h; + long h; if (d->map[type_id] == BTF_IN_PROGRESS_ID) return -ELOOP; @@ -2516,10 +2608,11 @@ static int btf_dedup_ref_type(struct btf_dedup *d, __u32 type_id) t->type = ref_type_id; h = btf_hash_common(t); - for_each_dedup_cand(d, h, cand_node) { - cand = d->btf->types[cand_node->type_id]; + for_each_dedup_cand(d, hash_entry, h) { + cand_id = (__u32)(long)hash_entry->value; + cand = d->btf->types[cand_id]; if (btf_equal_common(t, cand)) { - new_id = cand_node->type_id; + new_id = cand_id; break; } } @@ -2539,10 +2632,11 @@ static int btf_dedup_ref_type(struct btf_dedup *d, __u32 type_id) info->index_type = ref_type_id; h = btf_hash_array(t); - for_each_dedup_cand(d, h, cand_node) { - cand = d->btf->types[cand_node->type_id]; + for_each_dedup_cand(d, hash_entry, h) { + cand_id = (__u32)(long)hash_entry->value; + cand = d->btf->types[cand_id]; if (btf_equal_array(t, cand)) { - new_id = cand_node->type_id; + new_id = cand_id; break; } } @@ -2570,10 +2664,11 @@ static int btf_dedup_ref_type(struct btf_dedup *d, __u32 type_id) } h = btf_hash_fnproto(t); - for_each_dedup_cand(d, h, cand_node) { - cand = d->btf->types[cand_node->type_id]; + for_each_dedup_cand(d, hash_entry, h) { + cand_id = (__u32)(long)hash_entry->value; + cand = d->btf->types[cand_id]; if (btf_equal_fnproto(t, cand)) { - new_id = cand_node->type_id; + new_id = cand_id; break; } } @@ -2600,7 +2695,9 @@ static int btf_dedup_ref_types(struct btf_dedup *d) if (err < 0) return err; } - btf_dedup_table_free(d); + /* we won't need d->dedup_table anymore */ + hashmap__free(d->dedup_table); + d->dedup_table = NULL; return 0; } diff --git a/tools/lib/bpf/btf.h b/tools/lib/bpf/btf.h index c7b399e81fce..ba4ffa831aa4 100644 --- a/tools/lib/bpf/btf.h +++ b/tools/lib/bpf/btf.h @@ -4,6 +4,7 @@ #ifndef __LIBBPF_BTF_H #define __LIBBPF_BTF_H +#include <stdarg.h> #include <linux/types.h> #ifdef __cplusplus @@ -59,6 +60,8 @@ struct btf_ext_header { LIBBPF_API void btf__free(struct btf *btf); LIBBPF_API struct btf *btf__new(__u8 *data, __u32 size); +LIBBPF_API struct btf *btf__parse_elf(const char *path, + struct btf_ext **btf_ext); LIBBPF_API int btf__finalize_data(struct bpf_object *obj, struct btf *btf); LIBBPF_API int btf__load(struct btf *btf); LIBBPF_API __s32 btf__find_by_name(const struct btf *btf, @@ -100,6 +103,22 @@ struct btf_dedup_opts { LIBBPF_API int btf__dedup(struct btf *btf, struct btf_ext *btf_ext, const struct btf_dedup_opts *opts); +struct btf_dump; + +struct btf_dump_opts { + void *ctx; +}; + +typedef void (*btf_dump_printf_fn_t)(void *ctx, const char *fmt, va_list args); + +LIBBPF_API struct btf_dump *btf_dump__new(const struct btf *btf, + const struct btf_ext *btf_ext, + const struct btf_dump_opts *opts, + btf_dump_printf_fn_t printf_fn); +LIBBPF_API void btf_dump__free(struct btf_dump *d); + +LIBBPF_API int btf_dump__dump_type(struct btf_dump *d, __u32 id); + #ifdef __cplusplus } /* extern "C" */ #endif diff --git a/tools/lib/bpf/btf_dump.c b/tools/lib/bpf/btf_dump.c new file mode 100644 index 000000000000..4b22db77e2cc --- /dev/null +++ b/tools/lib/bpf/btf_dump.c @@ -0,0 +1,1336 @@ +// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) + +/* + * BTF-to-C type converter. + * + * Copyright (c) 2019 Facebook + */ + +#include <stdbool.h> +#include <stddef.h> +#include <stdlib.h> +#include <string.h> +#include <errno.h> +#include <linux/err.h> +#include <linux/btf.h> +#include "btf.h" +#include "hashmap.h" +#include "libbpf.h" +#include "libbpf_internal.h" + +#define min(x, y) ((x) < (y) ? (x) : (y)) +#define max(x, y) ((x) < (y) ? (y) : (x)) + +static const char PREFIXES[] = "\t\t\t\t\t\t\t\t\t\t\t\t\t"; +static const size_t PREFIX_CNT = sizeof(PREFIXES) - 1; + +static const char *pfx(int lvl) +{ + return lvl >= PREFIX_CNT ? PREFIXES : &PREFIXES[PREFIX_CNT - lvl]; +} + +enum btf_dump_type_order_state { + NOT_ORDERED, + ORDERING, + ORDERED, +}; + +enum btf_dump_type_emit_state { + NOT_EMITTED, + EMITTING, + EMITTED, +}; + +/* per-type auxiliary state */ +struct btf_dump_type_aux_state { + /* topological sorting state */ + enum btf_dump_type_order_state order_state: 2; + /* emitting state used to determine the need for forward declaration */ + enum btf_dump_type_emit_state emit_state: 2; + /* whether forward declaration was already emitted */ + __u8 fwd_emitted: 1; + /* whether unique non-duplicate name was already assigned */ + __u8 name_resolved: 1; +}; + +struct btf_dump { + const struct btf *btf; + const struct btf_ext *btf_ext; + btf_dump_printf_fn_t printf_fn; + struct btf_dump_opts opts; + + /* per-type auxiliary state */ + struct btf_dump_type_aux_state *type_states; + /* per-type optional cached unique name, must be freed, if present */ + const char **cached_names; + + /* topo-sorted list of dependent type definitions */ + __u32 *emit_queue; + int emit_queue_cap; + int emit_queue_cnt; + + /* + * stack of type declarations (e.g., chain of modifiers, arrays, + * funcs, etc) + */ + __u32 *decl_stack; + int decl_stack_cap; + int decl_stack_cnt; + + /* maps struct/union/enum name to a number of name occurrences */ + struct hashmap *type_names; + /* + * maps typedef identifiers and enum value names to a number of such + * name occurrences + */ + struct hashmap *ident_names; +}; + +static size_t str_hash_fn(const void *key, void *ctx) +{ + const char *s = key; + size_t h = 0; + + while (*s) { + h = h * 31 + *s; + s++; + } + return h; +} + +static bool str_equal_fn(const void *a, const void *b, void *ctx) +{ + return strcmp(a, b) == 0; +} + +static __u16 btf_kind_of(const struct btf_type *t) +{ + return BTF_INFO_KIND(t->info); +} + +static __u16 btf_vlen_of(const struct btf_type *t) +{ + return BTF_INFO_VLEN(t->info); +} + +static bool btf_kflag_of(const struct btf_type *t) +{ + return BTF_INFO_KFLAG(t->info); +} + +static const char *btf_name_of(const struct btf_dump *d, __u32 name_off) +{ + return btf__name_by_offset(d->btf, name_off); +} + +static void btf_dump_printf(const struct btf_dump *d, const char *fmt, ...) +{ + va_list args; + + va_start(args, fmt); + d->printf_fn(d->opts.ctx, fmt, args); + va_end(args); +} + +struct btf_dump *btf_dump__new(const struct btf *btf, + const struct btf_ext *btf_ext, + const struct btf_dump_opts *opts, + btf_dump_printf_fn_t printf_fn) +{ + struct btf_dump *d; + int err; + + d = calloc(1, sizeof(struct btf_dump)); + if (!d) + return ERR_PTR(-ENOMEM); + + d->btf = btf; + d->btf_ext = btf_ext; + d->printf_fn = printf_fn; + d->opts.ctx = opts ? opts->ctx : NULL; + + d->type_names = hashmap__new(str_hash_fn, str_equal_fn, NULL); + if (IS_ERR(d->type_names)) { + err = PTR_ERR(d->type_names); + d->type_names = NULL; + btf_dump__free(d); + return ERR_PTR(err); + } + d->ident_names = hashmap__new(str_hash_fn, str_equal_fn, NULL); + if (IS_ERR(d->ident_names)) { + err = PTR_ERR(d->ident_names); + d->ident_names = NULL; + btf_dump__free(d); + return ERR_PTR(err); + } + + return d; +} + +void btf_dump__free(struct btf_dump *d) +{ + int i, cnt; + + if (!d) + return; + + free(d->type_states); + if (d->cached_names) { + /* any set cached name is owned by us and should be freed */ + for (i = 0, cnt = btf__get_nr_types(d->btf); i <= cnt; i++) { + if (d->cached_names[i]) + free((void *)d->cached_names[i]); + } + } + free(d->cached_names); + free(d->emit_queue); + free(d->decl_stack); + hashmap__free(d->type_names); + hashmap__free(d->ident_names); + + free(d); +} + +static int btf_dump_order_type(struct btf_dump *d, __u32 id, bool through_ptr); +static void btf_dump_emit_type(struct btf_dump *d, __u32 id, __u32 cont_id); + +/* + * Dump BTF type in a compilable C syntax, including all the necessary + * dependent types, necessary for compilation. If some of the dependent types + * were already emitted as part of previous btf_dump__dump_type() invocation + * for another type, they won't be emitted again. This API allows callers to + * filter out BTF types according to user-defined criterias and emitted only + * minimal subset of types, necessary to compile everything. Full struct/union + * definitions will still be emitted, even if the only usage is through + * pointer and could be satisfied with just a forward declaration. + * + * Dumping is done in two high-level passes: + * 1. Topologically sort type definitions to satisfy C rules of compilation. + * 2. Emit type definitions in C syntax. + * + * Returns 0 on success; <0, otherwise. + */ +int btf_dump__dump_type(struct btf_dump *d, __u32 id) +{ + int err, i; + + if (id > btf__get_nr_types(d->btf)) + return -EINVAL; + + /* type states are lazily allocated, as they might not be needed */ + if (!d->type_states) { + d->type_states = calloc(1 + btf__get_nr_types(d->btf), + sizeof(d->type_states[0])); + if (!d->type_states) + return -ENOMEM; + d->cached_names = calloc(1 + btf__get_nr_types(d->btf), + sizeof(d->cached_names[0])); + if (!d->cached_names) + return -ENOMEM; + + /* VOID is special */ + d->type_states[0].order_state = ORDERED; + d->type_states[0].emit_state = EMITTED; + } + + d->emit_queue_cnt = 0; + err = btf_dump_order_type(d, id, false); + if (err < 0) + return err; + + for (i = 0; i < d->emit_queue_cnt; i++) + btf_dump_emit_type(d, d->emit_queue[i], 0 /*top-level*/); + + return 0; +} + +static int btf_dump_add_emit_queue_id(struct btf_dump *d, __u32 id) +{ + __u32 *new_queue; + size_t new_cap; + + if (d->emit_queue_cnt >= d->emit_queue_cap) { + new_cap = max(16, d->emit_queue_cap * 3 / 2); + new_queue = realloc(d->emit_queue, + new_cap * sizeof(new_queue[0])); + if (!new_queue) + return -ENOMEM; + d->emit_queue = new_queue; + d->emit_queue_cap = new_cap; + } + + d->emit_queue[d->emit_queue_cnt++] = id; + return 0; +} + +/* + * Determine order of emitting dependent types and specified type to satisfy + * C compilation rules. This is done through topological sorting with an + * additional complication which comes from C rules. The main idea for C is + * that if some type is "embedded" into a struct/union, it's size needs to be + * known at the time of definition of containing type. E.g., for: + * + * struct A {}; + * struct B { struct A x; } + * + * struct A *HAS* to be defined before struct B, because it's "embedded", + * i.e., it is part of struct B layout. But in the following case: + * + * struct A; + * struct B { struct A *x; } + * struct A {}; + * + * it's enough to just have a forward declaration of struct A at the time of + * struct B definition, as struct B has a pointer to struct A, so the size of + * field x is known without knowing struct A size: it's sizeof(void *). + * + * Unfortunately, there are some trickier cases we need to handle, e.g.: + * + * struct A {}; // if this was forward-declaration: compilation error + * struct B { + * struct { // anonymous struct + * struct A y; + * } *x; + * }; + * + * In this case, struct B's field x is a pointer, so it's size is known + * regardless of the size of (anonymous) struct it points to. But because this + * struct is anonymous and thus defined inline inside struct B, *and* it + * embeds struct A, compiler requires full definition of struct A to be known + * before struct B can be defined. This creates a transitive dependency + * between struct A and struct B. If struct A was forward-declared before + * struct B definition and fully defined after struct B definition, that would + * trigger compilation error. + * + * All this means that while we are doing topological sorting on BTF type + * graph, we need to determine relationships between different types (graph + * nodes): + * - weak link (relationship) between X and Y, if Y *CAN* be + * forward-declared at the point of X definition; + * - strong link, if Y *HAS* to be fully-defined before X can be defined. + * + * The rule is as follows. Given a chain of BTF types from X to Y, if there is + * BTF_KIND_PTR type in the chain and at least one non-anonymous type + * Z (excluding X, including Y), then link is weak. Otherwise, it's strong. + * Weak/strong relationship is determined recursively during DFS traversal and + * is returned as a result from btf_dump_order_type(). + * + * btf_dump_order_type() is trying to avoid unnecessary forward declarations, + * but it is not guaranteeing that no extraneous forward declarations will be + * emitted. + * + * To avoid extra work, algorithm marks some of BTF types as ORDERED, when + * it's done with them, but not for all (e.g., VOLATILE, CONST, RESTRICT, + * ARRAY, FUNC_PROTO), as weak/strong semantics for those depends on the + * entire graph path, so depending where from one came to that BTF type, it + * might cause weak or strong ordering. For types like STRUCT/UNION/INT/ENUM, + * once they are processed, there is no need to do it again, so they are + * marked as ORDERED. We |