lkml.org 
[lkml]   [2006]   [May]   [31]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: Question about tcp hash function tcp_hashfn()
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/

\
 
 \ /
  Last update: 2006-05-31 15:09    [W:0.090 / U:2.680 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site