[Bug general/31763] New: eu-readelf -r is super slow at packed relocation processing

[Bug general/31763] New: eu-readelf -r is super slow at packed relocation processing

[ajax at redhat dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=31763

            Bug ID: 31763
           Summary: eu-readelf -r is super slow at packed relocation
                    processing
           Product: elfutils
           Version: unspecified
            Status: NEW
          Severity: normal
          Priority: P2
         Component: general
          Assignee: unassigned at sourceware dot org
          Reporter: ajax at redhat dot com
                CC: elfutils-devel at sourceware dot org
  Target Milestone: ---

After upgrading to F40, I was pleased to find that packed relocations were
enabled, but one of my tools uses `eu-readelf -r` and apparently packed relocs
are super slow:

========
# What are we dealing with?
neo:~% eu-readelf -d /usr/lib64/libcrypto.so.3 | grep ^..REL
  RELA              0x000000000004acc8
  RELASZ            168 (bytes)
  RELAENT           24 (bytes)
  RELR              0x000000000004bc88
  RELRSZ            6000 (bytes)
  RELRENT           8 (bytes)

# Not too huge. How bad is it?
neo:~% time eu-readelf -r /usr/lib64/libcrypto.so | wc -l   
17904
eu-readelf -r /usr/lib64/libcrypto.so  5.80s user 0.00s system 99% cpu 5.812
total
wc -l  0.00s user 0.00s system 0% cpu 5.811 total

# That's... not good. How does the competition do?
neo:~% time readelf -r /usr/lib64/libcrypto.so | wc -l   
17905
readelf -r /usr/lib64/libcrypto.so  0.01s user 0.01s system 95% cpu 0.014 total
wc -l  0.00s user 0.00s system 25% cpu 0.013 total

# That's worse. Did it happen in F39?
neo:~% time toolbox run -c fedora39 eu-readelf -r /usr/lib64/libcrypto.so | wc
-l
17006
toolbox run -c fedora39 eu-readelf -r /usr/lib64/libcrypto.so  0.00s user 0.01s
system 3% cpu 0.348 total
wc -l  0.00s user 0.00s system 1% cpu 0.347 total

# Nope, even the container overhead doesn't come close.
# Does it happen with F40's elfutils but F39's libcrypto?
neo:~% toolbox run -c fedora39 cat /usr/lib64/libcrypto.so > f39-libcrypto.so
neo:~% time eu-readelf -r ./f39-libcrypto.so | wc -l
17006
eu-readelf -r ./f39-libcrypto.so  0.00s user 0.00s system 93% cpu 0.010 total
wc -l  0.00s user 0.00s system 37% cpu 0.009 total

# Nope. What does f39's libcrypto's reloc info look like?
neo:~% eu-readelf -d ./f39-libcrypto.so | grep ^..REL          
  RELA              0x00000000000494a0
  RELASZ            404592 (bytes)
  RELAENT           24 (bytes)
  RELACOUNT         16851
========

6 seconds is "bad but not awful", but I discovered this on libLLVM where it's
more like eight minutes.

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug general/31763] eu-readelf -r is super slow at packed relocation processing

[mark at klomp dot org]

https://sourceware.org/bugzilla/show_bug.cgi?id=31763

Mark Wielaard <mark at klomp dot org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |mark at klomp dot org

--- Comment #1 from Mark Wielaard <mark at klomp dot org> ---
Hohum. The slowdown comes from the fact that eu-readelf by default tries to do
an symbol lookup for every address it tries to print the function symbol +
offset.

The idea is that the -r output would look something like:

Relocation section [12] '.relr.dyn' at offset 0x4bc88 contains 750 entries:
  +0x000000000044bcd0 <__frame_dummy_init_array_entry> *
  +0x000000000044bcd8 <__do_global_dtors_aux_fini_array_entry>
  +0x000000000044bce0 <__dso_handle>
  +0x000000000044bd10 <ossl_ed448_asn1_meth+0x10>
  +0x000000000044bd18 <ossl_ed448_asn1_meth+0x18>
  +0x000000000044bd20 <ossl_ed448_asn1_meth+0x20>
[...]

But in practice this doesn't actually work for system libraries, since the
.symtab is stripped out, so the symbol lookup always fails (even with debuginfo
installed, since readelf doesn't do a separate .debug file lookup, you'll have
to eu-unstrip the library and debug file). It is super useful for your locally
build binaries though.

Unfortunately even with the .symtab stripped out this symbol lookup is
unreasonably slow.

As a workaround you can use:

  -N, --numeric-addresses    Do not find symbol names for addresses in DWARF
                             data

$ time eu-readelf -r ./libcrypto.so.3 | wc -l
17904

real    0m6.676s
user    0m6.648s
sys     0m0.010s

$ time eu-readelf -r -N ./libcrypto.so.3 | wc -l
17904

real    0m0.045s
user    0m0.037s
sys     0m0.013s

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug general/31763] eu-readelf -r is super slow at packed relocation processing

[mark at klomp dot org]

https://sourceware.org/bugzilla/show_bug.cgi?id=31763

--- Comment #2 from Mark Wielaard <mark at klomp dot org> ---
So the main issue is libdwfl/dwfl_module_addrsym.c which does a linear search
through all symbol tables each and every time...

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug general/31763] eu-readelf -r is super slow at packed relocation processing

[ajax at redhat dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=31763

--- Comment #3 from Adam Jackson <ajax at redhat dot com> ---
-N works, not sure how I'd missed it in the docs, thank you. I'm not sure if
there's a good way to cache the likely-negative-ness of the symbol lookup here.
From your example:

> Relocation section [12] '.relr.dyn' at offset 0x4bc88 contains 750 entries:
>   +0x000000000044bcd0 <__frame_dummy_init_array_entry> *
>   +0x000000000044bcd8 <__do_global_dtors_aux_fini_array_entry>
>   +0x000000000044bce0 <__dso_handle>
>   +0x000000000044bd10 <ossl_ed448_asn1_meth+0x10>
>   +0x000000000044bd18 <ossl_ed448_asn1_meth+0x18>
>   +0x000000000044bd20 <ossl_ed448_asn1_meth+0x20>

When you process 0x44bd10 you could look ahead to see that the next two have
the same increment (of 0x8, though, why be picky), and probably they, and any
more beyond with the same increment, would refer to offsets within a single
symbol. I don't know if there's a good way to express that as a heuristic here
though.

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug general/31763] eu-readelf -r is super slow at packed relocation processing

[fweimer at redhat dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=31763

Florian Weimer <fweimer at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |fweimer at redhat dot com

--- Comment #4 from Florian Weimer <fweimer at redhat dot com> ---
(In reply to Mark Wielaard from comment #1)
> But in practice this doesn't actually work for system libraries, since the
> .symtab is stripped out, so the symbol lookup always fails (even with
> debuginfo installed, since readelf doesn't do a separate .debug file lookup,
> you'll have to eu-unstrip the library and debug file). It is super useful
> for your locally build binaries though.

Isn't there a compressed symbol table in .gnu_debugdata?

But that's fairly Fedora/downstream specific, I think.

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug general/31763] eu-readelf -r is super slow at packed relocation processing

[mark at klomp dot org]

https://sourceware.org/bugzilla/show_bug.cgi?id=31763

--- Comment #5 from Mark Wielaard <mark at klomp dot org> ---
(In reply to Florian Weimer from comment #4)
> (In reply to Mark Wielaard from comment #1)
> > But in practice this doesn't actually work for system libraries, since the
> > .symtab is stripped out, so the symbol lookup always fails (even with
> > debuginfo installed, since readelf doesn't do a separate .debug file lookup,
> > you'll have to eu-unstrip the library and debug file). It is super useful
> > for your locally build binaries though.
> 
> Isn't there a compressed symbol table in .gnu_debugdata?

Yes, there is. And that one is searched. But it only contains STT_FUNC symbols
(since the main purpose is to show symbols for backtraces). And the RELR all
seem to be against addresses in SST_OBJECT symbols.

-- 
You are receiving this mail because:
You are on the CC list for the bug.