Hi,
I use readelf from elfutils to extract ABI information from the debug
info of an ELF object in the ABI Dumper tool [1]. The -N option of
readelf has fixed a problem with performance. But most of the symbol
names have missed from the debug dump. So I got symbol names by their
addresses effectively from the cached .dynsym and .symtab tables of an
object.
Thank you.
[1]
https://github.com/lvc/abi-dumper
Mark Wielaard wrote:
Hi Andrey,
(Thanks for upstream-tracker BTW. It has been really useful.)
On Fri, Jul 12, 2013 at 06:49:59PM +0400, Andrey Ponomarenko wrote:
> I've found an O(N^2) loop in the libdw library (N - number of
> symbols in the library). The dwfl_module_getsym function is called N
> times, but it calls resolve_symbol function each time and it loops
> through the number of symbols again.
>
> So `readelf --debug-dump=info shared_object.so` command is very slow
> on large input objects. As an example, it takes several minutes to
> analyse libOpenImageIO.so.1.1.11 (27mb), but readelf from binutils
> takes just several seconds to do it.
If the goal is just to have a faster eu-readelf -w than binutils
readelf -w then just run it with -N and it will not do any address
to symbol lookups and it should be faster.
But you are right that -N/--numeric-addresses isn't the default.
And by default eu-readelf will do address symbol lookups (because
that makes the output much richer than plain binutils readelf gives)
and those are indeed pretty slow atm.
> The gelf_getsymshndx, gelf_getshdr and elf_getscn functions from
> libelf are called 2 billion times and it takes about 60% of total
> execution time. Another 26% of execution time are taken by the
> search_table function that is called by the dwfl_module_addrsym and
> loops through the number of symbols too. The dwfl_module_addrsym is
> called for each symbol. So it also takes O(N^2).
>
> How can dwfl_module_getsym and dwfl_module_addrsym functions may be
> optimised to not to loop through all symbols in the library in order
> to find information for just one of them? This can make the library
> to be 10 times faster.
Those functions work with the "raw" .dynsyn or .symtab (in the ELF,
separate .debug file or in the .gnu_debugdata). Those tables aren't
sorted by address (just by whether they are local or global, we
prefer globals so we search those first in the hope not to have to
do a full N search) so we have to search them linearly.
They are really designed for doing a quick lookup for a single address.
If you really need all the addresses/symbols then iterating through
them all with dwfl_module_getsymtab() and dwfl_module_getsym (), then
you can create a search table for them all.
So readelf.c could be considered to use dwfl_module_addrsym "wrongly"
since in general it will call it for lots of different addresses. We
should probably build a search table. And maybe even do that not just
in readelf.c but add it to libdwfl for use with dwfl_module_addrsym
directly?
Cheers,
Mark
--
Andrey Ponomarenko, ROSA Lab.