netdev - Re: arp

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20150322215612.GA8274@gondor.apana.org.au>
Date:	Mon, 23 Mar 2015 08:56:12 +1100
From:	Herbert Xu <herbert@...dor.apana.org.au>
To:	Eric Dumazet <eric.dumazet@...il.com>
Cc:	"David S. Miller" <davem@...emloft.net>, netdev@...r.kernel.org,
	Roland Dreier <roland@...estorage.com>
Subject: Re: arp_hash

On Sun, Mar 22, 2015 at 05:56:21AM -0700, Eric Dumazet wrote:
> On Sun, 2015-03-22 at 22:42 +1100, Herbert Xu wrote:
> > 
> > While googling I found the 2011 discussion on changing the arp_hash
> > function.  I must say that I'm not really impressed by the new
> > function that replaced jhash :)
> > 
> > 	u32 key = *(const u32 *)pkey;
> > 	u32 val = key ^ hash32_ptr(dev);
> > 
> > 	return val * hash_rnd[0];

In fact this function is worse than I thought.  Because the IP
address is stored in big-endian, the low bits correspond to the
first octet.  So in any network smaller than a /8 everything
hashes the same value.

Try running the following program with say 4096.

If this really didn't matter why don't you guys just use a linked
list? Surely that is going to be faster than doing a multiply :)

#include <stdio.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>

typedef unsigned char u8;
typedef unsigned int u32;

static inline u32 hash32_ptr(const void *ptr)
{
        unsigned long val = (unsigned long)ptr;

        val ^= (val >> 32);
        return (u32)val;
}

static inline u32 arp_hashfn(const void *pkey, const void *dev, u32 hash_rnd)
{
        u32 key = *(const u32 *)pkey;
        u32 val = key ^ hash32_ptr(dev);

        return val * hash_rnd;
}

int main(int argc, char **argv)
{
        int i;
        union {
                void *s;
                void *t;
                u32 l;
                in_addr_t a;
        } k = { .s = 0 };
        int total;

        total = atoi(argv[1]);

        k.a = inet_addr("10.0.0.0");

        for (i = 0; i < total; i++) {
                k.l = htonl(ntohl(k.l) + 1);
                printf("%s 0x%x\n", inet_ntoa(k.a), arp_hashfn(&k, (void *)0xffff88043d760000, 12345) & (total - 1));
        }

        return 0;
}

Cheers,
-- 
Email: Herbert Xu <herbert@...dor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html