Re: [PATCH] xfrm: xfrm hash to use Jenkins' hash

[David Miller <davem@davemloft.net>]

From: Jussi Mäki <joamaki@gmail.com>
Date: Wed, 5 Aug 2009 10:41:42 +0300

> Hi,
> 
> The current xfrm hash functions perform very poorly when a number of
> policies have the same
> last byte in source and destination addresses.
> 
> For example with __xfrm_dst_hash, hmask of 0xfff:
> 
> 192.168.0.1-172.16.0.1 hashes to 3258
> 192.168.0.2-172.16.0.2 hashes to 3258
> ... and so on.
> 
> This patch addresses the issue by rewriting the xfrm
> hash functions to use the Jenkins' hash function.
> 
> Signed-off-by: Jussi Maki <joamaki@gmail.com>

jhash expands to a lot of code, and given your description of the
problem, you could have fixed it by adding 2 instructions (see below)
instead of 20 or 30 (jhash instruction count) at every hash
calculation site.

Simply change every instance of:

	(h >> 16)

with

	((h >> 16) ^ (h >> 24))

As much as I love jhash, it's overkill for fixing this problem.

And if we do end up using jhash, it should get inlined into a
seperate non-inline function instead of expanding that monster
4 or 5 times throughout the XFRM code.

I'm not applying this, either make the simple one-liner fix I
suggested above work or move the jhash into a non-inline expansion.