IPv4 ARP hash algorithm has poor distribution

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

@@ -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 - [email protected]
www.tpi.com 406-443-5357

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.