[PATCH 0/3] fib_trie: update (redo)

[PATCH 0/3] fib_trie: update (redo)

[Stephen Hemminger]

This supersedes yesterday's changes. It doesn't change list.h
because that seems to make people queasy, even if it is a clone
of existing code.  Moves the trie related special files to debugfs.

-- 
Stephen Hemminger <shemminger@vyatta.com>

[PATCH 1/3] fib_trie: move statistics to debugfs

[Stephen Hemminger]

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

Don't want /proc/net/fib_trie and /proc/net/fib_triestat to become
permanent kernel space ABI issues, so move to the safer confines of debugfs.

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

---
 net/ipv4/Kconfig    |    9 ++-
 net/ipv4/fib_trie.c |  127 +++++++++++++++++++++++++++++++++-------------------
 2 files changed, 86 insertions(+), 50 deletions(-)

--- a/net/ipv4/Kconfig	2008-02-13 10:58:51.000000000 -0800
+++ b/net/ipv4/Kconfig	2008-02-13 10:59:06.000000000 -0800
@@ -85,11 +85,12 @@ endchoice
 config IP_FIB_HASH
 	def_bool ASK_IP_FIB_HASH || !IP_ADVANCED_ROUTER
 
-config IP_FIB_TRIE_STATS
-	bool "FIB TRIE statistics"
-	depends on IP_FIB_TRIE
+config IP_FIB_TRIE_DEBUG
+	bool "FIB TRIE debugging information"
+	depends on IP_FIB_TRIE && DEBUG_FS
 	---help---
-	  Keep track of statistics on structure of FIB TRIE table.
+	  Provides interface for looking at internal structure, and
+	  statistics on for the  FIB TRIE table.
 	  Useful for testing and measuring TRIE performance.
 
 config IP_MULTIPLE_TABLES
--- a/net/ipv4/fib_trie.c	2008-02-13 10:58:51.000000000 -0800
+++ b/net/ipv4/fib_trie.c	2008-02-13 11:33:43.000000000 -0800
@@ -68,6 +68,7 @@
 #include <linux/netdevice.h>
 #include <linux/if_arp.h>
 #include <linux/proc_fs.h>
+#include <linux/debugfs.h>
 #include <linux/rcupdate.h>
 #include <linux/skbuff.h>
 #include <linux/netlink.h>
@@ -126,7 +127,8 @@ struct tnode {
 	struct node *child[0];
 };
 
-#ifdef CONFIG_IP_FIB_TRIE_STATS
+#ifdef CONFIG_IP_FIB_TRIE_DEBUG
+
 struct trie_use_stats {
 	unsigned int gets;
 	unsigned int backtrack;
@@ -135,7 +137,6 @@ struct trie_use_stats {
 	unsigned int null_node_hit;
 	unsigned int resize_node_skipped;
 };
-#endif
 
 struct trie_stat {
 	unsigned int totdepth;
@@ -146,10 +147,11 @@ struct trie_stat {
 	unsigned int prefixes;
 	unsigned int nodesizes[MAX_STAT_DEPTH];
 };
+#endif
 
 struct trie {
 	struct node *trie;
-#ifdef CONFIG_IP_FIB_TRIE_STATS
+#ifdef CONFIG_IP_FIB_TRIE_DEBUG
 	struct trie_use_stats stats;
 #endif
 };
@@ -588,7 +590,7 @@ static struct node *resize(struct trie *
 
 		if (IS_ERR(tn)) {
 			tn = old_tn;
-#ifdef CONFIG_IP_FIB_TRIE_STATS
+#ifdef CONFIG_IP_FIB_TRIE_DEBUG
 			t->stats.resize_node_skipped++;
 #endif
 			break;
@@ -631,7 +633,7 @@ static struct node *resize(struct trie *
 		tn = halve(t, tn);
 		if (IS_ERR(tn)) {
 			tn = old_tn;
-#ifdef CONFIG_IP_FIB_TRIE_STATS
+#ifdef CONFIG_IP_FIB_TRIE_DEBUG
 			t->stats.resize_node_skipped++;
 #endif
 			break;
@@ -1341,7 +1343,7 @@ static int check_leaf(struct trie *t, st
 		err = fib_semantic_match(&li->falh, flp, res,
 					 htonl(l->key), mask, plen);
 
-#ifdef CONFIG_IP_FIB_TRIE_STATS
+#ifdef CONFIG_IP_FIB_TRIE_DEBUG
 		if (err <= 0)
 			t->stats.semantic_match_passed++;
 		else
@@ -1376,7 +1378,7 @@ static int fn_trie_lookup(struct fib_tab
 	if (!n)
 		goto failed;
 
-#ifdef CONFIG_IP_FIB_TRIE_STATS
+#ifdef CONFIG_IP_FIB_TRIE_DEBUG
 	t->stats.gets++;
 #endif
 
@@ -1403,7 +1405,7 @@ static int fn_trie_lookup(struct fib_tab
 		n = tnode_get_child(pn, cindex);
 
 		if (n == NULL) {
-#ifdef CONFIG_IP_FIB_TRIE_STATS
+#ifdef CONFIG_IP_FIB_TRIE_DEBUG
 			t->stats.null_node_hit++;
 #endif
 			goto backtrace;
@@ -1546,7 +1548,7 @@ backtrace:
 			pn = parent;
 			chopped_off = 0;
 
-#ifdef CONFIG_IP_FIB_TRIE_STATS
+#ifdef CONFIG_IP_FIB_TRIE_DEBUG
 			t->stats.backtrack++;
 #endif
 			goto backtrace;
@@ -2022,7 +2024,8 @@ struct fib_table *fib_hash_table(u32 id)
 	return tb;
 }
 
-#ifdef CONFIG_PROC_FS
+#ifdef CONFIG_IP_FIB_TRIE_DEBUG
+
 /* Depth first Trie walk iterator */
 struct fib_trie_iter {
 	struct seq_net_private p;
@@ -2147,7 +2150,7 @@ static void trie_collect_stats(struct tr
 }
 
 /*
- *	This outputs /proc/net/fib_triestats
+ *	This outputs debugfs/fib/triestats
  */
 static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
 {
@@ -2189,7 +2192,6 @@ static void trie_show_stats(struct seq_f
 	seq_printf(seq, "Total size: %u  kB\n", (bytes + 1023) / 1024);
 }
 
-#ifdef CONFIG_IP_FIB_TRIE_STATS
 static void trie_show_usage(struct seq_file *seq,
 			    const struct trie_use_stats *stats)
 {
@@ -2204,7 +2206,7 @@ static void trie_show_usage(struct seq_f
 	seq_printf(seq, "skipped node resize = %u\n\n",
 		   stats->resize_node_skipped);
 }
-#endif /*  CONFIG_IP_FIB_TRIE_STATS */
+
 
 static void fib_trie_show(struct seq_file *seq, const char *name,
 			  struct trie *trie)
@@ -2214,9 +2216,7 @@ static void fib_trie_show(struct seq_fil
 	trie_collect_stats(trie, &stat);
 	seq_printf(seq, "%s:\n", name);
 	trie_show_stats(seq, &stat);
-#ifdef CONFIG_IP_FIB_TRIE_STATS
 	trie_show_usage(seq, &trie->stats);
-#endif
 }
 
 static int fib_triestat_seq_show(struct seq_file *seq, void *v)
@@ -2242,18 +2242,12 @@ static int fib_triestat_seq_show(struct 
 
 static int fib_triestat_seq_open(struct inode *inode, struct file *file)
 {
-	int err;
-	struct net *net;
+	struct net *net = maybe_get_net((struct net *)inode->i_private);
 
-	net = get_proc_net(inode);
-	if (net == NULL)
+	if (!net)
 		return -ENXIO;
-	err = single_open(file, fib_triestat_seq_show, net);
-	if (err < 0) {
-		put_net(net);
-		return err;
-	}
-	return 0;
+
+	return single_open(file, fib_triestat_seq_show, net);
 }
 
 static int fib_triestat_seq_release(struct inode *ino, struct file *f)
@@ -2447,8 +2441,19 @@ static const struct seq_operations fib_t
 
 static int fib_trie_seq_open(struct inode *inode, struct file *file)
 {
-	return seq_open_net(inode, file, &fib_trie_seq_ops,
-			    sizeof(struct fib_trie_iter));
+	struct net *net = maybe_get_net((struct net *)inode->i_private);
+	struct fib_trie_iter *iter;
+
+	if (!net)
+		return -ENXIO;
+
+	iter = __seq_open_private(file, &fib_trie_seq_ops, sizeof(*iter));
+	if (!iter) {
+		put_net(net);
+		return -ENOMEM;
+	}
+	iter->p.net = net;
+	return 0;
 }
 
 static const struct file_operations fib_trie_fops = {
@@ -2459,6 +2464,51 @@ static const struct file_operations fib_
 	.release = seq_release_net,
 };
 
+
+static struct dentry *fib_debug, *trie_debug, *triestat_debug;
+
+static void __net_init trie_debug_init(struct net *net)
+{
+	fib_debug = debugfs_create_dir("fib", NULL);
+	if (!fib_debug || IS_ERR(fib_debug))
+		goto out1;
+
+	trie_debug = debugfs_create_file("trie", S_IRUGO, fib_debug,
+					 net, &fib_trie_fops);
+	if (!trie_debug || IS_ERR(trie_debug))
+		goto out2;
+
+	triestat_debug = debugfs_create_file("triestat", S_IRUGO, fib_debug,
+					     net, &fib_triestat_fops);
+	if (!triestat_debug || IS_ERR(triestat_debug))
+		goto out3;
+
+	hold_net(net);
+	return;
+out3:
+	debugfs_remove(trie_debug);
+out2:
+	debugfs_remove(fib_debug);
+out1:
+	fib_debug = NULL;
+}
+
+static void __net_exit trie_debug_exit(struct net *net)
+{
+	if (!fib_debug)
+		return;
+
+	debugfs_remove(trie_debug);
+	debugfs_remove(triestat_debug);
+	debugfs_remove(fib_debug);
+	put_net(net);
+}
+#else
+#define trie_debug_init(n)
+#define trie_debug_exit(n)
+#endif
+
+#ifdef CONFIG_PROC_FS
 struct fib_route_iter {
 	struct seq_net_private p;
 	struct trie *main_trie;
@@ -2632,34 +2682,19 @@ static const struct file_operations fib_
 	.llseek = seq_lseek,
 	.release = seq_release_net,
 };
+#endif /* CONFIG_PROC_FS */
 
 int __net_init fib_proc_init(struct net *net)
 {
-	if (!proc_net_fops_create(net, "fib_trie", S_IRUGO, &fib_trie_fops))
-		goto out1;
-
-	if (!proc_net_fops_create(net, "fib_triestat", S_IRUGO,
-				  &fib_triestat_fops))
-		goto out2;
-
 	if (!proc_net_fops_create(net, "route", S_IRUGO, &fib_route_fops))
-		goto out3;
+		return -ENOMEM;
 
+	trie_debug_init(net);
 	return 0;
-
-out3:
-	proc_net_remove(net, "fib_triestat");
-out2:
-	proc_net_remove(net, "fib_trie");
-out1:
-	return -ENOMEM;
 }
 
 void __net_exit fib_proc_exit(struct net *net)
 {
-	proc_net_remove(net, "fib_trie");
-	proc_net_remove(net, "fib_triestat");
 	proc_net_remove(net, "route");
+	trie_debug_exit(net);
 }
-
-#endif /* CONFIG_PROC_FS */

-- 
Stephen Hemminger <shemminger@vyatta.com>

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

[Stephen Hemminger]

[-- Attachment #1: fib-trie-format.patch --]
[-- Type: text/plain, Size: 5134 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(-)

--- a/net/ipv4/fib_trie.c	2008-02-13 11:33:43.000000000 -0800
+++ b/net/ipv4/fib_trie.c	2008-02-13 11:41:23.000000000 -0800
@@ -2334,46 +2334,57 @@ static void fib_trie_seq_stop(struct seq
 	rcu_read_unlock();
 }
 
+/* print left side of tree */
 static void seq_indent(struct seq_file *seq, int n)
 {
-	while (n-- > 0) seq_puts(seq, "   ");
+	while (n-- > 0)
+		seq_puts(seq, "  |");
 }
 
-static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
+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",
+};
+
+static void fib_trie_show_alias(struct seq_file *seq, const struct fib_alias *fa)
 {
-	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";
+	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:
-		snprintf(buf, len, "scope=%d", s);
-		return buf;
+		seq_printf(seq, "scope:%d", fa->fa_scope);
 	}
-}
 
-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",
-};
+	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);
 
-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;
+	if (fa->fa_tos)
+		seq_printf(seq, " tos:%#x", fa->fa_tos);
 }
 
 /* Pretty print the trie */
@@ -2396,10 +2407,8 @@ static int fib_trie_seq_show(struct seq_
 		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;
@@ -2407,24 +2416,19 @@ static int fib_trie_seq_show(struct seq_
 		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;
 
-			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.%d.%d.%d/%d ",
+				   NIPQUAD(val), li->plen);
 
-				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');
+			list_for_each_entry_rcu(fa, &li->falh, fa_list) {
+				fib_trie_show_alias(seq, fa);
+				if (list_is_last(&fa->fa_list, &li->falh))
+					seq_putc(seq, '\n');
+				else
+					seq_puts(seq, ", ");
 			}
 		}
 	}

-- 
Stephen Hemminger <shemminger@vyatta.com>

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

[Stephen Hemminger]

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

Make debugfs/fib/trie and debugfs/fib/triestat handle
multiple (alternate) route tables.

Note: this usage of seq_file doesn't need/want SEQ_START_TOKEN

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

--- a/net/ipv4/fib_trie.c	2008-02-13 11:41:23.000000000 -0800
+++ b/net/ipv4/fib_trie.c	2008-02-13 11:41:35.000000000 -0800
@@ -2029,14 +2029,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;
@@ -2081,34 +2080,29 @@ 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 trie *t)
 {
-	struct node *n ;
+	struct node *n;
 
 	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)
@@ -2119,8 +2113,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, t); n; n = trie_get_next(&iter)) {
 		if (IS_LEAF(n)) {
 			struct leaf *l = (struct leaf *)n;
 			struct leaf_info *li;
@@ -2207,35 +2200,46 @@ static void trie_show_usage(struct seq_f
 		   stats->resize_node_skipped);
 }
 
-
-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)
 {
-	struct trie_stat stat;
-
-	trie_collect_stats(trie, &stat);
-	seq_printf(seq, "%s:\n", name);
-	trie_show_stats(seq, &stat);
-	trie_show_usage(seq, &trie->stats);
+	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 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) {
+			struct trie *t = (struct trie *) tb->tb_data;
+			struct trie_stat stat;
+
+			if (!t)
+				continue;
+
+			fib_table_print(seq, tb);
+
+			trie_collect_stats(t, &stat);
+			trie_show_stats(seq, &stat);
+			trie_show_usage(seq, &t->stats);
+		}
+	}
 
 	return 0;
 }
@@ -2265,23 +2269,30 @@ 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,
+						(struct trie *) tb->tb_data);
+			     n; n = trie_get_next(iter))
+				if (pos == idx++) {
+					iter->tb = tb;
+					return n;
+				}
+		}
 	}
+
 	return NULL;
 }
 
@@ -2289,43 +2300,52 @@ 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);
+	/* next node in same table */
+	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);
+	while ( (tb_node = rcu_dereference(tb->tb_hlist.next)) ) {
+		tb = hlist_entry(tb_node, struct fib_table, tb_hlist);
+		n = trie_get_first(iter, (struct trie *) tb->tb_data);
+		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, (struct trie *) tb->tb_data);
+			if (n)
+				goto found;
+		}
+	}
 
 	return NULL;
+
+found:
+	iter->tb = tb;
+	return n;
 }
 
 static void fib_trie_seq_stop(struct seq_file *seq, void *v)
@@ -2393,15 +2413,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 1/3] fib_trie: move statistics to debugfs

[David Miller]

From: Stephen Hemminger <shemminger@vyatta.com>
Date: Wed, 13 Feb 2008 11:58:06 -0800

> Don't want /proc/net/fib_trie and /proc/net/fib_triestat to become
> permanent kernel space ABI issues, so move to the safer confines of debugfs.
> 
> Signed-off-by: Stephen Hemminger <shemminger@vyatta.com>

Stephen, the cat is already out of the bag.  We already export this
thing so if you want to export different stuff you'll have to provide
it via some other means, somewhere else.

Thanks.

Re: [PATCH 1/3] fib_trie: move statistics to debugfs

[Stephen Hemminger]

On Sun, 17 Feb 2008 22:26:55 -0800 (PST)
David Miller <davem@davemloft.net> wrote:

> From: Stephen Hemminger <shemminger@vyatta.com>
> Date: Wed, 13 Feb 2008 11:58:06 -0800
> 
> > Don't want /proc/net/fib_trie and /proc/net/fib_triestat to become
> > permanent kernel space ABI issues, so move to the safer confines of debugfs.
> > 
> > Signed-off-by: Stephen Hemminger <shemminger@vyatta.com>
> 
> Stephen, the cat is already out of the bag.  We already export this
> thing so if you want to export different stuff you'll have to provide
> it via some other means, somewhere else.
> 
> Thanks.

Are we stuck with the format problems?
  * crappy tree printout
  * not printing other tables