[2.6] [1/2] hlist: replace explicit checks of hlist fields w/ func calls

PATCH In review Alex Pankratov 3 participants 8 messages Feb 11, 2004 – Feb 12, 2004

Subsystems (3)

Networking TCP Sockets

lore

Share & tools

lore

Alex Pankratov

author

2004-02-11 06:28 UTC #0 lore raw

PATCH 1/1 [2.6] [1/2] hlist: replace explicit checks of hlist fields w/ func calls

Arnaldo, Andi,

I have a set of two patches that removes if() branching from hlist_xxx() functions.

First patch replaces explicit manipulation and checks of hlist_head and hlist_node fields with hlist_xxx() function calls. The goal here is to hide the details of how the hlist is terminated from the external code.

Second patch removes if's from hlist_xxx() functions. The idea is to terminate the list not with 0, but with a pointer at a special 'null' item. Luckily a single 'null' can be shared between all hlists _without_ any synchronization, because its 'next' and 'pprev' fields are never read. In fact, 'next' is not accessed at all, and 'pprev' is used only for writing.

--------------

include/linux/list.h +12 -0

diff -uprX dontdiff linux-2.6.2/include/linux/list.h linux-2.6.2.hlist/include/linux/list.h
@@ -439,6 +439,16 @@ struct hlist_node {
 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
 #define INIT_HLIST_NODE(ptr) ((ptr)->next = NULL, (ptr)->pprev = NULL)
 
+static __inline__ void hlist_node_init(struct hlist_node *h)
+{
+	h->pprev = NULL;
+}
+
+static __inline__ int hlist_last(const struct hlist_node *h)
+{
+	return !h->next;
+}
+
 static __inline__ int hlist_unhashed(const struct hlist_node *h)
 {
 	return !h->pprev;

@@ -531,6 +541,8 @@ static __inline__ void hlist_add_after(s
 }
 
 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
+#define hlist_entry_safe(ptr, type, member) \
+	((ptr) == 0 ? NULL : container_of(ptr,type,member))
 
 /* Cannot easily do prefetch unfortunately */
 #define hlist_for_each(pos, head) \

include/net/sock.h +4 -5

diff -uprX dontdiff linux-2.6.2/include/net/sock.h linux-2.6.2.hlist/include/net/sock.h
@@ -266,13 +266,12 @@ static inline struct sock *__sk_head(str
 
 static inline struct sock *sk_head(struct hlist_head *head)
 {
-	return hlist_empty(head) ? NULL : __sk_head(head);
+	return hlist_entry_safe(head->first, struct sock, sk_node);
 }
 
 static inline struct sock *sk_next(struct sock *sk)
 {
-	return sk->sk_node.next ?
-		hlist_entry(sk->sk_node.next, struct sock, sk_node) : NULL;
+	return hlist_entry_safe(sk->sk_node.next, struct sock, sk_node);
 }
 
 static inline int sk_unhashed(struct sock *sk)

@@ -282,12 +281,12 @@ static inline int sk_unhashed(struct soc
 
 static inline int sk_hashed(struct sock *sk)
 {
-	return sk->sk_node.pprev != NULL;
+	return ! hlist_unhashed(&sk->sk_node);
 }
 
 static __inline__ void sk_node_init(struct hlist_node *node)
 {
-	node->pprev = NULL;
+	hlist_node_init(node);
 }
 
 static __inline__ void __sk_del_node(struct sock *sk)

include/net/tcp.h +0 -0

diff -uprX dontdiff linux-2.6.2/include/net/tcp.h linux-2.6.2.hlist/include/net/tcp.h
@@ -102,7 +102,8 @@ static inline struct tcp_bind_bucket *__
 
 static inline struct tcp_bind_bucket *tb_head(struct

tcp_bind_hashbucket *head)
{
- return hlist_empty(&head->chain) ? NULL : __tb_head(head);
+ return hlist_entry_safe(head->chain.first,
+ struct tcp_bind_bucket, node);
}

extern struct tcp_hashinfo {
@@ -237,12 +238,12 @@ static __inline__ void tw_add_bind_node(

static inline int tw_dead_hashed(struct tcp_tw_bucket *tw) {
- return tw->tw_death_node.pprev != NULL;
+ return ! hlist_unhashed(&tw->tw_death_node);
}

static __inline__ void tw_dead_node_init(struct tcp_tw_bucket *tw) {
- tw->tw_death_node.pprev = NULL;
+ hlist_node_init(&tw->tw_death_node);
}

static __inline__ void __tw_del_dead_node(struct tcp_tw_bucket *tw)

net/ax25/af_ax25.c +2 -2

diff -uprX dontdiff linux-2.6.2/net/ax25/af_ax25.c linux-2.6.2.hlist/net/ax25/af_ax25.c
@@ -1860,8 +1860,8 @@ static void *ax25_info_next(struct seq_f
 {
 	++*pos;
 
-	return hlist_entry( ((struct ax25_cb *)v)->ax25_node.next,
-			    struct ax25_cb, ax25_node);
+	return hlist_entry_safe(((struct ax25_cb *)v)->ax25_node.next,
+				struct ax25_cb, ax25_node);
 }
 	
 static void ax25_info_stop(struct seq_file *seq, void *v)

net/ipv4/tcp_ipv4.c +4 -6

diff -uprX dontdiff linux-2.6.2/net/ipv4/tcp_ipv4.c linux-2.6.2.hlist/net/ipv4/tcp_ipv4.c
@@ -459,7 +459,7 @@ inline struct sock *tcp_v4_lookup_listen
 	if (!hlist_empty(head)) {
 		struct inet_opt *inet = inet_sk((sk = __sk_head(head)));
 
-		if (inet->num == hnum && !sk->sk_node.next &&
+		if (inet->num == hnum && hlist_last(&sk->sk_node) &&
 		    (!inet->rcv_saddr || inet->rcv_saddr == daddr) &&
 		    (sk->sk_family == PF_INET || !ipv6_only_sock(sk)) &&
 		    !sk->sk_bound_dev_if)

@@ -736,7 +736,7 @@ ok:
  	head  = &tcp_bhash[tcp_bhashfn(snum)];
  	tb  = tcp_sk(sk)->bind_hash;
 	spin_lock_bh(&head->lock);
-	if (sk_head(&tb->owners) == sk && !sk->sk_bind_node.next) {
+	if (sk_head(&tb->owners) == sk && hlist_last(&sk->sk_bind_node)) {
 		__tcp_v4_hash(sk, 0);
 		spin_unlock_bh(&head->lock);
 		return 0;

@@ -2124,14 +2124,12 @@ static int tcp_v4_destroy_sock(struct so
 
 static inline struct tcp_tw_bucket *tw_head(struct hlist_head *head)
 {
-	return hlist_empty(head) ? NULL :
-		list_entry(head->first, struct tcp_tw_bucket, tw_node);
+	return hlist_entry_safe(head->first, struct tcp_tw_bucket, tw_node);
 }
 
 static inline struct tcp_tw_bucket *tw_next(struct tcp_tw_bucket *tw)
 {
-	return tw->tw_node.next ?
-		hlist_entry(tw->tw_node.next, typeof(*tw), tw_node) : NULL;
+	return hlist_entry_safe(tw->tw_node.next, typeof(*tw), tw_node);
 }
 
 static void *listening_get_first(struct seq_file *seq)

net/ipv6/tcp_ipv6.c +1 -1

diff -uprX dontdiff linux-2.6.2/net/ipv6/tcp_ipv6.c linux-2.6.2.hlist/net/ipv6/tcp_ipv6.c
@@ -524,7 +524,7 @@ static int tcp_v6_hash_connect(struct so
 
 	spin_lock_bh(&head->lock);
 
-	if (sk_head(&tb->owners) == sk && !sk->sk_bind_node.next) {
+	if (sk_head(&tb->owners) == sk && hlist_last(&sk->sk_bind_node)) {
 		__tcp_v6_hash(sk);
 		spin_unlock_bh(&head->lock);
 		return 0;

net/netrom/nr_route.c +2 -2

diff -uprX dontdiff linux-2.6.2/net/netrom/nr_route.c linux-2.6.2.hlist/net/netrom/nr_route.c
@@ -870,7 +870,7 @@ static void *nr_node_next(struct seq_fil
 		? nr_node_list.first
 		: ((struct nr_node *)v)->node_node.next;
 
-	return hlist_entry(node, struct nr_node, node_node);
+	return hlist_entry_safe(node, struct nr_node, node_node);
 }
 
 static void nr_node_stop(struct seq_file *seq, void *v)

@@ -953,7 +953,7 @@ static void *nr_neigh_next(struct seq_fi
 		? nr_neigh_list.first
 		: ((struct nr_neigh *)v)->neigh_node.next;
 
-	return hlist_entry(node, struct nr_neigh, neigh_node);
+	return hlist_entry_safe(node, struct nr_neigh, neigh_node);
 }
 
 static void nr_neigh_stop(struct seq_file *seq, void *v)

Andi Kleen

2004-02-11 06:41 UTC #1 lore raw

Quoted 7 lines · On Tue, 10 Feb 2004 22:28:11 -0800 Alex Pankratov <[email protected]> wrote:

Second patch removes if's from hlist_xxx() functions. The idea is to terminate the list not with 0, but with a pointer at a special 'null' item. Luckily a single 'null' can be shared between all hlists _without_ any synchronization, because its 'next' and 'pprev' fields are never read. In fact, 'next' is not accessed at all, and 'pprev' is used only for writing.

I disagree with this change. The problem is that in a loop you need a register now to store the terminating element and compare to it instead of just testing for zero. This can generate much worse code on register starved i386 than having the conditional.

If you really want to avoid the conditional you could restructure it so that i386 gcc can use a CMOV* (by using a pointer that either points to a dummy or the target). But that would make the code somewhat uglier and may not be worth it.

-Andi

Alex Pankratov

author

2004-02-11 06:58 UTC #2 lore raw

Quoted 11 lines · Andi Kleen

Quoted 6 lines · On Tue, 10 Feb 2004 22:28:11 -0800 Alex Pankratov <[email protected]> wrote:
Second patch removes if's from hlist_xxx() functions. The idea is to terminate the list not with 0, but with a pointer at a special 'null' item. Luckily a single 'null' can be shared between all hlists _without_ any synchronization, because its 'next' and 'pprev' fields are never read. In fact, 'next' is not accessed at all, and 'pprev' is used only for writing.

Quoted 3 lines

I disagree with this change. The problem is that in a loop
you need a register now to store the terminating element
and compare to it instead of just testing for zero. This can generate much worse code on register starved i386 than having the conditional.

Ugh, yeah, I thought about this. However my understand was that since hlist_null is statically allocated variable, its address will be a known constant at a link time (whether it's a static link or dynamic/run-time link - btw, excuse my lack of proper terminology here). So comparing something to &null would be equivalent to comparing to the constant and not require an extra register.

Alex

Andi Kleen

2004-02-11 07:50 UTC #3 lore raw

Quoted 7 lines · On Tue, 10 Feb 2004 22:57:43 -0800 Alex Pankratov <[email protected]> wrote:

Ugh, yeah, I thought about this. However my understand was that since hlist_null is statically allocated variable, its address will be a known constant at a link time (whether it's a static link or dynamic/run-time link - btw, excuse my lack of proper terminology here). So comparing something to &null would be equivalent to comparing to the constant and not require an extra register.

Hmm, you're right. Apparently I was still thinking about the bad code generated by the standard list_heads. I guess it would be ok then.

Still your first patch was rather intrusive regarding interface changes, so it may be a good idea to wait for 2.7 with this.

-Andi

Alex Pankratov

author

2004-02-11 16:37 UTC #4 lore raw

Quoted 6 lines · Andi Kleen

On Tue, 10 Feb 2004 22:57:43 -0800
Alex Pankratov <[email protected]> wrote:
Still your first patch was rather intrusive regarding interface changes, so it may be a good idea to wait for 2.7 with this.

Fully agreed. I did a grep on an entire tree, which produced a list of sources dependent on hlist. Then I temporarily renamed next, first and pprev fields and configured and built an image. This brought up all references to hlists within dependent code, I fixed what's needed and that produced patch #1. There's still a chance something's left unnoticed.

Alex Pankratov

author

2004-02-12 04:53 UTC #5 lore raw

In reply to Andi Kleen

Quoted 13 lines · Andi Kleen

Quoted 7 lines · On Tue, 10 Feb 2004 22:57:43 -0800 Alex Pankratov <[email protected]> wrote:
Ugh, yeah, I thought about this. However my understand was that since hlist_null is statically allocated variable, its address will be a known constant at a link time (whether it's a static link or dynamic/run-time link - btw, excuse my lack of proper terminology here). So comparing something to &null would be equivalent to comparing to the constant and not require an extra register.

Quoted 3 lines

Hmm, you're right. Apparently I was still thinking about the bad code generated by the standard list_heads.

A quick note about standard lists then - circular double-linked lists are normally described in textbooks as a clever trick allowing to avoid if's in insert() and delete(). Given what you have noted about CMP speed above, I wonder if simple 0-terminated lists would be something to consider for lower-end i386.

Alex

Andi Kleen

2004-02-12 07:10 UTC #6 lore raw

Quoted 5 lines · On Wed, 11 Feb 2004 20:52:39 -0800 Alex Pankratov <[email protected]> wrote:

A quick note about standard lists then - circular double-linked lists are normally described in textbooks as a clever trick allowing to avoid if's in insert() and delete(). Given what you have noted about CMP speed above, I wonder if simple 0-terminated lists would be something to consider for lower-end i386.

That is what hlists are.
Some of the existing users of list_heads could be converted to hlists yes. Basically all that don't need to access the end of the list in constant time.

-Andi

Arnaldo Carvalho de Melo

2004-02-11 11:54 UTC #7 lore raw

In reply to Alex Pankratov

Em Tue, Feb 10, 2004 at 10:57:43PM -0800, Alex Pankratov escreveu:

Quoted 20 lines

Quoted 11 lines · Andi Kleen
Quoted 6 lines · On Tue, 10 Feb 2004 22:28:11 -0800 Alex Pankratov <[email protected]> wrote:
Second patch removes if's from hlist_xxx() functions. The idea is to terminate the list not with 0, but with a pointer at a special 'null' item. Luckily a single 'null' can be shared between all hlists _without_ any synchronization, because its 'next' and 'pprev' fields are never read. In fact, 'next' is not accessed at all, and 'pprev' is used only for writing.
Quoted 4 lines
I disagree with this change. The problem is that in a loop you need a register now to store the terminating element and compare to it instead of just testing for zero. This can generate much worse code on register starved i386 than having the conditional.

Quoted 7 lines

Ugh, yeah, I thought about this. However my understand was that since hlist_null is statically allocated variable, its address will be a known constant at a link time (whether it's a static link or dynamic/run-time link - btw, excuse my lack of proper terminology here). So comparing something to &null would be equivalent to comparing to the constant and not require an extra register.

That is why I was going to generate the code to see the instructions used with your patch when I was captured by my lovely wife... 8)

- Arnaldo