Date: Wed, 31 May 2006 17:06:15 +0400
From: Evgeniy Polyakov <johnpol@2ka.mipt.ru>
To: David Miller <davem@davemloft.net>, draghuram@rocketmail.com,
       linux-kernel@vger.kernel.org, netdev@vger.kernel.org
Cc: "Brian F. G. Bidulock" <bidulock@openss7.org>
Subject: Re: Question about tcp hash function tcp_hashfn()
Message-ID: <20060531130615.GA32362@2ka.mipt.ru>
References: <20060530235525.A30563@openss7.org> <20060531.001027.60486156.davem@davemloft.net> <20060531014540.A1319@openss7.org> <20060531.004953.91760903.davem@davemloft.net> <20060531020009.A1868@openss7.org> <20060531090301.GA26782@2ka.mipt.ru> <20060531035124.B3065@openss7.org> <20060531105814.GB7806@2ka.mipt.ru> <20060531110459.GA20551@2ka.mipt.ru>
Mime-Version: 1.0
Content-Type: text/plain; charset=koi8-r
Content-Disposition: inline
In-Reply-To: <20060531110459.GA20551@2ka.mipt.ru>
User-Agent: Mutt/1.5.9i
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 1965
Lines: 52

On Wed, May 31, 2006 at 03:04:59PM +0400, Evgeniy Polyakov (johnpol@2ka.mipt.ru) wrote:
> On Wed, May 31, 2006 at 02:58:18PM +0400, Evgeniy Polyakov (johnpol@2ka.mipt.ru) wrote:
> > On Wed, May 31, 2006 at 03:51:24AM -0600, Brian F. G. Bidulock (bidulock@openss7.org) wrote:
> > > Evgeniy,
> > > 
> > > On Wed, 31 May 2006, Evgeniy Polyakov wrote:
> > > > 2. Compared Jenkins hash with XOR hash used in TCP socket selection code.
> > > > http://tservice.net.ru/~s0mbre/blog/2006/05/14#2006_05_14
> > > 
> > > Two problems with the comparison:
> > > 
> > >   Port numbers can be collected into a 32 bit register in network
> > >   byte order directly from the TCP packet without taking two 16 bit
> > >   values and shifting and or'ing them.
> > 
> > They are.
> > 
> > u32 ports;
> > 
> > ports = lport;
> > ports <<= 16;
> > ports |= fport;
> 
> Using network or host byte order does not affect hash distribution,
> that shifting was coded to simulate other types of mixing ports,
> which actually never showed different results.
> 
> > >   Worse: he folded the jenkins algorith result with
> > > 
> > >    h ^= h >> 16;
> > >    h ^= h >> 8;
> > > 
> > >   Destroying the coverage of the function.
> > 
> > It was done to simulate socket code which uses the same folding.
> > Leaving 32bit space is just wrong, consider hash table size with that
> > index.

Btw, that probably requires some clarification.
Since hash table size is definitely less than returned hash value, so
higher bits are removed, for that case above folding is done both in
XOR hash and my test case. 
It is possible to just remove higher bits, but fairly ditributed parts
being xored produce still fairly distributed value.

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