Question re: dynamic linking in musl

[Alex Dowad <alexinbeijing@gmail.com>]

Hi,

I'm just dealing with a problem whereby rrdtool is spending >90% of its runtime in
musl's dynamic linker (this is on Alpine Linux). This is making it too slow to do
what we need it to do.

After perusing some hotspots in dynlink.c (as measured by callgrind), there is
something which looks like a big opportunity for optimization. I hope I'm not wrong.
I probably am. I don't understand the code very well.

do_relocs is called 3 times for each binary which needs relocation (including the main
program and all its dependencies). Once for all the relocations in .rel.dyn, one
for those in .rel.plt, and one for... something else. Haven't looked it up, not
important right now.

do_relocs iterates through all those relocations, and calls find_sym for each one
to look up where the desired function, or variable, etc. can be found.

find_sym iterates through *each* binary which has been loaded, including *all*
the recursive dependencies, and does a hash lookup in each one to see if the
desired symbol can be found.

(Well, that's not quite right; for certain types of relocations, it skips the
head of the list of binaries.)

NOW: Is there any reason why dso->deps could not be used to search for symbols *only*
in the dependencies of the binary which is currently being relocated?

For example, rrdtool has dependencies on librrd, libxml, pango, libpng, libintl,
libgobject, libharfbuzz, libfontconfig, libfreetype, libX11, libexpat, etc. etc. etc.
When unresolved symbols in libX11 are being looked up, musl will start looking in
librrd, right at the top of the list. But there's no way it will find any of
libX11's relocations in librrd. The dependencies of libX11 are right down close
to the *bottom* of the list.

To add insult to injury, that wasteful lookup process will be repeated for each and
every of the more than 1000 relocations in libX11.

Hoping someone smarter than me can explain things... Thanks, AD