Re: [PATCH-RFC] Improve randomness of hash_long on 64bit.

[Andrew Morton]

NeilBrown <neilb@xxxxxxx> wrote:
>
> I'm still bothered by the poor showing on hash_long on 64bit
>  on number that differ only in the 3rd or 4th byte (as IP addresses might
>  on a little-endian host).
>  I hacked around the problem in net/sunrpc/svcauth_unix.c until this
>  issue got resolved, but it never did.  So I am pushing again.
> 
>  The problem is that the bit-spares prime that is close to the
>  golden ratio isn't really close enough.
> 
>  I propose 'fixing' it by using hash_u32 on the upper and lower halfs
>  of a 64bit value.  This is slightly less efficient, but most code would
>  probably be happy calling hash_u32 anyway.

We end up with

static inline u32 hash_u32(u32 val, unsigned int bits)
{
	u32 hash = val;

	/* On some cpus multiply is faster, on others gcc will do shifts */
	hash *= GOLDEN_RATIO_PRIME_32;

	/* High bits are more random, so use them. */
	return hash >> (32 - bits);
}

static inline u32 hash_u64(u64 val, unsigned int bits)
{
	u32 hi = val >> 32;
	return hash_u32(hash_u32(val, 32) ^ hi, bits);
}

So if one does

	hash_u64(foo, 44)

we have a negative shift distance.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/