lkml.org 
[lkml]   [2006]   [Jun]   [1]   [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 11:41:27AM -0700, David Miller (davem@davemloft.net) wrote:
> > > 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.
>
> You absolutely show not do this shifting on the jenkins hash
> result, you destroy the distribution entirely. Just mask
> it with the hash mask and that's all you need to do.
>
> Brian is right, this is absolutely critical to using the Jenkins hash
> correctly. You're "unmixing" the bits it worked so hard to mix.

That is wrong. And I have a code and picture to show that,
and you dont - prove me wrong :)

Attached code and picture which shows _exactly_ the same distribution for
folded and not folded Jenkins hash distribution, and it's artifact
compared to XOR hash.

Fairly distributed values being XORed produce still fairly distributed
value.

--
Evgeniy Polyakov
[unhandled content-type:image/png]#include <stdlib.h>
#include <stdio.h>
#include <errno.h>

typedef unsigned int u32;
typedef unsigned short u16;
typedef unsigned char u8;

typedef unsigned int __u32;
typedef unsigned short __u16;
typedef unsigned char __u8;

#include "jhash.h"

struct hash_entry
{
unsigned long counter;
};
static inline num2ip(__u8 a1, __u8 a2, __u8 a3, __u8 a4)
{
__u32 a = 0;
a |= a1;
a << 8;
a |= a2;
a << 8;
a |= a3;
a << 8;
a |= a4;
return a;
}
static inline __u8 get_random_byte(void)
{
return 1 + (int) (255.0 * (rand() / (RAND_MAX + 1.0)));
}
static inline __u16 get_random_word(void)
{
return 1 + (int) (65536.0 * (rand() / (RAND_MAX + 1.0)));
}
unsigned int hash_addr(__u32 faddr, __u16 fport, __u32 laddr, __u16 lport)
{
unsigned int h = (laddr ^ lport) ^ (faddr ^ fport);
h ^= h >> 16;
h ^= h >> 8;
return h;
}
unsigned int hash_addr1(__u32 faddr, __u16 fport, __u32 laddr, __u16 lport)
{
u32 ports;
unsigned int h;
ports = lport;
ports <<= 16;
ports |= fport;
h = jhash_2words(faddr, laddr, ports);
//h ^= h >> 16;
//h ^= h >> 8;
return h;
}
int main()
{
struct hash_entry *table;
__u32 saddr, daddr;
__u16 sport, dport;
unsigned int hash, i, *results;
unsigned int hash_size = 65536, iter_num = 100;
table = malloc(hash_size * sizeof(struct hash_entry));
if (!table)
return -ENOMEM;
results = malloc(hash_size * sizeof(unsigned int));
if (!results)
return -ENOMEM;
for (i=0; i<hash_size; ++i) {
results[i] = 0;
table[i].counter = 0;
}
srand(time(NULL));

daddr = num2ip(192, 168, 0, 1);
dport = htons(80);

for (i=0; i<hash_size*iter_num; ++i) {
saddr = num2ip(get_random_byte(), get_random_byte(), get_random_byte(), get_random_byte());
sport = get_random_word();
hash = hash_addr(saddr, sport, daddr, dport);
hash &= (hash_size - 1);

table[hash].counter++;
}
for (i=0; i<hash_size; ++i)
results[table[i].counter]++;

for (i=0; i<hash_size; ++i)
printf("%u %u\n", i, results[i]);
//printf("%u %u\n", i, table[i].counter);
}
\
 
 \ /
  Last update: 2006-06-01 08:07    [from the cache]
©2003-2011 Jasper Spaans