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    [W:0.028 / U:89.928 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site