Skip to contentSkip to conversation

fib_trie: update (redo)

PATCH In review Stephen Hemminger 2 participants 6 messages Feb 13, 2008 – Feb 18, 2008

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

cover fib_trie: update (redo)

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.

Signature · 1 line
Stephen Hemminger <[email protected]>
#1 lore raw

PATCH 1/3 fib_trie: move statistics to debugfs

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.

---
 net/ipv4/Kconfig    |    9 ++-
 net/ipv4/fib_trie.c |  127 +++++++++++++++++++++++++++++++++-------------------
 2 files changed, 86 insertions(+), 50 deletions(-)
net/ipv4/Kconfig +5 -4
@@ -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
net/ipv4/fib_trie.c +81 -46

256 lines not on this page · raw message

Signature · 1 line
Stephen Hemminger <[email protected]>
maintainer
#2 lore raw

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

From: Stephen Hemminger <[email protected]>
Date: Wed, 13 Feb 2008 11:58:06 -0800

Quoted 4 lines

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.

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.

#3 lore raw

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

Quoted 6 lines · On Sun, 17 Feb 2008 22:26:55 -0800 (PST) David Miller <[email protected]>…

From: Stephen Hemminger <[email protected]>
Date: Wed, 13 Feb 2008 11:58:06 -0800

Quoted 3 lines

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.

Quoted 7 lines
Quoted 1 line

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

#4 lore raw

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

In reply to Stephen Hemminger

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
---
 net/ipv4/fib_trie.c |  106 ++++++++++++++++++++++++++------------------------
 1 files changed, 55 insertions(+), 51 deletions(-)
net/ipv4/fib_trie.c +53 -49
@@ -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, ", ");
 			}
 		}
 	}
Signature · 1 line
Stephen Hemminger <[email protected]>
#5 lore raw

PATCH 3/3 fib_trie: print statistics for multiple tables

In reply to Stephen Hemminger

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

net/ipv4/fib_trie.c +100 -87
@@ -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;
Signature · 1 line
Stephen Hemminger <[email protected]>