[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Message-ID: <lhubji3f5wb.fsf@oldenburg.str.redhat.com>
Date: Thu, 05 Feb 2026 18:37:40 +0100
From: Florian Weimer <fweimer@...hat.com>
To: Fangrui Song <i@...kray.me>
Cc: musl@...ts.openwall.com, Fabian Rast <fabian.rast@....de>
Subject: Re: [PATCH v2] ldso: skip gnu hash calculation if precomputed
* Fangrui Song:
> On Mon, Dec 8, 2025 at 8:20 AM Rich Felker <dalias@...c.org> wrote:
>>
>> 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.
>
> Google modified glibc (GRTE) has a "fastload" patch that dramatically
> speeds up symbol resolution by building a position hash table at
> startup that records, for each symbol, the earliest position in the
> link map where that symbol can be found.
> During symbol lookup, instead of scanning from position 0, the rtld
> can skip directly to the relevant position.
> https://sourceware.org/bugzilla/show_bug.cgi?id=16709 ("Dynamic
> linking with large number of DSOs degrades into linear lookup")
I think the implementation started with this commit on the
google/grte/v5-2.27/master branch.
commit 590786950c039260b75db235e81f2ae1633a055e
Author: Paul Pluzhnikov <ppluzhnikov@...gle.com>
Date: Tue Mar 4 19:07:05 2014 -0800
Add "fastload" support.
<https://sourceware.org/cgit/glibc/commit/?id=590786950c039260b75db235e81f2ae1633a055e>
There's been some changes after that.
I'm not sure if this has ever been submitted to libc-alpha? It's
certainly an interesting approach.
I haven't checked if the latest implementation contains heuristics not
to duplicate the hash tables if there are only few symbol references in
relation to the total number of exported symbols. It might not be a
uniform improvement across all kinds of process images.
Thanks,
Florian
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.
