[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20251208162042.GI1827@brightrain.aerifal.cx>
Date: Mon, 8 Dec 2025 11:20:42 -0500
From: Rich Felker <dalias@...c.org>
To: Fabian Rast <fabian.rast@....de>, musl@...ts.openwall.com
Subject: Re: [PATCH v2] ldso: skip gnu hash calculation if precomputed
On Mon, Dec 08, 2025 at 06:20:58AM +0100, Szabolcs Nagy wrote:
> * Rich Felker <dalias@...c.org> [2025-12-07 21:25:42 -0500]:
> > On Sun, Dec 07, 2025 at 08:44:54PM -0500, Rich Felker wrote:
> > > This looks a lot more expensive than the method I suggested using the
> > > bloom filter, which has no modulo, much less two.
> >
> > Actually, I'm not sure if the bloom filter approach works. Is a hash
> > included in the bloom filter as soon as it's present in the symbol
> > table, or only if it's present with a definition?
> >
> > If it's absent for undefined, then this approach is a non-starter. It
> > can't tell us anything.
>
> isn't it the other way around?
>
> only defined symbols set bits in the bloom filter.
> it is for checking if a dso might have a definition.
I think you misunderstood what I was saying and looking for.
I was thinking the bloom filter would include everything in the symbol
table, including both symbols that provide definitions and symbol
table entries that are used to reference undefined symbols. In this
case, we could use the bloom filter of the DSO making the reference to
determine which of the two candidate hashes is correct, and do so very
quickly (nothing but a few bitshifts and masks).
However, it seems reasonable that the bloom filter would only include
symbols that actually have definitions. Otherwise at each step of the
DSO chain you'd get a false positive for every DSO that references the
symbol without defining it. So we probably can't do it the way I'd
hoped.
> > But if undefined symbols are present, then here's my concept for how
> > it would work:
> >
> > It should consist of grabbing two consecutive bits aligned at a 2-bit
> > boundary (so not crossing slots) from the bloom filter, and
> > considering the possible values:
> >
> > 00 - impossible
> > 01 - low bit is 0
> > 10 - low bit is 1
> > 11 - inconclusive; just compute hash. should be rare with good bloom.
>
> yeah, one of the bits is 'in the filter' the other
> is a random bit test: if p portion of the bits are
> 1 then with p chance we fail.
>
> in bfd ld the bloom mask seems to be sized such that
> if nsym in [ 3<<k, 3<<(k+1) ) then maskbits = 32<<k
> so 3/32 <= nsym/maskbits < 6/32
>
> each symbol sets two bits so the probability that
> a bit is 0 is (1-1/maskbits)^(2*nsym) so a bit is 1
> with roughly p = 1 - exp(-2*nsym/maskbits) that is
> 0.17 < p < 0.32 probability. (normally two bits
> are tested so bloom fails with p^2, but the other
> bit is shared between h&-2 and h|1)
>
> if this is right and the hash is good, then we have
> about 20-30% chance to fail and 70-80% to succeed
> just with that one bit.
>
>
> it seems to me that with many dsos (>50), it's not
> the gnu_hash but the walk over all dsos and checking
> gnu_lookup_filtered will be the slow part. not
> sure if it's possible to help with that.
> i also noticed that some symbols are looked up a lot:
> in clang >30% of lookups are (multiple relocs per dso)
> __cxa_pure_virtual
> _ZTVN10__cxxabiv120__si_class_type_infoE
> _ZTVN10__cxxabiv117__class_type_infoE
> _ZTVN10__cxxabiv121__vmi_class_type_infoE
> and these generate fair bit of lookups too (undef weak):
> _ITM_deregisterTMCloneTable
> _ITM_registerTMCloneTable
> __deregister_frame_info
> __register_frame_info
I think modern linkers sort relocations by the symbol referenced,
which allows you to bypass the lookup if the reference is the same as
the previous relocation. We do not take advantage of this in the
do_relocs loop at all, but we could. That would probably give far more
performance boost than eliding the hashing and might even make eliding
the hashing pointless.
Rich
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
