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

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

[Alex Pankratov]

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.

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

diff -uprX dontdiff linux-2.6.2/include/linux/list.h 
linux-2.6.2.hlist/include/linux/list.h
--- linux-2.6.2/include/linux/list.h	2004-02-03 19:43:56.000000000 -0800
+++ linux-2.6.2.hlist/include/linux/list.h	2004-02-10 12:35:57.000000000 
-0800
@@ -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) \
diff -uprX dontdiff linux-2.6.2/include/net/sock.h 
linux-2.6.2.hlist/include/net/sock.h
--- linux-2.6.2/include/net/sock.h	2004-02-03 19:44:05.000000000 -0800
+++ linux-2.6.2.hlist/include/net/sock.h	2004-02-10 12:38:24.000000000 -0800
@@ -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)
diff -uprX dontdiff linux-2.6.2/include/net/tcp.h 
linux-2.6.2.hlist/include/net/tcp.h
--- linux-2.6.2/include/net/tcp.h	2004-02-03 19:43:11.000000000 -0800
+++ linux-2.6.2.hlist/include/net/tcp.h	2004-02-10 12:47:32.000000000 -0800
@@ -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)
diff -uprX dontdiff linux-2.6.2/net/ax25/af_ax25.c 
linux-2.6.2.hlist/net/ax25/af_ax25.c
--- linux-2.6.2/net/ax25/af_ax25.c	2004-02-03 19:44:39.000000000 -0800
+++ linux-2.6.2.hlist/net/ax25/af_ax25.c	2004-02-10 12:48:28.000000000 -0800
@@ -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)
diff -uprX dontdiff linux-2.6.2/net/ipv4/tcp_ipv4.c 
linux-2.6.2.hlist/net/ipv4/tcp_ipv4.c
--- linux-2.6.2/net/ipv4/tcp_ipv4.c	2004-02-03 19:43:41.000000000 -0800
+++ linux-2.6.2.hlist/net/ipv4/tcp_ipv4.c	2004-02-10 12:50:27.000000000 
-0800
@@ -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)
diff -uprX dontdiff linux-2.6.2/net/ipv6/tcp_ipv6.c 
linux-2.6.2.hlist/net/ipv6/tcp_ipv6.c
--- linux-2.6.2/net/ipv6/tcp_ipv6.c	2004-02-03 19:43:56.000000000 -0800
+++ linux-2.6.2.hlist/net/ipv6/tcp_ipv6.c	2004-02-09 21:27:23.000000000 
-0800
@@ -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;
diff -uprX dontdiff linux-2.6.2/net/netrom/nr_route.c 
linux-2.6.2.hlist/net/netrom/nr_route.c
--- linux-2.6.2/net/netrom/nr_route.c	2004-02-03 19:45:02.000000000 -0800
+++ linux-2.6.2.hlist/net/netrom/nr_route.c	2004-02-10 
12:53:10.000000000 -0800
@@ -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)

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

[Andi Kleen]

On Tue, 10 Feb 2004 22:28:11 -0800
Alex Pankratov <ap@swapped.cc> 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

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

[Alex Pankratov]

Andi Kleen wrote:

> On Tue, 10 Feb 2004 22:28:11 -0800
> Alex Pankratov <ap@swapped.cc> 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.

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

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

[Arnaldo Carvalho de Melo]

Em Tue, Feb 10, 2004 at 10:57:43PM -0800, Alex Pankratov escreveu:
> 
> 
> Andi Kleen wrote:
> 
> >On Tue, 10 Feb 2004 22:28:11 -0800
> >Alex Pankratov <ap@swapped.cc> 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.
> 
> 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

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

[Andi Kleen]

On Tue, 10 Feb 2004 22:57:43 -0800
Alex Pankratov <ap@swapped.cc> 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

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

[Alex Pankratov]

Andi Kleen wrote:

> On Tue, 10 Feb 2004 22:57:43 -0800
> Alex Pankratov <ap@swapped.cc> 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.

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

[Alex Pankratov]

Andi Kleen wrote:

> On Tue, 10 Feb 2004 22:57:43 -0800
> Alex Pankratov <ap@swapped.cc> 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. 
> 

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

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

[Andi Kleen]

On Wed, 11 Feb 2004 20:52:39 -0800
Alex Pankratov <ap@swapped.cc> 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