[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20251208022542.GH1827@brightrain.aerifal.cx>
Date: Sun, 7 Dec 2025 21:25:42 -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 Sun, Dec 07, 2025 at 08:44:54PM -0500, Rich Felker wrote:
> On Sat, Dec 06, 2025 at 06:31:06PM +0100, Fabian Rast wrote:
> > calculating the hashes of symbol names can take a significant amount of
> > time while applying relocations. however, symbol lookups for
> > symbols that are themselves part of the gnu hashtable in the object
> > being relocated, the hashvalue is already present in that hashtable
> > and can be efficiently retrieved using the symbol index.
> >
> > the gnu hash table only stores the upper 31 bits of the 32 bit wide
> > hashes. the lsb is used to indicate the end of a chain.
> > this missing bit can be inferred from the position of the symbol index
> > relative to the two possible chains.
> > ---
> > ldso/dynlink.c | 25 +++++++++++++++++++------
> > 1 file changed, 19 insertions(+), 6 deletions(-)
> >
> > diff --git a/ldso/dynlink.c b/ldso/dynlink.c
> > index 44d9b181..6dee7a97 100644
> > --- a/ldso/dynlink.c
> > +++ b/ldso/dynlink.c
> > @@ -320,10 +320,23 @@ static Sym *gnu_lookup_filtered(uint32_t h1, uint32_t *hashtab, struct dso *dso,
> > #if defined(__GNUC__)
> > __attribute__((always_inline))
> > #endif
> > -static inline struct symdef find_sym2(struct dso *dso, const char *s, int need_def, int use_deps)
> > +static inline struct symdef find_sym2(struct dso *dso, const char *s, int need_def, int use_deps, struct dso *dso2, int sym_index)
> > {
> > - uint32_t h = 0, gh = gnu_hash(s), gho = gh / (8*sizeof(size_t)), *ght;
> > - size_t ghm = 1ul << gh % (8*sizeof(size_t));
> > + uint32_t h = 0, gh, gho, *ght;
> > + size_t ghm;
> > +
> > + if (dso2 && (ght = dso2->ghashtab) && sym_index >= ght[1] && ght[0] > 1) {
> > + uint32_t nbuckets = ght[0], *buckets = ght + 4 + ght[2] * 2;
> > + uint32_t h0 = buckets[nbuckets + sym_index - ght[1]] & ~1u, h1 = h0|1;
> > + uint32_t i0 = buckets[h0 % nbuckets], i1 = buckets[h1 % nbuckets];
> > + gh = i0 < i1 && sym_index < i1
> > + || i0 > i1 && sym_index >= i0
> > + || !i1 ? h0 : h1;
> > + } else gh = gnu_hash(s);
> > +
> > + gho = gh / (8*sizeof(size_t));
> > + ghm = 1ul << gh % (8*sizeof(size_t));
> > +
>
> 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.
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.
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.
