BTF-to-C converter
Subsystems (7)
v3 cover BTF-to-C converter
This patch set adds BTF-to-C dumping APIs to libbpf, allowing to output a subset of BTF types as a compilable C type definitions. This is useful by itself, as raw BTF output is not easy to inspect and comprehend. But it's also a big part of BPF CO-RE (compile once - run everywhere) initiative aimed at allowing to write relocatable BPF programs, that won't require on-the-host kernel headers (and would be able to inspect internal kernel structures, not exposed through kernel headers).
This patch set consists of three groups of patches and one pre-patch, with the BTF-to-C dumper API depending on the first two groups.
Pre-patch #1 fixes issue with libbpf_internal.h.
btf__parse_elf() API patches:
- patch #2 adds btf__parse_elf() API to libbpf, allowing to load BTF and/or BTF.ext from ELF file;
- patch #3 utilizies btf__parse_elf() from bpftool for btf dump file command;
- patch #4 switches test_btf.c to use btf__parse_elf() to check for presence of BTF data in object file.
libbpf's internal hashmap patches:
- patch #5 adds resizeable non-thread safe generic hashmap to libbpf;
- patch #6 adds tests for that hashmap;
- patch #7 migrates btf_dedup()'s dedup_table to use hashmap w/ APPEND.
BTF-to-C dumper API patches:
- patch #8 adds btf_dump APIs with all the logic for laying out type definitions in correct order and emitting C syntax for them;
- patch #9 adds lots of tests for common and quirky parts of C type system;
- patch #10 adds support for C-syntax btf dumping to bpftool;
- patch #11 updates bpftool documentation to mention C-syntax dump option;
- patch #12 update bash-completion for btf dump sub-command.
v2->v3:
- fix bpftool-btf.rst formatting (Quentin);
- simplify bash autocompletion script (Quentin);
- better error message in btf dump (Quentin);
v1->v2:
- removed unuseful file header (Jakub);
- removed inlines in .c (Jakub);
- added 'format {c|raw}' keyword/option (Jakub);
- re-use i var for iteration in btf_dump_c() (Jakub);
- bumped libbpf version to 0.0.4;
v0->v1:
- fix bug in hashmap__for_each_bucket_entry() not handling empty hashmap;
- removed btf dump-specific libbpf logging hook up (Quentin has more generic patchset);
- change btf__parse_elf() to always load .BTF and return it as a result, with .BTF.ext being optional and returned through struct btf_ext** arg (Alexei);
- endianness check to use __BYTE_ORDER__ (Alexei);
- bool:1 to __u8:1 in type_aux_state (Alexei);
- added HASHMAP_APPEND strategy to hashmap, changed hashmap__for_each_key_entry() to also check for key equality during iteration (multimap iteration for key);
- added new tests for empty hashmap and hashmap as a multimap;
- tried to clarify weak/strong dependency ordering comments (Alexei)
- btf dump test's expected output - support better commenting aproach (Alexei);
- added bash-completion for a new "c" option (Alexei).
Andrii Nakryiko (12):
libbpf: ensure libbpf.h is included along libbpf_internal.h
libbpf: add btf__parse_elf API to load .BTF and .BTF.ext
bpftool: use libbpf's btf__parse_elf API
selftests/bpf: use btf__parse_elf to check presence of BTF/BTF.ext
libbpf: add resizable non-thread safe internal hashmap selftests/bpf: add tests for libbpf's hashmap
libbpf: switch btf_dedup() to hashmap for dedup table
libbpf: add btf_dump API for BTF-to-C conversion selftests/bpf: add btf_dump BTF-to-C conversion tests
bpftool: add C output format option to btf dump subcommand bpftool/docs: add description of btf dump C option
bpftool: update bash-completion w/ new c option for btf dump
.../bpf/bpftool/Documentation/bpftool-btf.rst | 35 +- tools/bpf/bpftool/bash-completion/bpftool | 21 +- tools/bpf/bpftool/btf.c | 162 +- tools/lib/bpf/Build | 4 +- tools/lib/bpf/btf.c | 329 ++-- tools/lib/bpf/btf.h | 19 + tools/lib/bpf/btf_dump.c | 1336 +++++++++++++++++ tools/lib/bpf/hashmap.c | 229 +++ tools/lib/bpf/hashmap.h | 173 +++ tools/lib/bpf/libbpf.map | 8 + tools/lib/bpf/libbpf_internal.h | 2 + tools/testing/selftests/bpf/.gitignore | 2 + tools/testing/selftests/bpf/Makefile | 3 +- .../bpf/progs/btf_dump_test_case_bitfields.c | 92 ++ .../bpf/progs/btf_dump_test_case_multidim.c | 35 + .../progs/btf_dump_test_case_namespacing.c | 73 + .../bpf/progs/btf_dump_test_case_ordering.c | 63 + .../bpf/progs/btf_dump_test_case_packing.c | 75 + .../bpf/progs/btf_dump_test_case_padding.c | 111 ++ .../bpf/progs/btf_dump_test_case_syntax.c | 229 +++ tools/testing/selftests/bpf/test_btf.c | 71 +- tools/testing/selftests/bpf/test_btf_dump.c | 143 ++ tools/testing/selftests/bpf/test_hashmap.c | 382 +++++ 23 files changed, 3306 insertions(+), 291 deletions(-) create mode 100644 tools/lib/bpf/btf_dump.c create mode 100644 tools/lib/bpf/hashmap.c create mode 100644 tools/lib/bpf/hashmap.h create mode 100644 tools/testing/selftests/bpf/progs/btf_dump_test_case_bitfields.c create mode 100644 tools/testing/selftests/bpf/progs/btf_dump_test_case_multidim.c create mode 100644 tools/testing/selftests/bpf/progs/btf_dump_test_case_namespacing.c create mode 100644 tools/testing/selftests/bpf/progs/btf_dump_test_case_ordering.c create mode 100644 tools/testing/selftests/bpf/progs/btf_dump_test_case_packing.c create mode 100644 tools/testing/selftests/bpf/progs/btf_dump_test_case_padding.c create mode 100644 tools/testing/selftests/bpf/progs/btf_dump_test_case_syntax.c create mode 100644 tools/testing/selftests/bpf/test_btf_dump.c create mode 100644 tools/testing/selftests/bpf/test_hashmap.c
Signature · 1 line
2.17.1
PATCH v3 1/12 libbpf: ensure libbpf.h is included along libbpf_internal.h
libbpf_internal.h expects a bunch of stuff defined in libbpf.h to be defined. This patch makes sure that libbpf.h is always included.
--- tools/lib/bpf/libbpf_internal.h | 2 ++ 1 file changed, 2 insertions(+)
tools/lib/bpf/libbpf_internal.h +2 -0
@@ -9,6 +9,8 @@#ifndef __LIBBPF_LIBBPF_INTERNAL_H#define __LIBBPF_LIBBPF_INTERNAL_H +#include "libbpf.h" +#define BTF_INFO_ENC (kind, kind_flag, vlen) \ ((!!(kind_flag) << 31) | ((kind) << 24) | ((vlen) & BTF_MAX_VLEN))#define BTF_TYPE_ENC (name, info, size_or_type) (name), (info), (size_or_type)
Signature · 1 line
2.17.1
PATCH v3 2/12 libbpf: add btf__parse_elf API to load .BTF and .BTF.ext
In reply to Andrii NakryikoLoading BTF and BTF.ext from ELF file is a common need. Instead of requiring every user to re-implement it, let's provide this API from libbpf itself. It's mostly copy/paste from bpftool btf dump implementation, which will be switched to libbpf's version in next patch. btf__parse_elf allows to load BTF and optionally BTF.ext. This is also useful for tests that need to load/work with BTF, loaded from test ELF files.
--- tools/lib/bpf/btf.c | 128 +++++++++++++++++++++++++++++++++++++++ tools/lib/bpf/btf.h | 2 + tools/lib/bpf/libbpf.map | 5 ++ 3 files changed, 135 insertions(+)
tools/lib/bpf/btf.c +128 -0
@@ -4,10 +4,12 @@#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"
@@ -417,6 +419,132 @@ struct btf *btf__new(__u8 *data, __u32 size)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;
tools/lib/bpf/btf.h +2 -0
@@ -59,6 +59,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,
tools/lib/bpf/libbpf.map +5 -0
@@ -164,3 +164,8 @@ LIBBPF_0.0.3 { bpf_map_freeze; btf__finalize_data; } LIBBPF_0.0.2; + +LIBBPF_0.0.4 { + global: + btf__parse_elf; +} LIBBPF_0.0.3;
Signature · 1 line
2.17.1
PATCH v3 3/12 bpftool: use libbpf's btf__parse_elf API
In reply to Andrii NakryikoUse btf__parse_elf() API, provided by libbpf, instead of implementing ELF parsing by itself.
--- tools/bpf/bpftool/btf.c | 117 +++------------------------------------- 1 file changed, 8 insertions(+), 109 deletions(-)
tools/bpf/bpftool/btf.c +8 -109
@@ -8,8 +8,8 @@#include <stdio.h> #include <string.h> #include <unistd.h> -#include <gelf.h> #include <bpf.h> +#include <libbpf.h> #include <linux/btf.h> #include "btf.h"
@@ -340,112 +340,6 @@ static int dump_btf_raw(const struct btf *btf,return 0 ; } -static bool check_btf_endianness (GElf_Ehdr *ehdr) -{ -static unsigned int const endian =1 ; - -switch (ehdr->e_ident[EI_DATA ]) { -case ELFDATA2LSB : -return *(unsigned char const *)&endian ==1 ; -case ELFDATA2MSB : -return *(unsigned char const *)&endian ==0 ; -default : -return 0 ; - } -} - -static int btf_load_from_elf (const char *path,struct btf **btf) -{ -int err =-1 , fd =-1 , idx =0 ; -Elf_Data *btf_data =NULL ; -Elf_Scn *scn =NULL ; -Elf *elf =NULL ; -GElf_Ehdr ehdr; - -if (elf_version (EV_CURRENT ) ==EV_NONE ) { -p_err ("failed to init libelf for %s" , path); -return -1 ; - } - - fd =open (path,O_RDONLY ); -if (fd <0 ) { -p_err ("failed to open %s: %s" , path,strerror (errno)); -return -1 ; - } - - elf =elf_begin (fd,ELF_C_READ ,NULL ); -if (!elf) { -p_err ("failed to open %s as ELF file" , path); - goto done; - } -if (!gelf_getehdr (elf, &ehdr)) { -p_err ("failed to get EHDR from %s" , path); - goto done; - } -if (!check_btf_endianness (&ehdr)) { -p_err ("non-native ELF endianness is not supported" ); - goto done; - } -if (!elf_rawdata (elf_getscn (elf, ehdr.e_shstrndx),NULL )) { -p_err ("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) { -p_err ("failed to get section(%d) header from %s" , - idx, path); - goto done; - } - name =elf_strptr (elf, ehdr.e_shstrndx, sh.sh_name); -if (!name) { -p_err ("failed to get section(%d) name from %s" , - idx, path); - goto done; - } -if (strcmp (name,BTF_ELF_SEC ) ==0 ) { - btf_data =elf_getdata (scn,0 ); -if (!btf_data) { -p_err ("failed to get section(%d, %s) data from %s" , - idx, name, path); - goto done; - } -break ; - } - } - -if (!btf_data) { -p_err ("%s ELF section not found in %s" ,BTF_ELF_SEC , path); - goto done; - } - - *btf =btf__new (btf_data->d_buf, btf_data->d_size); -if (IS_ERR (*btf)) { - err =PTR_ERR (*btf); - *btf =NULL ; -p_err ("failed to load BTF data from %s: %s" , - path,strerror (err)); - goto done; - } - - err =0 ; -done: -if (err) { -if (*btf) { -btf__free (*btf); - *btf =NULL ; - } - } -if (elf) -elf_end (elf); -close (fd); -return err; -} -static int do_dump (int argc,char **argv) {struct btf *btf =NULL ;
@@ -522,9 +416,14 @@ static int do_dump(int argc, char **argv) }NEXT_ARG (); }else if (is_prefix (src,"file" )) { - err =btf_load_from_elf (*argv, &btf); -if (err) + btf =btf__parse_elf (*argv,NULL ); +if (IS_ERR (btf)) { + err =PTR_ERR (btf); + btf =NULL ; +p_err ("failed to load BTF from %s: %s" , + *argv,strerror (err)); goto done; + }NEXT_ARG (); }else { err =-1 ;
Signature · 1 line
2.17.1
PATCH v3 4/12 selftests/bpf: use btf__parse_elf to check presence of BTF/BTF.ext
In reply to Andrii NakryikoSwitch test_btf.c to rely on btf__parse_elf to check presence of BTF and BTF.ext data, instead of implementing its own ELF parsing.
--- tools/testing/selftests/bpf/test_btf.c | 71 +++++--------------------- 1 file changed, 13 insertions(+), 58 deletions(-)
tools/testing/selftests/bpf/test_btf.c +13 -58
@@ -4025,62 +4025,13 @@ static struct btf_file_test file_tests[] = { }, }; -static int file_has_btf_elf (const char *fn,bool *has_btf_ext) -{ -Elf_Scn *scn =NULL ; -GElf_Ehdr ehdr; -int ret =0 ; -int elf_fd; -Elf *elf; - -if (CHECK (elf_version (EV_CURRENT ) ==EV_NONE , -"elf_version(EV_CURRENT) == EV_NONE" )) -return -1 ; - - elf_fd =open (fn,O_RDONLY ); -if (CHECK (elf_fd ==-1 ,"open(%s): errno:%d" , fn, errno)) -return -1 ; - - elf =elf_begin (elf_fd,ELF_C_READ ,NULL ); -if (CHECK (!elf,"elf_begin(%s): %s" , fn,elf_errmsg (elf_errno ()))) { - ret =-1 ; - goto done; - } - -if (CHECK (!gelf_getehdr (elf, &ehdr),"!gelf_getehdr(%s)" , fn)) { - ret =-1 ; - goto done; - } - -while ((scn =elf_nextscn (elf, scn))) { -const char *sh_name; -GElf_Shdr sh; - -if (CHECK (gelf_getshdr (scn, &sh) != &sh, -"file:%s gelf_getshdr != &sh" , fn)) { - ret =-1 ; - goto done; - } - - sh_name =elf_strptr (elf, ehdr.e_shstrndx, sh.sh_name); -if (!strcmp (sh_name,BTF_ELF_SEC )) - ret =1 ; -if (!strcmp (sh_name,BTF_EXT_ELF_SEC )) - *has_btf_ext = true; - } - -done: -close (elf_fd); -elf_end (elf); -return ret; -} -static int do_test_file (unsigned int test_num) {const struct btf_file_test *test = &file_tests[test_num -1 ];const char *expected_fnames[] = {"_dummy_tracepoint" ,"test_long_fname_1" ,"test_long_fname_2" }; +struct btf_ext *btf_ext =NULL ;struct bpf_prog_info info = {};struct bpf_object *obj =NULL ;struct bpf_func_info *finfo;
@@ -4095,15 +4046,19 @@ static int do_test_file(unsigned int test_num)fprintf (stderr,"BTF libbpf test[%u] (%s): " , test_num, test->file); - err =file_has_btf_elf (test->file, &has_btf_ext); -if (err ==-1 ) -return err; - -if (err ==0 ) { -fprintf (stderr,"SKIP. No ELF %s found" ,BTF_ELF_SEC ); - skip_cnt++; -return 0 ; + btf =btf__parse_elf (test->file, &btf_ext); +if (IS_ERR (btf)) { +if (PTR_ERR (btf) == -ENOENT ) { +fprintf (stderr,"SKIP. No ELF %s found" ,BTF_ELF_SEC ); + skip_cnt++; +return 0 ; + } +return PTR_ERR (btf); } +btf__free (btf); + + has_btf_ext = btf_ext !=NULL ; +btf_ext__free (btf_ext); obj =bpf_object__open (test->file);if (CHECK (IS_ERR (obj),"obj: %ld" ,PTR_ERR (obj)))
Signature · 1 line
2.17.1
PATCH v3 5/12 libbpf: add resizable non-thread safe internal hashmap
In reply to Andrii NakryikoThere is a need for fast point lookups inside libbpf for multiple use cases (e.g., name resolution for BTF-to-C conversion, by-name lookups in BTF for upcoming BPF CO-RE relocation support, etc). This patch implements simple resizable non-thread safe hashmap using single linked list chains.
Four different insert strategies are supported:
- HASHMAP_ADD - only add key/value if key doesn't exist yet;
- HASHMAP_SET - add key/value pair if key doesn't exist yet; otherwise, update value;
- HASHMAP_UPDATE - update value, if key already exists; otherwise, do nothing and return -ENOENT;
- HASHMAP_APPEND - always add key/value pair, even if key already exists. This turns hashmap into a multimap by allowing multiple values to be associated with the same key. Most useful read API for such hashmap is hashmap__for_each_key_entry() iteration. If hashmap__find() is still used, it will return last inserted key/value entry (first in a bucket chain).
For HASHMAP_SET and HASHMAP_UPDATE, old key/value pair is returned, so that calling code can handle proper memory management, if necessary.
--- tools/lib/bpf/Build | 2 +- tools/lib/bpf/hashmap.c | 229 ++++++++++++++++++++++++++++++++++++++++ tools/lib/bpf/hashmap.h | 173 ++++++++++++++++++++++++++++++ 3 files changed, 403 insertions(+), 1 deletion(-) create mode 100644 tools/lib/bpf/hashmap.c create mode 100644 tools/lib/bpf/hashmap.h
tools/lib/bpf/Build +1 -1
@@ -1 +1 @@ -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
tools/lib/bpf/hashmap.c new file +229 -0
229 lines not on this page · raw message
tools/lib/bpf/hashmap.h new file +173 -0
173 lines not on this page · raw message
Signature · 1 line
2.17.1
Re: [PATCH v3 bpf-next 05/12] libbpf: add resizable non-thread safe internal hashmap
Em Fri, May 24, 2019 at 11:59:00AM -0700, Andrii Nakryiko escreveu:
Quoted 5 lines
There is a need for fast point lookups inside libbpf for multiple use cases (e.g., name resolution for BTF-to-C conversion, by-name lookups in BTF for upcoming BPF CO-RE relocation support, etc). This patch implements simple resizable non-thread safe hashmap using single linked list chains.
This is breaking the tools/perf build in some systems where __WORDSIZE use in tools/lib/bpf/hashmap.h is not finding the definition of __WORDSIZE, which I think requires using:
#include <limits.h>
Or perhaps
#include <stdint.h>
Non-exhaustive search on a fedora:30 system:
[acme@quaco perf]$ grep "define.*__WORDSIZE" /usr/include/*/*.h /usr/include/bits/elfclass.h:#define __ELF_NATIVE_CLASS __WORDSIZE /usr/include/bits/siginfo-arch.h:#if defined __x86_64__ && __WORDSIZE == 32
/usr/include/bits/timesize.h:# define __TIMESIZE __WORDSIZE
/usr/include/bits/wordsize.h:# define __WORDSIZE 64
/usr/include/bits/wordsize.h:# define __WORDSIZE 32
/usr/include/bits/wordsize.h:#define __WORDSIZE32_SIZE_ULONG 0
/usr/include/bits/wordsize.h:#define __WORDSIZE32_PTRDIFF_LONG 0
/usr/include/bits/wordsize.h:# define __WORDSIZE_TIME64_COMPAT32 1
/usr/include/bits/wordsize.h:# define __WORDSIZE_TIME64_COMPAT32 0
[acme@quaco perf]$ grep bits\/wordsize.h /usr/include/*.h /usr/include/bfd.h:#include <bits/wordsize.h> /usr/include/limits.h:#include <bits/wordsize.h> /usr/include/pthread.h:#include <bits/wordsize.h> /usr/include/stdint.h:#include <bits/wordsize.h> /usr/include/tiffconf.h:#include <bits/wordsize.h>
[acme@quaco perf]$
On fedora:30 it works, probably because some header included from there ends up adding the file that has that def, but these fail, for instance:
[perfbuilder@quaco linux-perf-tools-build]$ export PERF_TARBALL=http://192.168.124.1/perf/perf-5.2.0.tar.xz [perfbuilder@quaco linux-perf-tools-build]$ time dm
1 13.57 alpine:3.4 : FAIL gcc (Alpine 5.3.0) 5.3.0, clang version 3.8.0 (tags/RELEASE_380/final) 2 13.78 alpine:3.5 : FAIL gcc (Alpine 6.2.1) 6.2.1 20160822, clang version 3.8.1 (tags/RELEASE_381/final) 3 12.42 alpine:3.6 : FAIL gcc (Alpine 6.3.0) 6.3.0, clang version 4.0.0 (tags/RELEASE_400/final) 4 15.01 alpine:3.7 : FAIL gcc (Alpine 6.4.0) 6.4.0, Alpine clang version 5.0.0 (tags/RELEASE_500/final) (based on LLVM 5.0.0) 5 13.80 alpine:3.8 : FAIL gcc (Alpine 6.4.0) 6.4.0, Alpine clang version 5.0.1 (tags/RELEASE_501/final) (based on LLVM 5.0.1) 6 15.37 alpine:3.9 : FAIL gcc (Alpine 8.3.0) 8.3.0, Alpine clang version 5.0.1 (tags/RELEASE_502/final) (based on LLVM 5.0.1) 7 15.10 alpine:3.10 : FAIL gcc (Alpine 8.3.0) 8.3.0, Alpine clang version 8.0.0 (tags/RELEASE_800/final) (based on LLVM 8.0.0) 8 15.26 alpine:edge : FAIL gcc (Alpine 8.3.0) 8.3.0, Alpine clang version 7.0.1 (tags/RELEASE_701/final) (based on LLVM 7.0.1)
9: amazonlinux:1^C
I'm trying to see if adding #include <limits.h> fixes the problems in all the distros in my container based build test suite.
Lets see with at least alpine:3.4:
Nope, didn't work, will try revisiting this tomorrow...
I'll let it build anyway to see if this fails in other systems/libcs, BTW, Alpine uses musl libc.
- Arnaldo
Quoted 448 lines
Four different insert strategies are supported:
-HASHMAP_ADD- only add key/value if key doesn't exist yet;
-HASHMAP_SET- add key/value pair if key doesn't exist yet; otherwise, update value;
-HASHMAP_UPDATE- update value, if key already exists; otherwise, do nothing and return-ENOENT;
-HASHMAP_APPEND- always add key/value pair, even if key already exists. This turns hashmap into a multimap by allowing multiple values to be associated with the same key. Most useful read API for such hashmap ishashmap__for_each_key_entry()iteration. Ifhashmap__find()is still used, it will return last inserted key/value entry (first in a bucket chain).For
HASHMAP_SETandHASHMAP_UPDATE, old key/value pair is returned, so that calling code can handle proper memory management, if necessary.Signed-off-by Andrii Nakryiko <[email protected]>--- tools/lib/bpf/Build | 2 +- tools/lib/bpf/hashmap.c | 229 ++++++++++++++++++++++++++++++++++++++++ tools/lib/bpf/hashmap.h | 173 ++++++++++++++++++++++++++++++ 3 files changed, 403 insertions(+), 1 deletion(-) create mode 100644 tools/lib/bpf/hashmap.c create mode 100644 tools/lib/bpf/hashmap.htools/lib/bpf/Build +1
-1@@ -1 +1 @@ -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.otools/lib/bpf/hashmap.c new file +229
-0@@ -0,0 +1,229 @@ +// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) + +/* +* Generic non-thread safe hash map implementation. +* +* Copyright (c) 2019 Facebook +*/ +#include <stdint.h> +#include <stdlib.h> +#include <stdio.h> +#include <errno.h> +#include <linux/err.h> +#include "hashmap.h" + +/* start with 4 buckets */ +#define HASHMAP_MIN_CAP_BITS 2 + +static void hashmap_add_entry (struct hashmap_entry **pprev, +struct hashmap_entry *entry) +{ + entry->next = *pprev; + *pprev = entry; +} + +static void hashmap_del_entry (struct hashmap_entry **pprev, +struct hashmap_entry *entry) +{ + *pprev = entry->next; + entry->next =NULL ; +} + +void hashmap__init (struct hashmap *map,hashmap_hash_fn hash_fn, +hashmap_equal_fn equal_fn,void *ctx) +{ + map->hash_fn = hash_fn; + map->equal_fn = equal_fn; + map->ctx = ctx; + + map->buckets =NULL ; + map->cap =0 ; + map->cap_bits =0 ; + map->sz =0 ; +} + +struct hashmap *hashmap__new (hashmap_hash_fn hash_fn, +hashmap_equal_fn equal_fn, +void *ctx) +{ +struct hashmap *map =malloc (sizeof (struct hashmap )); + +if (!map) +return ERR_PTR (-ENOMEM ); +hashmap__init (map, hash_fn, equal_fn, ctx); +return map; +} + +void hashmap__clear (struct hashmap *map) +{ +free (map->buckets); + map->cap = map->cap_bits = map->sz =0 ; +} + +void hashmap__free (struct hashmap *map) +{ +if (!map) +return ; + +hashmap__clear (map); +free (map); +} + +size_t hashmap__size (const struct hashmap *map) +{ +return map->sz; +} + +size_t hashmap__capacity (const struct hashmap *map) +{ +return map->cap; +} + +static bool hashmap_needs_to_grow (struct hashmap *map) +{ +/* grow if empty or more than 75% filled */ +return (map->cap ==0 ) || ((map->sz +1 ) *4 /3 > map->cap); +} + +static int hashmap_grow (struct hashmap *map) +{ +struct hashmap_entry **new_buckets; +struct hashmap_entry *cur, *tmp; +size_t new_cap_bits, new_cap; +size_t h; +int bkt; + + new_cap_bits = map->cap_bits +1 ; +if (new_cap_bits <HASHMAP_MIN_CAP_BITS ) + new_cap_bits =HASHMAP_MIN_CAP_BITS ; + + new_cap =1UL << new_cap_bits; + new_buckets =calloc (new_cap,sizeof (new_buckets[0 ])); +if (!new_buckets) +return -ENOMEM ; + +hashmap__for_each_entry_safe (map, cur, tmp, bkt) { + h =hash_bits (map->hash_fn (cur->key, map->ctx), new_cap_bits); +hashmap_add_entry (&new_buckets[h], cur); + } + + map->cap = new_cap; + map->cap_bits = new_cap_bits; +free (map->buckets); + map->buckets = new_buckets; + +return 0 ; +} + +static bool hashmap_find_entry (const struct hashmap *map, +const void *key,size_t hash, +struct hashmap_entry ***pprev, +struct hashmap_entry **entry) +{ +struct hashmap_entry *cur, **prev_ptr; + +if (!map->buckets) +return false; + +for (prev_ptr = &map->buckets[hash], cur = *prev_ptr; + cur; + prev_ptr = &cur->next, cur = cur->next) { +if (map->equal_fn (cur->key, key, map->ctx)) { +if (pprev) + *pprev = prev_ptr; + *entry = cur; +return true; + } + } + +return false; +} + +int hashmap__insert (struct hashmap *map,const void *key,void *value, +enum hashmap_insert_strategy strategy, +const void **old_key,void **old_value) +{ +struct hashmap_entry *entry; +size_t h; +int err; + +if (old_key) + *old_key =NULL ; +if (old_value) + *old_value =NULL ; + + h =hash_bits (map->hash_fn (key, map->ctx), map->cap_bits); +if (strategy !=HASHMAP_APPEND && +hashmap_find_entry (map, key, h,NULL , &entry)) { +if (old_key) + *old_key = entry->key; +if (old_value) + *old_value = entry->value; + +if (strategy ==HASHMAP_SET || strategy ==HASHMAP_UPDATE ) { + entry->key = key; + entry->value = value; +return 0 ; + }else if (strategy ==HASHMAP_ADD ) { +return -EEXIST ; + } + } + +if (strategy ==HASHMAP_UPDATE ) +return -ENOENT ; + +if (hashmap_needs_to_grow (map)) { + err =hashmap_grow (map); +if (err) +return err; + h =hash_bits (map->hash_fn (key, map->ctx), map->cap_bits); + } + + entry =malloc (sizeof (struct hashmap_entry )); +if (!entry) +return -ENOMEM ; + + entry->key = key; + entry->value = value; +hashmap_add_entry (&map->buckets[h], entry); + map->sz++; + +return 0 ; +} + +bool hashmap__find (const struct hashmap *map,const void *key,void **value) +{ +struct hashmap_entry *entry; +size_t h; + + h =hash_bits (map->hash_fn (key, map->ctx), map->cap_bits); +if (!hashmap_find_entry (map, key, h,NULL , &entry)) +return false; + +if (value) + *value = entry->value; +return true; +} + +bool hashmap__delete (struct hashmap *map,const void *key, +const void **old_key,void **old_value) +{ +struct hashmap_entry **pprev, *entry; +size_t h; + + h =hash_bits (map->hash_fn (key, map->ctx), map->cap_bits); +if (!hashmap_find_entry (map, key, h, &pprev, &entry)) +return false; + +if (old_key) + *old_key = entry->key; +if (old_value) + *old_value = entry->value; + +hashmap_del_entry (pprev, entry); +free (entry); + map->sz--; + +return true; +} +tools/lib/bpf/hashmap.h new file +173
-0@@ -0,0 +1,173 @@ +/* SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) */ + +/* +* Generic non-thread safe hash map implementation. +* +* Copyright (c) 2019 Facebook +*/ +#ifndef __LIBBPF_HASHMAP_H +#define __LIBBPF_HASHMAP_H + +#include <stdbool.h> +#include <stddef.h> +#include "libbpf_internal.h" + +static inline size_t hash_bits (size_t h,int bits) +{ +/* shuffle bits and return requested number of upper bits */ +return (h *11400714819323198485llu ) >> (__WORDSIZE - bits); +} + +typedef size_t (*hashmap_hash_fn )(const void *key,void *ctx); +typedef bool (*hashmap_equal_fn )(const void *key1,const void *key2,void *ctx); + +struct hashmap_entry { +const void *key; +void *value; +struct hashmap_entry *next; +}; + +struct hashmap { +hashmap_hash_fn hash_fn; +hashmap_equal_fn equal_fn; +void *ctx; + +struct hashmap_entry **buckets; +size_t cap; +size_t cap_bits; +size_t sz; +}; + +#define HASHMAP_INIT (hash_fn, equal_fn, ctx) { \ + .hash_fn = (hash_fn), \ + .equal_fn = (equal_fn), \ + .ctx = (ctx), \ + .buckets = NULL, \ + .cap = 0, \ + .cap_bits = 0, \ + .sz = 0, \ +} + +void hashmap__init (struct hashmap *map,hashmap_hash_fn hash_fn, +hashmap_equal_fn equal_fn,void *ctx); +struct hashmap *hashmap__new (hashmap_hash_fn hash_fn, +hashmap_equal_fn equal_fn, +void *ctx); +void hashmap__clear (struct hashmap *map); +void hashmap__free (struct hashmap *map); + +size_t hashmap__size (const struct hashmap *map); +size_t hashmap__capacity (const struct hashmap *map); + +/* +* Hashmap insertion strategy: +* - HASHMAP_ADD - only add key/value if key doesn't exist yet; +* - HASHMAP_SET - add key/value pair if key doesn't exist yet; otherwise, +* update value; +* - HASHMAP_UPDATE - update value, if key already exists; otherwise, do +* nothing and return -ENOENT; +* - HASHMAP_APPEND - always add key/value pair, even if key already exists. +* This turns hashmap into a multimap by allowing multiple values to be +* associated with the same key. Most useful read API for such hashmap is +* hashmap__for_each_key_entry() iteration. If hashmap__find() is still +* used, it will return last inserted key/value entry (first in a bucket +* chain). +*/ +enum hashmap_insert_strategy { +HASHMAP_ADD , +HASHMAP_SET , +HASHMAP_UPDATE , +HASHMAP_APPEND , +}; + +/* +* hashmap__insert() adds key/value entry w/ various semantics, depending on +* provided strategy value. If a given key/value pair replaced already +* existing key/value pair, both old key and old value will be returned +* through old_key and old_value to allow calling code do proper memory +* management. +*/ +int hashmap__insert (struct hashmap *map,const void *key,void *value, +enum hashmap_insert_strategy strategy, +const void **old_key,void **old_value); + +static inline int hashmap__add (struct hashmap *map, +const void *key,void *value) +{ +return hashmap__insert (map, key, value,HASHMAP_ADD ,NULL ,NULL ); +} + +static inline int hashmap__set (struct hashmap *map, +const void *key,void *value, +const void **old_key,void **old_value) +{ +return hashmap__insert (map, key, value,HASHMAP_SET , + old_key, old_value); +} + +static inline int hashmap__update (struct hashmap *map, +const void *key,void *value, +const void **old_key,void **old_value) +{ +return hashmap__insert (map, key, value,HASHMAP_UPDATE , + old_key, old_value); +} + +static inline int hashmap__append (struct hashmap *map, +const void *key,void *value) +{ +return hashmap__insert (map, key, value,HASHMAP_APPEND ,NULL ,NULL ); +} + +bool hashmap__delete (struct hashmap *map,const void *key, +const void **old_key,void **old_value); + +bool hashmap__find (const struct hashmap *map,const void *key,void **value); + +/* +* hashmap__for_each_entry - iterate over all entries in hashmap +* @map: hashmap to iterate +* @cur: struct hashmap_entry * used as a loop cursor +* @bkt: integer used as a bucket loop cursor +*/ +#define hashmap__for_each_entry (map, cur, bkt) \ + for (bkt = 0; bkt < map->cap; bkt++) \ + for (cur = map->buckets[bkt]; cur; cur = cur->next) + +/* +* hashmap__for_each_entry_safe - iterate over all entries in hashmap, safe +* against removals +* @map: hashmap to iterate +* @cur: struct hashmap_entry * used as a loop cursor +* @tmp: struct hashmap_entry * used as a temporary next cursor storage +* @bkt: integer used as a bucket loop cursor +*/ +#define hashmap__for_each_entry_safe (map, cur, tmp, bkt) \ + for (bkt = 0; bkt < map->cap; bkt++) \ + for (cur = map->buckets[bkt]; \ + cur && ({tmp = cur->next; true; }); \ + cur = tmp) + +/* +* hashmap__for_each_key_entry - iterate over entries associated with given key +* @map: hashmap to iterate +* @cur: struct hashmap_entry * used as a loop cursor +* @key: key to iterate entries for +*/ +#define hashmap__for_each_key_entry (map, cur, _key) \ + for (cur = ({ size_t bkt = hash_bits(map->hash_fn((_key), map->ctx),\ + map->cap_bits); \ + map->buckets ? map->buckets[bkt] : NULL; }); \ + cur; \ + cur = cur->next) \ + if (map->equal_fn(cur->key, (_key), map->ctx)) + +#define hashmap__for_each_key_entry_safe (map, cur, tmp, _key) \ + for (cur = ({ size_t bkt = hash_bits(map->hash_fn((_key), map->ctx),\ + map->cap_bits); \ + cur = map->buckets ? map->buckets[bkt] : NULL; }); \ + cur && ({ tmp = cur->next; true; }); \ + cur = tmp) \ + if (map->equal_fn(cur->key, (_key), map->ctx)) + +#endif /* __LIBBPF_HASHMAP_H */ Signature · 1 line
2.17.1
Signature · 1 line
- Arnaldo
Re: [PATCH v3 bpf-next 05/12] libbpf: add resizable non-thread safe internal hashmap
Quoted 56 lines · Arnaldo Carvalho de Melo
Em Fri, May 24, 2019 at 11:59:00AM -0700, Andrii Nakryiko escreveu:
Quoted 5 lines
There is a need for fast point lookups inside libbpf for multiple use cases (e.g., name resolution for BTF-to-C conversion, by-name lookups in BTF for upcoming BPF CO-RE relocation support, etc). This patch implements simple resizable non-thread safe hashmap using single linked list chains.
This is breaking the
tools/perfbuild in some systems where__WORDSIZEuse intools/lib/bpf/hashmap.his not finding the definition of__WORDSIZE, which I think requires using:#include <
limits.h>Or perhaps
#include <
stdint.h>Non-exhaustive search on a fedora:30 system:
[acme@quaco perf]$ grep "define.*__WORDSIZE"
/usr/include/*/*.h/usr/include/bits/elfclass.h:#define__ELF_NATIVE_CLASS__WORDSIZE/usr/include/bits/siginfo-arch.h:#if defined__x86_64__&&__WORDSIZE== 32/usr/include/bits/timesize.h:# define __TIMESIZE __WORDSIZE /usr/include/bits/wordsize.h:# define __WORDSIZE 64 /usr/include/bits/wordsize.h:# define __WORDSIZE 32/usr/include/bits/wordsize.h:#define
__WORDSIZE32_SIZE_ULONG0
/usr/include/bits/wordsize.h:#define__WORDSIZE32_PTRDIFF_LONG0
/usr/include/bits/wordsize.h:# define__WORDSIZE_TIME64_COMPAT321
/usr/include/bits/wordsize.h:# define__WORDSIZE_TIME64_COMPAT320
[acme@quaco perf]$ grep bits\/wordsize.h/usr/include/*.h/usr/include/bfd.h:#include <bits/wordsize.h> /usr/include/limits.h:#include <bits/wordsize.h> /usr/include/pthread.h:#include <bits/wordsize.h> /usr/include/stdint.h:#include <bits/wordsize.h> /usr/include/tiffconf.h:#include <bits/wordsize.h> [acme@quaco perf]$On fedora:30 it works, probably because some header included from there ends up adding the file that has that def, but these fail, for instance:
[perfbuilder@quaco linux-perf-tools-build]$ export PERF_TARBALL=http://192.168.124.1/perf/perf-5.2.0.tar.xz [perfbuilder@quaco linux-perf-tools-build]$ time dm
1 13.57 alpine:3.4 : FAIL gcc (Alpine 5.3.0) 5.3.0, clang version 3.8.0 (tags/RELEASE_380/final) 2 13.78 alpine:3.5 : FAIL gcc (Alpine 6.2.1) 6.2.1 20160822, clang version 3.8.1 (tags/RELEASE_381/final) 3 12.42 alpine:3.6 : FAIL gcc (Alpine 6.3.0) 6.3.0, clang version 4.0.0 (tags/RELEASE_400/final) 4 15.01 alpine:3.7 : FAIL gcc (Alpine 6.4.0) 6.4.0, Alpine clang version 5.0.0 (tags/RELEASE_500/final) (based on LLVM 5.0.0) 5 13.80 alpine:3.8 : FAIL gcc (Alpine 6.4.0) 6.4.0, Alpine clang version 5.0.1 (tags/RELEASE_501/final) (based on LLVM 5.0.1) 6 15.37 alpine:3.9 : FAIL gcc (Alpine 8.3.0) 8.3.0, Alpine clang version 5.0.1 (tags/RELEASE_502/final) (based on LLVM 5.0.1) 7 15.10 alpine:3.10 : FAIL gcc (Alpine 8.3.0) 8.3.0, Alpine clang version 8.0.0 (tags/RELEASE_800/final) (based on LLVM 8.0.0) 8 15.26 alpine:edge : FAIL gcc (Alpine 8.3.0) 8.3.0, Alpine clang version 7.0.1 (tags/RELEASE_701/final) (based on LLVM 7.0.1)9: amazonlinux:1^C
I'm trying to see if adding #include <
limits.h> fixes the problems in all the distros in my container based build test suite.
Quoted 6 lines
Lets see with at least alpine:3.4:
Nope, didn't work, will try revisiting this tomorrow...
I'll let it build anyway to see if this fails in other systems/libcs, BTW, Alpine uses musl libc.
So it seems like __WORDSIZE is declared in bits/wordsize.h for glibc and in bits/reg.h for musl, so something like the following should fix this issue, but I can't easily verify. Can you please see if these changes fix the issue on your side?
#ifdef __GLIBC__
#include <bits/wordsize.h>
#else
#include <bits/reg.h>
#endif
Quoted 455 lines
- Arnaldo
Quoted 447 lines
Four different insert strategies are supported:
-HASHMAP_ADD- only add key/value if key doesn't exist yet;
-HASHMAP_SET- add key/value pair if key doesn't exist yet; otherwise, update value;
-HASHMAP_UPDATE- update value, if key already exists; otherwise, do nothing and return-ENOENT;
-HASHMAP_APPEND- always add key/value pair, even if key already exists. This turns hashmap into a multimap by allowing multiple values to be associated with the same key. Most useful read API for such hashmap ishashmap__for_each_key_entry()iteration. Ifhashmap__find()is still used, it will return last inserted key/value entry (first in a bucket chain).For
HASHMAP_SETandHASHMAP_UPDATE, old key/value pair is returned, so that calling code can handle proper memory management, if necessary.Signed-off-by Andrii Nakryiko <[email protected]>--- tools/lib/bpf/Build | 2 +- tools/lib/bpf/hashmap.c | 229 ++++++++++++++++++++++++++++++++++++++++ tools/lib/bpf/hashmap.h | 173 ++++++++++++++++++++++++++++++ 3 files changed, 403 insertions(+), 1 deletion(-) create mode 100644 tools/lib/bpf/hashmap.c create mode 100644 tools/lib/bpf/hashmap.htools/lib/bpf/Build +1
-1@@ -1 +1 @@ -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.otools/lib/bpf/hashmap.c new file +229
-0@@ -0,0 +1,229 @@ +// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) + +/* +* Generic non-thread safe hash map implementation. +* +* Copyright (c) 2019 Facebook +*/ +#include <stdint.h> +#include <stdlib.h> +#include <stdio.h> +#include <errno.h> +#include <linux/err.h> +#include "hashmap.h" + +/* start with 4 buckets */ +#define HASHMAP_MIN_CAP_BITS 2 + +static void hashmap_add_entry (struct hashmap_entry **pprev, +struct hashmap_entry *entry) +{ + entry->next = *pprev; + *pprev = entry; +} + +static void hashmap_del_entry (struct hashmap_entry **pprev, +struct hashmap_entry *entry) +{ + *pprev = entry->next; + entry->next =NULL ; +} + +void hashmap__init (struct hashmap *map,hashmap_hash_fn hash_fn, +hashmap_equal_fn equal_fn,void *ctx) +{ + map->hash_fn = hash_fn; + map->equal_fn = equal_fn; + map->ctx = ctx; + + map->buckets =NULL ; + map->cap =0 ; + map->cap_bits =0 ; + map->sz =0 ; +} + +struct hashmap *hashmap__new (hashmap_hash_fn hash_fn, +hashmap_equal_fn equal_fn, +void *ctx) +{ +struct hashmap *map =malloc (sizeof (struct hashmap )); + +if (!map) +return ERR_PTR (-ENOMEM ); +hashmap__init (map, hash_fn, equal_fn, ctx); +return map; +} + +void hashmap__clear (struct hashmap *map) +{ +free (map->buckets); + map->cap = map->cap_bits = map->sz =0 ; +} + +void hashmap__free (struct hashmap *map) +{ +if (!map) +return ; + +hashmap__clear (map); +free (map); +} + +size_t hashmap__size (const struct hashmap *map) +{ +return map->sz; +} + +size_t hashmap__capacity (const struct hashmap *map) +{ +return map->cap; +} + +static bool hashmap_needs_to_grow (struct hashmap *map) +{ +/* grow if empty or more than 75% filled */ +return (map->cap ==0 ) || ((map->sz +1 ) *4 /3 > map->cap); +} + +static int hashmap_grow (struct hashmap *map) +{ +struct hashmap_entry **new_buckets; +struct hashmap_entry *cur, *tmp; +size_t new_cap_bits, new_cap; +size_t h; +int bkt; + + new_cap_bits = map->cap_bits +1 ; +if (new_cap_bits <HASHMAP_MIN_CAP_BITS ) + new_cap_bits =HASHMAP_MIN_CAP_BITS ; + + new_cap =1UL << new_cap_bits; + new_buckets =calloc (new_cap,sizeof (new_buckets[0 ])); +if (!new_buckets) +return -ENOMEM ; + +hashmap__for_each_entry_safe (map, cur, tmp, bkt) { + h =hash_bits (map->hash_fn (cur->key, map->ctx), new_cap_bits); +hashmap_add_entry (&new_buckets[h], cur); + } + + map->cap = new_cap; + map->cap_bits = new_cap_bits; +free (map->buckets); + map->buckets = new_buckets; + +return 0 ; +} + +static bool hashmap_find_entry (const struct hashmap *map, +const void *key,size_t hash, +struct hashmap_entry ***pprev, +struct hashmap_entry **entry) +{ +struct hashmap_entry *cur, **prev_ptr; + +if (!map->buckets) +return false; + +for (prev_ptr = &map->buckets[hash], cur = *prev_ptr; + cur; + prev_ptr = &cur->next, cur = cur->next) { +if (map->equal_fn (cur->key, key, map->ctx)) { +if (pprev) + *pprev = prev_ptr; + *entry = cur; +return true; + } + } + +return false; +} + +int hashmap__insert (struct hashmap *map,const void *key,void *value, +enum hashmap_insert_strategy strategy, +const void **old_key,void **old_value) +{ +struct hashmap_entry *entry; +size_t h; +int err; + +if (old_key) + *old_key =NULL ; +if (old_value) + *old_value =NULL ; + + h =hash_bits (map->hash_fn (key, map->ctx), map->cap_bits); +if (strategy !=HASHMAP_APPEND && +hashmap_find_entry (map, key, h,NULL , &entry)) { +if (old_key) + *old_key = entry->key; +if (old_value) + *old_value = entry->value; + +if (strategy ==HASHMAP_SET || strategy ==HASHMAP_UPDATE ) { + entry->key = key; + entry->value = value; +return 0 ; + }else if (strategy ==HASHMAP_ADD ) { +return -EEXIST ; + } + } + +if (strategy ==HASHMAP_UPDATE ) +return -ENOENT ; + +if (hashmap_needs_to_grow (map)) { + err =hashmap_grow (map); +if (err) +return err; + h =hash_bits (map->hash_fn (key, map->ctx), map->cap_bits); + } + + entry =malloc (sizeof (struct hashmap_entry )); +if (!entry) +return -ENOMEM ; + + entry->key = key; + entry->value = value; +hashmap_add_entry (&map->buckets[h], entry); + map->sz++; + +return 0 ; +} + +bool hashmap__find (const struct hashmap *map,const void *key,void **value) +{ +struct hashmap_entry *entry; +size_t h; + + h =hash_bits (map->hash_fn (key, map->ctx), map->cap_bits); +if (!hashmap_find_entry (map, key, h,NULL , &entry)) +return false; + +if (value) + *value = entry->value; +return true; +} + +bool hashmap__delete (struct hashmap *map,const void *key, +const void **old_key,void **old_value) +{ +struct hashmap_entry **pprev, *entry; +size_t h; + + h =hash_bits (map->hash_fn (key, map->ctx), map->cap_bits); +if (!hashmap_find_entry (map, key, h, &pprev, &entry)) +return false; + +if (old_key) + *old_key = entry->key; +if (old_value) + *old_value = entry->value; + +hashmap_del_entry (pprev, entry); +free (entry); + map->sz--; + +return true; +} +tools/lib/bpf/hashmap.h new file +173
-1@@ -0,0 +1,173 @@ +/* SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) */ + +/* +* Generic non-thread safe hash map implementation. +* +* Copyright (c) 2019 Facebook +*/ +#ifndef __LIBBPF_HASHMAP_H +#define __LIBBPF_HASHMAP_H + +#include <stdbool.h> +#include <stddef.h> +#include "libbpf_internal.h" + +static inline size_t hash_bits (size_t h,int bits) +{ +/* shuffle bits and return requested number of upper bits */ +return (h *11400714819323198485llu ) >> (__WORDSIZE - bits); +} + +typedef size_t (*hashmap_hash_fn )(const void *key,void *ctx); +typedef bool (*hashmap_equal_fn )(const void *key1,const void *key2,void *ctx); + +struct hashmap_entry { +const void *key; +void *value; +struct hashmap_entry *next; +}; + +struct hashmap { +hashmap_hash_fn hash_fn; +hashmap_equal_fn equal_fn; +void *ctx; + +struct hashmap_entry **buckets; +size_t cap; +size_t cap_bits; +size_t sz; +}; + +#define HASHMAP_INIT (hash_fn, equal_fn, ctx) { \ + .hash_fn = (hash_fn), \ + .equal_fn = (equal_fn), \ + .ctx = (ctx), \ + .buckets = NULL, \ + .cap = 0, \ + .cap_bits = 0, \ + .sz = 0, \ +} + +void hashmap__init (struct hashmap *map,hashmap_hash_fn hash_fn, +hashmap_equal_fn equal_fn,void *ctx); +struct hashmap *hashmap__new (hashmap_hash_fn hash_fn, +hashmap_equal_fn equal_fn, +void *ctx); +void hashmap__clear (struct hashmap *map); +void hashmap__free (struct hashmap *map); + +size_t hashmap__size (const struct hashmap *map); +size_t hashmap__capacity (const struct hashmap *map); + +/* +* Hashmap insertion strategy: +* - HASHMAP_ADD - only add key/value if key doesn't exist yet; +* - HASHMAP_SET - add key/value pair if key doesn't exist yet; otherwise, +* update value; +* - HASHMAP_UPDATE - update value, if key already exists; otherwise, do +* nothing and return -ENOENT; +* - HASHMAP_APPEND - always add key/value pair, even if key already exists. +* This turns hashmap into a multimap by allowing multiple values to be +* associated with the same key. Most useful read API for such hashmap is +* hashmap__for_each_key_entry() iteration. If hashmap__find() is still +* used, it will return last inserted key/value entry (first in a bucket +* chain). +*/ +enum hashmap_insert_strategy { +HASHMAP_ADD , +HASHMAP_SET , +HASHMAP_UPDATE , +HASHMAP_APPEND , +}; + +/* +* hashmap__insert() adds key/value entry w/ various semantics, depending on +* provided strategy value. If a given key/value pair replaced already +* existing key/value pair, both old key and old value will be returned +* through old_key and old_value to allow calling code do proper memory +* management. +*/ +int hashmap__insert (struct hashmap *map,const void *key,void *value, +enum hashmap_insert_strategy strategy, +const void **old_key,void **old_value); + +static inline int hashmap__add (struct hashmap *map, +const void *key,void *value) +{ +return hashmap__insert (map, key, value,HASHMAP_ADD ,NULL ,NULL ); +} + +static inline int hashmap__set (struct hashmap *map, +const void *key,void *value, +const void **old_key,void **old_value) +{ +return hashmap__insert (map, key, value,HASHMAP_SET , + old_key, old_value); +} + +static inline int hashmap__update (struct hashmap *map, +const void *key,void *value, +const void **old_key,void **old_value) +{ +return hashmap__insert (map, key, value,HASHMAP_UPDATE , + old_key, old_value); +} + +static inline int hashmap__append (struct hashmap *map, +const void *key,void *value) +{ +return hashmap__insert (map, key, value,HASHMAP_APPEND ,NULL ,NULL ); +} + +bool hashmap__delete (struct hashmap *map,const void *key, +const void **old_key,void **old_value); + +bool hashmap__find (const struct hashmap *map,const void *key,void **value); + +/* +* hashmap__for_each_entry - iterate over all entries in hashmap +* @map: hashmap to iterate +* @cur: struct hashmap_entry * used as a loop cursor +* @bkt: integer used as a bucket loop cursor +*/ +#define hashmap__for_each_entry (map, cur, bkt) \ + for (bkt = 0; bkt < map->cap; bkt++) \ + for (cur = map->buckets[bkt]; cur; cur = cur->next) + +/* +* hashmap__for_each_entry_safe - iterate over all entries in hashmap, safe +* against removals +* @map: hashmap to iterate +* @cur: struct hashmap_entry * used as a loop cursor +* @tmp: struct hashmap_entry * used as a temporary next cursor storage +* @bkt: integer used as a bucket loop cursor +*/ +#define hashmap__for_each_entry_safe (map, cur, tmp, bkt) \ + for (bkt = 0; bkt < map->cap; bkt++) \ + for (cur = map->buckets[bkt]; \ + cur && ({tmp = cur->next; true; }); \ + cur = tmp) + +/* +* hashmap__for_each_key_entry - iterate over entries associated with given key +* @map: hashmap to iterate +* @cur: struct hashmap_entry * used as a loop cursor +* @key: key to iterate entries for +*/ +#define hashmap__for_each_key_entry (map, cur, _key) \ + for (cur = ({ size_t bkt = hash_bits(map->hash_fn((_key), map->ctx),\ + map->cap_bits); \ + map->buckets ? map->buckets[bkt] : NULL; }); \ + cur; \ + cur = cur->next) \ + if (map->equal_fn(cur->key, (_key), map->ctx)) + +#define hashmap__for_each_key_entry_safe (map, cur, tmp, _key) \ + for (cur = ({ size_t bkt = hash_bits(map->hash_fn((_key), map->ctx),\ + map->cap_bits); \ + cur = map->buckets ? map->buckets[bkt] : NULL; }); \ + cur && ({ tmp = cur->next; true; }); \ + cur = tmp) \ + if (map->equal_fn(cur->key, (_key), map->ctx)) + +#endif /* __LIBBPF_HASHMAP_H */ --Quoted 1 line
2.17.1
--
- Arnaldo
PATCH v3 6/12 selftests/bpf: add tests for libbpf's hashmap
In reply to Andrii NakryikoTest all APIs for internal hashmap implementation.
--- tools/testing/selftests/bpf/.gitignore | 1 + tools/testing/selftests/bpf/Makefile | 2 +- tools/testing/selftests/bpf/test_hashmap.c | 382 +++++++++++++++++++++ 3 files changed, 384 insertions(+), 1 deletion(-) create mode 100644 tools/testing/selftests/bpf/test_hashmap.c
tools/testing/selftests/bpf/.gitignore +1 -0
@@ -35,3 +35,4 @@ test_sysctl alu32 libbpf.pc libbpf.so.* +test_hashmap
tools/testing/selftests/bpf/Makefile +1 -1
@@ -23,7 +23,7 @@ TEST_GEN_PROGS = test_verifier test_tag test_maps test_lru_map test_lpm_map test test_align test_verifier_log test_dev_cgroup test_tcpbpf_user \ test_sock test_btf test_sockmap test_lirc_mode2_user get_cgroup_id_user \ test_socket_cookie test_cgroup_storage test_select_reuseport test_section_names \ - test_netcnt test_tcpnotify_user test_sock_fields test_sysctl + test_netcnt test_tcpnotify_user test_sock_fields test_sysctl test_hashmap BPF_OBJ_FILES = $(patsubst %.c,%.o, $(notdir $(wildcard progs/*.c))) TEST_GEN_FILES = $(BPF_OBJ_FILES)
tools/testing/selftests/bpf/test_hashmap.c new file +382 -0
382 lines not on this page · raw message
Signature · 1 line
2.17.1
PATCH v3 7/12 libbpf: switch btf_dedup() to hashmap for dedup table
In reply to Andrii NakryikoUtilize libbpf's hashmap as a multimap fof dedup_table implementation.
--- tools/lib/bpf/btf.c | 201 +++++++++++++++++++------------------------- 1 file changed, 85 insertions(+), 116 deletions(-)
tools/lib/bpf/btf.c +85 -116
@@ -14,6 +14,7 @@#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))
@@ -1293,16 +1294,9 @@ int btf__dedup(struct btf *btf, struct btf_ext *btf_ext,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;
@@ -1318,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 */
@@ -1343,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,
@@ -1395,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 ;
@@ -1438,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; }
@@ -1790,9 +1749,9 @@ static int btf_dedup_strings(struct btf_dedup *d)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);
@@ -1808,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);
@@ -1831,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);
@@ -1885,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++) {
@@ -1932,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);
@@ -1986,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++) {
@@ -2008,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;
@@ -2034,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;
@@ -2065,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 :
@@ -2088,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 ; } }
@@ -2099,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)
@@ -2110,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 ; } }
@@ -2525,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 )
@@ -2543,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;/*
@@ -2556,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 ; }
@@ -2616,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 ;
@@ -2644,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 ; } }
@@ -2667,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 ; } }
@@ -2698,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 ; } }
@@ -2728,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 ; }
Signature · 1 line
2.17.1
PATCH v3 8/12 libbpf: add btf_dump API for BTF-to-C conversion
In reply to Andrii NakryikoBTF contains enough type information to allow generating valid compilable C header w/ correct layout of structs/unions and all the typedef/enum definitions. This patch adds a new "object" - btf_dump to facilitate dumping BTF as valid C. btf_dump__dump_type() is the main API which takes care of dumping out (through user-provided printf-like callback function) C definitions for given type ID and it's required dependencies. This allows for not just dumping out entirety of BTF types, but also selective filtering based on user-provided criterias w/ minimal set of dependent types.
--- tools/lib/bpf/Build | 4 +- tools/lib/bpf/btf.h | 17 + tools/lib/bpf/btf_dump.c | 1336 ++++++++++++++++++++++++++++++++++++++ tools/lib/bpf/libbpf.map | 3 + 4 files changed, 1359 insertions(+), 1 deletion(-) create mode 100644 tools/lib/bpf/btf_dump.c
tools/lib/bpf/Build +3 -1
@@ -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 hashmap.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
tools/lib/bpf/btf.h +17 -0
@@ -4,6 +4,7 @@#ifndef __LIBBPF_BTF_H#define __LIBBPF_BTF_H +#include <stdarg.h> #include <linux/types.h> #ifdef __cplusplus
@@ -102,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
tools/lib/bpf/btf_dump.c new file +1336 -0
1,336 lines not on this page · raw message
tools/lib/bpf/libbpf.map +3 -0
@@ -167,5 +167,8 @@ LIBBPF_0.0.3 { LIBBPF_0.0.4 { global: + btf_dump__dump_type; + btf_dump__free; + btf_dump__new; btf__parse_elf; } LIBBPF_0.0.3;
Signature · 1 line
2.17.1
PATCH v3 9/12 selftests/bpf: add btf_dump BTF-to-C conversion tests
In reply to Andrii NakryikoAdd new test_btf_dump set of tests, validating BTF-to-C conversion correctness. Tests rely on clang to generate BTF from provided C test cases.
--- tools/testing/selftests/bpf/.gitignore | 1 + tools/testing/selftests/bpf/Makefile | 3 +- .../bpf/progs/btf_dump_test_case_bitfields.c | 92 +++++++ .../bpf/progs/btf_dump_test_case_multidim.c | 35 +++ .../progs/btf_dump_test_case_namespacing.c | 73 ++++++ .../bpf/progs/btf_dump_test_case_ordering.c | 63 +++++ .../bpf/progs/btf_dump_test_case_packing.c | 75 ++++++ .../bpf/progs/btf_dump_test_case_padding.c | 111 +++++++++ .../bpf/progs/btf_dump_test_case_syntax.c | 229 ++++++++++++++++++ tools/testing/selftests/bpf/test_btf_dump.c | 143 +++++++++++ 10 files changed, 824 insertions(+), 1 deletion(-) create mode 100644 tools/testing/selftests/bpf/progs/btf_dump_test_case_bitfields.c create mode 100644 tools/testing/selftests/bpf/progs/btf_dump_test_case_multidim.c create mode 100644 tools/testing/selftests/bpf/progs/btf_dump_test_case_namespacing.c create mode 100644 tools/testing/selftests/bpf/progs/btf_dump_test_case_ordering.c create mode 100644 tools/testing/selftests/bpf/progs/btf_dump_test_case_packing.c create mode 100644 tools/testing/selftests/bpf/progs/btf_dump_test_case_padding.c create mode 100644 tools/testing/selftests/bpf/progs/btf_dump_test_case_syntax.c create mode 100644 tools/testing/selftests/bpf/test_btf_dump.c
tools/testing/selftests/bpf/.gitignore +1 -0
@@ -36,3 +36,4 @@ alu32 libbpf.pc libbpf.so.* test_hashmap +test_btf_dump
tools/testing/selftests/bpf/Makefile +2 -1
@@ -23,7 +23,8 @@ TEST_GEN_PROGS = test_verifier test_tag test_maps test_lru_map test_lpm_map test test_align test_verifier_log test_dev_cgroup test_tcpbpf_user \ test_sock test_btf test_sockmap test_lirc_mode2_user get_cgroup_id_user \ test_socket_cookie test_cgroup_storage test_select_reuseport test_section_names \ - test_netcnt test_tcpnotify_user test_sock_fields test_sysctl test_hashmap + test_netcnt test_tcpnotify_user test_sock_fields test_sysctl test_hashmap \ + test_btf_dump BPF_OBJ_FILES = $(patsubst %.c,%.o, $(notdir $(wildcard progs/*.c))) TEST_GEN_FILES = $(BPF_OBJ_FILES)
tools/testing/selftests/bpf/progs/btf_dump_test_case_bitfields.c new file +92 -0
92 lines not on this page · raw message
tools/testing/selftests/bpf/progs/btf_dump_test_case_multidim.c new file +35 -0
@@ -0,0 +1,35 @@ +// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) + +/* +* BTF-to-C dumper test for multi-dimensional array output. +* +* Copyright (c) 2019 Facebook +*/ +/* ----- START-EXPECTED-OUTPUT ----- */ +typedef int arr_t [2 ]; + +typedef int multiarr_t [3 ][4 ][5 ]; + +typedef int *ptr_arr_t [6 ]; + +typedef int *ptr_multiarr_t [7 ][8 ][9 ][10 ]; + +typedef int * (*fn_ptr_arr_t [11 ])(); + +typedef int * (*fn_ptr_multiarr_t [12 ][13 ])(); + +struct root_struct { +arr_t _1; +multiarr_t _2; +ptr_arr_t _3; +ptr_multiarr_t _4; +fn_ptr_arr_t _5; +fn_ptr_multiarr_t _6; +}; + +/* ------ END-EXPECTED-OUTPUT ------ */ + +int f (struct root_struct *s) +{ +return 0 ; +}
tools/testing/selftests/bpf/progs/btf_dump_test_case_namespacing.c new file +73 -0
73 lines not on this page · raw message
tools/testing/selftests/bpf/progs/btf_dump_test_case_ordering.c new file +63 -0
63 lines not on this page · raw message
tools/testing/selftests/bpf/progs/btf_dump_test_case_packing.c new file +75 -0
75 lines not on this page · raw message
tools/testing/selftests/bpf/progs/btf_dump_test_case_padding.c new file +111 -0
111 lines not on this page · raw message
tools/testing/selftests/bpf/progs/btf_dump_test_case_syntax.c new file +229 -0
229 lines not on this page · raw message
tools/testing/selftests/bpf/test_btf_dump.c new file +143 -0
143 lines not on this page · raw message
Signature · 1 line
2.17.1
PATCH v3 10/12 bpftool: add C output format option to btf dump subcommand
In reply to Andrii NakryikoUtilize new libbpf's btf_dump API to emit BTF as a C definitions.
--- tools/bpf/bpftool/btf.c | 75 +++++++++++++++++++++++++++++++++++++++-- 1 file changed, 73 insertions(+), 2 deletions(-)
tools/bpf/bpftool/btf.c +73 -2
@@ -340,11 +340,49 @@ static int dump_btf_raw(const struct btf *btf,return 0 ; } +static void __printf(2, 0) btf_dump_printf(void *ctx, + const char *fmt, va_list args) +{ +vfprintf (stdout, fmt, args); +} + +static int dump_btf_c (const struct btf *btf, +__u32 *root_type_ids,int root_type_cnt) +{ +struct btf_dump *d; +int err =0 , i; + + d =btf_dump__new (btf,NULL ,NULL , btf_dump_printf); +if (IS_ERR (d)) +return PTR_ERR (d); + +if (root_type_cnt) { +for (i =0 ; i < root_type_cnt; i++) { + err =btf_dump__dump_type (d, root_type_ids[i]); +if (err) + goto done; + } + }else { +int cnt =btf__get_nr_types (btf); + +for (i =1 ; i <= cnt; i++) { + err =btf_dump__dump_type (d, i); +if (err) + goto done; + } + } + +done: +btf_dump__free (d); +return err; +} +static int do_dump (int argc,char **argv) {struct btf *btf =NULL ;__u32 root_type_ids[2 ];int root_type_cnt =0 ; +bool dump_c = false;__u32 btf_id =-1 ;const char *src;int fd =-1 ;
@@ -431,6 +469,29 @@ static int do_dump(int argc, char **argv) goto done; } +while (argc) { +if (is_prefix (*argv,"format" )) { +NEXT_ARG (); +if (argc <1 ) { +p_err ("expecting value for 'format' option\n" ); + goto done; + } +if (strcmp (*argv,"c" ) ==0 ) { + dump_c = true; + }else if (strcmp (*argv,"raw" ) ==0 ) { + dump_c = false; + }else { +p_err ("unrecognized format specifier: '%s', possible values: raw, c" , + *argv); + goto done; + } +NEXT_ARG (); + }else { +p_err ("unrecognized option: '%s'" , *argv); + goto done; + } + } +if (!btf) { err =btf__get_from_id (btf_id, &btf);if (err) {
@@ -444,7 +505,16 @@ static int do_dump(int argc, char **argv) } } -dump_btf_raw (btf, root_type_ids, root_type_cnt); +if (dump_c) { +if (json_output) { +p_err ("JSON output for C-syntax dump is not supported" ); + err = -ENOTSUP ; + goto done; + } + err =dump_btf_c (btf, root_type_ids, root_type_cnt); + }else { + err =dump_btf_raw (btf, root_type_ids, root_type_cnt); + } done:close (fd);
@@ -460,10 +530,11 @@ static int do_help(int argc, char **argv) }fprintf (stderr, -"Usage: %s btf dump BTF_SRC\n" +"Usage: %s btf dump BTF_SRC [format FORMAT]\n" " %s btf help\n" "\n" " BTF_SRC := { id BTF_ID | prog PROG | map MAP [{key | value | kv | all}] | file FILE }\n" +" FORMAT := { raw | c }\n" " " HELP_SPEC_MAP "\n" " " HELP_SPEC_PROGRAM "\n" " " HELP_SPEC_OPTIONS "\n"
Signature · 1 line
2.17.1
Re: [PATCH v3 bpf-next 10/12] bpftool: add C output format option to btf dump subcommand
2019-05-24 11:59 UTC-0700 ~ Andrii Nakryiko <[email protected]>
Quoted 4 lines
Utilize new libbpf's
btf_dumpAPI to emit BTF as a C definitions.Acked-by Jakub Kicinski <[email protected]>Signed-off-by Andrii Nakryiko <[email protected]>
Thanks for the changes!
PATCH v3 11/12 bpftool/docs: add description of btf dump C option
In reply to Andrii NakryikoDocument optional **c** option for btf dump subcommand.
--- .../bpf/bpftool/Documentation/bpftool-btf.rst | 35 +++++++++++-------- 1 file changed, 20 insertions(+), 15 deletions(-)
tools/bpf/bpftool/Documentation/bpftool-btf.rst +20 -15
@@ -19,10 +19,11 @@ SYNOPSIS BTF COMMANDS ============= -| **bpftool** **btf dump** *BTF_SRC* +| **bpftool** **btf dump** *BTF_SRC* [**format** *FORMAT*] | **bpftool** **btf help** | | *BTF_SRC* := { **id** *BTF_ID* | **prog** *PROG* | **map** *MAP* [{**key** | **value** | **kv** | **all**}] | **file** *FILE* } +| *FORMAT* := { **raw** | **c** } | *MAP* := { **id** *MAP_ID* | **pinned** *FILE* } | *PROG* := { **id** *PROG_ID* | **pinned** *FILE* | **tag** *PROG_TAG* }
@@ -31,23 +32,27 @@ DESCRIPTION **bpftool btf dump** *BTF_SRC* Dump BTF entries from a given *BTF_SRC*. - When **id** is specified, BTF object with that ID will be - loaded and all its BTF types emitted. + When **id** is specified, BTF object with that ID will be + loaded and all its BTF types emitted. - When **map** is provided, it's expected that map has - associated BTF object with BTF types describing key and - value. It's possible to select whether to dump only BTF - type(s) associated with key (**key**), value (**value**), - both key and value (**kv**), or all BTF types present in - associated BTF object (**all**). If not specified, **kv** - is assumed. + When **map** is provided, it's expected that map has + associated BTF object with BTF types describing key and + value. It's possible to select whether to dump only BTF + type(s) associated with key (**key**), value (**value**), + both key and value (**kv**), or all BTF types present in + associated BTF object (**all**). If not specified, **kv** + is assumed. - When **prog** is provided, it's expected that program has - associated BTF object with BTF types. + When **prog** is provided, it's expected that program has + associated BTF object with BTF types. - When specifying *FILE*, an ELF file is expected, containing - .BTF section with well-defined BTF binary format data, - typically produced by clang or pahole. + When specifying *FILE*, an ELF file is expected, containing + .BTF section with well-defined BTF binary format data, + typically produced by clang or pahole. + + **format** option can be used to override default (raw) + output format. Raw (**raw**) or C-syntax (**c**) output + formats are supported. **bpftool btf help** Print short help message.
Signature · 1 line
2.17.1
Re: [PATCH v3 bpf-next 11/12] bpftool/docs: add description of btf dump C option
2019-05-24 11:59 UTC-0700 ~ Andrii Nakryiko <[email protected]>
Quoted 4 lines
Document optional **c** option for btf dump subcommand.
Cc Quentin Monnet <[email protected]>Signed-off-by Andrii Nakryiko <[email protected]>
PATCH v3 12/12 bpftool: update bash-completion w/ new c option for btf dump
In reply to Andrii NakryikoAdd bash completion for new C btf dump option.
--- tools/bpf/bpftool/bash-completion/bpftool | 21 +++++++++++++++++---- 1 file changed, 17 insertions(+), 4 deletions(-)
tools/bpf/bpftool/bash-completion/bpftool +17 -4
@@ -638,11 +638,24 @@ _bpftool() esac return 0 ;; + format) + COMPREPLY=( $( compgen -W "c raw" -- "$cur" ) ) + ;; *) - if [[ $cword == 6 ]] && [[ ${words[3]} == "map" ]]; then - COMPREPLY+=( $( compgen -W 'key value kv all' -- \ - "$cur" ) ) - fi + # emit extra options + case ${words[3]} in + id|file) + _bpftool_once_attr 'format' + ;; + map|prog) + if [[ ${words[3]} == "map" ]] && [[ $cword == 6 ]]; then + COMPREPLY+=( $( compgen -W "key value kv all" -- "$cur" ) ) + fi + _bpftool_once_attr 'format' + ;; + *) + ;; + esac return 0 ;; esac
Signature · 1 line
2.17.1
Re: [PATCH v3 bpf-next 12/12] bpftool: update bash-completion w/ new c option for btf dump
2019-05-24 11:59 UTC-0700 ~ Andrii Nakryiko <[email protected]>
Quoted 4 lines
Add bash completion for new C btf dump option.
Cc Quentin Monnet <[email protected]>Signed-off-by Andrii Nakryiko <[email protected]>
Quoted 8 lines · Andrii Nakryiko
This patch set adds BTF-to-C dumping APIs to libbpf, allowing to output a subset of BTF types as a compilable C type definitions. This is useful by itself, as raw BTF output is not easy to inspect and comprehend. But it's also a big part of BPF CO-RE (compile once - run everywhere) initiative aimed at allowing to write relocatable BPF programs, that won't require on-the-host kernel headers (and would be able to inspect internal kernel structures, not exposed through kernel headers).
Tested. Works. Applied. Thanks!