[RFC 0/1] Combining CUs into a single hash table

[RFC 0/1] Combining CUs into a single hash table

[Bill Wendling]

Hey gang,

I would like your feedback on this patch.

This patch creates one hash table that all CUs share. The impetus for this
patch is to support clang's LTO (Link-Time Optimizations). Currently, pahole
can't handle the DWARF data that clang produces, because the CUs may refer to
tags in other CUs (all of the code having been squozen together).

One solution I found is to process the CUs in two steps:

  1. add the CUs into a single hash table, and
  2. perform the recoding and finalization steps in a a separate step.

The issue I'm facing with this patch is that it balloons the runtime from
~11.11s to ~14.27s. It looks like the underlying cause is that some (but not
all) hash buckets have thousands of entries each. I've bumped up the
HASHTAGS__BITS from 15 to 16, which helped a little. Bumping it up to 17 or
above causes a failure.

A couple of things I thought of may help. We could increase the number of
buckets, which would help with distribution. As I mentioned though, that seemed
to cause a failure. Another option is to store the bucket entries in a
non-list, e.g. binary search tree.

I wanted to get your opinions before I trod down one of these roads.

Share and enjoy!
-bw

Bill Wendling (1):
  dwarf_loader: have all CUs use a single hash table

 dwarf_loader.c | 45 +++++++++++++++++++++++++++++++++------------
 1 file changed, 33 insertions(+), 12 deletions(-)

-- 
2.30.0.478.g8a0d178c01-goog

[RFC PATCH 1/1] dwarf_loader: have all CUs use a single hash table

[Bill Wendling]

In some instances, e.g. with clang's LTO, a DWARF compilation units may
reference tags in other CUs. This presents us with a "chicken and egg"
problem, where in order to properly process on CU we need access to the
tags in all CUs.

This increases the runtime by ~28% (from 11.11s to 14.27s).

Signed-off-by: Bill Wendling <morbo@google.com>
---
 dwarf_loader.c | 45 +++++++++++++++++++++++++++++++++------------
 1 file changed, 33 insertions(+), 12 deletions(-)

diff --git a/dwarf_loader.c b/dwarf_loader.c
index b73d786..2b0d619 100644
--- a/dwarf_loader.c
+++ b/dwarf_loader.c
@@ -102,7 +102,7 @@ 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__BITS 16
 #define HASHTAGS__SIZE (1UL << HASHTAGS__BITS)
 
 #define obstack_chunk_alloc malloc
@@ -117,21 +117,42 @@ static void *obstack_zalloc(struct obstack *obstack, size_t size)
 	return o;
 }
 
+/* The tags and types hashes used by all "dwarf_cu" objects. */
+struct dwarf_cu_hash {
+	struct hlist_head tags[HASHTAGS__SIZE];
+	struct hlist_head types[HASHTAGS__SIZE];
+};
+
 struct dwarf_cu {
-	struct hlist_head hash_tags[HASHTAGS__SIZE];
-	struct hlist_head hash_types[HASHTAGS__SIZE];
+	struct dwarf_cu_hash *hashes;
 	struct obstack obstack;
 	struct cu *cu;
 	struct dwarf_cu *type_unit;
 };
 
+static struct dwarf_cu_hash *dwarf_cu__init_hashes(void)
+{
+	static struct dwarf_cu_hash *hashes = NULL;
+
+	if (!hashes) {
+		unsigned int i;
+
+		hashes = malloc(sizeof(struct dwarf_cu_hash));
+		if (!hashes)
+			return NULL;
+
+		for (i = 0; i < HASHTAGS__SIZE; ++i) {
+			INIT_HLIST_HEAD(&hashes->tags[i]);
+			INIT_HLIST_HEAD(&hashes->types[i]);
+		}
+	}
+
+	return hashes;
+}
+
 static void dwarf_cu__init(struct dwarf_cu *dcu)
 {
-	unsigned int i;
-	for (i = 0; i < HASHTAGS__SIZE; ++i) {
-		INIT_HLIST_HEAD(&dcu->hash_tags[i]);
-		INIT_HLIST_HEAD(&dcu->hash_types[i]);
-	}
+	dcu->hashes = dwarf_cu__init_hashes();
 	obstack_init(&dcu->obstack);
 	dcu->type_unit = NULL;
 }
@@ -166,8 +187,8 @@ static void cu__hash(struct cu *cu, struct tag *tag)
 {
 	struct dwarf_cu *dcu = cu->priv;
 	struct hlist_head *hashtable = tag__is_tag_type(tag) ?
-							dcu->hash_types :
-							dcu->hash_tags;
+							dcu->hashes->types :
+							dcu->hashes->tags;
 	hashtags__hash(hashtable, tag->priv);
 }
 
@@ -179,7 +200,7 @@ static struct dwarf_tag *dwarf_cu__find_tag_by_ref(const struct dwarf_cu *cu,
 	if (ref->from_types) {
 		return NULL;
 	}
-	return hashtags__find(cu->hash_tags, ref->off);
+	return hashtags__find(cu->hashes->tags, ref->off);
 }
 
 static struct dwarf_tag *dwarf_cu__find_type_by_ref(const struct dwarf_cu *dcu,
@@ -193,7 +214,7 @@ static struct dwarf_tag *dwarf_cu__find_type_by_ref(const struct dwarf_cu *dcu,
 			return NULL;
 		}
 	}
-	return hashtags__find(dcu->hash_types, ref->off);
+	return hashtags__find(dcu->hashes->types, ref->off);
 }
 
 extern struct strings *strings;
-- 
2.30.0.478.g8a0d178c01-goog

Re: [RFC 0/1] Combining CUs into a single hash table

[Bill Wendling]

Bump for exposure.

On Fri, Feb 12, 2021 at 1:16 PM Bill Wendling <morbo@google.com> wrote:
>
> Hey gang,
>
> I would like your feedback on this patch.
>
> This patch creates one hash table that all CUs share. The impetus for this
> patch is to support clang's LTO (Link-Time Optimizations). Currently, pahole
> can't handle the DWARF data that clang produces, because the CUs may refer to
> tags in other CUs (all of the code having been squozen together).
>
> One solution I found is to process the CUs in two steps:
>
>   1. add the CUs into a single hash table, and
>   2. perform the recoding and finalization steps in a a separate step.
>
> The issue I'm facing with this patch is that it balloons the runtime from
> ~11.11s to ~14.27s. It looks like the underlying cause is that some (but not
> all) hash buckets have thousands of entries each. I've bumped up the
> HASHTAGS__BITS from 15 to 16, which helped a little. Bumping it up to 17 or
> above causes a failure.
>
> A couple of things I thought of may help. We could increase the number of
> buckets, which would help with distribution. As I mentioned though, that seemed
> to cause a failure. Another option is to store the bucket entries in a
> non-list, e.g. binary search tree.
>
> I wanted to get your opinions before I trod down one of these roads.
>
> Share and enjoy!
> -bw
>
> Bill Wendling (1):
>   dwarf_loader: have all CUs use a single hash table
>
>  dwarf_loader.c | 45 +++++++++++++++++++++++++++++++++------------
>  1 file changed, 33 insertions(+), 12 deletions(-)
>
> --
> 2.30.0.478.g8a0d178c01-goog
>

Re: [RFC 0/1] Combining CUs into a single hash table

[Arnaldo Carvalho de Melo]

Em Tue, Feb 23, 2021 at 12:44:58PM -0800, Bill Wendling escreveu:
> Bump for exposure.

While preparing my presentation for devconf.cz I stumbled on a problem
with split btf, I want to first bisect this before publishing...

I'll move this to the front of my priority list and inform here about it
ASAP.

- Arnaldo

 
> On Fri, Feb 12, 2021 at 1:16 PM Bill Wendling <morbo@google.com> wrote:
> >
> > Hey gang,
> >
> > I would like your feedback on this patch.
> >
> > This patch creates one hash table that all CUs share. The impetus for this
> > patch is to support clang's LTO (Link-Time Optimizations). Currently, pahole
> > can't handle the DWARF data that clang produces, because the CUs may refer to
> > tags in other CUs (all of the code having been squozen together).
> >
> > One solution I found is to process the CUs in two steps:
> >
> >   1. add the CUs into a single hash table, and
> >   2. perform the recoding and finalization steps in a a separate step.
> >
> > The issue I'm facing with this patch is that it balloons the runtime from
> > ~11.11s to ~14.27s. It looks like the underlying cause is that some (but not
> > all) hash buckets have thousands of entries each. I've bumped up the
> > HASHTAGS__BITS from 15 to 16, which helped a little. Bumping it up to 17 or
> > above causes a failure.
> >
> > A couple of things I thought of may help. We could increase the number of
> > buckets, which would help with distribution. As I mentioned though, that seemed
> > to cause a failure. Another option is to store the bucket entries in a
> > non-list, e.g. binary search tree.
> >
> > I wanted to get your opinions before I trod down one of these roads.
> >
> > Share and enjoy!
> > -bw
> >
> > Bill Wendling (1):
> >   dwarf_loader: have all CUs use a single hash table
> >
> >  dwarf_loader.c | 45 +++++++++++++++++++++++++++++++++------------
> >  1 file changed, 33 insertions(+), 12 deletions(-)
> >
> > --
> > 2.30.0.478.g8a0d178c01-goog
> >

-- 

- Arnaldo

Re: [RFC 0/1] Combining CUs into a single hash table

[Yonghong Song]

On 2/23/21 12:44 PM, Bill Wendling wrote:
> Bump for exposure.
> 
> On Fri, Feb 12, 2021 at 1:16 PM Bill Wendling <morbo@google.com> wrote:
>>
>> Hey gang,
>>
>> I would like your feedback on this patch.
>>
>> This patch creates one hash table that all CUs share. The impetus for this
>> patch is to support clang's LTO (Link-Time Optimizations). Currently, pahole
>> can't handle the DWARF data that clang produces, because the CUs may refer to
>> tags in other CUs (all of the code having been squozen together).

Hi, Bill,

LTO build support is now in linus tree 5.12 rc2 and also merged in 
latest bpf-next. I tried thin-LTO build and it is fine with latest
trunk llvm (llvm13) until it hits pahole and it stuck there (pahole 
1.20) probably some kind of infinite loop in pahole as pahole is
not ready to handle lto dwarf yet.

I then applied this patch on top of master pahole (1.20) and pahole
seg faulted. I did not debug. Have you hit the same issue?
How did you make pahole work with LTO built kernel?

Thanks!

Yonghong

>>
>> One solution I found is to process the CUs in two steps:
>>
>>    1. add the CUs into a single hash table, and
>>    2. perform the recoding and finalization steps in a a separate step.
>>
>> The issue I'm facing with this patch is that it balloons the runtime from
>> ~11.11s to ~14.27s. It looks like the underlying cause is that some (but not
>> all) hash buckets have thousands of entries each. I've bumped up the
>> HASHTAGS__BITS from 15 to 16, which helped a little. Bumping it up to 17 or
>> above causes a failure.
>>
>> A couple of things I thought of may help. We could increase the number of
>> buckets, which would help with distribution. As I mentioned though, that seemed
>> to cause a failure. Another option is to store the bucket entries in a
>> non-list, e.g. binary search tree.
>>
>> I wanted to get your opinions before I trod down one of these roads.
>>
>> Share and enjoy!
>> -bw
>>
>> Bill Wendling (1):
>>    dwarf_loader: have all CUs use a single hash table
>>
>>   dwarf_loader.c | 45 +++++++++++++++++++++++++++++++++------------
>>   1 file changed, 33 insertions(+), 12 deletions(-)
>>
>> --
>> 2.30.0.478.g8a0d178c01-goog
>>

Re: [RFC 0/1] Combining CUs into a single hash table

[Bill Wendling]

[-- Attachment #1: Type: text/plain, Size: 3000 bytes --]

On Sat, Mar 13, 2021 at 11:05 PM Yonghong Song <yhs@fb.com> wrote:
> On 2/23/21 12:44 PM, Bill Wendling wrote:
> > Bump for exposure.
> >
> > On Fri, Feb 12, 2021 at 1:16 PM Bill Wendling <morbo@google.com> wrote:
> >>
> >> Hey gang,
> >>
> >> I would like your feedback on this patch.
> >>
> >> This patch creates one hash table that all CUs share. The impetus for this
> >> patch is to support clang's LTO (Link-Time Optimizations). Currently, pahole
> >> can't handle the DWARF data that clang produces, because the CUs may refer to
> >> tags in other CUs (all of the code having been squozen together).
>
> Hi, Bill,
>
> LTO build support is now in linus tree 5.12 rc2 and also merged in
> latest bpf-next. I tried thin-LTO build and it is fine with latest
> trunk llvm (llvm13) until it hits pahole and it stuck there (pahole
> 1.20) probably some kind of infinite loop in pahole as pahole is
> not ready to handle lto dwarf yet.
>
> I then applied this patch on top of master pahole (1.20) and pahole
> seg faulted. I did not debug. Have you hit the same issue?
> How did you make pahole work with LTO built kernel?
>
Hi Yonghong,

I haven't tried this very much with top-of-tree Linux, but it's quite
possible that there's a segfaulting issue I haven't come across yet.
Make sure that you're using pahole v1.20, because it supports clang's
penchant for assigning some objects "null" names.

This patch is the first step in my attempt to get pahole working with
LTO. There's a follow-up patch that I'll attach to this email that
gets me through the compilation. It's not been heavily tested or
reviewed (it's in my local tree), so caveat emptor. I would love to
have people test it to see if it helps or just makes things worse.

Cheers!
-bw

> Thanks!
>
> Yonghong
>
> >>
> >> One solution I found is to process the CUs in two steps:
> >>
> >>    1. add the CUs into a single hash table, and
> >>    2. perform the recoding and finalization steps in a a separate step.
> >>
> >> The issue I'm facing with this patch is that it balloons the runtime from
> >> ~11.11s to ~14.27s. It looks like the underlying cause is that some (but not
> >> all) hash buckets have thousands of entries each. I've bumped up the
> >> HASHTAGS__BITS from 15 to 16, which helped a little. Bumping it up to 17 or
> >> above causes a failure.
> >>
> >> A couple of things I thought of may help. We could increase the number of
> >> buckets, which would help with distribution. As I mentioned though, that seemed
> >> to cause a failure. Another option is to store the bucket entries in a
> >> non-list, e.g. binary search tree.
> >>
> >> I wanted to get your opinions before I trod down one of these roads.
> >>
> >> Share and enjoy!
> >> -bw
> >>
> >> Bill Wendling (1):
> >>    dwarf_loader: have all CUs use a single hash table
> >>
> >>   dwarf_loader.c | 45 +++++++++++++++++++++++++++++++++------------
> >>   1 file changed, 33 insertions(+), 12 deletions(-)
> >>
> >> --
> >> 2.30.0.478.g8a0d178c01-goog
> >>

[-- Attachment #2: pahole.patch --]
[-- Type: application/octet-stream, Size: 2966 bytes --]

commit 866fac58f88d501ca23131830679d1f96625dda8
Author: Bill Wendling <morbo@google.com>
Date:   Fri Feb 12 14:05:19 2021 -0800

    dwarf_loader: perform the recoding and finalization separately
    
    Clang's LTO produces DWARF data where a CU may refer to tags in other
    CU. This means that we need all tags from every CU available during
    recoding and finalization. So we gather the tag data in one phase and
    use it in the following phase.
    
    Signed-off-by: Bill Wendling <morbo@google.com>

diff --git a/dwarf_loader.c b/dwarf_loader.c
index 2b0d619..e83b247 100644
--- a/dwarf_loader.c
+++ b/dwarf_loader.c
@@ -2261,14 +2261,6 @@ static int die__process(Dwarf_Die *die, struct cu *cu)
 	return 0;
 }
 
-static int die__process_and_recode(Dwarf_Die *die, struct cu *cu)
-{
-	int ret = die__process(die, cu);
-	if (ret != 0)
-		return ret;
-	return cu__recode_dwarf_types(cu);
-}
-
 static int class_member__cache_byte_size(struct tag *tag, struct cu *cu,
 					 void *cookie)
 {
@@ -2498,6 +2490,20 @@ static int cus__load_module(struct cus *cus, struct conf_load *conf,
 		}
 	}
 
+	/*
+	 * CUs may refer to tags and types located in other CUs. To support
+	 * this, we process the CUs in two steps.
+	 *
+	 *   - Collect the CUs and adds their types and tags entries into
+	 *     hashes shared between all CUs.
+	 *   - Then recode and finalize the CUs.
+	 */
+
+	/* A temporary list of all CU objects. */
+	struct cus *dcus = cus__new();
+	if (dcus == NULL)
+		return DWARF_CB_ABORT;
+
 	while (dwarf_nextcu(dw, off, &noff, &cuhl, NULL, &pointer_size,
 			    &offset_size) == 0) {
 		Dwarf_Die die_mem;
@@ -2528,24 +2534,41 @@ static int cus__load_module(struct cus *cus, struct conf_load *conf,
 		}
 		cu->little_endian = ehdr.e_ident[EI_DATA] == ELFDATA2LSB;
 
-		struct dwarf_cu dcu;
-
-		dwarf_cu__init(&dcu);
-		dcu.cu = cu;
-		dcu.type_unit = type_cu ? &type_dcu : NULL;
-		cu->priv = &dcu;
-		cu->dfops = &dwarf__ops;
-
-		if (die__process_and_recode(cu_die, cu) != 0)
+		struct dwarf_cu *dcu = malloc(sizeof(struct dwarf_cu));
+		if (dcu == NULL)
 			return DWARF_CB_ABORT;
 
-		if (finalize_cu_immediately(cus, cu, &dcu, conf)
-		    == LSK__STOP_LOADING)
+		dwarf_cu__init(dcu);
+		dcu->cu = cu;
+		dcu->type_unit = type_cu ? &type_dcu : NULL;
+		cu->priv = dcu;
+		cu->dfops = &dwarf__ops;
+
+		cus__add(dcus, cu);
+
+		if (die__process(cu_die, cu) != LSK__KEEPIT)
 			return DWARF_CB_ABORT;
 
 		off = noff;
 	}
 
+	/* Recode and finalize the CUs. */
+	struct cu *pos, *n;
+	list_for_each_entry_safe(pos, n, &dcus->cus, node) {
+		struct cu *cu = pos;
+		struct dwarf_cu *dcu = (struct dwarf_cu *)cu->priv;
+
+		if (cu__recode_dwarf_types(cu) != LSK__KEEPIT)
+			return DWARF_CB_ABORT;
+
+		if (finalize_cu_immediately(cus, cu, dcu, conf)
+		    == LSK__STOP_LOADING)
+			return DWARF_CB_ABORT;
+	}
+
+	/* We no longer need this list of CU objects. */
+	free(dcus);
+
 	if (type_lsk == LSK__DELETE)
 		cu__delete(type_cu);
 

Re: [RFC 0/1] Combining CUs into a single hash table

[Yonghong Song]

On 3/14/21 12:28 AM, Bill Wendling wrote:
> On Sat, Mar 13, 2021 at 11:05 PM Yonghong Song <yhs@fb.com> wrote:
>> On 2/23/21 12:44 PM, Bill Wendling wrote:
>>> Bump for exposure.
>>>
>>> On Fri, Feb 12, 2021 at 1:16 PM Bill Wendling <morbo@google.com> wrote:
>>>>
>>>> Hey gang,
>>>>
>>>> I would like your feedback on this patch.
>>>>
>>>> This patch creates one hash table that all CUs share. The impetus for this
>>>> patch is to support clang's LTO (Link-Time Optimizations). Currently, pahole
>>>> can't handle the DWARF data that clang produces, because the CUs may refer to
>>>> tags in other CUs (all of the code having been squozen together).
>>
>> Hi, Bill,
>>
>> LTO build support is now in linus tree 5.12 rc2 and also merged in
>> latest bpf-next. I tried thin-LTO build and it is fine with latest
>> trunk llvm (llvm13) until it hits pahole and it stuck there (pahole
>> 1.20) probably some kind of infinite loop in pahole as pahole is
>> not ready to handle lto dwarf yet.
>>
>> I then applied this patch on top of master pahole (1.20) and pahole
>> seg faulted. I did not debug. Have you hit the same issue?
>> How did you make pahole work with LTO built kernel?
>>
> Hi Yonghong,
> 
> I haven't tried this very much with top-of-tree Linux, but it's quite
> possible that there's a segfaulting issue I haven't come across yet.
> Make sure that you're using pahole v1.20, because it supports clang's
> penchant for assigning some objects "null" names.
> 
> This patch is the first step in my attempt to get pahole working with
> LTO. There's a follow-up patch that I'll attach to this email that
> gets me through the compilation. It's not been heavily tested or
> reviewed (it's in my local tree), so caveat emptor. I would love to
> have people test it to see if it helps or just makes things worse.

I applied you "Combining CUs into a single hash table" patch and
the attach patch, now pahole does not segfault any more, but I still
get the following pahole errors:

...
<ERROR(tag__size:1040): 1622 not found!>
<ERROR(tag__size:1040): 1617 not found!>
<ERROR(tag__size:1040): 1615 not found!>
error: found variable 'loaded_vmcss_on_cpu' in CU 
'/home/yhs/work/bpf-next/arch/x86/kvm/vmx/vmx.c' that has void type
Encountered error while encoding BTF.

FYI, I compiled latest bpf-next with the following command:
    make LLVM=1 LLVM_IAS=1 -j60
the compiler is locally built with latest upstream llvm-project.
I am using thin-lto in kernel config.

I will take a look at your patch and the issue next week,
hopefully we can resolve the issue soon. Thanks!

> 
> Cheers!
> -bw
> 
>> Thanks!
>>
>> Yonghong
>>
>>>>
>>>> One solution I found is to process the CUs in two steps:
>>>>
>>>>     1. add the CUs into a single hash table, and
>>>>     2. perform the recoding and finalization steps in a a separate step.
>>>>
>>>> The issue I'm facing with this patch is that it balloons the runtime from
>>>> ~11.11s to ~14.27s. It looks like the underlying cause is that some (but not
>>>> all) hash buckets have thousands of entries each. I've bumped up the
>>>> HASHTAGS__BITS from 15 to 16, which helped a little. Bumping it up to 17 or
>>>> above causes a failure.
>>>>
>>>> A couple of things I thought of may help. We could increase the number of
>>>> buckets, which would help with distribution. As I mentioned though, that seemed
>>>> to cause a failure. Another option is to store the bucket entries in a
>>>> non-list, e.g. binary search tree.
>>>>
>>>> I wanted to get your opinions before I trod down one of these roads.
>>>>
>>>> Share and enjoy!
>>>> -bw
>>>>
>>>> Bill Wendling (1):
>>>>     dwarf_loader: have all CUs use a single hash table
>>>>
>>>>    dwarf_loader.c | 45 +++++++++++++++++++++++++++++++++------------
>>>>    1 file changed, 33 insertions(+), 12 deletions(-)
>>>>
>>>> --
>>>> 2.30.0.478.g8a0d178c01-goog
>>>>