ARP does not scale

ARP does not scale

[Tim Gardner]

ARP has hash table and garbage collection scalability limitations.

Please find attached a patch for 2.4.24 (also works for 2.4.25) that allows
you to choose the size of your ARP hash table. Simply choosing the ARP hash
table size that suits your network can cut the ARP list search time by an
order of magnitude. For example, the default hash table size is 32. My
network has over 1000 nodes. If you assume the hash function spreads those
evenly, then there are approximately 31 hash collisions per bucket.
Increasing the hash table size to 512 cuts down the collisions to
approximately 2 per bucket.

Related to scalability is the ARP entry garbage collector. It is currently
coded such that it runs at periodic intervals and processes all ARP entries
in all hash table buckets all within one invocation. As the number of ARP
entries becomes large, the amount of time spent processing all of the ARP
entries also becomes large. At a certain point I think it will begin to cause
significant jitter in packet delivery times. In an effort to smooth out the
garbage collector impact I've recoded it to only process one hash bucket per
invocation. The garbage collector resets its timer so that it processes all
buckets at least once every 60 seconds.

rtg

<--SNIP-->

diff -r -u --new-file linux-2.4.24/Documentation/Configure.help 
linux-2.4.24.arp/Documentation/Configure.help
--- linux-2.4.24/Documentation/Configure.help	2004-03-12 07:34:37.000000000 
-0700
+++ linux-2.4.24.arp/Documentation/Configure.help	2004-03-12 
09:07:01.000000000 -0700
@@ -6921,6 +6921,13 @@
 
   If unsure, say N.
 
+ARP hash table size power of 2
+CONFIG_NEIGH_NUM_HASHBITS
+  This option defines the size of the ARP hash table for each protocol. The 
default size of 5
+  bits (32) is adequate for small LANs. Larger LANs may have enough ARP 
entries that there are
+  multiple hash table collisions. In that case, increasing the number of hash 
table entries
+  improves ARP entry access performance at the expense of some RAM.
+
 Packet socket
 CONFIG_PACKET
   The Packet protocol is used by applications which communicate
diff -r -u --new-file linux-2.4.24/include/net/neighbour.h 
linux-2.4.24.arp/include/net/neighbour.h
--- linux-2.4.24/include/net/neighbour.h	2004-03-12 07:34:44.000000000 -0700
+++ linux-2.4.24.arp/include/net/neighbour.h	2004-03-12 09:35:07.000000000 
-0700
@@ -128,7 +128,7 @@
 	u8			key[0];
 };
 
-#define NEIGH_HASHMASK		0x1F
+#define NEIGH_HASHMASK		((1<<CONFIG_NEIGH_NUM_HASHBITS)-1)
 #define PNEIGH_HASHMASK		0xF
 
 /*
@@ -166,6 +166,7 @@
 	struct tasklet_struct	gc_task;
 	struct neigh_statistics	stats;
 	struct neighbour	*hash_buckets[NEIGH_HASHMASK+1];
+	int					curr_hash_bucket;
 	struct pneigh_entry	*phash_buckets[PNEIGH_HASHMASK+1];
 };
 
diff -r -u --new-file linux-2.4.24/net/Config.in 
linux-2.4.24.arp/net/Config.in
--- linux-2.4.24/net/Config.in	2004-03-12 07:33:30.000000000 -0700
+++ linux-2.4.24.arp/net/Config.in	2004-03-12 09:05:10.000000000 -0700
@@ -8,6 +8,8 @@
    bool '  Packet socket: mmapped IO' CONFIG_PACKET_MMAP
 fi
 
+int 'ARP hash table size power of 2' CONFIG_NEIGH_NUM_HASHBITS 5
+
 tristate 'Netlink device emulation' CONFIG_NETLINK_DEV
 
 bool 'Network packet filtering (replaces ipchains)' CONFIG_NETFILTER
diff -r -u --new-file linux-2.4.24/net/core/neighbour.c 
linux-2.4.24.arp/net/core/neighbour.c
--- linux-2.4.24/net/core/neighbour.c	2004-03-12 07:33:13.000000000 -0700
+++ linux-2.4.24.arp/net/core/neighbour.c	2004-03-12 09:36:35.000000000 -0700
@@ -566,9 +566,8 @@
 static void SMP_TIMER_NAME(neigh_periodic_timer)(unsigned long arg)
 {
 	struct neigh_table *tbl = (struct neigh_table*)arg;
+	struct neighbour *n, **np;
 	unsigned long now = jiffies;
-	int i;
-
 
 	write_lock(&tbl->lock);
 
@@ -583,46 +582,48 @@
 			p->reachable_time = neigh_rand_reach_time(p->base_reachable_time);
 	}
 
-	for (i=0; i <= NEIGH_HASHMASK; i++) {
-		struct neighbour *n, **np;
+	tbl->curr_hash_bucket &= NEIGH_HASHMASK;
+	np = &tbl->hash_buckets[tbl->curr_hash_bucket++];
 
-		np = &tbl->hash_buckets[i];
-		while ((n = *np) != NULL) {
-			unsigned state;
-
-			write_lock(&n->lock);
-
-			state = n->nud_state;
-			if (state&(NUD_PERMANENT|NUD_IN_TIMER)) {
-				write_unlock(&n->lock);
-				goto next_elt;
-			}
+	while ((n = *np) != NULL) {
+		unsigned state;
 
-			if ((long)(n->used - n->confirmed) < 0)
-				n->used = n->confirmed;
+		write_lock(&n->lock);
 
-			if (atomic_read(&n->refcnt) == 1 &&
-			    (state == NUD_FAILED || now - n->used > n->parms->gc_staletime)) {
-				*np = n->next;
-				n->dead = 1;
-				write_unlock(&n->lock);
-				neigh_release(n);
-				continue;
-			}
+		state = n->nud_state;
+		if (state&(NUD_PERMANENT|NUD_IN_TIMER)) {
+			write_unlock(&n->lock);
+			goto next_elt;
+		}
 
-			if (n->nud_state&NUD_REACHABLE &&
-			    now - n->confirmed > n->parms->reachable_time) {
-				n->nud_state = NUD_STALE;
-				neigh_suspect(n);
-			}
+		if ((long)(n->used - n->confirmed) < 0)
+			n->used = n->confirmed;
+
+		if (atomic_read(&n->refcnt) == 1 &&
+		    (state == NUD_FAILED || now - n->used > n->parms->gc_staletime)) {
+			*np = n->next;
+			n->dead = 1;
 			write_unlock(&n->lock);
+			neigh_release(n);
+			continue;
+		}
 
-next_elt:
-			np = &n->next;
+		if (n->nud_state&NUD_REACHABLE &&
+		    now - n->confirmed > n->parms->reachable_time) {
+			n->nud_state = NUD_STALE;
+			neigh_suspect(n);
 		}
+		write_unlock(&n->lock);
+
+next_elt:
+		np = &n->next;
 	}
 
-	mod_timer(&tbl->gc_timer, now + tbl->gc_interval);
+	/*
+	 * Cycle through all hash buckets every 60 seconds.
+	 */
+	mod_timer(&tbl->gc_timer, now+((HZ*60)/(NEIGH_HASHMASK+1)));
+
 	write_unlock(&tbl->lock);
 }
 

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

Re: ARP does not scale

[Anton Blanchard]

[moving this to netdev]

> ARP has hash table and garbage collection scalability limitations.
> 
> Please find attached a patch for 2.4.24 (also works for 2.4.25) that allows
> you to choose the size of your ARP hash table. Simply choosing the ARP hash
> table size that suits your network can cut the ARP list search time by an
> order of magnitude. For example, the default hash table size is 32. My
> network has over 1000 nodes. If you assume the hash function spreads those
> evenly, then there are approximately 31 hash collisions per bucket.
> Increasing the hash table size to 512 cuts down the collisions to
> approximately 2 per bucket.

It would be nice to fix this properly in 2.6, a CONFIG option for this sort 
of thing is painful for distros.

Check out net/ipv4/tcp.c and how it makes an effort to scale tcp_ehash and 
tcp_bhash with memory and also allows an override with a cmdline option 
thash_entries.

Anton

> Related to scalability is the ARP entry garbage collector. It is currently
> coded such that it runs at periodic intervals and processes all ARP entries
> in all hash table buckets all within one invocation. As the number of ARP
> entries becomes large, the amount of time spent processing all of the ARP
> entries also becomes large. At a certain point I think it will begin to cause
> significant jitter in packet delivery times. In an effort to smooth out the
> garbage collector impact I've recoded it to only process one hash bucket per
> invocation. The garbage collector resets its timer so that it processes all
> buckets at least once every 60 seconds.
> 
> rtg
> 
> <--SNIP-->
> 
> diff -r -u --new-file linux-2.4.24/Documentation/Configure.help 
> linux-2.4.24.arp/Documentation/Configure.help
> --- linux-2.4.24/Documentation/Configure.help	2004-03-12 07:34:37.000000000 
> -0700
> +++ linux-2.4.24.arp/Documentation/Configure.help	2004-03-12 
> 09:07:01.000000000 -0700
> @@ -6921,6 +6921,13 @@
>  
>    If unsure, say N.
>  
> +ARP hash table size power of 2
> +CONFIG_NEIGH_NUM_HASHBITS
> +  This option defines the size of the ARP hash table for each protocol. The 
> default size of 5
> +  bits (32) is adequate for small LANs. Larger LANs may have enough ARP 
> entries that there are
> +  multiple hash table collisions. In that case, increasing the number of hash 
> table entries
> +  improves ARP entry access performance at the expense of some RAM.
> +
>  Packet socket
>  CONFIG_PACKET
>    The Packet protocol is used by applications which communicate
> diff -r -u --new-file linux-2.4.24/include/net/neighbour.h 
> linux-2.4.24.arp/include/net/neighbour.h
> --- linux-2.4.24/include/net/neighbour.h	2004-03-12 07:34:44.000000000 -0700
> +++ linux-2.4.24.arp/include/net/neighbour.h	2004-03-12 09:35:07.000000000 
> -0700
> @@ -128,7 +128,7 @@
>  	u8			key[0];
>  };
>  
> -#define NEIGH_HASHMASK		0x1F
> +#define NEIGH_HASHMASK		((1<<CONFIG_NEIGH_NUM_HASHBITS)-1)
>  #define PNEIGH_HASHMASK		0xF
>  
>  /*
> @@ -166,6 +166,7 @@
>  	struct tasklet_struct	gc_task;
>  	struct neigh_statistics	stats;
>  	struct neighbour	*hash_buckets[NEIGH_HASHMASK+1];
> +	int					curr_hash_bucket;
>  	struct pneigh_entry	*phash_buckets[PNEIGH_HASHMASK+1];
>  };
>  
> diff -r -u --new-file linux-2.4.24/net/Config.in 
> linux-2.4.24.arp/net/Config.in
> --- linux-2.4.24/net/Config.in	2004-03-12 07:33:30.000000000 -0700
> +++ linux-2.4.24.arp/net/Config.in	2004-03-12 09:05:10.000000000 -0700
> @@ -8,6 +8,8 @@
>     bool '  Packet socket: mmapped IO' CONFIG_PACKET_MMAP
>  fi
>  
> +int 'ARP hash table size power of 2' CONFIG_NEIGH_NUM_HASHBITS 5
> +
>  tristate 'Netlink device emulation' CONFIG_NETLINK_DEV
>  
>  bool 'Network packet filtering (replaces ipchains)' CONFIG_NETFILTER
> diff -r -u --new-file linux-2.4.24/net/core/neighbour.c 
> linux-2.4.24.arp/net/core/neighbour.c
> --- linux-2.4.24/net/core/neighbour.c	2004-03-12 07:33:13.000000000 -0700
> +++ linux-2.4.24.arp/net/core/neighbour.c	2004-03-12 09:36:35.000000000 -0700
> @@ -566,9 +566,8 @@
>  static void SMP_TIMER_NAME(neigh_periodic_timer)(unsigned long arg)
>  {
>  	struct neigh_table *tbl = (struct neigh_table*)arg;
> +	struct neighbour *n, **np;
>  	unsigned long now = jiffies;
> -	int i;
> -
>  
>  	write_lock(&tbl->lock);
>  
> @@ -583,46 +582,48 @@
>  			p->reachable_time = neigh_rand_reach_time(p->base_reachable_time);
>  	}
>  
> -	for (i=0; i <= NEIGH_HASHMASK; i++) {
> -		struct neighbour *n, **np;
> +	tbl->curr_hash_bucket &= NEIGH_HASHMASK;
> +	np = &tbl->hash_buckets[tbl->curr_hash_bucket++];
>  
> -		np = &tbl->hash_buckets[i];
> -		while ((n = *np) != NULL) {
> -			unsigned state;
> -
> -			write_lock(&n->lock);
> -
> -			state = n->nud_state;
> -			if (state&(NUD_PERMANENT|NUD_IN_TIMER)) {
> -				write_unlock(&n->lock);
> -				goto next_elt;
> -			}
> +	while ((n = *np) != NULL) {
> +		unsigned state;
>  
> -			if ((long)(n->used - n->confirmed) < 0)
> -				n->used = n->confirmed;
> +		write_lock(&n->lock);
>  
> -			if (atomic_read(&n->refcnt) == 1 &&
> -			    (state == NUD_FAILED || now - n->used > n->parms->gc_staletime)) {
> -				*np = n->next;
> -				n->dead = 1;
> -				write_unlock(&n->lock);
> -				neigh_release(n);
> -				continue;
> -			}
> +		state = n->nud_state;
> +		if (state&(NUD_PERMANENT|NUD_IN_TIMER)) {
> +			write_unlock(&n->lock);
> +			goto next_elt;
> +		}
>  
> -			if (n->nud_state&NUD_REACHABLE &&
> -			    now - n->confirmed > n->parms->reachable_time) {
> -				n->nud_state = NUD_STALE;
> -				neigh_suspect(n);
> -			}
> +		if ((long)(n->used - n->confirmed) < 0)
> +			n->used = n->confirmed;
> +
> +		if (atomic_read(&n->refcnt) == 1 &&
> +		    (state == NUD_FAILED || now - n->used > n->parms->gc_staletime)) {
> +			*np = n->next;
> +			n->dead = 1;
>  			write_unlock(&n->lock);
> +			neigh_release(n);
> +			continue;
> +		}
>  
> -next_elt:
> -			np = &n->next;
> +		if (n->nud_state&NUD_REACHABLE &&
> +		    now - n->confirmed > n->parms->reachable_time) {
> +			n->nud_state = NUD_STALE;
> +			neigh_suspect(n);
>  		}
> +		write_unlock(&n->lock);
> +
> +next_elt:
> +		np = &n->next;
>  	}
>  
> -	mod_timer(&tbl->gc_timer, now + tbl->gc_interval);
> +	/*
> +	 * Cycle through all hash buckets every 60 seconds.
> +	 */
> +	mod_timer(&tbl->gc_timer, now+((HZ*60)/(NEIGH_HASHMASK+1)));
> +
>  	write_unlock(&tbl->lock);
>  }
>  
> 
> --
> Tim Gardner - timg@tpi.com
> www.tpi.com 406-443-5357
> 
> 
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/

Re: ARP does not scale

[Tim Gardner]

On Saturday 13 March 2004 16:32, Anton Blanchard wrote:
> [moving this to netdev]

Anton,

I figured out how to subscribe.

> It would be nice to fix this properly in 2.6, a CONFIG option for this sort
> of thing is painful for distros.
>
> Check out net/ipv4/tcp.c and how it makes an effort to scale tcp_ehash and
> tcp_bhash with memory and also allows an override with a cmdline option
> thash_entries.
>
> Anton
>

I checked out how tcp_ehash and tcp_bhash auto-size based on the amount of 
RAM. I think one can usually make the same assumption about the relative 
number of ARP entries. I say usually because I have some core routers that 
have over a thousand ARP entries. In that case I would like to override the 
auto-size calculation so that I can force enough hash buckets such that there 
is never (or rarely) a hash collision.

How about a compromise. Leave in the config option, but default it to 0 which 
enables the auto-size algorithm. Otherwise, use the size specified in the 
config option. 

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

Re: ARP does not scale

[Mike Fedyk]

Tim Gardner wrote:
> ARP has hash table and garbage collection scalability limitations.
> 

Is this needed for 2.6 also?