[PATCH] dwarf-reader: Use high bits of Bloom filter words.

[PATCH] dwarf-reader: Use high bits of Bloom filter words.

[Giuliano Procida]

Most of the bit values used for GNU hash ELF section Bloom filtering
were being ignored due to integer narrowing, reducing missing symbol
filtering efficiency considerably.

This patch fixes this.

	* src/abg-dwarf-reader.cc (lookup_symbol_from_gnu_hash_tab):
	Don't narrow calculated Bloom word to 8 bits before using it
	to mask the fetched Bloom word.
---
 src/abg-dwarf-reader.cc | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/src/abg-dwarf-reader.cc b/src/abg-dwarf-reader.cc
index 3454fcf5..5556bde5 100644
--- a/src/abg-dwarf-reader.cc
+++ b/src/abg-dwarf-reader.cc
@@ -2025,7 +2025,7 @@ lookup_symbol_from_gnu_hash_tab(const environment*		env,
   // filter, in bits.
   int c = get_elf_class_size_in_bytes(elf_handle) * 8;
   int n =  (h1 / c) % ht.bf_nwords;
-  unsigned char bitmask = (1ul << (h1 % c)) | (1ul << (h2 % c));
+  GElf_Word bitmask = (1ul << (h1 % c)) | (1ul << (h2 % c));
 
   // Test if the symbol is *NOT* present in this ELF file.
   if ((bloom_word_at(elf_handle, ht.bloom_filter, n) & bitmask) != bitmask)
-- 
2.25.1.481.gfbce0eb801-goog

Re: [PATCH] dwarf-reader: Use high bits of Bloom filter words.

[Matthias Maennich]

Hi!

On Wed, Mar 18, 2020 at 10:20:55AM +0000, Android Kernel Team wrote:
>Most of the bit values used for GNU hash ELF section Bloom filtering
>were being ignored due to integer narrowing, reducing missing symbol
>filtering efficiency considerably.

Nice! Maybe add the analysis result from the other mail thread to point
out the improvement made here (and the justification for this change).

>
>This patch fixes this.
>
>	* src/abg-dwarf-reader.cc (lookup_symbol_from_gnu_hash_tab):
>	Don't narrow calculated Bloom word to 8 bits before using it
>	to mask the fetched Bloom word.
Please sign off your work.

Reviewed-by: Matthias Maennich <maennich@google.com>

Cheers,
Matthias

>---
> src/abg-dwarf-reader.cc | 2 +-
> 1 file changed, 1 insertion(+), 1 deletion(-)
>
>diff --git a/src/abg-dwarf-reader.cc b/src/abg-dwarf-reader.cc
>index 3454fcf5..5556bde5 100644
>--- a/src/abg-dwarf-reader.cc
>+++ b/src/abg-dwarf-reader.cc
>@@ -2025,7 +2025,7 @@ lookup_symbol_from_gnu_hash_tab(const environment*		env,
>   // filter, in bits.
>   int c = get_elf_class_size_in_bytes(elf_handle) * 8;
>   int n =  (h1 / c) % ht.bf_nwords;
>-  unsigned char bitmask = (1ul << (h1 % c)) | (1ul << (h2 % c));
>+  GElf_Word bitmask = (1ul << (h1 % c)) | (1ul << (h2 % c));
>
>   // Test if the symbol is *NOT* present in this ELF file.
>   if ((bloom_word_at(elf_handle, ht.bloom_filter, n) & bitmask) != bitmask)
>-- 
>2.25.1.481.gfbce0eb801-goog
>
>

[PATCH v2] dwarf-reader: Use all bits of Bloom filter words.

[Giuliano Procida]

Most of the bit values used for GNU hash ELF section Bloom filtering
were being ignored due to integer narrowing, reducing missing symbol
filtering efficiency considerably.

This patch fixes this.

	* src/abg-dwarf-reader.cc (lookup_symbol_from_gnu_hash_tab):
	Don't narrow calculated Bloom word to 8 bits before using it
	to mask the fetched Bloom word.

Note on testing.

The .gnu.hash section seems to be present in all the .so but none of
the .o test files. abisym doesn't appear to find dynamic symbols (nm
-D), only normal ones, so it was a little tricky to test this.

I found a Debian .so (libpthread) with both the .gnu.hash section and
normal symbols. abisym behaves identically with my change, looking up
lots of present and non-present (as far as it's concerned) symbols. I
just extracted a full list with nm/sed and looked up each one.

389 symbols looked up, 241 present, 148 absent
8-bit filter: 336 maybe, 53 no (53/148 filtering efficiency)
64-bit filter: 255 maybe, 134 no (134/148 filtering efficiency)

Signed-off-by: Giuliano Procida <gprocida@google.com>
---
 src/abg-dwarf-reader.cc | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/src/abg-dwarf-reader.cc b/src/abg-dwarf-reader.cc
index 3454fcf5..5556bde5 100644
--- a/src/abg-dwarf-reader.cc
+++ b/src/abg-dwarf-reader.cc
@@ -2025,7 +2025,7 @@ lookup_symbol_from_gnu_hash_tab(const environment*		env,
   // filter, in bits.
   int c = get_elf_class_size_in_bytes(elf_handle) * 8;
   int n =  (h1 / c) % ht.bf_nwords;
-  unsigned char bitmask = (1ul << (h1 % c)) | (1ul << (h2 % c));
+  GElf_Word bitmask = (1ul << (h1 % c)) | (1ul << (h2 % c));
 
   // Test if the symbol is *NOT* present in this ELF file.
   if ((bloom_word_at(elf_handle, ht.bloom_filter, n) & bitmask) != bitmask)
-- 
2.25.1.481.gfbce0eb801-goog

Re: [PATCH] dwarf-reader: Use high bits of Bloom filter words.

[Giuliano Procida]

Will do.

I'll also change the commit name s/high/all/.

Giuliano.

On Wed, 18 Mar 2020 at 11:37, Matthias Maennich <maennich@google.com> wrote:
>
> Hi!
>
> On Wed, Mar 18, 2020 at 10:20:55AM +0000, Android Kernel Team wrote:
> >Most of the bit values used for GNU hash ELF section Bloom filtering
> >were being ignored due to integer narrowing, reducing missing symbol
> >filtering efficiency considerably.
>
> Nice! Maybe add the analysis result from the other mail thread to point
> out the improvement made here (and the justification for this change).
>
> >
> >This patch fixes this.
> >
> >       * src/abg-dwarf-reader.cc (lookup_symbol_from_gnu_hash_tab):
> >       Don't narrow calculated Bloom word to 8 bits before using it
> >       to mask the fetched Bloom word.
> Please sign off your work.
>
> Reviewed-by: Matthias Maennich <maennich@google.com>
>
> Cheers,
> Matthias
>
> >---
> > src/abg-dwarf-reader.cc | 2 +-
> > 1 file changed, 1 insertion(+), 1 deletion(-)
> >
> >diff --git a/src/abg-dwarf-reader.cc b/src/abg-dwarf-reader.cc
> >index 3454fcf5..5556bde5 100644
> >--- a/src/abg-dwarf-reader.cc
> >+++ b/src/abg-dwarf-reader.cc
> >@@ -2025,7 +2025,7 @@ lookup_symbol_from_gnu_hash_tab(const environment*               env,
> >   // filter, in bits.
> >   int c = get_elf_class_size_in_bytes(elf_handle) * 8;
> >   int n =  (h1 / c) % ht.bf_nwords;
> >-  unsigned char bitmask = (1ul << (h1 % c)) | (1ul << (h2 % c));
> >+  GElf_Word bitmask = (1ul << (h1 % c)) | (1ul << (h2 % c));
> >
> >   // Test if the symbol is *NOT* present in this ELF file.
> >   if ((bloom_word_at(elf_handle, ht.bloom_filter, n) & bitmask) != bitmask)
> >--
> >2.25.1.481.gfbce0eb801-goog
> >
> >

Re: [PATCH v2] dwarf-reader: Use all bits of Bloom filter words.

[Dodji Seketeli]

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

Hello Giuliano,

Giuliano Procida <gprocida@google.com> a écrit:

[...]

> diff --git a/src/abg-dwarf-reader.cc b/src/abg-dwarf-reader.cc
> index 3454fcf5..5556bde5 100644
> --- a/src/abg-dwarf-reader.cc
> +++ b/src/abg-dwarf-reader.cc
> @@ -2025,7 +2025,7 @@ lookup_symbol_from_gnu_hash_tab(const environment*		env,
>    // filter, in bits.
>    int c = get_elf_class_size_in_bytes(elf_handle) * 8;
>    int n =  (h1 / c) % ht.bf_nwords;
> -  unsigned char bitmask = (1ul << (h1 % c)) | (1ul << (h2 % c));
> +  GElf_Word bitmask = (1ul << (h1 % c)) | (1ul << (h2 % c));

Good catch!  I wonder what made me chose a byte-wide bitmask to begin
with.  The docmentation of the bloom filter of the GNU Hash table at
https://blogs.oracle.com/solaris/gnu-hash-elf-sections-v2 says:

    "The filter consists of maskwords words, each of which is 32-bits
    (ELFCLASS32) or 64-bits (ELFCLASS64) depending on the class of object"

So it's clear, the bitmask must be of type GElf_Word.

Have you seen any practical speed increase in the loading of ELF
binaries due to this change?

[...]

> Most of the bit values used for GNU hash ELF section Bloom filtering
> were being ignored due to integer narrowing, reducing missing symbol
> filtering efficiency considerably.
>
> This patch fixes this.
>
> 	* src/abg-dwarf-reader.cc (lookup_symbol_from_gnu_hash_tab):
> 	Don't narrow calculated Bloom word to 8 bits before using it
> 	to mask the fetched Bloom word.

I have amended the patch to have the ChangeLog section above come
last in the commit log message.

It really needs to come last because we have a script that build a
ChangeLog file from all the change log parts of the commit log and that
one is shipped in the released tarball, making it compliant with the GNU
tarball standards.  That way, users who consume the tarball can access
some history without needing to have (internet) access to the full Git
history.

[...]

> Note on testing.
>
> The .gnu.hash section seems to be present in all the .so but none of
> the .o test files. abisym doesn't appear to find dynamic symbols (nm
> -D), only normal ones, so it was a little tricky to test this.
>
> I found a Debian .so (libpthread) with both the .gnu.hash section and
> normal symbols. abisym behaves identically with my change, looking up
> lots of present and non-present (as far as it's concerned) symbols. I
> just extracted a full list with nm/sed and looked up each one.
>
> 389 symbols looked up, 241 present, 148 absent
> 8-bit filter: 336 maybe, 53 no (53/148 filtering efficiency)
> 64-bit filter: 255 maybe, 134 no (134/148 filtering efficiency)

Thanks.

So I am applying this to master.

Below is the actual patch that got applied.

Cheers,


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: applied patch --]
[-- Type: text/x-patch, Size: 2061 bytes --]

From e0950e64279d59e92de5170d805be99f84cdfd8d Mon Sep 17 00:00:00 2001
From: Giuliano Procida <gprocida@google.com>
Date: Wed, 18 Mar 2020 12:12:41 +0000
Subject: [PATCH] dwarf-reader: Use all bits of Bloom filter words.

Most of the bit values used for GNU hash ELF section Bloom filtering
were being ignored due to integer narrowing, reducing missing symbol
filtering efficiency considerably.

This patch fixes this.

Note on testing.

The .gnu.hash section seems to be present in all the .so but none of
the .o test files. abisym doesn't appear to find dynamic symbols (nm
-D), only normal ones, so it was a little tricky to test this.

I found a Debian .so (libpthread) with both the .gnu.hash section and
normal symbols. abisym behaves identically with my change, looking up
lots of present and non-present (as far as it's concerned) symbols. I
just extracted a full list with nm/sed and looked up each one.

389 symbols looked up, 241 present, 148 absent
8-bit filter: 336 maybe, 53 no (53/148 filtering efficiency)
64-bit filter: 255 maybe, 134 no (134/148 filtering efficiency)

	* src/abg-dwarf-reader.cc (lookup_symbol_from_gnu_hash_tab):
	Don't narrow calculated Bloom word to 8 bits before using it
	to mask the fetched Bloom word.

Signed-off-by: Giuliano Procida <gprocida@google.com>
Signed-off-by: Dodji Seketeli <dodji@redhat.com>
---
 src/abg-dwarf-reader.cc | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/src/abg-dwarf-reader.cc b/src/abg-dwarf-reader.cc
index ff532cfd..5bc8a157 100644
--- a/src/abg-dwarf-reader.cc
+++ b/src/abg-dwarf-reader.cc
@@ -2025,7 +2025,7 @@ lookup_symbol_from_gnu_hash_tab(const environment*		env,
   // filter, in bits.
   int c = get_elf_class_size_in_bytes(elf_handle) * 8;
   int n =  (h1 / c) % ht.bf_nwords;
-  unsigned char bitmask = (1ul << (h1 % c)) | (1ul << (h2 % c));
+  GElf_Word bitmask = (1ul << (h1 % c)) | (1ul << (h2 % c));
 
   // Test if the symbol is *NOT* present in this ELF file.
   if ((bloom_word_at(elf_handle, ht.bloom_filter, n) & bitmask) != bitmask)
-- 
2.25.0


[-- Attachment #3: Type: text/plain, Size: 13 bytes --]


-- 
		Dodji

Re: [PATCH v2] dwarf-reader: Use all bits of Bloom filter words.

[Giuliano Procida]

Hi Dodji.

On Thu, 19 Mar 2020 at 10:21, Dodji Seketeli <dodji@seketeli.org> wrote:
>
> Hello Giuliano,
>
> Giuliano Procida <gprocida@google.com> a écrit:
>
> [...]
>
> > diff --git a/src/abg-dwarf-reader.cc b/src/abg-dwarf-reader.cc
> > index 3454fcf5..5556bde5 100644
> > --- a/src/abg-dwarf-reader.cc
> > +++ b/src/abg-dwarf-reader.cc
> > @@ -2025,7 +2025,7 @@ lookup_symbol_from_gnu_hash_tab(const environment*              env,
> >    // filter, in bits.
> >    int c = get_elf_class_size_in_bytes(elf_handle) * 8;
> >    int n =  (h1 / c) % ht.bf_nwords;
> > -  unsigned char bitmask = (1ul << (h1 % c)) | (1ul << (h2 % c));
> > +  GElf_Word bitmask = (1ul << (h1 % c)) | (1ul << (h2 % c));
>
> Good catch!  I wonder what made me chose a byte-wide bitmask to begin
> with.  The docmentation of the bloom filter of the GNU Hash table at
> https://blogs.oracle.com/solaris/gnu-hash-elf-sections-v2 says:
>
>     "The filter consists of maskwords words, each of which is 32-bits
>     (ELFCLASS32) or 64-bits (ELFCLASS64) depending on the class of object"
>
> So it's clear, the bitmask must be of type GElf_Word.
>
> Have you seen any practical speed increase in the loading of ELF
> binaries due to this change?

I spotted the bug when reviewing maennich's fix for undefined
behaviour (integer overflow). I'm afraid I didn't go as far as testing
on a real workload as I don't think we have one that exercises this
code. It might help someone else though.

The whole of make check (excluding fedabipkgdiff tests) only made 3
calls to the function. I think the efficiency was 100% both before and
after (2/2 absent symbols excluded by the Bloom filter). :-)

> [...]
>
> > Most of the bit values used for GNU hash ELF section Bloom filtering
> > were being ignored due to integer narrowing, reducing missing symbol
> > filtering efficiency considerably.
> >
> > This patch fixes this.
> >
> >       * src/abg-dwarf-reader.cc (lookup_symbol_from_gnu_hash_tab):
> >       Don't narrow calculated Bloom word to 8 bits before using it
> >       to mask the fetched Bloom word.
>
> I have amended the patch to have the ChangeLog section above come
> last in the commit log message.
>
> It really needs to come last because we have a script that build a
> ChangeLog file from all the change log parts of the commit log and that
> one is shipped in the released tarball, making it compliant with the GNU
> tarball standards.  That way, users who consume the tarball can access
> some history without needing to have (internet) access to the full Git
> history.

I was happy for the note on testing to be excluded from the commit
message. Would it be better to just reply to the patch to add this
sort of context, or would you like to see these notes in the commit
messages?

Regards,
Giuliano.

> [...]
>
> > Note on testing.
> >
> > The .gnu.hash section seems to be present in all the .so but none of
> > the .o test files. abisym doesn't appear to find dynamic symbols (nm
> > -D), only normal ones, so it was a little tricky to test this.
> >
> > I found a Debian .so (libpthread) with both the .gnu.hash section and
> > normal symbols. abisym behaves identically with my change, looking up
> > lots of present and non-present (as far as it's concerned) symbols. I
> > just extracted a full list with nm/sed and looked up each one.
> >
> > 389 symbols looked up, 241 present, 148 absent
> > 8-bit filter: 336 maybe, 53 no (53/148 filtering efficiency)
> > 64-bit filter: 255 maybe, 134 no (134/148 filtering efficiency)
>
> Thanks.
>
> So I am applying this to master.
>
> Below is the actual patch that got applied.
>
> Cheers,
>
>
> --
>                 Dodji

Re: [PATCH v2] dwarf-reader: Use all bits of Bloom filter words.

[Matthias Männich]

On Thu, Mar 19, 2020 at 10:46:12AM +0000, Giuliano Procida wrote:
>Hi Dodji.
>
>On Thu, 19 Mar 2020 at 10:21, Dodji Seketeli <dodji@seketeli.org> wrote:
>>
>> Hello Giuliano,
>>
>> Giuliano Procida <gprocida@google.com> a écrit:
>>
>> [...]
>>
>> > diff --git a/src/abg-dwarf-reader.cc b/src/abg-dwarf-reader.cc
>> > index 3454fcf5..5556bde5 100644
>> > --- a/src/abg-dwarf-reader.cc
>> > +++ b/src/abg-dwarf-reader.cc
>> > @@ -2025,7 +2025,7 @@ lookup_symbol_from_gnu_hash_tab(const environment*              env,
>> >    // filter, in bits.
>> >    int c = get_elf_class_size_in_bytes(elf_handle) * 8;
>> >    int n =  (h1 / c) % ht.bf_nwords;
>> > -  unsigned char bitmask = (1ul << (h1 % c)) | (1ul << (h2 % c));
>> > +  GElf_Word bitmask = (1ul << (h1 % c)) | (1ul << (h2 % c));
>>
>> Good catch!  I wonder what made me chose a byte-wide bitmask to begin
>> with.  The docmentation of the bloom filter of the GNU Hash table at
>> https://blogs.oracle.com/solaris/gnu-hash-elf-sections-v2 says:
>>
>>     "The filter consists of maskwords words, each of which is 32-bits
>>     (ELFCLASS32) or 64-bits (ELFCLASS64) depending on the class of object"
>>
>> So it's clear, the bitmask must be of type GElf_Word.
>>
>> Have you seen any practical speed increase in the loading of ELF
>> binaries due to this change?
>
>I spotted the bug when reviewing maennich's fix for undefined
>behaviour (integer overflow). I'm afraid I didn't go as far as testing
>on a real workload as I don't think we have one that exercises this
>code. It might help someone else though.
>
>The whole of make check (excluding fedabipkgdiff tests) only made 3
>calls to the function. I think the efficiency was 100% both before and
>after (2/2 absent symbols excluded by the Bloom filter). :-)
>
>> [...]
>>
>> > Most of the bit values used for GNU hash ELF section Bloom filtering
>> > were being ignored due to integer narrowing, reducing missing symbol
>> > filtering efficiency considerably.
>> >
>> > This patch fixes this.
>> >
>> >       * src/abg-dwarf-reader.cc (lookup_symbol_from_gnu_hash_tab):
>> >       Don't narrow calculated Bloom word to 8 bits before using it
>> >       to mask the fetched Bloom word.
>>
>> I have amended the patch to have the ChangeLog section above come
>> last in the commit log message.
>>
>> It really needs to come last because we have a script that build a
>> ChangeLog file from all the change log parts of the commit log and that
>> one is shipped in the released tarball, making it compliant with the GNU
>> tarball standards.  That way, users who consume the tarball can access
>> some history without needing to have (internet) access to the full Git
>> history.
>
>I was happy for the note on testing to be excluded from the commit
>message. Would it be better to just reply to the patch to add this
>sort of context, or would you like to see these notes in the commit
>messages?

I would prefer those information in the commit message. But note,
everything below the '---' line is omitted from the commit message and
is therefore a good place to put additional information not to be
persisted in the final commit.

Cheers,
Matthias

>
>Regards,
>Giuliano.
>
>> [...]
>>
>> > Note on testing.
>> >
>> > The .gnu.hash section seems to be present in all the .so but none of
>> > the .o test files. abisym doesn't appear to find dynamic symbols (nm
>> > -D), only normal ones, so it was a little tricky to test this.
>> >
>> > I found a Debian .so (libpthread) with both the .gnu.hash section and
>> > normal symbols. abisym behaves identically with my change, looking up
>> > lots of present and non-present (as far as it's concerned) symbols. I
>> > just extracted a full list with nm/sed and looked up each one.
>> >
>> > 389 symbols looked up, 241 present, 148 absent
>> > 8-bit filter: 336 maybe, 53 no (53/148 filtering efficiency)
>> > 64-bit filter: 255 maybe, 134 no (134/148 filtering efficiency)
>>
>> Thanks.
>>
>> So I am applying this to master.
>>
>> Below is the actual patch that got applied.
>>
>> Cheers,
>>
>>
>> --
>>                 Dodji

Re: [PATCH v2] dwarf-reader: Use all bits of Bloom filter words.

[Dodji Seketeli]

Matthias Männich <maennich@google.com> a écrit:

>>
>>I was happy for the note on testing to be excluded from the commit
>>message. Would it be better to just reply to the patch to add this
>>sort of context, or would you like to see these notes in the commit
>>messages?
>
> I would prefer those information in the commit message. But note,
> everything below the '---' line is omitted from the commit message and
> is therefore a good place to put additional information not to be
> persisted in the final commit.

I didn't exclude the testing note from the commit message.  I just put
the ChangeLog part at the end.

Cheers,

-- 
		Dodji