Re: [PATCH 9/9] fix sparse warnings
Robert Olsson a écrit : Thanks for hacking and improving and the trie... another idea that could be also tested. If we look into routing table we see that most leafs only has one prefix Main: Aver depth: 2.57 Max depth: 7 Leaves: 231173 ip route | wc -l 241649 Thats 231173/241649 = 96% with the current Internet routing. How about if would have a fastpath and store one entry direct in the leaf struct this to avoid loading the leaf_info list in most cases? One could believe that both lookup and dump could improve. You mean to include one "leaf_info" inside leaf structure, so that we can access it without cache line miss ? -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 9/9] fix sparse warnings
Eric Dumazet writes: > > Thats 231173/241649 = 96% with the current Internet routing. > > > > How about if would have a fastpath and store one entry direct in the > > leaf struct this to avoid loading the leaf_info list in most cases? > > > > One could believe that both lookup and dump could improve. > > > You mean to include one "leaf_info" inside leaf structure, so that we > can access it without cache line miss ? Yes. Cheers --ro -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 9/9] fix sparse warnings
Thanks for hacking and improving and the trie... another idea that could be also tested. If we look into routing table we see that most leafs only has one prefix Main: Aver depth: 2.57 Max depth: 7 Leaves: 231173 ip route | wc -l 241649 Thats 231173/241649 = 96% with the current Internet routing. How about if would have a fastpath and store one entry direct in the leaf struct this to avoid loading the leaf_info list in most cases? One could believe that both lookup and dump could improve. Cheers. --ro Stephen Hemminger writes: > Remember that the code should be optimized for lookup, not management > operations. We ran into this during testing (the test suite was looking > for number of routes), thats why I put in the size field. > > The existing dump code is really slow: > > 1) FIB_TRIE Under KVM: > load 164393 routes 12.436 sec > ip route | wc -l12.569 sec > grep /proc/net/route25.357 sec > > 99% of the cpu time is spent in nextleaf() during these dump operations. > > 2) FIB_HASH Under KVM: > load 164393 routes 10.833 sec > ip route | wc -l1.981 sec > grep /proc/net/route0.204 sec -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 9/9] fix sparse warnings
From: Stephen Hemminger <[EMAIL PROTECTED]> Date: Sat, 12 Jan 2008 13:09:46 -0800 > On Sat, 12 Jan 2008 12:16:13 +0100 > Eric Dumazet <[EMAIL PROTECTED]> wrote: > > > [FIB]: Reduce text size of net/ipv4/fib_trie.o > > > > In struct tnode, we use two fields of 5 bits for 'pos' and 'bits'. > > Switching to plain 'unsigned char' (8 bits) take the same space > > because of compiler alignments, and reduce text size by 435 bytes > > on i386. > > > > On i386 : > > $ size net/ipv4/fib_trie.o.before_patch net/ipv4/fib_trie.o > > textdata bss dec hex filename > >13714 4 64 1378235d6 net/ipv4/fib_trie.o.before > >13279 4 64 133473423 net/ipv4/fib_trie.o > > > > Signed-off-by: Eric Dumazet <[EMAIL PROTECTED]> > > > > I agree they should not have been bitfields in the first place. Applied. -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 9/9] fix sparse warnings
From: Stephen Hemminger <[EMAIL PROTECTED]> Date: Fri, 11 Jan 2008 22:45:22 -0800 > Make FIB TRIE go through sparse checker without warnings. > > Signed-off-by: Stephen Hemminger <[EMAIL PROTECTED]> Also applied, thanks. -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 9/9] fix sparse warnings
On Sat, 12 Jan 2008 12:16:13 +0100 Eric Dumazet <[EMAIL PROTECTED]> wrote: > Stephen Hemminger a écrit : > > Make FIB TRIE go through sparse checker without warnings. > > > > Signed-off-by: Stephen Hemminger <[EMAIL PROTECTED]> > > Hi Stephen > > While reviewing your patches (and fib code) I had some questions : > > 1) I was wondering isn't trie_collect_stats() a potential cpu hog > (big latency) ? > > 2) struct tnode layout > If tnode->bits is large enough, we allocate a big area > of memory but roughly use only first half of it. > We could use a better scheme with an extra indirection. For small > nodes, we use space right after tnode, but for big nodes, we allocate > a power of two set of pages, to exactly match the memory need. > > 3) 'pos' and 'bits' fields of 'struct tnode' might be converted to > plain uchar, instead of 5-bits fields, to reduce complexity for > generated code. > > 4) full_children & empty_children being 'unsigned short', > we probably are limited to 2^15 elements, but I could not > find this limit enforced somewhere. > > [FIB]: Reduce text size of net/ipv4/fib_trie.o > > In struct tnode, we use two fields of 5 bits for 'pos' and 'bits'. > Switching to plain 'unsigned char' (8 bits) take the same space > because of compiler alignments, and reduce text size by 435 bytes > on i386. > > On i386 : > $ size net/ipv4/fib_trie.o.before_patch net/ipv4/fib_trie.o > textdata bss dec hex filename >13714 4 64 1378235d6 net/ipv4/fib_trie.o.before >13279 4 64 133473423 net/ipv4/fib_trie.o > > Signed-off-by: Eric Dumazet <[EMAIL PROTECTED]> > I agree they should not have been bitfields in the first place. -- Stephen Hemminger <[EMAIL PROTECTED]> -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 9/9] fix sparse warnings
On Sat, 12 Jan 2008 12:16:13 +0100 Eric Dumazet <[EMAIL PROTECTED]> wrote: > Stephen Hemminger a écrit : > > Make FIB TRIE go through sparse checker without warnings. > > > > Signed-off-by: Stephen Hemminger <[EMAIL PROTECTED]> > > Hi Stephen > > While reviewing your patches (and fib code) I had some questions : > > 1) I was wondering isn't trie_collect_stats() a potential cpu hog > (big latency) ? > > 2) struct tnode layout > If tnode->bits is large enough, we allocate a big area > of memory but roughly use only first half of it. > We could use a better scheme with an extra indirection. For small > nodes, we use space right after tnode, but for big nodes, we allocate > a power of two set of pages, to exactly match the memory need. > > 3) 'pos' and 'bits' fields of 'struct tnode' might be converted to > plain uchar, instead of 5-bits fields, to reduce complexity for > generated code. > > 4) full_children & empty_children being 'unsigned short', > we probably are limited to 2^15 elements, but I could not > find this limit enforced somewhere. Remember that the code should be optimized for lookup, not management operations. We ran into this during testing (the test suite was looking for number of routes), thats why I put in the size field. The existing dump code is really slow: 1) FIB_TRIE Under KVM: load 164393 routes 12.436 sec ip route | wc -l 12.569 sec grep /proc/net/route 25.357 sec 99% of the cpu time is spent in nextleaf() during these dump operations. 2) FIB_HASH Under KVM: load 164393 routes 10.833 sec ip route | wc -l 1.981 sec grep /proc/net/route 0.204 sec -- Stephen Hemminger <[EMAIL PROTECTED]> -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 9/9] fix sparse warnings
From: Eric Dumazet <[EMAIL PROTECTED]> Date: Sat, 12 Jan 2008 12:16:13 +0100 > We could use a better scheme with an extra indirection. Unfortunately, indirection will likely have a negative impact upon performance. We go only as fast as the number of memory references made by this code. > 3) 'pos' and 'bits' fields of 'struct tnode' might be converted to > plain uchar, instead of 5-bits fields, to reduce complexity for > generated code. This seems reasonable, I'll likely apply this. -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 9/9] fix sparse warnings
Stephen Hemminger a écrit :
Make FIB TRIE go through sparse checker without warnings.
Signed-off-by: Stephen Hemminger <[EMAIL PROTECTED]>
Hi Stephen
While reviewing your patches (and fib code) I had some questions :
1) I was wondering isn't trie_collect_stats() a potential cpu hog
(big latency) ?
2) struct tnode layout
If tnode->bits is large enough, we allocate a big area
of memory but roughly use only first half of it.
We could use a better scheme with an extra indirection. For small
nodes, we use space right after tnode, but for big nodes, we allocate
a power of two set of pages, to exactly match the memory need.
3) 'pos' and 'bits' fields of 'struct tnode' might be converted to
plain uchar, instead of 5-bits fields, to reduce complexity for
generated code.
4) full_children & empty_children being 'unsigned short',
we probably are limited to 2^15 elements, but I could not
find this limit enforced somewhere.
[FIB]: Reduce text size of net/ipv4/fib_trie.o
In struct tnode, we use two fields of 5 bits for 'pos' and 'bits'.
Switching to plain 'unsigned char' (8 bits) take the same space
because of compiler alignments, and reduce text size by 435 bytes
on i386.
On i386 :
$ size net/ipv4/fib_trie.o.before_patch net/ipv4/fib_trie.o
textdata bss dec hex filename
13714 4 64 1378235d6 net/ipv4/fib_trie.o.before
13279 4 64 133473423 net/ipv4/fib_trie.o
Signed-off-by: Eric Dumazet <[EMAIL PROTECTED]>
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index 2832610..4e91532 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -119,8 +119,8 @@ struct leaf_info {
struct tnode {
t_key key;
unsigned long parent;
- unsigned short pos:5; /* 2log(KEYLENGTH) bits needed */
- unsigned short bits:5; /* 2log(KEYLENGTH) bits needed */
+ unsigned char pos; /* 2log(KEYLENGTH) bits needed */
+ unsigned char bits; /* 2log(KEYLENGTH) bits needed */
unsigned short full_children; /* KEYLENGTH bits needed */
unsigned short empty_children; /* KEYLENGTH bits needed */
struct rcu_head rcu;
[PATCH 9/9] fix sparse warnings
Make FIB TRIE go through sparse checker without warnings.
Signed-off-by: Stephen Hemminger <[EMAIL PROTECTED]>
--- a/net/ipv4/fib_trie.c 2008-01-11 22:35:37.0 -0800
+++ b/net/ipv4/fib_trie.c 2008-01-11 22:41:57.0 -0800
@@ -653,7 +653,6 @@ static struct node *resize(struct trie *
static struct tnode *inflate(struct trie *t, struct tnode *tn)
{
- struct tnode *inode;
struct tnode *oldtnode = tn;
int olen = tnode_child_length(tn);
int i;
@@ -701,6 +700,7 @@ static struct tnode *inflate(struct trie
}
for (i = 0; i < olen; i++) {
+ struct tnode *inode;
struct node *node = tnode_get_child(oldtnode, i);
struct tnode *left, *right;
int size, j;
@@ -1037,8 +1037,7 @@ static struct list_head *fib_insert_node
/* Case 1: n is a leaf. Compare prefixes */
if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
- struct leaf *l = (struct leaf *) n;
-
+ l = (struct leaf *) n;
li = leaf_info_new(plen);
if (!li)
@@ -2231,6 +2230,7 @@ static struct node *fib_trie_get_idx(str
}
static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
+ __acquires(RCU)
{
struct fib_trie_iter *iter = seq->private;
struct fib_table *tb;
@@ -2273,6 +2273,7 @@ static void *fib_trie_seq_next(struct se
}
static void fib_trie_seq_stop(struct seq_file *seq, void *v)
+ __releases(RCU)
{
rcu_read_unlock();
}
--
Stephen Hemminger <[EMAIL PROTECTED]>
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
