[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20251209012713.GK1827@brightrain.aerifal.cx>
Date: Mon, 8 Dec 2025 20:27:13 -0500
From: Rich Felker <dalias@...c.org>
To: Fabian Rast <fabian.rast@....de>
Cc: musl@...ts.openwall.com
Subject: Re: [PATCH v2] ldso: skip gnu hash calculation if precomputed
On Tue, Dec 09, 2025 at 02:10:46AM +0100, Fabian Rast wrote:
> On Mon Dec 8, 2025 at 5:20 PM CET, Rich Felker wrote:
> > 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.
>
> I think only defined symbols are included.
> But UNDEF symbols are usually also not included in the hashtable - they
> are usually sorted to the beginning and gnu hash uses a constant offset
> for every symbol index to exclude them. So for these undef symbols where
> the bloom filter would not work we do not even have the other 31 bits
> because the symbol is not in the hashtable. Of course the hash is also
> a link time constant for these symbols, but its just not in the binary...
>
> >> > 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.
>
> This sounds like it should work. I will try to implement this and see.
Since the reference-only symbols aren't in the hashtable, I don't
think there's anything useful you can do with this.
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.
