| Message ID | 20210325065322.3121605-1-yhs@fb.com (mailing list archive) |
|---|---|
| State | Not Applicable |
| Headers | show |
| Series | add option to merge more dwarf cu's into | expand |
| Context | Check | Description |
|---|---|---|
| netdev/tree_selection | success | Not a local patch |
On Wed, Mar 24, 2021 at 11:53 PM Yonghong Song <yhs@fb.com> wrote: > > Currently, types/tags hash table has fixed HASHTAGS__BITS = 15. > That means the number of buckets will be 1UL << 15 = 32768. > In my experiments, a thin-LTO built vmlinux has roughly 9M entries > in types table and 5.2M entries in tags table. So the number > of buckets is too less for an efficient lookup. This patch > refactored the code to allow the number of buckets to be changed. > > In addition, currently hashtags__fn(key) return value is > assigned to uint16_t. Change to uint32_t as in a later patch > the number of hashtag bits can be increased to be more than 16. > > Signed-off-by: Yonghong Song <yhs@fb.com> > --- > dwarf_loader.c | 48 +++++++++++++++++++++++++++++++++++++----------- > 1 file changed, 37 insertions(+), 11 deletions(-) > > diff --git a/dwarf_loader.c b/dwarf_loader.c > index c106919..a02ef23 100644 > --- a/dwarf_loader.c > +++ b/dwarf_loader.c > @@ -50,7 +50,12 @@ struct strings *strings; > #define DW_FORM_implicit_const 0x21 > #endif > > -#define hashtags__fn(key) hash_64(key, HASHTAGS__BITS) > +static uint32_t hashtags__bits = 15; > + > +uint32_t hashtags__fn(Dwarf_Off key) > +{ > + return hash_64(key, hashtags__bits); I vaguely remember pahole patch that updated hash function to use the same one as libbpf's hashmap is using. Arnaldo, wasn't that patch accepted? But more to the point, I think hashtags__fn() should probably preserve all 64 bits of the hash? > +} > > bool no_bitfield_type_recode = true; > > @@ -102,9 +107,6 @@ static void dwarf_tag__set_spec(struct dwarf_tag *dtag, dwarf_off_ref spec) > *(dwarf_off_ref *)(dtag + 1) = spec; > } > > -#define HASHTAGS__BITS 15 > -#define HASHTAGS__SIZE (1UL << HASHTAGS__BITS) > - > #define obstack_chunk_alloc malloc > #define obstack_chunk_free free > > @@ -118,22 +120,41 @@ static void *obstack_zalloc(struct obstack *obstack, size_t size) > } > > struct dwarf_cu { > - struct hlist_head hash_tags[HASHTAGS__SIZE]; > - struct hlist_head hash_types[HASHTAGS__SIZE]; > + struct hlist_head *hash_tags; > + struct hlist_head *hash_types; > struct obstack obstack; > struct cu *cu; > struct dwarf_cu *type_unit; > }; > > -static void dwarf_cu__init(struct dwarf_cu *dcu) > +static int dwarf_cu__init(struct dwarf_cu *dcu) > { > + uint64_t hashtags_size = 1UL << hashtags__bits; I wish pahole could just use libbpf's dynamically resized hashmap, instead of hard-coding maximum size like this :( Arnaldo, libbpf is not going to expose its hashmap as public API, but if you'd like to use it, feel free to just copy/paste the code. It hasn't change for a while and is unlikely to change (unless some day we decide to make more efficient open-addressing implementation). > + dcu->hash_tags = malloc(sizeof(struct hlist_head) * hashtags_size); > + if (!dcu->hash_tags) > + return -ENOMEM; > + > + dcu->hash_types = malloc(sizeof(struct hlist_head) * hashtags_size); > + if (!dcu->hash_types) { > + free(dcu->hash_tags); > + return -ENOMEM; > + } > + [...]
On 3/26/21 4:13 PM, Andrii Nakryiko wrote: > On Wed, Mar 24, 2021 at 11:53 PM Yonghong Song <yhs@fb.com> wrote: >> >> Currently, types/tags hash table has fixed HASHTAGS__BITS = 15. >> That means the number of buckets will be 1UL << 15 = 32768. >> In my experiments, a thin-LTO built vmlinux has roughly 9M entries >> in types table and 5.2M entries in tags table. So the number >> of buckets is too less for an efficient lookup. This patch >> refactored the code to allow the number of buckets to be changed. >> >> In addition, currently hashtags__fn(key) return value is >> assigned to uint16_t. Change to uint32_t as in a later patch >> the number of hashtag bits can be increased to be more than 16. >> >> Signed-off-by: Yonghong Song <yhs@fb.com> >> --- >> dwarf_loader.c | 48 +++++++++++++++++++++++++++++++++++++----------- >> 1 file changed, 37 insertions(+), 11 deletions(-) >> >> diff --git a/dwarf_loader.c b/dwarf_loader.c >> index c106919..a02ef23 100644 >> --- a/dwarf_loader.c >> +++ b/dwarf_loader.c >> @@ -50,7 +50,12 @@ struct strings *strings; >> #define DW_FORM_implicit_const 0x21 >> #endif >> >> -#define hashtags__fn(key) hash_64(key, HASHTAGS__BITS) >> +static uint32_t hashtags__bits = 15; >> + >> +uint32_t hashtags__fn(Dwarf_Off key) >> +{ >> + return hash_64(key, hashtags__bits); > > I vaguely remember pahole patch that updated hash function to use the > same one as libbpf's hashmap is using. Arnaldo, wasn't that patch > accepted? > > But more to the point, I think hashtags__fn() should probably preserve > all 64 bits of the hash? I don't know the context. If the purpose is to avoid future changes in case that the hashtags__bits > 32 happens, yes, the change may make sense. > >> +} >> >> bool no_bitfield_type_recode = true; >> >> @@ -102,9 +107,6 @@ static void dwarf_tag__set_spec(struct dwarf_tag *dtag, dwarf_off_ref spec) >> *(dwarf_off_ref *)(dtag + 1) = spec; >> } >> >> -#define HASHTAGS__BITS 15 >> -#define HASHTAGS__SIZE (1UL << HASHTAGS__BITS) >> - >> #define obstack_chunk_alloc malloc >> #define obstack_chunk_free free >> >> @@ -118,22 +120,41 @@ static void *obstack_zalloc(struct obstack *obstack, size_t size) >> } >> >> struct dwarf_cu { >> - struct hlist_head hash_tags[HASHTAGS__SIZE]; >> - struct hlist_head hash_types[HASHTAGS__SIZE]; >> + struct hlist_head *hash_tags; >> + struct hlist_head *hash_types; >> struct obstack obstack; >> struct cu *cu; >> struct dwarf_cu *type_unit; >> }; >> >> -static void dwarf_cu__init(struct dwarf_cu *dcu) >> +static int dwarf_cu__init(struct dwarf_cu *dcu) >> { >> + uint64_t hashtags_size = 1UL << hashtags__bits; > > I wish pahole could just use libbpf's dynamically resized hashmap, > instead of hard-coding maximum size like this :( > > Arnaldo, libbpf is not going to expose its hashmap as public API, but > if you'd like to use it, feel free to just copy/paste the code. It > hasn't change for a while and is unlikely to change (unless some day > we decide to make more efficient open-addressing implementation). > >> + dcu->hash_tags = malloc(sizeof(struct hlist_head) * hashtags_size); >> + if (!dcu->hash_tags) >> + return -ENOMEM; >> + >> + dcu->hash_types = malloc(sizeof(struct hlist_head) * hashtags_size); >> + if (!dcu->hash_types) { >> + free(dcu->hash_tags); >> + return -ENOMEM; >> + } >> + > > [...] >
Em Fri, Mar 26, 2021 at 04:26:20PM -0700, Yonghong Song escreveu: > > > On 3/26/21 4:13 PM, Andrii Nakryiko wrote: > > On Wed, Mar 24, 2021 at 11:53 PM Yonghong Song <yhs@fb.com> wrote: > > > > > > Currently, types/tags hash table has fixed HASHTAGS__BITS = 15. > > > That means the number of buckets will be 1UL << 15 = 32768. > > > In my experiments, a thin-LTO built vmlinux has roughly 9M entries > > > in types table and 5.2M entries in tags table. So the number > > > of buckets is too less for an efficient lookup. This patch > > > refactored the code to allow the number of buckets to be changed. > > > > > > In addition, currently hashtags__fn(key) return value is > > > assigned to uint16_t. Change to uint32_t as in a later patch > > > the number of hashtag bits can be increased to be more than 16. > > > > > > Signed-off-by: Yonghong Song <yhs@fb.com> > > > --- > > > dwarf_loader.c | 48 +++++++++++++++++++++++++++++++++++++----------- > > > 1 file changed, 37 insertions(+), 11 deletions(-) > > > > > > diff --git a/dwarf_loader.c b/dwarf_loader.c > > > index c106919..a02ef23 100644 > > > --- a/dwarf_loader.c > > > +++ b/dwarf_loader.c > > > @@ -50,7 +50,12 @@ struct strings *strings; > > > #define DW_FORM_implicit_const 0x21 > > > #endif > > > > > > -#define hashtags__fn(key) hash_64(key, HASHTAGS__BITS) > > > +static uint32_t hashtags__bits = 15; > > > + > > > +uint32_t hashtags__fn(Dwarf_Off key) > > > +{ > > > + return hash_64(key, hashtags__bits); > > > > I vaguely remember pahole patch that updated hash function to use the > > same one as libbpf's hashmap is using. Arnaldo, wasn't that patch > > accepted? I guess so: https://git.kernel.org/pub/scm/devel/pahole/pahole.git/commit/?id=9fecc77ed82d429fd3fe49ba275465813228e617 dwarf_loader: Use a better hashing function, from libbpf This hashing function[1] produces better hash table bucket distributions. The original hashing function always produced zeros in the three least significant bits. The new hashing function gives a modest performance boost: Original: 0:11.373s New: 0:11.110s for a performance improvement of ~2%. [1] From the hash function used in libbpf. Committer notes: Bill found the suboptimality of the hash function being used, Andrii suggested using the libbpf one, which ended up being better. Signed-off-by: Bill Wendling <morbo@google.com> Suggested-by: Andrii Nakryiko <andrii@kernel.org> Cc: bpf@vger.kernel.org Cc: dwarves@vger.kernel.org Signed-off-by: Arnaldo Carvalho de Melo <acme@redhat.com> > > But more to the point, I think hashtags__fn() should probably preserve > > all 64 bits of the hash? > > I don't know the context. If the purpose is to avoid future changes > in case that the hashtags__bits > 32 happens, yes, the change may > make sense. > > > > > > +} > > > > > > bool no_bitfield_type_recode = true; > > > > > > @@ -102,9 +107,6 @@ static void dwarf_tag__set_spec(struct dwarf_tag *dtag, dwarf_off_ref spec) > > > *(dwarf_off_ref *)(dtag + 1) = spec; > > > } > > > > > > -#define HASHTAGS__BITS 15 > > > -#define HASHTAGS__SIZE (1UL << HASHTAGS__BITS) > > > - > > > #define obstack_chunk_alloc malloc > > > #define obstack_chunk_free free > > > > > > @@ -118,22 +120,41 @@ static void *obstack_zalloc(struct obstack *obstack, size_t size) > > > } > > > > > > struct dwarf_cu { > > > - struct hlist_head hash_tags[HASHTAGS__SIZE]; > > > - struct hlist_head hash_types[HASHTAGS__SIZE]; > > > + struct hlist_head *hash_tags; > > > + struct hlist_head *hash_types; > > > struct obstack obstack; > > > struct cu *cu; > > > struct dwarf_cu *type_unit; > > > }; > > > > > > -static void dwarf_cu__init(struct dwarf_cu *dcu) > > > +static int dwarf_cu__init(struct dwarf_cu *dcu) > > > { > > > + uint64_t hashtags_size = 1UL << hashtags__bits; > > > > I wish pahole could just use libbpf's dynamically resized hashmap, > > instead of hard-coding maximum size like this :( > > > > Arnaldo, libbpf is not going to expose its hashmap as public API, but > > if you'd like to use it, feel free to just copy/paste the code. It > > hasn't change for a while and is unlikely to change (unless some day > > we decide to make more efficient open-addressing implementation). > > > > > + dcu->hash_tags = malloc(sizeof(struct hlist_head) * hashtags_size); > > > + if (!dcu->hash_tags) > > > + return -ENOMEM; > > > + > > > + dcu->hash_types = malloc(sizeof(struct hlist_head) * hashtags_size); > > > + if (!dcu->hash_types) { > > > + free(dcu->hash_tags); > > > + return -ENOMEM; > > > + } > > > + > > > > [...] > >
On Mon, Mar 29, 2021 at 7:02 AM Arnaldo Carvalho de Melo <acme@kernel.org> wrote: > > Em Fri, Mar 26, 2021 at 04:26:20PM -0700, Yonghong Song escreveu: > > > > > > On 3/26/21 4:13 PM, Andrii Nakryiko wrote: > > > On Wed, Mar 24, 2021 at 11:53 PM Yonghong Song <yhs@fb.com> wrote: > > > > > > > > Currently, types/tags hash table has fixed HASHTAGS__BITS = 15. > > > > That means the number of buckets will be 1UL << 15 = 32768. > > > > In my experiments, a thin-LTO built vmlinux has roughly 9M entries > > > > in types table and 5.2M entries in tags table. So the number > > > > of buckets is too less for an efficient lookup. This patch > > > > refactored the code to allow the number of buckets to be changed. > > > > > > > > In addition, currently hashtags__fn(key) return value is > > > > assigned to uint16_t. Change to uint32_t as in a later patch > > > > the number of hashtag bits can be increased to be more than 16. > > > > > > > > Signed-off-by: Yonghong Song <yhs@fb.com> > > > > --- > > > > dwarf_loader.c | 48 +++++++++++++++++++++++++++++++++++++----------- > > > > 1 file changed, 37 insertions(+), 11 deletions(-) > > > > > > > > diff --git a/dwarf_loader.c b/dwarf_loader.c > > > > index c106919..a02ef23 100644 > > > > --- a/dwarf_loader.c > > > > +++ b/dwarf_loader.c > > > > @@ -50,7 +50,12 @@ struct strings *strings; > > > > #define DW_FORM_implicit_const 0x21 > > > > #endif > > > > > > > > -#define hashtags__fn(key) hash_64(key, HASHTAGS__BITS) > > > > +static uint32_t hashtags__bits = 15; > > > > + > > > > +uint32_t hashtags__fn(Dwarf_Off key) > > > > +{ > > > > + return hash_64(key, hashtags__bits); > > > > > > I vaguely remember pahole patch that updated hash function to use the > > > same one as libbpf's hashmap is using. Arnaldo, wasn't that patch > > > accepted? > > I guess so: > > https://git.kernel.org/pub/scm/devel/pahole/pahole.git/commit/?id=9fecc77ed82d429fd3fe49ba275465813228e617 Oh, my bad. I fetched the latest master but didn't notice that I had some local changes that conflicted, so my master didn't actually update. Sorry about the noise. > > dwarf_loader: Use a better hashing function, from libbpf > > This hashing function[1] produces better hash table bucket > distributions. The original hashing function always produced zeros in > the three least significant bits. The new hashing function gives a > modest performance boost: > > Original: 0:11.373s > New: 0:11.110s > > for a performance improvement of ~2%. > > [1] From the hash function used in libbpf. > > Committer notes: > > Bill found the suboptimality of the hash function being used, Andrii > suggested using the libbpf one, which ended up being better. > > Signed-off-by: Bill Wendling <morbo@google.com> > Suggested-by: Andrii Nakryiko <andrii@kernel.org> > Cc: bpf@vger.kernel.org > Cc: dwarves@vger.kernel.org > Signed-off-by: Arnaldo Carvalho de Melo <acme@redhat.com> > > > > But more to the point, I think hashtags__fn() should probably preserve > > > all 64 bits of the hash? > > > > I don't know the context. If the purpose is to avoid future changes > > in case that the hashtags__bits > 32 happens, yes, the change may > > make sense. > > > > > > > > > +} > > > > > > > > bool no_bitfield_type_recode = true; > > > > > > > > @@ -102,9 +107,6 @@ static void dwarf_tag__set_spec(struct dwarf_tag *dtag, dwarf_off_ref spec) > > > > *(dwarf_off_ref *)(dtag + 1) = spec; > > > > } > > > > > > > > -#define HASHTAGS__BITS 15 > > > > -#define HASHTAGS__SIZE (1UL << HASHTAGS__BITS) > > > > - > > > > #define obstack_chunk_alloc malloc > > > > #define obstack_chunk_free free > > > > > > > > @@ -118,22 +120,41 @@ static void *obstack_zalloc(struct obstack *obstack, size_t size) > > > > } > > > > > > > > struct dwarf_cu { > > > > - struct hlist_head hash_tags[HASHTAGS__SIZE]; > > > > - struct hlist_head hash_types[HASHTAGS__SIZE]; > > > > + struct hlist_head *hash_tags; > > > > + struct hlist_head *hash_types; > > > > struct obstack obstack; > > > > struct cu *cu; > > > > struct dwarf_cu *type_unit; > > > > }; > > > > > > > > -static void dwarf_cu__init(struct dwarf_cu *dcu) > > > > +static int dwarf_cu__init(struct dwarf_cu *dcu) > > > > { > > > > + uint64_t hashtags_size = 1UL << hashtags__bits; > > > > > > I wish pahole could just use libbpf's dynamically resized hashmap, > > > instead of hard-coding maximum size like this :( > > > > > > Arnaldo, libbpf is not going to expose its hashmap as public API, but > > > if you'd like to use it, feel free to just copy/paste the code. It > > > hasn't change for a while and is unlikely to change (unless some day > > > we decide to make more efficient open-addressing implementation). > > > > > > > + dcu->hash_tags = malloc(sizeof(struct hlist_head) * hashtags_size); > > > > + if (!dcu->hash_tags) > > > > + return -ENOMEM; > > > > + > > > > + dcu->hash_types = malloc(sizeof(struct hlist_head) * hashtags_size); > > > > + if (!dcu->hash_types) { > > > > + free(dcu->hash_tags); > > > > + return -ENOMEM; > > > > + } > > > > + > > > > > > [...] > > > > > -- > > - Arnaldo
diff --git a/dwarf_loader.c b/dwarf_loader.c index c106919..a02ef23 100644 --- a/dwarf_loader.c +++ b/dwarf_loader.c @@ -50,7 +50,12 @@ struct strings *strings; #define DW_FORM_implicit_const 0x21 #endif -#define hashtags__fn(key) hash_64(key, HASHTAGS__BITS) +static uint32_t hashtags__bits = 15; + +uint32_t hashtags__fn(Dwarf_Off key) +{ + return hash_64(key, hashtags__bits); +} bool no_bitfield_type_recode = true; @@ -102,9 +107,6 @@ static void dwarf_tag__set_spec(struct dwarf_tag *dtag, dwarf_off_ref spec) *(dwarf_off_ref *)(dtag + 1) = spec; } -#define HASHTAGS__BITS 15 -#define HASHTAGS__SIZE (1UL << HASHTAGS__BITS) - #define obstack_chunk_alloc malloc #define obstack_chunk_free free @@ -118,22 +120,41 @@ static void *obstack_zalloc(struct obstack *obstack, size_t size) } struct dwarf_cu { - struct hlist_head hash_tags[HASHTAGS__SIZE]; - struct hlist_head hash_types[HASHTAGS__SIZE]; + struct hlist_head *hash_tags; + struct hlist_head *hash_types; struct obstack obstack; struct cu *cu; struct dwarf_cu *type_unit; }; -static void dwarf_cu__init(struct dwarf_cu *dcu) +static int dwarf_cu__init(struct dwarf_cu *dcu) { + uint64_t hashtags_size = 1UL << hashtags__bits; + dcu->hash_tags = malloc(sizeof(struct hlist_head) * hashtags_size); + if (!dcu->hash_tags) + return -ENOMEM; + + dcu->hash_types = malloc(sizeof(struct hlist_head) * hashtags_size); + if (!dcu->hash_types) { + free(dcu->hash_tags); + return -ENOMEM; + } + unsigned int i; - for (i = 0; i < HASHTAGS__SIZE; ++i) { + for (i = 0; i < hashtags_size; ++i) { INIT_HLIST_HEAD(&dcu->hash_tags[i]); INIT_HLIST_HEAD(&dcu->hash_types[i]); } obstack_init(&dcu->obstack); dcu->type_unit = NULL; + return 0; +} + +static void dwarf_cu__delete(struct cu *cu) +{ + struct dwarf_cu *dcu = cu->priv; + free(dcu->hash_tags); + free(dcu->hash_types); } static void hashtags__hash(struct hlist_head *hashtable, @@ -151,7 +172,7 @@ static struct dwarf_tag *hashtags__find(const struct hlist_head *hashtable, struct dwarf_tag *tpos; struct hlist_node *pos; - uint16_t bucket = hashtags__fn(id); + uint32_t bucket = hashtags__fn(id); const struct hlist_head *head = hashtable + bucket; hlist_for_each_entry(tpos, pos, head, hash_node) { @@ -2429,7 +2450,9 @@ static int cus__load_debug_types(struct cus *cus, struct conf_load *conf, } cu->little_endian = ehdr.e_ident[EI_DATA] == ELFDATA2LSB; - dwarf_cu__init(dcup); + if (dwarf_cu__init(dcup) != 0) + return DWARF_CB_ABORT; + dcup->cu = cu; /* Funny hack. */ dcup->type_unit = dcup; @@ -2521,7 +2544,9 @@ static int cus__load_module(struct cus *cus, struct conf_load *conf, struct dwarf_cu dcu; - dwarf_cu__init(&dcu); + if (dwarf_cu__init(&dcu) != 0) + return DWARF_CB_ABORT; + dcu.cu = cu; dcu.type_unit = type_cu ? &type_dcu : NULL; cu->priv = &dcu; @@ -2672,5 +2697,6 @@ struct debug_fmt_ops dwarf__ops = { .tag__decl_file = dwarf_tag__decl_file, .tag__decl_line = dwarf_tag__decl_line, .tag__orig_id = dwarf_tag__orig_id, + .cu__delete = dwarf_cu__delete, .has_alignment_info = true, };
Currently, types/tags hash table has fixed HASHTAGS__BITS = 15. That means the number of buckets will be 1UL << 15 = 32768. In my experiments, a thin-LTO built vmlinux has roughly 9M entries in types table and 5.2M entries in tags table. So the number of buckets is too less for an efficient lookup. This patch refactored the code to allow the number of buckets to be changed. In addition, currently hashtags__fn(key) return value is assigned to uint16_t. Change to uint32_t as in a later patch the number of hashtag bits can be increased to be more than 16. Signed-off-by: Yonghong Song <yhs@fb.com> --- dwarf_loader.c | 48 +++++++++++++++++++++++++++++++++++++----------- 1 file changed, 37 insertions(+), 11 deletions(-)