[PATCH] [1/2] Skip empty hash buckets faster in /proc/net/tcp

[PATCH] [1/2] Skip empty hash buckets faster in /proc/net/tcp

[Andi Kleen]

On most systems most of the TCP established/time-wait hash buckets are empty.
When walking the hash table for /proc/net/tcp their read locks would
always be aquired just to find out they're empty. This patch changes the code
to check first if the buckets have any entries before taking the lock, which
is much cheaper than taking a lock. Since the hash tables are large
this makes a measurable difference on processing /proc/net/tcp, 
especially on architectures with slow read_lock (e.g. PPC) 

On a 2GB Core2 system here I see a time cat /proc/net/tcp > /dev/null
constently dropping from 0.44s to 0.4-0.8s system time with this change.
This is with mostly empty hash tables.

On systems with slower atomics (like P4 or POWER4) or larger hash tables
(more RAM) the difference is much higher.

This can be noticeable because there are some daemons around who regularly
scan /proc/net/tcp.

Original idea for this patch from Marcus Meissner, but redone by me.

Cc: meissner@suse.de
Signed-off-by: Andi Kleen <ak@suse.de>

---
 net/ipv4/tcp_ipv4.c |   30 ++++++++++++++++++------------
 1 file changed, 18 insertions(+), 12 deletions(-)

Index: linux/net/ipv4/tcp_ipv4.c
===================================================================
--- linux.orig/net/ipv4/tcp_ipv4.c
+++ linux/net/ipv4/tcp_ipv4.c
@@ -2039,6 +2039,12 @@ static void *listening_get_idx(struct se
 	return rc;
 }
 
+static inline int empty_bucket(struct tcp_iter_state *st)
+{
+	return hlist_empty(&tcp_hashinfo.ehash[st->bucket].chain) &&
+		hlist_empty(&tcp_hashinfo.ehash[st->bucket].twchain);
+}
+
 static void *established_get_first(struct seq_file *seq)
 {
 	struct tcp_iter_state* st = seq->private;
@@ -2050,6 +2056,10 @@ static void *established_get_first(struc
 		struct inet_timewait_sock *tw;
 		rwlock_t *lock = inet_ehash_lockp(&tcp_hashinfo, st->bucket);
 
+		/* Lockless fast path for the common case of empty buckets */
+		if (empty_bucket(st))
+			continue;
+
 		read_lock_bh(lock);
 		sk_for_each(sk, node, &tcp_hashinfo.ehash[st->bucket].chain) {
 			if (sk->sk_family != st->family) {
@@ -2097,13 +2107,15 @@ get_tw:
 		read_unlock_bh(inet_ehash_lockp(&tcp_hashinfo, st->bucket));
 		st->state = TCP_SEQ_STATE_ESTABLISHED;
 
-		if (++st->bucket < tcp_hashinfo.ehash_size) {
-			read_lock_bh(inet_ehash_lockp(&tcp_hashinfo, st->bucket));
-			sk = sk_head(&tcp_hashinfo.ehash[st->bucket].chain);
-		} else {
-			cur = NULL;
-			goto out;
-		}
+		/* Look for next non empty bucket */
+		while (++st->bucket < tcp_hashinfo.ehash_size &&
+				empty_bucket(st))
+			;
+		if (st->bucket >= tcp_hashinfo.ehash_size)
+			return NULL;
+
+		read_lock_bh(inet_ehash_lockp(&tcp_hashinfo, st->bucket));
+		sk = sk_head(&tcp_hashinfo.ehash[st->bucket].chain);
 	} else
 		sk = sk_next(sk);
 

[PATCH] [2/2] Remove some unnecessary gotos in established_get_first()

[Andi Kleen]

gcc does not generate different code for return foo vs bar = foo; goto x;
x: return bar; So convert it all to direct returns for better readability.

Signed-off-by: Andi Kleen <ak@suse.de>

Index: linux/net/ipv4/tcp_ipv4.c
===================================================================
--- linux.orig/net/ipv4/tcp_ipv4.c
+++ linux/net/ipv4/tcp_ipv4.c
@@ -2065,8 +2065,7 @@ static void *established_get_first(struc
 			if (sk->sk_family != st->family) {
 				continue;
 			}
-			rc = sk;
-			goto out;
+			return sk;
 		}
 		st->state = TCP_SEQ_STATE_TIME_WAIT;
 		inet_twsk_for_each(tw, node,
@@ -2074,13 +2073,11 @@ static void *established_get_first(struc
 			if (tw->tw_family != st->family) {
 				continue;
 			}
-			rc = tw;
-			goto out;
+			return tw;
 		}
 		read_unlock_bh(lock);
 		st->state = TCP_SEQ_STATE_ESTABLISHED;
 	}
-out:
 	return rc;
 }
 
@@ -2100,10 +2097,8 @@ get_tw:
 		while (tw && tw->tw_family != st->family) {
 			tw = tw_next(tw);
 		}
-		if (tw) {
-			cur = tw;
-			goto out;
-		}
+		if (tw)
+			return tw;
 		read_unlock_bh(inet_ehash_lockp(&tcp_hashinfo, st->bucket));
 		st->state = TCP_SEQ_STATE_ESTABLISHED;
 
@@ -2121,16 +2116,12 @@ get_tw:
 
 	sk_for_each_from(sk, node) {
 		if (sk->sk_family == st->family)
-			goto found;
+			return sk;
 	}
 
 	st->state = TCP_SEQ_STATE_TIME_WAIT;
 	tw = tw_head(&tcp_hashinfo.ehash[st->bucket].twchain);
 	goto get_tw;
-found:
-	cur = sk;
-out:
-	return cur;
 }
 
 static void *established_get_idx(struct seq_file *seq, loff_t pos)

Re: [PATCH] [2/2] Remove some unnecessary gotos in established_get_first()

[Oliver Neukum]

Am Mittwoch, 30. Januar 2008 09:01:10 schrieb Andi Kleen:
> 
> gcc does not generate different code for return foo vs bar = foo; goto x;
> x: return bar; So convert it all to direct returns for better readability.

Now suppose somebody needs to change locking. He'll have to convert
it back. IMHO a conditional return is worse than "goto clearly_named_label"

	Regards
		Oliver

Re: [PATCH] [2/2] Remove some unnecessary gotos in established_get_first()

[Andi Kleen]

Oliver Neukum <oliver@neukum.org> writes:

> Am Mittwoch, 30. Januar 2008 09:01:10 schrieb Andi Kleen:
>> 
>> gcc does not generate different code for return foo vs bar = foo; goto x;
>> x: return bar; So convert it all to direct returns for better readability.
>
> Now suppose somebody needs to change locking. He'll have to convert
> it back. 

Please take a look at the overall /proc/net/tcp logic. Any locking 
change will be a major change to the code flow of the whole family
of funtions.

-Andi

Re: [PATCH] [2/2] Remove some unnecessary gotos in established_get_first()

[David Miller]

From: Oliver Neukum <oliver@neukum.org>
Date: Wed, 30 Jan 2008 09:25:12 +0100

> Now suppose somebody needs to change locking. He'll have to convert
> it back. IMHO a conditional return is worse than "goto clearly_named_label"

I totally agree.

Re: [PATCH] [1/2] Skip empty hash buckets faster in /proc/net/tcp

[Roland Dreier]

 > On a 2GB Core2 system here I see a time cat /proc/net/tcp > /dev/null
 > constently dropping from 0.44s to 0.4-0.8s system time with this change.

Seems like there must be a typo in either the before or after times
you report here?

Re: [PATCH] [1/2] Skip empty hash buckets faster in /proc/net/tcp

[Andi Kleen]

On Wed, Jan 30, 2008 at 09:03:16AM -0800, Roland Dreier wrote:
>  > On a 2GB Core2 system here I see a time cat /proc/net/tcp > /dev/null
>  > constently dropping from 0.44s to 0.4-0.8s system time with this change.
> 
> Seems like there must be a typo in either the before or after times
> you report here?

Yes thanks, it was 0.44s down to 0.04s/0.08s here. Somehow the zeroes
got lost.

-Andi