[PATCH] rtld: skip symbol table index queries if possible

Thu Feb 12 18:08:43 GMT 2026

When a global lookup for a symbol contained in an objects symbol table
is made, we can skip querying the hashtable of the object that initiated
the lookup. The symbol table entry we already have must either be the
definition or the lookup in this object will be negative anyways.

Signed-off-by: Fabian Rast <fabian.rast@tum.de>
---
 elf/dl-lookup.c | 10 ++++++++++
 1 file changed, 10 insertions(+)

diff --git a/elf/dl-lookup.c b/elf/dl-lookup.c
index 7bf8dfbe2f..fc263c106d 100644
--- a/elf/dl-lookup.c
+++ b/elf/dl-lookup.c
@@ -403,6 +403,16 @@ do_lookup_x (const char *undef_name, unsigned int new_hash,
 
       const ElfW(Sym) *sym;
       const ElfW(Addr) *bitmask = map->l_gnu_bitmask;
+
+      /* Index lookup is not needed to find the symbol in undef_map itself */
+      if (__glibc_unlikely (map == undef_map) && ref != NULL)
+       {
+         if (ref->st_shndx == SHN_UNDEF)
+           continue;
+         sym = ref;
+         goto found_it;
+       }
+
       if (__glibc_likely (bitmask != NULL))
 	{
 	  ElfW(Addr) bitmask_word
-- 
2.52.0


Hello,

I would like to propose a symbol lookup optimization in the loader.
Specifically, when lookups are done for symbols that are in some
objects dynamic symbol table (like during program startup), it should
never be neccessary to use the hashtable of that specific object.  In
the case that this object actually provides a definition, the hashtable
lookup requires an expensive strcmp operation that is skipped.  Otherwise
we can still skip the bloom filter check.

This optimization can save a constant amount of time for each symbol
lookup, but introduces additional code for each object that is queried
per symbol (linear overhead). This can become problemantic for very big
lookup scopes, data below.

The check for symbol definedness is implemented by checking st_shndx for
SHN_UNDEF.  I think it is not entirely clear from the specification what
meaning the shndx field is supposed to have at load time, when sections
are not considered.  Fwiw the `strip --strip-section-headers` option
does not adjust the st_shndx field of symbols.  An alternative would
be to only do this when the gnu hashtable is present and check that the
symbol index is less than the symoffset. This would be a little bit more
complicated, but could be safer in terms of compatibility?

The main question is, can a symbol that is part of the dynamic symbol table
and has `st_shndx == 0` always be assumed to be undefined, so not reachable
using any index structure?
I think thit this assumption is reasonable.

I ran some startup time benchmarks (patched to exit at the end of dl_main)
using the binaries from fedora rawhide:

gsx master -> patch:
cycles:	 49600615.0 (0.65) -> 48846016.0 (0.76) -1.52%
instructions:	 96778260.0 (0.01) -> 98595049.0 (0.01) 1.88%
ref-cycles:	 36556549.0 (1.36) -> 36754076.0 (1.16) 0.54%
duration_time:	 20055483.0 (1.22) -> 19955590.0 (1.04) -0.5%

clang master -> patch:
cycles:	 18451085.0 (1.16) -> 17300092.0 (1.2) -6.24%
instructions:	 33377221.0 (0.03) -> 30504237.0 (0.04) -8.61%
ref-cycles:	 15201051.0 (1.13) -> 13621820.0 (1.86) -10.39%
duration_time:	 8834688.0 (1.11) -> 7875950.0 (1.66) -10.85%

libxul.so master -> patch:
cycles:	 56965260.0 (0.31) -> 57207803.0 (0.57) 0.43%
instructions:	 106676249.0 (0.01) -> 108969480.0 (0.02) 2.15%
ref-cycles:	 37133484.0 (1.5) -> 36358017.0 (2.28) -2.09%
duration_time:	 20332039.0 (1.35) -> 19865106.0 (2.14) -2.3%

mpv master -> patch:
cycles:	 332109991.0 (0.18) -> 327969907.0 (0.23) -1.25%
instructions:	 677376303.0 (0.0) -> 707839546.0 (0.0) 4.5%
ref-cycles:	 157862617.0 (2.04) -> 162873539.0 (2.01) 3.17%
duration_time:	 82185333.0 (2.0) -> 84774195.0 (1.99) 3.15%

soffice.bin master -> patch:
cycles:	 112404648.0 (0.47) -> 109063882.0 (0.48) -2.97%
instructions:	 210556428.0 (0.01) -> 215789817.0 (0.01) 2.49%
ref-cycles:	 76726608.0 (1.91) -> 76098069.0 (1.87) -0.82%
duration_time:	 40669911.0 (1.85) -> 40370024.0 (1.83) -0.74%

libwebkit2gtk-4.1.so.0 master -> patch:
cycles:	 106930973.0 (0.36) -> 106467742.0 (0.58) -0.43%
instructions:	 203966465.0 (0.01) -> 209437624.0 (0.01) 2.68%
ref-cycles:	 74536970.0 (1.8) -> 71861647.0 (2.41) -3.59%
duration_time:	 39650561.0 (1.73) -> 38192350.0 (2.33) -3.68%

ffmpeg master -> patch:
cycles:	 270076925.0 (0.25) -> 265669049.0 (0.3) -1.63%
instructions:	 555416657.0 (0.01) -> 578667697.0 (0.01) 4.19%
ref-cycles:	 135108577.0 (2.59) -> 134088490.0 (2.34) -0.76%
duration_time:	 70648042.0 (2.53) -> 70150181.0 (2.27) -0.7%

All but clang execute more instructions, because of the linear overhead
introduced. Clang is an extreme example, because it has relatively
few (but big) libraries that also have relatively long symbol names,
making strcmps more expensive.
mpv starts slower, for gsx there is pretty much no difference.
Because of the linear overhead, this is only preferable when the
lookup scope is not very large.
Please let me know what you think.

Cheers,
Fabian Rast
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 293 bytes
Desc: not available
URL: <https://sourceware.org/pipermail/libc-alpha/attachments/20260212/e6f38c2f/attachment-0001.sig>
