[PATCH] IPv4 ARP hash algorithm has poor distribution

[PATCH] IPv4 ARP hash algorithm has poor distribution

[Tim Gardner]

The current IPv4 ARP hash algorithm does not generate evenly distributed hash 
indices.

Included is a patch to fix the hash algorithm such that it will generate an 
even distribution of hash indices within a single subnet. It also uses the 
network bits of the address to attempt to avoid collisions with other 
subnets.

On my my router with 991 ARP entries, this algorithm utilized 669 out of 1024 
hash buckets. The old algorithm utilized 169.

rtg

<-Snip-->

diff -r -u --new-file linux-2.4.bk/net/ipv4/arp.c 
linux-2.4.bk-arp-hash/net/ipv4/arp.c
--- linux-2.4.bk/net/ipv4/arp.c	2004-03-15 11:24:07.000000000 -0700
+++ linux-2.4.bk-arp-hash/net/ipv4/arp.c	2004-03-15 10:15:48.000000000 -0700
@@ -215,11 +215,9 @@
 {
 	u32 hash_val;
 
-	hash_val = *(u32*)pkey;
+	hash_val = ntohl(*(u32*)pkey);
 	hash_val ^= (hash_val>>16);
-	hash_val ^= hash_val>>8;
-	hash_val ^= hash_val>>3;
-	hash_val = (hash_val^dev->ifindex)&(arp_tbl.num_hash_buckets-1);
+	hash_val &= (arp_tbl.num_hash_buckets-1);
 
 	return hash_val;
 }

-- 
Tim Gardner - timg@tpi.com
www.tpi.com 406-443-5357

Re: [PATCH] IPv4 ARP hash algorithm has poor distribution

[David S. Miller]

If you're going to change the hash algorithm, just use the linux/jhash.h stuff.
I'm sure it will give stunning hash chain distribution as it does for everything
else we've used it for.