Re: DT_GNU_HASH: reducing working set ...

[Michael Meeks <michael.meeks@novell.com>]

On Mon, 2006-07-03 at 17:59 +0200, Jakub Jelinek wrote:
> Ok, good we are on the same page ;)

	:-)

> 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.

	Ah - that's a neat trick: nice [ not that it isn't worth the single bit
anyway of course, as per convoluted calculations ;-]

> 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).

	The addend sounds nice.

	Of course - it depends on how hard to calculate the hash function is:
we could of course use a rather stronger / slower hash: and simply store
the value for all symbols [ regardless of def/undef etc. ] in the .chain
- and instead of calculating, look them up. [ Of course to calculate the
string hash we have to take a .dynstr cache miss in the 1st place so -
perhaps it's worthwhile ? ].

	Of course, if we do that, then it does in fact make sense to have the
-Bdirect indexes next to the undef symbols, so - OTOH - perhaps that
sort of thing does belong in another section;

> ELF requires that the STB_LOCAL symbols are at the beginning, not end of
> the .dynsym section.

	Yep - I fell over that :-)

>   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.

	That's interesting; I have an architecturally blinkered view.

> I will rework the patch now.

	Thanks,

		Michael.	

-- 
 michael.meeks@novell.com  <><, Pseudo Engineer, itinerant idiot