[PATCH] nf_conntrack: optimize hash calculation of tuple

[PATCH] nf_conntrack: optimize hash calculation of tuple

[Yasuyuki KOZAKAI]

[-- Attachment #1: jhash.patch --]
[-- Type: Text/Plain, Size: 2033 bytes --]

[NETFILTER] nf_conntrack: optimize hash calculation of tuple

This reduces the number of calling __jhash_mix() and addition of
JHASH_GOLDEN_RATIO.

Signed-off-by: Yasuyuki Kozakai <yasuyuki.kozakai@toshiba.co.jp>
Signed-off-by: YOSHIFUJI Hideaki <yoshfuji@linux-ipv6.org>

---
commit eac276f083c283360ed15571e8623463a8ace379
tree e7492317c9399f445bef061e76e01546f2517ef9
parent a54c9d30dbb06391ec4422aaf0e1dc2c8c53bd3e
author Yasuyuki Kozakai <yasuyuki.kozakai@toshiba.co.jp> Wed, 24 May 2006 21:16:51 +0900
committer Yasuyuki Kozakai <yasuyuki.kozakai@toshiba.co.jp> Wed, 24 May 2006 21:16:51 +0900

 net/netfilter/nf_conntrack_core.c |   30 ++++++++++++++++++++++++------
 1 files changed, 24 insertions(+), 6 deletions(-)

diff --git a/net/netfilter/nf_conntrack_core.c b/net/netfilter/nf_conntrack_core.c
index f9b83f9..b24edc9 100644
--- a/net/netfilter/nf_conntrack_core.c
+++ b/net/netfilter/nf_conntrack_core.c
@@ -271,13 +271,31 @@ static unsigned int nf_conntrack_hash_rn
 static u_int32_t __hash_conntrack(const struct nf_conntrack_tuple *tuple,
 				  unsigned int size, unsigned int rnd)
 {
-	unsigned int a, b;
-	a = jhash((void *)tuple->src.u3.all, sizeof(tuple->src.u3.all),
-		  ((tuple->src.l3num) << 16) | tuple->dst.protonum);
-	b = jhash((void *)tuple->dst.u3.all, sizeof(tuple->dst.u3.all),
-			(tuple->src.u.all << 16) | tuple->dst.u.all);
+	u32 a, b, c;
 
-	return jhash_2words(a, b, rnd) % size;
+	a = JHASH_GOLDEN_RATIO;
+	b = JHASH_GOLDEN_RATIO;
+	c = rnd;
+
+	a += tuple->src.u3.all[0];
+	b += tuple->src.u3.all[1];
+	c += tuple->src.u3.all[2];
+	__jhash_mix(a, b, c);
+
+	a += tuple->src.u3.all[3],
+	b += (tuple->src.l3num << 16) | tuple->src.u.all;
+	c += tuple->dst.u3.all[0];
+	__jhash_mix(a, b, c);
+
+	a += tuple->dst.u3.all[1];
+	b += tuple->dst.u3.all[2];
+	c += tuple->dst.u3.all[3];
+	__jhash_mix(a, b, c);
+
+	a += (tuple->dst.protonum << 16) | tuple->dst.u.all;
+	__jhash_mix(a, b, c);
+
+	return c % size;
 }
 
 static inline u_int32_t hash_conntrack(const struct nf_conntrack_tuple *tuple)

Re: [PATCH] nf_conntrack: optimize hash calculation of tuple

[Patrick McHardy]

Yasuyuki KOZAKAI wrote:
> [NETFILTER] nf_conntrack: optimize hash calculation of tuple
> 
> This reduces the number of calling __jhash_mix() and addition of
> JHASH_GOLDEN_RATIO.
> 
> Signed-off-by: Yasuyuki Kozakai <yasuyuki.kozakai@toshiba.co.jp>
> Signed-off-by: YOSHIFUJI Hideaki <yoshfuji@linux-ipv6.org>
> 
> ---
> commit eac276f083c283360ed15571e8623463a8ace379
> tree e7492317c9399f445bef061e76e01546f2517ef9
> parent a54c9d30dbb06391ec4422aaf0e1dc2c8c53bd3e
> author Yasuyuki Kozakai <yasuyuki.kozakai@toshiba.co.jp> Wed, 24 May 2006 21:16:51 +0900
> committer Yasuyuki Kozakai <yasuyuki.kozakai@toshiba.co.jp> Wed, 24 May 2006 21:16:51 +0900
> 
>  net/netfilter/nf_conntrack_core.c |   30 ++++++++++++++++++++++++------
>  1 files changed, 24 insertions(+), 6 deletions(-)
> 
> diff --git a/net/netfilter/nf_conntrack_core.c b/net/netfilter/nf_conntrack_core.c
> index f9b83f9..b24edc9 100644
> --- a/net/netfilter/nf_conntrack_core.c
> +++ b/net/netfilter/nf_conntrack_core.c
> @@ -271,13 +271,31 @@ static unsigned int nf_conntrack_hash_rn
>  static u_int32_t __hash_conntrack(const struct nf_conntrack_tuple *tuple,
>  				  unsigned int size, unsigned int rnd)
>  {
> -	unsigned int a, b;
> -	a = jhash((void *)tuple->src.u3.all, sizeof(tuple->src.u3.all),
> -		  ((tuple->src.l3num) << 16) | tuple->dst.protonum);
> -	b = jhash((void *)tuple->dst.u3.all, sizeof(tuple->dst.u3.all),
> -			(tuple->src.u.all << 16) | tuple->dst.u.all);
> +	u32 a, b, c;
>  
> -	return jhash_2words(a, b, rnd) % size;
> +	a = JHASH_GOLDEN_RATIO;
> +	b = JHASH_GOLDEN_RATIO;
> +	c = rnd;
> +
> +	a += tuple->src.u3.all[0];
> +	b += tuple->src.u3.all[1];
> +	c += tuple->src.u3.all[2];
> +	__jhash_mix(a, b, c);
> +
> +	a += tuple->src.u3.all[3],
> +	b += (tuple->src.l3num << 16) | tuple->src.u.all;
> +	c += tuple->dst.u3.all[0];
> +	__jhash_mix(a, b, c);
> +
> +	a += tuple->dst.u3.all[1];
> +	b += tuple->dst.u3.all[2];
> +	c += tuple->dst.u3.all[3];
> +	__jhash_mix(a, b, c);
> +
> +	a += (tuple->dst.protonum << 16) | tuple->dst.u.all;
> +	__jhash_mix(a, b, c);
> +
> +	return c % size;
>  }


That still looks pretty expensive. Is there a reason why you didn't
just add/xor/or/... the individual values until you get down to
three and then use jhash_3words? We could also get rid of the modula
operation by making sure the hash-size is always a power of 2.

Re: [PATCH] nf_conntrack: optimize hash calculation of tuple

[YOSHIFUJI Hideaki / 吉藤英明]

In article <447703F2.90401@trash.net> (at Fri, 26 May 2006 15:34:42 +0200), Patrick McHardy <kaber@trash.net> says:


> > +	return c % size;
> >  }
> 
> 
> That still looks pretty expensive. Is there a reason why you didn't
> just add/xor/or/... the individual values until you get down to
> three and then use jhash_3words? We could also get rid of the modula
> operation by making sure the hash-size is always a power of 2.

I disagree.  Suhc oprations are not good for randomness.
And, gcc is cleaver enough to convert it to shift operation.

--yoshfuji

Re: [PATCH] nf_conntrack: optimize hash calculation of tuple

[Patrick McHardy]

YOSHIFUJI Hideaki / ^[$B5HF#1QL@^[ wrote:
> In article <447703F2.90401@trash.net> (at Fri, 26 May 2006 15:34:42 +0200), Patrick McHardy <kaber@trash.net> says:
> 
> 
> 
>>>+	return c % size;
>>> }
>>
>>
>>That still looks pretty expensive. Is there a reason why you didn't
>>just add/xor/or/... the individual values until you get down to
>>three and then use jhash_3words? We could also get rid of the modula
>>operation by making sure the hash-size is always a power of 2.
> 
> 
> I disagree.  Suhc oprations are not good for randomness.
> And, gcc is cleaver enough to convert it to shift operation.


Assuming you're talking the modula operation: gcc can't do that,
a modula operation can only be represented by a shift for a small
subset of the possible values. The randomness is provided by
jhash + the initial random value. If we rely on randomness by
some assumption about the hash size our code is already broken.
But anyway, this is just a possible micro-optimization, the
real question is why we need three invocations of jhash_mix.

Re: [PATCH] nf_conntrack: optimize hash calculation of tuple

[YOSHIFUJI Hideaki / 吉藤英明]

In article <447707EB.7000401@trash.net> (at Fri, 26 May 2006 15:51:39 +0200), Patrick McHardy <kaber@trash.net> says:

> Assuming you're talking the modula operation: gcc can't do that,
> a modula operation can only be represented by a shift for a small
> subset of the possible values. ...

Sorry, I misunderstood here.

--yoshfuji

Re: [PATCH] nf_conntrack: optimize hash calculation of tuple

[Yasuyuki KOZAKAI]

Hi, Patrick,

> >>That still looks pretty expensive. Is there a reason why you didn't
> >>just add/xor/or/... the individual values until you get down to
> >>three and then use jhash_3words? We could also get rid of the modula
> >>operation by making sure the hash-size is always a power of 2.
> >
> >
> > I disagree.  Suhc oprations are not good for randomness.
> > And, gcc is cleaver enough to convert it to shift operation.
> 
> 
> Assuming you're talking the modula operation: gcc can't do that,
> a modula operation can only be represented by a shift for a small
> subset of the possible values. The randomness is provided by
> jhash + the initial random value. If we rely on randomness by
> some assumption about the hash size our code is already broken.
> But anyway, this is just a possible micro-optimization, the
> real question is why we need three invocations of jhash_mix.

That patch is just the result of extracting jhash() and jhash_2words().
I'm not familiar with hash algorithms. Does the degree of distribution
become bad if we replaces 3 jhash_mix with something like XOR ?

-- kozakai

Re: [PATCH] nf_conntrack: optimize hash calculation of tuple

[Patrick McHardy]

Yasuyuki KOZAKAI wrote:
>>But anyway, this is just a possible micro-optimization, the
>>real question is why we need three invocations of jhash_mix.
> 
> 
> That patch is just the result of extracting jhash() and jhash_2words().
> I'm not familiar with hash algorithms. Does the degree of distribution
> become bad if we replaces 3 jhash_mix with something like XOR ?


I'd say no. jhash was chosen because it has good distribution even
for non uniformly distributed input values, so it shouldn't be
necessary to try to provide more uniformly distributed input values
by hashing multiple times.

Re: [PATCH] nf_conntrack: optimize hash calculation of tuple

[Yasuyuki KOZAKAI]

From: Patrick McHardy <kaber@trash.net>
Date: Fri, 26 May 2006 19:54:21 +0200

> Yasuyuki KOZAKAI wrote:
> >>But anyway, this is just a possible micro-optimization, the
> >>real question is why we need three invocations of jhash_mix.
> > 
> > 
> > That patch is just the result of extracting jhash() and jhash_2words().
> > I'm not familiar with hash algorithms. Does the degree of distribution
> > become bad if we replaces 3 jhash_mix with something like XOR ?
> 
> 
> I'd say no. jhash was chosen because it has good distribution even
> for non uniformly distributed input values, so it shouldn't be
> necessary to try to provide more uniformly distributed input values
> by hashing multiple times.

Well, I don't think so. If we employ a function which has bad
distributin and we use outputs of it as inputs to jhash, the total result
for tuple will have bad distribution.

-- Yasuyuki Kozakai

Re: [PATCH] nf_conntrack: optimize hash calculation of tuple

[Patrick McHardy]

Yasuyuki KOZAKAI wrote:
> From: Patrick McHardy <kaber@trash.net>
> Date: Fri, 26 May 2006 19:54:21 +0200
> 
>>>That patch is just the result of extracting jhash() and jhash_2words().
>>>I'm not familiar with hash algorithms. Does the degree of distribution
>>>become bad if we replaces 3 jhash_mix with something like XOR ?
>>
>>
>>I'd say no. jhash was chosen because it has good distribution even
>>for non uniformly distributed input values, so it shouldn't be
>>necessary to try to provide more uniformly distributed input values
>>by hashing multiple times.
> 
> 
> Well, I don't think so. If we employ a function which has bad
> distributin and we use outputs of it as inputs to jhash, the total result
> for tuple will have bad distribution.

Input distribution shouldn't matter as long as clashes can't
be caused deliberately before jhash is called. A simple way
to avoid this is to use a function that can't be solved for
a specific result without knowledge of a secret:

x = v1 ^ (v2 + secret)

which means you still need 2^31 tries on average to find a
(v1,v2) with two equal results (assuming 4 byte values).