fib_trie related patches for 2.6.25
Subsystems (6)
cover fib_trie related patches for 2.6.25
More trie cleanups with some RCU related changes as well. Patches are against net-2.6 tree (sent already to netdev).
Signature · 1 line
Stephen Hemminger <[email protected]>
PATCH 1/4 rcu_assign_pointer: null check fix
Goofed on last change, should avoid barrier only on rcu_assign_pointer(p, NULL)
--- include/linux/rcupdate.h | 13 +++++++------ 1 files changed, 7 insertions(+), 6 deletions(-)
include/linux/rcupdate.h +1 -1
@@ -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); \ })
Signature · 1 line
Stephen Hemminger <[email protected]>
David Miller
maintainerRe: [PATCH 1/4] rcu_assign_pointer: null check fix
From: Stephen Hemminger <[email protected]>
Date: Tue, 12 Feb 2008 16:50:43 -0800
Quoted 3 lines
Goofed on last change, should avoid barrier only on
rcu_assign_pointer(p, NULL)Signed-off-by Stephen Hemminger <[email protected]>
Like the original change this needs to be merged upstream outside of the networking tree, sorry.
Re: [PATCH 1/4] rcu_assign_pointer: null check fix
In reply to Stephen HemmingerOn 13-02-2008 01:50, Stephen Hemminger wrote:
...
include/linux/rcupdate.h struct rcu_head { · line 181
Quoted 8 lines
include/linux/rcupdate.h +1
-1@@ -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) \
Isn't it a bit safer with this Paul's version yet?:
+ if (!__builtin_constant_p(v) || (v)) \
Jarek P.
PATCH 2/4 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 +55 -51
@@ -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,", " ); } } }
Signature · 4 lines
1.5.3.8 -- Stephen Hemminger <[email protected]>
Re: [PATCH 2/4] fib_trie: improve output format for /proc/net/fib_trie
Quoted 19 lines · On Tue, 12 Feb 2008 16:50:44 -0800 Stephen Hemminger <[email protected]>…
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
Quoted 8 lines
| +-- 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 unicastisn'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
Quoted 32 lines · Andrew Morton
Quoted 19 lines · On Tue, 12 Feb 2008 16:50:44 -0800 Stephen Hemminger <[email protected]>…
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 localQuoted 9 lines
| +-- 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
Quoted 4 lines
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.
Quoted 3 lines
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
In reply to Stephen HemmingerMake /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
--- include/linux/list.h | 13 ++++ net/ipv4/fib_trie.c | 186 ++++++++++++++++++++++++++++---------------------- 2 files changed, 117 insertions(+), 82 deletions(-)
include/linux/list.h +13 -0
@@ -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__ */
net/ipv4/fib_trie.c +100 -84
276 lines not on this page · raw message
Signature · 1 line
Stephen Hemminger <[email protected]>
Re: [PATCH 3/4] fib_trie: print statistics for multiple tables
include/linux/list.h static inline void hlist_add_after_rcu(s · line 1005
Quoted 11 lines · On Tue, 12 Feb 2008 16:50:45 -0800 Stephen Hemminger <[email protected]>…
include/linux/list.h +11
-0+/** +* 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
Quoted 16 lines · Andrew Morton
include/linux/list.h static inline void hlist_add_after_rcu(s · line 1005
Quoted 11 lines · On Tue, 12 Feb 2008 16:50:45 -0800 Stephen Hemminger <[email protected]>…
include/linux/list.h +11
-0+/** +* 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
Quoted 5 lines
({ 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.
Quoted 1 line
(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
In reply to Stephen HemmingerAll 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.
include/linux/list.h +2 -2
@@ -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)
include/net/sock.h +1 -1
@@ -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)
net/ipv4/fib_hash.c +1 -1
@@ -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;
net/xfrm/xfrm_policy.c +1 -1
@@ -577,7 +577,7 @@ int xfrm_policy_insert(int dir, struct xread_lock_bh (&xfrm_policy_lock); gc_list =NULL ; - entry = &policy->bydst; +hlist_for_each_entry_continue (policy, entry, bydst) {struct dst_entry *dst;
net/ipv4/fib_trie.c +0 -1
@@ -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)
Signature · 1 line
Stephen Hemminger <[email protected]>
David Miller
maintainerRe: [PATCH 4/4] hlist_for_each_entry_continue simplification
From: Stephen Hemminger <[email protected]>
Date: Tue, 12 Feb 2008 16:50:46 -0800
Quoted 5 lines
All the users of
hlist_for_each_entry_continuehad to intialize pos before use; change API so pos is a pure temporary variable which matches the usage of otherxxxx_for_each_entryroutines.Signed-off-by Stephen Hemminger <[email protected]>
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.