fib_trie: update (redo)
Subsystems (3)
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]>
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]>
David Miller
maintainerRe: [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_trieand/proc/net/fib_triestatto become permanent kernel space ABI issues, so move to the safer confines of debugfs.Signed-off-by Stephen Hemminger <[email protected]>
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
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 -0800Quoted 3 lines
Don't want
/proc/net/fib_trieand/proc/net/fib_triestatto become permanent kernel space ABI issues, so move to the safer confines of debugfs.
Quoted 7 lines
Quoted 1 line
Signed-off-by Stephen Hemminger <[email protected]>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
PATCH 2/3 fib_trie: improve output format for /proc/net/fib_trie
In reply to Stephen HemmingerMake 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 seqrcu_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]>
PATCH 3/3 fib_trie: print statistics for multiple tables
In reply to Stephen HemmingerMake 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 trmemset (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]>