From mboxrd@z Thu Jan 1 00:00:00 1970 From: Patrick McHardy Subject: Re: [PATCH] nf_conntrack: optimize hash calculation of tuple Date: Fri, 26 May 2006 15:34:42 +0200 Message-ID: <447703F2.90401@trash.net> References: <200605260015.k4Q0FpPC024839@toshiba.co.jp> Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-15 Content-Transfer-Encoding: 7bit Cc: netfilter-devel@lists.netfilter.org Return-path: To: Yasuyuki KOZAKAI In-Reply-To: <200605260015.k4Q0FpPC024839@toshiba.co.jp> List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: netfilter-devel-bounces@lists.netfilter.org Errors-To: netfilter-devel-bounces@lists.netfilter.org List-Id: netfilter-devel.vger.kernel.org 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 > Signed-off-by: YOSHIFUJI Hideaki > > --- > commit eac276f083c283360ed15571e8623463a8ace379 > tree e7492317c9399f445bef061e76e01546f2517ef9 > parent a54c9d30dbb06391ec4422aaf0e1dc2c8c53bd3e > author Yasuyuki Kozakai Wed, 24 May 2006 21:16:51 +0900 > committer Yasuyuki Kozakai 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.