Re: DT_GNU_HASH: reducing working set ...

[Jakub Jelinek <jakub at redhat dot com>]

On Mon, Jul 03, 2006 at 04:15:20PM +0100, Michael Meeks wrote:
> 	Yes - you're quite right - it's crack smoking to want to put -Bdirect
> stuff in that section anyway, as you say: a few minutes thought in a
> less excited state convinced me of that [ sadly while off line ].

Ok, good we are on the same page ;)

> 	OTOH - I do think that allowing the stealing of some bits from the hash
> code [ for other purposes ] in future is prudent, and need not perform
> badly:
> 
> 	if (!(new_hash ^ l->chain[foo]) & l->new_hash_mask))
> 		... hit.
> 
> 	etc. shouldn't be overly slower than a straight comparison surely ?

Djamel privately mentioned to me today that indeed if we require
nbuckets > 1 for valid .gnu.hash sections, we can get the chain
termination bit for free, i.e. not causing any extra collisions.
That's because if nbuckets > 1, then (hash+1) % nbuckets != hash % nbuckets,
so the bottom-most bit is effectively encoded in the bucket.

So we can get rid of the chain length words, and in that case we can
get rid of the symbol index word as well.

We have 2 options, either we create a 1:1 correspondence between the chain
position and .dynsym index (and perhaps sort the UNDEF symbols high, so that
we can trim the end of the .gnu.hash section), or we can store some addend
into the second word of .gnu.hash (before the buckets array).
ELF requires that the STB_LOCAL symbols are at the beginning, not end of
the .dynsym section.  The UNDEF symbols can of course be anywhere (after
the STB_LOCAL symbols).  On most of the arches there are only a few
STB_LOCAL symbols (< ~20), but on e.g. ia64 there are really many
(e.g. ia64 glibc has ~ 420 such symbols, all caused by relocations).
So, perhaps using the addend would be best.

It will limit us a little bit in the reordering to minimize chains crossing
cacheline boundaries in that we no longer can have padding/gaps in there
(well, we could store some UNDEF symbols there), but we still can do some
reordering.

I will rework the patch now.

	Jakub