[PATCH 0/4] fib_trie related patches for 2.6.25

[PATCH 0/4] fib_trie related patches for 2.6.25

[Stephen Hemminger]

More trie cleanups with some RCU related changes as well.
Patches are against net-2.6 tree (sent already to netdev).
-- 
Stephen Hemminger <shemminger@vyatta.com>

[PATCH 1/4] rcu_assign_pointer: null check fix

[Stephen Hemminger]

[-- Attachment #1: rcu-assign-warn.patch --]
[-- Type: text/plain, Size: 637 bytes --]

Goofed on last change, should avoid barrier only on rcu_assign_pointer(p, NULL)

Signed-off-by: Stephen Hemminger <shemminger@vyatta.com>
---
 include/linux/rcupdate.h |   13 +++++++------
 1 files changed, 7 insertions(+), 6 deletions(-)

--- a/include/linux/rcupdate.h	2008-02-12 14:46:49.000000000 -0800
+++ b/include/linux/rcupdate.h	2008-02-12 14:56:17.000000000 -0800
@@ -178,7 +178,7 @@ struct rcu_head {
 
 #define rcu_assign_pointer(p, v)			\
 	({						\
-		if (!(__builtin_constant_p(v) && v))	\
+		if (!__builtin_constant_p(v) || v)	\
 			smp_wmb();			\
 		(p) = (v);				\
 	})

-- 
Stephen Hemminger <shemminger@vyatta.com>

[PATCH 2/4] fib_trie: improve output format for /proc/net/fib_trie

[Stephen Hemminger]

[-- Attachment #1: fib-trie-format.patch --]
[-- Type: text/plain, Size: 5136 bytes --]

Make output format prettier (more tree like).

   <local>:
   --- 0.0.0.0/0
     |--- 10.111.111.0/24
     |  +-- 10.111.111.0/32 link broadcast
     |  |--- 10.111.111.254/31
     |  |  +-- 10.111.111.254/32 host local
     |  |  +-- 10.111.111.255/32 link broadcast
     |--- 127.0.0.0/8
     |  |--- 127.0.0.0/31
     |  |  +-- 127.0.0.0/32 link broadcast
     |  |  +-- 127.0.0.0/8 host local
     |  |  +-- 127.0.0.1/32 host local
     |  +-- 127.255.255.255/32 link broadcast
     |--- 192.168.1.0/24
     |  |--- 192.168.1.0/28
     |  |  +-- 192.168.1.0/32 link broadcast
     |  |  +-- 192.168.1.9/32 host local
     |  +-- 192.168.1.255/32 link broadcast
   <main>:
   --- 0.0.0.0/0
     |--- 0.0.0.0/4
     |  +-- 0.0.0.0/0 universe unicast
     |  +-- 10.111.111.0/24 link unicast
     +-- 169.254.0.0/16 link unicast
     +-- 192.168.1.0/24 link unicast
   
Signed-off-by: Stephen Hemminger <shemminger@vyatta.com>
---
 net/ipv4/fib_trie.c |  106 ++++++++++++++++++++++++++------------------------
 1 files changed, 55 insertions(+), 51 deletions(-)

diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index 1ff446d..72338cd 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -2340,46 +2340,57 @@ static void fib_trie_seq_stop(struct seq_file *seq, void *v)
 	rcu_read_unlock();
 }
 
+/* print left side of tree */
 static void seq_indent(struct seq_file *seq, int n)
 {
-	while (n-- > 0) seq_puts(seq, "   ");
-}
-
-static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
-{
-	switch (s) {
-	case RT_SCOPE_UNIVERSE: return "universe";
-	case RT_SCOPE_SITE:	return "site";
-	case RT_SCOPE_LINK:	return "link";
-	case RT_SCOPE_HOST:	return "host";
-	case RT_SCOPE_NOWHERE:	return "nowhere";
-	default:
-		snprintf(buf, len, "scope=%d", s);
-		return buf;
-	}
+	while (n-- > 0)
+		seq_puts(seq, "  |");
 }
 
 static const char *rtn_type_names[__RTN_MAX] = {
-	[RTN_UNSPEC] = "UNSPEC",
-	[RTN_UNICAST] = "UNICAST",
-	[RTN_LOCAL] = "LOCAL",
-	[RTN_BROADCAST] = "BROADCAST",
-	[RTN_ANYCAST] = "ANYCAST",
-	[RTN_MULTICAST] = "MULTICAST",
-	[RTN_BLACKHOLE] = "BLACKHOLE",
-	[RTN_UNREACHABLE] = "UNREACHABLE",
-	[RTN_PROHIBIT] = "PROHIBIT",
-	[RTN_THROW] = "THROW",
-	[RTN_NAT] = "NAT",
-	[RTN_XRESOLVE] = "XRESOLVE",
+	[RTN_UNSPEC]	= "unspec",
+	[RTN_UNICAST]	= "unicast",
+	[RTN_LOCAL]	= "local",
+	[RTN_BROADCAST] = "broadcast",
+	[RTN_ANYCAST]	= "anycast",
+	[RTN_MULTICAST] = "multicast",
+	[RTN_BLACKHOLE] = "blackhole",
+	[RTN_UNREACHABLE] = "unreachable",
+	[RTN_PROHIBIT] 	= "prohibit",
+	[RTN_THROW]	= "throw",
+	[RTN_NAT]	= "nat",
+	[RTN_XRESOLVE]	= "xresolve",
 };
 
-static inline const char *rtn_type(char *buf, size_t len, unsigned t)
-{
-	if (t < __RTN_MAX && rtn_type_names[t])
-		return rtn_type_names[t];
-	snprintf(buf, len, "type %u", t);
-	return buf;
+static void fib_trie_show_alias(struct seq_file *seq, const struct fib_alias *fa)
+{
+	switch (fa->fa_scope) {
+	case RT_SCOPE_UNIVERSE:
+		seq_puts(seq, "universe");
+		break;
+	case RT_SCOPE_SITE:
+		seq_puts(seq,  "site");
+		break;
+	case RT_SCOPE_LINK:
+		seq_puts(seq,  "link");
+		break;
+	case RT_SCOPE_HOST:
+		seq_puts(seq,  "host");
+		break;
+	case RT_SCOPE_NOWHERE:
+		seq_puts(seq,  "nowhere");
+		break;
+	default:
+		seq_printf(seq, "scope:%d", fa->fa_scope);
+	}
+
+	if (fa->fa_type < __RTN_MAX && rtn_type_names[fa->fa_type])
+		seq_printf(seq, " %s", rtn_type_names[fa->fa_type]);
+	else
+		seq_printf(seq, " type:%u", fa->fa_type);
+	
+	if (fa->fa_tos)
+		seq_printf(seq, " tos:%#x", fa->fa_tos);
 }
 
 /* Pretty print the trie */
@@ -2402,10 +2413,8 @@ static int fib_trie_seq_show(struct seq_file *seq, void *v)
 		struct tnode *tn = (struct tnode *) n;
 		__be32 prf = htonl(mask_pfx(tn->key, tn->pos));
 
-		seq_indent(seq, iter->depth-1);
-		seq_printf(seq, "  +-- %d.%d.%d.%d/%d %d %d %d\n",
-			   NIPQUAD(prf), tn->pos, tn->bits, tn->full_children,
-			   tn->empty_children);
+		seq_indent(seq, iter->depth - 1);
+		seq_printf(seq, "--- %d.%d.%d.%d/%d\n", NIPQUAD(prf), tn->pos);
 
 	} else {
 		struct leaf *l = (struct leaf *) n;
@@ -2413,24 +2422,19 @@ static int fib_trie_seq_show(struct seq_file *seq, void *v)
 		struct hlist_node *node;
 		__be32 val = htonl(l->key);
 
-		seq_indent(seq, iter->depth);
-		seq_printf(seq, "  |-- %d.%d.%d.%d\n", NIPQUAD(val));
-
 		hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
 			struct fib_alias *fa;
+			
+			seq_indent(seq, iter->depth - 1);	
+			seq_printf(seq, "  +-- %d.%d.%d.%d/%d ",
+				   NIPQUAD(val), li->plen);
 
 			list_for_each_entry_rcu(fa, &li->falh, fa_list) {
-				char buf1[32], buf2[32];
-
-				seq_indent(seq, iter->depth+1);
-				seq_printf(seq, "  /%d %s %s", li->plen,
-					   rtn_scope(buf1, sizeof(buf1),
-						     fa->fa_scope),
-					   rtn_type(buf2, sizeof(buf2),
-						    fa->fa_type));
-				if (fa->fa_tos)
-					seq_printf(seq, " tos=%d", fa->fa_tos);
-				seq_putc(seq, '\n');
+				fib_trie_show_alias(seq, fa);
+				if (list_is_last(&fa->fa_list, &li->falh))
+					seq_putc(seq, '\n');
+				else
+					seq_puts(seq, ", ");
 			}
 		}
 	}
-- 
1.5.3.8

-- 
Stephen Hemminger <shemminger@vyatta.com>

Re: [PATCH 2/4] fib_trie: improve output format for /proc/net/fib_trie

[Andrew Morton]

On Tue, 12 Feb 2008 16:50:44 -0800 Stephen Hemminger <shemminger@vyatta.com> wrote:

> Make output format prettier (more tree like).
> 
>    <local>:
>    --- 0.0.0.0/0
>      |--- 10.111.111.0/24
>      |  +-- 10.111.111.0/32 link broadcast
>      |  |--- 10.111.111.254/31
>      |  |  +-- 10.111.111.254/32 host local
>      |  |  +-- 10.111.111.255/32 link broadcast
>      |--- 127.0.0.0/8
>      |  |--- 127.0.0.0/31
>      |  |  +-- 127.0.0.0/32 link broadcast
>      |  |  +-- 127.0.0.0/8 host local
>      |  |  +-- 127.0.0.1/32 host local
>      |  +-- 127.255.255.255/32 link broadcast
>      |--- 192.168.1.0/24
>      |  |--- 192.168.1.0/28
>      |  |  +-- 192.168.1.0/32 link broadcast
>      |  |  +-- 192.168.1.9/32 host local
>      |  +-- 192.168.1.255/32 link broadcast
>    <main>:
>    --- 0.0.0.0/0
>      |--- 0.0.0.0/4
>      |  +-- 0.0.0.0/0 universe unicast
>      |  +-- 10.111.111.0/24 link unicast
>      +-- 169.254.0.0/16 link unicast
>      +-- 192.168.1.0/24 link unicast

isn't that a non-back-compatible kernel ABI change?  It might
break pre-existing parsers?

aside: how lame are we to put pretty-printers in the kernel?
English-only ones, at that?  Root cause: kernel developers still
don't have a sufficiently easy way of shipping userspace tools.

Re: [PATCH 2/4] fib_trie: improve output format for /proc/net/fib_trie

[Stephen Hemminger]

Andrew Morton wrote:
> On Tue, 12 Feb 2008 16:50:44 -0800 Stephen Hemminger <shemminger@vyatta.com> wrote:
>
>   
>> Make output format prettier (more tree like).
>>
>>    <local>:
>>    --- 0.0.0.0/0
>>      |--- 10.111.111.0/24
>>      |  +-- 10.111.111.0/32 link broadcast
>>      |  |--- 10.111.111.254/31
>>      |  |  +-- 10.111.111.254/32 host local
>>      |  |  +-- 10.111.111.255/32 link broadcast
>>      |--- 127.0.0.0/8
>>      |  |--- 127.0.0.0/31
>>      |  |  +-- 127.0.0.0/32 link broadcast
>>      |  |  +-- 127.0.0.0/8 host local
>>      |  |  +-- 127.0.0.1/32 host local
>>      |  +-- 127.255.255.255/32 link broadcast
>>      |--- 192.168.1.0/24
>>      |  |--- 192.168.1.0/28
>>      |  |  +-- 192.168.1.0/32 link broadcast
>>      |  |  +-- 192.168.1.9/32 host local
>>      |  +-- 192.168.1.255/32 link broadcast
>>    <main>:
>>    --- 0.0.0.0/0
>>      |--- 0.0.0.0/4
>>      |  +-- 0.0.0.0/0 universe unicast
>>      |  +-- 10.111.111.0/24 link unicast
>>      +-- 169.254.0.0/16 link unicast
>>      +-- 192.168.1.0/24 link unicast
>>     
>
> isn't that a non-back-compatible kernel ABI change?  It might
> break pre-existing parsers?
>
>   
Fib trie was always experimental and the output format was intended to 
be tree like
but was broken. There are no known parsers of fib trie, and I think 
Vyatta will probably
be the first distro to ship with it enabled.
> aside: how lame are we to put pretty-printers in the kernel?
> English-only ones, at that?  Root cause: kernel developers still
> don't have a sufficiently easy way of shipping userspace tools.
Agreed, the structure of the trie doesn't come out via netlink (only the 
addresses).

[PATCH 3/4] fib_trie: print statistics for multiple tables

[Stephen Hemminger]

[-- Attachment #1: fib-trie-tables.patch --]
[-- Type: text/plain, Size: 8538 bytes --]

Make /proc/net/fib_trie and /proc/net/fib_triestat handle
multiple (alternate) route tables. Need hliist_for_each_entry_continue_rcu
as well. 

Notes:
 * this usage of seq_file doesn't need/want SEQ_START_TOKEN
 * add hlist_for_each_entry_continue_rcu since it needs it

Signed-off-by: Stephen Hemminger <shemminger@vyatta.com>
---
 include/linux/list.h |   13 ++++
 net/ipv4/fib_trie.c  |  186 ++++++++++++++++++++++++++++----------------------
 2 files changed, 117 insertions(+), 82 deletions(-)

--- a/include/linux/list.h	2008-02-12 14:46:49.000000000 -0800
+++ b/include/linux/list.h	2008-02-12 15:09:17.000000000 -0800
@@ -991,6 +991,19 @@ static inline void hlist_add_after_rcu(s
 		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 	     pos = pos->next)
 
+
+/**
+ * hlist_for_each_entry_continue_rcu - iterate over rcu hlist after current point
+ * @tpos:	the type * to use as a loop cursor.
+ * @pos:	the &struct hlist_node to use as a loop cursor.
+ * @member:	the name of the hlist_node within the struct.
+ */
+#define hlist_for_each_entry_continue_rcu(tpos, pos, member)		\
+	for (pos = (pos)->next;						\
+	     rcu_dereference(pos) && ({ prefetch(pos->next); 1;}) &&	\
+		     ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
+	     pos = pos->next)
+
 #else
 #warning "don't include kernel headers in userspace"
 #endif /* __KERNEL__ */
--- a/net/ipv4/fib_trie.c	2008-02-12 14:56:58.000000000 -0800
+++ b/net/ipv4/fib_trie.c	2008-02-12 15:09:46.000000000 -0800
@@ -2026,14 +2026,13 @@ struct fib_table *fib_hash_table(u32 id)
 /* Depth first Trie walk iterator */
 struct fib_trie_iter {
 	struct seq_net_private p;
-	struct trie *trie_local, *trie_main;
+	struct fib_table *tb;
 	struct tnode *tnode;
-	struct trie *trie;
 	unsigned index;
 	unsigned depth;
 };
 
-static struct node *fib_trie_get_next(struct fib_trie_iter *iter)
+static struct node *trie_get_next(struct fib_trie_iter *iter)
 {
 	struct tnode *tn = iter->tnode;
 	unsigned cindex = iter->index;
@@ -2078,37 +2077,33 @@ rescan:
 	return NULL;
 }
 
-static struct node *fib_trie_get_first(struct fib_trie_iter *iter,
-				       struct trie *t)
+static struct node *trie_get_first(struct fib_trie_iter *iter, struct fib_table *tb)
 {
-	struct node *n ;
+	struct trie *t = (struct trie *) tb->tb_data;
+	struct node *n;
 
+	iter->tb = tb;
 	if (!t)
 		return NULL;
 
 	n = rcu_dereference(t->trie);
-
-	if (!iter)
+	if (!n)
 		return NULL;
 
-	if (n) {
-		if (IS_TNODE(n)) {
-			iter->tnode = (struct tnode *) n;
-			iter->trie = t;
-			iter->index = 0;
-			iter->depth = 1;
-		} else {
-			iter->tnode = NULL;
-			iter->trie  = t;
-			iter->index = 0;
-			iter->depth = 0;
-		}
-		return n;
+	if (IS_TNODE(n)) {
+		iter->tnode = (struct tnode *) n;
+		iter->index = 0;
+		iter->depth = 1;
+	} else {
+		iter->tnode = NULL;
+		iter->index = 0;
+		iter->depth = 0;
 	}
-	return NULL;
+
+	return n;
 }
 
-static void trie_collect_stats(struct trie *t, struct trie_stat *s)
+static void trie_collect_stats(struct fib_table *tb, struct trie_stat *s)
 {
 	struct node *n;
 	struct fib_trie_iter iter;
@@ -2116,8 +2111,7 @@ static void trie_collect_stats(struct tr
 	memset(s, 0, sizeof(*s));
 
 	rcu_read_lock();
-	for (n = fib_trie_get_first(&iter, t); n;
-	     n = fib_trie_get_next(&iter)) {
+	for (n = trie_get_first(&iter, tb); n; n = trie_get_next(&iter)) {
 		if (IS_LEAF(n)) {
 			struct leaf *l = (struct leaf *)n;
 			struct leaf_info *li;
@@ -2206,36 +2200,53 @@ static void trie_show_usage(struct seq_f
 }
 #endif /*  CONFIG_IP_FIB_TRIE_STATS */
 
-static void fib_trie_show(struct seq_file *seq, const char *name,
-			  struct trie *trie)
+static void fib_table_print(struct seq_file *seq, struct fib_table *tb)
+{
+	if (tb->tb_id == RT_TABLE_LOCAL)
+		seq_puts(seq, "Local:\n");
+	else if (tb->tb_id == RT_TABLE_MAIN)
+		seq_puts(seq, "Main:\n");
+	else
+		seq_printf(seq, "Id %d:\n", tb->tb_id);
+}
+
+static void fib_trie_show(struct seq_file *seq, struct fib_table *tb)
 {
+	struct trie *t = (struct trie *) tb->tb_data;
 	struct trie_stat stat;
 
-	trie_collect_stats(trie, &stat);
-	seq_printf(seq, "%s:\n", name);
+	if (!t)
+		return;
+
+	fib_table_print(seq, tb);
+
+	trie_collect_stats(tb, &stat);
 	trie_show_stats(seq, &stat);
 #ifdef CONFIG_IP_FIB_TRIE_STATS
-	trie_show_usage(seq, &trie->stats);
+	trie_show_usage(seq, &t->stats);
 #endif
 }
 
 static int fib_triestat_seq_show(struct seq_file *seq, void *v)
 {
 	struct net *net = (struct net *)seq->private;
-	struct fib_table *tb;
+	unsigned int h;
 
 	seq_printf(seq,
 		   "Basic info: size of leaf:"
 		   " %Zd bytes, size of tnode: %Zd bytes.\n",
 		   sizeof(struct leaf), sizeof(struct tnode));
 
-	tb = fib_get_table(net, RT_TABLE_LOCAL);
-	if (tb)
-		fib_trie_show(seq, "Local", (struct trie *) tb->tb_data);
-
-	tb = fib_get_table(net, RT_TABLE_MAIN);
-	if (tb)
-		fib_trie_show(seq, "Main", (struct trie *) tb->tb_data);
+	for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
+		struct hlist_head *head = &net->ipv4.fib_table_hash[h];
+		struct hlist_node *node;
+		struct fib_table *tb;
+
+		hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
+			fib_trie_show(seq, tb);
+
+		}
+	}
 
 	return 0;
 }
@@ -2271,23 +2282,29 @@ static const struct file_operations fib_
 	.release = fib_triestat_seq_release,
 };
 
-static struct node *fib_trie_get_idx(struct fib_trie_iter *iter,
-				      loff_t pos)
+static struct node *fib_trie_get_idx(struct fib_trie_iter *iter, loff_t pos)
 {
+	struct net *net = iter->p.net;
 	loff_t idx = 0;
-	struct node *n;
+	unsigned int h;
 
-	for (n = fib_trie_get_first(iter, iter->trie_local);
-	     n; ++idx, n = fib_trie_get_next(iter)) {
-		if (pos == idx)
-			return n;
-	}
+	for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
+		struct hlist_head *head = &net->ipv4.fib_table_hash[h];
+		struct hlist_node *node;
+		struct fib_table *tb;
 
-	for (n = fib_trie_get_first(iter, iter->trie_main);
-	     n; ++idx, n = fib_trie_get_next(iter)) {
-		if (pos == idx)
-			return n;
+		hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
+			struct node *n;
+
+			for (n = trie_get_first(iter, tb);
+			     n; n = trie_get_next(iter))
+				if (pos == idx++) {
+					iter->tb = tb;
+					return n;
+				}
+		}
 	}
+
 	return NULL;
 }
 
@@ -2295,43 +2312,49 @@ static void *fib_trie_seq_start(struct s
 	__acquires(RCU)
 {
 	struct fib_trie_iter *iter = seq->private;
-	struct fib_table *tb;
 
-	if (!iter->trie_local) {
-		tb = fib_get_table(iter->p.net, RT_TABLE_LOCAL);
-		if (tb)
-			iter->trie_local = (struct trie *) tb->tb_data;
-	}
-	if (!iter->trie_main) {
-		tb = fib_get_table(iter->p.net, RT_TABLE_MAIN);
-		if (tb)
-			iter->trie_main = (struct trie *) tb->tb_data;
-	}
 	rcu_read_lock();
-	if (*pos == 0)
-		return SEQ_START_TOKEN;
-	return fib_trie_get_idx(iter, *pos - 1);
+	return fib_trie_get_idx(iter, *pos);
 }
 
 static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
 {
 	struct fib_trie_iter *iter = seq->private;
-	void *l = v;
+	struct net *net = iter->p.net;
+	struct fib_table *tb = iter->tb;
+	struct hlist_node *tb_node;
+	unsigned int h;
+	struct node *n;
 
 	++*pos;
-	if (v == SEQ_START_TOKEN)
-		return fib_trie_get_idx(iter, 0);
+	n = trie_get_next(iter);
+	if (n)
+		return n;
 
-	v = fib_trie_get_next(iter);
-	BUG_ON(v == l);
-	if (v)
-		return v;
-
-	/* continue scan in next trie */
-	if (iter->trie == iter->trie_local)
-		return fib_trie_get_first(iter, iter->trie_main);
+	/* walk rest of this hash chain */
+	h = tb->tb_id & (FIB_TABLE_HASHSZ - 1);
+	tb_node = &tb->tb_hlist;
+	hlist_for_each_entry_continue_rcu(tb, tb_node, tb_hlist) {
+		n = trie_get_first(iter, tb);
+		if (n)
+			goto found;
+	}
+
+	/* new hash chain */
+	while (++h < FIB_TABLE_HASHSZ) {
+		struct hlist_head *head = &net->ipv4.fib_table_hash[h];
+		hlist_for_each_entry_rcu(tb, tb_node, head, tb_hlist) {
+			n = trie_get_first(iter, tb);
+			if (n)
+				goto found;
+		}
+	}
 
 	return NULL;
+
+found:
+	iter->tb = tb;
+	return n;
 }
 
 static void fib_trie_seq_stop(struct seq_file *seq, void *v)
@@ -2399,15 +2422,8 @@ static int fib_trie_seq_show(struct seq_
 	const struct fib_trie_iter *iter = seq->private;
 	struct node *n = v;
 
-	if (v == SEQ_START_TOKEN)
-		return 0;
-
-	if (!node_parent_rcu(n)) {
-		if (iter->trie == iter->trie_local)
-			seq_puts(seq, "<local>:\n");
-		else
-			seq_puts(seq, "<main>:\n");
-	}
+	if (!node_parent_rcu(n))
+		fib_table_print(seq, iter->tb);
 
 	if (IS_TNODE(n)) {
 		struct tnode *tn = (struct tnode *) n;

-- 
Stephen Hemminger <shemminger@vyatta.com>

Re: [PATCH 3/4] fib_trie: print statistics for multiple tables

[Andrew Morton]

On Tue, 12 Feb 2008 16:50:45 -0800 Stephen Hemminger <shemminger@vyatta.com> wrote:

> +/**
> + * hlist_for_each_entry_continue_rcu - iterate over rcu hlist after current point
> + * @tpos:	the type * to use as a loop cursor.
> + * @pos:	the &struct hlist_node to use as a loop cursor.
> + * @member:	the name of the hlist_node within the struct.
> + */
> +#define hlist_for_each_entry_continue_rcu(tpos, pos, member)		\
> +	for (pos = (pos)->next;						\
> +	     rcu_dereference(pos) && ({ prefetch(pos->next); 1;}) &&	\
> +		     ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
> +	     pos = pos->next)

Is the compiler allowed to look at a term such as

	({ prefetch(pos->next); 1;})

and, when it is used as a truth value, say "hey, that's always true" and
then elide the call to prefetch()?  We've no way of telling because this
remains gcc-specific territory, afaik.

(cc Paul for rcu stuff)

Re: [PATCH 3/4] fib_trie: print statistics for multiple tables

[Paul E. McKenney]

On Tue, Feb 12, 2008 at 06:35:21PM -0800, Andrew Morton wrote:
> On Tue, 12 Feb 2008 16:50:45 -0800 Stephen Hemminger <shemminger@vyatta.com> wrote:
> 
> > +/**
> > + * hlist_for_each_entry_continue_rcu - iterate over rcu hlist after current point
> > + * @tpos:	the type * to use as a loop cursor.
> > + * @pos:	the &struct hlist_node to use as a loop cursor.
> > + * @member:	the name of the hlist_node within the struct.
> > + */
> > +#define hlist_for_each_entry_continue_rcu(tpos, pos, member)		\
> > +	for (pos = (pos)->next;						\
> > +	     rcu_dereference(pos) && ({ prefetch(pos->next); 1;}) &&	\
> > +		     ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
> > +	     pos = pos->next)
> 
> Is the compiler allowed to look at a term such as
> 
> 	({ prefetch(pos->next); 1;})
> 
> and, when it is used as a truth value, say "hey, that's always true" and
> then elide the call to prefetch()?  We've no way of telling because this
> remains gcc-specific territory, afaik.

The prefetch() definitions I found are "asm volatile".  So, as I
understand it, the compiler is not supposed to remove it, just as it
would not be permitted to remove something that could have a side effect.

> (cc Paul for rcu stuff)

Given my track record with simple functions of late :-/ I will beat this
one up a bit...

							Thanx, Paul

[PATCH 4/4] hlist_for_each_entry_continue simplification

[Stephen Hemminger]

[-- Attachment #1: rcu-continue.patch --]
[-- Type: text/plain, Size: 2921 bytes --]

All the users of hlist_for_each_entry_continue had to intialize pos
before use; change API so pos is a pure temporary variable which matches
the usage of other xxxx_for_each_entry routines.

Signed-off-by: Stephen Hemminger <shemminger@vyatta.com>

--- a/include/linux/list.h	2008-02-12 15:09:17.000000000 -0800
+++ b/include/linux/list.h	2008-02-12 15:09:53.000000000 -0800
@@ -944,7 +944,7 @@ static inline void hlist_add_after_rcu(s
  * @member:	the name of the hlist_node within the struct.
  */
 #define hlist_for_each_entry_continue(tpos, pos, member)		 \
-	for (pos = (pos)->next;						 \
+	for (pos = (tpos)->member.next;					 \
 	     pos && ({ prefetch(pos->next); 1;}) &&			 \
 		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 	     pos = pos->next)
@@ -999,7 +999,7 @@ static inline void hlist_add_after_rcu(s
  * @member:	the name of the hlist_node within the struct.
  */
 #define hlist_for_each_entry_continue_rcu(tpos, pos, member)		\
-	for (pos = (pos)->next;						\
+	for (pos = (tpos)->member.next;					\
 	     rcu_dereference(pos) && ({ prefetch(pos->next); 1;}) &&	\
 		     ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 	     pos = pos->next)
--- a/include/net/sock.h	2008-02-12 15:09:17.000000000 -0800
+++ b/include/net/sock.h	2008-02-12 15:09:53.000000000 -0800
@@ -381,7 +381,7 @@ static __inline__ void sk_add_bind_node(
 	if (__sk && ({ node = &(__sk)->sk_node; 1; })) \
 		hlist_for_each_entry_from(__sk, node, sk_node)
 #define sk_for_each_continue(__sk, node) \
-	if (__sk && ({ node = &(__sk)->sk_node; 1; })) \
+	if (__sk) \
 		hlist_for_each_entry_continue(__sk, node, sk_node)
 #define sk_for_each_safe(__sk, node, tmp, list) \
 	hlist_for_each_entry_safe(__sk, node, tmp, list, sk_node)
--- a/net/ipv4/fib_hash.c	2008-02-12 15:09:17.000000000 -0800
+++ b/net/ipv4/fib_hash.c	2008-02-12 15:09:53.000000000 -0800
@@ -883,7 +883,7 @@ static struct fib_alias *fib_get_next(st
 
 	/* Advance FN. */
 	if (fn) {
-		struct hlist_node *node = &fn->fn_hash;
+		struct hlist_node *node;
 		hlist_for_each_entry_continue(fn, node, fn_hash) {
 			iter->fn = fn;
 
--- a/net/xfrm/xfrm_policy.c	2008-02-12 15:09:17.000000000 -0800
+++ b/net/xfrm/xfrm_policy.c	2008-02-12 15:09:53.000000000 -0800
@@ -577,7 +577,7 @@ int xfrm_policy_insert(int dir, struct x
 
 	read_lock_bh(&xfrm_policy_lock);
 	gc_list = NULL;
-	entry = &policy->bydst;
+
 	hlist_for_each_entry_continue(policy, entry, bydst) {
 		struct dst_entry *dst;
 
--- a/net/ipv4/fib_trie.c	2008-02-12 15:09:46.000000000 -0800
+++ b/net/ipv4/fib_trie.c	2008-02-12 15:12:21.000000000 -0800
@@ -2333,7 +2333,6 @@ static void *fib_trie_seq_next(struct se
 
 	/* walk rest of this hash chain */
 	h = tb->tb_id & (FIB_TABLE_HASHSZ - 1);
-	tb_node = &tb->tb_hlist;
 	hlist_for_each_entry_continue_rcu(tb, tb_node, tb_hlist) {
 		n = trie_get_first(iter, tb);
 		if (n)

-- 
Stephen Hemminger <shemminger@vyatta.com>

Re: [PATCH 4/4] hlist_for_each_entry_continue simplification

[David Miller]

From: Stephen Hemminger <shemminger@vyatta.com>
Date: Tue, 12 Feb 2008 16:50:46 -0800

> All the users of hlist_for_each_entry_continue had to intialize pos
> before use; change API so pos is a pure temporary variable which matches
> the usage of other xxxx_for_each_entry routines.
> 
> Signed-off-by: Stephen Hemminger <shemminger@vyatta.com>

linux/list.h changes need to be reviewed on linux-kernel and
merged into Linus's tree via some means other than the
networking tree.

I just got chewed out for a similar issue wrt. the rcupdate.h
changes of yesterday and thus have to remove them from my
tree.